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.

Description

A bitboard is a specialized bit field: a format that represents the state of a board game by packing multiple Boolean variables into the same machine word. Each bit represents a space; when the bit is positive, a property of that space is true.

Bitboards allow the computer to answer questions about game state using very few bitwise operations. 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, 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; for example 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. This allows a question like "what are the legal moves of a knight on space e4?" to be answered by a single memory fetch.

Bitboard 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 for operations to be fast. Bitboards may not be as effective on earlier 8- and 16-bit minicomputer and microprocessor architectures.

Implementation

Because the implementation of bitboards requires correct compression and encoding of massive tables and complex game states, bitboard programs can be tedious for software developers to write and debug.

Processor use

Advantages

Bitboard representations use parallel bitwise operations available on nearly all CPUs that complete in one cycle, and are typically among the fastest instructions (being fully pipelined and cached, as well as other CPU-specific optimizations). Nearly all CPUs have the AND, OR, NOR, and XOR operations. 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, increasing pipelining and making effective use of multiple execution units on many CPUs.

CPUs have a bit width, the number of completable bitwise operations in one cycle. On a 64-bit or larger CPU, 64-bit operations can therefore 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. A program using 64-bit bitboards would therefore run faster on a 64-bit processor than on a 32-bit processor.

Disadvantages

Bitboard representations have much longer code, both source and object code. Long bit-twiddling sequences are technically tricky to write and debug. This issue 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 loops or other high-level constructs.

Cache and memory use

Advantages

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.

Disadvantages

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. This can cause problems for mobile devices (such as cell phones) with a limited number of registers or processor instruction cache. 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.

Incremental update

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.

Precomputed bitmaps and table lookup

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.

In chess

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. Bitboards are faster, but more elaborate.

Standard

Chessboard with algebraic notation

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 often 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 such as one representing the first rank, which would have one bits in positions 0 - 7. Other local or transitional bitboards such as "all spaces adjacent to the king attacked by opposing pieces" may be collated as necessary or convenient.[1]

An example of the use of the bitboards would be determining whether a piece is en prise: bitboards for "all friendly pieces guarding space" and "all opposing pieces attacking space" would allow matching the pieces to readily determine whether a target piece on space is en prise.

One of the drawbacks of standard bitboards is collating the attack vectors of the sliding pieces (rook, bishop, queen), because they have an indefinite number of attack spaces depending on other occupied spaces. This requires several lengthy sequences of masks, shifts and complements per piece.

Auxiliary bitboard representations

For sliding pieces in chess (rooks, bishops, and queens), determining a piece's valid attacks is computationally complex because legal moves depend on obstructing pieces along a given ray from the piece.

Alternate bitboard data structures have been devised to collate the code size and computing complexity of generating bitboards for the attack vectors of sliding pieces. The bitboard representations of knights, kings, pawns and other board configurations are unaffected by the use of auxiliary bitboards for the sliding pieces.

Rotated bitboards

Rotated bitboards are complementary bitboard data structures that enable tabularizing of sliding piece attack vectors, one for file attack vectors of rooks, and one each for the diagonal and anti-diagonal attack vectors of bishops (rank attacks of rooks can be indexed from standard bitboards). With these bitboards, a single table lookup replaces lengthy sequences of bitwise operations.

These bitboards rotate the board occupancy configuration by 90 degrees, 45 degrees, and/or 315 degrees. A standard bitboard has one byte per rank of the chess board. With this bitboard, it is easy to determine rook attacks across a rank, using a table indexed by the occupied square and the occupied positions in the rank (because rook attacks stop at the first occupied square). By rotating the bitboard 90 degrees, rook attacks up and down a file can be examined the same way. Bitboards rotated 45 degrees and 315 degrees (-45 degrees) have diagonals that are easy to examine, for determining bishop attacks. The queen can be examined by combining rook and bishop attacks. The rotation of a bitboard, however, is an inelegant transformation that can take dozens of instructions.[2][3]

Direct hashing

The attack vectors of rooks and bishops can be separately masked and used as indices into a hash table of precomputed attack vectors depending on occupancy: 8 bits each for rooks and from 2 to 8 bits each for bishops. The full attack vector of a piece is obtained as the union of each of the two unidirectional vectors indexed from the hash table. The number of entries in the hash table is modest, on the order of bytes, or about 2 kilobytes. Two hash function computations and two lookups per piece are required for the hashing scheme.[4][5]

