Author: Bo Persson
Date: 03:42:03 08/31/03
Go up one level in this thread
On August 31, 2003 at 02:21:03, Steven Edwards wrote: >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. > The bitboard version is not only doing more than the non-bitboard version, there is also some overlap in the bitboard operations, meaning that some info is computed and stored several times: Bitboards in 1 & 3 hold the same info. Maybe you could remove one of them? Bitboards in 2 & 5 hold the same info. Perhaps you could remove some of them? For example, if you have one bitboard for diagonal sweepers (Q+B) and one for angular sweepers (Q+R) you can deduce the separate Q, R, and B positions from these. Bitboards in 4 hold the same info as bitboards in 6, just in a different way. Bitboards in 7 is sort of a cross reference for 6. Do you need both? If you alredy store the king squares, do you also need to update single bit bitboards for kings? Bo Persson
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.