The sentence that solved the other convention

The rung three below ends with the other convention as a footnote, and calls the footnote a warning:

Bouton’s paper also treats the other convention, and this is genuinely to his credit, because it is a harder result and he got it. Under misère play the winning condition for Nim is almost the same, with one exception: when every heap has size one, the criterion inverts.

That is the whole of the misère half of the 1901 paper: one sentence, one exception, one game solved completely under a convention that would defeat everybody for the next century. It is the only misère result in the subject that fits on a line.

This rung does to it exactly what the rung three below does to the other half — asserts it of games it was not written for, and watches.

The criterion #

Stated as a test on a position rather than as advice about play, Bouton’s misère rule has two clauses:

If every heap has at most one counter, the mover loses exactly when the number of heaps is odd.

Otherwise, the mover loses exactly when the heap sizes exclusive-or to nothing.

The second clause is the normal-play criterion unchanged. The first is the exception, and it fires only on the positions where every heap is a single counter — which under misère play is where the endgame’s parity inverts, because handing the opponent the last counter is now what a player wants.

One clause bolted onto a criterion that was already there. That is why it fits on a line, and it is why the rung three below can call misère Nim the one misère game with a clean answer.

What happens when it is moved #

Take the same range the rung three below uses — three heaps of at most six, three hundred and forty-three positions — and score the criterion against a misère search.

Nim: 343 of 343. As it must be, and the run is a test of the code rather than of the mathematics.

The subtraction game {1, 2, 3}: 276 of 343. Sixty-seven wrong.

The subtraction game {1, 2}: 222 of 343. A hundred and twenty-one wrong.

Dawson’s chess, ·137: 239 of 343. A hundred and four wrong.

Kayles, ·77: 279 of 343. Sixty-four wrong.

Those counts are unremarkable on their own — a criterion for one game is wrong about others, which the rung three below establishes at length for the normal-play half. What is not unremarkable is the direction.

Both directions, on every game #

The rung three below’s headline finding about the normal criterion is that its errors are one-sided. Transplanted onto {1, 2, 3} it disagrees with the truth on sixty-four of five hundred and twelve positions and every one of the sixty-four is Bouton calling a loss a win. Not one is the reverse.

It explains why, and the explanation is arithmetic. The subtraction game’s Grundy value is the heap size’s low two bits; the correct criterion is that those bits exclusive-or to nothing; Bouton’s criterion asks that all the bits do; and a zero over all the bits is in particular a zero over the low two. So his condition implies the true one and not conversely, and the criterion is sound and incomplete.

The misère criterion has no such protection, and the counts say so on every game:

{1, 2, 3}: twelve errors one way, fifty-five the other.

{1, 2}: thirty-three and eighty-eight.

·137: twenty-seven and seventy-seven.

·77: eighteen and forty-six.

Both directions, every time. A criterion that errs both ways is not a sufficient condition, not a necessary one, and not usable for anything — where the normal transplant at least tells a reader that a Bouton-even position really is lost, this one tells a reader nothing at all.

The two halves of the same paper, scored side by side #

Setting the two transplants beside each other is what makes the direction of the errors a finding rather than an observation, because the two criteria share most of their content.

Both read the heap sizes. Both use the exclusive-or. Both were published in the same paper by the same person about the same game, and both are exact on that game. The misère one is the normal one plus a clause.

And the normal one, transplanted onto {1, 2, 3} over three heaps, is wrong on sixty-four of five hundred and twelve — all in one direction. The misère one, transplanted onto the same game over three heaps of six, is wrong on sixty-seven of three hundred and forty-three, in both.

So the added clause does not merely add errors. It removes the property that made the errors useful, and it removes it because the exclusive-or’s protection is an argument about bits and the clause is not an argument about anything — it is a special case, and a special case has no direction.

That is the sharpest available demonstration of what a special case costs in a criterion. A rule assembled from an operation is a rule whose failures can be reasoned about; a rule assembled from an operation and an exception is a rule whose failures cannot.

The clause responsible #

The reason is in the exception, and it is worth stating precisely because it is a general hazard rather than a fact about Nim.

