Board representation (chess)

In computer chess, software developers must choose a data structure to represent chess positions on the chessboard. Several data structures exist, collectively known as board representations. Chess engines often utilize more than one board representation at different times, for efficiency.

A full description of a chess position, i.e. the position "state", should contain the following elements:

Board representation typically does not include the status of the threefold repetition draw rule. To determine this rule, a complete history of the game from the last irreversible action (capture, pawn movement, or castling) needs to be maintained, and so, is generally tracked in separate data structures.

Some of the very earliest chess programs were working with extremely limited amounts of memory, such that even the 64 memory locations required to represent a chess board was too much to spend. These early programs would instead maintain lists of the locations of the up to 16 black and white pieces. Piece lists are still used by many of today's programs in conjunction with a separate board representation structure to speed up access to the pieces. Instead of looping through 64 (or more) squares to find all of the pieces, piece lists give instant access to the pieces.

One of the simplest ways to represent a board is to create an 8x8 two-dimensional array (or, equivalently, a 64 element one-dimensional array). Each array element would identify what piece occupied the given square, or alternatively, if the square is empty. A common encoding is to consider 0 as empty, positive as white, and negative as black, e.g., white pawn +1, black pawn −1, white knight +2, black knight −2, white bishop +3, and so on.

A problem with this approach arises during move generation. Each move has to be checked to ensure it is on the board, significantly slowing down the process. One solution is to use a 12x12 array instead, with the outer edges filled with, say, the value 99. During move generation, the operation to check for a piece on the destination square will also indicate whether the destination square is off the board.

Better memory usage can be achieved with a 10x12 array, which provides the same functionalities as a 12x12 one by overlapping the leftmost and rightmost edge files (which are marked as off-the-board). Some chess engines use 16x16 arrays to improve the speed of the rank and file number conversion and allow some special coding tricks for attacks etc.

...
Wikipedia