A verdict that changes with the depth

The order a solver tries the moves in ended with a search that always reaches the last move. Ordering made that search twenty-seven times cheaper on a 4 × 5 Domineering board, but it did not make it shallower: every line was still followed until somebody could not place a domino. On a board of any size that is unaffordable in any order, and a practical search does something else. It stops at a fixed depth and puts a guess where it stopped.

What that guess costs is usually hard to see, because a search is cut short precisely on boards whose answers nobody knows. A 4 × 5 board is small enough to solve outright. So every verdict a cut search gives can be checked, position by position and depth by depth, against the exact answer — which turns the familiar folklore about searching deeper into a table of counts.

A search cut short, checked position by position #

The cut search is the exact search with one change. At depth 0 it does not look at any move: if the player to move has no placement it loses, which is the rule rather than a guess, and otherwise it guesses that the player with more placements wins. At depth d it tries each move and asks the depth d − 1 search about the result.

With no look-ahead at all, the guess is right about 72.5 per cent of the board’s positions. One move deeper, 90.3 per cent; two, 95.6; four, 99.6. At depth 5 seventeen positions are still wrong, at depth 6 one, and from depth 7 every verdict is right.

There is a rule that says when a verdict must be right, and it explains the tail. The longest line of play on 4 × 5 is nine moves. A search at least as deep as a position’s own longest line never reaches a guess below it, so it is simply the exact search. Before that, only positions whose line runs past the cut can be wrong, and the last column counts them: 46,400 at depth 0, 2,364 at depth 5, 33 at depth 7. Depth 7 is exact two moves short of the longest line because the guess happens to be right on all 33 positions it still makes. That is a fact about this board, found by solving it; nothing about depth 7 announces it in advance.

Right, then wrong, then right #

The totals climb steadily, and they hide the thing a cut search is known for. Take a single vertical domino in the second column, touching the top edge, with Right to move. Right has 12 places to put a horizontal domino and Left 13 for a vertical one, and with correct play Right loses.

At depth 0 the search guesses from the counts alone. Left has more placements, so Right loses — which is right. At depth 1 it tries each of Right’s placements and applies the guess to the position after it. Some Right placement blocks enough of Left’s columns that Left, to move, has no more placements than Right; the guess calls that position lost for Left, so the depth-1 search concludes that Right wins. That is wrong. At depth 2 the search looks one move further, finds Left’s answer to that placement, and sees that Left’s advantage in room comes back. From then on it says Right loses, and it stays right all the way to the longest line of eight moves.

That is the horizon effect in its smallest form. A line that turns just past the cut is scored as if it never turns. Searching deeper does not remove the effect; it moves the horizon, and a position that was safe at one depth can become a casualty of the next.

How much a deeper search overturns #

The first table counts how often that happens. Going from depth 0 to depth 1, 12,080 verdicts turn from wrong to right and 3,433 turn from right to wrong. From 1 to 2, 3,747 are corrected and 1,171 spoiled; from 3 to 4, 441 against 34. After depth 4 no verdict is ever spoiled again, though corrections continue to depth 7.

Across all depths, 4,697 positions — nearly one in ten — are right at some depth and wrong at a deeper one. The aggregate share right rises at every step, so a reader of the totals alone would conclude that deeper is simply better. Position by position it is not: every depth trades some right verdicts for more right verdicts, and a program that happens to be asking about one of the traded positions gets a worse answer for its extra work.

The last column of the first table says something the totals do not. At depth 4, 9,193 positions have a longest line the search does not reach, so their verdicts still rest on guesses — and 97.9 per cent of them are right. At depth 0 the same share was 71.2 per cent. Depth is not buying accuracy only by settling positions outright. On the positions it cannot settle, a guess consulted four moves further into the game is a much better guess, which is what a count of placements should be expected to do: near the end of a game there are fewer ways left for a lead in room to be overturned.

A guess that makes deeper worse #

The guess matters as much as the depth, and the cleanest way to see it is to replace the counting guess with one that knows nothing: any player who has a move wins. That is the guess a search makes when it has no view of the position at all.

