Hosted by Your Move Chess & Games
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Spite checks, again
Post new topic Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message

Joined: 10 Mar 2006
Posts: 21813
Location: Amsterdam

PostPost subject: Spite checks, again    Posted: Sun Oct 23, 2016 9:07 am Reply to topic Reply with quote

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.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
Spite checks, again H.G.Muller Sun Oct 23, 2016 9:07 am
      Re: Spite checks, again Karlo Bala Jr. Tue Oct 25, 2016 1:51 am
            Re: Spite checks, again H.G.Muller Tue Oct 25, 2016 6:54 am
Post new topic Forum Index -> Computer Chess Club: Programming and Technical Discussions

Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads