Combinatorial Game Theory
who wins, and by how much
Concept

Transposition table — where it appears

The store a search keeps of positions it has already valued, so that a position reached two ways is computed once. What it saves is bounded by how often positions repeat, and what it costs is the memory that usually runs out before the clock does.

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

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.

complexity · Value cost One licence, five prices. The third licence measured by saving, by table size, by expansions avoided, and by work under two implementations.

The price of asking what the parts are

The third licence lets a solver look up a region rather than a position, and the rung below priced it by the entries it stores. Priced by the work it costs, it saves between a third and two thirds of the expansions and pays for them with a flood fill at every node — six times the total. A square would have to be ten times cheaper than a table probe before it broke even.

limits · Universes 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 What a short key gets wrong. A memoised who-wins search of 4 × 5 Domineering using a Zobrist key of 10 to 32 bits, run under 60 random keys at each length and checked against the exact answer: how many stored positions share a key, how many runs store a wrong verdict or name the wrong winner, and what checking the whole position would cost instead. At 16 bits 59 runs store a wrong verdict and 19 name the wrong winner.

A key shorter than the position

A who-wins table for 4 × 5 Domineering addressed by a 16-bit Zobrist key stores a wrong verdict in 59 runs of 60 and names the wrong winner of the empty board in 19. The pairs of positions sharing a key follow the birthday count exactly while addresses are scarce, and fall away to nothing once the key has more bits than the board has squares, because a Zobrist key is linear. Symmetry and value identify positions that really are the same; a short key identifies positions that differ, at a rate set by arithmetic.

complexity · Identification One family of confused positions. Two 4 × 5 Domineering positions with Left to move that share every bit of an 18-bit Zobrist key, differing only on 4 marked squares whose words cancel. Under that key 100 of 136 confused pairs differ on exactly those squares; its other families hold 25 and 11.

A check bit halves the average and not the key

Real transposition tables keep a few of a key's bits beside each verdict and trust an entry only when they match. On 4 × 5 Domineering each such check bit halves the average number of wrong verdicts, exactly as the birthday count says. It does not halve any one key's. A Zobrist key confuses positions in families — every pair that differs on one set of squares whose words cancel — and a bit removes a family whole or not at all, so from eighteen bits to nineteen thirty of fifty-eight keys lose every confusion and fourteen keep every one.

complexity · Identification Two squares a key never needs. A 4 × 5 Domineering board shaded like a chessboard, with two squares of the same shade in rows 1 and 2 marked. Because a domino covers one square of each shade, a vertical domino covers one square in an odd row and one in an even row, and turns alternate, the other eighteen squares determine both marked squares: a key that leaves them out confuses none of the 48,670 reachable positions.

A key is a code, and two squares come free

The families of positions a Zobrist key confuses are the words of a binary linear code — the sets of squares whose words cancel — so choosing a key is choosing a code. On 4 × 5 Domineering the textbook choice, a code with the largest minimum distance, confuses more stored positions than a random key at fourteen, sixteen and nineteen bits. The choice that reads the board confuses none at eighteen: two squares of one shade, in rows of different parity, are decided by the other eighteen, and no seventeen-bit key is exact.

complexity · Identification

Named alongside it

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

DomineeringMemoisationSearch costDecompositionExhaustive searchIdentificationZobrist hashingCatalogueDisjunctive sumEnumerationHeuristicNormal play

All concepts