"Hopeless" was a claim about a method

Under misère play the player who cannot move wins. It is a one-word change to the rules — normal play says the opposite — and it destroys the theory.

Conway’s assessment in On Numbers and Games is often quoted as a verdict that misère analysis is hopeless. The assessment was accurate, and the reason it was accurate is more interesting than the fact: it was a claim about a specific question, and the question was the wrong one.

What normal play gives, and what misère takes away #

Under normal play every impartial position has a single number — its Grundy value — and that number is complete: two positions with the same value are interchangeable in any sum, alongside any other games, for ever.

That is an enormously strong property and it is easy to stop noticing. It means the analysis of a game can be done once, in isolation, and reused everywhere.

Under misère play it fails. Two positions can behave identically on their own, and differently when placed beside a third game. So there is no number that summarises a position, because summarising means “safe to substitute” and substitution is exactly what breaks.

Why the obvious repair does not work #

The natural first attempt is to compute misère Grundy values — the same mex recursion with the base case inverted — and it produces numbers.

The numbers are useless. They give the outcome class of a single position correctly and they do not add: the misère value of a sum is not any function of the misère values of the parts. So the whole apparatus that makes normal-play theory worth having is absent, and what remains is a table of answers for individual positions with no way to combine them.

That is the situation Conway was describing, and hopeless is a fair word for it. Computing an answer per position, in a subject whose entire subject matter is sums, is not a theory.

There is one case where it does not look like that, and it is the case everybody meets first. Misère Nim has a clean answer: play by the ordinary criterion until a move would leave every heap at a single counter, and then leave an odd number of them instead of an even one. One clause, appended to a theorem from 1901. It is the last thing about misère play that fits in a sentence, and its shortness is what made the general problem look like a variant rather than a different subject.

What exactly breaks, in one position #

The general statement — misère values do not compose — is easier to believe with the smallest instance in front of it.

Under normal play, a Nim heap of 1 and a Nim heap of 2 are worth ∗1 and ∗2, and any position worth ∗1 may be substituted for that heap of 1 anywhere. Under misère play, ask what a heap of 1 is worth and the answer is: it depends what else is on the table.

Beside nothing, a heap of 1 is a win for the mover — they take it, the opponent cannot move, and under misère play the player who cannot move wins, so the mover has lost. Beside a second heap of one the verdict inverts, because now the mover is the one who takes the second-to-last counter. Beside a heap of two it inverts back. So a “value” for the heap of 1 would have to encode how it behaves against everything, which is not a number and is the object the quotient construction produces.

The cost of that encoding is measurable in the friendliest game there is, which is the sharpest form of the point.

Ten against eight is a small number and it is the wrong kind of small. It is not a rounding error on a theory that mostly works; it is the statement that the Grundy value — complete, absolute, computed once and reused for ever — is not a complete answer even here.

What quotients changed #

The repair, worked out largely by Thane Plambeck and Aaron Siegel in the 2000s, does not find a better value. It changes what is being asked.

Instead of what is this position worth?, ask: given a fixed collection of games — a universe — which positions are interchangeable within it? That is an equivalence relation, the equivalence classes form a monoid under the disjunctive sum, and that monoid is the misère quotient of the universe.

The change is precise and worth stating exactly. Normal play has one theory covering all impartial games at once. Misère play has a theory per universe, and a position’s class is meaningful only relative to the universe it was computed in.

What a quotient looks like when it is small #

The construction is worth seeing at a size where it works, because “a monoid per universe” is abstract until there is one on the page.

For Nim itself, restricted to heaps of at most two, the quotient is small: six classes with a multiplication table that fits in a box. Every position of that universe falls into one of the six, the class determines the outcome, and the table determines the class of any sum. That is a complete misère theory of that universe, and it does everything the normal-play theory does — for the universe it was computed in and nowhere else.

The comparison with normal play is the thing to take away. Normal play does not need a table because the operation is exclusive-or and the classes are the nimbers, once and for all. Misère play needs a table, and a different one per universe.

Small is not the general case, and the game that shows it is the standard first example of one that misbehaves. Kayles — knock down one pin or two adjacent pins from a row — is wild: its positions do not all imitate Nim heaps, which is exactly the property the older misère machinery needed.

Kayles is worth having on the page because it removes an easy reading of the earlier figures. The normal-play line is not flat because normal play is trivial; it is flat once the Grundy values are exhausted, and here it climbs first. What separates the two conventions is not that one count moves and the other does not — it is that the normal-play count is bounded by the game and the misère count is bounded by the universe, and a universe can always be made wider.

