Grundy sequences, and where they stop being predictable

Sprague–Grundy says every impartial position is a Nim heap and gives a recursion for finding which one. For a game played on heaps, running that recursion over every heap size produces a sequence — the Grundy value of a heap of zero, of one, of two, and onwards.

That sequence is the complete solution of the game. It is also, in several well-studied cases, an object nobody understands.

The simplest sequences #

Start with subtraction games, where a move removes a number of counters from the chosen set $S$.

For $S = \{1\}$, the sequence is $0, 1, 0, 1, 0, 1, \ldots$ — period two, and the game is just parity. For $S = \{1, 2\}$, it is $0, 1, 2, 0, 1, 2, \ldots$ — period three, and the Grundy value is the heap size modulo three. In general, for $S = \{1, 2, \ldots, k\}$ the sequence is the heap size modulo $k+1$, which makes the game a thin disguise for Nim with a move limit.

These are the cases where the sequence can be predicted without computing it. They are also, essentially, all of them.

The moment prediction fails #

Change the set to $\{1, 3, 4\}$ and the sequence becomes

$$0, 1, 0, 1, 2, 3, 2, \; 0, 1, 0, 1, 2, 3, 2, \; \ldots$$

Period seven. The seven is not the sum of anything obvious, not one more than the largest element, and not derivable from the set by any rule anybody has found. It is a fact discovered by running the recursion.

Try $\{1, 2, 4\}$ and the period is three, with sequence $0, 1, 2, 0, 1, 2, \ldots$ — the element four is never useful, because subtracting four and subtracting one land on the same residue. Try $\{2, 3\}$ and the period is five: $0, 0, 1, 1, 2, 0, 0, 1, 1, 2, \ldots$, with the two leading zeros reflecting that heaps of nought and one are both dead.

Three sets of similar shape, three unrelated periods. There is no formula, and the reason is not that nobody has looked.

Why periodicity is the whole question #

If the sequence is eventually periodic, the game is solved in a strong sense: a finite table plus a modular arithmetic answers any question about any heap size, however large.

If it is not, the only known way to evaluate a heap of size $n$ is to compute every value below $n$, which is linear in $n$ and therefore exponential in the size of the input, since a heap size is written down in $\log n$ digits. The difference between a periodic sequence and an aperiodic one is the difference between a solved game and one that can only be simulated.

So “is this sequence eventually periodic” is not an aesthetic question about patterns. It is the question of whether the game has a solution at all in the usual sense.

The one theorem there is #

For finite subtraction sets, the answer is known and it is good news.

If $S$ is finite with largest element $m$, the Grundy sequence is eventually periodic. The proof is a counting argument: the Grundy value of a heap depends only on the previous $m$ values, and no Grundy value can exceed $|S|$, so there are at most $(|S|+1)^m$ possible windows of $m$ consecutive values. The sequence of windows must eventually repeat, and once a window repeats the entire subsequent sequence repeats.

That is a pigeonhole argument, and it is worth noticing what it does and does not give. It gives eventual periodicity, guaranteed. It gives a bound on when periodicity starts and how long the period is — but the bound is $(|S|+1)^m$, which for a set with largest element twenty is astronomically larger than any period ever observed. The theorem says the sequence repeats and is useless for predicting when.

Every actual period is found by computing until it appears.

Octal games, where it gets harder #

Subtraction games are the easy family because a move always leaves one heap. Loosen that and a move may split a heap in two, and the analysis changes character.

The standard notation for these is an octal code. In the game $\mathbf{0.07}$, the digit seven at position two means: from a heap, remove exactly two counters, and the remainder may be left whole, left as two non-empty heaps, or — the third bit — removed entirely. Kayles is $\mathbf{0.77}$; Dawson’s chess is $\mathbf{0.137}$.

Splitting means positions are sums, and a heap’s value is the mex over options that are themselves nim-sums of two heaps’ values. The recursion is still mechanical and the sequences become dramatically more erratic.

