Combinatorial Game Theory
who wins, and by how much
Concept

Vocabulary — where it appears

The set of names a notation needs to write every position of a given size, such as the onside and offside names of loopy regions. Counting it at each size says whether a notation stays usable as positions grow or turns into a list as long as the positions themselves.

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

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

Named alongside it

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

Exhaustive searchNotationStopperCounterexampleCountingDrawEnumerationEquivalenceIdentificationLoopyLoopy gameOn, the game that never stops

All concepts