Two misère outcomes are not enough

A position has an outcome class, and it is the cheapest possible summary: P if whoever must move loses, N if whoever moves first wins, L if Left wins whoever starts, R if Right wins whoever starts. Four letters, and every position in the subject wears one of them.

A board that falls into two independent regions is a disjunctive sum, and the natural hope is that the two letters compose — sixteen pairs of classes, sixteen answers, and the analysis of a split board becomes a lookup. That hope has a name, additivity of outcomes, and this page measures exactly how much of it each ending leaves standing.

Outcomes do not add kills that hope under normal play, and says what to do instead: the parts have values, the values add, and the sum’s outcome is read off the total. The failure is real and it is repaired one line later.

This essay asks the same question under misère play — the same games, the same moves, and the player who cannot move now wins — where there is no line after.

Nine against zero. Under normal play the outcome class is a badly incomplete summary of a position; under misère it is, for the purpose of adding, no summary at all.

Nine cells that are theorems, and seven that are not #

The nine determined cells in the normal-play table are not a lucky sample, and the whole comparison rests on their not being one.

Seven of them are the row and column headed P. A P-position is a second-player win, which is the same statement as the position is worth zero — equality in this subject means that G = H when G − H is a second-player win, so a P-position equals the empty game. Adding zero changes nothing, so P + X has X’s value and therefore X’s outcome, for all four choices of X, in both orders. That is seven cells, and it is a proof rather than a count.

The other two are L + L = L and R + R = R. An L-position is one Left wins going first and going second, which is a position greater than zero, and the sum of two positives is positive. Again a proof.

The seven that fail are exactly the ones no such argument covers: N + N, N + L, L + N, N + R, R + N, L + R and R + L. Each of those mixes a position confused with zero, or a positive with a negative, and the answer depends on how much. So additivity survives in nine cells for a stated reason and fails in seven for a stated reason, which is a great deal more than a count.

Nine survives the change of pool because it was never about the pool. One does not.

Two witnesses: five counters, and three numbers #

The abstract statement deserves a position a reader can build on a table, and the cheapest one costs five counters. Nim, the oldest impartial game there is, has a famously short misère theory: play as in normal Nim until the move that would leave every heap at one counter, then leave an odd number of single heaps instead of an even one. That shortness is what makes the following so easy to miss.

Take a single heap of two counters. Under misère play it is an N-position: the mover takes one counter, and the opponent is forced to take the last one. Now take two heaps of one counter each. Also an N-position under misère, for a different reason: the mover takes one heap and leaves one counter for the opponent.

Two positions, the same misère outcome, and each is two counters. Add a heap of one counter to each.

Nothing about the two starting positions, expressed as outcome classes, could have predicted that. Under normal play they are separated by their Grundy values — a heap of two is worth ∗2 and two heaps of one are worth ∗1 + ∗1 = 0 — and the values do the work the letters cannot. Under misère the letters are all there is.

The second witness leaves the impartial world altogether, and it is the cleanest single sentence in the essay.

Searching the twenty-six-position pool for the cheapest partizan witness under misère play returns 1, 2 and −1. The positions 1 and 2 — a single free move for Left, and two free moves for Left — are both R-positions under misère, because a player with moves in hand under this convention is a player who will be forced to make the last one. Adding −1, a single free move for Right, gives sums that are N and R respectively.

Running the same search under normal play returns the same three positions. 1 and 2 are both L, and adding −1 gives P and L.

The outcome function fails identically under the two conventions, on the same three positions, at the same price. What differs is what happens next. Under normal play a reader says at once that 1 and 2 are different numbers, that 1 + (−1) = 0 and 2 + (−1) = 1, and the failure is dissolved rather than explained: the outcomes were never the right summary, the values are, and comparing positions is arithmetic thereafter. Under misère there is no number to reach for, and the failure is the end of the road.

The same failure runs in Nim on rows the change of convention does not touch at all. Heaps of 2 and of 3 read N under both endings, and so do both of their sums with a further heap of 2 — and yet those sums are a second-player win in one case and a first-player win in the other. Under normal play the repair is one line: the heaps are worth ∗2 and ∗3, and ∗2 + ∗2 = 0 while ∗3 + ∗2 = ∗1. Under misère there is no line.

So the two failures differ in degree — sixteen ambiguous cells against seven — and enormously in consequence, because the normal-play table sits underneath a theory that makes it irrelevant and the misère table does not.

Nim is also where the emptiness of the misère table can be pinned to a single cell, because a pool of Nim heaps reaches only two of the four classes and the table shrinks to a corner small enough to read.

That cell is worth staring at, because it is the cleanest disproof available of the thing a reader keeps wanting to be true. Under normal play P + P = P is not a measurement; it is the statement that nought plus nought is nought. Under misère the same pair of classes is equally determined and gives the opposite answer, which means the P here is not a weakened zero or an approximate one. It is a different property with the same letter on it, and adding two of them is a construction rather than a no-op.

Nothing is worth zero, and nothing relabels #

Why the misère table has no determined cells at all, rather than merely fewer, is worth stating precisely, because it explains why even P + P is ambiguous.

