/*

Stockfish, a UCI chess playing engine derived from Glaurung 2.1

Copyright (C) 2004-2026 The Stockfish developers (see AUTHORS file)

Stockfish is free software: you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation, either version 3 of the License, or

(at your option) any later version.

Stockfish is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

GNU General Public License for more details.

You should have received a copy of the GNU General Public License

along with this program. If not, see <http://www.gnu.org/licenses/>.

*/

#include "search.h"

#include <algorithm>

#include <array>

#include <atomic>

#include <cassert>

#include <chrono>

#include <cmath>

#include <cstdint>

#include <cstdlib>

#include <initializer_list>

#include <iostream>

#include <list>

#include <ratio>

#include <string>

#include <utility>

#include "bitboard.h"

#include "evaluate.h"

#include "history.h"

#include "misc.h"

#include "movegen.h"

#include "movepick.h"

#include "nnue/network.h"

#include "nnue/nnue_accumulator.h"

#include "position.h"

#include "syzygy/tbprobe.h"

#include "thread.h"

#include "timeman.h"

#include "tt.h"

#include "types.h"

#include "uci.h"

#include "ucioption.h"

namespace Stockfish {

namespace TB = Tablebases;

void syzygy_extend_pv(const OptionsMap& options,

const Search::LimitsType& limits,

Stockfish::Position& pos,

Stockfish::Search::RootMove& rootMove,

Value& v);

using namespace Search;

namespace {

constexpr uint64_t NODES_LIMIT_OUTPUT = 10'000'000;

constexpr int SEARCHEDLIST_CAPACITY = 32;

using SearchedList = ValueList<Move, SEARCHEDLIST_CAPACITY>;

// (*Scalers):

// The values with Scaler asterisks have proven non-linear scaling.

// They are optimized to time controls of 180 + 1.8 and longer,

// so changing them or adding conditions that are similar requires

// tests at these types of time controls.

// (*Scaler) All tuned parameters at time controls shorter than

// optimized for require verifications at longer time controls

int correction_value(const Worker& w, const Position& pos, const Stack* const ss) {

const Color us = pos.side_to_move();

const auto m = (ss - 1)->currentMove;

const auto& shared = w.sharedHistory;

const int pcv = shared.pawn_correction_entry(pos).at(us).pawn;

const int micv = shared.minor_piece_correction_entry(pos).at(us).minor;

const int wnpcv = shared.nonpawn_correction_entry<WHITE>(pos).at(us).nonPawnWhite;

const int bnpcv = shared.nonpawn_correction_entry<BLACK>(pos).at(us).nonPawnBlack;

const int cntcv =

m.is_ok() ? (*(ss - 2)->continuationCorrectionHistory)[pos.piece_on(m.to_sq())][m.to_sq()]

+ (*(ss - 4)->continuationCorrectionHistory)[pos.piece_on(m.to_sq())][m.to_sq()]

: 8;

return 12153 * pcv + 8620 * micv + 12355 * (wnpcv + bnpcv) + 7982 * cntcv;

}

// Add correctionHistory value to raw staticEval and guarantee evaluation

// does not hit the tablebase range.

Value to_corrected_static_eval(const Value v, const int cv) {

return std::clamp(v + cv / 131072, VALUE_TB_LOSS_IN_MAX_PLY + 1, VALUE_TB_WIN_IN_MAX_PLY - 1);

}

void update_correction_history(const Position& pos,

Stack* const ss,

Search::Worker& workerThread,

const int bonus) {

const Move m = (ss - 1)->currentMove;

const Color us = pos.side_to_move();

constexpr int nonPawnWeight = 187;

auto& shared = workerThread.sharedHistory;

shared.pawn_correction_entry(pos).at(us).pawn << bonus;

shared.minor_piece_correction_entry(pos).at(us).minor << bonus * 153 / 128;

shared.nonpawn_correction_entry<WHITE>(pos).at(us).nonPawnWhite << bonus * nonPawnWeight / 128;

shared.nonpawn_correction_entry<BLACK>(pos).at(us).nonPawnBlack << bonus * nonPawnWeight / 128;

if (m.is_ok())

{

const Square to = m.to_sq();

const Piece pc = pos.piece_on(to);

(*(ss - 2)->continuationCorrectionHistory)[pc][to] << bonus * 126 / 128;

(*(ss - 4)->continuationCorrectionHistory)[pc][to] << bonus * 63 / 128;

}

}

// Add a small random component to draw evaluations to avoid 3-fold blindness

Value value_draw(size_t nodes) { return VALUE_DRAW - 1 + Value(nodes & 0x2); }

Value value_to_tt(Value v, int ply);

Value value_from_tt(Value v, int ply, int r50c);

void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus);

void update_quiet_histories(

const Position& pos, Stack* ss, Search::Worker& workerThread, Move move, int bonus);

void update_all_stats(const Position& pos,

Stack* ss,

Search::Worker& workerThread,

Move bestMove,

Square prevSq,

SearchedList& quietsSearched,

SearchedList& capturesSearched,

Depth depth,

Move ttMove);

bool is_shuffling(Move move, Stack* const ss, const Position& pos) {

if (pos.capture_stage(move) || pos.rule50_count() < 11)

return false;

if (pos.state()->pliesFromNull <= 6 || ss->ply < 18)

return false;

return move.from_sq() == (ss - 2)->currentMove.to_sq()

&& (ss - 2)->currentMove.from_sq() == (ss - 4)->currentMove.to_sq();

}

} // namespace

