Битборд: Қағаз ойындары үшін тиімді дерек құрылымы

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. Bits in the same bitboard relate to each other by the rules of the game, often forming a game position when taken together. Other bitboards are commonly used as masks to transform or answer queries about positions. Bitboards are applicable to any game whose progress is represented by the state of, or presence of pieces on, discrete spaces of a gameboard, by mapping of the space states to bits in the data structure. Bitboards are a more efficient alternative board representation to the traditional mailbox representation, where each piece or space on the board is an array element. Bitboards are especially effective when the associated bits of various related states on the board fit into a single word or double word of the CPU architecture, so that single bitwise operators like AND and OR can be used to build or query game states. Among the computer game implementations that use bitboards are chess, checkers, othello and word games. The scheme was first employed in checkers programs in the 1950s, and since the mid 1970s has been the de facto standard for game board representation in computer automatons.

A bitboard, a specialized bit field, is a format that packs multiple related boolean variables into the same machine word, typically representing a position on a board game, or state of a game. Each bit represents a space; when the bit is positive, a property of that space is true. Bitboards allow the computer to answer some questions about game state with one bitwise operation. For example, if a chess program wants to know if the white player has any pawns in the center of the board (center four squares) it can just compare a bitboard for the player's pawns with one for the center of the board using a bitwise AND operation. If there are no center pawns then the result will be all zero bits (i. e. equal to zero). Multiple bitboards may represent different properties of spaces over the board, and special or temporary bitboards (like temporary variables) may represent local properties or hold intermediate collated results. The efficacy of bitboards is augmented by two other properties of the implementation. First, bitboards are fast to incrementally update, such as flipping the bits at the source and destination positions in a bitboard for piece location when a piece is moved. Second, bitmaps representing static properties like all spaces attacked by each piece type for every position on a chessboard can be pre collated and stored in a table, so that answering a question like "what are the legal moves of a knight on space e4?" can be answered by a single memory fetch. Bitfield implementations take advantage of the presence of fullword (32 bit or 64 bit) bitwise logical operations like AND, OR, NOT and others on modern CPU architectures in order to be efficient. Bitboards may not be effective on earlier 8 and 16 bit minicomputer and microprocessor architectures.

As a result of necessary compression and encoding of the contents of massive tables and the probability of transcription or encoding errors, bitboard programs are tedious for software developers to either write or debug. Auxiliary generative methods not part of the application are usually required to build the tables.

Bitboard representations use parallel bitwise operations available on nearly all CPUs that complete in one cycle and are fully pipelined and cached etc. Nearly all CPUs have AND, OR, NOR, and XOR. Furthermore, modern CPUs have instruction pipelines that queue instructions for execution. A processor with multiple execution units can perform more than one instruction per cycle if more than one instruction is available in the pipeline. Normal instruction sequences with branches may cause the pipeline to empty if a branch is mispredicted. Many bitboard operations require fewer conditionals and therefore increase pipelining and make effective use of multiple execution units on many CPUs. CPUs have a bit width which they are designed toward and can carry out bitwise operations in one cycle in this width. So, on a 64 bit or more CPU, 64 bit operations can occur in one instruction. There may be support for higher or lower width instructions. Many 32 bit CPUs may have some 64 bit instructions and those may take more than one cycle or otherwise be handicapped compared to their 32 bit instructions. If the bitboard is larger than the width of the instruction set, multiple instructions will be required to perform a full width operation on it. So a program using 64 bit bitboards would run faster on a 64 bit processor than on a 32 bit processor.

Bitboard representations have much longer code, both source and object code. Long bit twiddling sequences are technically tricky to write and debug. The bitboards themselves are sparse, sometimes containing only a single one bit in 64, so bitboard implementations are memory intensive. Both these issues may increase cache misses or cause cache thrashing. If the processor does not have hardware instructions for 'first one' (or 'count leading zeros') and 'count ones' (or 'count zeros'), the implementation will be significantly handicapped, as these operations are extremely inefficient to code as assembly language loops.

Bitboards require more memory than piece list board data structures, but are more execution efficient because many loop and compare operations are reduced to a single (or small number of) bitwise operation(s). For example, in mailbox, determining whether piece attacks space requires generating and looping through legal moves of piece and comparing the final space with space. With bitboards, the legal moves of piece are stored in a bitmap, and that map is ANDed with the bitmap for space. A non zero result means that piece attacks space.

For some games, writing a bitboard engine requires a fair amount of source code including data tables that will be longer than the compact mailbox/enumeration implementation. For mobile devices (such as cell phones) with a limited number of registers or processor instruction cache, this can cause a problem. For full sized computers, it may cause cache misses between level one and level two cache. This is only a potential problem, not a major drawback, as most machines will have enough instruction cache for this not to be an issue.

Some kinds of bitboards are derived from others by an elaborate process of cross correlation, such as the attack maps in chess. Reforming all these maps at each change of game state (such as a move) can be prohibitively expensive, so derived bitmaps are incrementally updated, a process which requires intricate and precise code. This is much faster to execute, because only bitmaps associated with changed spaces, not all bitmaps over the board, need to change. Without incremental update, bitmapped representation may not be more efficient than the older mailbox representation where update is intrinsically local and incremental.

Some kinds of bitmaps that don't depend on board configurations can be precomputed and retrieved by table lookup rather than collated after a move or state change of the board, such as spaces attacked by a knight or king located on each of 64 spaces of a chessboard that would otherwise require an enumeration.

The obvious, and simplest representation of the configuration of pieces on a chessboard, is as a list (array) of pieces in a conveniently searchable order (such as smallest to largest in value) that maps each piece to its location on the board. Analogously, collating the spaces attacked by each piece requires a serial enumeration of such spaces for a piece. This scheme is called mailbox addressing. Separate lists are maintained for white and black pieces, and often for white and black pawns. The maps are updated each move, which requires a linear search (or two if a piece was captured) through the piece list. The advantage of mailbox is simple code; the disadvantage is linear lookups are slow. Faster, but more elaborate data structures that map pieces to locations are called bitboards.

In bitboard representations, each bit of a 64 bit word (or double word on 32 bit architectures) is associated with a square of the chessboard. Any mapping of bits to squares can be used, but by broad convention, bits are associated with squares from left to right and bottom to top, so that bit 0 represents square a1, bit 7 is square h1, bit 56 is square a8 and bit 63 is square h8. Many different configurations of the board are usually represented by their own bitboards including the locations of the kings, all white pawns, all black pawns, as well as bitboards for each of the other piece types or combinations of pieces like all white pieces. Two attack bitboards are also universal: one bitboard per square for all pieces attacking the square, and the inverse bitboard for all squares attacked by a piece for each square containing a piece. Bitboards can also be constants like one representing the first rank, which would have one bits in positions 0 7. Other local or transitional bitboards like "all spaces adjacent to the king attacked by opposing pieces" may be collated as necessary or convenient.

The author of the Frenzee engine had posted some source examples. A 155 line java Connect 4 program demonstrating the use of bitboards.

A complete discussion of Othello (Reversi) engines with some source code including an Othello bitboard in C and assembly. Edax (computing) See the Edax article. An Othello (Reversi) engine with source code based on bitboard.

Overview of bit board usage in word games.