Author: Vincent Diepeveen
Date: 03:13:30 01/13/99
Go up one level in this thread
On January 12, 1999 at 19:34:14, KarinsDad wrote:
>On January 12, 1999 at 08:59:33, Robert Hyatt wrote:
>
>>On January 12, 1999 at 00:11:02, KarinsDad wrote:
>>
>>>On January 11, 1999 at 23:01:45, Robert Hyatt wrote:
>>>
>>>>On January 11, 1999 at 17:44:02, Bruce Moreland wrote:
>
>Ok, it's good to know that BitBoards have no major technical drawbacks (at least
>none were mentioned). However, Bruce mentioned that "Too many try bitboards and
>give up after they find some difficulties they can't overcome". This implies
>that there are some design or implementation difficulties which can be handled,
>but are there lurking in wait.
>
>Does anyone know what these may be so that I'm forewarned?
If you want to make a huge evaluation using mobility and attacktables
extensively in search, then you have a major problem with bitboards.
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... :)
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.
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.
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.
To say that it's slow using bitboards would be an understatement.
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.
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
>Thanks in advance :)
>
>KarinsDad
>
>>>>
>>>>The main point here is 0x88, bitboards, or whatever, you *must* make a
>>>>commitment to doing the best you can do, for a period of time sufficient to
>>>>make sure you extract all there is to extract from the approach. Too many
>>>>try bitboards and give up after they find some difficulties they can't over-
>>>>come.
>>>
>>>What difficulties can be experienced with BitBoards? So far, they seem to work
>>>great (or at least accurately, I haven't yet cleaned them up for performance).
>>>Okay, you can drop the other shoe now.
>>>
>>>KarinsDad
>>>
>>
>>the approach works fine. I have been using it exclusively for about 4 years
>>now in Crafty. The problem is enumerating set bits into a list of to-squares
>>since we aren't yet using 64 bit architectures everywhere. The bsf/bsr
>>instructions work well on the newer pentium-II type processors, but only on 32
>>bit quantities, which means at present bitmaps are somewhat clumsy. But just
>>wait for 64 bit machines to come from Intel, or use a digital alpha, or MIPS
>>R10000, or a cray, and suddenly the bitmap advantage becomes quite real.
>>because we get much higher "information density"... since those processors pump
>>64 bits internally, programs not needing this waste density potential. Bitmaps
>>need all 64 bits moved around, and when we get it for "free" it begins to pay
>>off pretty well...
>>
>>
>>
>>
>>>
>>> Others try 0x88 and give up without ever realizing all the places it
>>>>is useful...
>>>>
>>>>classic mistake to try and give up too soon...
>>>>
>>>>
>>>>
>>>>>
>>>>>bruce
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.