Combinatorial Game Theory
who wins, and by how much
Theme

The thread: Small things decide

Infinitesimals are smaller than every positive number and are not zero. In a close game they are the whole margin, which is why the theory bothers with them.
012345601234valuetemperaturetemperature 2mean 3Left's wallRight's wall{5 | 1} — mean 3, temperature 2 Temperature

What is at stake

Some positions both players are desperate to move in, and some neither player wants to touch. The difference is a number — how much the move is worth — and it turns out to be the most useful single quantity for deciding where to play.

 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 Values

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.

 012345601234valuetemperaturetemperature 2mean 3Left's wallRight's wall{5 | 1} — mean 3, temperature 2 Temperature

Reading a thermograph

A thermograph is two walls rising from a number line, closing in as the tax on moving increases, and meeting where the position stops being worth fighting over. Everything about a position's hotness is in the shape.

 {6 | 0}t = 3a big fight{2 | 0}t = 1a smaller one{1 | 0}t = 1/2small change{0 | 1}no temperaturesettled — a numbercomponenthow much is at stakethe whole position is worth {{{19/2 | 17/2} | {15/2 | 13/2}} | {{7/2 | 5/2} | {3/2 | 1/2}}}and the first move goes in the hottest part, which is a theorem up to a small error rather than a rule of thumb Temperature

Playing the hottest

Given several independent fights, play in the one with most at stake. The rule is simple, it is what strong Go players do without being told, it is provably close to optimal — and it is provably not optimal, which is the interesting part.

 ∗N∗N0P∗Nblue toads move right · red frogs move leftevery value came out of the moves; none was chosen Particular games

Toads and Frogs

Toads shuffle right, frogs shuffle left, and either may jump over one of the other. A strip six cells long is worth exactly up. Another six-cell strip is worth exactly down. Nobody has a formula for which.

 ↑{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 Values

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 themes