Computer Chess Club Archives


Search

Terms

Messages

Subject: To bitboard or not to bitboard?

Author: Tord Romstad

Date: 11:37:44 08/30/03


My program has reached the stage where it is so complicated and ugly that I
no longer understand clearly how it works (it's rather miraculous that it
works at all), and there are many parts of the code which I am afraid of
touching because I am sure I will break something.  Besides, the program
is horribly slow, searching only about 120 kN/s on a PIV 2.4 GHz.

Because of this, I think it is time to throw away all the old code and
start from scratch.  Before I do this, I will consider replacing my
data structures with something more efficient.

Today, my board representation consists of a 256-byte array of squares
(visualised as a 16x16 board with the real board in the left half of
the middle 8 ranks) and a Phalanx-style piece list.  At every node in
the tree, I generate "attack tables" similar to those found in Rebel,
Phalanx and Diep (the tables are not updated incrementally).

I have never really liked bitboards, but because my next computer will
almost certainly be a PowerMac G5, I am considering to give them a try.
First, however, I have a few questions to the more experienced bitboard
users:

1. One of the things I dislike about bitboards (at least the modern
approach with rotated bitboards) is that even very simple operations
like generating moves seem to require either using huge lookup tables
(like in Crafty without -DCOMPACT_ATTACKS) or writing some extremely
complicated and unreadable code (like Crafty _with_ -DCOMPACT_ATTACKS).
Is there a way to use rotated bitboards without having big tables,
and still keeping the code short, clean and readable?

2. Another problem with bitboards is that there is no obvious way to
compute "weighted mobility".  While it is trivial to compute the number
of pseudo-legal moves for a piece with bitboards, this number is usually
not very interesting (at least not in my program).  In most cases, some
squares are much more valuable to attack than others.  Given a 64-byte
array of weights, and a bitboard of squares attacked by a piece, is there
a fast way to compute the "dot product"?  I have browsed the archive
and noticed that this question has been discussed numerous times before,
but I have never seen a good answer (Bob has explained a lot of times
how to do this on a Cray, which is not very useful to me).

3. I also dislike the fact that bitboards are much too big to be used
as indexes to lookup tables, and that extracting information from them
is often difficult to do without looping through all the 1 bits.  It is
easy to compute a bitboard of all pieces which attack a given square,
but in my evaluation I want to extract information about the number and
types of attackers in a small and compact bitfield (which can be used
as an index to a lookup table), while throwing away information about
the locations of all the attackers.  How do I achieve this with bitboards?

Tord




This page took 0.06 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.