Replace easyMove with simple scheme
authorJoost VandeVondele <Joost.VandeVondele@gmail.com>
Fri, 3 Nov 2017 12:51:53 +0000 (13:51 +0100)
committerMarco Costalba <mcostalba@users.noreply.github.com>
Fri, 3 Nov 2017 12:51:53 +0000 (13:51 +0100)
Reduces time for a stable bestMove, giving some of the won time for the next move.

the version before the pvDraw passed both STC and LTC

passed STC:
http://tests.stockfishchess.org/tests/view/59e98d5a0ebc590ccbb896ec
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 78561 W: 13945 L: 13921 D: 50695
elo =    0.106 +-    1.445 LOS:   55.716%

passed LTC:
http://tests.stockfishchess.org/tests/view/59eb9df90ebc590ccbb897ae
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 29056 W: 3640 L: 3530 D: 21886
elo =    1.315 +-    1.982 LOS:   90.314%

This version, rebased on pvDrawPR with the obvious change, was verified again on STC:

http://tests.stockfishchess.org/tests/view/59ee104e0ebc590ccbb89899
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 19890 W: 3648 L: 3525 D: 12717
elo =    2.149 +-    2.895 LOS:   92.692%

and LTC:
http://tests.stockfishchess.org/tests/view/59f9673a0ebc590ccbb89ea0
Total             :    17966
Win               :     2273 (  12.652%)
Loss              :     2149 (  11.961%)
Draw              :    13544 (  75.387%)
Score             :   50.345%
Sensitivity       :    0.014%
2*(W-L)/(W+L)     :    5.608%

LLR  [-3.0,  1.0] :     2.95

BayesElo range    : [  -1.161,   4.876,  10.830] (DrawElo:  341.132)
LogisticElo range : [  -0.501,   2.105,   4.677]
LOS               :   94.369 %

LTC again:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 17966 W: 2273 L: 2149 D: 13544
LogisticElo range : [ -0.501, 2.105, 4.677]
LOS : 94.369 %

unchanged bench: 5234652

src/search.cpp
src/thread.h

index 6ef74bea5e1a5c7b92951a89961117b37fd60763..34a478c54d33a7dc380d9a0c8505ef949a730915 100644 (file)
@@ -96,46 +96,6 @@ namespace {
     Move best = MOVE_NONE;
   };
 
     Move best = MOVE_NONE;
   };
 
-  // EasyMoveManager structure is used to detect an 'easy move'. When the PV is stable
-  // across multiple search iterations, we can quickly return the best move.
-  struct EasyMoveManager {
-
-    void clear() {
-      stableCnt = 0;
-      expectedPosKey = 0;
-      pv[0] = pv[1] = pv[2] = MOVE_NONE;
-    }
-
-    Move get(Key key) const {
-      return expectedPosKey == key ? pv[2] : MOVE_NONE;
-    }
-
-    void update(Position& pos, const std::vector<Move>& newPv) {
-
-      assert(newPv.size() >= 3);
-
-      // Keep track of how many times in a row the 3rd ply remains stable
-      stableCnt = (newPv[2] == pv[2]) ? stableCnt + 1 : 0;
-
-      if (!std::equal(newPv.begin(), newPv.begin() + 3, pv))
-      {
-          std::copy(newPv.begin(), newPv.begin() + 3, pv);
-
-          StateInfo st[2];
-          pos.do_move(newPv[0], st[0]);
-          pos.do_move(newPv[1], st[1]);
-          expectedPosKey = pos.key();
-          pos.undo_move(newPv[1]);
-          pos.undo_move(newPv[0]);
-      }
-    }
-
-    Key expectedPosKey;
-    int stableCnt;
-    Move pv[3];
-  };
-
-  EasyMoveManager EasyMove;
   Value DrawValue[COLOR_NB];
 
   template <NodeType NT>
   Value DrawValue[COLOR_NB];
 
   template <NodeType NT>
@@ -220,6 +180,7 @@ void Search::clear() {
 
   Threads.main()->callsCnt = 0;
   Threads.main()->previousScore = VALUE_INFINITE;
 
   Threads.main()->callsCnt = 0;
   Threads.main()->previousScore = VALUE_INFINITE;
+  Threads.main()->previousTimeReduction = 1;
 }
 
 
 }
 
 
