Misère play has no negatives

Every game has a negative is the fact that makes values into arithmetic. G + (−G) = 0 for every G whatever, the proof is the mirror strategy, and everything built on subtraction — comparison, dominated options, canonical forms, the whole apparatus — rests on it.

Change one word of the rules. Under misère play the player who cannot move wins. The positions are identical, the mirror strategy is identical, and the answer inverts.

Why the strategy turns on itself #

The mirror argument in full: whatever one player does in one copy, the other answers with the same move in the other copy. The two copies stay mirror images, so a move is always available to the answerer, so the answerer never runs out.

Under normal play running out is losing. The answerer never runs out, so the answerer wins, so the sum is a second-player win and worth zero.

Under misère running out is winning. The answerer never runs out, so the answerer is the one still moving when the other player has finished — and the player who finishes first has won.

The strategy is a machine for guaranteeing that its user always has a move. That is exactly what one convention rewards and the other punishes, and the inversion needs no new argument.

The four smallest positions move with it. Zero — the position with no moves at all — is a second-player win under normal play and a first-player win under misère; 1 and −1 swap sides; and ∗, the position whoever moves wins, becomes the one whoever moves loses. Nothing about any of them changed.

The sharpest case is the one where the mirror image is not built at all.

That row is worth keeping in view for the rest of the essay. Whenever a reader suspects the failure is an artefact of how the negative was built, the nimbers answer it: they are their own negatives, the two heaps in ∗2 + ∗2 are the same heap twice, and the sum is still a first-player win the moment the ending is reversed.

The sweep, and what it found #

The claim above is a theorem and it is also measured, because a theorem stated from memory is the failure mode this site has recorded more than once.

Six positions were run: a switch, an infinitesimal, a nimber, an integer, a fraction and a symmetric fight. For each, the negative was built by exchanging the two players’ roles all the way down, the two were added, and the sum was solved twice — once under each convention.

Six of six are second-player wins under normal play. The figure asserts it rather than reporting it: a row whose sum is not worth zero is a bug in the negation, and the generator throws rather than drawing it.

Zero of six are second-player wins under misère. All six are first-player wins, which is the strongest possible failure — not “the sum is sometimes not zero” but “the sum is never a second-player win at all”.

The second half is the one worth a test that can fail. A pool where some position kept its second-player win would be far more interesting than the uniform result, so the generator checks for exactly that and refuses to draw if it finds one. It has never found one, and the check is what makes the absence a finding rather than an assumption.

Six positions is still six positions somebody chose, and the way to stop choosing is to take a complete birthday instead.

Fourteen hundred and seventy-four is not a proof either, and it is a different kind of not-a-proof from six. Six positions can be a lucky pool; a complete birthday cannot, because there was no selection to be lucky in. What it leaves open is only the birthdays above it — and the strategy argument, which is the actual proof, does not mention a birthday.

What is lost, item by item #

The accounting is worth doing carefully, because “the theory does not transfer” understates it.

There is no zero. No position is a second-player win under misère and stays one in every sum. So the sums that make values a group do not exist, and the neutral element the arithmetic is built around is missing.

There is no subtraction. G − H means G + (−H), which needs the negative to behave. It does not, so the expression is defined and useless.

There is no comparison. G ≥ H is defined by who wins G − H, and with subtraction gone the definition has nothing to test.

Comparison under normal play is three steps — build the difference, play it out, read the relation off who won — and the first step is the one that is gone. Every relation this site quotes was settled that way, at a cost the search pays per pair, and under misère the object being searched is not the difference of anything.

And there is no substitution. Two positions with the same normal-play value can behave completely differently inside a misère sum, so the whole habit of replacing a component by an equal one is gone.

The place that costs most is the one nobody thinks of as arithmetic.

That is where the loss becomes concrete rather than structural. The numbers are the part of the theory a reader trusts without checking — they behave like arithmetic because they are an arithmetic — and the misère column says that the resemblance was a consequence of the ending rather than a property of the positions.

The outcomes get worse, not merely different #

Under normal play the outcomes of the parts do not determine the outcome of the sum, which is exactly why values were needed. Under misère the same failure is larger and there is nothing to replace them with.

Over a pool of ten small positions, sums were computed for every pair and grouped by the misère classes of the parts. Of the sixteen combinations that occur, fifteen are ambiguous — the same pair of classes going in produces different classes coming out. The worst is P + P, which produces all four classes across the pool.

The normal-play version of the same difficulty is a whole essay: three pairs of first-player wins whose sums land in different classes, and the failure values were invented to fix. Under normal play they fix it completely — the sum’s value is the sum of the values, every time — and under misère there is nothing to put in their place, which is measured cell by cell one rung above this one.

