i. Combinatorial Games and Nim

Combinatorial game theory studies two-player games with perfect information (no hidden state, so chess yes, poker no), no chance (no dice or cards, so no Monopoly), alternating turns and finite termination. Under normal play the player who cannot move loses; under misère play that player wins. Games that can go on forever (draws) are in Loopy Games; games with scores in Game DP and Minimax.

	Impartial	Partizan
legal moves	the same for both players	depend on whose turn it is
examples	Nim, subtraction games, Chomp, Kayles	chess, checkers, Blue-Red Hackenbush, Domineering
theory	Sprague–Grundy: every position equals one Nim heap	game values, surreal numbers
solved by	XOR of Grundy values	sums of values, minimax

Term	Meaning
terminal position	no legal moves
P-position	the Previous player wins: the player to move loses
N-position	the Next player (to move) wins
nim-sum	XOR of heap sizes
Grundy number (nim-value)	the size of the equivalent single Nim heap: Sprague–Grundy
mex	minimum excluded non-negative integer
disjoint sum	independent games side by side; a move is made in exactly one component

Win / lose classification

Under normal play, for any finite game: a position is losing iff every move leads to a winning position (in particular terminal positions lose), and winning iff some move leads to a losing position.

// moves(s) lists the positions reachable from s (the game must be finite and acyclic)
vector<int> memoWin;                                     // -1 unknown, 0 lose, 1 win
bool winning(int s, const vector<vector<int>>& moves) {
    if (memoWin[s] != -1) return memoWin[s];
    bool w = false;
    for (int t : moves[s]) if (!winning(t, moves)) { w = true; break; }
    memoWin[s] = w;
    return w;
}

Solving an unfamiliar game: (1) impartial? If not, minimax or game values. (2) Does it split into independent components? Then Grundy values and XOR. (3) Small state space? Memoized W/L search. (4) Otherwise compute small cases and look for a pattern: brute-force the first 30–50 values, print them, search OEIS; periodic sequences, $n\mathrm{mod}k$ and $\mathrm{ctz}(n)$-style patterns are common, and the guess must be verified on a longer range. (5) Can positions repeat? Plain memoization loops: use retrograde analysis and allow draws (Loopy Games).

Nim

Several heaps; a move removes any positive number of stones from one heap; the player who cannot move loses.

Bouton’s theorem. The first player wins iff the nim-sum $a_1\oplus a_2\oplus \cdots \oplus a_n\ne 0$. A winning move: with $S\ne 0$, pick a heap with $a_i\oplus S<a_i$ (any heap having the highest set bit of $S$) and reduce it to $a_i\oplus S$.

Misère Nim (taking the last stone loses): play as in normal Nim unless every heap has size at most 1; then the first player wins iff the number of heaps of size 1 is even.

bool nimFirstWins(const vector<ll>& a) { ll x = 0; for (ll h : a) x ^= h; return x != 0; }
 
pair<int, ll> nimWinningMove(const vector<ll>& a) {      // (heap, new size), or (-1, -1) if losing
    ll S = 0; for (ll h : a) S ^= h;
    if (!S) return {-1, -1};
    for (int i = 0; i < sz(a); i++) if ((a[i] ^ S) < a[i]) return {i, a[i] ^ S};
    return {-1, -1};
}
 
bool misereNimFirstWins(const vector<ll>& a) {
    ll S = 0; int big = 0, ones = 0;
    for (ll h : a) { S ^= h; big += h > 1; ones += h == 1; }
    if (big == 0) return ones % 2 == 0;                  // only heaps of size 0 and 1
    return S != 0;
}

Proof: Bouton's theorem and the winning move

Call a position zero if its nim-sum is 0. From zero, every move gives non-zero: changing one heap from $a$ to $a^{\prime }\ne a$ changes the nim-sum by $a\oplus a^{\prime }\ne 0$. From non-zero, some move gives zero: let $b$ be the highest set bit of $S$; some heap $a_i$ has bit $b$ set (otherwise bit $b$ of $S$ would be 0). In $a_i\oplus S$ bit $b$ turns off and higher bits are unchanged, so $a_i\oplus S<a_i$ and reducing heap $i$ to it is legal; the new nim-sum is $S\oplus a_i\oplus (a_i\oplus S)=0$. The terminal position (all heaps empty) is zero and losing. By induction on the total number of stones, zero positions are exactly the losing ones.

Proof: misère Nim

Claim: the P-positions are (a) all heaps $\le 1$ with an odd number of 1-heaps, and (b) some heap $\ge 2$ with nim-sum 0. Under misère play the empty position is an N-position (the opponent took the last stone). From (a) a move removes a 1-heap, leaving an even number of 1-heaps and no big heap: not (a) or (b). From (b): with nim-sum 0 at least two heaps are $\ge 2$ (a single big heap’s high bit could not cancel), a move changes one heap, so a big heap survives and the nim-sum becomes non-zero: not (a) or (b). From any other position some move reaches (a) or (b): if all heaps are $\le 1$ with an even, positive number of 1-heaps, remove one; if exactly one heap is $\ge 2$, reduce it to 0 or 1 so that the number of 1-heaps is odd; if at least two heaps are $\ge 2$ and the nim-sum is non-zero, the Bouton move keeps one big heap and reaches (b). By induction on the number of stones this is the classification. Note the count is of heaps of size 1: empty heaps do not matter (the classic one-liner a.size() % 2 is wrong when zero heaps are present).

Nim variants

