Bitboard

A bitboard (bitmap Board ) is a data structure that is often used in computer programs for board games found, especially in chess programs.

Survey

The basic idea of ​​bitboard structure is that the question whether a particular figure is present on a particular field, can be answered with yes or no. Because of the availability of a list of finite size can be represented as a sequence of individual binary numbers, which can take the value 0 or 1, respectively.

Binary numbers ( " bits " ) are the basis of most of today's computer systems, which is why it based structures can normally be processed very efficiently. Impact on the efficient use of bitboard structures have particular

• The Schedule Size: best this size is fixed and less than or equal to the maximum word size of the computer;
• The number of different characters, since a single bitboard can only describe the Schedule assignment with a single figure variety.

Basically bitboard structures for various board games are suitable. There are, for example, bitboard implementations of the lady and the Othello game. Of particular importance are bitboards however gained in the field of computer chess. A chessboard consists of 8x8 = 64 squares, an associated bitboard is therefore 64 bits long. This size can be handled by modern computer systems directly as a data word, what a great potential speed advantage promises. Examples of computer chess programs which use bitboards, make Crafty and the current version 5.0 of GNU Chess dar.

Pros and Cons

The main advantage of bitboard structures lies in the potentially very high processing efficiency, both in terms of space as well, especially with regard to the program speed. A complete chess position can for example be in well under 150 bytes encode, and many game plan operations can be performed in each case by a few processor instructions.

The main disadvantage of bitboards lies in its " otherness" against older, more widespread representation. Robert Hyatt, the developer of the popular chess software Crafty, writes about his first experience with bitboards:

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

Since there are now quite a number of open source bitboard implementations, this argument, however, is likely to weigh only weak against bitboards and take in its meaning further.

Example: computer chess

As already mentioned, a bitboard in chess case due to the size of the chessboard is exactly 64 bits long. As a special feature, there are 12 different types of characters ( farmers, towers, knight, bishop, queen, king in each of two colors). For this reason, usually but mostly more bitboard structures are at least 12, employed simultaneously.

The aforementioned software Crafty example, stores in addition to the positions of the 12 varieties figure in other structures, the positions of all the white or black pieces together, and also rotated versions of the game board for further optimization. A complete data structure which describes completely the current state of the game, also has information about the status, for example, of castling possibilities, "en passant " trains, the 50 - move rule and optionally further contain special rules.

The starting position (see diagram) leads to the white pawns on the following bitboard structure (for the other types of figures are corresponding assignments ):

00000000 00000000 00000000 00000000 00000000 00000000 11111111 00000000 2

What sort of " counted " is, so which index is assigned in the bit representation which square of the chessboard, is ultimately optional. In this example and in the following, starting with the field A1 line by line, counted, ie belongs to A1 bit 0 to A2 bit 1, and so on until finally field H8 and bit 63 As already mentioned, manage some chess programs even bitboard - structures as this certain operations are efficient possible in various counting ( by row or column by column, or diagonally ) simultaneously.

Train calculation

A central problem in the implementation of a chess program, the calculation of the possible redrawing from a given position out dar. When using bitboard structures this is done by logical operations on the Schedule assignment. Here, two types must be distinguished from figures: at the "jumping " figures such as farmers, jumpers and King, the occupancy of the target field is decisive. The "sliding " figures such as towers, runners and Lady the legal move is more complex because characters can block specific target fields without occupying it himself.

Bauer, Springer, King

In these figures, it is only important if a character of its own color is placed on the target field. In fact, the farmers in turn provide a special case, because they draw different, depending on whether they capture an opponent's piece or not. However, it will not be discussed here.

Consider as an example a knight on field D4. The possible target fields can be seen in the diagram. The question of whether the Springer basically can pull to a particular target field, in turn, is a yes or no question to answer, the answer is coded as bitboard. For each field of A1 to H8 may be calculated and stored in advance such " attack -board ".

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

00000000 00000000 00101000 01000100 00000000 01000100 00101000 00000000 2

If they are already calculated when the program starts a total of 64 possible bitboards ( for Springer ), access is possible later very efficiently as a simple index operation. Now, to decide which fields of the Springer can actually pull in the present case, information about the current Schedule assignment in their own paint is still required. This is either right before or can be determined from the six assignments of the individual character varieties ( by bitwise OR operation). Through a bitwise NOT apply to this assignment to determine the fields that are not occupied by figures of the same color.

The logical condition that must be met for a Springer - train on a particular field, is now just that there must be no figure of his own color. In the complement bitboard just described, the exact bit for each field set, in which said condition is fulfilled. The desired result is obtained as finally bitwise AND operation with the pre-calculated " attack -board " of the jumper.

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

Towers, runners, lady

These figures move fundamentally different than the three aforementioned species. These "floating " figures it comes in addition to the occupancy of the target field on whether the road is blocked there, whether by figures of their own or the opponent's suit. The lady can be interpreted as a combination of rook and bishop, which depending on the exact choice of data structures can represent a simplification.