Update stats at pv nodes
[stockfish] / src / search.cpp
index eea5298..8f074ca 100644 (file)
@@ -41,7 +41,6 @@ namespace Search {
   LimitsType Limits;
   RootMoveVector RootMoves;
   Position RootPos;
-  Time::point SearchTime;
   StateStackPtr SetupStates;
 }
 
@@ -66,30 +65,77 @@ namespace {
   // Different node types, used as template parameter
   enum NodeType { Root, PV, NonPV };
 
-  // Dynamic razoring margin based on depth
+  // Razoring and futility margin based on depth
   inline Value razor_margin(Depth d) { return Value(512 + 32 * d); }
+  inline Value futility_margin(Depth d) { return Value(200 * d); }
 
-  // Futility lookup tables (initialized at startup) and their access functions
-  int FutilityMoveCounts[2][16]; // [improving][depth]
+  // Futility and reductions lookup tables, initialized at startup
+  int FutilityMoveCounts[2][16];  // [improving][depth]
+  Depth Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber]
 
-  inline Value futility_margin(Depth d) {
-    return Value(200 * d);
+  template <bool PvNode> inline Depth reduction(bool i, Depth d, int mn) {
+    return Reductions[PvNode][i][std::min(d, 63 * ONE_PLY)][std::min(mn, 63)];
   }
 
-  // Reduction lookup tables (initialized at startup) and their access function
-  int8_t Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber]
+  // Skill struct is used to implement strength limiting
+  struct Skill {
+    Skill(int l) : level(l) {}
+    bool enabled() const { return level < 20; }
+    bool time_to_pick(Depth depth) const { return depth / ONE_PLY == 1 + level; }
+    Move best_move(size_t multiPV) { return best ? best : pick_best(multiPV); }
+    Move pick_best(size_t multiPV);
 
-  template <bool PvNode> inline Depth reduction(bool i, Depth d, int mn) {
-    return (Depth) Reductions[PvNode][i][std::min(int(d), 63)][std::min(mn, 63)];
-  }
+    int level;
+    Move best = MOVE_NONE;
+  };
+
+  // EasyMoveManager struct is used to detect a so called 'easy move'; when PV is
+  // stable across multiple search iterations we can fast 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 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.gives_check(newPv[0], CheckInfo(pos)));
+          pos.do_move(newPv[1], st[1], pos.gives_check(newPv[1], CheckInfo(pos)));
+          expectedPosKey = pos.key();
+          pos.undo_move(newPv[1]);
+          pos.undo_move(newPv[0]);
+      }
+    }
+
+    int stableCnt;
+    Key expectedPosKey;
+    Move pv[3];
+  };
 
   size_t PVIdx;
-  TimeManager TimeMgr;
+  EasyMoveManager EasyMove;
   double BestMoveChanges;
   Value DrawValue[COLOR_NB];
   HistoryStats History;
+  CounterMovesHistoryStats CounterMovesHistory;
   GainsStats Gains;
-  MovesStats Countermoves, Followupmoves;
+  MovesStats Countermoves;
 
   template <NodeType NT, bool SpNode>
   Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode);
@@ -102,26 +148,6 @@ namespace {
   Value value_from_tt(Value v, int ply);
   void update_pv(Move* pv, Move move, Move* childPv);
   void update_stats(const Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt);
-  string uci_pv(const Position& pos, Depth depth, Value alpha, Value beta);
-
-  struct Skill {
-    Skill(int l, size_t rootSize) : level(l),
-                                    candidates(l < 20 ? std::min(4, (int)rootSize) : 0),
-                                    best(MOVE_NONE) {}
-   ~Skill() {
-      if (candidates) // Swap best PV line with the sub-optimal one
-          std::swap(RootMoves[0], *std::find(RootMoves.begin(),
-                    RootMoves.end(), best ? best : pick_move()));
-    }
-
-    size_t candidates_size() const { return candidates; }
-    bool time_to_pick(Depth depth) const { return depth / ONE_PLY == 1 + level; }
-    Move pick_move();
-
-    int level;
-    size_t candidates;
-    Move best;
-  };
 
 } // namespace
 
