Add support for node limited search

Handle also the SMP case. This has been quite tricky, not
trivial to enforce the node limit in SMP case becuase
with "helpful master" concept we can have recursive split
points and we cannot lock them all at once so there is the
risk of counting the same nodes more than once.

Anyhow this patch should be race free and counted nodes are
correct.

No functional change.

diff --git a/src/search.cpp b/src/search.cpp
index 29dc00a996d2e97337c819b29a99681c49f9806f..3793766b9f845e931c52338010add92eba868e65 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -279,6 +279,8 @@ void Search::think() {
   // used to check for remaining available thinking time.
   if (Limits.use_time_management())
       Threads.set_timer(std::min(100, std::max(TimeMgr.available_time() / 16, TimerResolution)));
+  else if (Limits.nodes)
+      Threads.set_timer(2 * TimerResolution);
   else
       Threads.set_timer(100);
 
@@ -566,10 +568,6 @@ namespace {
         (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE;
     }
 
-    // Enforce node limit here. FIXME: This only works with 1 search thread.
-    if (Limits.nodes && pos.nodes_searched() >= Limits.nodes)
-        Signals.stop = true;
-
     if (!RootNode)
     {
         // Step 2. Check for aborted search and immediate draw
@@ -1712,6 +1710,10 @@ void Thread::idle_loop() {
 
           sp->mutex.lock();
 
+          assert(sp->activePositions[idx] == NULL);
+
+          sp->activePositions[idx] = &pos;
+
           if (sp->nodeType == Root)
               search<SplitPointRoot>(pos, ss+1, sp->alpha, sp->beta, sp->depth);
           else if (sp->nodeType == PV)
@@ -1724,6 +1726,7 @@ void Thread::idle_loop() {
           assert(is_searching);
 
           is_searching = false;
+          sp->activePositions[idx] = NULL;
           sp->slavesMask &= ~(1ULL << idx);
           sp->nodes += pos.nodes_searched();
 
@@ -1754,6 +1757,7 @@ void Thread::idle_loop() {
 void check_time() {
 
   static Time::point lastInfoTime = Time::now();
+  int64_t nodes = 0; // Workaround silly 'uninitialized' gcc warning
 
   if (Time::now() - lastInfoTime >= 1000)
   {
@@ -1764,6 +1768,35 @@ void check_time() {
   if (Limits.ponder)
       return;
 
+  if (Limits.nodes)
+  {
+      Threads.mutex.lock();
+
+      nodes = RootPosition.nodes_searched();
+
+      // Loop across all split points and sum accumulated SplitPoint nodes plus
+      // all the currently active slaves positions.
+      for (size_t i = 0; i < Threads.size(); i++)
+          for (int j = 0; j < Threads[i].splitPointsCnt; j++)
+          {
+              SplitPoint& sp = Threads[i].splitPoints[j];
+
+              sp.mutex.lock();
+
+              nodes += sp.nodes;
+              Bitboard sm = sp.slavesMask;
+              while (sm)
+              {
+                  Position* pos = sp.activePositions[pop_lsb(&sm)];
+                  nodes += pos ? pos->nodes_searched() : 0;
+              }
+
+              sp.mutex.unlock();
+          }
+
+      Threads.mutex.unlock();
+  }
+
   Time::point elapsed = Time::now() - SearchTime;
   bool stillAtFirstMove =    Signals.firstRootMove
                          && !Signals.failedLowAtRoot
@@ -1773,6 +1806,7 @@ void check_time() {
                    || stillAtFirstMove;
 
   if (   (Limits.use_time_management() && noMoreTime)
-      || (Limits.movetime && elapsed >= Limits.movetime))
+      || (Limits.movetime && elapsed >= Limits.movetime)
+      || (Limits.nodes && nodes >= Limits.nodes))
       Signals.stop = true;
 }

diff --git a/src/thread.cpp b/src/thread.cpp
index 8d522fa2bed9638b8375a859a18e9705ce1b45b6..271890c6f008b85eedee8d2302f0ebe4f2353e57 100644 (file)
--- a/src/thread.cpp
+++ b/src/thread.cpp
@@ -42,7 +42,7 @@ namespace { extern "C" {
 // Thread c'tor starts a newly-created thread of execution that will call
 // the idle loop function pointed by start_fn going immediately to sleep.
 
-Thread::Thread(Fn fn) {
+Thread::Thread(Fn fn) : splitPoints() {
 
   is_searching = do_exit = false;
   maxPly = splitPointsCnt = 0;
@@ -200,10 +200,10 @@ void ThreadPool::init() {
 
 void ThreadPool::exit() {
 
+  delete timer; // As first becuase check_time() accesses threads data
+
   for (size_t i = 0; i < threads.size(); i++)
       delete threads[i];
-
-  delete timer;
 }
 
 
@@ -327,8 +327,8 @@ Value ThreadPool::split(Position& pos, Stack* ss, Value alpha, Value beta,
   // Try to allocate available threads and ask them to start searching setting
   // is_searching flag. This must be done under lock protection to avoid concurrent
   // allocation of the same slave by another master.
-  sp.mutex.lock();
   mutex.lock();
+  sp.mutex.lock();
 
   for (size_t i = 0; i < threads.size() && !Fake; ++i)
       if (threads[i]->is_available_to(master))
@@ -346,8 +346,8 @@ Value ThreadPool::split(Position& pos, Stack* ss, Value alpha, Value beta,
 
   master->splitPointsCnt++;
 
-  mutex.unlock();
   sp.mutex.unlock();
+  mutex.unlock();
 
   // Everything is set up. The master thread enters the idle loop, from which
   // it will instantly launch a search, because its is_searching flag is set.
@@ -365,8 +365,8 @@ Value ThreadPool::split(Position& pos, Stack* ss, Value alpha, Value beta,
   // We have returned from the idle loop, which means that all threads are
   // finished. Note that setting is_searching and decreasing splitPointsCnt is
   // done under lock protection to avoid a race with Thread::is_available_to().
-  sp.mutex.lock(); // To protect sp.nodes
   mutex.lock();
+  sp.mutex.lock();
 
   master->is_searching = true;
   master->splitPointsCnt--;
@@ -374,8 +374,8 @@ Value ThreadPool::split(Position& pos, Stack* ss, Value alpha, Value beta,
   pos.set_nodes_searched(pos.nodes_searched() + sp.nodes);
   *bestMove = sp.bestMove;
 
-  mutex.unlock();
   sp.mutex.unlock();
+  mutex.unlock();
 
   return sp.bestValue;
 }

diff --git a/src/thread.h b/src/thread.h
index 38a29e8dc00d6c07bd88f097830ff8ce3d378a4c..f69012aeb0a3053130b85abada02704b7781d531 100644 (file)
--- a/src/thread.h
+++ b/src/thread.h
@@ -75,6 +75,7 @@ struct SplitPoint {
 
   // Shared data
   Mutex mutex;
+  Position* activePositions[MAX_THREADS];
   volatile uint64_t slavesMask;
   volatile int64_t nodes;
   volatile Value alpha;
@@ -153,6 +154,7 @@ public:
               Depth depth, Move threatMove, int moveCount, MovePicker* mp, int nodeType);
 private:
   friend class Thread;
+  friend void check_time();
 
   std::vector<Thread*> threads;
   Thread* timer;