Bitboard

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.

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.

Bitboards allow the computer to answer some questions about game state with one bitwise operation.

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.

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?"

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.

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.

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

Other local or transitional bitboards like "all spaces adjacent to the king attacked by opposing pieces" may be collated as necessary or convenient.

With these bitboards, a single table lookup replaces lengthy sequences of bitwise operations.

[5] Magic bitboards are an extrapolation of the time-space tradeoff of direct hashing lookup of attack vectors.

Magic is a misnomer, and simply refers to the generation and use of a perfect hash function in conjunction with tricks to reduce the potential size of the hash table that would have to be stored in memory, which is 8*2^64 or 144 exabytes.

But the intractable issue remains: these are very active tables, and their size (fewer than a million entries in most cases) is huge relative to the lower level cache sizes of modern chip architectures, resulting in cache flooding.

[6][7] The bitboard method for representing a board game appears to have been invented in the mid-1950s, by Arthur Samuel and was used in his checkers program.

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.

Today, game programs remain divided, with the best scheme being application dependent.