Perft Testing: How I Found 4 Move-Generation Bugs in One Afternoon

43,247.

The reference said 43,238. Nine nodes apart, on a position with five pieces on it, and I sat there refreshing the terminal like the number was going to change if I ran it again.

That was the first of four. By the time I stopped it was dark outside and I had a git log full of commits with messages like "en passant, again" and "no, THIS is why b1 was wrong."

Table of Contents

• The engine looked fine, which was the problem
• What perft is, minus the jargon
• One wrong number and you stop arguing
• Perft divide, or binary search over a game tree
• Four bugs, one afternoon
• 119,060,324
• What I'd do differently
• Frequently asked questions

The Engine Looked Fine, Which Was The Problem

By the end of the magic bitboards post I had something that felt finished. Rooks slid, bishops slid, queens did both, and the lookup tables agreed with my slow ray generator on all 64 squares for every blocker arrangement. I set the thing playing random legal moves against itself and watched a few hundred games scroll past.

They looked like chess. Pieces developed, pawns traded, kings sat behind their pawns doing nothing useful. Nothing crashed.

And that is the trap. A move generator with a real bug in it still produces games that look like chess, because the bug fires in maybe one position in ten thousand, and when it fires the result is a slightly wrong move in a game nobody is watching closely. I had no test that could distinguish "correct" from "wrong in a way I can't see." My unit tests all passed, which meant nothing, because I had written every one of them from my own mental model of the rules. If my mental model was the thing that was broken, the tests were broken in exactly the same shape.

What Perft Is, Minus The Jargon

Pick a position. Count every legal move. For each one, play it and count every legal reply. For each of those, play it and count the replies. Keep going until you've gone N plies deep, and count how many positions you ended up at. That total is perft(N).

From the starting position: 20 at depth 1, because White has twenty legal first moves. 400 at depth 2. Then 8,902, then 197,281, then 4,865,609.

The idea is not clever. The recursion fits on a napkin:

long perft(Board board, int depth) {
    if (depth == 0) return 1L;

    long nodes = 0L;
    for (Move m : moveGen.generateLegal(board)) {
        board.make(m);
        nodes += perft(board, depth - 1);
        board.unmake(m);
    }
    return nodes;
}

What makes it powerful is nothing to do with the code. It's that other people already computed those numbers, independently, with engines that have been checked against each other for decades. The counts for the starting position and for a set of standard test positions are shared factual data at this point. So when I run this function, I'm not testing my engine against my own understanding of chess. I'm diffing it against reality.

That distinction is the whole reason perft works and my unit tests didn't.

One Wrong Number And You Stop Arguing

The thing I wasn't ready for is how unforgiving it is. There is no partial credit. If depth 3 from the start position gives 8,903 instead of 8,902, there is a bug. Not a rounding issue, not a definitional disagreement, not "well it depends how you count." A bug. In your code. Right now.

I stared at a one-node difference for twenty minutes trying to think of a way it could be fine. There isn't one. Once you accept that, debugging gets much faster, because you stop spending energy on the possibility that you're actually correct.

It also cuts the other way, and this is the part I've come to appreciate more. When the number matches, it matches. Millions of leaf nodes, every one reached through your make and unmake, every castling right and en passant square and promotion handled the way the rules say. That's a level of confidence I have never gotten from a test suite I wrote myself.

Perft Divide, Or Binary Search Over A Game Tree

"You have 4,085,603 nodes and one of them is wrong" is not actionable. Perft divide is what makes it actionable.

Instead of one total, you print a subtotal per root move:

void divide(Board board, int depth) {
    long total = 0L;
    for (Move m : moveGen.generateLegal(board)) {
        board.make(m);
        long n = perft(board, depth - 1);
        board.unmake(m);
        System.out.println(m.uci() + ": " + n);   // e.g. "g1f3: 2812"
        total += n;
    }
    System.out.println("nodes: " + total);
}

Now compare your list against a reference engine's divide for the same position and depth. One line disagrees. Play that move on the board, run divide again at depth minus one, and one line of that disagrees. Repeat.

