Combinatorial Game Theory
who wins, and by how much
Series

Search — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    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.

    part 1 · complexity
  2. How much of the board a who-wins search walks. Positions a memoised who-wins search of 4 × 5 Domineering expands under six move orderings, drawn to scale against the 48,670 positions the board has. Leaving the opponent fewest replies expands 1,125; trying losing moves first expands 30,202; all six find the same winner.

    The order a solver tries the moves in

    A memoised search asking who wins 4 × 5 Domineering expands 1,125 positions when it tries first the move that leaves the opponent fewest replies, and 30,202 when it tries losing moves first — the same answer at twenty-seven times the price. The ordering that already knows which moves win is not the cheapest. A win needs one move and a loss needs all of them, so the price of an order is paid one level down, in the replies it leaves.

    part 2 · complexity
  3. Right, wrong, and right again. A 4 × 5 Domineering position with Right to move, which Right loses, beside what a search cut at each depth from 0 to 9 says about it when it guesses that the player with more placements wins. The guess alone is right, a search one move deeper is wrong, and every deeper search is right.

    A verdict that changes with the depth

    A who-wins search of 4 × 5 Domineering cut at a fixed depth, guessing that the player with more placements wins where it stops, is right about 72.5 per cent of positions at depth 0 and about every one of them by depth 7. On the way, 4,697 positions are right at one depth and wrong at a deeper one. With a guess that knows nothing, going one move deeper makes the search worse — and its errors alternate in kind with the parity of the depth, so that half its verdicts are proofs.

    part 3 · complexity
  4. Two depths that agree. A 4 × 5 Domineering position with Right to move, which Right wins, beside what a search to each depth from 0 to 6 says under the guess that any mover wins. The verdicts alternate until depths 2 and 3 agree, which certifies the answer 3 moves before the longest line.

    Where a search may stop

    A search deepened until two consecutive depths agree carries a proof of its verdict, and on 4 × 5 Domineering it stops before the longest line on 17,589 of 48,670 positions. It also costs three times what the search that simply finishes costs. The rule that pays is the other one. Search on wherever the two players' counts of placements are within one, and at depth 2 the wrong verdicts fall from 2,140 to 86 for about a quarter more work per search.

    part 4 · complexity
  5. Two ways to search on, one position. A 4 × 5 Domineering position with Right to move, which Right wins, beside what deepening says at each depth when it declines to guess where the counts of placements are close. Searching on one move at a time, depths 0 and 1 agree on the wrong verdict; searching on two moves at a time, the search stops at depth 3 with the right one.

    Search on in pairs of moves

    Deepening until two depths agree gives a proved verdict, and searching on where the counts are close gives a better one; put together the obvious way, they stop on a wrong verdict at 3,231 positions of 4 × 5 Domineering. A guess one move past the cut has the other player to move and flatters the wrong side. Searching on two moves at a time keeps the proof, and the window that suits it is one-sided — but however it is widened, the certificate gets cheaper only by turning into the search that finishes, and on four boards it never gets below it.

    part 5 · complexity

All series