Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Efficient Bitboard Implementation on 32-bit Architecture

Author: Robert Hyatt

Date: 06:20:05 10/26/98

Go up one level in this thread


On October 25, 1998 at 23:19:09, Roberto Waldteufel wrote:

>
>On October 25, 1998 at 19:28:54, Robert Hyatt wrote:
>
>>On October 25, 1998 at 19:16:05, Roberto Waldteufel wrote:
>>
>>>Hi all,
>>>
>>>Has anyone tried this, or thought of trying this before?
>>>
>>>The main drawback of 32-bit CPU's for bitboards is that each time you need to
>>>step through the bits in a bitboard you have to step through two 32-bit values,
>>>since that is all that will fit in a register. I have an idea that partially
>>>overcomes this problem. It is based on the observation that many of the
>>>bitboards used in move generation are mono-chromatic, by which I mean that the
>>>1's are either all light squares or all dark squares. For example, bishop moves,
>>>pawn captures and double pawn moves are always to a square of the same colour as
>>>the origin square, and knight moves and single pawn moves are always to a square
>>>of opposite colour to the origin square. I therefore propose a bitboard
>>>structure consisting of two 32-bit unsigned integers, one for the light squares
>>>and the other for the dark squares. If rotated bitboards are to be used, then
>>>the bits could be aligned for one set of diagonals, and a second pair of
>>>bitboards aligned for the other diagonals (ranks and files would be done same as
>>>before, only diagonals would need reorganising). Then when polling the bits of
>>>an attack map to find the moves for minor pieces, only one 32-bit bitboard is
>>>needed to hold all the destination squares, and generating pawn captures by
>>>means of shifting and logical ANDing can easily be divided into light-square
>>>captures and dark-square captures. I have not yet tried this, but I see no
>>>reason why it should not work. Of course, it does nothing to help rook-moves
>>>(including rook-type queen moves) or king moves, but these could be generated
>>>with no more work than is needed in a normal a1-h1,a2-b2,......a8-h8 ordering of
>>>the squares. Nevertheless, if some of the generation can be compressed to 32-bit
>>>operations instead of 64, it must surely help to some extent. Any comments?
>>>
>>>Roberto
>>
>>
>>
>>it's interesting to think about this... but it does break the "rotated bitmap"
>>idea which is to get all squares along a rank/file/diagonal into adjacent bits.
>>This would mean we'd need a few more bitmaps to work around this...
>>
>>certainly worth trying, however...
>
>I don't see how it breaks the rotated bitboards. You store all the light-squared
>diagonals in two distinct 32-bit bitboards, one for each direction of diagonal,
>and all the dark-squared diagonals in two similar 32-bit bitboards exactly like
>you do at present, except instead if interleaving the light- and dark-squared
>diagonals, you just have to keep them separate (4 x 32 bits instead of 2 x 64
>bits). The rank and file bitmaps can stay as they are. That way, you still have
>all the bits on any one diagonal adjacent in the appropriate 32-bit bitmap. This
>would of course require that you first test the origin or target square to see
>whether it is light or dark, but thereafter you get your index from 32-bit
>operations instead of 64-bit ones. Unless you are using the rotated bitmaps in
>some other way I do not realise, I think this would work OK for generating the
>bishop moves, diagonal queen moves and knight moves, regardles of whether you
>generate based on to-square (eg MVV/LVA capture generation) or on to-square. Of
>course, it is pretty pointless on your 64-bit machine, but you have 32-bit
>Crafty versions as well that might benefit from splitting the diagonals into two
>sets of 32 bits. I don't know if it would make a big difference or not, but I
>can't see how it would interfere with your current implementation to split the
>diagonals like this - you would just have to recalculate the attack arrays once
>and it should work right away. Then, if all runs well, you could start trying to
>speed up the access code for 32-bit versions without needing to have a different
>data structure from the 64-bit Crafty.
>
>I think I will fool around with some of this stuff to see if I can make it work
>OK. I never feel happy with an idea until I see it up and running....:-)



the problem is the ranks/files.. because they won't be adjacent in such bitmaps,
and the "rotated" approach depends on this being true so that you
can find the state of one rank or file in 1 eight-bit "chunk"...



This page took 0.02 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.