'Analogy grafting' and the horizon effect

[hgm]

Pointless delaying tactics can still be very effective for pushing trouble over the horizon. For example:

[d]1b6/4p2P/r2p4/8/6N1/8/4k3/1K6 b
Black cannot cover the promotion square, and a 1-ply search would see 2. h8=Q would follow any non-checking move. Black can delay the unavoidable by checking:

1... Rb6+ 2. Ka2 Ra6+ 3. Kb3 Rb6+ 4. Ka4 Ra6+ 5. Kb5

after which black runs out of safe checks. That adds 8 ply, 4 of which were taken care of by the check extension. But that still makes the promotion invisible to any search with less than 5 ply: after 5. Kb5 black will happily stand pat.

Preferably I would like a 1-ply search already to see the promotion (assuming promotions are searched in QS). I.e. it would be nice if the search would realize that the checks are merely pointless delays, which do not alter the threat situation in any way. Then it could prune them, rather than having them produce false fail highs. The problem is that not al checks are merely delay moves, and that it is difficult to recognize statically whether a check is pointless. (E.g. a seemingly pointless Pawn sac could lure the King to a square that is checked on promotion, and make all the difference.) To be sure the check did not just push the existing threat over the horizon you would have to search not only extending the check, but also the evasion. This would be very expensive, and could even lead to search explosion, so it is not really feasible.

To address this problem, the following heuristic occurred to me: 'suspect' moves, i.e. those notorious for being delaying tactics, such as checks or futile interposition as check evasion, define an 'analogy'. This is a mapping between positions that differ from each other by the suspect move plus its reply. E.g the check + the evasion, or the interposition and the renewal of the check by capturing the interposed piece with the checker. Note that the hash key of the analogous position can be obtained by XORing the hash key of the current position with the Zobrist keys describing the two moves that defined the mapping.

Whenever such an analogy is defined, it means we are in a sub-tree hanging from a suspected delaying tactic. If the suspected delaying tactic was really pointless, this tree should be identical to that hanging from the position before the delaying tactic, i.e. all moves by the delaying side should be refuted by the same cut move. If it would have been searched at the same depth, that is. But it is searched at a 1-ply lower depth. This means that some moves near the leaves will now not be searched for lack of depth. And this will corrupt the result.

There are two ways in which this can happen: a non-capture cut-move will now not be searched because it was pushed into QS, or a node that ought to fail low is rescued by a stand-pat in the face of an unsolvable threat. We can be alerted to this by looking at the analogous position without the delay, though: assuming we search suspect moves last, the undelayed sub-tree should already be in the hash table. So by probing the analogous position there, we should find a result that has been searched 1 ply deeper. In particular, the analogy to our current QS nodes should occur there with a 1-ply search result. This result should be a pretty reliable predictor of what would happen when we search the current node at 1 ply.

In particular, it is a sign of trouble when QS fails low, while the 1-ply search of the analogous position failed high through a non-capture cut move. Or whether stand-pat makes us fail high, while the 1-ply search of the analogous position failed low. You could decide to extend those, but that is expensive. A cheap alternative is to believe the 1-ply search of the analogous position rather than the QS result of the true position.

In the example this would work as follows: at 1-ply, all non-checking moves would be refuted by promotion. After 1... Rb6+ 2. Ka2 we get into QS without having suffered the promotion, so stand-pat would normally have worked. Because the check+evasion defined an analogy, however, we disallow stand-pat. (This is a special case, only occurring in the node directly after the delaying tactic: we cannot probe the has here, because the search of the analogous node has not finished yet, and is thus not stored in the hash. Because we got to searching the check, we know all non-checking moves must have failed low there, so we assume all non-checking non-captures will fail low now too. We should not do that if the check + evasion actually gained us material; such moves are not suspect.) We stil search all captures; after all, Rb6+ could have skewered K+Q, and we would not want to miss RxQ. But if we have no such luck, and the captures fail low, we return alpha, even though eval > alpha. We could even store that in the TT, as we genuinely believe this position to fail low in all cases, even though the fact that we noticed is was through a path-dependent clue.

So the 1-ply search now does assume white will promote. The 2-ply search will depend on a 1-ply search of the position following the check + evasion, which will similarly conceed that promotion is unavoidable, which then propagates to the 2-ply search, etc.

The opposite case occurs with futile interpositions. E.g. in the following position:

[d]8/3ppp2/7R/k7/8/2pPPP1P/P1Q1qr2/K1B3R1 b

