- // To allow access to (ss-7) up to (ss+2), the stack must be oversized.
- // The former is needed to allow update_continuation_histories(ss-1, ...),
- // which accesses its argument at ss-6, also near the root.
- // The latter is needed for statScore and killer initialization.
- Stack stack[MAX_PLY+10], *ss = stack+7;
- Move pv[MAX_PLY+1];
- Value alpha, beta, delta;
- Move lastBestMove = MOVE_NONE;
- Depth lastBestMoveDepth = 0;
- MainThread* mainThread = (this == Threads.main() ? Threads.main() : nullptr);
- double timeReduction = 1, totBestMoveChanges = 0;
- Color us = rootPos.side_to_move();
- int iterIdx = 0;
-
- std::memset(ss-7, 0, 10 * sizeof(Stack));
- for (int i = 7; i > 0; i--)
- (ss-i)->continuationHistory = &this->continuationHistory[0][0][NO_PIECE][0]; // Use as a sentinel
-
- for (int i = 0; i <= MAX_PLY + 2; ++i)
- (ss+i)->ply = i;
-
- ss->pv = pv;
-
- bestValue = delta = alpha = -VALUE_INFINITE;
- beta = VALUE_INFINITE;
-
- if (mainThread)
- {
- if (mainThread->bestPreviousScore == VALUE_INFINITE)
- for (int i = 0; i < 4; ++i)
- mainThread->iterValue[i] = VALUE_ZERO;
- else
- for (int i = 0; i < 4; ++i)
- mainThread->iterValue[i] = mainThread->bestPreviousScore;
- }
-
- size_t multiPV = size_t(Options["MultiPV"]);
- Skill skill(Options["Skill Level"], Options["UCI_LimitStrength"] ? int(Options["UCI_Elo"]) : 0);
-
- // When playing with strength handicap enable MultiPV search that we will
- // use behind the scenes to retrieve a set of possible moves.
- if (skill.enabled())
- multiPV = std::max(multiPV, (size_t)4);
-
- multiPV = std::min(multiPV, rootMoves.size());
-
- complexityAverage.set(174, 1);
-
- trend = SCORE_ZERO;
- optimism[ us] = Value(39);
- optimism[~us] = -optimism[us];
-
- int searchAgainCounter = 0;
-
- // Iterative deepening loop until requested to stop or the target depth is reached
- while ( ++rootDepth < MAX_PLY
- && !Threads.stop
- && !(Limits.depth && mainThread && rootDepth > Limits.depth))
- {
- // Age out PV variability metric
- if (mainThread)
- totBestMoveChanges /= 2;
-
- // Save the last iteration's scores before first PV line is searched and
- // all the move scores except the (new) PV are set to -VALUE_INFINITE.
- for (RootMove& rm : rootMoves)
- rm.previousScore = rm.score;
-
- size_t pvFirst = 0;
- pvLast = 0;
-
- if (!Threads.increaseDepth)
- searchAgainCounter++;
-
- // MultiPV loop. We perform a full root search for each PV line
- for (pvIdx = 0; pvIdx < multiPV && !Threads.stop; ++pvIdx)
- {
- if (pvIdx == pvLast)
- {
- pvFirst = pvLast;
- for (pvLast++; pvLast < rootMoves.size(); pvLast++)
- if (rootMoves[pvLast].tbRank != rootMoves[pvFirst].tbRank)
- break;
- }
-
- // Reset UCI info selDepth for each depth and each PV line
- selDepth = 0;
-
- // Reset aspiration window starting size
- if (rootDepth >= 4)
- {
- Value prev = rootMoves[pvIdx].averageScore;
- delta = Value(16) + int(prev) * prev / 19178;
- alpha = std::max(prev - delta,-VALUE_INFINITE);
- beta = std::min(prev + delta, VALUE_INFINITE);
-
- // Adjust trend and optimism based on root move's previousScore
- int tr = sigmoid(prev, 3, 8, 90, 125, 1);
- trend = (us == WHITE ? make_score(tr, tr / 2)
- : -make_score(tr, tr / 2));
-
- int opt = sigmoid(prev, 8, 17, 144, 13966, 183);
- optimism[ us] = Value(opt);
- optimism[~us] = -optimism[us];
- }
-
- // Start with a small aspiration window and, in the case of a fail
- // high/low, re-search with a bigger window until we don't fail
- // high/low anymore.
- int failedHighCnt = 0;
- while (true)
- {
- // Adjust the effective depth searched, but ensuring at least one effective increment for every
- // four searchAgain steps (see issue #2717).
- Depth adjustedDepth = std::max(1, rootDepth - failedHighCnt - 3 * (searchAgainCounter + 1) / 4);
- bestValue = Stockfish::search<Root>(rootPos, ss, alpha, beta, adjustedDepth, false);
-
- // Bring the best move to the front. It is critical that sorting
- // is done with a stable algorithm because all the values but the
- // first and eventually the new best one are set to -VALUE_INFINITE
- // and we want to keep the same order for all the moves except the
- // new PV that goes to the front. Note that in case of MultiPV
- // search the already searched PV lines are preserved.
- std::stable_sort(rootMoves.begin() + pvIdx, rootMoves.begin() + pvLast);
-
- // If search has been stopped, we break immediately. Sorting is
- // safe because RootMoves is still valid, although it refers to
- // the previous iteration.
- if (Threads.stop)
- break;
-
- // When failing high/low give some update (without cluttering
- // the UI) before a re-search.
- if ( mainThread
- && multiPV == 1
- && (bestValue <= alpha || bestValue >= beta)
- && Time.elapsed() > 3000)
- sync_cout << UCI::pv(rootPos, rootDepth, alpha, beta) << sync_endl;
-
- // In case of failing low/high increase aspiration window and
- // re-search, otherwise exit the loop.
- if (bestValue <= alpha)
- {
- beta = (alpha + beta) / 2;
- alpha = std::max(bestValue - delta, -VALUE_INFINITE);
-
- failedHighCnt = 0;
- if (mainThread)
- mainThread->stopOnPonderhit = false;
- }
- else if (bestValue >= beta)
- {
- beta = std::min(bestValue + delta, VALUE_INFINITE);
- ++failedHighCnt;
- }
- else
- break;
-
- delta += delta / 4 + 2;
-
- assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
- }
-
- // Sort the PV lines searched so far and update the GUI
- std::stable_sort(rootMoves.begin() + pvFirst, rootMoves.begin() + pvIdx + 1);
-
- if ( mainThread
- && (Threads.stop || pvIdx + 1 == multiPV || Time.elapsed() > 3000))
- sync_cout << UCI::pv(rootPos, rootDepth, alpha, beta) << sync_endl;
- }
-
- if (!Threads.stop)
- completedDepth = rootDepth;
-
- if (rootMoves[0].pv[0] != lastBestMove) {
- lastBestMove = rootMoves[0].pv[0];
- lastBestMoveDepth = rootDepth;
- }
-
- // Have we found a "mate in x"?
- if ( Limits.mate
- && bestValue >= VALUE_MATE_IN_MAX_PLY
- && VALUE_MATE - bestValue <= 2 * Limits.mate)
- Threads.stop = true;
-
- if (!mainThread)
- continue;
-
- // If skill level is enabled and time is up, pick a sub-optimal best move
- if (skill.enabled() && skill.time_to_pick(rootDepth))
- skill.pick_best(multiPV);
-
- // Use part of the gained time from a previous stable move for the current move
- for (Thread* th : Threads)
- {
- totBestMoveChanges += th->bestMoveChanges;
- th->bestMoveChanges = 0;
- }
-
- // Do we have time for the next iteration? Can we stop searching now?
- if ( Limits.use_time_management()
- && !Threads.stop
- && !mainThread->stopOnPonderhit)
- {
- double fallingEval = (69 + 12 * (mainThread->bestPreviousAverageScore - bestValue)
- + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 781.4;
- fallingEval = std::clamp(fallingEval, 0.5, 1.5);
-
- // If the bestMove is stable over several iterations, reduce time accordingly
- timeReduction = lastBestMoveDepth + 10 < completedDepth ? 1.63 : 0.73;
- double reduction = (1.56 + mainThread->previousTimeReduction) / (2.20 * timeReduction);
- double bestMoveInstability = 1 + 1.7 * totBestMoveChanges / Threads.size();
- int complexity = mainThread->complexityAverage.value();
- double complexPosition = std::min(1.0 + (complexity - 277) / 1819.1, 1.5);
-
- double totalTime = Time.optimum() * fallingEval * reduction * bestMoveInstability * complexPosition;
-
- // Cap used time in case of a single legal move for a better viewer experience in tournaments
- // yielding correct scores and sufficiently fast moves.
- if (rootMoves.size() == 1)
- totalTime = std::min(500.0, totalTime);
-
- // Stop the search if we have exceeded the totalTime
- if (Time.elapsed() > totalTime)
- {
- // If we are allowed to ponder do not stop the search now but
- // keep pondering until the GUI sends "ponderhit" or "stop".
- if (mainThread->ponder)
- mainThread->stopOnPonderhit = true;
- else
- Threads.stop = true;
- }
- else if ( Threads.increaseDepth
- && !mainThread->ponder
- && Time.elapsed() > totalTime * 0.43)
- Threads.increaseDepth = false;
- else
- Threads.increaseDepth = true;
- }
-
- mainThread->iterValue[iterIdx] = bestValue;
- iterIdx = (iterIdx + 1) & 3;
- }
-
- if (!mainThread)
- return;
-
- mainThread->previousTimeReduction = timeReduction;
-
- // If skill level is enabled, swap best PV line with the sub-optimal one
- if (skill.enabled())
- std::swap(rootMoves[0], *std::find(rootMoves.begin(), rootMoves.end(),
- skill.best ? skill.best : skill.pick_best(multiPV)));
+ // Allocate stack with extra size to allow access from (ss - 7) to (ss + 2):
+ // (ss - 7) is needed for update_continuation_histories(ss - 1) which accesses (ss - 6),
+ // (ss + 2) is needed for initialization of cutOffCnt and killers.
+ Stack stack[MAX_PLY + 10], *ss = stack + 7;
+ Move pv[MAX_PLY + 1];
+ Value alpha, beta, delta;
+ Move lastBestMove = MOVE_NONE;
+ Depth lastBestMoveDepth = 0;
+ MainThread* mainThread = (this == Threads.main() ? Threads.main() : nullptr);
+ double timeReduction = 1, totBestMoveChanges = 0;
+ Color us = rootPos.side_to_move();
+ int iterIdx = 0;
+
+ std::memset(ss - 7, 0, 10 * sizeof(Stack));
+ for (int i = 7; i > 0; --i)
+ {
+ (ss - i)->continuationHistory =
+ &this->continuationHistory[0][0][NO_PIECE][0]; // Use as a sentinel
+ (ss - i)->staticEval = VALUE_NONE;
+ }
+
+ for (int i = 0; i <= MAX_PLY + 2; ++i)
+ (ss + i)->ply = i;
+
+ ss->pv = pv;
+
+ bestValue = -VALUE_INFINITE;
+
+ if (mainThread)
+ {
+ if (mainThread->bestPreviousScore == VALUE_INFINITE)
+ for (int i = 0; i < 4; ++i)
+ mainThread->iterValue[i] = VALUE_ZERO;
+ else
+ for (int i = 0; i < 4; ++i)
+ mainThread->iterValue[i] = mainThread->bestPreviousScore;
+ }
+
+ size_t multiPV = size_t(Options["MultiPV"]);
+ Skill skill(Options["Skill Level"], Options["UCI_LimitStrength"] ? int(Options["UCI_Elo"]) : 0);
+
+ // When playing with strength handicap enable MultiPV search that we will
+ // use behind-the-scenes to retrieve a set of possible moves.
+ if (skill.enabled())
+ multiPV = std::max(multiPV, size_t(4));
+
+ multiPV = std::min(multiPV, rootMoves.size());
+
+ int searchAgainCounter = 0;
+
+ // Iterative deepening loop until requested to stop or the target depth is reached
+ while (++rootDepth < MAX_PLY && !Threads.stop
+ && !(Limits.depth && mainThread && rootDepth > Limits.depth))
+ {
+ // Age out PV variability metric
+ if (mainThread)
+ totBestMoveChanges /= 2;
+
+ // Save the last iteration's scores before the first PV line is searched and
+ // all the move scores except the (new) PV are set to -VALUE_INFINITE.
+ for (RootMove& rm : rootMoves)
+ rm.previousScore = rm.score;
+
+ size_t pvFirst = 0;
+ pvLast = 0;
+
+ if (!Threads.increaseDepth)
+ searchAgainCounter++;
+
+ // MultiPV loop. We perform a full root search for each PV line
+ for (pvIdx = 0; pvIdx < multiPV && !Threads.stop; ++pvIdx)
+ {
+ if (pvIdx == pvLast)
+ {
+ pvFirst = pvLast;
+ for (pvLast++; pvLast < rootMoves.size(); pvLast++)
+ if (rootMoves[pvLast].tbRank != rootMoves[pvFirst].tbRank)
+ break;
+ }
+
+ // Reset UCI info selDepth for each depth and each PV line
+ selDepth = 0;
+
+ // Reset aspiration window starting size
+ Value avg = rootMoves[pvIdx].averageScore;
+ delta = Value(10) + int(avg) * avg / 17470;
+ alpha = std::max(avg - delta, -VALUE_INFINITE);
+ beta = std::min(avg + delta, VALUE_INFINITE);
+
+ // Adjust optimism based on root move's averageScore (~4 Elo)
+ int opt = 113 * avg / (std::abs(avg) + 109);
+ optimism[us] = Value(opt);
+ optimism[~us] = -optimism[us];
+
+ // Start with a small aspiration window and, in the case of a fail
+ // high/low, re-search with a bigger window until we don't fail
+ // high/low anymore.
+ int failedHighCnt = 0;
+ while (true)
+ {
+ // Adjust the effective depth searched, but ensure at least one effective increment
+ // for every four searchAgain steps (see issue #2717).
+ Depth adjustedDepth =
+ std::max(1, rootDepth - failedHighCnt - 3 * (searchAgainCounter + 1) / 4);
+ bestValue = Stockfish::search<Root>(rootPos, ss, alpha, beta, adjustedDepth, false);
+
+ // Bring the best move to the front. It is critical that sorting
+ // is done with a stable algorithm because all the values but the
+ // first and eventually the new best one is set to -VALUE_INFINITE
+ // and we want to keep the same order for all the moves except the
+ // new PV that goes to the front. Note that in the case of MultiPV
+ // search the already searched PV lines are preserved.
+ std::stable_sort(rootMoves.begin() + pvIdx, rootMoves.begin() + pvLast);
+
+ // If search has been stopped, we break immediately. Sorting is
+ // safe because RootMoves is still valid, although it refers to
+ // the previous iteration.
+ if (Threads.stop)
+ break;
+
+ // When failing high/low give some update (without cluttering
+ // the UI) before a re-search.
+ if (mainThread && multiPV == 1 && (bestValue <= alpha || bestValue >= beta)
+ && Time.elapsed() > 3000)
+ sync_cout << UCI::pv(rootPos, rootDepth) << sync_endl;
+
+ // In case of failing low/high increase aspiration window and
+ // re-search, otherwise exit the loop.
+ if (bestValue <= alpha)
+ {
+ beta = (alpha + beta) / 2;
+ alpha = std::max(bestValue - delta, -VALUE_INFINITE);
+
+ failedHighCnt = 0;
+ if (mainThread)
+ mainThread->stopOnPonderhit = false;
+ }
+ else if (bestValue >= beta)
+ {
+ beta = std::min(bestValue + delta, VALUE_INFINITE);
+ ++failedHighCnt;
+ }
+ else
+ break;
+
+ delta += delta / 3;
+
+ assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
+ }
+
+ // Sort the PV lines searched so far and update the GUI
+ std::stable_sort(rootMoves.begin() + pvFirst, rootMoves.begin() + pvIdx + 1);
+
+ if (mainThread && (Threads.stop || pvIdx + 1 == multiPV || Time.elapsed() > 3000))
+ sync_cout << UCI::pv(rootPos, rootDepth) << sync_endl;
+ }
+
+ if (!Threads.stop)
+ completedDepth = rootDepth;
+
+ if (rootMoves[0].pv[0] != lastBestMove)
+ {
+ lastBestMove = rootMoves[0].pv[0];
+ lastBestMoveDepth = rootDepth;
+ }
+
+ // Have we found a "mate in x"?
+ if (Limits.mate && bestValue >= VALUE_MATE_IN_MAX_PLY
+ && VALUE_MATE - bestValue <= 2 * Limits.mate)
+ Threads.stop = true;
+
+ if (!mainThread)
+ continue;
+
+ // If the skill level is enabled and time is up, pick a sub-optimal best move
+ if (skill.enabled() && skill.time_to_pick(rootDepth))
+ skill.pick_best(multiPV);
+
+ // Use part of the gained time from a previous stable move for the current move
+ for (Thread* th : Threads)
+ {
+ totBestMoveChanges += th->bestMoveChanges;
+ th->bestMoveChanges = 0;
+ }
+
+ // Do we have time for the next iteration? Can we stop searching now?
+ if (Limits.use_time_management() && !Threads.stop && !mainThread->stopOnPonderhit)
+ {
+ double fallingEval = (66 + 14 * (mainThread->bestPreviousAverageScore - bestValue)
+ + 6 * (mainThread->iterValue[iterIdx] - bestValue))
+ / 583.0;
+ fallingEval = std::clamp(fallingEval, 0.5, 1.5);
+
+ // If the bestMove is stable over several iterations, reduce time accordingly
+ timeReduction = lastBestMoveDepth + 8 < completedDepth ? 1.56 : 0.69;
+ double reduction = (1.4 + mainThread->previousTimeReduction) / (2.03 * timeReduction);
+ double bestMoveInstability = 1 + 1.79 * totBestMoveChanges / Threads.size();
+
+ double totalTime = Time.optimum() * fallingEval * reduction * bestMoveInstability;
+
+ // Cap used time in case of a single legal move for a better viewer experience
+ if (rootMoves.size() == 1)
+ totalTime = std::min(500.0, totalTime);
+
+ // Stop the search if we have exceeded the totalTime
+ if (Time.elapsed() > totalTime)
+ {
+ // If we are allowed to ponder do not stop the search now but
+ // keep pondering until the GUI sends "ponderhit" or "stop".
+ if (mainThread->ponder)
+ mainThread->stopOnPonderhit = true;
+ else
+ Threads.stop = true;
+ }
+ else if (!mainThread->ponder && Time.elapsed() > totalTime * 0.50)
+ Threads.increaseDepth = false;
+ else
+ Threads.increaseDepth = true;
+ }
+
+ mainThread->iterValue[iterIdx] = bestValue;
+ iterIdx = (iterIdx + 1) & 3;
+ }
+
+ if (!mainThread)
+ return;
+
+ mainThread->previousTimeReduction = timeReduction;
+
+ // If the skill level is enabled, swap the best PV line with the sub-optimal one
+ if (skill.enabled())
+ std::swap(rootMoves[0], *std::find(rootMoves.begin(), rootMoves.end(),
+ skill.best ? skill.best : skill.pick_best(multiPV)));