Magic Bitboards in Java: What Finally Made Them Click

I remember where I was the first time I opened an article about magic bitboards. Second year, a laptop that ran hot, a half-finished chess engine in Java that could just about tell a legal knight move from an illegal one. I searched for a way to make rook and bishop moves faster and got hit in the face with a wall of hexadecimal.

0x0080001020400080L. Sixty-four of those. Then a paragraph about "relevant occupancy," then something called a "perfect hash," then a table labelled shifts with no explanation of what was being shifted. I scrolled to the bottom hoping for a summary and found a downloadable file of magic constants plus a cheerful note that finding your own was left as an exercise.

I closed the tab. Not in frustration — more like walking into the wrong lecture hall. Whatever this was, it assumed I already knew something I didn't, and I couldn't identify what.

What I didn't expect: when I came back five months later, after writing ray-based move generation by hand and staring at bitboards until I could read them, the same article was almost boring. The hexadecimal was still opaque, but it no longer mattered, because I finally understood what the numbers were for.

None of this is my invention. Magic bitboards have been part of chess programming for decades, refined by many people on forums and mailing lists, and used by a great many strong engines. What's mine is the learning path — the confusions, the bugs, and the moment it stopped feeling like magic.

Table of Contents

• Why I ignored magic bitboards at first
• The problem magic bitboards actually solve
• The insight that finally made sense
• Understanding occupancy masks
• Where the "magic" comes from
• Building it in Java
• The bugs that nearly broke my brain
• Visual debugging saved me
• What actually improved
• When you probably shouldn't use them
• Reading Stockfish suddenly felt different
• If I were learning again
• Lessons beyond chess programming
• Frequently asked questions
• Conclusion

Why I Ignored Magic Bitboards At First

Most introductions to this topic share a structure. Paragraph one: sliding pieces are slow. Paragraph two: here is the occupancy mask. Paragraph three: multiply by the magic number and shift right by 64 - bits. Paragraph four: here are the constants, good luck.

Every statement is true. Together they explain nothing, because they answer how without answering why this shape of solution. What blocked me:

• "Magic number." A name that resists understanding. It sounds like the number has a property you're meant to already know about. It doesn't — it's a constant that happens to work, found by trial.
• "Perfect hashing." I'd met hash maps. Nobody stopped to say that "perfect" just means no two inputs collide.
• "Relevant occupancy." Relevant to what? This turned out to be the actual key, and every article gave it half a sentence.
• Lookup tables. I understood caching fine. I didn't understand what was being cached.

So I made a decision that felt like giving up and was the best call of the project: write plain ray-based move generation first, and not touch an optimisation until it was provably correct. I wrote tests, fixed board-wrapping bugs, got perft numbers matching published values — and somewhere in those weeks I stopped thinking in squares and started thinking in rays and blockers. That vocabulary shift is the entire prerequisite. The problem only becomes real once you've solved it the slow way.

The Problem Magic Bitboards Actually Solve

Knights and kings jump — a knight on d4 attacks the same eight squares regardless of the board, so you precompute its attacks once and you're done forever. Rooks, bishops and queens slide, and their attacks depend on everything around them.

Rook on d4, empty board — 14 attacked squares

     a   b   c   d   e   f   g   h
   +---+---+---+---+---+---+---+---+
 8 |   |   |   | * |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 7 |   |   |   | * |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 6 |   |   |   | * |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 5 |   |   |   | * |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 4 | * | * | * | R | * | * | * | * |
   +---+---+---+---+---+---+---+---+
 3 |   |   |   | * |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 2 |   |   |   | * |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 1 |   |   |   | * |   |   |   |   |
   +---+---+---+---+---+---+---+---+

Now drop a pawn on d6 and another on b4, and watch the attack set collapse:

Same rook, two blockers (P)

     a   b   c   d   e   f   g   h
   +---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 6 |   |   |   | P |   |   |   |   |   <- attacked, nothing beyond
   +---+---+---+---+---+---+---+---+
 5 |   |   |   | * |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 4 |   | P | * | R | * | * | * | * |   <- b4 cuts the west ray
   +---+---+---+---+---+---+---+---+
 3 |   |   |   | * |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 2 |   |   |   | * |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 1 |   |   |   | * |   |   |   |   |
   +---+---+---+---+---+---+---+---+

Fourteen squares became ten. The rook didn't move; the board around it did.

