// 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<RootMove> {
typedef std::vector<RootMove> 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<RootMove, Base::iterator>(begin(), end()); }
+ void sort_multipv(int n) { insertion_sort<RootMove, Base::iterator>(begin(), begin() + n); }
};
value = -search<NonPV>(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<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
- doFullDepthSearch = (value > alpha);
- }
ss->reduction = DEPTH_ZERO; // Restore original reduction
}
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<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, ply+1);
- doFullDepthSearch = (value > alpha);
- }
ss->reduction = DEPTH_ZERO; // Restore original reduction
}
/// 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);
// 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<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
- pos.undo_move(cur->move);
push_back(rm);
+
+ pos.undo_move(cur->move);
}
sort();
}
}
}
- // 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