The cost is in the closure, not in the positions

Reverse one line of the rules — the player who cannot move now wins — and every position on the board is unchanged. Not one stone moves, no move becomes legal or illegal, and the graph of positions is the same graph it was. What changes is how many different kinds of position there are.

Under normal play, Dawson’s chess needs four kinds, at every heap size up to twelve. Under misère play it needs six, and then twelve, and the number keeps climbing as the universe widens.

A classification that is local, and one that is not #

The whole difference is in where the work happens, and it can be stated in two sentences.

Under normal play, a position’s class is computed from the position. The Grundy value is a mex over the values of its options, which are computed from their options, and nothing outside the position is ever consulted. Two positions with the same value are interchangeable everywhere, and the value was obtained without knowing what “everywhere” contains.

Under misère play, a position’s class is computed from the position and everything it might be added to. Two positions are the same when no sum tells them apart, and establishing that means trying sums. The classification is a property of a pair — a position and a universe — and the universe is not something a recursion over one position can see.

That is not a matter of difficulty. It is a matter of what kind of object is being computed, and everything about the cost follows from it.

The reason the normal-play version gets away with being local is a theorem, not a convenience. Sprague–Grundy says every impartial position is equal to a Nim heap, and equality there means equality in every sum — so computing the heap size settles the contextual question once and for all, without any context ever being examined. Take that theorem away and the contextual question comes back, because it was always the real one.

What that looks like on two actual positions is worth having in front of a reader before any counting starts, because the whole essay is arithmetic about a distinction the arithmetic cannot show.

That pair is what every extra class in this essay is made of, and it is also why the count cannot be computed one position at a time: neither of those two positions contains the information that separates them. The information is in a third position, added to both.

What the computation actually does #

The quotient over a bounded universe is computed here, and describing the procedure makes the expense obvious.

Fix a universe: all positions with at most four heaps, each of at most nine counters. That is 715 positions. Fix a set of test positions — the same universe, or a bounded part of it.

For each position, compute its signature: the outcome of that position added to each test position, as a string of Ns and Ps. Two positions are put in the same class exactly when their signatures agree.

So the work is one misère outcome per (position, test) pair — 715 × 715 of them at that size, each one a search of its own — and the number of pairs grows as the square of a universe that is itself growing exponentially in the heap size.

Compare with the normal-play computation on the same universe: one Grundy value per position, each a mex over its options, with everything memoised. Linear in the positions, and no pairs at all.

Both columns are worth printing rather than described, because the ratio between them is the whole finding and it is not a constant.

What all that work buys is one finite algebra, and the algebra is small enough to print. It is the object the whole computation exists to produce: a list of classes and a rule for multiplying them, from which the outcome of any sum inside the universe can be read off without another search.

The bound that has to be stated #

There is an honesty problem built into this and it is worth being explicit, because it is the reason every quotient figure here prints its universe.

The true misère quotient is defined over all sums, of which there are infinitely many. Nothing computes that directly. What is computed is the quotient over a bounded universe, and the relationship between the two runs one way only: a bounded universe can merge classes the true quotient keeps apart, and can never split ones it joins.

So every count here is a lower bound. Six classes over this universe means at least six, possibly more once wider sums are allowed — and the figure states the bound rather than leaving a reader to assume the number is final.

The measured jumps are what that looks like in practice. Dawson’s chess sits at six classes for heaps up to seven, then moves to twelve at nine. Nothing about the game changed at heap eight; the universe got wide enough to notice a distinction that was there all along.

Narrowing the universe rather than widening it is the same statement read backwards, and it is the one that can be drawn.

That is a peculiar epistemic position for a computation to be in, and it is exactly the situation the identification essay describes: under normal play, sameness is decided by the positions; under misère play it is decided by the company they keep.

Where the extra classes come from #

It is worth seeing one distinction that misère play makes and normal play does not, since the abstraction otherwise stays abstract.

Under normal play a heap of one and a heap of two are $\ast 1$ and $\ast 2$, and any position with the same value substitutes for either in any sum. Under misère play the single counter is special: a lone heap of one is a win for the player who must move into it, because taking the last counter loses.

Misère Nim survives this with one exception clause: play as usual unless every heap has one counter, and then invert. That is the whole theory of misère Nim, and it is the last time the subject is that generous. The exception exists because in Nim, “all heaps are one” is the only configuration where the ending convention bites — and in almost every other game the convention reaches much further back, dividing positions that normal play had happily merged.

