Author: Steven Edwards
Date: 23:21:03 08/30/03
The portable C++ CT toolkit has classes for describing positions either with or
without bitboard representation in use. Here are the results of running both of
them for enumerating the 119,060,324 movepaths of length six from the initial
position on a 800 MHz G4 PPC notebook:
Non bitboard:
Frequency 1.07069 MHz
Period 933.98 ns
Cycles per node 747.184
Bitboard:
Frequency 342.689 KHz
Period 2.9181 us
Cycles per node 2334.48
(There is no use of rotated bitboards, nor of any kind of machine or OS specific
techniques.)
Since the bitboard mode is doing everything the non bitboard mode is doing, plus
more, we can see that the additional cost for bitboard manipulation is roughly
twice the cost of the shared portion of the work.
Is it worth it? The answer depends on what is done with the additional
information provided by the bitboard database at each node. In CT, both modes
provide all of the following:
1. A 64 entry array with the current board contents.
2. The active color.
3. The castling availability status.
4. The en passant target square.
5. The halfmove clock.
6. The fullmove number (Items 1-6 together are the binary equivalent of FEN).
7. The hash key for the main transposition table.
8. The hash key for the pawn transposition table.
9. The location squares of the kings.
10. The material balance for both sides.
11. A two way linked list of the moves leading to the position.
12. A two way linked list of the main transposition table hash keys of the
previous positions.
In additon, the bitboard mode adds the entire bitboard database which includes:
1. The BB of occupied squares.
2. The BB of squares occupied by sweep [QRB] men.
3. For each color, the BB of squares occupied by that color.
4. For each color, the BB of squares attacked by that color.
5. For each of the 12 (2 x 6) man kinds, the BB of squares occupied by that man
kind.
6. For each square, the BB of squares attacked from that square.
7. For each square, the BB of squares attacking to that square.
Having the additional BB database items make writing fast and sophisticated
positional evaluation code easy. Having both the attack-from and attack-to
bitboards helps with implementing an exchange resolver. Staged move generation
and move ordering becomes much easier with the BB database present.
Overall, the time and work saved at each node with bitboards increases as the
processing at each node becomes more complex. If a program's evaluaton routine
is only something like:
score = material[active] - material[passive];
then bitboards are not all that useful. But if the evaluation has dozens to
hundreds of terms, then having the BB datbase present to help parallelize the
evaluation can more than pay for the effort to provide the BB database at each
node.
Keep in mind that the above benchmarks were done on a 32 bit machine. I would
expect that a recompilation for a 64 bit machine would double the BB processing
rate. The same recompilation for a non bitboard program might have no rate
increase at all.
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.