The step nobody took for thirty-four years

Three complete solutions of three games were published between 1901 and 1910. The theory that makes them instances of one thing arrived in 1935 and 1939. The four earlier essays this one explain why each individual solution led nowhere; none of them says what the intervening step actually was.

It is one substitution.

The two sentences #

1901. A Nim position is lost for the player to move exactly when the heap sizes exclusive-or to nothing.

1935. A position of any impartial game is lost for the player to move exactly when the components’ Grundy values exclusive-or to nothing.

Read them side by side and the difference is one noun. The operation is the same exclusive-or, applied to the same list of numbers, compared with the same nought. What changed is where the numbers come from: in the first they are read off the position and in the second they are computed by a recursion.

That is not a rhetorical compression. It is what the sweep runs: the same three lines with h replaced by g[h], over eight games.

What each half was worth alone #

Over three heaps of at most six — 84 positions a game, 672 in all — the substituted criterion is exact on every game. The original is exact on Nim and on nothing else, and its accuracy elsewhere runs from 70 to 93 per cent.

So the exclusive-or, taken alone, is a complete theory of exactly one game. And it is the half Bouton had.

The other half is the mex rule — a position’s value is the least number not among its options’ values — and it is the half that assigns numbers to positions that are not Nim heaps. Nothing in the 1901 paper needs it, because a Nim heap’s value is its size and the substitution is invisible there. Bouton could not have noticed the quantity he was missing, because in his game it was not missing.

The sequences, read across #

The eight Grundy sequences are worth looking at as a set, because what they have in common is the whole reason the substitution was available.

Nim’s is the identity: 0, 1, 2, 3, 4, 5, 6. The subtraction game $\{1, 2, 3\}$ gives 0, 1, 2, 3, 0, 1, 2 — the identity for four terms and then a repeat. The subtraction game $\{1, 2\}$ gives 0, 1, 2, 0, 1, 2, 0. Kayles gives 0, 1, 2, 3, 1, 4, 3, and Dawson’s chess 0, 1, 1, 2, 0, 3, 1.

Every one of them starts at nought and every one of them starts by agreeing with Nim for at least one term. That is not a coincidence: an empty heap has no options so its value is nought, and a heap with one option of value nought has value one. So the sequences all leave the identity somewhere and they all begin on it, which is precisely the condition under which the 1901 criterion is nearly right about small positions and wrong about the rest.

The earlier essay sweeps fifty-six subtraction games asking which of them have a criterion of Bouton’s shape — a description shorter than the game — and finds seven. The sequences above say what the other forty-nine look like from the inside: not chaotic, not unstructured, simply not the identity.

Where the sequences part company #

The two criteria are the same sentence at any heap whose Grundy value equals its size, so the natural next measurement is how far each game’s sequence departs from the identity.

One end of the relationship is exact and unsurprising: a game whose sequence is the identity is a game Bouton’s criterion settles, and Nim is the only such game here. Zero departure and exactness are the same condition.

The other end does not behave. The subtraction game $\{2, 5\}$ departs on every heap in range — not one value equals its size — and Bouton’s criterion is right about 71 per cent of its positions. Kayles departs on half its heaps and Bouton is right about 93 per cent. The subtraction game $\{1, 2\}$ departs on two thirds and Bouton manages 70.

Sorted by departure the accuracies run 100, 87, 93, 70, 87, 81, 71, 76. There is a relationship and it is not a function, and the reason is arithmetic rather than mysterious: what matters is not how many values differ but whether the exclusive-ors of three of them differ, and a sequence shifted by a constant or permuted within a power of two can leave the comparison with nought untouched at many positions.

So how much the substitution changed cannot be read off how much it changed the numbers, which is worth knowing before anybody tries to argue that some games were nearly solved in 1901.

Why nobody could price the gap from inside it #

The three papers between 1901 and 1910 each contain a complete solution of one game, and the four earlier essays establish that none of the three transplants.

What the substitution adds to that account is the shape of what was missing. It was not a better criterion; it was a quantity. The 1901 paper has an operation with nothing to apply it to, the 1907 paper has a closed form with no operation, and the 1910 paper has an operation that is a genuine generalisation of Bouton’s and still has nothing to apply it to.

A person in 1910 holding all three would have had the exclusive-or twice over and no reason to think that a heap could have a number attached to it other than its size. The step is not hard to state and it is very hard to want: it requires believing that a position of some other game is, for the purposes of the arithmetic, a Nim heap of some size — which is the content of the theorem rather than a route to it.

What a person in 1910 would have had to compute #

It is worth pricing the missing half in the currency of the time, because the answer is small enough to be surprising.

To apply the substituted criterion to a subtraction game, a person needs the Grundy values of single heaps up to whatever size they care about. Producing them is the mex rule applied once per heap: look at the values of the heaps reachable in one move, and write down the least number not among them.

For the subtraction set $\{1, 2, 3\}$, values to a heap of twenty are twenty applications of a rule with at most three lookups each — a few minutes with a pencil. For Dawson’s chess the sequence is harder and it is the computation of 1956 rather than of 1910, but the rule is the same rule and the first twenty terms are no worse.

So the obstacle was not arithmetic. A person with the mex rule and an afternoon could have solved forty-nine subtraction games in 1901, and the same person with Bouton’s exclusive-or could have combined heaps immediately afterwards. Every ingredient except the idea was cheap, and that is what makes thirty-four years the right length of time to be puzzled by.

What the gap is not evidence of #

Thirty-four years with nothing in between invites two readings and both are worth resisting.

It is not evidence that the step is deep. The substitution is one noun and the proof is Bouton’s own closure argument with a variable in it, which is the subject of the essay that follows. Measured by what has to be written down it is a short step.

