Combinatorial Game Theory
who wins, and by how much
Series

Misère play — the series

6 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. What reversing the ending destroys. Everything 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 means of evaluating them is gone, and what replaces it is far heavier.

    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 of the normal-play theory stops being true. It is the cheapest possible modification and the most expensive.

    part 1 · limits
  2. The misère quotient of Nim, heaps up to 2. Each row and column is a class of positions that no sum in this universe can tell apart, and each entry is the class their sum falls into. The shaded classes are the ones a player wants to hand over. Under normal play the same positions need only the Nim values; the extra classes here are what misère play costs.

    What survives misère play

    Misère play destroys the value theory, and something much smaller grows back. Fix one game, look only at sums of its own positions, and the classes that behave alike form a monoid — computed here, and larger than the normal-play answer every time.

    part 2 · limits
  3. Classes needed, as the heaps get bigger — Dawson's chess ·137. How many kinds of position there are, against how large a heap the universe allows. Under normal play the answer stops growing as soon as the Grundy values stop growing. Under misère play it does not stop, and every new class is a pair of positions that behave identically under normal play and differently under misère.

    "Hopeless" was a claim about a method

    Misère analysis was declared intractable in the 1970s, and the verdict was correct about what was being attempted. Quotients did not refute it thirty years later — they changed the question from a value per position to a monoid per universe, and the computed sizes show why the first question has no good answer.

    part 3 · history
  4. The mirror strategy, and the ending that punishes it. A position beside its negative and the sum of the two, with the outcome under both endings. Under normal play the sum is worth zero every time, because the second player answers every move with its mirror image. Under misère the same answers are available and the same player runs out last, so every one of these sums is a first-player win — there is no zero, and no subtraction.

    Misère play has no negatives

    Put a position beside its own mirror image and answer every move with the mirror move. Under normal play the answerer wins and the sum is worth zero. Under misère the answerer still has every reply and loses because of it — so there is no zero, no subtraction, and no comparison, which is why the misère theory had to be rebuilt rather than adjusted.

    part 4 · limits
  5. What the two outcome classes of the parts settle. For each pair of outcome classes, the set of outcomes the sums actually took. A cell with one letter is a pair of classes that decided the answer; a shaded cell with several is a pair that did not. Both conventions have ambiguous cells — the difference is that normal play repairs them with values and misère play has nothing to repair them with.

    Two misère outcomes are not enough

    Knowing who wins each part does not say who wins the sum. Over 676 sums built from a pool of twenty-six positions, nine of the sixteen pairs of outcome classes settle the answer under normal play and not one of the sixteen settles it under misère — and the nine that work are theorems about a value being zero, which is exactly the thing misère play does not have.

    part 5 · limits
  6. What a wider pool rescues. The misère outcome table built four times over, on pools of 10, 22, 100, 113 positions. A cell holds the set of outcomes that sums of its row class and column class actually took. Fifteen of the sixteen cells are short of all four outcomes on the smallest pool and none is on the largest, so every near-miss in the original table was a statement about the pool rather than about misère play.

    What a wider pool rescues

    The misère outcome table has sixteen cells, and over a pool of ten positions fifteen of them hold fewer than four outcomes — which looks like structure and might be a shortage of positions. Thirteen values further on there is nothing left: every pair of outcome classes takes every outcome, so the near-misses were the pool, and the prediction the rung below made was right.

    part 6 · limits

All series