The chess engine that stops looking once it knows enough

A chess engine that thinks four moves ahead is, on paper, staring down millions of positions. Mine looks at a small fraction of them and plays the exact move it would have picked if it had checked every last one. That is not a shortcut that trades away quality. It is a proof that the skipped positions could not have changed the answer.

That trick, alpha-beta pruning, is most of what separates a chess program that plays from a chess program that spins. Zugzwang is my from-scratch version of the whole stack: a terminal engine in Rust with legal move generation, search, and evaluation, no external chess crates doing the hard parts. It speaks UCI, the protocol every serious chess GUI already understands, so it plugs into Arena or CuteChess and plays a full game. And it stays around 4,000 lines, small enough to read end to end, which is the actual point: a reference for how these pieces fit, not a black box.

Why it can throw away most of the tree

Minimax, the base algorithm, assumes both sides play perfectly and scores a move by looking at your opponent's best reply, then your best reply to that, and so on down. The tree explodes fast: roughly 35 legal moves per position, raised to the depth.

Alpha-beta is the observation that you do not need to finish looking. Suppose you have already fully evaluated one move and know it guarantees you, say, a slight edge. Now you start checking a second move, and among the opponent's replies you find one that hands you a losing position. Stop. You do not care whether the opponent has other good replies to that move, because one refutation is enough to reject it. You will never choose it. Every branch under those unexamined replies gets pruned, unsearched, with no effect on the move you finally play.

The catch is that this only pays off if you stumble onto the refutations early. Search the moves in a dumb order and you prune almost nothing. So the engine orders moves before searching them, best guesses first: captures ranked by MVV-LVA (grab the most valuable victim with your least valuable attacker), then killer moves and a history heuristic for the quiet moves that caused cutoffs elsewhere. Good ordering pushes the search from roughly b^d work toward b^(d/2), which in practice means seeing about twice as deep in the same time budget. (Zugzwang folds the minimax sign-flip into the recursion, a variant called negamax, so one symmetric function handles both sides instead of two mirror-image ones.)

The bug that lurks at the bottom of the search

Here is a gotcha the algorithm hands you for free. If search simply stops at depth four and counts material, it can stop in the middle of a trade: one ply after your queen captures a pawn, one ply before the pawn's defender captures your queen. The engine reports a won pawn that is actually a lost queen. This is the horizon effect, and it will make an otherwise-correct engine play like it is drunk.

The fix is quiescence search: at the leaves, instead of scoring immediately, keep searching captures until the position goes quiet, so the engine only ever judges settled boards. The name of the whole project is a related admission of how thin the ice is. Zugzwang is German for the compulsion to move, a position where every legal move makes yours worse, which is a fair description of a program whose entire job is finding the least-bad move, every single ply.

Two honest limits: the board is still a plain 64-element array rather than bitboards, so it is readable but not fast, and raw playing strength was never the v1 bar. Correctness and speaking UCI cleanly enough to finish a real game were.

Try it

cargo build --release, then ./target/release/zugzwang play and type moves in coordinate form (e2e4, or e7e8q to promote). Want to watch it talk? Run zugzwang uci and type uci to see it introduce itself, then position startpos moves e2e4 e7e5 and go depth 6, and it answers with the one move it decided was least bad.