Combinatorial Game Theory
who wins, and by how much
Concept

Solver — where it appears

A program that computes a position's outcome or value by searching, with a table of what it has already worked out. What it costs is measured here in positions expanded rather than in seconds, so that a saving is a property of the method rather than of the machine.

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

Where in a game a board falls apart. Every position reachable from an empty Domineering board, grouped by how many dominoes have been placed, with the share that have fallen into two or more live pieces. The share is nought at both ends of the game and around three fifths in the middle.

How often a board falls apart

A decomposition turns a product into a sum, so a solver wants to know how often one arrives. Over every position of a 4 × 4 Domineering board the answer is 47 per cent — nought for the first two moves, three fifths in the middle, and nought again at the end. What one decomposition is worth is the other half of the answer and it is a factor of 1.8.

complexity · Decomposition Two readings of one sequence. The three licences with their savings and their tables, which order them oppositely.

The licence that weighs nothing

The third substitution licence is constant in the number of components, exactly as predicted, and it saves under two times where the first saves seventy-six million. Priced by its table instead of by its saving it is the only one of the three whose cost does not run away — which reverses the order three rungs of this anchor have put them in.

limits · Universes Three catalogues, ten entries each. The catalogue built from a sweep against two self-built ones, on reach and on content.

A catalogue that builds itself

A solver that stores every region it has to evaluate builds a catalogue out of its own games. After 650 games it holds 232 of the 1,042 shapes and is still growing — and the order things arrive in is nearly arbitrary while the order they are consulted in reproduces a census of a strong player's games almost exactly.

complexity · Value cost One board, two answers to how many pieces it is in. Every position reachable from a small Amazons opening, counted by depth, under two ways of deciding whether two squares are in the same region. Counting only edge neighbours, a third of all positions are in pieces; counting corners too, an eighth are.

A wall an amazon can walk through

An arrow burns a square for good, so an Amazons board that has fallen into pieces should stay in pieces. Over 127,583 positions it does not: fifty-one thousand moves put two regions back together. Every one of them is a single diagonal step, and what is wrong is not the game but the rule used to find the regions — which was borrowed from a game whose pieces lie along the board's own lines.

complexity · Decomposition

Named alongside it

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

DecompositionEnumerationRegionApproximationDisjunctive sumDomineeringSearchBoardCatalogueComplexityValue costAmazons

All concepts