Combinatorial Game Theory
who wins, and by how much
Theme

The thread: Who moves last

The player unable to move loses. That single convention generates the whole theory, and reversing it — misère play — destroys almost all of it.
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.

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

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.

 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 Sums and comparison

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.

 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.

 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 Where it stops

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.

 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 Impartial games

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.

 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.

 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 Where it stops

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.

 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 Impartial games

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.

 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 Values

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.

 ∗ + ∗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.

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