X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.h;h=92e124fc47453d60e415403c9a2addf81005605e;hb=HEAD;hp=5a0ad5df5790708e3a0e1d8d37f2926fcb3b668a;hpb=856a5f3aaaf8b9d53599963decacd4476b55c034;p=stockfish diff --git a/src/search.h b/src/search.h index 5a0ad5df..c9fe9e18 100644 --- a/src/search.h +++ b/src/search.h @@ -1,7 +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) 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 @@ -20,95 +19,333 @@ #ifndef SEARCH_H_INCLUDED #define SEARCH_H_INCLUDED -#include // For std::auto_ptr -#include +#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" -struct SplitPoint; +namespace Stockfish { -namespace Search { +// Different node types, used as a template parameter +enum NodeType { + NonPV, + PV, + Root +}; -/// 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. +class TranspositionTable; +class ThreadPool; +class OptionsMap; + +namespace Search { +// 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 { - SplitPoint* splitPoint; - Move* pv; - int ply; - Move currentMove; - Move ttMove; - Move excludedMove; - Move killers[2]; - Depth reduction; - Value staticEval; - bool skipEarlyPruning; + 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. +// 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 { - RootMove(Move m) : score(-VALUE_INFINITE), previousScore(-VALUE_INFINITE), pv(1, m) {} + 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; + } - bool operator<(const RootMove& m) const { return score > m.score; } // Ascending sort - bool operator==(const Move& m) const { return pv[0] == m; } - void insert_pv_in_tt(Position& pos); - Move extract_ponder_from_tt(Position& pos); - - Value score; - Value previousScore; - std::vector pv; + 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; }; -typedef std::vector RootMoveVector; +using RootMoves = std::vector; -/// LimitsType struct stores information sent by GUI about available time to -/// search the current move, maximum depth/time, if we are in analysis mode or -/// if we have to ponder while it's our opponent's turn to move. +// LimitsType struct stores information sent by the caller about the analysis required. struct LimitsType { - LimitsType() { // Init explicitly due to broken value-initialization of non POD in MSVC - nodes = time[WHITE] = time[BLACK] = inc[WHITE] = inc[BLACK] = movestogo = - depth = movetime = mate = infinite = ponder = 0; - } + // 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]; } + + 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; +}; + + +// 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) {} + + const OptionsMap& options; + ThreadPool& threads; + TranspositionTable& tt; + const LazyNumaReplicated& networks; +}; + +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; +}; - bool use_time_management() const { - return !(mate | movetime | depth | nodes | infinite); - } +// 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; - std::vector searchmoves; - int time[COLOR_NB], inc[COLOR_NB], movestogo, depth, movetime, mate, infinite, ponder; - int64_t nodes; + 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(); }; -/// The SignalsType struct stores volatile flags updated during the search -/// typically in an async fashion e.g. to stop the search by the GUI. +// 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; -struct SignalsType { - bool stop, stopOnPonderhit, firstRootMove, failedLowAtRoot; + 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 {} }; -typedef std::auto_ptr > StateStackPtr; -extern volatile SignalsType Signals; -extern LimitsType Limits; -extern RootMoveVector RootMoves; -extern Position RootPos; -extern Time::point SearchTime; -extern StateStackPtr SetupStates; +// 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; + + const OptionsMap& options; + ThreadPool& threads; + TranspositionTable& tt; + const LazyNumaReplicated& networks; + + // Used by NNUE + Eval::NNUE::AccumulatorCaches refreshTable; + + friend class Stockfish::ThreadPool; + friend class SearchManager; +}; + -void init(); -void think(); -template uint64_t perft(Position& pos, Depth depth); +} // namespace Search -} // namespace Search +} // namespace Stockfish -#endif // #ifndef SEARCH_H_INCLUDED +#endif // #ifndef SEARCH_H_INCLUDED