X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=677455ec05b0c26bb3722df69f6645a86f0c14d9;hp=516f2d051cc503f058d2f541a7d46ef9fcb8800e;hb=1d368bbbdc50bbb4e10933c4986abc07a08010fd;hpb=076b62310ee874adb38d2c9610aad163db65e2e8 diff --git a/src/search.cpp b/src/search.cpp index 516f2d05..677455ec 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -64,6 +64,7 @@ namespace { static storage duration are automatically set to zero before enter main() */ public: + Thread& operator[](int threadID) { return threads[threadID]; } void init_threads(); void exit_threads(); @@ -75,22 +76,19 @@ namespace { bool available_thread_exists(int master) const; bool thread_is_available(int slave, int master) const; bool cutoff_at_splitpoint(int threadID) const; - void wake_sleeping_thread(int threadID); void idle_loop(int threadID, SplitPoint* sp); template void split(Position& pos, SearchStack* ss, Value* alpha, const Value beta, Value* bestValue, Depth depth, Move threatMove, int moveCount, MovePicker* mp, bool pvNode); - private: + Lock mpLock; Depth minimumSplitDepth; int maxThreadsPerSplitPoint; bool useSleepingThreads; int activeThreads; volatile bool allThreadsShouldExit; Thread threads[MAX_THREADS]; - Lock mpLock, sleepLock[MAX_THREADS]; - WaitCondition sleepCond[MAX_THREADS]; }; @@ -118,8 +116,8 @@ namespace { void extract_pv_from_tt(Position& pos); void insert_pv_in_tt(Position& pos); - std::string pv_info_to_uci(Position& pos, int depth, Value alpha, Value beta, int pvIdx); - + std::string pv_info_to_uci(Position& pos, int depth, int selDepth, + Value alpha, Value beta, int pvIdx); int64_t nodes; Value pv_score; Value non_pv_score; @@ -127,7 +125,7 @@ namespace { }; - // RootMoveList struct is just a std::vector<> of RootMove objects, + // RootMoveList struct is just a vector of RootMove objects, // with an handful of methods above the standard ones. struct RootMoveList : public std::vector { @@ -190,8 +188,8 @@ namespace { // Step 11. Decide the new search depth - // Extensions. Configurable UCI options - // Array index 0 is used at non-PV nodes, index 1 at PV nodes. + // Extensions. Configurable UCI options. Array index 0 is used at + // non-PV nodes, index 1 at PV nodes. Depth CheckExtension[2], PawnPushTo7thExtension[2]; Depth PassedPawnExtension[2], PawnEndgameExtension[2]; @@ -205,14 +203,14 @@ namespace { // Futility lookup tables (initialized at startup) and their access functions Value FutilityMarginsMatrix[16][64]; // [depth][moveNumber] - int FutilityMoveCountArray[32]; // [depth] + int FutilityMoveCountArray[32]; // [depth] inline Value futility_margin(Depth d, int mn) { return d < 7 * ONE_PLY ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE; } inline int futility_move_count(Depth d) { return d < 16 * ONE_PLY ? FutilityMoveCountArray[d] : 512; } // Step 14. Reduced search - // Reduction lookup tables (initialized at startup) and their getter functions + // Reduction lookup tables (initialized at startup) and their access function int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber] template @@ -235,10 +233,9 @@ namespace { int MultiPV, UCIMultiPV; // Time management variables - int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime; - bool UseTimeManagement, InfiniteSearch, Pondering, StopOnPonderhit; - bool FirstRootMove, StopRequest, QuitRequest, AspirationFailLow; + bool StopOnPonderhit, FirstRootMove, StopRequest, QuitRequest, AspirationFailLow; TimeManager TimeMgr; + SearchLimits Limits; // Log file bool UseLogFile; @@ -293,7 +290,7 @@ namespace { 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 current_search_time(int set = 0); std::string value_to_uci(Value v); std::string speed_to_uci(int64_t nodes); void poll(const Position& pos); @@ -306,7 +303,7 @@ namespace { #endif - // MovePickerExt is an extended MovePicker used to choose at compile time + // MovePickerExt is an extended MovePicker class used to choose at compile time // the proper move source according to the type of node. template struct MovePickerExt; @@ -441,25 +438,30 @@ int64_t perft(Position& pos, Depth depth) { /// think() is the external interface to Stockfish's search, and is called when /// the program receives the UCI 'go' command. It initializes various global -/// variables, and calls id_loop(). It returns false when a quit command is +/// variables, and calls id_loop(). It returns false when a "quit" command is /// received during the search. -bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[], - int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) { +bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { // Initialize global search-related variables StopOnPonderhit = StopRequest = QuitRequest = AspirationFailLow = SendSearchedNodes = false; NodesSincePoll = 0; - SearchStartTime = get_system_time(); - ExactMaxTime = maxTime; - MaxDepth = maxDepth; - MaxNodes = maxNodes; - InfiniteSearch = infinite; - Pondering = ponder; - UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch; + current_search_time(get_system_time()); + Limits = limits; + TimeMgr.init(Limits, pos.startpos_ply_counter()); + + // 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, only during games, not tests - if (UseTimeManagement && Options["OwnBook"].value()) + if (Limits.useTimeManagement() && Options["OwnBook"].value()) { if (Options["Book File"].value() != OpeningBook.name()) OpeningBook.open(Options["Book File"].value()); @@ -467,7 +469,7 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[ Move bookMove = OpeningBook.get_move(pos, Options["Best Book Move"].value()); if (bookMove != MOVE_NONE) { - if (Pondering) + if (Limits.ponder) wait_for_stop_or_ponderhit(); cout << "bestmove " << bookMove << endl; @@ -506,38 +508,25 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[ ThreadsMgr.read_uci_options(); init_eval(ThreadsMgr.active_threads()); - // Wake up needed threads. Main thread, with threadID == 0, is always active - for (int i = 1; i < ThreadsMgr.active_threads(); i++) - ThreadsMgr.wake_sleeping_thread(i); - - // Set thinking time - int myTime = time[pos.side_to_move()]; - int myIncrement = increment[pos.side_to_move()]; - if (UseTimeManagement) - TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter()); - - // Set best NodesBetweenPolls interval to avoid lagging under time pressure - if (MaxNodes) - NodesBetweenPolls = Min(MaxNodes, 30000); - else if (myTime && myTime < 1000) - NodesBetweenPolls = 1000; - else if (myTime && myTime < 5000) - NodesBetweenPolls = 5000; - else - NodesBetweenPolls = 30000; + // Wake up needed threads and reset maxPly counter + for (int i = 0; i < ThreadsMgr.active_threads(); i++) + { + ThreadsMgr[i].wake_up(); + ThreadsMgr[i].maxPly = 0; + } - // Write search information to log file + // Write to log file and keep it open to be accessed during the search if (UseLogFile) { std::string name = Options["Search Log Filename"].value(); LogFile.open(name.c_str(), std::ios::out | std::ios::app); LogFile << "\nSearching: " << pos.to_fen() - << "\ninfinite: " << infinite - << " ponder: " << ponder - << " time: " << myTime - << " increment: " << myIncrement - << " moves to go: " << movesToGo + << "\ninfinite: " << Limits.infinite + << " ponder: " << Limits.ponder + << " time: " << Limits.time + << " increment: " << Limits.increment + << " moves to go: " << Limits.movesToGo << endl; } @@ -545,15 +534,15 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[ Move ponderMove = MOVE_NONE; Move bestMove = id_loop(pos, searchMoves, &ponderMove); - // Print final search statistics cout << "info" << speed_to_uci(pos.nodes_searched()) << endl; + // Write final search statistics and close log file if (UseLogFile) { int t = current_search_time(); LogFile << "Nodes: " << pos.nodes_searched() - << "\nNodes/second: " << (t > 0 ? int(pos.nodes_searched() * 1000 / t) : 0) + << "\nNodes/second: " << (t > 0 ? pos.nodes_searched() * 1000 / t : 0) << "\nBest move: " << move_to_san(pos, bestMove); StateInfo st; @@ -568,7 +557,7 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[ // If we are pondering or in infinite search, we shouldn't print the // best move before we are told to do so. - if (!StopRequest && (Pondering || InfiniteSearch)) + if (!StopRequest && (Limits.ponder || Limits.infinite)) wait_for_stop_or_ponderhit(); // Could be MOVE_NONE when searching on a stalemate position @@ -596,7 +585,7 @@ namespace { SearchStack ss[PLY_MAX_PLUS_2]; Value bestValues[PLY_MAX_PLUS_2]; int bestMoveChanges[PLY_MAX_PLUS_2]; - int depth, aspirationDelta, skillSamplingDepth; + int depth, selDepth, aspirationDelta; Value value, alpha, beta; Move bestMove, easyMove, skillBest, skillPonder; @@ -605,7 +594,7 @@ namespace { TT.new_search(); H.clear(); *ponderMove = bestMove = easyMove = skillBest = skillPonder = MOVE_NONE; - depth = aspirationDelta = skillSamplingDepth = 0; + depth = aspirationDelta = 0; alpha = -VALUE_INFINITE, beta = VALUE_INFINITE; ss->currentMove = MOVE_NULL; // Hack to skip update_gains() @@ -622,13 +611,8 @@ namespace { return MOVE_NONE; } - // Choose a random sampling depth according to SkillLevel so that at low - // skills there is an higher risk to pick up a blunder. - if (SkillLevelEnabled) - skillSamplingDepth = 4 + SkillLevel + (RK.rand() % 4); - // Iterative deepening loop - while (++depth <= PLY_MAX && (!MaxDepth || depth <= MaxDepth) && !StopRequest) + while (++depth <= PLY_MAX && (!Limits.maxDepth || depth <= Limits.maxDepth) && !StopRequest) { Rml.bestMoveChanges = 0; cout << set960(pos.is_chess960()) << "info depth " << depth << endl; @@ -690,12 +674,18 @@ namespace { bestMoveChanges[depth] = Rml.bestMoveChanges; // Do we need to pick now the best and the ponder moves ? - if (SkillLevelEnabled && depth == skillSamplingDepth) + if (SkillLevelEnabled && depth == 1 + SkillLevel) do_skill_level(&skillBest, &skillPonder); + // Retrieve max searched depth among threads + selDepth = 0; + for (int i = 0; i < ThreadsMgr.active_threads(); i++) + if (ThreadsMgr[i].maxPly > selDepth) + selDepth = ThreadsMgr[i].maxPly; + // Send PV line to GUI and to log file for (int i = 0; i < Min(UCIMultiPV, (int)Rml.size()); i++) - cout << Rml[i].pv_info_to_uci(pos, depth, alpha, beta, i) << endl; + cout << Rml[i].pv_info_to_uci(pos, depth, selDepth, alpha, beta, i) << endl; if (UseLogFile) LogFile << pretty_pv(pos, depth, value, current_search_time(), Rml[0].pv) << endl; @@ -706,7 +696,7 @@ namespace { else if (bestMove != easyMove) easyMove = MOVE_NONE; - if (UseTimeManagement && !StopRequest) + if (Limits.useTimeManagement() && !StopRequest) { // Time to stop? bool noMoreTime = false; @@ -741,7 +731,7 @@ namespace { if (noMoreTime) { - if (Pondering) + if (Limits.ponder) StopOnPonderhit = true; else break; @@ -798,6 +788,10 @@ namespace { isCheck = pos.is_check(); ss->ply = (ss-1)->ply + 1; + // Used to send selDepth info to GUI + if (PvNode && ThreadsMgr[threadID].maxPly < ss->ply) + ThreadsMgr[threadID].maxPly = ss->ply; + if (SpNode) { sp = ss->sp; @@ -1714,8 +1708,7 @@ split_point_start: // At split points actual search starts from here && pos.type_of_piece_on(move_to(m)) != PAWN && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO) - && !move_is_promotion(m) - && !move_is_ep(m)) + && !move_is_special(m)) { result += PawnEndgameExtension[PvNode]; *dangerous = true; @@ -1837,9 +1830,14 @@ split_point_start: // At split points actual search starts from here // current_search_time() returns the number of milliseconds which have passed // since the beginning of the current search. - int current_search_time() { + int current_search_time(int set) { + + static int searchStartTime; - return get_system_time() - SearchStartTime; + if (set) + searchStartTime = set; + + return get_system_time() - searchStartTime; } @@ -1855,9 +1853,9 @@ split_point_start: // At split points actual search starts from here std::stringstream s; if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY) - s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to centipawns + s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to centipawns else - s << "mate " << (v > 0 ? VALUE_MATE - v + 1 : -VALUE_MATE - v) / 2; + s << "mate " << (v > 0 ? VALUE_MATE - v + 1 : -VALUE_MATE - v) / 2; return s.str(); } @@ -1897,7 +1895,7 @@ split_point_start: // At split points actual search starts from here if (!std::getline(std::cin, command) || command == "quit") { // Quit the program as soon as possible - Pondering = false; + Limits.ponder = false; QuitRequest = StopRequest = true; return; } @@ -1905,7 +1903,7 @@ split_point_start: // At split points actual search starts from here { // Stop calculating as soon as possible, but still send the "bestmove" // and possibly the "ponder" token when finishing the search. - Pondering = false; + Limits.ponder = false; StopRequest = true; } else if (command == "ponderhit") @@ -1913,7 +1911,7 @@ split_point_start: // At split points actual search starts from here // 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. - Pondering = false; + Limits.ponder = false; if (StopOnPonderhit) StopRequest = true; @@ -1941,7 +1939,7 @@ split_point_start: // At split points actual search starts from here } // Should we stop the search? - if (Pondering) + if (Limits.ponder) return; bool stillAtFirstMove = FirstRootMove @@ -1951,9 +1949,9 @@ split_point_start: // At split points actual search starts from here bool noMoreTime = t > TimeMgr.maximum_time() || stillAtFirstMove; - if ( (UseTimeManagement && noMoreTime) - || (ExactMaxTime && t >= ExactMaxTime) - || (MaxNodes && pos.nodes_searched() >= MaxNodes)) // FIXME + if ( (Limits.useTimeManagement() && noMoreTime) + || (Limits.maxTime && t >= Limits.maxTime) + || (Limits.maxNodes && pos.nodes_searched() >= Limits.maxNodes)) // FIXME StopRequest = true; } @@ -2027,7 +2025,7 @@ split_point_start: // At split points actual search starts from here assert(threadID >= 0 && threadID < MAX_THREADS); int i; - bool allFinished = false; + bool allFinished; while (true) { @@ -2042,7 +2040,8 @@ split_point_start: // At split points actual search starts from here // If we are not thinking, wait for a condition to be signaled // instead of wasting CPU time polling for work. - while ( threadID >= activeThreads || threads[threadID].state == THREAD_INITIALIZING + while ( threadID >= activeThreads + || threads[threadID].state == THREAD_INITIALIZING || (useSleepingThreads && threads[threadID].state == THREAD_AVAILABLE)) { assert(!sp || useSleepingThreads); @@ -2051,8 +2050,8 @@ split_point_start: // At split points actual search starts from here if (threads[threadID].state == THREAD_INITIALIZING) threads[threadID].state = THREAD_AVAILABLE; - // Grab the lock to avoid races with wake_sleeping_thread() - lock_grab(&sleepLock[threadID]); + // Grab the lock to avoid races with Thread::wake_up() + lock_grab(&threads[threadID].sleepLock); // If we are master and all slaves have finished do not go to sleep for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {} @@ -2060,15 +2059,15 @@ split_point_start: // At split points actual search starts from here if (allFinished || allThreadsShouldExit) { - lock_release(&sleepLock[threadID]); + lock_release(&threads[threadID].sleepLock); break; } // Do sleep here after retesting sleep conditions if (threadID >= activeThreads || threads[threadID].state == THREAD_AVAILABLE) - cond_wait(&sleepCond[threadID], &sleepLock[threadID]); + cond_wait(&threads[threadID].sleepCond, &threads[threadID].sleepLock); - lock_release(&sleepLock[threadID]); + lock_release(&threads[threadID].sleepLock); } // If this thread has been assigned work, launch a search @@ -2078,7 +2077,7 @@ split_point_start: // At split points actual search starts from here threads[threadID].state = THREAD_SEARCHING; - // Copy SplitPoint position and search stack and call search() + // Copy split point position and search stack and call search() // with SplitPoint template parameter set to true. SearchStack ss[PLY_MAX_PLUS_2]; SplitPoint* tsp = threads[threadID].splitPoint; @@ -2098,8 +2097,10 @@ split_point_start: // At split points actual search starts from here // Wake up master thread so to allow it to return from the idle loop in // case we are the last slave of the split point. - if (useSleepingThreads && threadID != tsp->master && threads[tsp->master].state == THREAD_AVAILABLE) - wake_sleeping_thread(tsp->master); + if ( useSleepingThreads + && threadID != tsp->master + && threads[tsp->master].state == THREAD_AVAILABLE) + threads[tsp->master].wake_up(); } // If this thread is the master of a split point and all slaves have @@ -2125,41 +2126,36 @@ split_point_start: // At split points actual search starts from here } - // init_threads() is called during startup. It launches all helper threads, - // and initializes the split point stack and the global locks and condition - // objects. + // init_threads() is called during startup. Initializes locks and condition + // variables and launches all threads sending them immediately to sleep. void ThreadsManager::init_threads() { int i, arg[MAX_THREADS]; bool ok; - // Initialize global locks + // This flag is needed to properly end the threads when program exits + allThreadsShouldExit = false; + + // Threads will sent to sleep as soon as created, only main thread is kept alive + activeThreads = 1; + lock_init(&mpLock); for (i = 0; i < MAX_THREADS; i++) { - lock_init(&sleepLock[i]); - cond_init(&sleepCond[i]); - } + // Initialize thread and split point locks + lock_init(&threads[i].sleepLock); + cond_init(&threads[i].sleepCond); - // Initialize splitPoints[] locks - for (i = 0; i < MAX_THREADS; i++) for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++) lock_init(&(threads[i].splitPoints[j].lock)); - // Will be set just before program exits to properly end the threads - allThreadsShouldExit = false; - - // Threads will be put all threads to sleep as soon as created - activeThreads = 1; - - // All threads except the main thread should be initialized to THREAD_INITIALIZING - threads[0].state = THREAD_SEARCHING; - for (i = 1; i < MAX_THREADS; i++) - threads[i].state = THREAD_INITIALIZING; + // All threads but first should be set to THREAD_INITIALIZING + threads[i].state = (i == 0 ? THREAD_SEARCHING : THREAD_INITIALIZING); + } - // Launch the helper threads + // Create and startup the threads for (i = 1; i < MAX_THREADS; i++) { arg[i] = i; @@ -2188,28 +2184,27 @@ split_point_start: // At split points actual search starts from here void ThreadsManager::exit_threads() { - allThreadsShouldExit = true; // Let the woken up threads to exit idle_loop() + // Force the woken up threads to exit idle_loop() and hence terminate + allThreadsShouldExit = true; - // Wake up all the threads and waits for termination - for (int i = 1; i < MAX_THREADS; i++) + for (int i = 0; i < MAX_THREADS; i++) { - wake_sleeping_thread(i); - while (threads[i].state != THREAD_TERMINATED) {} - } + // Wake up all the threads and waits for termination + if (i != 0) + { + threads[i].wake_up(); + while (threads[i].state != THREAD_TERMINATED) {} + } + + // Now we can safely destroy the locks and wait conditions + lock_destroy(&threads[i].sleepLock); + cond_destroy(&threads[i].sleepCond); - // Now we can safely destroy the locks - for (int i = 0; i < MAX_THREADS; i++) for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++) lock_destroy(&(threads[i].splitPoints[j].lock)); + } lock_destroy(&mpLock); - - // Now we can safely destroy the wait conditions - for (int i = 0; i < MAX_THREADS; i++) - { - lock_destroy(&sleepLock[i]); - cond_destroy(&sleepCond[i]); - } } @@ -2368,7 +2363,7 @@ split_point_start: // At split points actual search starts from here threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop() if (useSleepingThreads && i != master) - wake_sleeping_thread(i); + threads[i].wake_up(); } // Everything is set up. The master thread enters the idle loop, from @@ -2392,17 +2387,6 @@ split_point_start: // At split points actual search starts from here } - // wake_sleeping_thread() wakes up the thread with the given threadID - // when it is time to start a new search. - - void ThreadsManager::wake_sleeping_thread(int threadID) { - - lock_grab(&sleepLock[threadID]); - cond_signal(&sleepCond[threadID]); - lock_release(&sleepLock[threadID]); - } - - /// RootMove and RootMoveList method's definitions RootMove::RootMove() { @@ -2489,21 +2473,20 @@ split_point_start: // At split points actual search starts from here // pv_info_to_uci() returns a string with information on the current PV line // formatted according to UCI specification. - std::string RootMove::pv_info_to_uci(Position& pos, int depth, Value alpha, + std::string RootMove::pv_info_to_uci(Position& pos, int depth, int selDepth, Value alpha, Value beta, int pvIdx) { - std::stringstream s, l; - Move* m = pv; - - while (*m != MOVE_NONE) - l << *m++ << " "; + std::stringstream s; s << "info depth " << depth - << " seldepth " << int(m - pv) + << " seldepth " << selDepth << " multipv " << pvIdx + 1 << " score " << value_to_uci(pv_score) << (pv_score >= beta ? " lowerbound" : pv_score <= alpha ? " upperbound" : "") << speed_to_uci(pos.nodes_searched()) - << " pv " << l.str(); + << " pv "; + + for (Move* m = pv; *m != MOVE_NONE; m++) + s << *m << " "; return s.str(); }