Pairing strategy — where it appears
Named by 24 essays across 3 fields — each of them below, with the objects they name alongside it.
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.
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.
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.
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.
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.
A pairing that is not a symmetry
Every pairing strategy found so far for these boards 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.
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.
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.
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.
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.
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.
Cram with the last move losing
Under misère play every Cram rectangle to twenty squares is tame at the start except 3 × 6 and 4 × 5, and twelve of the fifteen boards two rows deep behave like one counter or none. The pairing that settles even boards under normal play hands the misère game to the first player, who wins by any vertical domino. And the tame boards are not tame inside: wild positions appear on boards as small as 3 × 4, always at ten empty squares, the length at which the strip goes wild.
Three pairings and no order
The potential lost four-by-five Hex for Down, and fifty-five re-weightings lost it too, which left the question whether anything that orders the cells can hold the board. The plainest ordering — one fixed list, whatever the position — holds none of the boards the pairing is known for, and on four by five the best it can do is the left column. At the other end, every table of replies that wins a small board is a pairing, and four by five has exactly three pairings, each using all twenty cells.
A current through the board
In the early 1950s Shannon and Moore built a machine that played Hex by wiring the board as a network of resistors and reading its move off the electrical potential. There is no theorem behind that rule, and on every Hex board small enough to solve it can be scored against perfect play. On boards to twelve cells it takes a winning cell on more than 98 per cent of the positions where one exists, far above chance. And it loses: every board of three rows or more it has to defend, and four by four moving first, because an opponent needs only one of the two per cent and can steer the game to it.
A circuit asked once
The Hex machine's circuit rule loses every board past two rows that it has to defend, and the strategy that holds those boards is a pairing — a partner for every cell, fixed before the game begins. So make the circuit commit: consult it once per cell on an empty board and never again. Its table answers twelve openings with four cells, and loses every board the running circuit lost. Forced to choose a whole pairing, it picks a losing one under seven of eight ways of reading its scores; the eighth finds the winning pairing of three by four by a margin of rescaling and gives up two by four for it.
A pairing is checked, not measured
The Hex machine's circuit chose pairings near the winning ones and never at them, which left a finite question: does any score of a pair of cells, computed from the board alone, have a winning pairing as its best? The obvious scores count the chains a pair shares. All four hold two by three; on three by four the plain count cannot choose between a winning pairing and a losing one, and the corrected counts choose the loser; on four by five every one loses. The reason is arithmetic — a sum will give up one chain to cover two others twice. Told which chains it missed, the count finds the diagonal pairing at one rate in three, and by then it is checking, not measuring.
Two neighbours keep a pairing, three lose it
In the switching game on points, Short wins moving second by a pairing when every smallest set of points that cuts A from B holds both points of some pair. On every graph of seven points — 971,104 of them — every Short win has one, at every degree. In random link games, where each contested point has two neighbours, every win has one too, although the winning strategy follows trees that change as the game goes. The first wins with no pairing appear at nine points with four neighbours and at ten points with three: a cubic graph Short wins whoever moves, which no fixed set of answers explains.
The weights were not the argument
A chain count corrected by its own misses held the four-by-five Hex board with the diagonal pairing, the one pairing there with a sentence behind it, and the hope was that its weights were the sentence in numbers. They are not. One rate in twelve holds the board and one start in twenty; the weights it ends on survive five per cent of noise and not twenty; and weighting exactly the chains the argument relies on finds no winning pairing at all. Told which pairing to prefer, a measurement reaches any of the three in a dozen corrections. What chain weights can do is rule a pairing out, and on three by four they rule out one that wins.
A pairing that changes once
The cubic ten-point graph is a win for Short that no fixed pairing explains, and the full strategy that does explain it is a tree of 68 decisions. One change is enough: after Cut's first deletion Short claims a stated point, and from then on a fixed pairing of what is left holds every cutting set. Four such plans, eight pairs between them, answer every opening. Of the 23 pairless wins in the samples, 21 need one change and two need a second, and in both the second is a forced claim. Unless the hard problems collapse, no fixed number of changes can be enough for every graph.
Two reflections and a corner
Hex boards of n rows and n + 1 columns are won by the player with the nearer edges, by a pairing, and the count of pairings that do it ran two, three, three. It is three again on five by six, against 1,225 chains, and three on six by seven, against 16,097. They are the same three every time, and they are not three strategies: one is the classical reflection, and the other two are a reflection across the board's other diagonal, which joins its two far corners, in two versions that disagree about six cells. Each is a rule a sentence long, and each holds on every board out to ten by eleven.
The teacher's game
A machine that weighs Across's chains could be taught every winning Hex pairing on four by five, and on three by four it could never be taught the one pairing another winner covers chain by chain. Whether anything else could hide from it — a winner covered not by one rival but by a mixture of several — is a question about a game between a teacher choosing weights and a rival choosing pairings, and Jean Ville's 1938 theorem of the alternative, written for von Neumann's games, answers it in general. On five by six and six by seven every winner is taught in sixteen corrections or fewer, and nothing hides at all.
Two losers that average to a winner
On Hex boards to 6 × 7, a machine that weighs the opponent's winning sets could be taught every winning pairing except one, which another single winner covered. Ville's alternative allowed a second way to be out of reach — covered only by a mixture — and the switching game on points, where winners are many, is where it turns up. None in all graphs of seven points or in 4,000 of eight; 35 covers at nine and ten points. Every one is the even average of two losing pairings, and on six graphs Short wins and no weighting can teach the machine any winning pairing at all.
Blocking is not enough
Everybody knows noughts and crosses is a draw, and the usual explanation is that the second player can always block. That explanation is false. Against an opponent who can only block, the first player wins, from the centre or any corner. The game is a draw only because the second player's blocks build threats of their own. On fifteen boards solved outright, it is the only one where those two things come apart: everywhere else a draw is a draw because blocking is enough.
Three ways to know a draw
A draw on a board too large to search has to be certified, and there are two standard certificates: a pairing of cells and the Erdős–Selfridge sum over lines. Set against exhaustive search, both miss 4 × 4, and a rule taken from the sum holds there anyway. The sum looks far stronger until pairs are allowed to serve several lines at once. Then across 440 boards up to 12 × 12, the sum certifies no draw that a pairing does not, and a pairing certifies 36 that the sum cannot.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchStrategyCertificateCounterexampleSymmetryHeuristicHexStrategy stealingCramImpartialMove selectionEnumeration