Combinatorial Game Theory
who wins, and by how much
Concept

Cost — where it appears

What a question about a position takes to answer, counted in positions expanded rather than in seconds. Every price on this site is measured that way so that two questions can be compared without a machine in the comparison, and the currency matters: deciding a winner, computing a value and solving a sum are three different sums of money.

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

Knowing who wins, and knowing what it is worth. Nine positions, each evaluated twice by an instrumented evaluator that starts with an empty cache. The third column counts what deciding the winner costs and the fourth counts what the canonical form costs, in the currency each question is actually paid in.

Knowing who wins, and knowing what it is worth

Deciding a winner expands positions. Computing a canonical form expands pairs of positions, because a comparison unfolds as a recursion over one subposition of each and the reduction makes many comparisons. Measured on the same nine positions by an evaluator that starts empty every time, the second costs between 1.3 and 279 times the first, and the ratio grows with the tree.

complexity · Value cost What each reach answers. Catalogues of four to ten squares against the regions four sizes of board actually produce. The coverage rises from about 54 per cent to about 74 while the catalogue grows from 15 shapes to 12,871.

Where to stop building

The rung below priced a catalogue of small regions against the search it replaces and found the crossover. What it could not say is how far to build, and the coverage answers that: going from four squares of reach to ten multiplies the catalogue by 860 and lifts the share of regions it answers from 54 per cent to 74. The price of a point of coverage runs from five shapes to five thousand.

complexity · Value cost One test in front of a search. Five Cram boards solved with and without a check for a reachable pairing. A 4 × 5 board takes 17,348 node expansions without it and one with it.

A check in front of a search

The rung below found a pairing one move away on 288 of the 767 even first-player shapes, and asked what a solver that tested for one before recursing would save on a real game. On an even Cram board it saves nearly the whole search — a 4 × 5 board takes 17,348 node expansions without the check and one with it — and the depth profile shows why that number flatters: the check settles every winning position at the opening and at the last two moves, and about one in ten in between.

impartial · Pairing A product against a sum. The mean cost ratio on two components and on three. The saving from substituting grows with the board rather than staying a fixed factor.

A product against a sum

A company closed under both addition and options licenses a solver to rewrite any subposition, and the rung below found that exactly the nimber groups have both closures. Priced on Cram boards, that licence is the difference between walking a product of position sets and walking their sum — four to twenty-five times on two components, twenty-four to a hundred and sixty-one on three — and it is available to impartial games because their class representative is a heap rather than a form.

limits · Universes

Named alongside it

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

Exhaustive searchMemoisationEnumerationComplexityCramDomineeringHeuristicImpartialApproximationCanonical formComparisonComponent

All concepts