Sprague–Grundy Theorem and Nimbers

Turn any finite impartial game into a Nim problem you can solve. Learn how nimbers come from mex, why sums combine by xor, and how to spot winning moves. Build a workflow that scales from tiny game graphs to families with patterns.

Every impartial game position hides a number that behaves exactly like a Nim heap. That is the punchline of the Sprague–Grundy theorem. If you can compute that number, you can play the original game as if it were Nim, even when the moves look nothing like removing stones from a heap. The surprising part is not that Nim is solvable. It is that lots of other games are solvable for the same reason, and the arithmetic is just xor.

Take a look at how different game graphs can still correspond to the same Nim heap value.

Once you accept that different-looking positions can share the same nimber, the natural question is when you are allowed to make that identification.

When Sprague–Grundy applies and when it does not

The theorem is picky, and most confusion comes from silently changing the rules of the universe.

The required setup

• Impartial game means the set of legal moves from a position does not depend on which player is to move.
• Normal play means the player who makes the last move wins.
• The game graph is finite and acyclic, so play cannot continue forever and positions do not repeat.
• A disjunctive sum is the play convention where on each turn you choose exactly one component game and make one move in it.

Under these conditions, every position has a well-defined nimber, and a sum of games is equivalent to a Nim position whose heaps are those nimbers.

See how changing normal-play or impartial assumptions breaks the clean Nim equivalence.

A useful way to hold the conditions in your head is that Sprague–Grundy is a theorem about finite directed acyclic graphs with a particular win condition, not about any game you can play on a table.

Check the win rule
Most wrong applications come from accidentally analyzing a misère game as normal play, or a partizan game as impartial.

With the ground rules set, the whole machine runs on one local operation.

mex and Grundy numbers

A position’s nimber is computed from the nimbers of its options using minimum excluded value (mex). Given the set of nimbers reachable in one move, the position’s nimber is the smallest nonnegative integer not in that set.

Formally, if a position $P$ has options with nimbers in the set $S(P)$, then its Grundy number is

$$g(P)=\mathrm{mex}(S(P)).$$

That single line encodes the idea that positions are classified by what they can move to. Terminal positions have no options, so $S(P)=\varnothing$ and $g(P)=\mathrm{mex}(\varnothing)=0$.

Explore how mex turns a set of option nimbers into the position’s nimber.

The reason mex is the right rule is that nimbers are constructed so every smaller nimber is reachable from a heap of size $k$, but $k$ itself is not. mex recreates that property for an arbitrary game graph.

Why sums combine by xor

For finite impartial normal-play games, nimbers add like Nim heaps. If positions $A$ and $B$ have nimbers $g(A)$ and $g(B)$, then the disjunctive sum has nimber

$$g(A+B)=g(A)\oplus g(B),$$

where $\oplus$ is bitwise xor.

This gives a complete win test.

Featured snippet version

A position in a sum of impartial normal-play games is losing if and only if the xor of the component nimbers is $0$. If the xor is nonzero, there is a winning move that changes exactly one component so the new xor becomes $0$.

In practice, you do not need to memorize proofs. You need to be able to read a winning move off the xor. If the current xor is $X\neq0$, pick a component nimber $g_i$ that has the highest set bit of $X$. Move in that component to some option nimber $g_i'$ with $g_i'\oplus(X\oplus g_i)=0$, which is the same as $g_i'=g_i\oplus X$. The theorem guarantees such an option exists when $g_i'$ is smaller than $g_i$ in the Nim sense created by mex.

Experiment with heaps and watch how xor predicts losing states and points to the move that makes xor zero.

Worked nimber computations on small games

Small games teach you what mex is really doing. The point is not the final table. The point is noticing how local move rules create the set of reachable nimbers.

Subtraction games

Positions are heap sizes $n$, moves subtract from a fixed set like $\{1,3,4\}$. The recurrence is

$$g(n)=\mathrm{mex}(\{g(n-s)\mid s\in S,\ n\ge s\}).$$

Compute upward from $g(0)=0$ and you will often see eventual periodicity in the sequence of nimbers.

Split games and Kayles-like moves

When a move can split a component into two components, the option nimber becomes an xor of the two resulting subpositions. That is where people slip. The move is still one move in one component, but the resulting position is a sum.

So an option might look like

$$g(\text{after move})=g(\text{left})\oplus g(\text{right}).$$

Explore a small position graph and reveal nimbers layer by layer as the move rules change.

A good habit is to write the option nimbers explicitly before taking mex. If you skip that step, you will start taking mex of positions instead of mex of numbers, and the whole interpretation collapses.

Write the set
Before mex, list the nimbers of all immediate options. If a move splits, compute the xor of the parts first.

Not every game you meet satisfies the tidy assumptions that made all of this work.

Failure modes and edge cases to recognize fast

Sprague–Grundy analysis fails in recognizable ways. Spot them early and you save hours.

• Cycles create positions that do not have a well-defined Grundy number under the finite acyclic model.
• Misère play changes endgame behavior, so xor-to-zero is not the right global criterion.
• Partizan moves destroy impartiality, so nimbers are no longer the correct algebraic objects.
• Infinite play or draws require a different outcome model than win by last move.

Compare the standard setting to loopy, misère, and partizan variants to see exactly what must change in analysis.

If you are still in normal play but the graph has cycles, some positions can be winning for the next player, some for the previous player, and some can be draws. Grundy numbers alone cannot encode that richer outcome set.

A nimber workflow that scales

You do not need cleverness first. You need a repeatable pipeline.

Start with a clear state encoding, then build a table in increasing order of a measure that always decreases on moves. For heap-size games it is $n$. For row-and-pin games it is length. For composite shapes it might be total tokens.

When splits are possible, cache computed values so you can reuse them in option calculations. You are effectively doing dynamic programming on the game graph.

Two scaling tricks show up again and again:

• Detect periodicity by comparing blocks of computed nimbers once the move horizon is fully inside the table.
• Separate computation from play by precomputing nimbers for components, then using xor to analyze any sum instantly.

At that point, the hard part becomes choosing the right decomposition of a new game into components that behave independently.

From nimbers to strategy design

When you face a new impartial game, ask two questions before calculating anything.

First, what are the natural components. If moves never interact across regions, you have a disjunctive sum hiding in plain sight. If a move can merge regions, your decomposition is not stable and xor will not be a reliable shortcut until you redefine the state.

Second, what is the move vocabulary. Moves that only decrease a single size parameter usually lead to subtraction-like recurrences and periodic nimber sequences. Moves that split create xor inside the recurrence, which often produces richer patterns but still stays computable with memoization.

Pick one small position, compute its options, take mex, and repeat until you can see the structure. When the nimbers start repeating or the decomposition stabilizes, you are no longer solving a puzzle. You are designing a strategy.