Combinatorial Game Theory
who wins, and by how much
Generator

Everything walked, and the little that is kept

Everything walked, and the little that is kept
Everything walked, and the little that is kept. For each position: how many squares it is written on, how many positions its graph holds, and how many nodes are in the value that comes out. The value is smaller than the search by two or three orders of magnitude, and it is the only part worth storing — which is exactly why a component's value can be computed once and reused in every sum it appears in.

For each position: how many squares it is written on, how many positions its graph holds, and how many nodes are in the value that comes out. The value is smaller than the search by two or three orders of magnitude, and it is the only part worth storing — which is exactly why a component's value can be computed once and reused in every sum it appears in.

15 essays call value-vs-search. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

The positions it draws

9 distinct positions, harvested by running this generator again at the options each essay passed it.

PositionWorth OutcomeDrawn in
Clobber 2×4 0 P A game where nobody can be ahead in moves · Maundy Cake
Clobber 3×3 ∗ N A game where nobody can be ahead in moves · The heap is not the position · A position reached eleven ways is one position
Cutcake 5×5 0 P Maundy Cake
Domineering 3×3 1 | −1 N Knowing who wins, and knowing what it is worth · Maundy Cake · The heap is not the position · A position reached eleven ways is one position
Domineering 4×4 {0, {{2 | 0}, {2 | {2 | 0}} | {2 | 0}, {{2 | 0} | 0}} | 0, {{0 | {0 | −2}}, {0 | −2} | {0 | −2}, {{0 | −2} | −2}}} N Knowing who wins, and knowing what it is worth · A position reached eleven ways is one position
Nim heap of 11 ∗11 N The heap is not the position
Toads and Frogs TT..FF ∗ N The heap is not the position · The strip nobody has a formula for
Toads and Frogs TT.TFF {1 | ∗} L The strip nobody has a formula for
Toads and Frogs TTT...FFF 0 P Knowing who wins, and knowing what it is worth · The strip nobody has a formula for · A position reached eleven ways is one position

Where it is called

Changing this generator changes every one of these figures.

One node per route, one node per position. For each board, the number of nodes in the recursion tree a solver with no memo table would walk, beside the number of distinct positions that tree contains, beside the longest run of moves in it. The first number is the cost of forgetting; the second is the size of the table that avoids it; the third is the stack, and it stays small however the other two grow. What it costs

A position reached eleven ways is one position

A 4×4 Domineering board has 5,700 positions in it and 6,257,129 routes through them. Three heaps of 7, 11 and 13 have 480 positions and 7.6 × 10¹⁶ routes. The gap between those two numbers is not an optimisation — it is the difference between a search that finishes and one that does not.

 Clobber: every value smaller than every number. Blue and red stones on a small board. A move takes one of your own stones onto an orthogonally adjacent enemy stone, which is removed. Because adjacency is symmetric, a player has a move exactly when the opponent does — so no position can ever be worth a whole move to anybody, and every value that comes out is an infinitesimal. Particular games

A game where nobody can be ahead in moves

A blue stone beside a red one is a move for both players at once. So neither player can run out while the other still has something to do — and every value the game produces is smaller than every positive number, by the shape of the rule rather than by inspection.

 Toads and frogs. Toads move right and frogs move left, one square into a gap or hopping over exactly one opponent. A player unable to move loses. It can be played on squared paper by anybody, and its values are immediately stranger than the game looks. Particular games

The strip nobody has a formula for

Some toads, a gap, some frogs. Two counts and a spacing is the whole description, and the values that come out of it are integers, stars, switches with eighth-point options and a down — four classes inside one two-parameter family, which is why nobody has written the formula.

 Maundy Cake: the pieces must be equal. The same cake as Cutcake, cut by the same two players, with one extra rule: a cut must divide the cake into equal pieces, and every piece stays in play. The values are still whole numbers, but the arithmetic that decides them is not Cutcake's — it counts prime factors rather than binary digits. Particular games

Maundy Cake

Cutcake with one word added: a cut must divide the piece into equal parts. The values are still whole numbers, and the rule this site has been repeating about them is false — over all 1,296 cakes to 36×36 the largest-odd-divisor account has 946 counterexamples. What survives is a count of prime factors, and it says who wins without saying by how much.

 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. What it costs

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.

 Every heap up to 40, won or lost. Heap sizes with the outcome for the player who moves first. The lost ones are shaded; they are exactly the Fibonacci numbers, which is a fact about a game with one heap, no board and no geometry in it anywhere. Impartial games

The heap is not the position

Fibonacci Nim bounds a move by twice the previous move, which puts the state outside the board: a heap of six with a cap of two and a heap of six with a cap of five are different games. So there is nothing to add and no Grundy value to compute — and the game is completely solved anyway. The opener loses on exactly the nine Fibonacci numbers up to 120, and the smallest term of the Zeckendorf numeral is a winning move in all 110 winnable heaps.

 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. What it costs

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.

 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. What it costs

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.

 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. What it costs

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.

 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. What it costs

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.

 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. What it costs

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.

 Three catalogues, ten entries each. The catalogue built from a sweep against two self-built ones, on reach and on content. What it costs

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.

 The online rule beats the oracle. The three offline orderings against the two online eviction rules, all at ten entries over the same lookups. What it costs

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.

 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. What it costs

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.

 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. What it costs

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.

The whole library · The position index · The figures that play back