Every step throws away almost the entire tree. Four or five iterations and you are staring at a position where the depth-1 count is wrong, which means you can just print your generated move list and read it. The bug is right there, in a list of thirty moves, with either an extra one or a missing one.

I did this four times that afternoon and it worked identically every time. It is the single most effective debugging technique I have used on any project, and it took me about ten minutes to implement.

Four Bugs, One Afternoon

Bug #1: en passant took two pawns off the same rank

The 43,247. The position is one from the standard perft suite, usually listed as "position 3", chosen precisely because it hammers pawn and rook endgame edge cases:

8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1

depth 4    expected 43,238    mine 43,247

I was convinced the problem was the rooks. Two rooks, a lot of sliding, and I'd just rewritten sliding attacks; the magic lookup was obviously the suspect. Four divides later I was in a position where Black had just pushed a pawn two squares and White's reply list had one move in it that made me tilt my head.

Here's the bug boiled down to its smallest form:

8/8/8/8/k1p4R/8/3P4/3K4 w - - 0 1

White plays d2-d4.  Black now has 6 legal moves.  Mine generated 7.

Black king on a4, black pawn on c4, white rook on h4, all on the same rank. White pushes d2-d4 and Black can answer c4xd3 en passant. Except Black can't, because that capture takes the c4 pawn off rank 4 and removes the d4 pawn from rank 4 at the same time, and now the rook on h4 has a clear run to the king on a4. It's a discovered check on yourself. Illegal.

My legality filter never had a chance:

// BEFORE — the pin test only looks at the moving piece's own square.
boolean isLegal(Move m) {
    if (m.piece() == KING) {
        return !isAttacked(m.to(), them);
    }
    return !isPinnedAlong(m.from(), kingSquare[us], m.to());
}

Neither pawn is pinned. The c4 pawn isn't on the king's rank-line to the rook alone, and the d4 pawn belongs to the other side entirely. Every check I had was asking about one square, and en passant is the only move in chess that vacates two squares on one line simultaneously.

I fixed it the blunt way and have never regretted it:

// AFTER — make it, ask the only question that matters, unmake it.
boolean isLegal(Move m) {
    board.make(m);
    int ksq = Long.numberOfTrailingZeros(kings[us]);   // same occupancy longs from the bitboards post
    boolean ok = !isAttacked(ksq, them);
    board.unmake(m);
    return ok;
}

Yes, it's slower than a pin mask. It is also incapable of missing this class of bug, because it asks the actual question: after this move, is my king attacked. Faster engines special-case en passant inside the pin logic by testing the post-capture occupancy along the king's rank. I'll do that when profiling tells me to, and not before.

Lesson: en passant is the rule everyone forgets exists until it costs them an afternoon. If your legality check reasons about squares rather than about the resulting position, it will be wrong here.

Bug #2: castling rights that outlived the rook

Next up, the Kiwipete position from the standard suite, which exists more or less to punish castling code:

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1

depth 3    expected 97,862    mine 97,905

High, not low, which meant I was generating moves that don't exist. My first theory was the two-square king jump landing on an occupied square. Wrong. The divide walk put me in a position where a rook had been captured on h8, and Black cheerfully castled kingside anyway, conjuring a rook out of nothing.

My rights update only ever considered the piece that moved:

// BEFORE — handles the rook moving, not the rook dying.
if (m.piece() == KING) rights &= ~bothRightsFor(us);
if (m.piece() == ROOK) rights &= ~rightForSquare(m.from());

A rook that gets captured on its home square never moves. It just stops existing, and nothing in that code notices. The fix is a lookup table over squares, applied to both ends of the move:

// AFTER — CASTLE_MASK is 0b1111 everywhere except a1,e1,h1,a8,e8,h8.
rights &= CASTLE_MASK[m.from()];
rights &= CASTLE_MASK[m.to()];   // this is the line that cost me an hour

