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.

What the sweep runs on each code is the mex rule and nothing else: a heap is worth the smallest non-negative integer that is not the value of one of its options. The code decides what the options are, and in a take-and-break game they include the nim-sums of split pairs as well as the smaller heaps. The rule is the same for every member of the family, which is what makes an enumeration meaningful rather than a list of unrelated calculations.

Most of what the sweep returns is familiar. The two-digit code $\cdot 33$ lets a token be taken singly or in pairs and never permits a split, so it is the subtraction game “take one or two” wearing a different name.

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.

The sweep turns up something else about $\cdot 137$, and it is a fact about the names rather than about the game. The code $\cdot 07$ forbids taking one at all; its only move is to take two, and then end the heap, leave one heap, or split the rest in two. That is a different rule table by every reading of the digits. Its Grundy sequence is Dawson’s chess’s, moved one place to the right.

That is worth more than a curiosity, because it is the first thing the notation costs. An integer names a rule table, not a game, and nothing in the numeral says whether two tables produce the same answers. A sweep of the 512 three-digit codes is a sweep of 512 names; how many distinct games sit underneath them is a further question, and the notation gives no way of asking it.

One bit of the code decides which family a game is in #

The notation’s real payoff is not that games can be counted through. It is that the thing making them hard is a single bit, and the code puts it where a reader can see it.

Each digit is three bits: 1 for finishing the heap, 2 for leaving one heap, 4 for splitting into two. Only the third does anything to the theory.

A code with no digit of 4 or more is a subtraction game. Without the splitting bit no move ever produces two heaps, so a heap’s value depends on a fixed window of the values below it, the pigeonhole applies, and eventual periodicity is a theorem.

A code with a 4 bit anywhere is a conjecture. Splitting makes the option set include nim-sums of pairs drawn from anywhere below, so there is no window of fixed width to pigeonhole and no bound on how large the values can get.

That is the whole boundary between what is proved and what has been computed for seventy years, and it is one bit per digit.

Which says how much of the family is settled #

Counting that is immediate and the numbers are worth having, because they say something the prose version does not.

A digit is one of eight values, and four of them — $0, 1, 2, 3$ — have the splitting bit clear. So among the $8^3 = 512$ codes of three digits, exactly $4^3 = 64$ are subtraction games and settled by theorem. One code in eight.

And the share is not constant. For codes of $n$ digits it is $4^n / 8^n = 2^{-n}$: half of the one-digit codes, a quarter of the two-digit ones, an eighth at three digits, a sixteenth at four. The proved fraction halves with every digit added, because each new digit is another chance for the splitting bit to be set.

So the honest summary of the family is not that a handful of awkward codes resist. It is that the theorem covers a share of the family that goes to nothing as the codes lengthen, and everything else is evidence — nearly every computed sequence repeats, and nobody has an argument that covers even one code with a 4 in it.

And the notation is what makes that sayable. A family described in prose has no denominator: “some take-and-break games are settled” is a sentence with no count in it. A family whose members are digit strings has $8^n$ of them, a proved subset of $4^n$, and a ratio that can be written down and watched shrink. That is the naming scheme earning its place — not by making the games countable, but by making the boundary between the proved and the open into an arithmetic property of the name.

Where the difficulty enters #

The contrast is sharpest when two codes differ by a single bit, and the sweep supplies the pair. Take $\cdot 33$ from earlier in this essay — take one or two, never split — and set the splitting bit on its second digit. The code becomes $\cdot 37$, and the only rule that has changed is that a take of two may now cut the remainder in two instead of leaving it whole.

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 the whole of what the pigeonhole proof consumes. $\cdot 33$ has it and $\cdot 37$ does not, and the difference between them is one bit in one digit.

The growth is the part worth staring at. $\cdot 33$’s alphabet is three symbols and stays three symbols for ever. $\cdot 37$’s largest value is 8 by heap 100, 17 by heap 500, 32 by heap 1,000 and 64 by heap 2,000 — doubling as the range doubles, in a game whose rule fits in a line. Nothing in the code separates the two beyond the bit, and nothing in the two dozen values a strip can hold separates them either.

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, and the only take is three — after which the remainder may be finished, left whole, or cut in two, since the digit is a 7 and carries all three bits. 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, where a sequence can repeat with a constant added rather than repeat. 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.