Naming a game with a number

A subtraction game is specified by a set: from a heap of any size, remove one of these amounts. That is enough to produce Grundy sequences with periods nobody would guess, and it is also a very small corner of what a heap game can be.

Widen it slightly. Allow a move to split what is left into two heaps as well as leaving one, and allow the rule to depend on how much was taken. The result is a family large enough that its members need names, and small enough that the names can be integers.

The code #

A move in a take-and-break game does two things: it removes some tokens from one heap, and it leaves behind either nothing, or one heap, or two.

Number the possibilities. Taking exactly $k$ tokens and leaving nothing is possible only when the heap had exactly $k$ in it; call that option 1. Taking $k$ and leaving the remainder as a single heap is option 2. Taking $k$ and cutting the remainder into two non-empty heaps is option 4. Any combination of the three is a legal rule, and the sum of the ones allowed is a digit between 0 and 7.

Write one digit for each $k$, in order, and the whole game is a numeral: $d_1 d_2 d_3 \ldots$, conventionally with a point after the first digit, so the game is ·137 or ·6 or ·007.

The point is not decoration and the digits are not a number in any arithmetic sense. They are a table, laid out so that the table can be indexed by an integer.

Nim, in this notation, is $\cdot 333\ldots$ — every digit a 3, because from a heap of $n$ any $k$ may be taken, finishing the heap when $k = n$ and leaving one heap when $k < n$.

Two things about that strip are worth noticing before anything else. The first is that the value of a heap of $n$ is $n$, which is the Sprague–Grundy theorem’s simplest instance and the reason Nim is the yardstick. The second is that the code had to be written out to twenty-eight digits to say so.

A code is a finite string, so the game it names always has a largest legal take. Nim proper is the limit of an infinite code, and every finite prefix of it is a bounded Nim — take at most twenty-eight — which is a different game with a different, periodic answer. Where a figure on this page shows Nim as an octal game, the code is long enough for the heaps drawn and no longer.

What the notation is for #

The obvious objection to any naming scheme is that it does not do anything. This one does, and the reason is that an integer can be counted through.

The rules of a take-and-break game are exactly a digit string, so every such game with takes up to three is one of $8^3 = 512$ possibilities, and every one with takes up to four is one of $4{,}096$. A person can write a program that solves all of them, look at the results together, and notice which ones behave differently from the rest. That is not available for a family whose members are described in prose.

Richard Guy and Cedric Smith introduced the notation in 1956 for exactly this reason, and what came out of the sweep is the shape of the whole subject: nearly every code produces a Grundy sequence that eventually repeats, and a handful do not — or at least, have not yet.

Splitting is what makes the family interesting rather than a relabelling of subtraction games. When a move cuts a heap into two, the position becomes a sum, and the value of the sum is the nim-sum of the parts. So the mex is taken over a set that includes exclusive-ors of earlier values, and those propagate irregularly in a way that plain subtraction never does.

A sequence that repeats #

Dawson’s chess is the standard example, and it arrives from an unlikely direction.

Thomas Rayner Dawson published a chess problem in 1934: pawns on the third and fifth ranks, capturing compulsory, the player unable to move loses. Reduced to its combinatorial skeleton it becomes a heap game with code $\cdot 137$ — take one and end the heap, take two and leave one heap or nothing, take three and do anything at all.

The sequence settles into a period of 34 starting from a heap of 52, and stays there through every value computed. That is worth being precise about, because a strip that shows twenty-six values and announces a period of 34 has not shown anything: the period was searched for in two thousand values, not in the two dozen drawn.

Searching only the visible range is a specific and easy mistake. A short window of any sequence has periods in it that are artefacts of where the window stopped. The search here is run over a sequence long enough that a coincidence would have to persist for sixty repetitions, and the figure prints how many values it looked at.

Where the difficulty enters #

It is worth seeing what the family looks like without the splitting bit, because the contrast is the whole argument for why octal games are hard.

A subtraction game’s value at $n$ depends on a fixed window of earlier values, and nothing else. That is a strong structural constraint and it is visible in the picture: the strip settles into a repeat within a few heaps and stays there.

Add the splitting bit and the window argument collapses. The value at $n$ now depends on exclusive-ors of pairs drawn from everything below it, and no bounded amount of recent history determines what comes next. Every difficulty in this essay traces to that one digit.

The conjecture, and the games that resist it #

Every subtraction game is eventually periodic, and that is a theorem rather than an observation: with a largest take of $s$, the value of a heap is determined by the previous $s$ values, there are finitely many possible windows, and so a window must eventually recur and the sequence repeat from there.

The same argument does not work once splitting is allowed. A split makes the value of a heap depend on nim-sums of pairs of earlier values, and no bounded window determines what comes next. The pigeonhole argument has nothing to be applied to.

What replaces it is a conjecture — Guy’s — that every finite octal game is eventually periodic anyway. It has been checked against thousands of codes and holds in every case where anybody has been able to run the computation far enough, and it has never been proved.

