Grundy Numbers

Every position in a finite impartial game under normal play is equivalent to a single Nim heap. Its size is the position’s Grundy number (nim-value):

$g (P) = mex {g (Q) : Q reachable from P},$

where $mex$ is the minimum excluded non-negative integer.

$g (P) = 0 ⟺ P is losing.$

Computing them

int grundy(int s) {
    if (done[s]) return g[s];
    done[s] = true;
    set<int> reachable;
    for (int t : moves(s)) reachable.insert(grundy(t));
    int m = 0;
    while (reachable.count(m)) m++;
    return g[s] = m;
}

For an array-based version, use a boolean “seen” array of size $O (degree)$ and reset only the entries you touched — clearing a full array per state turns $O (n \cdot d)$ into $O (n \cdot max g)$ .

Terminal positions have no moves, so $mex (\emptyset) = 0$ — they are losing, as required.

The sum rule — why this matters

Sprague-Grundy: the Grundy value of a disjoint sum of games is the XOR of their Grundy values.

$g (G_{1} + G_{2} + \dots + G_{k}) = g (G_{1}) \oplus g (G_{2}) \oplus \dots \oplus g (G_{k}) .$

So a game with $k$ independent components has $\prod ∣ S_{i} ∣$ positions but needs only $k$ Grundy computations. This is the entire payoff of the theory.

int total = 0;
for (auto& component : components) total ^= grundy(component);
bool firstPlayerWins = (total != 0);

Known Grundy values

Game	Grundy value
Nim heap of size $a$	$a$
Subtraction game $S = {1.. m}$	$a mod (m + 1)$
Subtraction game $S = {1, 2}$	$a mod 3$
Subtraction game $S = {1, 3, 4}$	period 7: $0, 1, 0, 1, 2, 3, 2$
“Remove any square number”	irregular, no closed form known
Lasker’s Nim (remove, or split)	$g (4 k + 1) = 4 k + 1$ , $g (4 k + 2) = 4 k + 2$ , $g (4 k + 3) = 4 k + 4$ , $g (4 k + 4) = 4 k + 3$
Kayles (remove 1 or 2 adjacent pins)	eventually periodic with period 12
Dawson’s chess	eventually periodic with period 34
Green Hackenbush (a tree)	XOR of branch values (the “colon principle”)
Turning Turtles	$g (n) = n$
Mock Turtles	$g (n) = 2 n$ or $2 n + 1$

Almost every subtraction game has an eventually periodic Grundy sequence — a theorem for finite $S$ . So the practical method is: compute the first 100 values, find the period, extrapolate.

The practical recipe

Write a brute-force grundy for small states.
Print the first 30-50 values and look for a pattern.
Common patterns: constant, $n mod k$ , periodic, $ctz (n)$ , $⌊ n /2 ⌋$ , or a pattern in binary.
Verify the guessed formula against the brute force on a larger range.
If no pattern emerges, check whether the state space is small enough to precompute, or search OEIS.

This “compute, observe, conjecture, verify” loop is the standard way these problems are solved in contests — deriving the Grundy formula from first principles is usually much harder than spotting it.

Splitting moves

When a move splits one component into several, the resulting position’s value is the XOR of the parts:

// e.g. break a strip of length n into two strips
for (int i = 0; i + 1 < n; i++)
    reachable.insert(grundy(i) ^ grundy(n - 2 - i));

This is the shape of Kayles, Dawson’s chess, and most “cut the row” games. The XOR inside the mex is where the theory does its real work.

What Grundy numbers cannot do

Situation	Why it fails	Use instead
Partizan games (different moves per player)	Sprague-Grundy assumes impartiality	minimax, surreal numbers
Misère play	the sum rule breaks	genus theory; or find the pattern
Games with draws / infinite play	not a finite impartial game	retrograde analysis
Games with chance	not deterministic	expectiminimax
Moves affecting multiple components	the sum rule requires independence	model as one game
Scoring games (not just win/lose)	Grundy is about W/L only	game DP

The last row is worth flagging: if the problem asks “who wins and by how much”, Grundy numbers do not apply — use the advantage-DP from Game DP.

See also: Sprague-Grundy Theorem · Nim · Combinatorial Games

whoashish's cp notes

Directory