Combinatorial Game Theory
who wins, and by how much
Concept

Value cost — where it appears

What it costs to answer a question about a position, counted in positions expanded rather than in seconds. Deciding the winner and computing the value are different prices, and the gap between them is what a catalogue of small regions is bought against.

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

When a catalogue starts paying. How many decomposed boards a catalogue of regions has to answer before building it costs less than searching each board directly. Five boards for regions of four squares, two hundred for regions of eight.

When the catalogue starts paying

The rung below priced two questions — who wins one board, and what it is worth — and named the third: a program pays for a family of regions once and answers every board over them by addition. The crossover is between five boards and two hundred, depending on how far the catalogue reaches, and it falls as the board grows. The whole catalogue of every region to eight squares costs one part in seventy-six of one undecomposed five-by-five board.

complexity · Value cost The same coverage, an eighth of the shapes. Catalogues ordered by size against catalogues ordered by frequency, at the same coverage. The frequency order wins at every reach and by more at each one.

A catalogue that knows what it will meet

The rung below priced a catalogue of regions by its reach and found the coverage saturating, and asked what a catalogue ordered by frequency would cost instead. Eight shapes answer half the components a played Domineering board produces; a catalogue by size needs fifteen for the same, and 1,042 for what 119 chosen by frequency reach. Three quarters of a size-ordered catalogue never turns up in play at all.

complexity · Value cost Which catalogue is safe. Catalogues built from one style of play and used against another. A catalogue measured on random play over-serves a strong player and not the reverse.

The catalogue a strong player needs

A Domineering catalogue built from random play faces an objection that could overturn it: random play is not play. A player that reads the board produces the same head — eight of the ten commonest shapes — and concentrates far harder: 114 entries answer nine tenths of what it meets, against 2,018. And a catalogue measured on random play over-serves it, while the reverse fails.

complexity · Value cost 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

Named alongside it

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

ApproximationDecompositionEnumerationCatalogueDomineeringHeuristicRegionSearchMemoisationDisjunctive sumInvariantSolver

All concepts