Magic bitboards

Early chess engines used ray-casting loops, rotated bitboards, or direct hashing. Now, most chess engines use magic bitboards. Magic bitboards use a multiply-right-shift perfect hashing algorithm to directly map sliding piece (Rook, Bishop, or Queen) occupancy to attack patterns in a single constant time lookup O(1).[6]

Mechanics

Magic bitboards optimize the time-space tradeoff of direct hashing attacks. Unlike traditional bitboards, magic bitboards exploit the full attack vector as a hash table key, thus implementing a perfect hash function. Magic bitboards typically do not store attack vectors. They rely on tricks to reduce the hash table size, which is bytes (144 exabytes). [nb 1]

When aiming for the highest efficiency, all outer board edges (1st and 8th ranks, and A and H files) are removed. Sliding pieces attack all those squares. Blocking pieces past the first obstacle along a ray do not affect the piece's attack area. Relevant edge squares are removed. This reduces the maximum amount of relevant occupancy bits per square from 64 to 12 for central rooks, and to 5 for corner bishops.[7]

The attack index I for a given square and piece type is computed using a multiply-right-shift bitwise formula:

Where:

  • O is the 64-bit occupancy bitboard representing relevant blocking pieces on the slider's attack rays.
  • M is a square-specific 64-bit unsigned integer constant (magic number).
  • N is the number of bits required to index the attack lookup table for that specific square.
  • >> represents a bitwise right-shift operation (Isolates the significant bits of the 64-bit multiplication product to yield a dense array index[8])

This shows how magic bitboards allow moves of a rook to be calculated in O(1) time and without performing a move a square at a time. The program first notes the Current Position. Then it selects which squares, if any, can block the rook using a bitwise mask (Relevant Occupancy Mask). Then it selects which pieces are in those key squares (Relevant Piece Occupancy). To map the 64-bit integer to a small lookup table without collisions, it is multiplied by a pre-calculated 64-bit constant magic number. This multiplication acts as a bit permutation, hash, and pack directly into the top N most significant bits of the product. Shifting this product to the right by (64 - N) drops the lower bits, and creates a unique array index which is then used to retrieve the pre-computed Raw Attacks bitboard. The last step is removing the friendly pieces on e2, and this creates the Legal Moves.

Generating Magic Numbers

Each unique mapping sent by a magic number multiplier is tied to a different associated square configuration. Because of this, compatible magic numbers cannot be derived analytically, rather, are for the most part found through a structured process of trial and error. With Kannan's methodology, the components of a magic number are treated as variables and the process is generally composed of the following three steps:[9]

  1. Setting the Variables: All components of the candidate 64-bit magic number are left undefined as variables.
  2. Finding the Index Mappings: All possible occupancy configurations for the given square are multiplied against the variable magic number. This process is valid as a result of the fact that multiplying a number by a power of two is effectively the magic number performing a left bit shift.
  3. Finding Solutions By Trial and Error: Guessing is done in the most optimally ordered way to reduce redundancy in the search. After each guess, every potential input is checked against resolved indices to see if the index is clear. If two inputs yield the same resolved index and are not part of the same collision, solution is rejected and another value is guessed.

This is usually repeated independently for each of the 64 squares and for both rooks and bishops. It is normally run once, offline, before a chess engine's runtime, or the magic numbers hardcoded into the program.[9]

Constructive Collisions

Unlike most hash tables where hash collisions degrade performance, magic bitboards purposefully rely on constructive collisions. Distinct board occupancy configurations along one attack ray that yield the exact same legal move set (e.g., two pieces standing in line behind an initial blocker) are mapped to the exact same hash index, since the result is identical regardless of which of the two board positions actually occur in game.[10] This allows the technique to compress sparse and high dimensional occupancy space data down to a more dense lookup table without any loss in accuracy and correctness.

Implementation Variants

Magic bitboard architectures mostly fall into two structural implementations:

  • Plain Magics: Uses fixed and uniform multidimensional array sizes across all squares. While straightforward, it requires approximately 2.3 MB of total memory.[11]
  • Fancy Magics: Sizes lookup tables dynamically stored according to the exact number of relevant bits (2^n) needed for each individual square. This reduces the total memory footprint to under 840 KB.[11]

