The nine fields

Fields

The subject divides into nine, and the order is 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 together, then the games worth fighting over and the particular games the theory was built on, then the two places the machinery gives way, what any of it costs to compute, how it was found, and where it turns up outside itself.

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

Both players have the same moves. Every such position is a Nim heap, and the theorem that says so is the field's first.

51 essays

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

What a position is worth — numbers, and the things that are not numbers, and how to find the simplest one.

64 essays

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

Real games break into independent parts. Adding them up is the whole method, and comparing them is how it is checked.

52 essays

Temperature

How much is at stake, measured. Thermographs, cooling, and why a player moves where the game is hottest.

54 essays

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, Nim, Domineering, Toads and Frogs — the specific games the general theory was built to explain.

64 essays

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 and loopy games: the two places the theory itself gives way — values that stop composing, and a recursion with no bottom.

51 essays

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

Every theorem here can be true and the answer still out of reach. What a search costs, what a proof of a win looks like, and where the shortcuts are.

48 essays

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 theory looks inevitable in retrospect and the record says otherwise. The older arguments are run here rather than recounted — and one of them still answers a question nothing since has answered.

38 essays

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

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.

44 essays

Three other ways through

a field says what an essay is about; these say what else there is to say about it, what it names, and what can be played