Nim & Sprague–Grundy
The XOR rule for Nim and Grundy numbers that compose independent games. · 12 min read
Nim
In Nim, several piles of stones; a move removes any positive number from one pile; last to move wins. The remarkable theorem: the position is losing (for the player to move) iff the XOR of all pile sizes is 0. That XOR is called the nim-sum.
nim-sum = p₁ ⊕ p₂ ⊕ … ⊕ pₖ— XOR of the pile sizes.nim-sum = 0 ⟹ Losing— Any move makes it non-zero.nim-sum ≠ 0 ⟹ Winning— You can always move to make it 0.
Result: First player wins ⟺ nim-sum ≠ 0
Grundy numbers (mex)
Every impartial game position has a Grundy number (nimber): the mex — minimum excludant, the smallest non-negative integer not present — of the Grundy numbers of positions reachable in one move. A position is losing iff its Grundy number is 0, which generalises the W/L labels to a number.
g(position) = mex{ g(next) for next in moves(position) }
mex(S) = smallest non-negative integer not in SInteractive visualization: Grundy numbers via mex (0 ⟺ losing) — step through it frame by frame on this page.
Sprague–Grundy: summing games
The Sprague–Grundy theorem says any impartial game equals a single Nim pile of size g. For a game that's the sum of independent subgames (you move in exactly one each turn), the Grundy number of the whole is the XOR of the subgames' Grundy numbers. So you analyse each component, then XOR — Nim is just the special case where each pile's Grundy number is its size.
Practice: Nim — Who Wins? (Easy) — First player wins iff the XOR of pile sizes is non-zero.
Practice: Grundy Number (Sprague–Grundy) (Hard) — Compute the Grundy value of a subtraction-game position.