New easy move implementation

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

diff --git a/src/search.cpp b/src/search.cpp
index f374b462f8a0169be2a28399cb313975b653af56..ca1fe49c5fb700a2ad5955a0efa80c9d18b13e48 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -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

diff --git a/src/timeman.h b/src/timeman.h
index b904e1c152bd14b7b841277fe5c3d559e36d990a..551d73854fbf2763a644c73d237fbf994687f77c 100644 (file)
--- a/src/timeman.h
+++ b/src/timeman.h
@@ -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: