Skip to content

Combinatorial Games: Nim & Sprague–Grundy

Impartial games: both players have the same moves; last move wins (normal play) or loses (misère—harder).

Nim

Heaps of sizes \(a_1,\ldots,a_k\); a move removes any positive number of stones from one heap.

Theorem: first player wins iff XOR of heap sizes is nonzero:

\[ a_1 \oplus a_2 \oplus \cdots \oplus a_k \neq 0 \]

Sprague–Grundy

Each impartial game position has a Grundy number (nimber). A position is losing iff XOR of Grundy numbers of its components (in sum-like decompositions) is zero.

For Nim heap of size \(n\), Grundy number is \(n\). More complex games reduce to computing Grundy via mex (minimum excluded value) of options.