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.

It keeps growing #

Misère Nim with heaps of at most two 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.

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.

The contrast between those two figures 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.

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