Combinatorial Game Theory
who wins, and by how much
Concept

Horizon effect — where it appears

The error a depth-limited search makes when a line turns just past the point where the search stops, so that position is judged as if it never turns. Searching deeper moves the horizon rather than removing it, which is why programs extend lines that are still changing sharply.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

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 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.

complexity · Search

Named alongside it

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

DomineeringExhaustive searchHeuristicSearch costCertificateExact evaluationMove orderingAlternationGame treeParity

All concepts