The surprise: the cost is in the closure #

The thing that makes quotients expensive is not the positions. It is that a universe has to be closed under the sums of its own members.

Take a game, take all its positions, and start adding them together. The sums are also positions in the universe, so their sums are in it too, and the collection grows until it stops — if it stops. For some games it stops quickly and the quotient is small; for others it does not stop at any size anybody has computed.

That is the shape of the cost, and it is the subject of its own essay. What matters here is that it explains why the 1970s verdict was right: the object that behaves like a value is the quotient, and the quotient was not computable by hand for anything interesting.

Why the misère analogue of canonical form is so much worse #

Normal play has a reduction: remove dominated options, replace reversible ones, and what is left is the canonical form — unique, and reached in any order. It is the machine that makes values finite objects small enough to write down.

Misère play has a reduction too, and it barely reduces. The theorem that lets a normal-play reduction remove an option depends on the option being never worth taking in any sum, and under misère play far fewer options qualify, because the endgame inverts and a move that is bad everywhere else is good at the end.

The practical consequence is that misère canonical forms are enormous. Positions that reduce to ∗2 under normal play reduce to trees with dozens of nodes under misère play, and the trees grow with the position rather than collapsing. What the normal-play reduction does — strike out a dominated option, bypass a reversible one, and leave a small unique form behind — is what misère play does not get, and the class counts on this page are the compression that went missing measured from the other end.

That is the mechanical reason behind the verdict. It is not that anybody lacked ingenuity; it is that the tool that makes the normal-play theory tractable does almost no work in the misère setting, and the quotient construction is a way of getting the compression back by fixing a universe rather than by reducing a form.

One missing thing accounts for all of it #

The failures listed above — no composing value, almost no reduction, a theory per universe — read as four separate misfortunes. They are one, and naming it makes the quotient construction look inevitable rather than ingenious.

Misère play has no negatives. There is no $-G$: the position that mirrors $G$ does not cancel it, and $G$ plus its mirror is not a second-player win. So the games under the misère sum form a monoid rather than a group — an operation with an identity and no inverses.

Everything else follows from that in one chain.

No negatives, no difference. $G - H$ is written using $-H$, so without inverses the expression does not exist.

No difference, no order. Comparison on this site is a subtraction: $G \geq H$ means Left wins $G - H$ moving second. Take the subtraction away and there is no relation left to compute — not a harder one, none.

No order, no domination. An option is dominated when another is at least as good, which is a comparison. With no comparison there is nothing to test, so the reduction that removes dominated options has no criterion to apply, and reversibility — which is also stated as an inequality — goes with it.

No reduction, no canonical form. Which is the section above, arrived at as a consequence rather than reported as an observation.

And the first item on the list falls out too: a value is a thing safe to substitute, substitution is licensed by equality, and equality here was defined as a two-way inequality. Remove the order and the word value has nothing to denote.

Which is what a universe puts back, and what it costs #

Read that way, the quotient is not a clever alternative to the value. It is the smallest repair that restores the one missing ingredient.

Fix a universe $U$ and define $G \succeq H$ to mean: for every $X$ in $U$, the outcome of $G + X$ is at least as good for Left as the outcome of $H + X$. That is an order, domination becomes testable again, equivalence classes exist, and the classes form a monoid with a multiplication table — the whole apparatus, back.

But look at how the order was defined. Normal play gets it from a single difference game, computed once, with no reference to anything else. The misère version gets it from a quantifier over the universe, and a quantifier has to range over something closed, or a sum could leave the collection the comparison was checked against.

So the closure is not an implementation detail; it is where the missing inverses are being paid for. Normal play’s group structure buys the quantifier off — “for every $X$” collapses to “the difference is a second-player win”, because $X$ cancels — and misère play, having no cancellation, must actually visit every $X$. The essay’s observation that the cost is in the closure is that trade, and the class counts climbing with the size bound are the bill.

It also explains why the quotient is relative and cannot be otherwise. The order was defined against a universe, so it is an order about that universe, and a position moved into a larger one is being compared against tests it has never taken. A normal-play value is absolute because its defining test quantifies over everything and cancels down to one game; a misère class is relative because its defining test quantifies over everything and does not.

What the verdict got right, and what it did not anticipate #

Conway’s assessment was about the question everybody was asking, and about that question it was correct and remains correct: there is no misère value per position that composes, and there never will be, because the composition fails for structural reasons.

What it did not anticipate is that the failure is localisable. Restricting attention to a universe recovers enough structure to do arithmetic in, and for many specific games the universe is small enough to write down. That is a genuine theory with genuine results, and it is not a refutation of the verdict — it is a different question with a better answer.

