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. 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.

Every entry in either sequence is a single mex over the values of the options, which is the operation the theorem licenses and the only one these strips ever perform. The difficulty is not in any one of them. It is in how many are needed before the answer starts to repeat, and in the fact that nothing in the rule says how many that will be — which is a thing a strip can be drawn to demonstrate against itself.

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 $\{1,3,4\}$, $\{1,2,3\}$ and $\{2,3\}$ there is none — periodicity begins at heap zero — and three sets in a row behaving that way invite the reading that a subtraction game simply has no prefix. It is not true, and one more element is enough to break it.

Kayles’ prefix is seventy-one terms, and it is where the rare values live — though not in the way that phrase usually means. The value five occurs exactly once in the entire game, at a heap of twenty-eight. Six occurs four times, at eleven, twenty-two, thirty-four and seventy, and never again. Seven and eight are not exceptional at all: the repeating block is 7, 4, 1, 2, 8, 1, 4, 7, 2, 1, 8, 2, so each of them arrives twice in every period for ever. What the prefix actually contains is the fourteen heaps whose value differs from the periodic continuation, and they are scattered — 0, 3, 6, 9, 11, 15, 18, 21, 22, 28, 34, 39, 57, 70 — with the last of them one heap short of where the period starts.

One more thing is visible in Kayles and in nothing else on this page. Its only zero is the empty heap. Every positive heap of a single Kayles row is a win for whoever moves, so the sequence’s practical content is entirely in the sums: a player facing one row has nothing to decide and a player facing three has the whole problem.

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.

What arrives in place of the window is the exclusive-or. A split leaves two heaps, two heaps are an independent sum, and the option’s value is therefore $\mathcal{G}(a) \oplus \mathcal{G}(b)$ — so a single unusual value early in the sequence reaches forward into arbitrarily distant options rather than washing out of a fixed window.

It does not follow that every splitting game is hard, and assuming it would be the wrong lesson. Two of them have answers as short as anything in the subtraction family.

So splitting is not what makes a game hard; it is what removes the argument that a game must be easy. The three sequences above cost the same to compute and differ only in whether the answer has a short description, and no property of the rule table announces which of the three a new code will turn out to be.

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. One routine turns a rule — a subtraction set, or an octal code — into a sequence of values by taking a mex at each heap in turn. A second looks for the smallest period $p$ and offset $k$ such that $\mathcal{G}(n+p) = \mathcal{G}(n)$ for every $n \ge k$ in the range computed, and reports both.

The second routine has never been told the rule. It is handed a list of integers and nothing else, so it cannot be talked into the period the rule “ought” to have, and it has no way of preferring a short answer to a long one. That is what makes the annotation under each strip a finding rather than a restatement of the caption above it.

It is also why the range is stated. Each strip searches two thousand values and draws twenty-five of them, and the caption quotes the range because a period found within twenty-four terms is a period observed, not a period proved. For the octal games above, the difference between those two words has consumed decades.

Where a claim is stronger than “no disagreement was found”, it is checked against a second computation. The last figure is the case: Lasker’s Nim has a four-clause closed form on the heap size modulo four, and the figure runs the mex loop and the formula against each other on every heap up to two thousand rather than displaying the formula and inviting belief.

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. For $S = \{2, 4, 7\}$, period three starting at offset eight — the one set on this page whose period does not begin at the empty heap. 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.

What a sequence is evidence about #

A Grundy sequence is a strip of small numbers and it invites being read as a picture, so it is worth saying what a reader is entitled to conclude from looking at one.

A period seen is not a period. A repetition over a window is a repetition over that window, and the whole content of a period is a proof is that a checked window of the right width is a theorem while an observed one is not. The width is not decorative: it is the reach of the move rule, and one value short of it the induction has nothing to stand on.

A period not seen is not the absence of one. A search over periods up to some length, in a window of some size, has looked at what it looked at. The famous open cases in this family are famous because enormous windows have been searched and neither answer has arrived.

And a sequence that never repeats may still be settled. A period with a constant added is a completely solved game whose values climb for ever and use infinitely many symbols, so the alphabet keeps growing proves non-periodicity and says nothing about whether the game is understood.

So the three readings a strip invites — it repeats, it does not repeat, it is a mess — are three different claims with three different evidential standards, and only the first can ever be settled by a finite picture. That is an unusual situation for a figure to be in, and it is why every strip on this site prints how many values were examined rather than merely showing them.

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.

Where the ladder goes next #

grundy-sequences has two rungs to here: what a Grundy sequence is, and what its shape tells a reader.

The rung above changes what is being enumerated, and it is the change that made the whole subject searchable. Octal games compresses a take-and-break rule into a string of digits, so which game becomes something a program can count through rather than something a person has to invent. The family was swept that way in 1956, and the games nobody can solve were found by sweeping it rather than by anybody choosing them.

That is worth reading as a fact about method as much as about games. A sequence is an object to stare at; a rule table is an object to enumerate. Turning the first into the second is what converts look at this sequence and see whether it repeats into sweep every rule and report which repeat, and every open problem in the family — the conjecture that all of them settle, the code that has resisted billions of terms — is a question that could only be posed once the family had a coordinate system.

The other direction is the one that stays open. A sequence’s shape is a description of one game, and the two rungs above this one look for classes: which rules give a period, which give a period with a constant added, which give nothing anybody can find. None of those questions has an answer stated in the digits, and the reason is the standing complaint of this family — Kayles is $\cdot 77$ and has no formula, Lasker’s Nim has one, and nothing about the digits says which is which.