Where a search may stop

A verdict that changes with the depth cut a who-wins search of 4 × 5 Domineering at every depth from nought to nine and checked each verdict against the exact answer. It found a search that is right about almost every position by depth five and cannot say which positions it is still wrong about. It also found two structures in the errors, and left each as a question about when a search may stop.

The first structure was a bracket. Under the guess that knows nothing — any player with a move wins — an even depth can only overstate the chances of the player to move and an odd depth can only understate them. So if two consecutive depths say the same thing, the truth is pinned from both sides. The second was a concentration. Under the better guess, that the player with more placements wins, the errors did not look evenly spread, and the natural suspicion was that they sit where the two counts are close.

Each suggests a stopping rule a program could actually follow without knowing the answer. Deepen one move at a time and stop when two depths agree. Or guess only where the counts are far apart, and search on where they are close, which is what chess programmers call a quiescence search. Both can be run on every position of a board small enough to solve, and both can then be checked.

Two depths that bracket the answer #

The procedure is the plainest possible. Search to depth nought, then one, then two. After each, compare the verdict with the previous one. If they agree, stop and report it. If the search at some depth never reached a guess at all — every line it followed ended with a player unable to move — it has become the exact search, and it stops then too.

That second condition is not a trick. It arrives at exactly the position’s own longest line, which the count confirms on every one of the 48,670 positions, and it is the depth a search would need if it had no bracket to lean on. So the table is a measurement of what the bracket adds.

It adds a stop before the end on 17,589 positions, a little over a third. On 12,014 of them it saves one move, on 5,059 two, on 440 three and on 76 four. And not one of the 48,670 stops is wrong. That is not luck to be grateful for. It is the bracket, which is a theorem about the guess, and every one of the stops was checked against the exact answer rather than trusted to it.

There is a small cost on the other side. On 2,270 positions the two depths agree only one move after the search has already reached the end of every line, so the bracket would have stopped a move late if it were the only rule. A program that runs both tests never pays that, because the exhaustion test fires first.

One position, stopped three moves early #

The example is chosen as the position that saves the most moves among those where the agreement comes at depth three or later. Earlier agreements are not worth drawing: agreement at depth one means the mover can leave the opponent with no placement at once, and nobody needs a certificate for that.

Right has nine placements and Left seven, and six moves of play remain on the longest line. Depth nought says Right wins, because the guess says so of any mover. Depth one says Right loses — at depth one the guess is taken with Left to move, and it flatters Left. Depth two says Right wins again. Depth three says so too.

At that point the argument is complete. Depth two can only overstate Right’s chances, so a verdict of wins there might be too generous; depth three can only understate them, so a wins there cannot be too generous. The one says no more than the truth and the other no less, and they say the same thing. The search stops at depth three with a proof, where a search waiting for the end of every line would have gone to depth six.

The proof is dearer than the verdict #

A stop three moves early sounds like a saving. Whether it is one depends on what the search would otherwise have done, and on a board this small the alternative is not a deeper cut search. It is the memoised search of the tree and the graph, which ignores depth altogether and simply finishes.

From the empty board with Left to move, in the order the order a solver tries the moves in found cheapest — the move that leaves the opponent fewest replies first — the finishing search expands 234 positions. Deepening to agreement runs ten iterations, stops only at depth nine, the last move, and expands 2,099. With Right to move it stops a move early at depth eight and expands 2,565 against 891. In the order the moves are generated in the gap is smaller and still one way: 5,011 against 1,114, and 8,139 against 4,874.

The empty board is one position, and the gap there might be an accident of the opening. So the same comparison is run from a thousand positions drawn uniformly from the board. Deepening costs 20.8 positions a search on average and finishing costs 6.8, and deepening is the dearer of the two on 947 of the thousand.

The reason is structural rather than a matter of tuning. A search cut at a depth has to key its table by position and by depth left, because the same position asked with three moves in hand and with four can get different answers. So nothing learned at one depth can answer a question at the next, and every iteration pays again for everything the last one looked at. The finishing search keys by position alone, because its answer at a position does not depend on how it got there or how far it has to go. Space is the resource prices that table, and on a board with 48,670 positions it is small enough to hold whole; a key shorter than the position prices what an address for it can get wrong once it is not.