Here's where it gets expensive. A search engine doesn't ask this once — it walks a tree, millions of nodes, each needing sliding attacks recomputed. The ray walk is a loop with a data-dependent exit, so the CPU can't predict when it stops. Worse, transpositions mean the identical rook-on-d4-with-these-blockers question is asked over and over, and my generator answered it from scratch every time.

I'm deliberately not putting numbers in that table. I never ran a controlled benchmark of my two implementations, and inventing figures would be worse than useless.

The Insight That Finally Made Sense

The breakthrough came on a train, no laptop, sketching positions in a notebook. I was drawing the same rook on d4 with different blocker arrangements and noticed I kept drawing the same attack pattern. A pawn on d6 gave one picture. A pawn on d6 and a knight on d7 gave the identical picture — the rook never sees past d6. A queen on d6 gave it again. So did a bishop, a rook, an enemy king. Then it landed:

A pure function with a finite input domain is just a table you haven't built yet. That's the whole idea. Masks, magics, shifts — all of it is plumbing to make that table lookup fast.

The lamp and the pillars

Picture a room with a lamp in one corner and pillars scattered around. The lamp is fixed; the shadows depend entirely on where the pillars stand. Move a pillar and the shadows change; move a chair that's already in shadow and nothing changes. And if pillars can only stand in so many places, there are only so many shadow patterns — you could photograph every one in advance, and "computing the shadows" becomes "which photo is this?" The rook is the lamp, the blockers are the pillars, the attacked squares are the lit ones.

The vending machine

A vending machine doesn't reason about your snack. You press a code, it maps to a slot, the item is waiting — the intelligence went in when it was stocked. Magic bitboards stock the machine at startup using the slow ray walk I already had, and the multiply-and-shift is the keypad: it turns a messy blocker pattern into a small button number.

Why the numbers stay small

My worry was combinatorial explosion — the board has 2⁶⁴ possible occupancies. But that's not the input domain. The domain is "occupancy along this rook's rays, excluding squares that can't matter." For a central rook that's typically 10 squares, so 2¹⁰ = 1024 arrangements; a bishop often has 5 to 9, so at most 512. Across all 64 squares that's a few hundred thousand entries for rooks and bishops combined — megabytes, which was a fortune in 1995 and is nothing now.

The moment I did that arithmetic on the back of a train ticket, the fear went. This wasn't advanced mathematics. It was memoisation with a good indexing scheme.

Understanding Occupancy Masks

The occupancy mask is the piece I'd skimmed for months, and it does the real work. It answers: which squares can possibly affect this piece's attacks from this square? Everything else is noise. Two rules define it:

1. Only squares along the piece's own rays matter. A pawn on h7 is invisible to a rook on a1.
2. The last square of each ray is excluded. This surprised me, and it's the clever bit.

Take the rook on d4 looking north. If the only piece up there is on d8, the rook attacks d5–d8, sliding to the blocker and including it as a capture target. Remove that piece and the rook attacks d5–d8 again, because the ray runs to the edge. Identical output either way, so d8's state is unobservable — including it would double the table for zero information.

Rook occupancy mask for d4 — x = relevant, . = excluded

     a   b   c   d   e   f   g   h
   +---+---+---+---+---+---+---+---+
 8 |   |   |   | . |   |   |   |   |   <- edge
   +---+---+---+---+---+---+---+---+
 7 |   |   |   | x |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 6 |   |   |   | x |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 5 |   |   |   | x |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 4 | . | x | x | R | x | x | x | . |   <- a4, h4 edges
   +---+---+---+---+---+---+---+---+
 3 |   |   |   | x |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 2 |   |   |   | x |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 1 |   |   |   | . |   |   |   |   |   <- edge
   +---+---+---+---+---+---+---+---+

10 mask bits -> 2^10 = 1024 blocker arrangements

The bishop's mask on the same square is smaller, because diagonals are shorter and lose an edge square in every direction:

Bishop occupancy mask for d4

     a   b   c   d   e   f   g   h
   +---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   | . |   |
   +---+---+---+---+---+---+---+---+
 7 | . |   |   |   |   | x |   |   |
   +---+---+---+---+---+---+---+---+
 6 |   | x |   |   | x |   |   |   |
   +---+---+---+---+---+---+---+---+
 5 |   |   | x |   | x |   |   |   |
   +---+---+---+---+---+---+---+---+
 4 |   |   |   | B |   |   |   |   |
   +---+---+---+---+---+---+---+---+
 3 |   |   | x |   | x |   |   |   |
   +---+---+---+---+---+---+---+---+
 2 |   | x |   |   |   | x |   |   |
   +---+---+---+---+---+---+---+---+
 1 | . |   |   |   |   |   | . |   |
   +---+---+---+---+---+---+---+---+

