Hash Refutation

[Henk]

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.

When do you expect Simple to be World Champion ? And will it be the end of Stockfish project ?

[hgm]

I compiled Simple and ran a few quick tests. It crashed in one game, but demonstrated a strength of about 1800 elo.

Note that I just started to write this engine from scratch 2.5 weeks ago, and that although it already beats Fairy-Max, it isn't really fit for testing yet. The version in the repository still makes occasional false illegal-move claims, which I now traced to a refusal to accept his own e.p. captures due to a problem with remembering the previous move. Nothing is tuned, and most evaluation features are still switched off, so that it is playing by PST only.

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);

Normal IID would only search the node up to 'depth', which in the parent is then derived from 'iterDepth', (by subtracting one), the depth of the iteration (which will eventually run to 'depth' of that parent node). In this case the move could fail high in the parent for that iteration, but would then have to be searched again for the next iterations again and again, for as long as it keeps failing high (so that it cuts off that iteration). By specifying with the 'extraDepth' parameter how far this repetitive searching of that same cut move should go before the 'depth' of the parent node is satisfied, there is no need to return to the parent node all the time (and then having to generate the move list again when the parent sends control back to the same daughter), but the node mimics this repeated calling by stepping up its 'depth' as many times as the 'extraDepth' allowed it, as long as it fails low (meaning the move in the parent failed high).

Note that I integrated this with LMR, which would also order an immediate re-search of moves that fail high, at unreduced depth. Instead of applying a reduction in the parent, the parent just passes a flag to the daughter to indicate the preceding move was 'late'. The daughter then transfers the reduction from 'depth' to 'extraDepth', so that the search will stop at the reduced (iteration) depth if the late move in the parent failed low, but continues to the nominal depth if it failed high.

PVS re-searches could be treated in a similar way, but this engine uses vanilla alpha-beta.

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.

There is in fact IID everywhere. The choice is just whether you do that deepening in the parent (the conventional method), or in the daughter (self-deepening). The conventional method (which can be mimicked by setting extraDepth = 0 always) leads to repeated return to the parent and immediate research of the same daughter for as long as the iterations fail high. But that is not the only difference: when at some point the move would start to fail low, alternatives would be searched at the depth where this happened. When the daughter was deepening itself in an attempt to satisfy depth+extraDepth, it would leave the iterDepth of the parent untouched, so that when it fails to reach depth+extraDepth, the alternatives will be searched at the lowest depth where they were not yet searched before.

Whether there will be IID in a node or not is controlled by the start value of iterDepth. On a hash hit with useful bounds it will be started at the hashed depth (and incremented at the start of the IID loop). In other cases iterDepth starts at 0 (meaning IID will start at 1-ply). Note that this also includes the case where you have a hash move, but where the score bounds were not useful. And I think that would catch your 'hash refutation' case: the score bound would not be good enough to be usable, so it starts to deepen from scratch.

It is actually the other case, finding alternatives for a former cut move that suddenly fails low, that suffers from hashing. When starting the node from scratch it might find a cut move already in iteration 1, which then self-deepens to (say) 7 ply, the full depth of the node. So it gets stored with d=7 in the hash table. If the full depth had been 8, and the hash move failed low when it tried to deepen itself to 8, the node would remember that it was realy involved in the 1-ply iteration, and would continue that to find alternatives. But if the node is revisited with a d=8 request, and the hashed d=7 score looks good for a cutoff, so that the first IID iteration starts at d=8, if the hash move fails low, it will try to find alternatives at d=8 rather than d=1, because the information that the other moves have not been searched at all yet was not transferred through the hash.

Basically both depth and iterDepth should be stored in the hash entry, so that after a hash hit 'depth' could be used to decide on a hash cut, but if there is none, iterDepth could be used to resume the IID. If the hash move stays good iterDepth would be irrelevant, as the hash-move search would deepen itself to the now requested 'depth' anyway. But if it fails low against expectation, IID would start at lower depth. Now adding an extra depth field in the hash entry is of course rather expensive. An alternative would be to always reset iterDepth to 1 after an unexpected hash-move fail low, (as it is now already done on a fail low that was expected because of unusable bounds), and count on the first few iterations to be rapidly satisfied from the hash entries for the daughter nodes until you arrive at the depth where the real work starts. To slightly speed this up you could have the daughters pass the depth of the hashed result to the parent, so that after the 1-ply iteration it would be known how to increase iterDepth to get some real work done.

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.

As this is not PVS, the concept of PV node is a bit ill-defined, and only known after the fact (when the score is in window). In PVS you know it in advance, because you do the null-window scout search before opening the window to make it a PV search.

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;

I hope you have ==LOWER there, and note that not-in-check is indicated by checker<0 (as 0 is square a1).

But note that this is really not expected to do anything that is not already done: the condition score<beta && flags==LOWER is already tested in the hash-probe code, and when satisfied leads to iterDepth being set to 0 (via a signalling -1 detour to suppress in-check testing), requesting IID.

