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.
Nim with heaps of 3, 5, 7. Heaps of counters; a move takes any number from one heap. The position is a loss for the player to move exactly when the binary digits of the heap sizes cancel in every column — the nim-sum — and that is the whole of the theory of Nim. 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.

 Backward induction on a game that ends, one round at a time. Zermelo's argument as it actually runs. Round zero is the positions where the player to move has no move at all, which is the only thing the procedure knows without being told; each later round is what those settle. Anything still unlabelled when nothing more can be deduced has no label and never will — and on a game with a cycle in it, that leftover is exactly the set of drawn positions. The theorem is a statement about this procedure terminating, and it names the winner of nothing. How it was found

The first theorem, and the winner it declines to name

Zermelo proved in 1913 that a finite game with no chance and no hidden information is decided before anybody sits down — every position is a win for one side or a draw, and which one is settled already. The proof is a labelling procedure, and watching it run shows exactly how little it says.

 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. Out in the world

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.

 A position is the sum of its parts. Four separate Hackenbush sprigs. A move is a move in one of them, so the position is their disjunctive sum, and its value is the sum of their values. Which part to play in is the entire decision, and the values are what makes it decidable. 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.

 The thermograph of {5 | 1}. Temperature runs up the page and value across it. Each wall is where a player is willing to move once a tax of that much is charged per move; above the temperature at which they meet, neither wants to move and the position is worth its mean value. The height of the meeting point is what is at stake. 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.

 Four things a position can be. Every position falls into one of four outcome classes, and only three of them correspond to a comparison with zero. The fourth — first player wins — is a position confused with zero, neither greater, smaller nor equal, and it is where the subject departs from arithmetic. 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.

 A position that comes back. Three positions whose moves lead round in a circle. Every value in this subject is defined by recursion on the options, and that recursion assumes play ends — here it need not, so the definition has nothing to stand on and the outcome may be a draw, which normal-play theory has no name for. 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.

 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. Out in the world

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.

 Bouton's invariant, checked over 512 positions. Nim positions in binary, one column per bit. Bouton's 1901 argument is that a position is a loss for the mover exactly when every column holds an even number of marks — and that from such a position every move breaks a column, while from any other position some move repairs them all. Both halves are checked here over every position in the range rather than illustrated once, and the middle row shows the repairing move being made. How it was found

The theorem that needed none of the theory

Bouton solved Nim completely in 1901, with an argument that mentions no value, no sum of games and no Grundy number, because none of the three existed. The argument is two closure properties and it is airtight — and run on any other game it fails at the step that does the work.

 Knowing who wins is not enough. Three pairs of positions, every one of which is in outcome class N on its own. Their sums are not all the same, and not all in the same outcome class — so the outcome of a sum cannot be worked out from the outcomes of its parts, and that is why the theory needs values. Sums and comparison

Outcomes do not add

Knowing who wins each part of a position tells almost nothing about who wins the whole. Counted over every sum of two values born by day two, six of the outcome table's ten entries are settled and four are not — and every settled one is settled by the order rather than by anything about outcomes. Two first-player wins reach all four classes between them.

 The mex, and the rules that cannot replace it. Six candidate rules for the value of an impartial position, each a function of its options' values, run over the same subtraction game. The top strip is the truth. Every candidate but the mex assigns zero to a position somebody wins, or a non-zero value to a position somebody loses, and the circle marks the first heap where each one does it — which is why two people reaching for the same rule four years apart is evidence about the rule rather than about them. How it was found

Two people, four years apart, one theorem

Roland Sprague proved it in 1935 and Patrick Michael Grundy proved it in 1939, neither knowing of the other. That looks like coincidence until the alternatives are examined — and the rule they both reached turns out to be the only one that can work at all.

 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. Out in the world

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.

 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. Out in the world

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.

 Wythoff's game, and the line the losing squares lie on. A queen moves left, down, or diagonally down-left any distance, and whoever cannot move loses. Every square carries the Grundy value the mex rule gives it. The squares worth nothing — the ones a player wants to hand over — lie along two lines whose slopes are the golden ratio and its reciprocal, in a game with no geometry and no continuous quantity in its rules. Impartial games

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.

 Cutcake: every value an integer. The value of an m by n cake, for every small m and n. Left cuts down, Right cuts across, and neither player ever gains by moving — so nothing is ever at stake, every value is a whole number, and the number says exactly how many spare moves one player has. Particular games

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.

 Every quantifier is a move. A quantified boolean formula with its quantifiers drawn as turns: an existential is a choice by the player to move, a universal a choice by the opponent. The same formula is put through the reduction to Generalized Geography and the two answers are checked against each other, so the prefix of quantifiers and the game beside it are one claim. What it costs

A puzzle asks once, a game asks alternately

Quantifier alternation is the whole difference between a puzzle and a game. One chooser is an existential and its answer is a witness somebody can check; two choosers taking turns is a prefix of alternating quantifiers, and the witness stops being an assignment and becomes a strategy.

 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. Out in the world

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.

 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. Out in the world

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.

 Clobber: every value smaller than every number. Blue and red stones on a small board. A move takes one of your own stones onto an orthogonally adjacent enemy stone, which is removed. Because adjacency is symmetric, a player has a move exactly when the opponent does — so no position can ever be worth a whole move to anybody, and every value that comes out is an infinitesimal. Particular games

A game where nobody can be ahead in moves

A blue stone beside a red one is a move for both players at once. So neither player can run out while the other still has something to do — and every value the game produces is smaller than every positive number, by the shape of the rule rather than by inspection.

 Clobber: every value smaller than every number. Blue and red stones on a small board. A move takes one of your own stones onto an orthogonally adjacent enemy stone, which is removed. Because adjacency is symmetric, a player has a move exactly when the opponent does — so no position can ever be worth a whole move to anybody, and every value that comes out is an infinitesimal. Values

The class where nobody runs out first

Three stones in a row — blue, blue, red — and the position is worth exactly up. Clobber cannot produce anything else, because adjacency is symmetric — a player has a move precisely when the opponent does, and a game with that shape can never be worth a whole move to anybody.

 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. Out in the world

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.

 Mock Turtles on 8 coins: every lost position. The rows a player to move has already lost, drawn in full. A filled disc is a coin showing heads. The set is closed under turning over every coin two of its members disagree about, which is what makes it a linear code, and the count of heads in the sparsest of them is the fewest coin turns that separate two lost positions. Impartial games

The losing positions are a code

Turn over one, two or three coins, and the rows a player has already lost turn out to be closed under adding two of them together. That makes them a linear code — and on eight coins it is the extended Hamming code exactly, sixteen words with a weight enumerator of 1 + 14x⁴ + x⁸, produced by a move rule that knows nothing about codes.

 7 positions of the same value, and how long each of them lasts. Nim positions whose heap sizes all nim-sum to zero. As games they are the same object: each is worth zero, each is a loss for the player to move, and each may be substituted for any other inside any sum without changing a single outcome. The bars are how many moves each one takes, from the shortest legal play to the longest. The value determines everything about who wins and nothing at all about when. Values

What a value leaves out

A value settles who wins, by how much, and what happens in every sum the position appears in. It says nothing about when. Seven positions here are worth exactly zero and interchangeable everywhere, and they run from two moves long to eighteen.

 a loop with a way out under three rules for never ending. One graph, one labelling, and three ways of reading the residue the labelling never reaches. A draw is not a computed outcome here — it is what is left over — so declaring infinite play a win for one side is a legal alternative that costs no extra search and changes who wins. Where it stops

When never ending is a win

Retrograde analysis labels a position a win when somebody can force the opponent to be stuck, and leaves everything else blank. Calling the blanks draws is a rule from outside the game — and two other rules are available. The labelling does not change under any of them; only the residue does, and on a three-cycle that residue is every position on the board.

All themes