The second clause — the exclusive-or — carries whatever protection the normal criterion has, for the same reason and to the same degree. If it were the only clause, the transplanted misère criterion would inherit the one-sidedness wherever the normal one has it.

The first clause is the problem. It fires on positions where every heap has at most one counter, and at most one counter is a statement about the number of counters in a heap rather than about what a move can do with it.

In Nim those coincide. A heap of one is a heap with exactly one move available and that move empties it, so a heap of size one and a heap with one move, which ends it are the same thing, and Bouton could write either.

In any other game they come apart. In the subtraction game {1, 2, 3} a heap of one has one move; so does a heap of two, in a sense that matters — it has two, one of which empties it. In ·137 a heap of one may be taken whole and a heap of two may be taken whole as well, so the endgame’s parity involves heaps of two as much as heaps of one. The clause is looking at the wrong thing, and it is looking at the wrong thing in a way that has no correction because what makes a heap an endgame heap is different in every game.

Where each transplant first goes wrong #

The smallest failing positions are worth reading, because they are all the same shape.

On {1, 2, 3} the criterion first fails at a single heap of five. On {1, 2}, at a heap of four. On ·137, at a heap of two. On ·77, at a heap of four.

Every one of them is a single heap — not a combination, not an interaction between components, but one heap the criterion misreads on its own. And in every case the criterion says win and the truth is loss.

That locates the defect exactly. A criterion that first failed on a two-heap position would be a criterion whose combining rule is wrong; this one’s combining rule is the exclusive-or and the exclusive-or is not what breaks. What breaks is the reading of a single heap, which is the clause, which is the endgame.

It also explains the two-way errors without any further computation. A criterion misreading single heaps produces errors in whatever direction the misreading goes at that heap, and there is no reason for the direction to be constant — a heap the criterion calls a win might be a loss, and a heap it calls a loss might be a win, and both happen.

Why this is the harder half and the one that goes nowhere #

The rung three below is right that the misère sentence is to Bouton’s credit and it is worth saying why the credit is larger than it looks.

Under normal play, Nim’s answer falls out of one invariant. Under misère play, essentially every other game in the subject resists completely: misère analysis was declared intractable in the 1970s, and the verdict was correct about what was being attempted. What replaced it thirty years later is not a criterion but a quotient — a monoid of classes per game, whose size grows with the positions in view — and even that is a smaller ambition honestly stated. Dawson’s chess needs twelve classes where normal play needs four, and the count doubles the moment a wild heap enters the range.

So Bouton’s sentence is a complete misère solution in a subject where complete misère solutions do not exist. The reason it exists here is the reason the rung three below gives: Nim’s heaps are so simple that the endgame has only one special case.

And now apply the test this anchor is built on. Did the misère sentence leave behind an object with a life outside the problem?

No. The exclusive-or was already Bouton’s from the other half of the paper; the new content is the clause about heaps of size one, and the clause is a statement about one game’s endgame that has no form anywhere else. It is not an operation, it is not a quantity, it does not compose, and it cannot be parameterised — there is no k to vary, as Moore’s rule has, no bits to mask, as the reach sweep looks for, and no generalisation waiting.

That makes it the clearest case on this ladder of a result that is harder than its neighbours and is nevertheless a dead end. Difficulty is not what decides, and the misère sentence is the evidence: the harder half of the paper produced nothing and the easier half produced a subject.

What Bouton had to notice #

It is worth reconstructing what the sentence required, because the transplant makes the achievement legible in a way a summary does not.

Under normal play the last player to move wins, so a player wants the last counter and a heap of one is a prize. Under misère the last player loses, so a heap of one is a liability and the endgame is about handing them over. Everywhere else in Nim the two conventions agree about which positions are wins — which is itself a surprising fact and is the reason the criterion needs only one clause rather than a second theory.

What Bouton had to see is that the agreement holds right up to the endgame and breaks only at the shape where every heap is a single counter. That is a claim about when the two conventions come apart, and it is not obvious: a reader might reasonably expect two conventions that disagree about who wins the smallest position to disagree about a great many larger ones.