Kayles, $\mathbf{0.77}$, has period twelve — but only from heap size seventy-one onward, with an irregular prefix of seventy-one terms containing values as large as eight. Nothing about the rules suggests seventy-one. Dawson’s chess has period thirty-four, starting at heap size fifty-two, with a handful of exceptional values scattered through the prefix.

Reading a strip #

The strips on this page repay a slower look, because they contain more than the period.

The values that appear are bounded by the number of moves available, and usually well below it. For $\{1,3,4\}$ the values never exceed three, though the set has three elements and a heap can have many options. Large Grundy values are rare, and a game whose sequence reaches eight — as Kayles does — is unusual enough to be remarked on in the literature.

The zeros are the losing positions, and their spacing is the practical content of the sequence. For $\{1,3,4\}$ the zeros are at $0, 2, 7, 9, 14, 16, \ldots$: a pattern of gaps two and five alternating. A player who memorised only that would play the single-heap game perfectly and would still be helpless at a two-heap position, which needs the whole sequence and an exclusive-or.

The prefix, where there is one, is the part that resists explanation. For these small subtraction sets there is no prefix — periodicity begins at heap zero. For Kayles the prefix is seventy-one terms and contains the only appearances of the values six, seven and eight in the entire game. Those exceptional values are genuinely exceptional: they occur once each, early, and never again in an infinite sequence.

What a period does not buy #

Suppose the period is known. What follows?

The one-heap game is solved: reduce the heap size modulo the period, look up the value, and if it is nonzero find the move that reaches zero. That is genuinely a solution and it is fast.

The many-heap game is also solved, by exclusive-or of the components, and this is where the periodicity pays off. Ten heaps of arbitrary size collapse to ten table lookups and nine exclusive-ors.

What is not solved is anything about the structure of play. The sequence says which positions are lost; it does not say how long the game will run, whether the winner has one winning move or many, or how badly a mistake costs. A player handed the sequence plays perfectly and understands nothing, which is a recurring theme — a value is not a strategy, and a table of values is not an account of a game.

Nor does a period explain itself. Knowing that $\{1,3,4\}$ has period seven does not indicate why, and does not help with $\{1,3,5\}$. Each set is its own computation.

Splitting, and why it changes everything #

The gap between subtraction games and octal games deserves isolating, because it is where a tractable family becomes an open problem.

In a subtraction game, a move takes a heap of size $n$ to a heap of size $n - s$. One heap in, one heap out, so the recursion at $n$ looks back at a fixed window of $|S|$ earlier values, and the window has bounded width. That bounded width is exactly what the pigeonhole proof needs.

In an octal game with splitting, a move can take a heap of size $n$ to two heaps of sizes $a$ and $b$ with $a + b = n - s$. The recursion at $n$ now looks at $\mathcal{G}(a) \oplus \mathcal{G}(b)$ over every such pair — a set of options whose size grows with $n$, drawing on the entire earlier sequence rather than a fixed window.

There is no bounded state to apply pigeonhole to. The proof does not merely become harder; the object it was about no longer exists. That single structural change is the whole reason Guy’s conjecture is a conjecture, and it is why a game as simple as splitting a heap into two unequal parts has resisted since 1939.

The open problems #

Here is the part that is genuinely unresolved.

Is every finite octal game eventually periodic? Guy conjectured yes in the 1950s. It is open. No finite octal game has been proved aperiodic, and none has been proved to have no period.

$\mathbf{0.007}$ — Grundy values computed past $2^{40}$ heap sizes, no period found. Every known term has been computed and the sequence has not repeated.

$\mathbf{0.106}$ — the same story, and it is the smallest code for which nobody knows.

Grundy’s game, where a move splits a heap into two unequal heaps: values computed past $2^{35}$, no period. This one has the simplest rule statement of any unsolved impartial game, and it can be explained to a child in one sentence.

These are not deep-looking problems. The rules fit on a line, the recursion is a first exercise in dynamic programming, and after seventy years of computation and several people’s careers there is no answer. The recursion is trivially computable and the pattern in what it computes is not.

