Combinatorial Game Theory
who wins, and by how much
Concept

Pairing — where it appears

A strategy that answers every move with a fixed partner move, so the answer is always available and the opponent runs out first. It proves a win without any value being computed, which makes it the cheapest kind of argument in the subject and the one that works only where a position has a symmetry to exploit.

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

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.

impartial · Pairing 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.

impartial · Pairing 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.

impartial · Pairing 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.

impartial · Pairing 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.

impartial · Pairing

Named alongside it

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

CramEnumerationImpartialSymmetryStrategyCounterexampleExhaustive searchParitySearchGrundy valueHeuristicInvariant

All concepts