Sprague–Grundy 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).

Experiment

You can use the interactive module to trace these calculations step-by-step.

1. Open the Sprague–Grundy Subtraction Games module.
2. Set the Moves control to "One three four".
3. Set the Heap control to "7".
4. Click Step repeatedly to observe the recursive calculation of Grundy values for heap sizes from 0 up to 7.
5. Notice how the diagram visualizes the dependencies (legal moves) and the reachable Grundy values (the set passed to the mex function).
6. 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.