X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=677455ec05b0c26bb3722df69f6645a86f0c14d9;hp=27a67a639401e3d18e48a3416a1ea4592ce1f072;hb=1d368bbbdc50bbb4e10933c4986abc07a08010fd;hpb=927f1b0bd30a5b2cfdcdf163f26f528738509064 diff --git a/src/search.cpp b/src/search.cpp index 27a67a63..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, int ply, Value* alpha, const Value beta, Value* bestValue, - Depth depth, Move threatMove, bool mateThreat, int moveCount, MovePicker* mp, bool pvNode); - + 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,10 +188,10 @@ 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. - Depth CheckExtension[2], PawnPushTo7thExtension[2], PassedPawnExtension[2]; - Depth PawnEndgameExtension[2], MateThreatExtension[2]; + // 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]; // Minimum depth for use of singular extension const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */}; @@ -205,18 +203,18 @@ 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 - inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; } + inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / ONE_PLY, 63)][Min(mn, 63)]; } // Easy move margin. An easy move candidate must be at least this much // better than the second best move. @@ -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; @@ -267,20 +264,20 @@ namespace { Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove); template - Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply); + Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth); template - Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply); + Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth); template - inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) { + inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) { - return depth < ONE_PLY ? qsearch(pos, ss, alpha, beta, DEPTH_ZERO, ply) - : search(pos, ss, alpha, beta, depth, ply); + return depth < ONE_PLY ? qsearch(pos, ss, alpha, beta, DEPTH_ZERO) + : search(pos, ss, alpha, beta, depth); } template - Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool mateThreat, bool* dangerous); + Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool* dangerous); bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue); bool connected_moves(const Position& pos, Move m1, Move m2); @@ -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; @@ -484,8 +486,6 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[ PassedPawnExtension[0] = Options["Passed Pawn Extension (non-PV nodes)"].value(); PawnEndgameExtension[1] = Options["Pawn Endgame Extension (PV nodes)"].value(); PawnEndgameExtension[0] = Options["Pawn Endgame Extension (non-PV nodes)"].value(); - MateThreatExtension[1] = Options["Mate Threat Extension (PV nodes)"].value(); - MateThreatExtension[0] = Options["Mate Threat Extension (non-PV nodes)"].value(); UCIMultiPV = Options["MultiPV"].value(); SkillLevel = Options["Skill level"].value(); UseLogFile = Options["Use Search Log"].value(); @@ -508,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; } @@ -547,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; @@ -570,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 @@ -598,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; @@ -607,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() @@ -624,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; @@ -652,7 +634,7 @@ namespace { // research with bigger window until not failing high/low anymore. do { // Search starting from ss+1 to allow calling update_gains() - value = search(pos, ss+1, alpha, beta, depth * ONE_PLY, 0); + value = search(pos, ss+1, alpha, beta, depth * ONE_PLY); // Write PV back to transposition table in case the relevant entries // have been overwritten during the search. @@ -692,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; @@ -708,7 +696,7 @@ namespace { else if (bestMove != easyMove) easyMove = MOVE_NONE; - if (UseTimeManagement && !StopRequest) + if (Limits.useTimeManagement() && !StopRequest) { // Time to stop? bool noMoreTime = false; @@ -743,7 +731,7 @@ namespace { if (noMoreTime) { - if (Pondering) + if (Limits.ponder) StopOnPonderhit = true; else break; @@ -773,12 +761,11 @@ namespace { // here: This is taken care of after we return from the split point. template - Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) { + Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) { assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); assert(beta > alpha && beta <= VALUE_INFINITE); assert(PvNode || alpha == beta - 1); - assert((Root || ply > 0) && ply < PLY_MAX); assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads()); Move movesSearched[MOVES_MAX]; @@ -792,7 +779,6 @@ namespace { Value bestValue, value, oldAlpha; Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific bool isPvMove, isCheck, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous, isBadCap; - bool mateThreat = false; int moveCount = 0, playedMoveCount = 0; int threadID = pos.thread(); SplitPoint* sp = NULL; @@ -800,6 +786,11 @@ namespace { refinedValue = bestValue = value = -VALUE_INFINITE; oldAlpha = alpha; 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) { @@ -807,7 +798,6 @@ namespace { tte = NULL; ttMove = excludedMove = MOVE_NONE; threatMove = sp->threatMove; - mateThreat = sp->mateThreat; goto split_point_start; } else if (Root) @@ -828,12 +818,12 @@ namespace { if (( StopRequest || ThreadsMgr.cutoff_at_splitpoint(threadID) || pos.is_draw() - || ply >= PLY_MAX - 1) && !Root) + || ss->ply > PLY_MAX) && !Root) return VALUE_DRAW; // Step 3. Mate distance pruning - alpha = Max(value_mated_in(ply), alpha); - beta = Min(value_mate_in(ply+1), beta); + alpha = Max(value_mated_in(ss->ply), alpha); + beta = Min(value_mate_in(ss->ply+1), beta); if (alpha >= beta) return alpha; @@ -852,11 +842,11 @@ namespace { if ( !Root && tte && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT - : ok_to_use_TT(tte, depth, beta, ply))) + : ok_to_use_TT(tte, depth, beta, ss->ply))) { TT.refresh(tte); ss->bestMove = ttMove; // Can be MOVE_NONE - return value_from_tt(tte->value(), ply); + return value_from_tt(tte->value(), ss->ply); } // Step 5. Evaluate the position statically and update parent's gain statistics @@ -868,7 +858,7 @@ namespace { ss->eval = tte->static_value(); ss->evalMargin = tte->static_value_margin(); - refinedValue = refine_eval(tte, ss->eval, ply); + refinedValue = refine_eval(tte, ss->eval, ss->ply); } else { @@ -889,7 +879,7 @@ namespace { && !pos.has_pawn_on_7th(pos.side_to_move())) { Value rbeta = beta - razor_margin(depth); - Value v = qsearch(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply); + Value v = qsearch(pos, ss, rbeta-1, rbeta, DEPTH_ZERO); if (v < rbeta) // Logically we should return (v + razor_margin(depth)), but // surprisingly this did slightly weaker in tests. @@ -928,7 +918,7 @@ namespace { pos.do_null_move(st); (ss+1)->skipNullMove = true; - nullValue = -search(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1); + nullValue = -search(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY); (ss+1)->skipNullMove = false; pos.undo_null_move(); @@ -943,7 +933,7 @@ namespace { // Do verification search at high depths ss->skipNullMove = true; - Value v = search(pos, ss, alpha, beta, depth-R*ONE_PLY, ply); + Value v = search(pos, ss, alpha, beta, depth-R*ONE_PLY); ss->skipNullMove = false; if (v >= beta) @@ -957,9 +947,6 @@ namespace { // move which was reduced. If a connection is found, return a fail // low score (which will cause the reduced move to fail high in the // parent node, which will trigger a re-search with full depth). - if (nullValue == value_mated_in(ply + 2)) - mateThreat = true; - threatMove = (ss+1)->bestMove; if ( depth < ThreatDepth @@ -978,17 +965,13 @@ namespace { Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2); ss->skipNullMove = true; - search(pos, ss, alpha, beta, d, ply); + search(pos, ss, alpha, beta, d); ss->skipNullMove = false; ttMove = ss->bestMove; tte = TT.retrieve(posKey); } - // Mate threat detection for PV nodes, otherwise we use null move search - if (PvNode) - mateThreat = pos.has_mate_threat(); - split_point_start: // At split points actual search starts from here // Initialize a MovePicker object for the current position @@ -1055,7 +1038,7 @@ split_point_start: // At split points actual search starts from here captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 11. Decide the new search depth - ext = extension(pos, move, captureOrPromotion, moveIsCheck, mateThreat, &dangerous); + ext = extension(pos, move, captureOrPromotion, moveIsCheck, &dangerous); // Singular extension search. If all moves but one fail low on a search of // (alpha-s, beta-s), and just one fails high on (alpha, beta), then that move @@ -1066,14 +1049,14 @@ split_point_start: // At split points actual search starts from here && move == tte->move() && ext < ONE_PLY) { - Value ttValue = value_from_tt(tte->value(), ply); + Value ttValue = value_from_tt(tte->value(), ss->ply); if (abs(ttValue) < VALUE_KNOWN_WIN) { Value rBeta = ttValue - int(depth); ss->excludedMove = move; ss->skipNullMove = true; - Value v = search(pos, ss, rBeta - 1, rBeta, depth / 2, ply); + Value v = search(pos, ss, rBeta - 1, rBeta, depth / 2); ss->skipNullMove = false; ss->excludedMove = MOVE_NONE; ss->bestMove = MOVE_NONE; @@ -1162,7 +1145,7 @@ split_point_start: // At split points actual search starts from here if (Root && MultiPV > 1) alpha = -VALUE_INFINITE; - value = -search(pos, ss+1, -beta, -alpha, newDepth, ply+1); + value = -search(pos, ss+1, -beta, -alpha, newDepth); } else { @@ -1183,7 +1166,7 @@ split_point_start: // At split points actual search starts from here { alpha = SpNode ? sp->alpha : alpha; Depth d = newDepth - ss->reduction; - value = -search(pos, ss+1, -(alpha+1), -alpha, d, ply+1); + value = -search(pos, ss+1, -(alpha+1), -alpha, d); doFullDepthSearch = (value > alpha); } @@ -1197,7 +1180,7 @@ split_point_start: // At split points actual search starts from here ss->reduction = 3 * ONE_PLY; Value rAlpha = alpha - 300; Depth d = newDepth - ss->reduction; - value = -search(pos, ss+1, -(rAlpha+1), -rAlpha, d, ply+1); + value = -search(pos, ss+1, -(rAlpha+1), -rAlpha, d); doFullDepthSearch = (value > rAlpha); ss->reduction = DEPTH_ZERO; // Restore original reduction } @@ -1206,13 +1189,13 @@ split_point_start: // At split points actual search starts from here if (doFullDepthSearch) { alpha = SpNode ? sp->alpha : alpha; - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1); + value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth); // Step extra. pv search (only in PV nodes) // Search only for possible new PV nodes, if instead value >= beta then // parent node fails low with value <= alpha and tries another move. if (PvNode && value > alpha && (Root || value < beta)) - value = -search(pos, ss+1, -beta, -alpha, newDepth, ply+1); + value = -search(pos, ss+1, -beta, -alpha, newDepth); } } @@ -1248,7 +1231,7 @@ split_point_start: // At split points actual search starts from here else if (SpNode) sp->betaCutoff = true; - if (value == value_mate_in(ply + 1)) + if (value == value_mate_in(ss->ply + 1)) ss->mateKiller = move; ss->bestMove = move; @@ -1308,8 +1291,8 @@ split_point_start: // At split points actual search starts from here && ThreadsMgr.available_thread_exists(threadID) && !StopRequest && !ThreadsMgr.cutoff_at_splitpoint(threadID)) - ThreadsMgr.split(pos, ss, ply, &alpha, beta, &bestValue, depth, - threatMove, mateThreat, moveCount, &mp, PvNode); + ThreadsMgr.split(pos, ss, &alpha, beta, &bestValue, depth, + threatMove, moveCount, &mp, PvNode); } // Step 19. Check for mate and stalemate @@ -1317,7 +1300,7 @@ split_point_start: // At split points actual search starts from here // no legal moves, it must be mate or stalemate. // If one move was excluded return fail low score. if (!SpNode && !moveCount) - return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW; + return excludedMove ? oldAlpha : isCheck ? value_mated_in(ss->ply) : VALUE_DRAW; // Step 20. Update tables // If the search is not aborted, update the transposition table, @@ -1328,7 +1311,7 @@ split_point_start: // At split points actual search starts from here vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT; - TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, ss->evalMargin); + TT.store(posKey, value_to_tt(bestValue, ss->ply), vt, depth, move, ss->eval, ss->evalMargin); // Update killers and history only for non capture moves that fails high if ( bestValue >= beta @@ -1361,13 +1344,12 @@ split_point_start: // At split points actual search starts from here // less than ONE_PLY). template - Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) { + Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) { assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE); assert(PvNode || alpha == beta - 1); assert(depth <= 0); - assert(ply > 0 && ply < PLY_MAX); assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads()); StateInfo st; @@ -1379,9 +1361,10 @@ split_point_start: // At split points actual search starts from here Value oldAlpha = alpha; ss->bestMove = ss->currentMove = MOVE_NONE; + ss->ply = (ss-1)->ply + 1; // Check for an instant draw or maximum ply reached - if (pos.is_draw() || ply >= PLY_MAX - 1) + if (ss->ply > PLY_MAX || pos.is_draw()) return VALUE_DRAW; // Decide whether or not to include checks, this fixes also the type of @@ -1395,10 +1378,10 @@ split_point_start: // At split points actual search starts from here tte = TT.retrieve(pos.get_key()); ttMove = (tte ? tte->move() : MOVE_NONE); - if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ply)) + if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ss->ply)) { ss->bestMove = ttMove; // Can be MOVE_NONE - return value_from_tt(tte->value(), ply); + return value_from_tt(tte->value(), ss->ply); } // Evaluate the position statically @@ -1426,7 +1409,7 @@ split_point_start: // At split points actual search starts from here if (bestValue >= beta) { if (!tte) - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin); + TT.store(pos.get_key(), value_to_tt(bestValue, ss->ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin); return bestValue; } @@ -1515,7 +1498,7 @@ split_point_start: // At split points actual search starts from here // Make and search the move pos.do_move(move, st, ci, moveIsCheck); - value = -qsearch(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1); + value = -qsearch(pos, ss+1, -beta, -alpha, depth-ONE_PLY); pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); @@ -1535,11 +1518,11 @@ split_point_start: // At split points actual search starts from here // All legal moves have been searched. A special case: If we're in check // and no legal moves were found, it is checkmate. if (isCheck && bestValue == -VALUE_INFINITE) - return value_mated_in(ply); + return value_mated_in(ss->ply); // Update transposition table ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT); - TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin); + TT.store(pos.get_key(), value_to_tt(bestValue, ss->ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1696,21 +1679,15 @@ split_point_start: // At split points actual search starts from here // the move is marked as 'dangerous' so, at least, we avoid to prune it. template Depth extension(const Position& pos, Move m, bool captureOrPromotion, - bool moveIsCheck, bool mateThreat, bool* dangerous) { + bool moveIsCheck, bool* dangerous) { assert(m != MOVE_NONE); Depth result = DEPTH_ZERO; - *dangerous = moveIsCheck | mateThreat; + *dangerous = moveIsCheck; - if (*dangerous) - { - if (moveIsCheck && pos.see_sign(m) >= 0) - result += CheckExtension[PvNode]; - - if (mateThreat) - result += MateThreatExtension[PvNode]; - } + if (moveIsCheck && pos.see_sign(m) >= 0) + result += CheckExtension[PvNode]; if (pos.type_of_piece_on(move_from(m)) == PAWN) { @@ -1731,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; @@ -1854,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; } @@ -1872,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(); } @@ -1914,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; } @@ -1922,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") @@ -1930,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; @@ -1950,18 +1931,15 @@ split_point_start: // At split points actual search starts from here { lastInfoTime = t; - if (dbg_show_mean) - dbg_print_mean(); - - if (dbg_show_hit_rate) - dbg_print_hit_rate(); + dbg_print_mean(); + dbg_print_hit_rate(); // Send info on searched nodes as soon as we return to root SendSearchedNodes = true; } // Should we stop the search? - if (Pondering) + if (Limits.ponder) return; bool stillAtFirstMove = FirstRootMove @@ -1971,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; } @@ -2047,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) { @@ -2062,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); @@ -2071,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++) {} @@ -2080,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 @@ -2098,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; @@ -2108,9 +2087,9 @@ split_point_start: // At split points actual search starts from here (ss+1)->sp = tsp; if (tsp->pvNode) - search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth, tsp->ply); + search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); else - search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth, tsp->ply); + search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); assert(threads[threadID].state == THREAD_SEARCHING); @@ -2118,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 @@ -2145,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; @@ -2208,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]); - } } @@ -2309,11 +2284,10 @@ split_point_start: // At split points actual search starts from here // call search().When all threads have returned from search() then split() returns. template - void ThreadsManager::split(Position& pos, SearchStack* ss, int ply, Value* alpha, - const Value beta, Value* bestValue, Depth depth, Move threatMove, - bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) { + void ThreadsManager::split(Position& pos, SearchStack* ss, Value* alpha, const Value beta, + Value* bestValue, Depth depth, Move threatMove, + int moveCount, MovePicker* mp, bool pvNode) { assert(pos.is_ok()); - assert(ply > 0 && ply < PLY_MAX); assert(*bestValue >= -VALUE_INFINITE); assert(*bestValue <= *alpha); assert(*alpha < beta); @@ -2343,10 +2317,8 @@ split_point_start: // At split points actual search starts from here splitPoint.parent = masterThread.splitPoint; splitPoint.master = master; splitPoint.betaCutoff = false; - splitPoint.ply = ply; splitPoint.depth = depth; splitPoint.threatMove = threatMove; - splitPoint.mateThreat = mateThreat; splitPoint.alpha = *alpha; splitPoint.beta = beta; splitPoint.pvNode = pvNode; @@ -2391,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 @@ -2415,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() { @@ -2460,13 +2421,13 @@ split_point_start: // At split points actual search starts from here TTEntry* tte; int ply = 1; - assert(pv[0] != MOVE_NONE && move_is_legal(pos, pv[0])); + assert(pv[0] != MOVE_NONE && pos.move_is_legal(pv[0])); pos.do_move(pv[0], *st++); while ( (tte = TT.retrieve(pos.get_key())) != NULL && tte->move() != MOVE_NONE - && move_is_legal(pos, tte->move()) + && pos.move_is_legal(tte->move()) && ply < PLY_MAX && (!pos.is_draw() || ply < 2)) { @@ -2490,7 +2451,7 @@ split_point_start: // At split points actual search starts from here Value v, m = VALUE_NONE; int ply = 0; - assert(pv[0] != MOVE_NONE && move_is_legal(pos, pv[0])); + assert(pv[0] != MOVE_NONE && pos.move_is_legal(pv[0])); do { k = pos.get_key(); @@ -2512,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(); }