From: Marco Costalba Date: Sat, 18 Jun 2011 06:43:25 +0000 (+0100) Subject: Use an array index instead of an iterator in root list X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=8173d92dd2b339e02dcf0ae6de9954ef33e3e0a1 Use an array index instead of an iterator in root list It is not correct to use an iterator stick on a vector that is sorted becuase iterator is invalidated in general case. It happens to work by accident because iterators are implemented as pointers and so they behave in the same (correct) way then using array indices, but the latters are the correct thing to use. Also better document the code. No functional change. Signed-off-by: Marco Costalba --- 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