At depth 0 it is right about 65.6 per cent of positions, seven points below the counting guess. At depth 1 it is right about 56.9 per cent. The search that looks one move ahead is nearly nine points worse than the search that does not look at all. It recovers — 84.8 at depth 2, 98.0 at depth 4 — and becomes exact at depth 8, one move later than the counting guess.

The counting guess is at least as good at every depth, by 33 points at depth 1. Placements are a good enough guide to a Domineering position that the margin a count needs could ask exactly how large a lead in them has to be before it settles the game, and a threshold is a detection limit examines the same count as a mobility rule. Here the count is doing a humbler job: saying something better than nothing at the edge of a search, which is enough to keep deeper from being worse.

Errors that alternate, and verdicts that are proofs #

The know-nothing guess has a property that makes up for its poor average, and the split of its errors shows it. At depth 0 it claims 16,726 wins that are losses and no losses that are wins. At depth 1, 20,956 losses that are wins and no false wins. At depth 2, false wins only; at depth 3, false losses only; the pattern holds at every depth until the errors run out.

The reason is a two-line argument. The guess flatters whoever is to move at the cut. At an even depth that is the same player who moves at the root, so every leaf is scored as well as it could be for that player, and since a better leaf for a player can never make that player’s position worse, the verdict can only overstate the root mover’s chances. At an odd depth the opponent moves at the cut, the flattery is the opponent’s, and the verdict can only understate them. Even depths bound the truth from above and odd depths from below.

That turns a poor guess into a source of certainty. An even-depth search that says loses cannot be overstating, so the position really is lost. An odd-depth search that says wins cannot be understating, so it really is won. Half of every such search’s verdicts are proofs, and whenever two consecutive depths agree, both are exact, since one of them is a bound in each direction. A position wrong at one depth is always right at the next. The counting guess is better on average and gives no such bracket: at depth 3 it claims 296 false wins and 300 false losses, and nothing in a single verdict says which kind it might be.

This is the structure a bound instead of an answer prefers for other reasons — a quantity known to be on one side of the truth — arising here from nothing more than the parity of the depth.

The opening position, depth by depth #

The empty board shows both guesses at their most awkward. Left has 15 places for a vertical domino and Right 16 for a horizontal one, and Left wins anyway, whoever starts.

So the counting guess is wrong about the opening position at depth 0 for both players: it gives the game to Right, who has more room. With Left moving first it is right at depth 1, wrong again at depth 2, and settled from depth 3. With Right moving first it is wrong at depths 0, 1 and 3 and settled from depth 4. A search that stopped at depth 2 would announce that Left, moving first, loses a board Left wins.

The know-nothing guess changes its mind at every depth up to 7, exactly as the bracket requires: right about Left moving first at even depths and wrong at odd ones, the reverse for Right, settling at depth 8 for Left and 7 for Right. A player watching an engine’s verdict on the opening flip at every iteration of deepening is watching this.

Four boards, and where the horizon stops mattering #

On every board measured the counting guess is exact before the longest line: at depth 3 on 3 × 4, whose longest line is five moves; at depth 6 on 4 × 4, against eight; at depth 5 on 3 × 6, against nine; at depth 7 on 4 × 5, against nine. The know-nothing guess is exact at the same depth on 4 × 4 and later everywhere else. And the counting guess overturns far fewer verdicts on the way — 4,697 against 28,363 on 4 × 5, a ratio between 5.6 and 6.3 on all four boards.

None of those depths is available to a program that needs it. Each was found by solving the board, which is the search the cut was meant to avoid. The honest reading of this table is not “depth 7 suffices on 4 × 5” but “a cut search on a board this size is wrong about very few positions by depth 5, and which few is not predictable from the depth alone”.

The order does not change a verdict #

None of these verdicts depends on the order in which moves are tried. A cut search with a given depth and a given guess is a fixed function of the position: a position is won at depth d if some move leads to a position lost at depth d − 1, and which move is tried first changes only how soon the search finds it. Every count in the tables above is a property of the depth and the guess alone.

