Combinatorial Game Theory
who wins, and by how much
The collection

Every essay

One idea per essay, ordered so that the earlier ones set up the later ones — but nothing here depends on being read in sequence.

Impartial games

Both players have the same moves. Every such position is a Nim heap, and the theorem that says so is the field's first.

301151017111nim-sum001= 1some column does notthe player to move winstake 1 from the heap of 3outcome N

Nim, and the nim-sum

Three heaps of counters, take as many as you like from one of them, and the player who takes the last counter wins. The winning condition is not a search, not a table, and not a heuristic — it is the bitwise exclusive-or of the heap sizes, and it was found in 1901.

7 figures a heap of 10, taking 1, 3, 4options lead to heaps of 9, 7, 6whose values are 0, 0, 2mex of those is 1plays exactly likea Nim heap of 1= ∗the value is the heap size — nothing else about the position survives

Every impartial game is a Nim heap

Sprague and Grundy proved, independently and four years apart, that any position in any impartial game is equivalent to a single heap of counters. Not similar to one — equal to one, interchangeable with it inside any larger game.

6 figures 001230412308123012123016123020123024heap size, and the value of a heap that bigperiod 4, from heap 0a heap of size n is worth ∗g(n) — and the whole game is the nim-sum of its heaps

Grundy sequences, and where they stop being predictable

Computing one Grundy value is a mex. Computing all of them produces a sequence, and the sequences do something nobody has fully explained — most of them eventually repeat, some of them take thousands of terms to start, and for a few nobody knows whether they ever do.

6 figures

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.

8 figures 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.

7 figures 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.

6 figures ↑{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.

6 figures

Sums and comparison

Real games break into independent parts. Adding them up is the whole method, and comparing them is how it is checked.

2+-1+1/4+∗={5/4 | 5/4}outcome Leach sprig is a separate game; a move is a move in one of themthe total was computed by adding the games, not the labels

The sum is the object

Real positions come apart into independent regions, and a move happens in exactly one of them. That operation — the disjunctive sum — is what the whole theory is built to survive, and it is the reason values exist at all.

6 figures ↑ − 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

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.

6 figures ∗ + ∗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

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.

6 figures

Temperature

How much is at stake, measured. Thermographs, cooling, and why a player moves where the game is hottest.

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

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.

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

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 figures {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

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.

6 figures

Particular games

Hackenbush, Nim, Domineering, Toads and Frogs — the specific games the general theory was built to explain.

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

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.

9 figures the boardworth 2 | −1/2outcome N{2 | −1/2}Left plays verticallyRight plays horizontally

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.

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

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.

7 figures

Where it stops

Misère play, loopy games and computational hardness — three ways the theory runs out, and what survives each.

normal playmisère playevery impartial position is a Nim heapno such reduction existsequal games can be swapped in any sumonly within a restricted universethe value is a single small integeran element of a quotient monoida canonical form exists and is uniquecanonical forms are enormousthe game is what mattersthe game is what mattersmisère quotients recover some of it, one game at a timeand there is no general theory, which after fifty years is a real result rather than a gap

Misère play

Change one word — the player who cannot move wins — and the games are identical, the strategies are not, and almost every theorem on this site stops being true. It is the cheapest possible modification and the most expensive.

6 figures ABCthe moves lead back to where they startedno base case, so the recursion never bottoms outa third outcome appears: neither player can force a winloopy game theory is a separate subject with separate machinery

Loopy games

The whole theory assumes play stops. Allow a position to recur and the induction that every value rests on has nothing to stand on — and a fifth outcome appears that normal-play theory has no name for.

6 figures the value of a Nim positioninstantthe Grundy value of a small subtraction gamelinearthe canonical form of a moderate positionexponential in theorywho wins a general Domineering boardno efficient methodwho wins a generalised board gamePSPACE-completecostthe definitions are constructive, so everything here is computable in principleand the practical range of an exact evaluator is a few dozen moves, which is the working constraint

How hard is it

Every theorem on this site stays true at any size. The answers stop being reachable long before the games get interesting — deciding the winner of a generalised board game is PSPACE-complete, and an exact evaluator gives out after a few dozen moves.

6 figures