X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=1ffab9d3f16055b5227317e2340c56861c6d7383;hp=cd8a9e461083a63fd21531fb88cf6944f67db09b;hb=8173d92dd2b339e02dcf0ae6de9954ef33e3e0a1;hpb=808a4fe817f79f472c92e7b9fb914a8be73ff1be diff --git a/src/search.cpp b/src/search.cpp index cd8a9e46..1ffab9d3 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -88,48 +88,11 @@ namespace { void init(Position& pos, Move searchMoves[]); void sort() { insertion_sort(begin(), end()); } - void sort_multipv(int n) { insertion_sort(begin(), begin() + n); } + void sort_first(int n) { insertion_sort(begin(), begin() + n); } int bestMoveChanges; }; - // MovePickerExt template class extends MovePicker and allows to choose at compile - // time the proper moves source according to the type of node. In the default case - // we simply create and use a standard MovePicker object. - template struct MovePickerExt : public MovePicker { - - MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) - : MovePicker(p, ttm, d, h, ss, b) {} - - RootMoveList::iterator rm; // Dummy, needed to compile - }; - - // In case of a SpNode we use split point's shared MovePicker object as moves source - template<> struct MovePickerExt : public MovePickerExt { - - 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) {} - - Move get_next_move() { return mp->get_next_move(); } - MovePicker* mp; - }; - - template<> struct MovePickerExt : public MovePickerExt { - - MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) - : MovePickerExt(p, ttm, d, h, ss, b) {} - }; - - // In case of a Root node we use RootMoveList as moves source - template<> struct MovePickerExt : public MovePicker { - - MovePickerExt(const Position&, Move, Depth, const History&, SearchStack*, Value); - Move get_next_move(); - - RootMoveList::iterator rm; - bool firstCall; - }; - /// Constants @@ -260,6 +223,43 @@ namespace { void poll(const Position& pos); void wait_for_stop_or_ponderhit(); + // MovePickerExt template class extends MovePicker and allows to choose at compile + // time the proper moves source according to the type of node. In the default case + // we simply create and use a standard MovePicker object. + template struct MovePickerExt : public MovePicker { + + MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) + : MovePicker(p, ttm, d, h, ss, b) {} + + RootMove& current() { assert(false); return Rml[0]; } // Dummy, needed to compile + }; + + // In case of a SpNode we use split point's shared MovePicker object as moves source + template<> struct MovePickerExt : public MovePickerExt { + + 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) {} + + Move get_next_move() { return mp->get_next_move(); } + MovePicker* mp; + }; + + template<> struct MovePickerExt : public MovePickerExt { + + MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) + : MovePickerExt(p, ttm, d, h, ss, b) {} + }; + + // In case of a Root node we use RootMoveList as moves source + template<> struct MovePickerExt : public MovePicker { + + MovePickerExt(const Position&, Move, Depth, const History&, SearchStack*, Value); + RootMove& current() { return Rml[cur]; } + Move get_next_move() { return ++cur < (int)Rml.size() ? Rml[cur].pv[0] : MOVE_NONE; } + + int cur; + }; + // Overload operator<<() to make it easier to print moves in a coordinate // notation compatible with UCI protocol. std::ostream& operator<<(std::ostream& os, Move m) { @@ -1214,15 +1214,15 @@ split_point_start: // At split points actual search starts from here break; // Remember searched nodes counts for this move - mp.rm->nodes += pos.nodes_searched() - nodes; + mp.current().nodes += pos.nodes_searched() - nodes; // PV move or new best move ? if (isPvMove || value > alpha) { // Update PV ss->bestMove = move; - mp.rm->pv_score = value; - mp.rm->extract_pv_from_tt(pos); + mp.current().pv_score = value; + mp.current().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 @@ -1230,17 +1230,24 @@ split_point_start: // At split points actual search starts from here if (!isPvMove && MultiPV == 1) Rml.bestMoveChanges++; - Rml.sort_multipv(moveCount); + // It is critical that sorting is done with a stable algorithm + // becuase 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. + Rml.sort_first(moveCount); - // Update alpha. In multi-pv we don't use aspiration window, so - // set alpha equal to minimum score among the PV lines. + // Update alpha. In multi-pv we don't use aspiration window, so set + // alpha equal to minimum score among the PV lines searched so far. if (MultiPV > 1) - alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount? + alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score; else if (value > alpha) alpha = value; } else - mp.rm->pv_score = -VALUE_INFINITE; + // 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. + mp.current().pv_score = -VALUE_INFINITE; } // RootNode @@ -2077,8 +2084,8 @@ split_point_start: // At split points actual search starts from here // Specializations for MovePickerExt in case of Root node MovePickerExt::MovePickerExt(const Position& p, Move ttm, Depth d, - const History& h, SearchStack* ss, Value b) - : MovePicker(p, ttm, d, h, ss, b), firstCall(true) { + const History& h, SearchStack* ss, Value b) + : MovePicker(p, ttm, d, h, ss, b), cur(-1) { Move move; Value score = VALUE_ZERO; @@ -2087,7 +2094,7 @@ split_point_start: // At split points actual search starts from here // This is the second order score that is used to compare the moves when // the first orders pv_score of both moves are equal. while ((move = MovePicker::get_next_move()) != MOVE_NONE) - for (rm = Rml.begin(); rm != Rml.end(); ++rm) + for (RootMoveList::iterator rm = Rml.begin(); rm != Rml.end(); ++rm) if (rm->pv[0] == move) { rm->non_pv_score = score--; @@ -2095,17 +2102,6 @@ split_point_start: // At split points actual search starts from here } Rml.sort(); - rm = Rml.begin(); - } - - Move MovePickerExt::get_next_move() { - - if (!firstCall) - ++rm; - else - firstCall = false; - - return rm != Rml.end() ? rm->pv[0] : MOVE_NONE; } } // namespace