Misère play

Every rule stays. Every position stays. Every legal move stays. One clause is reversed:

The player who cannot move wins.

That is misère play, and it destroys most of the theory.

What breaks first #

Under normal play, having more options cannot hurt. That is the monotonicity lemma, and it is used silently everywhere: it is why dominated options can be deleted, why a bigger heap is better, why the ordering behaves.

Under misère play it is false. An extra option can be exactly the thing that forces a player to make the last move and lose. Being able to move is now a liability as often as an asset.

Everything downstream falls. The ordering stops being compatible with addition. Dominated options cannot be deleted. Canonical forms as constructed do not exist. And the substitution theorem — that equal games are interchangeable in any context — fails, which is the fatal one.

The equivalence failure #

Under normal play, two games are equal when their difference is a second-player win, and equal games can be exchanged anywhere with no effect. That single fact is what makes values worth computing.

Under misère play, the analogous relation is not a congruence. Two positions can be indistinguishable when played alone, and distinguishable when added to a third.

The consequence is that there is no useful notion of “the value of a misère position” independent of what it might be added to. A misère analysis has to be relative to a universe of positions the component might meet, and changing the universe changes the analysis.

That is the difference between a theory and a case-by-case study, and it is why misère play was regarded as intractable for seventy years.

Misère Nim, and why it misleads #

Nim is the exception, and it does more harm than good.

The misère Nim rule: play as in normal Nim until all heaps but one have size one. Then take the whole of the last big heap, or all but one of it, whichever leaves an odd number of size-one heaps. If every heap already has size one, leave an odd number.

That is the entire modification: one special case at the very end, triggered only when at most one heap exceeds size one.

Everybody who meets this concludes misère play is a minor variation. It is not. Nim’s misère solution works because Nim heaps are unusually well behaved — the position where the special case fires is easy to recognise and the rest of the game is untouched. No other game of interest has that property.

Kayles, Dawson’s chess, and essentially every octal game have misère versions with no comparable description. The misère analysis of Dawson’s chess took decades of work after the normal-play version was routine.

Three heaps of one #

The smallest position where the conventions disagree is worth naming, because it is the whole of misère Nim in one line.

Three heaps of one counter. The nim-sum is $1 \oplus 1 \oplus 1 = 1$, so under normal play the player to move wins — take one heap, leaving two, which is balanced.

Under misère play there is no winning move at all. Every move from three heaps of one leaves two heaps of one — that is the only kind of move available. The opponent then takes one, leaving a single counter, and the mover must take it. Taking the last counter is a loss under this convention, so the player who moved first from three heaps of one loses.

So three heaps of one is a first-player win under normal play and a first-player loss under misère. Same position, same rules, opposite answers.

Four heaps of one reverses again: the mover wins, by taking one and leaving three. The parity of the count of size-one heaps is the entire content, which is why the misère rule has the shape it does.

It is worth going below three, because the disagreement does not begin there. A single counter is already a position the two conventions answer oppositely, and so is a pair of single counters, and a single heap of two is not.

So the arrangement of two counters decides whether the convention matters at all, which is a strange thing for a rule change to be sensitive to and is the first sign that the exception is about shape rather than about size.

Run the all-ones family up and the answer alternates, for ever, and every row disagrees with normal play.

Anything with a heap of two or more is unaffected, because the player who is ahead can always steer into the right parity at the moment the last big heap is broken up. That steering freedom is what Nim has and other games do not, and it survives however many single counters are piled beside the big heap.

A theory that does not localise #

The deepest way to say what goes wrong is in terms of what a value is supposed to be.

A value is a local summary. It describes a component, it is computed from that component alone, and it composes with other components’ values by an operation that does not consult the components again. That is what makes analysis by decomposition possible, and it is what the whole of the normal-play theory delivers.

Misère play resists localisation because the endgame condition is global. Whether an extra move helps depends on the parity of everything remaining — including components on the other side of the board, which the local analysis cannot see.

Misère quotients recover localisation by shrinking the world. Fix a single game, and within sums of positions from that game the parity information is constrained enough that a local value exists. Change the game and the constraint changes, so the values do not transfer.

That is a real theory and a modest one. It says: localisation is possible relative to a universe, and there is no universal universe. The normal-play theory’s claim — one value system for all games at once — turns out to have been a considerable piece of luck rather than the natural state of affairs.

Decomposition is the operation this denies. Putting two positions side by side and adding their values is how every analysis on this site is done, and the step that makes it legitimate is that each component’s value is computed without consulting the other. Under misère play the combination depends on what else is present, so a component cannot be evaluated before it is known what it will be standing beside — which is not a harder version of decomposition but the absence of one.

