Combinatorial Game Theory
who wins, and by how much
Generator

An argument that names a winner, and a search that names a move

An argument that names a winner, and a search that names a move
An argument that names a winner, and a search that names a move. Strategy stealing written out as its steps, with the hypothesis it rests on marked: an extra stone of one's own is never a disadvantage. Beside it, what exhaustive search supplies and the argument cannot — the number of openings each game has and how many of them win. The proof reaches every board size and yields no move; the search yields every move and reaches almost no board.

Strategy stealing written out as its steps, with the hypothesis it rests on marked: an extra stone of one's own is never a disadvantage. Beside it, what exhaustive search supplies and the argument cannot — the number of openings each game has and how many of them win. The proof reaches every board size and yields no move; the search yields every move and reaches almost no board.

2 essays call existence-only. 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

Changing this generator changes every one of these figures.

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.

 a path with every link doubled: the criterion and the game. A Shannon switching graph with the two marked vertices in gold. Short secures links and Cut deletes them; Short wins by joining the two marks. Lehman's criterion says Short wins moving second exactly when some subgraph holding both marks splits into two edge-disjoint spanning trees — drawn here in blue and red where one exists. The verdicts beside the graph come from playing the game out, and the criterion is computed without looking at the game at all. Out in the world

A winning strategy that is a spanning tree

The Shannon switching game was sold in a box in 1960 and solved in 1964, and the solution is not an assertion that somebody wins. It is a property of the graph anybody can check, and the strategy falls straight out of it — whichever link the opponent cuts, take its partner in the other tree.

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