If LMR search fails high research at intemediate depth

Do not search immediately at full depth, but try a second
chance at lower depth. This is a feature that should scale
well because become important at high depths where we have
big reductions and also big savings in avoiding a costly
full depth search.

After 942 games at 1+0
Mod vs Orig +158 =645 -139  +7 ELO

Signed-off-by: Marco Costalba <mcostalba@gmail.com>

diff --git a/src/search.cpp b/src/search.cpp
index 96720e215ed61347231601041d8bf074c98e38a5..a76ff2ca117f394daf27deb6c306deee8e6005ad 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1309,8 +1309,8 @@ namespace {
           value = -search<PV>(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID);
       else
       {
-          // Step 14. Reduced search
-          // if the move fails high will be re-searched at full depth.
+          // Step 14. Reduced depth search
+          // If the move fails high will be re-searched at full depth.
           bool doFullDepthSearch = true;
 
           if (    depth >= 3 * OnePly
@@ -1325,6 +1325,16 @@ namespace {
                   value = -search<NonPV>(pos, ss, -(alpha+1), -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
                   doFullDepthSearch = (value > alpha);
               }
+
+              // The move failed high, but if reduction is very big we could
+              // face a false positive, retry with a less aggressive reduction,
+              // if the move fails high again then go with full depth search.
+              if (doFullDepthSearch && ss[ply].reduction > 2 * OnePly)
+              {
+                  ss[ply].reduction = OnePly;
+                  value = -search<NonPV>(pos, ss, -(alpha+1), -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
+                  doFullDepthSearch = (value > alpha);
+              }
           }
 
           // Step 15. Full depth search
@@ -1687,7 +1697,7 @@ namespace {
       pos.do_move(move, st, ci, moveIsCheck);
 
       // Step 14. Reduced search
-      // if the move fails high will be re-searched at full depth.
+      // If the move fails high will be re-searched at full depth.
       bool doFullDepthSearch = true;
 
       if (   !dangerous
@@ -1702,6 +1712,17 @@ namespace {
               value = -search<NonPV>(pos, ss, -(localAlpha+1), -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
               doFullDepthSearch = (value > localAlpha);
           }
+
+          // The move failed high, but if reduction is very big we could
+          // face a false positive, retry with a less aggressive reduction,
+          // if the move fails high again then go with full depth search.
+          if (doFullDepthSearch && ss[sp->ply].reduction > 2 * OnePly)
+          {
+              ss[sp->ply].reduction = OnePly;
+              Value localAlpha = sp->alpha;
+              value = -search<NonPV>(pos, ss, -(localAlpha+1), -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
+              doFullDepthSearch = (value > localAlpha);
+          }
       }
 
       // Step 15. Full depth search