Search::Worker::Worker(SharedState& sharedState,

std::unique_ptr<ISearchManager> sm,

size_t threadId,

size_t numaThreadId,

size_t numaTotalThreads,

NumaReplicatedAccessToken token) :

// Unpack the SharedState struct into member variables

sharedHistory(sharedState.sharedHistories.at(token.get_numa_index())),

threadIdx(threadId),

numaThreadIdx(numaThreadId),

numaTotal(numaTotalThreads),

numaAccessToken(token),

manager(std::move(sm)),

options(sharedState.options),

threads(sharedState.threads),

tt(sharedState.tt),

networks(sharedState.networks),

refreshTable(networks[token]) {

clear();

}

void Search::Worker::ensure_network_replicated() {

// Access once to force lazy initialization.

// We do this because we want to avoid initialization during search.

(void) (networks[numaAccessToken]);

}

void Search::Worker::start_searching() {

accumulatorStack.reset();

lastIterationPV.clear();

// Non-main threads go directly to iterative_deepening()

if (!is_mainthread())

{

iterative_deepening();

return;

}

main_manager()->tm.init(limits, rootPos.side_to_move(), rootPos.game_ply(), options,

main_manager()->originalTimeAdjust);

tt.new_search();

if (rootMoves.empty())

{

main_manager()->updates.onUpdateNoMoves(

{0, {rootPos.checkers() ? -VALUE_MATE : VALUE_DRAW, rootPos}});

main_manager()->updates.onBestmove(UCIEngine::move(Move::none()), "");

return;

}

// Main thread starts non-main threads, and begins own search.

threads.start_searching();

bool uciPvSent = iterative_deepening();

// When we reach the maximum depth, we can arrive here without a raise of

// threads.stop. However, if we are pondering or in an infinite search,

// the UCI protocol states that we shouldn't print the best move before the

// GUI sends a "stop" or "ponderhit" command. We therefore simply wait here

// until the GUI sends one of those commands.

while (!threads.stop && (main_manager()->ponder || limits.infinite))

{} // Busy wait for a stop or a ponder reset

// Stop the threads if not already stopped (also raise the stop if

// "ponderhit" just reset threads.ponder)

threads.stop = true;

// Wait until all threads have finished

threads.wait_for_search_finished();

// When playing in 'nodes as time' mode, subtract the searched nodes from

// the available ones before exiting.

if (limits.npmsec)

main_manager()->tm.advance_nodes_time(threads.nodes_searched()

- limits.inc[rootPos.side_to_move()]);

Worker* bestThread = this;

Skill skill =

Skill(options["Skill Level"], options["UCI_LimitStrength"] ? int(options["UCI_Elo"]) : 0);

if (int(options["MultiPV"]) == 1 && !limits.depth && !skill.enabled())

bestThread = threads.get_best_thread()->worker.get();

main_manager()->bestPreviousScore = bestThread->rootMoves[0].score;

main_manager()->bestPreviousAverageScore = bestThread->rootMoves[0].averageScore;

if (bestThread->rootMoves[0].pv.size() == 1

&& bestThread->rootMoves[0].extract_ponder_from_tt(tt, rootPos))

uciPvSent = false;

// Send PV info if it has changed since last output in iterative_deepening().

if (!uciPvSent || bestThread != this)

main_manager()->pv(*bestThread, threads, tt, bestThread->completedDepth);

// In rare cases, pv() may change the ponder move through syzygy_extend_pv().

std::string ponder;

if (bestThread->rootMoves[0].pv.size() > 1)

ponder = UCIEngine::move(bestThread->rootMoves[0].pv[1], rootPos.is_chess960());

auto bestmove = UCIEngine::move(bestThread->rootMoves[0].pv[0], rootPos.is_chess960());

main_manager()->updates.onBestmove(bestmove, ponder);

}