The general lesson is one this field keeps producing: an impossibility result is always relative to a formulation, and the productive response to one is often to change what is being asked rather than to try harder at the original.

What the growth figure is actually measuring #

The number at the top of this page needs its units stated, because “how many classes” is ambiguous in a way that matters.

A quotient’s size depends on two parameters, not one: how large the individual positions are allowed to get, and how many of them may be added together. Widening either grows the universe, and the class count is a function of both. A figure reporting a single number for a game is reporting a number for a choice of both bounds.

The second bound is the one a reader is likeliest to skip past, and it is not a detail of the computation. Run the same game again with the sums narrowed from four heaps to two.

Two figures of one game, differing in a bound that appears nowhere in its rules, and the misère answer is twelve in one and seven in the other. Neither is wrong. A quotient is the quotient of a universe, and the universe is the pair of bounds; a class count quoted without them is a number with no question attached. That the normal-play line sits at four in both is the control, and it is what a value being absolute looks like when it is measured rather than asserted.

A count that is still climbing at the edge of the computation says nothing about whether it stops. That is the same caution as everywhere else on this site about a search that has not found something, and it applies here with particular force, because a quotient that fails to close is the difference between a game having a misère theory and not.

Where the model stops #

Every quotient computed here is bounded by its universe’s size. The figures state the range, and a quotient reported as having $n$ classes is a statement about closing the universe within a computed bound.

And the theory is impartial-only, in the same sense that Sprague–Grundy is. Misère partizan games are worse again: there is no analogue of the quotient construction that anybody has made work, and the normal-play theory’s own extension to partizan games has no misère counterpart. So the repair described here fixes one of the two things misère play breaks.

What the picture cannot show #

A quotient’s multiplication table looks like arithmetic, and it is arithmetic — but it is arithmetic in an object with no numbers in it. The classes have names because they need names, not because they are quantities, and there is no ordering, no size, and no meaningful comparison between the class of one position and the class of another.

That is unlike everything else on this site, where a value is at minimum comparable with zero. A figure showing a table of symbols cannot convey that the symbols are not measurements.

Why “hopeless” is worth defending #

It has become slightly fashionable to treat the 1970s verdict as an example of a great mathematician being too pessimistic. That reading is wrong and worth correcting.

The verdict was about a specific, well-defined question — is there a value per position that composes — and the answer to that question is no, and remains no, and is not a matter of effort. Nothing in the quotient theory contradicts it.

What the quotient theory does is decline the question. That is a real contribution and it is a different kind of contribution from answering it, and conflating the two teaches the wrong lesson: that persistence beats an impossibility result. It does not. Changing the question beats an impossibility result, and knowing which question is impossible is what identifies the one to change.

Who found it, and when #

The misère problem is as old as the normal-play theory — Bouton solved misère Nim in 1901, in the same paper — and the general difficulty was clear by the 1970s.

Misère quotients date from Plambeck’s work in the early 2000s and Plambeck and Siegel’s joint work later in the decade. The construction is a genuine reframing rather than an incremental improvement, and it is one of the few places in this subject where a thirty-year-old verdict of hopelessness turned out to be answerable by asking something else.

The shape of the reframing, stated generally #

It is worth extracting the move, because it is transferable and this subject has used it more than once.

The original question was: what is the smallest object that summarises a position, safely, in every context? The answer is that there is none.

The replacement question is: fix the contexts, and then ask. With the contexts fixed the answer exists and is often small.

That is the same manoeuvre as restricting a theorem’s hypothesis to recover a conclusion, and it appears elsewhere here in a different costume: complexity results are stated per family and per encoding for exactly the same reason, because “how hard is this game” has no answer and “how hard is this family under this encoding” does.

In both cases the reframing is not a weaker result. It is a different one, and the temptation to read it as a partial version of the impossible original is what makes people call it a workaround.

A last measurement worth keeping #

One number from the survey is worth stating on its own, because it is the compact form of everything above.

For a game where the quotient closes, the normal-play analysis needs one class per Grundy value — a handful — and the misère analysis of the same positions needs several times as many, with a multiplication table rather than an operation. The ratio is the price of the convention change, and it is charged per game rather than once.

That is the honest summary of what thirty years of work bought: not a way of avoiding the price, but a way of computing it, and a demonstration that for many games it is finite.

Where the ladder goes next #

The rungs below are misère play and misère quotients as objects. This rung is what the reframing cost and bought. The direction onward is toward the cases where even the quotient does not close, and toward the partizan side, where nothing of this applies at all.