Hash Depth Extension

[mcostalba]

How come, "iterate up to the TT entry depth"? IID can not produce a cutoff, and unless there is some additional deepening loop I do not see, it looks more like "jump to the TT entry depth".

The deepening loop is in the recursivity of the search.

For instance suppose you are at depth 4 and TT depth is 8 (all depths given in ply).

Now with my patch you extend of one ply, but after you call search() in the child node you will have again a TT hit (very probably) and there the conditions are met again, in that case TT depth will be 7, our depth still 4 because we have extended and so we extend again also in the child node and so on until we reach a position where TT depth is 4 and we don't extend any more.

I don't know if I've been clear. I hope so.

[QED]

How come, "iterate up to the TT entry depth"? IID can not produce a cutoff, and unless there is some additional deepening loop I do not see, it looks more like "jump to the TT entry depth".

Why "ext < OnePly"? If a move gets ext = OnePly at step 11, is the move really not allowed to get (perhaps huge) ext from HME?

Oh, there was Min, not Max. Mea culpa. Now, ext is at most OnePly. So almost nothing I have said about HME applies.

Imagine this scenario. In a game, stockfish starts to think about next move, with all the information from previous move analysis in TT. At depth 2 extension will guide it through whole principal variation. Either pv will hold, or an alternative move appears somewhere, because it stands pat with better score. In any case, TT entries for all the nodes along pv line will be overwritten by depth == 2 entries (I guess). In depth 3, alternative move from depth 2 will be probably refuted (with the help of HME), the old pv line still runs all the way with depth 2, and some other alternative move that looks good at low depth will take place.

So, HME will not waste time, but it will not protect pv from shallow moves in general (HDE will). HME stockfish will have more steady hand when its position improves with depth, but may appear to panic when its position degrades.

Still, I think it is worth a test.

[mcostalba]

Still, I think it is worth a test.

I would think so too. I am not very skilled at predicting if a patch is good or not by just looking at it....and the more I get experience in chess engines the less skilled I am

[QED]

I had time to do a 500 games match, so I tested two versions of HDE against each other, first one updates killers and history before HDExtension (the last one posted by me), second one updates after. Surprisingly, it ended (from the point of view of "before" version) ++7 +=16 +-23 =+21 ==95 =-34 -+17 -=30 --7. That means the "after" version has won, 118:91 (291 draws). Bayeselo has 90% confidence that "after" version is stronger.

I have another promising ideas in mind, so expect another patch soon, little cleaner, stronger and better tested.

[mcostalba]

I have another promising ideas in mind, so expect another patch soon, little cleaner, stronger and better tested.

Great !

In the meantime I have started testing a refined version of mine:

Code: Select all

c5c87da16a30bae2dd74d9194091d572cbdd661f
 src/search.cpp |   26 ++++++++++++++++++++------
 1 files changed, 20 insertions(+), 6 deletions(-)