Under normal play the P row and column are settled by one fact: a P-position is zero. Under misère that fact is gone, and its going is the subject of misère play has no negatives. Put a position beside its own mirror image and the second player answers every move in one copy with the mirror move in the other; under normal play the answerer therefore always has a reply and wins, which is why G + (−G) is zero for every game there is. Under misère the answerer still always has a reply, and always having a reply is exactly how a player ends up making the last move.

A misère P-position is a position whose particular tree happens to lose for the mover. It is not an identity for the disjunctive sum, it cannot be dropped from one, and two of them added together may be anything at all. That is P + P = PNLR, and it is the cell that has no analogue in the normal-play table — negation and zero having gone together.

There is a tempting shortcut worth closing off, since the essay would be much shorter if it worked: perhaps the misère outcome is a function of the normal one, and the misère table can be got from the normal one by relabelling. One position from each class settles the shape of the guess — the empty game is P and becomes N, ↑ is L and becomes R, ↓ is R and becomes L, and ∗2 is N under both — so three of the four change hands and the swap looks like a permutation.

Over the twenty-six-position pool the relabelling fails. Twenty-two of the twenty-six change class when the ending is reversed, which is unsurprising; what is surprising is that the change is not a permutation of the four classes. Eight of the pool are L under normal play, and seven become R while one becomes P. Seven are R, and six become L while one becomes P.

The two exceptions are ⇑ and ⇓ — double-up and double-down, the infinitesimals below a star. Under normal play ↑ and ⇑ are both L, as plainly as any two positions in the subject are alike; under misère ↑ is an R-position and ⇑ is a P-position. That was checked twice, once by the site’s misère machinery and once by an independent recursion written to disagree with it if it could.

So there is no relabelling. Not even the single-position map from normal outcome to misère outcome is a function, which is a strictly stronger failure than the one the tables measure.

Those two exceptions suggest a last experiment, and it produces the one result on this page that runs the other way. Take a pool with no numbers and no switches in it — the nimbers and the small infinitesimals, the corner of the value space ⇑ and ⇓ came from — and rebuild both tables over it.

That is not a crack in the result and it is worth saying why, because it looks like one. Four determined cells over a hundred sums is what the whole essay has spent its length calling an artefact — the misère cell N + N was determined over the ten-position pool and stopped being at twenty-six. What is different here is only that the artefact is legible: this pool is closed under negation, and every position in it is infinitesimal, so no sum of two of them can be a number. A corner produces a rule about the corner. The nine normal-play cells are the same nine in every pool on this page that reaches all sixteen, and no misère cell has been the same in two.

Every number above comes from one piece of machinery — the misère evaluator — and from an explicit finite search rather than from a theorem.

The tables. normalSumTable(pool) and misereSumTable(pool) take a list of positions, form all ordered pairs, add each pair with the site’s ordinary game arithmetic, and record which outcomes appeared in each of the sixteen cells: 676 sums per convention on the twenty-six-position pool, 100 on the ten-position default. The counts come out 9 determined and 7 ambiguous for normal play at both sizes, and 1 / 15 then 0 / 16 for misère.

The misère outcome of a single position comes from a recursion differing from the normal one in exactly one place: a player with no moves is scored a winner rather than a loser. Flipping that one constant back reproduces the normal-play outcomes, which is the check that both columns of every figure here are the same code answering two questions.

The witness searches are exhaustive over their stated range. nimSeparation({maxHeap: 4, maxHeaps: 4}) walks all 69 non-empty Nim positions of at most four heaps of at most four counters, takes every pair sharing a misère outcome, and tries every position in the range as a third component: 1,278 witnesses, the cheapest by counters being the one drawn above. misereSeparation does the same over the twenty-six-position pool and finds 880 witnesses under misère and 864 under normal play, with 1, 2, −1 cheapest under both.

The mirror check is misereMirror(): eight sums G + (−G), of which 8 of 8 are worth zero and are second-player wins under normal play against 0 of 8 second-player wins under misère. The figure throws rather than draws if any row disagrees, which makes it a test the claim could fail.

Where the search stops being evidence #

Three limits, and the first is the one that decides how the headline may be read.

Ambiguity is a lower bound, never an upper bound on determinacy. A cell showing one outcome over 676 sums might hold two over a larger pool — which is precisely what happened to the misère cell N + N between the ten-position and twenty-six-position pools. So “0 of 16 under misère” is a floor a wider search can only confirm, while “9 of 16 under normal play” would be fragile if it rested on the search, and it does not, because those nine are proved.

The pool is not closed under negation. Four of the twenty-six — {3/4|1/4}, { {2|0}|0}, {0|{0|−1}} and {1|∗} — have negatives that are neither in the pool nor equal to anything in it. So where the misère table treats L and R asymmetrically, that asymmetry is a fact about the pool rather than about the convention, and the way to find out how much of it is is to put the four missing negatives in and look again.

