Computer Chess Club Archives


Search

Terms

Messages

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

Author: Roberto Waldteufel

Date: 08:35:18 10/26/98

Go up one level in this thread



On October 26, 1998 at 09:20:05, Robert Hyatt wrote:

>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"...


Yes, the ranks and files are difficult with colour-split bitmaps, but I think it
is still possible to do this. If I understand your draft paper about this
(thanks for sending me this) correctly, you maintain four bitboard
representations of occupied squares (the rotated bitmaps), but for all other
bitmap data you always use the square standard ordering that puts the rank bits
together, ie a1-h1, then a2-h2 etc, so these other bitmaps have only the one
standard orientation. Now it seems to me that there is nothing special about the
ranks, and you could just as easily use any of the four directions as the
"standard" orientation in which all the other bitmaps are stored. For example,
you could choose a1-a8,b1-b8....h1-h8 as your standard ordering and it would
still work, except you would perhaps have to make minor changes to the way you
generate the pawn moves. Now suppose you choose one of the two diagonal
orientations to be the "standard". Then you can generate the bishop and knight
moves with 32-bit bitboards, and for the ranks and files, you get an index from
the appropriate ranks- or files- location bitmap, and then when you look up the
attack map in the table thus indexed, your attacked squares will be stored in
the new "standard orientation", ie one of the diagonals, so that either all
light squares precede all dark squares or vice versa. Then you step through two
mono-chromatic bitboards intstead of one big 64-bit bitboard. Since the two
32-bit bitboards would presumably be in contiguous memory, there would be no
problem in accessing both of these 32-bit bitmaps as a single 64-bit bitmap when
running on 64-bit hardware. Only the choice of standard orientation needs to
change in order to facilitate this. With the currant standard a1-h1, a2-h2 etc,
we could, using bitmaps for particular types of pieces, readily discover all the
pieces of that type in the White or the Black half of the board using 32-bit
operations, but I think there is far more opportunity to take advantage of a
diagonal standard ordering that allows all monochromatic sets of squares to be
handled this way instead of all sets of squares entirely in one player's half of
the board. After all, there are no pieces that stay always in one player's half
of the board, like the bishops always stay on the same monochromatic set, nor
are there any pieces that always alternate between each player's half of the
board like the knights always alternate between light and dark squares.

At the end of all this, however, I have my doubts that the savings would be very
large, since I think Pentiums can sometimes work on two 32-bit values in
parallel, but I am not sure whether or not this happens when I use 64-bit values
in my program. Certainly I have found the old standard order quite reasonable on
the Pentium, but I have only ever compared it to non-bitboard methods, so I
don't know how much of a saving I might achieve with rotated bitmaps and altered
standard ordering. It's an interesting problem to explore....:-)

Roberto



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.