X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=b75b6fa850f7d359d269faeac62b58258c55b3c2;hb=58c6e64069cc2d278756fb2e73f54ca5346ec35d;hp=fdad3e51d50f9183c378f1aa1ded6205aa52d426;hpb=30c14fdc9532fc94217eba708653a188a9b24504;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index fdad3e51..b75b6fa8 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -107,51 +107,60 @@ namespace { // RootMove struct is used for moves at the root at the tree. For each root // move, we store two scores, a node count, and a PV (really a refutation - // in the case of moves which fail low). Value pvScore is normally set at - // -VALUE_INFINITE for all non-pv moves, while nonPvScore is computed + // in the case of moves which fail low). Value pv_score is normally set at + // -VALUE_INFINITE for all non-pv moves, while non_pv_score is computed // according to the order in which moves are returned by MovePicker. struct RootMove { - RootMove() : nodes(0) { pv_score = non_pv_score = -VALUE_INFINITE; move = pv[0] = MOVE_NONE; } + RootMove(); RootMove(const RootMove& rm) { *this = rm; } - RootMove& operator=(const RootMove& rm); // Skip costly full pv[] copy + 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 pvScore, or if it has - // equal pvScore but m1 has the higher nonPvScore. In this way - // we are guaranteed that PV moves are always sorted as first. + // than a move m2 if it has an higher pv_score, or if it has + // equal pv_score but m1 has the higher non_pv_score. In this + // way we are guaranteed that PV moves are always sorted as first. bool operator<(const RootMove& m) const { - return pv_score != m.pv_score ? pv_score < m.pv_score : non_pv_score <= m.non_pv_score; + return pv_score != m.pv_score ? pv_score < m.pv_score + : non_pv_score <= m.non_pv_score; } void set_pv(const Move newPv[]); int64_t nodes; - Value pv_score, non_pv_score; - Move move, pv[PLY_MAX_PLUS_2]; + Value pv_score; + Value non_pv_score; + Move move; + Move pv[PLY_MAX_PLUS_2]; }; + RootMove::RootMove() { + + nodes = 0; + pv_score = non_pv_score = -VALUE_INFINITE; + move = pv[0] = MOVE_NONE; + } + RootMove& RootMove::operator=(const RootMove& rm) { - pv_score = rm.pv_score; non_pv_score = rm.non_pv_score; - nodes = rm.nodes; move = rm.move; - set_pv(rm.pv); - return *this; + nodes = rm.nodes; + pv_score = rm.pv_score; + non_pv_score = rm.non_pv_score; + move = rm.move; + set_pv(rm.pv); // Skip costly full pv[] copy + return *this; } void RootMove::set_pv(const Move newPv[]) { - int i = -1; + Move* p = pv; - while (newPv[++i] != MOVE_NONE) - pv[i] = newPv[i]; - - pv[i] = MOVE_NONE; + do *p++ = *newPv; while (*newPv++ != MOVE_NONE); } - // The RootMoveList struct is essentially a std::vector<> of RootMove objects, + // RootMoveList struct is essentially a std::vector<> of RootMove objects, // with an handful of methods above the standard ones. struct RootMoveList : public std::vector { @@ -159,10 +168,10 @@ namespace { typedef std::vector Base; RootMoveList(Position& pos, Move searchMoves[]); - void sort() { sort_multipv((int)size() - 1); } // Sort all items - void set_non_pv_scores(const Position& pos); - void sort_multipv(int n); + + void sort() { insertion_sort(begin(), end()); } + void sort_multipv(int n) { insertion_sort(begin(), begin() + n); } }; @@ -821,18 +830,6 @@ namespace { value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1); doFullDepthSearch = (value > alpha); } - - // The move failed high, but if reduction is very big we could - // face a false positive, retry with a less aggressive reduction, - // if the move fails high again then go with full depth search. - if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY) - { - assert(newDepth - ONE_PLY >= ONE_PLY); - - ss->reduction = ONE_PLY; - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1); - doFullDepthSearch = (value > alpha); - } ss->reduction = DEPTH_ZERO; // Restore original reduction } @@ -1340,19 +1337,6 @@ split_point_start: // At split points actual search starts from here doFullDepthSearch = (value > alpha); } - - // The move failed high, but if reduction is very big we could - // face a false positive, retry with a less aggressive reduction, - // if the move fails high again then go with full depth search. - if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY) - { - assert(newDepth - ONE_PLY >= ONE_PLY); - - ss->reduction = ONE_PLY; - alpha = SpNode ? sp->alpha : alpha; - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, ply+1); - doFullDepthSearch = (value > alpha); - } ss->reduction = DEPTH_ZERO; // Restore original reduction } @@ -2675,14 +2659,12 @@ split_point_start: // At split points actual search starts from here /// The RootMoveList class - // RootMoveList c'tor - RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) { SearchStack ss[PLY_MAX_PLUS_2]; MoveStack mlist[MOVES_MAX]; StateInfo st; - bool includeAllMoves = (searchMoves[0] == MOVE_NONE); + Move* sm; // Initialize search stack init_ss_array(ss, PLY_MAX_PLUS_2); @@ -2691,25 +2673,26 @@ split_point_start: // At split points actual search starts from here // Generate all legal moves MoveStack* last = generate_moves(pos, mlist); - // Add each move to the moves[] array + // Add each move to the RootMoveList's vector for (MoveStack* cur = mlist; cur != last; cur++) { - bool includeMove = includeAllMoves; + // If we have a searchMoves[] list then verify cur->move + // is in the list before to add it. + for (sm = searchMoves; *sm && *sm != cur->move; sm++) {} - for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++) - includeMove = (searchMoves[k] == cur->move); - - if (!includeMove) + if (searchMoves[0] && *sm != cur->move) continue; // Find a quick score for the move and add to the list + pos.do_move(cur->move, st); + RootMove rm; rm.move = ss[0].currentMove = rm.pv[0] = cur->move; rm.pv[1] = MOVE_NONE; - pos.do_move(cur->move, st); rm.pv_score = -qsearch(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1); - pos.undo_move(cur->move); push_back(rm); + + pos.undo_move(cur->move); } sort(); } @@ -2734,22 +2717,4 @@ split_point_start: // At split points actual search starts from here } } - // RootMoveList::sort_multipv() sorts the first few moves in the root move - // list by their scores and depths. It is used to order the different PVs - // correctly in MultiPV mode. - - void RootMoveList::sort_multipv(int n) { - - int i,j; - - for (i = 1; i <= n; i++) - { - const RootMove& rm = this->at(i); - for (j = i; j > 0 && this->at(j - 1) < rm; j--) - (*this)[j] = this->at(j - 1); - - (*this)[j] = rm; - } - } - } // namespace