Combinatorial Game Theory
who wins, and by how much
Concept

Catalogue — where it appears

A stored table of small positions with their values, consulted instead of searching. What it costs is measured in entries and what it buys in searches avoided, so the useful question is not how large it can be but which positions it should hold.

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

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 A count that forgets, at six rates of forgetting. The hit rate of a component table limited to 10, 20 and 40 entries under recency, under a use count halved every 25 to 5,000 lookups, under a use count never forgotten, and against the best fixed table chosen with the whole run in view. At every size some half-life beats recency, and the longest half-lives fall back toward the rule that never forgets.

A count that forgets

A Domineering solver with room for ten component values does better evicting whatever it used least recently than evicting whatever it used least often, and the explanation offered was that a use count never forgets. Halve every count at a fixed interval and the count overtakes recency at every table size — by less than half a point, and only with the right interval. The right interval grows with the table: a quarter of a game's worth of lookups at ten entries, five games' worth at forty.

complexity · Value cost The board held fixed, and recency still wins. Each of the four board sizes played on its own for 650 games, with a component table of ten entries under recency, a use count never forgotten and the best of three half-lives, against the best fixed ten shapes chosen with the whole run in view. Counting beats recency only on the 4 × 5 board; on 5 × 5, 6 × 6 and 7 × 7 recency beats both counting and the fixed table, by the widest margin on 7 × 7.

One board, and recency still wins

A Domineering solver's table of component values did best evicting whatever it used least recently, and the explanation was that the run changed board size three times. Take the change away — play all 650 games on one board — and counting wins back its lead only on the smallest board. On 5 × 5, 6 × 6 and 7 × 7 recency still beats both counting and the best fixed table, by the most on the largest. The locality recency exploits is not between boards or between opening and endgame. It is inside a single move.

complexity · Value cost

Named alongside it

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

DecompositionDomineeringHeuristicRegionApproximationEnumerationMemoisationValue costSamplingSearchInvariantSearch cost

All concepts