Combinatorial Game Theory
who wins, and by how much
Concept

Misere play — where it appears

The convention where the player unable to move wins rather than loses. It leaves every move set unchanged and breaks almost everything built on the other convention, which is why it needs a separate apparatus rather than a sign change.

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

Who gains, and how much. How much each test improves when dead-endedness is turned on, with the class-specific test beside the others.

The clause that turns the class off

Three rungs failed to find the dead-ending class doing measurable work, and each time the population was blamed. Toads and Frogs with and without the jump is the matched pair the anchor wanted — the same board with the class switched on and off — and on it the test the class licenses gains less from the class than a control that has never heard of it.

limits · Dead-ending Neither quotient identifies anything. The number of misère-equivalence classes on each side of the matched pair, against the number of distinct positions.

A quotient that identifies nothing

The dead-ending class is famous for quotients rather than comparisons, so the matched pair was asked the question its own subject is about. Neither quotient identifies a single pair of positions, and both are separated by exactly five addends — because a quotient is small when its universe is poor, which is a choice of company and not a property of a class.

limits · Dead-ending The genus of Kayles ·77, heap by heap. One row per heap: the genus symbol, the misère outcome it implies, and whether the symbol is one a Nim heap has. A game all of whose positions are tame is played in a misère sum exactly as Nim is; a single wild heap ends that, and the normal-play Grundy value gives no warning of which heaps those will be.

Closing the wild side

The twenty-two wild genus symbols are not closed under addition, and the rung below offered two answers: a monoid nobody had guessed, or no algebra at any size. Neither. Five of the six games with wild heaps close at three or four heaps, with closures of two to five symbols, and the sixth is still growing.

limits · Genus Misère Cram, board by board. The normal-play value and misère genus of every Cram rectangle with at least two rows and at most twenty squares. 12 are fickle, 4 × 4 is firm, and 3 × 6 and 4 × 5 are wild.

Cram with the last move losing

Under misère play every Cram rectangle to twenty squares is tame at the start except 3 × 6 and 4 × 5, and twelve of the fifteen boards two rows deep behave like one counter or none. The pairing that settles even boards under normal play hands the misère game to the first player, who wins by any vertical domino. And the tame boards are not tame inside: wild positions appear on boards as small as 3 × 4, always at ten empty squares, the length at which the strip goes wild.

impartial · Cram

Named alongside it

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

EnumerationMisère quotientDead-endingExhaustive searchGenusOctal gameToads and FrogsBounded universeCanonical formClosureComparisonCounterexample

All concepts