Hash Refutation

[D Sceviour]

H.G. Muller wrote,

So it is best to control the IID directly from the PV node. This will then effectively inhibit IID in the entire set of side branches.

I tried that and it is not quite correct. First, the new move trying to refute the PV may not be in the PV line. That is, the new move may be another one in the root move list.

Second, PV nodes are exact scores and have already been searched full width. It is better to concentrate on fail high hash entries because these are the move lists that have not been searched full width.

[hgm]

I tried that and it is not quite correct. First, the new move trying to refute the PV may not be in the PV line. That is, the new move may be another one in the root move list.

True, sometimes the PV refutation cannot be repaired in the current PV node, and has to be repared closer to the root. Sometimes it cannot be repaired before it reaches the root, or even in the root itself. But that doesn't mean the current node isn't the best place to try to repair it. Of all the nodes between the root and itself it is the node with the shallowest side branches, and when you can get a move there that was close to the originalscore of the PV move that was now refuted, you are back to 'business as usual' in the still lower levels.

Second, PV nodes are exact scores and have already been searched full width. It is better to concentrate on fail high hash entries because these are the move lists that have not been searched full width.

They have all been searched to nearly the required depth, but not with a relevant window. They could all have failed low against the (now refuted) high score of the hash move. And that would mean you have no idea which of them were good and which truly stink. Nevertheless it seems very dangerous to restart at lower depth just for that. Because you might do it again and again. If the PV hash move scored +200 at d=7, and now that you are at d=8 scores only -400, many other moves might run into the same deep tactics that eventually refuted the PV. So you would re-search all alternative moves up to d=7 to find the second best there, which might be +190, and then at d=8, boom, it drops to -410. You could then launch a new IID search to eventually get the 3rd-best move at d=7, see that fail low at d=8 too, and so on, and so on...

It is a very tricky problem. There is a definite possibility that all moves look good at d=7 (say between 0 and +200), and most of them then are dramatically refuted at d=8 (because of the same weakness they failed to repair), except the very few that address the weakness. Then you would always plunge in at d=8 blindly, with very little chance of success. IID won't help, and is thus just a waste of time. That is the worst case, however, and there will also be cases where the d=8 refutation could only be masked at d=7 because of a unique series of delaying tactics, and for any other sequence of moves the axe would fall already at d=7.

I guess this is where aspiration can prove its worth.

[D Sceviour]

H.G. Muller wrote,

And that would mean you have no idea which of them were good and which truly stink. Nevertheless it seems very dangerous to restart at lower depth just for that.

We seem to be getting off track. That is exactly what happens when black loses the Queen and the PV is refuted. With beta cutoffs, the line returns very quickly to the root to look for another move. The problem starts when searching deep on move lists that have never been searched full width. We do not know what is there, but we do know where to start. You have to accept that searching the PV is a waste of time, as it contains no useful information anymore. The thing is shocked as you say.

[hgm]

BTW, I now discovered a bug in the self-deepening of the version of SImple you have seen. The way I combined the deepening because of an LMR re-search with the deepening due to IID cut moves was not correct, as the cases are subtly different:

For IID you want to continue searching the cut move for as long as it is really causing a cut (i.e. score >= beta). For LMR you already want to deepen (to the unreduced depth) if it scores > alpha. In PVS this is of course the same, as you only do LMR on non-PV moves, which all have beta = alpha+1. But Simple uses plain alpha-beta. So the condition for adding extra iterations in the daughter node has to distinguish the cases, and either only add 'reduction' or 'reduction + extraDepth' iterations, rather than always lumping 'extraDepth' with 'reduction'.

This does in fact raise a question pertaining to what we were discussing:

If you get in a PV node without hash move (which happens in PVS every time you over-turn a PV, as the previous null-window search then failed high, so that the daughter, which now becomes the first node of the new PV continuation, must have failed low), you would start IID. Moves that in the shallower iterations fail low can of course be discarded without further thought. If you find a move that fails high, the current node might not be PV after all (i.e. the preceding fail high on the null-window search was a false one, and has disappeared due to search instability). But the interesting case is when you get a move that scores between alpha and beta (as you expect you would):

You can either just use it to raise alpha, and finish the iteration, before embarking on the next depth (starting with that move, if no other move beat it). This means the remaining moves are all searched with a pretty high alpha, to which they failed low. So they would remain 'poorly ordered'. Now if in the final iteration the score of that move suddenly drops drastically, the remaining moves would be searched at the largest depth and much lower alpha by 'plunging in blindly'.

The alternative would be to treat a PV score the same as a fail high, and also (self-)deepen it before going to the next move. (In the daughter that would mean adding extra iterations for any score that ends below beta, rather than only when score <= alpha.) This would latch on to any PV-move candidate at low depth, immediately verifying if it stays good until the target depth, and only raising alpha to the score it will eventually get at this target depth. If the move peters out before the target depth, there would be no raise of alpha, and the search of the remaining moves would continue at the low depth as well as the low alpha.

The latter sounds like a much more robust way to do it, in the sense of optimal handling of the worst case. (This does not guarantee that it is faster on average, of course.) The problem is how to make it survive the process of hashing. If you are deepening within the node you would quickly deepen the PV move for as long as it stays PV (as you would when you did not do IID at all, immediately search every move to the target depth), but when it fails low you would resume the low depth without alpha having been raised. If you restart the IID from a hashed value of one-lower depth (created by the previous root iteration), and the PV hash move fails low, you would not really know what depth to fall back to. So I guess you would have little choice other than to start IID from the lowest depth.

[D Sceviour]

H.G. Muller wrote,

So I guess you would have little choice other than to start IID from the lowest depth.

Correct. You are trying to beat the normal alpha-beta search. However, you end up with solutions that show it is a waste of effort. IMHO self-deepening needs a substantial depth window to avoid this problem.

For anyone out there who might be trying hash refutation, insert a printf(beta-tt.value) inside the test and you will see that a fail-high hash miss does not occur that often. It might trigger when the lower depth move does not perform a null move search because of in check status. That would be from 2. Rxg7+ in the OP example. Therefore, hash refutation is mainly to prevent thrashing during mate hunts and spite checks.

[D Sceviour]

I noticed a glaring error in the line that should have read 2... Ke8 3. Rxh7? I must apologize as with age it seems more and more that grammar errors get past my eyes. The protocol will not allow changes to the post after 15 minutes. Perhaps the moderators could assist with stuff like this. Of course, maybe no one else noticed it.