The Sprague-Grundy Theorem: Reducing Every Combinatorial Game to a Single Number

Pick up two unrelated games — a pile of coins in Nim, and a row of bowling pins in Kayles — and something strange is true: at every moment, no matter how different they look, each position secretly is a number. Not "can be scored" or "can be ranked" — it literally behaves, in every mathematical sense that matters, exactly like a pile of a certain size in the game of Nim. That collapsing of an entire universe of games into pure arithmetic is the Sprague-Grundy theorem, one of the cleanest and most underrated results in 20th-century mathematics.

The Concept

Start with Nim, the ancestor of this whole story. Two players face several piles of stones. On your turn you remove any number of stones from a single pile. Whoever takes the last stone wins. It looks like a children's game, but in 1901 the Harvard mathematician Charles L. Bouton proved something exact about it: write the size of each pile in binary, and XOR (bitwise exclusive-or) all those numbers together. If the result is zero, the player about to move is already losing against perfect play. If it's nonzero, they have a winning move. Bouton's 1902 paper is now considered the founding document of combinatorial game theory — the study of games with no hidden information and no luck, just two players alternating moves until someone can't move anymore.

For three decades, Nim's XOR trick looked like a special party trick for one specific game. Then two mathematicians, working continents apart and decades apart from each other, discovered it was universal.

Roland Sprague, a German mathematician (1894-1967), proved it in 1936. Patrick Michael Grundy, an English mathematician and statistician (1917-1959), proved it independently in 1939 — as a Cambridge undergraduate, in his very first published paper, "Mathematics and Games," which appeared in the student magazine Eureka. Neither knew about the other's work at the time; the result now carries both their names.

The theorem says: every impartial game, played under "normal play" rules, is equivalent to some single pile of Nim. "Impartial" means both players have exactly the same moves available from any position (unlike chess, where only one side can move the white pieces). "Normal play" means the last player to move wins. Under those conditions — which cover an enormous zoo of games, from Kayles to dozens of pencil-and-paper classics — the entire tangled tree of possible moves in a game collapses down to one number, called the Grundy number (or nimber) of that position.

Here's how you compute it, using a function with the delightfully blunt name mex — "minimum excludant." The mex of a set of numbers is simply the smallest non-negative integer not in that set. Mex{1, 4} = 0. Mex{0, 1, 2, 5} = 3. Now define the Grundy number of a game position recursively: look at every position you could move to, find the Grundy number of each of those, and take the mex of that whole set. A position with no legal moves (the player to move has already lost) gets Grundy number 0. Every other position's Grundy number is the mex of where it can go.

Do this all the way down a game tree, and every position ends up labeled with a single number. A position is a loss for the player about to move if and only if its Grundy number is 0 — exactly mirroring the "you're already beaten" condition in ordinary Nim.

Why It Matters

The real payoff isn't analyzing one game — it's analyzing combinations of games, which is where real strategy problems live. Most interesting combinatorial games aren't one clean game; they're several games glued together, where on your turn you pick exactly one component to move in (think of several simultaneous Nim-like puzzles on the table, and you must act in just one of them). This is called a "disjunctive sum," and it's a nightmare to analyze directly — the combined game tree's size multiplies across every component.

Sprague-Grundy theory turns that combinatorial explosion into grade-school arithmetic. The Grundy number of the whole combined game is just the Nim-sum (bitwise XOR) of the Grundy numbers of each separate piece. You never have to look at the giant combined tree at all. Solve each small game once, get a number, XOR the numbers together, and you know — instantly — who wins the monster combination and, if it's you, which component to move in.

That single idea is the engine behind decades of recreational-math problem solving (Martin Gardner built whole columns around it) and behind the landmark 1982 book Winning Ways for Your Mathematical Plays by Elwyn Berlekamp, John Conway, and Richard Guy, which systematized combinatorial game theory as a field. Conway pushed the underlying arithmetic even further in his 1976 book On Numbers and Games, where the "nimbers" of Sprague-Grundy theory turn out to be a special case of his surreal numbers — an entire number system built out of game positions, extending the real numbers to include infinite and infinitesimal quantities. A game invented to analyze bowling-pin puzzles ended up contributing to one of the strangest number systems in modern mathematics.

It also turns out to be genuinely useful outside pure recreation. Many impartial games used as toy models in theoretical computer science — vertex geography on graphs, node-Kayles played on networks, various "coin-turning games" — are analyzed, and sometimes solved in polynomial time, precisely by computing their Grundy functions rather than searching their exponential game trees. Competitive programmers encounter Grundy numbers constantly, since a huge class of contest problems ("who wins this game?") reduces directly to computing mex values over small game graphs — a Sprague-Grundy computation is often the entire intended solution.

The Details

Let's walk Kayles, invented by puzzle-maker Henry Dudeney in 1908, through the machinery. Imagine a row of bowling pins. On your turn, knock down either one pin, or two adjacent standing pins. Whoever knocks down the last pin wins. A row of zero pins has no moves — Grundy number 0. A single pin: your only move is to remove it, leaving the empty row (Grundy number 0), so mex{0} = 1. Two pins: you can remove one pin (leaving 1 pin, Grundy number 1) or remove both (leaving 0 pins, Grundy number 0); the reachable set is {1, 0}, so mex{0,1} = 2. Keep going, and every row-length gets its own Grundy number — a sequence that was fully worked out using exactly this method and is, famously, eventually periodic with a period of 12, after some early irregular terms.

Now suppose the actual game on the table isn't one row of pins but three separate rows, and on your turn you must play a Kayles move in exactly one of the rows. Look up each row's Grundy number from the sequence, XOR the three numbers together. Nonzero means the player to move wins; they win by making a move in whichever single row changes the total XOR to zero, which Sprague-Grundy guarantees is always possible from a winning position and never possible from a losing one. No need to ever draw the full three-row game tree, which would have thousands of nodes.

It's worth sitting with how strange this is as a mathematical fact, not just a computational shortcut. Two games can look utterly different — different boards, different pieces, different rules for what counts as a legal move — and still be the same game in the only sense that matters for who wins: the same number. Sprague-Grundy theory is a statement about the deep structure underlying "taking turns until someone can't move," stripped of every surface detail. It's the kind of result that makes you suspect strategy itself has an algebra, and in Nim-addition, it does.

One honest limitation: the theorem is specifically about impartial games, where both players have identical move sets. The moment a game becomes "partizan" — different pieces or moves available to each side, as in chess or Go — the clean reduction to a single number breaks down, and you need the richer (and much harder) machinery of partizan game values that Conway developed afterward. Sprague-Grundy theory is the complete, elegant answer to a more restricted question — which is exactly why it's so sharp.

Takeaways

Every impartial, normal-play game is secretly equivalent to a single Nim pile — an entire universe of different-looking games collapses into one number, the Grundy number.
The Grundy number of a position is computed with mex, the "smallest missing non-negative integer" among the Grundy numbers of all positions you can move to.
Combining separate games into one sum is as easy as XOR-ing their Grundy numbers together — turning an exponential game-tree problem into simple arithmetic.
Discovered independently by Roland Sprague (1936) and Patrick Michael Grundy (1939, as a Cambridge undergraduate), building on Charles Bouton's 1901-1902 complete solution of Nim.
The theory's arithmetic of game values was later absorbed into John Conway's surreal numbers — a direct line from a bowling-pin puzzle to one of the most exotic number systems mathematicians have built.

Resources: - Sprague-Grundy theorem — Wikipedia - Charles L. Bouton — Wikipedia - AMS Feature Column: "Towards a theory for combinatorial games"