This article discusses some alternative ways of representing a chess board with pieces in computer memory.
Arrays
The most straighforward representation of a chess board is as a 64 elements long array. Each element represents a square of the chess board that either is empty or is occupied by a chess piece. There are 12 different chess pieces and one value is needed to represent an empty square; this fits into 4 bits per square. For efficiency reasons in most cases one byte per square will be used.
In addition to the position of all pieces, the following information is needed:
-
- the side to move
-
- the position of an en passant square if present
-
- flags indication possibility of short/long castling for both sides
Variations on the array theme are to use 10×12 and 16×16 chess boards. The idea here is to have cheap checks to see if a move crosses a border. In the 10×12 case, the 8×8 board is centered on the 10×12 board and enclosed with occupied squares. In the 16×16 case, we can encode square numbers as 0rrr0ccc (binary), where rrr is the row number and ccc the column number (file); crossing a border will turn one of the 0 bits into a 1, which can be detected with an AND operation.
Minimal coding
When using 4 bits per square, an array representation will have a total size of 256 bits. It is possible to squeeze a chess position in less bits by using Huffman coding techniques. For example (C is colour of the piece):
-
- Empty square: 0
-
- Pawn: 10C
-
- Bishop: 1100C
-
- Knight: 1101C
-
- Rook: 1110C
-
- Queen: 11110C
-
- King: 11111C
This gives a total size of 32 + 48 + 20 + 20 + 20 + 12 + 12 = 164 bits. Some additional bits will be necessary to indicate castle status and side to move.
An alternative for this is to store the sequence of moves from the opening position. Again by using Huffman coding this can be very compact, although it is difficult to give an upper bound or average size.
Such representations are not very useful for use in a chess program, but may be useful e.g. for storing positions in a database.
Bit boards
Bit board representations are based on the observation that a chess board has 64 squares and that there is a trend towards 64 bit computers. One computer word can then represent a boolean condition for each square of the chess board. Examples of such conditions are:
-
- Square is occupied by certain piece.
-
- Square is occupied by white (or black).
-
- Square is attacked by white (or black).
The advantage of bit boards is that boolean operations can be performed on all squares in parallel. The disadvantage is that updating all bit board information after each move can be costly. This is especially true for attack information (which sqaures are attacking a square).
Rotated bitboards
Normally a bitboard will have one byte per rank of the chess board. This allows efficient determination of rook attacks across a rank by using a lookup table indexed by square and rank-occupied-byte (we need the occupied bitboard because rook attacks stop at the first occupied square in the line of sight).
A simple variation of the normal bitboard is to use a 90 degree rotated occupied bitboard, where each file of the chess board will be represented by one byte. In the same way as above, the rook attacks across a file can be determined.
We can also introduce 45 degrees left and right rotated occupied bitboards, where a left or right diagonal will be stored in one byte (actually in less than one byte). Using these bitboards and a table lookup we can determine bishop attacks. Queen attacks are obtained by or-ing the rook and bishop attacks.
