Combinatorial Game Theory
who wins, and by how much
Generator

Chomp: 35 rectangles, all first-player wins, and where the winning moves are

Chomp: 35 rectangles, all first-player wins, and where the winning moves are
Chomp: 35 rectangles, all first-player wins, and where the winning moves are. Strategy stealing proves in two lines that the first player wins Chomp on every rectangle larger than a single square, and it produces no move at all: the argument works by refuting the assumption that the second player has a strategy, and a refutation names nothing. The numbers in the grid are how many opening moves actually win, obtained by labelling the whole position graph. The two columns are the same theorem and completely different objects.

Strategy stealing proves in two lines that the first player wins Chomp on every rectangle larger than a single square, and it produces no move at all: the argument works by refuting the assumption that the second player has a strategy, and a refutation names nothing. The numbers in the grid are how many opening moves actually win, obtained by labelling the whole position graph. The two columns are the same theorem and completely different objects.

3 essays call strategy-stealing. 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.

The positions it draws

6 distinct positions, harvested by running this generator again at the options each essay passed it.

PositionWorth OutcomeDrawn in
1 × 2 bar N N The first theorem, and the winner it declines to name · The theorem that names a winner and no move
2 × 1 bar N N The first theorem, and the winner it declines to name · The theorem that names a winner and no move
3 × 1 bar N N The first theorem, and the winner it declines to name · The theorem that names a winner and no move
4 × 1 bar N N The first theorem, and the winner it declines to name · The theorem that names a winner and no move
5 × 1 bar N N The first theorem, and the winner it declines to name · The theorem that names a winner and no move
6 × 1 bar N N The first theorem, and the winner it declines to name · The theorem that names a winner and no move

Where it is called

Changing this generator changes every one of these figures.

Backward induction on a game that ends, one round at a time. Zermelo's argument as it actually runs. Round zero is the positions where the player to move has no move at all, which is the only thing the procedure knows without being told; each later round is what those settle. Anything still unlabelled when nothing more can be deduced has no label and never will — and on a game with a cycle in it, that leftover is exactly the set of drawn positions. The theorem is a statement about this procedure terminating, and it names the winner of nothing. How it was found

The first theorem, and the winner it declines to name

Zermelo proved in 1913 that a finite game with no chance and no hidden information is decided before anybody sits down — every position is a win for one side or a draw, and which one is settled already. The proof is a labelling procedure, and watching it run shows exactly how little it says.

 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.

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

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.

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