@@ -130,25 +156,23 @@ namespace {
 
 void Search::init() {
 
-  // Init reductions array
-  for (int d = 1; d < 64; ++d)
-      for (int mc = 1; mc < 64; ++mc)
-      {
-          double    pvRed = 0.00 + log(double(d)) * log(double(mc)) / 3.00;
-          double nonPVRed = 0.33 + log(double(d)) * log(double(mc)) / 2.25;
+  const double K[][2] = {{ 0.83, 2.25 }, { 0.50, 3.00 }};
 
-          Reductions[1][1][d][mc] = int8_t(   pvRed >= 1.0 ?    pvRed + 0.5: 0);
-          Reductions[0][1][d][mc] = int8_t(nonPVRed >= 1.0 ? nonPVRed + 0.5: 0);
+  for (int pv = 0; pv <= 1; ++pv)
+      for (int imp = 0; imp <= 1; ++imp)
+          for (int d = 1; d < 64; ++d)
+              for (int mc = 1; mc < 64; ++mc)
+              {
+                  double r = K[pv][0] + log(d) * log(mc) / K[pv][1];
 
-          Reductions[1][0][d][mc] = Reductions[1][1][d][mc];
-          Reductions[0][0][d][mc] = Reductions[0][1][d][mc];
+                  if (r >= 1.5)
+                      Reductions[pv][imp][d][mc] = int(r) * ONE_PLY;
 
-          // Increase reduction when eval is not improving
-          if (Reductions[0][0][d][mc] >= 2)
-              Reductions[0][0][d][mc] += 1;
-      }
+                  // Increase reduction when eval is not improving
+                  if (!pv && !imp && Reductions[pv][imp][d][mc] >= 2 * ONE_PLY)
+                      Reductions[pv][imp][d][mc] += ONE_PLY;
+              }
 
-  // Init futility move count array
   for (int d = 0; d < 16; ++d)
   {
       FutilityMoveCounts[0][d] = int(2.4 + 0.773 * pow(d + 0.00, 1.8));
@@ -167,19 +191,19 @@ uint64_t Search::perft(Position& pos, Depth depth) {
   CheckInfo ci(pos);
   const bool leaf = (depth == 2 * ONE_PLY);
 
-  for (MoveList<LEGAL> it(pos); *it; ++it)
+  for (const auto& m : MoveList<LEGAL>(pos))
   {
       if (Root && depth <= ONE_PLY)
           cnt = 1, nodes++;
       else
       {
-          pos.do_move(*it, st, ci, pos.gives_check(*it, ci));
+          pos.do_move(m, st, pos.gives_check(m, ci));
           cnt = leaf ? MoveList<LEGAL>(pos).size() : perft<false>(pos, depth - ONE_PLY);
           nodes += cnt;
-          pos.undo_move(*it);
+          pos.undo_move(m);
       }
       if (Root)
-          sync_cout << UCI::move(*it, pos.is_chess960()) << ": " << cnt << sync_endl;
+          sync_cout << UCI::move(m, pos.is_chess960()) << ": " << cnt << sync_endl;
   }
   return nodes;
 }
@@ -193,11 +217,12 @@ template uint64_t Search::perft<true>(Position& pos, Depth depth);
 
 void Search::think() {
 
-  TimeMgr.init(Limits, RootPos.side_to_move(), RootPos.game_ply());
+  Color us = RootPos.side_to_move();
+  Time.init(Limits, us, RootPos.game_ply(), now());
 
   int contempt = Options["Contempt"] * PawnValueEg / 100; // From centipawns
-  DrawValue[ RootPos.side_to_move()] = VALUE_DRAW - Value(contempt);
-  DrawValue[~RootPos.side_to_move()] = VALUE_DRAW + Value(contempt);
+  DrawValue[ us] = VALUE_DRAW - Value(contempt);
+  DrawValue[~us] = VALUE_DRAW + Value(contempt);
 
   TB::Hits = 0;
   TB::RootInTB = false;
@@ -214,7 +239,7 @@ void Search::think() {
 
   if (RootMoves.empty())
   {
-      RootMoves.push_back(MOVE_NONE);
+      RootMoves.push_back(RootMove(MOVE_NONE));
       sync_cout << "info depth 0 score "
                 << UCI::value(RootPos.checkers() ? -VALUE_MATE : VALUE_DRAW)
                 << sync_endl;
@@ -252,17 +277,25 @@ void Search::think() {
           }
       }
 
-      for (size_t i = 0; i < Threads.size(); ++i)
-          Threads[i]->maxPly = 0;
+      for (Thread* th : Threads)
+      {
+          th->maxPly = 0;
+          th->notify_one(); // Wake up all the threads
+      }
 
       Threads.timer->run = true;
-      Threads.timer->notify_one(); // Wake up the recurring timer
+      Threads.timer->notify_one(); // Start the recurring timer
 
       id_loop(RootPos); // Let's start searching !
 
       Threads.timer->run = false;
   }
 
+  // When playing in 'nodes as time' mode, subtract the searched nodes from
+  // the available ones before to exit.
+  if (Limits.npmsec)
+      Time.availableNodes += Limits.inc[us] - RootPos.nodes_searched();
+
   // When we reach the maximum depth, we can arrive here without a raise of
   // Signals.stop. However, if we are pondering or in an infinite search,
   // the UCI protocol states that we shouldn't print the best move before the
@@ -295,6 +328,9 @@ namespace {
     Depth depth;
     Value bestValue, alpha, beta, delta;
 
+    Move easyMove = EasyMove.get(pos.key());
+    EasyMove.clear();
+
     std::memset(ss-2, 0, 5 * sizeof(Stack));
 
     depth = DEPTH_ZERO;
@@ -304,16 +340,19 @@ namespace {
 
     TT.new_search();
     History.clear();
+    CounterMovesHistory.clear();
     Gains.clear();
     Countermoves.clear();
-    Followupmoves.clear();
 
     size_t multiPV = Options["MultiPV"];
-    Skill skill(Options["Skill Level"], RootMoves.size());
+    Skill skill(Options["Skill Level"]);
 
-    // Do we have to play with skill handicap? In this case enable MultiPV search
-    // that we will use behind the scenes to retrieve a set of possible moves.
-    multiPV = std::max(multiPV, skill.candidates_size());
+    // When playing with strength handicap enable MultiPV search that we will
+    // use behind the scenes to retrieve a set of possible moves.
+    if (skill.enabled())
+        multiPV = std::max(multiPV, (size_t)4);
+
+    multiPV = std::min(multiPV, RootMoves.size());
 
     // Iterative deepening loop until requested to stop or target depth reached
     while (++depth < DEPTH_MAX && !Signals.stop && (!Limits.depth || depth <= Limits.depth))
@@ -323,11 +362,11 @@ namespace {
 
         // Save the last iteration's scores before first PV line is searched and
         // all the move scores except the (new) PV are set to -VALUE_INFINITE.
-        for (size_t i = 0; i < RootMoves.size(); ++i)
-            RootMoves[i].previousScore = RootMoves[i].score;
+        for (RootMove& rm : RootMoves)
+            rm.previousScore = rm.score;
 
         // MultiPV loop. We perform a full root search for each PV line
-        for (PVIdx = 0; PVIdx < std::min(multiPV, RootMoves.size()) && !Signals.stop; ++PVIdx)
+        for (PVIdx = 0; PVIdx < multiPV && !Signals.stop; ++PVIdx)
         {
             // Reset aspiration window starting size
             if (depth >= 5 * ONE_PLY)
@@ -367,8 +406,8 @@ namespace {
                 // the UI) before a re-search.
                 if (   multiPV == 1
                     && (bestValue <= alpha || bestValue >= beta)
-                    && Time::now() - SearchTime > 3000)
-                    sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl;
+                    && Time.elapsed() > 3000)
+                    sync_cout << UCI::pv(pos, depth, alpha, beta) << sync_endl;
 
                 // In case of failing low/high increase aspiration window and
                 // re-search, otherwise exit the loop.
@@ -398,16 +437,15 @@ namespace {
 
             if (Signals.stop)
                 sync_cout << "info nodes " << RootPos.nodes_searched()
-                          << " time " << Time::now() - SearchTime << sync_endl;
+                          << " time " << Time.elapsed() << sync_endl;
 
-            else if (   PVIdx + 1 == std::min(multiPV, RootMoves.size())
-                     || Time::now() - SearchTime > 3000)
-                sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl;
+            else if (PVIdx + 1 == multiPV || Time.elapsed() > 3000)
+                sync_cout << UCI::pv(pos, depth, alpha, beta) << sync_endl;
         }
 
-        // If skill levels are enabled and time is up, pick a sub-optimal best move
-        if (skill.candidates_size() && skill.time_to_pick(depth))
-            skill.pick_move();
+        // If skill level is enabled and time is up, pick a sub-optimal best move
+        if (skill.enabled() && skill.time_to_pick(depth))
+            skill.pick_best(multiPV);
 
         // Have we found a "mate in x"?
         if (   Limits.mate
@@ -416,26 +454,48 @@ 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
-                || Time::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)
+                    Time.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 an easyMove
+                // from the previous search and just did a fast verification.
+                if (   RootMoves.size() == 1
+                    || Time.elapsed() > Time.available()
+                    || (   RootMoves[0].pv[0] == easyMove
+                        && BestMoveChanges < 0.03
+                        && Time.elapsed() > Time.available() / 10))
+                {
+                    // 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;
+                }
             }
+
+            if (RootMoves[0].pv.size() >= 3)
+                EasyMove.update(pos, RootMoves[0].pv);
+            else
+                EasyMove.clear();
         }
     }
+
+    // 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 || Time.elapsed() < Time.available())
+        EasyMove.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(),
+                  RootMoves.end(), skill.best_move(multiPV)));
   }
 
 
@@ -477,7 +537,7 @@ namespace {
         splitPoint = ss->splitPoint;
         bestMove   = splitPoint->bestMove;
         bestValue  = splitPoint->bestValue;
-        tte = NULL;
+        tte = nullptr;
         ttHit = false;
         ttMove = excludedMove = MOVE_NONE;
         ttValue = VALUE_NONE;
@@ -528,7 +588,7 @@ namespace {
     ss->ttMove = ttMove = RootNode ? RootMoves[PVIdx].pv[0] : ttHit ? tte->move() : MOVE_NONE;
     ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
 
-    // At non-PV nodes we check for a fail high/low. We don't probe at PV nodes
+    // At non-PV nodes we check for a fail high/low. We don't prune at PV nodes
     if (  !PvNode
         && ttHit
         && tte->depth() >= depth
@@ -538,9 +598,9 @@ namespace {
     {
         ss->currentMove = ttMove; // Can be MOVE_NONE
 
-        // If ttMove is quiet, update killers, history, counter move and followup move on TT hit
-        if (ttValue >= beta && ttMove && !pos.capture_or_promotion(ttMove) && !inCheck)
-            update_stats(pos, ss, ttMove, depth, NULL, 0);
+        // If ttMove is quiet, update killers, history, counter move on TT hit
+        if (ttValue >= beta && ttMove && !pos.capture_or_promotion(ttMove))
+            update_stats(pos, ss, ttMove, depth, nullptr, 0);
 
         return ttValue;
     }
@@ -695,14 +755,14 @@ namespace {
         assert((ss-1)->currentMove != MOVE_NONE);
         assert((ss-1)->currentMove != MOVE_NULL);
 
-        MovePicker mp(pos, ttMove, History, pos.captured_piece_type());
+        MovePicker mp(pos, ttMove, History, CounterMovesHistory, pos.captured_piece_type());
         CheckInfo ci(pos);
 
         while ((move = mp.next_move<false>()) != MOVE_NONE)
             if (pos.legal(move, ci.pinned))
             {
                 ss->currentMove = move;
-                pos.do_move(move, st, ci, pos.gives_check(move, ci));
+                pos.do_move(move, st, pos.gives_check(move, ci));
                 value = -search<NonPV, false>(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode);
                 pos.undo_move(move);
                 if (value >= rbeta)
@@ -727,14 +787,9 @@ namespace {
 moves_loop: // When in check and at SpNode search starts from here
 
     Square prevMoveSq = to_sq((ss-1)->currentMove);
-    Move countermoves[] = { Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].first,
-                            Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].second };
-
-    Square prevOwnMoveSq = to_sq((ss-2)->currentMove);
-    Move followupmoves[] = { Followupmoves[pos.piece_on(prevOwnMoveSq)][prevOwnMoveSq].first,
-                             Followupmoves[pos.piece_on(prevOwnMoveSq)][prevOwnMoveSq].second };
+    Move countermove = Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq];
 
-    MovePicker mp(pos, ttMove, depth, History, countermoves, followupmoves, ss);
+    MovePicker mp(pos, ttMove, depth, History, CounterMovesHistory, countermove, ss);
     CheckInfo ci(pos);
     value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
     improving =   ss->staticEval >= (ss-2)->staticEval
@@ -773,7 +828,7 @@ moves_loop: // When in check and at SpNode search starts from here
               continue;
 
           moveCount = ++splitPoint->moveCount;
-          splitPoint->mutex.unlock();
+          splitPoint->spinlock.release();
       }
       else
           ++moveCount;
@@ -782,14 +837,14 @@ moves_loop: // When in check and at SpNode search starts from here
       {
           Signals.firstRootMove = (moveCount == 1);
 
-          if (thisThread == Threads.main() && Time::now() - SearchTime > 3000)
+          if (thisThread == Threads.main() && Time.elapsed() > 3000)
               sync_cout << "info depth " << depth / ONE_PLY
                         << " currmove " << UCI::move(move, pos.is_chess960())
                         << " currmovenumber " << moveCount + PVIdx << sync_endl;
       }
 
       if (PvNode)
-          (ss+1)->pv = NULL;
+          (ss+1)->pv = nullptr;
 
       extension = DEPTH_ZERO;
       captureOrPromotion = pos.capture_or_promotion(move);
@@ -842,7 +897,7 @@ moves_loop: // When in check and at SpNode search starts from here
               && moveCount >= FutilityMoveCounts[improving][depth])
           {
               if (SpNode)
-                  splitPoint->mutex.lock();
+                  splitPoint->spinlock.acquire();
 
               continue;
           }
@@ -861,7 +916,7 @@ moves_loop: // When in check and at SpNode search starts from here
 
                   if (SpNode)
                   {
-                      splitPoint->mutex.lock();
+                      splitPoint->spinlock.acquire();
                       if (bestValue > splitPoint->bestValue)
                           splitPoint->bestValue = bestValue;
                   }
@@ -873,14 +928,14 @@ moves_loop: // When in check and at SpNode search starts from here
           if (predictedDepth < 4 * ONE_PLY && pos.see_sign(move) < VALUE_ZERO)
           {
               if (SpNode)
-                  splitPoint->mutex.lock();
+                  splitPoint->spinlock.acquire();
 
               continue;
           }
       }
 
       // Speculative prefetch as early as possible
-      prefetch((char*)TT.first_entry(pos.key_after(move)));
+      prefetch(TT.first_entry(pos.key_after(move)));
 
       // Check for legality just before making the move
       if (!RootNode && !SpNode && !pos.legal(move, ci.pinned))
@@ -890,11 +945,9 @@ moves_loop: // When in check and at SpNode search starts from here
       }
 
       ss->currentMove = move;
-      if (!SpNode && !captureOrPromotion && quietCount < 64)
-          quietsSearched[quietCount++] = move;
 
       // Step 14. Make the move
-      pos.do_move(move, st, ci, givesCheck);
+      pos.do_move(move, st, givesCheck);
 
       // Step 15. Reduced depth search (LMR). If the move fails high it will be
       // re-searched at full depth.
@@ -907,10 +960,13 @@ moves_loop: // When in check and at SpNode search starts from here
           ss->reduction = reduction<PvNode>(improving, depth, moveCount);
 
           if (   (!PvNode && cutNode)
-              ||  History[pos.piece_on(to_sq(move))][to_sq(move)] < VALUE_ZERO)
+              ||  History[pos.piece_on(to_sq(move))][to_sq(move)] < VALUE_ZERO
+              || (  History[pos.piece_on(to_sq(move))][to_sq(move)]
+                  + CounterMovesHistory[pos.piece_on(prevMoveSq)][prevMoveSq]
+                                       [pos.piece_on(to_sq(move))][to_sq(move)] < VALUE_ZERO))
               ss->reduction += ONE_PLY;
 
-          if (move == countermoves[0] || move == countermoves[1])
+          if (move == countermove)
               ss->reduction = std::max(DEPTH_ZERO, ss->reduction - ONE_PLY);
 
           // Decrease reduction for moves that escape a capture
@@ -973,7 +1029,7 @@ moves_loop: // When in check and at SpNode search starts from here
       // Step 18. Check for new best move
       if (SpNode)
       {
-          splitPoint->mutex.lock();
+          splitPoint->spinlock.acquire();
           bestValue = splitPoint->bestValue;
           alpha = splitPoint->alpha;
       }
@@ -1012,12 +1068,20 @@ moves_loop: // When in check and at SpNode search starts from here
               rm.score = -VALUE_INFINITE;
       }
 
