Combinatorial Game Theory
who wins, and by how much
Concept

Reversibility — where it appears

A move that can be answered by returning to a position at least as good as the one left, so the move can be replaced by its answer’s options. It is the deeper of the two simplifications to canonical form, and the one that can make a game smaller than any of its options.

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

The proposed case, scored. The gift-horse theorem and the domination argument proposed for it, each scored over every gift horse added.

The proof needs both reductions

The gift-horse theorem was to be proved by showing the added option dominated. It is, on 97.8 per cent — and the other 232 are reversible instead, with nothing left over. The case the proposal missed is almost entirely one follower: none under a positive number, 190 under a negative one.

sums · Ordinal sum A factor, and it grows. The ratio between reducing and deciding, by the number of options the form carries.

A factor, and not an overhead

Deciding who wins a form searches the form's own tree. Reducing it to canonical form searches a difference game for every comparison, and a difference game is a sum. Over 256 forms the reduction expands 5.46 times as many positions — and the ratio runs from 0.58 at one option to 9.80 at eight.

values · Canonical form 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 The reversing move is the follower's. For each follower under which some gift horse escapes domination, the number of escapes, how many are reversed by Right's move inside the follower, and how many by a Right move in the base part. The follower's move reverses every one.

The follower does the reversing

The gift-horse theorem for the ordinal sum needs two cases, and the second — the added option is reversible — was counted and not described. Recorded move by move, the reversing answer is always Right's move inside the follower: on all 410 escapes under five followers, and on every one of the 2,628 gift horses under every follower that gives Right a move at all. The case split is by follower, not by horse.

sums · Ordinal sum What survived, and what did not. The gift-horse theorem, the two-case proof and the one-line description of the reversal case, each scored on the day-three sweep and its mirror and on the day-four sweep and its mirror.

The split slips one day deeper

The reversal case of the gift-horse theorem was described in one line — the follower's own move reverses every gift horse, whenever the follower has one — and tested only where it was found. In the mirror it holds exactly, with 1 and −1 trading places. One day deeper it fails: under ↑ and ½, three gift horses on built day-four bases are not reversed by the follower's move. All three are dominated, so the theorem stands; the clean split by follower does not.

sums · Ordinal sum

Named alongside it

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

Canonical formEnumerationDominanceNormal playEqualityGift horseOrdinal sumCounterexampleHackenbushProofSubstitutionComparison

All concepts