Search on in pairs of moves

Where a search may stop measured two rules for ending a who-wins search of 4 × 5 Domineering early, and found that each did one thing well. Deepening one move at a time under the guess that any player with a move wins, and stopping when two consecutive depths agree, produced a proof of the verdict on every one of 48,670 positions — at three times the cost of the memoised search that simply finishes. Declining to guess where the two players’ counts of placements were close, and searching on there, made the counting guess far more accurate for a quarter more work, and proved nothing.

It closed by proposing the combination. The bracket needs the know-nothing guess at its leaves; a window replaces some leaves with further search; further search only 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 proof and stop by agreement sooner.

The middle step of that argument is false, and the way it fails is the most useful thing the combination has to teach.

Two rules that do not simply add #

A search to depth d that guesses at its leaves is right about positions whose lines end before the cut and guesses about the rest. The bracket rests on a fact about who is to move at the guesses. At an even depth every guessed leaf has the root’s player to move, so any mover wins can only flatter that player: the whole search overstates the root player’s chances, or states them exactly. At an odd depth every guessed leaf has the opponent to move, and the search can only understate. One verdict from above and one from below, agreeing, pin the truth.

Searching on one move where the counts are close breaks that fact. A leaf that is declined becomes a search one move deeper, and the positions at the bottom of that search have the other player to move. If they are guessed, the guesses flatter the other side. An even-depth search now contains guesses leaning both ways, and it is no longer an upper bound on anything.

Over every position of the board, with the window the earlier essay used — decline to guess wherever the mover’s placements are within one of the opponent’s — the count is exact. At depth nought, 2,340 verdicts say the mover loses a position it wins, which an even depth is supposed never to do. At depth one, 891 say the mover wins a position it loses. At depth two, 60 more. From depth three the extensions reach the ends of lines often enough that none are left.

The proposal’s own sentence was nearly right, which is what made it convincing. Further search that reaches the end of a line does make a leaf exact, and an exact leaf never breaks a bound. The failure is in the extensions that stop short of the end — at a position where the counts have moved apart after one more move, and a guess is taken there with the wrong player to move. On a board this small most extensions end a few moves in, and the few that end at a guess are enough.

A broken bracket is not only a broken theorem. Where two broken verdicts happen to agree, the rule stops and reports them. It stops on a wrong verdict at 3,231 positions: 891 false wins and 2,340 false losses, all at the shallow depths where the broken verdicts are, since a wrong stop needs two neighbouring verdicts wrong in the same direction.

One position, stopped wrong #

The position drawn has two dominoes on it and ten placements left for each player, so the counts are level and the window declines to guess. Right is to move and wins, and the longest line left is seven moves.

At depth nought, a search that declines to guess steps one move in, to the positions after each of Right’s ten placements, every one with Left to move. Five of them leave the counts within one and are searched further. The other five are guessed, and the guess says Left wins — including the three where Right’s domino has left Left three placements behind, which Left in fact loses. In truth Left wins after only three of Right’s ten moves; the search, finding a win for Left after every one of them, reports that Right loses. At depth one the same thing happens a level further down, and again Right loses. Two consecutive depths agree, and the combined rule stops, wrong, six moves before the end of the longest line.

Searching on two moves at a time, the depth-nought search steps past Left’s replies to Right’s next turn before it will guess, and there the guess flatters Right, as an even depth must. It says Right wins. Depth one says Right loses, depth two says Right wins, and depth three says so again: two depths agree, from opposite sides of the truth, and the search stops with a proof four moves before the longest line.

Why two moves repairs it #

The repair has a one-line justification. A search that may guess only at an even number of moves past the depth it was asked for puts every guess at a position with the same player to move as a search without any window would. Every even-depth search then still flatters only the root player at its guesses, and every odd-depth search only the opponent. The positions the window extends are replaced by deeper searches whose own guesses sit at the same parity, and positions where a line ends are exact. So the bracket holds at every depth, and agreement is again a certificate.

The figure above confirms it on every position: with the same window, searching on two moves at a time puts no verdict on the wrong side at any depth, and no stop is wrong. It is also cheaper than plain deepening, 16.0 positions a search against 20.8, because the extension reaches the ends of lines on many positions that plain deepening had to approach one iteration at a time.

