Combinatorial Game Theory
who wins, and by how much
Series

Value cost — the series

10 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · complexity
  2. Three questions about the same board. For each sum of two positions: the cost of deciding who wins each part alone, of deciding who wins the whole sum by search, and of computing what each part is worth. The middle question is in the middle on seven of the eight, and the exception is the sum whose two parts are identical.

    The question in the middle

    Between knowing who wins each part and knowing what each part is worth sits the question a player actually has: who wins the board. Priced on sums of two it lands between the other two on seven of eight, cheaper than the values by up to eight times. On sums of three, with nothing repeated, it is dearer than the values on five of six — because a component multiplies a search and only adds to a value.

    part 2 · complexity
  3. 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.

    part 3 · complexity
  4. 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.

    part 4 · complexity
  5. 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.

    part 5 · complexity
  6. 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.

    part 6 · complexity
  7. 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.

    part 7 · complexity
  8. The online rule beats the oracle. The three offline orderings against the two online eviction rules, all at ten entries over the same lookups.

    The table that changes its mind

    The advice that ten entries chosen by use serve nine lookups in ten was untested: it describes a table sorted after the fact rather than a solver that only ever held ten. A solver that only ever held ten gets 94.2 per cent — beating the best ten chosen with the whole run in view, because there is no best ten.

    part 8 · complexity
  9. 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.

    part 9 · complexity
  10. 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.

    part 10 · complexity

All series