Pattern Reference
Sprague-Grundy Theorem
"Grundy numbers for impartial games. Compute mex, XOR combined games, game of Nim, Kayles, subtraction games."
Loading...
Deep Dive Tutorial
Grundy value (nimber) of a position = mex of Grundy values of all positions reachable in one move. mex = minimum excludant = smallest non-negative integer not in the set {0, 1, 2} → mex = 3; {0, 2} → mex = 1. A position is a losing position (P-position) iff its Grundy value is 0. Combined games (play multiple independent games, choose one to move in): XOR all Grundy values — non-zero means first player wins.
Grundy value computation
// Compute Grundy values for all states via memoization
function grundy(state, getNextStates, memo = new Map()) {
if (memo.has(state)) return memo.get(state);
const nextGrundy = new Set(getNextStates(state).map(s => grundy(s, getNextStates, memo)));
// Compute mex: smallest non-negative integer not in nextGrundy
let mex = 0;
while (nextGrundy.has(mex)) mex++;
memo.set(state, mex);
return mex;
}
// Standard Nim: n piles of stones, can remove any amount from one pile
// G(pile of k stones) = k (take k-j stones → pile of j, G = j)
// Combined game: XOR all pile sizes. XOR ≠ 0 → first player wins
// Nim with restricted moves (can only take 1-k stones):
// G(n) = n % (k+1) — this is "subtraction game" with set {1,...,k}
// Example: Wythoff's game (two piles, can remove from one or equal from both)
// Uses golden ratio, complex Grundy valuesWorked Problems
swords
Sprague-Grundy key facts:
- G(state) = mex{G(reachable states)}
- G = 0 → losing position (P-position, previous player wins)
- G > 0 → winning position (N-position, next/current player wins)
- Combined independent games: XOR all Grundy values
Common patterns:
- Nim (remove 1..k from pile of n): G(n) = n % (k+1)
- Standard Nim (remove any): G(n) = n
- Wythoff (two piles, equal removal): uses floor(n * φ) where φ = golden ratio
When SG doesn't apply: Partizan games (different moves for each player) — use Combinatorial Game Theory instead.
- G(state) = mex{G(reachable states)}
- G = 0 → losing position (P-position, previous player wins)
- G > 0 → winning position (N-position, next/current player wins)
- Combined independent games: XOR all Grundy values
Common patterns:
- Nim (remove 1..k from pile of n): G(n) = n % (k+1)
- Standard Nim (remove any): G(n) = n
- Wythoff (two piles, equal removal): uses floor(n * φ) where φ = golden ratio
When SG doesn't apply: Partizan games (different moves for each player) — use Combinatorial Game Theory instead.