Lazy SMP
authormbootsector <mbootsector@gmail.com>
Tue, 6 Oct 2015 06:15:17 +0000 (08:15 +0200)
committerMarco Costalba <mcostalba@gmail.com>
Tue, 20 Oct 2015 04:58:08 +0000 (06:58 +0200)
Start all threads searching on root position and
use only the shared TT table as synching scheme.

It seems this scheme scales better than YBWC for
high number of threads.

Verified for nor regression at STC 3 threads
LLR: -2.95 (-2.94,2.94) [-3.00,1.00]
Total: 40232 W: 6908 L: 7130 D: 26194

Verified for nor regression at LTC 3 threads
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 28186 W: 3908 L: 3798 D: 20480

Verified for nor regression at STC 7 threads
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 3607 W: 674 L: 526 D: 2407

Verified for nor regression at LTC 7 threads
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 4235 W: 671 L: 528 D: 3036

Tested with fixed games at LTC with 20 threads
ELO: 44.75 +-7.6 (95%) LOS: 100.0%
Total: 2069 W: 407 L: 142 D: 1520

Tested with fixed games at XLTC (120secs) with 20 threads
ELO: 28.01 +-6.7 (95%) LOS: 100.0%
Total: 2275 W: 349 L: 166 D: 1760

Original patch of mbootsector, with additional work
from Ivan Ivec (log formula), Joerg Oster (id loop
simplification) and Marco Costalba (assorted formatting
and rework).

Bench: 8116244

src/benchmark.cpp
src/movepick.cpp
src/movepick.h
src/search.cpp
src/search.h
src/thread.cpp
src/thread.h
src/timeman.cpp
src/timeman.h
src/uci.cpp

index 5c4c4e3..8f3e6ae 100644 (file)
@@ -156,9 +156,10 @@ void benchmark(const Position& current, istream& is) {
       else
       {
           Search::StateStackPtr st;
+          limits.startTime = now();
           Threads.start_thinking(pos, limits, st);
           Threads.main()->join();
-          nodes += Search::RootPos.nodes_searched();
+          nodes += Threads.nodes_searched();
       }
   }
 
index 7cf3e60..ed7c380 100644 (file)
@@ -238,8 +238,8 @@ void MovePicker::generate_next_stage() {
 /// a new pseudo legal move every time it is called, until there are no more moves
 /// left. It picks the move with the biggest value from a list of generated moves
 /// taking care not to return the ttMove if it has already been searched.
-template<>
-Move MovePicker::next_move<false>() {
+
+Move MovePicker::next_move() {
 
   Move move;
 
@@ -320,10 +320,3 @@ Move MovePicker::next_move<false>() {
       }
   }
 }
-
-
-/// Version of next_move() to use at split point nodes where the move is grabbed
-/// from the split point's shared MovePicker object. This function is not thread
-/// safe so must be lock protected by the caller.
-template<>
-Move MovePicker::next_move<true>() { return ss->splitPoint->movePicker->next_move<false>(); }
index b488313..d3bca28 100644 (file)
@@ -92,7 +92,7 @@ public:
   MovePicker(const Position&, Move, const HistoryStats&, const CounterMovesHistoryStats&, Value);
   MovePicker(const Position&, Move, Depth, const HistoryStats&, const CounterMovesHistoryStats&, Move, Search::Stack*);
 
-  template<bool SpNode> Move next_move();
+  Move next_move();
 
 private:
   template<GenType> void score();
index 4988dc8..3bcb7ef 100644 (file)
@@ -39,8 +39,6 @@ namespace Search {
 
   volatile SignalsType Signals;
   LimitsType Limits;
-  RootMoveVector RootMoves;
-  Position RootPos;
   StateStackPtr SetupStates;
 }
 
@@ -128,21 +126,17 @@ namespace {
     Move pv[3];
   };
 
-  size_t PVIdx;
   EasyMoveManager EasyMove;
   double BestMoveChanges;
   Value DrawValue[COLOR_NB];
-  HistoryStats History;
   CounterMovesHistoryStats CounterMovesHistory;
-  MovesStats Countermoves;
 
-  template <NodeType NT, bool SpNode>
+  template <NodeType NT>
   Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode);
 
   template <NodeType NT, bool InCheck>
   Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth);
 
-  void id_loop(Position& pos);
   Value value_to_tt(Value v, int ply);
   Value value_from_tt(Value v, int ply);
   void update_pv(Move* pv, Move move, Move* childPv);