In QS or at 1-ply black imagines it can gain a juicy Queen through 1... Qxc2. At 2-ply this can be followed by 2. Rg5+, which in absence of interpositions would be mate-in-2 through 2... Kb4 3. Rh4#. Black can delay the inevitable by

2... f5 3. Rxf5+ e5 4. Rxe5+ d5 5. Rxd5+ Kb4 6. Rxh4#

That requires 6 ply, if the evasions are extended (and no checks in QS). The Pawns are peanuts compared to the Queen black already captured, so black will not be impressed very much that it will lose a few, and only start to worry when he sees himself checkmated. Without interpositions the mate would be recognized at 3 ply.

At 3 ply the interposition f5 leaves a 1-ply search, good for Rxf5, after which e5 puts us in QS. As the check renewals are (good) captures, QS goes on some more moves, until the evasion Kb4. Then the mating move is a non-capture, and no longer seen in QS. (Note we are very deep into QS now, so even engines that search checks in the first few QS levels would no longer do it here.) In fact the evasion 3... Kb4 instead of e5 would already be considered good enough if QS doesn't search checks.

Now if f5 + Rxf5 define an analogy, the QS that would normally fail low after 2... f5 3. Rxf5 Kb4 (or Ka4) could probe the analogous position (after 2... Kb4), and find in the TT that the 1-ply search result for this was a mate-in-1 through the non-capture Rh4#. So it could assume it would be a mate-in-1 now, if we would have taken the trouble to search it. (A sort of reversal of the burden of proof.) So in stead of failing low for lack of captures to recoup the Queen, the analogy would make this QS node fail high. This is of course just a guess, but it seems the more-likely guess. In the TT we would store the entry with QS draft (d=0, say), but with Rh4# as cut move. At ply 5 Kb4 would then be seen not to work, and as a result we would have to consider alternative evasions, in particular e5 or d5. The combination e5 + Rxe5 would define a new analogy, however (replacing the old one in this sub-tree). When the position after 4... Kb4 would be 'analogy probed', it would find the 'upgraded' QS result there, and again be considered a d=0 position with a mate-in-1 result (as if Rh4# would have been a capture, which it would have been if there accidentally had been a black piece on h4). This continues to the very end, where no more interpositions are available.

Note that we only use the analogy in QS, to correct for the different behavior there. In deeper modes where the analogous moves would be searched anyway, we just search them to verify the reult is indeed what we expcet. We could still use the anlogous cut-move as a hash move, if we did not have one, or if it had higher draft.

[stegemma]

I think that it is hard to solve this problem, in normal alphabeta search. This situations require some kind of knowledge of the "path" that any piece should follow:

- the white king must move toward the rook
- the black rook should move laterally, giving always check

Something similar is in the second position.

For the first one, maybe there are another biggest problem: black can simply play:

1...., Ra4
2. h8=Q, RxN
3. QxB, Re4

I don't know if QxB is forced and if this position is a win for white (I suspect no) but this is just to say that even if you solve the initial problem of seeing that interleaving checks are useless, then you fall into another problem and you can't easily know even if you are in a position when there are useless moves and good ones. Maybe you lose time to avoid analyzing checks and you miss the opportunity to draw

[hgm]

Alpha-beta search will eventually find any path, as it considers every path. If there is a path that will move your King to a check-free place, alpha-beta will eventually find it, and get time to look at the unavoidable things that happen afterwards. As always, it holds that you need sufficient remaining depth to judge those things. The prurpose of the proposed technique is not to predict by magic what would happen afterwards, but just to discard the intervening checks as pointless delay, as a human would do.

The tricky issue is what should be the default assumption when you encounters a series of checks: whether you should count it as a perpetual until proven otherwise, or assume that you will eventually be able to find shelter from the checks. For humans knowledge helps. In particular that for an unprotected Rook moving towards it will help, while for a protected Rook or Queen this is pointless, and you should try to find something to shelter behind.

My intuition says forced perpetuals are rare, and much more often checks come to an end (except in the famous case of the rabid Rook). A standard search put way too much faith in that the checks will solve anything, rather than just postpone it. You would be right much more often then not assuming they change nothing. Which is the best you can hope for, in a search of limited depth. It will only get perfect when you search deep enough to see the full picture even after all delaying tactics.

I am not sure why the line you mention would be a problem. Is it that you don't know whether it is won to white, or draw? The default assumption that an advanced passer can be stopped at the expense of a minor, which would be made when evaluating leaf positions on branches that did not already promote the Pawn, would evaluate it as a very bad loss for white (R+2P vs N), and it seems quite relevant to know that this is wrong, even when you cannot see whether it is a draw or a white win. But the important thing is that the line you propose would be searched anyway. What I propose only alters the results of the checking lines, from a +3 score to a -2 score (black POV).

