Dec 14, 2006

[Guide] Board representation choice

The board representation is the heart of the chess program (the brain being the search algorithm :). It's important to have a board representation which makes for fast move generation, since this is basically what costs when calculating the moves.

There are basically three choices:
  • Simple arrays

  • The 0x88 method

  • Bitboards

Arrays: A chess board consists of 8x8 squares, so why not represent the board with an 8x8 array, containing a number representing a piece on each index.

You can make this work very well, but basically there are problems with speed. One of them being checking if a target-"square" is on the board or not (we don't want the bishops running off into outer space). There are solutions to this particular problem, like making it a 12x12 board instead and letting the extra squares represent "off-the-board"-squares.

But the real problems come when applying certain move generating techniques, which will be discussed at a later date.

So I scratched this approach

0x88: The representation I'm going to use. More about it in the next post.

Bitboards: This method uses a 64-bit sequence of zeros and ones (bits). Every bit states something about the board. Like every zero is an empty square and every one is a white pawn. Then you have a number of sequences to represent all the pieces on the board.

But you can also have the ones represent attacked squares for example, or a countless number of other information you might want to store.

This approach is very fast, especially using the 64-bit processors which calculates this extremely fast.

However it is a tad complicated to implement, so I'll leave it be for my next engine. :)

1 comment:

Anonymous said...

Some may feel squeamish about eating it, but rabbit has a fan base that grows as cooks discover how easy they are to raise — and how good the meat tastes.