X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=95fab3f176a5ba01263a16091b257a6f73e54964;hp=199c547f99d93f13cd91b0b686ab5e873167c19a;hb=5bad5fc0a737b214b2a6b3031e4b92200be012eb;hpb=392c7f2ab6e1e3894def16d37a70d3db4c02fbfd diff --git a/src/search.cpp b/src/search.cpp index 199c547f..95fab3f1 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -129,7 +129,7 @@ namespace { void extract_pv_from_tt(Position& pos); void insert_pv_in_tt(Position& pos); - std::string pv_info_to_uci(Position& pos, Value alpha, Value beta, int pvLine = 0); + std::string pv_info_to_uci(Position& pos, Depth depth, Value alpha, Value beta, int pvLine = 0); int64_t nodes; Value pv_score; @@ -145,11 +145,13 @@ namespace { typedef std::vector Base; - RootMoveList(Position& pos, Move searchMoves[]); + void init(Position& pos, Move searchMoves[]); void set_non_pv_scores(const Position& pos, Move ttm, SearchStack* ss); void sort() { insertion_sort(begin(), end()); } void sort_multipv(int n) { insertion_sort(begin(), begin() + n); } + + int bestMoveChanges; }; @@ -249,17 +251,7 @@ namespace { Book OpeningBook; // Pointer to root move list - RootMoveList* Rml; - - // Iteration counter - int Iteration; - - // Scores and number of times the best move changed for each iteration - Value ValueByIteration[PLY_MAX_PLUS_2]; - int BestMoveChangesByIteration[PLY_MAX_PLUS_2]; - - // Search window management - int AspirationDelta; + RootMoveList Rml; // MultiPV mode int MultiPV; @@ -331,7 +323,54 @@ namespace { DWORD WINAPI init_thread(LPVOID threadID); #endif -} + + // A dispatcher to choose among different move sources according to the type of node + template struct MovePickerExt; + + // In Root nodes use RootMoveList Rml as source + template<> struct MovePickerExt { + + MovePickerExt(const Position&, Move, Depth, const History&, SearchStack*, Value) + : rm(Rml.begin()), firstCall(true) {} + + Move get_next_move() { + + if (!firstCall) + ++rm; + else + firstCall = false; + + return rm != Rml.end() ? rm->pv[0] : MOVE_NONE; + } + int number_of_evasions() const { return (int)Rml.size(); } + + RootMoveList::iterator rm; + bool firstCall; + }; + + // In SpNodes use split point's shared MovePicker as move source + template<> struct MovePickerExt { + + MovePickerExt(const Position&, Move, Depth, const History&, SearchStack* ss, Value) + : mp(ss->sp->mp) {} + + Move get_next_move() { return mp->get_next_move(); } + int number_of_evasions() const { return mp->number_of_evasions(); } + + RootMoveList::iterator rm; // Dummy, never used + MovePicker* mp; + }; + + // Normal case, create and use a MovePicker object as source + template<> struct MovePickerExt : public MovePicker { + + MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, + SearchStack* ss, Value beta) : MovePicker(p, ttm, d, h, ss, beta) {} + + RootMoveList::iterator rm; // Dummy, never used + }; + +} // namespace //// @@ -555,97 +594,96 @@ namespace { Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove) { SearchStack ss[PLY_MAX_PLUS_2]; + Value bestValues[PLY_MAX_PLUS_2]; + int bestMoveChanges[PLY_MAX_PLUS_2]; + int iteration, researchCountFL, researchCountFH, aspirationDelta; + Value value, alpha, beta; Depth depth; - Move EasyMove = MOVE_NONE; - Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE; - int researchCountFL, researchCountFH; + Move EasyMove; // Moves to search are verified, scored and sorted - RootMoveList rml(pos, searchMoves); - Rml = &rml; + Rml.init(pos, searchMoves); + + // Initialize FIXME move before Rml.init() + TT.new_search(); + H.clear(); + init_ss_array(ss, PLY_MAX_PLUS_2); + alpha = -VALUE_INFINITE, beta = VALUE_INFINITE; + EasyMove = MOVE_NONE; + aspirationDelta = 0; + iteration = 1; // Handle special case of searching on a mate/stale position - if (rml.size() == 0) + if (Rml.size() == 0) { - Value s = (pos.is_check() ? -VALUE_MATE : VALUE_DRAW); - - cout << "info depth " << 1 - << " score " << value_to_uci(s) << endl; + cout << "info depth " << iteration << " score " + << value_to_uci(pos.is_check() ? -VALUE_MATE : VALUE_DRAW) + << endl; return MOVE_NONE; } - // Initialize - TT.new_search(); - H.clear(); - init_ss_array(ss, PLY_MAX_PLUS_2); - ValueByIteration[1] = rml[0].pv_score; - Iteration = 1; - - // Send initial RootMoveList scoring (iteration 1) + // Send initial scoring (iteration 1) cout << set960(pos.is_chess960()) // Is enough to set once at the beginning - << "info depth " << Iteration - << "\n" << rml[0].pv_info_to_uci(pos, alpha, beta) << endl; + << "info depth " << iteration + << "\n" << Rml[0].pv_info_to_uci(pos, ONE_PLY, alpha, beta) << endl; // Is one move significantly better than others after initial scoring ? - if ( rml.size() == 1 - || rml[0].pv_score > rml[1].pv_score + EasyMoveMargin) - EasyMove = rml[0].pv[0]; + if ( Rml.size() == 1 + || Rml[0].pv_score > Rml[1].pv_score + EasyMoveMargin) + EasyMove = Rml[0].pv[0]; // Iterative deepening loop - while (Iteration < PLY_MAX) + while (++iteration <= PLY_MAX && (!MaxDepth || iteration <= MaxDepth) && !StopRequest) { - // Initialize iteration - Iteration++; - BestMoveChangesByIteration[Iteration] = 0; + cout << "info depth " << iteration << endl; - cout << "info depth " << Iteration << endl; + Rml.bestMoveChanges = researchCountFL = researchCountFH = 0; + depth = (iteration - 2) * ONE_PLY + InitialDepth; // Calculate dynamic aspiration window based on previous iterations - if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN) + if (MultiPV == 1 && iteration >= 6 && abs(bestValues[iteration - 1]) < VALUE_KNOWN_WIN) { - int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2]; - int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3]; + int prevDelta1 = bestValues[iteration - 1] - bestValues[iteration - 2]; + int prevDelta2 = bestValues[iteration - 2] - bestValues[iteration - 3]; - AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16); - AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize + aspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16); + aspirationDelta = (aspirationDelta + 7) / 8 * 8; // Round to match grainSize - alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE); - beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE); + alpha = Max(bestValues[iteration - 1] - aspirationDelta, -VALUE_INFINITE); + beta = Min(bestValues[iteration - 1] + aspirationDelta, VALUE_INFINITE); } - depth = (Iteration - 2) * ONE_PLY + InitialDepth; - - researchCountFL = researchCountFH = 0; - // We start with small aspiration window and in case of fail high/low, we // research with bigger window until we are not failing high/low anymore. while (true) { // Sort the moves before to (re)search - rml.set_non_pv_scores(pos, rml[0].pv[0], ss); - rml.sort(); + Rml.set_non_pv_scores(pos, Rml[0].pv[0], ss); + Rml.sort(); - // Search to the current depth, rml is updated and sorted + // Search to the current depth value = search(pos, ss, alpha, beta, depth, 0); - // Sort the moves before to return - rml.sort(); - - // Write PV lines to transposition table, in case the relevant entries - // have been overwritten during the search. - for (int i = 0; i < Min(MultiPV, (int)rml.size()); i++) - rml[i].insert_pv_in_tt(pos); + // Sort the moves and write PV lines to transposition table, in case + // the relevant entries have been overwritten during the search. + Rml.sort(); + for (int i = 0; i < Min(MultiPV, (int)Rml.size()); i++) + Rml[i].insert_pv_in_tt(pos); + // Value cannot be trusted. Break out immediately! if (StopRequest) break; assert(value >= alpha); + bestMoveChanges[iteration] = Rml.bestMoveChanges; // FIXME move outside fail high/low loop + + // In case of failing high/low increase aspiration window and research, + // otherwise exit the fail high/low loop. if (value >= beta) { - // Prepare for a research after a fail high, each time with a wider window - beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE); + beta = Min(beta + aspirationDelta * (1 << researchCountFH), VALUE_INFINITE); researchCountFH++; } else if (value <= alpha) @@ -653,61 +691,56 @@ namespace { AspirationFailLow = true; StopOnPonderhit = false; - // Prepare for a research after a fail low, each time with a wider window - alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE); + alpha = Max(alpha - aspirationDelta * (1 << researchCountFL), -VALUE_INFINITE); researchCountFL++; } else break; } - if (StopRequest) - break; // Value cannot be trusted. Break out immediately! - //Save info about search result - ValueByIteration[Iteration] = value; + bestValues[iteration] = value; // Drop the easy move if differs from the new best move - if (rml[0].pv[0] != EasyMove) + if (Rml[0].pv[0] != EasyMove) EasyMove = MOVE_NONE; - if (UseTimeManagement) + if (UseTimeManagement && !StopRequest) { // Time to stop? - bool stopSearch = false; + bool noMoreTime = false; // Stop search early if there is only a single legal move, // we search up to Iteration 6 anyway to get a proper score. - if (Iteration >= 6 && rml.size() == 1) - stopSearch = true; + if (iteration >= 6 && Rml.size() == 1) + noMoreTime = true; // Stop search early when the last two iterations returned a mate score - if ( Iteration >= 6 - && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100 - && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100) - stopSearch = true; + if ( iteration >= 6 + && abs(bestValues[iteration]) >= abs(VALUE_MATE) - 100 + && abs(bestValues[iteration-1]) >= abs(VALUE_MATE) - 100) + noMoreTime = true; // Stop search early if one move seems to be much better than the others - if ( Iteration >= 8 - && EasyMove == rml[0].pv[0] - && ( ( rml[0].nodes > (pos.nodes_searched() * 85) / 100 + if ( iteration >= 8 + && EasyMove == Rml[0].pv[0] + && ( ( Rml[0].nodes > (pos.nodes_searched() * 85) / 100 && current_search_time() > TimeMgr.available_time() / 16) - ||( rml[0].nodes > (pos.nodes_searched() * 98) / 100 + ||( Rml[0].nodes > (pos.nodes_searched() * 98) / 100 && current_search_time() > TimeMgr.available_time() / 32))) - stopSearch = true; + noMoreTime = true; // Add some extra time if the best move has changed during the last two iterations - if (Iteration > 5 && Iteration <= 50) - TimeMgr.pv_instability(BestMoveChangesByIteration[Iteration], - BestMoveChangesByIteration[Iteration-1]); + if (iteration > 5 && iteration <= 50) + TimeMgr.pv_instability(bestMoveChanges[iteration], bestMoveChanges[iteration-1]); // Stop search if most of MaxSearchTime is consumed at the end of the // iteration. We probably don't have enough time to search the first // move at the next iteration anyway. if (current_search_time() > (TimeMgr.available_time() * 80) / 128) - stopSearch = true; + noMoreTime = true; - if (stopSearch) + if (noMoreTime) { if (Pondering) StopOnPonderhit = true; @@ -715,13 +748,10 @@ namespace { break; } } - - if (MaxDepth && Iteration >= MaxDepth) - break; } - *ponderMove = rml[0].pv[1]; - return rml[0].pv[0]; + *ponderMove = Rml[0].pv[1]; + return Rml[0].pv[0]; } @@ -743,7 +773,6 @@ namespace { Move movesSearched[MOVES_MAX]; int64_t nodes; - RootMoveList::iterator rm; StateInfo st; const TTEntry *tte; Key posKey; @@ -771,7 +800,9 @@ namespace { mateThreat = sp->mateThreat; goto split_point_start; } - else {} // Hack to fix icc's "statement is unreachable" warning + else if (Root) + bestValue = alpha; + else {} // Hack to fix icc's "statement is unreachable" warning FIXME // Step 1. Initialize node and poll. Polling can abort search ss->currentMove = ss->bestMove = threatMove = MOVE_NONE; @@ -958,9 +989,7 @@ namespace { split_point_start: // At split points actual search starts from here // Initialize a MovePicker object for the current position - // FIXME currently MovePicker() c'tor is needless called also in SplitPoint - MovePicker mpBase(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta)); - MovePicker& mp = SpNode ? *sp->mp : mpBase; + MovePickerExt mp(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta)); CheckInfo ci(pos); ss->bestMove = MOVE_NONE; singleEvasion = !SpNode && isCheck && mp.number_of_evasions() == 1; @@ -973,12 +1002,6 @@ split_point_start: // At split points actual search starts from here && !excludedMove // Do not allow recursive singular extension search && (tte->type() & VALUE_TYPE_LOWER) && tte->depth() >= depth - 3 * ONE_PLY; - if (Root) - { - rm = Rml->begin(); - bestValue = alpha; - } - if (SpNode) { lock_grab(&(sp->lock)); @@ -988,16 +1011,25 @@ split_point_start: // At split points actual search starts from here // Step 10. Loop through moves // Loop through all legal moves until no moves remain or a beta cutoff occurs while ( bestValue < beta - && (!Root || rm != Rml->end()) - && ( Root || (move = mp.get_next_move()) != MOVE_NONE) + && (move = mp.get_next_move()) != MOVE_NONE && !ThreadsMgr.cutoff_at_splitpoint(threadID)) { - if (Root) + assert(move_is_ok(move)); + + if (SpNode) { - move = rm->pv[0]; + moveCount = ++sp->moveCount; + lock_release(&(sp->lock)); + } + else if (move == excludedMove) + continue; + else + movesSearched[moveCount++] = move; + if (Root) + { // This is used by time management - FirstRootMove = (rm == Rml->begin()); + FirstRootMove = (moveCount == 1); // Save the current node count before the move is searched nodes = pos.nodes_searched(); @@ -1017,18 +1049,6 @@ split_point_start: // At split points actual search starts from here << " currmovenumber " << moveCount << endl; } - assert(move_is_ok(move)); - - if (SpNode) - { - moveCount = ++sp->moveCount; - lock_release(&(sp->lock)); - } - else if (move == excludedMove) - continue; - else - movesSearched[moveCount++] = move; - isPvMove = (PvNode && moveCount <= (Root ? MultiPV : 1)); moveIsCheck = pos.move_is_check(move, ci); captureOrPromotion = pos.move_is_capture_or_promotion(move); @@ -1213,6 +1233,10 @@ split_point_start: // At split points actual search starts from here if (Root) { + // To avoid to exit with bestValue == -VALUE_INFINITE + if (value > bestValue) + bestValue = value; + // Finished searching the move. If StopRequest is true, the search // was aborted because the user interrupted the search or because we // ran out of time. In this case, the return value of the search cannot @@ -1222,46 +1246,44 @@ split_point_start: // At split points actual search starts from here break; // Remember searched nodes counts for this move - rm->nodes += pos.nodes_searched() - nodes; + mp.rm->nodes += pos.nodes_searched() - nodes; // Step 17. Check for new best move if (!isPvMove && value <= alpha) - rm->pv_score = -VALUE_INFINITE; + mp.rm->pv_score = -VALUE_INFINITE; else { // PV move or new best move! // Update PV ss->bestMove = move; - rm->pv_score = value; - rm->extract_pv_from_tt(pos); + mp.rm->pv_score = value; + mp.rm->extract_pv_from_tt(pos); // We record how often the best move has been changed in each // iteration. This information is used for time managment: When // the best move changes frequently, we allocate some more time. if (!isPvMove && MultiPV == 1) - BestMoveChangesByIteration[Iteration]++; + Rml.bestMoveChanges++; // Inform GUI that PV has changed, in case of multi-pv UCI protocol // requires we send all the PV lines properly sorted. - Rml->sort_multipv(moveCount); + Rml.sort_multipv(moveCount); - for (int j = 0; j < Min(MultiPV, (int)Rml->size()); j++) - cout << (*Rml)[j].pv_info_to_uci(pos, alpha, beta, j) << endl; + for (int j = 0; j < Min(MultiPV, (int)Rml.size()); j++) + cout << Rml[j].pv_info_to_uci(pos, depth, alpha, beta, j) << endl; // Update alpha. In multi-pv we don't use aspiration window if (MultiPV == 1) { // Raise alpha to setup proper non-pv search upper bound if (value > alpha) - alpha = bestValue = value; + alpha = value; } else // Set alpha equal to minimum score among the PV lines - alpha = bestValue = (*Rml)[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount? + alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount? } // PV move or new best move - - ++rm; } // Step 18. Check for split @@ -1272,10 +1294,9 @@ split_point_start: // At split points actual search starts from here && bestValue < beta && ThreadsMgr.available_thread_exists(threadID) && !StopRequest - && !ThreadsMgr.cutoff_at_splitpoint(threadID) - && Iteration <= 99) + && !ThreadsMgr.cutoff_at_splitpoint(threadID)) ThreadsMgr.split(pos, ss, ply, &alpha, beta, &bestValue, depth, - threatMove, mateThreat, moveCount, &mp, PvNode); + threatMove, mateThreat, moveCount, (MovePicker*)&mp, PvNode); } // Step 19. Check for mate and stalemate @@ -2528,7 +2549,7 @@ split_point_start: // At split points actual search starts from here // formatted according to UCI specification and eventually writes the info // to a log file. It is called at each iteration or after a new pv is found. - std::string RootMove::pv_info_to_uci(Position& pos, Value alpha, Value beta, int pvLine) { + std::string RootMove::pv_info_to_uci(Position& pos, Depth depth, Value alpha, Value beta, int pvLine) { std::stringstream s, l; Move* m = pv; @@ -2536,7 +2557,7 @@ split_point_start: // At split points actual search starts from here while (*m != MOVE_NONE) l << *m++ << " "; - s << "info depth " << Iteration // FIXME + s << "info depth " << depth / ONE_PLY << " seldepth " << int(m - pv) << " multipv " << pvLine + 1 << " score " << value_to_uci(pv_score) @@ -2551,13 +2572,13 @@ split_point_start: // At split points actual search starts from here ValueType t = pv_score >= beta ? VALUE_TYPE_LOWER : pv_score <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT; - LogFile << pretty_pv(pos, current_search_time(), Iteration, pv_score, t, pv) << endl; + LogFile << pretty_pv(pos, current_search_time(), depth / ONE_PLY, pv_score, t, pv) << endl; } return s.str(); } - RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) { + void RootMoveList::init(Position& pos, Move searchMoves[]) { SearchStack ss[PLY_MAX_PLUS_2]; MoveStack mlist[MOVES_MAX]; @@ -2567,6 +2588,8 @@ split_point_start: // At split points actual search starts from here // Initialize search stack init_ss_array(ss, PLY_MAX_PLUS_2); ss[0].eval = ss[0].evalMargin = VALUE_NONE; + bestMoveChanges = 0; + clear(); // Generate all legal moves MoveStack* last = generate(pos, mlist);