Combinatorial Game Theory
who wins, and by how much
Series

Identification — the series

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

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

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

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

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

    part 5 · complexity

All series