X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=3c61ea2f395cdbc441f58dcffd94b615436cbd5a;hb=HEAD;hp=fa479c4b8272b9896081c0f07c7da86e06a15797;hpb=7970236e9ea64796d5c7597cb1aedde737751f07;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index fa479c4b..ac0b9c6d 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -1,6 +1,6 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 - Copyright (C) 2004-2023 The Stockfish developers (see AUTHORS file) + Copyright (C) 2004-2024 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 @@ -22,280 +22,216 @@ #include #include #include +#include #include +#include #include -#include #include #include -#include +#include +#include #include #include -#include "bitboard.h" #include "evaluate.h" #include "misc.h" #include "movegen.h" #include "movepick.h" -#include "nnue/evaluate_nnue.h" +#include "nnue/network.h" +#include "nnue/nnue_accumulator.h" #include "nnue/nnue_common.h" +#include "nnue/nnue_misc.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 Search { - -LimitsType Limits; -} - -namespace Tablebases { - -int Cardinality; -bool RootInTB; -bool UseRule50; -Depth ProbeDepth; -} - namespace TB = Tablebases; -using std::string; +void syzygy_extend_pv(const OptionsMap& options, + const Search::LimitsType& limits, + Stockfish::Position& pos, + Stockfish::Search::RootMove& rootMove, + Value& v); + using Eval::evaluate; using namespace Search; namespace { -// Different node types, used as a template parameter -enum NodeType { - NonPV, - PV, - Root -}; - // Futility margin -Value futility_margin(Depth d, bool noTtCutNode, bool improving) { - return Value((125 - 43 * noTtCutNode) * (d - improving)); -} - -// Reductions lookup table initialized at startup -int Reductions[MAX_MOVES]; // [depth or moveNumber] +Value futility_margin(Depth d, bool noTtCutNode, bool improving, bool oppWorsening) { + Value futilityMult = 122 - 37 * noTtCutNode; + Value improvingDeduction = improving * futilityMult * 2; + Value worseningDeduction = oppWorsening * futilityMult / 3; -Depth reduction(bool i, Depth d, int mn, Value delta, Value rootDelta) { - int reductionScale = Reductions[d] * Reductions[mn]; - return (reductionScale + 1487 - int(delta) * 976 / int(rootDelta)) / 1024 - + (!i && reductionScale > 808); + return futilityMult * d - improvingDeduction - worseningDeduction; } constexpr int futility_move_count(bool improving, Depth depth) { - return improving ? (3 + depth * depth) : (3 + depth * depth) / 2; + return (3 + depth * depth) / (2 - improving); +} + +// Add correctionHistory value to raw staticEval and guarantee evaluation +// does not hit the tablebase range. +Value to_corrected_static_eval(Value v, const Worker& w, const Position& pos) { + const auto pcv = + w.pawnCorrectionHistory[pos.side_to_move()][pawn_structure_index(pos)]; + const auto mcv = w.materialCorrectionHistory[pos.side_to_move()][material_index(pos)]; + const auto cv = (2 * pcv + mcv) / 3; + v += 66 * cv / 512; + return std::clamp(v, VALUE_TB_LOSS_IN_MAX_PLY + 1, VALUE_TB_WIN_IN_MAX_PLY - 1); } // History and stats update bonus, based on depth -int stat_bonus(Depth d) { return std::min(364 * d - 438, 1501); } +int stat_bonus(Depth d) { return std::min(190 * d - 108, 1596); } // History and stats update malus, based on depth -int stat_malus(Depth d) { return std::min(452 * d - 452, 1478); } +int stat_malus(Depth d) { return std::min(736 * d - 268, 2044); } // Add a small random component to draw evaluations to avoid 3-fold blindness -Value value_draw(const Thread* thisThread) { - return VALUE_DRAW - 1 + Value(thisThread->nodes & 0x2); -} - -// Skill structure is used to implement strength limit. If we have a UCI_Elo, -// we convert it to an appropriate skill level, anchored to the Stash engine. -// This method is based on a fit of the Elo results for games played between -// Stockfish at various skill levels and various versions of the Stash engine. -// Skill 0 .. 19 now covers CCRL Blitz Elo from 1320 to 3190, approximately -// Reference: https://github.com/vondele/Stockfish/commit/a08b8d4e9711c2 -struct Skill { - Skill(int skill_level, int uci_elo) { - if (uci_elo) - { - double e = double(uci_elo - 1320) / (3190 - 1320); - level = std::clamp((((37.2473 * e - 40.8525) * e + 22.2943) * e - 0.311438), 0.0, 19.0); - } - else - level = double(skill_level); - } - bool enabled() const { return level < 20.0; } - bool time_to_pick(Depth depth) const { return depth == 1 + int(level); } - Move pick_best(size_t multiPV); - - double level; - Move best = MOVE_NONE; -}; - -template -Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); - -template -Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth = 0); - +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_pv(Move* pv, Move move, const Move* childPv); void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus); -void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus); -void update_all_stats(const Position& pos, - Stack* ss, - Move bestMove, - Value bestValue, - Value beta, - Square prevSq, - Move* quietsSearched, - int quietCount, - Move* capturesSearched, - int captureCount, - Depth depth); - -// Utility to verify move generation. All the leaf nodes up -// to the given depth are generated and counted, and the sum is returned. -template -uint64_t perft(Position& pos, Depth depth) { - - StateInfo st; - ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize); - - uint64_t cnt, nodes = 0; - const bool leaf = (depth == 2); - - for (const auto& m : MoveList(pos)) - { - if (Root && depth <= 1) - cnt = 1, nodes++; - else - { - pos.do_move(m, st); - cnt = leaf ? MoveList(pos).size() : perft(pos, depth - 1); - nodes += cnt; - pos.undo_move(m); - } - if (Root) - sync_cout << UCI::move(m, pos.is_chess960()) << ": " << cnt << sync_endl; - } - return nodes; -} +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, + ValueList& quietsSearched, + ValueList& capturesSearched, + Depth depth); } // namespace - -// Called at startup to initialize various lookup tables -void Search::init() { - - for (int i = 1; i < MAX_MOVES; ++i) - Reductions[i] = int((20.37 + std::log(Threads.size()) / 2) * std::log(i)); +Search::Worker::Worker(SharedState& sharedState, + std::unique_ptr sm, + size_t threadId, + NumaReplicatedAccessToken token) : + // Unpack the SharedState struct into member variables + threadIdx(threadId), + numaAccessToken(token), + manager(std::move(sm)), + options(sharedState.options), + threads(sharedState.threads), + tt(sharedState.tt), + networks(sharedState.networks), + refreshTable(networks[token]) { + clear(); } - -// Resets search state to its initial value -void Search::clear() { - - Threads.main()->wait_for_search_finished(); - - Time.availableNodes = 0; - TT.clear(); - Threads.clear(); - Tablebases::init(Options["SyzygyPath"]); // Free mapped files +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() { -// Called when the program receives the UCI 'go' -// command. It searches from the root position and outputs the "bestmove". -void MainThread::search() { - - if (Limits.perft) + // Non-main threads go directly to iterative_deepening() + if (!is_mainthread()) { - nodes = perft(rootPos, Limits.perft); - sync_cout << "\nNodes searched: " << nodes << "\n" << sync_endl; + iterative_deepening(); return; } - Color us = rootPos.side_to_move(); - Time.init(Limits, us, rootPos.game_ply()); - TT.new_search(); - - Eval::NNUE::verify(); + main_manager()->tm.init(limits, rootPos.side_to_move(), rootPos.game_ply(), options, + main_manager()->originalTimeAdjust); + tt.new_search(); if (rootMoves.empty()) { - rootMoves.emplace_back(MOVE_NONE); - sync_cout << "info depth 0 score " - << UCI::value(rootPos.checkers() ? -VALUE_MATE : VALUE_DRAW) << sync_endl; + rootMoves.emplace_back(Move::none()); + main_manager()->updates.onUpdateNoMoves( + {0, {rootPos.checkers() ? -VALUE_MATE : VALUE_DRAW, rootPos}}); } else { - Threads.start_searching(); // start non-main threads - Thread::search(); // main thread start searching + threads.start_searching(); // start non-main threads + iterative_deepening(); // main thread start searching } // 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, + // 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 && (ponder || Limits.infinite)) + 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; + // "ponderhit" just reset threads.ponder) + threads.stop = true; // Wait until all threads have finished - Threads.wait_for_search_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) - Time.availableNodes += Limits.inc[us] - Threads.nodes_searched(); + if (limits.npmsec) + main_manager()->tm.advance_nodes_time(threads.nodes_searched() + - limits.inc[rootPos.side_to_move()]); - Thread* bestThread = this; + Worker* bestThread = this; Skill skill = - Skill(Options["Skill Level"], Options["UCI_LimitStrength"] ? int(Options["UCI_Elo"]) : 0); + Skill(options["Skill Level"], options["UCI_LimitStrength"] ? int(options["UCI_Elo"]) : 0); - if (int(Options["MultiPV"]) == 1 && !Limits.depth && !skill.enabled() - && rootMoves[0].pv[0] != MOVE_NONE) - bestThread = Threads.get_best_thread(); + if (int(options["MultiPV"]) == 1 && !limits.depth && !limits.mate && !skill.enabled() + && rootMoves[0].pv[0] != Move::none()) + bestThread = threads.get_best_thread()->worker.get(); - bestPreviousScore = bestThread->rootMoves[0].score; - bestPreviousAverageScore = bestThread->rootMoves[0].averageScore; + main_manager()->bestPreviousScore = bestThread->rootMoves[0].score; + main_manager()->bestPreviousAverageScore = bestThread->rootMoves[0].averageScore; // Send again PV info if we have a new best thread if (bestThread != this) - sync_cout << UCI::pv(bestThread->rootPos, bestThread->completedDepth) << sync_endl; + main_manager()->pv(*bestThread, threads, tt, bestThread->completedDepth); - sync_cout << "bestmove " << UCI::move(bestThread->rootMoves[0].pv[0], rootPos.is_chess960()); + std::string ponder; if (bestThread->rootMoves[0].pv.size() > 1 - || bestThread->rootMoves[0].extract_ponder_from_tt(rootPos)) - std::cout << " ponder " << UCI::move(bestThread->rootMoves[0].pv[1], rootPos.is_chess960()); + || bestThread->rootMoves[0].extract_ponder_from_tt(tt, rootPos)) + ponder = UCIEngine::move(bestThread->rootMoves[0].pv[1], rootPos.is_chess960()); - std::cout << sync_endl; + 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. -void Thread::search() { +void Search::Worker::iterative_deepening() { + + SearchManager* mainThread = (is_mainthread() ? main_manager() : nullptr); + + Move pv[MAX_PLY + 1]; + + Depth lastBestMoveDepth = 0; + Value lastBestScore = -VALUE_INFINITE; + auto lastBestPV = std::vector{Move::none()}; + + 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 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)); + // (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 = @@ -308,20 +244,16 @@ void Thread::search() { 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; + mainThread->iterValue.fill(VALUE_ZERO); else - for (int i = 0; i < 4; ++i) - mainThread->iterValue[i] = mainThread->bestPreviousScore; + 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); + 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. @@ -333,8 +265,8 @@ void Thread::search() { 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)) + while (++rootDepth < MAX_PLY && !threads.stop + && !(limits.depth && mainThread && rootDepth > limits.depth)) { // Age out PV variability metric if (mainThread) @@ -348,11 +280,11 @@ void Thread::search() { size_t pvFirst = 0; pvLast = 0; - if (!Threads.increaseDepth) + if (!threads.increaseDepth) searchAgainCounter++; // MultiPV loop. We perform a full root search for each PV line - for (pvIdx = 0; pvIdx < multiPV && !Threads.stop; ++pvIdx) + for (pvIdx = 0; pvIdx < multiPV; ++pvIdx) { if (pvIdx == pvLast) { @@ -367,12 +299,12 @@ void Thread::search() { // Reset aspiration window starting size Value avg = rootMoves[pvIdx].averageScore; - delta = Value(10) + int(avg) * avg / 15335; + delta = 5 + avg * avg / 13424; alpha = std::max(avg - delta, -VALUE_INFINITE); beta = std::min(avg + delta, VALUE_INFINITE); // Adjust optimism based on root move's averageScore (~4 Elo) - optimism[us] = 110 * avg / (std::abs(avg) + 121); + optimism[us] = 125 * avg / (std::abs(avg) + 89); optimism[~us] = -optimism[us]; // Start with a small aspiration window and, in the case of a fail @@ -381,11 +313,12 @@ void Thread::search() { 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). + // 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(rootPos, ss, alpha, beta, adjustedDepth, false); + rootDelta = beta - alpha; + bestValue = search(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 @@ -398,17 +331,18 @@ void Thread::search() { // 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) + if (threads.stop) break; - // When failing high/low give some update (without cluttering - // the UI) before a re-search. + // 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) - && Time.elapsed() > 3000) - sync_cout << UCI::pv(rootPos, rootDepth) << sync_endl; + && nodes > 10000000) + main_manager()->pv(*this, threads, tt, rootDepth); - // In case of failing low/high increase aspiration window and - // re-search, otherwise exit the loop. + // In case of failing low/high increase aspiration window and re-search, + // otherwise exit the loop. if (bestValue <= alpha) { beta = (alpha + beta) / 2; @@ -434,71 +368,105 @@ void Thread::search() { // 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 (mainThread + && (threads.stop || pvIdx + 1 == multiPV || nodes > 10000000) + // A thread that aborted search can have mated-in/TB-loss PV and + // score that cannot be trusted, i.e. it can be delayed or refuted + // if we would have had time to fully search other root-moves. Thus + // we suppress this output and below pick a proven score/PV for this + // thread (from the previous iteration). + && !(threads.abortedSearch && rootMoves[0].uciScore <= VALUE_TB_LOSS_IN_MAX_PLY)) + main_manager()->pv(*this, threads, tt, rootDepth); + + if (threads.stop) + break; } - if (!Threads.stop) + if (!threads.stop) completedDepth = rootDepth; - if (rootMoves[0].pv[0] != lastBestMove) + // We make sure not to pick an unproven mated-in score, + // in case this thread prematurely stopped search (aborted-search). + if (threads.abortedSearch && rootMoves[0].score != -VALUE_INFINITE + && rootMoves[0].score <= VALUE_TB_LOSS_IN_MAX_PLY) { - lastBestMove = rootMoves[0].pv[0]; + // Bring the last best move to the front for best thread selection. + Utility::move_to_front(rootMoves, [&lastBestPV = std::as_const(lastBestPV)]( + const auto& rm) { return rm == lastBestPV[0]; }); + rootMoves[0].pv = lastBestPV; + rootMoves[0].score = rootMoves[0].uciScore = lastBestScore; + } + else if (rootMoves[0].pv[0] != lastBestPV[0]) + { + lastBestPV = rootMoves[0].pv; + lastBestScore = rootMoves[0].score; 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; + // Have we found a "mate in x"? + if (limits.mate && rootMoves[0].score == rootMoves[0].uciScore + && ((rootMoves[0].score >= VALUE_MATE_IN_MAX_PLY + && VALUE_MATE - rootMoves[0].score <= 2 * limits.mate) + || (rootMoves[0].score != -VALUE_INFINITE + && rootMoves[0].score <= VALUE_MATED_IN_MAX_PLY + && VALUE_MATE + rootMoves[0].score <= 2 * limits.mate))) + threads.stop = true; + // 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); + skill.pick_best(rootMoves, multiPV); // Use part of the gained time from a previous stable move for the current move - for (Thread* th : Threads) + for (auto&& th : threads) { - totBestMoveChanges += th->bestMoveChanges; - th->bestMoveChanges = 0; + 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) + 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); + int nodesEffort = rootMoves[0].effort * 100 / std::max(size_t(1), size_t(nodes)); + + double fallingEval = (1067 + 223 * (mainThread->bestPreviousAverageScore - bestValue) + + 97 * (mainThread->iterValue[iterIdx] - bestValue)) + / 10000.0; + fallingEval = std::clamp(fallingEval, 0.580, 1.667); // 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(); + timeReduction = lastBestMoveDepth + 8 < completedDepth ? 1.495 : 0.687; + double reduction = (1.48 + mainThread->previousTimeReduction) / (2.17 * timeReduction); + double bestMoveInstability = 1 + 1.88 * totBestMoveChanges / threads.size(); + double recapture = limits.capSq == rootMoves[0].pv[0].to_sq() ? 0.955 : 1.005; - double totalTime = Time.optimum() * fallingEval * reduction * bestMoveInstability; + double totalTime = + mainThread->tm.optimum() * fallingEval * reduction * bestMoveInstability * recapture; // 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); + auto elapsedTime = elapsed(); + + if (completedDepth >= 10 && nodesEffort >= 97 && elapsedTime > totalTime * 0.739 + && !mainThread->ponder) + threads.stop = true; + // Stop the search if we have exceeded the totalTime - if (Time.elapsed() > totalTime) + if (elapsedTime > 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; + threads.stop = true; } - else if (!mainThread->ponder && Time.elapsed() > totalTime * 0.50) - Threads.increaseDepth = false; else - Threads.increaseDepth = true; + threads.increaseDepth = mainThread->ponder || elapsedTime <= totalTime * 0.506; } mainThread->iterValue[iterIdx] = bestValue; @@ -512,29 +480,52 @@ void Thread::search() { // 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))); + std::swap(rootMoves[0], + *std::find(rootMoves.begin(), rootMoves.end(), + skill.best ? skill.best : skill.pick_best(rootMoves, multiPV))); } +// Reset histories, usually before a new game +void Search::Worker::clear() { + mainHistory.fill(0); + captureHistory.fill(-700); + pawnHistory.fill(-1188); + pawnCorrectionHistory.fill(0); + materialCorrectionHistory.fill(0); + + for (bool inCheck : {false, true}) + for (StatsType c : {NoCaptures, Captures}) + for (auto& to : continuationHistory[inCheck][c]) + for (auto& h : to) + h->fill(-658); + + for (size_t i = 1; i < reductions.size(); ++i) + reductions[i] = int((18.62 + std::log(size_t(options["Threads"])) / 2) * std::log(i)); + + refreshTable.clear(networks[numaAccessToken]); +} -namespace { // Main search function for both PV and non-PV nodes template -Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) { +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); - // Check if we have an upcoming move that draws by repetition, or - // if the opponent had an alternative move earlier to this position. - if (!rootNode && alpha < VALUE_DRAW && pos.has_game_cycle(ss->ply)) + // 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(pos.this_thread()); + alpha = value_draw(this->nodes); if (alpha >= beta) return alpha; } @@ -544,32 +535,33 @@ Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, boo assert(0 < depth && depth < MAX_PLY); assert(!(PvNode && cutNode)); - Move pv[MAX_PLY + 1], capturesSearched[32], quietsSearched[32]; + Move pv[MAX_PLY + 1]; StateInfo st; ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize); - TTEntry* tte; - Key posKey; - Move ttMove, move, excludedMove, bestMove; - Depth extension, newDepth; - Value bestValue, value, ttValue, eval, maxValue, probCutBeta; - bool givesCheck, improving, priorCapture, singularQuietLMR; - bool capture, moveCountPruning, ttCapture; - Piece movedPiece; - int moveCount, captureCount, quietCount; + Key posKey; + Move move, excludedMove, bestMove; + Depth extension, newDepth; + Value bestValue, value, eval, maxValue, probCutBeta; + bool givesCheck, improving, priorCapture, opponentWorsening; + bool capture, ttCapture; + Piece movedPiece; + + ValueList capturesSearched; + ValueList quietsSearched; // Step 1. Initialize node - Thread* thisThread = pos.this_thread(); + Worker* thisThread = this; ss->inCheck = pos.checkers(); priorCapture = pos.captured_piece(); Color us = pos.side_to_move(); - moveCount = captureCount = quietCount = ss->moveCount = 0; - bestValue = -VALUE_INFINITE; - maxValue = VALUE_INFINITE; + ss->moveCount = 0; + bestValue = -VALUE_INFINITE; + maxValue = VALUE_INFINITE; // Check for the available remaining time - if (thisThread == Threads.main()) - static_cast(thisThread)->check_time(); + if (is_mainthread()) + main_manager()->check_time(*thisThread); // Used to send selDepth info to GUI (selDepth counts from 1, ply from 0) if (PvNode && thisThread->selDepth < ss->ply + 1) @@ -578,10 +570,12 @@ Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, boo if (!rootNode) { // Step 2. Check for aborted search and immediate draw - if (Threads.stop.load(std::memory_order_relaxed) || pos.is_draw(ss->ply) + 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(pos.this_thread()); + return (ss->ply >= MAX_PLY && !ss->inCheck) + ? evaluate(networks[numaAccessToken], pos, refreshTable, + thisThread->optimism[us]) + : value_draw(thisThread->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 @@ -594,93 +588,82 @@ Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, boo if (alpha >= beta) return alpha; } - else - thisThread->rootDelta = beta - alpha; assert(0 <= ss->ply && ss->ply < MAX_PLY); - (ss + 1)->excludedMove = bestMove = MOVE_NONE; - (ss + 2)->killers[0] = (ss + 2)->killers[1] = MOVE_NONE; - (ss + 2)->cutoffCnt = 0; - ss->doubleExtensions = (ss - 1)->doubleExtensions; - Square prevSq = is_ok((ss - 1)->currentMove) ? to_sq((ss - 1)->currentMove) : SQ_NONE; + bestMove = Move::none(); + (ss + 2)->cutoffCnt = 0; + Square prevSq = ((ss - 1)->currentMove).is_ok() ? ((ss - 1)->currentMove).to_sq() : SQ_NONE; ss->statScore = 0; - // Step 4. Transposition table lookup. - excludedMove = ss->excludedMove; - posKey = pos.key(); - tte = TT.probe(posKey, ss->ttHit); - ttValue = ss->ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE; - ttMove = rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0] - : ss->ttHit ? tte->move() - : MOVE_NONE; - ttCapture = ttMove && pos.capture_stage(ttMove); + // 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 ? thisThread->rootMoves[thisThread->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); // At this point, if excluded, skip straight to step 6, static eval. However, // to save indentation, we list the condition in all code between here and there. - if (!excludedMove) - ss->ttPv = PvNode || (ss->ttHit && tte->is_pv()); // At non-PV nodes we check for an early TT cutoff - if (!PvNode && !excludedMove && tte->depth() > depth - && ttValue != VALUE_NONE // Possible in case of TT access race or if !ttHit - && (tte->bound() & (ttValue >= beta ? BOUND_LOWER : BOUND_UPPER))) + if (!PvNode && !excludedMove && ttData.depth > depth - (ttData.value <= beta) + && ttData.value != VALUE_NONE // Can happen when !ttHit or when access race in probe() + && (ttData.bound & (ttData.value >= beta ? BOUND_LOWER : BOUND_UPPER))) { // If ttMove is quiet, update move sorting heuristics on TT hit (~2 Elo) - if (ttMove) + if (ttData.move && ttData.value >= beta) { - if (ttValue >= beta) - { - // Bonus for a quiet ttMove that fails high (~2 Elo) - if (!ttCapture) - update_quiet_stats(pos, ss, ttMove, stat_bonus(depth)); - - // Extra penalty for early quiet moves of - // the previous ply (~0 Elo on STC, ~2 Elo on LTC). - if (prevSq != SQ_NONE && (ss - 1)->moveCount <= 2 && !priorCapture) - update_continuation_histories(ss - 1, pos.piece_on(prevSq), prevSq, - -stat_malus(depth + 1)); - } - // Penalty for a quiet ttMove that fails low (~1 Elo) - else if (!ttCapture) - { - int penalty = -stat_malus(depth); - thisThread->mainHistory[us][from_to(ttMove)] << penalty; - update_continuation_histories(ss, pos.moved_piece(ttMove), to_sq(ttMove), penalty); - } + // Bonus for a quiet ttMove that fails high (~2 Elo) + if (!ttCapture) + update_quiet_histories(pos, ss, *this, ttData.move, stat_bonus(depth)); + + // Extra penalty for early quiet moves of + // the previous ply (~1 Elo on STC, ~2 Elo on LTC) + if (prevSq != SQ_NONE && (ss - 1)->moveCount <= 2 && !priorCapture) + update_continuation_histories(ss - 1, pos.piece_on(prevSq), prevSq, + -stat_malus(depth + 1)); } // Partial workaround for the graph history interaction problem // For high rule50 counts don't produce transposition table cutoffs. if (pos.rule50_count() < 90) - return ttValue; + return ttData.value; } // Step 5. Tablebases probe - if (!rootNode && !excludedMove && TB::Cardinality) + if (!rootNode && !excludedMove && tbConfig.cardinality) { int piecesCount = pos.count(); - if (piecesCount <= TB::Cardinality - && (piecesCount < TB::Cardinality || depth >= TB::ProbeDepth) && pos.rule50_count() == 0 - && !pos.can_castle(ANY_CASTLING)) + 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 = Tablebases::probe_wdl(pos, &err); // Force check of time on the next occasion - if (thisThread == Threads.main()) - static_cast(thisThread)->callsCnt = 0; + if (is_mainthread()) + main_manager()->callsCnt = 0; if (err != TB::ProbeState::FAIL) { thisThread->tbHits.fetch_add(1, std::memory_order_relaxed); - int drawScore = TB::UseRule50 ? 1 : 0; + int drawScore = tbConfig.useRule50 ? 1 : 0; + + Value tbValue = VALUE_TB - ss->ply; - // use the range VALUE_MATE_IN_MAX_PLY to VALUE_TB_WIN_IN_MAX_PLY to score - value = wdl < -drawScore ? VALUE_MATED_IN_MAX_PLY + ss->ply + 1 - : wdl > drawScore ? VALUE_MATE_IN_MAX_PLY - ss->ply - 1 + // 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 @@ -689,8 +672,9 @@ Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, boo if (b == BOUND_EXACT || (b == BOUND_LOWER ? value >= beta : value <= alpha)) { - tte->save(posKey, value_to_tt(value, ss->ply), ss->ttPv, b, - std::min(MAX_PLY - 1, depth + 6), MOVE_NONE, VALUE_NONE); + 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; } @@ -706,13 +690,12 @@ Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, boo } } - CapturePieceToHistory& captureHistory = thisThread->captureHistory; - // Step 6. Static evaluation of the position + Value unadjustedStaticEval = VALUE_NONE; if (ss->inCheck) { // Skip early pruning when in check - ss->staticEval = eval = VALUE_NONE; + ss->staticEval = eval = (ss - 2)->staticEval; improving = false; goto moves_loop; } @@ -720,92 +703,98 @@ Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, boo { // Providing the hint that this node's accumulator will be used often // brings significant Elo gain (~13 Elo). - Eval::NNUE::hint_common_parent_position(pos); - eval = ss->staticEval; + Eval::NNUE::hint_common_parent_position(pos, networks[numaAccessToken], refreshTable); + unadjustedStaticEval = eval = ss->staticEval; } else if (ss->ttHit) { // Never assume anything about values stored in TT - ss->staticEval = eval = tte->eval(); - if (eval == VALUE_NONE) - ss->staticEval = eval = evaluate(pos); + unadjustedStaticEval = ttData.eval; + if (unadjustedStaticEval == VALUE_NONE) + unadjustedStaticEval = + evaluate(networks[numaAccessToken], pos, refreshTable, thisThread->optimism[us]); else if (PvNode) - Eval::NNUE::hint_common_parent_position(pos); + Eval::NNUE::hint_common_parent_position(pos, networks[numaAccessToken], refreshTable); + + ss->staticEval = eval = to_corrected_static_eval(unadjustedStaticEval, *thisThread, pos); // ttValue can be used as a better position evaluation (~7 Elo) - if (ttValue != VALUE_NONE && (tte->bound() & (ttValue > eval ? BOUND_LOWER : BOUND_UPPER))) - eval = ttValue; + if (ttData.value != VALUE_NONE + && (ttData.bound & (ttData.value > eval ? BOUND_LOWER : BOUND_UPPER))) + eval = ttData.value; } else { - ss->staticEval = eval = evaluate(pos); - // Save static evaluation into the transposition table - tte->save(posKey, VALUE_NONE, ss->ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); + unadjustedStaticEval = + evaluate(networks[numaAccessToken], pos, refreshTable, thisThread->optimism[us]); + ss->staticEval = eval = to_corrected_static_eval(unadjustedStaticEval, *thisThread, pos); + + // 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()); } - // Use static evaluation difference to improve quiet move ordering (~4 Elo) - if (is_ok((ss - 1)->currentMove) && !(ss - 1)->inCheck && !priorCapture) + // Use static evaluation difference to improve quiet move ordering (~9 Elo) + if (((ss - 1)->currentMove).is_ok() && !(ss - 1)->inCheck && !priorCapture) { - int bonus = std::clamp(-18 * int((ss - 1)->staticEval + ss->staticEval), -1812, 1812); - thisThread->mainHistory[~us][from_to((ss - 1)->currentMove)] << bonus; - if (type_of(pos.piece_on(prevSq)) != PAWN && type_of((ss - 1)->currentMove) != PROMOTION) - thisThread->pawnHistory[pawn_structure(pos)][pos.piece_on(prevSq)][prevSq] << bonus / 4; + int bonus = std::clamp(-10 * int((ss - 1)->staticEval + ss->staticEval), -1664, 1471) + 752; + thisThread->mainHistory[~us][((ss - 1)->currentMove).from_to()] << bonus; + if (type_of(pos.piece_on(prevSq)) != PAWN && ((ss - 1)->currentMove).type_of() != PROMOTION) + thisThread->pawnHistory[pawn_structure_index(pos)][pos.piece_on(prevSq)][prevSq] + << bonus / 2; } // 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 look at static evaluation at move prior to it - // and if we were in check at move prior to it flag is set to true) and is + // 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. - improving = (ss - 2)->staticEval != VALUE_NONE ? ss->staticEval > (ss - 2)->staticEval - : (ss - 4)->staticEval != VALUE_NONE ? ss->staticEval > (ss - 4)->staticEval - : true; + improving = ss->staticEval > (ss - 2)->staticEval; + + opponentWorsening = ss->staticEval + (ss - 1)->staticEval > 2; // Step 7. Razoring (~1 Elo) - // If eval is really low check with qsearch if it can exceed alpha, if it can't, - // return a fail low. - // Adjust razor margin according to cutoffCnt. (~1 Elo) - if (eval < alpha - 474 - (270 - 174 * ((ss + 1)->cutoffCnt > 3)) * depth * depth) + // If eval is really low, check with qsearch if we can exceed alpha. If the + // search suggests we cannot exceed alpha, return a speculative fail low. + if (eval < alpha - 494 - 290 * depth * depth) { value = qsearch(pos, ss, alpha - 1, alpha); - if (value < alpha) + if (value < alpha && std::abs(value) < VALUE_TB_WIN_IN_MAX_PLY) return value; } // Step 8. Futility pruning: child node (~40 Elo) // The depth condition is important for mate finding. - if (!ss->ttPv && depth < 9 - && eval - futility_margin(depth, cutNode && !ss->ttHit, improving) - - (ss - 1)->statScore / 321 + if (!ss->ttPv && depth < 13 + && eval - futility_margin(depth, cutNode && !ss->ttHit, improving, opponentWorsening) + - (ss - 1)->statScore / 260 >= beta - && eval >= beta && eval < 29462 // smaller than TB wins - && (!ttMove || ttCapture)) - return eval; + && eval >= beta && (!ttData.move || ttCapture) && beta > VALUE_TB_LOSS_IN_MAX_PLY + && eval < VALUE_TB_WIN_IN_MAX_PLY) + return beta + (eval - beta) / 3; // Step 9. Null move search with verification search (~35 Elo) - if (!PvNode && (ss - 1)->currentMove != MOVE_NULL && (ss - 1)->statScore < 17257 && eval >= beta - && eval >= ss->staticEval && ss->staticEval >= beta - 24 * depth + 281 && !excludedMove - && pos.non_pawn_material(us) && ss->ply >= thisThread->nmpMinPly - && beta > VALUE_TB_LOSS_IN_MAX_PLY) + if (cutNode && (ss - 1)->currentMove != Move::null() && eval >= beta + && ss->staticEval >= beta - 21 * depth + 390 && !excludedMove && pos.non_pawn_material(us) + && ss->ply >= thisThread->nmpMinPly && beta > VALUE_TB_LOSS_IN_MAX_PLY) { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and eval - Depth R = std::min(int(eval - beta) / 152, 6) + depth / 3 + 4; + Depth R = std::min(int(eval - beta) / 202, 6) + depth / 3 + 5; - ss->currentMove = MOVE_NULL; + ss->currentMove = Move::null(); ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0]; - pos.do_null_move(st); + pos.do_null_move(st, tt); - Value nullValue = -search(pos, ss + 1, -beta, -beta + 1, depth - R, !cutNode); + Value nullValue = -search(pos, ss + 1, -beta, -beta + 1, depth - R, false); pos.undo_null_move(); // Do not return unproven mate or TB scores if (nullValue >= beta && nullValue < VALUE_TB_WIN_IN_MAX_PLY) { - if (thisThread->nmpMinPly || depth < 14) + if (thisThread->nmpMinPly || depth < 16) return nullValue; assert(!thisThread->nmpMinPly); // Recursive verification is not allowed @@ -824,83 +813,95 @@ Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, boo } // Step 10. Internal iterative reductions (~9 Elo) - // For PV nodes without a ttMove, we decrease depth by 2, - // or by 4 if the current position is present in the TT and - // the stored depth is greater than or equal to the current depth. - // Use qsearch if depth <= 0. - if (PvNode && !ttMove) - depth -= 2 + 2 * (ss->ttHit && tte->depth() >= depth); + // For PV nodes without a ttMove, we decrease depth. + if (PvNode && !ttData.move) + depth -= 3; + // Use qsearch if depth <= 0 if (depth <= 0) return qsearch(pos, ss, alpha, beta); - // For cutNodes without a ttMove, we decrease depth by 2 - // if current depth >= 8. - if (cutNode && depth >= 8 && !ttMove) - depth -= 2; - - probCutBeta = beta + 168 - 70 * improving; + // For cutNodes, if depth is high enough, decrease depth by 2 if there is no ttMove, + // or by 1 if there is a ttMove with an upper bound. + if (cutNode && depth >= 7 && (!ttData.move || ttData.bound == BOUND_UPPER)) + depth -= 1 + !ttData.move; // Step 11. ProbCut (~10 Elo) - // 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. - if ( - !PvNode && depth > 3 - && abs(beta) < VALUE_TB_WIN_IN_MAX_PLY - // If value from transposition table is lower than probCutBeta, don't attempt probCut - // there and in further interactions with transposition table cutoff depth is set to depth - 3 - // because probCut search has depth set to depth - 4 but we also do a move before it - // So effective depth is equal to depth - 3 - && !(tte->depth() >= depth - 3 && ttValue != VALUE_NONE && ttValue < probCutBeta)) + // 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 + 184 - 53 * improving; + if (!PvNode && depth > 3 + && std::abs(beta) < VALUE_TB_WIN_IN_MAX_PLY + // If value from transposition table is lower than probCutBeta, don't attempt + // probCut there and in further interactions with transposition table cutoff + // depth is set to depth - 3 because probCut search has depth set to depth - 4 + // but we also do a move before it. So effective depth is equal to depth - 3. + && !(ttData.depth >= depth - 3 && ttData.value != VALUE_NONE && ttData.value < probCutBeta)) { - assert(probCutBeta < VALUE_INFINITE); + assert(probCutBeta < VALUE_INFINITE && probCutBeta > beta); - MovePicker mp(pos, ttMove, probCutBeta - ss->staticEval, &captureHistory); + MovePicker mp(pos, ttData.move, probCutBeta - ss->staticEval, &thisThread->captureHistory); + Piece captured; - while ((move = mp.next_move()) != MOVE_NONE) - if (move != excludedMove && pos.legal(move)) - { - assert(pos.capture_stage(move)); + while ((move = mp.next_move()) != Move::none()) + { + assert(move.is_ok()); - // Prefetch the TT entry for the resulting position - prefetch(TT.first_entry(pos.key_after(move))); + if (move == excludedMove) + continue; - ss->currentMove = move; - ss->continuationHistory = - &thisThread - ->continuationHistory[ss->inCheck][true][pos.moved_piece(move)][to_sq(move)]; + if (!pos.legal(move)) + continue; - pos.do_move(move, st); + assert(pos.capture_stage(move)); - // Perform a preliminary qsearch to verify that the move holds - value = -qsearch(pos, ss + 1, -probCutBeta, -probCutBeta + 1); + movedPiece = pos.moved_piece(move); + captured = pos.piece_on(move.to_sq()); - // If the qsearch held, perform the regular search - if (value >= probCutBeta) - value = -search(pos, ss + 1, -probCutBeta, -probCutBeta + 1, depth - 4, - !cutNode); - pos.undo_move(move); + // Prefetch the TT entry for the resulting position + prefetch(tt.first_entry(pos.key_after(move))); - if (value >= probCutBeta) - { - // Save ProbCut data into transposition table - tte->save(posKey, value_to_tt(value, ss->ply), ss->ttPv, BOUND_LOWER, depth - 3, - move, ss->staticEval); - return value - (probCutBeta - beta); - } + ss->currentMove = move; + ss->continuationHistory = + &this->continuationHistory[ss->inCheck][true][pos.moved_piece(move)][move.to_sq()]; + + thisThread->nodes.fetch_add(1, std::memory_order_relaxed); + pos.do_move(move, st); + + // Perform a preliminary qsearch to verify that the move holds + value = -qsearch(pos, ss + 1, -probCutBeta, -probCutBeta + 1); + + // If the qsearch held, perform the regular search + if (value >= probCutBeta) + value = + -search(pos, ss + 1, -probCutBeta, -probCutBeta + 1, depth - 4, !cutNode); + + pos.undo_move(move); + + if (value >= probCutBeta) + { + thisThread->captureHistory[movedPiece][move.to_sq()][type_of(captured)] + << stat_bonus(depth - 2); + + // Save ProbCut data into transposition table + ttWriter.write(posKey, value_to_tt(value, ss->ply), ss->ttPv, BOUND_LOWER, + depth - 3, move, unadjustedStaticEval, tt.generation()); + return std::abs(value) < VALUE_TB_WIN_IN_MAX_PLY ? value - (probCutBeta - beta) + : value; } + } - Eval::NNUE::hint_common_parent_position(pos); + Eval::NNUE::hint_common_parent_position(pos, networks[numaAccessToken], refreshTable); } moves_loop: // When in check, search starts here - // Step 12. A small Probcut idea, when we are in check (~4 Elo) - probCutBeta = beta + 416; - if (ss->inCheck && !PvNode && ttCapture && (tte->bound() & BOUND_LOWER) - && tte->depth() >= depth - 4 && ttValue >= probCutBeta - && abs(ttValue) < VALUE_TB_WIN_IN_MAX_PLY && abs(beta) < VALUE_TB_WIN_IN_MAX_PLY) + // Step 12. A small Probcut idea (~4 Elo) + probCutBeta = beta + 390; + if ((ttData.bound & BOUND_LOWER) && ttData.depth >= depth - 4 && ttData.value >= probCutBeta + && std::abs(beta) < VALUE_TB_WIN_IN_MAX_PLY + && std::abs(ttData.value) < VALUE_TB_WIN_IN_MAX_PLY) return probCutBeta; const PieceToHistory* contHist[] = {(ss - 1)->continuationHistory, @@ -910,25 +911,20 @@ moves_loop: // When in check, search starts here nullptr, (ss - 6)->continuationHistory}; - Move countermove = - prevSq != SQ_NONE ? thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] : MOVE_NONE; - MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &captureHistory, contHist, - &thisThread->pawnHistory, countermove, ss->killers); + MovePicker mp(pos, ttData.move, depth, &thisThread->mainHistory, &thisThread->captureHistory, + contHist, &thisThread->pawnHistory); - value = bestValue; - moveCountPruning = singularQuietLMR = false; + value = bestValue; - // Indicate PvNodes that will probably fail low if the node was searched - // at a depth equal to or greater than the current depth, and the result - // of this search was a fail low. - bool likelyFailLow = PvNode && ttMove && (tte->bound() & BOUND_UPPER) && tte->depth() >= depth; + int moveCount = 0; + bool moveCountPruning = false; // Step 13. Loop through all pseudo-legal moves until no moves remain // or a beta cutoff occurs. - while ((move = mp.next_move(moveCountPruning)) != MOVE_NONE) + while ((move = mp.next_move(moveCountPruning)) != Move::none()) { - assert(is_ok(move)); + assert(move.is_ok()); if (move == excludedMove) continue; @@ -947,10 +943,11 @@ moves_loop: // When in check, search starts here ss->moveCount = ++moveCount; - if (rootNode && thisThread == Threads.main() && Time.elapsed() > 3000) - sync_cout << "info depth " << depth << " currmove " - << UCI::move(move, pos.is_chess960()) << " currmovenumber " - << moveCount + thisThread->pvIdx << sync_endl; + if (rootNode && is_mainthread() && nodes > 10000000) + { + main_manager()->updates.onIter( + {depth, UCIEngine::move(move, pos.is_chess960()), moveCount + thisThread->pvIdx}); + } if (PvNode) (ss + 1)->pv = nullptr; @@ -962,65 +959,71 @@ moves_loop: // When in check, search starts here // Calculate new depth for this move newDepth = depth - 1; - Value delta = beta - alpha; + int delta = beta - alpha; - Depth r = reduction(improving, depth, moveCount, delta, thisThread->rootDelta); + Depth r = reduction(improving, depth, moveCount, delta); // Step 14. Pruning at shallow depth (~120 Elo). // Depth conditions are important for mate finding. if (!rootNode && pos.non_pawn_material(us) && bestValue > VALUE_TB_LOSS_IN_MAX_PLY) { // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold (~8 Elo) - if (!moveCountPruning) - moveCountPruning = moveCount >= futility_move_count(improving, depth); + moveCountPruning = moveCount >= futility_move_count(improving, depth); // Reduced depth of the next LMR search int lmrDepth = newDepth - r; if (capture || givesCheck) { + Piece capturedPiece = pos.piece_on(move.to_sq()); + int captHist = + thisThread->captureHistory[movedPiece][move.to_sq()][type_of(capturedPiece)]; + // Futility pruning for captures (~2 Elo) if (!givesCheck && lmrDepth < 7 && !ss->inCheck) { - Piece capturedPiece = pos.piece_on(to_sq(move)); - int futilityEval = - ss->staticEval + 239 + 291 * lmrDepth + PieceValue[capturedPiece] - + captureHistory[movedPiece][to_sq(move)][type_of(capturedPiece)] / 7; - if (futilityEval < alpha) + Value futilityValue = ss->staticEval + 285 + 251 * lmrDepth + + PieceValue[capturedPiece] + captHist / 7; + if (futilityValue <= alpha) continue; } // SEE based pruning for captures and checks (~11 Elo) - if (!pos.see_ge(move, Value(-185) * depth)) + int seeHist = std::clamp(captHist / 32, -182 * depth, 166 * depth); + if (!pos.see_ge(move, -168 * depth - seeHist)) continue; } else { - int history = (*contHist[0])[movedPiece][to_sq(move)] - + (*contHist[1])[movedPiece][to_sq(move)] - + (*contHist[3])[movedPiece][to_sq(move)] - + thisThread->pawnHistory[pawn_structure(pos)][movedPiece][to_sq(move)]; + int history = + (*contHist[0])[movedPiece][move.to_sq()] + + (*contHist[1])[movedPiece][move.to_sq()] + + thisThread->pawnHistory[pawn_structure_index(pos)][movedPiece][move.to_sq()]; // Continuation history based pruning (~2 Elo) - if (lmrDepth < 6 && history < -3645 * depth) + if (history < -4165 * depth) continue; - history += 2 * thisThread->mainHistory[us][from_to(move)]; + history += 2 * thisThread->mainHistory[us][move.from_to()]; - lmrDepth += history / 7836; - lmrDepth = std::max(lmrDepth, -1); + lmrDepth += history / 3853; + + Value futilityValue = + ss->staticEval + (bestValue < ss->staticEval - 51 ? 143 : 52) + 135 * lmrDepth; // Futility pruning: parent node (~13 Elo) - if (!ss->inCheck && lmrDepth < 13 - && ss->staticEval + (bestValue < ss->staticEval - 62 ? 123 : 77) - + 127 * lmrDepth - <= alpha) + if (!ss->inCheck && lmrDepth < 12 && futilityValue <= alpha) + { + if (bestValue <= futilityValue && std::abs(bestValue) < VALUE_TB_WIN_IN_MAX_PLY + && futilityValue < VALUE_TB_WIN_IN_MAX_PLY) + bestValue = futilityValue; continue; + } lmrDepth = std::max(lmrDepth, 0); // Prune moves with negative SEE (~4 Elo) - if (!pos.see_ge(move, Value(-26 * lmrDepth * lmrDepth))) + if (!pos.see_ge(move, -24 * lmrDepth * lmrDepth)) continue; } } @@ -1029,193 +1032,172 @@ moves_loop: // When in check, search starts here // We take care to not overdo to avoid search getting stuck. if (ss->ply < thisThread->rootDepth * 2) { - // Singular extension search (~94 Elo). If all moves but one fail low on a - // search of (alpha-s, beta-s), and just one fails high on (alpha, beta), - // then that move is singular and should be extended. To verify this we do - // a reduced search on the position excluding the ttMove and if the result - // is lower than ttValue minus a margin, then we will extend the ttMove. - - // Note: the depth margin and singularBeta margin are known for having non-linear - // scaling. Their values are optimized to time controls of 180+1.8 and longer - // so changing them requires tests at this type of time controls. - // Recursive singular search is avoided. - if (!rootNode && move == ttMove && !excludedMove - && depth >= 4 - (thisThread->completedDepth > 24) + 2 * (PvNode && tte->is_pv()) - && abs(ttValue) < VALUE_TB_WIN_IN_MAX_PLY && (tte->bound() & BOUND_LOWER) - && tte->depth() >= depth - 3) + // Singular extension search (~76 Elo, ~170 nElo). If all moves but one + // fail low on a search of (alpha-s, beta-s), and just one fails high on + // (alpha, beta), then that move is singular and should be extended. To + // verify this we do a reduced search on the position excluding the ttMove + // and if the result is lower than ttValue minus a margin, then we will + // extend the ttMove. Recursive singular search is avoided. + + // Note: the depth margin and singularBeta margin are known for having + // non-linear scaling. Their values are optimized to time controls of + // 180+1.8 and longer so changing them requires tests at these types of + // time controls. Generally, higher singularBeta (i.e closer to ttValue) + // and lower extension margins scale well. + + if (!rootNode && move == ttData.move && !excludedMove + && depth >= 4 - (thisThread->completedDepth > 36) + ss->ttPv + && std::abs(ttData.value) < VALUE_TB_WIN_IN_MAX_PLY && (ttData.bound & BOUND_LOWER) + && ttData.depth >= depth - 3) { - Value singularBeta = ttValue - (64 + 57 * (ss->ttPv && !PvNode)) * depth / 64; - Depth singularDepth = (depth - 1) / 2; + Value singularBeta = ttData.value - (54 + 76 * (ss->ttPv && !PvNode)) * depth / 64; + Depth singularDepth = newDepth / 2; ss->excludedMove = move; value = search(pos, ss, singularBeta - 1, singularBeta, singularDepth, cutNode); - ss->excludedMove = MOVE_NONE; + ss->excludedMove = Move::none(); if (value < singularBeta) { - extension = 1; - singularQuietLMR = !ttCapture; - - // Avoid search explosion by limiting the number of double extensions - if (!PvNode && value < singularBeta - 18 && ss->doubleExtensions <= 11) - { - extension = 2; - depth += depth < 15; - } + int doubleMargin = 293 * PvNode - 195 * !ttCapture; + int tripleMargin = 107 + 259 * PvNode - 260 * !ttCapture + 98 * ss->ttPv; + + extension = 1 + (value < singularBeta - doubleMargin) + + (value < singularBeta - tripleMargin); + + depth += ((!PvNode) && (depth < 16)); } // Multi-cut pruning // Our ttMove is assumed to fail high based on the bound of the TT entry, - // and if after excluding the ttMove with a reduced search we fail high over the original beta, - // we assume this expected cut-node is not singular (multiple moves fail high), - // and we can prune the whole subtree by returning a softbound. - else if (singularBeta >= beta) - return singularBeta; + // and if after excluding the ttMove with a reduced search we fail high + // over the original beta, we assume this expected cut-node is not + // singular (multiple moves fail high), and we can prune the whole + // subtree by returning a softbound. + else if (value >= beta && std::abs(value) < VALUE_TB_WIN_IN_MAX_PLY) + return value; // Negative extensions - // If other moves failed high over (ttValue - margin) without the ttMove on a reduced search, - // but we cannot do multi-cut because (ttValue - margin) is lower than the original beta, - // we do not know if the ttMove is singular or can do a multi-cut, - // so we reduce the ttMove in favor of other moves based on some conditions: - - // If the ttMove is assumed to fail high over currnet beta (~7 Elo) - else if (ttValue >= beta) - extension = -2 - !PvNode; - - // If we are on a cutNode but the ttMove is not assumed to fail high over current beta (~1 Elo) + // If other moves failed high over (ttValue - margin) without the + // ttMove on a reduced search, but we cannot do multi-cut because + // (ttValue - margin) is lower than the original beta, we do not know + // if the ttMove is singular or can do a multi-cut, so we reduce the + // ttMove in favor of other moves based on some conditions: + + // If the ttMove is assumed to fail high over current beta (~7 Elo) + else if (ttData.value >= beta) + extension = -3; + + // If we are on a cutNode but the ttMove is not assumed to fail high + // over current beta (~1 Elo) else if (cutNode) - extension = depth < 19 ? -2 : -1; - - // If the ttMove is assumed to fail low over the value of the reduced search (~1 Elo) - else if (ttValue <= value) - extension = -1; + extension = -2; } - // Check extensions (~1 Elo) - else if (givesCheck && depth > 9) - extension = 1; - - // Quiet ttMove extensions (~1 Elo) - else if (PvNode && move == ttMove && move == ss->killers[0] - && (*contHist[0])[movedPiece][to_sq(move)] >= 4194) - extension = 1; - - // Recapture extensions (~1 Elo) - else if (PvNode && move == ttMove && to_sq(move) == prevSq - && captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))] - > 4000) + // Extension for capturing the previous moved piece (~1 Elo at LTC) + else if (PvNode && move.to_sq() == prevSq + && thisThread->captureHistory[movedPiece][move.to_sq()] + [type_of(pos.piece_on(move.to_sq()))] + > 3994) extension = 1; } // Add extension to new depth newDepth += extension; - ss->doubleExtensions = (ss - 1)->doubleExtensions + (extension == 2); // Speculative prefetch as early as possible - prefetch(TT.first_entry(pos.key_after(move))); + prefetch(tt.first_entry(pos.key_after(move))); // Update the current move (this must be done after singular extension search) ss->currentMove = move; ss->continuationHistory = - &thisThread->continuationHistory[ss->inCheck][capture][movedPiece][to_sq(move)]; + &thisThread->continuationHistory[ss->inCheck][capture][movedPiece][move.to_sq()]; + + uint64_t nodeCount = rootNode ? uint64_t(nodes) : 0; // Step 16. Make the move + thisThread->nodes.fetch_add(1, std::memory_order_relaxed); pos.do_move(move, st, givesCheck); - // Decrease reduction if position is or has been on the PV (~4 Elo) - if (ss->ttPv && !likelyFailLow) - r -= cutNode && tte->depth() >= depth ? 3 : 2; + // These reduction adjustments 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. - // Decrease reduction if opponent's move count is high (~1 Elo) - if ((ss - 1)->moveCount > 7) - r--; + // Decrease reduction if position is or has been on the PV (~7 Elo) + if (ss->ttPv) + r -= 1 + (ttData.value > alpha) + (ttData.depth >= depth); - // Increase reduction for cut nodes (~3 Elo) - if (cutNode) - r += 2; - - // Increase reduction if ttMove is a capture (~3 Elo) - if (ttCapture) - r++; - - // Decrease reduction for PvNodes (~2 Elo) + // Decrease reduction for PvNodes (~0 Elo on STC, ~2 Elo on LTC) if (PvNode) r--; - // Decrease reduction if a quiet ttMove has been singularly extended (~1 Elo) - if (singularQuietLMR) - r--; + // These reduction adjustments have no proven non-linear scaling + + // Increase reduction for cut nodes (~4 Elo) + if (cutNode) + r += 2 - (ttData.depth >= depth && ss->ttPv); - // Increase reduction on repetition (~1 Elo) - if (move == (ss - 4)->currentMove && pos.has_repeated()) - r += 2; + // Increase reduction if ttMove is a capture but the current move is not a capture (~3 Elo) + if (ttCapture && !capture) + r++; // Increase reduction if next ply has a lot of fail high (~5 Elo) if ((ss + 1)->cutoffCnt > 3) - r++; + r += 1 + allNode; - // Set reduction to 0 for first generated move (ttMove) - // Nullifies all previous reduction adjustments to ttMove and leaves only history to do them - else if (move == ttMove) - r = 0; + // For first picked move (ttMove) reduce reduction (~3 Elo) + else if (move == ttData.move) + r -= 2; - ss->statScore = 2 * thisThread->mainHistory[us][from_to(move)] - + (*contHist[0])[movedPiece][to_sq(move)] - + (*contHist[1])[movedPiece][to_sq(move)] - + (*contHist[3])[movedPiece][to_sq(move)] - 3848; + ss->statScore = 2 * thisThread->mainHistory[us][move.from_to()] + + (*contHist[0])[movedPiece][move.to_sq()] + + (*contHist[1])[movedPiece][move.to_sq()] - 4664; - // Decrease/increase reduction for moves with a good/bad history (~25 Elo) - r -= ss->statScore / (10216 + 3855 * (depth > 5 && depth < 23)); + // Decrease/increase reduction for moves with a good/bad history (~8 Elo) + r -= ss->statScore / 10898; // Step 17. Late moves reduction / extension (LMR, ~117 Elo) - // We use various heuristics for the sons of a node after the first son has - // been searched. In general, we would like to reduce them, but there are many - // cases where we extend a son if it has good chances to be "interesting". - if (depth >= 2 && moveCount > 1 + (PvNode && ss->ply <= 1) - && (!ss->ttPv || !capture || (cutNode && (ss - 1)->moveCount > 1))) + if (depth >= 2 && moveCount > 1) { // In general we want to cap the LMR depth search at newDepth, but when // reduction is negative, we allow this move a limited search extension - // beyond the first move depth. This may lead to hidden double extensions. + // beyond the first move depth. // To prevent problems when the max value is less than the min value, // std::clamp has been replaced by a more robust implementation. - Depth d = std::max(1, std::min(newDepth - r, newDepth + 1)); + Depth d = std::max(1, std::min(newDepth - r, newDepth + !allNode)); value = -search(pos, ss + 1, -(alpha + 1), -alpha, d, true); // Do a full-depth search when reduced LMR search fails high if (value > alpha && d < newDepth) { - // Adjust full-depth search based on LMR results - if the result - // was good enough search deeper, if it was bad enough search shallower. - const bool doDeeperSearch = value > (bestValue + 51 + 10 * (newDepth - d)); - const bool doEvenDeeperSearch = value > alpha + 700 && ss->doubleExtensions <= 6; - const bool doShallowerSearch = value < bestValue + newDepth; + // Adjust full-depth search based on LMR results - if the result was + // good enough search deeper, if it was bad enough search shallower. + const bool doDeeperSearch = value > (bestValue + 35 + 2 * newDepth); // (~1 Elo) + const bool doShallowerSearch = value < bestValue + 8; // (~2 Elo) - ss->doubleExtensions = ss->doubleExtensions + doEvenDeeperSearch; - - newDepth += doDeeperSearch - doShallowerSearch + doEvenDeeperSearch; + newDepth += doDeeperSearch - doShallowerSearch; if (newDepth > d) value = -search(pos, ss + 1, -(alpha + 1), -alpha, newDepth, !cutNode); - int bonus = value <= alpha ? -stat_malus(newDepth) - : value >= beta ? stat_bonus(newDepth) - : 0; + // Post LMR continuation history updates (~1 Elo) + int bonus = value >= beta ? stat_bonus(newDepth) : -stat_malus(newDepth); - update_continuation_histories(ss, movedPiece, to_sq(move), bonus); + update_continuation_histories(ss, movedPiece, move.to_sq(), bonus); } } // Step 18. Full-depth search when LMR is skipped else if (!PvNode || moveCount > 1) { - // Increase reduction for cut nodes without ttMove (~1 Elo) - if (!ttMove && cutNode) + // Increase reduction if ttMove is not present (~6 Elo) + if (!ttData.move) r += 2; - // Note that if expected reduction is high, we reduce search depth by 1 here + // Note that if expected reduction is high, we reduce search depth by 1 here (~9 Elo) value = -search(pos, ss + 1, -(alpha + 1), -alpha, newDepth - (r > 3), !cutNode); } @@ -1224,7 +1206,11 @@ moves_loop: // When in check, search starts here if (PvNode && (moveCount == 1 || value > alpha)) { (ss + 1)->pv = pv; - (ss + 1)->pv[0] = MOVE_NONE; + (ss + 1)->pv[0] = Move::none(); + + // Extend move from transposition table if we are about to dive into qsearch. + if (move == ttData.move && ss->ply <= thisThread->rootDepth * 2) + newDepth = std::max(newDepth, 1); value = -search(pos, ss + 1, -beta, -alpha, newDepth, false); } @@ -1236,9 +1222,9 @@ moves_loop: // When in check, search starts here // Step 20. Check for a new best move // Finished searching the move. If a stop occurred, the return value of - // the search cannot be trusted, and we return immediately without - // updating best move, PV and TT. - if (Threads.stop.load(std::memory_order_relaxed)) + // the search cannot be trusted, and we return immediately without updating + // best move, principal variation nor transposition table. + if (threads.stop.load(std::memory_order_relaxed)) return VALUE_ZERO; if (rootNode) @@ -1246,8 +1232,10 @@ moves_loop: // When in check, search starts here RootMove& rm = *std::find(thisThread->rootMoves.begin(), thisThread->rootMoves.end(), move); + rm.effort += nodes - nodeCount; + rm.averageScore = - rm.averageScore != -VALUE_INFINITE ? (2 * value + rm.averageScore) / 3 : value; + rm.averageScore != -VALUE_INFINITE ? (value + rm.averageScore) / 2 : value; // PV move or new best move? if (moveCount == 1 || value > alpha) @@ -1271,7 +1259,7 @@ moves_loop: // When in check, search starts here assert((ss + 1)->pv); - for (Move* m = (ss + 1)->pv; *m != MOVE_NONE; ++m) + for (Move* m = (ss + 1)->pv; *m != Move::none(); ++m) rm.pv.push_back(*m); // We record how often the best move has been changed in each iteration. @@ -1287,11 +1275,17 @@ moves_loop: // When in check, search starts here rm.score = -VALUE_INFINITE; } - if (value > bestValue) + // In case we have an alternative move equal in eval to the current bestmove, + // promote it to bestmove by pretending it just exceeds alpha (but not beta). + int inc = + (value == bestValue && (int(nodes) & 15) == 0 && ss->ply + 2 >= thisThread->rootDepth + && std::abs(value) + 1 < VALUE_TB_WIN_IN_MAX_PLY); + + if (value + inc > bestValue) { bestValue = value; - if (value > alpha) + if (value + inc > alpha) { bestMove = move; @@ -1300,14 +1294,14 @@ moves_loop: // When in check, search starts here if (value >= beta) { - ss->cutoffCnt += 1 + !ttMove; + ss->cutoffCnt += !ttData.move + (extension < 2); assert(value >= beta); // Fail high break; } else { // Reduce other moves if we have found at least one score improvement (~2 Elo) - if (depth > 2 && depth < 12 && beta < 13828 && value > -11369) + if (depth > 2 && depth < 14 && std::abs(value) < VALUE_TB_WIN_IN_MAX_PLY) depth -= 2; assert(depth > 0); @@ -1321,10 +1315,9 @@ moves_loop: // When in check, search starts here if (move != bestMove && moveCount <= 32) { if (capture) - capturesSearched[captureCount++] = move; - + capturesSearched.push_back(move); else - quietsSearched[quietCount++] = move; + quietsSearched.push_back(move); } } @@ -1335,25 +1328,46 @@ moves_loop: // When in check, search starts here assert(moveCount || !ss->inCheck || excludedMove || !MoveList(pos).size()); + // Adjust best value for fail high cases at non-pv nodes + if (!PvNode && bestValue >= beta && std::abs(bestValue) < VALUE_TB_WIN_IN_MAX_PLY + && std::abs(beta) < VALUE_TB_WIN_IN_MAX_PLY && std::abs(alpha) < VALUE_TB_WIN_IN_MAX_PLY) + bestValue = (bestValue * depth + beta) / (depth + 1); + if (!moveCount) bestValue = excludedMove ? alpha : ss->inCheck ? mated_in(ss->ply) : VALUE_DRAW; - // If there is a move that produces search value greater than alpha we update the stats of searched moves + // If there is a move that produces search value greater than alpha, + // we update the stats of searched moves. else if (bestMove) - update_all_stats(pos, ss, bestMove, bestValue, beta, prevSq, quietsSearched, quietCount, - capturesSearched, captureCount, depth); + update_all_stats(pos, ss, *this, bestMove, prevSq, quietsSearched, capturesSearched, depth); // Bonus for prior countermove that caused the fail low else if (!priorCapture && prevSq != SQ_NONE) { - int bonus = (depth > 6) + (PvNode || cutNode) + (bestValue < alpha - 657) - + ((ss - 1)->moveCount > 10); + int bonus = (122 * (depth > 5) + 39 * !allNode + 165 * ((ss - 1)->moveCount > 8) + + 107 * (!ss->inCheck && bestValue <= ss->staticEval - 98) + + 134 * (!(ss - 1)->inCheck && bestValue <= -(ss - 1)->staticEval - 91)); + + // Proportional to "how much damage we have to undo" + bonus += std::min(-(ss - 1)->statScore / 100, 304); + + bonus = std::max(bonus, 0); + update_continuation_histories(ss - 1, pos.piece_on(prevSq), prevSq, - stat_bonus(depth) * bonus); - thisThread->mainHistory[~us][from_to((ss - 1)->currentMove)] - << stat_bonus(depth) * bonus / 2; + stat_bonus(depth) * bonus / 116); + thisThread->mainHistory[~us][((ss - 1)->currentMove).from_to()] + << stat_bonus(depth) * bonus / 180; + + + if (type_of(pos.piece_on(prevSq)) != PAWN && ((ss - 1)->currentMove).type_of() != PROMOTION) + thisThread->pawnHistory[pawn_structure_index(pos)][pos.piece_on(prevSq)][prevSq] + << stat_bonus(depth) * bonus / 25; } + // Bonus when search fails low and there is a TT move + else if (moveCount > 1 && ttData.move && !allNode) + thisThread->mainHistory[us][ttData.move.from_to()] << stat_bonus(depth) / 4; + if (PvNode) bestValue = std::min(bestValue, maxValue); @@ -1362,13 +1376,25 @@ moves_loop: // When in check, search starts here if (bestValue <= alpha) ss->ttPv = ss->ttPv || ((ss - 1)->ttPv && depth > 3); - // Write gathered information in transposition table + // Write gathered information in transposition table. Note that the + // static evaluation is saved as it was before correction history. if (!excludedMove && !(rootNode && thisThread->pvIdx)) - tte->save(posKey, value_to_tt(bestValue, ss->ply), ss->ttPv, - bestValue >= beta ? BOUND_LOWER - : PvNode && bestMove ? BOUND_EXACT - : BOUND_UPPER, - depth, bestMove, ss->staticEval); + ttWriter.write(posKey, value_to_tt(bestValue, ss->ply), ss->ttPv, + bestValue >= beta ? BOUND_LOWER + : PvNode && bestMove ? BOUND_EXACT + : BOUND_UPPER, + depth, bestMove, unadjustedStaticEval, tt.generation()); + + // Adjust correction history + if (!ss->inCheck && (!bestMove || !pos.capture(bestMove)) + && !(bestValue >= beta && bestValue <= ss->staticEval) + && !(!bestMove && bestValue >= ss->staticEval)) + { + auto bonus = std::clamp(int(bestValue - ss->staticEval) * depth / 8, + -CORRECTION_HISTORY_LIMIT / 4, CORRECTION_HISTORY_LIMIT / 4); + thisThread->pawnCorrectionHistory[us][pawn_structure_index(pos)] << bonus; + thisThread->materialCorrectionHistory[us][material_index(pos)] << bonus; + } assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1376,24 +1402,25 @@ moves_loop: // When in check, search starts here } -// Quiescence search function, which is called by the main search -// function with zero depth, or recursively with further decreasing depth per call. -// (~155 Elo) +// Quiescence search function, which is called by the main search function with +// depth zero, or recursively with further decreasing depth. With depth <= 0, we +// "should" be using static eval only, but tactical moves may confuse the static eval. +// To fight this horizon effect, we implement this qsearch of tactical moves (~155 Elo). +// See https://www.chessprogramming.org/Horizon_Effect +// and https://www.chessprogramming.org/Quiescence_Search template -Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { +Value Search::Worker::qsearch(Position& pos, Stack* ss, Value alpha, Value beta) { static_assert(nodeType != Root); constexpr bool PvNode = nodeType == PV; assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE); assert(PvNode || (alpha == beta - 1)); - assert(depth <= 0); - // Check if we have an upcoming move that draws by repetition, or - // if the opponent had an alternative move earlier to this position. - if (alpha < VALUE_DRAW && pos.has_game_cycle(ss->ply)) + // Check if we have an upcoming move that draws by repetition (~1 Elo) + if (alpha < VALUE_DRAW && pos.upcoming_repetition(ss->ply)) { - alpha = value_draw(pos.this_thread()); + alpha = value_draw(this->nodes); if (alpha >= beta) return alpha; } @@ -1402,50 +1429,54 @@ Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { StateInfo st; ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize); - TTEntry* tte; - Key posKey; - Move ttMove, move, bestMove; - Depth ttDepth; - Value bestValue, value, ttValue, futilityValue, futilityBase; - bool pvHit, givesCheck, capture; - int moveCount; - Color us = pos.side_to_move(); + Key posKey; + Move move, bestMove; + Value bestValue, value, futilityBase; + bool pvHit, givesCheck, capture; + int moveCount; + Color us = pos.side_to_move(); // Step 1. Initialize node if (PvNode) { (ss + 1)->pv = pv; - ss->pv[0] = MOVE_NONE; + ss->pv[0] = Move::none(); } - Thread* thisThread = pos.this_thread(); - bestMove = MOVE_NONE; + Worker* thisThread = this; + bestMove = Move::none(); ss->inCheck = pos.checkers(); moveCount = 0; + // Used to send selDepth info to GUI (selDepth counts from 1, ply from 0) + if (PvNode && thisThread->selDepth < ss->ply + 1) + thisThread->selDepth = ss->ply + 1; + // Step 2. Check for an immediate draw or maximum ply reached if (pos.is_draw(ss->ply) || ss->ply >= MAX_PLY) - return (ss->ply >= MAX_PLY && !ss->inCheck) ? evaluate(pos) : VALUE_DRAW; + return (ss->ply >= MAX_PLY && !ss->inCheck) + ? evaluate(networks[numaAccessToken], pos, refreshTable, thisThread->optimism[us]) + : VALUE_DRAW; assert(0 <= ss->ply && ss->ply < MAX_PLY); - // Decide the replacement and cutoff priority of the qsearch TT entries - ttDepth = ss->inCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS; - // Step 3. Transposition table lookup - posKey = pos.key(); - tte = TT.probe(posKey, ss->ttHit); - ttValue = ss->ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE; - ttMove = ss->ttHit ? tte->move() : MOVE_NONE; - pvHit = ss->ttHit && tte->is_pv(); + posKey = pos.key(); + auto [ttHit, ttData, ttWriter] = tt.probe(posKey); + // Need further processing of the saved data + ss->ttHit = ttHit; + ttData.move = ttHit ? ttData.move : Move::none(); + ttData.value = ttHit ? value_from_tt(ttData.value, ss->ply, pos.rule50_count()) : VALUE_NONE; + pvHit = ttHit && ttData.is_pv; // At non-PV nodes we check for an early TT cutoff - if (!PvNode && tte->depth() >= ttDepth - && ttValue != VALUE_NONE // Only in case of TT access race or if !ttHit - && (tte->bound() & (ttValue >= beta ? BOUND_LOWER : BOUND_UPPER))) - return ttValue; + if (!PvNode && ttData.depth >= DEPTH_QS + && ttData.value != VALUE_NONE // Can happen when !ttHit or when access race in probe() + && (ttData.bound & (ttData.value >= beta ? BOUND_LOWER : BOUND_UPPER))) + return ttData.value; // Step 4. Static evaluation of the position + Value unadjustedStaticEval = VALUE_NONE; if (ss->inCheck) bestValue = futilityBase = -VALUE_INFINITE; else @@ -1453,55 +1484,64 @@ Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { if (ss->ttHit) { // Never assume anything about values stored in TT - if ((ss->staticEval = bestValue = tte->eval()) == VALUE_NONE) - ss->staticEval = bestValue = evaluate(pos); + unadjustedStaticEval = ttData.eval; + if (unadjustedStaticEval == VALUE_NONE) + unadjustedStaticEval = + evaluate(networks[numaAccessToken], pos, refreshTable, thisThread->optimism[us]); + ss->staticEval = bestValue = + to_corrected_static_eval(unadjustedStaticEval, *thisThread, pos); // ttValue can be used as a better position evaluation (~13 Elo) - if (ttValue != VALUE_NONE - && (tte->bound() & (ttValue > bestValue ? BOUND_LOWER : BOUND_UPPER))) - bestValue = ttValue; + if (std::abs(ttData.value) < VALUE_TB_WIN_IN_MAX_PLY + && (ttData.bound & (ttData.value > bestValue ? BOUND_LOWER : BOUND_UPPER))) + bestValue = ttData.value; } else - // In case of null move search use previous static eval with a different sign + { + // In case of null move search, use previous static eval with opposite sign + unadjustedStaticEval = + (ss - 1)->currentMove != Move::null() + ? evaluate(networks[numaAccessToken], pos, refreshTable, thisThread->optimism[us]) + : -(ss - 1)->staticEval; ss->staticEval = bestValue = - (ss - 1)->currentMove != MOVE_NULL ? evaluate(pos) : -(ss - 1)->staticEval; + to_corrected_static_eval(unadjustedStaticEval, *thisThread, pos); + } // Stand pat. Return immediately if static value is at least beta if (bestValue >= beta) { + if (std::abs(bestValue) < VALUE_TB_WIN_IN_MAX_PLY) + bestValue = (3 * bestValue + beta) / 4; if (!ss->ttHit) - tte->save(posKey, value_to_tt(bestValue, ss->ply), false, BOUND_LOWER, DEPTH_NONE, - MOVE_NONE, ss->staticEval); - + ttWriter.write(posKey, value_to_tt(bestValue, ss->ply), false, BOUND_LOWER, + DEPTH_UNSEARCHED, Move::none(), unadjustedStaticEval, + tt.generation()); return bestValue; } if (bestValue > alpha) alpha = bestValue; - futilityBase = ss->staticEval + 200; + futilityBase = ss->staticEval + 299; } const PieceToHistory* contHist[] = {(ss - 1)->continuationHistory, (ss - 2)->continuationHistory}; - // Initialize a MovePicker object for the current position, and prepare - // to search the moves. Because the depth is <= 0 here, only captures, - // queen promotions, and other checks (only if depth >= DEPTH_QS_CHECKS) - // will be generated. - Square prevSq = is_ok((ss - 1)->currentMove) ? to_sq((ss - 1)->currentMove) : SQ_NONE; - MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &thisThread->captureHistory, - contHist, &thisThread->pawnHistory, prevSq); + Square prevSq = ((ss - 1)->currentMove).is_ok() ? ((ss - 1)->currentMove).to_sq() : SQ_NONE; - int quietCheckEvasions = 0; + // Initialize a MovePicker object for the current position, and prepare to search + // the moves. We presently use two stages of move generator in quiescence search: + // captures, or evasions only when in check. + MovePicker mp(pos, ttData.move, DEPTH_QS, &thisThread->mainHistory, &thisThread->captureHistory, + contHist, &thisThread->pawnHistory); - // Step 5. Loop through all pseudo-legal moves until no moves remain - // or a beta cutoff occurs. - while ((move = mp.next_move()) != MOVE_NONE) + // Step 5. Loop through all pseudo-legal moves until no moves remain or a beta + // cutoff occurs. + while ((move = mp.next_move()) != Move::none()) { - assert(is_ok(move)); + assert(move.is_ok()); - // Check for legality if (!pos.legal(move)) continue; @@ -1514,32 +1554,32 @@ Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { if (bestValue > VALUE_TB_LOSS_IN_MAX_PLY && pos.non_pawn_material(us)) { // Futility pruning and moveCount pruning (~10 Elo) - if (!givesCheck && to_sq(move) != prevSq && futilityBase > VALUE_TB_LOSS_IN_MAX_PLY - && type_of(move) != PROMOTION) + if (!givesCheck && move.to_sq() != prevSq && futilityBase > VALUE_TB_LOSS_IN_MAX_PLY + && move.type_of() != PROMOTION) { if (moveCount > 2) continue; - futilityValue = futilityBase + PieceValue[pos.piece_on(to_sq(move))]; + Value futilityValue = futilityBase + PieceValue[pos.piece_on(move.to_sq())]; - // If static eval + value of piece we are going to capture is much lower - // than alpha we can prune this move. + // If static eval + value of piece we are going to capture is + // much lower than alpha, we can prune this move. (~2 Elo) if (futilityValue <= alpha) { bestValue = std::max(bestValue, futilityValue); continue; } - // If static eval is much lower than alpha and move is not winning material - // we can prune this move. - if (futilityBase <= alpha && !pos.see_ge(move, VALUE_ZERO + 1)) + // If static eval is much lower than alpha and move is + // not winning material, we can prune this move. (~2 Elo) + if (futilityBase <= alpha && !pos.see_ge(move, 1)) { bestValue = std::max(bestValue, futilityBase); continue; } - // If static exchange evaluation is much worse than what is needed to not - // fall below alpha we can prune this move. + // If static exchange evaluation is much worse than what + // is needed to not fall below alpha, we can prune this move. if (futilityBase > alpha && !pos.see_ge(move, (alpha - futilityBase) * 4)) { bestValue = alpha; @@ -1547,36 +1587,33 @@ Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { } } - // We prune after the second quiet check evasion move, where being 'in check' is - // implicitly checked through the counter, and being a 'quiet move' apart from - // being a tt move is assumed after an increment because captures are pushed ahead. - if (quietCheckEvasions > 1) - break; - // Continuation history based pruning (~3 Elo) - if (!capture && (*contHist[0])[pos.moved_piece(move)][to_sq(move)] < 0 - && (*contHist[1])[pos.moved_piece(move)][to_sq(move)] < 0) + if (!capture + && (*contHist[0])[pos.moved_piece(move)][move.to_sq()] + + (*contHist[1])[pos.moved_piece(move)][move.to_sq()] + + thisThread->pawnHistory[pawn_structure_index(pos)][pos.moved_piece(move)] + [move.to_sq()] + <= 4643) continue; // Do not search moves with bad enough SEE values (~5 Elo) - if (!pos.see_ge(move, Value(-90))) + if (!pos.see_ge(move, -83)) continue; } // Speculative prefetch as early as possible - prefetch(TT.first_entry(pos.key_after(move))); + prefetch(tt.first_entry(pos.key_after(move))); // Update the current move ss->currentMove = move; ss->continuationHistory = &thisThread - ->continuationHistory[ss->inCheck][capture][pos.moved_piece(move)][to_sq(move)]; - - quietCheckEvasions += !capture && ss->inCheck; + ->continuationHistory[ss->inCheck][capture][pos.moved_piece(move)][move.to_sq()]; // Step 7. Make and search the move + thisThread->nodes.fetch_add(1, std::memory_order_relaxed); pos.do_move(move, st, givesCheck); - value = -qsearch(pos, ss + 1, -beta, -alpha, depth - 1); + value = -qsearch(pos, ss + 1, -beta, -alpha); pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); @@ -1602,58 +1639,93 @@ Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { } // Step 9. Check for mate - // All legal moves have been searched. A special case: if we're in check - // and no legal moves were found, it is checkmate. + // All legal moves have been searched. A special case: if we are + // in check and no legal moves were found, it is checkmate. if (ss->inCheck && bestValue == -VALUE_INFINITE) { assert(!MoveList(pos).size()); - return mated_in(ss->ply); // Plies to mate from the root } - // Save gathered info in transposition table - tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit, - bestValue >= beta ? BOUND_LOWER : BOUND_UPPER, ttDepth, bestMove, ss->staticEval); + if (std::abs(bestValue) < VALUE_TB_WIN_IN_MAX_PLY && bestValue >= beta) + bestValue = (3 * bestValue + beta) / 4; + + // Save gathered info in transposition table. The static evaluation + // is saved as it was before adjustment by correction history. + ttWriter.write(posKey, value_to_tt(bestValue, ss->ply), pvHit, + bestValue >= beta ? BOUND_LOWER : BOUND_UPPER, DEPTH_QS, bestMove, + unadjustedStaticEval, tt.generation()); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); return bestValue; } +Depth Search::Worker::reduction(bool i, Depth d, int mn, int delta) const { + int reductionScale = reductions[d] * reductions[mn]; + return (reductionScale + 1274 - delta * 746 / rootDelta) / 1024 + (!i && reductionScale > 1293); +} + +// elapsed() returns the time elapsed since the search started. If the +// 'nodestime' option is enabled, it will return the count of nodes searched +// instead. This function is called to check whether the search should be +// stopped based on predefined thresholds like time limits or nodes searched. +// +// elapsed_time() returns the actual time elapsed since the start of the search. +// This function is intended for use only when printing PV outputs, and not used +// for making decisions within the search algorithm itself. +TimePoint Search::Worker::elapsed() const { + return main_manager()->tm.elapsed([this]() { return threads.nodes_searched(); }); +} + +TimePoint Search::Worker::elapsed_time() const { return main_manager()->tm.elapsed_time(); } -// Adjusts a mate or TB score from "plies to mate from the root" -// to "plies to mate from the current position". Standard scores are unchanged. + +namespace { +// Adjusts a mate or TB score from "plies to mate from the root" to +// "plies to mate from the current position". Standard scores are unchanged. // The function is called before storing a value in the transposition table. Value value_to_tt(Value v, int ply) { assert(v != VALUE_NONE); - return v >= VALUE_TB_WIN_IN_MAX_PLY ? v + ply : v <= VALUE_TB_LOSS_IN_MAX_PLY ? v - ply : v; } -// Inverse of value_to_tt(): it adjusts a mate or TB score -// from the transposition table (which refers to the plies to mate/be mated from -// current position) to "plies to mate/be mated (TB win/loss) from the root". -// However, to avoid potentially false mate scores related to the 50 moves rule -// and the graph history interaction problem, we return an optimal TB score instead. +// Inverse of value_to_tt(): it adjusts a mate or TB score from the transposition +// table (which refers to the plies to mate/be mated from current position) to +// "plies to mate/be mated (TB win/loss) from the root". However, to avoid +// potentially false mate or TB scores related to the 50 moves rule and the +// graph history interaction, we return the highest non-TB score instead. Value value_from_tt(Value v, int ply, int r50c) { if (v == VALUE_NONE) return VALUE_NONE; - if (v >= VALUE_TB_WIN_IN_MAX_PLY) // TB win or better + // handle TB win or better + if (v >= VALUE_TB_WIN_IN_MAX_PLY) { - if (v >= VALUE_MATE_IN_MAX_PLY && VALUE_MATE - v > 99 - r50c) - return VALUE_MATE_IN_MAX_PLY - 1; // do not return a potentially false mate score + // Downgrade a potentially false mate score + if (v >= VALUE_MATE_IN_MAX_PLY && VALUE_MATE - v > 100 - r50c) + return VALUE_TB_WIN_IN_MAX_PLY - 1; + + // Downgrade a potentially false TB score. + if (VALUE_TB - v > 100 - r50c) + return VALUE_TB_WIN_IN_MAX_PLY - 1; return v - ply; } - if (v <= VALUE_TB_LOSS_IN_MAX_PLY) // TB loss or worse + // handle TB loss or worse + if (v <= VALUE_TB_LOSS_IN_MAX_PLY) { - if (v <= VALUE_MATED_IN_MAX_PLY && VALUE_MATE + v > 99 - r50c) - return VALUE_MATED_IN_MAX_PLY + 1; // do not return a potentially false mate score + // Downgrade a potentially false mate score. + if (v <= VALUE_MATED_IN_MAX_PLY && VALUE_MATE + v > 100 - r50c) + return VALUE_TB_LOSS_IN_MAX_PLY + 1; + + // Downgrade a potentially false TB score. + if (VALUE_TB + v > 100 - r50c) + return VALUE_TB_LOSS_IN_MAX_PLY + 1; return v + ply; } @@ -1665,131 +1737,99 @@ Value value_from_tt(Value v, int ply, int r50c) { // Adds current move and appends child pv[] void update_pv(Move* pv, Move move, const Move* childPv) { - for (*pv++ = move; childPv && *childPv != MOVE_NONE;) + for (*pv++ = move; childPv && *childPv != Move::none();) *pv++ = *childPv++; - *pv = MOVE_NONE; + *pv = Move::none(); } // Updates stats at the end of search() when a bestMove is found -void update_all_stats(const Position& pos, - Stack* ss, - Move bestMove, - Value bestValue, - Value beta, - Square prevSq, - Move* quietsSearched, - int quietCount, - Move* capturesSearched, - int captureCount, - Depth depth) { - - Color us = pos.side_to_move(); - Thread* thisThread = pos.this_thread(); - CapturePieceToHistory& captureHistory = thisThread->captureHistory; +void update_all_stats(const Position& pos, + Stack* ss, + Search::Worker& workerThread, + Move bestMove, + Square prevSq, + ValueList& quietsSearched, + ValueList& capturesSearched, + Depth depth) { + + CapturePieceToHistory& captureHistory = workerThread.captureHistory; Piece moved_piece = pos.moved_piece(bestMove); PieceType captured; - int quietMoveBonus = stat_bonus(depth + 1); - int quietMoveMalus = stat_malus(depth + 1); + int quietMoveBonus = stat_bonus(depth); + int quietMoveMalus = stat_malus(depth); if (!pos.capture_stage(bestMove)) { - int bestMoveBonus = bestValue > beta + 168 ? quietMoveBonus // larger bonus - : stat_bonus(depth); // smaller bonus - - // Increase stats for the best move in case it was a quiet move - update_quiet_stats(pos, ss, bestMove, bestMoveBonus); - thisThread->pawnHistory[pawn_structure(pos)][moved_piece][to_sq(bestMove)] - << quietMoveBonus; - - int moveMalus = bestValue > beta + 168 ? quietMoveMalus // larger malus - : stat_malus(depth); // smaller malus + update_quiet_histories(pos, ss, workerThread, bestMove, quietMoveBonus); // Decrease stats for all non-best quiet moves - for (int i = 0; i < quietCount; ++i) - { - thisThread->pawnHistory[pawn_structure(pos)][pos.moved_piece(quietsSearched[i])] - [to_sq(quietsSearched[i])] - << -moveMalus; - thisThread->mainHistory[us][from_to(quietsSearched[i])] << -moveMalus; - update_continuation_histories(ss, pos.moved_piece(quietsSearched[i]), - to_sq(quietsSearched[i]), -moveMalus); - } + for (Move move : quietsSearched) + update_quiet_histories(pos, ss, workerThread, move, -quietMoveMalus); } else { // Increase stats for the best move in case it was a capture move - captured = type_of(pos.piece_on(to_sq(bestMove))); - captureHistory[moved_piece][to_sq(bestMove)][captured] << quietMoveBonus; + captured = type_of(pos.piece_on(bestMove.to_sq())); + captureHistory[moved_piece][bestMove.to_sq()][captured] << quietMoveBonus; } - // Extra penalty for a quiet early move that was not a TT move or - // main killer move in previous ply when it gets refuted. - if (prevSq != SQ_NONE - && ((ss - 1)->moveCount == 1 + (ss - 1)->ttHit - || ((ss - 1)->currentMove == (ss - 1)->killers[0])) - && !pos.captured_piece()) + // Extra penalty for a quiet early move that was not a TT move in + // previous ply when it gets refuted. + if (prevSq != SQ_NONE && ((ss - 1)->moveCount == 1 + (ss - 1)->ttHit) && !pos.captured_piece()) update_continuation_histories(ss - 1, pos.piece_on(prevSq), prevSq, -quietMoveMalus); // Decrease stats for all non-best capture moves - for (int i = 0; i < captureCount; ++i) + for (Move move : capturesSearched) { - moved_piece = pos.moved_piece(capturesSearched[i]); - captured = type_of(pos.piece_on(to_sq(capturesSearched[i]))); - captureHistory[moved_piece][to_sq(capturesSearched[i])][captured] << -quietMoveMalus; + moved_piece = pos.moved_piece(move); + captured = type_of(pos.piece_on(move.to_sq())); + captureHistory[moved_piece][move.to_sq()][captured] << -quietMoveMalus; } } -// Updates histories of the move pairs formed -// by moves at ply -1, -2, -3, -4, and -6 with current move. +// Updates histories of the move pairs formed by moves +// at ply -1, -2, -3, -4, and -6 with current move. void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus) { + bonus = bonus * 52 / 64; + for (int i : {1, 2, 3, 4, 6}) { // Only update the first 2 continuation histories if we are in check if (ss->inCheck && i > 2) break; - if (is_ok((ss - i)->currentMove)) - (*(ss - i)->continuationHistory)[pc][to] << bonus / (1 + 3 * (i == 3)); + if (((ss - i)->currentMove).is_ok()) + (*(ss - i)->continuationHistory)[pc][to] << bonus / (1 + (i == 3)); } } - // Updates move sorting heuristics -void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus) { - // Update killers - if (ss->killers[0] != move) - { - ss->killers[1] = ss->killers[0]; - ss->killers[0] = move; - } +void update_quiet_histories( + const Position& pos, Stack* ss, Search::Worker& workerThread, Move move, int bonus) { - Color us = pos.side_to_move(); - Thread* thisThread = pos.this_thread(); - thisThread->mainHistory[us][from_to(move)] << bonus; - update_continuation_histories(ss, pos.moved_piece(move), to_sq(move), bonus); + Color us = pos.side_to_move(); + workerThread.mainHistory[us][move.from_to()] << bonus; - // Update countermove history - if (is_ok((ss - 1)->currentMove)) - { - Square prevSq = to_sq((ss - 1)->currentMove); - thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] = move; - } + update_continuation_histories(ss, pos.moved_piece(move), move.to_sq(), bonus); + + int pIndex = pawn_structure_index(pos); + workerThread.pawnHistory[pIndex][pos.moved_piece(move)][move.to_sq()] << bonus / 2; } -// When playing with strength handicap, choose the best move among a set of RootMoves -// using a statistical rule dependent on 'level'. Idea by Heinz van Saanen. -Move Skill::pick_best(size_t multiPV) { +} - const RootMoves& rootMoves = Threads.main()->rootMoves; - static PRNG rng(now()); // PRNG sequence should be non-deterministic +// When playing with strength handicap, choose the best move among a set of +// RootMoves using a statistical rule dependent on 'level'. Idea by Heinz van Saanen. +Move Skill::pick_best(const RootMoves& rootMoves, size_t multiPV) { + static PRNG rng(now()); // PRNG sequence should be non-deterministic // RootMoves are already sorted by score in descending order Value topScore = rootMoves[0].score; - int delta = std::min(topScore - rootMoves[multiPV - 1].score, PawnValue); + int delta = std::min(topScore - rootMoves[multiPV - 1].score, int(PawnValue)); int maxScore = -VALUE_INFINITE; double weakness = 120 - 2 * level; @@ -1799,9 +1839,9 @@ Move Skill::pick_best(size_t multiPV) { for (size_t i = 0; i < multiPV; ++i) { // This is our magic formula - int push = int((weakness * int(topScore - rootMoves[i].score) - + delta * (rng.rand() % int(weakness))) - / 128); + int push = (weakness * int(topScore - rootMoves[i].score) + + delta * (rng.rand() % int(weakness))) + / 128; if (rootMoves[i].score + push >= maxScore) { @@ -1813,23 +1853,20 @@ Move Skill::pick_best(size_t multiPV) { return best; } -} // namespace - - -// Used to print debug info and, more importantly, -// to detect when we are out of available time and thus stop the search. -void MainThread::check_time() { +// Used to print debug info and, more importantly, to detect +// when we are out of available time and thus stop the search. +void SearchManager::check_time(Search::Worker& worker) { if (--callsCnt > 0) return; // When using nodes, ensure checking rate is not lower than 0.1% of nodes - callsCnt = Limits.nodes ? std::min(512, int(Limits.nodes / 1024)) : 512; + callsCnt = worker.limits.nodes ? std::min(512, int(worker.limits.nodes / 1024)) : 512; static TimePoint lastInfoTime = now(); - TimePoint elapsed = Time.elapsed(); - TimePoint tick = Limits.startTime + elapsed; + TimePoint elapsed = tm.elapsed([&worker]() { return worker.threads.nodes_searched(); }); + TimePoint tick = worker.limits.startTime + elapsed; if (tick - lastInfoTime >= 1000) { @@ -1841,24 +1878,162 @@ void MainThread::check_time() { if (ponder) return; - if ((Limits.use_time_management() && (elapsed > Time.maximum() || stopOnPonderhit)) - || (Limits.movetime && elapsed >= Limits.movetime) - || (Limits.nodes && Threads.nodes_searched() >= uint64_t(Limits.nodes))) - Threads.stop = true; + if ( + // Later we rely on the fact that we can at least use the mainthread previous + // root-search score and PV in a multithreaded environment to prove mated-in scores. + worker.completedDepth >= 1 + && ((worker.limits.use_time_management() && (elapsed > tm.maximum() || stopOnPonderhit)) + || (worker.limits.movetime && elapsed >= worker.limits.movetime) + || (worker.limits.nodes && worker.threads.nodes_searched() >= worker.limits.nodes))) + worker.threads.stop = worker.threads.abortedSearch = true; } +// Used to correct and extend PVs for moves that have a TB (but not a mate) score. +// Keeps the search based PV for as long as it is verified to maintain the game +// outcome, truncates afterwards. Finally, extends to mate the PV, providing a +// possible continuation (but not a proven mating line). +void syzygy_extend_pv(const OptionsMap& options, + const Search::LimitsType& limits, + Position& pos, + RootMove& rootMove, + Value& v) { + + auto t_start = std::chrono::steady_clock::now(); + int moveOverhead = int(options["Move Overhead"]); + + // Do not use more than moveOverhead / 2 time, if time management is active + auto time_abort = [&t_start, &moveOverhead, &limits]() -> bool { + auto t_end = std::chrono::steady_clock::now(); + return limits.use_time_management() + && 2 * std::chrono::duration(t_end - t_start).count() + > moveOverhead; + }; + + std::list sts; + + // Step 0, do the rootMove, no correction allowed, as needed for MultiPV in TB. + auto& stRoot = sts.emplace_back(); + pos.do_move(rootMove.pv[0], stRoot); + int ply = 1; + + // Step 1, walk the PV to the last position in TB with correct decisive score + while (size_t(ply) < rootMove.pv.size()) + { + Move& pvMove = rootMove.pv[ply]; + + RootMoves legalMoves; + for (const auto& m : MoveList(pos)) + legalMoves.emplace_back(m); + + Tablebases::Config config = Tablebases::rank_root_moves(options, pos, legalMoves); + RootMove& rm = *std::find(legalMoves.begin(), legalMoves.end(), pvMove); + + if (legalMoves[0].tbRank != rm.tbRank) + break; + + ply++; + + auto& st = sts.emplace_back(); + pos.do_move(pvMove, st); + + // Do not allow for repetitions or drawing moves along the PV in TB regime + if (config.rootInTB && pos.is_draw(ply)) + { + pos.undo_move(pvMove); + ply--; + break; + } + + // Full PV shown will thus be validated and end in TB. + // If we cannot validate the full PV in time, we do not show it. + if (config.rootInTB && time_abort()) + break; + } + + // Resize the PV to the correct part + rootMove.pv.resize(ply); + + // Step 2, now extend the PV to mate, as if the user explored syzygy-tables.info + // using top ranked moves (minimal DTZ), which gives optimal mates only for simple + // endgames e.g. KRvK. + while (!pos.is_draw(0)) + { + if (time_abort()) + break; + + RootMoves legalMoves; + for (const auto& m : MoveList(pos)) + { + auto& rm = legalMoves.emplace_back(m); + StateInfo tmpSI; + pos.do_move(m, tmpSI); + // Give a score of each move to break DTZ ties restricting opponent mobility, + // but not giving the opponent a capture. + for (const auto& mOpp : MoveList(pos)) + rm.tbRank -= pos.capture(mOpp) ? 100 : 1; + pos.undo_move(m); + } + + // Mate found + if (legalMoves.size() == 0) + break; + + // Sort moves according to their above assigned rank. + // This will break ties for moves with equal DTZ in rank_root_moves. + std::stable_sort( + legalMoves.begin(), legalMoves.end(), + [](const Search::RootMove& a, const Search::RootMove& b) { return a.tbRank > b.tbRank; }); + + // The winning side tries to minimize DTZ, the losing side maximizes it + Tablebases::Config config = Tablebases::rank_root_moves(options, pos, legalMoves, true); + + // If DTZ is not available we might not find a mate, so we bail out + if (!config.rootInTB || config.cardinality > 0) + break; + + ply++; + + Move& pvMove = legalMoves[0].pv[0]; + rootMove.pv.push_back(pvMove); + auto& st = sts.emplace_back(); + pos.do_move(pvMove, st); + } + + // Finding a draw in this function is an exceptional case, that cannot happen + // during engine game play, since we have a winning score, and play correctly + // with TB support. However, it can be that a position is draw due to the 50 move + // rule if it has been been reached on the board with a non-optimal 50 move counter + // (e.g. 8/8/6k1/3B4/3K4/4N3/8/8 w - - 54 106 ) which TB with dtz counter rounding + // cannot always correctly rank. See also + // https://github.com/official-stockfish/Stockfish/issues/5175#issuecomment-2058893495 + // We adjust the score to match the found PV. Note that a TB loss score can be + // displayed if the engine did not find a drawing move yet, but eventually search + // will figure it out (e.g. 1kq5/q2r4/5K2/8/8/8/8/7Q w - - 96 1 ) + if (pos.is_draw(0)) + v = VALUE_DRAW; + + // Undo the PV moves + for (auto it = rootMove.pv.rbegin(); it != rootMove.pv.rend(); ++it) + pos.undo_move(*it); + + // Inform if we couldn't get a full extension in time + if (time_abort()) + sync_cout + << "info string Syzygy based PV extension requires more time, increase Move Overhead as needed." + << sync_endl; +} -// Formats PV information according to the UCI protocol. UCI requires -// that all (if any) unsearched PV lines are sent using a previous search score. -string UCI::pv(const Position& pos, Depth depth) { +void SearchManager::pv(Search::Worker& worker, + const ThreadPool& threads, + const TranspositionTable& tt, + Depth depth) { - std::stringstream ss; - TimePoint elapsed = Time.elapsed() + 1; - const RootMoves& rootMoves = pos.this_thread()->rootMoves; - size_t pvIdx = pos.this_thread()->pvIdx; - size_t multiPV = std::min(size_t(Options["MultiPV"]), rootMoves.size()); - uint64_t nodesSearched = Threads.nodes_searched(); - uint64_t tbHits = Threads.tb_hits() + (TB::RootInTB ? rootMoves.size() : 0); + const auto nodes = threads.nodes_searched(); + auto& rootMoves = worker.rootMoves; + auto& pos = worker.rootPos; + size_t pvIdx = worker.pvIdx; + size_t multiPV = std::min(size_t(worker.options["MultiPV"]), rootMoves.size()); + uint64_t tbHits = threads.tb_hits() + (worker.tbConfig.rootInTB ? rootMoves.size() : 0); for (size_t i = 0; i < multiPV; ++i) { @@ -1873,110 +2048,77 @@ string UCI::pv(const Position& pos, Depth depth) { if (v == -VALUE_INFINITE) v = VALUE_ZERO; - bool tb = TB::RootInTB && abs(v) < VALUE_MATE_IN_MAX_PLY; + bool tb = worker.tbConfig.rootInTB && std::abs(v) <= VALUE_TB; v = tb ? rootMoves[i].tbScore : v; - if (ss.rdbuf()->in_avail()) // Not at first line - ss << "\n"; + bool isExact = i != pvIdx || tb || !updated; // tablebase- and previous-scores are exact - ss << "info" - << " depth " << d << " seldepth " << rootMoves[i].selDepth << " multipv " << i + 1 - << " score " << UCI::value(v); + // Potentially correct and extend the PV, and in exceptional cases v + if (std::abs(v) >= VALUE_TB_WIN_IN_MAX_PLY && std::abs(v) < VALUE_MATE_IN_MAX_PLY + && ((!rootMoves[i].scoreLowerbound && !rootMoves[i].scoreUpperbound) || isExact)) + syzygy_extend_pv(worker.options, worker.limits, pos, rootMoves[i], v); - if (Options["UCI_ShowWDL"]) - ss << UCI::wdl(v, pos.game_ply()); + std::string pv; + for (Move m : rootMoves[i].pv) + pv += UCIEngine::move(m, pos.is_chess960()) + " "; - if (i == pvIdx && !tb && updated) // tablebase- and previous-scores are exact - ss << (rootMoves[i].scoreLowerbound - ? " lowerbound" - : (rootMoves[i].scoreUpperbound ? " upperbound" : "")); + // Remove last whitespace + if (!pv.empty()) + pv.pop_back(); - ss << " nodes " << nodesSearched << " nps " << nodesSearched * 1000 / elapsed - << " hashfull " << TT.hashfull() << " tbhits " << tbHits << " time " << elapsed << " pv"; + auto wdl = worker.options["UCI_ShowWDL"] ? UCIEngine::wdl(v, pos) : ""; + auto bound = rootMoves[i].scoreLowerbound + ? "lowerbound" + : (rootMoves[i].scoreUpperbound ? "upperbound" : ""); - for (Move m : rootMoves[i].pv) - ss << " " << UCI::move(m, pos.is_chess960()); - } + InfoFull info; - return ss.str(); -} + info.depth = d; + info.selDepth = rootMoves[i].selDepth; + info.multiPV = i + 1; + info.score = {v, pos}; + info.wdl = wdl; + if (!isExact) + info.bound = bound; -// Called in case we have no ponder move -// before exiting the search, for instance, in case we stop the search during a -// fail high at root. We try hard to have a ponder move to return to the GUI, + TimePoint time = tm.elapsed_time() + 1; + info.timeMs = time; + info.nodes = nodes; + info.nps = nodes * 1000 / time; + info.tbHits = tbHits; + info.pv = pv; + info.hashfull = tt.hashfull(); + + updates.onUpdateFull(info); + } +} + +// Called in case we have no ponder move before exiting the search, +// for instance, in case we stop the search during a fail high at root. +// We try hard to have a ponder move to return to the GUI, // otherwise in case of 'ponder on' we have nothing to think about. -bool RootMove::extract_ponder_from_tt(Position& pos) { +bool RootMove::extract_ponder_from_tt(const TranspositionTable& tt, Position& pos) { StateInfo st; ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize); - bool ttHit; - assert(pv.size() == 1); - - if (pv[0] == MOVE_NONE) + if (pv[0] == Move::none()) return false; pos.do_move(pv[0], st); - TTEntry* tte = TT.probe(pos.key(), ttHit); + auto [ttHit, ttData, ttWriter] = tt.probe(pos.key()); if (ttHit) { - Move m = tte->move(); // Local copy to be SMP safe - if (MoveList(pos).contains(m)) - pv.push_back(m); + if (MoveList(pos).contains(ttData.move)) + pv.push_back(ttData.move); } pos.undo_move(pv[0]); return pv.size() > 1; } -void Tablebases::rank_root_moves(Position& pos, Search::RootMoves& rootMoves) { - - RootInTB = false; - UseRule50 = bool(Options["Syzygy50MoveRule"]); - ProbeDepth = int(Options["SyzygyProbeDepth"]); - Cardinality = int(Options["SyzygyProbeLimit"]); - bool dtz_available = true; - - // Tables with fewer pieces than SyzygyProbeLimit are searched with - // ProbeDepth == DEPTH_ZERO - if (Cardinality > MaxCardinality) - { - Cardinality = MaxCardinality; - ProbeDepth = 0; - } - - if (Cardinality >= popcount(pos.pieces()) && !pos.can_castle(ANY_CASTLING)) - { - // Rank moves using DTZ tables - RootInTB = root_probe(pos, rootMoves); - - if (!RootInTB) - { - // DTZ tables are missing; try to rank moves using WDL tables - dtz_available = false; - RootInTB = root_probe_wdl(pos, rootMoves); - } - } - - if (RootInTB) - { - // Sort moves according to TB rank - std::stable_sort(rootMoves.begin(), rootMoves.end(), - [](const RootMove& a, const RootMove& b) { return a.tbRank > b.tbRank; }); - - // Probe during search only if DTZ is not available and we are winning - if (dtz_available || rootMoves[0].tbScore <= VALUE_DRAW) - Cardinality = 0; - } - else - { - // Clean up if root_probe() and root_probe_wdl() have failed - for (auto& m : rootMoves) - m.tbRank = 0; - } -} } // namespace Stockfish