Combinatorial Game Theory
who wins, and by how much
Concept

Solved game — where it appears

A game whose answer is known, in one of three senses that are routinely spoken as one word. The three senses are routinely spoken as one word, and a game can be solved in the weakest and open in the strongest.

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

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.

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.

applied · Strategy stealing 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.

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.

complexity · Complexity Three questions about the same board. For each sum of two positions: the cost of deciding who wins each part alone, of deciding who wins the whole sum by search, and of computing what each part is worth. The middle question is in the middle on seven of the eight, and the exception is the sum whose two parts are identical.

The question in the middle

Between knowing who wins each part and knowing what each part is worth sits the question a player actually has: who wins the board. Priced on sums of two it lands between the other two on seven of eight, cheaper than the values by up to eight times. On sums of three, with nothing repeated, it is dearer than the values on five of six — because a component multiplies a search and only adds to a value.

complexity · Value cost 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 searchCertificateStrategy stealingCounterexamplePairing strategyStrategySymmetryComplexityHeuristicHexIntractableNim

All concepts