Author: Eugene Nalimov
Date: 21:00:39 01/15/99
Go up one level in this thread
On January 15, 1999 at 22:09:04, Robert Hyatt wrote:
>On January 15, 1999 at 21:26:17, Vincent Diepeveen wrote:
>
>>On January 13, 1999 at 07:19:54, Ernst A. Heinz wrote:
>>
>>>On January 13, 1999 at 06:13:30, Vincent Diepeveen wrote:
>>>>
>>>> [...]
>>>
>>>Vincent,
>>>
>>>As usual you spread your own fallible impressions and interpretations
>>>in a style that suggests they are proven facts. But indeed they are *not*.
>>
>>I have not seen a single function using bitboards making attacktables
>>for every square indeed.
>>In crafty there is only this: a function that gives
>>soemthing for a single square.
>>
>>I thought a long time about it.
>
>Vincent this is simply wrong, and your reasoning is badly flawed. In early
>versions of crafty I did _full_ attack bitmaps, so that at any point I had
>the bitmaps for the squares attacked from a specific square, and bitmaps for
>every square showing which squares were attacking _it_. I kept these
>incrementally updated.
>
>I later decided that the 'latter' bitboard wasn't being used much and I got
>rid of it as it did have a cost. But that cost was some 10% overall speed,
>which I could instantly get back if I wanted to use such bitmaps.
>
>your bad logic seems to be "if it isn't in Crafty now, it isn't practical
>or it can't be done." On the contrary, if it isn't done in crafty now, it
>is because I don't need (or don't want) the information at present. Nothing
>says others don't / can't do it...
>
>
>
>>
>>>The "problems" (rumors?) you allude to in the post only show that you have
>>>*not* understood what bitboards are capable of and how to handle them
>>>effciently. You are of course free to criticize Bob's coding style and his
>>>design decisions in "Crafty". However, only inexperienced and narrow-minded
>>>people draw general conclusions from just a single example (i.e. the source
>>
>>Now comon comon, who is narrowminded here.
>>I've investigated bitboards just as close as you did.
>>
>>Note that i don't have a 64 bits processor, and even if i did, then still
>>i never might sell a 64 bits program, where never is defined as next
>>few years.
>>
>
>I doubt you have 'investigated bitboards just as close as you did' (you talking
>to Ernst here). It took me a _long_ time to become competent with them. It
>did _not" come by just taking a casual look. I had to start writing code and
>spend a year figuring out how to do everything I wanted to do efficiently. An
>example: I teach a programming language course and cover some esoteric things
>like APL, prolog, etc. And when I assign a program in (say) APL to students,
>I get "C" programs back. Syntactically APL. But algorithmically C. That is
>what happens with bitboards for a good while, _until_ the writer becomes used to
>'thinking bitboards'. (or thinking parallel search or whatever). These topics
>are _not_ something you spend a day or two thinking about and then say "been
>there, done that, it's no good..."
>
>
>
>
>>>code of "Crafty"). There are many ways to do things differently with bitboards
>>>and rotated bitboards than in "Crafty". Overall, your post mainly elaborates
>>>on some of Bob's design decisions which you deem non-optimal.
>>>
>>>The only real disadvantage of bitboards at the moment is the obvious penalty
>>>of 64-bit integers on 32-bit CPUs which comes hand in hand with unfortunately
>>>limited compilers and programming environments.
>>
>>I'm waiting for your implementation of attacktables using bitboards.
>>
>>I'll even be friendly to you allowing it to do at a 64 bits machine,
>>which next 5 years is probably out of wallet of 99% of the people,
>>but then please don't use macros, but write it all out. Macros confuse people,
>>giving them the idea that it is simple using bitboards, where actually
>>every macro is a kind of hacked thing in bitboards imho. Please post again
>>how you count the number of bits in a bitboard?
>>
>
>
>well known:
>
> int c;
> while (bitboard) {
> c++;
> bitboard=bitboard&(bitboard-1);
> }
> return(c);
>
>is best for small numbers of bits.
>
>Or on intel machines, even better is this piece of code:
>
>PopCnt:
> movl 4(%esp), %ecx
> xorl %eax, %eax
> testl %ecx, %ecx
> jz l1
>l0:
> leal -1(%ecx), %edx
> incl %eax
> andl %edx, %ecx
> jnz l0
>l1:
> movl 8(%esp), %ecx
> testl %ecx, %ecx
> jz l3
>l2:
> leal -1(%ecx), %edx
> incl %eax
> andl %edx, %ecx
> jnz l2
>l3:
> ret
>
>that is _very_ fast...
>
As Vincent hates assembly, I suggest equivalent C code. I
didn't tried it, but more or less sure that VC will generate
exactly the same code:
ULONG ulTemp;
int cBits;
ul = ((ULONG *) &bitboard) [0];
cBits = 0;
while (ul)
{
ul &= ul - 1;
cBits ++;
}
ul = ((ULONG *) &bitboard) [1];
while (ul)
{
ul &= ul - 1;
cBits ++;
}
You can get rid of casts by using union.
Eugene
>
>>At a PII-450 diep generates 250k attacktables a second in the position
>>after openingsposition+1.e4,e5 2.d4,d5
>>
>>I'm only using C code. Not a single assembler instruction is in my code,
>>as far as i know your bitboards are written in C? In that case
>>there is no unfair comparision.
>>
>>An attacktable is a table in my program of
>>int attacktable [2][64];
>>First i clean the attacktable, then i store for every piece all attacks.
>>
>>that includes
>> a) piece that attacks (what square it is from)
>> b) number of attackers (clear i guess)
>> c) kind of piece (pawn,knight,bishop ...)
>>
>>I need this to evaluate in my program, as it evaluates also 'relationships'
>>between pieces and mobility is also depending upon it.
>>
>>My mobility goes like this: i loop over all squares of a piece, including
>>xray squares and then find out how important control over such a square is
>>depending on all kind of chessknowlege where info from attacktable is
>>used using lookup of attacktable[c][sq] where sq are all squares that
>>need to be considered. And as i use this 'attacktable' info a lot,
>>i therefore store it in this a simple way in [2][64] array.
>>Every time i use something out of my attacktable i definitely not
>>am gonna add all values of the different bitboards *just* to get the
>>number of attackers. That would slow down my program *considerable*.
>>
>>Now a problem using attacktables with mobility is:
>>if you do all squares at once (otherwise bitboards not rewarding),
>>that is kind of tough, considering that values are different
>>for every square. So where i simply count a+b+c, where probably
>>a != b != c then you run into problems, as for a range of -50 to +50
>>you need to do 101 bitboard counts.
>>
>
>
>I've already pointed out that this is false. Here's how to do this _fast_ on
>the cray:
>
>first compute the bitmap for the squares a piece on "sq" attacks. This produces
>a set of zeros and ones. Then take a static const array sqval[64] where you
>have filled in the value of attacking each square. IE values for e4 d5 and
>so forth, and _every_ value can be different.
>
>ON the cray, we use the vector load instruction, but from this sqval[] array
>we only load the values with 1's set in the according bitmap. We sum these
>and we are done, and it takes roughly 20 clock cycles to get the first value
>from the sq array, and assuming you have 20 squares you attack, the entire
>thing will complete in about 50 clock ticks _total_.
>
>Not very inefficient. So things you think are hard are actually trivial on the
>right hardware...
>
>
>
>>I have given you exact data here.
>>2 challenges are posted, from which one is very clear.
>>The second one, mobility is simply impossible, unless you use the same
>>code i use, so you get every square out of the bitboard and then run
>>through the evaluation code, which means that the loop used over the squares
>>is different, but not the evaluation code
>
>better rethink that 'impossible' as I just did it and I did it many times
>faster than you can. On the cray of course. Or on the intel i860/960...
>which are commodity micros.
>
>
>
>>
>>Assuming in all cases lossless code,
>>Greetings,
>>Vincent
>>
>>>=Ernst=
>>
>>Please guys don't moderate Ernst too tough, if you do, then i dunno
>>what Heinz thinks of himselve.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.