Sprague–Grundy Subtraction Games
Use mex values to classify subtraction positions and find winning moves.
By Riano · Published · Updated · Report a correction
Sprague–Grundy Theorem in Subtraction Games
The Sprague–Grundy theorem classifies finite, impartial games played under normal play convention. A game is impartial if the available moves from any position are exactly the same for both players, and normal play means the last player to move wins (or equivalently, a player facing a position with no legal moves loses).
Concept Overview
The theorem states that every position in such a game is equivalent to a single-heap game of Nim of a certain size. This size is called the Grundy value or nim-value of the position. It is calculated recursively using the minimum excluded value (mex) of the Grundy values of all positions reachable in one move. If a position has a Grundy value of 0, it is a losing position (P-position) for the current player. If it has a positive Grundy value, it is a winning position (N-position), meaning there is at least one move to a position with a Grundy value of 0. When considering sums of independent games, the total Grundy value is the bitwise XOR sum of the individual games' Grundy values.
Worked Example
Consider a subtraction game where a player can remove either 1, 3, or 4 tokens from a single heap. Let's calculate the Grundy values g(n) for n = 0 to 7.
g(0) = mex({}) = 0 (Terminal position, player to move loses)
g(1) = mex({g(0)}) = mex({0}) = 1
g(2) = mex({g(1)}) = mex({1}) = 0
g(3) = mex({g(2), g(0)}) = mex({0, 0}) = 1
g(4) = mex({g(3), g(1), g(0)}) = mex({1, 1, 0}) = 2
g(5) = mex({g(4), g(2), g(1)}) = mex({2, 0, 1}) = 3
g(6) = mex({g(5), g(3), g(2)}) = mex({3, 1, 0}) = 2
g(7) = mex({g(6), g(4), g(3)}) = mex({2, 2, 1}) = 0For a heap of size 7, we expect the calculated result to be g(7) = 0. Therefore, a heap of 7 is a losing position. No matter what move the current player makes (removing 1, 3, or 4), they will leave a heap of size 6, 4, or 3, which have Grundy values of 2, 2, and 1 respectively—all winning positions for the opponent. The final calculated expected result is 0.
Experiment
You can use the interactive module to trace these calculations step-by-step.
- Open the Sprague–Grundy Subtraction Games module.
- Set the Moves control to "One three four".
- Set the Heap control to "7".
- Click Step repeatedly to observe the recursive calculation of Grundy values for heap sizes from 0 up to 7.
- Notice how the diagram visualizes the dependencies (legal moves) and the reachable Grundy values (the set passed to the mex function).
- At the final step, observe the Outcome and Winning removals. Because g(7) = 0, it confirms it's a losing position with no winning moves available.
Limitations
The Sprague–Grundy theorem specifically applies to finite, impartial games under the normal play convention. It does not directly apply to misère play (where the last player to move loses), although some extensions (like Conway's Genus theory) exist. Furthermore, this module analyzes a single heap. For a game consisting of multiple independent heaps, the overall Grundy value is found by computing the bitwise XOR sum of the individual heaps' Grundy values. This module strictly calculates the values for a single heap rather than being a generalized solver for sums of arbitrary games. Finally, games must be acyclic (no infinite loops or repetitions) for the Grundy values to be well-defined as finite integers in this manner.
References
Thomas S. Ferguson's notes on impartial games and the Sprague-Grundy theorem provide comprehensive proofs and rigorous definitions for the computation of Grundy values, the role of the mex function, and the application to various nim-like subtraction games.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Sprague–Grundy Subtraction Games module.
Try Sprague–Grundy Subtraction Games on Riano →