// Main iterative deepening loop. It calls search()

// repeatedly with increasing depth until the allocated thinking time has been

// consumed, the user stops the search, or the maximum search depth is reached.

bool Search::Worker::iterative_deepening() {

SearchManager* mainThread = (is_mainthread() ? main_manager() : nullptr);

PVMoves pv;

Depth lastBestMoveDepth = 0;

Value alpha, beta;

Value bestValue = -VALUE_INFINITE;

Color us = rootPos.side_to_move();

double timeReduction = 1, totBestMoveChanges = 0;

int delta, iterIdx = 0;

// 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.

Stack stack[MAX_PLY + 10] = {};

Stack* ss = stack + 7;

for (int i = 7; i > 0; --i)

{

(ss - i)->continuationHistory =

&continuationHistory[0][0][NO_PIECE][0]; // Use as a sentinel

(ss - i)->continuationCorrectionHistory = &continuationCorrectionHistory[NO_PIECE][0];

(ss - i)->staticEval = VALUE_NONE;

}

for (int i = 0; i <= MAX_PLY + 2; ++i)

(ss + i)->ply = i;

ss->pv = &pv;

if (mainThread)

{

if (mainThread->bestPreviousScore == VALUE_INFINITE)

mainThread->iterValue.fill(VALUE_ZERO);

else

mainThread->iterValue.fill(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;

bool uciPvSent = false;

lowPlyHistory.fill(98);

for (Color c : {WHITE, BLACK})

for (int i = 0; i < UINT_16_HISTORY_SIZE; i++)

mainHistory[c][i] = mainHistory[c][i] * 820 / 1024;

// 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 and signal the start of a new iteration.

if (mainThread)

{

totBestMoveChanges /= 2;

uciPvSent = false;

}

// 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; ++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

delta = 5 + threadIdx % 8 + std::abs(rootMoves[pvIdx].meanSquaredScore) / 10208;

Value avg = rootMoves[pvIdx].averageScore;

alpha = std::max(avg - delta, -VALUE_INFINITE);

beta = std::min(avg + delta, VALUE_INFINITE);

// Adjust optimism based on root move's averageScore

optimism[us] = 144 * avg / (std::abs(avg) + 91);

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);

rootDelta = beta - alpha;

bestValue = 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 before a re-search. To avoid

// excessive output that could hang GUIs like Fritz 19, only start

// at nodes > 10M (rather than depth N, which can be reached quickly)

if (mainThread && multiPV == 1 && (bestValue <= alpha || bestValue >= beta)

&& nodes > NODES_LIMIT_OUTPUT)

main_manager()->pv(*this, threads, tt, rootDepth);

// In case of failing low/high increase aspiration window and re-search,

// otherwise exit the loop.

if (bestValue <= alpha)

{

beta = alpha;

alpha = std::max(bestValue - delta, -VALUE_INFINITE);

failedHighCnt = 0;

if (mainThread)

mainThread->stopOnPonderhit = false;

}

else if (bestValue >= beta)

{

alpha = std::max(beta - delta, alpha);

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 || nodes > NODES_LIMIT_OUTPUT))

{

main_manager()->pv(*this, threads, tt, rootDepth);

uciPvSent = (pvIdx + 1 == multiPV);

}

if (threads.stop)

break;

}

