Introduce DistanceFromPV

We introduce a metric for each internal node in search, called DistanceFromPV.
This distance indicated how far the current node is from the principal variation.

We then use this distance to search the nodes which are close to the PV a little
deeper (up to 4 plies deeper than the PV): this improves the quality of the search
at these nodes and bring better updates for the PV during search.

STC:
LLR: 2.96 (-2.94,2.94) {-0.25,1.25}
Total: 54936 W: 5047 L: 4850 D: 45039
Ptnml(0-2): 183, 3907, 19075, 4136, 167
https://tests.stockfishchess.org/tests/view/6037b88e7f517a561bc4a392

LTC:
LLR: 2.95 (-2.94,2.94) {0.25,1.25}
Total: 49608 W: 1880 L: 1703 D: 46025
Ptnml(0-2): 22, 1514, 21555, 1691, 22
https://tests.stockfishchess.org/tests/view/6038271b7f517a561bc4a3cb

Closes https://github.com/official-stockfish/Stockfish/pull/3369

Bench: 5037279

diff --git a/src/search.cpp b/src/search.cpp
index c33bc9143920324d229dd34ae050072d1079a963..b3bd2f0371f393767cc52a948c26cf79beddfa83 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -616,6 +616,7 @@ namespace {
     moveCount = captureCount = quietCount = ss->moveCount = 0;
     bestValue = -VALUE_INFINITE;
     maxValue = VALUE_INFINITE;
+    ss->distanceFromPv = (PvNode ? 0 : ss->distanceFromPv);
 
     // Check for the available remaining time
     if (thisThread == Threads.main())
@@ -1175,8 +1176,12 @@ moves_loop: // When in check, search starts from here
       // Step 15. Make the move
       pos.do_move(move, st, givesCheck);
 
-      // Step 16. Reduced depth search (LMR, ~200 Elo). If the move fails high it will be
-      // re-searched at full depth.
+      (ss+1)->distanceFromPv = ss->distanceFromPv + moveCount - 1;
+
+      // Step 16. Late moves reduction / extension (LMR, ~200 Elo)
+      // We use various heuristics for the sons of a node after the first son has
+      // been searched. In general we would like to reduce them, but there are many
+      // cases where we extend a son if it has good chances to be "interesting".
       if (    depth >= 3
           &&  moveCount > 1 + 2 * rootNode
           && (  !captureOrPromotion
@@ -1258,8 +1263,8 @@ moves_loop: // When in check, search starts from here
                   r++;
 
               // Decrease/increase reduction for moves with a good/bad history (~30 Elo)
-              // If we are not in check use statScore, if we are in check
-              // use sum of main history and first continuation history with an offset
+              // If we are not in check use statScore, but if we are in check we use
+              // the sum of main history and first continuation history with an offset.
               if (ss->inCheck)
                   r -= (thisThread->mainHistory[us][from_to(move)]
                      + (*contHist[0])[movedPiece][to_sq(move)] - 3833) / 16384;
@@ -1267,18 +1272,20 @@ moves_loop: // When in check, search starts from here
                   r -= ss->statScore / 14790;
           }
 
-          Depth d = std::clamp(newDepth - r, 1, newDepth);
+          // In general we want to cap the LMR depth search at newDepth. But for nodes
+          // close to the principal variation the cap is at (newDepth + 1), which will
+          // allow these nodes to be searched deeper than the pv (up to 4 plies deeper).
+          Depth d = std::clamp(newDepth - r, 1, newDepth + ((ss+1)->distanceFromPv <= 4));
 
           value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, true);
 
-          doFullDepthSearch = value > alpha && d != newDepth;
-
+          // If the son is reduced and fails high it will be re-searched at full depth
+          doFullDepthSearch = value > alpha && d < newDepth;
           didLMR = true;
       }
       else
       {
           doFullDepthSearch = !PvNode || moveCount > 1;
-
           didLMR = false;
       }
 

diff --git a/src/search.h b/src/search.h
index 3bf3e9ae605727fc9235812782c884e25d259d6c..5e51c18e043398fe44e5cee7e3125a39114e1b9d 100644 (file)
--- a/src/search.h
+++ b/src/search.h
@@ -47,6 +47,7 @@ struct Stack {
   Value staticEval;
   int statScore;
   int moveCount;
+  int distanceFromPv;
   bool inCheck;
   bool ttPv;
   bool ttHit;