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.

The technique is applicable to any board game whose game state is represented by the presence of pieces on discrete spaces of a gameboard, including chess, checkers, othello and word games. It 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.

Compared with the traditional mailbox representation, where each piece or space on the board is an array element, bitboards are a more space-efficient board representation.

Bitboards are often also more time-efficient. When the associated bits of related states on the bitboard fit into a single word or double word of the CPU architecture, single bitwise operators like AND and OR can be used to operate on the bitboard. These parallel bitwise operations can be much faster at setting and querying game states, and determining moves and plays in the game, than performing iterative array operations on a mailbox representation would be.

Modern chess engines predominantly utilize magic bitboards, which employ perfect hashing to map a piece's occupancy mask directly to a pre-computed array of attack patterns in a single lookup operation.