Computer Chess Club Archives




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

Author: Vincent Diepeveen

Date: 11:37:49 01/16/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:
>>>> [...]
>>>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 talk in numbers Bob, not in "i have done something in the past".
You generate a bunch of different bitboards. Cool with me.

A) You miss number of attackers
B) you miss where the attacker comes from

Main thing is that i miss are numbers. Things can get
measured you know.

>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...

This has to do with how your tables look like. You need to
add all your bitmaps before you can do something useful with it.
That is a mainpoint. Please don't get personal, i am not insulting you
personal. I'm just talking about

a) how difficult bitboards are to work with
b) that you need 64 bits machines for it which are very expensive
   unless you want to buy an outdated 21164 533Mhz chip, with say a 1 gig
   harddisk in it (this advertisement here i see in this magazine offers
   it for the prize of 6000 dutch guilder (3500 dollar) a 1 GIG harddisk in
   it!! and 64 MB RAM).

c) that after the big effort of a and b it is not possible to do everything
   quickly with it and that it is definitely not faster.

>>>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

We don't doubt your insight in bitboards Bob. Please don't doubt my insight
either. That's a bad way of writing emails.

Don't forget i use a single bitboard for speeding up my pawn structure
evaluation. I take the best of all worlds. That's why
in the rest or the program i don't use bitboards.

>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..."

I'm not busy one day with my program either. We don't doubt your experience,
that still however doesn't give the objective reader clear numbers about
WHETHER you can do it.

It is very simple. Just dig up your old code and test it at your Xeon.
matter of a few minutes to run the old code imho and with your deep insight
easy to initialize the demanded arrays, then please count speed of it,
leave the code in crafty as a 'testroutine' and we know.

>>>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:

>        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
>        ret
>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

The problem is that according bitmaps. If value can range from -50 to 50
then you need to do this 101 times, because you need a bitcount for
every 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...

A rude way of mobility can be done quickly. NO doubt. Please don't talk
about the cray. We're talking general audience here. General audience
doesn't have a cray nor alpha 533 and also will not buy it.

In that respect crafty does a good job as it can be compiled at all

>>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.

I fear you didn't get the point, or simply are hiding it.

I have a big range of values here and a big bunch of chessknowledge
which decides which square gets what value, and that chessknowledge
is based on piece relationships and attackers and a lot of other things.

Please don't compare that with a rude "how many moves can i make" count.

I don't doubt we all generate that quickly. Actually in DIEP i generate
15 million move generations a second after 1.e4,e5 2.d4,d5 at a PII-450

>>Assuming in all cases lossless code,

This was my point. Your code is lossy to mine.

>>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.