Combinatorial Games

Combinatorial game theory studies two-player games with:

• perfect information — no hidden state, no cards, no dice;
• no randomness — every move fully determines the next position;
• alternating turns;
• finite termination — no infinite play.

Under the normal play convention, the player who cannot move loses. Under misère play, that player wins.

Impartial vs partizan

	Impartial	Partizan
Legal moves	the same for both players	depend on whose turn it is
Examples	Nim, subtraction games, Chomp	chess, checkers, Hackenbush
Theory	Sprague-Grundy — every position ≡ one Nim heap	surreal numbers
Solved by	XOR of Grundy values	game values, minimax

Sprague-Grundy applies only to impartial games. For partizan games use minimax or the surreal-number machinery.

W/L classification

For any impartial game under normal play:

• A position is losing (P-position, previous player wins) iff every move leads to a winning position.
• A position is winning (N-position, next player wins) iff some move leads to a losing position.
• Terminal positions are losing under normal play.

bool win(int s) {
    if (done[s]) return memo[s];
    done[s] = true;
    memo[s] = false;
    for (int t : moves(s))
        if (!win(t)) { memo[s] = true; break; }
    return memo[s];
}

This is enough for small state spaces. For games that decompose into independent parts, Grundy numbers are far more powerful.

The vocabulary

Term	Meaning
Terminal position	no legal moves
P-position	Previous player wins (the player to move loses)
N-position	Next player wins
Nim-sum	XOR of heap sizes
Grundy number / nim-value	the equivalent single Nim heap
mex	minimum excluded non-negative integer
Disjoint sum	independent games played side by side, one move in one component

The disjoint sum principle

If a game splits into independent components, and a move affects exactly one component, the Grundy value of the whole is the XOR of the components’ Grundy values.

This is the reason the theory is useful: a game with $k$ piles has exponentially many positions, but only $k$ Grundy values to compute and XOR. See Sprague-Grundy Theorem.

Solving a game — the procedure

1. Is it impartial? If not, use minimax or game values.
2. Does it decompose into independent components? If yes, compute Grundy values per component and XOR.
3. Is the state space small? If yes, memoised W/L search.
4. Compute small cases and look for a pattern — Grundy sequences are frequently periodic or have a simple closed form.
5. Can positions repeat? Then plain memoization loops; use retrograde analysis (BFS backwards from terminal positions) and allow for draws.

Step 4 is worth emphasising: brute-force the first 30-50 Grundy values, print them, and look. Periodicity, $g(n)=n\mathrm{mod}k$, and $g(n)=\mathrm{ctz}(n)$-style patterns are common, and OEIS often identifies the sequence.

Retrograde analysis

When positions can repeat (so the game graph has cycles), classification must be done backwards:

// deg[s] = number of moves out of s
queue<int> q;
for (terminal s) { result[s] = LOSE; q.push(s); }
while (!q.empty()) {
    int s = q.front(); q.pop();
    for (int p : predecessors(s)) {
        if (result[p] != UNKNOWN) continue;
        if (result[s] == LOSE) { result[p] = WIN; q.push(p); }
        else if (--deg[p] == 0) { result[p] = LOSE; q.push(p); }
    }
}
// anything still UNKNOWN is a DRAW (infinite play)

This is the only correct method when draws are possible, and it is how endgame tablebases are built.

Misère play

The player who cannot move wins. Grundy theory does not transfer directly. The one clean result:

Misère Nim: play as in normal Nim, unless every heap has size 1 — in that case the first player wins iff the number of heaps is even.

General misère theory (genus theory) is genuinely hard. For contest purposes, compute small cases and look for the pattern.

See also: Nim · Grundy Numbers · Sprague-Grundy Theorem