Combinatorial Game Theory
who wins, and by how much
Depth

Ladders

A field says what an essay is about. A ladder says what else there is to say about it — the distinct arguments that stand against one idea, from the one that introduces it to the one that assumes all the others.
011/2{0 | 1}031{0 | 3}-570{-5 | 7}142{1 | 4}1/411/2{1/4 | 1}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.

3 rungs · values 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.

3 rungs · temperature 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.

2 rungs · limits 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.

2 rungs · sums 001230412308123012123016123020123024heap size, and the value of a heap that bigperiod 4 from heap 0, holding through all 2001 values computeda 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.

2 rungs · impartial ↑{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.

2 rungs · values 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.

2 rungs · limits 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.

2 rungs · temperature ∗ + ∗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.

1 rung · sums worth 2, outcome La burnt square is crossed out; the shading separates the regionsthe regions, evaluated aloneregion 1 — 5region 2 — -3their sum is 2which is what the whole board is worththe regions were found by walking the board, evaluated separately, and their values added — the equality is checked, not claimed

Amazons, and when a position becomes a sum

Every technique on this site starts from a position already broken into independent parts. Amazons does not begin that way — the board is one fight until the arrows cut it, and the moment of cutting is something the play produces rather than the analyst assumes.

1 rung · positions 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.

1 rung · values Colnot next to your own colourworth 0a number — nobody is in a hurryoutcome P · Left may paint 4, Right 4Snortnot next to your opponent'sworth {{2 | 1} | {-1 | -2}}not a numberoutcome N · Left may paint 4, Right 4a ringed vertex is one somebody may still paint; a filled one is already painted

One board, two rules

Col forbids painting next to your own colour. Snort forbids painting next to your opponent's. One word differs, the boards are identical, and the values that come out are not the same kind of object.

1 rung · positions ↑ − 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.

1 rung · sums n →m123451234501234-10011-20011-3-1-100-4-1-100the 2×4 cakeis worth 1every entry checkedto be a whole numberblue where Left is ahead, red where Right is, shaded where the cake is worth nothinga value with no fraction and no star in it is a game nobody wants to move in

Cutcake, where every value is a whole number

A partizan game in which no position is ever worth a fraction, a star or a fight. Every value is an integer, the integer is a count of spare moves, and the pattern it follows is decided by binary digits.

1 rung · positions 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.

1 rung · positions 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.

1 rung · positions 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.

1 rung · limits 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.

1 rung · impartial 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.

1 rung · values 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.

1 rung · impartial 051015how many moves the game lasted1 spotBrussels — always 3Sprouts — 2 in these games2 spotsBrussels — always 8Sprouts — anywhere from 4 to 53 spotsBrussels — always 13Sprouts — anywhere from 6 to 84 spotsBrussels — always 18Sprouts — anywhere from 9 to 10every Brussels length matched 5n − 2 across 40 random games from each startand the figure refuses to draw itself if any of them does not

Sprouts, and the game that is not one

Two games played with dots and curves, invented in the same room, all but indistinguishable on paper. One is unsolved past forty spots. The other has no decisions in it at all — the winner is fixed before the first curve is drawn.

1 rung · positions -205{2 | -2}mean 0t = 2{5 | 1}mean 3t = 2{1 | 0}mean 1/2t = 1/2{3 | -1}mean 1t = 2{1/2 | −1/2}mean 0t = 1/2valuethe mean is the midpoint of the two options, and the temperature is half the distance between thema switch is worth nothing on average and everything to whoever moves in it

Worth nothing, and worth fighting for

A switch is a position both players want to move in. Its average value can be zero while the difference between getting there first and second is enormous, and that gap is a second number every position carries.

1 rung · values ∗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.

1 rung · positions 012345678910111213141204537861011913141220153486711910141213345620191012871511164532769018131211161553406810127121491517678191034513021617187869014531415131721086710125341516171809910111287131415161761951101198131201516171418762119107121421317618158192012131415119161718197810202113141211161517205619209714121316151718109122021711the value of the position with the queen on that square11 squares worth nothingevery one of them on the linesof slope φ = 1.6180…checked against ⌊nφ⌋, ⌊nφ²⌋and the table was never toldleft, down, or diagonally — a queen's moves, restricted to towards the corner

Wythoff's game, and the ratio nobody put there

Two heaps, three kinds of move, and losing positions that lie along a line of irrational slope. Nothing in the rules mentions a ratio, a length or a continuous quantity — and the golden ratio comes out anyway.

1 rung · impartial

All essays