Combinatorial Game Theory
who wins, and by how much
Concept

Option listing — where it appears

The two lists of moves a form is written as, whose length the reduction can increase even though its purpose is to simplify. Its length is decided by the shape of the order on the options rather than by what the options are worth.

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

Which part to move in. A sum, and every move one player has in it. Each row is a component, the option taken in it, and what the whole position becomes. The values of the parts say who wins; they do not say where to play, and the winning move here is in the component worth the least.

Which part to move in

The value of a sum is the sum of the values. The move in a sum is not the move in any part, and there is no rule that reads it off the values — in the smallest interesting example, the only winning move is in the component worth nothing.

sums · Disjunctive sum The reduction that puts options back. How the two reductions change the width of a form. Domination only ever removes an option. Bypassing a reversible option substitutes the answer's whole option list, so it can leave the form wider than it started — and the finished canonical form can be wider than the form it came from.

The reduction that puts options back

Canonical form is presented as simplification, and half of it is. Deleting a dominated option takes one away. Bypassing a reversible one substitutes the answer's whole option list, so it can leave the form wider than it started — and 60 of 32,428 forms end up with a canonical form wider than they are.

values · Reversibility 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

Named alongside it

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

Star (∗)Up (↑)Born on dayCanonical formComparisonDominated optionExhaustive searchNormal playReductionReversible optionUniquenessAdditivity

All concepts