Spite checks, again

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Post Reply
User avatar
hgm
Posts: 22195
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Spite checks, again

Post by hgm » Sun Oct 23, 2016 9:07 am

Even with check extension, checks shave 1 ply off your depth. So they would remain a good way to mask problems, e.g. that you are unavoidably getting checkmated as soon as you run out of checks. The following is an attempt to cure that.

When the previous two ply were a check + evasion that did not gain any material, current evaluation is above beta, and the null move fails high, you are in a highly suspect situation. The fact that you are searching this line at all indicates that two ply earlier the null move must have failed low (starting from a position with as least as good an evaluation). So there must have been a threat against you. And most of the time delivering checks doesn't solve any threats. So it is likely that you pushed the threat over the horizon.

To prevent accepting a false result, we can re-search the null move one ply deeper. This is an expensive measure, but still relatively cheap, because it is still reduced compared to the nominal search depth. Just somewhat less reduced. So now you are searching with the same depth as two ply earlier, and should be able to see the same threat. A fail high now would mean the check really solved the threat. (E.g. you might have sacrificed away the piece making the threat, accidentally checking as a side effect.) But most of the time you will of course fail low now, because the threat is still there. The spite check just pushed it over the horizon.

This means you are in a situation that you cannot afford spite checks to reduce the distance to the horizon, and would have to extend the entire node, to make the check+evasion plies free. This, however, would cause (near) infinite recursion in situations where spite checks could drag on forever. So we only extend all non-checking moves, in an LMR-like way, i.e. we accept a fail low at the nominal depth, but will re-search the move with one ply extension if it fails high.

The checking moves will be treated differently. Before embarking on their search, we define an 'analogy'. This is a hash-key shift inverting the key change brought about by the check+evasion plies, plus the evaluation change caused by them, remembered globally (i.e. seen by all nodes of this search). The extension procedure described so far is suppressed when an analogy is already defined.

The analogy will remain in force for the search of the checking move, but can be 'updated' when in the sub-tree of that new check+evasion pairs occur. In that case the key shift and evaluation changes of the check+evasion pairs in the current branch are accumulated. The key shift allows the search to probe the hash table for an 'analogous position', i.e. the position brought about by the same move sequence omitting the checks + evasions, and use their scores to estimate the score that the current position would get from a search of the hashed depth, by adjusting them with the accumulated evaluation change of the check+evasion pairs.

Now the search will only make use of this possibility in the leaves, as an alternative for stand pat. The assumption is that the result of a real search of the analogous node will be a better approximation of the score of the current one than the static evaluation, in the face of threats very close to the horizon. So if the hash table says that at d=1 the analogous position had a score <= -500 (an upper bound), alpha = -450, and we spent 100 in spite checks, we would assume the score in the current position is<= -600, even when the current evaluation is -200. In the analogous position the static evaluation would have been -100, (as we did not toss any material in spite checks there), but whatever we did there would still leave us at -400,. So apparently an unavoidable loss of 400 looms just behind the horizon. (E.g. our Queen is skewered to the King by a Rook.) This doesn't cost any extra nodes; it just tries to make smart use of information already there.

The crux is that when we define the analogy, the analogous node two ply below us is being searched already one ply deeper (because of check extension) than the current one. Although that search is still in progress, on the previous iteration it will have been searched at the same depth as we need now. After we do the new check+evasion pair we are just embarking on, we will still use that same node two ply below us as an analogy, but we will then need results that are yet one ply less deep. So any analogous position in its sub-tree will, on probing, be found in the hash table with a depth one or two ply higher than what we need. This effectively boosts the search depth one ply (in so far the analogy can be trusted).

To enhance reliability we can put some effort in making sure we use the closest-available analogy. I.e. after we make a new check+evasion pair, we don't automatically accumulate it in the (key shift, evaluation change) pair to keep the current analogy, but we can probe the TT for the analogous position of the current one. If this already is available at a depth one higher than we need to effectively extend the checking move, it means that the analogy of the spite check we are trying now was already searched in the node two ply below us before the current branch. So the nodes in its sub-tree would be present in the TT with a depth good enough for our purpose, and we could use that as an analogy, differing only by one check+evasion pair from the current node, rather than two.

Karlo Bala
Posts: 296
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Spite checks, again

Post by Karlo Bala » Tue Oct 25, 2016 1:51 am

hgm wrote:Even with check extension, checks shave 1 ply off your depth. So they would remain a good way to mask problems, e.g. that you are unavoidably getting checkmated as soon as you run out of checks. The following is an attempt to cure that.

When the previous two ply were a check + evasion that did not gain any material, current evaluation is above beta, and the null move fails high, you are in a highly suspect situation. The fact that you are searching this line at all indicates that two ply earlier the null move must have failed low (starting from a position with as least as good an evaluation). So there must have been a threat against you. And most of the time delivering checks doesn't solve any threats. So it is likely that you pushed the threat over the horizon.
...
Never tried, however always thought that the side in constant check should have eval at most 0 or very close to 0 (the weaker side has at least a perpetual check).
Best Regards,
Karlo Balla Jr.

User avatar
hgm
Posts: 22195
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Re: Spite checks, again

Post by hgm » Tue Oct 25, 2016 6:54 am

That depends a lot on whether the checks are burning material, if the last three checks before the horizon tossed a Queen and two Rooks, the checking side is likely getting checkmated.

Post Reply