if (!threads.stop)

{

completedDepth = rootDepth;

if (lastIterationPV.empty() || rootMoves[0].pv[0] != lastIterationPV[0])

lastBestMoveDepth = rootDepth;

lastIterationPV = rootMoves[0].pv;

}

// A mated-in/TB-loss score from an aborted search cannot be trusted: the loss

// could be delayed or refuted upon exploring the remaining root-moves.

// Thus here we roll back to the score from the previous iteration.

else if (rootMoves[0].score != -VALUE_INFINITE && is_loss(rootMoves[0].score))

{

// Bring the last best move to the front for best thread selection.

if (!lastIterationPV.empty())

{

Utility::move_to_front(rootMoves, [&lastPV = std::as_const(lastIterationPV)](

const auto& rm) { return rm == lastPV[0]; });

rootMoves[0].pv = lastIterationPV;

rootMoves[0].score = rootMoves[0].uciScore = rootMoves[0].previousScore;

if (mainThread)

uciPvSent = true;

}

// For an aborted d1 search we label the loss score as inexact.

else if (!rootMoves[0].scoreLowerbound)

rootMoves[0].scoreUpperbound = true;

}

// Have we found a "mate in x" after a completed iteration?

if (limits.mate && !threads.stop

&& ((rootMoves[0].score >= VALUE_MATE_IN_MAX_PLY

&& VALUE_MATE - rootMoves[0].score <= 2 * limits.mate)

|| (rootMoves[0].score <= VALUE_MATED_IN_MAX_PLY

&& VALUE_MATE + rootMoves[0].score <= 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(rootMoves, multiPV);

// Use part of the gained time from a previous stable move for the current move

for (auto&& th : threads)

{

totBestMoveChanges += th->worker->bestMoveChanges;

th->worker->bestMoveChanges = 0;

}

// Do we have time for the next iteration? Can we stop searching now?

if (limits.use_time_management() && !threads.stop && !mainThread->stopOnPonderhit)

{

uint64_t nodesEffort =

rootMoves[0].effort * 100000 / std::max(uint64_t(1), uint64_t(nodes));

double fallingEval = (12.44 + 2.318 * (mainThread->bestPreviousAverageScore - bestValue)

+ 0.95 * (mainThread->iterValue[iterIdx] - bestValue))

/ 100.0;

fallingEval = std::clamp(fallingEval, 0.581, 1.655);

// If the bestMove is stable over several iterations, reduce time accordingly

double k = 0.476;

double center = lastBestMoveDepth + 11.565;

timeReduction = 0.64 + 0.93 / (0.953 + std::exp(-k * (completedDepth - center)));

double reduction = (1.5 + mainThread->previousTimeReduction) / (2.255 * timeReduction);

double bestMoveInstability = 1.088 + 2.315 * totBestMoveChanges / threads.size();

double highBestMoveEffort = std::clamp(

interpolate(int64_t(nodesEffort), int64_t(78000), int64_t(94000), 0.96, 0.74), 0.74,

0.96);

double totalTime = mainThread->tm.optimum() * fallingEval * reduction

* bestMoveInstability * highBestMoveEffort;

// Cap used time in case of a single legal move for a better viewer experience

if (rootMoves.size() == 1)

totalTime = std::min(504.4, totalTime);

auto elapsedTime = elapsed();

// Stop the search if we have exceeded the totalTime or maximum

if (elapsedTime > std::min(totalTime, double(mainThread->tm.maximum())))

{

// 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

threads.increaseDepth = mainThread->ponder || elapsedTime <= totalTime * 0.50;

}

mainThread->iterValue[iterIdx] = bestValue;

iterIdx = (iterIdx + 1) & 3;

}

if (!mainThread)

return false;

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(rootMoves, multiPV)));

return uciPvSent;

}

void Search::Worker::do_move(Position& pos, const Move move, StateInfo& st, Stack* const ss) {

do_move(pos, move, st, pos.gives_check(move), ss);

}

