Sprague-Grundy Theorem
Pillar: Set — "The Grundy number = mex (minimum excludant) = the smallest non-negative integer NOT in the set of reachable Grundy values." Pillar: Chain — "Grundy values form a dependency chain: \(G(n)\) depends on \(G(\text{reachable states from } n)\)."
The Setup
You know from Ch8 L1 that Nim has a clean solution: XOR the pile sizes, and if the result is nonzero, the first player wins. But what about games that aren't Nim?
Consider this: two players take turns removing stones from a pile. The allowed moves are \(\{1, 2, 3\}\) — you can remove one, two, or three stones per turn. Whoever takes the last stone wins. Who wins with \(7\) stones?
This isn't standard Nim (where you can remove any number up to the pile size). You can't just XOR things. But there's a theorem that says every game like this — every impartial game — is secretly equivalent to a Nim pile of some size. The Sprague-Grundy theorem tells you exactly which size.
Once you see this, game theory problems stop being ad-hoc. You compute one number per game state, XOR them across independent sub-games, and read off the winner. The same framework handles subtraction games, staircase games, graph games, and dozens of competitive programming variations.
Impartial Games
An impartial game is a two-player game where:
- Both players have exactly the same set of moves from any position.
- The game ends when no moves are available — the player who can't move loses (normal play convention).
- The game always terminates (no infinite loops).
Nim is impartial. Chess is not (White and Black have different pieces). The subtraction game above is impartial. Any game where the rules depend on whose turn it is fails this definition.
Here's a quick test: if you swap the two players mid-game and nothing about the available moves changes, the game is impartial. In Nim, both players can remove stones from any pile — swapping players changes nothing. In chess, if you swap sides, suddenly you're controlling different pieces with different moves. That's a partisan game, and Sprague-Grundy doesn't apply.
The Sprague-Grundy theorem applies to all impartial games. Every single one.
The Mex Function
Before the theorem, you need one operation.
Mex (minimum excludant) of a set \(S\) of non-negative integers is the smallest non-negative integer not in \(S\).
Examples:
| Set \(S\) | \(\text{mex}(S)\) | Why |
|---|---|---|
| \(\{0, 1, 3\}\) | \(2\) | \(0\) and \(1\) are present, \(2\) is missing |
| \(\{1, 2, 3\}\) | \(0\) | \(0\) is missing |
| \(\{0, 1, 2, 3\}\) | \(4\) | All of \(0\) through \(3\) are present |
| \(\{\}\) | \(0\) | Empty set — \(0\) is missing |
| \(\{0\}\) | \(1\) | \(0\) is present, \(1\) is missing |
The mex finds the "hole" in the set. Think of lining up non-negative integers and scanning left to right — the first gap is the mex.
Mex Implementation: Watch the Complexity
A common mistake is computing mex with a set<int> and a while loop — while (reachable.count(mex)) mex++. If the reachable set has \(k\) elements, this is \(O(k \log k)\) per position (insert into set + scan). For games where each position has up to \(k\) moves and there are \(n\) positions, total cost is \(O(nk \log k)\).
The \(O(k)\) alternative: use a boolean array of size \(k+1\) (since mex is at most \(k\)), mark which values appear, then scan linearly:
int computeMex(vector<int>& reachableGrundy) {
int k = reachableGrundy.size();
vector<bool> present(k + 1, false);
for (int g : reachableGrundy) {
if (g <= k) present[g] = true;
}
for (int i = 0; i <= k; i++) {
if (!present[i]) return i;
}
return k + 1; // unreachable
}
This avoids the \(O(\log k)\) per-insert cost of set and runs in strict \(O(k)\). When \(n\) and \(k\) are both \(10^5\), this difference can be the line between AC and TLE.
The Grundy Number
Every position in an impartial game gets a number called its Grundy number (also called a nimber). The definition is recursive:
In words: from your current position, look at every position you can move to. Compute their Grundy numbers. Collect those numbers into a set. Take the mex.
The base case: a position with no moves (a losing position for the player whose turn it is) has \(G = \text{mex}(\{\}) = 0\).
The key insight through the pillar lens: \(G(n)\) depends on the Grundy values of positions reachable from \(n\), which in turn depend on positions reachable from them. This is a dependency chain that bottoms out at terminal positions.
Why Mex?
Why is mex the right function? Think about what it encodes.
A Nim pile of size \(g\) lets you move to any pile of size \(0, 1, \ldots, g - 1\). That means the set of Grundy values reachable from a Nim pile of size \(g\) is exactly \(\{0, 1, \ldots, g - 1\}\).
Now consider a game position where the reachable Grundy values are \(\{0, 1, 3\}\). The mex is \(2\). A Nim pile of size \(2\) has reachable Grundy values \(\{0, 1\}\). These aren't the same set — but strategically, the position behaves like a Nim pile of size \(2\). The position can reach Grundy \(0\) and \(1\) (just like the Nim pile), and it can also reach Grundy \(3\) (which the Nim pile can't) — but reaching a higher Grundy value is never advantageous. The critical property is: you can reach \(0\) and \(1\) but not \(2\). That's exactly the fingerprint of a Nim pile of size \(2\).
The mex captures the smallest value you can't reach — and that's the value that makes the position strategically equivalent to the corresponding Nim pile.
The Theorem
Sprague-Grundy Theorem. Every position in an impartial game with Grundy number \(g\) is equivalent to a single Nim pile of size \(g\).
What "equivalent" means: replacing a sub-game with a Nim pile of the same Grundy number doesn't change who wins. A position with \(G = 0\) is a losing position for the player to move (a P-position). A position with \(G > 0\) is a winning position (an N-position).
This is the bridge between arbitrary impartial games and Nim. You don't need to analyze the game tree — just compute Grundy numbers.
Game Decomposition
Most competitive programming game problems involve multiple independent sub-games played simultaneously. On each turn, a player picks one sub-game and makes a move in it. The combined game ends when no moves remain in any sub-game.
Sprague-Grundy for sums of games. If a game decomposes into independent sub-games with Grundy numbers \(G_1, G_2, \ldots, G_k\), then:
where \(\oplus\) is XOR.
This is exactly the Nim XOR trick from Ch8 L1, but generalized. Standard Nim is a special case: each pile is an independent sub-game, and the Grundy number of a pile of size \(n\) in standard Nim is just \(n\). So XOR of pile sizes gives the combined Grundy number.
For non-standard games, compute each sub-game's Grundy number with the mex recursion, then XOR them. First player wins if and only if the XOR is nonzero.
Concrete example. Suppose you have three piles in a subtraction game with allowed moves \(\{1, 2, 3\}\). Pile sizes: \(5\), \(8\), \(6\).
- \(G(5) = 5 \bmod 4 = 1\)
- \(G(8) = 8 \bmod 4 = 0\)
- \(G(6) = 6 \bmod 4 = 2\)
- Combined: \(1 \oplus 0 \oplus 2 = 3 \neq 0\). First player wins.
The winning strategy: move in one pile to make the XOR equal \(0\). Currently \(1 \oplus 0 \oplus 2 = 3\). If you change pile \(1\) from Grundy \(1\) to Grundy \(2\) (i.e., move it from position \(5\) to position \(6 \bmod 4 = 2\)... wait, you need position \(5 \to 2\), which means removing \(3\) stones), the XOR becomes \(2 \oplus 0 \oplus 2 = 0\). Your opponent is now in a P-position no matter which pile they touch.
Worked Example: Subtraction Game
The subtraction game with allowed moves \(\{1, 2, 3\}\). From position \(n\), you can move to \(n - 1\), \(n - 2\), or \(n - 3\) (if those positions are \(\geq 0\)). Whoever takes the last stone wins.
Compute Grundy numbers bottom-up from position \(0\):
Position \(0\): No moves available. \(G(0) = \text{mex}(\{\}) = 0\).
Position \(1\): Can move to \(0\). Reachable Grundy values: \(\{G(0)\} = \{0\}\). \(G(1) = \text{mex}(\{0\}) = 1\).
Position \(2\): Can move to \(1\) or \(0\). Reachable: \(\{G(1), G(0)\} = \{1, 0\}\). \(G(2) = \text{mex}(\{0, 1\}) = 2\).
Position \(3\): Can move to \(2\), \(1\), or \(0\). Reachable: \(\{G(2), G(1), G(0)\} = \{2, 1, 0\}\). \(G(3) = \text{mex}(\{0, 1, 2\}) = 3\).
Position \(4\): Can move to \(3\), \(2\), or \(1\). Reachable: \(\{G(3), G(2), G(1)\} = \{3, 2, 1\}\). \(G(4) = \text{mex}(\{1, 2, 3\}) = 0\).
Position \(5\): Can move to \(4\), \(3\), or \(2\). Reachable: \(\{G(4), G(3), G(2)\} = \{0, 3, 2\}\). \(G(5) = \text{mex}(\{0, 2, 3\}) = 1\).
Continue for all positions through \(10\):
| Position | Reachable Grundy values | \(G(\text{position})\) |
|---|---|---|
| \(0\) | \(\{\}\) | \(0\) |
| \(1\) | \(\{0\}\) | \(1\) |
| \(2\) | \(\{0, 1\}\) | \(2\) |
| \(3\) | \(\{0, 1, 2\}\) | \(3\) |
| \(4\) | \(\{1, 2, 3\}\) | \(0\) |
| \(5\) | \(\{0, 2, 3\}\) | \(1\) |
| \(6\) | \(\{0, 1, 3\}\) | \(2\) |
| \(7\) | \(\{0, 1, 2\}\) | \(3\) |
| \(8\) | \(\{1, 2, 3\}\) | \(0\) |
| \(9\) | \(\{0, 2, 3\}\) | \(1\) |
| \(10\) | \(\{0, 1, 3\}\) | \(2\) |
The pattern: \(G(n) = n \bmod 4\).
This makes sense. The moves \(\{1, 2, 3\}\) create a cycle of length \(4\) (one more than the max move). At multiples of \(4\), you're in a losing position — no matter what you take (\(1\), \(2\), or \(3\)), your opponent can take enough to reach the next multiple of \(4\). Exactly like Nim with a cap.
Back to the original question: with \(7\) stones, \(G(7) = 7 \bmod 4 = 3 \neq 0\). First player wins. The winning move: remove \(3\) stones, leaving \(4\) (a P-position for your opponent).
What if the moves aren't consecutive? Try allowed moves \(\{1, 3, 4\}\) instead. Compute a few values:
| Position | Reachable positions | Reachable Grundy values | \(G(\text{position})\) |
|---|---|---|---|
| \(0\) | — | \(\{\}\) | \(0\) |
| \(1\) | \(\{0\}\) | \(\{0\}\) | \(1\) |
| \(2\) | \(\{1\}\) | \(\{1\}\) | \(0\) |
| \(3\) | \(\{2, 0\}\) | \(\{0\}\) | \(1\) |
| \(4\) | \(\{3, 1, 0\}\) | \(\{0, 1\}\) | \(2\) |
| \(5\) | \(\{4, 2, 1\}\) | \(\{0, 1, 2\}\) | \(3\) |
| \(6\) | \(\{5, 3, 2\}\) | \(\{0, 1, 3\}\) | \(2\) |
| \(7\) | \(\{6, 4, 3\}\) | \(\{1, 2\}\) | \(0\) |
| \(8\) | \(\{7, 5, 4\}\) | \(\{0, 2, 3\}\) | \(1\) |
| \(9\) | \(\{8, 6, 5\}\) | \(\{1, 2, 3\}\) | \(0\) |
| \(10\) | \(\{9, 7, 6\}\) | \(\{0, 2\}\) | \(1\) |
The pattern \(0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, \ldots\) isn't as clean as \(n \bmod 4\). The Sprague-Grundy periodicity theorem guarantees that for any subtraction game, the Grundy sequence eventually becomes periodic. But the period length can be surprising. For non-trivial move sets, just compute the table with DP and look for the repeating pattern.
General rule for subtraction games. If the allowed moves are \(\{1, 2, \ldots, m\}\), then \(G(n) = n \bmod (m + 1)\). When the allowed moves are an arbitrary set, the pattern is still periodic — but the period isn't always obvious, so you compute it with DP.
Computing Grundy Numbers
Two approaches: memoized recursion (for game graphs where you don't visit all states) or bottom-up DP (when you need all values up to some bound). The DP approach is standard for competitive programming because most problems involve pile-based games where you need Grundy values for every size up to some maximum.
#include <bits/stdc++.h>
using namespace std;
vector<int> computeAllGrundy(int maxPosition, vector<int>& allowedMoves) {
int numMoves = allowedMoves.size();
vector<int> grundy(maxPosition + 1, 0);
for (int position = 1; position <= maxPosition; position++) {
vector<int> reachable;
for (int move : allowedMoves) {
if (position >= move) {
reachable.push_back(grundy[position - move]);
}
}
// O(k) mex using boolean array (see above)
int k = reachable.size();
vector<bool> present(k + 1, false);
for (int g : reachable) {
if (g <= k) present[g] = true;
}
int mexValue = 0;
while (mexValue <= k && present[mexValue]) mexValue++;
grundy[position] = mexValue;
}
return grundy;
}
int main() {
int numPiles, numMoves;
cin >> numPiles >> numMoves;
vector<int> allowedMoves(numMoves);
for (int i = 0; i < numMoves; i++) cin >> allowedMoves[i];
vector<int> pileSizes(numPiles);
int maxPile = 0;
for (int i = 0; i < numPiles; i++) {
cin >> pileSizes[i];
maxPile = max(maxPile, pileSizes[i]);
}
vector<int> grundy = computeAllGrundy(maxPile, allowedMoves);
int xorSum = 0;
for (int pile : pileSizes) xorSum ^= grundy[pile];
cout << (xorSum != 0 ? "first" : "second") << "\n";
return 0;
}
The game decomposition solver in action: compute Grundy values for all reachable pile sizes, XOR across piles, output the winner.
For games where the state space isn't a simple linear chain (e.g., graph games where you move a token along edges), use memoized recursion instead:
#include <bits/stdc++.h>
using namespace std;
int computeGrundy(int node, vector<vector<int>>& adjacencyList, vector<int>& grundyCache) {
if (grundyCache[node] != -1) return grundyCache[node];
set<int> reachableGrundy;
for (int neighbor : adjacencyList[node]) {
reachableGrundy.insert(computeGrundy(neighbor, adjacencyList, grundyCache));
}
int mexValue = 0;
while (reachableGrundy.count(mexValue)) mexValue++;
return grundyCache[node] = mexValue;
}
This handles DAG-structured game graphs where the positions aren't just integers. The adjacency list defines which positions are reachable from each node. The cache prevents recomputation — without it, you'd re-traverse the entire sub-DAG for every query.
Note: the game graph must be a DAG (no cycles). If cycles exist, the game might not terminate, violating the impartial game definition. In practice, competitive programming game problems always give you acyclic state spaces.
Complexity
\(O(N \times M)\) time to compute Grundy values for positions \(0\) through \(N\), where \(M\) is the number of allowed moves. \(O(N)\) space for the Grundy table. The mex computation inside each position costs \(O(M)\) amortized since the set of reachable Grundy values has at most \(M\) elements. For graph-based games, \(O(V + E)\) time and \(O(V)\) space where \(V\) is the number of game states and \(E\) is the total number of transitions.
Common Mistakes
-
Forgetting that \(G(0) = 0\), not undefined. A terminal position (no moves available) always has Grundy number \(0\). This is the base case of the recursion. If you skip it or initialize it wrong, the entire chain of Grundy values collapses.
-
Computing mex incorrectly. Mex is the smallest non-negative integer not in the set — not the smallest element, not the max plus one. If the reachable Grundy values are \(\{0, 2, 3\}\), the mex is \(1\), not \(4\). Use a loop that increments from \(0\) until it finds a gap.
-
Confusing Grundy number with win/loss. \(G = 0\) means losing position. \(G > 0\) means winning position. But the Grundy number carries more information than just win/loss — it tells you the equivalent Nim pile size, which matters when you XOR across sub-games. Two sub-games with \(G = 3\) XOR to \(0\) (a loss), even though each individually is a winning position.
Quick Recap
- Every impartial game position has a Grundy number: \(G(\text{pos}) = \text{mex}(\{G(s') : s' \text{ reachable}\})\).
- \(G = 0\) means the current player loses (P-position). \(G > 0\) means the current player wins (N-position).
- The Sprague-Grundy theorem: every position is equivalent to a Nim pile of size \(G\).
- For compound games (sum of independent sub-games), XOR the individual Grundy numbers.
- Subtraction games with moves \(\{1, 2, \ldots, m\}\) have \(G(n) = n \bmod (m + 1)\). Arbitrary move sets produce periodic Grundy sequences computable with DP.
- Mex works because the smallest unreachable Grundy value is what makes a position equivalent to the corresponding Nim pile — you can reach everything below it, and that's what matters strategically.
- For graph games (tokens on DAGs), use memoized recursion. For linear games (piles with move constraints), use bottom-up DP.
Problems
| Problem | Link | Difficulty | Focus |
|---|---|---|---|
| CSES — Nim Game II | cses.fi/problemset/task/1098 | Medium | Subtraction game with custom move set; compute Grundy values via DP, XOR across piles |
| CSES — Stair Game | cses.fi/problemset/task/1099 | Medium | Recognize staircase Nim as Nim on odd-indexed stairs; Grundy decomposition |
| LC 464 — Can I Win | leetcode.com/problems/can-i-win | Medium | Bitmask game state DP; each number is usable once, compute win/loss per state |
| CSES — Grundy's Game | cses.fi/problemset/task/2207 | Hard | Split a pile into two unequal parts; Grundy values don't have a clean closed form — precompute and XOR |