Board representation (computer chess)

Last updated

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.

Contents

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:

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

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

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] [3] 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

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] [4]

Bitboards

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

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

Other methods

Other methods such as Compact Chessboard Representation (CCR) have been proposed,[ citation needed ] 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 24=16 possible codes.

Related Research Articles

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. There are 92 solutions. The problem was first posed in the mid-19th century. In the modern era, it is often used as an example problem for various computer programming techniques.

Baroque chess is a chess variant invented in 1962 by Robert Abbott. In 1963, at the suggestion of his publisher, he changed the name to Ultima, by which name it is also known. Abbott later considered his invention flawed and suggested amendments to the rules, but these suggestions have been substantially ignored by the gaming community, which continues to play by the 1962 rules. Since the rules for Baroque were first laid down in 1962, some regional variation has arisen, causing the game to diverge from Ultima.

<span class="mw-page-title-main">Chessboard</span> Any board used in the game chess

A chessboard is a gameboard used to play chess. It consists of 64 squares, 8 rows by 8 columns, on which the chess pieces are placed. It is square in shape and uses two colours of squares, one light and one dark, in a chequered pattern. During play, the board is oriented such that each player's near-right corner square is a light square.

<span class="mw-page-title-main">Chess piece</span> Game piece for playing chess

A chess piece, or chessman, is a game piece that is placed on a chessboard to play the game of chess. It can be either white or black, and it can be one of six types: king, queen, rook, bishop, knight, or pawn.

<span class="mw-page-title-main">Pawn (chess)</span> Chess piece

The pawn is the most numerous and weakest piece in the game of chess. It may move one square directly forward, it may move two squares directly forward on its first move, and it may capture one square diagonally forward. Each player begins a game with eight pawns, one on each square of their second rank. The white pawns start on a2 through h2; the black pawns start on a7 through h7.

<span class="mw-page-title-main">Rules of chess</span> Rules of play for the game of chess

The rules of chess govern the play of the game of chess. Chess is a two-player abstract strategy board game. Each player controls sixteen pieces of six types on a chessboard. Each type of piece moves in a distinct way. The object of the game is to checkmate the opponent's king; checkmate occurs when a king is threatened with capture and has no escape. A game can end in various ways besides checkmate: a player can resign, and there are several ways a game can end in a draw.

<span class="mw-page-title-main">Three-dimensional chess</span> Variants of chess with multiple boards at different levels

Three-dimensional chess is any chess variant that replaces the two-dimensional board with a three-dimensional array of cells between which the pieces can move. In practice, this is usually achieved by boards representing different layers being laid out next to each other. Three-dimensional chess has often appeared in science fiction—the Star Trek franchise in particular—contributing to the game's familiarity.

This glossary of chess explains commonly used terms in chess, in alphabetical order. Some of these terms have their own pages, like fork and pin. For a list of unorthodox chess pieces, see Fairy chess piece; for a list of terms specific to chess problems, see Glossary of chess problems; for a list of named opening lines, see List of chess openings; for a list of chess-related games, see List of chess variants; for a list of terms general to board games, see Glossary of board games.

<span class="mw-page-title-main">Evaluation function</span> Function in a computer game-playing program that evaluates a game position

An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing computer programs to estimate the value or goodness of a position in a game tree. Most of the time, the value is either a real number or a quantized integer, often in nths of the value of a playing piece such as a stone in go or a pawn in chess, where n may be tenths, hundredths or other convenient fraction, but sometimes, the value is an array of three values in the unit interval, representing the win, draw, and loss percentages of the position.

A bitboard is a specialized bit array data structure commonly used in computer systems that play board games, where each bit corresponds to a game board space or piece. This allows parallel bitwise operations to set or query the game state, or determine moves or plays in the game.

Tamerlane chess is a medieval chess variant. Like modern chess, it is derived from shatranj. It was developed in Central Asia during the reign of Emperor Timur, and its invention is also attributed to him. Because Tamerlane chess is a larger variant of chaturanga, it is also called Shatranj Al-Kabir, as opposed to Shatranj as-saghir. Although the game is similar to modern chess, it is distinctive in that there are varieties of pawn, each of which promotes in its own way.

Zobrist hashing is a hash function construction used in computer programs that play abstract board games, such as chess and Go, to implement transposition tables, a special kind of hash table that is indexed by a board position and used to avoid analyzing the same position more than once. Zobrist hashing is named for its inventor, Albert Lindsey Zobrist. It has also been applied as a method for recognizing substitutional alloy configurations in simulations of crystalline materials. Zobrist hashing is the first known instance of the generally useful underlying technique called tabulation hashing.

Yari shogi is a modern variant of shogi ; however, it is not Japanese. It was invented in 1981 by Christian Freeling of the Netherlands. This game accentuates shogi’s intrinsically forward range of direction by giving most of the pieces the ability to move any number of free squares orthogonally forward like a shogi lance. The opposite is true of promoted pieces which can move backward with the same power.

<span class="mw-page-title-main">Hexagonal chess</span> Set of chess variants played on a board with hexagonal cells

Hexagonal chess is a group of chess variants played on boards composed of hexagon cells. The best known is Gliński's variant, played on a symmetric 91-cell hexagonal board.

A mathematical chess problem is a mathematical problem which is formulated using a chessboard and chess pieces. These problems belong to recreational mathematics. The most well-known problems of this kind are the eight queens puzzle and the knight's tour problem, which have connection to graph theory and combinatorics. Many famous mathematicians studied mathematical chess problems, such as, Thabit, Euler, Legendre and Gauss. Besides finding a solution to a particular problem, mathematicians are usually interested in counting the total number of possible solutions, finding solutions with certain properties, as well as generalization of the problems to N×N or M×N boards.

<span class="mw-page-title-main">Outline of chess</span> Strategy board game

The following outline is provided as an overview of and topical guide to chess:

<span class="mw-page-title-main">Falcon–hunter chess</span>

Falcon–hunter chess is a chess variant invented by Karl Schultz in 1943, employing the two fairy chess pieces falcon and hunter. The game takes several forms, including variations hunter chess and decimal falcon–hunter chess added in the 1950s.

Dynamo chess is a chess variant invented by chess problemists Hans Klüver and Peter Kahl in 1968. The invention was inspired by the closely related variant push chess, invented by Fred Galvin in 1967. The pieces, board, and starting position of Dynamo chess are the same as in orthodox chess, but captures are eliminated and enemy pieces are instead "pushed" or "pulled" off the board. On any given move, a player can make a standard move as in orthodox chess, or execute a "push move" or a "pull move". A move that is either a push move or a pull move is called a "dynamo move".

<span class="mw-page-title-main">0x88</span>

The 0x88 chess board representation is a square-centric method of representing the chess board in computer chess programs. The number 0x88 is a hexadecimal integer (13610, 2108, 100010002). The rank and file positions are each represented by a nibble (hexadecimal digit), and the bit gaps simplify a number of computations to bitwise operations.

References

  1. 1 2 3 4 Hyatt, Robert. "Chess program board representations". Archived from the original on 12 February 2013. Retrieved 15 January 2012.
  2. ↑ mnj12 (2021-07-07), mnj12/chessDeepLearning , retrieved 2021-07-07{{citation}}: CS1 maint: numeric names: authors list (link)
  3. 1 2 Frey, Peter W., ed. (1983) [1977], "An introduction to computer chess", Chess Skill In Man and Machine, Springer–Verlag, pp. 55–56
  4. ↑ 0x88 method. Bruce Moreland
  5. ↑ Albert Lindsey Zobrist, A New Hashing Method with Application for Game Playing, Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, (1969).
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.