X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=fefc886424e9935116191a27c44594b7ad6d887b;hp=c163e8eac590cade95af87ccab64189b38c0a677;hb=d58176bfead421088bb3543b3cb6d1c359a3c91b;hpb=e7cfe42d3f5bf385bcfafebeabd9eb887f0f21ce diff --git a/src/search.cpp b/src/search.cpp index c163e8ea..fefc8864 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -24,6 +24,7 @@ #include #include #include +#include #include "book.h" #include "evaluate.h" @@ -128,7 +129,7 @@ namespace { inline Value futility_margin(Depth d, int mn) { - return d < 7 * ONE_PLY ? FutilityMargins[Max(d, 1)][Min(mn, 63)] + return d < 7 * ONE_PLY ? FutilityMargins[std::max(int(d), 1)][std::min(mn, 63)] : 2 * VALUE_INFINITE; } @@ -144,7 +145,7 @@ namespace { template inline Depth reduction(Depth d, int mn) { - return (Depth) Reductions[PvNode][Min(d / ONE_PLY, 63)][Min(mn, 63)]; + return (Depth) Reductions[PvNode][std::min(int(d) / ONE_PLY, 63)][std::min(mn, 63)]; } // Easy move margin. An easy move candidate must be at least this much @@ -169,11 +170,6 @@ namespace { int SkillLevel; bool SkillLevelEnabled; - // 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. - int NodesSincePoll; - int NodesBetweenPolls = 30000; - // History table History H; @@ -196,16 +192,14 @@ namespace { bool connected_threat(const Position& pos, Move m, Move threat); Value refine_eval(const TTEntry* tte, Value defaultEval, int ply); void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount); - void update_gains(const Position& pos, Move move, Value before, Value after); void do_skill_level(Move* best, Move* ponder); - int current_search_time(int set = 0); + int elapsed_search_time(int set = 0); string score_to_uci(Value v, Value alpha = -VALUE_INFINITE, Value beta = VALUE_INFINITE); string speed_to_uci(int64_t nodes); string pv_to_uci(const 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(); // MovePickerExt template class extends MovePicker and allows to choose at compile @@ -284,14 +278,14 @@ namespace { if ( captureOrPromotion && type_of(pos.piece_on(move_to(m))) != PAWN && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) - - piece_value_midgame(pos.piece_on(move_to(m))) == VALUE_ZERO) + - PieceValueMidgame[pos.piece_on(move_to(m))] == VALUE_ZERO) && !is_special(m)) { result += PawnEndgameExtension[PvNode]; *dangerous = true; } - return Min(result, ONE_PLY); + return std::min(result, ONE_PLY); } } // namespace @@ -363,24 +357,13 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { // Initialize global search-related variables StopOnPonderhit = StopRequest = QuitRequest = AspirationFailLow = false; - NodesSincePoll = 0; - current_search_time(get_system_time()); + elapsed_search_time(get_system_time()); Limits = limits; TimeMgr.init(Limits, pos.startpos_ply_counter()); // Set output steram in normal or chess960 mode cout << set960(pos.is_chess960()); - // Set best NodesBetweenPolls interval to avoid lagging under time pressure - if (Limits.maxNodes) - NodesBetweenPolls = Min(Limits.maxNodes, 30000); - else if (Limits.time && Limits.time < 1000) - NodesBetweenPolls = 1000; - else if (Limits.time && Limits.time < 5000) - NodesBetweenPolls = 5000; - else - NodesBetweenPolls = 30000; - // Look for a book move if (Options["OwnBook"].value()) { @@ -398,6 +381,12 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { } } + // Set best timer interval to avoid lagging under time pressure + 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(); @@ -417,7 +406,7 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { // 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 ? Max(UCIMultiPV, 4) : UCIMultiPV); + MultiPV = (SkillLevelEnabled ? std::max(UCIMultiPV, 4) : UCIMultiPV); // Wake up needed threads and reset maxPly counter for (int i = 0; i < Threads.size(); i++) @@ -439,18 +428,24 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { << endl; } + // 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); + Threads.set_timer(0); + // Write final search statistics and close log file if (Options["Use Search Log"].value()) { - int t = current_search_time(); + int e = elapsed_search_time(); Log log(Options["Search Log Filename"].value()); log << "Nodes: " << pos.nodes_searched() - << "\nNodes/second: " << (t > 0 ? pos.nodes_searched() * 1000 / t : 0) + << "\nNodes/second: " << (e > 0 ? pos.nodes_searched() * 1000 / e : 0) << "\nBest move: " << move_to_san(pos, bestMove); StateInfo st; @@ -462,6 +457,9 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { // 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(); + // If we are pondering or in infinite search, we shouldn't print the // best move before we are told to do so. if (!StopRequest && (Limits.ponder || Limits.infinite)) @@ -503,7 +501,7 @@ namespace { *ponderMove = bestMove = easyMove = skillBest = skillPonder = MOVE_NONE; depth = aspirationDelta = 0; value = alpha = -VALUE_INFINITE, beta = VALUE_INFINITE; - ss->currentMove = MOVE_NULL; // Hack to skip update_gains() + ss->currentMove = MOVE_NULL; // Hack to skip update gains // Moves to search are verified and copied Rml.init(pos, searchMoves); @@ -527,7 +525,7 @@ namespace { Rml.bestMoveChanges = 0; // MultiPV loop. We perform a full root search for each PV line - for (MultiPVIdx = 0; MultiPVIdx < Min(MultiPV, (int)Rml.size()); MultiPVIdx++) + for (MultiPVIdx = 0; MultiPVIdx < std::min(MultiPV, (int)Rml.size()); MultiPVIdx++) { // Calculate dynamic aspiration window based on previous iterations if (depth >= 5 && abs(Rml[MultiPVIdx].prevScore) < VALUE_KNOWN_WIN) @@ -535,11 +533,11 @@ namespace { int prevDelta1 = bestValues[depth - 1] - bestValues[depth - 2]; int prevDelta2 = bestValues[depth - 2] - bestValues[depth - 3]; - aspirationDelta = Min(Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16), 24); + aspirationDelta = std::min(std::max(abs(prevDelta1) + abs(prevDelta2) / 2, 16), 24); aspirationDelta = (aspirationDelta + 7) / 8 * 8; // Round to match grainSize - alpha = Max(Rml[MultiPVIdx].prevScore - aspirationDelta, -VALUE_INFINITE); - beta = Min(Rml[MultiPVIdx].prevScore + aspirationDelta, VALUE_INFINITE); + alpha = std::max(Rml[MultiPVIdx].prevScore - aspirationDelta, -VALUE_INFINITE); + beta = std::min(Rml[MultiPVIdx].prevScore + aspirationDelta, VALUE_INFINITE); } else { @@ -551,7 +549,7 @@ namespace { // research with bigger window until not failing high/low anymore. do { // Search starts from ss+1 to allow referencing (ss-1). This is - // needed by update_gains() and ss copy when splitting at Root. + // needed by update gains and ss copy when splitting at Root. value = search(pos, ss+1, alpha, beta, depth * ONE_PLY); // Bring to front the best move. It is critical that sorting is @@ -584,8 +582,8 @@ 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) || current_search_time() > 2000) - for (int i = 0; i < Min(UCIMultiPV, (int)Rml.size()); i++) + if ((value > alpha && value < beta) || elapsed_search_time() > 2000) + for (int i = 0; i < std::min(UCIMultiPV, (int)Rml.size()); i++) { bool updated = (i <= MultiPVIdx); @@ -607,7 +605,7 @@ namespace { // research, otherwise exit the fail high/low loop. if (value >= beta) { - beta = Min(beta + aspirationDelta, VALUE_INFINITE); + beta = std::min(beta + aspirationDelta, VALUE_INFINITE); aspirationDelta += aspirationDelta / 2; } else if (value <= alpha) @@ -615,7 +613,7 @@ namespace { AspirationFailLow = true; StopOnPonderhit = false; - alpha = Max(alpha - aspirationDelta, -VALUE_INFINITE); + alpha = std::max(alpha - aspirationDelta, -VALUE_INFINITE); aspirationDelta += aspirationDelta / 2; } else @@ -637,7 +635,7 @@ namespace { if (Options["Use Search Log"].value()) { Log log(Options["Search Log Filename"].value()); - log << pretty_pv(pos, depth, value, current_search_time(), &Rml[0].pv[0]) << endl; + log << pretty_pv(pos, depth, value, elapsed_search_time(), &Rml[0].pv[0]) << endl; } // Init easyMove at first iteration or drop it if differs from the best move @@ -656,9 +654,9 @@ namespace { && easyMove == bestMove && ( Rml.size() == 1 ||( Rml[0].nodes > (pos.nodes_searched() * 85) / 100 - && current_search_time() > TimeMgr.available_time() / 16) + && elapsed_search_time() > TimeMgr.available_time() / 16) ||( Rml[0].nodes > (pos.nodes_searched() * 98) / 100 - && current_search_time() > TimeMgr.available_time() / 32))) + && elapsed_search_time() > TimeMgr.available_time() / 32))) StopRequest = true; // Take in account some extra time if the best move has changed @@ -667,7 +665,7 @@ namespace { // Stop search if most of available time is already consumed. We probably don't // have enough time to search the first move at the next iteration anyway. - if (current_search_time() > (TimeMgr.available_time() * 62) / 100) + if (elapsed_search_time() > (TimeMgr.available_time() * 62) / 100) StopRequest = true; // If we are allowed to ponder do not stop the search now but keep pondering @@ -736,7 +734,7 @@ namespace { if (PvNode && thread.maxPly < ss->ply) thread.maxPly = ss->ply; - // Step 1. Initialize node and poll. Polling can abort search + // Step 1. Initialize node if (!SpNode) { ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE; @@ -752,12 +750,6 @@ namespace { goto split_point_start; } - if (pos.thread() == 0 && ++NodesSincePoll > NodesBetweenPolls) - { - NodesSincePoll = 0; - poll(pos); - } - // Step 2. Check for aborted search and immediate draw if (( StopRequest || pos.is_draw() @@ -767,8 +759,8 @@ namespace { // Step 3. Mate distance pruning if (!RootNode) { - alpha = Max(value_mated_in(ss->ply), alpha); - beta = Min(value_mate_in(ss->ply+1), beta); + alpha = std::max(value_mated_in(ss->ply), alpha); + beta = std::min(value_mate_in(ss->ply+1), beta); if (alpha >= beta) return alpha; } @@ -820,8 +812,17 @@ namespace { TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin); } - // Save gain for the parent non-capture move - update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval); + // Update gain for the parent non-capture move given the static position + // evaluation before and after the move. + if ( (move = (ss-1)->currentMove) != MOVE_NULL + && (ss-1)->eval != VALUE_NONE + && ss->eval != VALUE_NONE + && pos.captured_piece_type() == PIECE_TYPE_NONE + && !is_special(move)) + { + Square to = move_to(move); + H.update_gain(pos.piece_on(to), to, -(ss-1)->eval - ss->eval); + } // Step 6. Razoring (is omitted in PV nodes) if ( !PvNode @@ -870,12 +871,12 @@ namespace { if (refinedValue - PawnValueMidgame > beta) R++; - pos.do_null_move(st); + pos.do_null_move(st); (ss+1)->skipNullMove = true; nullValue = depth-R*ONE_PLY < ONE_PLY ? -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) : - search(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY); (ss+1)->skipNullMove = false; - pos.undo_null_move(); + pos.do_null_move(st); if (nullValue >= beta) { @@ -1015,7 +1016,7 @@ split_point_start: // At split points actual search starts from here nodes = pos.nodes_searched(); // For long searches send current move info to GUI - if (pos.thread() == 0 && current_search_time() > 2000) + if (pos.thread() == 0 && elapsed_search_time() > 2000) cout << "info" << depth_to_uci(depth) << " currmove " << move << " currmovenumber " << moveCount + MultiPVIdx << endl; @@ -1244,9 +1245,11 @@ split_point_start: // At split points actual search starts from here } // Step 20. Check for mate and stalemate - // All legal moves have been searched and if there are - // no legal moves, it must be mate or stalemate. - // If one move was excluded return fail low score. + // All legal moves have been searched and if there are no legal moves, it + // must be mate or stalemate. Note that we can have a false positive in + // case of StopRequest or thread.cutoff_occurred() are set, but this is + // harmless because return value is discarded anyhow in the parent nodes. + // If we are in a singular extension search then return a fail low score. if (!SpNode && !moveCount) return excludedMove ? oldAlpha : inCheck ? value_mated_in(ss->ply) : VALUE_DRAW; @@ -1397,7 +1400,7 @@ split_point_start: // At split points actual search starts from here && !pos.is_passed_pawn_push(move)) { futilityValue = futilityBase - + piece_value_endgame(pos.piece_on(move_to(move))) + + PieceValueEndgame[pos.piece_on(move_to(move))] + (is_enpassant(move) ? PawnValueEndgame : VALUE_ZERO); if (futilityValue < beta) @@ -1530,7 +1533,7 @@ split_point_start: // At split points actual search starts from here while (b) { victimSq = pop_1st_bit(&b); - futilityValue = futilityBase + piece_value_endgame(pos.piece_on(victimSq)); + futilityValue = futilityBase + PieceValueEndgame[pos.piece_on(victimSq)]; // Note that here we generate illegal "double move"! if ( futilityValue >= beta @@ -1654,7 +1657,7 @@ split_point_start: // At split points actual search starts from here // Case 2: If the threatened piece has value less than or equal to the // value of the threatening piece, don't prune moves which defend it. if ( pos.is_capture(threat) - && ( piece_value_midgame(pos.piece_on(tfrom)) >= piece_value_midgame(pos.piece_on(tto)) + && ( PieceValueMidgame[pos.piece_on(tfrom)] >= PieceValueMidgame[pos.piece_on(tto)] || type_of(pos.piece_on(tfrom)) == KING) && pos.move_attacks_square(m, tto)) return true; @@ -1678,8 +1681,8 @@ split_point_start: // At split points actual search starts from here Value v = value_from_tt(tte->value(), ply); return ( tte->depth() >= depth - || v >= Max(VALUE_MATE_IN_PLY_MAX, beta) - || v < Min(VALUE_MATED_IN_PLY_MAX, beta)) + || v >= std::max(VALUE_MATE_IN_PLY_MAX, beta) + || v < std::min(VALUE_MATED_IN_PLY_MAX, beta)) && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta) || ((tte->type() & VALUE_TYPE_UPPER) && v < beta)); @@ -1724,24 +1727,10 @@ split_point_start: // At split points actual search starts from here } - // update_gains() updates the gains table of a non-capture move given - // the static position evaluation before and after the move. - - void update_gains(const Position& pos, Move m, Value before, Value after) { - - if ( m != MOVE_NULL - && before != VALUE_NONE - && after != VALUE_NONE - && pos.captured_piece_type() == PIECE_TYPE_NONE - && !is_special(m)) - H.update_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after)); - } - - // current_search_time() returns the number of milliseconds which have passed // since the beginning of the current search. - int current_search_time(int set) { + int elapsed_search_time(int set) { static int searchStartTime; @@ -1780,7 +1769,7 @@ split_point_start: // At split points actual search starts from here string speed_to_uci(int64_t nodes) { std::stringstream s; - int t = current_search_time(); + int t = elapsed_search_time(); s << " nodes " << nodes << " nps " << (t > 0 ? int(nodes * 1000 / t) : 0) @@ -1906,81 +1895,6 @@ split_point_start: // At split points actual search starts from here 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 - // search. - - void poll(const Position& pos) { - - static int lastInfoTime; - int t = current_search_time(); - - // Poll for input - if (input_available()) - { - // We are line oriented, don't read single chars - string command; - - if (!std::getline(std::cin, command) || command == "quit") - { - // Quit the program as soon as possible - Limits.ponder = false; - QuitRequest = StopRequest = true; - return; - } - else if (command == "stop") - { - // Stop calculating as soon as possible, but still send the "bestmove" - // and possibly the "ponder" token when finishing the search. - Limits.ponder = false; - StopRequest = true; - } - else if (command == "ponderhit") - { - // The opponent has played the expected move. GUI sends "ponderhit" if - // we were told to ponder on the same move the opponent has played. We - // should continue searching but switching from pondering to normal search. - Limits.ponder = false; - - if (StopOnPonderhit) - StopRequest = true; - } - } - - // Print search information - if (t < 1000) - lastInfoTime = 0; - - else if (lastInfoTime > t) - // HACK: Must be a new search where we searched less than - // NodesBetweenPolls nodes during the first second of search. - lastInfoTime = 0; - - else if (t - lastInfoTime >= 1000) - { - lastInfoTime = t; - - dbg_print_mean(); - dbg_print_hit_rate(); - } - - // Should we stop the search? - if (Limits.ponder) - return; - - bool stillAtFirstMove = FirstRootMove - && !AspirationFailLow - && t > TimeMgr.available_time(); - - bool noMoreTime = t > TimeMgr.maximum_time() - || stillAtFirstMove; - - if ( (Limits.useTimeManagement() && noMoreTime) - || (Limits.maxTime && t >= Limits.maxTime) - || (Limits.maxNodes && pos.nodes_searched() >= Limits.maxNodes)) // FIXME - StopRequest = true; - } - // wait_for_stop_or_ponderhit() is called when the maximum depth is reached // while the program is pondering. The point is to work around a wrinkle in @@ -1991,14 +1905,14 @@ split_point_start: // At split points actual search starts from here void wait_for_stop_or_ponderhit() { - string command; + string cmd; // Wait for a command from stdin - while ( std::getline(std::cin, command) - && command != "ponderhit" && command != "stop" && command != "quit") {}; + while (cmd != "ponderhit" && cmd != "stop" && cmd != "quit") + Threads.getline(cmd); - if (command != "ponderhit" && command != "stop") - QuitRequest = true; // Must be "quit" or getline() returned false + if (cmd == "quit") + QuitRequest = true; } @@ -2013,9 +1927,9 @@ split_point_start: // At split points actual search starts from here // Rml list is already sorted by score in descending order int s; int max_s = -VALUE_INFINITE; - int size = Min(MultiPV, (int)Rml.size()); + int size = std::min(MultiPV, (int)Rml.size()); int max = Rml[0].score; - int var = Min(max - Rml[size - 1].score, PawnValueMidgame); + int var = std::min(max - Rml[size - 1].score, int(PawnValueMidgame)); int wk = 120 - 2 * SkillLevel; // PRNG sequence should be non deterministic @@ -2251,3 +2165,68 @@ void Thread::idle_loop(SplitPoint* sp) { } } } + + +// do_uci_async_cmd() is called by listener thread when in async mode and 'cmd' +// input line is received from the GUI. + +void do_uci_async_cmd(const std::string& cmd) { + + if (cmd == "quit") + { + // Quit the program as soon as possible + Limits.ponder = false; + QuitRequest = StopRequest = true; + } + else if (cmd == "stop") + { + // Stop calculating as soon as possible, but still send the "bestmove" + // and possibly the "ponder" token when finishing the search. + Limits.ponder = false; + StopRequest = true; + } + else if (cmd == "ponderhit") + { + // The opponent has played the expected move. GUI sends "ponderhit" if + // we were told to ponder on the same move the opponent has played. We + // should continue searching but switching from pondering to normal search. + Limits.ponder = false; + + if (StopOnPonderhit) + StopRequest = true; + } +} + + +// do_timer_event() is called by the timer thread when the timer triggers + +void do_timer_event() { + + static int lastInfoTime; + int e = elapsed_search_time(); + + // Print debug information every second + if (get_system_time() - lastInfoTime >= 1000) + { + lastInfoTime = get_system_time(); + + dbg_print_mean(); + dbg_print_hit_rate(); + } + + // Should we stop the search? + if (Limits.ponder) + return; + + bool stillAtFirstMove = FirstRootMove + && !AspirationFailLow + && e > TimeMgr.available_time(); + + bool noMoreTime = e > TimeMgr.maximum_time() + || stillAtFirstMove; + + if ( (Limits.useTimeManagement() && noMoreTime) + || (Limits.maxTime && e >= Limits.maxTime) + /* missing nodes limit */ ) // FIXME + StopRequest = true; +}