+      bool newBestMove = false;
       if (value > bestValue)
       {
           bestValue = SpNode ? splitPoint->bestValue = value : value;
 
           if (value > alpha)
           {
+              // If there is an easy move for this position, clear it if unstable
+              if (    PvNode
+                  &&  EasyMove.get(pos.key())
+                  && (move != EasyMove.get(pos.key()) || moveCount > 1))
+                  EasyMove.clear();
+
+              newBestMove = true;
               bestMove = SpNode ? splitPoint->bestMove = move : move;
 
               if (PvNode && !RootNode) // Update pv even in fail-high case
@@ -1037,12 +1101,17 @@ moves_loop: // When in check and at SpNode search starts from here
           }
       }
 
+      if (!SpNode && !captureOrPromotion && !newBestMove && quietCount < 64)
+          quietsSearched[quietCount++] = move;
+
       // Step 19. Check for splitting the search
       if (   !SpNode
           &&  Threads.size() >= 2
           &&  depth >= Threads.minimumSplitDepth
           &&  (   !thisThread->activeSplitPoint
-               || !thisThread->activeSplitPoint->allSlavesSearching)
+               || !thisThread->activeSplitPoint->allSlavesSearching
+               || (   Threads.size() > MAX_SLAVES_PER_SPLITPOINT
+                   && thisThread->activeSplitPoint->slavesMask.count() == MAX_SLAVES_PER_SPLITPOINT))
           &&  thisThread->splitPointsSize < MAX_SPLITPOINTS_PER_THREAD)
       {
           assert(bestValue > -VALUE_INFINITE && bestValue < beta);
@@ -1077,9 +1146,9 @@ moves_loop: // When in check and at SpNode search starts from here
         bestValue = excludedMove ? alpha
                    :     inCheck ? mated_in(ss->ply) : DrawValue[pos.side_to_move()];
 
-    // Quiet best move: update killers, history, countermoves and followupmoves
-    else if (bestValue >= beta && !pos.capture_or_promotion(bestMove) && !inCheck)
-        update_stats(pos, ss, bestMove, depth, quietsSearched, quietCount - 1);
+    // Quiet best move: update killers, history and countermoves
+    else if (bestMove != MOVE_NONE && !pos.capture_or_promotion(bestMove))
+        update_stats(pos, ss, bestMove, depth, quietsSearched, quietCount);
 
     tte->save(posKey, value_to_tt(bestValue, ss->ply),
               bestValue >= beta ? BOUND_LOWER :
@@ -1198,7 +1267,7 @@ moves_loop: // When in check and at SpNode search starts from here
     // to search the moves. Because the depth is <= 0 here, only captures,
     // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
     // be generated.
-    MovePicker mp(pos, ttMove, depth, History, to_sq((ss-1)->currentMove));
+    MovePicker mp(pos, ttMove, depth, History, CounterMovesHistory, to_sq((ss-1)->currentMove));
     CheckInfo ci(pos);
 
     // Loop through the moves until no moves remain or a beta cutoff occurs
@@ -1236,8 +1305,7 @@ moves_loop: // When in check and at SpNode search starts from here
       // Detect non-capture evasions that are candidates to be pruned
       evasionPrunable =    InCheck
                        &&  bestValue > VALUE_MATED_IN_MAX_PLY
-                       && !pos.capture(move)
-                       && !pos.can_castle(pos.side_to_move());
+                       && !pos.capture(move);
 
       // Don't search moves with negative SEE values
       if (  (!InCheck || evasionPrunable)
@@ -1246,7 +1314,7 @@ moves_loop: // When in check and at SpNode search starts from here
           continue;
 
       // Speculative prefetch as early as possible
-      prefetch((char*)TT.first_entry(pos.key_after(move)));
+      prefetch(TT.first_entry(pos.key_after(move)));
 
       // Check for legality just before making the move
       if (!pos.legal(move, ci.pinned))
@@ -1255,7 +1323,7 @@ moves_loop: // When in check and at SpNode search starts from here
       ss->currentMove = move;
 
       // Make and search the move
-      pos.do_move(move, st, ci, givesCheck);
+      pos.do_move(move, st, givesCheck);
       value = givesCheck ? -qsearch<NT,  true>(pos, ss+1, -beta, -alpha, depth - ONE_PLY)
                          : -qsearch<NT, false>(pos, ss+1, -beta, -alpha, depth - ONE_PLY);
       pos.undo_move(move);
@@ -1337,8 +1405,7 @@ moves_loop: // When in check and at SpNode search starts from here
     *pv = MOVE_NONE;
   }
 
-  // update_stats() updates killers, history, countermoves and followupmoves stats after a fail-high
-  // of a quiet move.
+  // update_stats() updates killers, history, countermove history and countermoves stats for a quiet best move.
 
   void update_stats(const Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt) {
 
@@ -1348,122 +1415,127 @@ moves_loop: // When in check and at SpNode search starts from here
         ss->killers[0] = move;
     }
 
-    // Increase history value of the cut-off move and decrease all the other
-    // played quiet moves.
     Value bonus = Value((depth / ONE_PLY) * (depth / ONE_PLY));
+
+    Square prevSq = to_sq((ss-1)->currentMove);
+    HistoryStats& cmh = CounterMovesHistory[pos.piece_on(prevSq)][prevSq];
+
     History.update(pos.moved_piece(move), to_sq(move), bonus);
-    for (int i = 0; i < quietsCnt; ++i)
+
+    if (is_ok((ss-1)->currentMove))
     {
-        Move m = quiets[i];
-        History.update(pos.moved_piece(m), to_sq(m), -bonus);
+        Countermoves.update(pos.piece_on(prevSq), prevSq, move);
+        cmh.update(pos.moved_piece(move), to_sq(move), bonus);
     }
 
-    if (is_ok((ss-1)->currentMove))
+    // Decrease all the other played quiet moves
+    for (int i = 0; i < quietsCnt; ++i)
     {
-        Square prevMoveSq = to_sq((ss-1)->currentMove);
-        Countermoves.update(pos.piece_on(prevMoveSq), prevMoveSq, move);
+        History.update(pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus);
+
+        if (is_ok((ss-1)->currentMove))
+            cmh.update(pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus);
     }
 
+    // Extra penalty for TT move in previous ply when it gets refuted
     if (is_ok((ss-2)->currentMove) && (ss-1)->currentMove == (ss-1)->ttMove)
     {
-        Square prevOwnMoveSq = to_sq((ss-2)->currentMove);
-        Followupmoves.update(pos.piece_on(prevOwnMoveSq), prevOwnMoveSq, move);
+        Square prevPrevSq = to_sq((ss-2)->currentMove);
+        HistoryStats& ttMoveCmh = CounterMovesHistory[pos.piece_on(prevPrevSq)][prevPrevSq];
+        ttMoveCmh.update(pos.piece_on(prevSq), prevSq, -bonus - 2 * depth / ONE_PLY - 1);
     }
   }
 
 
-  // When playing with a strength handicap, choose best move among the first 'candidates'
-  // RootMoves using a statistical rule dependent on 'level'. Idea by Heinz van Saanen.
+  // When playing with strength handicap, choose best move among a set of RootMoves
+  // using a statistical rule dependent on 'level'. Idea by Heinz van Saanen.
 
-  Move Skill::pick_move() {
+  Move Skill::pick_best(size_t multiPV) {
 
     // PRNG sequence should be non-deterministic, so we seed it with the time at init
-    static PRNG rng(Time::now());
+    static PRNG rng(now());
 
     // RootMoves are already sorted by score in descending order
-    int variance = std::min(RootMoves[0].score - RootMoves[candidates - 1].score, PawnValueMg);
+    int variance = std::min(RootMoves[0].score - RootMoves[multiPV - 1].score, PawnValueMg);
     int weakness = 120 - 2 * level;
     int maxScore = -VALUE_INFINITE;
-    best = MOVE_NONE;
 
     // Choose best move. For each move score we add two terms both dependent on
-    // weakness. One deterministic and bigger for weaker moves, and one random,
+    // weakness. One deterministic and bigger for weaker levels, and one random,
     // then we choose the move with the resulting highest score.
-    for (size_t i = 0; i < candidates; ++i)
+    for (size_t i = 0; i < multiPV; ++i)
     {
-        int score = RootMoves[i].score;
-
         // This is our magic formula
-        score += (  weakness * int(RootMoves[0].score - score)
-                  + variance * (rng.rand<unsigned>() % weakness)) / 128;
+        int push = (  weakness * int(RootMoves[0].score - RootMoves[i].score)
+                    + variance * (rng.rand<unsigned>() % weakness)) / 128;
 
-        if (score > maxScore)
+        if (RootMoves[i].score + push > maxScore)
         {
-            maxScore = score;
+            maxScore = RootMoves[i].score + push;
             best = RootMoves[i].pv[0];
         }
     }
     return best;
   }
 
+} // namespace
 
-  // uci_pv() formats PV information according to the UCI protocol. UCI
-  // requires that all (if any) unsearched PV lines are sent using a previous
-  // search score.
 
-  string uci_pv(const Position& pos, Depth depth, Value alpha, Value beta) {
+/// UCI::pv() formats PV information according to the UCI protocol. UCI requires
+/// that all (if any) unsearched PV lines are sent using a previous search score.
 
-    std::stringstream ss;
-    Time::point elapsed = Time::now() - SearchTime + 1;
-    size_t uciPVSize = std::min((size_t)Options["MultiPV"], RootMoves.size());
-    int selDepth = 0;
+string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) {
 
-    for (size_t i = 0; i < Threads.size(); ++i)
-        if (Threads[i]->maxPly > selDepth)
-            selDepth = Threads[i]->maxPly;
+  std::stringstream ss;
+  int elapsed = Time.elapsed() + 1;
+  size_t multiPV = std::min((size_t)Options["MultiPV"], RootMoves.size());
+  int selDepth = 0;
 
-    for (size_t i = 0; i < uciPVSize; ++i)
-    {
-        bool updated = (i <= PVIdx);
+  for (Thread* th : Threads)
+      if (th->maxPly > selDepth)
+          selDepth = th->maxPly;
 
-        if (depth == ONE_PLY && !updated)
-            continue;
+  for (size_t i = 0; i < multiPV; ++i)
+  {
+      bool updated = (i <= PVIdx);
 
-        Depth d = updated ? depth : depth - ONE_PLY;
-        Value v = updated ? RootMoves[i].score : RootMoves[i].previousScore;
+      if (depth == ONE_PLY && !updated)
+          continue;
 
-        bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY;
-        v = tb ? TB::Score : v;
+      Depth d = updated ? depth : depth - ONE_PLY;
+      Value v = updated ? RootMoves[i].score : RootMoves[i].previousScore;
 
-        if (ss.rdbuf()->in_avail()) // Not at first line
-            ss << "\n";
+      bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY;
+      v = tb ? TB::Score : v;
 
-        ss << "info depth " << d / ONE_PLY
-           << " seldepth "  << selDepth
-           << " multipv "   << i + 1
-           << " score "     << UCI::value(v);
+      if (ss.rdbuf()->in_avail()) // Not at first line
+          ss << "\n";
 
-        if (!tb && i == PVIdx)
-              ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : "");
+      ss << "info"
+         << " depth "    << d / ONE_PLY
+         << " seldepth " << selDepth
+         << " multipv "  << i + 1
+         << " score "    << UCI::value(v);
 
-        ss << " nodes "     << pos.nodes_searched()
-           << " nps "       << pos.nodes_searched() * 1000 / elapsed;
+      if (!tb && i == PVIdx)
+          ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : "");
 
-        if (elapsed > 1000) // Earlier makes little sense
-           ss << " hashfull "  << TT.hashfull();
+      ss << " nodes "    << pos.nodes_searched()
+         << " nps "      << pos.nodes_searched() * 1000 / elapsed;
 
-        ss << " tbhits "    << TB::Hits
-           << " time "      << elapsed
-           << " pv";
+      if (elapsed > 1000) // Earlier makes little sense
+          ss << " hashfull " << TT.hashfull();
 
-        for (size_t j = 0; j < RootMoves[i].pv.size(); ++j)
-            ss << " " << UCI::move(RootMoves[i].pv[j], pos.is_chess960());
-    }
+      ss << " tbhits "   << TB::Hits
+         << " time "     << elapsed
+         << " pv";
 
-    return ss.str();
+      for (Move m : RootMoves[i].pv)
+          ss << " " << UCI::move(m, pos.is_chess960());
   }
 
