Combinatorial Game Theory
who wins, and by how much
Concept

Monoid — where it appears

A set with an associative operation and an identity but no inverses, which is the structure misère play leaves standing. It is enough to compute with and not enough to subtract in, so comparison has to be rebuilt from outcomes rather than from differences.

Named by 5 essays across 3 fields — each of them below, with the objects they name alongside it.

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.

limits · Misère play 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.

history · Misère play Cancellation, by exhaustion. The law checked on every triple of values born by day two, and then put to work: two Domineering regions compared directly and compared again inside a larger board. The comparison never changes, which is the licence every decomposition on this site is drawn under.

What can be struck out

From G + X = H + X it follows that G = H, in one line, by adding −X to both sides. It is the shortest theorem here and the most used: it is what makes comparing two boards region by region legitimate. Over 10,648 triples the hypothesis fires 484 times and the conclusion holds 484 times — and the licence expires in three separate directions, each of which loses the same axiom in a different way.

sums · Negation Where the thirty sit on the scale. How many of the values equal to their own negatives carry each temperature. Fifteen sit at nought, fourteen are hot, and one is a number — so the subgroup runs the whole length of the scale rather than living at the cold end of it.

The thirty that cancel themselves

Thirty values born by day three are equal to their own negatives, and every one of them has a mean of exactly nought and two stops that are exact opposites. Neither property comes close to picking them out — 496 values of the day have a mean of nought — and half of the thirty are hot, one of them the hottest value the day produces.

sums · Negation The same rules under the convention they were posed in. Dawson's chess under misère play, which is how Dawson posed it. Under normal play every position of the game collapses onto one of a handful of nimbers however large the heaps are allowed to get. Under misère play the positions that behave alike form classes whose number grows with the heap limit, and a heap carries a genus rather than a value. The first wild heap is where the two accounts stop resembling each other, and the classification doubles at exactly the limit that admits it.

The convention Dawson actually used

Dawson published his puzzle as a problem where running out of moves loses you the game, and every compact result about ·137 is about the other convention. Under his own, nine values become a classification that doubles the moment a wild heap enters the range, and a heap stops carrying a number at all.

history · Dawson

Named alongside it

The objects these essays reach for when they reach for this one.

Misère playDisjunctive sumGroupMisère quotientNegationComparisonEquivalenceGrundy valueIndistinguishabilityOctal gameOutcome classAdditivity

All concepts