User:Jmulada/Bitboard

This is the sandbox page where you will draft your initial Wikipedia contribution. If you're starting a new article, you can develop it here until it's ready to go live. If you're working on improvements to an existing article, copy only one section at a time of the article to this sandbox to work on, and be sure to use an edit summary linking to the article you copied from. Do not copy over the entire article. You can find additional instructions here. Remember to save your work regularly using the "Publish page" button. (It just means 'save'; it will still be in the sandbox.) You can add bold formatting to your additions to differentiate them from existing content. Bibliography sandbox Outline sandbox

While early chess engines relied on ray-casting loops, rotated bitboards, or direct hashing, modern chess engines predominantly utilize magic bitboards.This technique employs a multiply-right-shift perfect hashing algorithm to map a sliding piece's (Rook, Bishop, or Queen) occupancy configuration directly to a precomputed array of attack patterns in a single O(1) constant-time lookup operation.^[1] The sections below trace the technique's historical origins, detailing the multiplication mechanics behind the hashing formula, the constructive collisions that make it possible, the searching process for valid magic numbers and memory tradeoffs of variants.

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.^[2] 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.^[3]

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.^[4] 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. ^[5] 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.^[6]

Magic bitboards are an extrapolation of the time-space tradeoff of direct hashing lookups for attack vectors. They use a transmutation of the full attack vector as an index into a lookup table. Uncompressed direct hashing across all possible board occupancies would require a table size of 8 times 2^64 bytes, which is memory-prohibitive.^[1]

To minimize the state space, outer board edges (the 1st and 8th ranks, along with the 'a' and 'h' files) are masked out. A sliding piece attacks those outer squares regardless of whether an enemy piece stands on them; blocking pieces past the first obstacle along a ray do not alter the piece's immediate attack footprint. Eliminating irrelevant edge squares reduces the maximum relevant occupancy bits per square from 64 down to a maximum of 12 bits for central rooks, and as few as 5 bits for corner bishops.^[1]

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

${\displaystyle I=(O\times M)\gg (64-N)}$

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 (the "magic multiplier").
• N is the number of bits required to index the attack lookup table for that specific square.
• >> represents a bitwise right-shift operation, which isolates the most significant bits of the 64-bit multiplication product to yield a dense array index.^[1]

Because a magic number multiplier must map every relevant occupancy configuration for a given square to a unique index, compatible magic numbers cannot be derived analytically and are instead found through a structured trial-and-error search. Kannan's methodology treats the bits of a potential magic number as unknowns and then proceeds in three general steps:^[4]

1. Assume variable bits in the magic: Each bit of the candidate 64-bit magic number is initially left undetermined.
2. Compute index mapping symbolically: Every possible occupancy input for the square is multiplied against the variable magic to express each resulting index as a symbolic function of the unknown bits, exploiting the fact that multiplying by a power of two is essentially a left-shift.
3. Resolve bits by trial-and-error, checking for any collisions: Bits are guessed one at a time, in an order chosen to minimize wasted search effort. After each guess, any input whose index can already be found is checked against previously resolved indices. If two inputs resolve to the same index without being part of the same collision group, the guess is rejected and another value is tried instead.

This process is repeated independently for each of the 64 squares and for both rook and bishop attack sets, and is normally run once, offline, before a chess engine's runtime, with the resulting magic numbers hardcoded into the program.^[4]

Unlike general-purpose hash tables where hash collisions degrade performance, magic bitboards purposefully rely on constructive collisions. Multiple distinct occupancy configurations along an attack ray that yield the exact same legal move set (for instance, two pieces standing in sequence behind an initial blocker) are intentionally mapped to the exact same hash index, since the resulting attack set is identical regardless of which of the two configurations actually occurred.^[1] This property is what allows the technique to compress a sparse, high-dimensional occupancy space down to a small, dense lookup table without any loss of correctness.

Magic bitboard architectures generally fall into two structural implementations:

• Plain Magics: Uses fixed, uniform multidimensional array sizes across all squares. While computationally straightforward, it requires approximately 2.3 MB of total memory.^[1]
• Fancy Magics: Sizes lookup tables dynamically 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, allowing the entire move table to fit inside fast CPU L1/L2 caches.^[1]

As with other perfect hashing schemes, generating valid magic numbers requires a pre-initialization process using Monte Carlo trial-and-error algorithms.^[1] 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 smaller cache topologies compared to simpler stepping-piece arrays.^[7]