9 mask bits -> 2^9 = 512 blocker arrangements

A bishop on a1 has only 6 mask bits — 64 arrangements. That asymmetry is why implementations store a per-square shift rather than one global constant. At runtime, applying the mask is a single AND:

long relevant = boardOccupancy & ROOK_MASK[square];

Everything irrelevant is now zero. What's left is the key we look up.

Where the "Magic" Comes From

So we have a 64-bit word with a handful of scattered bits, and we need a small array index. That's the entire remaining problem.

The obvious approach is to gather the bits with a loop — walk the mask positions, test each, build the index bit by bit. It works, and it's what my first version did. It's also a loop, which is what we were escaping.

Magic replaces it with one multiplication. Multiplying a 64-bit value by a constant produces a sum of shifted copies of that value, one per set bit in the constant — so it smears many displaced copies of your pattern across the word at once. Pick the constant well and those copies line up so the bits you care about, previously spread out with big gaps, all land in a compact block at the top of the product. The lower bits become garbage, thrown away by the shift.

  scattered blocker bits    ....1...0.....1......0..1.......
            * magic         (many shifted copies, summed)
            = product       garbage garbage garbage [1 0 1 0 1]
            >>> (64 - 10)   -----------------------> a small index

That's the magic: a hash function whose implementation happens to be "multiply by a number someone found by trying candidates until one worked." Two properties make a constant valid for a square:

• Collision-free — two different blocker patterns mustn't map to the same index, unless they happen to share an attack set anyway. That case is a harmless "constructive collision," and good magics exploit it to shrink tables.
• Compact — the index must fit the bit budget for that square, so the table stays small.

How are they found? Brute force. Generate random 64-bit numbers with few set bits, test each against every blocker pattern for that square, keep any with no destructive collisions. A full set for all 128 cases takes seconds to minutes. There's no closed form — nobody derives 0x0080001020400080L from first principles. I found that reassuring: the scariest-looking numbers in the technique are the least meaningful ones.

Building It in Java

Java suits this well, because a chess board has 64 squares and a Java long has exactly 64 bits — one long, one set of squares, nothing wasted. And java.lang.Long exposes the operations bitboard code needs as JIT intrinsics that compile to single machine instructions.

long bb = 0b1011L;

Long.bitCount(bb);              // 3  -> how many squares are in this set
Long.numberOfTrailingZeros(bb); // 0  -> index of the lowest set square

In plain English: bitCount tells you how many pieces a bitboard holds — how you count material or size a table. numberOfTrailingZeros gives the lowest set bit's index, which is how you pull squares out one at a time:

// Visit every set square in a bitboard.
long bb = someBitboard;
while (bb != 0) {
    int square = Long.numberOfTrailingZeros(bb);
    doSomethingWith(square);
    bb &= bb - 1;   // clears the lowest set bit
}

The bb &= bb - 1 trick is worth internalising: subtracting one flips the lowest set bit to zero and everything below to one, so the AND wipes exactly that bit. The loop runs once per occupied square, not 64 times.

The occupancy mask

// Squares that can block a rook on 'square'.
// Walk each ray but stop BEFORE the final square.
static long rookMask(int square) {
    long mask = 0L;
    int r = square / 8, f = square % 8;

    for (int i = r + 1; i <= 6; i++) mask |= 1L << (i * 8 + f);  // north
    for (int i = r - 1; i >= 1; i--) mask |= 1L << (i * 8 + f);  // south
    for (int i = f + 1; i <= 6; i++) mask |= 1L << (r * 8 + i);  // east
    for (int i = f - 1; i >= 1; i--) mask |= 1L << (r * 8 + i);  // west

    return mask;
}

The bounds are the whole story — the loops stop at 6 and 1 rather than 7 and 0, which is the edge-exclusion rule in code. Each mask |= 1L << n means "square n is in this set."

The slow attack calculation

