Combinatorial Game Theory
who wins, and by how much
Generator

A winning strategy on 3×3, drawn whole

A winning strategy on 3×3, drawn whole
A winning strategy on 3×3, drawn whole. The whole of one player's winning strategy on a small Domineering board: their own move at each of their turns, and every reply the opponent has at each of theirs. The strategy branches only where the loser chooses. Its size is what somebody would have to be handed to check the claim that this player wins, and it is far larger than the claim itself.

The whole of one player's winning strategy on a small Domineering board: their own move at each of their turns, and every reply the opponent has at each of theirs. The strategy branches only where the loser chooses. Its size is what somebody would have to be handed to check the claim that this player wins, and it is far larger than the claim itself.

1 essay calls strategy-tree. 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

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

PositionWorth OutcomeDrawn in
2×3 2 | −1/2 N A board that is a sum of its regions · "Left wins" has no short proof · One board, two rules · Cooling by exactly one · Domineering · Turn the board through a right angle · Worth nothing, and worth fighting for · The values of every small board · Tiny, miny, and the sizes below every size · What can be struck out · What counts as the same position, and what that is worth · Where the impartial theory stops · Which option the reduction keeps · Which shapes are worth fighting over
2×5 1/2 L "Left wins" has no short proof · The values of every small board
3×2 1/2 | −2 N "Left wins" has no short proof · Cooling by exactly one · Turn the board through a right angle
3×3 1 | −1 N A board that is a sum of its regions · "Left wins" has no short proof · One board, two rules · Cooling by exactly one · Cram · Domineering · Worth nothing, and worth fighting for · The values of every small board · Tiny, miny, and the sizes below every size · What counts as the same position, and what that is worth · Which option the reduction keeps · Which shapes are worth fighting over

Where it is called

Changing this generator changes every one of these figures.

A winning strategy on 3×3, drawn whole. The whole of one player's winning strategy on a small Domineering board: their own move at each of their turns, and every reply the opponent has at each of theirs. The strategy branches only where the loser chooses. Its size is what somebody would have to be handed to check the claim that this player wins, and it is far larger than the claim itself. What it costs

"Left wins" has no short proof

A complete solution of Nim on heaps of 7, 11 and 13 is 480 table entries. A winning strategy for the same position — one move of the winner's at each of their turns, and an answer to every reply — has 56,167,022 nodes in it. The answer is smaller than the proof by a factor of a hundred thousand.

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