[stegemma]

Alpha-beta search will eventually find any path, as it considers every path. If there is a path that will move your King to a check-free place, alpha-beta will eventually find it, and get time to look at the unavoidable things that happen afterwards. As always, it holds that you need sufficient remaining depth to judge those things. The prurpose of the proposed technique is not to predict by magic what would happen afterwards, but just to discard the intervening checks as pointless delay, as a human would do.

The tricky issue is what should be the default assumption when you encounters a series of checks: whether you should count it as a perpetual until proven otherwise, or assume that you will eventually be able to find shelter from the checks. For humans knowledge helps. In particular that for an unprotected Rook moving towards it will help, while for a protected Rook or Queen this is pointless, and you should try to find something to shelter behind.

My intuition says forced perpetuals are rare, and much more often checks come to an end (except in the famous case of the rabid Rook). A standard search put way too much faith in that the checks will solve anything, rather than just postpone it. You would be right much more often then not assuming they change nothing. Which is the best you can hope for, in a search of limited depth. It will only get perfect when you search deep enough to see the full picture even after all delaying tactics.

I am not sure why the line you mention would be a problem. Is it that you don't know whether it is won to white, or draw? The default assumption that an advanced passer can be stopped at the expense of a minor, which would be made when evaluating leaf positions on branches that did not already promote the Pawn, would evaluate it as a very bad loss for white (R+2P vs N), and it seems quite relevant to know that this is wrong, even when you cannot see whether it is a draw or a white win. But the important thing is that the line you propose would be searched anyway. What I propose only alters the results of the checking lines, from a +3 score to a -2 score (black POV).

The problem is that after any check there could be an intermediate move, winning for the checking side or for the opponent. Alphabeta would find that move but we are talking about the problem that the checking line will put that move over the horizon, if there are any. We cannot know if there are that move, because the problem is in fact that the checking line can override the horizon. Any heuristics is welcome and can helps but, as you know, there are a lot of positions where it fails.

[bob]

Pointless delaying tactics can still be very effective for pushing trouble over the horizon. For example:

[d]1b6/4p2P/r2p4/8/6N1/8/4k3/1K6 b
Black cannot cover the promotion square, and a 1-ply search would see 2. h8=Q would follow any non-checking move. Black can delay the unavoidable by checking:

1... Rb6+ 2. Ka2 Ra6+ 3. Kb3 Rb6+ 4. Ka4 Ra6+ 5. Kb5

after which black runs out of safe checks. That adds 8 ply, 4 of which were taken care of by the check extension. But that still makes the promotion invisible to any search with less than 5 ply: after 5. Kb5 black will happily stand pat.

Preferably I would like a 1-ply search already to see the promotion (assuming promotions are searched in QS). I.e. it would be nice if the search would realize that the checks are merely pointless delays, which do not alter the threat situation in any way. Then it could prune them, rather than having them produce false fail highs. The problem is that not al checks are merely delay moves, and that it is difficult to recognize statically whether a check is pointless. (E.g. a seemingly pointless Pawn sac could lure the King to a square that is checked on promotion, and make all the difference.) To be sure the check did not just push the existing threat over the horizon you would have to search not only extending the check, but also the evasion. This would be very expensive, and could even lead to search explosion, so it is not really feasible.

To address this problem, the following heuristic occurred to me: 'suspect' moves, i.e. those notorious for being delaying tactics, such as checks or futile interposition as check evasion, define an 'analogy'. This is a mapping between positions that differ from each other by the suspect move plus its reply. E.g the check + the evasion, or the interposition and the renewal of the check by capturing the interposed piece with the checker. Note that the hash key of the analogous position can be obtained by XORing the hash key of the current position with the Zobrist keys describing the two moves that defined the mapping.

Whenever such an analogy is defined, it means we are in a sub-tree hanging from a suspected delaying tactic. If the suspected delaying tactic was really pointless, this tree should be identical to that hanging from the position before the delaying tactic, i.e. all moves by the delaying side should be refuted by the same cut move. If it would have been searched at the same depth, that is. But it is searched at a 1-ply lower depth. This means that some moves near the leaves will now not be searched for lack of depth. And this will corrupt the result.

There are two ways in which this can happen: a non-capture cut-move will now not be searched because it was pushed into QS, or a node that ought to fail low is rescued by a stand-pat in the face of an unsolvable threat. We can be alerted to this by looking at the analogous position without the delay, though: assuming we search suspect moves last, the undelayed sub-tree should already be in the hash table. So by probing the analogous position there, we should find a result that has been searched 1 ply deeper. In particular, the analogy to our current QS nodes should occur there with a 1-ply search result. This result should be a pretty reliable predictor of what would happen when we search the current node at 1 ply.