// The reference implementation. Slow, correct, used only at init.
static long rookAttacksSlow(int square, long blockers) {
    long attacks = 0L;
    int r = square / 8, f = square % 8;

    for (int i = r + 1; i <= 7; i++) {
        attacks |= 1L << (i * 8 + f);
        if ((blockers & (1L << (i * 8 + f))) != 0) break;  // include, then stop
    }
    // ...same for south, east, west
    return attacks;
}

Here the loops do run to the edge, stopping after including the blocker. Include-then-break is the correct order; reversing it silently removes every capture from your move list.

Enumerating blocker arrangements

// Produce the index-th subset of the given mask.
static long setOccupancy(int index, long mask) {
    long occupancy = 0L;
    int bits = Long.bitCount(mask);

    for (int i = 0; i < bits; i++) {
        int square = Long.numberOfTrailingZeros(mask);
        mask &= mask - 1;                    // consume that bit
        if ((index & (1 << i)) != 0) {
            occupancy |= 1L << square;       // this subset includes it
        }
    }
    return occupancy;
}

The loop counter's bits act as a selector over the mask's set bits. Run index from 0 to 2^bits−1 and you generate every arrangement exactly once.

The lookup

static int magicIndex(long blockers, long magic, int shift) {
    return (int) ((blockers * magic) >>> shift);
}

static long rookAttacks(int square, long occupancy) {
    long blockers = occupancy & ROOK_MASK[square];
    return ROOK_ATTACKS[square][
        magicIndex(blockers, ROOK_MAGIC[square], ROOK_SHIFT[square])];
}

static long bishopAttacks(int square, long occupancy) {
    long blockers = occupancy & BISHOP_MASK[square];
    return BISHOP_ATTACKS[square][
        magicIndex(blockers, BISHOP_MAGIC[square], BISHOP_SHIFT[square])];
}

// A queen is just both, which still delights me.
static long queenAttacks(int square, long occupancy) {
    return rookAttacks(square, occupancy) | bishopAttacks(square, occupancy);
}

Mask, multiply, shift, index. No loop. And >>> rather than >> matters enormously — more on that shortly.

Filling the table

static void initRookTable(int square) {
    long mask  = ROOK_MASK[square];
    int  bits  = Long.bitCount(mask);
    ROOK_SHIFT[square]   = 64 - bits;
    ROOK_ATTACKS[square] = new long[1 << bits];

    for (int i = 0; i < (1 << bits); i++) {
        long blockers = setOccupancy(i, mask);
        int  index    = magicIndex(blockers, ROOK_MAGIC[square], 64 - bits);
        ROOK_ATTACKS[square][index] = rookAttacksSlow(square, blockers);
    }
}

That loop is the whole technique in eight lines: for every blocker arrangement, compute the answer slowly, and store it where the fast lookup will later go looking.

The test to write first

@Test
void magicLookupMatchesReferenceForEverySquare() {
    for (int sq = 0; sq < 64; sq++) {
        long mask = ROOK_MASK[sq];
        int bits = Long.bitCount(mask);
        for (int i = 0; i < (1 << bits); i++) {
            long blockers = setOccupancy(i, mask);
            assertEquals(rookAttacksSlow(sq, blockers),
                         rookAttacks(sq, blockers),
                         "mismatch at square " + sq + ", occupancy " + i);
        }
    }
}

This is exhaustive over the real input domain and runs in under a second. Keeping the slow generator meant I had a trustworthy oracle; deleting it would have left me checking the fast version against nothing but vibes.

The Bugs That Nearly Broke My Brain

Every one of these cost me real hours, listed in the order they hurt.

1. The signed shift

Symptom: ArrayIndexOutOfBoundsException with a large negative index — but only for some squares and positions, which made it feel haunted.

Cause: I wrote (blockers * magic) >> shift. Java has no unsigned 64-bit type, so the multiply overflows negative about half the time and the arithmetic right shift sign-extends.

Fix and lesson: one character — >>> fills with zeroes. Most bitboard material was written with C's unsigned types in mind; porting it means every shift is a place to stop and think.

2. Bishops attacking through the edge of the board

Symptom: A bishop on h4 attacking squares on the a-file. My engine thought it was giving check from across the board and the evaluation went wild.

Cause: An early hand-rolled generator shifting by 9 and 7 without file masking. On a flat 64-bit layout, shifting left by 9 from h4 wraps onto the next rank's a-file — still "diagonal" in the bit layout, just not on a chess board.

