X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=c4613ccd07e2ca23d639f8297e7602b336db7a88;hp=95e7019b18ccbe2811d9859a2951e9304cbb7172;hb=a3c1d64a5fdc525948bb388e0f426692d97cde65;hpb=ff41b8df764b352b450af572fa98097343b3f808 diff --git a/src/search.cpp b/src/search.cpp index 95e7019b..c4613ccd 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 { @@ -50,10 +52,9 @@ namespace { enum NodeType { Root, PV, NonPV, SplitPointPV, SplitPointNonPV }; // RootMove struct is used for moves at the root of the tree. For each root - // move, we store two scores, a node count, and a PV (really a refutation + // move, we store a pv_score, a node count, and a PV (really a refutation // in the case of moves which fail low). Value pv_score is normally set at - // -VALUE_INFINITE for all non-pv moves, while non_pv_score is computed - // according to the order in which moves are returned by MovePicker. + // -VALUE_INFINITE for all non-pv moves. struct RootMove { RootMove(); @@ -62,33 +63,21 @@ namespace { // RootMove::operator<() is the comparison function used when // sorting the moves. A move m1 is considered to be better - // than a move m2 if it has an higher pv_score, or if it has - // equal pv_score but m1 has the higher non_pv_score. In this way - // we are guaranteed that PV moves are always sorted as first. - bool operator<(const RootMove& m) const { - return pv_score != m.pv_score ? pv_score < m.pv_score - : non_pv_score < m.non_pv_score; - } + // than a move m2 if it has an higher pv_score + bool operator<(const RootMove& m) const { return pv_score < m.pv_score; } void extract_pv_from_tt(Position& pos); void insert_pv_in_tt(Position& pos); int64_t nodes; Value pv_score; - Value non_pv_score; Move pv[PLY_MAX_PLUS_2]; }; - // RootMoveList struct is just a vector of RootMove objects, - // with an handful of methods above the standard ones. + // RootMoveList struct is mainly a std::vector of RootMove objects struct RootMoveList : public std::vector { - - typedef std::vector Base; - void init(Position& pos, Move searchMoves[]); - void sort() { insertion_sort(begin(), end()); } - void sort_first(int n) { insertion_sort(begin(), begin() + n); } - + RootMove* find(const Move &m); int bestMoveChanges; }; @@ -217,10 +206,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(); @@ -231,8 +221,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 @@ -251,16 +239,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) { @@ -418,8 +396,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) @@ -464,7 +442,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()) @@ -579,6 +557,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++) @@ -596,7 +580,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. @@ -640,12 +624,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. @@ -733,7 +711,14 @@ namespace { if (PvNode && thread.maxPly < ss->ply) thread.maxPly = ss->ply; - if (SpNode) + // Step 1. Initialize node and poll. Polling can abort search + if (!SpNode) + { + ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE; + (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; + (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; + } + else { sp = ss->sp; tte = NULL; @@ -742,11 +727,6 @@ namespace { goto split_point_start; } - // Step 1. Initialize node and poll. Polling can abort search - ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE; - (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; - (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; - if (pos.thread() == 0 && ++NodesSincePoll > NodesBetweenPolls) { NodesSincePoll = 0; @@ -778,9 +758,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 @@ -944,7 +925,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; @@ -1198,14 +1179,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 @@ -1213,24 +1194,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. - Rml.sort_first(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 @@ -1553,7 +1525,8 @@ split_point_start: // At split points actual search starts from here bool connected_moves(const Position& pos, Move m1, Move m2) { Square f1, t1, f2, t2; - Piece p; + Piece p1, p2; + Square ksq; assert(m1 && move_is_ok(m1)); assert(m2 && move_is_ok(m2)); @@ -1571,26 +1544,24 @@ split_point_start: // At split points actual search starts from here return true; // Case 3: Moving through the vacated square - if ( piece_is_slider(pos.piece_on(f2)) + p2 = pos.piece_on(f2); + if ( piece_is_slider(p2) && bit_is_set(squares_between(f2, t2), f1)) return true; // Case 4: The destination square for m2 is defended by the moving piece in m1 - p = pos.piece_on(t1); - if (bit_is_set(pos.attacks_from(p, t1), t2)) + p1 = pos.piece_on(t1); + if (bit_is_set(pos.attacks_from(p1, t1), t2)) return true; // Case 5: Discovered check, checking piece is the piece moved in m1 - if ( piece_is_slider(p) - && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2) - && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2)) + ksq = pos.king_square(pos.side_to_move()); + if ( piece_is_slider(p1) + && bit_is_set(squares_between(t1, ksq), f2)) { - // discovered_check_candidates() works also if the Position's side to - // move is the opposite of the checking piece. - Color them = opposite_color(pos.side_to_move()); - Bitboard dcCandidates = pos.discovered_check_candidates(them); - - if (bit_is_set(dcCandidates, f2)) + Bitboard occ = pos.occupied_squares(); + clear_bit(&occ, f2); + if (bit_is_set(pos.attacks_from(p1, t1, occ), ksq)) return true; } return false; @@ -1757,7 +1728,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; @@ -1775,7 +1746,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(); @@ -1790,11 +1761,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 << " "; @@ -1805,7 +1776,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; @@ -1820,6 +1791,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 @@ -1834,7 +1888,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") { @@ -1909,7 +1963,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) @@ -1969,7 +2023,7 @@ split_point_start: // At split points actual search starts from here RootMove::RootMove() { nodes = 0; - pv_score = non_pv_score = -VALUE_INFINITE; + pv_score = -VALUE_INFINITE; pv[0] = MOVE_NONE; } @@ -1983,7 +2037,6 @@ split_point_start: // At split points actual search starts from here nodes = rm.nodes; pv_score = rm.pv_score; - non_pv_score = rm.non_pv_score; return *this; } @@ -2011,6 +2064,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 @@ -2029,7 +2093,7 @@ split_point_start: // At split points actual search starts from here while ( (tte = TT.probe(pos.get_key())) != NULL && tte->move() != MOVE_NONE && pos.move_is_pl(tte->move()) - && pos.pl_move_is_legal(tte->move(), pos.pinned_pieces(pos.side_to_move())) + && pos.pl_move_is_legal(tte->move(), pos.pinned_pieces()) && ply < PLY_MAX && (!pos.is_draw() || ply < 2)) { @@ -2071,29 +2135,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; - } - - Rml.sort(); - } - } // namespace