To implement depth-reset on hash-move fail low would be trickier. It would require a 'resetOnFail' flag to be set if there is a valid hash move, and this flag to be tested after the usual if(score > bestScore) section (from which you would never emerge on a cutoff). If it would be set, iterDepth should be reset to 1, and in any case the flag should be cleared.

[D Sceviour]

H.G. Muller wrote,

But note that this is really not expected to do anything that is not already done: the condition score<beta && flags==LOWER is already tested in the hash-probe code, and when satisfied leads to iterDepth being set to 0 (via a signalling -1 detour to suppress in-check testing), requesting IID

I cannot understand why you say there are no expectations unless you refuse to try it. The condition score<beta && flags==LOWER would return a hash miss after hashprobe(). Nothing is being done to reaffirm the move ordering or to stop the engine from deep searches on irrelevant moves. In fact, the signaling IID requests extend the searches even worse.

Further tests indicate a small improvement in Simple. Perhaps I am mistaken, but it seems to change style similar to the aggressive attacking style noted in Schooner.

[hgm]

I cannot understand why you say there are no expectations unless you refuse to try it. The condition score<beta && flags==LOWER would return a hash miss after hashprobe().

Indeed. And if there is a hash miss, Simple always starts IID at the 1-ply level:

Code: Select all

  int hashDepth, iterDepth = -2; // KLUDGE: use this invalid value for iterDepth to signal hash miss.

