Combinatorial Game Theory
who wins, and by how much
Concept

Domination — where it appears

A move that can be discarded because another move is at least as good for the same player. It is one of the two simplifications that reduce a game to canonical form, and it is the cheap one: comparing two options settles it without looking further down the tree.

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

The same game, written twice. A position as it arises and the same position reduced. Left would never move to 0 when 2 is available, so that option is dominated and can go. The two games are equal — checked, not assumed — and the second is the canonical form.

A reduction that reads a graph

The two reductions are defined as deletions from an option list, and the shared form has no option lists — a node is reached from several parents at once. Both restate as rewritings at a node, the rewriting is confluent, and its fixed point is the canonical form. What does not carry over is the sharing: four fifths of the shared nodes need a different answer under different parents.

values · Reversibility Two fibres and a tail. The values reached by the most antichains. Nought takes half of them and star fourteen more; twenty-three of the thirty values are reached by exactly one.

Twenty-six other values

The mex rule accounts for sixty-six of the ninety-six antichains and is silent on the other thirty. Every one of those thirty is worth a self-negative value born by day three — and the same mex, run over that family instead of over the nimbers, is exact on all ninety-six. The nimber rule is this one cut short after its fourth member.

sums · Negation

Named alongside it

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

Canonical formEnumerationEqualityExhaustive searchValueGraphMexNegationNimbersPartial orderRecursionReversibility

All concepts