Fix and lesson: AND with NOT_A_FILE or NOT_H_FILE before shifting. The bit layout has adjacency the board doesn't. In the final magic version this vanished, since rays come from explicit rank/file loops that can't wrap.

3. Square numbering, twice

Symptom: Everything vertically mirrored — rooks on rank 1 behaving like rooks on rank 8, perft wrong in ways that looked almost right.

Cause: I used a1 = 0, then copied a mask snippet that assumed a8 = 0. Both conventions are common; mixing them is fatal. The second occurrence was worse — I'd fixed the masks but not the debug printer, so my output looked correct while the engine was wrong. Half a day debugging correct code because my instrument was lying.

Fix and lesson: pick one convention, document it at the top of the board class, convert at the boundary of anything you copy — and validate your debugging tools independently.

4. Masks that included the edges

Symptom: Tables twice the expected size, and the exhaustive test failing on scattered occupancies with no visible pattern.

Cause: Mask loops running to 7 instead of 6. The mask had 12 relevant bits where the published magic was found for 10, so the multiply-shift no longer distributed patterns cleanly. Two blocker sets landed on one index and whichever was written second won.

Diagnosis: I added a collision detector to the table builder:

if (table[index] != 0L && table[index] != attacks) {
    throw new IllegalStateException(
        "Destructive collision at square " + square + ", index " + index);
}

Lesson: a magic is only valid for the exact mask it was found against — magic, mask and shift are one inseparable triple. That check still lives in my init path; it costs nothing and turns a subtle wrong-answer bug into an immediate named crash.

5. Break before include

Symptom: Legal move counts slightly low everywhere, and rooks never finding captures.

Cause: In rookAttacksSlow I broke before adding the blocker's square, so the capture target was never in the attack set.

Why it hid: the tables were built from that same function, so the fast lookup agreed with the slow one perfectly and my equivalence test passed. Both were wrong the same way — the exact failure a reference implementation is meant to catch and can't, when the reference is the bug.

Lesson: agreement proves consistency, not correctness. You still need assertions grounded in a board you drew by hand.

6. Sharing an array reference

Symptom: Rook attacks correct for square 63, nonsense everywhere else.

Cause: A refactor allocated one long[] outside the per-square loop, so all 64 entries pointed at the same array, each overwritten by the next.

Lesson: not every bug in advanced code is an advanced bug. When something exotic breaks, check the boring explanations first — aliasing, off-by-one, uninitialised state.

Visual Debugging Saved Me

I'll be blunt: I could not have finished this without a bitboard printer. Reading 0x000000FF00000000L and picturing a chess board is not a skill I ever developed. Thirty lines changed the project:

static void print(long bb, String label) {
    System.out.println(label);
    for (int rank = 7; rank >= 0; rank--) {
        System.out.print((rank + 1) + "  ");
        for (int file = 0; file < 8; file++) {
            int square = rank * 8 + file;
            System.out.print(((bb >>> square) & 1L) == 1 ? ". " : "- ");
        }
        System.out.println();
    }
    System.out.println("   a b c d e f g h   (bits: "
                       + Long.bitCount(bb) + ")\n");
}

Now a failing test could show me the problem instead of describing it:

rook attacks d4, blockers on d6 and b4
8  - - - - - - - -
7  - - - - - - - -
6  - - - . - - - -
5  - - - . - - - -
4  - - . - . . . .
3  - - - . - - - -
2  - - - . - - - -
1  - - - . - - - -
   a b c d e f g h   (bits: 10)

Ten seconds to spot a wrapped bishop diagonal in that format; ten minutes in hex, if you're lucky. What made the difference wasn't cleverness — it was working in the domain's own units. Every layer between the bug and my eyes was a layer I had to simulate in my head, and my head is not reliable at 1am. Three habits came out of it:

• Print three boards side by side — blockers, expected attacks, actual attacks. The difference is usually visible instantly.
• Use tiny hand-made positions. A lone rook and one pawn, not a middlegame where the bug hides in a crowd.
• Test the printer. After the mirrored-output incident, mine has its own test asserting a known bitboard renders exactly as expected.

What Actually Improved

I'm not giving you numbers. I never set up a rigorous benchmark — same hardware, same positions, controlled for JIT warm-up — and quoting figures I didn't measure would undermine everything else here. What I can describe is what I noticed.