The numbers, side by side #

The two lines on the figure at the top are worth reading off, because the shapes differ before the sizes do.

Normal play, Dawson’s chess. Four classes at heaps up to three, four at five, four at seven, four at nine. The Grundy values of this game are 0, 1, 2 and 3 for every heap up to twelve — the first heap worth more is thirteen, worth ∗4 — so across the universes drawn here the classification is complete at the smallest one and nothing later adds to it.

Misère play, same game. Six at three, six at five, six at seven — and twelve at nine.

Normal play, Nim. Four, then eight, then eight, then sixteen: the count tracks how many Grundy values fit under the heap limit, which is exactly what it should do.

Misère play, Nim. Six, ten, ten, eighteen. Always ahead, and the gap widening.

Notice that the two games differ in which line moves. Nim’s normal-play count climbs because its Grundy values climb; Dawson’s does not, because its values stay at three or below through every heap drawn. The misère count climbs in both, and in Dawson’s case it climbs while the normal count is flat — which is the cleanest form of the finding, since there is then nothing about the positions that the growth could be tracking.

The cost in work follows the same shape and is the one to quote, because it does not depend on a machine. The misère classification over heaps up to nine computes 511,225 outcomes; the normal-play classification over the same universe computes 715 values. Both finish quickly at this size, and the ratio is what matters: one is linear in the positions and the other quadratic in a set growing exponentially, so the gap is a fixed fact about the two methods rather than an artefact of a small experiment.

The universe is not a parameter of the game #

There is one more consequence of contextual classification, and it is the one most likely to trip a reader who has internalised how normal play works.

Under normal play, the value of a position is a property of that position. It can be computed once, written down, and reused in any sum for the rest of time — which is why a table of values is a library of components.

Under misère play there is no such object. A position’s class is an index into a particular quotient, and that quotient belongs to a particular universe. Change the universe — add a new kind of component to the board — and the classes may split, and the index a position was given no longer names the same thing.

So the misère analogue of a value table is not portable. Two people computing misère quotients for two games cannot share their results the way two people computing Grundy values can, unless the universes coincide. What is portable is the method, which is a much weaker kind of reuse and is exactly what the normal-play theory spent its founding theorems escaping.

Why this is a cost essay and not a limits essay #

Misère play appears twice on this site, and the split is deliberate.

The essays in where it stops are about the machinery failing: the equivalences stop holding, values stop composing, and the apparatus that makes normal play tractable is not available at any price.

This rung is about what replaces it, and how much that costs. The misère quotient is a genuine theory — a finite algebra that answers the questions for a restricted universe — so this is not a case of nothing being possible. It is a case where the shape of the computation changed: from a recursion over positions to a closure over a universe, and from linear to quadratic in a set that is itself exponential.

Both halves are worth having. A reader who knows only the first thinks misère play is hopeless, which is wrong. A reader who knows only the second thinks it is merely slower, which is also wrong. The accurate summary is that a working theory exists, it answers less than the normal-play one does, and it is bought at a price that rises with how much is being asked.

The general shape: local against contextual #

There is a pattern here that outlives misère play, and naming it is the point of putting this rung in the complexity field.

A local invariant is computed from an object and its parts. Grundy values, canonical forms, thermographs and this whole site’s values are local: a recursion computes them bottom-up, memoisation applies, and results compose.

A contextual classification is computed from an object and its environment. Misère quotients are contextual. So is any notion of “these behave the same in every situation” where the situations cannot be enumerated cheaply.

Local invariants are cheap and compositional. Contextual ones need a closure computation, and the closure is where the cost sits. The difference shows up all over computing under other names — bisimulation and observational equivalence in the theory of processes are exactly this distinction — and combinatorial game theory has the clearest small example of it anybody could ask for: one word of the rules changed, one classification made contextual, and the expense follows.

The ordinary kind of expense in this field is a search being large: more positions to evaluate, and a closed form or a decomposition to avoid evaluating them. Misère play’s cost is a different animal, and the cost table above is where the difference shows. The search is not larger — the positions column is the same universe under either convention — and what has changed is the shape of the question asked about it.

What a solver would do differently #

It is worth asking what a program built for misère play looks like, since almost nothing carries over from the normal-play design this site uses everywhere else.

