The Sprague-Grundy Theorem: Reducing Every Impartial Game to a Single XOR

The setting: impartial games and the normal-play convention

The theorem applies to a precise class. A game is impartial if the set of legal moves from any position depends only on the position, not on whose turn it is — both players can make exactly the same moves (this excludes chess, where one player moves only white pieces). We further require finite play (no infinite games, so every play terminates), perfect information, no chance, and the normal-play convention: the player who cannot move loses. Positions are modeled as a finite directed acyclic graph (DAG) — vertices are positions, edges are legal moves, and terminal (out-degree 0) positions are losses for the player to move.

• P-position — the Previous player (the one who just moved) wins; equivalently the player to move loses. Terminal positions are P-positions.
• N-position — the Next player (to move) wins; there exists at least one move to a P-position.

Classifying every vertex as N or P is a straightforward backward induction over the DAG. Sprague-Grundy does something stronger: it assigns each position a number that not only tells you N vs. P but lets you combine games.

The core idea: mex and the Grundy value

Define the Grundy value (also nimber or Grundy number) of a position x by the recurrence

g(x) = mex{ g(y) : x → y is a legal move }

where mex ("minimum excludant") of a set S ⊆ ℕ is the smallest non-negative integer not in S. So mex{} = 0, mex{0,1,2} = 3, mex{1,2} = 0, mex{0,2,3} = 1. Two facts follow immediately from the definition:

• Terminal ⇒ 0. A position with no moves has g = mex{} = 0, matching that it is a P-position (loss for the mover).
• g(x) = 0 ⟺ x is a P-position. If g(x)=0 then no option has Grundy value 0 (mex skipped 0 only because 0 was absent), so every move lands on an N-position — the mover is stuck. If g(x)>0 then some option has value 0, giving the mover a move to a P-position.

The deep insight of Sprague and Grundy is that g(x) is not just a 0/nonzero flag: the number itself is the size of the equivalent Nim heap. A position with Grundy value v behaves, for all combinatorial purposes, exactly like a single Nim pile of v stones. That is what makes composition work.

The composition theorem: sums of games are XOR of nimbers

The disjunctive sum G₁ + G₂ + … + Gₖ is the game where, on your turn, you pick one component and make a legal move there; you lose when no move exists in any component. The Sprague-Grundy theorem states:

g(G₁ + G₂ + … + Gₖ) = g(G₁) ⊕ g(G₂) ⊕ … ⊕ g(Gₖ)

where ⊕ is bitwise XOR. Combined with the win test, the whole strategy of an arbitrarily complex compound game reduces to: compute each component's Grundy value, XOR them; the mover wins iff the result is nonzero.

Why XOR? This is exactly Bouton's 1901 theorem for Nim, which Sprague-Grundy generalizes. XOR is the addition operation of the nimbers (the field-like structure on ℕ used in combinatorial game theory). The key lemma: for a single component of Grundy value v, the player who can move it can change it to any value in {0,1,…,v−1} but never keep it at v. That is precisely the move-structure of a Nim heap of size v, so replacing each component by its heap is lossless.

Finding the winning move. If the XOR X = g₁ ⊕ … ⊕ gₖ ≠ 0, let b be the index of the highest set bit of X. Pick any component i whose gᵢ has that bit set (one must, since it set the bit in X). The target value gᵢ ⊕ X < gᵢ, and because a component of Grundy value gᵢ can move to any smaller nimber, such a move exists. After it, the total XOR becomes 0 — you have handed your opponent a P-position.

Computing Grundy values: the algorithm and its complexity

Grundy values are a textbook memoized DFS / dynamic program over the DAG. Process positions so that every option is solved before the position itself (a reverse topological order, or lazy memoization).

grundy(x):
  if x in memo: return memo[x]
  seen = boolean set
  for y in moves(x):
      seen.add(grundy(y))
  m = 0
  while m in seen: m += 1     # mex
  memo[x] = m
  return m

Time. Each vertex is expanded once; computing its mex touches each of its d out-edges once and then scans upward at most d+1 integers, so a vertex costs O(deg(x)). Summed over the DAG this is Θ(V + E) time and Θ(V) space for the memo table. This is optimal — you must at least read every edge.

• mex bound. A position with d options has Grundy value ≤ d (the set {g(y)} has at most d elements, so mex ≤ d). Hence you never need integers larger than the maximum out-degree; a bool[d+1] or hash set for the "seen" marks suffices, giving O(deg) mex, not O(V).
• Closed forms. For structured games the recurrence collapses to O(1). Nim: g(heap of n) = n. Subtraction game removing 1..k: g(n) = n mod (k+1). "Turning Turtles", Kayles, Dawson's chess and dozens more have small periodic Grundy sequences you precompute or memoize in O(N) up to bound N.

