Combinatorial Game Theory
who wins, and by how much
Concept

Fuzzy — where it appears

Confused with zero, so that whoever moves first wins — the outcome class no comparison with a number can express. It is a computed verdict rather than a gap in the machinery, and it is the fourth relation numbers have no room for.

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

Four things a position can be. Every position falls into one of four outcome classes, and only three of them correspond to a comparison with zero. The fourth — first player wins — is a position confused with zero, neither greater, smaller nor equal, and it is where the subject departs from arithmetic.

Who moves last

The player who cannot move loses. That single convention generates the whole theory — and it produces four outcomes rather than three, because a position can be confused with zero rather than greater, smaller or equal to it.

values · Outcomes 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 Comparing two positions is playing their difference. To decide whether one position is worth at least another, subtract and see who wins moving second. It is the only definition of comparison the subject has, and it produces a partial order — some pairs come out confused, which no comparison of numbers ever does.

Confused is not the same as unknown

Two positions can be neither greater, nor smaller, nor equal. That is a fourth relation with its own symbol, it is a fact about the pair rather than a limit of the method, and it is what makes a game worth playing — a position is a first-player win exactly when it is confused with zero.

sums · Comparison What deleting is worth on its own. The reduction split into its two halves and each measured. Deleting a dominated option removes exactly one option and can do nothing else; bypassing a reversible one substitutes an option list and can widen the form. The counts say how much of the reduction the monotone half accounts for.

The reduction that always shrinks

Canonical form is two reductions and they are not the same kind of operation. Deleting a dominated option removes one option and can do nothing else; bypassing a reversible one substitutes a whole option list. Over the 256 forms born by day two, deleting alone finishes 225 of them and accounts for 480 of the 520 options that come off — and the 31 it cannot finish are almost all the ones with a star in them.

values · Dominance Which end of the interval is open. Every value born by day 3 compared with each of its own two stops — 2,948 comparisons, each one a search over the difference. The two rows are mirror images because the day is closed under negation, and the small number in each row is the exception class: the 352 values whose two stops coincide, for which the left stop is the right stop and the law has nothing to bite on.

Which end of the interval is open

The confusion interval is open at both ends, and the two ends are not the same kind of open. At its own left stop a position can be below the number, confused with it or equal to it, and — over 2,948 comparisons — above it exactly thirty-three times, every one of them a value whose two stops are the same number and whose left end is therefore also its right one.

values · Stops The identity that would join the order to the addition. Every pair of the twenty-two values born by day two, asked whether the join plus the meet equals the sum. It holds on all 201 comparable pairs, where the join is the larger and the meet the smaller and it cannot do otherwise, and on none of the 52 incomparable ones.

Where the order and the sum disagree

Day two is a lattice, and day two is a group, and it is not a lattice-ordered group. The one identity that would join the two structures — the join plus the meet equals the pair — holds on exactly the 201 pairs where it cannot fail and on none of the other 52, and the errors split thirteen high, thirteen low and twenty-six confused.

values · Lattice

Named alongside it

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

ComparisonPartial orderStar (∗)Canonical formDisjunctive sumExhaustive searchInfinitesimalAntichainConfusedDominated optionEqualityGroup

All concepts