diff --git a/src/search.cpp b/src/search.cpp
index a349fd6..f7d118a 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1053,7 +1053,7 @@ namespace {
     Value bestValue, value, oldAlpha;
     Value refinedValue, nullValue, futilityValueScaled; // Non-PV specific
     bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
-    bool mateThreat = false;
+    bool mateThreat = false, hashExt = false;
     int moveCount = 0;
     refinedValue = bestValue = value = -VALUE_INFINITE;
     oldAlpha = alpha;
@@ -1095,13 +1095,18 @@ namespace {
     // * Searching for a mate
     // * Printing of full PV line
 
-    if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
+    if (tte && ok_to_use_TT(tte, depth, beta, ply))
     {
-        // Refresh tte entry to avoid aging
-        TT.store(posKey, tte->value(), tte->type(), tte->depth(), ttMove);
+        if (!PvNode)
+        {
+            // Refresh tte entry to avoid aging
+            TT.store(posKey, tte->value(), tte->type(), tte->depth(), ttMove);
 
-        ss[ply].currentMove = ttMove; // Can be MOVE_NONE
-        return value_from_tt(tte->value(), ply);
+            ss[ply].currentMove = ttMove; // Can be MOVE_NONE
+            return value_from_tt(tte->value(), ply);
+        }
+        else if (tte->depth() > depth)
+            hashExt = true;
     }
 
     // Step 5. Evaluate the position statically
@@ -1243,6 +1248,15 @@ namespace {
       // Step 11. Decide the new search depth
       ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
 
+     // Hash extension. We extend the PV if we have a valid TT entry with depth bigger then
+     // current one. Idea is that we should quickly search the extra depth because TT supported.
+     if (    PvNode
+          && hashExt
+          && tte
+          && move == tte->move()
+          && ext < OnePly)
+          ext = Min(tte->depth() - depth, OnePly);
+
       // Singular extension search. We extend the TT move if its value is much better than
       // its siblings. To verify this we do a reduced search on all the other moves but the
       // ttMove, if result is lower then ttValue minus a margin then we extend ttMove.

[yolin]

QED wrote:

I have another promising ideas in mind, so expect another patch soon, little cleaner, stronger and better tested.


Great !

In the meantime I have started testing a refined version of mine ...

Any updates on these two?

[mcostalba]

QED wrote:

I have another promising ideas in mind, so expect another patch soon, little cleaner, stronger and better tested.


Great !

In the meantime I have started testing a refined version of mine ...

Any updates on these two?

Unfortunatly not good results, about +3 ELO after 1000 games so well below noise level

[QED]

QED wrote:

I have another promising ideas in mind, so expect another patch soon, little cleaner, stronger and better tested.


Great !

In the meantime I have started testing a refined version of mine ...

Any updates on these two?

I got distracted a little. I was trying to make a version that does both HDE and IID in the same iterative loop. I tried to make 100% comaptible version first and only then tweak it, but the thing was stubbornly behaving differently. So I went on a journey to the land of debugging. It was interesting, but I do not want to go there anytime soon.

My testposition was [d] where Qh4 is the move to find, but the search of stockfish is really sensitive to move ordering here, so I knew I had a bug somewhere. Only recently I have found the problem was, that the recursive IID version, at one place, was calling IID that got HDExtended immediately and failed high, which resulted in the history being updated twice with the same move. Which in turn resulted in different move ordering, and domino effect caused completely different PVs at higher depths.

So, nothing "soon", "better tested" nor "stronger" yet, I can only offer "ideas" and "cleaner" (with respect to indentation) in this patch (this time also tt.h was changed):

Code: Select all

vrato@notas:~/Prg/stockfish-171$ diff -udr src-Ch src-HdeiidCh
diff -udr src-Ch/search.cpp src-HdeiidCh/search.cpp
--- src-Ch/search.cpp   2010-04-20 00:45:49.000000000 +0200
+++ src-HdeiidCh/search.cpp     2010-05-24 23:03:24.000000000 +0200
@@ -1032,17 +1032,15 @@
     assert(ply >= 0 && ply < PLY_MAX);
     assert(threadID >= 0 && threadID < TM.active_threads());
 
-    Move movesSearched[256];
     EvalInfo ei;
     StateInfo st;
     const TTEntry* tte;
     Move ttMove, move;
-    Depth ext, newDepth;
-    Value bestValue, value, oldAlpha;
+    Depth ext, newDepth, ttDepth, oldDepth = depth;
+    Value bestValue, value, ttValue, oldAlpha;
+    ValueType ttType;
     bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
-    bool mateThreat = false;
-    int moveCount = 0;
-    bestValue = value = -VALUE_INFINITE;
+    bool mateThreat = false, ttStore = false;
 
     if (depth < OnePly)
         return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID);
@@ -1073,8 +1071,16 @@
     // * Fifty move rule detection
     // * Searching for a mate
     // * Printing of full PV line
-    tte = TT.retrieve(pos.get_key());
-    ttMove = (tte ? tte->move() : MOVE_NONE);
+    tte     = TT.retrieve(pos.get_key());
+    ttMove  = (tte ? tte->move() : MOVE_NONE);
+    ttDepth = (tte ? tte->depth() : Depth(-20));
+    ttValue = (tte ? value_from_tt(tte->value(), ply) : VALUE_NONE);
+    ttType  = (tte ? tte->type() : VALUE_TYPE_NONE);
+
+    // Refresh entry from previous generation immediately.
+    if (   tte
+        && tte->generation() != TT.get_generation())
+        TT.store(pos.get_key(), value_to_tt(ttValue, ply), ttType, ttDepth, ttMove);
 
     // Step 5. Evaluate the position statically
     // At PV nodes we do this only to update gain statistics
@@ -1090,25 +1096,34 @@
     // Step 8. Null move search with verification search (is omitted in PV nodes)
 
     // Step 9. Internal iterative deepening
-    if (   depth >= IIDDepthAtPVNodes
-        && ttMove == MOVE_NONE)
-    {
-        search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID);
-        ttMove = ss[ply].pv[ply];
-        tte = TT.retrieve(pos.get_key());
-    }
+    while (   depth >= IIDDepthAtPVNodes
+           && ttMove == MOVE_NONE)
+        depth = depth-2*OnePly;
 
     // Initialize a MovePicker object for the current position
     mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move()));
