Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Problems with BitBoards?

Author: Eugene Nalimov

Date: 17:26:26 01/12/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?
>
>Thanks in advance :)
>
>KarinsDad

IMHO, there are the following drawbacks:

(1) It's much harder to think in the bitboards terms; they are not
for the beginners. 0x88 approach, for example, can be explained in
one post (as it was done recently by both Bruce and Bob).

(2) (Maybe that's part of (1), too). Algorithms are not trivial.
For example, it takes some time to understand rotated bitboards.

(3) Large data structures are necessary. For example, the entire
search part of the "fast and dumb" chess program that don't use
bitboards and use mainly piece/square tables for evaluation
(something like Fritz, if everybody is correct and Fritz is really
such a program) can be fit into L1 cache on any modern x86 CPU -
both code and data. Craftys' tables are much larger - that's why
Crafty "likes" CPUs with fast L2 cache (PPro and Xeon).

(4) Bad support in the development tools. Few C compilers supports
64-bit integers on 32-bit platforms, and even in those few, often
code quality is much worse than for 32-bit integers, or there are
bugs in the code generators.

(5) Often chess program starts as modification of the existing
project (like Gnu Chess or TSCP). There are no bitboard programs
with source available let alone Crafty, and modifying Crafty
source is not for the beginners.

Eugene

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