Three complete solutions in nine years

The rung below has a job it states plainly: what a complete solution looks like when it arrives before the theory that would explain it. It takes Bouton’s 1901 solution of Nim, asserts his two closure properties of a game he did not write them for, and watches one half survive and the other break.

It ends on a test rather than a result. A complete, correct, elementary solution can be a dead end rather than a foundation, and what decides which is whether the solution introduces an object that turns out to have a life outside the problem.

Bouton’s paper is offered as the clearest instance of the failure. It is not the only instance available, and the decade after it supplied two more solutions of the same kind — different games, different people, same shape — which makes the test something that can be applied rather than illustrated.

The three #

Bouton, 1901. Write the heap sizes in binary and stack them; the mover loses exactly when every column holds an even number of marks. Equivalently, the sizes exclusive-or to nothing.

Wythoff, 1907. A queen on a quarter-infinite board, moved left, down or diagonally down-left any distance. The cold positions — the ones the mover loses — are the pairs ⌊nφ⌋ and ⌊nφ⌋ + n, for n = 0, 1, 2, and so on. A closed form, in terms of the golden ratio, thirty years before anybody could have said what a Grundy value was.

Moore, 1910. Nim with the rule that a move may take from up to k heaps at once. The mover loses exactly when every binary column of the heap sizes sums to a multiple of k + 1. At k = 1 that is Bouton’s criterion, because a column summing to nothing modulo two is a column with an even number of marks, so Moore’s is a genuine generalisation rather than a second theorem about a nearby game.

Three papers, nine years, three games, three complete answers, and not one line of theory between them. Every one of them is stated as a test on a position — look at the heaps, apply the rule, get a verdict — because the alternative, a value the position has, had not been invented.

The grid #

Take each criterion and ask it about each game, with the truth in every cell coming from a search rather than from another criterion.

Bouton’s is exact on Nim, as it must be: 343 of 343 positions of three heaps up to six. On Wythoff’s game it is right on 39 of 49; on Moore’s it is right on 295 of 343; on the subtraction game {1, 2, 3} it is right on 300 of 343.

Moore’s is exact on Moore’s own game, 343 of 343. On Nim it is right on 295 of 343 — the same number, from the other side, since at k = 2 the two criteria disagree on exactly the positions where a column of three marks matters. On Wythoff it manages 45 of 49 and on the subtraction game 254 of 343.

The Grundy criterion — the nim-sum of the heaps’ Grundy values — is exact on Nim, on Wythoff and on the subtraction game, which is what a theorem looks like.

Three criteria, each right about its own game and wrong about everything else. That is the rung below’s finding replicated twice over, and by itself it says nothing new: a criterion for a game is a criterion for that game, and nobody claimed otherwise.

The two blanks #

The grid has two cells that are not scores, and they are the reason to draw it.

Wythoff’s criterion has no entry for the three-heap games at all. Not a low score, not a bad approximation. It cannot be asked. His description names a pair — one number is ⌊nφ⌋ and the other is that plus n — and a position of three heaps is not a pair. There is no reading of the description that applies to it, no natural extension anybody has proposed, and nothing to score.

The Grundy criterion has no entry for Moore’s Nim. For a different reason and it is just as structural. A Grundy value is a value per component, and the theorem that makes it work says the value of a sum is the exclusive-or of the parts. Moore’s Nim is not a sum: a move takes from several heaps at once, so the heaps are not independent components, so there is nothing for a value per heap to be a value of.

Those two blanks are the whole essay, and they are two different kinds of thing:

A criterion that gives wrong answers has a form and is false. It can be scored, its errors can be counted and their direction reported, and — as the rung below shows for Bouton’s on the subtraction game — the direction of the errors says what it may still be used for.

A criterion with no form for the question is not false. It is silent. There is nothing to score, no direction to report, and no repaired version to look for.

What the numbers in the grid are worth #

Before the blanks, a word about the scores, because a reader could take 295 of 343 as nearly right and it is not.

A criterion that is right on 86% of positions is not 86% of a solution. It is a rule that names the wrong winner one time in seven, and a player using it loses one game in seven from a position they thought was won. There is no partial credit in a criterion; it is a claim about every position it is applied to.