Variant	Rule	Losing positions (or Grundy value)
Nim	remove any number from one heap	XOR $=0$
misère Nim	the last stone loses	as above
bounded Nim	remove $\mathrm{1..}m$ from one heap	$g(a)=a\mathrm{mod}(m+1)$; XOR of these $=0$
Moore’s Nim${}_k$	remove from up to $k$ heaps at once	every binary digit column sums to $0\mathrm{mod}(k+1)$
staircase Nim	move coins from step $i$ to step $i-1$; step 0 is dead	XOR of the odd-indexed steps $=0$
Wythoff’s game	two heaps; remove from one, or the same amount from both	$(\lfloor k\phi \rfloor ,\lfloor k{\phi }^2\rfloor )$: see Wythoff’s Game
subtraction games	remove $s\in S$	Grundy values, eventually periodic for finite $S$: Sprague–Grundy
Lasker’s Nim	remove any number, or split a heap in two	$g(4k+1)=4k+1$, $g(4k+2)=4k+2$, $g(4k+3)=4k+4$, $g(4k+4)=4k+3$
Kayles, Dawson’s chess, Grundy’s game	remove pins / split a row	splitting games, periods 12 and 34: Sprague–Grundy
turning games (Turning Turtles, Mock Turtles)	flip coins	Grundy theory, $g(n)=n$ and odious numbers
Green Hackenbush	cut edges of a rooted graph	colon and fusion principles: Hackenbush
Cram (impartial) / Domineering (partizan)	place dominoes	Grundy values / game values; no simple closed form on general boards, both are computed, not derived
Col, Snort (partizan map-colouring games)	colour regions of a map, adjacent regions must differ (Col) / may not both be the player’s colour (Snort)	game values; Snort reduces to a sum of games on the complement graph’s components
Chomp, Hex		strategy stealing: Chomp and Hex
Dots and Boxes (via strings-and-coins)	draw one edge of a grid; completing a box’s 4th edge scores and grants another move	each undrawn edge of a box is a “string” to a “coin” (a shared edge is one string to two coins); long chains and loops of coins behave like Nim heaps with an extra “loony” twist (double-crossing a long chain or loop controls who opens the next one)

Many “push tokens toward the exit” games reduce to staircase Nim (for example coins on a line moving left, scored by the gaps between them), and “each move takes $\mathrm{1..}m$” is the most common contest variation.

bool mooreLoses(const vector<ll>& a, int k) {            // Nim_k: remove from up to k heaps
    for (int b = 0; b < 62; b++) {
        int s = 0;
        for (ll h : a) s += h >> b & 1;
        if (s % (k + 1)) return false;
    }
    return true;
}
 
bool staircaseFirstWins(const vector<ll>& c) {           // c[i] coins on step i, moves go i -> i-1
    ll x = 0;
    for (int i = 1; i < sz(c); i += 2) x ^= c[i];
    return x != 0;
}
 
bool boundedNimFirstWins(const vector<ll>& a, ll m) {     // each move removes 1..m from one heap
    ll x = 0; for (ll h : a) x ^= h % (m + 1);
    return x != 0;
}

Proof: Moore's Nim, staircase Nim and bounded Nim

Moore. Call a position balanced if every bit column has a count divisible by $k+1$. From balanced, every move unbalances: let $b$ be the highest bit at which some changed heap changes; each changed heap decreases, so at its highest changed bit it goes from 1 to 0, hence at bit $b$ between 1 and $k$ heaps lose a one and the column count drops by $t\in [1,k]$, no longer divisible by $k+1$. From unbalanced, some move balances: go from the highest bit down, keeping a set $C$ of chosen heaps, $|C|=m\le k$; a chosen heap already went $1\to 0$ at a higher bit, so its lower bits can be set freely. At bit $b$ let $r$ be the number of ones among unchosen heaps, mod $k+1$. If $m+r\le k$, choose $r$ unchosen heaps with a one at bit $b$, clear their bit (they join $C$) and clear the bit of all chosen heaps; otherwise set the bit to one in $k+1-r\le m$ chosen heaps and to zero in the others. Either way the column becomes divisible by $k+1$ and $|C|\le k$. At the highest unbalanced bit $m=0$ and $1\le r\le k$, so at least one heap is chosen and the move is legal. The empty position is balanced and losing.

Staircase. Let $X$ be the XOR of the odd steps. Every move changes exactly one odd step (from an odd step $i$ the coins leave it; from an even step $i\ge 2$ they arrive at odd step $i-1$), and changing one term changes $X$; so from $X=0$ every move gives $X\ne 0$. From $X\ne 0$, the Bouton move on the odd steps (move coins from odd step $i$ down to step $i-1$) gives $X=0$. When no move is possible all coins are on step 0, so $X=0$. Hence the losing positions are exactly $X=0$ (the game is finite: the total height of the coins decreases).

Bounded Nim. From a heap of size $a$ the options are $a-1,\dots ,a-m$ (those $\ge 0$); by induction their values $(a-s)\mathrm{mod}(m+1)$ are $m$ (or fewer, near 0) consecutive residues avoiding $a\mathrm{mod}(m+1)$ and including all smaller residues, so the mex is $a\mathrm{mod}(m+1)$; Sprague–Grundy gives the XOR rule. All functions were checked against exhaustive game search on small positions.

Related notes

• Sprague–Grundy
• Bachet’s Game, Wythoff’s Game, Coins in a Row
• Bit Tricks and XOR