Two lines replacing the whole branchy mess, and they cover king moves, rook moves and rook captures at once.

Then I overcorrected. Feeling clever, I tightened the castling path checks and Kiwipete depth 4 came back at 4,085,571 against an expected 4,085,603. Low this time. I had started requiring b1 to be a safe square, and it doesn't have to be. The king travels e1 to c1, so e1, d1 and c1 must all be unattacked, but b1 only has to be empty for the rook to slide across it. The king never sets foot there.

// Two different questions about two different square sets.
static final long WQ_MUST_BE_EMPTY = bit(B1) | bit(C1) | bit(D1);
static final int[] WQ_MUST_BE_SAFE = { E1, D1, C1 };   // note: no B1

boolean canCastleQueenside(long occ) {
    if ((rights & WHITE_QUEENSIDE) == 0)   return false;
    if ((occ & WQ_MUST_BE_EMPTY) != 0)     return false;
    for (int sq : WQ_MUST_BE_SAFE) {
        if (isAttacked(sq, them)) return false;
    }
    return true;
}

Lesson: occupancy and safety are separate constraints over separate square sets, and castling rights are state that other pieces can destroy without the rook ever taking a step.

Bug #3: I only ever promoted to queens

This one I found in about ninety seconds, and it's the one I'm least proud of. Position 5 from the suite:

rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8

depth 1    expected 44    mine 41

Depth 1. Not a subtle interaction four plies deep, just White's legal moves in a single position, off by exactly three. That exactness is the tell. Three is what you're short when one promotion move generated a queen and nothing else.

White has a pawn on d7 and the only promotion available is the capture on c8, so my generator produced one move where there should have been four.

// BEFORE — with a comment I actually wrote, which makes it worse.
if (rankOf(to) == promoRank) {
    moves.add(new Move(from, to, PROMO_QUEEN));   // nobody underpromotes
}

Nobody underpromotes, except perft counts legal moves rather than sensible ones, so every promotion square is worth four nodes and my tree was permanently thin. And underpromotion isn't purely theoretical anyway; knight promotion with check is a real tactic that a search which can't generate it will never find.

// AFTER
private static final int[] PROMOTIONS =
    { PROMO_QUEEN, PROMO_ROOK, PROMO_BISHOP, PROMO_KNIGHT };

if (rankOf(to) == promoRank) {
    for (int piece : PROMOTIONS) moves.add(new Move(from, to, piece));
} else {
    moves.add(new Move(from, to, QUIET));
}

And the part that bit me a second time twenty minutes later: pawn pushes and pawn captures went through two different code paths in my generator. I fixed promotions in the push path, watched the number improve, assumed I was done, and left the capture path generating a lone queen. Position 5 caught it again immediately, because every promotion in that position is a capture.

Lesson: if a rule has two code paths, it has two bugs. Go and look at the other one before you commit.

Bug #4: the pawn on h3 that captured on a3

The last one is my favourite, because it explains why the starting position had been lying to me all along. Back to Kiwipete, now at depth 3, still slightly high after the castling fix.

The divide walk ended somewhere odd: White plays a2-a3, and Black's move list contains h3a3. A pawn on h3, capturing on a3. Across the entire board, sideways.

I was sure this was a square-indexing problem, because I'd had one of those before and it left the same kind of fingerprint. It wasn't. It was the pawn capture generator I'd written months earlier, on the day I first learned that a bitboard shift can do eight things at once:

// BEFORE — looks elegant, wraps around the board.
long capsLeft  = (whitePawns << 7) & blackPieces;
long capsRight = (whitePawns << 9) & blackPieces;

Shifting left by 7 means "up one rank, left one file", which is true for every square except the a-file, where left one file falls off the world and reappears on the h-file of the rank below. The bits don't know the board has edges. They're a flat run of 64.

// AFTER — mask off the file that can't go that way.
static final long FILE_A = 0x0101010101010101L;
static final long FILE_H = 0x8080808080808080L;

