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 two scores, a node count, and a PV (really a refutation
+ // 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
- // -VALUE_INFINITE for all non-pv moves, while non_pv_score is computed
- // according to the order in which moves are returned by MovePicker.
+ // -VALUE_INFINITE for all non-pv moves.
struct RootMove {
RootMove();
// 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, 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;
- }
+ // than a move m2 if it has an higher pv_score
+ bool operator<(const RootMove& m) const { return pv_score < m.pv_score; }
void extract_pv_from_tt(Position& pos);
void insert_pv_in_tt(Position& pos);
int64_t nodes;
Value pv_score;
- Value non_pv_score;
Move pv[PLY_MAX_PLUS_2];
};
// RootMoveList struct is mainly a std::vector of RootMove objects
struct RootMoveList : public std::vector<RootMove> {
void init(Position& pos, Move searchMoves[]);
+ RootMove* find(const Move &m, const int startIndex = 0);
int bestMoveChanges;
};
RootMoveList Rml;
// MultiPV mode
- int MultiPV, UCIMultiPV;
+ int MultiPV, UCIMultiPV, MultiPVIteration;
// Time management variables
bool StopOnPonderhit, FirstRootMove, StopRequest, QuitRequest, AspirationFailLow;
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
: MovePickerExt<SplitPointNonPV>(p, ttm, d, h, ss, b) {}
};
- // In case of a Root node we use RootMoveList as moves source
- template<> struct MovePickerExt<Root> : 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) {
H.clear();
*ponderMove = bestMove = easyMove = skillBest = skillPonder = MOVE_NONE;
depth = aspirationDelta = 0;
- alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
+ value = alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
ss->currentMove = MOVE_NULL; // Hack to skip update_gains()
// Moves to search are verified and copied
{
Rml.bestMoveChanges = 0;
- // Calculate dynamic aspiration window based on previous iterations
- if (MultiPV == 1 && depth >= 5 && abs(bestValues[depth - 1]) < VALUE_KNOWN_WIN)
- {
- int prevDelta1 = bestValues[depth - 1] - bestValues[depth - 2];
- int prevDelta2 = bestValues[depth - 2] - bestValues[depth - 3];
-
- aspirationDelta = Min(Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16), 24);
- aspirationDelta = (aspirationDelta + 7) / 8 * 8; // Round to match grainSize
+ // Remember best moves and values from previous iteration
+ std::vector<Move> prevMoves;
+ std::vector<Value> prevValues;
- alpha = Max(bestValues[depth - 1] - aspirationDelta, -VALUE_INFINITE);
- beta = Min(bestValues[depth - 1] + aspirationDelta, VALUE_INFINITE);
+ 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);
}
- // Start with a small aspiration window and, in case of fail high/low,
- // research with bigger window until not failing high/low anymore.
- do {
- // Search starting from ss+1 to allow calling update_gains()
- value = search<Root>(pos, ss+1, alpha, beta, depth * ONE_PLY);
-
- // Write PV back to transposition table in case the relevant entries
- // have been overwritten during the search.
- for (int i = 0; i < Min(MultiPV, (int)Rml.size()); i++)
- Rml[i].insert_pv_in_tt(pos);
-
- // Value cannot be trusted. Break out immediately!
- if (StopRequest)
- break;
-
- // 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++)
- cout << "info"
- << depth_to_uci(depth * ONE_PLY)
- << score_to_uci(Rml[i].pv_score, alpha, beta)
- << speed_to_uci(pos.nodes_searched())
- << pv_to_uci(Rml[i].pv, i + 1, pos.is_chess960()) << endl;
-
- // In case of failing high/low increase aspiration window and research,
- // otherwise exit the fail high/low loop.
- if (value >= beta)
- {
- beta = Min(beta + aspirationDelta, VALUE_INFINITE);
- aspirationDelta += aspirationDelta / 2;
- }
- else if (value <= alpha)
+ // 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)
{
- AspirationFailLow = true;
- StopOnPonderhit = false;
+ int prevDelta1 = bestValues[depth - 1] - bestValues[depth - 2];
+ int prevDelta2 = bestValues[depth - 2] - bestValues[depth - 3];
- alpha = Max(alpha - aspirationDelta, -VALUE_INFINITE);
- aspirationDelta += aspirationDelta / 2;
+ 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);
}
else
- break;
+ {
+ alpha = -VALUE_INFINITE;
+ beta = VALUE_INFINITE;
+ }
- } while (abs(value) < VALUE_KNOWN_WIN);
+ // Start with a small aspiration window and, in case of fail high/low,
+ // research with bigger window until not failing high/low anymore.
+ do {
+ // Search starting from ss+1 to allow calling update_gains()
+ value = search<Root>(pos, ss+1, alpha, beta, depth * ONE_PLY);
+
+ // It is critical that sorting is done with a stable algorithm
+ // 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.
+ if (value > alpha && value < beta)
+ sort<RootMove>(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<RootMove>(Rml.begin() + MultiPVIteration, Rml.end());
+
+ // Write PV back to transposition table in case the relevant entries
+ // have been overwritten during the search.
+ for (int i = 0; i <= MultiPVIteration; i++)
+ Rml[i].insert_pv_in_tt(pos);
+
+ // Value cannot be trusted. Break out immediately!
+ if (StopRequest)
+ break;
+
+ // 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++)
+ {
+ 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)
+ << speed_to_uci(pos.nodes_searched())
+ << pv_to_uci(updated ? Rml[i].pv : Rml.find(prevMoves[i])->pv,
+ i + 1, pos.is_chess960())
+ << endl;
+ }
+
+ // In case of failing high/low increase aspiration window and research,
+ // otherwise exit the fail high/low loop.
+ if (value >= beta)
+ {
+ beta = Min(beta + aspirationDelta, VALUE_INFINITE);
+ aspirationDelta += aspirationDelta / 2;
+ }
+ else if (value <= alpha)
+ {
+ AspirationFailLow = true;
+ StopOnPonderhit = false;
+
+ alpha = Max(alpha - aspirationDelta, -VALUE_INFINITE);
+ aspirationDelta += aspirationDelta / 2;
+ }
+ else
+ break;
+
+ } while (abs(value) < VALUE_KNOWN_WIN);
+ }
// Collect info about search result
bestMove = Rml[0].pv[0];
split_point_start: // At split points actual search starts from here
// Initialize a MovePicker object for the current position
- MovePickerExt<NT> mp(pos, ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta);
+ MovePickerExt<NT> mp(pos, RootNode ? Rml[MultiPVIteration].pv[0] : ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta);
CheckInfo ci(pos);
ss->bestMove = MOVE_NONE;
futilityBase = ss->eval + ss->evalMargin;
if (move == excludedMove)
continue;
+ // At root obey the "searchmoves" option and skip moves not listed in Root Move List.
+ // Also in MultiPV mode we skip moves which already have got an exact score
+ // in previous MultiPV Iteration.
+ if (RootNode && !Rml.find(move, MultiPVIteration))
+ continue;
+
// At PV and SpNode nodes we want all moves to be legal since the beginning
if ((PvNode || SpNode) && !pos.pl_move_is_legal(move, ci.pinned))
continue;
// For long searches send current move info to GUI
if (current_search_time() > 2000)
cout << "info" << depth_to_uci(depth)
- << " currmove " << move << " currmovenumber " << moveCount << endl;
+ << " currmove " << move << " currmovenumber " << moveCount + MultiPVIteration << endl;
}
// At Root and at first iteration do a PV search on all the moves to score root moves
- isPvMove = (PvNode && moveCount <= (!RootNode ? 1 : depth <= ONE_PLY ? MAX_MOVES : MultiPV));
+ isPvMove = (PvNode && moveCount <= ((RootNode && depth <= ONE_PLY) ? MAX_MOVES : 1));
givesCheck = pos.move_gives_check(move, ci);
captureOrPromotion = pos.move_is_capture_or_promotion(move);
break;
// Remember searched nodes counts for this move
- mp.current().nodes += pos.nodes_searched() - nodes;
+ Rml.find(move)->nodes += pos.nodes_searched() - nodes;
// PV move or new best move ?
if (isPvMove || value > alpha)
{
// Update PV
- mp.current().pv_score = value;
- mp.current().extract_pv_from_tt(pos);
+ Rml.find(move)->pv_score = value;
+ Rml.find(move)->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
if (!isPvMove && MultiPV == 1)
Rml.bestMoveChanges++;
- // It is critical that sorting is done with a stable algorithm
- // 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<RootMove>(Rml.begin(), Rml.begin() + moveCount);
-
- // 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;
- else if (value > alpha)
+ // Update alpha.
+ if (value > alpha)
alpha = value;
}
else
// 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;
+ Rml.find(move)->pv_score = -VALUE_INFINITE;
} // RootNode
RootMove::RootMove() {
nodes = 0;
- pv_score = non_pv_score = -VALUE_INFINITE;
+ pv_score = -VALUE_INFINITE;
pv[0] = MOVE_NONE;
}
nodes = rm.nodes;
pv_score = rm.pv_score;
- non_pv_score = rm.non_pv_score;
return *this;
}
}
}
+ RootMove* RootMoveList::find(const Move &m, const int startIndex) {
+
+ for (int i = startIndex; i < int(size()); i++)
+ {
+ if ((*this)[i].pv[0] == m)
+ return &(*this)[i];
+ }
+
+ return NULL;
+ }
+
// extract_pv_from_tt() builds a PV by adding moves from the transposition table.
// We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
// allow to always have a ponder move even when we fail high at root and also a
do pos.undo_move(pv[--ply]); while (ply);
}
-
- // Specializations for MovePickerExt in case of Root node
- MovePickerExt<Root>::MovePickerExt(const Position& p, Move ttm, Depth d,
- const History& h, SearchStack* ss, Value b)
- : MovePicker(p, ttm, d, h, ss, b), cur(-1) {
- Move move;
- Value score = VALUE_ZERO;
-
- // Score root moves using standard ordering used in main search, the moves
- // are scored according to the order in which they are returned by MovePicker.
- // 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 (RootMoveList::iterator rm = Rml.begin(); rm != Rml.end(); ++rm)
- if (rm->pv[0] == move)
- {
- rm->non_pv_score = score--;
- break;
- }
-
- sort<RootMove>(Rml.begin(), Rml.end());
- }
-
} // namespace
projects / stockfish / blobdiff