Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Problems with BitBoards?

Author: KarinsDad

Date: 07:23:32 01/13/99

Go up one level in this thread


On January 13, 1999 at 06:13:30, Vincent Diepeveen wrote:

[snip]

>
>If you want to make a huge evaluation using mobility and attacktables
>extensively in search, then you have a major problem with bitboards.

Strange. I have both attacktables and BitBoards in my code and I haven't
experienced any problems.

>
>Also at 32 bits machines bitboards are rather slow compared to 0x88 and
>similar datastructures.
>
>Main problem has to do with L1 cache and especially the 64 bits length
>of a bitboard. Rotated bitboards in crafty eat 1MB
>of storage. Doesn't fit in 32 kb L1 cache of PII or Xeon... :)

Well, there you have it. My bitboards take up 144 bytes (not including my 2-3
KBytes of lookup tables), so they should work in cache.

>
>However as you see in crafty enough speed gets left, so problems come
>down to the point that you can't write a huge evaluation using bitboards,
>as at a certain point speed isn't the weakest chain anymore.

Since I have attacktables, a larger evaluation should be possible.

>
>In crafty mobility is the summation of squares attacked. If you want to
>do something with a square, like discriminating between a1 and d4 (controlling
>d4 is generally better than controlling a1), then bitboards give problems.
>
>Finally, bitboards are programmed for every piece.
>When i generate moves, i am using general code, so 10 lines of
>code which works for every piece. Crafty has written down
>code for every piece, so it's more work using bitboards too, both in
>coding and in updating datastructure.

This is true. My BitBoard code for rooks, queens, and bishops is different than
the code for pawns, knights, and kings.

>
>Then there is the huge coding needed for the functions. In order to be
>compatible, crafty is using functions which *should* be a single instruction.
>
>Like if i do: a = (b|c|d)^0x07;
>then that's about 18 characters, new line not included.
>In crafty that's much more than 18. To do b|c at a bitboard it needs a special
>function calls, and no matter whether it gets translated to '|', you
>need to write down that code.
>
>that means that 10 lines of C code from me are usually equivalent with at least
>20 lines in crafty. then there is some nice comment, which makes it another
>10 lines larger. so 3:1 would be rather good.
>
>That means that to do something bitboards is way more work.
>
>However, main problem is that it is not practical to create metaknowledge
>like attacktables using bitboards.

This, however, is false since I am doing it.

>
>To say that it's slow using bitboards would be an understatement.
>

That I do not know for sure. Preliminary tests indicate that they are slightly
faster, however, I haven't tweaked them yet either.

>In my evaluation i'm using extensively whether a square is attacked (so for
>example f6-f5 is not possible, which makes f6 weak). Therefore i generate
>a whole attacktable for both colors. Now very important is to know
>for example the number of attackers.
>
>To get my # attackers i just need an array lookup, so in a[i] somehow is my
>info.

Yup. That's how I'm doing it.

>
>Now that works rather quickly.
>
>only quicker is to have info in a variable.
>
>Using bitboards however generating an attacktable for all squares is
>a big disaster. In fact that function is not even in crafty. It has
>only a function that can collect the attackers of a single square,
>and that's already rather slow.
>
>So main problem of bitboards is implied in the definition. It has only
>a single bit for a square, so it's tough to represent more info about something
>than a single bit. Now if you need a 'collection' of info, like #attackers
>and what kind of attackers, then a single bit is not gonna give what you want.
>
>the more knowledgeable a program gets, the less helpful a bitboard-only
>solution is.
>
>So my advice is to not start with bitboards. That keeps away attention
>from other things, like making an evaluation.
>
>If i think out a new pattern, then i want to write it down in a recognizable
>form. My experience is that there are usual bugs in patterns when they are
>new. For me it's very important to be able to easily read my code back
>when concerning evaluation. Bitboard code is tough to read. Very tough.
>
>So concluding bitboards are:
>   - a lot of work
>   - slower
>   - needing always the newest machine to get that huge data
>     quickly out of L2 cache (Pro,Xeon,Tanner...)
>   - hard to read
>   - if you want to make a huge evaluation then you can't do some
>     very necessary things with mobility and attackers.
>
>Vincent Diepeveen
>

[snip]

Thanks Vincent. Cannot say that I've seen your kind of results, but it's good to
know where other people ran into problems.

KarinsDad :)



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.