From 35fa4fc71f7cf7b8f7ffc8a8c22f60048be99f86 Mon Sep 17 00:00:00 2001
From: Marco Costalba <mcostalba@gmail.com>
Date: Sat, 8 Oct 2011 13:01:18 +0100
Subject: [PATCH] Rewrite early stop logic

In the "easy move" paradigm we verify if the best move has
ever changed over a good number of iterations and if the
biggest part of the searched nodes are consumed on it.
This is a kind of hacky ad indirect heuristic to deduce
if one move is much better than others.

Rewrite the early stop condition to verify directly if one
move is much better than others performing an exclusion
search.

Idea to use exclusion search for time management if form Critter.

After 12245 games at 30"+0.1
Mod vs Orig 1776 - 1775 - 8694 ELO +0 (+-3.4)

Signed-off-by: Marco Costalba <mcostalba@gmail.com>
---
 src/search.cpp | 48 ++++++++++++++++++++++++++++--------------------
 1 file changed, 28 insertions(+), 20 deletions(-)

diff --git a/src/search.cpp b/src/search.cpp
index fc5dc4ee..4304298c 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -150,7 +150,7 @@ namespace {
 
   // Easy move margin. An easy move candidate must be at least this much
   // better than the second best move.
-  const Value EasyMoveMargin = Value(0x200);
+  const Value EasyMoveMargin = Value(0x150);
 
 
   /// Namespace variables
@@ -497,13 +497,14 @@ namespace {
     int bestMoveChanges[PLY_MAX_PLUS_2];
     int depth, aspirationDelta;
     Value bestValue, alpha, beta;
-    Move bestMove, easyMove, skillBest, skillPonder;
+    Move bestMove, skillBest, skillPonder;
+    bool bestMoveNeverChanged = true;
 
     // Initialize stuff before a new search
     memset(ss, 0, 4 * sizeof(SearchStack));
     TT.new_search();
     H.clear();
-    *ponderMove = bestMove = easyMove = skillBest = skillPonder = MOVE_NONE;
+    *ponderMove = bestMove = skillBest = skillPonder = MOVE_NONE;
     depth = aspirationDelta = 0;
     bestValue = alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
     ss->currentMove = MOVE_NULL; // Hack to skip update gains
@@ -643,25 +644,16 @@ namespace {
             log << pretty_pv(pos, depth, bestValue, elapsed_search_time(), &Rml[0].pv[0]) << endl;
         }
 
-        // Init easyMove at first iteration or drop it if differs from the best move
-        if (depth == 1 && (Rml.size() == 1 || Rml[0].score > Rml[1].score + EasyMoveMargin))
-            easyMove = bestMove;
-        else if (bestMove != easyMove)
-            easyMove = MOVE_NONE;
+        // Filter out startup noise when monitoring best move stability
+        if (depth > 2 && bestMoveChanges[depth])
+            bestMoveNeverChanged = false;
 
         // Check for some early stop condition
         if (!StopRequest && Limits.useTimeManagement())
         {
-            // Easy move: Stop search early if one move seems to be much better
-            // than the others or if there is only a single legal move. Also in
-            // the latter case search to some depth anyway to get a proper score.
-            if (   depth >= 7
-                && easyMove == bestMove
-                && (   Rml.size() == 1
-                    ||(   Rml[0].nodes > (pos.nodes_searched() * 85) / 100
-                       && elapsed_search_time() > TimeMgr.available_time() / 16)
-                    ||(   Rml[0].nodes > (pos.nodes_searched() * 98) / 100
-                       && elapsed_search_time() > TimeMgr.available_time() / 32)))
+            // Stop search early if there is only a single legal move. Search to
+            // some depth anyway to get a proper score.
+            if (Rml.size() == 1 && depth >= 7)
                 StopRequest = true;
 
             // Take in account some extra time if the best move has changed
@@ -673,6 +665,23 @@ namespace {
             if (elapsed_search_time() > (TimeMgr.available_time() * 62) / 100)
                 StopRequest = true;
 
+            // Stop search early if one move seems to be much better than others
+            if (   depth >= 10
+                && !StopRequest
+                && (   bestMoveNeverChanged
+                    || elapsed_search_time() > (TimeMgr.available_time() * 40) / 100))
+            {
+                Value rBeta = bestValue - EasyMoveMargin;
+                (ss+1)->excludedMove = bestMove;
+                (ss+1)->skipNullMove = true;
+                Value v = search<NonPV>(pos, ss+1, rBeta - 1, rBeta, (depth * ONE_PLY) / 2);
+                (ss+1)->skipNullMove = false;
+                (ss+1)->excludedMove = MOVE_NONE;
+
+                if (v < rBeta)
+                    StopRequest = true;
+            }
+
             // If we are allowed to ponder do not stop the search now but keep pondering
             if (StopRequest && Limits.ponder)
             {
@@ -1027,8 +1036,7 @@ split_point_start: // At split points actual search starts from here
                    << " currmovenumber " << moveCount + MultiPVIdx << endl;
       }
 
-      // At Root and at first iteration do a PV search on all the moves to score root moves
-      isPvMove = (PvNode && moveCount <= (RootNode && depth <= ONE_PLY ? MAX_MOVES : 1));
+      isPvMove = (PvNode && moveCount <= 1);
       givesCheck = pos.move_gives_check(move, ci);
       captureOrPromotion = pos.is_capture_or_promotion(move);
 
-- 
2.39.2