Genus theory, and its limits #

The first serious attempt at a general misère theory is the genus, developed by Conway and presented in On Numbers and Games and Winning Ways.

The idea is to attach more than one number to a position. A position’s genus records its normal-play Grundy value together with a sequence of misère Grundy values computed under successive perturbations — what happens when the position is added to one copy of $\ast2$, two copies, and so on. The perturbation is $\ast2$ and not a heap of one, which matters: with heaps of one the classification would be a different and weaker one.

Written $g^{g_0 g_1 g_2 \ldots}$, the genus is a Grundy value with a tail, and positions with the same genus behave the same in a restricted class of sums.

It works for a useful family of games — the tame ones, whose genus values are those of Nim heaps — and it fails for the rest. Nim is tame, as it must be; Kayles and Dawson’s chess are both wild, Kayles from its fifth heap and Dawson’s from its ninth. For wild games the genus is not a complete invariant, and computing it is expensive without settling the question.

So genus theory is a partial answer that identifies which games are easy and does not solve the hard ones.

Misère quotients #

The modern approach, and the reason misère play is no longer regarded as hopeless, is Thane Plambeck’s misère quotient construction, from around 2004.

The move is to give up on absolute values and localise. Fix a game — a specific rule set — and consider only sums of positions from that game. Within that restricted universe, the indistinguishability relation is a congruence, and quotienting by it gives a finite commutative monoid: the misère quotient of that game.

The quotient is the smallest algebraic structure in which the game’s misère positions can be evaluated. Each position maps to an element, elements multiply to give sums, and a designated subset of elements are the losing positions.

That is a genuine theory, and it works. Quotients have been computed for many octal games, some with a handful of elements and some with thousands.

What it gives up is universality. A misère quotient is a statement about one game; positions from different games cannot be added, because the quotients differ. The commensurability that Sprague–Grundy provides for normal play — all impartial games measurable on one scale — is simply gone.

The size of what that costs is measured elsewhere — what misère play costs puts the normal-play and misère analyses of the same game side by side and reports how far each reaches — and the short version is that the gap widens with the game rather than staying a constant factor.

What the solver computed #

The site’s evaluator handles normal play. It does not implement misère analysis, and the site does not claim misère values it has not computed.

What the figures do show is computed: the failure. For the positions in the misère figures, the code evaluates the normal-play outcome by the standard recursion and the misère outcome by a separate recursion that inverts the base case — a position with no options is a win for the player to move rather than a loss. Both are exact for positions this small.

For misère Nim the rule quoted above is verified rather than trusted. The site’s own gate runs a brute-force misère recursion — a position with no moves is a win for the player to move, and everything else is decided by whether some move leads to a loss for the opponent — over every position with at most four heaps of at most five counters. That is 126 distinct positions. The rule’s answer and the recursion’s answer are compared on all of them, and a single disagreement stops the figures being published.

Writing that check found a bug in the rule as this site first stated it. The version drafted here special-cased the empty position as a previous-player win, which is the normal-play answer; under misère play a player facing no heaps at all has no move and therefore wins. One position out of 126 disagreed, and it was the base case. The all-ones branch turns out to cover it correctly with no special case at all — zero heaps is an even number of size-one heaps — which is tidier as well as right.

That is a small error and it is exactly the kind misère play produces: a base case inverted, in a rule that looked obviously correct, caught only by running the recursion the rule was supposed to replace.

The moment the rule fires is worth drawing, because it is one move wide. From heaps of 1, 1, 2 the mover breaks up the last big heap and chooses what to leave behind.

The misère comparison table is not computed. It is a summary of what the literature establishes, and it is drawn as a table rather than dressed up as a derivation.

Nothing here computes a misère quotient. That would need machinery this site does not have, and the essay says so rather than gesturing at values it cannot produce.

Why the reversal costs so much #

It is worth asking why one clause does so much damage, because the answer is structural rather than accidental.

Normal play makes “having a move” unambiguously good. That single orientation is what lets options be compared, dominated ones deleted, and positions ordered — the whole partial order and everything built on it.

Misère play makes having a move good sometimes: good in the middle of the game, fatal at the end. The value of an option now depends on the parity of what remains, which is global information. A local analysis cannot see it, and the theory is built entirely out of local analyses.

So the failure is not that misère play is harder to compute. It is that the quantity the normal-play theory computes — a local value that composes — does not exist. Misère quotients work by rebuilding a local value for one game at a time, at the cost of the universality.

Where it matters #

Misère versions are played. The Nim variant is the standard bar game, precisely because the misère rule is more natural to a casual player: taking the last object feels like losing.

