Combinatorial Game Theory
who wins, and by how much
Concept

Outcomes — where it appears

The four verdicts a short position can carry, which do not determine the verdict of a sum and are why values exist. Four of them, twelve transitions between them, and an infinitesimal can produce every one of the twelve.

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

a cycle of three: what the backward analysis settles. A position graph in which the moves can lead back to where they started. The labels are the order in which a backward analysis settles each position, starting from the ones where a player has already run out of moves. Positions the analysis never reaches are drawn — and there is no test for that; being unreachable is what a draw is.

An outcome with no value behind it

Retrograde analysis labels positions in rounds, outward from the ones already lost. Whatever is still blank when nothing more can be deduced is a draw — and there is no separate test for a draw, because a draw is exactly the residue the method never reaches.

limits · Loopy Comparing two positions means playing a third. Pairs of positions with the relation between them, and the game whose solution decided it. There is no way to compare two games by looking at them: the question “is G at least H?” is answered by playing G − H and asking who wins, which is a search, and its cost is counted here beside each answer.

Comparing two positions means playing a third

There is no way to look at two games and see which is better. The question "is G at least H?" is answered by building G − H and asking who wins it — so the most basic operation in the theory is a decision problem, and every canonical form is built out of them.

sums · Comparison 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.

limits · Misère play The collapse happens twice. How many subsets, antichains and values there are. Domination takes 1,793 subsets to 96 antichains and the rest of the reduction takes those to 30 values.

What identifies two subsets

Every subset of a day gives a self-negative value by mirroring it, and 1,793 subsets of day two give thirty values. The collapse happens in two stages with different characters: domination takes the 1,793 to 96 antichains and is a theorem, and the rest of the reduction takes 96 to 30 and is concentrated almost entirely on two values — nought, which has an exact description, and star, which has none.

sums · Negation 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

Named alongside it

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

ComparisonCounterexampleDisjunctive sumEnumerationNegationCanonical formComplexityExhaustive searchMisère quotientNormal playP-positionAdditivity

All concepts