• Search got deeper in the same wall-clock time. At a fixed few-second limit my engine consistently reached a greater depth. I can't attribute it precisely, since I changed other things in the same period.
• Move generation stopped being what I worried about. My attention moved to evaluation and move ordering, which is where it should have been.
• The code got simpler at the call site. This surprised me. rookAttacks(square, occupancy) is one expression returning a bitboard, where the ray version was a loop that also had to know about friendly pieces and move objects. The complexity moved into an init routine that runs once.
• Attack queries became reusable. Once attacks are cheap you call them everywhere — check detection, pins, square-attacked-by tests, mobility, static exchange evaluation. When it was an expensive loop I avoided it; cheap, whole features became practical.
• Timing became predictable. No data-dependent loops means node cost varies far less between a bare endgame and a crowded middlegame.

When You Probably Shouldn't Use Them

Having spent all this time on magic bitboards, my honest advice is that most people reading this shouldn't implement them yet.

• Your first chess engine. Castling, en passant, promotion, check detection, pins, legality filtering, repetition — that's where the genuine rule complexity lives, and none of it gets easier because your rook lookups are fast. Get a legal game first.
• College assignments. You'll be asked to explain your design. "I walk each ray until blocked" is a clear answer. A wall of constants you can't derive is a liability in a viva, and it looks like copied code even when it isn't.
• Still learning Java. If >>> versus >>, precedence with &, and integer overflow aren't second nature, magic bitboards will teach you them via some of the most confusing bugs available. Learn them somewhere cheaper.
• Learning move generation itself. Understanding what a rook attacks has to come before optimising how fast you compute it. Backwards, you're memorising.
• Algorithm practice. Ray traversal, bounds checking and early termination transfer to grid problems, pathfinding and graphics. Magic bitboards transfer to almost nothing outside chess.
• You haven't profiled. If move generation isn't demonstrably hot, this is effort spent on the wrong thing regardless of what any article implies.

Step 5 deserves a mention: precomputing knight attacks is the same core idea — a pure function memoised into a table — with none of the hashing. Doing it first gave me the concept in an afternoon and made step 6 feel like an extension rather than a new subject.

Reading Stockfish Suddenly Felt Different

Early on I cloned Stockfish out of curiosity and got about four files deep before admitting I was just looking at characters. Dense C++, templates, bit tricks I couldn't name.

Going back after finishing my own implementation was genuinely different. Not "I understand this codebase" — it's enormous and I don't. But I could navigate. I found the magic initialisation and recognised the shape immediately: masks, occupancy enumeration, table filling.

What struck me most was the differences. Where I used a 2D array indexed by square, they use a flat table with per-square offsets — better cache locality, and I understood why without needing it explained. There's a variant, PEXT bitboards, replacing the multiply with a hardware instruction on CPUs that support it. Each read as a design decision with tradeoffs rather than as noise.

The satisfying part wasn't feeling smart. It was realising the gap between me and a serious engine isn't a wall of incomprehensible cleverness — it's a long series of individually understandable decisions, each made by someone who'd hit the same problem and thought about it longer. That changed how I approach any intimidating codebase: build a small bad version yourself first, then come back, because the questions you bring back are what make the reading productive.

If I Were Learning Again

1. Get fluent with bitboards for their own sake. Before any chess logic — shifts, masks, bitCount, numberOfTrailingZeros, the bb & (bb - 1) idiom. Every magic bitboard bug I hit was a bitwise-fluency bug in disguise.
2. Write the bitboard printer first. Thirty lines, and it's the instrument you'll use for everything after.
3. Implement ray generation and keep it forever. It's your reference oracle, permanently. I'd never delete it now.
4. Reach perft correctness before optimising. Non-negotiable — optimising an incorrect generator produces fast wrong answers.
5. Precompute knight and king attacks. The lookup-table idea in miniature, with no hashing to confuse it.
6. Understand occupancy masks, especially edge exclusion. If you can explain why d8 is excluded from d4's mask, you understand the technique. If not, no amount of code will help.
7. Write the exhaustive equivalence test before wiring anything up.
8. Then magic lookups — with published magics initially, there's no shame in it, and a collision detector in the init path.
9. Optionally write the magic finder. Not necessary, but a fun evening that permanently removes the mystique.

Above all: don't copy code you can't explain. Not for moral reasons — because you'll hit a bug at midnight, and if you don't understand the code you have nowhere to start.

Lessons Beyond Chess Programming

