Author: Gerd Isenberg
Date: 14:07:47 08/30/03
Go up one level in this thread
On August 30, 2003 at 14:37:44, Tord Romstad wrote:
>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:
Thinking bitboards takes some (hard) time, but you will don't regret it.
Not for generating moves, but for eval patterns and abstraction level.
Generating pattern is a rather loopless and uncondition task with botboards.
Unconditional bitwise, arithmetic and shift operations with bitboards have most
often a loop equivalent in other approaches.
One possible weakness of bitboards is the "conversion" from bitboard metric to
square index metric. If you have a particular square index "sq", the single
populated bitboard has the value of 2**sq == 1<<sq. Addition like sq+x is done
by some shift. Wraps are handled by appopriate and before or after shifting.
sq^x (e.g. for some morroring) in square metric is equivalent to rotate in
bitboard metric.
>
>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?
With G5 (how many 64-bit registers?) or Opteron in mind, you may have a closer
look at Kogge-Stone-fill routines attack generation.
It is very usefull to get disjoint directions wise attacks, e.g. obviously pawns
left and right attacks, as well all 8 directions for sliders.
These algotithms may be implemented for several directions as well as piecesets
in parallel or interlaced, as long you have 64-bit registers free.
http://peter.fendrich.net/Terra/Terra%20Help-1647.htm
These simple file-fill routines are great to get a lot of pawn patterns, like
backward, passers, isolanis, etc.:
BitBoard fillUp(BitBoard bb)
{
bb |= (bb<<8);
bb |= (bb<<16);
bb |= (bb<<32);
return bb;
}
BitBoard fillDown(BitBoard bb)
{
bb |= (bb>>8);
bb |= (bb>>16);
bb |= (bb>>32);
return bb;
}
>
>2. Another problem with bitboards is that there is no obvious way to
>compute "weighted mobility".
For center control, one may use three parallel popcounts.
All squares (8*8), no boarder squares(6*6), and combined shifted extended center
(4*4) and center (2*2). So center is weighted by 4, extended by 3, remaining
none boarder by 2 and boarder squares by 1. Due to independent instruction
scheduling, three (or four e.g. squares "near" king) interlaced popcounts are
very fast, not much slower than a single one with a lot dependencies!
>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"?
The obvious approach is a "slow" bitscan loop, e.g.:
BitBoard bb = ....;
int score = 0;
while (bb)
{
BitBoard lsb = bb & -bb; // isolate bit
bb ^= lsb; // reset bit
unsigned idx = (int)((lsb * deBruijn ) >> (64 - 6));
score += table[idx];
}
e.g. with one of millions 64-bit deBruijns:
const BitBoard deBruijn = 0x03f08c5392cd5dbd;
But one should avoid or delay such loops,
e.g. by unrolling and conditional write.
> 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?
There are other solutions. You may have sets of "tabu" squares, sets controlled
by pawns, by light pieces, exclusivly by queen or king, etc. And sets of e.g.
more than triple attacked, triple, double (may include xrays) and single
attacks. This is fine for eval, considering enprised or hanging pieces, SEE and
move sorting.
Gerd
>
>Tord
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.