So misère play fails the same test twice as badly, and fails it with no repair available. That is the precise sense in which the convention is harder rather than merely different.

What actually survives #

Something does, and it is much smaller than a value theory.

Misère Nim is the reason misère play looks manageable at first: the games are identical to normal Nim and the answer flips for exactly one class of position, those where every heap holds a single counter. One clause, and it has been known since 1901. It is a special property of Nim and it is the last time misère play is this easy.

The general repair is to give up on comparing arbitrary games and to fix a universe: take one game, look only at sums of its own positions, and ask which of them behave identically inside that universe. That equivalence has classes, the classes form a commutative monoid, and the monoid is the misère quotient.

The quotient is a genuine object and it is not a value theory. It has no order on it, no subtraction, and it is specific to the game it was computed from — a quotient for Nim says nothing about Dawson’s chess.

And it does not settle. As the universe grows the class count grows with it — Dawson’s chess needs four classes under normal play at every heap size and its misère count doubles from six to twelve the moment a heap of nine is admitted — which is the honest shape of “there is no misère Sprague–Grundy theorem”.

The group law has a second form, and it is the form the theory actually uses. G + (−G) = 0 licenses cancellation: if G + X = H + X then G = H, so a component two positions share may be struck out of a comparison. That licence is what makes analysing a board region by region legitimate, and it is a one-line consequence of the negative. With no negative there is no line, and the question has to be asked of the positions directly.

So the loss is not confined to the places where a minus sign is written. Every argument on this site that looks at part of a board and reasons about it alone is standing on cancellation, and cancellation is standing on the negative.

Why the theory could not be adjusted #

It is natural to expect that a convention differing in one word should need a theory differing in a few lemmas, and the reason it does not is worth stating plainly.

Every theorem in the normal-play theory is proved by an induction whose base case is the position with no moves. That position is worth zero, it is a second-player win, and it is the identity of the arithmetic. Under misère it is a first-player win — the mover has already won by being unable to move — so the base case of every induction has the opposite verdict.

An induction whose base case inverts is not a proof needing repair. It is a different proof, with a different conclusion, and the honest response is to build a different theory rather than to patch this one.

The pair of failures this site now has #

Two essays here report G + (−G) failing to be zero, and they fail for opposite reasons — which between them isolate what the theorem needs.

Under misère the game ends and the mirror strategy loses because the answerer makes the last move. Under loopy play the mirror strategy answers every move and the game never ends at all, so on + off is drawn rather than zero.

The proof of G + (−G) = 0 is one sentence with two hidden hypotheses: there is a last move, and making it is a win. Loopy play removes the first; misère play removes the second. Remove either and the sentence stops being a proof, and the arithmetic built on it stops existing.

That is the most useful thing to carry away from both essays. A one-line strategy argument is rarely wrong and frequently under-stated, and the way to find what it assumed is to look at the neighbouring conventions that change one thing each. The subject has exactly two such neighbours, and each of them breaks a different clause.

It is also why the ending condition is stated as a condition rather than as an observation. What looks like a technicality about termination is the load-bearing hypothesis of the theorem the whole value theory rests on.

The one place the two conventions agree #

It is worth finding the common ground, because there is a little and it is where a misère player’s intuition comes from.

The move rules are identical. Every position, every option, every game tree is the same object. Only the labelling at the leaves differs, and the leaves are the positions with no moves.

The position graph is the same size. Everything the complexity field measures about search — routes, distinct positions, depth — is unchanged, because those are properties of the graph rather than of the winning condition. What changes is the closure: a misère analysis has to consider sums the normal-play one can skip, and that is where the cost goes.

And a game with a unique long line plays the same either way until the end. If a position has one sensible move for most of its length, both conventions follow it and disagree only in the last few plies, which is why misère variants of real games are usually described as “the same, but be careful at the end”.

That last observation is a warning rather than a comfort. The two conventions agreeing for ninety per cent of a game and inverting at the end is exactly the arrangement in which a player’s habits are trained on the wrong thing, and the same is true of a theory’s.

Where the model stops #

Six positions is a pool. The claim that G + (−G) is a first-player win under misère for every short game is a theorem, and its proof is the strategy argument at the top of this essay. The figure checks it on six positions and the site’s gate checks it on more; neither is the proof, and the pool would be the wrong kind of evidence if the argument were not available.

The quotients here are over bounded universes. A quotient computed over sums of at most four heaps of at most two counters is a quotient of that universe, and it is not a claim about the game in general. The figures say which bound they used, because the two are different statements.

