Editing Bitboard (section)

== Chess bitboards ==
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.  Faster, but more elaborate data structures that map pieces to locations are called ''bitboards''.

===Standard===
[[File:SCD algebraic notation.svg|right|[[Algebraic notation (chess)|Algebraic notation]]|frame]]
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 usually 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 like one representing the first rank, which would have one bits in positions 0 - 7.  Other local or transitional bitboards like "all spaces adjacent to the king attacked by opposing pieces" may be collated as necessary or convenient.<ref name="Atkin_1977"/>

An example of the use of the bitboards would be determining whether a piece is '' [[Glossary of chess#en prise|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 ===
In acknowledgement of the code size and computing complexity of generating bitboards for the attack vectors of sliding pieces, alternate bitboard data structures have been devised to collate them.  The bitboard representations of knights, kings, pawns and other board configurations is 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 will have one byte per rank of the chess board. With this bitboard it's 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. Adding bitboards rotated 45 degrees and 315 degrees (-45 degrees) produces bitboards in which the diagonals are easy to examine. The queen can be examined by combining rook and bishop attacks.  Actually rotating a bitboard is an inelegant transformation that can take dozens of instructions.<ref name="Heinz_1997"/><ref name="Hyatt_1999"/>

====Direct hashing====
The rank and file attack vectors of rooks and the diagonal and anti-diagonal attack vectors of 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 2-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 8*2^8 or 2K bytes, but two hash function computations and two lookups per piece are required.,<ref name="Tannous_2007"/> see the hashing scheme employed.<ref name="Knuth_1973"/>

====Magic bitboards====
Magic bitboards are an extrapolation of the time-space tradeoff of direct hashing lookup of attack vectors. These use a transmutation of the full attack vector as an index into the hash table.  ''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 [[exabyte]]s.<ref group="nb" name="NB1"/>  The first observation is that the ''outer squares'' or first and eighth ranks together with the 'a' and 'h' files are irrelevant to the occupancy of the attack vector: the piece attacks those squares or not (depending on other blocking pieces) regardless of occupancy, so these can be eliminated from consideration, leaving just 6x6 or 36 squares (~bits in the corresponding hash function). As with other schemes which require a perfect hashing function, an exhaustive process of enumeration, partly algorithmic and partly trial and error, is necessary to generate the hash function.  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.  So magic bitboards in many applications provide no performance gain over more modest hashing schemes or rotated bitboards.<ref name="Sherwin_2006"/><ref name="Hansen_2006"/>