ii. Sprague-Grundy

Every position of a finite impartial game under normal play is equivalent to a single Nim heap. Its size is the Grundy number (nim-value)
$g(P)=\mathrm{mex}\{g(Q):Q\text{ reachable from }P\},$
where mex is the minimum excluded non-negative integer; terminal positions get $\mathrm{mex}(\varnothing )=0$. Then $g(P)=0$ iff $P$ is losing, and the value of a disjoint sum (a move changes exactly one component) is the XOR:
$g(G_1+\cdots +G_k)=g(G_1)\oplus \cdots \oplus g(G_k).$
A game with $k$ independent components has $\prod |S_i|$ positions but needs only $k$ Grundy computations. To find a winning move, pick a component and a move in it that turns the total XOR into 0 (as in Nim). Cost: $O(\text{states}\times \text{out-degree})$ for all values, $O(k)$ to combine.

Nimber is the formal name (from Conway’s combinatorial game theory) for a Grundy value viewed as an element of an algebraic structure rather than just an integer: nimbers under “nimber addition” (defined as XOR, matching the disjoint-sum rule above) and a separate “nimber multiplication” (a more exotic operation, computed recursively via $a\ast b=\text{mex}\{(a^{\prime }\ast b)\oplus (a\ast b^{\prime })\oplus (a^{\prime }\ast b^{\prime }):a^{\prime }<a,b^{\prime }<b\}$) form a field — this lets a game be analysed as an algebraic value, which is how Hackenbush/Nim-like sums get combined in deeper combinatorial-game-theory arguments. Nimber multiplication itself is essentially never needed directly in CP (every problem in this repo’s scope only uses nimber addition, i.e. plain XOR); it is cited here, not derived, purely so the term “nimber” is not an unexplained gap.

// Grundy values of an acyclic game graph given in topological order of "moves go to smaller ids" (or any DAG order).
vector<int> grundyAll(const vector<vector<int>>& moves, const vector<int>& order) {   // order: sinks first
    int n = sz(moves); vector<int> g(n, 0), seen(n + 2, -1);
    for (int s : order) {
        for (int t : moves[s]) if (g[t] <= n) seen[g[t]] = s;                    // mark with the state id: no clearing
        int m = 0; while (seen[m] == s) m++;
        g[s] = m;
    }
    return g;
}
 
// Row games ("octal-like"): a row of n pins, a move removes r in R adjacent pins anywhere, possibly splitting the row.
// Kayles: R = {1, 2}; Dawson's Kayles: R = {2} (Dawson's chess with n pawns = Dawson's Kayles with n + 1 pins).
vector<int> rowGameGrundy(int N, const vector<int>& R) {
    vector<int> g(N + 1, 0), seen(2 * N + 4, -1);
    for (int n = 1; n <= N; n++) {
        for (int r : R) for (int a = 0; a + r <= n; a++) seen[g[a] ^ g[n - r - a]] = n;
        int m = 0; while (seen[m] == n) m++;
        g[n] = m;
    }
    return g;
}
 
// Smallest period p (with start n0) such that g[n + p] = g[n] holds on [n0, 2 n0 + p + t), which by the
// Guy-Smith periodicity theorem proves periodicity forever (t = largest number of pins removed). {-1,-1} if none.
pair<int, int> certifiedPeriod(const vector<int>& g, int t, int maxP) {
    int N = sz(g) - 1;
    for (int p = 1; p <= maxP; p++) {
        int n0 = N - p;
        while (n0 > 0 && g[n0 - 1 + p] == g[n0 - 1]) n0--;
        if (2 * n0 + p + t <= N - p) return {n0, p};
    }
    return {-1, -1};
}
 
vector<int> subtractionGrundy(int N, const vector<int>& S) {    // remove s in S stones from one heap
    vector<int> g(N + 1, 0), seen(sz(S) + 2, -1);
    for (int n = 1; n <= N; n++) {
        for (int s : S) if (s <= n && g[n - s] <= sz(S)) seen[g[n - s]] = n;
        int m = 0; while (seen[m] == n) m++;
        g[n] = m;
    }
    return g;
}
 
int mockTurtles(ll i) { return int(2 * i + (__builtin_popcountll(i) % 2 == 0)); }   // i-th odious number

Known values

