Combinatorial Game Theory
who wins, and by how much
Concept

Stopper — where it appears

A loopy game with no alternating run that could go on for ever, so play in it ends however long it takes. Stoppers are the loopy games that behave enough like finite ones to be added and compared, and each side of a region with a cycle is one.

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

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 Four positions, sampled. Three samples of three thousand loopy regions on four positions, drawn with each possible move present at a chance of one half, about a third and a quarter. For each: how many regions have both sides named by the thirty-five names two-position regions use, by those together with the thirteen invented for three positions, and how many need a new name.

Four positions, sampled

Ten names write both sides of every loopy region of two positions, and forty-eight every region of three. Four positions are over four billion graphs and cannot be counted, but they can be drawn. Three thousand regions at each of three densities: the forty-eight names cover between 95.9 and 99.5 per cent, the thirteen names invented for three positions come back at four almost all of them, and the sparsest sample meets thirty-five sides nothing earlier reproduces — a floor of eighty-three names, and a curve that grows by accretion rather than collapse.

history · Notation Half the new sides are sums. The 50 sides of four-position loopy regions that no earlier name reproduces, tested against every sum of two games from the day-two values, the stoppers and the thirteen three-position names. 23 are such sums, 15 of them using a three-position name; 27 are not.

Each size is built from the last

At three positions the sides that needed new names were sums of nothing older: no pair of stoppers, and no two-position stopper with a small game beside it, wrote any of them. At four positions the thirteen names three positions forced are available as parts, and they change the answer. Of the fifty sides the samples met that nothing earlier names, twenty-three are sums of two earlier games — fifteen of them using a three-position name — and twenty-seven are not.

history · Notation Three parts close most of the gap. The fifty sides four-position regions needed new names for, split by the smallest sum of earlier games that writes them: 23 by a sum of two, 16 only by a sum of three, and 11 by neither, with how often each group turned up in the samples.

Composition at every size

Twenty-seven of the fifty new four-position sides were written by no sum of two earlier games. Sums of three write sixteen of them — seven plain finite games born after day two, nine built on the names three positions forced — and leave eleven, met seventeen times in nine thousand regions. Run the same test one size down and the story the counts told falls apart: eight of the thirteen names three positions were thought to invent are sums of up to three older parts, two of them just two finite values. Every size composes. What each invents is a residue — five, then eleven.

history · Notation

Named alongside it

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

NotationExhaustive searchVocabularyDisjunctive sumDrawEnumerationIdentificationLoopyLoopy gameRetrograde analysisSamplingCounterexample

All concepts