Like other perfect hashing schemes, generating valid magic numbers requires a pre-initialization process using Monte Carlo trial-and-error algorithms.[11] While magic bitboards are the primary lookup method in modern engines like Stockfish, their memory access patterns can occasionally cause cache misses on processors with a smaller cache.[12]

BMI2 instruction set optimization

On modern x86-64 processors supporting the BMI2 (Bit Manipulation Instruction Set 2) architecture, the calculation of chess sliding piece attacks can be accelerated directly via hardware, removing the need for magic multiplier hashing. This approach utilizes the parallel bit extract (_pext_u64) and parallel bit deposit (_pdep_u64) assembly instructions. The PEXT instruction uses a pre-computed blocker mask to extract the relevant occupancy bits directly into a contiguous, zero-extended index. This index is then used to perform an instantaneous array lookup for the attack map, optimizing CPU register usage and eliminating potential cache misses associated with larger magic lookup tables.[13]

History

The bitboard method for representing a board game is credited to Arthur Samuel, who used it in the mid-1950s in his checkers program.[14] For the more complicated game of chess, the method was credited to both the Kaissa team in the Soviet Union in the late 1960s,[15] and to the authors of the U.S. Northwestern University program "Chess" in the early 1970s. The 64-bit word length of 1970s supercomputers like Amdahl and Cray machines facilitated the development of bitboard representations, which conveniently mapped the 64-squares of the chessboard to bits of a word.

Rotated bitboards for collating the moves of sliding pieces were invented by Professor Robert Hyatt, author of Cray Blitz and Crafty chess engines, sometime in the mid-1990s and shared with the Dark Thought programming team. They were later implemented in Crafty and Dark Thought, but the first published description wasn't until 1997.

Prior to 2006, the primary state-of-the-art technique for sliding move generation was rotated bitboards, introduced by Professor Robert Hyatt, author of Cray Blitz and Crafty chess engines in the mid-1990s for the Crafty engine.[16] Rotated bitboards maintained four seprate, synchronized 64-bit representations of the board rotated at 0°, 90°, 45°, and -45°. While this bypassed slow ray-scanning loops, keeping four parallel board states updated after every move created significant CPU cache thrashing.[17]

In the mid 2000s, two related but independently developed alternatives for rotated bitboards emerged. Magic bitboards were proposed around 2006 by Lasse Hansen, with Gerd Isenberg independently developing a separated-direction variant. Pradu Kannan's 2007 paper documented the mathematics behind the approach and a general methodology for generating optimal magic numbers.[18] Around that time, an intermediate, alternate approach was proposed by Sam Tannous. Directing hashing via masked rank, file and diagonal lookup was more efficient in that it avoided maintenance of redundant board copies, though it still required two separate hash computations and lookups per piece. [19] Magic bitboards use the same direct-hashing idea but completely replacing Tannous's two-hash-table lookup and collapsing it into a single perfect-hash multiplication, allowing engines to evaluate board states using a single, unified bitboard representation, and have since been the dominant technique in modern engine.[20]

Other games

Many other games besides chess benefit from bitboards.

  • In Connect Four, they allow for very efficient testing for four consecutive discs, by just two shift + AND operations per direction.
  • In Conway's Game of Life, they are a possible alternative to arrays.
  • They are also used in Reversi (also known as Othello).

See also

Notes

  1. ↑ Use of a perfect hash function is not required for implementation of this method, and provides only a vanishingly small benefit over standard hashing methods.

