Combinatorial Game Theory
who wins, and by how much
Field

Values

What a position is worth — numbers, and the things that are not numbers, and how to find the simplest one.
0outcome P= 0whoever must move, loses10outcome L> 0Left wins, whoever starts-10outcome R< 0Right wins, whoever starts∗00outcome N‖ 0whoever moves first, winsblue edges are Left's moves, red are Right'sthree of the four are comparisons with zero; the fourth is not

Who moves last

The player who cannot move loses. That single convention generates the whole theory — and it produces four outcomes rather than three, because a position can be confused with zero rather than greater, smaller or equal to it.

 011/2{0 | 1}021{0 | 2}-550{-5 | 5}1/43/41/2{1/4 | 3/4}13/25/4{1 | 3/2}the marked point is the value; the hollow one, where it differs, is the midpoint

The simplicity rule

When both players' options are numbers, the position is worth the simplest number strictly between them. Not the midpoint, not the average, and the difference between "simplest" and "middle" is the entire content of the rule.

 as it arises1/201{0 | 1}dominatedoption removedcanonical1/201{0 | 1}both are worth 1/2and every game has exactly one canonical form, which is why values can be compared at all

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.

 ↑{0 | {0 | 0}}> 0< 1/1024outcome L⇑{0 | {{0 | 0}, 0 | 0}}> 0< 1/1024outcome L↑∗{{0 | 0}, 0 | 0}‖ 0< 1/1024outcome N∗{0 | 0}‖ 0< 1/1024outcome N↓{{0 | 0} | 0}< 0< 1/1024outcome Rvaluecanonical formagainst 0against a thousandth↑ is positive and smaller than every positive number — which no real number is∗ is none of greater, smaller or equal — the order is partial, and that is the point

Infinitesimals

Some positions are positive — Left wins them whoever moves first — and smaller than every positive number, including a millionth and a millionth of that. They are the values that decide close games, and the smallest of them is a single move's worth of nothing.

All essays