So on a board small enough to finish, a certificate costs more than an answer. The same ordering of the two appeared, far more steeply, when a winning strategy was measured against the table that answers it: there a proof that Left wins from one Nim position was a hundred thousand times the size of a complete solution. Here the proof is only a few times the price, because a bracket of two verdicts is a much smaller object than a strategy. That is not a verdict on iterative deepening, which chess programs use for reasons this measurement does not touch. It says that the bracket’s value lives entirely on boards where the finishing search is unaffordable, which are exactly the boards where no count of this kind can be taken.

Where the count of placements goes wrong #

The second rule starts from the better guess, and from the suspicion about its errors, which can be tested with no search at all.

The suspicion is right, and more sharply than expected. Where the two counts are level the guess is wrong on 6,868 of 9,845 positions, well over two thirds. With the mover one behind it is wrong on 3,916 of 8,944. Those two columns hold 10,784 of the 13,363 wrong guesses the rule makes over the board. Two placements ahead it is wrong on 94 of 5,450, and past three either way it is almost never wrong.

The table is also lopsided, and the lopsidedness is the more interesting fact. A mover one ahead is misjudged on 693 of 8,356 positions and a mover one behind on 3,916 of 8,944. The guess treats the counts as symmetric and the game does not. Having the move is worth something in Domineering: a level mover places a domino first, and a domino can remove the opponent’s placements as well as spending one of the mover’s own. The table says how much that is worth where the counts are level. Those positions are mostly won for the player to move, and a guess that calls them lost is wrong on most of them. The margin a count needs measures how large a lead in placements has to be before it settles the game outright; this is the same asymmetry seen from the guess’s side.

The last line of the footer is the price of acting on the suspicion. The mover level or one behind is 18,789 of 46,400 positions, two in five. A rule that declines to guess on all of them is not declining on a rare kind of position.

Moving the threshold instead #

The asymmetry suggests a repair that costs nothing: call a tie for the mover. The guess becomes the player to move wins unless the opponent has strictly more placements.

As a guess on its own it is better, exactly as the asymmetry predicts. With no search, 9,472 positions are misjudged instead of 13,363. Put the same guess at the bottom of a search and the result reverses. One move deeper it is wrong on 5,946 positions against the original’s 4,716; two moves deeper on 3,475 against 2,140; three moves deeper on 1,606 against 596. The repaired guess is worse at every searched depth until both are exact.

The split by kind shows the mechanism, or the first half of it. At depth one the guess is never asked about the player to move at the start. It is asked about the opponent, at every position one move away. A guess leaning toward the player at the cut therefore leans against the player at the root. The original guess leans against whoever is at the cut, and at depth one its errors are false wins at the root: 4,082 of 4,716. The repaired guess leans the other way, and its errors at depth one are false losses: 4,078 of 5,946.

The second half is a selection the search makes. A lost position is called won when any one of its moves reaches a position the guess wrongly calls lost for the opponent, so a lean against the opponent needs only one misjudged move to invent a win. A won position is called lost only when every winning move reaches a position the guess wrongly calls won for the opponent, so a lean toward the opponent has to catch all the winning moves at once — which is one misjudgement on a position with a single winning move. Which lean does more damage is therefore not decided by the guess alone but by how many winning moves the won positions of the board have, and the table is the answer to that question for this board rather than a consequence of anything said here.

A guess is not scored where it stands. It is scored at the positions a search chooses to consult it, and the search chooses them. The repair was fitted to every position weighted equally, and that is not the population the search puts in front of it.

Searching on while it is close #

Declining to guess is the repair that respects that. Where the counts are close, a quiescent search does not guess at all; it searches one more move, and again, until it reaches a position where the counts are apart or somebody cannot move. Three windows are measured: search on only where the counts are level, where the mover is level or one behind, and where the counts differ by at most one in either direction.

The cost is counted as a program pays it. From each of 5,000 positions drawn uniformly, a search with a fresh table, trying the move with fewest replies first and stopping at the first winning move. The wrong verdicts are counted exactly, over all 48,670 positions, so both columns describe the same population: every position of the board, weighted equally.

The widest window at depth two leaves 86 positions wrong, and expands 5.59 positions a search. Plain search at depth two leaves 2,140 wrong for 4.46. To be as right as the window, plain search has to go to depth five, where it is wrong on 17 and expands 7.16. At depth three the window is wrong on sixteen positions for 6.46, and plain search is that right only at depth six, for 7.27. Across every depth where a window is still wrong somewhere, it is cheaper than the plain depth that matches it in seventeen of nineteen cases.

