New easy move implementation
authormstembera <MissingEmail@email>
Thu, 12 Mar 2015 19:49:30 +0000 (19:49 +0000)
committerJoona Kiiski <joona.kiiski@gmail.com>
Thu, 12 Mar 2015 19:49:30 +0000 (19:49 +0000)
Spend much less time in positions where one move is much better than all other alternatives.
We carry forward pv stability information from the previous search to identify such positions.
It's based on my old InstaMove idea but with two significant improvements.

1) Much better instability detection inside the search itself.
2) When it's time to make a FastMove we no longer make it instantly but still spend at least 10% of normal time verifying it.

Credit to Gull for the inspiration.
BIG thanks to Gary because this would not work without accurate PV!

20K
ELO: 8.22 +-3.0 (95%) LOS: 100.0%
Total: 20000 W: 4203 L: 3730 D: 12067

STC
LLR: 2.96 (-2.94,2.94) [-1.50,4.50]
Total: 23266 W: 4662 L: 4492 D: 14112

LTC
LLR: 2.95 (-2.94,2.94) [0.00,6.00]
Total: 12470 W: 2091 L: 1931 D: 8448

Resolves #283

src/search.cpp
src/timeman.h

index f374b46..ca1fe49 100644 (file)
@@ -90,6 +90,45 @@ namespace {
     Move best = MOVE_NONE;
   };
 
+  struct FastMove {
+    FastMove() { clear(); }
+
+    inline void clear() {
+      expectedPosKey = 0;
+      pv3[0] = pv3[1] = pv3[2] = MOVE_NONE;
+      stableCnt = 0;
+    }
+
+    void update(Position& pos) {
+      // Keep track how many times in a row the PV stays stable 3 ply deep.
+      const std::vector<Move>& RMpv = RootMoves[0].pv;
+      if (RMpv.size() >= 3)
+      {
+          if (pv3[2] == RMpv[2])
+              stableCnt++;
+          else
+              stableCnt = 0, pv3[2] = RMpv[2];
+
+          if (!expectedPosKey || pv3[0] != RMpv[0] || pv3[1] != RMpv[1])
+          {
+              pv3[0] = RMpv[0], pv3[1] = RMpv[1];
+              StateInfo st[2];
+              pos.do_move(RMpv[0], st[0], pos.gives_check(RMpv[0], CheckInfo(pos)));
+              pos.do_move(RMpv[1], st[1], pos.gives_check(RMpv[1], CheckInfo(pos)));
+              expectedPosKey = pos.key();
+              pos.undo_move(RMpv[1]);
+              pos.undo_move(RMpv[0]);
+          }
+      }
+      else
+        clear();
+    }
+
+    Key expectedPosKey;
+    Move pv3[3];
+    int stableCnt;
+  } FM;
+
   size_t PVIdx;
   TimeManager TimeMgr;
   double BestMoveChanges;
@@ -281,6 +320,10 @@ namespace {
     Depth depth;
     Value bestValue, alpha, beta, delta;
 
+    // Init fastMove if the previous search generated a candidate and we now got the predicted position.
+    const Move fastMove = (FM.expectedPosKey == pos.key()) ? FM.pv3[2] : MOVE_NONE;
+    FM.clear();
+
     std::memset(ss-2, 0, 5 * sizeof(Stack));
 
     depth = DEPTH_ZERO;
@@ -405,27 +448,43 @@ namespace {
             Signals.stop = true;
 
         // Do we have time for the next iteration? Can we stop searching now?
-        if (Limits.use_time_management() && !Signals.stop && !Signals.stopOnPonderhit)
+        if (Limits.use_time_management())
         {
-            // Take some extra time if the best move has changed
-            if (depth > 4 * ONE_PLY && multiPV == 1)
-                TimeMgr.pv_instability(BestMoveChanges);
-
-            // Stop the search if only one legal move is available or all
-            // of the available time has been used.
-            if (   RootMoves.size() == 1
-                || now() - SearchTime > TimeMgr.available_time())
+            if (!Signals.stop && !Signals.stopOnPonderhit)
             {
-                // If we are allowed to ponder do not stop the search now but
-                // keep pondering until the GUI sends "ponderhit" or "stop".
-                if (Limits.ponder)
-                    Signals.stopOnPonderhit = true;
-                else
-                    Signals.stop = true;
+                // Take some extra time if the best move has changed
+                if (depth > 4 * ONE_PLY && multiPV == 1)
+                    TimeMgr.pv_instability(BestMoveChanges);
+
+                // Stop the search if only one legal move is available or all
+                // of the available time has been used or we matched a fastMove
+                // from the previous search and just did a fast verification.
+                if (   RootMoves.size() == 1
+                    || now() - SearchTime > TimeMgr.available_time()
+                    || (   fastMove == RootMoves[0].pv[0]
+                        && BestMoveChanges < 0.03
+                        && 10 * (now() - SearchTime) > TimeMgr.available_time()))
+                {
+                    // If we are allowed to ponder do not stop the search now but
+                    // keep pondering until the GUI sends "ponderhit" or "stop".
+                    if (Limits.ponder)
+                        Signals.stopOnPonderhit = true;
+                    else
+                        Signals.stop = true;
+                }
             }
+
+            // Update fast move stats.
+            FM.update(pos);
         }
     }
 
+    // Clear any candidate fast move that wasn't completely stable for at least
+    // the 6 final search iterations. (Independent of actual depth and thus TC.)
+    // Time condition prevents consecutive fast moves.
+    if (FM.stableCnt < 6 || now() - SearchTime < TimeMgr.available_time())
+        FM.clear();
+
     // If skill level is enabled, swap best PV line with the sub-optimal one
     if (skill.enabled())
         std::swap(RootMoves[0], *std::find(RootMoves.begin(),
@@ -1012,6 +1071,10 @@ moves_loop: // When in check and at SpNode search starts from here
 
           if (value > alpha)
           {
+              // Clear fast move if unstable.
+              if (PvNode && pos.key() == FM.expectedPosKey && (move != FM.pv3[2] || moveCount > 1))
+                  FM.clear();
+
               bestMove = SpNode ? splitPoint->bestMove = move : move;
 
               if (PvNode && !RootNode) // Update pv even in fail-high case
index b904e1c..551d738 100644 (file)
@@ -27,7 +27,7 @@ class TimeManager {
 public:
   void init(const Search::LimitsType& limits, Color us, int ply);
   void pv_instability(double bestMoveChanges) { unstablePvFactor = 1 + bestMoveChanges; }
-  int available_time() const { return int(optimumSearchTime * unstablePvFactor * 0.71); }
+  int available_time() const { return int(optimumSearchTime * unstablePvFactor * 0.76); }
   int maximum_time() const { return maximumSearchTime; }
 
 private: