Combinatorial Game Theory
who wins, and by how much

Who wins, and by how much.

Two players, no dice, nothing hidden, and the player who cannot move loses. That is a narrow enough set of rules to be worth exactly — every position has a value, the value is computed rather than estimated, and positions add. These are essays about what comes out of that, one idea at a time, with the arithmetic done rather than asserted.

The picture is the numeral. Blue-red Hackenbush strings and their values. Left may cut a blue edge, Right a red one, and everything above the cut falls. The value of each string is a number, and reading the string from the ground upward gives the binary expansion of exactly that number.
Fig. 1 Hackenbush strings and what they are worth. Left may cut a blue edge, Right a red one, and everything that loses its footing falls. Each string is worth a number — and reading it from the ground upward gives the binary expansion of exactly that number, so the picture is not a diagram of the value, it is a way of writing it. Both routes are computed here, and the figure refuses to build if they disagree.

Start anywhere

the first twelve of 466 — the rest are here

The picture is the numeral. Blue-red Hackenbush strings and their values. Left may cut a blue edge, Right a red one, and everything above the cut falls. The value of each string is a number, and reading the string from the ground upward gives the binary expansion of exactly that number. 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.

8 figures Which questions are answerable. The theory is exact and much of it is expensive. Values are computable by definition; computing one for a position of any size is a different matter, and deciding the winner of a generalised board game is complete for PSPACE — as hard as anything solvable in polynomial space. What it costs

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 What reversing the ending destroys. Everything that makes normal play tractable is a theorem about who moves last, and misère play contradicts every one of them. The positions are unchanged; the means of evaluating them is gone, and what replaces it is far heavier. 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 of the normal-play theory stops being true. It is the cheapest possible modification and the most expensive.

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

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

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

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

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

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

8 figures Comparing two positions is playing their difference. To decide whether one position is worth at least another, subtract and see who wins moving second. It is the only definition of comparison the subject has, and it produces a partial order — some pairs come out confused, which no comparison of numbers ever does. Sums and comparison

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 Domineering on 2 by 3. Left places vertical dominoes, Right horizontal ones, and a player who cannot place loses. The two players see different games on the same board, which is what partizan means — and the value that results is not a number. Particular games

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

7 figures

Seven ways in

a flat list of essays stops being navigable somewhere in the low hundreds; these do not

The nine fields

The subject in the order it builds itself: the games where both players have the same moves, then what a position is worth, then what happens when positions are added, and last the places the machinery gives way.

9 fields

Series

An idea, and the distinct arguments that stand against it, ordered by depth. A field says what an essay is about; a series says what else there is to say about it.

92 ideas

Every object named here

The third axis, after the field and the series: the games, values and theorems themselves, and every essay that touches each one.

344 objects

The position index

Every position this site draws, with the value the solver computed for it and the essay that argues about it. The corpus, browsable as a corpus.

every reply worked out in advance

Figures that play back

The positions small enough to solve completely, where the winner is named before the reader starts and every reply was worked out in advance.

state the winner, then lose

The figure library

Every generator behind the pictures, each one rendered at its defaults, with the essays that instantiate it. The reuse the collection runs on, made visible.

146 generators

What arrived last

The collection grows in batches and each batch has a shape. This is the most recent one, in the order it was written, for a reader who has been here before.

newest first

Threads running through

themes, not chapters

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.

42 essays

One clause decides it

Change a word of the rule and the values change completely. A cliff or a wall, a jump allowed or forbidden, a pass that may or may not end the game — the same board, and nothing in common.

96 essays

The sum is the object

Real positions break into independent parts that are played at once, and adding them up is what the theory was built to do. The hard step is the splitting, not the addition.

86 essays

The parts do not decide the whole

Outcomes do not add. Neither do temperatures, atomic weights, misère outcomes or the value of an auction. Which quantities survive being added is the question every method here turns on.

54 essays

Not every game is a number

Some positions are worth a half or a quarter. Others are worth something no number can express, and the ones that are not numbers are where the subject becomes interesting.

47 essays

How much is at stake

A position is worth something on average and worth something more to move in first, and the second number is the one a player feels. Temperature is that number, and most of what it measures is not where it is expected.

99 essays

Small things decide

Infinitesimals are smaller than every positive number and are not zero. In a close game they are the whole margin, which is why the theory bothers with them.

28 essays

Equal, better, or neither

Two positions can be equal, one can be better, or the pair can be genuinely incomparable — a fourth relation with its own symbol. Deciding which is a search rather than a look, and equality quantifies over every game there is.

78 essays

The notation is not the position

A brace form, a binary numeral, an octal code and a thermograph are four ways of writing a position down, and each throws something away. Occasionally one of them turns out to be the argument.

89 essays

A theorem that names no move

Knowing who wins and knowing what to play are different achievements, and the subject is full of results that supply the first and refuse the second. A bound is sometimes all there is.

99 essays

It depends on the company

Sente, independence, equality, the size of a move and even the winner turn out to be facts about the rest of the board rather than about the position in front of the reader.

43 essays

It has to end

Every value here is defined by a recursion that needs play to stop. Sometimes that is obvious, sometimes it is a theorem, and sometimes the game ends with nothing bounding when.

31 essays

The theory runs out

Misère play, scoring, three players and computational hardness each break something essential. Knowing which of them is biting is most of knowing where a game stands.

75 essays

Play it and lose

The strongest argument this subject can make is to state the winner before the reader starts, and then be right. These are the essays carrying a figure that plays back.

20 essays

Assertions that reject

Every claim here is given a test it could fail, and the tests that matter are the ones that have failed. These are the essays where a check refused something — a guess, a rival explanation, or the essay's own first draft.

18 essays

What a search costs

A value is worth what it costs to find. These essays price the search rather than quoting the answer: positions visited, states stored, and the size of the board where the counting stops.

42 essays