That gap — between a value that can be computed and a value that can be predicted — is the characteristic difficulty of this corner of the subject and a preview of where the theory runs out generally.

What the solver computed #

Every strip on this page was generated by running the mex recursion, not by transcribing a published table. subtractionGrundy(set, upTo) in lib/games.js computes the sequence directly from the rules; findPeriod looks for the smallest $p$ and offset $k$ such that $\mathcal{G}(n+p) = \mathcal{G}(n)$ for every $n \ge k$ within the computed range, and reports both.

The caption on each figure quotes what the search found, and where no period is found within the range the figure says so rather than claiming one. That distinction matters more here than anywhere else on this site: a period found within twenty-four terms is a period observed, not a period proved, and for the octal games above the difference has consumed decades.

The values are cross-checked. For each heap size drawn, lib/cgt.js independently builds the position as a game, reduces it to canonical form, and confirms the canonical form is the nimber the mex recursion predicted. Two routes, same answer, or the build fails.

For $S = \{1, 3, 4\}$ the search reports period seven starting at offset zero. For $S = \{2, 3\}$, period five at offset zero. For $S = \{1, 2, 3\}$, period four at offset zero. Those are the numbers in the captions, and they came out of the code.

Sparse and infinite sets #

Two variations are worth mentioning because they break the theorem in different ways.

Infinite subtraction sets. If $S$ is all the powers of two, the sequence is $0,1,2,0,1,2,\ldots$ with period three — periodic despite the set being infinite, because only the low bits ever matter. If $S$ is all the primes, the sequence is far less regular and the pigeonhole proof does not apply at all, since there is no largest element to bound the window.

All-but-finitely-many sets. If $S$ is every positive integer except one, the game is nearly Nim and the sequence is nearly the identity, with a defect where the missing move would have been. These are the cases where the sequence can be reasoned about rather than computed, and they are a small island.

The general picture is that periodicity is common, proved only in the easiest family, and conjectured everywhere else on the strength of computation.

Who found it, and when #

Grundy computed sequences by hand in the 1930s. Richard Guy and Cedric Smith systematised the octal notation and the periodicity questions in The G-values of various games, published in 1956 — a paper that is essentially the founding document of this area, and that already contains the conjecture and the unsolved cases.

Guy returned to the problem repeatedly for the next fifty years and offered a prize for a decision on $\mathbf{0.007}$. Achim Flammenkamp maintained the computational record from the 1990s, pushing the search bounds for the unsolved codes by many orders of magnitude and finding nothing.

The list of unsolved octal games in Winning Ways is short and has barely changed since 1982. What has changed is the amount of computation thrown at it, by a factor of billions, with no effect on the answer.

Where the model stops #

Heap games only. Subtraction and octal games are played on heaps, which is what makes a one-dimensional sequence the right object. Impartial games on graphs or boards have no such indexing and no such sequences.

Impartial only, as the theorem requires. Partizan games have no Grundy values, and their analogue — the sequence of canonical forms along a family — is far less tractable.

Normal play only. Under misère play these sequences do not describe the game, and the misère analysis of even simple octal games is disproportionately harder.

Observed periods are not proved periods. The figures show what a finite search found. For finite subtraction sets a proof exists, so the observation is confirmation. For octal games no proof exists, and a figure that claimed one would be overstating what the code did.

The ladder from here #

Nearby rungs: the octal notation properly developed, digit by digit; Kayles worked all the way through, prefix and period; Dawson’s chess and why a chess variant is an octal game at all; Wythoff’s game, which is impartial and whose losing positions involve the golden ratio rather than binary arithmetic; and the sparse-set variants where periodicity can be proved by a different argument.

Further out, the connection to complexity: the periodicity question is exactly the question of whether these games are solvable in polynomial time in the input length, and the answer being unknown for a game with a one-sentence rule is the most concrete illustration this subject offers of a theory that computes everything and predicts nothing.