Move generation was done and perft said it was correct, and the engine still played like it had been dropped on its head. A legal move generator has no opinion about which legal move is any good. This post is what happened when I wrote minimax, bolted alpha-beta onto it, and counted every node instead of repeating the textbook line about searching the square root of the tree.
The headline, measured rather than quoted: from the start position a depth-6 search goes from 124,132,537 nodes to 469,620 with alpha-beta, a 264x cut. Capture ordering takes it to 225,982. But at depth 4 that same ordering saved twenty-one nodes out of fifteen hundred, while in a middlegame position it was worth 44x. The position everyone benchmarks on is the one position where move ordering has almost nothing to show you.
Table of Contents
- A Rulebook With No Opinions
- Minimax First, Negamax Because the Duplication Annoyed Me
- Counting Wood, On Purpose
- The Node Counter, and the Check That Proves It Works
- Where Full-Width Minimax Falls Over
- Alpha-Beta: "I Already Have Better, Stop Looking"
- The Measured Comparison
- The Part Most Posts Skip
- How Close Is This to the Best Case?
- What I Got Wrong First
- What These Numbers Do and Don't Transfer
- What's Next
- Frequently Asked Questions
A Rulebook With No Opinions
By the end of the perft post I had a move generator that produced exactly the right moves and a make/unmake pair that put the board back the way it found it. What I didn't have was any way to choose between the moves. The engine picked at random. It was a dice roller with a rulebook.
That gap is bigger than it sounds. Everything up to this point — the bitboard representation, the magic bitboard lookups, the fiddly en passant and castling bookkeeping — exists to make one operation fast: generate the moves in this position. Search is what finally spends that speed. I'd put it off because minimax felt like homework I'd already done at university, then wrote it in an evening.
Minimax First, Negamax Because the Duplication Annoyed Me
The textbook version. Two players, one maximising, one minimising, a depth limit, evaluate at the leaves.
int minimax(Board board, int depth, boolean maximizing) {
nodes++;
List<Move> moves = board.generateLegalMoves();
if (moves.isEmpty()) {
return board.isInCheck() ? (maximizing ? -MATE : MATE) : DRAW;
}
if (depth == 0) return evaluate(board);
int best = maximizing ? -INF : INF;
for (Move m : moves) {
board.makeMove(m);
int score = minimax(board, depth - 1, !maximizing);
board.unmakeMove(m);
best = maximizing ? Math.max(best, score) : Math.min(best, score);
}
return best;
}Two details there cost me time. The empty-move-list check has to come before the depth check, or a position that's already mate at the horizon gets scored as ordinary material and the engine walks into it. And the mate score flips with maximizing: being checkmated is catastrophic for whoever is to move, not for White specifically.
Negamax collapses the duplicated branches. One player, one sign flip per ply.
int negamax(Board board, int depth) {
nodes++;
List<Move> moves = board.generateLegalMoves();
if (moves.isEmpty()) return board.isInCheck() ? -MATE : DRAW;
if (depth == 0) return evaluate(board);
int best = -INF;
for (Move m : moves) {
board.makeMove(m);
int score = -negamax(board, depth - 1);
board.unmakeMove(m);
if (score > best) best = score;
}
return best;
}Same tree, same answers, half the code. The trick that makes it work lives in the evaluation function.
Counting Wood, On Purpose
For every measurement in this post the evaluation is pure material. Pawn 100, knight 320, bishop 330, rook 500, queen 900. No piece-square tables, no mobility, no king safety, no pawn structure.
int evaluate(Board board) {
int score = 0;
for (int sq = 0; sq < 64; sq++) {
Piece p = board.pieceAt(sq);
if (p == null) continue;
int value = PIECE_VALUES[p.type()];
score += (p.color() == WHITE) ? value : -value;
}
// negamax wants the score from the mover's point of view, not White's
return board.whiteToMove() ? score : -score;
}That last line is the whole negamax contract, and it's where I lost an evening. More on that below.
Keeping the eval this dumb is deliberate. Every node does roughly the same work, so node counts and wall-clock time stay proportional. It also keeps the pruning honest: a smarter eval produces more distinct scores, which changes how often cutoffs fire. I wanted to measure alpha-beta, not my evaluation function.
The Node Counter, and the Check That Proves It Works
A long field, incremented at the very top of the search function, before any return can escape. That's the entire instrument.
class Search {
long nodes;
int negamax(Board board, int depth) {
nodes++; // first statement, so every entry is counted exactly once
// ...
}
}Here's the part that turned out to be the most useful thing in the exercise. A full-width search to depth d visits every node down to d, so its node count is not approximately anything. It is exactly the sum of perft(0) through perft(d).
long expected = 0;
for (int i = 0; i <= depth; i++) expected += perft(board, i);
assertEquals(expected, search.nodes); // must match to the nodeFrom the start position that's 1 + 20 + 400 + 8,902 + 197,281 = 206,604 for a depth-4 search. My counter said 206,604. Not close to it, exactly it. If the counter is misplaced, the recursion skips a terminal case, or make/unmake leaks state, the identity breaks immediately — using perft numbers you already have. A free correctness test before you trust a single benchmark the harness produces.
Where Full-Width Minimax Falls Over
Two positions throughout. The start position, and a balanced Semi-Slav middlegame, r1bq1rk1/pp1nbppp/2p1pn2/3p4/2PP4/2N1PN2/PP2BPPP/R1BQ1RK1 w - - 0 9, which has 32 legal moves and dead-level material. Plain minimax, no pruning:
| Depth | Start position | Middlegame |
|---|---|---|
| 1 | 21 | 33 |
| 2 | 421 | 992 |
| 3 | 9,323 | 32,924 |
| 4 | 206,604 | 1,045,110 |
| 5 | 5,072,213 | 35,911,467 |
| 6 | 124,132,537 | — |
Growth sits around 22 per ply from the start position and closer to 32 in the middlegame, exactly the branching factors perft reported. Minimax has no mechanism for skipping anything, so tree size is search cost. At the two to three million nodes per second my engine manages with this eval, depth 6 from the start is about a minute of staring at the terminal. The middlegame depth 6 I never bothered to finish.
Alpha-Beta: "I Already Have Better, Stop Looking"
The intuition before the code, because the code is short and the idea is what matters.
You're looking at your candidate moves. The first, after a full search, is worth +50. You start on the second and partway through you find a reply that holds you to +30. Stop searching it. Not because you know what it's really worth, but because you know it's worth at most +30 and you already have +50 in your pocket. You're never playing it.
That's the whole algorithm. Alpha is what the side to move has already guaranteed itself elsewhere, beta is what the opponent has. When a node's best score reaches beta, the opponent would just avoid the line, so finishing the node is pointless.
Fail-hard clamps the return value into the [alpha, beta] window on a cutoff; fail-soft returns the actual best score even when it lands outside. Node counts are identical either way at these depths, but fail-soft preserves a tighter bound, useful later for aspiration windows and transposition entries. I went fail-soft: it costs nothing now and saves a rewrite.
int alphaBeta(Board board, int depth, int alpha, int beta) {
nodes++;
List<Move> moves = board.generateLegalMoves();
if (moves.isEmpty()) return board.isInCheck() ? -MATE : DRAW;
if (depth == 0) return evaluate(board);
int best = -INF;
for (Move m : moves) {
board.makeMove(m);
int score = -alphaBeta(board, depth - 1, -beta, -alpha);
board.unmakeMove(m);
if (score > best) best = score;
if (best > alpha) alpha = best;
if (alpha >= beta) break; // opponent won't let us reach this node
}
return best;
}Root call is alphaBeta(board, depth, -INF, INF). The window swaps and negates on the way down for the same reason the score does, which is the one line I'd stare at if the counts look wrong.
Before benchmarking anything I asserted that alpha-beta returns the identical score to minimax at every depth on both positions. It has to. Alpha-beta is not an approximation; it prunes only branches that provably cannot change the answer. If the two disagree by a centipawn you have a bug, and no amount of impressive node reduction counts until they agree.
The Measured Comparison
Alpha-beta with moves in whatever order the generator emits them:
Start position
| Depth | Minimax | Alpha-beta | Reduction |
|---|---|---|---|
| 1 | 21 | 21 | 1.0x |
| 2 | 421 | 60 | 7.0x |
| 3 | 9,323 | 581 | 16.0x |
| 4 | 206,604 | 1,516 | 136x |
| 5 | 5,072,213 | 22,463 | 226x |
| 6 | 124,132,537 | 469,620 | 264x |
Middlegame position
| Depth | Minimax | Alpha-beta | Reduction |
|---|---|---|---|
| 1 | 33 | 33 | 1.0x |
| 2 | 992 | 495 | 2.0x |
| 3 | 32,924 | 4,698 | 7.0x |
| 4 | 1,045,110 | 39,278 | 26.6x |
| 5 | 35,911,467 | 233,305 | 154x |
The reduction compounds with depth, which is the expected shape: a cutoff near the root discards a whole subtree, and subtrees grow exponentially.
The Part Most Posts Skip
Every article about alpha-beta ends with "and of course this depends on move ordering." Few show by how much, and those that do tend to use the start position, which is the worst possible place to measure it.
The standard first heuristic is MVV-LVA: most valuable victim, least valuable attacker. Captures first, biggest prize first, cheapest attacker among equal prizes.
int mvvLva(Board board, Move m) {
if (!m.isCapture()) return 0;
// en passant is the exception: the victim isn't on the destination square
int victim = m.isEnPassant() ? PAWN : board.pieceTypeAt(m.to());
int attacker = board.pieceTypeAt(m.from());
return 10 * PIECE_VALUES[victim] - PIECE_VALUES[attacker];
}
void orderMoves(Board board, List<Move> moves) {
moves.sort((a, b) -> Integer.compare(mvvLva(board, b), mvvLva(board, a)));
}Scoring has to happen before makeMove, while the victim is still on the board. Obvious in hindsight. Not obvious at 1am.
Here is what that ordering actually bought, unordered alpha-beta against ordered alpha-beta on both positions:
| Depth | Start position | Middlegame | ||||
|---|---|---|---|---|---|---|
| Unordered | Ordered | Gain | Unordered | Ordered | Gain | |
| 2 | 60 | 60 | 1.00x | 495 | 96 | 5.16x |
| 3 | 581 | 581 | 1.00x | 4,698 | 1,211 | 3.88x |
| 4 | 1,516 | 1,495 | 1.01x | 39,278 | 3,527 | 11.14x |
| 5 | 22,463 | 21,086 | 1.07x | 233,305 | 51,834 | 4.50x |
| 6 | 469,620 | 225,982 | 2.08x | 5,515,631 | 123,865 | 44.53x |
At depth 3 from the start position, capture ordering changed nothing at all. Not "barely anything" — the two searches visited the same 581 nodes. At depth 4 it saved 21 nodes out of 1,516.
The reason is simple once you look at the tree instead of the algorithm. The earliest capture from the start position is on the third ply (1.e4 d5 2.exd5). In a depth-3 search every node that gets sorted sits at ply 1 or 2, where there is not a single capture on the board. The comparator runs, scores every move zero, and hands the list back untouched.
The middlegame position tells a different story, and it's the one that matters, because engines spend approximately none of their life on move one. Capture ordering cut the middlegame search by 11.1x at depth 4 and 44.5x at depth 6. Stacked on alpha-beta itself, depth 5 went from 35,911,467 nodes to 51,834 — a 693x reduction, where unordered alpha-beta on the identical position managed 154x. Same code, same comparator, same two dozen lines. The only thing I changed was the FEN.
The gain doesn't climb smoothly either: 5.2x, 3.9x, 11.1x, 4.5x, 44.5x for depths 2 through 6. Even depths beat odd ones in every run. My guess is it's about which side gets the last word before the horizon, but two positions isn't enough to state that as fact.
Had I only benchmarked the start position I'd have written MVV-LVA off as a rounding error. That's the trap. Pruning heuristics are only ever measured against the positions you feed them, and the start position is pathological: no captures, no imbalance, and a flat-zero eval that triggers cutoffs almost immediately regardless of sort order. That flat-eval effect is doing much of the 136x at depth 4, and almost none of it is skill.
How Close Is This to the Best Case?
The number everyone quotes is bd/2, the square root of the tree. The sharper version is the Knuth-Moore result for a perfectly ordered tree: b⌈d/2⌉ + b⌊d/2⌋ − 1 nodes.
The start position has an effective branching factor of about 22 across six plies. That puts the minimal depth-6 tree at roughly 21,300 nodes. My ordered search visited 225,982. So I'm about 10x above optimal, which sounds bad until you remember minimax visited 124 million.
Depth 5 tells a better story. With b around 22 the minimal depth-5 tree is about 11,100 nodes against my measured 21,086, so 1.9x above optimal; the middlegame is closer still at roughly 33,800 against 51,834, or 1.5x. Then depth 6 jumps back out to 10x. I don't have a clean explanation for that step and would rather say so than invent one. The obvious suspect is the same even-depth effect from the ordering table.
Four causes I can name. Material-only eval produces vast numbers of exactly-equal scores, and equal isn't better, so bounds tighten slowly. MVV-LVA sorts only captures, and most nodes at depth 6 are quiet moves in generator order. There's no transposition table, so positions reachable by more than one move order get searched again from scratch. And there's no quiescence search, so leaf scores are noise whenever a capture hangs at the horizon.
What I Got Wrong First
The counter was in the wrong place. I put nodes++ after the depth check, so leaves never got counted and depth 4 reported 9,323 instead of 206,604. The perft identity made it obvious: 9,323 isn't a wrong-ish number, it's exactly the depth-3 total, which points straight at the missing bottom ply.
The evaluation sign. I wrote evaluate() to return material from White's perspective and dropped it into negamax without the flip on the last line. White's moves were fine. Black played like it was trying to lose, because from Black's nodes the search was maximising White's material. Nothing crashed and the scores looked plausible, which is why it took so long to spot.
My first test position was rigged. The middlegame FEN I first used was missing Black's light-squared bishop — I'd typed it by hand and dropped a piece. White was up 330 centipawns before the search even started, so one side had a trivially winning line at every depth and every pruning number was inflated. I caught it only after adding a material-balance assertion to the harness on a hunch.
Ordering quiet moves made things worse. I extended the comparator to sort quiet moves by a crude piece-square score and node counts went up at depths 3 and 4. My guess is the ordering was actively wrong given a material-only eval, so it reliably searched the least useful move first, but I'm not confident that's the explanation. Took it out; I'll revisit it when there's a real evaluation to sort against.
What These Numbers Do and Don't Transfer
The minimax and ordered alpha-beta counts should reproduce almost exactly in any engine with the same piece values and MVV-LVA rule, because they're fixed by the algorithm and the position, not the implementation. The unordered column won't transfer: it means whatever sequence your generator happens to emit, and mine emits knights before pawns and quiets before captures. If your unordered numbers beat mine, your generator is accidentally ordering for you.
Wall-clock times are mine alone: single-threaded, one laptop, one JVM, and JIT warmup matters more than you'd expect at the shallow end.
If you're partway through your own engine: alpha-beta plus captures-first is the largest single win available, and it's about forty lines. Get it measured and working before you go near multithreading or a faster language.
What's Next
Iterative deepening next, mostly so the best move from depth N gets searched first at depth N+1 — a far better ordering signal than MVV-LVA alone. Then a transposition table, then quiescence search so the leaf evaluation stops being blind to a hanging queen. Each measured the same way against the same two positions, so the numbers stack up across the series.
If you've run this in your own engine and got a meaningfully different curve, I'd like to see it. And if my MVV-LVA is missing something obvious, or you have a real explanation for the quiet-move ordering result, tell me in the comments. I'm still working out which of these heuristics pay for themselves and which are folklore.
Author's note: Every node count here came out of my own instrumented search on the two positions given, not from a paper or another blog. I've kept the runs that embarrassed me — the rigged test position, the ordering experiment that backfired — because the tidy version of this comparison, where alpha-beta neatly hits the square root and every heuristic helps, is not what my terminal printed.
Frequently Asked Questions
How much does alpha-beta pruning actually reduce node counts?
Measured in my engine with a material-only evaluation: from the start position, 16x at depth 3, 136x at depth 4 and 264x at depth 6, against a full-width minimax that visits 124,132,537 nodes at depth 6. From a balanced middlegame position the reduction was 154x with unordered alpha-beta and 693x with capture ordering at depth 5, against a full-width minimax that visits 35,911,467 nodes. The reduction compounds with depth because a cutoff near the root discards an entire subtree.
Why did capture ordering save almost nothing from the start position?
Because there are no captures in the opening. The earliest capture from the start position takes three plies to arrange, so a captures-first comparator is sorting a list in which every move scores zero. At depth 3 the ordered and unordered searches visited an identical 581 nodes; at depth 4 ordering saved 21 nodes out of 1,516. It only starts paying at depth 6, and it pays properly in a middlegame position. Benchmarking move ordering on the start position will tell you the heuristic is worthless.
What is the difference between fail-soft and fail-hard alpha-beta?
Fail-hard clamps the returned value into the [alpha, beta] window when a cutoff happens. Fail-soft returns the actual best score it found, even when that value lies outside the window. Node counts are the same at these depths, so the choice is about what you do later: fail-soft hands back a tighter bound, which is more useful for aspiration windows and for storing accurate transposition table entries.
What is MVV-LVA move ordering?
Most Valuable Victim, Least Valuable Attacker. Sort captures by the value of the captured piece descending, breaking ties by the value of the capturing piece ascending, so a pawn taking a queen is searched before a queen taking a queen. One implementation trap: the move has to be scored before it is played, and for an en passant capture the victim is not standing on the destination square, so a naive lookup finds an empty square and scores the capture as a quiet move.
Do minimax and alpha-beta return different moves?
No. Alpha-beta visits fewer nodes to reach exactly the same score and the same best move, because it only discards branches that provably cannot change the result. Asserting that the two searches agree at every depth is the first test to write, and it should pass before you take any node count seriously.
How do I know my node counter is correct?
A full-width search to depth d visits exactly perft(0) + perft(1) + ... + perft(d) nodes. From the start position a depth-4 minimax must report 206,604, not a number near it. If your total disagrees, the counter is in the wrong place, the recursion is skipping a terminal case, or make/unmake is corrupting state, and you can find out in seconds using perft numbers you already have.