Subtraction Game Solver
Change Nim so a player may only take one, two or three objects and the answer changes with it — now the losing heaps are the multiples of four. Change the allowed takes again and the pattern changes again, but it always settles into a repeating cycle. This computes the Grundy value of every heap size for whatever takes you allow, marks the heaps that lose, and finds the period, which is what lets a short table answer a heap of any size.
What this generator does
Builds the Grundy value of every heap size from zero upwards, each one being the smallest value not reachable in a single legal move, then reports the heaps whose value is zero and searches for the period the sequence falls into.
How to use this tool
- List the numbers of objects a player may take, separated by commas.
- Choose how far up the table should run.
- Press Solve.
- Read the losing heaps and the period the values fall into.
Understanding the controls
- Allowed takes
- How many objects a player may remove on a turn, separated by commas. Take 1, 2 or 3 is the classic game; take 1, 3 or 4 gives a much less obvious answer.
- Largest heap to tabulate
- How far the table runs. The period only becomes visible once the table is several times longer than the largest allowed take, so short tables report no period rather than guessing one.
Common use cases
- Working out the strategy for a house variant of the matchstick game
- Finding the losing positions for take one, two or three and its cousins
- Seeing the Sprague-Grundy theory work on a game you can play by hand
- Combining several heaps by exclusive-or of their Grundy values
- Checking that a game you invented is not trivially won by whoever starts
How this generator works
A heap's Grundy value is the smallest non-negative number that no legal move reaches — the mex of its options. A value of zero means every move leads somewhere winning for the opponent, so the heap is lost for the player to move. Because each value depends only on the ones below it and only as far down as the largest allowed take, the sequence must eventually repeat, and the tool searches for the shortest period that holds across the whole tail. Before display every value is recomputed from its own options, the losing heaps are re-derived from the zeroes, and any claimed period is re-checked at every heap in range.
Randomness and fairness
Nothing here is random. A set of allowed takes gives exactly one table of Grundy values, computed rather than sampled.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- This covers subtraction games where the same takes are allowed from every heap. Games where the options depend on the last move played are a different problem.
- A period is only reported when it holds across the whole tail of the table computed. A longer table can reveal a longer period the shorter one appeared to satisfy.
- Grundy values combine across heaps by exclusive-or, but that is a fact about the theory rather than something this table does for you.
- Only normal play is modelled, where taking the last object wins. Misere subtraction games have a separate and much messier theory.
Privacy and your data
The calculation runs in your browser and the takes you allow are never transmitted, stored or included in analytics.
Related generators
- Nim Position SolverSolves any Nim position outright, listing every winning move and confirming each one leaves a nim-sum of zero.
- Dice Probability CalculatorThe exact distribution of any dice total — every outcome counted, not simulated, with the odds of rolling at least a given number.
- First-Player PickerRandomly pick who goes first from a list of players.
- Turn-Order GeneratorGenerate a full random turn order for every player in a game.