Combinatorial Game Theory
who wins, and by how much
Concept

Loopy game — where it appears

A game in which a position can recur, so that a play need not end and the recursion defining a value has no base case. It is solved by working backwards from lost positions, and whatever that never reaches is drawn unless a rule gives the endless play to one player.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

What the notation costs to write. Every game born by each day, written in the brace notation and measured. The expressions are all distinct, which is what the notation is for, and by day three the typical one is twenty-two characters and the longest is fifty.

Where the braces stop

The brace notation names every game exactly — 1,474 games born by day three, 1,474 different expressions, no two alike. It also gets long: the middle one is twenty-two characters and the abbreviations everybody actually writes cover one game in twenty-three. And it has two hard edges. A game with a cycle in it has no finite expression at all, and the equation the minus sign encodes — that a game and its negative cancel — is false under misère play on every one of those 1,474.

history · Notation Every two-position loopy region, as two names. The 256 loopy regions of two positions, placed by the names of their onside and offside as identified against the 1,474 values born by day three. Ten names cover every side: 0, 1, −1, ∗, on, off, over, under, upon + ∗ and −upon + ∗. The largest groups are on & off with 94 regions and off & off and on & on with 53 each; 25 regions need only finite names.

A loop is written with two names

A region with a cycle in it has no brace expression, and every one of the 256 regions of two positions can be written anyway — as two names, the game it is when a play that never ends goes to Left and the game it is when it goes to Right. Checked against all 1,474 values born by day three, ten names cover every side, 25 regions need only finite ones, and the pair predicts every sum with a finite game, draws included: a draw arrives exactly where the two names disagree.

history · Notation Every region of three positions, counted. The 262,144 graphs on three positions reduced to the regions that are genuinely three positions with a cycle in them, and then split by whether the two-position vocabulary has a name for both of their sides.

Four thousand nine hundred regions with no name

Two positions give 256 regions and ten names cover every side of all of them. Three positions give 262,144 graphs, 110,934 genuine loopy regions — and 4,931 of those have a side that no name in the two-position vocabulary reproduces, with 3,990 of them named on one side and blank on the other. The count the earlier essay left open comes back in the affirmative.

history · Notation The guess, and what it covered. Two attempts to name the leftover sides out of the old vocabulary: every pair of the six stoppers, and every two-position region that is a stopper, each with small finite games added. Both cover nothing, and the count of distinct leftovers is what remains.

The names are not built out of the old ones

The guess was that a three-position region's missing names would be sums of two loopy ones — on plus over, and that family. Built and tried, every pair of the six stoppers covers none of the 4,931 regions that need one, and so does every two-position stopper there is, all seventy-nine of them with small games added. Thirteen names have to be invented, and forty-eight cover the whole census against ten at two positions.

history · Notation

Named alongside it

The objects these essays reach for when they reach for this one.

NotationEnumerationStopperCountingDisjunctive sumDrawEquivalenceExhaustive searchOn, the game that never stopsRegionUniquenessAdditivity

All concepts