No value cache. There is nothing to cache: a class index is meaningless outside its universe, so the entry cannot be reused in another computation.

No decomposition into components with values. A board that falls into two regions still falls into two regions, and the saving that gives under normal play depends on the parts having values that add. Under misère play they have classes that multiply in a table specific to the universe, so the decomposition survives in a much weaker form — useful, and not the exponential collapse it is elsewhere.

Outcome-first, everywhere. The primitive is is this position a win for the mover under misère play, computed by search, and everything is built from counting those. That is the recursion at its most basic, without any of the algebra that normally sits between the search and the answer.

Universe management as the main design problem. Widening the universe finds more classes and costs quadratically more; not widening it risks reporting classes that a wider view would split. A misère solver spends its engineering effort on that trade, which has no counterpart at all under normal play.

Which is a fair summary of what the convention costs: not a slower version of the same program, but a different program with none of the same parts.

Why a cost measured in classes is the right currency #

There is a question hiding behind every number on this page — cost of what, measured in what? — and it is worth answering carefully, because the obvious alternative gives a much smaller and much less honest figure.

The obvious measure is time: how long the misère computation takes against the normal-play one on the same position. That number is respectable and it is nearly meaningless, because both computations are searches over the same game tree with the same memoisation, and the misère one is slower by a modest factor. Reported alone, it would say misère play costs a little more, which is the opposite of the truth.

The measure that carries the finding is the number of classes: how many distinct objects the theory has to keep apart before it can answer anything. Under normal play the answer is one value per position and the value is the same in every company. Under misère there is no such object, and what stands in its place is a class within a universe — so the count grows with the universe rather than with the position, and asking about a bigger universe is a bigger computation on the same position.

That is the shape of the cost and it is why it is unbounded rather than large. A cost that grows with the position is a cost a bigger machine addresses. A cost that grows with the question is not, because nothing about the position has changed and there is nothing to make bigger except the thing being asked about.

It also says why the comparison to normal play is fair rather than rhetorical. Normal play’s class count does not depend on the universe at all — equality quantifies over every game there is and delivers one answer — so the two conventions are being measured on the same axis and one of them simply does not move along it.

What the measurement cannot say #

Three limits, and the second is the one that matters most for reading any misère result.

No claim here is about the true quotient. Every count is over an explicitly bounded universe and the bounds are printed. A wider universe can only find more classes.

Finite does not mean small, and infinite is possible. Some games have finite misère quotients; others are known not to. A game whose quotient is infinite has no finite algebra to compute, and the entire method stops applying — not slowly, but at all.

Nothing here compares misère play to a hardness result. The measurements above are about the shape of a computation, not about a complexity class. There is no claim on this page that misère play is PSPACE-anything, and the reader who wants that kind of statement should look at what a hardness result actually says and note that it is about families and encodings rather than about conventions.

These are tiny games. Heaps of at most nine, sums of at most four. The published work on misère quotients handles considerably more, with far better algorithms than the direct signature computation used here, and the reason this site’s version stays small is that it computes rather than quotes.

Under normal play Dawson’s chess is an octal game with a settled Grundy sequence: the values run into a period of thirty-four, and they stay at three or below until heap thirteen, which is why its normal-play classification sits at four classes across every universe drawn here. A staircase, not a slope takes the heaps past twelve, where a value of four appears and normal play’s count doubles. The misère count climbs over exactly the same sequence of positions, computed from exactly the same move rule, and that is the sharpest way to put what this rung measures — the positions did not get harder, the question did.

Who built the theory #

Misère play resisted a general theory for the whole of the twentieth century. Conway’s treatment in On Numbers and Games establishes what misère canonical forms are and how enormous they get; the practical breakthrough came with Plambeck’s misère quotients in the 2000s and the subsequent work with Siegel, which reframed the question as: do not ask for a universal theory, ask for the algebra of one game’s own positions.

That reframing is what made the subject computable at all. It also produced the finding this rung is named for — the cost is in the closure. The positions of a misère game are the positions of the normal-play game and are no harder to enumerate. What is expensive is deciding which of them are the same, and that question was cheap under the other convention only because a theorem made it local.

The last three rungs of this field are elsewhere in the collection, because the complexity work needed them: a family of impartial games where a finite check settles every size, a game whose values are all infinitesimal, and the operation the whole theory rests on, which turns out to be a search of its own.