There is a deeper reason the number is two. A puzzle asks once, a game asks alternately identifies a game’s turns with a prefix of alternating quantifiers, and the bracket is a statement about that prefix: cut it after an exists and the guesses are optimistic, cut it after a for all and they are pessimistic. A window that extends by one move changes the last quantifier. A window that extends by two changes nothing about which quantifier comes last, and it is the only kind of extension that can leave a bound a bound.

The window belongs to the guess #

The two-move repair keeps the proof. It does not say where to extend, and the earlier essay’s window was chosen for a different guess.

The counting guess, more placements wins, is wrong where the counts are close, and a window of one either way holds 11,477 of its 13,363 errors. The know-nothing guess is wrong on a different set: on exactly the positions the mover loses, because it says the mover wins everywhere. Those are not where the counts are close. They are where the mover is behind. A mover two placements behind loses 76 per cent of the time and three behind 88 per cent; a mover level loses 30 per cent and a mover one ahead only 8. Of the 16,726 lost positions with a move, 15,915 have the mover level or behind.

So the window of one either way declines to guess where the counting guess would have been wrong, and not where the know-nothing guess would. It extends 8,356 positions with the mover one ahead, where the know-nothing guess is right 92 times in a hundred. And it guesses, with the most confident guess there is, on every position with the mover two or more behind — the 9,678 positions where it is wrong most often. The window a search needs is one-sided: decline to guess wherever the mover is not comfortably ahead. How comfortably is a threshold, and the next figure varies it.

The margin a count needs measured how large a lead in placements settles a game outright; the threshold here is the same question asked of a guess rather than of a verdict.

A certificate gets cheaper by becoming the answer #

The costs are counted as a program pays them, as before: from each of a thousand positions drawn uniformly, deepening with a fresh table each iteration, trying first the move that leaves the opponent fewest replies — the order the order a solver tries the moves in found cheapest — stopping at the first agreement or at the first iteration that consulted no guess at all.

Searching on two moves at a time, the certificate gets steadily cheaper as the window widens. Declining to guess only where the mover is two or more behind, it costs 17.7 positions a search; one or more behind, 12.1; level or behind, 9.4; up to one ahead, 8.3; two ahead, 7.9; three ahead, 7.3. Every step is cheaper than the last, and the widest is a third of plain deepening’s 20.8. None of them reaches the search that finishes, at 6.8.

The one-move line is the warning. Declining to guess wherever the mover is behind, it costs 6.3 positions a search, and at level or behind 6.7 — the only two windows on the chart below the finishing search. They are also the two that stop wrongly most, on 3,662 positions and on 1,611. The certificate is cheaper than the answer only when it is not a certificate. Past the window of one ahead the one-move line runs above the two-move line, and from two ahead it is no longer wrong anywhere, because its extensions end most lines before a guess of the wrong parity is reached.

The two-move line’s shape has a reason, and the reason is where it is heading. Widen the window all the way — decline to guess anywhere — and the depth-nought iteration never guesses: it is the search that finishes, and the rule stops there because no guess was consulted. Every window short of that is a mixture: some positions are guessed at and need further iterations to reach agreement, and some are finished outright in the first. Widening moves positions from the first kind to the second, and on these boards the second kind is cheaper.

Cheaper, position by position #

A mean hides where the saving is, so the same thousand positions are sorted one at a time: is deepening to a stop cheaper than finishing on this position, exactly as cheap, or dearer?

Across all six two-move windows, the certificate is cheaper than finishing on ten searches out of six thousand. Plain deepening is dearer on 947 positions and never cheaper. Each widening of the window moves positions out of the dearer band into the middle band — the positions where the first iteration consulted no guess and so was the finishing search, at identical cost — and almost none into the cheaper band. At a window of three ahead, 916 positions are in the middle band and 84 still dearer.

The one-move windows are the only ones with a real cheaper band: 276 positions with the mover one or more behind, 219 with the mover level or behind. They are cheaper because their extensions stop searching lines too soon, and they carry 68 and 30 wrong verdicts among the thousand.

