]> git.sesse.net Git - stockfish/blobdiff - src/search.cpp
Move depth computation out of fail low loop
[stockfish] / src / search.cpp
index 5048381d2bf91c363e386864437ca8fe07cedc44..fff00026c6cdad7380c32d1e4b53471f65efae05 100644 (file)
@@ -251,8 +251,7 @@ namespace {
   int MultiPV;
 
   // Time managment variables
-  int SearchStartTime, MaxNodes, MaxDepth, OptimumSearchTime;
-  int MaximumSearchTime, ExtraSearchTime, ExactMaxTime;
+  int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
   bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
   bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
   TimeManager TimeMgr;
@@ -264,7 +263,7 @@ namespace {
   // Multi-threads related variables
   Depth MinimumSplitDepth;
   int MaxThreadsPerSplitPoint;
-  ThreadsManager TM;
+  ThreadsManager ThreadsMgr;
 
   // Node counters, used only by thread[0] but try to keep in different cache
   // lines (64 bytes each) from the heavy multi-thread read accessed variables.
@@ -330,9 +329,9 @@ namespace {
 /// init_threads(), exit_threads() and nodes_searched() are helpers to
 /// give accessibility to some TM methods from outside of current file.
 
-void init_threads() { TM.init_threads(); }
-void exit_threads() { TM.exit_threads(); }
-int64_t nodes_searched() { return TM.nodes_searched(); }
+void init_threads() { ThreadsMgr.init_threads(); }
+void exit_threads() { ThreadsMgr.exit_threads(); }
+int64_t nodes_searched() { return ThreadsMgr.nodes_searched(); }
 
 
 /// init_search() is called during startup. It initializes various lookup tables
@@ -367,26 +366,27 @@ void init_search() {
 
 int perft(Position& pos, Depth depth)
 {
+    MoveStack mlist[256];
     StateInfo st;
-    Move move;
+    Move m;
     int sum = 0;
-    MovePicker mp(pos, MOVE_NONE, depth, H);
+
+    // Generate all legal moves
+    MoveStack* last = generate_moves(pos, mlist);
 
     // If we are at the last ply we don't need to do and undo
     // the moves, just to count them.
-    if (depth <= OnePly) // Replace with '<' to test also qsearch
-    {
-        while (mp.get_next_move()) sum++;
-        return sum;
-    }
+    if (depth <= OnePly)
+        return int(last - mlist);
 
     // Loop through all legal moves
     CheckInfo ci(pos);
-    while ((move = mp.get_next_move()) != MOVE_NONE)
+    for (MoveStack* cur = mlist; cur != last; cur++)
     {
-        pos.do_move(move, st, ci, pos.move_is_check(move, ci));
+        m = cur->move;
+        pos.do_move(m, st, ci, pos.move_is_check(m, ci));
         sum += perft(pos, depth - OnePly);
-        pos.undo_move(move);
+        pos.undo_move(m);
     }
     return sum;
 }
@@ -402,9 +402,8 @@ bool think(const Position& pos, bool infinite, bool ponder, int time[], int incr
 
   // Initialize global search variables
   StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
-  OptimumSearchTime = MaximumSearchTime = ExtraSearchTime = 0;
   NodesSincePoll = 0;
-  TM.resetNodeCounters();
+  ThreadsMgr.resetNodeCounters();
   SearchStartTime = get_system_time();
   ExactMaxTime = maxTime;
   MaxDepth = maxDepth;
@@ -461,21 +460,20 @@ bool think(const Position& pos, bool infinite, bool ponder, int time[], int incr
 
   // Set the number of active threads
   int newActiveThreads = get_option_value_int("Threads");
-  if (newActiveThreads != TM.active_threads())
+  if (newActiveThreads != ThreadsMgr.active_threads())
   {
-      TM.set_active_threads(newActiveThreads);
-      init_eval(TM.active_threads());
+      ThreadsMgr.set_active_threads(newActiveThreads);
+      init_eval(ThreadsMgr.active_threads());
   }
 
   // Wake up sleeping threads
-  TM.wake_sleeping_threads();
+  ThreadsMgr.wake_sleeping_threads();
 
   // Set thinking time
   int myTime = time[pos.side_to_move()];
   int myIncrement = increment[pos.side_to_move()];
   if (UseTimeManagement)
-      TimeMgr.update(myTime, myIncrement, movesToGo, pos.startpos_ply_counter(),
-                     &OptimumSearchTime, &MaximumSearchTime);
+      TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter());
 
   // Set best NodesBetweenPolls interval to avoid lagging under
   // heavy time pressure.
@@ -503,7 +501,7 @@ bool think(const Position& pos, bool infinite, bool ponder, int time[], int incr
   if (UseLogFile)
       LogFile.close();
 
-  TM.put_threads_to_sleep();
+  ThreadsMgr.put_threads_to_sleep();
 
   return !Quit;
 }
@@ -542,7 +540,7 @@ namespace {
          << "\ninfo depth " << 1
          << " score " << value_to_uci(rml.get_move_score(0))
          << " time " << current_search_time()
-         << " nodes " << TM.nodes_searched()
+         << " nodes " << ThreadsMgr.nodes_searched()
          << " nps " << nps()
          << " pv " << rml.get_move(0) << "\n";
 
@@ -615,24 +613,24 @@ namespace {
                 stopSearch = true;
 
             // Stop search early if one move seems to be much better than the others
-            int64_t nodes = TM.nodes_searched();
+            int64_t nodes = ThreadsMgr.nodes_searched();
             if (   Iteration >= 8
                 && EasyMove == pv[0]
                 && (  (   rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
-                       && current_search_time() > OptimumSearchTime / 16)
+                       && current_search_time() > TimeMgr.available_time() / 16)
                     ||(   rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100
-                       && current_search_time() > OptimumSearchTime / 32)))
+                       && current_search_time() > TimeMgr.available_time() / 32)))
                 stopSearch = true;
 
             // Add some extra time if the best move has changed during the last two iterations
             if (Iteration > 5 && Iteration <= 50)
-                ExtraSearchTime = BestMoveChangesByIteration[Iteration]   * (OptimumSearchTime / 2)
-                                + BestMoveChangesByIteration[Iteration-1] * (OptimumSearchTime / 3);
+                TimeMgr.pv_unstability(BestMoveChangesByIteration[Iteration],
+                                       BestMoveChangesByIteration[Iteration-1]);
 
             // Stop search if most of MaxSearchTime is consumed at the end of the
             // iteration. We probably don't have enough time to search the first
             // move at the next iteration anyway.
-            if (current_search_time() > ((OptimumSearchTime + ExtraSearchTime) * 80) / 128)
+            if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
                 stopSearch = true;
 
             if (stopSearch)
@@ -654,7 +652,7 @@ namespace {
         wait_for_stop_or_ponderhit();
     else
         // Print final search statistics
-        cout << "info nodes " << TM.nodes_searched()
+        cout << "info nodes " << ThreadsMgr.nodes_searched()
              << " nps " << nps()
              << " time " << current_search_time() << endl;
 
@@ -682,7 +680,7 @@ namespace {
         if (dbg_show_hit_rate)
             dbg_print_hit_rate(LogFile);
 
-        LogFile << "\nNodes: " << TM.nodes_searched()
+        LogFile << "\nNodes: " << ThreadsMgr.nodes_searched()
                 << "\nNodes/second: " << nps()
                 << "\nBest move: " << move_to_san(p, pv[0]);
 
@@ -717,6 +715,7 @@ namespace {
     alpha = *alphaPtr;
     beta = *betaPtr;
     isCheck = pos.is_check();
+    depth = (Iteration - 2) * OnePly + InitialDepth;
 
     // Step 1. Initialize node (polling is omitted at root)
     ss->currentMove = ss->bestMove = MOVE_NONE;
@@ -749,10 +748,10 @@ namespace {
             FirstRootMove = (i == 0);
 
             // Save the current node count before the move is searched
-            nodes = TM.nodes_searched();
+            nodes = ThreadsMgr.nodes_searched();
 
             // Reset beta cut-off counters
-            TM.resetBetaCounters();
+            ThreadsMgr.resetBetaCounters();
 
             // Pick the next root move, and print the move and the move number to
             // the standard output.
@@ -766,7 +765,6 @@ namespace {
             captureOrPromotion = pos.move_is_capture_or_promotion(move);
 
             // Step 11. Decide the new search depth
-            depth = (Iteration - 2) * OnePly + InitialDepth;
             ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
             newDepth = depth + ext;
 
@@ -876,9 +874,9 @@ namespace {
             // Remember beta-cutoff and searched nodes counts for this move. The
             // info is used to sort the root moves for the next iteration.
             int64_t our, their;
-            TM.get_beta_counters(pos.side_to_move(), our, their);
+            ThreadsMgr.get_beta_counters(pos.side_to_move(), our, their);
             rml.set_beta_counters(i, our, their);
-            rml.set_move_nodes(i, TM.nodes_searched() - nodes);
+            rml.set_move_nodes(i, ThreadsMgr.nodes_searched() - nodes);
 
             assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
             assert(value < beta);
@@ -920,7 +918,7 @@ namespace {
                              << " score " << value_to_uci(rml.get_move_score(j))
                              << " depth " << (j <= i ? Iteration : Iteration - 1)
                              << " time " << current_search_time()
-                             << " nodes " << TM.nodes_searched()
+                             << " nodes " << ThreadsMgr.nodes_searched()
                              << " nps " << nps()
                              << " pv ";
 
@@ -967,7 +965,7 @@ namespace {
     assert(beta > alpha && beta <= VALUE_INFINITE);
     assert(PvNode || alpha == beta - 1);
     assert(ply > 0 && ply < PLY_MAX);
-    assert(pos.thread() >= 0 && pos.thread() < TM.active_threads());
+    assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
 
     Move movesSearched[256];
     EvalInfo ei;
@@ -986,7 +984,7 @@ namespace {
     oldAlpha = alpha;
 
     // Step 1. Initialize node and poll. Polling can abort search
-    TM.incrementNodeCounter(threadID);
+    ThreadsMgr.incrementNodeCounter(threadID);
     ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
     (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
 
@@ -997,7 +995,7 @@ namespace {
     }
 
     // Step 2. Check for aborted search and immediate draw
-    if (AbortSearch || TM.thread_should_stop(threadID))
+    if (AbortSearch || ThreadsMgr.thread_should_stop(threadID))
         return Value(0);
 
     if (pos.is_draw() || ply >= PLY_MAX - 1)
@@ -1188,7 +1186,7 @@ namespace {
     // Loop through all legal moves until no moves remain or a beta cutoff occurs
     while (   bestValue < beta
            && (move = mp.get_next_move()) != MOVE_NONE
-           && !TM.thread_should_stop(threadID))
+           && !ThreadsMgr.thread_should_stop(threadID))
     {
       assert(move_is_ok(move));
 
@@ -1354,14 +1352,14 @@ namespace {
 
       // Step 18. Check for split
       if (   depth >= MinimumSplitDepth
-          && TM.active_threads() > 1
+          && ThreadsMgr.active_threads() > 1
           && bestValue < beta
-          && TM.available_thread_exists(threadID)
+          && ThreadsMgr.available_thread_exists(threadID)
           && !AbortSearch
-          && !TM.thread_should_stop(threadID)
+          && !ThreadsMgr.thread_should_stop(threadID)
           && Iteration <= 99)
-          TM.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
-                              threatMove, mateThreat, &moveCount, &mp, PvNode);
+          ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
+                                      threatMove, mateThreat, &moveCount, &mp, PvNode);
     }
 
     // Step 19. Check for mate and stalemate
@@ -1374,7 +1372,7 @@ namespace {
     // Step 20. Update tables
     // If the search is not aborted, update the transposition table,
     // history counters, and killer moves.
-    if (AbortSearch || TM.thread_should_stop(threadID))
+    if (AbortSearch || ThreadsMgr.thread_should_stop(threadID))
         return bestValue;
 
     ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
@@ -1384,7 +1382,7 @@ namespace {
     // Update killers and history only for non capture moves that fails high
     if (bestValue >= beta)
     {
-        TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
+        ThreadsMgr.incrementBetaCounter(pos.side_to_move(), depth, threadID);
         if (!pos.move_is_capture_or_promotion(move))
         {
             update_history(pos, move, depth, movesSearched, moveCount);
@@ -1410,7 +1408,7 @@ namespace {
     assert(PvNode || alpha == beta - 1);
     assert(depth <= 0);
     assert(ply > 0 && ply < PLY_MAX);
-    assert(pos.thread() >= 0 && pos.thread() < TM.active_threads());
+    assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
 
     EvalInfo ei;
     StateInfo st;
@@ -1420,7 +1418,7 @@ namespace {
     const TTEntry* tte;
     Value oldAlpha = alpha;
 
-    TM.incrementNodeCounter(pos.thread());
+    ThreadsMgr.incrementNodeCounter(pos.thread());
     ss->bestMove = ss->currentMove = MOVE_NONE;
 
     // Check for an instant draw or maximum ply reached
@@ -1587,8 +1585,8 @@ namespace {
   template <NodeType PvNode>
   void sp_search(SplitPoint* sp, int threadID) {
 
-    assert(threadID >= 0 && threadID < TM.active_threads());
-    assert(TM.active_threads() > 1);
+    assert(threadID >= 0 && threadID < ThreadsMgr.active_threads());
+    assert(ThreadsMgr.active_threads() > 1);
 
     StateInfo st;
     Move move;
@@ -1610,7 +1608,7 @@ namespace {
 
     while (    sp->bestValue < sp->beta
            && (move = sp->mp->get_next_move()) != MOVE_NONE
-           && !TM.thread_should_stop(threadID))
+           && !ThreadsMgr.thread_should_stop(threadID))
     {
       moveCount = ++sp->moveCount;
       lock_release(&(sp->lock));
@@ -1719,7 +1717,7 @@ namespace {
       // Step 17. Check for new best move
       lock_grab(&(sp->lock));
 
-      if (value > sp->bestValue && !TM.thread_should_stop(threadID))
+      if (value > sp->bestValue && !ThreadsMgr.thread_should_stop(threadID))
       {
           sp->bestValue = value;
 
@@ -2071,7 +2069,7 @@ namespace {
   int nps() {
 
     int t = current_search_time();
-    return (t > 0 ? int((TM.nodes_searched() * 1000) / t) : 0);
+    return (t > 0 ? int((ThreadsMgr.nodes_searched() * 1000) / t) : 0);
   }
 
 
@@ -2128,7 +2126,7 @@ namespace {
         if (dbg_show_hit_rate)
             dbg_print_hit_rate();
 
-        cout << "info nodes " << TM.nodes_searched() << " nps " << nps()
+        cout << "info nodes " << ThreadsMgr.nodes_searched() << " nps " << nps()
              << " time " << t << endl;
     }
 
@@ -2138,14 +2136,14 @@ namespace {
 
     bool stillAtFirstMove =    FirstRootMove
                            && !AspirationFailLow
-                           &&  t > OptimumSearchTime + ExtraSearchTime;
+                           &&  t > TimeMgr.available_time();
 
-    bool noMoreTime =   t > MaximumSearchTime
+    bool noMoreTime =   t > TimeMgr.maximum_time()
                      || stillAtFirstMove;
 
     if (   (Iteration >= 3 && UseTimeManagement && noMoreTime)
         || (ExactMaxTime && t >= ExactMaxTime)
-        || (Iteration >= 3 && MaxNodes && TM.nodes_searched() >= MaxNodes))
+        || (Iteration >= 3 && MaxNodes && ThreadsMgr.nodes_searched() >= MaxNodes))
         AbortSearch = true;
   }
 
@@ -2161,9 +2159,9 @@ namespace {
 
     bool stillAtFirstMove =    FirstRootMove
                            && !AspirationFailLow
-                           &&  t > OptimumSearchTime + ExtraSearchTime;
+                           &&  t > TimeMgr.available_time();
 
-    bool noMoreTime =   t > MaximumSearchTime
+    bool noMoreTime =   t > TimeMgr.maximum_time()
                      || stillAtFirstMove;
 
     if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
@@ -2224,7 +2222,7 @@ namespace {
          << " score "     << value_to_uci(value)
          << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
          << " time "  << current_search_time()
-         << " nodes " << TM.nodes_searched()
+         << " nodes " << ThreadsMgr.nodes_searched()
          << " nps "   << nps()
          << " pv ";
 
@@ -2239,7 +2237,7 @@ namespace {
                       value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
 
         LogFile << pretty_pv(pos, current_search_time(), Iteration,
-                             TM.nodes_searched(), value, t, pv) << endl;
+                             ThreadsMgr.nodes_searched(), value, t, pv) << endl;
     }
   }
 
@@ -2308,7 +2306,7 @@ namespace {
 
   void* init_thread(void *threadID) {
 
-    TM.idle_loop(*(int*)threadID, NULL);
+    ThreadsMgr.idle_loop(*(int*)threadID, NULL);
     return NULL;
   }
 
@@ -2316,7 +2314,7 @@ namespace {
 
   DWORD WINAPI init_thread(LPVOID threadID) {
 
-    TM.idle_loop(*(int*)threadID, NULL);
+    ThreadsMgr.idle_loop(*(int*)threadID, NULL);
     return 0;
   }