X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=1b98627e9bf1749e6e5ebb04370fdd09539c0016;hb=3835f49aa10af094642d94b1765183c8bffd561b;hp=fceaccb524fec10493a68961222ccd7a225e49d8;hpb=d2a4aac53d8eb2cf21e0b8f1154412b1edd5afae;p=stockfish

diff --git a/src/search.cpp b/src/search.cpp
index fceaccb5..1b98627e 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -127,33 +127,16 @@ namespace {
                                     : non_pv_score < m.non_pv_score;
     }
 
+    void extract_pv_from_tt(Position& pos);
+    void insert_pv_in_tt(Position& pos);
+    std::string pv_info_to_uci(const Position& pos, Value alpha, Value beta, int pvLine = 0);
+
     int64_t nodes;
     Value pv_score;
     Value non_pv_score;
     Move pv[PLY_MAX_PLUS_2];
   };
 
-  RootMove::RootMove() {
-
-    nodes = 0;
-    pv_score = non_pv_score = -VALUE_INFINITE;
-    pv[0] = MOVE_NONE;
-  }
-
-  RootMove& RootMove::operator=(const RootMove& rm) {
-
-    const Move* src = rm.pv;
-    Move* dst = pv;
-
-    // Avoid a costly full rm.pv[] copy
-    do *dst++ = *src; while (*src++ != MOVE_NONE);
-
-    nodes = rm.nodes;
-    pv_score = rm.pv_score;
-    non_pv_score = rm.non_pv_score;
-    return *this;
-  }
-
 
   // RootMoveList struct is essentially a std::vector<> of RootMove objects,
   // with an handful of methods above the standard ones.
@@ -292,8 +275,8 @@ namespace {
 
   /// Local functions
 
-  Value id_loop(Position& pos, Move searchMoves[]);
-  Value root_search(Position& pos, SearchStack* ss, RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
+  Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove);
+  Value root_search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, RootMoveList& rml);
 
   template <NodeType PvNode, bool SpNode>
   Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
@@ -330,9 +313,6 @@ namespace {
   void ponderhit();
   void wait_for_stop_or_ponderhit();
   void init_ss_array(SearchStack* ss, int size);
-  void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value);
-  void insert_pv_in_tt(const Position& pos, Move pv[]);
-  void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]);
 
 #if !defined(_MSC_VER)
   void* init_thread(void* threadID);