In particular, it is a sign of trouble when QS fails low, while the 1-ply search of the analogous position failed high through a non-capture cut move. Or whether stand-pat makes us fail high, while the 1-ply search of the analogous position failed low. You could decide to extend those, but that is expensive. A cheap alternative is to believe the 1-ply search of the analogous position rather than the QS result of the true position.

In the example this would work as follows: at 1-ply, all non-checking moves would be refuted by promotion. After 1... Rb6+ 2. Ka2 we get into QS without having suffered the promotion, so stand-pat would normally have worked. Because the check+evasion defined an analogy, however, we disallow stand-pat. (This is a special case, only occurring in the node directly after the delaying tactic: we cannot probe the has here, because the search of the analogous node has not finished yet, and is thus not stored in the hash. Because we got to searching the check, we know all non-checking moves must have failed low there, so we assume all non-checking non-captures will fail low now too. We should not do that if the check + evasion actually gained us material; such moves are not suspect.) We stil search all captures; after all, Rb6+ could have skewered K+Q, and we would not want to miss RxQ. But if we have no such luck, and the captures fail low, we return alpha, even though eval > alpha. We could even store that in the TT, as we genuinely believe this position to fail low in all cases, even though the fact that we noticed is was through a path-dependent clue.

So the 1-ply search now does assume white will promote. The 2-ply search will depend on a 1-ply search of the position following the check + evasion, which will similarly conceed that promotion is unavoidable, which then propagates to the 2-ply search, etc.

The opposite case occurs with futile interpositions. E.g. in the following position:

[d]8/3ppp2/7R/k7/8/2pPPP1P/P1Q1qr2/K1B3R1 b

In QS or at 1-ply black imagines it can gain a juicy Queen through 1... Qxc2. At 2-ply this can be followed by 2. Rg5+, which in absence of interpositions would be mate-in-2 through 2... Kb4 3. Rh4#. Black can delay the inevitable by

2... f5 3. Rxf5+ e5 4. Rxe5+ d5 5. Rxd5+ Kb4 6. Rxh4#

That requires 6 ply, if the evasions are extended (and no checks in QS). The Pawns are peanuts compared to the Queen black already captured, so black will not be impressed very much that it will lose a few, and only start to worry when he sees himself checkmated. Without interpositions the mate would be recognized at 3 ply.

At 3 ply the interposition f5 leaves a 1-ply search, good for Rxf5, after which e5 puts us in QS. As the check renewals are (good) captures, QS goes on some more moves, until the evasion Kb4. Then the mating move is a non-capture, and no longer seen in QS. (Note we are very deep into QS now, so even engines that search checks in the first few QS levels would no longer do it here.) In fact the evasion 3... Kb4 instead of e5 would already be considered good enough if QS doesn't search checks.

Now if f5 + Rxf5 define an analogy, the QS that would normally fail low after 2... f5 3. Rxf5 Kb4 (or Ka4) could probe the analogous position (after 2... Kb4), and find in the TT that the 1-ply search result for this was a mate-in-1 through the non-capture Rh4#. So it could assume it would be a mate-in-1 now, if we would have taken the trouble to search it. (A sort of reversal of the burden of proof.) So in stead of failing low for lack of captures to recoup the Queen, the analogy would make this QS node fail high. This is of course just a guess, but it seems the more-likely guess. In the TT we would store the entry with QS draft (d=0, say), but with Rh4# as cut move. At ply 5 Kb4 would then be seen not to work, and as a result we would have to consider alternative evasions, in particular e5 or d5. The combination e5 + Rxe5 would define a new analogy, however (replacing the old one in this sub-tree). When the position after 4... Kb4 would be 'analogy probed', it would find the 'upgraded' QS result there, and again be considered a d=0 position with a mate-in-1 result (as if Rh4# would have been a capture, which it would have been if there accidentally had been a black piece on h4). This continues to the very end, where no more interpositions are available.

Note that we only use the analogy in QS, to correct for the different behavior there. In deeper modes where the analogous moves would be searched anyway, we just search them to verify the reult is indeed what we expcet. We could still use the anlogous cut-move as a hash move, if we did not have one, or if it had higher draft.

You should read the paper Botvinnik and/or Donskoy wrote back in the 70's, "the method of analogies." It sounded pretty good, but it was way too expensive back then. I think this might have been Botvinniks paper now that I think about it, the one where Berliner excoriated him in the JICCA and called him an outright fraud... Berliner proved that his examples were fabricated, even though the underlying idea seemed reasonable.