@@ -185,9 +179,13 @@ void Search::init() {
 void Search::reset () {
 
   TT.clear();
-  History.clear();
   CounterMovesHistory.clear();
-  Countermoves.clear();
+
+  for (Thread* th : Threads)
+  {
+      th->History.clear();
+      th->Countermoves.clear();
+  }
 }
 
 
@@ -221,14 +219,14 @@ uint64_t Search::perft(Position& pos, Depth depth) {
 template uint64_t Search::perft<true>(Position& pos, Depth depth);
 
 
-/// Search::think() is the external interface to Stockfish's search, and is
-/// called by the main thread when the program receives the UCI 'go' command. It
-/// searches from RootPos and at the end prints the "bestmove" to output.
+/// MainThread::think() is called by the main thread when the program receives
+/// the UCI 'go' command. It searches from root position and at the end prints
+/// the "bestmove" to output.
 
-void Search::think() {
+void MainThread::think() {
 
-  Color us = RootPos.side_to_move();
-  Time.init(Limits, us, RootPos.game_ply(), now());
+  Color us = rootPos.side_to_move();
+  Time.init(Limits, us, rootPos.game_ply());
 
   int contempt = Options["Contempt"] * PawnValueEg / 100; // From centipawns
   DrawValue[ us] = VALUE_DRAW - Value(contempt);
@@ -247,21 +245,21 @@ void Search::think() {
       TB::ProbeDepth = DEPTH_ZERO;
   }
 
-  if (RootMoves.empty())
+  if (rootMoves.empty())
   {
-      RootMoves.push_back(RootMove(MOVE_NONE));
+      rootMoves.push_back(RootMove(MOVE_NONE));
       sync_cout << "info depth 0 score "
-                << UCI::value(RootPos.checkers() ? -VALUE_MATE : VALUE_DRAW)
+                << UCI::value(rootPos.checkers() ? -VALUE_MATE : VALUE_DRAW)
                 << sync_endl;
   }
   else
   {
-      if (TB::Cardinality >=  RootPos.count<ALL_PIECES>(WHITE)
-                            + RootPos.count<ALL_PIECES>(BLACK))
+      if (TB::Cardinality >=  rootPos.count<ALL_PIECES>(WHITE)
+                            + rootPos.count<ALL_PIECES>(BLACK))
       {
           // If the current root position is in the tablebases then RootMoves
           // contains only moves that preserve the draw or win.
-          TB::RootInTB = Tablebases::root_probe(RootPos, RootMoves, TB::Score);
+          TB::RootInTB = Tablebases::root_probe(rootPos, rootMoves, TB::Score);
 
           if (TB::RootInTB)
               TB::Cardinality = 0; // Do not probe tablebases during the search
@@ -269,7 +267,7 @@ void Search::think() {
           else // If DTZ tables are missing, use WDL tables as a fallback
           {
               // Filter out moves that do not preserve a draw or win
-              TB::RootInTB = Tablebases::root_probe_wdl(RootPos, RootMoves, TB::Score);
+              TB::RootInTB = Tablebases::root_probe_wdl(rootPos, rootMoves, TB::Score);
 
               // Only probe during search if winning
               if (TB::Score <= VALUE_DRAW)
@@ -278,7 +276,7 @@ void Search::think() {
 
           if (TB::RootInTB)
           {
-              TB::Hits = RootMoves.size();
+              TB::Hits = rootMoves.size();
 
               if (!TB::UseRule50)
                   TB::Score =  TB::Score > VALUE_DRAW ?  VALUE_MATE - MAX_PLY - 1
@@ -290,21 +288,35 @@ void Search::think() {
       for (Thread* th : Threads)
       {
           th->maxPly = 0;
-          th->notify_one(); // Wake up all the threads
+          th->depth = DEPTH_ZERO;
+          th->searching = true;
+          if (th != this)
+          {
+              th->rootPos = Position(rootPos, th);
+              th->rootMoves = rootMoves;
+              th->notify_one(); // Wake up the thread and start searching
+          }
       }
 
       Threads.timer->run = true;
       Threads.timer->notify_one(); // Start the recurring timer
 
-      id_loop(RootPos); // Let's start searching !
+      search(true); // Let's start searching!
 
+      // Stop the threads and the timer
+      Signals.stop = true;
       Threads.timer->run = false;
+
+      // Wait until all threads have finished
+      for (Thread* th : Threads)
+          if (th != this)
+              th->wait_while(th->searching);
   }
 
   // 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();
+      Time.availableNodes += Limits.inc[us] - Threads.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,
@@ -314,196 +326,218 @@ void Search::think() {
   if (!Signals.stop && (Limits.ponder || Limits.infinite))
   {
       Signals.stopOnPonderhit = true;
-      RootPos.this_thread()->wait_for(Signals.stop);
+      wait(Signals.stop);
   }
 
-  sync_cout << "bestmove " << UCI::move(RootMoves[0].pv[0], RootPos.is_chess960());
+  sync_cout << "bestmove " << UCI::move(rootMoves[0].pv[0], rootPos.is_chess960());
 
-  if (RootMoves[0].pv.size() > 1 || RootMoves[0].extract_ponder_from_tt(RootPos))
-      std::cout << " ponder " << UCI::move(RootMoves[0].pv[1], RootPos.is_chess960());
+  if (rootMoves[0].pv.size() > 1 || rootMoves[0].extract_ponder_from_tt(rootPos))
+      std::cout << " ponder " << UCI::move(rootMoves[0].pv[1], rootPos.is_chess960());
 
   std::cout << sync_endl;
 }
 
 
-namespace {
+// Thread::search() is the main iterative deepening loop. It calls search()
+// repeatedly with increasing depth until the allocated thinking time has been
+// consumed, user stops the search, or the maximum search depth is reached.
 
-  // id_loop() is the main iterative deepening loop. It calls search() repeatedly
-  // with increasing depth until the allocated thinking time has been consumed,
-  // user stops the search, or the maximum search depth is reached.
+void Thread::search(bool isMainThread) {
 
-  void id_loop(Position& pos) {
+  Stack* ss = stack + 2; // To allow referencing (ss-2) and (ss+2)
+  Value bestValue, alpha, beta, delta;
+  Move easyMove = MOVE_NONE;
 
-    Stack stack[MAX_PLY+4], *ss = stack+2; // To allow referencing (ss-2) and (ss+2)
-    Depth depth;
-    Value bestValue, alpha, beta, delta;
+  std::memset(ss-2, 0, 5 * sizeof(Stack));
 
-    Move easyMove = EasyMove.get(pos.key());
-    EasyMove.clear();
+  bestValue = delta = alpha = -VALUE_INFINITE;
+  beta = VALUE_INFINITE;
 
-    std::memset(ss-2, 0, 5 * sizeof(Stack));
+  if (isMainThread)
+  {
+      easyMove = EasyMove.get(rootPos.key());
+      EasyMove.clear();
+      BestMoveChanges = 0;
+      TT.new_search();
+  }
 
-    depth = DEPTH_ZERO;
-    BestMoveChanges = 0;
-    bestValue = delta = alpha = -VALUE_INFINITE;
-    beta = VALUE_INFINITE;
+  size_t multiPV = Options["MultiPV"];
+  Skill skill(Options["Skill Level"]);
 
-    TT.new_search();
+  // 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);
 
-    size_t multiPV = Options["MultiPV"];
-    Skill skill(Options["Skill Level"]);
+  multiPV = std::min(multiPV, rootMoves.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);
+  // Iterative deepening loop until requested to stop or target depth reached
+  while (++depth < DEPTH_MAX && !Signals.stop && (!Limits.depth || depth <= Limits.depth))
+  {
+      // Set up the new depth for the helper threads
+      if (!isMainThread)
+          depth = Threads.main()->depth + Depth(int(3 * log(1 + this->idx)));
 
-    multiPV = std::min(multiPV, RootMoves.size());
+      // Age out PV variability metric
+      if (isMainThread)
+          BestMoveChanges *= 0.5;
 
-    // Iterative deepening loop until requested to stop or target depth reached
-    while (++depth < DEPTH_MAX && !Signals.stop && (!Limits.depth || depth <= Limits.depth))
-    {
-        // Age out PV variability metric
-        BestMoveChanges *= 0.5;
+      // 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 (RootMove& rm : rootMoves)
+          rm.previousScore = rm.score;
 
-        // 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 (RootMove& rm : RootMoves)
-            rm.previousScore = rm.score;
+      // MultiPV loop. We perform a full root search for each PV line
+      for (PVIdx = 0; PVIdx < multiPV && !Signals.stop; ++PVIdx)
+      {
+          // Reset aspiration window starting size
+          if (depth >= 5 * ONE_PLY)
+          {
+              delta = Value(16);
+              alpha = std::max(rootMoves[PVIdx].previousScore - delta,-VALUE_INFINITE);
+              beta  = std::min(rootMoves[PVIdx].previousScore + delta, VALUE_INFINITE);
+          }
 
-        // MultiPV loop. We perform a full root search for each PV line
-        for (PVIdx = 0; PVIdx < multiPV && !Signals.stop; ++PVIdx)
-        {
-            // Reset aspiration window starting size
-            if (depth >= 5 * ONE_PLY)
-            {
-                delta = Value(16);
-                alpha = std::max(RootMoves[PVIdx].previousScore - delta,-VALUE_INFINITE);
-                beta  = std::min(RootMoves[PVIdx].previousScore + delta, VALUE_INFINITE);
-            }
+          // Start with a small aspiration window and, in the case of a fail
+          // high/low, re-search with a bigger window until we're not failing
+          // high/low anymore.
+          while (true)
+          {
+              bestValue = ::search<Root>(rootPos, ss, alpha, beta, depth, false);
+
+              // Bring the best move to the front. It is critical that sorting
+              // is done with a stable algorithm because all the values but the
+              // first and eventually the new best one are set to -VALUE_INFINITE
+              // and we want to keep the same order for all the moves except the
+              // new PV that goes to the front. Note that in case of MultiPV
+              // search the already searched PV lines are preserved.
+              std::stable_sort(rootMoves.begin() + PVIdx, rootMoves.end());
+
+              // Write PV back to transposition table in case the relevant
+              // entries have been overwritten during the search.
+              for (size_t i = 0; i <= PVIdx; ++i)
+                  rootMoves[i].insert_pv_in_tt(rootPos);
+
+              // If search has been stopped break immediately. Sorting and
+              // writing PV back to TT is safe because RootMoves is still
+              // valid, although it refers to previous iteration.
+              if (Signals.stop)
+                  break;
 
-            // Start with a small aspiration window and, in the case of a fail
-            // high/low, re-search with a bigger window until we're not failing
-            // high/low anymore.
-            while (true)
-            {
-                bestValue = search<Root, false>(pos, ss, alpha, beta, depth, false);
-
-                // Bring the best move to the front. It is critical that sorting
-                // is done with a stable algorithm because all the values but the
-                // first and eventually the new best one are set to -VALUE_INFINITE
-                // and we want to keep the same order for all the moves except the
-                // new PV that goes to the front. Note that in case of MultiPV
-                // search the already searched PV lines are preserved.
-                std::stable_sort(RootMoves.begin() + PVIdx, RootMoves.end());
-
-                // Write PV back to transposition table in case the relevant
-                // entries have been overwritten during the search.
-                for (size_t i = 0; i <= PVIdx; ++i)
-                    RootMoves[i].insert_pv_in_tt(pos);
-
-                // If search has been stopped break immediately. Sorting and
-                // writing PV back to TT is safe because RootMoves is still
-                // valid, although it refers to previous iteration.
-                if (Signals.stop)
-                    break;
-
-                // When failing high/low give some update (without cluttering
-                // the UI) before a re-search.
-                if (   multiPV == 1
-                    && (bestValue <= alpha || bestValue >= beta)
-                    && 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.
-                if (bestValue <= alpha)
-                {
-                    beta = (alpha + beta) / 2;
-                    alpha = std::max(bestValue - delta, -VALUE_INFINITE);
-
-                    Signals.failedLowAtRoot = true;
-                    Signals.stopOnPonderhit = false;
-                }
-                else if (bestValue >= beta)
-                {
-                    alpha = (alpha + beta) / 2;
-                    beta = std::min(bestValue + delta, VALUE_INFINITE);
-                }
-                else
-                    break;
-
-                delta += delta / 2;
-
-                assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
-            }
+              // When failing high/low give some update (without cluttering
+              // the UI) before a re-search.
+              if (   isMainThread
+                  && multiPV == 1
+                  && (bestValue <= alpha || bestValue >= beta)
+                  && Time.elapsed() > 3000)
+                  sync_cout << UCI::pv(rootPos, depth, alpha, beta) << sync_endl;
+
+              // In case of failing low/high increase aspiration window and
+              // re-search, otherwise exit the loop.
+              if (bestValue <= alpha)
+              {
+                  beta = (alpha + beta) / 2;
+                  alpha = std::max(bestValue - delta, -VALUE_INFINITE);
 
-            // Sort the PV lines searched so far and update the GUI
-            std::stable_sort(RootMoves.begin(), RootMoves.begin() + PVIdx + 1);
+                  if (isMainThread)
+                  {
+                      Signals.failedLowAtRoot = true;
+                      Signals.stopOnPonderhit = false;
+                  }
+              }
+              else if (bestValue >= beta)
+              {
+                  alpha = (alpha + beta) / 2;
+                  beta = std::min(bestValue + delta, VALUE_INFINITE);
+              }
+              else
+                  break;
 
-            if (Signals.stop)
-                sync_cout << "info nodes " << RootPos.nodes_searched()
-                          << " time " << Time.elapsed() << sync_endl;
+              delta += delta / 2;
 
-            else if (PVIdx + 1 == multiPV || Time.elapsed() > 3000)
-                sync_cout << UCI::pv(pos, depth, alpha, beta) << sync_endl;
-        }
+              assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
+          }
 
-        // 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);
+          // Sort the PV lines searched so far and update the GUI
+          std::stable_sort(rootMoves.begin(), rootMoves.begin() + PVIdx + 1);
 
-        // Have we found a "mate in x"?
-        if (   Limits.mate
-            && bestValue >= VALUE_MATE_IN_MAX_PLY
-            && VALUE_MATE - bestValue <= 2 * Limits.mate)
-            Signals.stop = true;
+          if (!isMainThread)
+              break;
 
-        // Do we have time for the next iteration? Can we stop searching now?
-        if (Limits.use_time_management())
-        {
-            if (!Signals.stop && !Signals.stopOnPonderhit)
-            {
-                // 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 (Signals.stop)
+              sync_cout << "info nodes " << Threads.nodes_searched()
+                        << " time " << Time.elapsed() << sync_endl;
 
-            if (RootMoves[0].pv.size() >= 3)
-                EasyMove.update(pos, RootMoves[0].pv);
-            else
-                EasyMove.clear();
-        }
-    }
+          else if (PVIdx + 1 == multiPV || Time.elapsed() > 3000)
+              sync_cout << UCI::pv(rootPos, depth, alpha, beta) << sync_endl;
+      }
 
-    // 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 (!isMainThread)
+          continue;
 
-    // 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)));
+      // 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
+          && bestValue >= VALUE_MATE_IN_MAX_PLY
+          && VALUE_MATE - bestValue <= 2 * Limits.mate)
+          Signals.stop = true;
+
+      // Do we have time for the next iteration? Can we stop searching now?
+      if (Limits.use_time_management())
+      {
+          if (!Signals.stop && !Signals.stopOnPonderhit)
+          {
+              // 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(rootPos, rootMoves[0].pv);
+          else
+              EasyMove.clear();
+      }
   }
 
+  searching = false;
+  notify_one(); // Wake up main thread if is sleeping waiting for us
+
+  if (!isMainThread)
+      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 || 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)));
+}
+
+
+namespace {
 
   // search<>() is the main search function for both PV and non-PV nodes and for
   // normal and SplitPoint nodes. When called just after a split point the search
@@ -512,7 +546,7 @@ namespace {
   // repeat all this work again. We also don't need to store anything to the hash
   // table here: This is taken care of after we return from the split point.
 
-  template <NodeType NT, bool SpNode>
+  template <NodeType NT>
   Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) {
 
     const bool RootNode = NT == Root;
@@ -525,7 +559,6 @@ namespace {
     Move pv[MAX_PLY+1], quietsSearched[64];
     StateInfo st;
     TTEntry* tte;
-    SplitPoint* splitPoint;
     Key posKey;
     Move ttMove, move, excludedMove, bestMove;
     Depth extension, newDepth, predictedDepth;
@@ -537,22 +570,6 @@ namespace {
     // Step 1. Initialize node
     Thread* thisThread = pos.this_thread();
     inCheck = pos.checkers();
-
-    if (SpNode)
-    {
-        splitPoint = ss->splitPoint;
-        bestMove   = splitPoint->bestMove;
-        bestValue  = splitPoint->bestValue;
-        tte = nullptr;
-        ttHit = false;
-        ttMove = excludedMove = MOVE_NONE;
-        ttValue = VALUE_NONE;
-
-        assert(splitPoint->bestValue > -VALUE_INFINITE && splitPoint->moveCount > 0);
-
-        goto moves_loop;
-    }
-
     moveCount = quietCount =  ss->moveCount = 0;
     bestValue = -VALUE_INFINITE;
     ss->ply = (ss-1)->ply + 1;
@@ -591,7 +608,7 @@ namespace {
     excludedMove = ss->excludedMove;
     posKey = excludedMove ? pos.exclusion_key() : pos.key();
     tte = TT.probe(posKey, ttHit);
-    ss->ttMove = ttMove = RootNode ? RootMoves[PVIdx].pv[0] : ttHit ? tte->move() : MOVE_NONE;
+    ss->ttMove = ttMove = RootNode ? thisThread->rootMoves[thisThread->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 prune at PV nodes
@@ -710,7 +727,7 @@ namespace {
         pos.do_null_move(st);
         (ss+1)->skipEarlyPruning = true;
         nullValue = depth-R < ONE_PLY ? -qsearch<NonPV, false>(pos, ss+1, -beta, -beta+1, DEPTH_ZERO)
-                                      : - search<NonPV, false>(pos, ss+1, -beta, -beta+1, depth-R, !cutNode);
+                                      : - search<NonPV>(pos, ss+1, -beta, -beta+1, depth-R, !cutNode);
         (ss+1)->skipEarlyPruning = false;
         pos.undo_null_move();
 
@@ -726,7 +743,7 @@ namespace {
             // Do verification search at high depths
             ss->skipEarlyPruning = true;
             Value v = depth-R < ONE_PLY ? qsearch<NonPV, false>(pos, ss, beta-1, beta, DEPTH_ZERO)
-                                        :  search<NonPV, false>(pos, ss, beta-1, beta, depth-R, false);
+                                        :  search<NonPV>(pos, ss, beta-1, beta, depth-R, false);
             ss->skipEarlyPruning = false;
 
             if (v >= beta)
@@ -749,15 +766,15 @@ namespace {
         assert((ss-1)->currentMove != MOVE_NONE);
         assert((ss-1)->currentMove != MOVE_NULL);
 
-        MovePicker mp(pos, ttMove, History, CounterMovesHistory, PieceValue[MG][pos.captured_piece_type()]);
+        MovePicker mp(pos, ttMove, thisThread->History, CounterMovesHistory, PieceValue[MG][pos.captured_piece_type()]);
         CheckInfo ci(pos);
 
-        while ((move = mp.next_move<false>()) != MOVE_NONE)
+        while ((move = mp.next_move()) != MOVE_NONE)
             if (pos.legal(move, ci.pinned))
             {
                 ss->currentMove = move;
                 pos.do_move(move, st, pos.gives_check(move, ci));
-                value = -search<NonPV, false>(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode);
+                value = -search<NonPV>(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode);
                 pos.undo_move(move);
                 if (value >= rbeta)
                     return value;
@@ -771,19 +788,19 @@ namespace {
     {
         Depth d = depth - 2 * ONE_PLY - (PvNode ? DEPTH_ZERO : depth / 4);
         ss->skipEarlyPruning = true;
-        search<PvNode ? PV : NonPV, false>(pos, ss, alpha, beta, d, true);
+        search<PvNode ? PV : NonPV>(pos, ss, alpha, beta, d, true);
         ss->skipEarlyPruning = false;
 
         tte = TT.probe(posKey, ttHit);
         ttMove = ttHit ? tte->move() : MOVE_NONE;
     }
 
-moves_loop: // When in check and at SpNode search starts from here
+moves_loop: // When in check search starts from here
 
     Square prevMoveSq = to_sq((ss-1)->currentMove);
-    Move countermove = Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq];
+    Move countermove = thisThread->Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq];
 
-    MovePicker mp(pos, ttMove, depth, History, CounterMovesHistory, countermove, ss);
+    MovePicker mp(pos, ttMove, depth, thisThread->History, CounterMovesHistory, countermove, ss);
     CheckInfo ci(pos);
     value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
     improving =   ss->staticEval >= (ss-2)->staticEval
@@ -791,7 +808,6 @@ moves_loop: // When in check and at SpNode search starts from here
                ||(ss-2)->staticEval == VALUE_NONE;
 
     singularExtensionNode =   !RootNode
-                           && !SpNode
                            &&  depth >= 8 * ONE_PLY
                            &&  ttMove != MOVE_NONE
                        /*  &&  ttValue != VALUE_NONE Already implicit in the next condition */
@@ -802,7 +818,7 @@ moves_loop: // When in check and at SpNode search starts from here
 
     // Step 11. Loop through moves
     // Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs
-    while ((move = mp.next_move<SpNode>()) != MOVE_NONE)
+    while ((move = mp.next_move()) != MOVE_NONE)
     {
       assert(is_ok(move));
 
@@ -812,29 +828,19 @@ moves_loop: // When in check and at SpNode search starts from here
       // At root obey the "searchmoves" option and skip moves not listed in Root
       // Move List. As a consequence any illegal move is also skipped. In MultiPV
       // mode we also skip PV moves which have been already searched.
-      if (RootNode && !std::count(RootMoves.begin() + PVIdx, RootMoves.end(), move))
+      if (RootNode && !std::count(thisThread->rootMoves.begin() + thisThread->PVIdx, thisThread->rootMoves.end(), move))
           continue;
 
-      if (SpNode)
-      {
-          // Shared counter cannot be decremented later if the move turns out to be illegal
-          if (!pos.legal(move, ci.pinned))
-              continue;
+      ss->moveCount = ++moveCount;
 
-          ss->moveCount = moveCount = ++splitPoint->moveCount;
-          splitPoint->spinlock.release();
-      }
-      else
-          ss->moveCount = ++moveCount;
-
-      if (RootNode)
+      if (RootNode && thisThread == Threads.main())
       {
           Signals.firstRootMove = (moveCount == 1);
 
-          if (thisThread == Threads.main() && Time.elapsed() > 3000)
+          if (Time.elapsed() > 3000)
               sync_cout << "info depth " << depth / ONE_PLY
                         << " currmove " << UCI::move(move, pos.is_chess960())
-                        << " currmovenumber " << moveCount + PVIdx << sync_endl;
+                        << " currmovenumber " << moveCount + thisThread->PVIdx << sync_endl;
       }
 
       if (PvNode)
@@ -864,7 +870,7 @@ moves_loop: // When in check and at SpNode search starts from here
           Value rBeta = ttValue - 2 * depth / ONE_PLY;
           ss->excludedMove = move;
           ss->skipEarlyPruning = true;
-          value = search<NonPV, false>(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode);
+          value = search<NonPV>(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode);
           ss->skipEarlyPruning = false;
           ss->excludedMove = MOVE_NONE;
 
@@ -886,12 +892,7 @@ moves_loop: // When in check and at SpNode search starts from here
           // Move count based pruning
           if (   depth < 16 * ONE_PLY
               && moveCount >= FutilityMoveCounts[improving][depth])
-          {
-              if (SpNode)
-                  splitPoint->spinlock.acquire();
-
               continue;
-          }
 
           predictedDepth = newDepth - reduction<PvNode>(improving, depth, moveCount);
 
@@ -903,32 +904,20 @@ moves_loop: // When in check and at SpNode search starts from here
               if (futilityValue <= alpha)
               {
                   bestValue = std::max(bestValue, futilityValue);
-
-                  if (SpNode)
-                  {
-                      splitPoint->spinlock.acquire();
-                      if (bestValue > splitPoint->bestValue)
-                          splitPoint->bestValue = bestValue;
-                  }
                   continue;
               }
           }
 
           // Prune moves with negative SEE at low depths
           if (predictedDepth < 4 * ONE_PLY && pos.see_sign(move) < VALUE_ZERO)
-          {
-              if (SpNode)
-                  splitPoint->spinlock.acquire();
-
               continue;
-          }
       }
 
       // Speculative prefetch as early as possible
       prefetch(TT.first_entry(pos.key_after(move)));
 
       // Check for legality just before making the move
-      if (!RootNode && !SpNode && !pos.legal(move, ci.pinned))
+      if (!RootNode && !pos.legal(move, ci.pinned))
       {
           ss->moveCount = --moveCount;
           continue;
@@ -950,12 +939,12 @@ 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
+              || (   thisThread->History[pos.piece_on(to_sq(move))][to_sq(move)] < VALUE_ZERO
                   && CounterMovesHistory[pos.piece_on(prevMoveSq)][prevMoveSq]
                                         [pos.piece_on(to_sq(move))][to_sq(move)] <= VALUE_ZERO))
               ss->reduction += ONE_PLY;
 
-          if (   History[pos.piece_on(to_sq(move))][to_sq(move)] > VALUE_ZERO
+          if (   thisThread->History[pos.piece_on(to_sq(move))][to_sq(move)] > VALUE_ZERO
               && CounterMovesHistory[pos.piece_on(prevMoveSq)][prevMoveSq]
                                     [pos.piece_on(to_sq(move))][to_sq(move)] > VALUE_ZERO)
               ss->reduction = std::max(DEPTH_ZERO, ss->reduction - ONE_PLY);
@@ -968,10 +957,8 @@ moves_loop: // When in check and at SpNode search starts from here
               ss->reduction = std::max(DEPTH_ZERO, ss->reduction - ONE_PLY);
 
           Depth d = std::max(newDepth - ss->reduction, ONE_PLY);
-          if (SpNode)
-              alpha = splitPoint->alpha;
 
-          value = -search<NonPV, false>(pos, ss+1, -(alpha+1), -alpha, d, true);
+          value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, true);
 
           doFullDepthSearch = (value > alpha && ss->reduction != DEPTH_ZERO);
           ss->reduction = DEPTH_ZERO;
@@ -981,15 +968,10 @@ moves_loop: // When in check and at SpNode search starts from here
 
       // Step 16. Full depth search, when LMR is skipped or fails high
       if (doFullDepthSearch)
-      {
-          if (SpNode)
-              alpha = splitPoint->alpha;
-
           value = newDepth <   ONE_PLY ?
                             givesCheck ? -qsearch<NonPV,  true>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO)
                                        : -qsearch<NonPV, false>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO)
-                                       : - search<NonPV, false>(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode);
-      }
+                                       : - search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode);
 
       // For PV nodes only, do a full PV search on the first move or after a fail
       // high (in the latter case search only if value < beta), otherwise let the
@@ -1002,7 +984,7 @@ moves_loop: // When in check and at SpNode search starts from here
           value = newDepth <   ONE_PLY ?
                             givesCheck ? -qsearch<PV,  true>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
                                        : -qsearch<PV, false>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
-                                       : - search<PV, false>(pos, ss+1, -beta, -alpha, newDepth, false);
+                                       : - search<PV>(pos, ss+1, -beta, -alpha, newDepth, false);
       }
 
       // Step 17. Undo move
@@ -1011,22 +993,15 @@ moves_loop: // When in check and at SpNode search starts from here
       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
 
       // Step 18. Check for new best move
-      if (SpNode)
-      {
-          splitPoint->spinlock.acquire();
-          bestValue = splitPoint->bestValue;
-          alpha = splitPoint->alpha;
-      }
-
-      // Finished searching the move. If a stop or a cutoff occurred, the return
-      // value of the search cannot be trusted, and we return immediately without
+      // Finished searching the move. If a stop occurred, the return value of
+      // the search cannot be trusted, and we return immediately without
       // updating best move, PV and TT.
-      if (Signals.stop || thisThread->cutoff_occurred())
+      if (Signals.stop)
           return VALUE_ZERO;
 
       if (RootNode)
       {
-          RootMove& rm = *std::find(RootMoves.begin(), RootMoves.end(), move);
+          RootMove& rm = *std::find(thisThread->rootMoves.begin(), thisThread->rootMoves.end(), move);
 
           // PV move or new best move ?
           if (moveCount == 1 || value > alpha)
@@ -1042,7 +1017,7 @@ moves_loop: // When in check and at SpNode search starts from here
               // We record how often the best move has been changed in each
               // iteration. This information is used for time management: When
               // the best move changes frequently, we allocate some more time.
-              if (moveCount > 1)
+              if (moveCount > 1 && thisThread == Threads.main())
                   ++BestMoveChanges;
           }
           else
@@ -1054,69 +1029,41 @@ moves_loop: // When in check and at SpNode search starts from here
 
       if (value > bestValue)
       {
-          bestValue = SpNode ? splitPoint->bestValue = value : value;
+          bestValue = value;
 
           if (value > alpha)
           {
               // If there is an easy move for this position, clear it if unstable
               if (    PvNode
+                  &&  thisThread == Threads.main()
                   &&  EasyMove.get(pos.key())
                   && (move != EasyMove.get(pos.key()) || moveCount > 1))
                   EasyMove.clear();
 
-              bestMove = SpNode ? splitPoint->bestMove = move : move;
+              bestMove = move;
 
               if (PvNode && !RootNode) // Update pv even in fail-high case
-                  update_pv(SpNode ? splitPoint->ss->pv : ss->pv, move, (ss+1)->pv);
+                  update_pv(ss->pv, move, (ss+1)->pv);
 
               if (PvNode && value < beta) // Update alpha! Always alpha < beta
-                  alpha = SpNode ? splitPoint->alpha = value : value;
+                  alpha = value;
               else
               {
                   assert(value >= beta); // Fail high
-
-                  if (SpNode)
-                      splitPoint->cutoff = true;
-
                   break;
               }
           }
       }
 
-      if (!SpNode && !captureOrPromotion && move != bestMove && quietCount < 64)
+      if (!captureOrPromotion && move != bestMove && 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
-               || (   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);
-
-          thisThread->split(pos, ss, alpha, beta, &bestValue, &bestMove,
-                            depth, moveCount, &mp, NT, cutNode);
-
-          if (Signals.stop || thisThread->cutoff_occurred())
-              return VALUE_ZERO;
-
-          if (bestValue >= beta)
-              break;
-      }
     }
 
-    if (SpNode)
-        return bestValue;
-
-    // Following condition would detect a stop or a cutoff set only after move
-    // loop has been completed. But in this case bestValue is valid because we
-    // have fully searched our subtree, and we can anyhow save the result in TT.
+    // Following condition would detect a stop only after move loop has been
+    // completed. But in this case bestValue is valid because we have fully
+    // searched our subtree, and we can anyhow save the result in TT.
     /*
-       if (Signals.stop || thisThread->cutoff_occurred())
+       if (Signals.stop)
         return VALUE_DRAW;
     */
 
@@ -1262,11 +1209,11 @@ 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, CounterMovesHistory, to_sq((ss-1)->currentMove));
+    MovePicker mp(pos, ttMove, depth, pos.this_thread()->History, CounterMovesHistory, to_sq((ss-1)->currentMove));
     CheckInfo ci(pos);
 
     // Loop through the moves until no moves remain or a beta cutoff occurs
-    while ((move = mp.next_move<false>()) != MOVE_NONE)
+    while ((move = mp.next_move()) != MOVE_NONE)
     {
       assert(is_ok(move));
 
@@ -1417,19 +1364,20 @@ moves_loop: // When in check and at SpNode search starts from here
 
     Square prevSq = to_sq((ss-1)->currentMove);
     HistoryStats& cmh = CounterMovesHistory[pos.piece_on(prevSq)][prevSq];
+    Thread* thisThread = pos.this_thread();
 
-    History.updateH(pos.moved_piece(move), to_sq(move), bonus);
+    thisThread->History.updateH(pos.moved_piece(move), to_sq(move), bonus);
 
     if (is_ok((ss-1)->currentMove))
     {
-        Countermoves.update(pos.piece_on(prevSq), prevSq, move);
+        thisThread->Countermoves.update(pos.piece_on(prevSq), prevSq, move);
         cmh.updateCMH(pos.moved_piece(move), to_sq(move), bonus);
     }
 
     // Decrease all the other played quiet moves
     for (int i = 0; i < quietsCnt; ++i)
     {
-        History.updateH(pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus);
+        thisThread->History.updateH(pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus);
 
         if (is_ok((ss-1)->currentMove))
             cmh.updateCMH(pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus);
@@ -1451,10 +1399,11 @@ moves_loop: // When in check and at SpNode search starts from here
   Move Skill::pick_best(size_t multiPV) {
 
     // PRNG sequence should be non-deterministic, so we seed it with the time at init
+    const Search::RootMoveVector& rootMoves = Threads.main()->rootMoves;
     static PRNG rng(now());
 
     // RootMoves are already sorted by score in descending order
-    int variance = std::min(RootMoves[0].score - RootMoves[multiPV - 1].score, PawnValueMg);
+    int variance = std::min(rootMoves[0].score - rootMoves[multiPV - 1].score, PawnValueMg);
     int weakness = 120 - 2 * level;
     int maxScore = -VALUE_INFINITE;
 
@@ -1464,13 +1413,13 @@ moves_loop: // When in check and at SpNode search starts from here
     for (size_t i = 0; i < multiPV; ++i)
     {
         // This is our magic formula
-        int push = (  weakness * int(RootMoves[0].score - RootMoves[i].score)
+        int push = (  weakness * int(rootMoves[0].score - rootMoves[i].score)
                     + variance * (rng.rand<unsigned>() % weakness)) / 128;
 
-        if (RootMoves[i].score + push > maxScore)
+        if (rootMoves[i].score + push > maxScore)
         {
-            maxScore = RootMoves[i].score + push;
-            best = RootMoves[i].pv[0];
+            maxScore = rootMoves[i].score + push;
+            best = rootMoves[i].pv[0];
         }
     }
     return best;
@@ -1486,12 +1435,10 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) {
 
   std::stringstream ss;
   int elapsed = Time.elapsed() + 1;
-  size_t multiPV = std::min((size_t)Options["MultiPV"], RootMoves.size());
-  int selDepth = 0;
-
-  for (Thread* th : Threads)
-      if (th->maxPly > selDepth)
-          selDepth = th->maxPly;
+  const Search::RootMoveVector& rootMoves = pos.this_thread()->rootMoves;
+  size_t PVIdx = pos.this_thread()->PVIdx;
+  size_t multiPV = std::min((size_t)Options["MultiPV"], rootMoves.size());
+  uint64_t nodes_searched = Threads.nodes_searched();
 
   for (size_t i = 0; i < multiPV; ++i)
   {
@@ -1501,7 +1448,7 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) {
           continue;
 
       Depth d = updated ? depth : depth - ONE_PLY;
-      Value v = updated ? RootMoves[i].score : RootMoves[i].previousScore;
+      Value v = updated ? rootMoves[i].score : rootMoves[i].previousScore;
 
       bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY;
       v = tb ? TB::Score : v;
@@ -1511,15 +1458,15 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) {
 
       ss << "info"
          << " depth "    << d / ONE_PLY
-         << " seldepth " << selDepth
+         << " seldepth " << pos.this_thread()->maxPly
          << " multipv "  << i + 1
          << " score "    << UCI::value(v);
 
       if (!tb && i == PVIdx)
           ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : "");
 
-      ss << " nodes "    << pos.nodes_searched()
-         << " nps "      << pos.nodes_searched() * 1000 / elapsed;
+      ss << " nodes "    << nodes_searched
+         << " nps "      << nodes_searched * 1000 / elapsed;
 
       if (elapsed > 1000) // Earlier makes little sense
           ss << " hashfull " << TT.hashfull();
@@ -1528,7 +1475,7 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) {
          << " time "     << elapsed
          << " pv";
 
-      for (Move m : RootMoves[i].pv)
+      for (Move m : rootMoves[i].pv)
           ss << " " << UCI::move(m, pos.is_chess960());
   }
 
@@ -1589,144 +1536,6 @@ bool RootMove::extract_ponder_from_tt(Position& pos)
 }
 
 
-/// Thread::idle_loop() is where the thread is parked when it has no work to do
-
-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 = activeSplitPoint;
-
-  assert(!this_sp || (this_sp->master == this && searching));
-
-  while (!exit && !(this_sp && this_sp->slavesMask.none()))
-  {
-      // If this thread has been assigned work, launch a search
-      while (searching)
-      {
-          spinlock.acquire();
-
-          assert(activeSplitPoint);
-          SplitPoint* sp = activeSplitPoint;
-
-          spinlock.release();
-
-          Stack stack[MAX_PLY+4], *ss = stack+2; // To allow referencing (ss-2) and (ss+2)
-          Position pos(*sp->pos, this);
-
-          std::memcpy(ss-2, sp->ss-2, 5 * sizeof(Stack));
-          ss->splitPoint = sp;
-
-          sp->spinlock.acquire();
-
-          assert(activePosition == nullptr);
-
-          activePosition = &pos;
-
-          if (sp->nodeType == NonPV)
-              search<NonPV, true>(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode);
-
-          else if (sp->nodeType == PV)
-              search<PV, true>(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode);
-
-          else if (sp->nodeType == Root)
-              search<Root, true>(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode);
-
-          else
-              assert(false);
-
-          assert(searching);
-
-          spinlock.acquire();
-
-          searching = false;
-          activePosition = nullptr;
-
-          spinlock.release();
-
-          sp->slavesMask.reset(idx);
-          sp->allSlavesSearching = false;
-          sp->nodes += pos.nodes_searched();
-
-          // 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->spinlock.release();
-
-          // Try to late join to another split point if none of its slaves has
-          // already finished.
-          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))
-              {
-                  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 (level < minLevel)
-                  {
-                      bestSp = sp;
-                      minLevel = level;
-                  }
-              }
-          }
-
-          if (bestSp)
-          {
-              sp = bestSp;
-
-              // Recheck the conditions under lock protection
-              sp->spinlock.acquire();
-
-              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 search is finished then sleep, otherwise just yield
-      if (!Threads.main()->thinking)
-      {
-          assert(!this_sp);
-
-          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
-  }
-}
-
-
 /// check_time() is called by the timer thread when the timer triggers. It is
 /// used to print debug info and, more importantly, to detect when we are out of
 /// available time and thus stop the search.
@@ -1759,30 +1568,6 @@ void check_time() {
   else if (Limits.movetime && elapsed >= Limits.movetime)
       Signals.stop = true;
 
-  else if (Limits.nodes)
-  {
-      int64_t nodes = RootPos.nodes_searched();
-
-      // Loop across all split points and sum accumulated SplitPoint nodes plus
-      // all the currently active positions nodes.
-      // FIXME: Racy...
-      for (Thread* th : Threads)
-          for (size_t i = 0; i < th->splitPointsSize; ++i)
-          {
-              SplitPoint& sp = th->splitPoints[i];
-
-              sp.spinlock.acquire();
-
-              nodes += sp.nodes;
-
-              for (size_t idx = 0; idx < Threads.size(); ++idx)
-                  if (sp.slavesMask.test(idx) && Threads[idx]->activePosition)
-                      nodes += Threads[idx]->activePosition->nodes_searched();
-
-              sp.spinlock.release();
-          }
-
-      if (nodes >= Limits.nodes)
+  else if (Limits.nodes && Threads.nodes_searched() >= Limits.nodes)
           Signals.stop = true;
-  }
 }
index 5ba95fe..c7abb9d 100644 (file)
@@ -88,6 +88,7 @@ struct LimitsType {
   std::vector<Move> searchmoves;
   int time[COLOR_NB], inc[COLOR_NB], npmsec, movestogo, depth, movetime, mate, infinite, ponder;
   int64_t nodes;
+  TimePoint startTime;
 };
 
 /// The SignalsType struct stores volatile flags updated during the search
@@ -101,12 +102,9 @@ typedef std::unique_ptr<std::stack<StateInfo>> StateStackPtr;
 
 extern volatile SignalsType Signals;
 extern LimitsType Limits;
-extern RootMoveVector RootMoves;
-extern Position RootPos;
 extern StateStackPtr SetupStates;
 
 void init();
-void think();
 void reset();
 template<bool Root> uint64_t perft(Position& pos, Depth depth);
 
index cdb0d54..88b4592 100644 (file)
@@ -66,15 +66,24 @@ void ThreadBase::notify_one() {
 }
 
 
-// ThreadBase::wait_for() set the thread to sleep until 'condition' turns true
+// ThreadBase::wait() set the thread to sleep until 'condition' turns true
 
-void ThreadBase::wait_for(volatile const bool& condition) {
+void ThreadBase::wait(volatile const bool& condition) {
 
   std::unique_lock<Mutex> lk(mutex);
   sleepCondition.wait(lk, [&]{ return condition; });
 }
 
 
+// ThreadBase::wait_while() set the thread to sleep until 'condition' turns false
+
+void ThreadBase::wait_while(volatile const bool& condition) {
+
+  std::unique_lock<Mutex> lk(mutex);
+  sleepCondition.wait(lk, [&]{ return !condition; });
+}
+
+
 // Thread c'tor makes some init but does not launch any execution thread that
 // will be started only when c'tor returns.
 
@@ -82,159 +91,45 @@ Thread::Thread() /* : splitPoints() */ { // Initialization of non POD broken in
 
   searching = false;
   maxPly = 0;
-  splitPointsSize = 0;
-  activeSplitPoint = nullptr;
-  activePosition = nullptr;
   idx = Threads.size(); // Starts from 0
 }
 
 
-// Thread::cutoff_occurred() checks whether a beta cutoff has occurred in the
-// current active split point, or in some ancestor of the split point.
-
-bool Thread::cutoff_occurred() const {
-
-  for (SplitPoint* sp = activeSplitPoint; sp; sp = sp->parentSplitPoint)
-      if (sp->cutoff)
-          return true;
-
-  return false;
-}
-
-
-// Thread::can_join() checks whether the thread is available to join the split
-// point 'sp'. An obvious requirement is that thread must be idle. With more than
-// two threads, this is not sufficient: If the thread is the master of some split
-// point, it is only available as a slave for the split points below his active
-// one (the "helpful master" concept in YBWC terminology).
-
-bool Thread::can_join(const SplitPoint* sp) const {
-
-  if (searching)
-      return false;
-
-  // Make a local copy to be sure it doesn't become zero under our feet while
-  // testing next condition and so leading to an out of bounds access.
-  const size_t size = splitPointsSize;
-
-  // No split points means that the thread is available as a slave for any
-  // other thread otherwise apply the "helpful master" concept if possible.
-  return !size || splitPoints[size - 1].slavesMask.test(sp->master->idx);
-}
+// TimerThread::idle_loop() is where the timer thread waits Resolution milliseconds
+// and then calls check_time(). When not searching, thread sleeps until it's woken up.
 
+void TimerThread::idle_loop() {
 
-// Thread::split() does the actual work of distributing the work at a node between
-// several available threads. If it does not succeed in splitting the node
-// (because no idle threads are available), the function immediately returns.
-// If splitting is possible, a SplitPoint object is initialized with all the
-// data that must be copied to the helper threads and then helper threads are
-// informed that they have been assigned work. This will cause them to instantly
-// leave their idle loops and call search(). When all threads have returned from
-// search() then split() returns.
-
-void Thread::split(Position& pos, Stack* ss, Value alpha, Value beta, Value* bestValue,
-                   Move* bestMove, Depth depth, int moveCount,
-                   MovePicker* movePicker, int nodeType, bool cutNode) {
-
-  assert(searching);
-  assert(-VALUE_INFINITE < *bestValue && *bestValue <= alpha && alpha < beta && beta <= VALUE_INFINITE);
-  assert(depth >= Threads.minimumSplitDepth);
-  assert(splitPointsSize < MAX_SPLITPOINTS_PER_THREAD);
-
-  // Pick and init the next available split point
-  SplitPoint& sp = splitPoints[splitPointsSize];
-
-  sp.spinlock.acquire(); // No contention here until we don't increment splitPointsSize
-
-  sp.master = this;
-  sp.parentSplitPoint = activeSplitPoint;
-  sp.slavesMask = 0, sp.slavesMask.set(idx);
-  sp.depth = depth;
-  sp.bestValue = *bestValue;
-  sp.bestMove = *bestMove;
-  sp.alpha = alpha;
-  sp.beta = beta;
-  sp.nodeType = nodeType;
-  sp.cutNode = cutNode;
-  sp.movePicker = movePicker;
-  sp.moveCount = moveCount;
-  sp.pos = &pos;
-  sp.nodes = 0;
-  sp.cutoff = false;
-  sp.ss = ss;
-  sp.allSlavesSearching = true; // Must be set under lock protection
-
-  ++splitPointsSize;
-  activeSplitPoint = &sp;
-  activePosition = nullptr;
-
-  // Try to allocate available threads
-  Thread* slave;
-
-  while (    sp.slavesMask.count() < MAX_SLAVES_PER_SPLITPOINT
-         && (slave = Threads.available_slave(&sp)) != nullptr)
+  while (!exit)
   {
-     slave->spinlock.acquire();
-
-      if (slave->can_join(activeSplitPoint))
-      {
-          activeSplitPoint->slavesMask.set(slave->idx);
-          slave->activeSplitPoint = activeSplitPoint;
-          slave->searching = true;
-      }
-
-      slave->spinlock.release();
-  }
-
-  // Everything is set up. The master thread enters the idle loop, from which
-  // it will instantly launch a search, because its 'searching' flag is set.
-  // The thread will return from the idle loop when all slaves have finished
-  // their work at this split point.
-  sp.spinlock.release();
-
-  Thread::idle_loop(); // Force a call to base class idle_loop()
-
-  // In the helpful master concept, a master can help only a sub-tree of its
-  // split point and because everything is finished here, it's not possible
-  // for the master to be booked.
-  assert(!searching);
-  assert(!activePosition);
-
-  // We have returned from the idle loop, which means that all threads are
-  // finished. Note that decreasing splitPointsSize must be done under lock
-  // protection to avoid a race with Thread::can_join().
-  spinlock.acquire();
+      std::unique_lock<Mutex> lk(mutex);
 
-  searching = true;
-  --splitPointsSize;
-  activeSplitPoint = sp.parentSplitPoint;
-  activePosition = &pos;
+      if (!exit)
+          sleepCondition.wait_for(lk, std::chrono::milliseconds(run ? Resolution : INT_MAX));
 
-  spinlock.release();
+      lk.unlock();
 
-  // Split point data cannot be changed now, so no need to lock protect
-  pos.set_nodes_searched(pos.nodes_searched() + sp.nodes);
-  *bestMove = sp.bestMove;
-  *bestValue = sp.bestValue;
+      if (!exit && run)
+          check_time();
+  }
 }
 
 
-// TimerThread::idle_loop() is where the timer thread waits Resolution milliseconds
-// and then calls check_time(). When not searching, thread sleeps until it's woken up.
+// Thread::idle_loop() is where the thread is parked when it has no work to do
 
-void TimerThread::idle_loop() {
+void Thread::idle_loop() {
 
   while (!exit)
   {
       std::unique_lock<Mutex> lk(mutex);
 
-      if (!exit)
-          sleepCondition.wait_for(lk, std::chrono::milliseconds(run ? Resolution : INT_MAX));
+      while (!searching && !exit)
+          sleepCondition.wait(lk);
 
       lk.unlock();
 
-      if (run)
-          check_time();
+      if (!exit && searching)
+          search();
   }
 }
 
@@ -259,20 +154,12 @@ void MainThread::idle_loop() {
       lk.unlock();
 
       if (!exit)
-      {
-          searching = true;
-
-          Search::think();
-
-          assert(searching);
-
-          searching = false;
-      }
+          think();
   }
 }
 
 
-// MainThread::join() waits for main thread to finish the search
+// MainThread::join() waits for main thread to finish thinking
 
 void MainThread::join() {
 
@@ -317,7 +204,6 @@ void ThreadPool::exit() {
 
 void ThreadPool::read_uci_options() {
 
-  minimumSplitDepth = Options["Min Split Depth"] * ONE_PLY;
   size_t requested  = Options["Threads"];
 
   assert(requested > 0);
@@ -333,16 +219,14 @@ void ThreadPool::read_uci_options() {
 }
 
 
-// ThreadPool::available_slave() tries to find an idle thread which is available
-// to join SplitPoint 'sp'.
-
-Thread* ThreadPool::available_slave(const SplitPoint* sp) const {
+// ThreadPool::nodes_searched() returns the number of nodes searched
 
-  for (Thread* th : *this)
-      if (th->can_join(sp))
-          return th;
+int64_t ThreadPool::nodes_searched() {
 
-  return nullptr;
+  int64_t nodes = 0;
+  for (Thread *th : *this)
+      nodes += th->rootPos.nodes_searched();
+  return nodes;
 }
 
 
@@ -356,8 +240,8 @@ void ThreadPool::start_thinking(const Position& pos, const LimitsType& limits,
   Signals.stopOnPonderhit = Signals.firstRootMove = false;
   Signals.stop = Signals.failedLowAtRoot = false;
 
-  RootMoves.clear();
-  RootPos = pos;
+  main()->rootMoves.clear();
+  main()->rootPos = pos;
   Limits = limits;
   if (states.get()) // If we don't set a new position, preserve current state
   {
@@ -368,7 +252,7 @@ void ThreadPool::start_thinking(const Position& pos, const LimitsType& limits,
   for (const auto& m : MoveList<LEGAL>(pos))
       if (   limits.searchmoves.empty()
           || std::count(limits.searchmoves.begin(), limits.searchmoves.end(), m))
-          RootMoves.push_back(RootMove(m));
+          main()->rootMoves.push_back(RootMove(m));
 
   main()->thinking = true;
   main()->notify_one(); // Wake up main thread: 'thinking' must be already set
index e880b01..97ed219 100644 (file)
 struct Thread;
 
 const size_t MAX_THREADS = 128;
-const size_t MAX_SPLITPOINTS_PER_THREAD = 8;
-const size_t MAX_SLAVES_PER_SPLITPOINT = 4;
-
-class Spinlock {
-
-  std::atomic_int lock;
-
-public:
-  Spinlock() { lock = 1; } // Init here to workaround a bug with MSVC 2013
-  void acquire() {
-      while (lock.fetch_sub(1, std::memory_order_acquire) != 1)
-          while (lock.load(std::memory_order_relaxed) <= 0)
-              std::this_thread::yield(); // Be nice to hyperthreading
-  }
-  void release() { lock.store(1, std::memory_order_release); }
-};
-
-
-/// SplitPoint struct stores information shared by the threads searching in
-/// parallel below the same split point. It is populated at splitting time.
-
-struct SplitPoint {
-
-  // Const data after split point has been setup
-  const Position* pos;
-  Search::Stack* ss;
-  Thread* master;
-  Depth depth;
-  Value beta;
-  int nodeType;
-  bool cutNode;
-
-  // Const pointers to shared data
-  MovePicker* movePicker;
-  SplitPoint* parentSplitPoint;
-
-  // Shared variable data
-  Spinlock spinlock;
-  std::bitset<MAX_THREADS> slavesMask;
-  volatile bool allSlavesSearching;
-  volatile uint64_t nodes;
-  volatile Value alpha;
-  volatile Value bestValue;
-  volatile Move bestMove;
-  volatile int moveCount;
-  volatile bool cutoff;
-};
 
 
 /// ThreadBase struct is the base of the hierarchy from where we derive all the
@@ -94,10 +47,10 @@ struct ThreadBase : public std::thread {
   virtual ~ThreadBase() = default;
   virtual void idle_loop() = 0;
   void notify_one();
-  void wait_for(volatile const bool& b);
+  void wait(volatile const bool& b);
+  void wait_while(volatile const bool& b);
 
   Mutex mutex;
-  Spinlock spinlock;
   ConditionVariable sleepCondition;
   volatile bool exit = false;
 };
@@ -112,22 +65,21 @@ struct Thread : public ThreadBase {
 
   Thread();
   virtual void idle_loop();
-  bool cutoff_occurred() const;
-  bool can_join(const SplitPoint* sp) const;
-
-  void split(Position& pos, Search::Stack* ss, Value alpha, Value beta, Value* bestValue, Move* bestMove,
-             Depth depth, int moveCount, MovePicker* movePicker, int nodeType, bool cutNode);
+  void search(bool isMainThread = false);
 
-  SplitPoint splitPoints[MAX_SPLITPOINTS_PER_THREAD];
   Pawns::Table pawnsTable;
   Material::Table materialTable;
   Endgames endgames;
-  Position* activePosition;
-  size_t idx;
+  size_t idx, PVIdx;
   int maxPly;
-  SplitPoint* volatile activeSplitPoint;
-  volatile size_t splitPointsSize;
   volatile bool searching;
+
+  Position rootPos;
+  Search::RootMoveVector rootMoves;
+  Search::Stack stack[MAX_PLY+4];
+  HistoryStats History;
+  MovesStats Countermoves;
+  Depth depth;
 };
 
 
@@ -137,6 +89,7 @@ struct Thread : public ThreadBase {
 struct MainThread : public Thread {
   virtual void idle_loop();
   void join();
+  void think();
   volatile bool thinking = true; // Avoid a race with start_thinking()
 };
 
@@ -161,10 +114,8 @@ struct ThreadPool : public std::vector<Thread*> {
 
   MainThread* main() { return static_cast<MainThread*>(at(0)); }
   void read_uci_options();
-  Thread* available_slave(const SplitPoint* sp) const;
   void start_thinking(const Position&, const Search::LimitsType&, Search::StateStackPtr&);
-
-  Depth minimumSplitDepth;
+  int64_t nodes_searched();
   TimerThread* timer;
 };
 
index 7a5db25..3a4e157 100644 (file)
@@ -80,7 +80,7 @@ namespace {
 ///  inc >  0 && movestogo == 0 means: x basetime + z increment
 ///  inc >  0 && movestogo != 0 means: x moves in y minutes + z increment
 
-void TimeManagement::init(Search::LimitsType& limits, Color us, int ply, TimePoint now)
+void TimeManagement::init(Search::LimitsType& limits, Color us, int ply)
 {
   int minThinkingTime = Options["Minimum Thinking Time"];
   int moveOverhead    = Options["Move Overhead"];
@@ -102,7 +102,7 @@ void TimeManagement::init(Search::LimitsType& limits, Color us, int ply, TimePoi
       limits.npmsec = npmsec;
   }
 
-  start = now;
+  startTime = limits.startTime;
   unstablePvFactor = 1;
   optimumTime = maximumTime = std::max(limits.time[us], minThinkingTime);
 
index c5390be..b6eb348 100644 (file)
 
 #include "misc.h"
 #include "search.h"
+#include "thread.h"
 
 /// The TimeManagement class computes the optimal time to think depending on
 /// the maximum available time, the game move number and other parameters.
 
 class TimeManagement {
 public:
-  void init(Search::LimitsType& limits, Color us, int ply, TimePoint now);
+  void init(Search::LimitsType& limits, Color us, int ply);
   void pv_instability(double bestMoveChanges) { unstablePvFactor = 1 + bestMoveChanges; }
   int available() const { return int(optimumTime * unstablePvFactor * 0.76); }
   int maximum() const { return maximumTime; }
-  int elapsed() const { return int(Search::Limits.npmsec ? Search::RootPos.nodes_searched() : now() - start); }
+  int elapsed() const { return int(Search::Limits.npmsec ? Threads.nodes_searched() : now() - startTime); }
 
   int64_t availableNodes; // When in 'nodes as time' mode
 
 private:
-  TimePoint start;
+  TimePoint startTime;
   int optimumTime;
   int maximumTime;
   double unstablePvFactor;
index 4e56542..c5dbafa 100644 (file)
@@ -112,6 +112,8 @@ namespace {
     Search::LimitsType limits;
     string token;
 
+    limits.startTime = now(); // As early as possible!
+
     while (is >> token)
         if (token == "searchmoves")
             while (is >> token)