Misère Dots and Boxes, misère tic-tac-toe and misère chess variants all have followings, and misère Sprouts is standard among people who play Sprouts at all.

So the convention that breaks the theory is the one people often prefer, which is a slightly awkward fact for a subject that presents normal play as the default. The default is chosen because it works, not because it is more natural.

There is a reason the bar game is the one that inverts. The positions a casual game actually reaches are small, and small is exactly where the two conventions come apart — the nim-sum settles everything until the heaps run down to single counters, and then it settles nothing without the parity beside it.

Who found it, and when #

Bouton’s 1901 paper solved misère Nim alongside normal Nim, so the exception was known from the start.

Grundy and Smith attacked general misère play in the 1950s and produced the genus, which Conway systematised. On Numbers and Games and Winning Ways both cover it, and both are frank that it does not go far enough.

Plambeck’s misère quotient construction appeared around 2004, with Aaron Siegel developing the computational side. Siegel’s software has computed quotients for a long list of octal games, and the field went from “essentially hopeless” to “hard but tractable game by game” in about a decade — a rare thing in a subject where the open problems tend to stay open.

One clause, and why it reaches so far #

Reversing the ending condition changes one sentence of the rules and destroys most of the theory, and the disproportion is worth explaining rather than reporting.

Under normal play, the player unable to move loses makes a move a resource spent. Everything follows from that reading. A position where every move loses ground is a standoff, which is what a number is. A player answering in a mirrored copy always has a reply, which is why $G + (-G)$ is nought and why a negative exists. And the recursion is grounded because running out of moves is the end, so the base case is a verdict rather than a convention.

Reverse it and each of those reverses independently. A move becomes a resource a player wants to be out of. The mirror strategy still supplies a reply and the reply is now fatal, so the answerer loses and the negative goes. The base case flips, and every value built on it flips underneath its own construction.

So the clause is not a detail of the ending; it is the sentence the arithmetic is derived from. That is why the misère theory could not be adjusted — there is no parameter to change, because the affected object is the meaning of a move rather than a coefficient anywhere.

It also says what a reader should expect of any other convention change. A change to what happens when a player runs out is a change to the whole theory; a change to what moves are available is usually a change to one game. The first kind is rare and this is the standing example; the second kind is what most of this site’s variants are, and it is why they stay inside the apparatus.

What survives the reversal #

For completeness, the short list of things that do carry over.

The games themselves. Every position, every move, every game graph is identical. Only the labelling of terminal positions changes.

Termination. A short game is short under either convention, so the recursion still bottoms out and every position still has a determined outcome. Misère play is decidable; it is the composition that fails, not the decision.

The outcome classes. Four of them, defined the same way, and every position still falls into exactly one.

Symmetry arguments. A position of the form $G + G$ is still a second-player win under misère play for impartial games, by the same mirroring — the copier is never the one without a move.

What does not survive is everything that makes those facts useful together: the values, the ordering, the substitution theorem and the reduction to a single scale. The pieces are all there and they no longer fit.

That is a precise and rather unusual kind of failure. The theory is not approximately true under misère play, or true with corrections, or true for most positions. It is true for exactly one game, and the game is Nim.

Where the model stops #

This site computes normal play. The misère figures show computed failures and computed outcomes for small positions; no misère value system is implemented.

Misère quotients are per-game. No universal value system exists and none is expected.

Genus theory covers tame games only, which excludes most of the interesting ones.

Misère Nim is not evidence. It is the exceptional case and it is the one everybody meets first.

Everything else on this site assumes normal play. Every theorem quoted elsewhere should be read with that hypothesis attached, and almost none survive without it.

Where the ladder goes next #

misere opens here with the convention: the player unable to move wins, one clause changed, every position exactly as it was.

Misère quotients is what replaces the missing arithmetic — a monoid computed per universe rather than a value per position — and hopeless was a claim about a method is the historical correction that goes with it: the 1970s verdict of intractability was right about what was being attempted, and quotients did not refute it so much as change the question.

The three rungs after that measure what the convention destroys, and they measure it at three levels. Misère play has no negatives is the loss at the root: put a position beside its mirror image and the answerer still has every reply and loses because of it, so there is no zero, no subtraction and no comparison.

Two misère outcomes are not enough is the same loss one level up. Nine of sixteen pairs of outcome classes settle a sum under normal play and not one of the sixteen settles it under misère — and the nine that work are theorems about a value being nought, which is exactly what has just been shown not to exist.

And what a wider pool rescues removes the last apparent structure. Over a small pool fifteen of the sixteen cells look constrained; widen it and every cell takes every outcome, while the normal-play control does not move at all — because its empty cells are shut by theorems and a theorem is not embarrassed by more examples.