The code $\cdot 007$ is the best-known of the resistant cases. Taking one or two is illegal; the only move is to take exactly three and split the remainder into two non-empty heaps. It is about as simple as a rule can get, and its Grundy sequence has been computed to a length that makes the figures on this page look like a rounding error, by people who made a project of it — and no period has appeared.

What the figure above claims is therefore carefully small. It does not say $\cdot 007$ is aperiodic; nobody knows that, and the conjecture says it is not. It says no period exists in the first two thousand values, which is a fact about a computation this page ran.

What the solver computed, and how #

Every strip on this page comes out of one loop, and it is worth writing down because its shape explains why the family is hard.

For a heap of $n$, the set of option values is assembled by running over each legal take $k$ and reading the digit $d_k$. Bit 1 contributes the value $0$, but only when $k = n$. Bit 2 contributes $g(n-k)$, the value already computed for the smaller heap. Bit 4 contributes $g(a) \oplus g(n-k-a)$ for every way of splitting the remainder into $a$ and $n-k-a$. The value $g(n)$ is the mex of everything collected.

The splits are the expensive part and the irregular part. Each one reaches back into two earlier values at once and combines them with exclusive-or, so a single unusual value early in the sequence propagates forward into arbitrarily distant sums rather than washing out.

The period search is separate and deliberately dumb: for each starting index and each candidate length, check whether the sequence agrees with itself shifted by that length, all the way to the end of what was computed. It returns the first pair that survives, and nothing else. It has no model of what a period ought to look like and cannot be talked into one.

Both halves are given something they must refuse. The period search is handed a sequence that repeats by construction and has to find the period; it is separately handed $\cdot 007$ and has to come back empty. A search that only ever said yes would make every strip on this page worthless.

Where the model stops #

A code is not a game with unbounded takes. Every claim here is about a finite digit string. Nim is not an octal game; each of its finite approximations is, and they are periodic for reasons Nim is not.

Eventual periodicity is not periodicity. Dawson’s chess is irregular for fifty-two heaps before it settles. A game can be arbitrarily badly behaved for arbitrarily long and still fall into a period afterwards, so a strip that looks disorderly proves nothing about what follows it.

The theory here is normal play only. Every value on this page is a Grundy value, and Grundy values describe misère play not at all. The same code under the misère convention needs a completely different apparatus, and that apparatus is not a sequence of integers.

Splitting is where the family gets its difficulty, and its usefulness. A game whose codes are all 1s and 2s is a subtraction game with extra steps. The moment a 4 appears the position stops being a single heap and becomes a sum, and that is both why the values are interesting and why nobody can prove anything about them.

The generalisation, and its price #

Octal codes extend. Hexadecimal codes allow a move to leave three heaps; “all-but” codes allow a move to take from every heap at once. Each extension names a wider family with a longer string, and each makes the sequences harder rather than easier.

There is a general lesson in the failure, and it is not about games. A naming scheme that turns a family into an enumeration is enormously productive — it produced the whole catalogue of small games and it found the exceptions — and it produces no proofs. Knowing that $\cdot 007$ has no period in the first billion values is knowing something about a billion integers. It is not knowing anything about the billion-and-first.

The subject has learned to live with that. The tables of octal games in Winning Ways mark the periodic ones with their periods and the resistant ones with a question mark, and the question marks have been there since 1982.

There is a second lesson, which is about what a hard case looks like. Nothing distinguishes $\cdot 007$ from its neighbours by inspection. It is not longer, not stranger, not built from any unusual ingredient — it is three digits, two of which are zero. Difficulty in this family is not visible in the description of a game, only in what happens when the rule is run, which is the same reason an exact evaluator runs out of room so quickly on positions that look small.

Who found it, and when #

Guy and Smith’s paper of 1956 introduced both the notation and the periodicity question, and it is a striking piece of work: it is essentially a survey of a family that did not exist as a family until the paper named it.

Dawson’s problem is from 1934 and the connection to the heap game was not made for two decades. That gap is typical of the subject. The games came first, as puzzles and problems, and the framework that showed them to be the same object came much later.

The large computations on the resistant codes are recent and are a different kind of work: hundreds of processor-years spent producing evidence for a conjecture that a single proof would settle permanently.

The ladder from here #

This anchor started with a Grundy sequence and a period, which is the first time a heap game does something a player would not have predicted. This rung generalises the game so far that the periodicity stops being provable, and finds that it seems to happen anyway.

Later rungs: the sparse-space games, where the values are mostly zero and the exceptions are what matter. Hexadecimal games and what a third heap costs. The reduction of a real board game to a code, which is where Dawson’s chess came from and where several others have since. And the misère side of the same codes, which is a different subject with the same rules.

The thing to carry forward is the shape of the evidence. Every figure on this page is a computation with its range printed on it, because the difference between “no period in two thousand values” and “no period” is the entire content of the open question.