Представление шахматной доски в компьютерных программах

User interface board representations

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.

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. A problem with this approach arises during move generation. Each move has to be checked to ensure it does not wrap around an edge of the board, which significantly slows 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).

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 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 computationally 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.

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".

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.

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, 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.