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.[1] Chess engines often utilize more than one board representation at different times, for efficiency.

Requirements

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.

Types

Piece lists

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.

Array based

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

Machine code programmers have another alternative. Using 4 bits per square, an entire row can be represented in 32 bits, and the board in 8 registers (with an additional one for remaining position information). By use of a jump table, adding the piece value to the program counter can go directly to the code to generate moves for this type of piece on this square. Although the program is longer than for a conventional move generation methods, no checks for the edge of the board are required, and no moves off the board are considered, increasing move generation speed.

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

Bitboard

Main article: Bitboard

One commonly used board representation 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 about each place 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.

Stream-based

As in array encoding, four bits suffice to encode the twelve different pieces. This leaves three combinations for encoding one to three empty squares and one combination to indicate that the next four bits encode four to 19 empty squares. This allows encoding the starting position in 18 bytes. As pieces get taken, the encoding becomes ever shorter. The maximal penalty comes for four square gaps, which require eight bits. But there can be at most 13 of them, taking 20 bytes for such a board. A hypothetical board alternating a piece and a gap takes the maximum length of 32 bytes. To this must be added two bytes for the 50-move rule and such things.

Huffman encodings

Inspired by Huffman coding, chess positions can be represented with bit patterns in such a way that the more common board elements (empty squares and pawns) are stored using fewer bits than the less common board elements:

Empty square = 0
Pawn         = 10c
Bishop       = 1100c
Knight       = 1101c
Rook         = 1110c
Queen        = 11110c
King         = 11111c

where c is a bit representing the color of the piece (1 = LIGHT, 0 = DARK).

Additional bits are needed for:[4]
50-move rule (7 bits)
en-passant column (3 bits)
color to move (1 bit)
castling rights (4 bits).

For the fifty-move rule, a number representing one of 101 possibilities is needed: a pawn was just moved or a piece just captured, a pawn was moved or a piece was captured 1..99 moves ago, or a pawn was moved or a piece captured 100 or more moves ago. This fits in 7 bits.

Any board may have a maximum of 5 seemingly en-passant-capturable pawns.[4] Thus a number representing one of 6 possibilities is needed. This fits in 3 bits and is only needed if the board appears to allow an en passant.

Trailing empty squares can be omitted. If the remaining last piece is a king, it can by definition be omitted without loss of information, saving six more bits in some cases. Castling rights need be stored if the board appears to allow such castling.

With the above, a complete board state can be represented in a maximum of 204 bits, and often much less.

Huffman encodings are fairly CPU intensive, in comparison to other board representations which seek to minimize required processor and memory cycles. However, the small size of the final representation makes this approach well suited to storage of long-term knowledge, for instance in storing positions in an opening book, where minimizing the board representation's size is more important than minimizing CPU cycles. Huffman encoded boards are also sometimes used in transposition tables for shallow entries.

Huffman fine-tuning

An even more compact variant sacrifices the two to four-bit representation of as many empty squares for encoding two to nine empty squares in five bits. If another zero follows, the number is extended by two bits, allowing ten to 41 empty squares to be encoded in eight bits.

One empty square               = 0
nnn+2 (2-9) empty squares      = 00nnn
nnnnn+10 (10-41) empty squares = 00nnn0nn

or

nnnn+10 (10-25) empty squares  = 00nnn0n

For up to 41-length gaps, like the initial or end game boards, this saves up to 33 bits. For all sparse boards where there are pieces or pawns at near nine-square intervals or much longer gaps, there are also nice savings, e.g. 16 bits for four gaps of length nine. This is offset by the extra bits for short gaps. To always have the optimal encoding, one extra bit can mark whether straightforward or compact empty square encoding is used.

In addition the coordinates of the kings can be stored and their fields ignored in the bit sequence instead. This also takes 6 bits each. But the queen can then be coded in five bits. And gaps to the right and left can then be coalesced, making for one longer gap which is often a candidate for better compacting.

The color-to-move bit need not be part of the encoding, instead the stored value can indicate for which color (or both) a move is stored. Along with the two bits guaranteed to be saved with the above king positions, this means the encoding will never be more than 24 bytes long, which fits nicely with 32 or 64 bit architectures.

Four extra bits can store the number of pieces of the first color encountered. After the last piece of that color, the color bit can be skipped. For the initial boards, this saves 12 bits. Alternately or additionally, when the maximal possible number of one piece of the first color has been stored, i.e. eight black pawns, or two white rooks, all further pawns, rooks, etc. must be of the other color and don't require the color bit.

Another extra bit appears when the number of pieces of the first color is eight or less. It can mark the fact that no pawns are left. In this case the first bit of all pieces can be skipped:

Bishop       = 100c
Knight       = 101c
Rook         = 110c
Queen        = 1110c
King         = 1111c

Huffman multi-table approach

Additionally you can consider that for each rook there are 3 possibilities related to its home square: it has left it or it is there, either with or without castling right. When combining this for all rooks, that creates 81 different board categories, going from those with all rooks being home with castling rights, to none being home. If you store each category in a separate table, that table holds implicit information about rooks and castling rights, i.e. you only need to encode those rooks in those tables which mean it is not home. Moreover, in 25 of these categories, on each side at least one rook has its castling right, meaning that the king's position is implicitly known and need not be encoded either. And if the king's position is implicit, the queen's last bit is not needed or where both rooks are home, its shorter bit sequence can be used for the queen.

This means that for the nine tables with both rooks home, and at least one on each side having castling rights, you always save 38 bits (20 bits for four rooks, 12 bits for two kings and 2 bits for the queens and, as in all cases, 4 bits for the castling rights). At the other extreme, with no rooks home, you only save the 4 castling bits. So the gains are much higher for an opening data base than for end games.

(seems very tricky and doesn't work in case of rook promotion. Coding castle rights with the two kings positions (3612 possibilities without castle + 329 with castle => 12 bits) is safer)

Forsyth-Edwards Notation (FEN)

FEN notation is a board representation that was popularized before the advent of computers and is a human-readable method of recording a chess game position in a single line of text. FEN is still used frequently by chess programs for saving board positions to external storage, whenever a human may view that storage. It is also sometimes used as a communication standard between chess software packages; the Universal Chess Interface, for example, specifies the FEN notation for transmitting board positions to a chess engine.

Examples

Here is the FEN for the starting position:

   rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Here is the FEN after the move 1. e4:

   rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1

And then after 1. ... c5:

   rnbqkbnr/pp1ppppp/8/2p5/4P3/8/PPPP1PPP/RNBQKBNR w KQkq c6 0 2

References

  1. 1 2 3 4 Hyatt, Robert. "Chess program board representations". Retrieved 15 January 2012.
  2. 1 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. 1 2 https://groups.google.com/group/rec.games.chess.computer/browse_thread/thread/be6bc8d1e3c7da42?q=bits+chess+++fulldecent#9656fff9a921d4eb
This article is issued from Wikipedia - version of the 11/4/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.