X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;ds=sidebyside;f=src%2Fsearch.h;h=801baacc7f1cccfb8ed0852cab3d250ea6ca4e83;hb=HEAD;hp=1274b9681958fce4d2cbf53b6695c33505c1ab67;hpb=9afa1d73306cb98e95acec5daf4efd65e592ceff;p=stockfish diff --git a/src/search.h b/src/search.h index 1274b968..c9fe9e18 100644 --- a/src/search.h +++ b/src/search.h @@ -1,8 +1,6 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 - Copyright (C) 2004-2008 Tord Romstad (Glaurung author) - Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad - Copyright (C) 2015-2018 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad + 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 @@ -21,86 +19,333 @@ #ifndef SEARCH_H_INCLUDED #define SEARCH_H_INCLUDED +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include #include #include "misc.h" #include "movepick.h" +#include "nnue/network.h" +#include "nnue/nnue_accumulator.h" +#include "numa.h" +#include "position.h" +#include "score.h" +#include "syzygy/tbprobe.h" +#include "timeman.h" #include "types.h" -class Position; +namespace Stockfish { + +// Different node types, used as a template parameter +enum NodeType { + NonPV, + PV, + Root +}; + +class TranspositionTable; +class ThreadPool; +class OptionsMap; namespace Search { -/// Threshold used for countermoves based pruning -const int CounterMovePruneThreshold = 0; +// Stack struct keeps track of the information we need to remember from nodes +// shallower and deeper in the tree during the search. Each search thread has +// its own array of Stack objects, indexed by the current ply. +struct Stack { + Move* pv; + PieceToHistory* continuationHistory; + int ply; + Move currentMove; + Move excludedMove; + Value staticEval; + int statScore; + int moveCount; + bool inCheck; + bool ttPv; + bool ttHit; + int cutoffCnt; +}; + +// RootMove struct is used for moves at the root of the tree. For each root move +// we store a score and a PV (really a refutation in the case of moves which +// fail low). Score is normally set at -VALUE_INFINITE for all non-pv moves. +struct RootMove { -/// Stack struct keeps track of the information we need to remember from nodes -/// shallower and deeper in the tree during the search. Each search thread has -/// its own array of Stack objects, indexed by the current ply. + explicit RootMove(Move m) : + pv(1, m) {} + bool extract_ponder_from_tt(const TranspositionTable& tt, Position& pos); + bool operator==(const Move& m) const { return pv[0] == m; } + // Sort in descending order + bool operator<(const RootMove& m) const { + return m.score != score ? m.score < score : m.previousScore < previousScore; + } -struct Stack { - Move* pv; - PieceToHistory* contHistory; - int ply; - Move currentMove; - Move excludedMove; - Move killers[2]; - Value staticEval; - int statScore; - int moveCount; + uint64_t effort = 0; + Value score = -VALUE_INFINITE; + Value previousScore = -VALUE_INFINITE; + Value averageScore = -VALUE_INFINITE; + Value uciScore = -VALUE_INFINITE; + bool scoreLowerbound = false; + bool scoreUpperbound = false; + int selDepth = 0; + int tbRank = 0; + Value tbScore; + std::vector pv; }; +using RootMoves = std::vector; -/// RootMove struct is used for moves at the root of the tree. For each root move -/// we store a score and a PV (really a refutation in the case of moves which -/// fail low). Score is normally set at -VALUE_INFINITE for all non-pv moves. -struct RootMove { +// LimitsType struct stores information sent by the caller about the analysis required. +struct LimitsType { + + // Init explicitly due to broken value-initialization of non POD in MSVC + LimitsType() { + time[WHITE] = time[BLACK] = inc[WHITE] = inc[BLACK] = npmsec = movetime = TimePoint(0); + movestogo = depth = mate = perft = infinite = 0; + nodes = 0; + ponderMode = false; + } + + bool use_time_management() const { return time[WHITE] || time[BLACK]; } - explicit RootMove(Move m) : pv(1, m) {} - bool extract_ponder_from_tt(Position& pos); - bool operator==(const Move& m) const { return pv[0] == m; } - bool operator<(const RootMove& m) const { // Sort in descending order - return m.score != score ? m.score < score - : m.previousScore < previousScore; - } - - Value score = -VALUE_INFINITE; - Value previousScore = -VALUE_INFINITE; - int selDepth = 0; - std::vector pv; + std::vector searchmoves; + TimePoint time[COLOR_NB], inc[COLOR_NB], npmsec, movetime, startTime; + int movestogo, depth, mate, perft, infinite; + uint64_t nodes; + bool ponderMode; + Square capSq; }; -typedef std::vector RootMoves; +// The UCI stores the uci options, thread pool, and transposition table. +// This struct is used to easily forward data to the Search::Worker class. +struct SharedState { + SharedState(const OptionsMap& optionsMap, + ThreadPool& threadPool, + TranspositionTable& transpositionTable, + const LazyNumaReplicated& nets) : + options(optionsMap), + threads(threadPool), + tt(transpositionTable), + networks(nets) {} -/// LimitsType struct stores information sent by GUI about available time to -/// search the current move, maximum depth/time, or if we are in analysis mode. + const OptionsMap& options; + ThreadPool& threads; + TranspositionTable& tt; + const LazyNumaReplicated& networks; +}; -struct LimitsType { +class Worker; + +// Null Object Pattern, implement a common interface for the SearchManagers. +// A Null Object will be given to non-mainthread workers. +class ISearchManager { + public: + virtual ~ISearchManager() {} + virtual void check_time(Search::Worker&) = 0; +}; + +struct InfoShort { + int depth; + Score score; +}; + +struct InfoFull: InfoShort { + int selDepth; + size_t multiPV; + std::string_view wdl; + std::string_view bound; + size_t timeMs; + size_t nodes; + size_t nps; + size_t tbHits; + std::string_view pv; + int hashfull; +}; + +struct InfoIteration { + int depth; + std::string_view currmove; + size_t currmovenumber; +}; + +// 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 { + // Lowest and highest Elo ratings used in the skill level calculation + constexpr static int LowestElo = 1320; + constexpr static int HighestElo = 3190; + + Skill(int skill_level, int uci_elo) { + if (uci_elo) + { + double e = double(uci_elo - LowestElo) / (HighestElo - LowestElo); + 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(const RootMoves&, size_t multiPV); + + double level; + Move best = Move::none(); +}; + +// SearchManager manages the search from the main thread. It is responsible for +// keeping track of the time, and storing data strictly related to the main thread. +class SearchManager: public ISearchManager { + public: + using UpdateShort = std::function; + using UpdateFull = std::function; + using UpdateIter = std::function; + using UpdateBestmove = std::function; + + struct UpdateContext { + UpdateShort onUpdateNoMoves; + UpdateFull onUpdateFull; + UpdateIter onIter; + UpdateBestmove onBestmove; + }; + + + SearchManager(const UpdateContext& updateContext) : + updates(updateContext) {} + + void check_time(Search::Worker& worker) override; + + void pv(Search::Worker& worker, + const ThreadPool& threads, + const TranspositionTable& tt, + Depth depth); + + Stockfish::TimeManagement tm; + double originalTimeAdjust; + int callsCnt; + std::atomic_bool ponder; + + std::array iterValue; + double previousTimeReduction; + Value bestPreviousScore; + Value bestPreviousAverageScore; + bool stopOnPonderhit; + + size_t id; + + const UpdateContext& updates; +}; + +class NullSearchManager: public ISearchManager { + public: + void check_time(Search::Worker&) override {} +}; + + +// Search::Worker is the class that does the actual search. +// It is instantiated once per thread, and it is responsible for keeping track +// of the search history, and storing data required for the search. +class Worker { + public: + Worker(SharedState&, std::unique_ptr, size_t, NumaReplicatedAccessToken); + + // Called at instantiation to initialize reductions tables. + // Reset histories, usually before a new game. + void clear(); + + // Called when the program receives the UCI 'go' command. + // It searches from the root position and outputs the "bestmove". + void start_searching(); + + bool is_mainthread() const { return threadIdx == 0; } + + void ensure_network_replicated(); + + // Public because they need to be updatable by the stats + ButterflyHistory mainHistory; + CapturePieceToHistory captureHistory; + ContinuationHistory continuationHistory[2][2]; + PawnHistory pawnHistory; + PawnCorrectionHistory pawnCorrectionHistory; + MaterialCorrectionHistory materialCorrectionHistory; + + private: + void iterative_deepening(); + + // This is the 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); + + // Quiescence search function, which is called by the main search + template + Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta); + + Depth reduction(bool i, Depth d, int mn, int delta) const; + + // Pointer to the search manager, only allowed to be called by the main thread + SearchManager* main_manager() const { + assert(threadIdx == 0); + return static_cast(manager.get()); + } + + TimePoint elapsed() const; + TimePoint elapsed_time() const; + + LimitsType limits; + + size_t pvIdx, pvLast; + std::atomic nodes, tbHits, bestMoveChanges; + int selDepth, nmpMinPly; + + Value optimism[COLOR_NB]; + + Position rootPos; + StateInfo rootState; + RootMoves rootMoves; + Depth rootDepth, completedDepth; + Value rootDelta; + + size_t threadIdx; + NumaReplicatedAccessToken numaAccessToken; + + // Reductions lookup table initialized at startup + std::array reductions; // [depth or moveNumber] + + // The main thread has a SearchManager, the others have a NullSearchManager + std::unique_ptr manager; + + Tablebases::Config tbConfig; - LimitsType() { // Init explicitly due to broken value-initialization of non POD in MSVC - nodes = time[WHITE] = time[BLACK] = inc[WHITE] = inc[BLACK] = - npmsec = movestogo = depth = movetime = mate = perft = infinite = 0; - } + const OptionsMap& options; + ThreadPool& threads; + TranspositionTable& tt; + const LazyNumaReplicated& networks; - bool use_time_management() const { - return !(mate | movetime | depth | nodes | perft | infinite); - } + // Used by NNUE + Eval::NNUE::AccumulatorCaches refreshTable; - std::vector searchmoves; - int time[COLOR_NB], inc[COLOR_NB], npmsec, movestogo, depth, - movetime, mate, perft, infinite; - int64_t nodes; - TimePoint startTime; + friend class Stockfish::ThreadPool; + friend class SearchManager; }; -extern LimitsType Limits; -void init(); -void clear(); +} // namespace Search -} // namespace Search +} // namespace Stockfish -#endif // #ifndef SEARCH_H_INCLUDED +#endif // #ifndef SEARCH_H_INCLUDED