Bitboard

A bitboard (bitmap board) is a data structure for representing a game situation (position), which is often used in computer programs for board games , in particular in chess programs .

Overview

The basic idea of ​​the bitboard structure is that the question of whether a certain figure is present on a certain playing field can be answered with yes or no . Because of this, the allocation of a game board / board of finite size can be represented as a sequence of individual binary numbers , each of which can assume the value 0 or 1.

Binary numbers (" bits ") form the basis of most computer systems today. If information can be represented as a sequence of bits that fit into a data word of the machine used, it can possibly be processed very efficiently. In particular, they have an impact on the efficiency of bitboard structures

• the size of the board: it is best to have this size fixed and smaller than or equal to the word size of the computer;
• the number of different figures, as a single word can only describe the assignment of a single type of figure.

Basically, bitboard structures are suitable for various board games. For example, there are also bitboard implementations for games such as checkers , othello , four wins or tic-tac-toe . Bitboards, however, have achieved particular importance in the field of computer chess. A chessboard consists of 8 × 8 = 64 fields, so a word of an associated bitboard is 64 bits long. This size can be processed directly as a data word by modern computer systems, which promises a great speed advantage. Examples of computer chess programs that use bitboards are Crafty and the current version 5.0 of GNU Chess .

Advantages and disadvantages

The main advantage of bitboard structures lies in their potentially very high efficiency, both in terms of memory space and, above all, in terms of program speed. A complete chess position can e.g. B. encode well in 64 bytes, in principle even in 32 bytes. Many operations in the positions represented in this way can each be carried out by a few processor instructions.

The main disadvantage of bitboards is their "otherness" compared to older, more widespread types of representation. Robert Hyatt , the developer of the well-known chess software Crafty , writes about his first experiences with bitboards:

“This has likely been the primary reason that bitmaps have not been widely used; They are different and take some time to 'sink in' to the point where they become easy to use. I would speculate that it took me roughly a year before I was able to get past the mental gymnastics of designing an algorithm using offset representation ideas and then working out how to modify the idea to fit the bitmap approach. "

“That's probably the main reason why bitboards weren't widely used; they are different and it takes some time for it to 'sag' to the point where they are easy to use. I guess it took me roughly a year to learn to avoid the mental detour of first designing an algorithm that works with field indices and then figuring out how the idea can be transferred to the bitboard approach. "

- Robert Hyatt

Since there are now a number of open-source bitboard implementations, this argument against bitboards should weigh only weakly and continue to decrease in importance.

Application example: computer chess

As already mentioned, a word on a bitboard in the chess case is exactly 64 bits long due to the size of the chessboard. As a special feature, there are 12 different types of figures ( pawns , rooks , knights , bishops , queen , king , each white and black). For this reason, it takes at least four words to fully represent a position. Usually, however, a lot more is used in order to be able to process the information more easily, i. H. redundant information is also shown explicitly.

The Crafty software mentioned at the beginning, for example, saves the positions of the 12 types of pieces in additional words, the positions of all white and black pieces combined, and also rotated versions of the game board for further optimization. A complete data structure that fully describes the current state of the game must also contain information about the status z. B. of castling opportunities, " en passant " moves, the 50- move rule and possibly other special rules.

	a	b	c	d	e	f	G	H
8th									8th
7th									7th
6th									6th
5									5
4th									4th
3									3
2									2
1									1
	a	b	c	d	e	f	G	H

Chess: starting position

0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1
0	0	0	0	0	0	0	0

The starting position (see diagram) leads e.g. B. for the white pawns on the following bitboard structure (bit pattern of a word):

00000000 00000000 00000000 00000000 00000000 00000000 11111111 00000000 ₂ .

The way in which it is “counted”, ie which field on the chessboard is assigned to which index (bit position in the word), is ultimately optional. In this example and in the following, counting is carried out line by line, starting with field A1, so bit 0 belongs to A1, bit 1 belongs to A2, and so on up to field H8 and bit 63.As already mentioned, some chess programs even manage bitboard Structures in different ways of counting (in rows or columns, or also diagonally) at the same time, as this enables certain operations to be more efficient.

Train calculation

A central problem in the implementation of a chess program is the calculation of the possible subsequent moves from a given position. When using bitboard structures, this is done through logical operations on the map allocation. A distinction must be made between two types of pieces: in the case of "jumping" pieces such as pawns, knights and kings, only the occupation of the target field is decisive. With the “sliding” figures such as towers, bishops and checkers, the possibility of moving is more complex, since figures can block certain target areas without occupying them themselves.

Pawn, knight, king

	a	b	c	d	e	f	G	H
8th									8th
7th									7th
6th									6th
5									5
4th									4th
3									3
2									2
1									1
	a	b	c	d	e	f	G	H

Possible knight moves from field D4

0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	1	0	1	0	0	0
0	1	0	0	0	1	0	0
0	0	0	0	0	0	0	0
0	1	0	0	0	1	0	0
0	0	1	0	1	0	0	0
0	0	0	0	0	0	0	0

With these pieces it only depends on whether a piece of your own color is placed on the target space. In fact, the pawns are a special case because they move differently depending on whether they capture an opposing piece or not. However, this will not be discussed here.

As an example, consider a knight on space D4. The possible target fields can be seen in the diagram. The question of whether the jumper can basically move to a certain target field is again a question to be answered with yes or no , the answer of which can be coded as a bitboard. Such an “attack board” can be calculated and saved in advance for each field from A1 to H8.

In the example chosen, the field D4 is the 28th field counted line by line from A1, so in a list of 64-bit numbers the index 27 (if 0 is the first index) would be assigned the following number:

00000000 00000000 00101000 01000100 00000000 01000100 00101000 00000000 ₂ .

If this total of 64 possible bitboards (for the jumper) are already calculated when the program is started, later access is very efficient as a simple index operation. In order to decide which squares the knight can actually move to in the present case, information about the current map allocation in his own color is required. This is either available directly or can be determined from the 6 assignments of the individual types of figures (by bitwise OR operation ). A bitwise NOT applied to this assignment determines the fields that are not occupied by figures of their own color.

The logical condition that must be fulfilled for a knight to move to a certain square is that there must not be any piece of one's own color. In the complement bit board just described, the bit for which this condition is met is set for each field. The desired result is finally obtained through a bit-by-bit AND operation with the pre-calculated “attack board” of the jumper.

With slight adjustments, the same procedure can be used to calculate the moves for pawns and for the king.

Towers, runners, checkers

These figures move fundamentally differently than the three aforementioned types. In the case of these "sliding" pieces, in addition to occupying the target area, it depends on whether the way there is blocked, be it by pieces of your own or the opponent's color. The queen can be interpreted as a combination of tower and bishop, which can represent a simplification depending on the exact choice of data structures.

See also

• Computer chess

Individual evidence

1. ↑ Representation of bitboard structures in checkers game (English)
2. ↑ Discussion of various implementation details of Othello, including bitboards (English).
3. ↑ bitboards and Connect Four describes in detail an implementation for Connect Four (English).
4. ↑ The instructional video Bitboards for Tic-Tac-Toe explains an implementation for Tic-Tac-Toe (German)
5. ↑ Robert Hyatt : Article about the "rotated bitboard" structures used in Crafty.
6. ↑ Documentation of GNU Chess 5.0
7. ^ R. Hyatt : Comparative article on data structures for chess programs