Combinatorial Game Theory
who wins, and by how much
Concept

Pairing strategy — where it appears

A winning strategy consisting of a symmetry: whatever the opponent does, restore it. It needs the symmetry to carry one player's moves to the other's and to fix nothing a single move can cover, and it computes nothing at all.

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

Cram on 4 by 4: the pairing strategy. Cram is Domineering with the orientations shared: either player may place a domino either way up, so both players have exactly the same moves and the game is impartial. Every position therefore has a Grundy value, and this board's was computed by the mex rule over its own placements.

Cram

Domineering with one word of the rule changed: both players may place a domino either way up. That makes the game impartial, and the entire partizan apparatus collapses into a single Grundy value — on the 4 × 4 board, Domineering's canonical form runs to 114 characters of nested braces and Cram's answer is the one character 0.

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

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

impartial · Pairing Thirty-two words, four of them lost. Every position of five heaps grouped by the parities of its heaps in decreasing order of size. Each word is uniform, and four of the thirty-two are losing.

The parities, in size order

The rung below settled four of six parity classes in bounded Moore's Nim and asked whether the sizes pick out the losing positions in the two it could not. They do — but only through the order they put the parities in. Sort the heaps largest first, read off their parities, and that five-bit word settles the whole game at every width of move, with the losing words forming a subspace.

impartial · Moores-nim 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 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 The Bridg-It board of size 3, both players at once. A Bridg-It board of size 3: blue dots in 4 rows of 3, red dots in 3 rows of 4, interleaved. Every bridge blue can usefully build is drawn in blue and every bridge red can usefully build in red, and each blue bridge crosses exactly one red one. Blue's switching graph and its planar dual have the same numbers of points and links, because the dual is red's board turned a quarter.

Cut is Short on another graph

Everything proved about the switching game is proved from Short's side, and Cut appears only as the player whose moves get enumerated. On a graph drawn without crossings Cut does not need a theory of its own: deleting a link is securing the link that crosses it in the dual, so Cut's game is Short's game on a different graph. Bridg-It is the board that is its own dual — one link short of two trees at every size, which is why its first player wins.

applied · Switching Chomp to 12 × 8: one needle on every bar but one. Every Chomp rectangle up to 12 columns by 8 rows, with the number of winning opening moves in each cell, found by search. All but one have exactly one; the 10 × 8 bar has 2. Cells in blue belong to the families whose winning move can be stated in a sentence — a single row, two rows, or a square; cells in gold are found only by searching.

Where the needle has a sentence

Strategy stealing proves the first player wins every Chomp bar and names no square to take. On two families the square can be said in a sentence — a square bar and a bar two rows deep — and in both the sentence is a pairing that names every later move too. Three rows deep the needle wanders, and the observation that every bar has exactly one needle survives ninety-four rectangles and fails on the ninety-fifth.

applied · Strategy stealing Hex on 3 × 4: the nearer edges win whoever starts. Two copies of a Hex board of 3 rows and 4 columns. On the left each cell is coloured by whether Down, joining top to bottom, wins by taking it first: all 12 do. On the right each cell is coloured by whether Across, joining left to right, wins by taking it first: none do. Down's edges are one row nearer together than Across's, and Down wins whoever moves first.

A board one column wider

Strategy stealing proves the first player wins Hex, and it needs three things: no draws, an extra stone never hurting, and rules that treat the two players alike. Add one column to the board and the third goes. The player whose edges are now nearer together wins whoever moves first — and does it with a table of pairs that names every reply, checked against every line to a board of twenty cells.

applied · Strategy stealing Two replies to the first stone. The 4 by 5 Hex board after Across's first stone in row 1, column 1, with every empty cell labelled by the weight of Across's unblocked chains through it. The potential answers in the heaviest cell, row 2, column 4; the pairing, which wins this board for Down, answers in row 1, column 2.

A potential that names every move

Strategy stealing names no move, and the pairings that do name moves need a board with the right symmetry. The Erdős–Selfridge potential needs neither: Down, moving second in Hex, takes the empty cell through which Across's unfinished chains weigh most. Its guarantee reaches only boards two rows deep. It wins far past the guarantee — on every board of three rows that Down can win — and then, on a four-by-five board that a table of pairs wins for Down with certainty, it answers Across's first stone in a different cell and loses along the bottom edge.

applied · Strategy stealing An edge bonus, on every board it could help. The Erdős–Selfridge potential for Hex with the chains along the outer rows weighted more heavily, on six boards. No bonus wins the four-by-five board the plain potential loses, and the bonus costs Down 4 boards it was already holding.

The winning reply is the fourth choice

The repair proposed for the potential was to weigh an edge chain more heavily. Fifty-five weightings later, none holds the four-by-five board, and an edge bonus costs Down four boards it was already holding. The reason is not the numbers: over 393,660 turns of the pairing that does hold that board, the potential would take the same cell 26.1% of the time, and the winning cell is its 3.7th choice on average and as low as its seventeenth.

applied · Strategy stealing

Named alongside it

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

Exhaustive searchStrategySymmetryStrategy stealingCertificateImpartialCounterexampleCramEnumerationP-positionSolved gameBoard

All concepts