Computer Chess Club Archives




Subject: Re: BitBoard challenge to Ernst A. Heinz and bitboard fans - no moderation

Author: Robert Hyatt

Date: 19:09:04 01/15/99

Go up one level in this thread

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:
>>> [...]
>>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) {

is best for small numbers of bits.

Or on intel machines, even better is this piece of code:

        movl    4(%esp), %ecx
        xorl    %eax, %eax
        testl   %ecx, %ecx
        jz      l1
        leal    -1(%ecx), %edx
        incl    %eax
        andl    %edx, %ecx
        jnz     l0
        movl    8(%esp), %ecx
        testl   %ecx, %ecx
        jz      l3
        leal    -1(%ecx), %edx
        incl    %eax
        andl    %edx, %ecx
        jnz     l2

that is _very_ fast...

>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,
>Please guys don't moderate Ernst too tough, if you do, then i dunno
>what Heinz thinks of himselve.

This page took 0.01 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.