Combinatorial Game Theory
who wins, and by how much
Concept

Reversible option — where it appears

A move whose reply returns to something no worse than the position it left, so it can be replaced by that reply's own options. Bypassing one is the half of the reduction that can make a form wider before it makes it smaller.

Named by 11 essays across 4 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 −1 when 0 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.

Canonical form

Two positions are worth the same when neither player can tell them apart inside any larger game. Deciding that could be an infinite search. Instead there is a normal form — delete what nobody would play, bypass what backfires — and equality becomes a comparison of two small trees.

values · Canonical form Poker Nim from 3, 5, 7, with reserves of 4 and 4. Nim with one extra kind of move: a player may put any number of counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. They cannot, and the winner is decided by exactly the same nim-sum as ordinary Nim — checked here over every position within a stated range rather than argued.

The move that gives counters back

Poker Nim adds one rule to Nim — a player may put counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. The winner is decided by exactly the same nim-sum, and the reason is the single most useful idea in the whole reduction apparatus.

impartial · Nim The same game, written twice. A position as it arises and the same position reduced. Three of the options are dominated — a sibling is at least as good for the player who owns them — so they can go. The two games are equal — checked, not assumed — and the second is the canonical form.

Two hundred and fifty-six ways to write twenty-two things

Every game whose options come from the four born on day one — there are 256 of them, and between them they carry 22 values. The reduction that collapses one to the other has choices in it at every step, and uniqueness is the claim that none of the choices matters.

values · Canonical form How old a form is, and how old its value is. Every one of the 256 forms born by day two, placed by the depth it is written at and by the birthday of the value it carries. Nothing sits above the diagonal, because a form cannot be younger than the value in it; the diagonal holds the forms written at exactly their value's birthday, and everything below it is a position written older than it needs to be. The count in each cell was obtained by canonicalising all 256 forms and measuring both depths.

How old a value is

A form's depth bounds the birthday of the value inside it, and reducing to canonical form attains the bound — for all 22 values born by day two, with no exception. Twenty-four of the 256 forms are older than what they are worth. The same reduction that makes the bound tight is what puts day three within reach: 98 option sets a side instead of four million, 9,604 forms, 1,474 values, a quarter of a second.

values · Numbers Knowing who wins, and knowing what it is worth. Nine positions, each evaluated twice by an instrumented evaluator that starts with an empty cache. The third column counts what deciding the winner costs and the fourth counts what the canonical form costs, in the currency each question is actually paid in.

Knowing who wins, and knowing what it is worth

Deciding a winner expands positions. Computing a canonical form expands pairs of positions, because a comparison unfolds as a recursion over one subposition of each and the reduction makes many comparisons. Measured on the same nine positions by an evaluator that starts empty every time, the second costs between 1.3 and 279 times the first, and the ratio grows with the tree.

complexity · Value cost 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 What the reduction collapses. Each reduced form with the values that reduce to it. The largest class is the one that reduces to zero and it holds every infinitesimal on the list, which is exactly what the reduction is for — against a hot background, none of them is distinguishable from nothing.

What is left when the small change is thrown away

Canonical form answers a demanding question: which positions are interchangeable inside every sum whatever. A player with a hot board does not have every sum — an infinitesimal difference cannot decide anything against a genuine fight — so there is a coarser question with an exact answer. The reduced canonical form takes the 1,474 values born by day three to 61, with 292 of them collapsing to zero, and it is a homomorphism on all 8,100 pairs tested only when a second pass is made.

sums · Reduced form 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 How many options a value needs. The canonical form is the smallest form of its value, so the number of options it carries is a property of the value. Three days of the construction, with the widths that occur and the widest value of each.

How wide a form can get

Bypassing a reversible option replaces it with a whole option list, so a form grows in the middle of its own reduction. Whether it can come out wider than it went in is the question that leaves standing, and over 64,515 forms built from day-two options the answer is no, not once — the growth is real, it is transient, and the widest canonical form reached is exactly as wide as the widest form that reaches it.

values · Reversibility Not a domination, in the order the rung below meant. The second pass's deletions scored as dominations in two orders: the partial order on games, and the order on stops.

Not a domination, in that order

The rung below asked which pair the second reduction acts on, taking for granted that the operation is a domination. It is not: on none of the 525 deletions is a surviving option greater than or equal to the deleted one. In the order the reduced form actually works in — both stops at least as good — every deletion with a survivor is a domination, the dominator is unique on all but twelve, and it always comes from the other part.

sums · Reduced form

Named alongside it

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

Canonical formDominated optionComparisonExhaustive searchReductionBorn on dayStar (∗)EqualityNormal playPartial orderUniquenessBirthday

All concepts