Nor is it evidence that nobody was looking. Nothing here is archival and nothing here could be: a sweep over games says what was reachable and says nothing about who reached for it. What it does establish is that the reach was not blocked by a computation — the Grundy values of a subtraction game to a heap of twenty are twenty numbers a person can produce in an afternoon, and the mex rule is a rule a person can be told in a sentence.

So the honest statement is about the shape of the gap rather than its length. What was missing was not a technique and not a calculation. It was the idea that the quantity in the exclusive-or could be something other than the heap it is read from.

The one game the substitution does nothing to #

There is a reading of the first figure that makes the whole essay concrete, and it is the row for Nim.

Bouton’s criterion is right about all 84 of Nim’s positions. The substituted criterion is right about all 84 as well, and it is right about them by computing the same numbers — since a Nim heap’s Grundy value is its size, the substitution replaces each heap by itself and the two columns are the same arithmetic run twice.

So on the one game the theory was found in, the theory is invisible. A person checking the 1935 statement against Nim would see nothing new at all, and a person checking the 1901 statement against any other game would see it fail without being told which quantity to replace.

That is the trap in as sharp a form as it gets. The example that made the operation available is the example on which the missing ingredient has no effect, so the ingredient could not be discovered by studying the example more carefully. It could only be discovered by studying something else, and the four earlier essays are about how thoroughly the decade after 1901 failed to.

What the substitution is an instance of #

The pattern has a name once it is seen, and it recurs across these essays.

An operation is discovered on the object where it happens to be free — where the quantity it needs is already lying about — and the operation is then mistaken for the theory. The theory is the operation plus the thing that produces its inputs, and the second half is invisible wherever the inputs are free.

The nim-sum fails on Dots and Boxes for a related reason in reverse: there the operation is right, the inputs are computable and the combining is what breaks, because a capture keeps the turn. Here the combining is right and the inputs were missing. Two halves of one theorem, each of which can fail without the other noticing.

So the honest description of 1901 is that it is half a theorem with the other half supplied by an accident of the game it was proved about. That is a much more useful thing to say about it than it did not generalise, and it is what the substitution makes measurable.

A criterion stated as a test on a position #

Normal play throughout: the player who cannot move loses. Every criterion here is stated as a test on a position — this position is lost for the player to move — rather than as advice about play, which is what makes two of them comparable at all.

Three conventions of the sweep.

Positions are multisets of heaps, which is how the 1901 criterion itself reads a position. Three heaps of at most six is 84 positions rather than 343, because the order of the heaps is not part of a position and counting it would weight the symmetric ones wrongly.

The truth is a search rather than either criterion. Both columns are scored against an exhaustive recursion over the game’s own moves, so an agreement is a criterion agreeing with the game rather than with the other criterion.

Heaps are the components and the substitution is per heap. A subtraction game’s position is several heaps and each contributes its own Grundy value, which is the arrangement Bouton’s criterion assumes and the theorem generalises. A game whose position is not a list of independent parts is outside both statements.

And the family is eight games chosen for their sequences. Four subtraction sets and three octal codes, picked to span sequences that are the identity, that are periodic with a small period, and that are neither. A family chosen to make the old criterion look bad would be easy to assemble and would establish nothing; what is wanted is a spread of departures, and the spread is what the second figure reports.

Eight games, and heaps of at most eight #

Eight games and heaps of at most eight. The exactness of the substituted criterion is a theorem and does not need the sweep; the inexactness of the original is measured, and it is measured over a family.

Octal games are taken one heap at a time. A take-and-break move splits a heap in two, so the substituted criterion is being applied to a position with more components than it started with — which is exactly what the theorem is for and is worth stating, because the 1901 criterion has no form for it at all.

Nor does it price the 1935 proof. The substitution is one noun and the argument that it works is not; what the sweep establishes is that the statement differs by one quantity, which is a claim about the sentences rather than about the proofs behind them.

And nothing here is about the misère convention. The other half of Bouton’s paper has its own criterion and its own failure, and the substitution above does nothing for it: replacing sizes by Grundy values in the misère criterion does not produce the misère theory, because there is no misère theory of that shape.

Where the errors fall #

One more reading of the sweep is available and it says what a person meeting the old criterion in the wild would have experienced.

Bouton’s criterion is right about between 70 and 93 per cent of the positions of the games it was not written for. That is a high enough rate to be useful and far too high to be noticed as wrong by casual play — a rule that settles four positions in five looks like a rule with a few exceptions rather than a rule about a different game.

The essay four below measures the direction of the errors on one game and finds them one-sided: transplanted onto a subtraction game the normal criterion calls losses wins and never the reverse, so it is sound and incomplete. A player following it would never be told they had won when they had lost; they would simply fail to find wins that were there.

Put together with the accuracy, that is a criterion which is hard to catch out. It is right most of the time and its mistakes are all of the forgiving kind, which is a considerably better description of why 1901 sat undisturbed than nobody tried.

Still open: whether the 1910 rule was closer #

Moore’s 1910 solution is a genuine generalisation of Bouton’s — it allows a player to take from up to $k$ heaps at once, and its criterion is a digit sum modulo $k+1$ rather than an exclusive-or, which is the same thing at $k = 1$.

That makes it the one object in the decade with a parameter in it, and the earlier essays establish that it does not transplant to other games either. What has not been measured is whether the substitution works on it: replace the heap sizes in Moore’s criterion by some per-heap quantity and ask whether any assignment makes it exact on a game it was not written for.

If some assignment does, then the 1910 paper was one substitution from a theory of a family of games rather than of one, and the gap has a different shape than this essay gives it. If none does, then Moore’s parameter is a generalisation in a direction with nothing in it, and the two facts together say exactly how narrow the 1901–1910 decade was.