Magic Bitboards
Explained

§ 01 Before You Begin

This article aims to be concise and accessible. For those who prefer a deeper dive, the following resources cover the topic with great rigour:

• Chess Programming Wiki — Magic Bitboards
• Pradu's original writeup
• Generating Magic Multipliers — Chessprogramming.net
• Chess Move Generation with Magic Bitboards (essay)

§ 02 What Are Magic Numbers?

In a chess engine, computing the legal moves for sliding pieces — bishops, rooks, and queens — during a deep search is one of the most performance-critical operations. Naïvely iterating over the board square by square on every node is prohibitively slow.

The solution is precomputation. We calculate all possible moves for every piece on every square ahead of time and store them as 64-bit integers called bitboard masks. During the actual search, retrieving the moves for any position then becomes a simple table lookup — extremely fast.

This technique applies to bishops (moving diagonally) and rooks (moving along ranks and files), and therefore to queens as well (since queen moves are the union of the two). In deep searches with millions of nodes, the performance gain is substantial.

§ 03 Framing the Problem

The key insight that makes the problem tractable is to break it into independent sub-problems. We solve it one square at a time: if we can find the magic for a bishop sitting on E4, we can apply the same method to all 64 squares independently. We also treat bishops and rooks separately — their movement patterns are different, but the approach is identical.

Start with an empty board and place a bishop on E4. The squares it can reach are shown below (the black dots represent all potential destination squares, ignoring any blocking pieces for now):

In a real game, other pieces will stand on those diagonals and block the bishop's path. Place some blocking pieces on the board. The blue dots now mark the actually legal moves — the squares the bishop can reach before being stopped by a blocker:

Note that we do not distinguish between friendly and enemy pieces at this stage. Any piece stops the bishop's ray. We can filter out captures of our own pieces afterward with a simple bitmask: moves & ~ourPieces. What we care about here is purely where the bishop can go given the occupancy.

§ 04 Building the Lookup Table

Now imagine enumerating every possible arrangement of blocking pieces on the bishop's diagonals — every permutation of occupancy — and recording the corresponding set of legal moves. This gives us a two-column table:

This table is our ground truth. A table generation tool is available if you want to inspect the data directly or export it to a database.

The table works — but querying a general database during a search is far too slow. We need a mathematical function that maps any occupancy bitboard instantly to the correct row of legal moves. That function is what the magic number provides.

§ 05 Constructing the Magic Index

Expand the table by inserting a middle column — the computed index. This column will serve as the array index into our in-memory move table:

The goal is to find a mathematical function that fills in the index column such that no two distinct occupancies that produce different move sets share the same index. Collisions between occupancies that happen to produce identical legal moves are acceptable — they can share a slot.

The search procedure works as follows:

1. Clear the index column (zero out the move array).
2. Iterate over every possible blocker occupancy and compute a candidate index using the current magic number.
3. Use that index as an array pointer and attempt to write the corresponding legal moves into that slot.
4. If every slot either remains empty or already holds an identical move set, we have a valid magic — the search succeeds.
5. If any slot would be overwritten with a different move set (a true collision), the candidate magic is invalid. Pick a new candidate and restart from step 1.

The underlying goal is to find an array large enough to accommodate one unique entry per distinct move set, indexed without destructive collisions. Allowing a larger array (more bits) makes valid magics easier to find; a tighter array requires rarer, harder-to-find numbers. Once a valid magic is found, the move array is populated once at engine startup and then queried in constant time during the search.

§ 06 The Fast Math — Multiply and Shift

Why multiplication? It is the ideal operator for this purpose: it produces a result that is partly proportional and partly pseudo-random, spreading different inputs across a wide range of outputs efficiently. A subsequent right bit-shift then compresses the large 64-bit product down to a small array index.

The full formula for retrieving the bishop's legal moves from any position is:

Both MagicNumber and shiftNumber for each square can be found by random trial: generate a 64-bit random number with few set bits, run the validation procedure above, and repeat until a valid magic is found. Alternatively, use precomputed values from established chess engines or generate them with a dedicated tool — a magic generator is available, and the source code is also on GitHub.

§ 07 Additional Details

A common optimisation is to exclude the edge squares of the diagonals from the occupancy mask. A piece on the board edge always stops the ray regardless, so it carries no information — including it only wastes index bits. This is why you will often see the inner 6×6 region (B2–G7) used as the relevant occupancy area, rather than the full diagonals. The resulting tables are somewhat smaller and the magics slightly easier to find.

The magic number technique is not limited to bishops and rooks. It generalises to any situation where a lookup from a compact, occupancy-derived key is needed — including advanced pawn move generation, pin detection, and check evasion masks. Many parts of a modern chess engine can be accelerated using the same principle.

Furthermore, there are alternative hash functions beyond plain multiplication. Some engines use XOR-folding, PEXT (a BMI2 hardware instruction available on modern x86 CPUs that extracts bits directly), or other bit-manipulation tricks. Each has trade-offs in portability, table size, and CPU-specific speed.

§ 08 Reality Check