-} // namespace
+  return ss.str();
+}
 
 
 /// RootMove::insert_pv_in_tt() is called at the end of a search iteration, and
@@ -1473,22 +1545,22 @@ moves_loop: // When in check and at SpNode search starts from here
 void RootMove::insert_pv_in_tt(Position& pos) {
 
   StateInfo state[MAX_PLY], *st = state;
-  size_t idx = 0;
+  bool ttHit;
 
-  for ( ; idx < pv.size(); ++idx)
+  for (Move m : pv)
   {
-      bool ttHit;
-      TTEntry* tte = TT.probe(pos.key(), ttHit);
+      assert(MoveList<LEGAL>(pos).contains(m));
 
-      if (!ttHit || tte->move() != pv[idx]) // Don't overwrite correct entries
-          tte->save(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[idx], VALUE_NONE, TT.generation());
+      TTEntry* tte = TT.probe(pos.key(), ttHit);
 
-      assert(MoveList<LEGAL>(pos).contains(pv[idx]));
+      if (!ttHit || tte->move() != m) // Don't overwrite correct entries
+          tte->save(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, m, VALUE_NONE, TT.generation());
 
-      pos.do_move(pv[idx], *st++);
+      pos.do_move(m, *st++, pos.gives_check(m, CheckInfo(pos)));
   }
 
-  while (idx) pos.undo_move(pv[--idx]);
+  for (size_t i = pv.size(); i > 0; )
+      pos.undo_move(pv[--i]);
 }
 
 
