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.[1] 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.

For User interface board representations, see Forsyth-Edwards Notation and Portable Game Notation.

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.

Board state

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

• The location of each piece on the board
• Whose turn it is to move
• Status of the 50-move draw rule. The name of this is sometimes a bit confusing, as it is 50 moves by each player, and therefore 100 half-moves, or ply. For example, if the previous 80 half-moves passed without a capture or a pawn move, the fifty-move rule will kick in after another twenty half-moves.
• Whether either player is permanently disqualified to castle, both kingside and queenside.
• If an en passant capture is possible.

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.

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.

Types

Array based

Piece lists

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.

Square list

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.

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.[1][2]

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).[1][2] 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.

0x88 method

Main article: 0x88

The 0x88 method takes advantage of the fact that a chessboard's 8x8 dimensions are an even power of two (i.e. 8 squared). The board uses a one-dimensional array of size 16x8 = 128, numbered 0 to 127 rather than an array of size 64. It is basically two boards next to each other, the actual board on the left while the board on the right would contain illegal territory. The binary layout for a legal board coordinate's rank and file within the array is 0rrr0fff (The r's are the 3 bits used to represent the rank. The f's for the file). For example, 0x71 (binary 01110001) would represent the square b8 (in Algebraic notation). When generating moves from the main board, one can check that a destination square is on the main board before consulting the array simply by ANDing the square number with hexadecimal 0x88 (binary 10001000). A non-zero result indicates that the square is off the main board. In addition, the difference between two squares' coordinates uniquely determines whether those two squares are along the same row, column, or diagonal (a common query used for determining check).[1][3]

Bitboards

Main article: Bitboard

A more efficient but more elaborate board representation than the array-based structures is the bitboard. A bitboard is a 64-bit sequence of bits (0 or 1), which indicates the absence or presence (false or true) of some state of each space on the board. A board position can then be represented using a series of bitboards. For example, a series of bitboards for each piece type, for each side, can represent the board position.

The advantage to this representation is the ability to use bit parallel operations upon the 64-bit entities instead of iteration to manipulate and derive information about the state of the board. This makes maximal use of the hardware available, especially as 64-bit processors have become mainstream.

A substantive advantage of bitboards is that enables maps for the spaces attacked by each type of piece on each space of the board to be pre-collated and stored in a table, so that possible moves of the piece can be retrieved in a single memory fetch of the attack map for the square on which the piece resides which, excluding spaces occupied by friendly pieces (one bitwise operation), yields the legal moves of the piece. But the moves of the sliding pieces (rooks, bishops, queens) are indeterminate because the moves of these pieces depend on the configuration of other pieces on the board. So special and complex data structures have been devised to represent their moves.

Rotated bitboards

Rotated bitboards is a move generation technique for the sliding pieces that uses rotated copies of a bitboard to place spaces (bits) in a file or diagonal into adjacent bits analogous to the bits representing a rank. These bits can be extracted and used as an index into a table to obtain the map of spaces attacked by these pieces. The bitboard is rotated 90° for file indexing and either 45° or -45° for diagonal indexing. Rotating a chessboard is conceptually challenging, and rotating a bitboard is computational inelegant, but the transformation avoids serially enumerating the piece moves, or a lengthy sequence of shifting and masking a bitboard of the attack map of the piece to take into account the board configuration.

Direct lookup

The masked ranks, files and diagonals of sliding pieces can be used via a hash function to directly index a table of precomputed attack vectors based on the occupancy bits in the masked portion. One such scheme that uses a perfect hash function along with tricks to minimize the potential size of the table that must be stored in memory, is called "magic bitboards".

Transposition table

A transposition table is a cache of previously seen positions, and associated evaluations, in a game tree generated by a computer game playing program. For fast searching of the table, a hash function may be used, such as Zobrist hashing, to speed finding matching boards.[4]

Other methods

Other methods such as Compact Chessboard Representation (CCR) have been proposed, but none has gained acceptance.

CCR uses 4 bits per square to represent the occupancy of the square,[Notes 1] an entire rank can be represented in 32 bits, and the board in 8 registers (with an additional one for remaining position information). The occupancy code for a square can be dialed out of a register and added to the program counter to index a jump table, branching directly to code to generate moves for the type of piece on this square (if any). Although the program is longer than for conventional move generation methods, no checks for the edge of the board are required, and no moves off the board are possible, increasing move generation speed.

The drawbacks of CCR are: 1) dependency on 32-bit word size; 2) availability of at least 9 free registers to the API; 3) necessity of assembly programming on a CISC architecture to access the registers; 4) non-portability of assembly application.

Notes

1. There are 6 types of pieces: king, queen, rook,bishop,knight,pawn for each of black and white plus unoccupied square, for a total of 13 states, representable in 4 bits or 2⁴=16 possible codes.

References

1. Hyatt, Robert. "Chess program board representations". Archived from the original on 12 February 2013. Retrieved 15 January 2012.
2. Frey, Peter W., ed. (1983) [1977], "An introduction to computer chess", Chess Skill In Man and Machine, Springer–Verlag, pp. 55–56
3. 0x88 method. Bruce Moreland
4. Albert Lindsey Zobrist, A New Hashing Method with Application for Game Playing, Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, (1969).