Sprague-Grundy vs. minimax. Minimax on the compound game explores the product state space of size ∏|Gᵢ|, i.e. exponential in k, even with alpha-beta pruning. Sprague-Grundy solves each component's state space independently (a sum, not a product) and then does an O(k) XOR — the difference between tractable and intractable for many-component games.

Worked example: Nim plus a subtraction game

Play a disjunctive sum of two games. Game A is Nim with heaps of size 3 and 4. Game B is a subtraction game on n = 10 tokens where a move removes 1, 2, or 3 tokens (lose when you cannot move, i.e. at 0).

• Game B's Grundy values are periodic: g(n) = n mod 4 because from n you can reach n−1, n−2, n−3 with values (n−1,n−2,n−3) mod 4 — three consecutive residues — whose mex is n mod 4. So g(10) = 10 mod 4 = 2.
• Nim heaps contribute their own sizes as nimbers: g = 3 and g = 4.
• Total: 3 ⊕ 4 ⊕ 2 = 011₂ ⊕ 100₂ ⊕ 010₂ = 101₂ = 5 ≠ 0, so the player to move wins.

Finding the move: X = 5 = 101₂, highest set bit is bit 2 (value 4). The component whose nimber has bit 2 set is the Nim heap of 4. Target = 4 ⊕ 5 = 1, so reduce that heap from 4 stones to 1. New XOR: 3 ⊕ 1 ⊕ 2 = 0 — a P-position handed to the opponent. Notice you did not search a joint game tree; you did three tiny per-game computations and one XOR.

Where it is used, and where it breaks

Real usage. Sprague-Grundy is the backbone of combinatorial game theory as developed in Berlekamp, Conway, and Guy's Winning Ways for Your Mathematical Plays and Conway's On Numbers and Games. In practice it powers Nim-family analyses (Kayles, Cram, Nimber-additive games, coin-turning games), appears constantly in competitive programming (Codeforces, ICPC, Project Euler problems on "who wins"), and underlies endgame analysis of Go via Conway's surreal/nimber machinery. Any time a problem decomposes into independent sub-games under normal play, this is the first tool to reach for.

Where it does NOT apply — the failure modes:

• Partisan games. If the two players have different move sets (chess, checkers, Hackenbush with colored edges), positions are no longer single nimbers; you need the full surreal-number / game-value theory, and XOR does not decide the sum.
• Misère play. Under the misère convention (the player who cannot move wins), the clean XOR rule fails in general. Misère Nim has a special-case rule, but arbitrary misère games require misère quotients — vastly more complex, and an active research area.
• Loopy games / draws. The DAG must be acyclic and finite. If positions can repeat (loopy games), Grundy values may be undefined; you need extensions handling ∞ / draw outcomes.
• Non-disjunctive interaction. The sum must be truly independent — a move affects exactly one component. Games where a single move touches multiple components (e.g. many Wythoff-style or scoring games) are not disjunctive sums, so the theorem does not apply directly.

Pitfalls, edge cases, and implementation notes

mex bugs are the most common error. mex is over ℕ starting at 0, not 1; mex{} = 0, and a common mistake is returning 1 for the empty set or forgetting that the terminal position must be 0. Test against the invariant g(x)=0 ⟺ P-position on a tiny known game (a single Nim heap) before trusting a big table.

• Integer width for XOR. Grundy values are bounded by max out-degree; for typical games they stay small (single or double digits), so 32-bit ints are ample. But coin-turning and product games can push nimbers higher — size your "seen" array to the actual out-degree, not a guessed constant.
• Periodicity detection. Many one-dimensional games have eventually periodic Grundy sequences (Guy-Smith periodicity). Compute the sequence up to a safe bound, detect the period, then answer huge n in O(1). Do not assume periodicity without checking a long enough prefix — some games (famously Dawson's chess variants) have surprisingly long pre-periods.
• Stack depth / cycles. Recursive grundy() can blow the call stack on long chains; use an explicit stack or iterative topological order. If the graph is accidentally cyclic (a modeling bug), the naive recursion loops forever — guard with an "in-progress" marker to fail loudly.
• Don't confuse the count with the classification. N vs. P needs only a boolean, but you must retain the full numeric g of each component to XOR sums correctly. Collapsing to booleans too early loses composability — the exact thing the theorem buys you.
• Memoize by canonical position key. Symmetric positions (mirror/rotation) share Grundy values; canonicalizing the key shrinks V dramatically and turns an exponential-looking search into a small table.

Deciding a compound impartial game: Sprague-Grundy vs. brute-force minimax

Approach	Single position	k independent games	Space	Scope
Minimax (game tree)	O(bᵈ)	Product of trees, exponential	O(d)	Any game (partisan too)
Memoized win/lose DFS	O(V + E)	Must re-solve the product state space	O(V)	Impartial, one game
Sprague-Grundy values	O(V + E) once	O(k) XOR fold after per-game tables	O(V)	Impartial, normal play
Closed-form nimber	O(1)	O(k)	O(1)	Games with a known g formula (e.g. Nim)