More to the point, the errors are not distributed the way a reader would guess. The rung below measures the direction for Bouton’s criterion on a subtraction game and finds it one-sided — every one of the sixty-four errors is a loss called a win, none the reverse — and explains why: the subtraction game’s values are the heap size’s low two bits, so Bouton’s test consults extra bits and can only refuse positions the true test would have accepted.

That protection is a property of that pairing rather than of the criterion, and the grid’s other cells have no such guarantee. What the scores establish is that the criteria are false elsewhere. What direction they are false in has to be asked case by case, and the answer changes.

Which failure is the one that matters #

Now apply the test the rung below states.

Did the solution leave behind an object with a life outside the problem?

Bouton’s did. The nim-sum is an operation on numbers, defined for any number of arguments, and the criterion is apply it to the heaps and see if the answer is nought. Ask about a game with four heaps instead of three and the operation has an answer; ask about a game whose heaps are worth something other than their size and the operation still has an answer, applied to those values instead. The object is separable from the criterion, and thirty-four years later somebody separated it.

Moore’s did. His rule is a digit-sum modulo k + 1, and it is stated for any number of heaps from the beginning — the criterion is about columns and a column can have any height. It also has a parameter in it, and what the parameter is doing turns out to be a subject of its own.

Wythoff’s did not. The Beatty pair is a description of a set: these positions are cold, those are not. It is exact, it is beautiful, it involves the golden ratio in a game about picking up stones, and it has nothing in it that could be applied to anything. There is no operation, no quantity per component, no rule for combining. The description tells a reader which pairs are cold and stops.

Sprague and Grundy supplied the separation, and what they supplied is a value rather than a better test — the difference the rung below is entirely about. That is why the grid’s blanks are the finding. The criterion that could not be asked the question is the criterion whose game led nowhere, and the two facts are the same fact.

The test the grid cannot run #

There is a sharper form of the question, and the grid cannot ask it because the grid compares criteria on single positions.

The real test of an object with a life outside its problem is whether it survives a disjunctive sum. A criterion that describes a set answers one question about one position. A criterion that describes a combination of the parts answers the question about any number of them at once.

So put two Wythoff games side by side. Wythoff’s description says exactly which single positions are cold and has nothing to say about a pair of them, and the natural reading — a sum is cold when both parts are — is checkable.

It is wrong on 153 of 1,296 sums. Twenty-five sums have both parts cold and every one of those is genuinely cold, so the naive reading is sound. But 153 sums are cold with neither part cold on its own, so it is badly incomplete — and the positions it misses are exactly the ones where the two components’ Grundy values happen to cancel, which is a fact about numbers the description does not compute.

For Bouton’s and Moore’s the question does not arise, and that is the point rather than an exemption. Both are stated for any number of heaps to begin with, so a sum of two games of theirs is just a bigger position of the same kind and the criterion applies to it unchanged.

What the golden ratio was for #

None of this is a complaint about Wythoff, and it would be a poor reading of the record to take it as one.

His result is the more surprising of the three. Bouton found a parity in a game about counters and parities are what one finds in games about counters; Wythoff found φ in one, which is a fact nobody would have predicted and which connects a stone-picking pastime to the theory of Beatty sequences. The two routes to it — a table computed by mex and a formula that never mentions φ — arrive at the same set, and that is a genuinely deep coincidence rather than a lucky one.

What it is not is a foundation. The golden ratio has an enormous life outside Wythoff’s game and none of it is in game theory; the object his solution introduced belongs to number theory, and number theory took it and did things with it that have nothing to do with who wins anything.

So the test is not about how good an object is. It is about which subject the object belongs to. A set with three descriptions is where this site follows Wythoff’s cold positions into number theory and finds them described three ways, none of which is a rule for combining anything. A solution founds a theory when the thing it introduces turns out to be about the same subject as the problem, and Wythoff’s is a case where a first-rate object went somewhere else.

Moore’s rule is the one that generalises Bouton’s #

Of the two criteria that pass the test, one contains the other, and that containment is worth drawing out because it is the closest anybody came to a theory before there was one.

Set k = 1 in Moore’s rule: a move may take from up to one heap at a time, which is Nim; and every column must sum to a multiple of two, which is every column holding an even number of marks, which is Bouton. So Moore’s paper contains Bouton’s as the first case of a family, nine years later, stated in the same vocabulary.

That is a generalisation of exactly the kind the test rewards. It did not require a new object — the digit sum was already there — and it did require noticing that Bouton’s parity was a modulus in disguise, which is a small step and a real one.

