What survives misère play

Under normal play, an impartial position is worth a Nim heap. All of them are: that is the Sprague–Grundy theorem, and it collapses every impartial game ever invented into arithmetic on small integers.

Under misère play — the player who cannot move wins — there is no such theorem, and the failure is not a technicality. Two positions with the same Grundy value can behave completely differently in a misère sum, so a value in the normal-play sense does not exist at all.

What replaces it is smaller, stranger, and computable only one game at a time.

Giving up on a universal theory #

The normal-play theorem works because of one fact: every impartial game is equivalent, in every sum whatsoever, to some Nim heap. The equivalence is universal — it holds against any background, drawn from any game.

Misère play has no such universality. The standard demonstration is that a single heap of two under misère Nim and a single heap of two under a different octal game may be indistinguishable when added to positions from their own game and distinguishable when added to positions from each other’s.

So the misère theory abandons universality and keeps everything else. Fix a game $\Gamma$. Look only at sums of positions from $\Gamma$. Within that restricted world, ask the same question: when do two positions behave identically in every sum?

$$G \equiv H \iff \text{outcome}(G + X) = \text{outcome}(H + X) \text{ for every } X \text{ from } \Gamma.$$

That is an equivalence relation, the classes form a commutative monoid under addition, and the monoid is the misère quotient of $\Gamma$. For some games it is finite and tiny. For others it grows without any known bound.

Reading the table #

The figure is the quotient of misère Nim restricted to heaps of one and two.

Six classes. The identity is the empty position, written $1$ in the table because it is a multiplicative identity. The others are named by the smallest position in each class, so $\{1\}$ is the class of a single heap of one, $\{2\}$ the class of a single heap of two, and so on.

The shading marks the classes that are losses for the player to move. Under normal play there is exactly one such class — the positions worth zero — and here there are two, which is the first sign that something has changed structurally rather than just numerically.

$$\text{normal play: } 4 \text{ classes} \qquad \text{misère play: } 6.$$

Where do the extra two come from? Under normal play, misère Nim’s positions are sorted entirely by their nim-sum, which for heaps of at most two ranges over four values. Under misère play the answer additionally depends on whether every heap has exactly one counter, because that is the case where the rule flips — and “all heaps are one” is not a function of the nim-sum.

So the extra classes are exactly the positions the nim-sum cannot distinguish from each other and misère play can: a collection of ones with even count, and one with odd count, both of which have their own behaviour.

That is the misère Nim rule read off an algebra instead of off a sentence. The rule says the answer flips exactly when every heap holds a single counter; the table says the same thing by needing two classes where the nim-sum offers one, and by shading both of them.

The friendly game grows too #

Six classes against four is a small enough excess to be dismissed as the price of one exception. It is not a fixed price, and Nim itself is where that shows first.

Widen the universe from heaps of at most two to heaps of at most four and the normal-play answer doubles, because the Grundy values available double: four values become eight. The misère answer does not merely double with it.

The two extra classes are the same two extra classes, and that is the good case. It is what a game with a describable exception looks like: the exception costs a fixed amount and widening the universe does not find more of it.

It keeps growing #

Misère Nim is the easiest case in the subject, and it is easy because the exception is small and describable. Most games are not like that.

The normal-play line flattens because the Grundy values of the game are bounded — once the largest value has appeared, a wider universe cannot produce a new class, since a class is a Grundy value and there are no more.

The misère line does not flatten, and the reason is that misère equivalence has no such bound to hit. Every widening of the universe brings in positions that can serve as new tests, and every new test can split a class that had held together.

The line cannot come back down, and that is worth saying because it is a property of the computation rather than of the game. A wider universe contains every test the narrower one contained, so it can only separate more positions. Anything else would be a bug.

A second game, and a wider gap #

Nim is the friendliest case and it understates the situation. Dawson’s chess, the octal game $\cdot 137$, is more typical.

The difference between the two games is the difference between an exception and a phenomenon. Misère Nim’s extra classes come from one identifiable special case, statable in a sentence and provable in a paragraph. Dawson’s extra classes come from nothing in particular — they are what happens when the ordering that made positions comparable is removed and each position has to be tested against every other.

Both of those tables still have exactly two shaded classes, though, and that is worth noticing before it stops being true. A shaded class is a class of losses for the player to move, and normal play has precisely one of them, because a loss for the mover means a value of zero and there is only one zero. Two is already an oddity. Kayles — the octal game ·77, and the standard first example of a game whose positions do not all behave like Nim heaps — is where the count goes further.