void Search::Worker::do_move(

Position& pos, const Move move, StateInfo& st, const bool givesCheck, Stack* const ss) {

bool capture = pos.capture_stage(move);

// Preferable over fetch_add to avoid locking instructions

nodes.store(nodes.load(std::memory_order_relaxed) + 1, std::memory_order_relaxed);

auto [dirtyPiece, dirtyThreats] = accumulatorStack.push();

pos.do_move(move, st, givesCheck, dirtyPiece, dirtyThreats, &tt, &sharedHistory);

if (ss != nullptr)

{

ss->currentMove = move;

ss->continuationHistory =

&continuationHistory[ss->inCheck][capture][dirtyPiece.pc][move.to_sq()];

ss->continuationCorrectionHistory =

&continuationCorrectionHistory[dirtyPiece.pc][move.to_sq()];

}

}

void Search::Worker::do_null_move(Position& pos, StateInfo& st, Stack* const ss) {

pos.do_null_move(st);

ss->currentMove = Move::null();

ss->continuationHistory = &continuationHistory[0][0][NO_PIECE][0];

ss->continuationCorrectionHistory = &continuationCorrectionHistory[NO_PIECE][0];

}

void Search::Worker::undo_move(Position& pos, const Move move) {

pos.undo_move(move);

accumulatorStack.pop();

}

void Search::Worker::undo_null_move(Position& pos) { pos.undo_null_move(); }

// Reset histories, usually before a new game

void Search::Worker::clear() {

mainHistory.fill(0);

captureHistory.fill(-678);

// Each thread is responsible for clearing their part of shared history

sharedHistory.correctionHistory.clear_range(0, numaThreadIdx, numaTotal);

sharedHistory.pawnHistory.clear_range(-1238, numaThreadIdx, numaTotal);

ttMoveHistory = 0;

for (auto& to : continuationCorrectionHistory)

for (auto& h : to)

h.fill(6);

for (bool inCheck : {false, true})

for (StatsType c : {NoCaptures, Captures})

for (auto& to : continuationHistory[inCheck][c])

for (auto& h : to)

h.fill(-523);

for (size_t i = 1; i < reductions.size(); ++i)

reductions[i] = int(2763 / 128.0 * std::log(i));

refreshTable.clear(networks[numaAccessToken]);

}

// Main search function for both PV and non-PV nodes

template<NodeType nodeType>

