Combinatorial Game Theory
who wins, and by how much
Concept

Search — where it appears

The exhaustive walk over a position's game tree that answers a question by trying everything. It is what every value on this site is computed by, and its cost is the reason a catalogue of small regions is worth building.

Named by 11 essays across 3 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 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 check fires on positions that lose. How often the pairing check accepts a position, and how often the position is a loss. On every even board in the sweep it is wrong between an eighth and a fifth of the time.

The check that was not a check

The rung below asked for a depth-conditioned solver and named the board to measure it on. Building it found two things first. The pairing check is unsound at interior positions — on a four by five Cram board it fires on 8,613 positions and 1,026 of them are losses — and the board it named has twenty-five squares, so the check can never fire there at all. Repaired, the check is right everywhere, and the policy that pays is the root alone.

impartial · Pairing Four solvers on one sum. The states each solver has to distinguish on a three by four board plus a three by five, with one more substitution allowed at each step. A million and a half becomes fourteen.

Half a licence is nearly all of it

The rung below priced the substitution licence a restricted universe gives a solver and asked what half of one is worth — the licence to rewrite components but not subpositions. It is worth nearly the whole saving. Rewriting components collapses a million and a half states to three thousand six hundred; rewriting subpositions collapses those to eight hundred and eighty-four, and splitting the pieces takes it to fourteen.

limits · Universes 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 Two symmetries, the same two clauses. The half-turn pairing and the reflection pairing written side by side, with the fixed squares and self-paired dominoes each has to exclude.

A pairing, and the pairing

The rung below repaired the half-turn check and asked whether a reflection would fire where it does not. It does — forty positions of 58,830 on the largest board — and it is sound, and it is worth one node in a thousand to a solver. It can never fire on an empty rectangle at all, which is why the ladder's whole subject is the half turn.

impartial · Pairing 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 The clause that was free. Five requirements on a pairing strategy, with which of them each map meets.

A symmetry that is not a pairing

The quarter turn was the last symmetry a Cram pairing argument had not tried, and the one a square board seemed to offer. It fires on the empty four by four and it settles nothing the half turn misses — and the reason is a clause four rungs of this anchor never had to write down, because every map tried so far was its own inverse.

impartial · Pairing 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 What the folding costs to do. The same search over a 4 × 4 Domineering board run twice, once folding positions by symmetry and once not, with everything counted. The fold stores 3.75 times fewer entries and spends 17.5 times more elementary operations to decide where to put them.

What it costs to notice a repetition

Folding a 4 × 4 Domineering board by its symmetries takes the table from 5,700 entries to 1,522. It also spends 559,424 square-mappings to work out where each entry goes — seventeen and a half times the entire cost of not folding. The saving has a ceiling of four and the price has no ceiling at all, and knowing which currency each is paid in is the difference between an optimisation and a habit.

complexity · Identification

Named alongside it

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

EnumerationDecompositionDomineeringMemoisationApproximationHeuristicRegionSymmetryComplexityCramDisjunctive sumExhaustive search

All concepts