Hubbry Logo
search
logo

Bitboard

logo
Community Hub0 Subscribers
Write something...
Be the first to start a discussion here.
Be the first to start a discussion here.
See all
Bitboard

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

See all
User Avatar
No comments yet.