Combinatorial Game Theory
who wins, and by how much
Theme

The thread: Not every game is a number

Some positions are worth a half or a quarter. Others are worth something no number can express, and the ones that are not numbers are where the subject becomes interesting.
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 Values

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.

 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.

 1blue2blue blue1/2blue red3/4blue red blue1/4blue red red3/8blue red red blueeach string is worth a number, and the string spells itblue is Left · red is Right · the ground is what holds it up Particular games

Hackenbush is a numeral

Draw a stalk of coloured edges. Read it as a string, blue for one and red for zero, and the string is the binary expansion of what the position is worth. Not approximately — exactly, and the site computes it both ways and refuses to build if they disagree.

 ↑ − 0= ↑outcome L↑ > 0∗ − 0= ∗outcome N∗ ‖ 0⇑ − ↑= ↑outcome L⇑ > ↑1/2 − 1/4= 1/4outcome L1/2 > 1/4↑∗ − ∗= ↑outcome L↑∗ > ∗the differencethe verdict‖ means confused: neither greater, nor smaller, nor equal — and no amount of care removes it Sums and comparison

Comparing positions

One position is worth at least another when the second player wins their difference. That is the only definition there is, it is a computation rather than a judgement, and it produces an order in which some pairs are simply not comparable.

 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.

 the boardworth 2 | −1/2outcome N{2 | −1/2}Left plays verticallyRight plays horizontally Particular games

Domineering

One player places dominoes vertically, the other horizontally, on a shared grid. The rules take one line, the values are a mess, and that mess is the point — this is what the theory looks like applied to a game nobody designed for it.

 ∗ + ∗N + N0outcome P∗ + ∗2N + N∗3outcome N↑∗ + ↑∗N + N⇑outcome Leach part is a first-player winthe sumsame outcome classes going in, different outcomes coming outso a position has to be given a value, not merely a winner Sums and comparison

Outcomes do not add

Knowing who wins each part of a position tells almost nothing about who wins the whole. Two first-player wins can sum to a second-player win, or to another first-player win, and no rule distinguishes the cases from the outcomes alone.

 ∗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