@@ -511,7 +491,32 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[
               << " moves to go: " << movesToGo << endl;
 
   // We're ready to start thinking. Call the iterative deepening loop function
-  id_loop(pos, searchMoves);
+  Move ponderMove = MOVE_NONE;
+  Move bestMove = id_loop(pos, searchMoves, &ponderMove);
+
+  // Print final search statistics
+  cout << "info nodes " << pos.nodes_searched()
+       << " nps " << nps(pos)
+       << " time " << current_search_time() << endl;
+
+  if (UseLogFile)
+  {
+      if (dbg_show_mean)
+          dbg_print_mean(LogFile);
+
+      if (dbg_show_hit_rate)
+          dbg_print_hit_rate(LogFile);
+
+      LogFile << "\nNodes: " << pos.nodes_searched()
+              << "\nNodes/second: " << nps(pos)
+              << "\nBest move: " << move_to_san(pos, bestMove);
+
+      StateInfo st;
+      pos.do_move(bestMove, st);
+      LogFile << "\nPonder move: "
+              << move_to_san(pos, ponderMove) // Works also with MOVE_NONE
+              << endl;
+  }
 
   if (UseLogFile)
       LogFile.close();
@@ -519,6 +524,14 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[
   // This makes all the threads to go to sleep
   ThreadsMgr.set_active_threads(1);
 
+  // If we are pondering or in infinite search, we shouldn't print the
+  // best move before we are told to do so.
+  if (!AbortSearch && (PonderSearch || InfiniteSearch))
+      wait_for_stop_or_ponderhit();
+
+  // Could be both MOVE_NONE when searching on a stalemate position
+  cout << "bestmove " << bestMove << " ponder " << ponderMove << endl;
+
   return !Quit;
 }
 
@@ -530,34 +543,26 @@ namespace {
   // been consumed, the user stops the search, or the maximum search depth is
   // reached.
 
-  Value id_loop(Position& pos, Move searchMoves[]) {
+  Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove) {
 
     SearchStack ss[PLY_MAX_PLUS_2];
+    Depth depth;
     Move EasyMove = MOVE_NONE;
     Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
 
-    // Moves to search are verified, copied, scored and sorted
+    // Moves to search are verified, scored and sorted
     RootMoveList rml(pos, searchMoves);
 
     // Handle special case of searching on a mate/stale position
     if (rml.size() == 0)
     {
-        if (PonderSearch)
-            wait_for_stop_or_ponderhit();
+        Value s = (pos.is_check() ? -VALUE_MATE : VALUE_DRAW);
 
-        return pos.is_check() ? -VALUE_MATE : VALUE_DRAW;
-    }
+        cout << "info depth " << 1
+             << " score " << value_to_uci(s) << endl;
 
-    // Print RootMoveList startup scoring to the standard output,
-    // so to output information also for iteration 1.
-    cout << set960(pos.is_chess960()) // Is enough to set once at the beginning
-         << "info depth " << 1
-         << "\ninfo depth " << 1
-         << " score " << value_to_uci(rml[0].pv_score)
-         << " time " << current_search_time()
-         << " nodes " << pos.nodes_searched()
-         << " nps " << nps(pos)
-         << " pv " << rml[0].pv[0] << "\n";
+        return MOVE_NONE;
+    }
 
     // Initialize
     TT.new_search();
@@ -566,6 +571,11 @@ namespace {
     ValueByIteration[1] = rml[0].pv_score;
     Iteration = 1;
 
+    // Send initial RootMoveList scoring (iteration 1)
+    cout << set960(pos.is_chess960()) // Is enough to set once at the beginning
+         << "info depth " << Iteration
+         << "\n" << rml[0].pv_info_to_uci(pos, alpha, beta) << endl;
+
     // Is one move significantly better than others after initial scoring ?
     if (   rml.size() == 1
         || rml[0].pv_score > rml[1].pv_score + EasyMoveMargin)
@@ -593,8 +603,10 @@ namespace {
             beta  = Min(ValueByIteration[Iteration - 1] + AspirationDelta,  VALUE_INFINITE);
         }
 
-        // Search to the current depth, rml is updated and sorted, alpha and beta could change
-        value = root_search(pos, ss, rml, &alpha, &beta);
+        depth = (Iteration - 2) * ONE_PLY + InitialDepth;
+
+        // Search to the current depth, rml is updated and sorted
+        value = root_search(pos, ss, alpha, beta, depth, rml);
 
         if (AbortSearch)
             break; // Value cannot be trusted. Break out immediately!
@@ -655,67 +667,29 @@ namespace {
             break;
     }
 
-    // If we are pondering or in infinite search, we shouldn't print the
-    // best move before we are told to do so.
-    if (!AbortSearch && (PonderSearch || InfiniteSearch))
-        wait_for_stop_or_ponderhit();
-    else
-        // Print final search statistics
-        cout << "info nodes " << pos.nodes_searched()
-             << " nps " << nps(pos)
-             << " time " << current_search_time() << endl;
-
-    // Print the best move and the ponder move to the standard output
-    cout << "bestmove " << rml[0].pv[0];
-
-    if (rml[0].pv[1] != MOVE_NONE)
-        cout << " ponder " << rml[0].pv[1];
-
-    cout << endl;
-
-    if (UseLogFile)
-    {
-        if (dbg_show_mean)
-            dbg_print_mean(LogFile);
-
-        if (dbg_show_hit_rate)
-            dbg_print_hit_rate(LogFile);
-
-        LogFile << "\nNodes: " << pos.nodes_searched()
-                << "\nNodes/second: " << nps(pos)
-                << "\nBest move: " << move_to_san(pos, rml[0].pv[0]);
-
-        StateInfo st;
-        pos.do_move(rml[0].pv[0], st);
-        LogFile << "\nPonder move: "
-                << move_to_san(pos, rml[0].pv[1]) // Works also with MOVE_NONE
-                << endl;
-    }
-    return rml[0].pv_score;
+    *ponderMove = rml[0].pv[1];
+    return rml[0].pv[0];
   }
 
 
   // root_search() is the function which searches the root node. It is
-  // similar to search_pv except that it uses a different move ordering
-  // scheme, prints some information to the standard output and handles
-  // the fail low/high loops.
-
-  Value root_search(Position& pos, SearchStack* ss, RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
+  // similar to search_pv except that it prints some information to the
+  // standard output and handles the fail low/high loops.
 
+  Value root_search(Position& pos, SearchStack* ss, Value alpha,
+                    Value beta, Depth depth, RootMoveList& rml) {
     StateInfo st;
     CheckInfo ci(pos);
     int64_t nodes;
     Move move;
-    Depth depth, ext, newDepth;
-    Value value, alpha, beta;
+    Depth ext, newDepth;
+    Value value, oldAlpha;
     bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
     int researchCountFH, researchCountFL;
 
     researchCountFH = researchCountFL = 0;
-    alpha = *alphaPtr;
-    beta = *betaPtr;
+    oldAlpha = alpha;
     isCheck = pos.is_check();
-    depth = (Iteration - 2) * ONE_PLY + InitialDepth;
 
     // Step 1. Initialize node (polling is omitted at root)
     ss->currentMove = ss->bestMove = MOVE_NONE;
@@ -836,15 +810,15 @@ namespace {
 
                 // We are failing high and going to do a research. It's important to update
                 // the score before research in case we run out of time while researching.
-                rml[i].pv_score = value;
                 ss->bestMove = move;
-                extract_pv_from_tt(pos, move, rml[i].pv);
+                rml[i].pv_score = value;
+                rml[i].extract_pv_from_tt(pos);
 
-                // Print information to the standard output
-                print_pv_info(pos, rml[i].pv, alpha, beta, value);
+                // Inform GUI that PV has changed
+                cout << rml[i].pv_info_to_uci(pos, alpha, beta) << endl;
 
                 // Prepare for a research after a fail high, each time with a wider window
-                *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
+                beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
                 researchCountFH++;
 
             } // End of fail high loop
@@ -871,61 +845,50 @@ namespace {
                 // PV move or new best move!
 
                 // Update PV
-                rml[i].pv_score = value;
                 ss->bestMove = move;
-                extract_pv_from_tt(pos, move, rml[i].pv);
+                rml[i].pv_score = value;
+                rml[i].extract_pv_from_tt(pos);
 
-                if (MultiPV == 1)
-                {
-                    // We record how often the best move has been changed in each
-                    // iteration. This information is used for time managment: When
-                    // the best move changes frequently, we allocate some more time.
-                    if (i > 0)
-                        BestMoveChangesByIteration[Iteration]++;
+                // We record how often the best move has been changed in each
+                // iteration. This information is used for time managment: When
+                // the best move changes frequently, we allocate some more time.
+                if (MultiPV == 1 && i > 0)
+                    BestMoveChangesByIteration[Iteration]++;
+
+                // Inform GUI that PV has changed, in case of multi-pv UCI protocol
+                // requires we send all the PV lines properly sorted.
+                rml.sort_multipv(i);
 
-                    // Print information to the standard output
-                    print_pv_info(pos, rml[i].pv, alpha, beta, value);
+                for (int j = 0; j < Min(MultiPV, (int)rml.size()); j++)
+                    cout << rml[j].pv_info_to_uci(pos, alpha, beta, j) << endl;
 
+                // Update alpha. In multi-pv we don't use aspiration window
+                if (MultiPV == 1)
+                {
                     // Raise alpha to setup proper non-pv search upper bound
                     if (value > alpha)
                         alpha = value;
                 }
-                else // MultiPV > 1
-                {
-                    rml.sort_multipv(i);
-                    for (int j = 0; j < Min(MultiPV, (int)rml.size()); j++)
-                    {
-                        cout << "info multipv " << j + 1
-                             << " score " << value_to_uci(rml[j].pv_score)
-                             << " depth " << (j <= i ? Iteration : Iteration - 1)
-                             << " time " << current_search_time()
-                             << " nodes " << pos.nodes_searched()
-                             << " nps " << nps(pos)
-                             << " pv ";
-
-                        for (int k = 0; rml[j].pv[k] != MOVE_NONE && k < PLY_MAX; k++)
-                            cout << rml[j].pv[k] << " ";
-
-                        cout << endl;
-                    }
+                else // Set alpha equal to minimum score among the PV lines
                     alpha = rml[Min(i, MultiPV - 1)].pv_score;
-                }
+
             } // PV move or new best move
 
-            assert(alpha >= *alphaPtr);
+            assert(alpha >= oldAlpha);
 
-            AspirationFailLow = (alpha == *alphaPtr);
+            AspirationFailLow = (alpha == oldAlpha);
 
             if (AspirationFailLow && StopOnPonderhit)
                 StopOnPonderhit = false;
-        }
+
+        } // Root moves loop
 
         // Can we exit fail low loop ?
         if (AbortSearch || !AspirationFailLow)
             break;
 
         // Prepare for a research after a fail low, each time with a wider window
-        *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
+        oldAlpha = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
         researchCountFL++;
 
     } // Fail low loop
@@ -933,9 +896,10 @@ namespace {
     // Sort the moves before to return
     rml.sort();
 
-    // Write PV to transposition table, in case the relevant entries have
-    // been overwritten during the search.
-    insert_pv_in_tt(pos, rml[0].pv);
+    // Write PV lines to transposition table, in case the relevant entries
+    // have been overwritten during the search.
+    for (int i = 0; i < MultiPV; i++)
+        rml[i].insert_pv_in_tt(pos);
 
     return alpha;
   }
@@ -1967,14 +1931,19 @@ split_point_start: // At split points actual search starts from here
   }
 
 
-  // value_to_uci() converts a value to a string suitable for use with the UCI protocol
+  // value_to_uci() converts a value to a string suitable for use with the UCI
+  // protocol specifications:
+  //
+  // cp <x>     The score from the engine's point of view in centipawns.
+  // mate <y>   Mate in y moves, not plies. If the engine is getting mated
+  //            use negative values for y.
 
   std::string value_to_uci(Value v) {
 
     std::stringstream s;
 
     if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
-      s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100
+      s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to centipawns
     else
       s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
 
@@ -2131,88 +2100,6 @@ split_point_start: // At split points actual search starts from here
   }
 
 
-  // print_pv_info() prints to standard output and eventually to log file information on
-  // the current PV line. It is called at each iteration or after a new pv is found.
-
-  void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) {
-
-    cout << "info depth " << Iteration
-         << " score "     << value_to_uci(value)
-         << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
-         << " time "  << current_search_time()
-         << " nodes " << pos.nodes_searched()
-         << " nps "   << nps(pos)
-         << " pv ";
-
-    for (Move* m = pv; *m != MOVE_NONE; m++)
-        cout << *m << " ";
-
-    cout << endl;
-
-    if (UseLogFile)
-    {
-        ValueType t = value >= beta  ? VALUE_TYPE_LOWER :
-                      value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
-
-        LogFile << pretty_pv(pos, current_search_time(), Iteration, value, t, pv) << endl;
-    }
-  }
-
-
-  // insert_pv_in_tt() is called at the end of a search iteration, and inserts
-  // the PV back into the TT. This makes sure the old PV moves are searched
-  // first, even if the old TT entries have been overwritten.
-
-  void insert_pv_in_tt(const Position& pos, Move pv[]) {
-
-    StateInfo st;
-    TTEntry* tte;
-    Position p(pos, pos.thread());
-    Value v, m = VALUE_NONE;
-
-    for (int i = 0; pv[i] != MOVE_NONE; i++)
-    {
-        tte = TT.retrieve(p.get_key());
-        if (!tte || tte->move() != pv[i])
-        {
-            v = (p.is_check() ? VALUE_NONE : evaluate(p, m));
-            TT.store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[i], v, m);
-        }
-        p.do_move(pv[i], st);
-    }
-  }
-
-
-  // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
-  // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
-  // allow to always have a ponder move even when we fail high at root and also a
-  // long PV to print that is important for position analysis.
-
-  void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]) {
-
-    StateInfo st;
-    TTEntry* tte;
-    Position p(pos, pos.thread());
-    int ply = 0;
-
-    assert(bestMove != MOVE_NONE);
-
-    pv[ply] = bestMove;
-    p.do_move(pv[ply++], st);
-
-    while (   (tte = TT.retrieve(p.get_key())) != NULL
-           && tte->move() != MOVE_NONE
-           && move_is_legal(p, tte->move())
-           && ply < PLY_MAX
-           && (!p.is_draw() || ply < 2))
-    {
-        pv[ply] = tte->move();
-        p.do_move(pv[ply++], st);
-    }
-    pv[ply] = MOVE_NONE;
-  }
-
-
   // init_thread() is the function which is called when a new thread is
   // launched. It simply calls the idle_loop() function with the supplied
   // threadID. There are two versions of this function; one for POSIX
