Combinatorial Game Theory
who wins, and by how much
Series

Pairing — the series

8 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 7 symmetries, and the one that is a strategy. 4 games and 7 candidate symmetries, each tested by playing the strategy out against every opponent line rather than by argument. A pairing strategy needs a map that fixes the start, is an involution, and carries one player's moves to the other's — and the last condition is where most of these fail.

    The strategy that is a symmetry

    A pairing strategy is a symmetry of the board that turns one player's moves into the other's, and it wins without computing anything. Tested by playing it out rather than argued, it wins one of seven candidate symmetries across four games — exactly the Cram boards with both sides even, which is exactly where no domino is its own image.

    part 1 · impartial
  2. A thousand shapes, and twelve pairings. Cram on every connected shape of at most eight squares, with the search for a symmetry that answers each of the opponent’s moves. Every pairing found is a second-player win, most shapes have no involution at all, and the strategy accounts for a sixth of the second-player wins there are.

    Looking for the symmetry

    Answering every move with its mirror image wins Cram on a board with both sides even, which is the argument everybody meets. Asked of every connected shape of at most eight squares instead of of thirteen rectangles, it wins twelve — and accounts for a sixth of the second-player wins there are, because 852 of the 1,042 shapes have no symmetry to answer with in the first place.

    part 2 · impartial
  3. Parity decides it before the shape does. For each size, how many first-player wins can reach a position a half-turn pairs in a single move. Every odd size is nought and cannot be anything else, because a pairing needs an even number of squares and a move removes two.

    The symmetry one move away

    A pairing argument proves the second player wins and names no move to do it with. Asked of every shape of up to eight squares it settles twelve boards. Asked one move later — can the first player reach a position a half-turn pairs? — it settles 288, and which boards those are is decided by parity before anything about their outline is looked at.

    part 3 · impartial
  4. One test in front of a search. Five Cram boards solved with and without a check for a reachable pairing. A 4 × 5 board takes 17,348 node expansions without it and one with it.

    A check in front of a search

    The rung below found a pairing one move away on 288 of the 767 even first-player shapes, and asked what a solver that tested for one before recursing would save on a real game. On an even Cram board it saves nearly the whole search — a 4 × 5 board takes 17,348 node expansions without the check and one with it — and the depth profile shows why that number flatters: the check settles every winning position at the opening and at the last two moves, and about one in ten in between.

    part 4 · impartial
  5. The check fires on positions that lose. How often the pairing check accepts a position, and how often the position is a loss. On every even board in the sweep it is wrong between an eighth and a fifth of the time.

    The check that was not a check

    The rung below asked for a depth-conditioned solver and named the board to measure it on. Building it found two things first. The pairing check is unsound at interior positions — on a four by five Cram board it fires on 8,613 positions and 1,026 of them are losses — and the board it named has twenty-five squares, so the check can never fire there at all. Repaired, the check is right everywhere, and the policy that pays is the root alone.

    part 5 · impartial
  6. Two symmetries, the same two clauses. The half-turn pairing and the reflection pairing written side by side, with the fixed squares and self-paired dominoes each has to exclude.

    A pairing, and the pairing

    The rung below repaired the half-turn check and asked whether a reflection would fire where it does not. It does — forty positions of 58,830 on the largest board — and it is sound, and it is worth one node in a thousand to a solver. It can never fire on an empty rectangle at all, which is why the ladder's whole subject is the half turn.

    part 6 · impartial
  7. The clause that was free. Five requirements on a pairing strategy, with which of them each map meets.

    A symmetry that is not a pairing

    The quarter turn was the last symmetry a Cram pairing argument had not tried, and the one a square board seemed to offer. It fires on the empty four by four and it settles nothing the half turn misses — and the reason is a clause four rungs of this anchor never had to write down, because every map tried so far was its own inverse.

    part 7 · impartial
  8. A pairing no motion of the square gives. The smallest Cram shape carrying a pairing that is not a rigid motion, with its three pairs drawn as lines between the squares they join.

    A pairing that is not a symmetry

    Every pairing strategy this ladder has found is a rigid motion of the square, and the requirement mentions no geometry at all. Searching all 8.8 million fixed-point-free involutions instead of the eight maps more than doubles what a pairing explains — and the smallest new one turns out to be a reflection with its two fixed squares swapped.

    part 8 · impartial

All series