X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=9a1fa821211c317bed64fb25e71a82d9604a23d9;hb=91601d7f95a3e84d2d46ca9a36637508197dbdab;hp=d1504e323e779671ddf2e1a88e1034132793769b;hpb=56774fff20e73ede9ea8548997c9b1798c5344d5;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index d1504e32..9a1fa821 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -147,20 +147,11 @@ namespace { /// Namespace variables - // Root move list RootMoveList Rml; - - // MultiPV mode - int MultiPV, UCIMultiPV, MultiPVIdx; - - // Time management variables + size_t MultiPV, UCIMultiPV, MultiPVIdx; TimeManager TimeMgr; - - // Skill level adjustment int SkillLevel; bool SkillLevelEnabled; - - // History table History H; @@ -294,15 +285,12 @@ int64_t Search::perft(Position& pos, Depth depth) { StateInfo st; int64_t sum = 0; - // Generate all legal moves MoveList ml(pos); - // If we are at the last ply we don't need to do and undo - // the moves, just to count them. + // At the last ply just return the number of moves (leaf nodes) if (depth <= ONE_PLY) return ml.size(); - // Loop through all legal moves CheckInfo ci(pos); for ( ; !ml.end(); ++ml) { @@ -323,14 +311,12 @@ void Search::think() { static Book book; // Defined static to initialize the PRNG only once Position& pos = RootPosition; - - // Reset elapsed search time elapsed_time(true); + TimeMgr.init(Limits, pos.startpos_ply_counter()); // Set output stream mode: normal or chess960. Castling notation is different cout << set960(pos.is_chess960()); - // Look for a book move if (Options["OwnBook"].value()) { if (Options["Book File"].value() != book.name()) @@ -351,24 +337,21 @@ void Search::think() { read_evaluation_uci_options(pos.side_to_move()); Threads.read_uci_options(); - // Set a new TT size if changed TT.set_size(Options["Hash"].value()); - if (Options["Clear Hash"].value()) { Options["Clear Hash"].set_value("false"); TT.clear(); } - UCIMultiPV = Options["MultiPV"].value(); - SkillLevel = Options["Skill Level"].value(); + 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); + MultiPV = (SkillLevelEnabled ? std::max(UCIMultiPV, (size_t)4) : UCIMultiPV); - // Write current search header to log file if (Options["Use Search Log"].value()) { Log log(Options["Search Log Filename"].value()); @@ -390,8 +373,6 @@ void Search::think() { // 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 @@ -401,13 +382,10 @@ void Search::think() { Move ponderMove = MOVE_NONE; Move bestMove = id_loop(pos, &RootMoves[0], &ponderMove); - // Stop timer, no need to check for available time any more + // Stop timer and send all the slaves to sleep, if not already sleeping 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()) { int e = elapsed_time(); @@ -457,7 +435,6 @@ namespace { Move bestMove, skillBest, skillPonder; bool bestMoveNeverChanged = true; - // Initialize stuff before a new search memset(ss, 0, 4 * sizeof(Stack)); TT.new_search(); H.clear(); @@ -465,8 +442,6 @@ namespace { depth = aspirationDelta = 0; bestValue = alpha = -VALUE_INFINITE, beta = VALUE_INFINITE; ss->currentMove = MOVE_NULL; // Hack to skip update gains - - // Moves to search are verified and copied Rml.init(pos, rootMoves); // Handle special case of searching on a mate/stalemate position @@ -488,7 +463,7 @@ namespace { Rml.bestMoveChanges = 0; // MultiPV loop. We perform a full root search for each PV line - for (MultiPVIdx = 0; MultiPVIdx < std::min(MultiPV, (int)Rml.size()); MultiPVIdx++) + for (MultiPVIdx = 0; MultiPVIdx < std::min(MultiPV, Rml.size()); MultiPVIdx++) { // Calculate dynamic aspiration window based on previous iterations if (depth >= 5 && abs(Rml[MultiPVIdx].prevScore) < VALUE_KNOWN_WIN) @@ -532,7 +507,7 @@ namespace { // Write PV back to transposition table in case the relevant entries // have been overwritten during the search. - for (int i = 0; i <= MultiPVIdx; i++) + for (size_t i = 0; i <= MultiPVIdx; i++) Rml[i].insert_pv_in_tt(pos); // If search has been stopped exit the aspiration window loop, @@ -546,7 +521,7 @@ namespace { // 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 ((bestValue > alpha && bestValue < beta) || elapsed_time() > 2000) - for (int i = 0; i < std::min(UCIMultiPV, (int)Rml.size()); i++) + for (size_t i = 0; i < std::min(UCIMultiPV, Rml.size()); i++) { bool updated = (i <= MultiPVIdx); @@ -585,7 +560,6 @@ namespace { } while (abs(bestValue) < VALUE_KNOWN_WIN); } - // Collect info about search result bestMove = Rml[0].pv[0]; *ponderMove = Rml[0].pv[1]; bestValues[depth] = bestValue; @@ -932,7 +906,6 @@ 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); CheckInfo ci(pos); ss->bestMove = MOVE_NONE; @@ -941,13 +914,16 @@ split_point_start: // At split points actual search starts from here && !SpNode && depth >= SingularExtensionDepth[PvNode] && ttMove != MOVE_NONE - && !excludedMove // Do not allow recursive singular extension search + && !excludedMove // Recursive singular search is not allowed && (tte->type() & VALUE_TYPE_LOWER) && tte->depth() >= depth - 3 * ONE_PLY; if (SpNode) { lock_grab(&(sp->lock)); bestValue = sp->bestValue; + moveCount = sp->moveCount; + + assert(bestValue > -VALUE_INFINITE && moveCount > 0); } // Step 11. Loop through moves @@ -984,10 +960,8 @@ split_point_start: // At split points actual search starts from here // This is used by time management Signals.firstRootMove = (moveCount == 1); - // Save the current node count before the move is searched nodes = pos.nodes_searched(); - // For long searches send current move info to GUI if (pos.thread() == 0 && elapsed_time() > 2000) cout << "info" << depth_to_uci(depth) << " currmove " << move @@ -1042,12 +1016,12 @@ split_point_start: // At split points actual search starts from here && !inCheck && !dangerous && move != ttMove - && !is_castle(move)) + && !is_castle(move) + && (bestValue > VALUE_MATED_IN_PLY_MAX || bestValue == -VALUE_INFINITE)) { // Move count based pruning if ( moveCount >= futility_move_count(depth) - && (!threatMove || !connected_threat(pos, move, threatMove)) - && bestValue > VALUE_MATED_IN_PLY_MAX) // FIXME bestValue is racy + && (!threatMove || !connected_threat(pos, move, threatMove))) { if (SpNode) lock_grab(&(sp->lock)); @@ -1065,20 +1039,13 @@ split_point_start: // At split points actual search starts from here if (futilityValue < beta) { if (SpNode) - { lock_grab(&(sp->lock)); - if (futilityValue > sp->bestValue) - sp->bestValue = bestValue = futilityValue; - } - else if (futilityValue > bestValue) - bestValue = futilityValue; continue; } // Prune moves with negative SEE at low depths if ( predictedDepth < 2 * ONE_PLY - && bestValue > VALUE_MATED_IN_PLY_MAX && pos.see_sign(move) < 0) { if (SpNode) @@ -1159,14 +1126,12 @@ split_point_start: // At split points actual search starts from here // be trusted, and we don't update the best move and/or PV. if (RootNode && !Signals.stop) { - // Remember searched nodes counts for this move RootMove* rm = Rml.find(move); rm->nodes += pos.nodes_searched() - nodes; // PV move or new best move ? if (isPvMove || value > alpha) { - // Update PV rm->score = value; rm->extract_pv_from_tt(pos); @@ -1182,7 +1147,7 @@ split_point_start: // At split points actual search starts from here // position in the list is preserved, just the PV is pushed up. rm->score = -VALUE_INFINITE; - } // RootNode + } if (value > bestValue) { @@ -1220,12 +1185,19 @@ split_point_start: // At split points actual search starts from here // 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) + if (!moveCount) return excludedMove ? oldAlpha : inCheck ? value_mated_in(ss->ply) : VALUE_DRAW; + // If we have pruned all the moves without searching return a fail-low score + if (bestValue == -VALUE_INFINITE) + { + assert(!playedMoveCount); + + bestValue = alpha; + } + // Step 21. Update tables - // If the search is not aborted, update the transposition table, - // history counters, and killer moves. + // Update transposition table entry, history and killers if (!SpNode && !Signals.stop && !thread.cutoff_occurred()) { move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove; @@ -1260,6 +1232,7 @@ split_point_start: // At split points actual search starts from here return bestValue; } + // qsearch() is the quiescence search function, which is called by the main // search function when the remaining depth is zero (or, to be more precise, // less than ONE_PLY). @@ -1340,7 +1313,6 @@ split_point_start: // At split points actual search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - // Futility pruning parameters, not needed when in check futilityBase = ss->eval + evalMargin + FutilityMarginQS; enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame; } @@ -1422,7 +1394,6 @@ split_point_start: // At split points actual search starts from here if (!pos.pl_move_is_legal(move, ci.pinned)) continue; - // Update current move ss->currentMove = move; // Make and search the move @@ -1643,8 +1614,8 @@ split_point_start: // At split points actual search starts from here } - // can_return_tt() returns true if a transposition table score - // can be used to cut-off at a given point in search. + // can_return_tt() returns true if a transposition table score can be used to + // cut-off at a given point in search. bool can_return_tt(const TTEntry* tte, Depth depth, Value beta, int ply) { @@ -1659,8 +1630,8 @@ split_point_start: // At split points actual search starts from here } - // refine_eval() returns the transposition table score if - // possible otherwise falls back on static position evaluation. + // refine_eval() returns the transposition table score if possible, otherwise + // falls back on static position evaluation. Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) { @@ -1676,8 +1647,8 @@ split_point_start: // At split points actual search starts from here } - // update_history() registers a good move that produced a beta-cutoff - // in history and marks as failures all the other moves of that ply. + // update_history() registers a good move that produced a beta-cutoff in + // history and marks as failures all the other moves of that ply. void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount) { @@ -1783,6 +1754,12 @@ 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"). It uses the two helpers + // time_to_string() and score_to_string() to format time and score respectively. + string time_to_string(int millisecs) { const int MSecMinute = 1000 * 60; @@ -1815,11 +1792,6 @@ 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"). - string pretty_pv(Position& pos, int depth, Value value, int time, Move pv[]) { const int64_t K = 1000; @@ -1880,8 +1852,8 @@ split_point_start: // At split points actual search starts from here // Rml list is already sorted by score in descending order int s; + size_t size = std::min(MultiPV, Rml.size()); int max_s = -VALUE_INFINITE; - int size = std::min(MultiPV, (int)Rml.size()); int max = Rml[0].score; int var = std::min(max - Rml[size - 1].score, int(PawnValueMidgame)); int wk = 120 - 2 * SkillLevel; @@ -1893,7 +1865,7 @@ split_point_start: // At split points actual search starts from here // Choose best move. For each move's score we add two terms both dependent // on wk, one deterministic and bigger for weaker moves, and one random, // then we choose the move with the resulting highest score. - for (int i = 0; i < size; i++) + for (size_t i = 0; i < size; i++) { s = Rml[i].score; @@ -1914,7 +1886,7 @@ split_point_start: // At split points actual search starts from here } - /// RootMove and RootMoveList method's definitions + // RootMove and RootMoveList method's definitions void RootMoveList::init(Position& pos, Move rootMoves[]) { @@ -2020,9 +1992,9 @@ split_point_start: // At split points actual search starts from here } // namespace -// Thread::idle_loop() is where the thread is parked when it has no work to do. -// The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint object -// for which the thread is the master. +/// Thread::idle_loop() is where the thread is parked when it has no work to do. +/// The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint object +/// for which the thread is the master. void Thread::idle_loop(SplitPoint* sp) { @@ -2036,7 +2008,6 @@ void Thread::idle_loop(SplitPoint* sp) { { assert((!sp && threadID) || Threads.use_sleeping_threads()); - // Slave thread should exit as soon as do_terminate flag raises if (do_terminate) { assert(!sp); @@ -2111,15 +2082,16 @@ void Thread::idle_loop(SplitPoint* sp) { } -// do_timer_event() is called by the timer thread when the timer triggers +/// do_timer_event() is called by the timer thread when the timer triggers. It +/// is used to print debug info and, more important, to detect when we are out of +/// available time and so stop the search. void do_timer_event() { static int lastInfoTime; int e = elapsed_time(); - // Print debug information every one second - if (!lastInfoTime || get_system_time() - lastInfoTime >= 1000) + if (get_system_time() - lastInfoTime >= 1000 || !lastInfoTime) { lastInfoTime = get_system_time(); @@ -2127,7 +2099,6 @@ void do_timer_event() { dbg_print_hit_rate(); } - // Should we stop the search? if (Limits.ponder) return;