@@ -285,8 +246,7 @@ void MainThread::search() {
 
   // Check if there are threads with a better score than main thread
   Thread* bestThread = this;
 
   // Check if there are threads with a better score than main thread
   Thread* bestThread = this;
-  if (   !this->easyMovePlayed
-      &&  Options["MultiPV"] == 1
+  if (    Options["MultiPV"] == 1
       && !Limits.depth
       && !Skill(Options["Skill Level"]).enabled()
       &&  rootMoves[0].pv[0] != MOVE_NONE)
       && !Limits.depth
       && !Skill(Options["Skill Level"]).enabled()
       &&  rootMoves[0].pv[0] != MOVE_NONE)
@@ -326,8 +286,10 @@ void Thread::search() {
 
   Stack stack[MAX_PLY+7], *ss = stack+4; // To reference from (ss-4) to (ss+2)
   Value bestValue, alpha, beta, delta;
 
   Stack stack[MAX_PLY+7], *ss = stack+4; // To reference from (ss-4) to (ss+2)
   Value bestValue, alpha, beta, delta;
-  Move easyMove = MOVE_NONE;
+  Move  lastBestMove = MOVE_NONE;
+  Depth lastBestMoveDepth = DEPTH_ZERO;
   MainThread* mainThread = (this == Threads.main() ? Threads.main() : nullptr);
   MainThread* mainThread = (this == Threads.main() ? Threads.main() : nullptr);
+  double timeReduction = 1.0;
 
   std::memset(ss-4, 0, 7 * sizeof(Stack));
   for (int i = 4; i > 0; i--)
 
   std::memset(ss-4, 0, 7 * sizeof(Stack));
   for (int i = 4; i > 0; i--)
@@ -338,9 +300,7 @@ void Thread::search() {
 
   if (mainThread)
   {
 
   if (mainThread)
   {
-      easyMove = EasyMove.get(rootPos.key());
-      EasyMove.clear();
-      mainThread->easyMovePlayed = mainThread->failedLow = false;
+      mainThread->failedLow = false;
       mainThread->bestMoveChanges = 0;
   }
 
       mainThread->bestMoveChanges = 0;
   }
 
@@ -453,6 +413,11 @@ void Thread::search() {
       if (!Threads.stop)
           completedDepth = rootDepth;
 
       if (!Threads.stop)
           completedDepth = rootDepth;
 
+      if (rootMoves[0].pv[0] != lastBestMove) {
+         lastBestMove = rootMoves[0].pv[0];
+         lastBestMoveDepth = rootDepth;
+      }
+
       // Have we found a "mate in x"?
       if (   Limits.mate
           && bestValue >= VALUE_MATE_IN_MAX_PLY
       // Have we found a "mate in x"?
       if (   Limits.mate
           && bestValue >= VALUE_MATE_IN_MAX_PLY
@@ -472,8 +437,7 @@ void Thread::search() {
           if (!Threads.stop && !Threads.stopOnPonderhit)
           {
               // Stop the search if only one legal move is available, or if all
           if (!Threads.stop && !Threads.stopOnPonderhit)
           {
               // Stop the search if only one legal move is available, or if all
-              // of the available time has been used, or if we matched an easyMove
-              // from the previous search and just did a fast verification.
+              // of the available time has been used
               const int F[] = { mainThread->failedLow,
                                 bestValue - mainThread->previousScore };
               int improvingFactor = std::max(229, std::min(715, 357 + 119 * F[0] - 6 * F[1]));
               const int F[] = { mainThread->failedLow,
                                 bestValue - mainThread->previousScore };
               int improvingFactor = std::max(229, std::min(715, 357 + 119 * F[0] - 6 * F[1]));
@@ -485,14 +449,17 @@ void Thread::search() {
 
               double unstablePvFactor = 1 + mainThread->bestMoveChanges + thinkHard;
 
 
               double unstablePvFactor = 1 + mainThread->bestMoveChanges + thinkHard;
 
-              bool doEasyMove =   rootMoves[0].pv[0] == easyMove
-                               && !thinkHard
-                               && mainThread->bestMoveChanges < 0.03
-                               && Time.elapsed() > Time.optimum() * 5 / 44;
+              // if the bestMove is stable over several iterations, reduce time for this move,
+              // the longer the move has been stable, the more.
+              // Use part of the gained time from a previous stable move for the current move.
+              timeReduction = 1;
+              for (int i : {3, 4, 5})
+                  if (lastBestMoveDepth * i < completedDepth && !thinkHard)
+                     timeReduction *= 1.3;
+              unstablePvFactor *=  std::pow(mainThread->previousTimeReduction, 0.51) / timeReduction;
 
               if (   rootMoves.size() == 1
 
               if (   rootMoves.size() == 1
-                  || Time.elapsed() > Time.optimum() * unstablePvFactor * improvingFactor / 628
-                  || (mainThread->easyMovePlayed = doEasyMove, doEasyMove))
+                  || Time.elapsed() > Time.optimum() * unstablePvFactor * improvingFactor / 628)
               {
                   // If we are allowed to ponder do not stop the search now but
                   // keep pondering until the GUI sends "ponderhit" or "stop".
               {
                   // If we are allowed to ponder do not stop the search now but
                   // keep pondering until the GUI sends "ponderhit" or "stop".
@@ -502,21 +469,13 @@ void Thread::search() {
                       Threads.stop = true;
               }
           }
                       Threads.stop = true;
               }
           }
-
-          if (rootMoves[0].pv.size() >= 3)
-              EasyMove.update(rootPos, rootMoves[0].pv);
-          else
-              EasyMove.clear();
       }
   }
 
   if (!mainThread)
       return;
 
       }
   }
 
   if (!mainThread)
       return;
 
-  // Clear any candidate easy move that wasn't stable for the last search
-  // iterations; the second condition prevents consecutive fast moves.
-  if (EasyMove.stableCnt < 6 || mainThread->easyMovePlayed)
-      EasyMove.clear();
+  mainThread->previousTimeReduction = timeReduction;
 
   // If skill level is enabled, swap best PV line with the sub-optimal one
   if (skill.enabled())
 
   // If skill level is enabled, swap best PV line with the sub-optimal one
   if (skill.enabled())
index 093b9512f82626ff231a7945489e0137b3b5eab9..3e9d92446fb5b1c7960fa9b0587b9bb612ad8526 100644 (file)
@@ -82,8 +82,8 @@ struct MainThread : public Thread {
   void search() override;
   void check_time();
 
   void search() override;
   void check_time();
 
-  bool easyMovePlayed, failedLow;
-  double bestMoveChanges;
+  bool failedLow;
+  double bestMoveChanges, previousTimeReduction;
   Value previousScore;
   int callsCnt;
 };
   Value previousScore;
   int callsCnt;
 };