• Intuition before implementation. I bounced off this for months trying to learn the code before the concept. Once I had "attacks are a pure function of square and blockers," the code took an afternoon. Now when something won't stick, I assume I'm missing a concept, not a detail.
• Optimisation without understanding is guessing. Adopting a technique because strong projects use it is cargo culting, however good the technique.
• Keep the slow version. It's your oracle, your documentation and your fallback. Deleting it to tidy the codebase is a trade I no longer make.
• Build instruments, not just features. The bitboard printer shipped nothing and probably saved more hours than any other file. Time spent on visibility compounds.
• Agreement is not correctness. Somewhere in your suite you need assertions grounded in reality, not in other code.
• Detect the impossible loudly. A cheap invariant check at construction time converted a class of silent wrong answers into an immediate named crash.
• Difficulty is often just missing context. This felt like it needed a mathematical background I lacked. It needed knowing what a blocker is. A lot of intimidating topics are like that — a small missing piece, presented as an advanced subject.

Frequently Asked Questions

What are magic bitboards in chess programming?

A way to look up sliding-piece attacks rather than recompute them. For each square you precompute every attack set a rook or bishop could have, indexed by the arrangement of blockers along its rays. At runtime you mask the board to the squares that matter, multiply by a constant acting as a collision-free hash, shift the top bits down into a small index, and read the answer from a table. The "magic" is just that the constant was found by search rather than derived.

Why multiplication instead of extracting the bits directly?

The relevant bits are scattered with large gaps, so they can't serve as an index as-is. Multiplying by a good constant sums many shifted copies of the pattern so the bits you care about end up compacted at the high end of the product; a right shift isolates them. You can extract them with a loop instead — fine as a first version — but the multiply replaces that loop with one instruction.

Why are edge squares excluded from occupancy masks?

Because a piece on the final square of a ray can't change the answer. A rook on d4 attacks d5–d8 whether or not d8 is occupied, since the ray reaches the edge either way. That square is unobservable, so including it would double the table for that ray while adding no information.

Should a beginner use magic bitboards in a first chess engine?

Usually not. They're an optimisation, not a correctness requirement, and a first engine still has castling, en passant, promotion, check detection and legality filtering ahead of it. Write ray-based generation first and you get both an understanding of the problem and a reference implementation to validate against later.

Why is Java's long a good fit for bitboards?

Sixty-four squares, sixty-four bits — one long holds one set of squares exactly. Long.bitCount and Long.numberOfTrailingZeros are intrinsics that compile to single instructions on modern CPUs. The main caveat is the lack of an unsigned 64-bit type, so magic multiplication overflows negative and you must use >>> for the index.

Do I have to find my own magic numbers?

No. Published sets have been available for years and are widely used, and writing a finder is optional. The important caveat is that a magic is only valid for the exact mask and shift it was found against, so never pair a published constant with a mask you generated by your own rules.

Are magic bitboards still the standard approach?

They remain very widely used but aren't the only option. PEXT bitboards use a hardware bit-extraction instruction to replace the multiplication where it's fast, and others exist, including kindergarten bitboards and the rotated-bitboard schemes more common historically. Which is best depends on target hardware and engine design.

Conclusion

The strangest part of finally understanding magic bitboards was how ordinary they turned out to be. For months they'd occupied a mental category labelled "things real chess programmers know that I don't," and when I got there, the contents of that category was: a rook's attacks depend only on its square and its blockers, so you can precompute them.

Everything else is engineering around that sentence. The masks shrink the input space. The magic turns a sparse pattern into a dense index. The tables exist because memory is cheaper than repeated work. Each piece answers a problem the previous piece created — but you only see that if you know what the first problem was.

Which is why the months I spent writing slow ray-based move generation weren't a detour before learning the real technique. They were learning the real technique. The magic implementation was a two-week epilogue to an education that happened in the boring loops.

So if you're staring at a page of hex constants feeling the way I felt: close the tab and build the version you can explain. Make it slow. Get it right. Print the boards. Test it until you'd bet money on it. Then come back — the same page that was impenetrable will read like a description of a problem you've already solved.

The knowledge I actually trust myself with isn't the knowledge I found fastest. It's what I built up in the wrong order, with too many bugs, over more evenings than it should have taken. Shortcuts get you working code. Understanding is what's still there six months later when the code breaks — and it's the only thing that lets you judge the next clever technique instead of merely adopting it.