X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=ebd004d39c541d5632163ffe8817f113a6891f74;hb=77bb9a94aed2a78d98e04399207f51ed92d531d3;hp=aea07fdae7fdf93df1cc60b3981ea8bf99810f27;hpb=b39a24ecca28620239818ca393a46a47f9d42824;p=stockfish

diff --git a/src/search.cpp b/src/search.cpp
index aea07fda..ebd004d3 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -70,7 +70,6 @@ namespace {
 
     int active_threads() const { return ActiveThreads; }
     void set_active_threads(int newActiveThreads) { ActiveThreads = newActiveThreads; }
-    void set_stop_request(int threadID) { threads[threadID].stopRequest = true; }
     void incrementNodeCounter(int threadID) { threads[threadID].nodes++; }
     void incrementBetaCounter(Color us, Depth d, int threadID) { threads[threadID].betaCutOffs[us] += unsigned(d); }
     void print_current_line(SearchStack ss[], int ply, int threadID);
@@ -85,7 +84,7 @@ namespace {
     void wake_sleeping_threads();
     void put_threads_to_sleep();
     void idle_loop(int threadID, SplitPoint* waitSp);
-    bool split(const Position& pos, SearchStack* ss, int ply, Value* alpha, Value* beta, Value* bestValue,
+    bool split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
                const Value futilityValue, Depth depth, int* moves, MovePicker* mp, int master, bool pvNode);
 
   private:
@@ -443,9 +442,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
   // Wake up sleeping threads
   TM.wake_sleeping_threads();
 
-  for (int i = 1; i < TM.active_threads(); i++)
-      assert(TM.thread_is_available(i, 0));
-
   // Set thinking time
   int myTime = time[side_to_move];
   int myIncrement = increment[side_to_move];
@@ -1211,7 +1207,7 @@ namespace {
           && TM.available_thread_exists(threadID)
           && !AbortSearch
           && !TM.thread_should_stop(threadID)
-          && TM.split(pos, ss, ply, &alpha, &beta, &bestValue, VALUE_NONE,
+          && TM.split(pos, ss, ply, &alpha, beta, &bestValue, VALUE_NONE,
                       depth, &moveCount, &mp, threadID, true))
           break;
     }
@@ -1271,29 +1267,30 @@ namespace {
     if (depth < OnePly)
         return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
 
-    // Initialize, and make an early exit in case of an aborted search,
-    // an instant draw, maximum ply reached, etc.
+    // Step 1. Initialize node and poll
+    // Polling can abort search.
     init_node(ss, ply, threadID);
 
-    // After init_node() that calls poll()
+    // Step 2. Check for aborted search and immediate draw
     if (AbortSearch || TM.thread_should_stop(threadID))
         return Value(0);
 
     if (pos.is_draw() || ply >= PLY_MAX - 1)
         return VALUE_DRAW;
 
-    // Mate distance pruning
+    // Step 3. Mate distance pruning
     if (value_mated_in(ply) >= beta)
         return beta;
 
     if (value_mate_in(ply + 1) < beta)
         return beta - 1;
 
+    // Step 4. Transposition table lookup
+
     // We don't want the score of a partial search to overwrite a previous full search
     // TT value, so we use a different position key in case of an excluded move exsists.
     Key posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
 
-    // Transposition table lookup
     tte = TT.retrieve(posKey);
     ttMove = (tte ? tte->move() : MOVE_NONE);
 
@@ -1303,9 +1300,9 @@ namespace {
         return value_from_tt(tte->value(), ply);
     }
 
+    // Step 5. Evaluate the position statically
     isCheck = pos.is_check();
 
-    // Evaluate the position statically
     if (!isCheck)
     {
         if (tte && (tte->type() & VALUE_TYPE_EVAL))
@@ -1525,7 +1522,7 @@ namespace {
           && TM.available_thread_exists(threadID)
           && !AbortSearch
           && !TM.thread_should_stop(threadID)
-          && TM.split(pos, ss, ply, &beta, &beta, &bestValue, futilityValue, //FIXME: SMP & futilityValue
+          && TM.split(pos, ss, ply, NULL, beta, &bestValue, futilityValue, //FIXME: SMP & futilityValue
                       depth, &moveCount, &mp, threadID, false))
           break;
     }
@@ -1839,7 +1836,7 @@ namespace {
           if (ss[sp->ply].reduction)
           {
               value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
-              doFullDepthSearch = (value >= sp->beta);
+              doFullDepthSearch = (value >= sp->beta && !TM.thread_should_stop(threadID));
           }
       }
 
@@ -1852,12 +1849,6 @@ namespace {
 
       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
 
-      if (TM.thread_should_stop(threadID))
-      {
-          lock_grab(&(sp->lock));
-          break;
-      }
-
       // New best move?
       if (value > sp->bestValue) // Less then 2% of cases
       {
@@ -1867,12 +1858,8 @@ namespace {
               sp->bestValue = value;
               if (sp->bestValue >= sp->beta)
               {
+                  sp->stopRequest = true;
                   sp_update_pv(sp->parentSstack, ss, sp->ply);
-                  for (int i = 0; i < TM.active_threads(); i++)
-                      if (i != threadID && (i == sp->master || sp->slaves[i]))
-                          TM.set_stop_request(i);
-
-                  sp->finished = true;
               }
           }
           lock_release(&(sp->lock));
@@ -1881,15 +1868,6 @@ namespace {
 
     /* Here we have the lock still grabbed */
 
-    // If this is the master thread and we have been asked to stop because of
-    // a beta cutoff higher up in the tree, stop all slave threads. Note that
-    // thread_should_stop(threadID) does not imply that 'stop' flag is set, so
-    // do this explicitly now, under lock protection.
-    if (sp->master == threadID && TM.thread_should_stop(threadID))
-        for (int i = 0; i < TM.active_threads(); i++)
-            if (sp->slaves[i] || i == threadID)
-                TM.set_stop_request(i);
-
     sp->cpus--;
     sp->slaves[threadID] = 0;
 
@@ -1955,7 +1933,7 @@ namespace {
           {
               Value localAlpha = sp->alpha;
               value = -search(pos, ss, -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
-              doFullDepthSearch = (value > localAlpha);
+              doFullDepthSearch = (value > localAlpha && !TM.thread_should_stop(threadID));
           }
       }
 
@@ -1965,27 +1943,19 @@ namespace {
           ss[sp->ply].reduction = Depth(0);
           value = -search(pos, ss, -localAlpha, newDepth, sp->ply+1, true, threadID);
 
-          if (value > localAlpha && value < sp->beta)
+          if (value > localAlpha && value < sp->beta && !TM.thread_should_stop(threadID))
           {
               // If another thread has failed high then sp->alpha has been increased
               // to be higher or equal then beta, if so, avoid to start a PV search.
               localAlpha = sp->alpha;
               if (localAlpha < sp->beta)
                   value = -search_pv(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, threadID);
-              else
-                  assert(TM.thread_should_stop(threadID));
-        }
+          }
       }
       pos.undo_move(move);
 
       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
 
-      if (TM.thread_should_stop(threadID))
-      {
-          lock_grab(&(sp->lock));
-          break;
-      }
-
       // New best move?
       if (value > sp->bestValue) // Less then 2% of cases
       {
@@ -1997,13 +1967,7 @@ namespace {
               {
                   // Ask threads to stop before to modify sp->alpha
                   if (value >= sp->beta)
-                  {
-                      for (int i = 0; i < TM.active_threads(); i++)
-                          if (i != threadID && (i == sp->master || sp->slaves[i]))
-                              TM.set_stop_request(i);
-
-                      sp->finished = true;
-                  }
+                      sp->stopRequest = true;
 
                   sp->alpha = value;
 
@@ -2018,15 +1982,6 @@ namespace {
 
     /* Here we have the lock still grabbed */
 
-    // If this is the master thread and we have been asked to stop because of
-    // a beta cutoff higher up in the tree, stop all slave threads. Note that
-    // thread_should_stop(threadID) does not imply that 'stop' flag is set, so
-    // do this explicitly now, under lock protection.
-    if (sp->master == threadID && TM.thread_should_stop(threadID))
-        for (int i = 0; i < TM.active_threads(); i++)
-            if (sp->slaves[i] || i == threadID)
-                TM.set_stop_request(i);
-
     sp->cpus--;
     sp->slaves[threadID] = 0;
 
@@ -2627,34 +2582,40 @@ namespace {
     {
         // Slave threads can exit as soon as AllThreadsShouldExit raises,
         // master should exit as last one.
-        if (AllThreadsShouldExit && !waitSp)
+        if (AllThreadsShouldExit)
         {
+            assert(!waitSp);
             threads[threadID].state = THREAD_TERMINATED;
             return;
         }
 
         // If we are not thinking, wait for a condition to be signaled
         // instead of wasting CPU time polling for work.
-        while (    threadID != 0
-               && !AllThreadsShouldExit
-               && (AllThreadsShouldSleep || threadID >= ActiveThreads))
+        while (AllThreadsShouldSleep || threadID >= ActiveThreads)
         {
+            assert(!waitSp);
+            assert(threadID != 0);
             threads[threadID].state = THREAD_SLEEPING;
 
 #if !defined(_MSC_VER)
             pthread_mutex_lock(&WaitLock);
-            pthread_cond_wait(&WaitCond, &WaitLock);
+            if (AllThreadsShouldSleep || threadID >= ActiveThreads)
+                pthread_cond_wait(&WaitCond, &WaitLock);
             pthread_mutex_unlock(&WaitLock);
 #else
             WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
 #endif
-            // State is already changed by wake_sleeping_threads()
-            assert(threads[threadID].state == THREAD_AVAILABLE || threadID >= ActiveThreads);
         }
 
+        // If thread has just woken up, mark it as available
+        if (threads[threadID].state == THREAD_SLEEPING)
+            threads[threadID].state = THREAD_AVAILABLE;
+
         // If this thread has been assigned work, launch a search
         if (threads[threadID].state == THREAD_WORKISWAITING)
         {
+            assert(!AllThreadsShouldExit && !AllThreadsShouldSleep);
+
             threads[threadID].state = THREAD_SEARCHING;
 
             if (threads[threadID].splitPoint->pvNode)
@@ -2664,21 +2625,14 @@ namespace {
 
             assert(threads[threadID].state == THREAD_SEARCHING);
 
-            // If this is a slave thread reset to available, instead
-            // if it is a master thread and all slaves have finished
-            // then leave as is to avoid booking by another master,
-            // we will leave idle loop shortly anyhow.
-            if (   !AllThreadsShouldExit
-                && (!waitSp || waitSp->cpus > 0))
-                threads[threadID].state = THREAD_AVAILABLE;
+            threads[threadID].state = THREAD_AVAILABLE;
         }
 
         // If this thread is the master of a split point and all threads have
         // finished their work at this split point, return from the idle loop.
         if (waitSp != NULL && waitSp->cpus == 0)
         {
-            assert(   threads[threadID].state == THREAD_AVAILABLE
-                   || threads[threadID].state == THREAD_SEARCHING);
+            assert(threads[threadID].state == THREAD_AVAILABLE);
 
             threads[threadID].state = THREAD_SEARCHING;
             return;
@@ -2705,7 +2659,7 @@ namespace {
     lock_init(&IOLock, NULL);
 
     // Initialize SplitPointStack locks
-    for (int i = 0; i < MAX_THREADS; i++)
+    for (i = 0; i < MAX_THREADS; i++)
         for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
         {
             SplitPointStack[i][j].parent = NULL;
@@ -2769,8 +2723,7 @@ namespace {
 
     // Wait for thread termination
     for (int i = 1; i < MAX_THREADS; i++)
-        while (threads[i].state != THREAD_TERMINATED)
-            threads[i].stopRequest = true;
+        while (threads[i].state != THREAD_TERMINATED);
 
     // Now we can safely destroy the locks
     for (int i = 0; i < MAX_THREADS; i++)
@@ -2779,10 +2732,9 @@ namespace {
   }
 
 
-  // thread_should_stop() checks whether the thread with a given threadID has
-  // been asked to stop, directly or indirectly. This can happen if a beta
-  // cutoff has occurred in the thread's currently active split point, or in
-  // some ancestor of the current split point.
+  // thread_should_stop() checks whether the thread should stop its search.
+  // This can happen if a beta cutoff has occurred in the thread's currently
+  // active split point, or in some ancestor of the current split point.
 
   bool ThreadsManager::thread_should_stop(int threadID) const {
 
@@ -2790,17 +2742,8 @@ namespace {
 
     SplitPoint* sp;
 
-    if (threads[threadID].stopRequest)
-        return true;
-
-    if (ActiveThreads <= 2)
-        return false;
-
-    for (sp = threads[threadID].splitPoint; sp != NULL; sp = sp->parent)
-        if (sp->finished)
-            return true;
-
-    return false;
+    for (sp = threads[threadID].splitPoint; sp && !sp->stopRequest; sp = sp->parent);
+    return sp != NULL;
   }
 
 
@@ -2871,15 +2814,17 @@ namespace {
   // splitPoint->cpus becomes 0), split() returns true.
 
   bool ThreadsManager::split(const Position& p, SearchStack* sstck, int ply,
-             Value* alpha, Value* beta, Value* bestValue, const Value futilityValue,
+             Value* alpha, const Value beta, Value* bestValue, const Value futilityValue,
              Depth depth, int* moves, MovePicker* mp, int master, bool pvNode) {
 
     assert(p.is_ok());
     assert(sstck != NULL);
     assert(ply >= 0 && ply < PLY_MAX);
-    assert(*bestValue >= -VALUE_INFINITE && *bestValue <= *alpha);
-    assert(!pvNode || *alpha < *beta);
-    assert(*beta <= VALUE_INFINITE);
+    assert(*bestValue >= -VALUE_INFINITE);
+    assert(   ( pvNode && *bestValue <= *alpha)
+           || (!pvNode && *bestValue <   beta ));
+    assert(!pvNode || *alpha < beta);
+    assert(beta <= VALUE_INFINITE);
     assert(depth > Depth(0));
     assert(master >= 0 && master < ActiveThreads);
     assert(ActiveThreads > 1);
@@ -2898,16 +2843,15 @@ namespace {
     }
 
     // Pick the next available split point object from the split point stack
-    splitPoint = SplitPointStack[master] + threads[master].activeSplitPoints;
-    threads[master].activeSplitPoints++;
+    splitPoint = &SplitPointStack[master][threads[master].activeSplitPoints];
 
     // Initialize the split point object
     splitPoint->parent = threads[master].splitPoint;
-    splitPoint->finished = false;
+    splitPoint->stopRequest = false;
     splitPoint->ply = ply;
     splitPoint->depth = depth;
-    splitPoint->alpha = pvNode ? *alpha : (*beta - 1);
-    splitPoint->beta = *beta;
+    splitPoint->alpha = pvNode ? *alpha : beta - 1;
+    splitPoint->beta = beta;
     splitPoint->pvNode = pvNode;
     splitPoint->bestValue = *bestValue;
     splitPoint->futilityValue = futilityValue;
@@ -2921,6 +2865,7 @@ namespace {
         splitPoint->slaves[i] = 0;
 
     threads[master].splitPoint = splitPoint;
+    threads[master].activeSplitPoints++;
 
     // If we are here it means we are not available
     assert(threads[master].state != THREAD_AVAILABLE);
@@ -2930,7 +2875,6 @@ namespace {
         if (thread_is_available(i, master))
         {
             threads[i].state = THREAD_BOOKED;
-            threads[i].stopRequest = false;
             threads[i].splitPoint = splitPoint;
             splitPoint->slaves[i] = 1;
             splitPoint->cpus++;
@@ -2968,9 +2912,7 @@ namespace {
     if (pvNode)
         *alpha = splitPoint->alpha;
 
-    *beta = splitPoint->beta;
     *bestValue = splitPoint->bestValue;
-    threads[master].stopRequest = false;
     threads[master].activeSplitPoints--;
     threads[master].splitPoint = splitPoint->parent;
 
@@ -2993,12 +2935,8 @@ namespace {
         return;
 
     for (int i = 1; i < ActiveThreads; i++)
-    {
         assert(threads[i].state == THREAD_SLEEPING);
 
-        threads[i].state = THREAD_AVAILABLE;
-    }
-
 #if !defined(_MSC_VER)
     pthread_mutex_lock(&WaitLock);
     pthread_cond_broadcast(&WaitCond);
@@ -3022,14 +2960,11 @@ namespace {
     // This makes the threads to go to sleep
     AllThreadsShouldSleep = true;
 
-    // Wait for the threads to be all sleeping and reset flags
-    // to a known state.
+    // Reset flags to a known state.
     for (int i = 1; i < ActiveThreads; i++)
     {
-        while (threads[i].state != THREAD_SLEEPING);
-
-        // These two flags can be in a random state
-        threads[i].stopRequest = threads[i].printCurrentLineRequest = false;
+        // This flag can be in a random state
+        threads[i].printCurrentLineRequest = false;
     }
   }