Nothing about the headline moves: nine determined under normal play, none under misère, on thirty positions as on twenty-six. What moves is the shape of the residue, and it moves in the direction a reader ought to be able to predict, which is the point of running it. A pool that is not closed under negation cannot tell a fact about Left from a fact about the list, and a table read without that check will report the list.

And the Nim search is bounded in both dimensions. Four heaps of at most four counters is 69 positions; a pair separated by nothing in that range might be separated by a fifth heap.

The repair that exists, and what it costs #

Something does grow back where the value theory was, and its shape is the last thing to say.

The misère quotient is the repair, and it is an impartial construction: fix one impartial game, look only at disjunctive sums of that game’s own positions, and group positions that no sum within that universe can tell apart. The classes form a commutative monoid, and inside it the outcome of a sum is determined by the classes of the parts — additivity restored, at the price of the universe.

The price is in the phrase within that universe. Equality in the normal-play sense means agreement in every company, and a misère quotient buys agreement in a stated one. It is a repair per game rather than a theory of sums.

The price is measurable and it is charged even in Nim. Over heaps of at most three — all eighty-four positions of at most six heaps, told apart by sums of at most four — the quotient needs six classes where normal play needs four, and the two extra ones are two refusals: heaps 2, 2 are worth nought under normal play and would sit with the empty position, and 2, 3 is worth ∗1 and would sit with a single heap of one. Under misère neither identification is safe, and a monoid two elements larger is what refusing them costs.

Even Nim, whose misère theory fits in a sentence, needs six classes where normal play needs four. For a game whose positions are not all tame the count rises with the size of the universe rather than of the position — what misère play costs, and how far the counts climb is a different kind of expense from anything normal play charges.

Who noticed, and when #

Misère Nim was solved in the paper that solved Nim: Bouton’s 1902 account gives both endings, and the misère rule is short enough that it reads like a footnote rather than a warning.

That shortness cost the subject decades. The general theory arrived with Grundy and Smith in 1956, in a paper whose title states the problem exactly — Disjunctive games with the last player losing — and whose machinery is the genus, a Grundy value with a tail of misère information attached. The genus works completely on games all of whose positions behave like Nim heaps, and says nothing reliable about the rest.

Conway’s On Numbers and Games (1976) put the situation plainly: the misère theory of a game is a theory of that game, and there is no general one. The modern repair is Plambeck’s misère quotients, introduced in 2005 and developed with Siegel in 2008 — roughly a hundred years after the failure was first in print, and a construction per game rather than a theory.

What the picture cannot show #

The hero figure is two four-by-four grids of letters. It is the right drawing for a claim about sixteen pairs and it hides three things worth naming.

It cannot show a cell settled for a good reason beside one settled for a bad reason. The normal-play cell P + N = N is a theorem; the misère cell N + N = N on the small pool was a coincidence a wider pool erased. On the page they are the same mark, and only drawing the table over more than one pool separates them.

It cannot show absence. “No pair of misère outcome classes determines the sum” is a claim about every cell at once, and a claim about an absence has no picture beyond the shading. The strongest sentence on this page is one number wide.

And it cannot show a bound. Every cell is a set of outcomes reached by this pool, and the figure cannot draw the difference between “this holds” and “nothing in 676 sums contradicted it”. That distinction lives in the prose.

The convention, named #

Both conventions are on the page at once here, which is unusual for this site, so both should be said out loud.

Normal play: the player who cannot move loses. Every value on this site, every thermograph, every Grundy value and the whole of the arithmetic assume it.

Misère play: the player who cannot move wins. The games, the positions and the move graph are the same; what changes is one scoring constant at the leaves — and, downstream of it, whether the subject has a theory of sums.

Two further conventions are load-bearing in the figures. The pools are explicit finite lists, so every cell states what those lists reached. And the quotient figures compute over sums of at most a stated number of heaps, distinguished by sums of at most a stated number — a bounded universe, within which the class counts are counts.

Where the ladder goes next #

The misère anchor has three essays beneath this one and several obvious rungs above it.

The canonical form that exists and is useless. Misère games do have canonical forms, and the simplification theory that reduces a normal-play game to a small unique tree survives in a badly weakened version: some reversible moves may be bypassed, dominated ones removed, and what comes out is still enormous. A rung measuring how enormous would give the third row of the what reversing the ending destroys table the essay it does not yet have.

The universes that behave. Misère quotients are computed per game here, but there are whole classes of games — dead-ending games, and partizan universes closed under the operations that matter — in which comparison behaves again. That is the frontier, and the rung where misère play stops being a list of losses.

Which cells a wider pool would rescue, if any. The misère table’s four near-miss cells hold two or three outcomes rather than four. Whether they survive a pool of a hundred positions is a computation this site can run, and the expected answer — that they do not — is a prediction the machinery could refuse.

And the genus, the partial repair this essay did not use. Tame and wild opens that anchor at the bottom; its next rung is the demonstration that the genus is not a complete invariant either, with a witness in Kayles at nineteen counters. Between the outcome class, which settles nothing, and the quotient, which settles everything inside a universe, the genus sits in the middle — and knowing what sits where in that middle is what the misère theory has instead of a theorem about sums.