Combinatorial Game Theory
who wins, and by how much
Generator

Hex on 3 × 3, with every winning opening found

Hex on 3 × 3, with every winning opening found
Hex on 3 × 3, with every winning opening found. A rhombic Hex board with each cell marked according to whether taking it first wins. Left joins the top edge to the bottom and Right joins left to right; a filled board is always a win for exactly one of them, so the search needs no draw test. Strategy stealing proves that a winning opening exists without exhibiting one — these are the ones exhaustive search finds, on a board small enough for exhaustive search to finish.

A rhombic Hex board with each cell marked according to whether taking it first wins. Left joins the top edge to the bottom and Right joins left to right; a filled board is always a win for exactly one of them, so the search needs no draw test. Strategy stealing proves that a winning opening exists without exhibiting one — these are the ones exhaustive search finds, on a board small enough for exhaustive search to finish.

12 essays call hex-board. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

Where it is called

Every one of these figures is a drawing of the same construction, so a correction to it corrects them all.

Hex on 3 × 3, with every winning opening found. A rhombic Hex board with each cell marked according to whether taking it first wins. Left joins the top edge to the bottom and Right joins left to right; a filled board is always a win for exactly one of them, so the search needs no draw test. Strategy stealing proves that a winning opening exists without exhibiting one — these are the ones exhaustive search finds, on a board small enough for exhaustive search to finish. Out in the world

The theorem that names a winner and no move

Strategy stealing proves that the first player wins Hex and wins Chomp, on every board, in about four lines. It exhibits no move, contains nothing a move could be extracted from, and is not going to. The moves have to come from somewhere else, and where they come from runs out almost immediately.

 Three things the word “solved” is used for. The three standard senses of a solved game, priced on positions this solver can settle completely. Ultra-weak names the winner; weak supplies a strategy from the opening; strong supplies one from every position. They differ by orders of magnitude, and a claim that a game is solved is nearly useless until it says which of the three it means. What it costs

Three different claims are all called solved

Hex is solved in the sense that the first player provably wins, by an argument that names no move whatever. Nim is solved in the sense that a formula gives the right move from any position at any size. Between them sit strategies for one opening, and databases of a few billion positions. The word covers all four.

 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. Out in the world

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.

 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. Out in the world

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.

 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. Out in the world

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.

 Orders, weights and pairs. For five Hex boards Down wins moving second: whether any fixed order of cells holds the board, whether the Erdős–Selfridge potential holds it, and how many sets of pairs meet every one of Across's chains in a whole pair. A fixed order holds only 2 × 4; the potential holds every board but 4 × 5; 4 × 5 has exactly three pairings. Out in the world

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 Hex board read as a circuit. A three-by-four Hex board with Down to move, one Down stone and two Across stones. Each empty cell carries a disc whose area is the current through it when both players' edges are held at a unit voltage; the busiest cell is the current rule's move. The three cells that actually win for Down are shaded, and the busiest cell is not among them. How it was found

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.

 Twelve openings, four answers. A three-by-four Hex board. Each cell is labelled with the cell the current rule of Shannon and Moore's Hex machine takes for Down when Across has a single stone on it. The twelve answers are only four cells, shaded, each answering three openings. How it was found

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.

 One chain given up. Two pairings of the three-by-four Hex board. Left, the pairing the chain-sharing scores choose, with the one chain it misses shaded. Right, the diagonal pairing, which meets all 25 chains. How it was found

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.

 One rate in twelve. The chain count reweighted by the chains it misses, at 12 rates from 1.1 to 3, on the Hex boards 2 × 3, 3 × 4 and 4 × 5. The small boards are held at every rate by the diagonal pairing; 4 × 5 is held only at × 1.5, round 46, and every other rate stalls with chains still missed. How it was found

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.

 Three, again. Every set of disjoint pairs meeting each of Across's minimal chains in a whole pair, on Hex boards 2 × 3 to 5 × 6: 2, 3, 3 and 3 pairings on 5, 25, 148 and 1,225 chains. Every one uses every cell, is unchanged by a half-turn, and is written by one of three rules. Out in the world

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.

 Every winner but one. A perceptron over chain weights taught to make each winning Hex pairing the heaviest, on boards 3 × 4 to 6 × 7. Every winner is reached in at most sixteen corrections except the cross pairing of 3 × 4, which another winning pairing covers on every chain. How it was found

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.

The whole library · The position index · The figures that play back