A chess problem that turned out to be an octal game

Thomas Rayner Dawson was a chess problemist, and in 1934 he published a puzzle in Caissa’s Wild Roses: white pawns and black pawns on a board three ranks deep, each side obliged to capture when a capture is available, and whoever runs out of moves loses.

It is not a chess problem in any sense a chess player would recognise, and it is not about chess. Stripped of the board it is this: a row of counters; a move takes one counter and splits the remaining row into two rows; and a row of one may be taken outright.

In the notation the subject settled on decades later it is the octal game ·137.

What the octal code means #

An octal game is a game on heaps where a move takes some counters from one heap and may leave the remainder as zero, one, or two heaps. The code says which.

The code ·137 has three digits, one for each number of counters a move may take. Digit $d_k$ is read in binary: the 1-bit says a move taking $k$ counters may empty the heap, the 2-bit says it may leave one heap, the 4-bit says it may split the remainder into two.

• $d_1 = 1$: taking one counter is allowed only if it empties the heap.
• $d_2 = 3$ = 1 + 2: taking two may empty the heap, or leave one heap.
• $d_3 = 7$ = 1 + 2 + 4: taking three may do any of the three.

That is a compact and completely mechanical description of a rule, and the whole point of the notation is that it is mechanical: an octal code names a game and a program reads it directly.

What “eventually periodic” is hiding #

The result usually quoted about ·137 is that its Grundy sequence is eventually periodic with period 34. That is true and it is less than it sounds.

Computing the sequence to heap 600 and asking for a period finds one: period 34, starting at heap 52. So from heap 52 onward the values repeat with a cycle of 34, for ever, and the periodicity argument makes that a proof rather than an observation.

It is not the short proof a subtraction game gets, and the difference is the splitting move. In a subtraction game a value is a mex over the values one largest-move behind it, so a window that long settles everything after it. The digit 7 in ·137 sets the 4-bit, which lets a move take three counters and cut the remainder in two — and the value of a heap is then a mex over exclusive-ors of values arbitrarily far below it. Guy and Smith’s 1956 theorem covers that case with a longer window: the repeat must hold from the start of the period $s$ all the way to $2s + 2p + m$, where $p$ is the period and $m$ the number of digits in the code. For ·137 that is heap 175, and the certificate is a hundred and twenty-four values rather than three.

Below heap 52 the values are not a warm-up that settles down. Five of them are exceptions: heaps 14, 16, 31, 34 and 51, whose values differ from the value 34 places later. They will never agree, at any distance, because the periodic part has already begun and they are outside it.

So the sequence is not “irregular and then regular”. It is regular from 52, and five specific values below that are permanently out of step with the pattern.

The convention for counting exceptions matters and is not standard. An exception here is a heap $n$ below the period’s start where $g(n) \ne g(n + 34)$. Another reasonable definition counts every heap below the start, whether or not it happens to agree. A third counts the heaps carrying a value the periodic part never produces. Published lists differ, and quoting a number without the convention is quoting nothing, so the three are worth counting rather than describing.

That third count is the one worth having, because it says what an exception is not. A reader told that five heaps are exceptional may reasonably picture five stray values the periodic part has no room for. There are none: ·137 takes nine distinct values in six hundred heaps — 0, 1, 2, 3, 4, 5, 7, 8 and 9, with 6 never appearing at all — and every one of the nine that occurs below heap 52 occurs above it too. The exceptions are ordinary values sitting where the period would have put something else.

What the period costs to find, and what it buys #

Finding the period is a search, and it is worth being clear about what kind.

The values are computed in order — each one a mex over options already known — so reaching heap 600 costs the work of six hundred mex computations, each over a set whose size grows with the heap because of the splitting moves. Nothing about this is clever and nothing about it is optional: there is no way to compute the value of heap 500 without the four hundred and ninety-nine below it.

Then the search for a period is a second pass, and it is the cheap half: for each candidate start and each candidate length, check whether the window repeats. The certificate, once found, is short.

What it buys is the difference between linear and constant. Without a period, the value of a heap of a million counters costs a million mex computations. With one, it costs a division: reduce the index modulo 34, look up one of 34 numbers. That is the same transformation a closed form always makes, and it is the reason periodicity is the property people look for in these sequences rather than any other.

The surprise: the numbers are small and the game is not #

The largest Grundy value anywhere in the sequence computed here — six hundred heaps — is 9.

That is worth pausing on. A Grundy value of 9 means the heap is equivalent to a Nim heap of nine counters. So every position of Dawson’s chess, however long the row, is equivalent to a Nim position built from heaps of at most nine — and the game as a whole is a disjunctive sum of such rows.

