Combinatorial Game Theory
who wins, and by how much
Concept

Move ordering — where it appears

The order in which a search tries a position's moves, which changes how much it has to examine and never what it concludes. A win is settled by the first winning move found and a loss only by refuting every move, so a good order finds wins early and leads into losses with few moves.

Named by 5 essays across 2 fields — each of them below, with the objects they name alongside it.

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.

complexity · Search 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.

complexity · Search 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.

complexity · Search Proofs against a budget. For 1000 deep positions of 4 × 5 Domineering, how many each method has proved once it may expand 16, 32, … 8,192 positions. The search that finishes leads at every budget; deepening to agreement trails far behind, and the one-sided two-move window comes closest.

A proof inside a budget

A certificate — two depths of search that agree — was always dearer than the search that finishes, but that compared proofs with answers. Its whole purpose is the board where nothing finishes, so the fair test is a budget: cap the positions a search may expand and count the proved verdicts each method returns inside the cap. On a thousand deep positions of 4 × 5 Domineering, the search that finishes proves more at every budget from sixteen to eight thousand. The best certificate, with a one-sided two-move window, proves at most three positions finishing cannot, at any budget, and plain deepening proves none. Where deepening earns its keep is the guess it holds while it works, not the proof it ends with.

complexity · Search The order decides the exceptions. The pruned search that finishes and the told proof, both under five move orders, over the 1766 irreducible Sylver Coinage positions to twenty gaps: the number where the proof is cheaper and the median ratio of their costs. Smallest first gives seven, largest first 55, and a free winning-move-first order none.

The seven were the order

A Sylver Coinage proof told its depth beat the search that finishes on seven positions of 1,766, and on all seven the winning move came fifth when moves were tried smallest first. Run both searches under five orders and the seven vanish under every other one; try the largest move first and there are fifty-five new ones instead. Give both searches the winning move first, free, and the proof is cheaper on none. The exceptions were never positions where proving is easy. They were positions where one order made the finishing search stumble — and what is left when the order is perfect is the price of asking a proof's question.

applied · Sylver

Named alongside it

The objects these essays reach for when they reach for this one.

Exhaustive searchHeuristicSearch costDomineeringCertificateHorizon effectMemoisationExact evaluationGame treeProofCounterexampleDecision

All concepts