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.

Out in the world

Games people played before there was a theory, and questions outside game theory that a game answers. Every one of them solved here rather than cited — including the one every child is taught to play wrong.

A 2 × 3 board of boxes, 6 still on the table. A Dots and Boxes position drawn as dots and lines, and — where the figure asks for it — the same position as a strings-and-coins graph: one coin per box, one string per line, and the border lines running to the ground. Lines already played are solid, lines still available are dashed, and a box with no strings left has been pocketed. The footer carries the exact net score the solver computes from here and the normal-play verdict on the same position.

The game in every exercise book

Dots and Boxes is played by more people than every game in this collection put together, and everybody is taught the same rule — take every box available. The rule is wrong. Establishing that takes a solver rather than an opinion, and the solver says how wrong, on which boards, and by how many boxes.

9 figures · Dots and Boxes The impartial game inside the scoring one. For every position of a Dots and Boxes board, two questions asked separately: who wins the scoring game, and who wins Nimstring — the same position under the normal-play convention, with no score kept. The bars show how often the two answers agree, grouped by how many boxes are still on the table. Agreement is near-total when there is enough left to be worth controlling and falls away when there is not.

The chains decide it before the boxes do

Under every game of Dots and Boxes there is an impartial game with no score in it, and it settles the question the scoring game keeps asking — who ends up having to open. The rule players learn as folklore falls out of it, and so do the exceptions nobody mentions.

8 figures · Dots and Boxes 1 ko point, no ko rule. A ko fight drawn as a position graph and labelled by retrograde analysis: blue edges are Black's captures, red are White's, and each position carries the verdict for whichever side is to move. Positions the propagation never reaches are drawn — neither player can force a win and the game does not end — and they appear only where the rules permit a repetition.

The rule that makes Go a finite game

A ko is a point in Go where a capture can be recaptured for ever, and every set of rules forbids it. That prohibition is not etiquette or tidiness — it is the hypothesis that puts Go inside the class of games every theorem on this site is about, and removing it removes the values.

9 figures · Go Every row of 8 squares, and the 36 values they hold. A census of Kōnane rows: how many arrangements of a row of squares carry each value, with the shortest row carrying that value printed beside it. Most arrangements are worth nothing at all; the rest spread over numbers, halves and quarters, stars, switches and infinitesimals — the whole vocabulary of the theory, from a game that predates it.

A game older than the theory

Kōnane was played on carved lava boards in Hawai‘i long before anybody wrote a brace notation, and its rule for losing is the normal-play convention arrived at some centuries early. Evaluate a row of it and the answers are halves, quarters, stars and infinitesimals — the theory's whole vocabulary, out of a game that was not built to display any of it.

10 figures · Kōnane Hex on 3 × 3, with every winning opening found. A rhombic Hex board with each cell marked according to whether taking it first wins. Left joins the top edge to the bottom and Right joins left to right; a filled board is always a win for exactly one of them, so the search needs no draw test. Strategy stealing proves that a winning opening exists without exhibiting one — these are the ones exhaustive search finds, on a board small enough for exhaustive search to finish.

The theorem that names a winner and no move

Strategy stealing proves that the first player wins Hex and wins Chomp, on every board, in about four lines. It exhibits no move, contains nothing a move could be extracted from, and is not going to. The moves have to come from somewhere else, and where they come from runs out almost immediately.

9 figures · Strategy stealing a path with every link doubled: the criterion and the game. A Shannon switching graph with the two marked vertices in gold. Short secures links and Cut deletes them; Short wins by joining the two marks. Lehman's criterion says Short wins moving second exactly when some subgraph holding both marks splits into two edge-disjoint spanning trees — drawn here in blue and red where one exists. The verdicts beside the graph come from playing the game out, and the criterion is computed without looking at the game at all.

A winning strategy that is a spanning tree

The Shannon switching game was sold in a box in 1960 and solved in 1964, and the solution is not an assertion that somebody wins. It is a property of the graph anybody can check, and the strategy falls straight out of it — whichever link the opponent cuts, take its partner in the other tree.

9 figures · Switching The gaps of ⟨5, 7⟩, which are the moves. A Sylver Coinage position drawn as the numerical semigroup it is. Gold squares are the numbers already named; plain squares are sums of them, and so cannot be named again; magenta squares are the gaps, which are exactly the legal moves. The largest gap is the Frobenius number, marked F — past it every integer is reachable, which is why the game has finitely many moves left and must end.

The game that is a number system

In Sylver Coinage two players name integers and nobody may name a sum of what has already been named. Its positions are not boards — they are numerical semigroups, its termination is a theorem of Sylvester's from 1884, and the question of who wins after the opening move 16 has been worth a thousand dollars since 2017.

9 figures · Sylver A game where the last move decides nothing. Rows of coins taken from either end, with the exact score for each side moving first. Under the normal-play convention this family is settled entirely by the parity of the row — nobody is ever without a move until the coins run out — so normal-play theory returns the same answer for every row and it is not the answer anybody wants. The scoring answer depends on nothing but the numbers.

