Editing Bitboard (section)

====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"/>