What it did not do was change the kind of thing being computed. Moore’s criterion is still a test on a position, still stated in terms of the heap sizes, and still incapable of saying what a heap is worth. Taking from several heaps at once is where the game itself is worked out on this site, and the thing that has no answer there is the same thing: a game whose moves touch several components has no per-component value, so the Sprague–Grundy machinery is unavailable to it and Moore’s rule is what stands in for it.

So the decade produced one criterion that generalises another and no criterion that generalises to a different game. Every one of the three is about the game it was written for, and the two that pass the test pass it by being stated as arithmetic rather than by being about anything wider.

Why nobody could have known #

It is worth resisting the reading in which somebody should have noticed which of the three was the foundation.

In 1910 all three looked alike: a hard game, a complete answer, a criterion a person could apply. Nothing distinguished the nim-sum from the Beatty pair except a property — separability from the criterion — that has no meaning until somebody asks a question the criterion was not written for.

And the question that reveals it is the disjunctive sum, which is Conway’s subject and is sixty years away. There was no sum of games in 1910 to test anything against. Bouton’s criterion turns out to survive a question nobody could pose, and it survives it because he happened to state his condition in terms of an operation rather than in terms of a list.

That is the honest form of the record. The property that decided which solution founded a subject is a property nobody in that decade could have checked.

What the picture cannot show #

The four games are chosen and not sampled. Nim, Wythoff, Moore’s Nim and a subtraction game are four games with three complete pre-theory solutions between them, which is what the essay is about; nothing here is a claim about impartial games in general.

Moore’s Nim is swept at k = 2 only. The parameter is what an anchor of its own is about, and the grid uses one setting because a criterion has to be scored against a game rather than against a family.

And the ranges differ between columns. Wythoff’s game is a game on two heaps and Moore’s is not a game at all until there are three, since taking from two of two heaps empties the board. A grid that forced one range on all four would be reporting a degenerate column as a result, so each game is swept over the number of heaps it is a game about — and the counts in different columns are therefore not directly comparable to each other.

The convention, named #

Normal play throughout: the player who cannot move loses. All three papers use it, none of them says so, and none of them had a word for it.

That is worth a sentence because it is the one thing the three did share, and sharing it is not a coincidence. Nim, Wythoff’s game and Moore’s Nim are all games of taking things away, and a game of taking things away ends when there is nothing left, and the natural reading of who has lost is the player facing nothing. The convention is what the games suggest rather than something anybody chose.

Bouton’s paper does treat the other convention as well, in a sentence, and that sentence is the rung two above this one — where the same transplant is performed on the misère half of the 1901 paper and produces a different kind of failure.

The surprise: two of the three succeeded and the wrong one is remembered as the founder #

The usual story about this decade is that Bouton solved Nim and the subject grew out of it. The rung below already complicates that: Bouton’s solution was so clean that it suggested nothing, thirty-four years passed, and what broke the silence was somebody looking at a game that is not Nim.

The grid complicates it further and in the opposite direction. Two of the three criteria pass the test, not one. Moore’s rule is a digit-sum for any number of heaps, it has a parameter, it generalises Bouton’s exactly, and it left behind an object that is used — and it is much less famous than either of the others.

So the scoreboard is not one founder and two dead ends. It is two solutions whose objects were separable and one whose object belonged to a different subject, and which of the two separable ones is remembered as the founder was decided by which game was more famous rather than by which criterion was more general. Bouton’s own paper is a bar game solved completely, and being a bar game is most of why anybody read it.

The general shape is worth carrying. The property that makes a result a foundation is whether the thing it introduces can be asked a question the result was not about, and that property is invisible at the time, is not correlated with elegance, and is not correlated with fame. What decides it is a piece of grammar: whether the answer was written as an operation on the parts or as a description of the whole.

Where the ladder goes next #

bouton now has the 1901 paper, and the two solutions beside it put to its own test.

The rung above turns the test on the method rather than on the result. Bouton’s argument is a closure argument about a set: exhibit a set no move leaves and every other position reaches, and that set is the losing positions. That much is available for every impartial game whatever, with the set being the losing positions themselves — so the method is complete and says nothing. What made 1901 a theorem is that his set had a description shorter than the game, and how far a description of that kind reaches is a question with a count for an answer.