Counting at the end changes everything

Go is scored. So are Dots and Boxes, chess and almost everything anybody plays for money — and none of them is the kind of game this site's whole apparatus is built for. The simplest scoring game there is shows what that costs — the normal-play theory gives every position of it the same answer, and the answer is useless.

8 figures · Scoring A blocked file, and the tempo it holds. Files of a blocked pawn ending: a White pawn below, a Black pawn above, and a gap between them that either side may close one square at a time. Each file carries the value the game recursion gives it. With only single steps available a file is worth a star or nothing, by the parity of the gap, so the whole position is tempo and no material at all — which is what a chess player means by mutual zugzwang.

A pawn ending is a sum

In a blocked pawn ending the material is level, the files never speak to each other, and whoever has to move is the one in trouble. Chess calls that mutual zugzwang; this site calls it a P-position; and the two vocabularies were built four decades and one subject apart to say the same thing.

10 figures · Chess The cold positions, written in Fibonacci base. The first several cold pairs of Wythoff's game with both heap sizes written in Fibonacci base — as sums of non-consecutive Fibonacci numbers, which every integer has exactly one of. Blue is the smaller heap and red the larger. Read as digits, the pair is a shift: the larger numeral is the smaller one with a zero appended, and the smaller one always ends in an even number of zeros.

The digits say which move wins

Wythoff's cold positions are usually given as a pair of golden-ratio formulas. Written in Fibonacci base they are a statement about digits instead — the smaller heap ends in an even number of zeros and the larger is the same numeral shifted up a place — and a rule about digits answers a question about a heap of a trillion.

7 figures · Wythoff's game Where the count and the value part company. Amazons endgames whose arrows have already cut the board into regions, with the territory count beside the computed value. Territory gives every empty square to whichever amazon can reach it in fewer moves, which is what Amazons programs compute. The positions drawn are the ones where that number gets the outcome wrong, and they have something in common: each is worth a switch, so there is no number for the count to have been right about.

When a real board falls apart

Amazons is played competitively, and late in a game the arrows have cut the board into regions no piece can cross. From that moment the position is a disjunctive sum — arrived at by the play rather than assumed — and the territory count every program uses can be measured against what the sum is actually worth.

8 figures · Amazons One set, described three ways that share no arithmetic. Wythoff's cold positions can be stated as the Beatty pairs of the golden ratio, as a greedy construction over the integers that mentions no constant, and as a condition on Fibonacci numerals. None of the three consults the game. The fourth column is the game — a mex table over the moves — and all four name the same set of cold pairs over the whole square, which is what the figure counts.

A set with three descriptions, and a function with none

Wythoff's cold positions can be written three ways that share no arithmetic — an irrational constant, a greedy rule, a condition on Fibonacci digits — and all three are exact. The same game's Grundy values have no closed form at all. Both facts are about one table, and the gap between them is the subject.

6 figures · Wythoff's game Every part on its own is worth nothing. The Grundy value of each chain and loop considered as a game by itself, and three real Dots and Boxes boards used to check the turn-by-turn walk against the win-or-lose solver already used here. Every component alone is a second-player win, which is exactly what makes the nim-sum useless.

The parts are worth nothing and the sum is not

Every chain and every loop in Nimstring, taken alone, has Grundy value nought. So the Sprague–Grundy theorem predicts that every position built from them is worth nought — and ninety-six of the two hundred and seven positions checked here are not. The theorem is not being misapplied; it does not apply, because a capture keeps the turn. What replaces it is smaller and sharper: count the short chains, and one long component of any kind reverses the parity.

7 figures · Dots and Boxes Every position, by how much is left. Sylver Coinage positions counted by genus — the number of integers still unnameable — with the share on which the player to move loses. The parity of the genus very nearly decides the game: odd rows run between a fifth and a half, even rows between nothing and a thirteenth.

A parity with a first exception

Sort every Sylver Coinage position by how many numbers are still unnameable and the game very nearly falls to parity: odd rows are between a fifth and a half positions the mover loses, and the first three even rows hold none at all. The rule has a first counterexample at genus eight, where it is a single position out of sixty-seven, and eleven more at genus ten. It is a tendency wearing away from both ends rather than a law with exceptions.

7 figures · Sylver Which clause of the rules produces which kind of value. Every combination of pawn-file clause in range, sorted by the kind of value it produces. Files where both pawns can advance are all-small and their values are nimbers and infinitesimals. A file where one pawn is stuck behind a friendly piece gives the other side free moves and is worth an integer. A file whose middle square can be held stops the other pawn the moment somebody reaches it, and is worth a switch — a position both players want to move in. The dictionary is read off the evaluation rather than asserted.

What has to break before a pawn is worth a number

Every value the blocked-file model can hold is an infinitesimal, and the reason is one sentence about the move rule rather than anything about pawns. Break that sentence — a pawn stuck behind a friend, a square only one side can hold — and integers, switches and positions worth fighting over arrive at once.

7 figures · Chess

All ladders · Every object named here · The position index · Figures that play back · Search