/// Namespace variables
std::vector<RootMove> RootMoves;
- size_t MultiPV, UCIMultiPV, MultiPVIdx;
+ size_t MultiPV, UCIMultiPV, PVIdx;
TimeManager TimeMgr;
int BestMoveChanges;
int SkillLevel;
/// Local functions
- Move id_loop(Position& pos, Move* ponderMove);
+ void id_loop(Position& pos);
template <NodeType NT>
Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth);
bool connected_threat(const Position& pos, Move m, Move threat);
Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
- void do_skill_level(Move* best, Move* ponder);
+ Move do_skill_level();
int elapsed_time(bool reset = false);
string score_to_uci(Value v, Value alpha = -VALUE_INFINITE, Value beta = VALUE_INFINITE);
- string speed_to_uci(int64_t nodes);
- string pv_to_uci(const Move pv[], int pvNum, bool chess960);
- string pretty_pv(Position& pos, int depth, Value score, int time, Move pv[]);
- string depth_to_uci(Depth depth);
+ void pv_info_to_log(Position& pos, int depth, Value score, int time, Move pv[]);
+ void pv_info_to_uci(const Position& pos, int depth, Value alpha, Value beta);
// MovePickerExt class template extends MovePicker and allows to choose at
// compile time the proper moves source according to the type of node. In the
} // namespace
-/// init_search() is called during startup to initialize various lookup tables
+/// Search::init() is called during startup to initialize various lookup tables
void Search::init() {
}
-/// perft() is our utility to verify move generation. All the leaf nodes up to
-/// the given depth are generated and counted and the sum returned.
+/// Search::perft() is our utility to verify move generation. All the leaf nodes
+/// up to the given depth are generated and counted and the sum returned.
int64_t Search::perft(Position& pos, Depth depth) {
}
-/// think() is the external interface to Stockfish's search, and is called by the
-/// main thread when the program receives the UCI 'go' command. It searches from
-/// RootPosition and at the end prints the "bestmove" to output.
+/// Search::think() is the external interface to Stockfish's search, and is
+/// called by the main thread when the program receives the UCI 'go' command. It
+/// searches from RootPosition and at the end prints the "bestmove" to output.
void Search::think() {
Position& pos = RootPosition;
elapsed_time(true);
TimeMgr.init(Limits, pos.startpos_ply_counter());
+ TT.new_search();
+ H.clear();
+ RootMoves.clear();
+
+ // Populate RootMoves with all the legal moves (default) or, if a SearchMoves
+ // is given, with the subset of legal moves to search.
+ for (MoveList<MV_LEGAL> ml(pos); !ml.end(); ++ml)
+ if ( SearchMoves.empty()
+ || std::count(SearchMoves.begin(), SearchMoves.end(), ml.move()))
+ RootMoves.push_back(RootMove(ml.move()));
// Set output stream mode: normal or chess960. Castling notation is different
cout << set960(pos.is_chess960());
<< endl;
}
- // Wake up needed threads and reset maxPly counter
for (int i = 0; i < Threads.size(); i++)
{
Threads[i].maxPly = 0;
else
Threads.set_timer(100);
- // We're ready to start thinking. Call the iterative deepening loop function
- Move ponderMove = MOVE_NONE;
- Move bestMove = id_loop(pos, &ponderMove);
+ // We're ready to start searching. Call the iterative deepening loop function
+ id_loop(pos);
// Stop timer and send all the slaves to sleep, if not already sleeping
Threads.set_timer(0);
Log log(Options["Search Log Filename"].value<string>());
log << "Nodes: " << pos.nodes_searched()
<< "\nNodes/second: " << (e > 0 ? pos.nodes_searched() * 1000 / e : 0)
- << "\nBest move: " << move_to_san(pos, bestMove);
+ << "\nBest move: " << move_to_san(pos, RootMoves[0].pv[0]);
StateInfo st;
- pos.do_move(bestMove, st);
- log << "\nPonder move: " << move_to_san(pos, ponderMove) << endl;
- pos.undo_move(bestMove); // Return from think() with unchanged position
+ pos.do_move(RootMoves[0].pv[0], st);
+ log << "\nPonder move: " << move_to_san(pos, RootMoves[0].pv[1]) << endl;
+ pos.undo_move(RootMoves[0].pv[0]);
}
// When we reach max depth we arrive here even without a StopRequest, but if
Threads.wait_for_stop_or_ponderhit();
// Could be MOVE_NONE when searching on a stalemate position
- cout << "bestmove " << bestMove;
+ cout << "bestmove " << RootMoves[0].pv[0];
// UCI protol is not clear on allowing sending an empty ponder move, instead
// it is clear that ponder move is optional. So skip it if empty.
- if (ponderMove != MOVE_NONE)
- cout << " ponder " << ponderMove;
+ if (RootMoves[0].pv[1] != MOVE_NONE)
+ cout << " ponder " << RootMoves[0].pv[1];
cout << endl;
}
// with increasing depth until the allocated thinking time has been consumed,
// user stops the search, or the maximum search depth is reached.
- Move id_loop(Position& pos, Move* ponderMove) {
+ void id_loop(Position& pos) {
Stack ss[PLY_MAX_PLUS_2];
- Value bestValues[PLY_MAX_PLUS_2];
- int bestMoveChanges[PLY_MAX_PLUS_2];
- int depth, aspirationDelta;
- Value bestValue, alpha, beta;
- Move bestMove, skillBest, skillPonder;
+ int depth, prevBestMoveChanges;
+ Value bestValue, alpha, beta, delta;
bool bestMoveNeverChanged = true;
+ Move skillBest = MOVE_NONE;
memset(ss, 0, 4 * sizeof(Stack));
- TT.new_search();
- H.clear();
- RootMoves.clear();
- *ponderMove = bestMove = skillBest = skillPonder = MOVE_NONE;
- depth = aspirationDelta = 0;
- bestValue = alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
+ depth = BestMoveChanges = 0;
+ bestValue = delta = -VALUE_INFINITE;
ss->currentMove = MOVE_NULL; // Hack to skip update gains
- for (MoveList<MV_LEGAL> ml(pos); !ml.end(); ++ml)
- if ( SearchMoves.empty()
- || std::count(SearchMoves.begin(), SearchMoves.end(), ml.move()))
- RootMoves.push_back(RootMove(ml.move()));
-
- // Handle special case of searching on a mate/stalemate position
+ // Handle the special case of a mate/stalemate position
if (RootMoves.empty())
{
- cout << "info" << depth_to_uci(DEPTH_ZERO)
- << score_to_uci(pos.in_check() ? -VALUE_MATE : VALUE_DRAW, alpha, beta) << endl;
+ cout << "info depth 0"
+ << score_to_uci(pos.in_check() ? -VALUE_MATE : VALUE_DRAW) << endl;
- return MOVE_NONE;
+ RootMoves.push_back(MOVE_NONE);
+ return;
}
// Iterative deepening loop until requested to stop or target depth reached
while (!Signals.stop && ++depth <= PLY_MAX && (!Limits.maxDepth || depth <= Limits.maxDepth))
{
- // Save now last iteration's scores, before Rml moves are reordered
+ // Save last iteration's scores before first PV line is searched and all
+ // the move scores but the (new) PV are set to -VALUE_INFINITE.
for (size_t i = 0; i < RootMoves.size(); i++)
RootMoves[i].prevScore = RootMoves[i].score;
+ prevBestMoveChanges = BestMoveChanges;
BestMoveChanges = 0;
// MultiPV loop. We perform a full root search for each PV line
- for (MultiPVIdx = 0; MultiPVIdx < std::min(MultiPV, RootMoves.size()); MultiPVIdx++)
+ for (PVIdx = 0; PVIdx < std::min(MultiPV, RootMoves.size()); PVIdx++)
{
- // Calculate dynamic aspiration window based on previous iterations
- if (depth >= 5 && abs(RootMoves[MultiPVIdx].prevScore) < VALUE_KNOWN_WIN)
+ // Set aspiration window default width
+ if (depth >= 5 && abs(RootMoves[PVIdx].prevScore) < VALUE_KNOWN_WIN)
{
- int prevDelta1 = bestValues[depth - 1] - bestValues[depth - 2];
- int prevDelta2 = bestValues[depth - 2] - bestValues[depth - 3];
-
- aspirationDelta = std::min(std::max(abs(prevDelta1) + abs(prevDelta2) / 2, 16), 24);
- aspirationDelta = (aspirationDelta + 7) / 8 * 8; // Round to match grainSize
-
- alpha = std::max(RootMoves[MultiPVIdx].prevScore - aspirationDelta, -VALUE_INFINITE);
- beta = std::min(RootMoves[MultiPVIdx].prevScore + aspirationDelta, VALUE_INFINITE);
+ delta = Value(16);
+ alpha = RootMoves[PVIdx].prevScore - delta;
+ beta = RootMoves[PVIdx].prevScore + delta;
}
else
{
// we want to keep the same order for all the moves but the new
// PV that goes to the front. Note that in case of MultiPV search
// the already searched PV lines are preserved.
- sort<RootMove>(RootMoves.begin() + MultiPVIdx, RootMoves.end());
+ sort<RootMove>(RootMoves.begin() + PVIdx, RootMoves.end());
// In case we have found an exact score and we are going to leave
// the fail high/low loop then reorder the PV moves, otherwise
// leave the last PV move in its position so to be searched again.
// Of course this is needed only in MultiPV search.
- if (MultiPVIdx && bestValue > alpha && bestValue < beta)
- sort<RootMove>(RootMoves.begin(), RootMoves.begin() + MultiPVIdx);
+ if (PVIdx && bestValue > alpha && bestValue < beta)
+ sort<RootMove>(RootMoves.begin(), RootMoves.begin() + PVIdx);
- // Write PV back to transposition table in case the relevant entries
- // have been overwritten during the search.
- for (size_t i = 0; i <= MultiPVIdx; i++)
+ // Write PV back to transposition table in case the relevant
+ // entries have been overwritten during the search.
+ for (size_t i = 0; i <= PVIdx; i++)
RootMoves[i].insert_pv_in_tt(pos);
- // If search has been stopped exit the aspiration window loop,
- // note that sorting and writing PV back to TT is safe becuase
- // Rml is still valid, although refers to the previous iteration.
+ // If search has been stopped exit the aspiration window loop.
+ // Sorting and writing PV back to TT is safe becuase RootMoves
+ // is still valid, although refers to previous iteration.
if (Signals.stop)
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. UCI
- // protocol requires to send all the PV lines also if are still
- // to be searched and so refer to the previous search's score.
+ // if we have a fail high/low and we are deep in the search.
if ((bestValue > alpha && bestValue < beta) || elapsed_time() > 2000)
- for (size_t i = 0; i < std::min(UCIMultiPV, RootMoves.size()); i++)
- {
- bool updated = (i <= MultiPVIdx);
-
- if (depth == 1 && !updated)
- continue;
-
- Depth d = (updated ? depth : depth - 1) * ONE_PLY;
- Value s = (updated ? RootMoves[i].score : RootMoves[i].prevScore);
-
- cout << "info"
- << depth_to_uci(d)
- << (i == MultiPVIdx ? score_to_uci(s, alpha, beta) : score_to_uci(s))
- << speed_to_uci(pos.nodes_searched())
- << pv_to_uci(&RootMoves[i].pv[0], i + 1, pos.is_chess960())
- << endl;
- }
+ pv_info_to_uci(pos, depth, alpha, beta);
// In case of failing high/low increase aspiration window and
// research, otherwise exit the fail high/low loop.
if (bestValue >= beta)
{
- beta = std::min(beta + aspirationDelta, VALUE_INFINITE);
- aspirationDelta += aspirationDelta / 2;
+ beta += delta;
+ delta += delta / 2;
}
else if (bestValue <= alpha)
{
Signals.failedLowAtRoot = true;
Signals.stopOnPonderhit = false;
- alpha = std::max(alpha - aspirationDelta, -VALUE_INFINITE);
- aspirationDelta += aspirationDelta / 2;
+ alpha -= delta;
+ delta += delta / 2;
}
else
break;
+ assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
+
} while (abs(bestValue) < VALUE_KNOWN_WIN);
}
- bestMove = RootMoves[0].pv[0];
- *ponderMove = RootMoves[0].pv[1];
- bestValues[depth] = bestValue;
- bestMoveChanges[depth] = BestMoveChanges;
-
- // Skills: Do we need to pick now the best and the ponder moves ?
+ // Skills: Do we need to pick now the best move ?
if (SkillLevelEnabled && depth == 1 + SkillLevel)
- do_skill_level(&skillBest, &skillPonder);
+ skillBest = do_skill_level();
if (Options["Use Search Log"].value<bool>())
- {
- Log log(Options["Search Log Filename"].value<string>());
- log << pretty_pv(pos, depth, bestValue, elapsed_time(), &RootMoves[0].pv[0]) << endl;
- }
+ pv_info_to_log(pos, depth, bestValue, elapsed_time(), &RootMoves[0].pv[0]);
// Filter out startup noise when monitoring best move stability
- if (depth > 2 && bestMoveChanges[depth])
+ if (depth > 2 && BestMoveChanges)
bestMoveNeverChanged = false;
// Do we have time for the next iteration? Can we stop searching now?
if (!Signals.stop && !Signals.stopOnPonderhit && Limits.useTimeManagement())
{
- bool stop = false; // Local variable instead of the volatile Signals.stop
+ bool stop = false; // Local variable, not the volatile Signals.stop
// Take in account some extra time if the best move has changed
if (depth > 4 && depth < 50)
- TimeMgr.pv_instability(bestMoveChanges[depth], bestMoveChanges[depth - 1]);
+ TimeMgr.pv_instability(BestMoveChanges, prevBestMoveChanges);
- // Stop search if most of available time is already consumed. We probably don't
- // have enough time to search the first move at the next iteration anyway.
+ // Stop search if most of available time is already consumed. We
+ // probably don't have enough time to search the first move at the
+ // next iteration anyway.
if (elapsed_time() > (TimeMgr.available_time() * 62) / 100)
stop = true;
|| elapsed_time() > (TimeMgr.available_time() * 40) / 100))
{
Value rBeta = bestValue - EasyMoveMargin;
- (ss+1)->excludedMove = bestMove;
+ (ss+1)->excludedMove = RootMoves[0].pv[0];
(ss+1)->skipNullMove = true;
Value v = search<NonPV>(pos, ss+1, rBeta - 1, rBeta, (depth * ONE_PLY) / 2);
(ss+1)->skipNullMove = false;
}
}
- // When using skills overwrite best and ponder moves with the sub-optimal ones
+ // When using skills swap best PV line with the sub-optimal one
if (SkillLevelEnabled)
{
if (skillBest == MOVE_NONE) // Still unassigned ?
- do_skill_level(&skillBest, &skillPonder);
+ skillBest = do_skill_level();
- bestMove = skillBest;
- *ponderMove = skillPonder;
+ std::swap(RootMoves[0], *std::find(RootMoves.begin(), RootMoves.end(), skillBest));
}
-
- return bestMove;
}
excludedMove = ss->excludedMove;
posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
tte = TT.probe(posKey);
- ttMove = RootNode ? RootMoves[MultiPVIdx].pv[0] : tte ? tte->move() : MOVE_NONE;
+ ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE;
// At PV nodes we check for exact scores, while at non-PV nodes we check for
// a fail high/low. Biggest advantage at probing at PV nodes is to have a
// At root obey the "searchmoves" option and skip moves not listed in Root
// Move List, as a consequence any illegal move is also skipped. In MultiPV
// mode we also skip PV moves which have been already searched.
- if (RootNode && !std::count(RootMoves.begin() + MultiPVIdx, RootMoves.end(), move))
+ if (RootNode && !std::count(RootMoves.begin() + PVIdx, RootMoves.end(), move))
continue;
// At PV and SpNode nodes we want all moves to be legal since the beginning
nodes = pos.nodes_searched();
if (pos.thread() == 0 && elapsed_time() > 2000)
- cout << "info" << depth_to_uci(depth)
+ cout << "info depth " << depth / ONE_PLY
<< " currmove " << move
- << " currmovenumber " << moveCount + MultiPVIdx << endl;
+ << " currmovenumber " << moveCount + PVIdx << endl;
}
isPvMove = (PvNode && moveCount <= 1);
}
- // speed_to_uci() returns a string with time stats of current search suitable
- // to be sent to UCI gui.
+ // pv_info_to_uci() sends search info to GUI. UCI protocol requires to send all
+ // the PV lines also if are still to be searched and so refer to the previous
+ // search score.
- string speed_to_uci(int64_t nodes) {
+ void pv_info_to_uci(const Position& pos, int depth, Value alpha, Value beta) {
- std::stringstream s;
int t = elapsed_time();
-
- s << " nodes " << nodes
- << " nps " << (t > 0 ? int(nodes * 1000 / t) : 0)
- << " time " << t;
-
- return s.str();
- }
-
-
- // pv_to_uci() returns a string with information on the current PV line
- // formatted according to UCI specification.
-
- string pv_to_uci(const Move pv[], int pvNum, bool chess960) {
-
- std::stringstream s;
-
- s << " multipv " << pvNum << " pv " << set960(chess960);
-
- for ( ; *pv != MOVE_NONE; pv++)
- s << *pv << " ";
-
- return s.str();
- }
-
-
- // depth_to_uci() returns a string with information on the current depth and
- // seldepth formatted according to UCI specification.
-
- string depth_to_uci(Depth depth) {
-
- std::stringstream s;
int selDepth = 0;
- // Retrieve max searched depth among threads
for (int i = 0; i < Threads.size(); i++)
if (Threads[i].maxPly > selDepth)
selDepth = Threads[i].maxPly;
- s << " depth " << depth / ONE_PLY << " seldepth " << selDepth;
+ for (size_t i = 0; i < std::min(UCIMultiPV, RootMoves.size()); i++)
+ {
+ bool updated = (i <= PVIdx);
- return s.str();
+ if (depth == 1 && !updated)
+ continue;
+
+ int d = (updated ? depth : depth - 1);
+ Value s = (updated ? RootMoves[i].score : RootMoves[i].prevScore);
+
+ cout << "info"
+ << " depth " << d
+ << " seldepth " << selDepth
+ << (i == PVIdx ? score_to_uci(s, alpha, beta) : score_to_uci(s))
+ << " nodes " << pos.nodes_searched()
+ << " nps " << (t > 0 ? pos.nodes_searched() * 1000 / t : 0)
+ << " time " << t
+ << " multipv " << i + 1 << " pv";
+
+ for (int j = 0; RootMoves[i].pv[j] != MOVE_NONE; j++)
+ cout << " " << RootMoves[i].pv[j];
+
+ cout << endl;
+ }
}
- // pretty_pv() creates a human-readable string from a position and a PV. It is
- // used to write search information to the log file (which is created when the
- // UCI parameter "Use Search Log" is "true"). It uses the two below helper to
- // pretty format time and score respectively.
+ // pv_info_to_log() writes human-readable search information to the log file
+ // (which is created when the UCI parameter "Use Search Log" is "true"). It
+ // uses the two below helpers to pretty format time and score respectively.
string time_to_string(int millisecs) {
return s.str();
}
- string pretty_pv(Position& pos, int depth, Value value, int time, Move pv[]) {
+ void pv_info_to_log(Position& pos, int depth, Value value, int time, Move pv[]) {
const int64_t K = 1000;
const int64_t M = 1000000;
if (pos.nodes_searched() < M)
s << std::setw(8) << pos.nodes_searched() / 1 << " ";
+
else if (pos.nodes_searched() < K * M)
s << std::setw(7) << pos.nodes_searched() / K << "K ";
+
else
s << std::setw(7) << pos.nodes_searched() / M << "M ";
pos.do_move(*m++, *st++);
}
- // Restore original position before to leave
while (m != pv)
pos.undo_move(*--m);
- return s.str();
+ Log l(Options["Search Log Filename"].value<string>());
+ l << s.str() << endl;
}
// When playing with strength handicap choose best move among the MultiPV set
// using a statistical rule dependent on SkillLevel. Idea by Heinz van Saanen.
- void do_skill_level(Move* best, Move* ponder) {
+ Move do_skill_level() {
assert(MultiPV > 1);
int variance = std::min(RootMoves[0].score - RootMoves[size - 1].score, PawnValueMidgame);
int weakness = 120 - 2 * SkillLevel;
int max_s = -VALUE_INFINITE;
+ Move best = MOVE_NONE;
// Choose best move. For each move score we add two terms both dependent on
// weakness, one deterministic and bigger for weaker moves, and one random,
if (s > max_s)
{
max_s = s;
- *best = RootMoves[i].pv[0];
- *ponder = RootMoves[i].pv[1];
+ best = RootMoves[i].pv[0];
}
}
+ return best;
}
Value v, m = VALUE_NONE;
int ply = 0;
- assert(pv[0] != MOVE_NONE && pos.is_pseudo_legal(pv[0]));
+ assert(pv[ply] != MOVE_NONE && pos.is_pseudo_legal(pv[ply]));
do {
k = pos.get_key();