Board representation (computer chess)
Board representation (computer chess)
Main page
1851807

Board representation (computer chess)

logo
Community Hub0 subscribers
What are your thoughts?
Be the first to start a discussion here.
Be the first to start a discussion here.
Board representation (computer chess)

Board representation in computer chess is a data structure in a chess program representing the position on the chessboard and associated game state. Board representation is fundamental to all aspects of a chess program including move generation, the evaluation function, and making and unmaking moves (i.e. search) as well as maintaining the state of the game during play. Several different board representations exist. Chess programs often utilize more than one board representation at different times, for efficiency. Execution efficiency and memory footprint are the primary factors in choosing a board representation; secondary considerations are effort required to code, test and debug the application.

Early programs used piece lists and square lists, both array based. Most modern implementations use a more elaborate but more efficient bit array approach called bitboards which map bits of a 64-bit word or double word to squares of the board.

A full description of a chess position, i.e. the position "state", must 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. Without this information, models may repeat the position despite having a winning advantage, resulting in an excessive amount of draws.

The board state may also contain secondary derived information like which pieces attack a square; for squares containing pieces, which spaces are attacked or guarded by that piece; which pieces are pinned; and other convenient or temporary state.

The board state is associated with each node of the game tree, representing a position arrived at by a move, whether that move was played over the board, or generated as part of the program's search. It is conceptually local to the node, but may be defined globally, and incrementally updated from node to node as the tree is traversed.

Some of the very earliest chess programs working with extremely limited amounts of memory maintained serial lists (arrays) of the pieces in a conveniently searchable order, like largest to smallest; associated with each piece was its location on the board as well as other information, such as squares representing its legal moves. There were several lists, one set for white pieces and another for black pieces. The lists were usually divided into pieces and pawns. This was a compact representation because most squares of the board are unoccupied, but inefficient because acquiring information about the relationship of pieces to the board or to each other was tedious. Piece lists are still used by many of today's programs in conjunction with a separate board representation structure, to give serial access to the pieces without searching the board.

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. This scheme is called mailbox addressing.

See all
User Avatar
No comments yet.