-    MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
     CheckInfo ci(pos);
 
-    // Step 10. Loop through moves
-    // Loop through all legal moves until no moves remain or a beta cutoff occurs
-    while (   alpha < beta
-           && (move = mp.get_next_move()) != MOVE_NONE
-           && !TM.thread_should_stop(threadID))
-    {
+    // Step extra. HDE/IID loop.
+    while(1)
+    { // Also, the scope for mp, movesSearched, etc.
+
+     // Check for abort.
+     if (AbortSearch || TM.thread_should_stop(threadID))
+         return bestValue;
+
+     Move movesSearched[256];
+     int moveCount = 0;
+     MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
+     alpha = oldAlpha;
+     bestValue = -VALUE_INFINITE;
+
+     // Step 10. Loop through moves
+     // Loop through all legal moves until no moves remain or a beta cutoff occurs
+     while (   alpha < beta
+            && (move = mp.get_next_move()) != MOVE_NONE
+            && !TM.thread_should_stop(threadID))
+     {
       assert(move_is_ok(move));
 
       singleEvasion = (isCheck && mp.number_of_evasions() == 1);
@@ -1123,13 +1138,11 @@
       // ttMove, if result is lower then ttValue minus a margin then we extend ttMove.
       if (   depth >= SingularExtensionDepthAtPVNodes
           && tte
-          && move == tte->move()
+          && move == ttMove
           && ext < OnePly
-          && is_lower_bound(tte->type())
-          && tte->depth() >= depth - 3 * OnePly)
+          && is_lower_bound(ttType)
+          && ttDepth >= depth - 3 * OnePly)
       {
-          Value ttValue = value_from_tt(tte->value(), ply);
-
           if (abs(ttValue) < VALUE_KNOWN_WIN)
           {
               Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move);
@@ -1194,10 +1207,10 @@
       if (value > bestValue)
       {
           bestValue = value;
+          update_pv(ss, ply);
           if (value > alpha)
           {
               alpha = value;
-              update_pv(ss, ply);
               if (value == value_mate_in(ply + 1))
                   ss[ply].mateKiller = move;
           }
@@ -1214,7 +1227,8 @@
           && TM.split(pos, ss, ply, &alpha, beta, &bestValue,
                       depth, mateThreat, &moveCount, &mp, threadID, true))
           break;
-    }
+
+    } // Move list.
 
     // Step 19. Check for mate and stalemate
     // All legal moves have been searched and if there were
@@ -1229,21 +1243,108 @@
         return bestValue;
 
     if (bestValue <= oldAlpha)
-        TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
+    { // failing low
+
+        // Hash depth extension check.
+        if (ttDepth > depth && is_lower_bound(ttType) && ttValue > oldAlpha)
+        { // Incompatible deeper TT entry.
+            depth = Min(ttDepth, depth+2*OnePly);
+            continue; // The HDE loop with higher depth.
+        } // HDE low.
 
+        // Do we want to rewrite TT entry?
+        if (    depth >  ttDepth || !is_upper_bound(ttType)
+            || (depth >= ttDepth && ttType != VALUE_TYPE_EXACT))
+        { // Prepare new entry to store.
+            ttValue = bestValue;
+            ttType = VALUE_TYPE_UPPER;
+            ttDepth = depth;
+            ttMove = MOVE_NONE;
+            ttStore = true;
+        }
+    }
     else if (bestValue >= beta)
-    {
-        TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
+    { // failing high
+
+        // Update killers before HDE check.
         move = ss[ply].pv[ply];
         if (!pos.move_is_capture_or_promotion(move))
-        {
-            update_history(pos, move, depth, movesSearched, moveCount);
             update_killers(move, ss[ply]);
+
+        // Hash depth extension check.
+        if (ttDepth > depth && is_upper_bound(ttType) && ttValue < beta)
+        { // Incompatible deeper TT entry.
+            depth = Min(ttDepth, depth+2*OnePly);
+            continue; // The HDE loop with higher depth.
+        } // HDE high.
+
+        // Update history and beta counters after HDE check.
+        // But only when we would not do IID.
+        // And let us pretend we knew it all the way.
+        if (depth >= oldDepth)
+        { // scope for d
+            Depth d = depth;
+
+            while (d >= (ttMove == MOVE_NONE ? IIDDepthAtPVNodes-2*OnePly : oldDepth))
+            {
+                TM.incrementBetaCounter(pos.side_to_move(), d, threadID);
+                if (!pos.move_is_capture_or_promotion(move))
+                    update_history(pos, move, d, movesSearched, moveCount);
+                d -= 2*OnePly;
+            }
+        }
+
+        // Do we want to rewrite TT entry?
+        if (    depth >  ttDepth || !is_lower_bound(ttType)
+            || (depth >= ttDepth && ttType != VALUE_TYPE_EXACT))
+        { // Prepare new entry to store.
+            ttValue = bestValue;
+            ttType = VALUE_TYPE_LOWER;
+            ttDepth = depth;
+            ttMove = ss[ply].pv[ply];
+            ttStore = true;
         }
-        TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
     }
     else
-        TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
+    { // exact score
+
+        // Hash depth extension check.
+        if (   (ttDepth > depth && is_lower_bound(ttType)     && ttValue >= beta)
+            || (ttDepth > depth && is_upper_bound(ttType)     && ttValue <= oldAlpha)
+            || (ttDepth > depth && ttType == VALUE_TYPE_EXACT && ttMove != ss[ply].pv[ply]))
+        { // Incompatible deeper TT entry.
+            depth = Min(ttDepth, depth+2*OnePly);
+            continue; // The HDE loop with higher depth.
+        } // HDE exact.
+
+        // Do we want to rewrite TT entry?
+        if (depth >= ttDepth || ttType != VALUE_TYPE_EXACT)
+        { // Prepare new entry to store.
+            ttValue = bestValue;
+            ttType = VALUE_TYPE_EXACT;
+            ttDepth = depth;
+            ttMove = ss[ply].pv[ply];
+            ttStore = true;
+        }
+    }
+
+    // IID?
+    if (depth < oldDepth)
+    {
+        depth = depth+2*OnePly;
+        ttMove = ss[ply].pv[ply];
+        continue; // IID loop.
+    }
+
+    // At last, store the prepared entry.
+    if (ttStore == true)
+    {
+        TT.store(pos.get_key(), value_to_tt(ttValue, ply), ttType, ttDepth, ttMove);
+        ttStore = false;
+    }
+
+    break; // Exit from HDE loop.
+   } // HDE loop.
 
     return bestValue;
   }
@@ -1300,6 +1401,11 @@
     tte = TT.retrieve(posKey);
     ttMove = (tte ? tte->move() : MOVE_NONE);
 
+    // Refresh entry from previous generation immediately.
+    if (   tte
+        && tte->generation() != TT.get_generation())
+        TT.store(posKey, tte->value(), tte->type(), tte->depth(), tte->move());
+
     if (tte && ok_to_use_TT(tte, depth, beta, ply, allowNullmove))
     {
         ss[ply].currentMove = ttMove; // Can be MOVE_NONE
@@ -1533,8 +1639,7 @@
       if (value > bestValue)
       {
           bestValue = value;
-          if (value >= beta)
-              update_pv(ss, ply);
+          update_pv(ss, ply);
 
           if (value == value_mate_in(ply + 1))
               ss[ply].mateKiller = move;
@@ -1737,11 +1842,9 @@
       if (value > bestValue)
       {
           bestValue = value;
+          update_pv(ss, ply);
           if (value > alpha)
-          {
               alpha = value;
-              update_pv(ss, ply);
-          }
        }
     }
 
@@ -3080,8 +3183,8 @@
 
   void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
 
-    moves[moveNum].ourBeta = our;
-    moves[moveNum].theirBeta = their;
+    moves[moveNum].ourBeta += our;
+    moves[moveNum].theirBeta += their;
   }
 
   void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
diff -udr src-Ch/tt.h src-HdeiidCh/tt.h
--- src-Ch/tt.h 2010-04-10 09:50:18.000000000 +0200
+++ src-HdeiidCh/tt.h   2010-05-20 22:19:06.000000000 +0200
@@ -104,6 +104,7 @@
   void insert_pv(const Position& pos, Move pv[]);
   void extract_pv(const Position& pos, Move pv[], const int PLY_MAX);
   int full() const;
+  inline uint8_t get_generation() const {return generation;}
 
 private:
   inline TTEntry* first_entry(const Key posKey) const;

In the testposition, this patch gets Qh4 on depth 15, drops it at depth 16 and gets it again on depth 19 (1024MB hash, 1 thread, zugzwang detection on). So it is weaker than my latest HDE version with recursive IID, but for the right reasons (I think for now). So I am going back to testing/tweaking phase.