References

  1. ↑ Atkin, Larry R.; Slate, David J. (1983) [1977]. "Chess 4.5: the Northwestern University Chess Program". In Frey, Peter W. (ed.). Chess Skill in Man and Machine (2 ed.). Springer Verlag. pp. 82–118. CiteSeerX 10.1.1.111.926. ISBN 0-387-90790-4. {{cite book}}: Cite uses deprecated parameter |citeseerx= (help)
  2. ↑ Heinz, Ernst A. (September 1997). "How Dark Thought Plays Chess". ICCA Journal. 20 (3): 166–176.
  3. ↑ Hyatt, Robert (1999). "Rotated Bitboards: New Twist on an Old Idea". Archived from the original on 2005-04-28.
  4. ↑ Tannous, Sam (2007-07-23) [2006]. "Avoiding Rotated Bitboards with Direct Lookup". ICGA Journal. 30 (2) (2 ed.). Durham, North Carolina, USA: 85–91. arXiv:0704.3773v2. CiteSeerX 10.1.1.561.3461. doi:10.3233/ICG-2007-30204. {{cite journal}}: Cite uses deprecated parameter |citeseerx= (help)
  5. ↑ Knuth, Donald (1973). "Section 6.4. Algorithm D (Open addressing with double hashing)". The Art of Computer Programming. Vol. 3.
  6. ↑ "Magic Bitboards". Chess Programming Wiki. Retrieved 2026-07-26.
  7. ↑ "Magic Bitboards". Chess Programming Wiki. Retrieved 2026-07-26.
  8. ↑ Cite error: The named reference CPWMagic4 was invoked but never defined (see the help page).
  9. 1 2 Kannan, Pradyumna (2007-04-30). "Magic Move-Bitboard Generation in Computer Chess" (PDF).
  10. ↑ "Magic Bitboards". Chess Programming Wiki. Retrieved 2026-07-26.
  11. 1 2 3 "Magic Bitboards". Chess Programming Wiki. Retrieved 2026-07-26.
  12. ↑ Vrzina, Sander (July 2023). Piece by Piece: Building a Strong Chess Engine (PDF) (BSc thesis thesis). Vrije Universiteit Amsterdam. pp. 11–13.
  13. ↑ "BMI2 Optimization for Bitboards". Chess Programming Wiki. Chess Programming Wiki. 2026-03-03. Retrieved 2026-06-18.
  14. ↑ "Some Studies in Machine Learning Using the Game of Checkers". IBM Journal of Research and Development. 1959.
  15. ↑ Adel'Son-Vel'Skii, G. M.; Arlazarov, V. L.; Bitman, A. R.; Zhivotovskii, A. A.; Uskov, A. V. (1970). "Programming a computer to play chess". Russian Mathematical Surveys. 25 (2): 221. Bibcode:1970RuMaS..25..221A. doi:10.1070/RM1970v025n02ABEH003792.
  16. ↑ Hyatt, Robert (December 1999). "Rotated Bitmaps, a New Twist on an Old Idea". ICCA Journal. 22 (4): 213–222. doi:10.3233/ICG-1999-22403.
  17. ↑ "Magic Bitboards". Chess Programming Wiki. Retrieved 2026-07-26.
  18. ↑ Kannan, Pradyumna (2007-04-30). "Magic Move-Bitboard Generation in Computer Chess" (PDF).
  19. ↑ Tannous, Sam (2007). "Avoiding Rotated Bitboards with Direct Lookup". ICGA Journal. 30 (2): 85–91. arXiv:0704.3773.
  20. ↑ Browne, Cameron (June 2014). "Bitboard Methods for Games". ICGA Journal. 37 (2): 67–84. doi:10.3233/ICG-2014-37202.
  21. Sherwin, Michael; Isenberg, Gerd (2006-12-04). "Magic Bitboards Explained!". Winboard Forum. Call it Kindergarten Bitboards
  22. Hansen, Lasse (2006-06-14). "Fast(er) bitboard move generator". Winboard Forum..
Cite error: A list-defined reference named "Sherwin_2006" is not used in the content (see the help page).
Cite error: A list-defined reference named "Hansen_2006" is not used in the content (see the help page).

Further reading

Calculators

Checkers

Chess

Articles

Code examples

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

Implementations

Open source
  • Beowulf Unix, Linux, Windows. Rotated bitboards.
  • Crafty See the Crafty article. Written in straight C. Rotated bitboards in the old versions, now uses magic bitboards.
  • GNU Chess See the GNU Chess Article.
  • Stockfish UCI chess engine ranking second in Elo as of 2010
  • Gray Matter C++, rotated bitboards.
  • KnightCap GPL. ELO of 2300.
  • Pepito C. Bitboard, by Carlos del Cacho. Windows and Linux binaries as well as source available.
  • Simontacci Rotated bitboards.
Closed source

Othello

Word games

allikas: https://en.wikipedia.org/wiki/Bitboard