long capsLeft  = ((whitePawns & ~FILE_A) << 7) & blackPieces;
long capsRight = ((whitePawns & ~FILE_H) << 9) & blackPieces;

Here's why it survived so long. A wrapped capture only becomes a move if there's an enemy piece sitting on the wrapped destination, because of that & blackPieces at the end. In the starting position every wrapped target is an empty square on rank 3, so the AND quietly deletes all of them and perft comes out perfect. The bug is invisible until pieces cluster near the a- and h-files, which is exactly what the suite positions are built to arrange and exactly what a fresh board never does.

Lesson: the starting position is the worst test position in chess. Everything is symmetric, nothing is near an edge in a way that matters, and half your bugs are masked by empty squares.

119,060,324

Late evening, four fixes in, I kicked off depth 6 from the starting position and went to make coffee. Came back to:

startpos depth 6
nodes: 119060324
time:  41.7s

That is the published number. Exactly. A hundred and nineteen million positions, every one of them reached through my make, my unmake, my castling rights, my en passant square, my promotions, and not one node out of place.

I'd be lying if I said that wasn't the best moment of the whole project so far. Not because it was hard to get there once I had divide, but because for the first time I knew something about my own code instead of believing it. Six months of "I think this works" collapsed into one number that either matched or didn't.

Then the honest part. Perft proves legality and nothing else. It doesn't care that my node rate is embarrassing next to any serious engine, it doesn't know whether my evaluation can tell a good bishop from a bad one, and it certainly doesn't know whether the thing plays decent chess. It proved the foundation is solid. It proved nothing whatsoever about the building.

What I'd Do Differently

Build perft first. Before magic bitboards, before the fancy sliding-piece lookups, before any of the parts that were fun to write. It needs a board, a move generator and make/unmake, and it is the first thing that can tell you whether those three are correct. I built it fifth, and every optimisation I wrote before it was an optimisation of code I couldn't verify.

Use a real suite from the start, not just the starting position. Kiwipete, position 3, position 5, and a handful of others are standard test positions that circulate in the chess programming community precisely because each one targets rules the start position can't reach. Six positions caught every bug in this post. The start position caught none of them.

And automate it. Mine now runs as a parameterised JUnit test over a CSV of FEN, depth and expected count, shallow depths on every push and the deep ones nightly. That took twenty minutes to set up and it means a refactor can no longer quietly break move generation while all my hand-written tests keep passing. Which, if I'm honest about it, is exactly what had been happening for months.

Frequently Asked Questions

What is perft in chess programming?

A function that counts leaf nodes at a fixed depth from a position. From the starting position it gives 20, 400, 8,902 and 197,281 for depths 1 to 4. Its value is that those counts have been independently computed and published, so you're comparing your engine against a known-correct answer rather than against your own understanding of the rules.

How do I find the bug once perft disagrees?

Perft divide. Print a node count per root move, compare against a reference engine's divide for the same position and depth, play the move whose subtree disagrees, and run divide again one depth shallower. Four or five iterations gets you to a position where the depth-1 count is wrong, and at that point you can read the illegal or missing move straight out of your generated list.

Why bother generating underpromotions?

Perft counts legal moves, not good ones, so each promotion square contributes four nodes instead of one. Omit them and you'll be exactly three nodes short per promotion move, compounding at every deeper ply. Knight promotion with check also shows up in real tactics, so a search that can't generate it will miss them.

Should legality checking use make/unmake or pin masks?

Pin masks are faster and are what strong engines use. Make/unmake with a single "is my king attacked" test is slower and structurally incapable of missing en passant discovered checks, pinned-piece edge cases and the rest. Start with the version that can't be subtly wrong, get perft passing, then optimise with the correct version still available as a reference.

My perft matches. Is my engine finished?

Your move generator is correct, which is a real milestone and not the same thing. Perft says nothing about search speed, evaluation quality or playing strength. It's the floor everything else stands on.

Next time: turning that tree walk into an actual search. Minimax, alpha-beta, and why my first attempt at pruning made the engine slower than just counting the nodes.