X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=94bab30801d39dbb7c186333bf5d43410a166e07;hp=f2dc392ebf2f3747c2248aa6049a901fc03fd819;hb=bb6a6e159adf090413273e0ca92b4f2d0471ef68;hpb=b88f7df3876115ff6cad70d57164012f7f70480b diff --git a/src/search.cpp b/src/search.cpp index f2dc392e..94bab308 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -52,32 +52,31 @@ namespace { enum NodeType { Root, PV, NonPV, SplitPointPV, SplitPointNonPV }; // RootMove struct is used for moves at the root of the tree. For each root - // move, we store a pv_score, a node count, and a PV (really a refutation - // in the case of moves which fail low). Value pv_score is normally set at + // move, we store a score, a node count, and a PV (really a refutation + // in the case of moves which fail low). Score is normally set at // -VALUE_INFINITE for all non-pv moves. struct RootMove { - RootMove(); - RootMove(const RootMove& rm) { *this = rm; } - RootMove& operator=(const RootMove& rm); - // RootMove::operator<() is the comparison function used when // sorting the moves. A move m1 is considered to be better - // than a move m2 if it has an higher pv_score - bool operator<(const RootMove& m) const { return pv_score < m.pv_score; } + // than a move m2 if it has an higher score + bool operator<(const RootMove& m) const { return score < m.score; } void extract_pv_from_tt(Position& pos); void insert_pv_in_tt(Position& pos); int64_t nodes; - Value pv_score; - Move pv[PLY_MAX_PLUS_2]; + Value score; + Value prevScore; + std::vector pv; }; // RootMoveList struct is mainly a std::vector of RootMove objects struct RootMoveList : public std::vector { + void init(Position& pos, Move searchMoves[]); - RootMove* find(const Move &m, const int startIndex = 0); + RootMove* find(const Move& m, int startIndex = 0); + int bestMoveChanges; }; @@ -198,7 +197,7 @@ namespace { bool connected_moves(const Position& pos, Move m1, Move m2); Value value_to_tt(Value v, int ply); Value value_from_tt(Value v, int ply); - bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply); + bool can_return_tt(const TTEntry* tte, Depth depth, Value beta, int ply); bool connected_threat(const Position& pos, Move m, Move threat); Value refine_eval(const TTEntry* tte, Value defaultEval, int ply); void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount); @@ -206,9 +205,9 @@ namespace { void do_skill_level(Move* best, Move* ponder); int current_search_time(int set = 0); - string score_to_uci(Value v, Value alpha, Value beta); + string score_to_uci(Value v, Value alpha = -VALUE_INFINITE, Value beta = VALUE_INFINITE); string speed_to_uci(int64_t nodes); - string pv_to_uci(Move pv[], int pvNum, bool chess960); + string pv_to_uci(const Move pv[], int pvNum, bool chess960); string pretty_pv(Position& pos, int depth, Value score, int time, Move pv[]); string depth_to_uci(Depth depth); void poll(const Position& pos); @@ -224,10 +223,10 @@ namespace { }; // In case of a SpNode we use split point's shared MovePicker object as moves source - template<> struct MovePickerExt : public MovePickerExt { + template<> struct MovePickerExt : public MovePicker { MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) - : MovePickerExt(p, ttm, d, h, ss, b), mp(ss->sp->mp) {} + : MovePicker(p, ttm, d, h, ss, b), mp(ss->sp->mp) {} Move get_next_move() { return mp->get_next_move(); } MovePicker* mp; @@ -536,23 +535,18 @@ namespace { // Iterative deepening loop until requested to stop or target depth reached while (!StopRequest && ++depth <= PLY_MAX && (!Limits.maxDepth || depth <= Limits.maxDepth)) { - Rml.bestMoveChanges = 0; - - // Remember best moves and values from previous iteration - std::vector prevMoves; - std::vector prevValues; + // Save last iteration's scores, this needs to be done now, because in + // the following MultiPV loop Rml moves could be reordered. + for (size_t i = 0; i < Rml.size(); i++) + Rml[i].prevScore = Rml[i].score; - for (int i = 0; i < Min(MultiPV, (int)Rml.size()); i++) - { - prevMoves.push_back(Rml[i].pv[0]); - prevValues.push_back(Rml[i].pv_score); - } + Rml.bestMoveChanges = 0; // MultiPV iteration loop for (MultiPVIteration = 0; MultiPVIteration < Min(MultiPV, (int)Rml.size()); MultiPVIteration++) { // Calculate dynamic aspiration window based on previous iterations - if (depth >= 5 && abs(prevValues[MultiPVIteration]) < VALUE_KNOWN_WIN) + if (depth >= 5 && abs(Rml[MultiPVIteration].prevScore) < VALUE_KNOWN_WIN) { int prevDelta1 = bestValues[depth - 1] - bestValues[depth - 2]; int prevDelta2 = bestValues[depth - 2] - bestValues[depth - 3]; @@ -560,8 +554,8 @@ namespace { aspirationDelta = Min(Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16), 24); aspirationDelta = (aspirationDelta + 7) / 8 * 8; // Round to match grainSize - alpha = Max(prevValues[MultiPVIteration] - aspirationDelta, -VALUE_INFINITE); - beta = Min(prevValues[MultiPVIteration] + aspirationDelta, VALUE_INFINITE); + alpha = Max(Rml[MultiPVIteration].prevScore - aspirationDelta, -VALUE_INFINITE); + beta = Min(Rml[MultiPVIteration].prevScore + aspirationDelta, VALUE_INFINITE); } else { @@ -579,12 +573,13 @@ namespace { // because all the values but the first are usually set to // -VALUE_INFINITE and we want to keep the same order for all // the moves but the new PV that goes to head. + sort(Rml.begin() + MultiPVIteration, Rml.end()); + + // In case we have found an exact score reorder the PV moves + // before leaving the fail high/low loop, otherwise leave the + // last PV move in its position so to be searched again. if (value > alpha && value < beta) - sort(Rml.begin(), Rml.end()); - else - // In MultiPV mode, sort only the tail of the list - // until all fail-highs and fail-lows have been resolved - sort(Rml.begin() + MultiPVIteration, Rml.end()); + sort(Rml.begin(), Rml.begin() + MultiPVIteration); // Write PV back to transposition table in case the relevant entries // have been overwritten during the search. @@ -598,22 +593,14 @@ namespace { // Send full PV info to GUI if we are going to leave the loop or // if we have a fail high/low and we are deep in the search. if ((value > alpha && value < beta) || current_search_time() > 2000) - for (int i = 0; i < Min(UCIMultiPV, (int)Rml.size()); i++) + for (int i = 0; i < Min(UCIMultiPV, MultiPVIteration); i++) { - bool updated = (i <= MultiPVIteration); - bool match = (i == MultiPVIteration); - - if (!updated && depth == 1) - continue; - cout << "info" - << depth_to_uci((updated ? depth : depth - 1) * ONE_PLY) - << score_to_uci(updated ? Rml[i].pv_score : prevValues[i], - match ? alpha : -VALUE_INFINITE, - match ? beta : VALUE_INFINITE) + << depth_to_uci(depth * ONE_PLY) + << (i == MultiPVIteration ? score_to_uci(Rml[i].score, alpha, beta) : + score_to_uci(Rml[i].score)) << speed_to_uci(pos.nodes_searched()) - << pv_to_uci(updated ? Rml[i].pv : Rml.find(prevMoves[i])->pv, - i + 1, pos.is_chess960()) + << pv_to_uci(&Rml[i].pv[0], i + 1, pos.is_chess960()) << endl; } @@ -649,10 +636,10 @@ namespace { do_skill_level(&skillBest, &skillPonder); if (LogFile.is_open()) - LogFile << pretty_pv(pos, depth, value, current_search_time(), Rml[0].pv) << endl; + LogFile << pretty_pv(pos, depth, value, current_search_time(), &Rml[0].pv[0]) << endl; // Init easyMove after first iteration or drop if differs from the best move - if (depth == 1 && (Rml.size() == 1 || Rml[0].pv_score > Rml[1].pv_score + EasyMoveMargin)) + if (depth == 1 && (Rml.size() == 1 || Rml[0].score > Rml[1].score + EasyMoveMargin)) easyMove = bestMove; else if (bestMove != easyMove) easyMove = MOVE_NONE; @@ -797,7 +784,7 @@ namespace { // smooth experience in analysis mode. We don't probe at Root nodes otherwise // we should also update RootMoveList to avoid bogus output. if (!RootNode && tte && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT - : ok_to_use_TT(tte, depth, beta, ss->ply))) + : can_return_tt(tte, depth, beta, ss->ply))) { TT.refresh(tte); ss->bestMove = ttMove; // Can be MOVE_NONE @@ -1221,14 +1208,15 @@ split_point_start: // At split points actual search starts from here break; // Remember searched nodes counts for this move - Rml.find(move)->nodes += pos.nodes_searched() - nodes; + RootMove* rm = Rml.find(move); + rm->nodes += pos.nodes_searched() - nodes; // PV move or new best move ? if (isPvMove || value > alpha) { // Update PV - Rml.find(move)->pv_score = value; - Rml.find(move)->extract_pv_from_tt(pos); + rm->score = value; + 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 management: When @@ -1244,7 +1232,7 @@ split_point_start: // At split points actual search starts from here // All other moves but the PV are set to the lowest value, this // is not a problem when sorting becuase sort is stable and move // position in the list is preserved, just the PV is pushed up. - Rml.find(move)->pv_score = -VALUE_INFINITE; + rm->score = -VALUE_INFINITE; } // RootNode @@ -1346,7 +1334,7 @@ split_point_start: // At split points actual search starts from here tte = TT.probe(pos.get_key()); ttMove = (tte ? tte->move() : MOVE_NONE); - if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ss->ply)) + if (!PvNode && tte && can_return_tt(tte, ttDepth, beta, ss->ply)) { ss->bestMove = ttMove; // Can be MOVE_NONE return value_from_tt(tte->value(), ss->ply); @@ -1681,10 +1669,10 @@ split_point_start: // At split points actual search starts from here } - // ok_to_use_TT() returns true if a transposition table score - // can be used 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 ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) { + bool can_return_tt(const TTEntry* tte, Depth depth, Value beta, int ply) { Value v = value_from_tt(tte->value(), ply); @@ -1803,7 +1791,7 @@ split_point_start: // At split points actual search starts from here // pv_to_uci() returns a string with information on the current PV line // formatted according to UCI specification. - string pv_to_uci(Move pv[], int pvNum, bool chess960) { + string pv_to_uci(const Move pv[], int pvNum, bool chess960) { std::stringstream s; @@ -2024,12 +2012,12 @@ split_point_start: // At split points actual search starts from here static RKISS rk; - // Rml list is already sorted by pv_score in descending order + // Rml list is already sorted by score in descending order int s; int max_s = -VALUE_INFINITE; int size = Min(MultiPV, (int)Rml.size()); - int max = Rml[0].pv_score; - int var = Min(max - Rml[size - 1].pv_score, PawnValueMidgame); + int max = Rml[0].score; + int var = Min(max - Rml[size - 1].score, PawnValueMidgame); int wk = 120 - 2 * SkillLevel; // PRNG sequence should be non deterministic @@ -2041,10 +2029,10 @@ split_point_start: // At split points actual search starts from here // then we choose the move with the resulting highest score. for (int i = 0; i < size; i++) { - s = Rml[i].pv_score; + s = Rml[i].score; // Don't allow crazy blunders even at very low skills - if (i > 0 && Rml[i-1].pv_score > s + EasyMoveMargin) + if (i > 0 && Rml[i-1].score > s + EasyMoveMargin) break; // This is our magical formula @@ -2062,26 +2050,6 @@ split_point_start: // At split points actual search starts from here /// RootMove and RootMoveList method's definitions - RootMove::RootMove() { - - nodes = 0; - pv_score = -VALUE_INFINITE; - pv[0] = MOVE_NONE; - } - - RootMove& RootMove::operator=(const RootMove& rm) { - - const Move* src = rm.pv; - Move* dst = pv; - - // Avoid a costly full rm.pv[] copy - do *dst++ = *src; while (*src++ != MOVE_NONE); - - nodes = rm.nodes; - pv_score = rm.pv_score; - return *this; - } - void RootMoveList::init(Position& pos, Move searchMoves[]) { Move* sm; @@ -2099,22 +2067,21 @@ split_point_start: // At split points actual search starts from here continue; RootMove rm; - rm.pv[0] = ml.move(); - rm.pv[1] = MOVE_NONE; - rm.pv_score = -VALUE_INFINITE; + rm.pv.push_back(ml.move()); + rm.pv.push_back(MOVE_NONE); + rm.score = rm.prevScore = -VALUE_INFINITE; + rm.nodes = 0; push_back(rm); } } - RootMove* RootMoveList::find(const Move &m, const int startIndex) { + RootMove* RootMoveList::find(const Move& m, int startIndex) { - for (int i = startIndex; i < int(size()); i++) - { - if ((*this)[i].pv[0] == m) - return &(*this)[i]; - } + for (size_t i = startIndex; i < size(); i++) + if ((*this)[i].pv[0] == m) + return &(*this)[i]; - return NULL; + return NULL; } // extract_pv_from_tt() builds a PV by adding moves from the transposition table. @@ -2127,10 +2094,13 @@ split_point_start: // At split points actual search starts from here StateInfo state[PLY_MAX_PLUS_2], *st = state; TTEntry* tte; int ply = 1; + Move m = pv[0]; - assert(pv[0] != MOVE_NONE && pos.move_is_pl(pv[0])); + assert(m != MOVE_NONE && pos.move_is_pl(m)); - pos.do_move(pv[0], *st++); + pv.clear(); + pv.push_back(m); + pos.do_move(m, *st++); while ( (tte = TT.probe(pos.get_key())) != NULL && tte->move() != MOVE_NONE @@ -2139,10 +2109,11 @@ split_point_start: // At split points actual search starts from here && ply < PLY_MAX && (!pos.is_draw() || ply < 2)) { - pv[ply] = tte->move(); - pos.do_move(pv[ply++], *st++); + pv.push_back(tte->move()); + pos.do_move(tte->move(), *st++); + ply++; } - pv[ply] = MOVE_NONE; + pv.push_back(MOVE_NONE); do pos.undo_move(pv[--ply]); while (ply); }