Combinatorial Game Theory
who wins, and by how much
Where it stops

Misère play

Change one word — the player who cannot move wins — and the games are identical, the strategies are not, and almost every theorem on this site stops being true. It is the cheapest possible modification and the most expensive.
15 min read 6 figures The theory runs outWho moves lastThe sum is the object

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 reversing the ending destroysEverything that makes normal play tractable is a theorem about who moves last, and misère play contradicts every one of them. The positions are unchanged; the machinery for evaluating them is gone, and what replaces it is far heavier.normal playmisère playevery impartial position is a Nim heapno such reduction existsequal games can be swapped in any sumonly within a restricted universethe value is a single small integeran element of a quotient monoida canonical form exists and is uniquecanonical forms are enormousthe game is what mattersthe game is what mattersmisère quotients recover some of it, one game at a timeand there is no general theory, which after fifty years is a real result rather than a gap
Fig. 1 What holds under each convention. Every load-bearing statement of the normal-play theory is in the left column, and only one of them survives the move to the right.

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.

The same game, the opposite endingNim under normal play, where the player who cannot move loses, and under misère play, where they win. The positions are identical and only one class of them changes hands — which makes misère Nim look easy and is deeply misleading about misère play in general.heapsnormalmisère1, 1, 1NPthe answer flips1, 2, 3PPunchanged1, 1, 1, 1PNthe answer flips2, 2PPunchanged1, 1, 5NNunchangedmisère Nim differs only when every heap has one counterwhich is a special property of Nim, and not a feature of misère play at all
Fig. 2 Normal and misère Nim compared. Only the endgame differs, and only in one family of positions — which makes misère Nim look like a footnote and is thoroughly misleading.

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⊕1⊕1=11 \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.

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.

The same game, the opposite endingNim under normal play, where the player who cannot move loses, and under misère play, where they win. The positions are identical and only one class of them changes hands — which makes misère Nim look easy and is deeply misleading about misère play in general.heapsnormalmisère1, 1, 1NPthe answer flips1, 2, 3PPunchanged1, 1, 1, 1PNthe answer flips2, 2PPunchanged1, 1, 5NNunchangedmisère Nim differs only when every heap has one counterwhich is a special property of Nim, and not a feature of misère play at all
Fig. 3 The positions where the answer flips, and the positions where it does not. Only the all-ones family changes hands, and everything else is the normal-play analysis untouched.

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.

A position is the sum of its partsFour separate Hackenbush sprigs. A move is a move in one of them, so the position is their disjunctive sum, and its value is the sum of their values. Which part to play in is the entire decision, and the values are what makes it decidable.2+-1+1/4=5/4outcome Leach sprig is a separate game; a move is a move in one of themthe total was computed by adding the games, not the labels
Fig. 4 Decomposition, which is the operation misère play denies. Under normal play these components’ values combine without reference to one another; under misère play the combination depends on what else is present.

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 Nim heap of size one, two of them, and so on.

Written gg0g1g2…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. Kayles is tame; Dawson’s chess is not. 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.

Which questions are answerableThe theory is exact and much of it is expensive. Values are computable by definition; computing one for a position of any size is a different matter, and deciding the winner of a generalised board game is complete for PSPACE — as hard as anything solvable in polynomial space.the value of a Nim positioninstantthe Grundy value of a small subtraction gamelinearthe canonical form of a moderate positionexponential in theorywho wins a general Domineering boardno efficient methodwho wins a generalised board gamePSPACE-completecostthe definitions are constructive, so everything here is computable in principleand the practical range of an exact evaluator is a few dozen moves, which is the working constraint
Fig. 5 The scale of the difference. Normal-play analysis reaches a certain size; misère analysis of the same game reaches very much less, and the gap widens with the game.

What the solver computed

lib/cgt.js evaluates 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. scripts/valuecheck.mjs 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 the gate fails the build if any disagree.

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 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.

Nim with heaps of 1, 1, 1Heaps of counters; a move takes any number from one heap. The position is a loss for the player to move exactly when the binary digits of the heap sizes cancel in every column — the nim-sum — and that is the whole of the theory of Nim.100110011001nim-sum001= 1some column does notthe player to move winstake 1 from the heap of 1outcome N
Fig. 6 The position where the two conventions differ. Three heaps of one: the nim-sum says the first player wins under normal play, and under misère play the same position is a loss.

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.

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+GG + 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.

The ladder from here

Nearby: the genus computed and its failure exhibited; misère quotients built for a small octal game, element by element; tame and wild games separated; and the misère analysis of Dawson’s chess, which is the standard hard case.

Then to the other two boundaries — loopy games, which break the induction rather than the ordering, and complexity, which leaves every theorem true and puts the answers out of reach. Three different ways for a theory to run out, and misère play is the one that costs the most for the smallest change.

Where this goes next

0outcome P= 0whoever must move, loses10outcome L> 0Left wins, whoever starts-10outcome R< 0Right wins, whoever starts∗00outcome N‖ 0whoever moves first, winsblue edges are Left's moves, red are Right'sthree of the four are comparisons with zero; the fourth is not Who moves last The player who cannot move loses. That single convention generates the whole theory — and it produces four outcomes rather than three, because a position can be confused with zero rather than greater, smaller or equal to it. a heap of 10, taking 1, 3, 4options lead to heaps of 9, 7, 6whose values are 0, 0, 2mex of those is 1plays exactly likea Nim heap of 1= ∗the value is the heap size — nothing else about the position survives Every impartial game is a Nim heap Sprague and Grundy proved, independently and four years apart, that any position in any impartial game is equivalent to a single heap of counters. Not similar to one — equal to one, interchangeable with it inside any larger game. the value of a Nim positioninstantthe Grundy value of a small subtraction gamelinearthe canonical form of a moderate positionexponential in theorywho wins a general Domineering boardno efficient methodwho wins a generalised board gamePSPACE-completecostthe definitions are constructive, so everything here is computable in principleand the practical range of an exact evaluator is a few dozen moves, which is the working constraint How hard is it Every theorem on this site stays true at any size. The answers stop being reachable long before the games get interesting — deciding the winner of a generalised board game is PSPACE-complete, and an exact evaluator gives out after a few dozen moves.