Value Search::Worker::search(

Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) {

constexpr bool PvNode = nodeType != NonPV;

constexpr bool rootNode = nodeType == Root;

const bool allNode = !(PvNode || cutNode);

// Dive into quiescence search when the depth reaches zero

if (depth <= 0)

return qsearch<PvNode ? PV : NonPV>(pos, ss, alpha, beta);

// Limit the depth if extensions made it too large

depth = std::min(depth, MAX_PLY - 1);

// Check if we have an upcoming move that draws by repetition

if (!rootNode && alpha < VALUE_DRAW && pos.upcoming_repetition(ss->ply))

{

alpha = value_draw(nodes);

if (alpha >= beta)

return alpha;

}

assert(-VALUE_INFINITE <= alpha && alpha < beta && beta <= VALUE_INFINITE);

assert(PvNode || (alpha == beta - 1));

assert(0 < depth && depth < MAX_PLY);

assert(!(PvNode && cutNode));

PVMoves pv;

StateInfo st;

Key posKey;

Move move, excludedMove, bestMove;

Depth extension, newDepth;

Value bestValue, value, eval, maxValue, probCutBeta;

bool givesCheck, improving, priorCapture, opponentWorsening;

bool capture, ttCapture;

int priorReduction;

Piece movedPiece;

SearchedList capturesSearched;

SearchedList quietsSearched;

// Step 1. Initialize node

ss->inCheck = pos.checkers();

priorCapture = pos.captured_piece();

Color us = pos.side_to_move();

ss->moveCount = 0;

bestValue = -VALUE_INFINITE;

maxValue = VALUE_INFINITE;

ss->followPV = rootNode

|| ((ss - 1)->followPV && static_cast<size_t>(ss->ply - 1) < lastIterationPV.size()

&& (ss - 1)->currentMove == lastIterationPV[ss->ply - 1]);

// Check for the available remaining time

if (is_mainthread())

main_manager()->check_time(*this);

// Used to send selDepth info to GUI (selDepth counts from 1, ply from 0)

if (PvNode && selDepth < ss->ply + 1)

selDepth = ss->ply + 1;

if (!rootNode)

{

// Step 2. Check for aborted search and immediate draw

if (threads.stop.load(std::memory_order_relaxed) || pos.is_draw(ss->ply)

|| ss->ply >= MAX_PLY)

return (ss->ply >= MAX_PLY && !ss->inCheck) ? evaluate(pos) : value_draw(nodes);

// Step 3. Mate distance pruning. Even if we mate at the next move our score

// would be at best mate_in(ss->ply + 1), but if alpha is already bigger because

// a shorter mate was found upward in the tree then there is no need to search

// because we will never beat the current alpha. Same logic but with reversed

// signs apply also in the opposite condition of being mated instead of giving

// mate. In this case, return a fail-high score.

alpha = std::max(mated_in(ss->ply), alpha);

beta = std::min(mate_in(ss->ply + 1), beta);

if (alpha >= beta)

return alpha;

}

assert(0 <= ss->ply && ss->ply < MAX_PLY);

Square prevSq = ((ss - 1)->currentMove).is_ok() ? ((ss - 1)->currentMove).to_sq() : SQ_NONE;

bestMove = Move::none();

priorReduction = (ss - 1)->reduction;

(ss - 1)->reduction = 0;

ss->statScore = 0;

(ss + 2)->cutoffCnt = 0;

// Step 4. Transposition table lookup

excludedMove = ss->excludedMove;

posKey = pos.key();

auto [ttHit, ttData, ttWriter] = tt.probe(posKey);

// Need further processing of the saved data

ss->ttHit = ttHit;

ttData.move = rootNode ? rootMoves[pvIdx].pv[0] : ttHit ? ttData.move : Move::none();

ttData.value = ttHit ? value_from_tt(ttData.value, ss->ply, pos.rule50_count()) : VALUE_NONE;

ss->ttPv = excludedMove ? ss->ttPv : PvNode || (ttHit && ttData.is_pv);

ttCapture = ttData.move && pos.capture_stage(ttData.move);

// Step 5. Static evaluation of the position

Value unadjustedStaticEval = VALUE_NONE;

const auto correctionValue = correction_value(*this, pos, ss);

// Skip early pruning when in check

if (ss->inCheck)

ss->staticEval = eval = (ss - 2)->staticEval;

else if (excludedMove)

unadjustedStaticEval = eval = ss->staticEval;

else if (ss->ttHit)

{

// Never assume anything about values stored in TT

unadjustedStaticEval = ttData.eval;

if (!is_valid(unadjustedStaticEval))

unadjustedStaticEval = evaluate(pos);

ss->staticEval = eval = to_corrected_static_eval(unadjustedStaticEval, correctionValue);

// ttValue can be used as a better position evaluation

if (is_valid(ttData.value)

&& (ttData.bound & (ttData.value > eval ? BOUND_LOWER : BOUND_UPPER)))

eval = ttData.value;

}

else

{

unadjustedStaticEval = evaluate(pos);

ss->staticEval = eval = to_corrected_static_eval(unadjustedStaticEval, correctionValue);

// Static evaluation is saved as it was before adjustment by correction history

ttWriter.write(posKey, VALUE_NONE, ss->ttPv, BOUND_NONE, DEPTH_UNSEARCHED, Move::none(),

unadjustedStaticEval, tt.generation());

}

// Set up the improving flag, which is true if current static evaluation is

// bigger than the previous static evaluation at our turn (if we were in

// check at our previous move we go back until we weren't in check) and is

// false otherwise. The improving flag is used in various pruning heuristics.

// Similarly, opponentWorsening is true if our static evaluation is better

// for us than at the last ply.

improving = ss->staticEval > (ss - 2)->staticEval;

opponentWorsening = ss->staticEval > -(ss - 1)->staticEval;

// Hindsight adjustment of reductions based on static evaluation difference.

if (priorReduction >= 3 && !opponentWorsening)

depth++;

if (priorReduction >= 2 && depth >= 2 && ss->staticEval + (ss - 1)->staticEval > 195)

depth--;

// At non-PV nodes we check for an early TT cutoff

if (!PvNode && !excludedMove && ttData.depth > depth - (ttData.value <= beta)

&& is_valid(ttData.value) // Can happen when !ttHit or when access race in probe()

&& (ttData.bound & (ttData.value >= beta ? BOUND_LOWER : BOUND_UPPER))

&& (cutNode == (ttData.value >= beta) || depth > 5))

{

// If ttMove is quiet, update move sorting heuristics on TT hit

if (ttData.move && ttData.value >= beta)

{

// Bonus for a quiet ttMove that fails high

if (!ttCapture)

update_quiet_histories(pos, ss, *this, ttData.move,

std::min(119 * depth - 74, 855));

// Extra penalty for early quiet moves of the previous ply

if (prevSq != SQ_NONE && (ss - 1)->moveCount < 4 && !priorCapture)

update_continuation_histories(ss - 1, pos.piece_on(prevSq), prevSq, -2014);

}

// Partial workaround for the graph history interaction problem

// For high rule50 counts don't produce transposition table cutoffs.

if (pos.rule50_count() < 96)

{

if (depth >= 7 && ttData.move && pos.pseudo_legal(ttData.move) && pos.legal(ttData.move)

&& !is_decisive(ttData.value))

{

pos.do_move(ttData.move, st);

Key nextPosKey = pos.key();

auto [ttHitNext, ttDataNext, ttWriterNext] = tt.probe(nextPosKey);

pos.undo_move(ttData.move);

// Check that the ttValue after the tt move would also trigger a cutoff

if (!is_valid(ttDataNext.value))

return ttData.value;

if ((ttData.value >= beta) == (-ttDataNext.value >= beta))

return ttData.value;

}

else

return ttData.value;

}

}

// Step 6. Tablebases probe

if (!rootNode && !excludedMove && tbConfig.cardinality)

{

int piecesCount = pos.count<ALL_PIECES>();

if (piecesCount <= tbConfig.cardinality

&& (piecesCount < tbConfig.cardinality || depth >= tbConfig.probeDepth)

&& pos.rule50_count() == 0 && !pos.can_castle(ANY_CASTLING))

{

TB::ProbeState err;

TB::WDLScore wdl = TB::probe_wdl(pos, &err);

// Force check of time on the next occasion

if (is_mainthread())

main_manager()->callsCnt = 0;

if (err != TB::ProbeState::FAIL)

{

// Preferable over fetch_add to avoid locking instructions

tbHits.store(tbHits.load(std::memory_order_relaxed) + 1, std::memory_order_relaxed);

int drawScore = tbConfig.useRule50 ? 1 : 0;

Value tbValue = VALUE_TB - ss->ply;

// Use the range VALUE_TB to VALUE_TB_WIN_IN_MAX_PLY to score

value = wdl < -drawScore ? -tbValue

: wdl > drawScore ? tbValue

: VALUE_DRAW + 2 * wdl * drawScore;

Bound b = wdl < -drawScore ? BOUND_UPPER

: wdl > drawScore ? BOUND_LOWER

: BOUND_EXACT;

if (b == BOUND_EXACT || (b == BOUND_LOWER ? value >= beta : value <= alpha))

{

ttWriter.write(posKey, value_to_tt(value, ss->ply), ss->ttPv, b,

std::min(MAX_PLY - 1, depth + 6), Move::none(), VALUE_NONE,

tt.generation());

return value;

}

if (PvNode)

{

if (b == BOUND_LOWER)

bestValue = value, alpha = std::max(alpha, bestValue);

else

maxValue = value;

}

}

}

}

if (ss->inCheck)

goto moves_loop;

// Use static evaluation difference to improve quiet move ordering

if (((ss - 1)->currentMove).is_ok() && !(ss - 1)->inCheck && !priorCapture)

{

int evalDiff = std::clamp(-int((ss - 1)->staticEval + ss->staticEval), -214, 171) + 60;

mainHistory[~us][((ss - 1)->currentMove).raw()] << evalDiff * 10;

if (!ttHit && type_of(pos.piece_on(prevSq)) != PAWN

&& ((ss - 1)->currentMove).type_of() != PROMOTION)

sharedHistory.pawn_entry(pos)[pos.piece_on(prevSq)][prevSq] << evalDiff * 12;

}

// Step 7. Razoring

// If eval is really low, skip search entirely and return the qsearch value.

// For PvNodes, we must have a guard against mates being returned.

if (!PvNode && eval < alpha - 502 - 306 * depth * depth)

return qsearch<NonPV>(pos, ss, alpha, beta);

// Step 8. Futility pruning: child node

// The depth condition is important for mate finding.

{

auto futility_margin = [&](Depth d) {

Value futilityMult = 76 - 21 * !ss->ttHit;

return futilityMult * d

- (2686 * improving + 362 * opponentWorsening) * futilityMult / 1024 //

+ std::abs(correctionValue) / 180600;

};

if (!ss->ttPv && depth < 15 && eval - futility_margin(depth) >= beta && eval >= beta

&& (!ttData.move || ttCapture) && !is_loss(beta) && !is_win(eval))

return (2 * beta + eval) / 3;

}

// Step 9. Null move search with verification search

if (cutNode && ss->staticEval >= beta - 16 * depth - 53 * improving + 378 && !excludedMove

&& pos.non_pawn_material(us) && ss->ply >= nmpMinPly && !is_loss(beta))

{

assert((ss - 1)->currentMove != Move::null());

// Null move dynamic reduction based on depth

Depth R = 7 + depth / 3;

do_null_move(pos, st, ss);

Value nullValue = -search<NonPV>(pos, ss + 1, -beta, -beta + 1, depth - R, false);

undo_null_move(pos);

// Do not return unproven mate or TB scores

if (nullValue >= beta && !is_win(nullValue))

{

if (nmpMinPly || depth < 16)

return nullValue;

assert(!nmpMinPly); // Recursive verification is not allowed

// Do verification search at high depths, with null move pruning disabled

// until ply exceeds nmpMinPly.

nmpMinPly = ss->ply + 3 * (depth - R) / 4;

Value v = search<NonPV>(pos, ss, beta - 1, beta, depth - R, false);

nmpMinPly = 0;

if (v >= beta)

return nullValue;

}

}

improving |= ss->staticEval >= beta;

// Step 10. Internal iterative reductions

// At sufficient depth, reduce depth for PV/Cut nodes without a TTMove.

// (*Scaler) Making IIR more aggressive scales poorly.

if (!ss->followPV && !allNode && depth >= 6 && !ttData.move && priorReduction <= 3)

depth--;

// Step 11. ProbCut

// If we have a good enough capture (or queen promotion) and a reduced search

// returns a value much above beta, we can (almost) safely prune the previous move.

probCutBeta = beta + 224 - 61 * improving;

if (depth >= 3

&& !is_decisive(beta)

// If value from transposition table is lower than probCutBeta, don't attempt

// probCut there

&& !(is_valid(ttData.value) && ttData.value < probCutBeta))

{

assert(probCutBeta < VALUE_INFINITE && probCutBeta > beta);

MovePicker mp(pos, ttData.move, probCutBeta - ss->staticEval, &captureHistory);

Depth probCutDepth = depth - 4;

while ((move = mp.next_move()) != Move::none())

{

assert(move.is_ok());

if (move == excludedMove || !pos.legal(move))

continue;

assert(pos.capture_stage(move));

do_move(pos, move, st, ss);

// Perform a preliminary qsearch to verify that the move holds

value = -qsearch<NonPV>(pos, ss + 1, -probCutBeta, -probCutBeta + 1);

// If the qsearch held, perform the regular search

if (value >= probCutBeta && probCutDepth > 0)

value = -search<NonPV>(pos, ss + 1, -probCutBeta, -probCutBeta + 1, probCutDepth,

!cutNode);

undo_move(pos, move);

if (value >= probCutBeta)

{

// Save ProbCut data into transposition table

ttWriter.write(posKey, value_to_tt(value, ss->ply), ss->ttPv, BOUND_LOWER,

probCutDepth + 1, move, unadjustedStaticEval, tt.generation());

if (!is_decisive(value))

return value - (probCutBeta - beta);

}

}

}

moves_loop: // When in check, search starts here