Marginal hash move

[hgm]

Some times an iteration just seems to last forever, when the engine alters the PV. I have traced what is going on in such a case, and very often it is this:

At low depth you find a move that causes a beta cutoff. This then becomes hash move, and the search will try to keep using that move to cause the cutoff. If it is a 'marginal cut move', where the exact score lies only very little above beta, this will be a lot of work, because you nearly have to reproduce the exact score. Especially so if it is a quiet move, and there are many nearly equivalent replies to it. After each of those you would again have to work very hard to prove a fail high.

This is kind of wasteful if there would have been another move in the original node, with a much higher exact score. If you would have used that as cut move, it would be relatively cheap to prove its fail high, because its exact score is so much above beta that you don't have to do your best to find cut moves deeper in the sub-tree; almost any move that doesn't blunder away a great deal will already do the job.

But since you went for the first move that did the job, you would never know if such a better cut move exist. Of course you hope that the static move ordering, MVV/LVA captures first, would usually give you the cut move that grabs the most material, and thus has the highest exact score. Often this works.

Sometimes there is nothing to grab, however. And no threats against you to resolve. And the current evaluation is close to beta. So you must either try to cut with a positionally good and tactically sound move that the opponent cannot top. But then he will have many moves that come very close, so this will be very expensive. Or you could make a threat. Solving it limits the opponent's move choice, so he cannot do his most profitable moves, and likely the exact score will be better by keeping the opponent under pressure this way. Perhaps you even have a decisive threat, against which the opponent has no defense, and then the exact score would be very much above beta. Problem is that threat moves are rare, and in positions where they exist, they are also rare amongst your playable moves. So the chances that you pick them as hash move are pretty slim. Most likely you would find some good positional move first, and stick to that.

Of course the killer heuristic is supposed to help you find such a threat move before trying all your non-captures (which then likely would give you the expensive positional cut move). The disgusting thing is that the threat move usually would not become killer either. Because to do so, a sibbling node should have found it, and these sibblings had exactly the same problem. They are likely to find the expensive positional cut move first, and make that killer. This makes it even less likely that other sibblings will find the threat move, as they will all try that same positional killer first, and usually it would work.

It is hard to solve this problem without refusing the beta cutoff. You could hope that the history heuristic hands you the threat moves, but there is no guarantee the same threat is common everywhere in the tree. And even if it is, there is no guarantee that the search would use it, exactly because of the mentioned problem. If many nodes use a positional killer rather than the undetected threat move, it is the positional killer that will get the good history. At some point you will have to spend work to try to discover threat moves before you can judge and award their performance.

Now ignoring beta cutoffs in an attempt to find the best cut move would of course give you minimax, which is prohibitively expensive. But if the depth gets very large, having a sub-optimal cut move might cost so much compared to having a better one, that it might pay off to spend a small fraction of the search time normally needed at that depth for checking if you are not 'betting on the wrong horse', and repent your ways when you have been so far.

So suppose for depth = 11 I would not just start searching a non-capture hash move, but instead would do an open-window d=1 search on all other moves, to see which is best. (Well, a half-open window, {beta, INF}.) And then, if that is (significantly) better than the hash-move bound and beta, conditionally deepen it with the normal window for as long as it fails high. In the hope this would give you a cheaper hash move.

There are a few dangers here. For instance, if any of the captures look good at d=1 you should wonder how it is that the hash move is a non-capture. At some point between d=1 and the currently requested depth > 10 it should have been chosen because all the captures failed low. In general, all moves that in the static ordering would come before the hash move are suspect this way. You might not be able to reconstruct the order of the non-captures if you used history, but good captures would certainly have been searched before a non-capture hash move, and must have failed low at a depth higher than the d=1 you are using now to hunt for a better cut move. So you might as well exclude those immediately.

[hgm]

Would it be a good idea to re-search the null move when it fails low, at a lower depth but with a wider window? I.e. in stead of {beta-1, beta} use {beta-100, beta}. This would force the null-move reply to work harder to find the best cut move in an attempt to find a devastating one (which scores above beta+100). This would then become killer, and would be tried with priority to refute all quiet move.

You would do such a re-search after having searched all the good captures, (which would need tactical refutations), and your own killers (which you count on to be irrefutable), just before searching other non-captures. You might do that only when the null move was refuted by a non-capture; if it was refuted by a capture, that capture would likely refute most quiet moves as well, so that their replies would never get to the killer stage.