A game with unbounded positions whose values live in a set of nine numbers is a strong compression, and it is the ordinary situation for octal games rather than a surprise about this one. What is genuinely surprising is the arrangement: the values do not increase with the heap, do not correlate with anything visible, and the sequence looks random until it repeats. Nothing in the first forty values suggests that a period of 34 is coming, and nothing in them suggests the values are bounded either. Both are facts obtained by computing far enough and then checking, and neither is visible in any stretch of the sequence short enough to read.

The neighbour that behaves almost identically #

Dawson’s chess has a close relative, and the pair make a point neither makes alone.

Dawson’s Kayles is the octal game ·07: a move takes two counters and may split the remainder, and — the difference — no move may take a whole heap of one. One bit of one digit separates the two codes.

Period 34 in both, from heap 52 and heap 53, and the same thirty-four values in the repeating block. That is more than a family resemblance, and the way to find out how much more is to stop comparing the two sequences at the same index and let a search find the offset that fits.

So the two are not two sequences that happen to agree about their period; they are one sequence read from two starting points, and the agreement about the period follows from that rather than standing beside it. A heap of $n$ counters in Dawson’s Kayles is worth what a heap of $n-1$ is worth in Dawson’s chess, which is a statement about the rules — take one or two and split, against take one and split or take two — and not about the sequences at all.

That is also why the pair is a poor guide to the general problem. Two codes this closely related are the easy case, and the family does not oblige. Kayles is the next code along and behaves completely differently.

Elsewhere in the same family, one bit is the difference between a sequence that settles at heap 71 and one that has never settled at all — ·007 and its neighbours have been computed to hundreds of thousands of heaps with nothing periodic appearing.

Why a problem column produced a research object #

The natural reading is that Dawson invented a game and the theory later explained it. That is not quite what happened, and the difference is the point of filing this essay here.

Dawson posed a puzzle: this position, who wins. A puzzle asks about one position, and the answer to a puzzle is a line of play. Dawson’s own answer was of that kind.

The object that the modern subject cares about is not the position but the family — every row length, all at once — and the family is what has a Grundy sequence. Nobody was asking about the family in 1934, because the machinery for it (Sprague and Grundy) was one year old, in Japanese, and unknown in England.

So the game arrived first and the question arrived second, which is the usual direction. What makes it worth recording is how thoroughly the second question buried the first: nobody now cites Dawson’s puzzle for the position he was asking about.

Set ·137 beside its neighbours and the striking thing is how little a code tells anybody. ·6 and ·106 and ·007 have had no period found in twelve hundred values; ·137, ·07 and ·77 settle. There is no feature of the digits that separates the two groups, which is the whole content of the open conjecture and the reason a survey of these games is a table of computations rather than a theory.

Reading a position, rather than a heap #

One thing the octal reduction throws away deserves recovering, because it is what makes the game playable rather than merely computable.

A position of Dawson’s chess is not a heap. It is a collection of rows, produced by the splitting moves, and the value of the position is the nim-sum of the rows’ values. So a row of 20 counters is worth some single number, and a position that has broken into rows of 7, 5 and 3 is worth the exclusive-or of three numbers, each looked up in the sequence.

That is the disjunctive sum doing its job, and it means the sequence at the top of this page is not a table of answers — it is the input to the answer for any actual position.

The last step of evaluating any octal position is therefore the nim-sum: the values of the parts, combined without carrying. The Grundy sequence supplies the numbers and Bouton’s criterion, thirty-three years older than Dawson’s puzzle, supplies the combination — so the only part of the calculation that needs this page is the lookup.

The consequence is a pleasant inversion. The hard computational object is the sequence for a single row, which has to be built up from the bottom; combining rows, which sounds like the harder problem, is free.

Where the model stops #

The period is proved; the exceptions are computed. The periodicity from heap 52 is a theorem, established by the window argument, and holds for every heap there will ever be. The claim that there are exactly five exceptions below it is a statement about a finite computation, and it is exactly as strong as that computation is correct.

The distinction is not pedantry. It is the same distinction as between a bound and an answer, and this site’s habit is to say which side of it each number falls on.

And the sequence’s boundedness is not proved here. That the values never exceed 9 is an observation over 600 heaps. For a game whose period is established it follows — the tail repeats, so it introduces nothing new — but that reasoning uses the period, and it is worth noticing that it does, because for the octal games with no period found the same observation supports nothing at all.

What the picture cannot show #

The strip and the sequence figures draw the values and cannot draw the moves, and that hides where the difficulty of an octal game comes from.

In a subtraction game the value of a heap depends on a fixed number of values below it, which is why its periodicity argument is short. In an octal game a move may split a heap, and the value of the split is the nim-sum of the two parts — so heap $n$’s value depends on the exclusive-or of pairs of values from anywhere below it.

That is the whole reason octal periodicity is hard, and no picture of a value sequence contains it. The values are the output; the dependency structure is what makes them hard to predict, and it is invisible in every figure on this page.

The convention, named #

Everything here is normal play: the player who cannot move loses. Dawson’s original puzzle has the same convention, since a player with no capture available has lost.

It is worth saying because octal games are one of the places where the misère version is not a variation but a different subject. The Grundy value of a heap under normal play is one number; under misère play a heap does not have a value at all in the sense that composes, and the analysis of misère Dawson’s chess is a much larger object than a sequence of small integers.

So the compact sequence at the top of this page, and the period, and the certificate, are all statements about one convention, and none of them survives the change.

Who found what, and when #

Dawson’s puzzle is 1934. The identification with an octal game and the computation of the sequence belong to the survey work of the 1950s — Guy and Smith, who gave the octal notation its modern form and computed sequences by hand for dozens of codes.

The period of ·137 was found in that period, by hand, and has been confirmed by every computation since. There is something worth respecting in that: fifty-two values of a sequence with no visible pattern, computed by a person, far enough to find a repeat of length 34 and to check it.

The pattern this essay is an instance of #

Three things happened in order and it is worth naming the pattern, because it recurs.

A question was posed in one language. Dawson asked about pawns, in a chess column, for an audience of chess problemists.

It was answered in another. The answer — a Grundy sequence, a period, a certificate — is stated in terms none of the original audience had, about an object (the whole family of row lengths) nobody had asked about.

And the translation lost the original question. Dawson’s actual puzzle, the specific position he set, is not what anybody now means by Dawson’s chess.

The same shape is all over this subject. Wythoff’s game was a stone-picking pastime before it was a theorem about Beatty sequences. Sprouts was invented over tea and is now a search problem. And Nim was a bar game.

The reason to record it is that it cuts the other way too: a game that looks like a toy is not evidence that the question about it is a toy, and several of the hardest open problems in the subject are about objects somebody made up for fun in an afternoon.

What a code does not settle #

The octal notation is complete — the code determines the game exactly — and it is almost useless as a predictor.

Two codes differing in one bit can produce sequences that settle at different heaps with different periods and different numbers of exceptions, or one that settles and one that does not. There is no known map from a code to any property of its sequence, and finding one would settle the periodicity conjecture as a side effect.

So the notation’s value is that it makes the family enumerable and the games mechanically specifiable. It carries no analysis, and everything about a code’s behaviour has to be computed.

What it takes for a real game to have a code #

Dawson’s chess having an octal code is the family’s best advertisement and it is worth asking what had to be true of the game for it to work, because the conditions are restrictive and that is why there is only one such advertisement.

The position has to be a multiset of independent pieces. An octal code describes what may be done to one heap, and a code names a game only if a position is a collection of heaps that do not interact. A chess-like game on a board is not that in general; Dawson’s is, because the pawns’ interactions confine themselves to a row and a row decomposes into runs.

A move has to be describable by how much it removes. The code’s digit $d_k$ says what may happen when exactly $k$ counters go, so the rule has to be a function of the amount taken and nothing else — not of which counters, not of where in the heap, not of what has happened before.

And the splitting has to be into at most two, or the code is hexadecimal. A move that leaves three heaps needs the fourth bit, which is why the wider family exists and why it corresponds to fewer real games.

So the correspondence is rarer than the notation’s coverage suggests. Every finite string of digits names a game; almost none of those games is one anybody plays, and the traffic in the useful direction — a played game turning out to have a code — has essentially one example. That asymmetry is worth carrying whenever the octal family is described as a catalogue of games: it is a catalogue of rules, and the games are somewhere else.

A note on the name #

“Dawson’s chess” is a poor name for it and has stuck. It is not chess, it is not a chess variant, and Dawson posed it as a problem rather than as a game. The name records where it was published rather than what it is, which is common enough in this subject that the octal codes exist partly as a corrective: ·137 says what the rules are and needs no provenance.

Where the ladder goes next #

This anchor’s first rung is the game and the exceptions its quoted result loses. The direction from here is toward the codes that have not settled — ·007 and its neighbours — where the same computation run vastly further finds nothing, and where the conjecture that it must eventually is seventy years old and open.