A dart landed on the game that founded combinatorial game theory — the first ever given a complete mathematical theory. Nim looks trivial — take any number of tokens from one row, last to take wins — but a single idea, the nim-sum, tells you the perfect move every time. Play it below. You will lose to perfect play, and then see exactly why.
THE TECHNIQUE nim-sum = XOR of the heaps
Compute the bitwise XOR of all heap sizes — the nim-sum. If it is zero, the player to move loses under perfect play; if not, there is always a move that makes it zero, and that is the winning move. Click a token to take it and everything above it in that row. The machine replies with perfect play. live demo
nim-sum now: —
HISTORY & CREDIT the first solved game
People trace Nim to ancient China (“Tsyan-shizi”, picking stones) — the game is old, but the solution has a precise author and date. cited
1901 · Charles L. Bouton (Harvard) publishes “Nim, a game with a complete mathematical theory” — names the game, proves the nim-sum criterion, and gives the first complete mathematical theory of a game — the founding work of combinatorial game theory. 1935 / 1939 · R. P. Sprague and P. M. Grundy, independently, show every impartial game reduces to a single Nim heap (the Sprague–Grundy theorem) — Nim becomes the atom of combinatorial game theory. 1940 · the Nimatron, a relay computer, plays Nim at the New York World’s Fair — one of the first game-playing machines.
From a stone-picking pastime to the foundation of a whole branch of mathematics, on the strength of one exclusive-or. foundational
RECOMMEND FOR I-13 the wall this dart finds
The entire theory is one operator: XOR. To play perfectly, I-13 would compute the nim-sum h1 ^ h2 ^ h3. That character is not in the alphabet:
$ i13 check nim.i13
error[E0001] lex/syntax: unexpected character `^`
--> nim.i13:3:10 (I s <- a ^ b)
Recommend: add bitwise operators — ^, &, |, >> — as new BinOp discriminants, spending zero new alphabet symbols (exactly the move that added %, and the same ask that dart 001, fast inverse square root, made independently). Two darts now converge on bitwise: that is a signal, not a coincidence. Honest note: I-13 is not strictly stuck — a nim-sum can be built from arithmetic alone by peeling off bits with the (branch) % and division, then recombining. But it is ugly and slow where XOR is one instruction. The recommend is about giving the natural expression a home, not about raw possibility.