Three shaded classes is the sharpest small statement of what has been lost. Under normal play the losing positions are one class because they are one value, and every argument about zero — that adding it changes nothing, that a position equals another when their difference is a loss — is an argument about that class being a single thing. Kayles has three, they multiply into each other, and none of them is an identity.

That is why the quotient is presented as a table rather than as a formula. For misère Nim a formula exists; for almost every other game the table is the answer, and the table is what a computation produces.

That strip beside the Dawson table is the essay in two pictures. One line of integers against a multiplication table, for the same game, differing only in who wins when nobody can move.

What the solver computed, and how #

The quotient is brute force, and the bound is reported with the answer because the bound is part of the claim.

The universe is every multiset of heaps drawn from sizes $1$ to $H$, with at most $K$ heaps. The misère outcome of each position is computed by a recursion whose only difference from the normal-play one is the base case: a position with no move is a win for the player to move.

Two positions are then compared by their signatures. The signature of a position is the list of outcomes it produces when each test position in the universe is added to it. Positions with the same signature go in the same class.

The multiplication table is filled by adding representatives and looking up which class the sum falls into. Entries where the sum leaves the universe are marked with a dot rather than guessed at.

That construction has a precise and limited meaning, and the figure states it rather than hiding it. Testing against a bounded universe can only ever merge classes the true quotient would keep apart — a test that would have separated them may simply not be in the set. It can never split a class the true quotient joins. So the computed number of classes is a lower bound on the true one, and a growing sequence of lower bounds is exactly what the second figure shows.

The site’s gate checks two things about this machinery, and they pull in opposite directions. Misère Nim over the universe drawn must need strictly more classes than normal play — a bug that collapsed the misère outcome onto the Grundy value would fail. And widening the universe must never reduce the class count, at any of three widths — a bug in the signature comparison would show up as a count that wobbled.

Where the model stops #

A quotient over a bounded universe is not the quotient of the game. This is the most important sentence in the essay. Every table here is a quotient of the positions computed, and the true quotient of the game is what the computation is converging towards from below. The two are different claims and the figures say which one they are making.

The theory is one game at a time. There is no misère theory of impartial games, only misère theories of particular impartial games. A quotient computed for Dawson’s chess says nothing about any other octal code, which is precisely the universality that was given up.

Finiteness is not guaranteed. Some games have finite misère quotients — Dawson’s chess does, at a size in the hundreds, established by work considerably more careful than brute force. Some do not, and there is no general test. The situation rhymes with the periodicity question for octal codes: a property that holds in every case anybody has managed to settle, with no proof that it always holds.

Nothing here is a value. A class in the quotient is not a number and does not add like one. The monoid has multiplication and an identity and no inverses at all — a position’s negative does not exist, because there is no misère analogue of the mirroring argument that makes $G + (-G) = 0$ work. Nothing in the ordinary value theory transfers.

The list of what stopped working is longer than this page needs and every entry on it is a theorem about who moves last: the reduction to a single Nim heap, the licence to swap equal games in any sum, the small integer value, the unique canonical form. The quotient is what was salvaged, and the salvage is smaller than the wreck.

Why the monoid rather than a group #

The most instructive fact about the misère quotient is what it lacks.

Under normal play, values form an abelian group. Every game has a negative — the same game with the players swapped — and $G + (-G) = 0$, because whoever moves second can mirror every move across the two components. That single argument is the engine behind comparison, cancellation and the whole ordering.

Under misère play the mirroring argument fails, and it fails at the last move. Playing $G + (-G)$ second and copying every move, the mirroring player makes the final move — which under misère play is a loss. So $G + (-G)$ is not a second-player win, negatives do not exist, and the structure is a monoid rather than a group.

Everything else follows from that one loss. Without negatives there is no subtraction, so comparison by playing the difference is unavailable, so there is no ordering, so positions cannot be ranked and there is nothing for a value to be a value on. Canonical forms go with it, since the reductions that produce them are justified by comparisons that no longer exist. What remains is the multiplication table and the list of which classes are losses, and those two pieces of data are the whole theory.

What the table cannot show #

A multiplication table is an unusually complete kind of figure — every product is there — and there are still three things it does not contain.

