Combinatorial Game Theory
who wins, and by how much
Concept

Hex — where it appears

A connection game on a rhombus of hexagons, in which one player joins the left and right edges with a chain of their own cells and the other joins top to bottom. A filled board holds exactly one such chain, so there are no draws, and that is what lets strategy stealing give the first player the win on every square board without naming a move.

Named by 2 essays across one field — 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 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.

CertificateCounterexampleExhaustive searchSolved gameStrategy stealingChompDeterminacyHeuristicIntractableNormal playOutcome classPairing strategy

All concepts