They do not, in Nim. They do in essentially everything else, and the counts on this page are how that is said — a criterion built on the agreement holding until the very end is a criterion that fails wherever the agreement fails earlier.

What a repaired criterion would need #

It is worth asking what the misère sentence would have to say to survive a transplant, because the answer says why nobody wrote one.

The clause needs to fire on the positions where the endgame’s parity inverts, and in Nim those are the positions where every heap has exactly one move. So the general form of the clause would be: if every heap has exactly one option and that option ends it, the mover loses when the heaps are odd in number.

That is stateable. It is also useless, because in most games the set of heaps with that property is empty or nearly so, and the inversion happens somewhere else entirely — at heaps whose options are several, in patterns that differ from game to game and that the genus exists to record.

Which is to say the repair does not converge on a criterion. It converges on a classification, one per game, with no fixed size — and the classification is the misère quotient, and building one is a computation rather than a sentence.

So the honest answer to why did nobody generalise Bouton’s misère rule is that generalising it is the whole misère theory, and the whole misère theory is not a rule.

What the picture cannot show #

Four games is four games. Nim, two subtraction games and two octal codes are chosen for being the games this site already computes, and the finding — errors in both directions — is a finding about those four rather than about impartial games in general. What generalises is the explanation, since the clause about heaps of size one is a Nim-specific reading whatever else it is asked about.

And the range is three heaps of at most six. The misère search is exponential in the heaps, and three of six is where an exhaustive check is affordable. A wider range would change every count and, on the evidence of the two ranges swept, no verdict.

Nor does anything here measure how wrong the criterion is on a real position. A count of disagreements over a uniform sweep weights a heap of one as heavily as a heap of six, and a player does not meet positions uniformly. What the counts establish is that the criterion is false, not how badly it would perform.

The convention, named #

Misère play throughout: the player who cannot move wins. That is the convention the criterion is about and it is the convention the truth column is computed under.

The thing worth noticing is how small the change is at the level of the code and how large at the level of the result. The misère search differs from the normal one in a single line — a position with no moves returns a win for the mover rather than a loss — and everything else is identical: the same games, the same move generators, the same recursion, the same memoisation.

One line, and a criterion that was exact becomes a criterion that is wrong in both directions on every game it is asked about. What misère play costs is the general accounting; this is one line of it, on one criterion. That is the whole of what a convention is worth, measured on a criterion rather than on a theory.

The surprise: the harder result was the more parochial one #

The story the rung three below sets up is that Bouton’s normal-play criterion is a dead end because it was too clean to suggest anything. The misère half complicates it, because the misère half is not clean — it has an exception in it, it is harder to prove, and it is the part of the paper that shows the author was paying attention to something awkward.

And it goes nowhere at all, and goes nowhere worse than the normal half does. The normal criterion transplanted is sound and incomplete, which is a useful thing to be; the misère criterion transplanted is neither, which is nothing.

The awkwardness that makes a result impressive is not the same as the generality that makes it a foundation, and here they run in opposite directions. What made the misère sentence hard is the exception; the exception is a fact about Nim’s endgame; and a fact about one game’s endgame is the least portable kind of statement there is.

That is worth carrying whenever a result is being praised for being difficult. Difficulty is a property of the proof and portability is a property of the statement, and the two are unrelated — a hard proof of a parochial fact is a hard proof of a parochial fact. The test remains the one this anchor is built on, and it is not how hard was it: did it leave behind an object with a life outside the problem?

Where the ladder goes next #

bouton has four rungs now: the 1901 criterion and where it fails, the two solutions published beside it, how far a description of its kind reaches, and the other half of the same paper.

The rung above is the one that would close the anchor, and it is a piece of archival arithmetic rather than a piece of mathematics. The three papers here are 1901, 1907 and 1910, and the theory arrives in 1935 and 1939 — thirty-four years, with nothing in between. The rungs so far explain why each individual solution led nowhere; what none of them establishes is whether anybody in that gap tried, what they tried, and whether the objects were sitting there unrecognised in papers nobody now reads. That is a rung about the gap rather than about the results either side of it.