@@ -1497,22 +1569,25 @@ void RootMove::insert_pv_in_tt(Position& pos) {
 /// root. We try hard to have a ponder move to return to the GUI, otherwise in case of
 /// 'ponder on' we have nothing to think on.
 
-Move RootMove::extract_ponder_from_tt(Position& pos)
+bool RootMove::extract_ponder_from_tt(Position& pos)
 {
     StateInfo st;
-    bool found;
+    bool ttHit;
 
     assert(pv.size() == 1);
 
-    pos.do_move(pv[0], st);
-    TTEntry* tte = TT.probe(pos.key(), found);
-    Move m = found ? tte->move() : MOVE_NONE;
-    if (!MoveList<LEGAL>(pos).contains(m))
-        m = MOVE_NONE;
-
+    pos.do_move(pv[0], st, pos.gives_check(pv[0], CheckInfo(pos)));
+    TTEntry* tte = TT.probe(pos.key(), ttHit);
     pos.undo_move(pv[0]);
-    pv.push_back(m);
-    return m;
+
+    if (ttHit)
+    {
+        Move m = tte->move(); // Local copy to be SMP safe
+        if (MoveList<LEGAL>(pos).contains(m))
+           return pv.push_back(m), true;
+    }
+
+    return false;
 }
 
 
@@ -1522,21 +1597,21 @@ void Thread::idle_loop() {
 
   // Pointer 'this_sp' is not null only if we are called from split(), and not
   // at the thread creation. This means we are the split point's master.
-  SplitPoint* this_sp = splitPointsSize ? activeSplitPoint : NULL;
+  SplitPoint* this_sp = activeSplitPoint;
 
-  assert(!this_sp || (this_sp->masterThread == this && searching));
+  assert(!this_sp || (this_sp->master == this && searching));
 
-  while (!exit)
+  while (!exit && !(this_sp && this_sp->slavesMask.none()))
   {
       // If this thread has been assigned work, launch a search
       while (searching)
       {
-          Threads.mutex.lock();
+          spinlock.acquire();
 
           assert(activeSplitPoint);
           SplitPoint* sp = activeSplitPoint;
 
-          Threads.mutex.unlock();
+          spinlock.release();
 
           Stack stack[MAX_PLY+4], *ss = stack+2; // To allow referencing (ss-2) and (ss+2)
           Position pos(*sp->pos, this);
@@ -1544,9 +1619,9 @@ void Thread::idle_loop() {
           std::memcpy(ss-2, sp->ss-2, 5 * sizeof(Stack));
           ss->splitPoint = sp;
 
-          sp->mutex.lock();
+          sp->spinlock.acquire();
 
-          assert(activePosition == NULL);
+          assert(activePosition == nullptr);
 
           activePosition = &pos;
 
@@ -1565,74 +1640,86 @@ void Thread::idle_loop() {
           assert(searching);
 
           searching = false;
-          activePosition = NULL;
+          activePosition = nullptr;
           sp->slavesMask.reset(idx);
           sp->allSlavesSearching = false;
           sp->nodes += pos.nodes_searched();
 
-          // Wake up the master thread so to allow it to return from the idle
-          // loop in case we are the last slave of the split point.
-          if (    this != sp->masterThread
-              &&  sp->slavesMask.none())
-          {
-              assert(!sp->masterThread->searching);
-              sp->masterThread->notify_one();
-          }
-
           // After releasing the lock we can't access any SplitPoint related data
           // in a safe way because it could have been released under our feet by
           // the sp master.
-          sp->mutex.unlock();
+          sp->spinlock.release();
 
           // Try to late join to another split point if none of its slaves has
           // already finished.
-          if (Threads.size() > 2)
-              for (size_t i = 0; i < Threads.size(); ++i)
+          SplitPoint* bestSp = NULL;
+          int minLevel = INT_MAX;
+
+          for (Thread* th : Threads)
+          {
+              const size_t size = th->splitPointsSize; // Local copy
+              sp = size ? &th->splitPoints[size - 1] : nullptr;
+
+              if (   sp
+                  && sp->allSlavesSearching
+                  && sp->slavesMask.count() < MAX_SLAVES_PER_SPLITPOINT
+                  && can_join(sp))
               {
-                  const int size = Threads[i]->splitPointsSize; // Local copy
-                  sp = size ? &Threads[i]->splitPoints[size - 1] : NULL;
+                  assert(this != th);
+                  assert(!(this_sp && this_sp->slavesMask.none()));
+                  assert(Threads.size() > 2);
+
+                  // Prefer to join to SP with few parents to reduce the probability
+                  // that a cut-off occurs above us, and hence we waste our work.
+                  int level = 0;
+                  for (SplitPoint* p = th->activeSplitPoint; p; p = p->parentSplitPoint)
+                      level++;
 
-                  if (   sp
-                      && sp->allSlavesSearching
-                      && available_to(Threads[i]))
+                  if (level < minLevel)
                   {
-                      // Recheck the conditions under lock protection
-                      Threads.mutex.lock();
-                      sp->mutex.lock();
-
-                      if (   sp->allSlavesSearching
-                          && available_to(Threads[i]))
-                      {
-                           sp->slavesMask.set(idx);
-                           activeSplitPoint = sp;
-                           searching = true;
-                      }
-
-                      sp->mutex.unlock();
-                      Threads.mutex.unlock();
-
-                      break; // Just a single attempt
+                      bestSp = sp;
+                      minLevel = level;
                   }
               }
-      }
+          }
+
+          if (bestSp)
+          {
+              sp = bestSp;
 
-      // Grab the lock to avoid races with Thread::notify_one()
-      mutex.lock();
+              // Recheck the conditions under lock protection
+              sp->spinlock.acquire();
 
-      // If we are master and all slaves have finished then exit idle_loop
-      if (this_sp && this_sp->slavesMask.none())
-      {
-          assert(!searching);
-          mutex.unlock();
-          break;
+              if (   sp->allSlavesSearching
+                  && sp->slavesMask.count() < MAX_SLAVES_PER_SPLITPOINT)
+              {
+                  spinlock.acquire();
+
+                  if (can_join(sp))
+                  {
+                      sp->slavesMask.set(idx);
+                      activeSplitPoint = sp;
+                      searching = true;
+                  }
+
+                  spinlock.release();
+              }
+
+              sp->spinlock.release();
+          }
       }
 
-      // If we are not searching, wait for a condition to be signaled instead of
-      // wasting CPU time polling for work.
-      if (!searching && !exit)
-          sleepCondition.wait(mutex);
+      // If search is finished then sleep, otherwise just yield
+      if (!Threads.main()->thinking)
+      {
+          assert(!this_sp);
 
-      mutex.unlock();
+          std::unique_lock<Mutex> lk(mutex);
+          while (!exit && !Threads.main()->thinking)
+              sleepCondition.wait(lk);
+      }
+      else
+          std::this_thread::yield(); // Wait for a new job or for our slaves to finish
   }
 }
 
@@ -1643,12 +1730,12 @@ void Thread::idle_loop() {
 
 void check_time() {
 
-  static Time::point lastInfoTime = Time::now();
-  Time::point elapsed = Time::now() - SearchTime;
+  static TimePoint lastInfoTime = now();
+  int elapsed = Time.elapsed();
 
-  if (Time::now() - lastInfoTime >= 1000)
+  if (now() - lastInfoTime >= 1000)
   {
-      lastInfoTime = Time::now();
+      lastInfoTime = now();
       dbg_print();
   }
 
@@ -1660,10 +1747,10 @@ void check_time() {
   {
       bool stillAtFirstMove =    Signals.firstRootMove
                              && !Signals.failedLowAtRoot
-                             &&  elapsed > TimeMgr.available_time() * 75 / 100;
+                             &&  elapsed > Time.available() * 75 / 100;
 
       if (   stillAtFirstMove
-          || elapsed > TimeMgr.maximum_time() - 2 * TimerThread::Resolution)
+          || elapsed > Time.maximum() - 2 * TimerThread::Resolution)
           Signals.stop = true;
   }
   else if (Limits.movetime && elapsed >= Limits.movetime)
@@ -1671,18 +1758,17 @@ void check_time() {
 
   else if (Limits.nodes)
   {
-      Threads.mutex.lock();
-
       int64_t nodes = RootPos.nodes_searched();
 
       // Loop across all split points and sum accumulated SplitPoint nodes plus
       // all the currently active positions nodes.
-      for (size_t i = 0; i < Threads.size(); ++i)
-          for (int j = 0; j < Threads[i]->splitPointsSize; ++j)
+      // FIXME: Racy...
+      for (Thread* th : Threads)
+          for (size_t i = 0; i < th->splitPointsSize; ++i)
           {
-              SplitPoint& sp = Threads[i]->splitPoints[j];
+              SplitPoint& sp = th->splitPoints[i];
 
-              sp.mutex.lock();
+              sp.spinlock.acquire();
 
               nodes += sp.nodes;
 
@@ -1690,11 +1776,9 @@ void check_time() {
                   if (sp.slavesMask.test(idx) && Threads[idx]->activePosition)
                       nodes += Threads[idx]->activePosition->nodes_searched();
 
-              sp.mutex.unlock();
+              sp.spinlock.release();
           }
 
-      Threads.mutex.unlock();
-
       if (nodes >= Limits.nodes)
           Signals.stop = true;
   }