[hgm]

The problem is that after any check there could be an intermediate move, winning for the checking side or for the opponent. Alphabeta would find that move but we are talking about the problem that the checking line will put that move over the horizon, if there are any. We cannot know if there are that move, because the problem is in fact that the checking line can override the horizon. Any heuristics is welcome and can helps but, as you know, there are a lot of positions where it fails.

Indeed, you cannot know what is over the horizon. This is why you have to guess. But it helps to make that guess as accurate as possible. And for that, it helps to make it as informed as possible. The normal static evaluation is the best guess you can make when you don't know anything at all; it is supposed to work on average best on all possible positions.

But if you know that a position very similar to the current one has already been searched, you might be able to use the information obtained from that to your advantage. It is relatively rare that the score of a node is below the static evaluation, i.e. that the advantage of having the move would not be enough to deal with any threats (unless, perhaps, when you are in check, which is why we extend checks). It usually means there is a fork or a skewer (or in the case of the example an unstoppable promotion) aiming at you. If you know this was the case in a position that only differs in the location of 2 pieces one of those a King (which during most of the game does not exert very much influence on play), it might be a relatively safe bet that there is such a threat against you in the current position as well. It could of course be that the check really solved the fork, because it was a safe check with one of the forked pieces. Then your guess was wrong. But this is only in a minority of the cases, and you would correct that mistake if you search deeper, so that the resolution of the fork is within the horizon even after the check.

[hgm]

You should read the paper Botvinnik and/or Donskoy wrote back in the 70's, "the method of analogies." It sounded pretty good, but it was way too expensive back then. I think this might have been Botvinniks paper now that I think about it, the one where Berliner excoriated him in the JICCA and called him an outright fraud... Berliner proved that his examples were fabricated, even though the underlying idea seemed reasonable.

Sounds interesting. But note that what I propose is not expensive at all. It is in fact basically free. You don't search a single extra node because of it. You just take the score from the TT table, (from a recently stored entry!), but not from the position itself, but from a nearly identical one.

[stegemma]

You should read the paper Botvinnik and/or Donskoy wrote back in the 70's, "the method of analogies." It sounded pretty good, but it was way too expensive back then. I think this might have been Botvinniks paper now that I think about it, the one where Berliner excoriated him in the JICCA and called him an outright fraud... Berliner proved that his examples were fabricated, even though the underlying idea seemed reasonable.

Sounds interesting. But note that what I propose is not expensive at all. It is in fact basically free. You don't search a single extra node because of it. You just take the score from the TT table, (from a recently stored entry!), but not from the position itself, but from a nearly identical one.

At first sight this could sounds dangerous, for an engine, but if we think at an human player we realize that this is the way how a chess player "evaluates" a position. In fact, an engine that reached the horizon is similar to an human who always works at the horizon edge. The engine can't have an human brain but yes, it could search in its own TT. It is not clear how you define similarity, maybe removing checking piece and king from the hash value? This would be no expensive, i think.

[Gerd Isenberg]

You should read the paper Botvinnik and/or Donskoy wrote back in the 70's, "the method of analogies." It sounded pretty good, but it was way too expensive back then. I think this might have been Botvinniks paper now that I think about it, the one where Berliner excoriated him in the JICCA and called him an outright fraud... Berliner proved that his examples were fabricated, even though the underlying idea seemed reasonable.

Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (1975). Some Methods of Controlling the Tree Search in Chess Programs.
has chapter 4 Method of Analogies, reprinted 1988 in Levy's Computer Chess Compendium

see also
http://www.stmintz.com/ccc/index.php?id=19469

[hgm]

Well, any form of static evaluation is dangerous for an engine. The question is whether it is more or less dangerous to make specific assumptions tailored to the position, (based on a more elaborate search of its 'analog'), or make completely general ones.

The hash key of the analog is simply the key of the current position XORed with the from- and to-keys (and possible victim keys) for the two moves that make it different (i.e. the check and the evasion). That 'difference key' can be calculated once by XORing the key from just before and just after the move pair (assuming these are accessible in a stack also used for repetition checking), when you play it. It can then be used to map positions to their analog through the entire sub-tree by a single XOR operation. And if the check+evasion were not too far from the leaves, they access recently stored (and thus still cached) TT entries. That should cause an unmeasurably small slowdown. The question is whether it on the average will improve accuracy of the scores, or destroy it.

You might even improve the branching ratio by using the analog move as hash move when you don't have one for the current position.