Hash Refutation

[D Sceviour]

There is no need to search a position to full depth to find a mate in one, and that is much of the problem.

[hgm]

Indeed. But you have to search at least one ply to see that. And in 99.9% of the nodes there will of course not be a mate in 1, while the same problem (the root score dropping because the PV gets refuted) occurs there just as often. Butthe idea is always the same: there is one good move amongst a large number of poor moves, and quite low depth would already be enough to recognize that. But alas, you only start to need that move when the depth is already quite high.

This is what makes IID so useful. You go through a lot of no-good moves at reduced depth, until you find something good. Then you re-order, putting the something good in front of all the rejected stuff, for the full depth.

This solves both the problem of the window having been raised to above the hashed lower bound, and the problem of the hash move dropping very much in score from one iteration to the next.

[D Sceviour]

We seem to have a good picture of IID. IID is normally used on a PV node when there is no best move stored in the hash table. The difference with hash refutation is IDD is used when it is not a PV node and there is already a best move stored in the hash table. That is why a trick has to be played on the IID checklists to make sure it triggers. An alternative might be to do a shallow verification search in the code above that said { Do something about it! }

Another idea tried was to test for possible mates in the first move list ordering but that becomes too expensive on time and usually fails (perhaps 99.9% as you mention).

[hgm]

Normally one would use IID in any node were one lacks a reliable cut move, and the depth is so large that it would be very expensive to just try all the moves blindly at the full depth. I don't see why that that would be any different in non-PV nodes.

It seems obvious that a move with a +200 lower bound is not reliable in the face of a +500 window ('hash refutation'). And that a randomly piciked alternative for a hash move that failed low also inspires little confidence (self-deepening).

As to the search for mate-in-1: my Shogi engine actually does test for mate-in-1 by drop moves in every node, even in QS. And that very significantly increased its strength. But in Shogi the probability for this is of course not small, especially deep in QS when the hands fill up. And I don't use normal search for this, but a static recognition algorithm. ('Mate at a glance'.)

[D Sceviour]

H.G. Muller wrote,

Normally one would use IID in any node were one lacks a reliable cut move, and the depth is so large that it would be very expensive to just try all the moves blindly at the full depth. I don't see why that that would be any different in non-PV nodes.

I have tried a more aggressive use of IID, but the results tend to drag on time without much gain. Other engines concur. For example, in Crafty's notes to IID:

If there is no best move from the hash table, and this is a PV node, then we need a good move to search first.

Hash refutation might be the exception to this rule.

[hgm]

Well, normally the root score does not change very drastically from one iteration to the next, so normally the hash moves in the non-PV side branches just have to repeat their previous performance to deliver the sought cutoff. So normally having a hash move would be enough not to worry much.

But, like you say, with 'hash refutation', where the hashed bound falls far below beta, this would be a clear exception . The move is still the earliest one in the static sorting (and thus probably the most likely one) that might do the job, and the poor lower bound might just be a consequence of laziness lower down the branch (like null moves where good moves were available). But is seems very useful to first test it cheaply at a far lower depth. Because if it falls far short of the mark there, hoping that it will magically improve on larger depth is just wishful thinking. This is where the 'self-deepening' comes in: instead of searching the suspect hash move unconditionally at maximum depth you order it to iteratively deepen the following expected all-node (which in fact might very well be a cut-node in this situation), and abort the deepening when that node fails high (meaning that the hash move in the parent failed low with respect to the more demanding window).

Without hash move in a non-PV node I would not be so confident that the first move of the static ordering will do the job when the job is not trivial. It is true that null-moving tends to delay cashing of gains; most of the tree is the low-failing side exposing its material to capture, and the high-failing side just ignoring that. So when you let the opponent's scorecreep up so high that action is required, just executing the most valuable 'hostage', as MVV sorting would, will usually be enough to push him back under water. But you can see (or actually SEE) if you have such a move available, and sometimes you just haven't got what it needs. Often the only thing that helps then is a threat evasion, and that might not come very early in the static ordering at all, if the threat was created with the preceding move (so that ot would not be killer). IID would find the evasion very cheaply...

So I guess it all depends on what exactly you mean by 'applying IID more aggressively'. Did you try to apply it in non-PV nodes after the hash move turned out to fail low (unexpectedly or expected because of a strongly raised window)? Did you try it in all-nodes that have a hashed lupper-bound score far above the current window? These are the cases where one expects it would help. OTOH, when you do it in nodes where there is a SEE = +5 capture while the eval is only 2 Pawns below beta, it would probably be a waste of time.

Sharp tools should always be used with precision...

[D Sceviour]

There is a lot of room for study and error here. One has to rely on the opinion of other programmers to a certain degree. I tried IID on non-pv nodes with a lazy evaluation > beta and for some reason a null move search was not tried.

Do you have a source example of self-deepening? Some code might be easier to understand.

[hgm]

My new engine 'Simple' uses self-deepening IID (and LMR). I just put the (highly commented) source code in my on-line git repository. The entire source is contained in a single file, and is only some 1500 lines long.

[D Sceviour]

I compiled Simple and ran a few quick tests. It crashed in one game, but demonstrated a strength of about 1800 elo. It seems that the self-deepening flag extraDepth is to make sure the engine depth does not exceed a certain iterative depth.

extraDepth = (depth > iterDepth ? depth - iterDepth : 0);

There does not appear to be any IID, but as you indicate the entire routine is a self-deepening routine. It is very interesting and looks worth closer examination, but it does not relate to PV refutation.

I plugged hash refutation into simple.c as a simple demonstration but could not find a suitable flag to indicate whether the phase is a pv node or not. It plays about the same strength, but the paramaters are probably not correct.

Code: Select all

if (&#40;bucket->score&#91;slot&#93;<beta&#41; 
&& &#40;bucket->flags&#91;slot&#93;=LOWER&#41;
&& &#40;depth-bucket->depth&#91;slot&#93;>5&#41; 
&& &#40;checker=0&#41;)
&#123; 
    bestScore = -Search&#40;-beta, 1-beta, -mobilityGuess, INF, 0, 0, 2, 0&#41;;
    if &#40;bestScore > beta&#41; 
	 return bestScore;
&#125;

[elpapa]

if ((bucket->score[slot]<beta)
&& (bucket->flags[slot]=LOWER)
&& (depth-bucket->depth[slot]>5)
&& (checker=0))
{
...
}