It cannot show that the classes are right. Two positions are in the same class because no test in the universe told them apart. Whether a test outside the universe would have separated them is exactly the question the table cannot answer, and it is the question that decides whether the table is the game’s quotient or a coarsening of it.

It cannot show the positions. Each class is named by the smallest position in it, and every other member is invisible. A class containing a hundred positions and a class containing two look identical in the table, and for a player wanting to recognise a position on a board, the membership is what matters.

It cannot show the presentation. Large quotients are stated as generators and relations — a few symbols and a handful of equations — rather than as tables, because a table with several hundred rows is not readable. The table form is available exactly when the quotient is small, which is to say exactly when the game is easy.

That last figure is the caution in its sharpest form. A small table for a game nobody can analyse is not evidence that the game is simple; it is evidence that the universe drawn was narrow. The number of classes is a lower bound and the bound is printed beside it.

What replaces subtraction #

A quotient is usually met as a way of computing, and it is worth reading first as a replacement for a missing operation, because that says what it is for.

Under normal play, deciding whether two positions are interchangeable is a subtraction: form $G - H$ and ask who wins it. The whole apparatus of values rests on that one move, and misère play does not have it — there is no negative, so there is no difference to play.

What a quotient does is answer the same question by a different route. Instead of subtracting, it partitions: two positions land in the same class when no position of the universe tells them apart, and the classes are found by testing against the universe rather than by any arithmetic on the pair. The monoid’s multiplication table then records how the classes combine, which is the information the missing subtraction would have supplied.

The price of that substitution is visible in the shape of the answer. A subtraction is local — two positions in, one game out, no reference to anything else — while a partition is global, because a class is defined by what it is distinguishable from, and that is a fact about the whole universe. So changing the universe changes the classes, and there is no sense in which a class computed for one game means anything in another.

That is the whole content of “a quotient per universe” and it is a consequence rather than a design choice. Nobody chose to make misère analysis contextual; the operation that would have made it universal is not available, and the replacement is contextual by construction. The growth in the tables above is what that costs, measured — and it is why the theory is a computation rather than a body of theorems.

What it is good for #

The misère quotient is not a curiosity, although its size makes it look like one.

For a game with a finite quotient, having it is decisive. A player who knows the quotient can evaluate any sum of that game’s positions by looking up each component’s class and multiplying — the same service the nim-sum performs under normal play, at the price of a lookup table specific to the game.

For a game whose quotient is infinite, having the first several dozen classes is still useful, because real positions are small and the classes that occur are the early ones. That is a practical argument rather than a theoretical one, and it is the argument the working literature makes.

The deeper value is what the construction demonstrates about the subject. Given a theory that breaks, the productive response was not to patch it but to identify exactly which universality assumption was doing the work, drop it, and see what remained. What remained is game-specific, computable, and genuinely a theory — and it took thirty years after the failure was understood for anybody to find it.

Who found it, and when #

The failure of misère play has been known since Grundy. Grundy and Smith made the first serious attempt in 1956, and the situation was well enough understood by the 1980s for Winning Ways to give it a chapter and a general air of resignation. Conway proved that misère equivalence over all impartial games is essentially trivial — almost nothing is equivalent to anything else — which closed the universal route permanently.

The quotient construction is Thane Plambeck’s, from around 2004, with the key move being exactly the restriction to sums drawn from one game. Plambeck and Aaron Siegel developed it into a working theory over the following years, and the computation of quotients for specific octal games became a small industry.

The results have the flavour of a catalogue rather than a theorem, and that is the honest character of the subject. Dawson’s chess has a finite quotient of a few hundred elements; several nearby codes do not; and the pattern of which is which has no known description.

The ladder from here #

This anchor began with misère play and what it costs — the demonstration that reversing one clause destroys the theory. This rung is what was built afterwards.

Later rungs: the proof that the classes form a monoid, and why the outcome partition is a congruence on it. Presentations — a quotient given by generators and relations rather than by a table, which is how the large ones are stated. Games with provably infinite quotients. The misère version of the octal codes, where the periodicity question reappears in a new and worse form. And the genus theory, which is the older partial answer that the quotient construction subsumes.

The thing established here is the size of the honest claim. Every table on this page is a quotient of a stated universe, converging from below on something the computation cannot reach, and printing the bound alongside the answer is what keeps the two apart.