A bitboard is a specialized data structure widely used in computer systems engaged in board games. In this structure, each bit corresponds to a specific space or piece on the game board. This design enables parallel bitwise operations for setting or querying the game state and determining moves or plays within the game.
The bits within the same bitboard are interconnected based on the rules of the game, often forming a complete game position when considered together. Additional bitboards are commonly employed as masks to transform or answer queries related to positions. Bitboards find applications in any game where progress is represented by the state or presence of pieces on distinct spaces of the game board, achieved by mapping the space states to bits in the data structure. They offer a more efficient alternative to traditional mailbox representation, where each piece or space on the board is an array element.
Bitboards excel when associated bits of various related states on the board can fit into a single word or double word of the CPU architecture. This allows single bitwise operators like AND and OR to be used for building or querying game states. The crucial point is that this compact representation enables the use of single bitwise operators like AND and OR. This is advantageous because bitwise operations are fundamental and often executed with high efficiency at the hardware level.When these related states can fit into a single machine word or double word of the CPU architecture, it implies that a significant amount of information can be stored in a compact manner.
Computer game implementations that leverage bitboards include chess, checkers, othello, and various word games.
Description
A bitboard, being a specialized bit field, is a format that packs multiple related boolean variables into the same machine word. It typically represents a position on a game board or the state of a game. Each bit in the bitboard represents a space, where a positive bit indicates a true property of that space. Bitboards empower computers to answer specific questions about the game state using a single bitwise operation. For instance, in a chess program, determining if the white player has any pawns in the center of the board can be accomplished by comparing 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, the result will be all zero bits (i.e., equal to zero). Multiple bitboards may represent different properties of spaces on the board, and special or temporary bitboards (akin to temporary variables) may represent local properties or hold intermediate collated results.
The effectiveness of bitboards is enhanced by two other properties of the implementation. Firstly, bitboards can be incrementally updated at a fast pace, such as flipping the bits at the source and destination positions in a bitboard for piece location when a piece is moved. Secondly, 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, enabling efficient answers to questions like "what are the legal moves of a knight on space e4?" through a single memory fetch.
Implementing bitfields takes advantage of fullword (32-bit or 64-bit) bitwise logical operations like AND, OR, NOT, and others on modern CPU architectures for efficiency. However, bitboards may not be as effective on earlier 8- and 16-bit minicomputer and microprocessor architectures.
Implementation Issues
As a consequence of the compression and encoding of the contents of massive tables and the likelihood of transcription or encoding errors, developing and debugging bitboard programs can be tedious for software developers. Auxiliary generative methods, not originally part of the application, are often required to build these tables.
Processor Use
Pros
Bitboard representations leverage parallel bitwise operations available on nearly all CPUs, completing in one cycle and being fully pipelined and cached. Virtually all CPUs possess AND, OR, NOR, and XOR operations. Additionally, modern CPUs feature instruction pipelines that queue instructions for execution. Processors with multiple execution units can perform more than one instruction per cycle if multiple instructions are available in the pipeline. Bitboard operations typically require fewer conditionals, increasing pipelining and making effective use of multiple execution units on many CPUs.
CPUs are designed with a specific bit width, allowing them to carry out bitwise operations in one cycle within this width. Therefore, on a 64-bit or larger CPU, 64-bit operations can occur in one instruction. While there may be support for higher or lower width instructions, many 32-bit CPUs may have some 64-bit instructions, which may take more than one cycle or be handicapped compared to their 32-bit counterparts. A program using 64-bit bitboards would run faster on a 64-bit processor than on a 32-bit processor if the bitboard is larger than the width of the instruction set.
Cons
Bitboard representations result in longer code, both in source and object code. Crafting intricate bit-twiddling sequences can be technically challenging to write and debug. The bitboards themselves are often sparse, containing only a single one bit in 64. As a result, bitboard implementations are memory-intensive. These issues may increase cache misses or cause cache thrashing.
If the processor lacks hardware instructions for 'first one' (or 'count leading zeros') and 'count ones' (or 'count zeros'), the implementation may be significantly handicapped. These operations are extremely inefficient to code as assembly language loops.
Cache and Memory Usage
Pros
While bitboards demand more memory than piece-list structures, they exhibit superior execution efficiency. Numerous loop-and-compare operations are reduced to single or a small number of bitwise operations.
Cons
Developing a bitboard engine may require extensive source code, especially for certain games. For resource-constrained devices, such as mobile phones, the memory-intensive nature of bitboards can be problematic.
Incremental Update
Bitboards undergo incremental updates, efficiently modifying only bitmaps associated with changed spaces rather than recalculating all bitmaps across the entire board.
Precomputed Bitmaps and Table Lookup
Some bitmaps, independent of board configurations, can be precomputed and retrieved through table lookup. This eliminates the need for extensive enumeration after every move.
Chess Bitboards
In chess bitboards, each bit corresponds to a square on the chessboard. Various configurations, such as piece locations, have dedicated bitboards. Standard bitboards face challenges in collating attack vectors for sliding pieces.
Auxiliary Bitboard Representations
Alternative bitboard structures, like rotated bitboards and direct hashing, simplify the tabularization of sliding piece attack vectors. Magic bitboards, despite their name, involve a tradeoff between time and space efficiency.
Chess Bitboard Example
In chess programming, bitboards are often used to represent various aspects of the game state efficiently. Below is a detailed pseudo code example illustrating a simple chess bitboard for the placement of white pawns.
uint64_t whitePawnBitboard = 0;
whitePawnBitboard = setBit(whitePawnBitboard, squareToBitIndex("a2"));
whitePawnBitboard = setBit(whitePawnBitboard, squareToBitIndex("b2"));
whitePawnBitboard = setBit(whitePawnBitboard, squareToBitIndex("c2"));
whitePawnBitboard = setBit(whitePawnBitboard, squareToBitIndex("d2"));
whitePawnBitboard = setBit(whitePawnBitboard, squareToBitIndex("e2"));
whitePawnBitboard = setBit(whitePawnBitboard, squareToBitIndex("f2"));
whitePawnBitboard = setBit(whitePawnBitboard, squareToBitIndex("g2"));
whitePawnBitboard = setBit(whitePawnBitboard, squareToBitIndex("h2"));
function setBit(bitboard, position) {
return bitboard | (1n << position);
}
function squareToBitIndex(square) {
const file = square.charCodeAt(0) - 'a'.charCodeAt(0);
const rank = square.charCodeAt(1) - '1'.charCodeAt(0);
return 8n * BigInt(rank) + BigInt(file);
}
This pseudo code initializes a bitboard representing the positions of white pawns on the chessboard. The setBit function is used to set individual bits, and squareToBitIndex converts chess square notation (e.g., "a2") to the corresponding bit index.
This is a basic example, and in real implementations, various bitboards would be used for different aspects of the chess position, such as pieces, attacks, and more.
Extended Chess Bitboard Example
This example extends the previous bitboard demonstration to include multiple piece types (white pawns and black knights) and showcases basic bitwise operations.
uint64_t whitePawnBitboard = 0;
uint64_t blackKnightBitboard = 0;
whitePawnBitboard = setBit(whitePawnBitboard, squareToBitIndex("a2"));
whitePawnBitboard = setBit(whitePawnBitboard, squareToBitIndex("b2"));
whitePawnBitboard = setBit(whitePawnBitboard, squareToBitIndex("c2"));
blackKnightBitboard = setBit(blackKnightBitboard, squareToBitIndex("b8"));
blackKnightBitboard = setBit(blackKnightBitboard, squareToBitIndex("g8"));
let combinedBitboard = whitePawnBitboard | blackKnightBitboard; // OR operation
let overlappingBitboard = whitePawnBitboard & blackKnightBitboard; // AND operation
let exclusiveBitboard = whitePawnBitboard ^ blackKnightBitboard; // XOR operation
console.log("Combined Bitboard:", combinedBitboard.toString(2));
console.log("Overlapping Bitboard:", overlappingBitboard.toString(2));
console.log("Exclusive Bitboard:", exclusiveBitboard.toString(2));
function setBit(bitboard, position) {
return bitboard | (1n << position);
}
function squareToBitIndex(square) {
const file = square.charCodeAt(0) - 'a'.charCodeAt(0);
const rank = square.charCodeAt(1) - '1'.charCodeAt(0);
return 8n * BigInt(rank) + BigInt(file);
}
This extended example includes bitboards for white pawns and black knights. It then demonstrates basic bitwise operations such as OR, AND, and XOR to combine, find overlapping positions, and find exclusive positions, respectively.
Sudoku Bitboard Example
In this example, we use bitboards to efficiently represent a Sudoku puzzle and check the validity of numbers in rows, columns, and 3x3 subgrids.
let rowBitboards = [0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n];
let colBitboards = [0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n];
let subgridBitboards = [0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n];
function setNumber(row, col, num) {
const bitIndex = 9n * BigInt(row) + BigInt(col);
const numBitboard = 1n << (num - 1);
rowBitboards[row] |= numBitboard;
colBitboards[col] |= numBitboard;
subgridBitboards[getSubgridIndex(row, col)] |= numBitboard;
}
function isValidNumber(row, col, num) {
const bitIndex = 9n * BigInt(row) + BigInt(col);
const numBitboard = 1n << (num - 1);
return (
(rowBitboards[row] & numBitboard) === 0n &&
(colBitboards[col] & numBitboard) === 0n &&
(subgridBitboards[getSubgridIndex(row, col)] & numBitboard) === 0n
);
}
function getSubgridIndex(row, col) {
return 3 * (row / 3) + col / 3;
}
In this example, we utilize three sets of bitboards to represent numbers in rows, columns, and 3x3 subgrids. The setNumber function updates the bitboards when a number is placed, and isValidNumber checks if placing a number is valid in terms of Sudoku rules.
This concept can be adapted for various puzzle-solving scenarios where efficient representation and validation of placement are crucial.