...

    if(bucket->signature[0] == sig) slot = 0; else
    if(bucket->signature[1] == sig) slot = 1; else slot = -1;
    if(slot >= 0) {                                  // we have a hash hit
      hashMove = bucket->move[slot];                 // in any case use the move
      checker  = hashMove>>24; hashMove &= 0xFFFFFF; // and the in-check info packed in it
      if(checker >= 0) checkDir = vector[king-checker], checkDist = dist[king - checker];
      if(ply > 0 &&                                  // force starting at d=0 in root. TODO: in all PV nodes? (optionally?)
         (bucket->flags[slot] & LOWER ||
          bucket->score&#91;slot&#93; <= startAlpha&#41; &&
         &#40;bucket->flags&#91;slot&#93; & UPPER ||
          bucket->score&#91;slot&#93; >= beta&#41;  ) &#123;          // bound is useful
        iterDepth = bucket->depth&#91;slot&#93;;             // so IID can continue from stored depth
        bestScore = bucket->score&#91;slot&#93;;             // and use the score
      &#125; else iterDepth = -1;                         // signals unusable hit
    &#125; else &#123;                                             // hash miss. Reserve slot for new entry by 'under-cut replacement'&#58;
      static int f;                                      // 'coin-flip' variable, to 'randomize' which slot we try to undercut
      if&#40;bucket->depth&#91;f&#93; == bucket->depth&#91;!f&#93; + 1&#41;      // if stored depths differ by 1 we replace the deepest in 50% of cases...
        slot = f, f = !f;                                //    to prevent deep entries live forever and eventually poison the table
      else slot = &#40;bucket->depth&#91;0&#93; > bucket->depth&#91;1&#93;); // otherwise 'slot' is set &#40;to 0 or 1&#41; to indicate lowest-depth entry
      hashMove = -1;                                     // no hash move on hash miss. KLUDGE&#58; -1 signals miss
    &#125;

 ...

    if&#40;iterDepth >= 0&#41; &#123;                           // we had a hash hit with usable score bound
      if&#40;checker == -3&#41; iterDepth = 256;           // mates valid to any depth  TODO&#58; upgrade longer mates too?
      if&#40;iterDepth >= depth + reduction ||         // if sufficient depth for unreduced search...
         iterDepth >= depth && bestScore >= beta&#41;  //     or for reduced search when it will fail high
          goto Out;                                //     return bestScore immediately
    &#125; else iterDepth = 0;                          // without usable hit, start IID from scratch

...

  do &#123; // IID Loop; done at least once, as hash cutoffs were already taken before
    int current, bestNr = captures;     // assume first move is best &#40;in case all fail low&#41;

    iterDepth++; // Even without hash hit start at 1 &#40;in QS the move list only contains captures&#41;

... // search moves at d = 'iterDepth'

  &#125; while&#40;iterDepth < depth ||                                         // start next depth iteration if not yet there
          !ply && !forceMove && iterDepth < maxDepth && !TimeIsUp&#40;1&#41;); // but in root for thinking continue until time is up

The trick is in the line with the comment "signals unusable hit"; this would be executed in case the condition you layed out were true. The later test for a hash cutoff corrects the value -1 to 0 in the else part.

[D Sceviour]

So the line

Code: Select all

else iterDepth = -1;                         // signals unusable hit

sets the search depth to 1?

[hgm]

So the line

Code: Select all

else iterDepth = -1;                         // signals unusable hit

sets the search depth to 1?

Indeed. Because of the subsequent

Code: Select all

    if(iterDepth >= 0) {                           // we had a hash hit with usable score bound
... // tests if hashed depth is good enough for hash cut
    } else iterDepth = 0;                          // without usable hit, start IID from scratch

and the IID loop starting with

Code: Select all

    iterDepth++; // Even without hash hit start at 1 (in QS the move list only contains captures)

This means that the first iteration is done at d=1, as the recursive calls to Search() in this loop are made with iterDepth-1 as 'depth' parameter. On a valid hash hit iterDepth would be set to the hashed depth during the probe, so that IID would start at the first depth above that.

Note that this is rather primitive 'micro-Max style' IID, where you run through all depths 1-N in steps of 1. This could of course be tweaked by adding some statement before the loop to determine optimal starting depth and increment based on the depth available from hash and the target depth, and perhaps the score of the hash probe or previous iteration ('hashScore'). E.g. you could decide to skip to the final depth if the previous iteration or hash hit suggests you are in an all-node because it failed low.

[D Sceviour]

So more or less, your solution to hash refutation is

Code: Select all

	depth = 1;
	iterDepth++;

Ok, that makes some sense. However, this seems like too much researching near the horizon. That is one reason I suggest a depth limit of 5.

The self-deepening also applies to a fail-low condition, which is another matter. That would probably not have anything to do with the refutation of a principle variation. Why use shallow self-deepening on a move list that has already been searched full-width?

[hgm]

Ok, that makes some sense. However, this seems like too much researching near the horizon. That is one reason I suggest a depth limit of 5.

That would probably be better. But that can be tweaked later. My first focus was on getting the code correct and verified, optimalization can come later.

The self-deepening also applies to a fail-low condition, which is another matter. That would probably not have anything to do with the refutation of a principle variation. Why use shallow self-deepening on a move list that has already been searched full-width?

I am not entirely sure what you mean by 'fail-low condition'. The other case in which the hashed bound is useless is an upper bound > alpha. And this happens in the same situations as the other, but in the opponent nodes.

I still think it would be useful to do IID there: apparently the window moved down a lot, so a score that was a fail low on an earlier search could very well be a fail high now. To discover which move could do the trick a low-depth iteration can be useful and efficient. If this still fails low compared to the less-demanding window, you might give up and immediately jump to full depth, under the assumption that this will remain an all node.

Self-deepening is a bit tricky, though: a fail low means that the move in the parent fails high, so you would want it searched to depth+extraDepth, rather than just depth. But if you directly jump to depth+extraDepth, and it does fail high there, you might have spent a lot of search effort to get a depth that was better than needed. But when you directy skip to depth, and it does indeed fail low there, you have done an IID iteration in an all-node, which in general is rather useless. The latter is probably the lesser of two evils, though.

[D Sceviour]

H.G. Muller wrote,

That would probably be better. But that can be tweaked later. My first focus was on getting the code correct and verified, optimalization can come later.

Good luck. If you are correct then Stockfish look out. No more Mister Nice Guy.

[hgm]

I gave this some more thought. The point is that when the PV runs into trouble at the tips, like in your example when it loses the Queen, a 'score shock' starts propagating through the tree. Along the PV branch this propagates towards the root, and manifests itself by the hash move in the PV nodes returning a score very much different from what they had in the hash table (in either direction, depending on who has the move). But then the searching of alternatives starts in the those PV nodes, and this propagates the now-displaced window towards the leaves of the side branches. The highest-depth node of the side brach is the first to receive this 'window shock'.

Now the point is that in a stable search this whole IID loop is basically a no-op: you will get a hash hit for the node with depth=N-1, left there by the previous root iteration, when depth N is now required. So iterDepth starts and ends at N. The ID at the root will effectively turn off IID in the entire tree.

If the window-shock inspires a node to start iterating, this will basically inhibit IID in the sub-tree hanging from it, like the root inhibits it for the stable part of the tree (provided the depth strides are equal). The deepening node acts as a control center for the discovery of a new tree very different from the old one.

The question merely is: which node do you want this to be? The daughters of PV nodes used to be cut nodes, but when the PV score dropped, they see their window raised, making it doubtfull even in advance their hash move will still fail high. Starting IID there is probably the cheapest way to confirm that.

BUT...

It is not really your priority to confirm that. Because the alternative to the flunked PV move was more or less randomly picked, and searching it to the full depth, even in increasing steps, might be a waste of time if there are other moves in the PV node that are still better. Your first priority would be to figure out which of the alternative moves in the PV node is best now that the false high score of the PV hash move no longer masks the difference. So you want to find that out at low depth, before putting effort in one particular move by doing it at full depth. 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. The nodes there will be searched at slowly increasing depth, for sure, but only because the PV node first walks the entire tree at one depth, and then on a higher one, etc., and they spend the time between visits in the hash table. They will not do any deepening by themselves.

So it seems the remedy can be applied purely in the PV nodes: a node that experiences a downward score shock had better start at low depth to do some re-ordering of the remaining moves, before doing a full-depth search on them. This is then not so much based on a fail low, but on an unacceptably large score drop of the hash move. That makes the two cases very similar: an unexpected drop of the hash-move score, which might make the move fail low (in non-PV nodes) or not (in PV nodes), and in response to which you have to start iterating.