X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=f600876e98e69ddd9aee98ac6c45ee14c377ce2a;hb=ce24a229df4ddc7a9870515b5b710f259dcd50e3;hp=94b34389178f0f18119d010bea23c8bdebf3d06e;hpb=69f4954df1de3ed264212a6e871986781d717e08;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index 94b34389..f600876e 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -21,6 +21,7 @@ #include #include #include +#include #include #include #include @@ -40,6 +41,7 @@ using std::cout; using std::endl; +using std::string; namespace { @@ -82,6 +84,7 @@ namespace { // RootMoveList struct is mainly a std::vector of RootMove objects struct RootMoveList : public std::vector { void init(Position& pos, Move searchMoves[]); + RootMove* find(const Move &m); int bestMoveChanges; }; @@ -210,10 +213,11 @@ namespace { void do_skill_level(Move* best, Move* ponder); int current_search_time(int set = 0); - std::string score_to_uci(Value v, Value alpha, Value beta); - std::string speed_to_uci(int64_t nodes); - std::string pv_to_uci(Move pv[], int pvNum); - std::string depth_to_uci(Depth depth); + string score_to_uci(Value v, Value alpha, Value beta); + string speed_to_uci(int64_t nodes); + string pv_to_uci(Move pv[], int pvNum, bool chess960); + string pretty_pv(Position& pos, int depth, Value score, int time, Move pv[]); + string depth_to_uci(Depth depth); void poll(const Position& pos); void wait_for_stop_or_ponderhit(); @@ -224,8 +228,6 @@ namespace { MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) : MovePicker(p, ttm, d, h, ss, b) {} - - RootMove& current() { assert(false); return Rml[0]; } // Dummy, needed to compile }; // In case of a SpNode we use split point's shared MovePicker object as moves source @@ -244,16 +246,6 @@ namespace { : MovePickerExt(p, ttm, d, h, ss, b) {} }; - // In case of a Root node we use RootMoveList as moves source - template<> struct MovePickerExt : public MovePicker { - - MovePickerExt(const Position&, Move, Depth, const History&, SearchStack*, Value); - RootMove& current() { return Rml[cur]; } - Move get_next_move() { return ++cur < (int)Rml.size() ? Rml[cur].pv[0] : MOVE_NONE; } - - int cur; - }; - // Overload operator<<() to make it easier to print moves in a coordinate // notation compatible with UCI protocol. std::ostream& operator<<(std::ostream& os, Move m) { @@ -411,8 +403,8 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { // Look for a book move if (Options["OwnBook"].value()) { - if (Options["Book File"].value() != book.name()) - book.open(Options["Book File"].value()); + if (Options["Book File"].value() != book.name()) + book.open(Options["Book File"].value()); Move bookMove = book.get_move(pos, Options["Best Book Move"].value()); if (bookMove != MOVE_NONE) @@ -457,7 +449,7 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { // Write to log file and keep it open to be accessed during the search if (Options["Use Search Log"].value()) { - std::string name = Options["Search Log Filename"].value(); + string name = Options["Search Log Filename"].value(); LogFile.open(name.c_str(), std::ios::out | std::ios::app); if (LogFile.is_open()) @@ -572,6 +564,12 @@ namespace { // Search starting from ss+1 to allow calling update_gains() value = search(pos, ss+1, alpha, beta, depth * ONE_PLY); + // It is critical that sorting is done with a stable algorithm + // because all the values but the first are usually set to + // -VALUE_INFINITE and we want to keep the same order for all + // the moves but the new PV that goes to head. + sort(Rml.begin(), Rml.end()); + // Write PV back to transposition table in case the relevant entries // have been overwritten during the search. for (int i = 0; i < Min(MultiPV, (int)Rml.size()); i++) @@ -589,7 +587,7 @@ namespace { << depth_to_uci(depth * ONE_PLY) << score_to_uci(Rml[i].pv_score, alpha, beta) << speed_to_uci(pos.nodes_searched()) - << pv_to_uci(Rml[i].pv, i + 1) << endl; + << pv_to_uci(Rml[i].pv, i + 1, pos.is_chess960()) << endl; // In case of failing high/low increase aspiration window and research, // otherwise exit the fail high/low loop. @@ -633,12 +631,6 @@ namespace { // Check for some early stop condition if (!StopRequest && Limits.useTimeManagement()) { - // Stop search early when the last two iterations returned a mate score - if ( depth >= 5 - && abs(bestValues[depth]) >= VALUE_MATE_IN_PLY_MAX - && abs(bestValues[depth - 1]) >= VALUE_MATE_IN_PLY_MAX) - StopRequest = true; - // Stop search early if one move seems to be much better than the // others or if there is only a single legal move. Also in the latter // case we search up to some depth anyway to get a proper score. @@ -773,9 +765,10 @@ namespace { // At PV nodes we check for exact scores, while at non-PV nodes we check for // a fail high/low. Biggest advantage at probing at PV nodes is to have a - // smooth experience in analysis mode. - if (tte && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT - : ok_to_use_TT(tte, depth, beta, ss->ply))) + // smooth experience in analysis mode. We don't probe at Root nodes otherwise + // we should also update RootMoveList to avoid bogus output. + if (!RootNode && tte && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT + : ok_to_use_TT(tte, depth, beta, ss->ply))) { TT.refresh(tte); ss->bestMove = ttMove; // Can be MOVE_NONE @@ -939,7 +932,7 @@ namespace { split_point_start: // At split points actual search starts from here // Initialize a MovePicker object for the current position - MovePickerExt mp(pos, ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta); + MovePickerExt mp(pos, RootNode ? Rml[0].pv[0] : ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta); CheckInfo ci(pos); ss->bestMove = MOVE_NONE; futilityBase = ss->eval + ss->evalMargin; @@ -1193,14 +1186,14 @@ split_point_start: // At split points actual search starts from here break; // Remember searched nodes counts for this move - mp.current().nodes += pos.nodes_searched() - nodes; + Rml.find(move)->nodes += pos.nodes_searched() - nodes; // PV move or new best move ? if (isPvMove || value > alpha) { // Update PV - mp.current().pv_score = value; - mp.current().extract_pv_from_tt(pos); + Rml.find(move)->pv_score = value; + Rml.find(move)->extract_pv_from_tt(pos); // We record how often the best move has been changed in each // iteration. This information is used for time management: When @@ -1208,24 +1201,15 @@ split_point_start: // At split points actual search starts from here if (!isPvMove && MultiPV == 1) Rml.bestMoveChanges++; - // It is critical that sorting is done with a stable algorithm - // because all the values but the first are usually set to - // -VALUE_INFINITE and we want to keep the same order for all - // the moves but the new PV that goes to head. - sort(Rml.begin(), Rml.begin() + moveCount); - - // Update alpha. In multi-pv we don't use aspiration window, so set - // alpha equal to minimum score among the PV lines searched so far. - if (MultiPV > 1) - alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score; - else if (value > alpha) + // Update alpha. + if (value > alpha) alpha = value; } else // All other moves but the PV are set to the lowest value, this // is not a problem when sorting becuase sort is stable and move // position in the list is preserved, just the PV is pushed up. - mp.current().pv_score = -VALUE_INFINITE; + Rml.find(move)->pv_score = -VALUE_INFINITE; } // RootNode @@ -1751,7 +1735,7 @@ split_point_start: // At split points actual search starts from here // mate Mate in y moves, not plies. If the engine is getting mated // use negative values for y. - std::string score_to_uci(Value v, Value alpha, Value beta) { + string score_to_uci(Value v, Value alpha, Value beta) { std::stringstream s; @@ -1769,7 +1753,7 @@ split_point_start: // At split points actual search starts from here // speed_to_uci() returns a string with time stats of current search suitable // to be sent to UCI gui. - std::string speed_to_uci(int64_t nodes) { + string speed_to_uci(int64_t nodes) { std::stringstream s; int t = current_search_time(); @@ -1784,11 +1768,11 @@ split_point_start: // At split points actual search starts from here // pv_to_uci() returns a string with information on the current PV line // formatted according to UCI specification. - std::string pv_to_uci(Move pv[], int pvNum) { + string pv_to_uci(Move pv[], int pvNum, bool chess960) { std::stringstream s; - s << " multipv " << pvNum << " pv "; + s << " multipv " << pvNum << " pv " << set960(chess960); for ( ; *pv != MOVE_NONE; pv++) s << *pv << " "; @@ -1799,7 +1783,7 @@ split_point_start: // At split points actual search starts from here // depth_to_uci() returns a string with information on the current depth and // seldepth formatted according to UCI specification. - std::string depth_to_uci(Depth depth) { + string depth_to_uci(Depth depth) { std::stringstream s; @@ -1814,6 +1798,89 @@ split_point_start: // At split points actual search starts from here return s.str(); } + string time_to_string(int millisecs) { + + const int MSecMinute = 1000 * 60; + const int MSecHour = 1000 * 60 * 60; + + int hours = millisecs / MSecHour; + int minutes = (millisecs % MSecHour) / MSecMinute; + int seconds = ((millisecs % MSecHour) % MSecMinute) / 1000; + + std::stringstream s; + + if (hours) + s << hours << ':'; + + s << std::setfill('0') << std::setw(2) << minutes << ':' << std::setw(2) << seconds; + return s.str(); + } + + string score_to_string(Value v) { + + std::stringstream s; + + if (v >= VALUE_MATE_IN_PLY_MAX) + s << "#" << (VALUE_MATE - v + 1) / 2; + else if (v <= VALUE_MATED_IN_PLY_MAX) + s << "-#" << (VALUE_MATE + v) / 2; + else + s << std::setprecision(2) << std::fixed << std::showpos << float(v) / PawnValueMidgame; + + return s.str(); + } + + // pretty_pv() creates a human-readable string from a position and a PV. + // It is used to write search information to the log file (which is created + // when the UCI parameter "Use Search Log" is "true"). + + string pretty_pv(Position& pos, int depth, Value value, int time, Move pv[]) { + + const int64_t K = 1000; + const int64_t M = 1000000; + const int startColumn = 28; + const size_t maxLength = 80 - startColumn; + + StateInfo state[PLY_MAX_PLUS_2], *st = state; + Move* m = pv; + string san; + std::stringstream s; + size_t length = 0; + + // First print depth, score, time and searched nodes... + s << set960(pos.is_chess960()) + << std::setw(2) << depth + << std::setw(8) << score_to_string(value) + << std::setw(8) << time_to_string(time); + + if (pos.nodes_searched() < M) + s << std::setw(8) << pos.nodes_searched() / 1 << " "; + else if (pos.nodes_searched() < K * M) + s << std::setw(7) << pos.nodes_searched() / K << "K "; + else + s << std::setw(7) << pos.nodes_searched() / M << "M "; + + // ...then print the full PV line in short algebraic notation + while (*m != MOVE_NONE) + { + san = move_to_san(pos, *m); + length += san.length() + 1; + + if (length > maxLength) + { + length = san.length() + 1; + s << "\n" + string(startColumn, ' '); + } + s << san << ' '; + + pos.do_move(*m++, *st++); + } + + // Restore original position before to leave + while (m != pv) pos.undo_move(*--m); + + return s.str(); + } // poll() performs two different functions: It polls for user input, and it // looks at the time consumed so far and decides if it's time to abort the @@ -1828,7 +1895,7 @@ split_point_start: // At split points actual search starts from here if (input_available()) { // We are line oriented, don't read single chars - std::string command; + string command; if (!std::getline(std::cin, command) || command == "quit") { @@ -1903,7 +1970,7 @@ split_point_start: // At split points actual search starts from here void wait_for_stop_or_ponderhit() { - std::string command; + string command; // Wait for a command from stdin while ( std::getline(std::cin, command) @@ -2005,6 +2072,17 @@ split_point_start: // At split points actual search starts from here } } + RootMove* RootMoveList::find(const Move &m) { + + for (int i = 0; i < int(size()); i++) + { + if ((*this)[i].pv[0] == m) + return &(*this)[i]; + } + + return NULL; + } + // 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 @@ -2065,29 +2143,6 @@ split_point_start: // At split points actual search starts from here do pos.undo_move(pv[--ply]); while (ply); } - - // Specializations for MovePickerExt in case of Root node - MovePickerExt::MovePickerExt(const Position& p, Move ttm, Depth d, - const History& h, SearchStack* ss, Value b) - : MovePicker(p, ttm, d, h, ss, b), cur(-1) { - Move move; - Value score = VALUE_ZERO; - - // Score root moves using standard ordering used in main search, the moves - // are scored according to the order in which they are returned by MovePicker. - // This is the second order score that is used to compare the moves when - // the first orders pv_score of both moves are equal. - while ((move = MovePicker::get_next_move()) != MOVE_NONE) - for (RootMoveList::iterator rm = Rml.begin(); rm != Rml.end(); ++rm) - if (rm->pv[0] == move) - { - rm->non_pv_score = score--; - break; - } - - sort(Rml.begin(), Rml.end()); - } - } // namespace