The tree and the graph supplies the reason the finishing search is so hard to beat here. It keys its table by position alone, so a position met on a second line is answered at once. Every deepening iteration keys by position and depth left, and cannot reuse a thing the previous iteration learned; space is the resource prices the table that makes that difference. A certificate needs at least two iterations that each guess somewhere, and two such iterations of even a well-windowed search almost always touch more positions than one search that remembers everything and goes to the end. A strategy is not a certificate found the same ordering on Nim at a far larger scale, where a proof that one position is won dwarfed the table answering every position; here the gap is a few positions a search, and no window closes it.

Four boards #

The shape is the same on 3 × 4, 4 × 4, 3 × 6 and 4 × 5. On every board the two-move certificate with the level-or-behind window roughly halves plain deepening — 6.8 to 4.0, 15.5 to 8.9, 21.1 to 9.6, 20.8 to 9.4 — and on every board the widest window comes closest to finishing without reaching it: 3.25 against 3.16 on the smallest, 5.7 against 5.3, 7.3 against 7.0, 7.3 against 6.8. And on every board the one-move combination with the close window stops wrongly somewhere, from 16 positions on 3 × 4 to 3,231 on 4 × 5.

So what the earlier essay left open has three answers, and only one of them is the one it expected. The combination does keep the bracket, but only when the search goes on in pairs of moves. It does stop sooner — a third of plain deepening’s cost at the widest window. And it does not bring the certificate’s cost under the cost of finishing on any board small enough to check, because every way of making it cheaper is a way of making it more like the search that finishes.

Where this sits in practice #

Chess programs have searched past a fixed depth in noisy positions since Shannon’s 1950 proposal, and have deepened one iteration at a time since the 1970s. The odd–even effect is familiar to their authors as oscillation: scores at odd and even depths differ systematically, because the side to move at the leaves alternates. A verdict that changes with the depth found the same alternation in this game’s errors, which change kind with the parity of the depth. That observation and this measurement are the same fact from two sides. Two iterations of the same parity have the same player to move at their leaves; a window is safe for a bound only when its extensions keep that player the same.

None of those programs use agreement as a stopping rule, and on boards they play the search cannot finish, so there is nothing to compare a certificate’s cost with. The comparison made here is available only on boards small enough to solve, which is also why its answer — the finishing search wins — says nothing about boards that are not.

What a thousand positions cannot show #

The positions are weighted equally. A program in play meets positions in proportion to how often play reaches them, and the uniform draw is dominated by positions in the late middle game, where every search is short and the finishing search is cheapest. A weighting by play would move the early positions, where deepening pays most, into view.

The windows are thresholds on one count. Every window here declines to guess by the difference in placements. A window that looked at something else — the number of regions, or a quiet region where no domino interferes — could put its extensions elsewhere, and nothing here measures one.

The tables are fresh each iteration. A program that kept its table between iterations and used it only to order moves, as real programs do, would pay less per iteration; it could not reuse verdicts across depths without breaking what a depth-keyed verdict means, which is the constraint that keeps finishing ahead here.

The extension is unbounded. A window searches on until a guess is allowed or a line ends. On a larger board a program would cap it, and a capped extension must still stop at the right parity or the bracket breaks again, which a cap by a fixed number of moves does only when that number is even.

The rules the counts assume #

Normal-play Domineering on rectangular boards: 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. A count of placements is the number of places a player could put a domino now. The exact answer for every position comes from the full search, and every stop is compared with it. The sample is the same thousand positions where a search may stop drew, and on 3 × 4, with 493 positions, every position is used.

Still open: a certificate on a board too large to finish #

Everything here is priced against a search that finishes, because that is what makes a verdict checkable. The certificate’s whole purpose is the board where no search finishes, and there the question changes: not whether agreement is cheaper than finishing, but how often it arrives at all within a budget, and whether a two-move window makes it arrive on positions plain deepening never settles. On 4 × 5 that can be simulated by capping the positions a search may expand and counting the proved verdicts each rule returns before the cap. Whether the window still pays when the comparison is proofs against nothing, rather than proofs against answers, is the measurement this leaves.