Combinatorial Game Theory
who wins, and by how much
Concept

Involution — where it appears

A map that is its own inverse, so applying it twice returns what it started from. It is the property a copying strategy needs and the one nobody on this site had written down, because every symmetry tried had it.

Named by 3 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 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 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.

impartial · Pairing

Named alongside it

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

CramEnumerationImpartialSecond-player winStrategySymmetryCounterexampleExhaustive searchGrundy valueNormal playPairingDecomposition

All concepts