And nothing here is about partizan misère theory as a subject. There is one — it is recent, it is difficult, and it works with a partial order defined over a universe rather than over all games. What this essay establishes is why the obvious route is closed, not that no route exists.

What a misère player is actually doing #

If comparison and values are gone, it is fair to ask what a competent misère player has instead, and the answer is more interesting than “nothing”.

A universe, and a table. A player who plays one game repeatedly can compute its quotient once and then read positions off it. That is what the quotient is for: not a general theory, but a lookup table for a game somebody actually plays.

Parity, near the end. Misère play is usually normal play until the last few moves, and the difference is concentrated where the heaps are small. Misère Nim is the extreme case — identical to normal Nim except when every heap has one counter — and the general pattern is that the two conventions agree until the endgame and then diverge.

And a much greater respect for the count. Under normal play a player wants moves; under misère a player wants the opponent to have moves. That is not the same as wanting fewer moves, because a player with no moves has won and a player with one has usually lost — the quantity that matters is parity rather than quantity, and the cost of misère play is that the parity has to be computed rather than counted.

The honest summary is that misère play is harder to play well for the same reason it is harder to theorise: the local information a player can gather does not compose, and composing local information is what the normal-play theory does.

What the picture cannot show #

Every figure here shows two columns of verdicts, and the interesting thing is not either column but the fact that one machine produced both.

The same tree, the same options, the same mirror strategy: the only difference is one clause at the leaves, and a diagram of two outcome letters side by side makes that look like two facts rather than one fact seen twice. The captions say it and the pictures cannot.

The other invisible thing is the size of what is lost. “There is no comparison” is a sentence about an absence; a figure of comparisons that cannot be made would be a blank page. What is drawn instead is the machinery working under normal play, with the observation that none of it is available — which asks the reader to take the negative on trust, or to notice that no misère figure in this collection compares anything.

Why this was not obvious for seventy years #

The historical shape is worth a paragraph, because it is a good illustration of how a field discovers what it assumed.

Misère Nim was solved in 1901 alongside normal Nim, and it is easy — one clause different. That made misère play look like a variant rather than a different subject, and the natural programme was to find the misère analogue of Sprague–Grundy.

It does not exist. The realisation took decades, and what the verdict of “hopeless” was actually about is the essay on that history: the declaration was correct about the programme being attempted and wrong about the subject.

What broke the impasse was giving up on generality. A quotient is computed for one game, over one universe, and it is a smaller claim than a value — which is exactly why it can be made at all. The change was in what question to ask rather than in how hard anybody worked on the old one.

That pattern shows up in this collection more than once, and it is worth naming: when a theory refuses to generalise, the productive move is often to shrink the claim rather than to strengthen the method. The quotient does for misère play what nothing was going to do for it in the original vocabulary.

The convention, named #

The whole essay is about a convention, so the thing to name is the other one.

Normal play is the convention where a player unable to move loses, and it is what makes the empty position worth zero. Every value, sum, comparison and thermograph on this site assumes it, and this essay is the measurement of what one word costs.

The second thing worth naming is what misère play is not. It is not “playing to lose”: both players are still trying to win, and the winning condition has changed. A player who simply plays the normal-play strategy backwards will not do well — what survives misère play is the essay about what a misère player actually needs, and it is an algebra rather than an inversion.

Where the ladder goes next #

The misere anchor has four rungs to here: the convention, the quotients that recover a comparison inside one game, what the convention costs, and now the operation it does not have.

The two rungs above take the same loss to the outcome table, which is the coarsest thing left once the arithmetic is gone. Two misère outcomes are not enough puts 676 sums through it and finds nine of the sixteen pairs of outcome classes settling the answer under normal play and not one of the sixteen under misère. The nine that work are theorems about a value being nought — precisely the object this page has just shown misère play does not have — so the failure one level up is this page’s failure wearing a different hat.

What a wider pool rescues then removes the last thing that looked like structure. Over a small pool fifteen of the sixteen cells hold fewer than four outcomes, which reads as constraint; widen the pool and every cell takes every outcome, so the near-misses were a shortage of positions. The control is what makes it a finding rather than an artefact: the normal-play table does not move at all under the same widening, because its empty cells are shut by theorems and a theorem is not embarrassed by more examples.

Read together the three rungs are one statement made at three levels. There is no negative, so there is no zero; with no zero there is no theorem about adding one; with no such theorem the outcome table has nothing to constrain it, and a census large enough shows it constrained by nothing.

What that leaves is the direction the anchor’s second rung already took: give up on a theory across games and compute one per game, which is what a misère quotient is, and the cost of doing so is what makes it worth measuring.