X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=4304298c73eb4783a7f45e4c20b488f3aa8f567e;hb=35fa4fc71f7cf7b8f7ffc8a8c22f60048be99f86;hp=bdb64ab5ea1cd300e8f69b3ccffb12bca37633a4;hpb=8fa53a5b92bdfce4613ef04b88715ec9ccd9864c;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index bdb64ab5..4304298c 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -150,7 +150,7 @@ namespace { // Easy move margin. An easy move candidate must be at least this much // better than the second best move. - const Value EasyMoveMargin = Value(0x200); + const Value EasyMoveMargin = Value(0x150); /// Namespace variables @@ -355,13 +355,14 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { static Book book; // Defined static to initialize the PRNG only once + // Save "search start" time and reset elapsed time to zero + elapsed_search_time(get_system_time()); + // Initialize global search-related variables StopOnPonderhit = StopRequest = QuitRequest = AspirationFailLow = false; - elapsed_search_time(get_system_time()); Limits = limits; - TimeMgr.init(Limits, pos.startpos_ply_counter()); - // Set output stream in normal or chess960 mode + // Set output stream mode: normal or chess960. Castling notation is different cout << set960(pos.is_chess960()); // Look for a book move @@ -381,17 +382,7 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { } } - // Set best timer interval to avoid lagging under time pressure. Timer is - // used to check for remaining available thinking time. - if (TimeMgr.available_time()) - Threads.set_timer(std::min(100, std::max(TimeMgr.available_time() / 8, 20))); - else - Threads.set_timer(100); - - // Read UCI options - UCIMultiPV = Options["MultiPV"].value(); - SkillLevel = Options["Skill Level"].value(); - + // Read UCI options: GUI could change UCI parameters during the game read_evaluation_uci_options(pos.side_to_move()); Threads.read_uci_options(); @@ -404,22 +395,14 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { TT.clear(); } + UCIMultiPV = Options["MultiPV"].value(); + SkillLevel = Options["Skill Level"].value(); + // Do we have to play with skill handicap? In this case enable MultiPV that // we will use behind the scenes to retrieve a set of possible moves. SkillLevelEnabled = (SkillLevel < 20); MultiPV = (SkillLevelEnabled ? std::max(UCIMultiPV, 4) : UCIMultiPV); - // Wake up needed threads and reset maxPly counter - for (int i = 0; i < Threads.size(); i++) - { - Threads[i].wake_up(); - Threads[i].maxPly = 0; - } - - // Start async mode to catch UCI commands sent to us while searching, - // like "quit", "stop", etc. - Threads.start_listener(); - // Write current search header to log file if (Options["Use Search Log"].value()) { @@ -433,10 +416,39 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { << endl; } + // Wake up needed threads and reset maxPly counter + for (int i = 0; i < Threads.size(); i++) + { + Threads[i].maxPly = 0; + Threads[i].wake_up(); + } + + // Set best timer interval to avoid lagging under time pressure. Timer is + // used to check for remaining available thinking time. + TimeMgr.init(Limits, pos.startpos_ply_counter()); + + if (TimeMgr.available_time()) + Threads.set_timer(std::min(100, std::max(TimeMgr.available_time() / 8, 20))); + else + Threads.set_timer(100); + + // Start async mode to catch UCI commands sent to us while searching, + // like "quit", "stop", etc. + Threads.start_listener(); + // We're ready to start thinking. Call the iterative deepening loop function Move ponderMove = MOVE_NONE; Move bestMove = id_loop(pos, searchMoves, &ponderMove); + // From now on any UCI command will be read in-sync with Threads.getline() + Threads.stop_listener(); + + // Stop timer, no need to check for available time any more + Threads.set_timer(0); + + // This makes all the slave threads to go to sleep, if not already sleeping + Threads.set_size(1); + // Write current search final statistics to log file if (Options["Use Search Log"].value()) { @@ -453,17 +465,8 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { pos.undo_move(bestMove); // Return from think() with unchanged position } - // This makes all the threads to go to sleep - Threads.set_size(1); - - // From now on any UCI command will be read in-sync with Threads.getline() - Threads.stop_listener(); - - // Stop timer, no need to check for available time any more - Threads.set_timer(0); - - // If we are pondering or in infinite search, we shouldn't print the - // best move before we are told to do so. + // If we are pondering or in infinite search, we shouldn't print the best move + // before we are told to do so. if (Limits.ponder || Limits.infinite) wait_for_stop_or_ponderhit(); @@ -493,16 +496,17 @@ namespace { Value bestValues[PLY_MAX_PLUS_2]; int bestMoveChanges[PLY_MAX_PLUS_2]; int depth, aspirationDelta; - Value value, alpha, beta; - Move bestMove, easyMove, skillBest, skillPonder; + Value bestValue, alpha, beta; + Move bestMove, skillBest, skillPonder; + bool bestMoveNeverChanged = true; // Initialize stuff before a new search memset(ss, 0, 4 * sizeof(SearchStack)); TT.new_search(); H.clear(); - *ponderMove = bestMove = easyMove = skillBest = skillPonder = MOVE_NONE; + *ponderMove = bestMove = skillBest = skillPonder = MOVE_NONE; depth = aspirationDelta = 0; - value = alpha = -VALUE_INFINITE, beta = VALUE_INFINITE; + bestValue = alpha = -VALUE_INFINITE, beta = VALUE_INFINITE; ss->currentMove = MOVE_NULL; // Hack to skip update gains // Moves to search are verified and copied @@ -552,7 +556,7 @@ namespace { do { // Search starts from ss+1 to allow referencing (ss-1). This is // needed by update gains and ss copy when splitting at Root. - value = search(pos, ss+1, alpha, beta, depth * ONE_PLY); + bestValue = search(pos, ss+1, alpha, beta, depth * ONE_PLY); // Bring to front the best move. It is critical that sorting is // done with a stable algorithm because all the values but the first @@ -566,7 +570,7 @@ namespace { // the fail high/low loop then reorder the PV moves, otherwise // leave the last PV move in its position so to be searched again. // Of course this is needed only in MultiPV search. - if (MultiPVIdx && value > alpha && value < beta) + if (MultiPVIdx && bestValue > alpha && bestValue < beta) sort(Rml.begin(), Rml.begin() + MultiPVIdx); // Write PV back to transposition table in case the relevant entries @@ -584,7 +588,7 @@ namespace { // if we have a fail high/low and we are deep in the search. UCI // protocol requires to send all the PV lines also if are still // to be searched and so refer to the previous search's score. - if ((value > alpha && value < beta) || elapsed_search_time() > 2000) + if ((bestValue > alpha && bestValue < beta) || elapsed_search_time() > 2000) for (int i = 0; i < std::min(UCIMultiPV, (int)Rml.size()); i++) { bool updated = (i <= MultiPVIdx); @@ -605,12 +609,12 @@ namespace { // In case of failing high/low increase aspiration window and // research, otherwise exit the fail high/low loop. - if (value >= beta) + if (bestValue >= beta) { beta = std::min(beta + aspirationDelta, VALUE_INFINITE); aspirationDelta += aspirationDelta / 2; } - else if (value <= alpha) + else if (bestValue <= alpha) { AspirationFailLow = true; StopOnPonderhit = false; @@ -621,13 +625,13 @@ namespace { else break; - } while (abs(value) < VALUE_KNOWN_WIN); + } while (abs(bestValue) < VALUE_KNOWN_WIN); } // Collect info about search result bestMove = Rml[0].pv[0]; *ponderMove = Rml[0].pv[1]; - bestValues[depth] = value; + bestValues[depth] = bestValue; bestMoveChanges[depth] = Rml.bestMoveChanges; // Skills: Do we need to pick now the best and the ponder moves ? @@ -637,28 +641,19 @@ namespace { if (Options["Use Search Log"].value()) { Log log(Options["Search Log Filename"].value()); - log << pretty_pv(pos, depth, value, elapsed_search_time(), &Rml[0].pv[0]) << endl; + log << pretty_pv(pos, depth, bestValue, elapsed_search_time(), &Rml[0].pv[0]) << endl; } - // Init easyMove at first iteration or drop it if differs from the best move - if (depth == 1 && (Rml.size() == 1 || Rml[0].score > Rml[1].score + EasyMoveMargin)) - easyMove = bestMove; - else if (bestMove != easyMove) - easyMove = MOVE_NONE; + // Filter out startup noise when monitoring best move stability + if (depth > 2 && bestMoveChanges[depth]) + bestMoveNeverChanged = false; // Check for some early stop condition if (!StopRequest && Limits.useTimeManagement()) { - // Easy move: 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 search to some depth anyway to get a proper score. - if ( depth >= 7 - && easyMove == bestMove - && ( Rml.size() == 1 - ||( Rml[0].nodes > (pos.nodes_searched() * 85) / 100 - && elapsed_search_time() > TimeMgr.available_time() / 16) - ||( Rml[0].nodes > (pos.nodes_searched() * 98) / 100 - && elapsed_search_time() > TimeMgr.available_time() / 32))) + // Stop search early if there is only a single legal move. Search to + // some depth anyway to get a proper score. + if (Rml.size() == 1 && depth >= 7) StopRequest = true; // Take in account some extra time if the best move has changed @@ -670,6 +665,23 @@ namespace { if (elapsed_search_time() > (TimeMgr.available_time() * 62) / 100) StopRequest = true; + // Stop search early if one move seems to be much better than others + if ( depth >= 10 + && !StopRequest + && ( bestMoveNeverChanged + || elapsed_search_time() > (TimeMgr.available_time() * 40) / 100)) + { + Value rBeta = bestValue - EasyMoveMargin; + (ss+1)->excludedMove = bestMove; + (ss+1)->skipNullMove = true; + Value v = search(pos, ss+1, rBeta - 1, rBeta, (depth * ONE_PLY) / 2); + (ss+1)->skipNullMove = false; + (ss+1)->excludedMove = MOVE_NONE; + + if (v < rBeta) + StopRequest = true; + } + // If we are allowed to ponder do not stop the search now but keep pondering if (StopRequest && Limits.ponder) { @@ -1024,8 +1036,7 @@ split_point_start: // At split points actual search starts from here << " currmovenumber " << moveCount + MultiPVIdx << endl; } - // At Root and at first iteration do a PV search on all the moves to score root moves - isPvMove = (PvNode && moveCount <= (RootNode && depth <= ONE_PLY ? MAX_MOVES : 1)); + isPvMove = (PvNode && moveCount <= 1); givesCheck = pos.move_gives_check(move, ci); captureOrPromotion = pos.is_capture_or_promotion(move); @@ -1780,6 +1791,7 @@ split_point_start: // At split points actual search starts from here return s.str(); } + // pv_to_uci() returns a string with information on the current PV line // formatted according to UCI specification. @@ -1795,6 +1807,7 @@ split_point_start: // At split points actual search starts from here return s.str(); } + // depth_to_uci() returns a string with information on the current depth and // seldepth formatted according to UCI specification. @@ -1845,6 +1858,7 @@ split_point_start: // At split points actual search starts from here 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"). @@ -1920,6 +1934,7 @@ split_point_start: // At split points actual search starts from here // When playing with strength handicap choose best move among the MultiPV set // using a statistical rule dependent on SkillLevel. Idea by Heinz van Saanen. + void do_skill_level(Move* best, Move* ponder) { assert(MultiPV > 1); @@ -1998,6 +2013,7 @@ split_point_start: // At split points actual search starts from here 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 @@ -2032,6 +2048,7 @@ split_point_start: // At split points actual search starts from here 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. @@ -2062,20 +2079,8 @@ split_point_start: // At split points actual search starts from here do pos.undo_move(pv[--ply]); while (ply); } -} // namespace - - -// Little helper used by idle_loop() to check that all the slave threads of a -// split point have finished searching. - -static bool all_slaves_finished(SplitPoint* sp) { - for (int i = 0; i < Threads.size(); i++) - if (sp->is_slave[i]) - return false; - - return true; -} +} // namespace // Thread::idle_loop() is where the thread is parked when it has no work to do. @@ -2105,7 +2110,7 @@ void Thread::idle_loop(SplitPoint* sp) { lock_grab(&sleepLock); // If we are master and all slaves have finished don't go to sleep - if (sp && all_slaves_finished(sp)) + if (sp && Threads.split_point_finished(sp)) { lock_release(&sleepLock); break; @@ -2157,7 +2162,7 @@ void Thread::idle_loop(SplitPoint* sp) { // If this thread is the master of a split point and all slaves have // finished their work at this split point, return from the idle loop. - if (sp && all_slaves_finished(sp)) + if (sp && Threads.split_point_finished(sp)) { // Because sp->is_slave[] is reset under lock protection, // be sure sp->lock has been released before to return.