Combinatorial Game Theory
who wins, and by how much
Concept

Identification — where it appears

Folding positions that are the same up to symmetry, which divides a table by at most the size of the group. What counts as the same position is a choice, and the choice changes both the size of the search and what the answer means.

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

Folding a 4×4 board by its symmetries. The size of a Domineering solver's table when positions related by a board symmetry are stored once. The saving rises toward the size of the symmetry group and stops there — it is a constant factor by construction, and no board is large enough to make it anything else.

What counts as the same position, and what that is worth

Folding a 4×4 Domineering board by its symmetries takes the table from 5,700 entries to 1,522 — a saving of 3.75, against a ceiling of exactly 4. An orbit cannot be larger than the group acting on it, so this is the one saving in the subject that can never change an exponent.

complexity · Identification Classes needed, as the heaps get bigger — Dawson's chess ·137. How many kinds of position there are, against how large a heap the universe allows. Under normal play the answer stops growing as soon as the Grundy values stop growing. Under misère play it does not stop, and every new class is a pair of positions that behave identically under normal play and differently under misère.

The cost is in the closure, not in the positions

Under normal play, Dawson's chess needs four classes for every heap up to twelve, because its Grundy values stay at three or below there. Under misère play the same game needs six, then twelve, and the number rises with the universe rather than with the position — which is a different kind of expense entirely.

complexity · Misere cost Generalized Geography. A token on a directed graph. A move slides it along an edge to a vertex not yet visited, and a player who cannot move loses. That is the whole game, and deciding who wins it is as hard as anything decidable in polynomial space — which is the strongest hardness claim anybody makes about a combinatorial game.

A token on a graph

Geography is an impartial game whose position is a vertex and a history, so a ten-vertex graph has ten thousand states rather than ten. Take the arrows off and the same game is decided by a maximum matching — first player wins exactly when every maximum matching covers the start, verified on 41 vertices across eight graphs. One word in the rules separates a polynomial criterion from a PSPACE-complete problem.

impartial · Geography Finding the parts costs the same whether there are any or not. Domineering boards of 4 squares by 5 with different squares blocked out, and what the decomposition is worth on each. The pass that finds the regions is a flood fill and visits every square once, so it costs the same on all of them. What it buys ranges from nothing — on the boards that do not decompose — to a saving of 2,808 positions, and it cannot tell which case it is in until it has run.

Finding the parts

Decomposition turns a product into a sum and is the largest saving in the subject. Nobody labels the regions. The pass that finds them costs the same on every board of a size — including the boards where there is nothing to find — and what it buys ranges from four orders of magnitude to nothing at all.

complexity · Decomposition What a day of canonical forms costs, written out and written once. Three costs for the values born by each of the first three days: every node written every time it occurs, every distinct subposition of a single form, and every distinct subposition of any form of the day. The last is one node per value, and the gap between the first and the last widens as the construction goes on.

The same position, written once

Writing out the canonical forms of day three takes 24,940 nodes. Naming each distinct subposition once inside each form takes 10,102, and naming each distinct subposition once across the whole day takes exactly 1,474 — one per value, because nothing appears inside a canonical form that is not itself a value of the day.

values · Reversibility 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.

complexity · Value cost A gap that widens without bound. Both savings as the number of components grows, enumerated where possible and given by the closed forms beyond.

One half multiplies, the other adds

The rung below priced the two halves of a substitution licence on sums of two Cram boards and predicted that the first half's saving would grow with the number of components while the second's would not. It is right, and both halves have closed forms: the component licence saves s^(k−1)/k and the subposition licence k·s over a shape count that never moves.

limits · Universes 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 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 12 classes, 7 questions. A grid for Dawson's chess with heaps up to nine: rows are the 12 misère classes of positions of at most four heaps, columns the 7 tests a greedy search chose, and each cell the outcome — N for the player to move, P for the other — when the test is added to the class.

Twelve classes, seven questions

Twelve misère classes of Dawson's chess were found by testing 715 positions against 715 others. Seven of those tests are enough to tell every class from every other — a greedy choice against a floor of four, since each test is one yes-or-no question. Kayles needs nine of 715 and Nim sixteen. The seven cost almost nothing to use and cannot be found without the whole closure, and they do not carry: the tests found with heaps up to seven tell apart only seven of the twelve classes with heaps up to nine.

complexity · Misere cost Four positions, sampled. Three samples of three thousand loopy regions on four positions, drawn with each possible move present at a chance of one half, about a third and a quarter. For each: how many regions have both sides named by the thirty-five names two-position regions use, by those together with the thirteen invented for three positions, and how many need a new name.

Four positions, sampled

Ten names write both sides of every loopy region of two positions, and forty-eight every region of three. Four positions are over four billion graphs and cannot be counted, but they can be drawn. Three thousand regions at each of three densities: the forty-eight names cover between 95.9 and 99.5 per cent, the thirteen names invented for three positions come back at four almost all of them, and the sparsest sample meets thirty-five sides nothing earlier reproduces — a floor of eighty-three names, and a curve that grows by accretion rather than collapse.

history · Notation

Named alongside it

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

Exhaustive searchMemoisationComplexityDomineeringPosition graphCanonical formDecompositionNimEnumerationEqualitySearch costSymmetry

All concepts