- // 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;
- }
-
- std::copy(&lowPlyHistory[2][0], &lowPlyHistory.back().back() + 1, &lowPlyHistory[0][0]);
- std::fill(&lowPlyHistory[MAX_LPH - 2][0], &lowPlyHistory.back().back() + 1, 0);
-
- 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());
-
- doubleExtensionAverage[WHITE].set(0, 100); // initialize the running average at 0%
- doubleExtensionAverage[BLACK].set(0, 100); // initialize the running average at 0%
-
- nodesLastExplosive = nodes;
- nodesLastNormal = nodes;
- state = EXPLOSION_NONE;
- trend = SCORE_ZERO;
- optimism[ us] = Value(25);
- 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(17) + int(prev) * prev / 16384;
- 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, 0, 0, 147, 113, 1);
- trend = (us == WHITE ? make_score(tr, tr / 2)
- : -make_score(tr, tr / 2));
-
- int opt = sigmoid(prev, 0, 25, 147, 14464, 256);
- 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)
- {
- Depth adjustedDepth = std::max(1, rootDepth - failedHighCnt - searchAgainCounter);
- 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 + 5;
-
- 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 = (142 + 12 * (mainThread->bestPreviousAverageScore - bestValue)
- + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 825.0;
- fallingEval = std::clamp(fallingEval, 0.5, 1.5);
-
- // If the bestMove is stable over several iterations, reduce time accordingly
- timeReduction = lastBestMoveDepth + 9 < completedDepth ? 1.92 : 0.95;
- double reduction = (1.47 + mainThread->previousTimeReduction) / (2.32 * timeReduction);
- double bestMoveInstability = 1.073 + std::max(1.0, 2.25 - 9.9 / rootDepth)
- * 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 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.58)
- 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)));