Combinatorial Game Theory
who wins, and by how much
Generator

Domineering on 3×4 — and who wins

Domineering on 3×4 — and who wins
Domineering on 3×4 — and who winsA Domineering board with the outcome stated before anybody moves. Left places vertically, Right horizontally, and on this board Right wins whoever starts. Every reply the machine can make was worked out in advance from the game recursion, so it is following the analysis rather than searching.worth −3/2Right wins whoever movesstated before a move is madeyou place vertically · it places horizontallywith the script running, the vertical pairs become clickable and this claim can be tested

A Domineering board with the outcome stated before anybody moves. Left places vertically, Right horizontally, and on this board Right wins whoever starts. Every reply the machine can make was worked out in advance from the game recursion, so it is following the analysis rather than searching.

3 essays call play-domineering. 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

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

PositionWorth OutcomeDrawn in
3×4 −3/2 R A board that is a sum of its regions · "Left wins" has no short proof · Domineering · A position reached eleven ways is one position · The values of every small board · Which shapes are worth fighting over

It plays back

The winner is named before a move is made, and every reply was worked out in advance.

Where it is called

Changing this generator changes every one of these figures.

Domineering on 2 by 3. Left places vertical dominoes, Right horizontal ones, and a player who cannot place loses. The two players see different games on the same board, which is what partizan means — and the value that results is not a number. Particular games

Domineering

One player places dominoes vertically, the other horizontally, on a shared grid. The rules take one line, the values are a mess, and that mess is the point — this is what the theory looks like applied to a game nobody designed for it.

 One node per route, one node per position. For each board, the number of nodes in the recursion tree a solver with no memo table would walk, beside the number of distinct positions that tree contains, beside the longest run of moves in it. The first number is the cost of forgetting; the second is the size of the table that avoids it; the third is the stack, and it stays small however the other two grow. What it costs

A position reached eleven ways is one position

A 4×4 Domineering board has 5,700 positions in it and 6,257,129 routes through them. Three heaps of 7, 11 and 13 have 480 positions and 7.6 × 10¹⁶ routes. The gap between those two numbers is not an optimisation — it is the difference between a search that finishes and one that does not.

 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