The narrower windows are weaker, and the pattern says why. Searching on only where the counts are level removes the worst column of the margin table and leaves its neighbour. The window that takes both, level and one behind, is better again. The one that also takes a mover one ahead is much better, even though a mover one ahead is misjudged only one time in twelve. That column holds 8,356 positions, and 693 errors on it are still 693 errors, each of which a search one move above can inherit.

This is the rule the earlier survey of the horizon predicted, and it turns out to be the one that pays: a verdict that changes with the depth guessed that the counting guess’s failures “are presumably concentrated on positions where the two counts are close”. They are, and a search that spends its extra work there beats one that spends it uniformly.

Four boards #

Neither result is a fact about 4 × 5 alone. On all four boards agreement stops a share of positions before their longest line, from about a sixth on 3 × 4 to about two fifths on 4 × 4, saving at most two moves on the smallest board and four on the others. On all four it costs more than finishing, between 2.1 and 3.1 times as much per search, and the ratio grows with the board rather than shrinking.

And on all four a window is cheaper than deepening to the same accuracy in most of the contests the board offers: six of eight on 3 × 4, eleven of fifteen on 4 × 4, eleven of thirteen on 3 × 6, seventeen of nineteen on 4 × 5. The boards are small and the counts are few, but the direction is the same everywhere measured.

Where the two rules came from #

The idea of evaluating only quiet positions is as old as chess programming. Claude Shannon’s 1950 paper on programming a computer to play chess already proposed searching past a fixed depth wherever the position was still changing sharply — captures pending, a piece under attack — so that the evaluation would be applied only where it could be trusted. The count of placements here plays the part of material in a chess program, and a close count plays the part of a capture pending.

Deepening one move at a time became standard in chess programs in the 1970s, and Richard Korf analysed it as a general search method in 1985. Its usual justification is not a certificate at all. It is that each iteration orders the moves for the next, and that a program with a time limit always has a completed shallower answer in hand. Neither benefit is counted here: the finishing search is given the good move order for free, and it has no time limit to run out of.

The bracket that makes agreement a certificate is the odd–even effect deepening programs have long observed as oscillation in their evaluations. Seen from the other side, it is the same fact a bound instead of an answer prefers for other reasons: a quantity known to lie on one side of the truth.

What the counts cannot show #

Every position is weighted equally. A program in play meets positions in proportion to how often play reaches them, and a uniform draw from the board is dominated by the late middle game, where searches are short. Both costs and errors would move under a weighting by play. The empty-board rows of the cost table are there as one position a program certainly meets.

The boards are small enough to finish. That is what lets every stop be checked, and it is also what makes the certificate lose. On a board where the finishing search cannot complete, deepening to agreement may be the only way to obtain a proved verdict at all, and nothing here measures how often it would arrive.

The window’s extension has no limit. A quiescent search here keeps going until the counts are apart or the game ends, which on 4 × 5 is never far, and it is guaranteed to end only because every line of Domineering does — the licence it ends, and nothing says when examines for games where no count of squares supplies it. On a larger board a window of this width could keep a search going a long way past the nominal depth, and a practical rule would cap it.

Verdicts are not moves, and move generation is not charged. A program chooses a move, and choosing the right one is a different measurement from judging the position right. And reading a child’s reply count to order the moves costs a move generation that neither rule is billed for; both rules pay it equally, so it cannot reverse the comparison, but it changes the size of every cost column.

The rules the counts assume #

Normal play Domineering: Left places vertical dominoes, Right horizontal ones, and the player who cannot place loses. A position is a set of covered squares with a player to move, reached in alternating play from the empty board with either player starting. The exact answer for every position is the result of the full search; a guess is consulted only at a position with a move, since a position without one is lost by the rule, not by a guess. The count of placements is the number of places the player could put a domino now, not the number of dominoes it will manage to place.

Still open: the two rules together #

The two rules use two different guesses, and they do not obviously combine. The bracket needs the know-nothing guess at every leaf, since it is the flattery of whoever is to move at the cut that makes an even depth an upper bound. A window replaces some of those leaves with further search, and further search to the end of a line only ever makes a leaf more exact. So a search that searches on where the counts are close and guesses any mover wins everywhere else ought to keep the bracket and stop by agreement sooner — on the positions where the know-nothing guess was most misleading. Whether it does, how much sooner, and whether that brings the certificate’s cost under the cost of finishing on any board small enough to check, is the next measurement to take.