Computer Chess Club Archives




Subject: Efficient Bitboard Implementation on 32-bit Architecture

Author: Roberto Waldteufel

Date: 16:16:05 10/25/98

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?


This page took 0.01 seconds to execute

