Combinatorial Game Theory
who wins, and by how much
Concept

Gift horse — where it appears

An option that may be added to a position for nothing, because it is not as good as the position already is. It shows that the canonical form's options need not have been in the form it came from, which is what bypassing puts back.

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

Options handed to Left in 1 | −1. A position, and one candidate option after another added to it. Where the gift is one the player would never take the value does not move at all; where it is one they would, it does. The last column is the value of the enlarged form, computed by the same recursion as the original.

An option nobody would take

Every reduction of a form deletes. The gift horse principle adds: a move may be handed to a player for nothing, provided it is one they would never choose. Over all 484 additions to the values born by day two, 283 leave the value exactly where it was and the 201 that move it are precisely the ones the condition forbids — with the boundary at *not better*, which is a weaker demand than *worse*.

values · Gift horse 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 No fifth value. Forms of day-three values built by adding day-three gift horses, and the ordinal sums they give. Over eighteen thousand forms and four followers, no value's forms disagree.

No fifth value

The colon reads a form rather than a value, and the rung below found the forms of a value disagreeing at exactly four of them — the values born by day one. It could only check forms whose options came from day two. Built one day deeper, by adding day-three gift horses to day-three values, eighteen thousand forms give no disagreement at all, while the same treatment still splits nought four ways. The class is about the width of the base's form and not the depth of its options.

sums · Ordinal sum 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 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 formEqualityNormal playDominanceEnumerationOrdinal sumCounterexampleHackenbushReversibilitySubstitutionBorn on dayComparison

All concepts