What the order changes is how many guesses are made. A search that tries first the move leaving the fewest replies usually settles a won position with its first move, and so consults the guess at far fewer positions than one trying moves in a bad order — the asymmetry that made ordering pay in the full search, applied to a search that stops. Ordering and the horizon are separate levers: one sets how much a cut search costs, the other how often it is wrong, and neither can do the other’s job.

That is also why a program using one count for both jobs — to order moves and to judge positions where it stops — is making two different bets with one number. The count orders 4 × 5 almost perfectly and still misjudges its opening position at depth 0 for both players. Being a good guide to where to look first is a weaker property than being a good judge of who is winning, and the same number can have the first without the second.

What a finite depth is licensed to do #

It ends and nothing says when separates two things a solver might mean by a game being finite. When the longest line has a finite rank, a depth-limited search to that rank is complete, and the depth limit is a theorem rather than a heuristic. Every exhaustive census in these essays works that way.

This essay is about the other side of that line: a depth limit set below the rank, for the sake of cost. There the limit is a heuristic, and the counts say what kind. It is extraordinarily good on average and unreliable on individual positions, and its failures are all on positions whose lines run past the cut — overturned, as in the one-domino example, when a reply the search did not see restores what the count at the cut concealed.

That is also why the space cost of search, which space is the resource ties to the depth of the longest line, is not the only depth that matters. A search can hold a line nine moves deep in almost no memory. What it cannot do cheaply is know which of its shallower verdicts it would have regretted.

Names: the horizon effect and pathology #

The term horizon effect comes from chess programming, where Hans Berliner described it in the early 1970s: a program facing an unavoidable loss plays delaying moves that push the loss past its search depth, and so judges the position as better than it is. The remedy chess programs adopted is quiescence search, which keeps searching past the nominal depth wherever the position is still changing sharply, so that guesses are only made at positions quiet enough to guess about.

The alternation of the know-nothing guess is the odd–even effect that iterative deepening programs see when their evaluation oscillates between even and odd depths. And the finding that a deeper search can be worse on average has a name too: Dana Nau and Don Beal showed around 1980 that there are game trees on which deeper minimax search chooses worse moves on average, and called the phenomenon pathology. The drop from 65.6 to 56.9 per cent at depth 1 is a very small case of it, measured on verdicts rather than on moves.

What the checks cannot show #

Every position is weighted equally. The shares are over all 48,670 positions, while a search in play meets positions in proportion to how often play reaches them, and the positions reached are not a uniform sample. An error on a position no line ever visits costs nothing.

Verdicts are not moves. A program chooses a move, and it can choose the right move from a wrong verdict, or the wrong move from a right one. The accuracy of move choice under a cut search is a different measurement and is not taken.

Cost is not counted. The tables report verdicts, not the positions a cut search expands. A depth-5 search is right about all but 17 positions of 4 × 5, and how much cheaper it is than the full search — which, from the empty board and in a good order, expands 1,125 positions — is not measured. On a board this small the saving may well be slight.

The boards are small enough to solve, which is what makes every check possible and is also the limitation. The whole point of cutting a search is to use it where the exact answer is not available, and on those boards nobody can count the overturned verdicts.

The convention, named #

Normal play, as in Domineering: Left places vertical dominoes, Right horizontal ones, and a player who cannot place loses. A position is a set of covered squares together with the player to move, reached in alternating play from the empty board with either player starting. The exact answer is the result of the full search of the tree and the graph; the cut search differs only at depth 0, where a position with a move is given the guess instead of being searched.

Still open: a guess that knows when to stop #

The bracket suggests a stopping rule that needs no exact answer: deepen until two consecutive depths agree, and under the know-nothing guess that agreement is a certificate. How deep that runs on each position, and how its cost compares with a search that simply goes to the longest line, is not measured here. The counting guess has no certificate, but its failures are not spread evenly: they are presumably concentrated on positions where the two counts are close, which would make “keep searching while the counts are close” the Domineering version of a quiescence rule. Whether the errors really do sit there, and how much deeper such a rule would need to look, is the next measurement to take.