@@ -2640,7 +2527,119 @@ split_point_start: // At split points actual search starts from here
   }
 
 
-  /// The RootMoveList class
+  /// RootMove and RootMoveList method's definitions
+
+  RootMove::RootMove() {
+
+    nodes = 0;
+    pv_score = non_pv_score = -VALUE_INFINITE;
+    pv[0] = MOVE_NONE;
+  }
+
+  RootMove& RootMove::operator=(const RootMove& rm) {
+
+    const Move* src = rm.pv;
+    Move* dst = pv;
+
+    // Avoid a costly full rm.pv[] copy
+    do *dst++ = *src; while (*src++ != MOVE_NONE);
+
+    nodes = rm.nodes;
+    pv_score = rm.pv_score;
+    non_pv_score = rm.non_pv_score;
+    return *this;
+  }
+
+  // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
+  // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
+  // allow to always have a ponder move even when we fail high at root and also a
+  // long PV to print that is important for position analysis.
+
+  void RootMove::extract_pv_from_tt(Position& pos) {
+
+    StateInfo state[PLY_MAX_PLUS_2], *st = state;
+    TTEntry* tte;
+    int ply = 1;
+
+    assert(pv[0] != MOVE_NONE && move_is_legal(pos, pv[0]));
+
+    pos.do_move(pv[0], *st++);
+
+    while (   (tte = TT.retrieve(pos.get_key())) != NULL
+           && tte->move() != MOVE_NONE
+           && move_is_legal(pos, tte->move())
+           && ply < PLY_MAX
+           && (!pos.is_draw() || ply < 2))
+    {
+        pv[ply] = tte->move();
+        pos.do_move(pv[ply++], *st++);
+    }
+    pv[ply] = MOVE_NONE;
+
+    do pos.undo_move(pv[--ply]); while (ply);
+  }
+
+  // insert_pv_in_tt() is called at the end of a search iteration, and inserts
+  // the PV back into the TT. This makes sure the old PV moves are searched
+  // first, even if the old TT entries have been overwritten.
+
+  void RootMove::insert_pv_in_tt(Position& pos) {
+
+    StateInfo state[PLY_MAX_PLUS_2], *st = state;
+    TTEntry* tte;
+    Key k;
+    Value v, m = VALUE_NONE;
+    int ply = 0;
+
+    assert(pv[0] != MOVE_NONE && move_is_legal(pos, pv[0]));
+
+    do {
+        k = pos.get_key();
+        tte = TT.retrieve(k);
+
+        // Don't overwrite exsisting correct entries
+        if (!tte || tte->move() != pv[ply])
+        {
+            v = (pos.is_check() ? VALUE_NONE : evaluate(pos, m));
+            TT.store(k, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[ply], v, m);
+        }
+        pos.do_move(pv[ply], *st++);
+
+    } while (pv[++ply] != MOVE_NONE);
+
+    do pos.undo_move(pv[--ply]); while (ply);
+  }
+
+  // pv_info_to_uci() returns a string with information on the current PV line
+  // formatted according to UCI specification and eventually writes the info
+  // to a log file. It is called at each iteration or after a new pv is found.
+
+  std::string RootMove::pv_info_to_uci(const Position& pos, Value alpha, Value beta, int pvLine) {
+
+    std::stringstream s;
+
+    s << "info depth " << Iteration // FIXME
+      << " multipv " << pvLine + 1
+      << " score " << value_to_uci(pv_score)
+      << (pv_score >= beta ? " lowerbound" : pv_score <= alpha ? " upperbound" : "")
+      << " time "  << current_search_time()
+      << " nodes " << pos.nodes_searched()
+      << " nps "   << nps(pos)
+      << " pv ";
+
+    for (Move* m = pv; *m != MOVE_NONE; m++)
+        s << *m << " ";
+
+    if (UseLogFile && pvLine == 0)
+    {
+        ValueType t = pv_score >= beta  ? VALUE_TYPE_LOWER :
+                      pv_score <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
+
+        LogFile << pretty_pv(pos, current_search_time(), Iteration, pv_score, t, pv) << endl;
+    }
+    return s.str();
+  }
+
 
   RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) {