Game	Grundy value
Nim heap of size $a$	$a$
subtraction game $S=\{\mathrm{1..}m\}$	$a\mathrm{mod}(m+1)$ (so $\{1,2\}$: $a\mathrm{mod}3$)
$S=\{1,3,4\}$	period 7: $0,1,0,1,2,3,2$
$S=\{2,3\}$	period 5: $0,0,1,1,2$
any finite $S$	eventually periodic (theorem below)
$S$ = all squares, all primes	irregular, no closed form known
Lasker’s Nim (remove, 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 (remove 1 or 2 adjacent pins)	period 12 from $n=71$ on: $g(\mathrm{71..82})=7,4,1,2,8,1,4,7,2,1,8,2$
Dawson’s Kayles (remove exactly 2 adjacent pins)	period 34 from $n=53$ on
Grundy’s game (split a heap into two unequal heaps)	computed to huge $n$, no period found
Green Hackenbush on a tree	${⨁}_{\text{children}}(g(c)+1)$: Hackenbush
Turning Turtles (turn one coin H$\to$T, optionally one coin to its left)	single head at position $i$ (from 1): $g=i$, i.e. plain Nim
Mock Turtles (turn up to 3 coins, the rightmost H$\to$T)	single head at position $i$ (from 0): the $i$-th odious number $2i$ or $2i+1$
coin-turning games in general	a position is the XOR of its single-head values

Practical recipe: write a brute-force grundy for small states, print the first 30–50 values, guess the pattern (constant, $n\mathrm{mod}k$, periodic, $\mathrm{ctz}(n)$, $\lfloor n/2\rfloor$, a binary pattern), verify against the brute force on a larger range, and if nothing appears, precompute or search OEIS. For splitting moves the reachable set contains XORs of the parts, g[i] ^ g[n - r - i]: this XOR inside the mex is where the theory does its real work (Kayles, Dawson’s chess, “cut the row” games).

Proof: the Sprague–Grundy theorem

Write $G\equiv H$ if $G+K$ and $H+K$ have the same winner for every game $K$. Claim: every position $P$ satisfies $P\equiv \ast g(P)$, the Nim heap of size $g(P)$. Induction on the (well-founded) game order. By the mex definition the options of $P$ include, for every $k<g(P)$, a position of value $k$, which by induction is equivalent to $\ast k$; and no option has value $g(P)$. Consider $P+\ast g(P)+K$ against $\ast g(P)+\ast g(P)+K$; it suffices to show that $P+\ast g(P)$ is a second-player win. Indeed, adding a second-player win $Z$ never changes the winner of a game $X$ (whoever wins $X$ keeps playing there and answers every move in $Z$ by $Z$‘s second-player strategy), and $\ast m+\ast m$ is a second-player win (mirror), so $P+K\equiv P+K+\ast g(P)+\ast g(P)=(P+\ast g(P))+(\ast g(P)+K)\equiv \ast g(P)+K$. In $P+\ast g(P)$: if the first player moves the heap to $\ast k$, $k<g(P)$, the second player moves $P$ to an option of value $k$, giving $Q+\ast k$ with $Q\equiv \ast k$, a second-player win by induction. If the first player moves $P$ to an option $Q$ with $g(Q)=k$: if $k<g(P)$, reply by moving the heap to $\ast k$; if $k>g(P)$, $Q$ has an option of value $g(P)$ (mex), move there. Either way the second player restores a position of the form $R+\ast g(R)$, and the game is finite.

Sums. Each component is equivalent to a Nim heap, so the sum is equivalent to a Nim position, whose value is the XOR of the heap sizes (Bouton). In particular a sum is losing iff the XOR is 0.

Proof: eventual periodicity (subtraction games and the Guy–Smith certificate)

Finite subtraction sets. With $S$ finite, $g(n)$ is the mex of at most $|S|$ values, so $g(n)\le |S|$. The value $g(n)$ depends only on the window $(g(n-1),\dots ,g(n-\max S))$, which takes at most $(|S|+1{)}^{\max S}$ values. Some window repeats, at $n_0$ and $n_0+p$, and from then on the sequence repeats with period $p$ (the recurrence is deterministic). The code’s seen array is indexed by values $\le |S|$.

Row games (Guy–Smith). Suppose moves remove at most $t$ pins and $g(n+p)=g(n)$ for all $n$ in $[n_0,2n_0+p+t)$. Take $N\ge 2n_0+p+t$ and assume the relation for all $n_0\le n<N$. An option of $N+p$ removes $r\le t$ pins and leaves rows $a,b$ with $a+b=N+p-r\ge 2n_0+2p$, so one of them, say $b$, is at least $n_0+p$, and $g(b)=g(b-p)$ with $n_0\le b-p<N$; hence $g(a)\oplus g(b)$ is the value of the option $(a,b-p)$ of $N$. Conversely an option $(a^{\prime },b^{\prime })$ of $N$ has $a^{\prime }+b^{\prime }=N-r\ge 2n_0$, so one part, say $b^{\prime }$, is at least $n_0$ and $g(b^{\prime }+p)=g(b^{\prime })$, giving an option of $N+p$ with the same value. Equal option sets give $g(N+p)=g(N)$. certifiedPeriod checks exactly this window; it certifies Kayles (period 12 from 71) and Dawson’s Kayles (period 34 from 53).

Proof: Lasker's Nim

Claim for $n\ge 1$: $g(n)\mathrm{mod}4=f(n\mathrm{mod}4)$ with $f(1)=1,f(2)=2,f(3)=0,f(0)=3$, and precisely $g(4k+1)=4k+1$, $g(4k+2)=4k+2$, $g(4k+3)=4k+4$, $g(4k+4)=4k+3$. Induction on $n$. Removals reach every $m<n$; by induction $\{g(m):m<n\}$ is $\{0,\dots ,n-1\}$ when $n\equiv 1,2,3(\mathrm{mod}4)$, and $\{0,\dots ,n-2\}\cup \{n\}$ when $n\equiv 0$. Splits $a+b=n$ ($a,b\ge 1$) give $g(a)\oplus g(b)$, whose residue mod 4 is $f(a)\oplus f(b)$. For $n\equiv 1$: residue pairs $(0,1),(2,3)$ give $3\oplus 1=2$ and $2\oplus 0=2$, so splits are $\equiv 2$ and miss $n$: $g(n)=n$. For $n\equiv 2$: pairs $(0,2),(1,1),(3,3)$ give $1,0,0$: splits miss $n$, $g(n)=n$. For $n\equiv 3$: pairs $(0,3),(1,2)$ give $3,3$; the split $1+(n-1)$ gives $1\oplus (n-1)=n$, and no option equals $n+1\equiv 0$: $g(n)=n+1$. For $n\equiv 0$: the value $n-1$ is missing from removals, and splits give residues $(0,0)\to 0$, $(1,3)\to 1$, $(2,2)\to 0$, never $3$: $g(n)=n-1$.

Proof: coin-turning games are sums of single heads

In a coin-turning game a move turns over a set of coins whose rightmost one goes from heads to tails, and the allowed sets do not depend on the other coins. Identify a position with the sum of single-head games, one per head. A move at a head $i$ is the same in both: remove component $i$, and toggle the coins to its left; a toggled tail becomes a new single-head component, and a toggled head $j$ becomes a second component at $j$. Two equal components sum to a second-player win ($G+G\equiv 0$, mirror strategy), so adding a second copy of the head-$j$ game is equivalent to removing the first. Hence the position and the sum always have equal values, and the value is the XOR of single-head values. Checked by exhaustive search over all positions of up to 12 coins for Turning Turtles ($g=i$) and Mock Turtles (odious numbers).

What Grundy numbers cannot do

Situation	Why it fails	Use instead
partizan games	Sprague–Grundy needs identical move sets	minimax, game values: Hackenbush and Surreal Numbers
misère play	the sum rule breaks	misère Nim, genus theory, or find the pattern
draws / infinite play	not a finite game	generalized Sprague–Grundy, retrograde analysis: Loopy Games
chance	not deterministic	expectiminimax
moves touching several components	the sum rule needs independence	model as one game
scores (“who wins and by how much”)	Grundy is about win/lose only	advantage DP: Game DP

Applications: Nim itself (heap = value), Wythoff’s game (with an extra move type), turning and coin games, Green Hackenbush, and almost every multi-pile contest game problem.

Related notes

• Combinatorial Games and Nim
• Loopy Games
• Bachet’s Game