X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=82ecd913f8ddfec988f58f638fd52247d9c9e7f1;hp=abf2673499ec8be4f0f5ea7a09ad63701ef4542c;hb=a303bde26c166abf6a14846f841694fa81d8d0a3;hpb=e84488ed6bef17ed3914a272a4a2622a2db44cc9 diff --git a/src/search.cpp b/src/search.cpp index abf26734..82ecd913 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -53,43 +53,59 @@ namespace { /// Types - // IterationInfoType stores search results for each iteration - // - // Because we use relatively small (dynamic) aspiration window, - // there happens many fail highs and fail lows in root. And - // because we don't do researches in those cases, "value" stored - // here is not necessarily exact. Instead in case of fail high/low - // we guess what the right value might be and store our guess - // as a "speculated value" and then move on. Speculated values are - // used just to calculate aspiration window width, so also if are - // not exact is not big a problem. - - struct IterationInfoType { - - IterationInfoType(Value v = Value(0), Value sv = Value(0)) - : value(v), speculatedValue(sv) {} - - Value value, speculatedValue; - }; + // ThreadsManager class is used to handle all the threads related stuff in search, + // init, starting, parking and, the most important, launching a slave thread at a + // split point are what this class does. All the access to shared thread data is + // done through this class, so that we avoid using global variables instead. + + class ThreadsManager { + /* As long as the single ThreadsManager object is defined as a global we don't + need to explicitly initialize to zero its data members because variables with + static storage duration are automatically set to zero before enter main() + */ + public: + void init_threads(); + void exit_threads(); + + int active_threads() const { return ActiveThreads; } + void set_active_threads(int newActiveThreads) { ActiveThreads = newActiveThreads; } + void incrementNodeCounter(int threadID) { threads[threadID].nodes++; } + void incrementBetaCounter(Color us, Depth d, int threadID) { threads[threadID].betaCutOffs[us] += unsigned(d); } + + void resetNodeCounters(); + void resetBetaCounters(); + int64_t nodes_searched() const; + void get_beta_counters(Color us, int64_t& our, int64_t& their) const; + bool available_thread_exists(int master) const; + bool thread_is_available(int slave, int master) const; + bool thread_should_stop(int threadID) const; + void wake_sleeping_threads(); + void put_threads_to_sleep(); + void idle_loop(int threadID, SplitPoint* waitSp); + bool split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue, + Depth depth, int* moves, MovePicker* mp, int master, bool pvNode); + + private: + friend void poll(SearchStack ss[], int ply); + + int ActiveThreads; + volatile bool AllThreadsShouldExit, AllThreadsShouldSleep; + Thread threads[MAX_THREADS]; + SplitPoint SplitPointStack[MAX_THREADS][ACTIVE_SPLIT_POINTS_MAX]; - // The BetaCounterType class is used to order moves at ply one. - // Apart for the first one that has its score, following moves - // normally have score -VALUE_INFINITE, so are ordered according - // to the number of beta cutoffs occurred under their subtree during - // the last iteration. The counters are per thread variables to avoid - // concurrent accessing under SMP case. + Lock MPLock, WaitLock; - struct BetaCounterType { +#if !defined(_MSC_VER) + pthread_cond_t WaitCond; +#else + HANDLE SitIdleEvent[MAX_THREADS]; +#endif - BetaCounterType(); - void clear(); - void add(Color us, Depth d, int threadID); - void read(Color us, int64_t& our, int64_t& their); }; - // The RootMove class is used for moves at the root at the tree. For each + // RootMove struct is used for moves at the root at the tree. For each // root move, we store a score, a node count, and a PV (really a refutation // in the case of moves which fail low). @@ -141,62 +157,79 @@ namespace { }; - /// Constants - - // Search depth at iteration 1 - const Depth InitialDepth = OnePly; - - // Depth limit for selective search - const Depth SelectiveDepth = 7 * OnePly; - - // Use internal iterative deepening? - const bool UseIIDAtPVNodes = true; - const bool UseIIDAtNonPVNodes = true; + /// Adjustments - // Internal iterative deepening margin. At Non-PV moves, when - // UseIIDAtNonPVNodes is true, we do an internal iterative deepening - // search when the static evaluation is at most IIDMargin below beta. - const Value IIDMargin = Value(0x100); + // Step 6. Razoring - // Easy move margin. An easy move candidate must be at least this much - // better than the second best move. - const Value EasyMoveMargin = Value(0x200); + // Maximum depth for razoring + const Depth RazorDepth = 4 * OnePly; - // Problem margin. If the score of the first move at iteration N+1 has - // dropped by more than this since iteration N, the boolean variable - // "Problem" is set to true, which will make the program spend some extra - // time looking for a better move. - const Value ProblemMargin = Value(0x28); + // Dynamic razoring margin based on depth + inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); } - // No problem margin. If the boolean "Problem" is true, and a new move - // is found at the root which is less than NoProblemMargin worse than the - // best move from the previous iteration, Problem is set back to false. - const Value NoProblemMargin = Value(0x14); + // Step 8. Null move search with verification search // Null move margin. A null move search will not be done if the static // evaluation of the position is more than NullMoveMargin below beta. const Value NullMoveMargin = Value(0x200); - // If the TT move is at least SingleReplyMargin better then the + // Maximum depth for use of dynamic threat detection when null move fails low + const Depth ThreatDepth = 5 * OnePly; + + // Step 9. Internal iterative deepening + + // Minimum depth for use of internal iterative deepening + const Depth IIDDepthAtPVNodes = 5 * OnePly; + const Depth IIDDepthAtNonPVNodes = 8 * OnePly; + + // At Non-PV nodes we do an internal iterative deepening search + // when the static evaluation is at most IIDMargin below beta. + const Value IIDMargin = Value(0x100); + + // Step 11. Decide the new search depth + + // Extensions. Configurable UCI options + // Array index 0 is used at non-PV nodes, index 1 at PV nodes. + Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2]; + Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2]; + + // Minimum depth for use of singular extension + const Depth SingularExtensionDepthAtPVNodes = 6 * OnePly; + const Depth SingularExtensionDepthAtNonPVNodes = 8 * OnePly; + + // If the TT move is at least SingularExtensionMargin better then the // remaining ones we will extend it. - const Value SingleReplyMargin = Value(0x20); + const Value SingularExtensionMargin = Value(0x20); + + // Step 12. Futility pruning - // Margins for futility pruning in the quiescence search, and at frontier - // and near frontier nodes. + // Futility margin for quiescence search const Value FutilityMarginQS = Value(0x80); - Value FutilityMargins[2 * PLY_MAX_PLUS_2]; // Initialized at startup. + // Futility lookup tables (initialized at startup) and their getter functions + int32_t FutilityMarginsMatrix[16][64]; // [depth][moveNumber] + int FutilityMoveCountArray[32]; // [depth] - // Each move futility margin is decreased - const Value IncrementalFutilityMargin = Value(0x8); + inline Value futility_margin(Depth d, int mn) { return Value(d < 7 * OnePly ? FutilityMarginsMatrix[Max(d, 0)][Min(mn, 63)] : 2 * VALUE_INFINITE); } + inline int futility_move_count(Depth d) { return d < 16 * OnePly ? FutilityMoveCountArray[d] : 512; } - // Depth limit for razoring - const Depth RazorDepth = 4 * OnePly; + // Step 14. Reduced search + + // Reduction lookup tables (initialized at startup) and their getter functions + int8_t PVReductionMatrix[64][64]; // [depth][moveNumber] + int8_t NonPVReductionMatrix[64][64]; // [depth][moveNumber] - /// Variables initialized by UCI options + inline Depth pv_reduction(Depth d, int mn) { return (Depth) PVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; } + inline Depth nonpv_reduction(Depth d, int mn) { return (Depth) NonPVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; } - // Depth limit for use of dynamic threat detection - Depth ThreatDepth; + // Common adjustments + + // Search depth at iteration 1 + const Depth InitialDepth = OnePly; + + // Easy move margin. An easy move candidate must be at least this much + // better than the second best move. + const Value EasyMoveMargin = Value(0x200); // Last seconds noise filtering (LSN) const bool UseLSNFiltering = true; @@ -204,16 +237,14 @@ namespace { const Value LSNValue = value_from_centipawns(200); bool loseOnTime = false; - // Extensions. Array index 0 is used at non-PV nodes, index 1 at PV nodes. - Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2]; - Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2]; - // Iteration counters + /// Global variables + + // Iteration counter int Iteration; - BetaCounterType BetaCounter; // Scores and number of times the best move changed for each iteration - IterationInfoType IterationInfo[PLY_MAX_PLUS_2]; + Value ValueByIteration[PLY_MAX_PLUS_2]; int BestMoveChangesByIteration[PLY_MAX_PLUS_2]; // Search window management @@ -223,13 +254,10 @@ namespace { int MultiPV; // Time managment variables - int RootMoveNumber; - int SearchStartTime; - int MaxNodes, MaxDepth; + int RootMoveNumber, SearchStartTime, MaxNodes, MaxDepth; int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime; bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit; - bool AbortSearch, Quit; - bool FailHigh, FailLow, Problem; + bool AbortSearch, Quit, AspirationFailLow; // Show current line? bool ShowCurrentLine; @@ -238,37 +266,20 @@ namespace { bool UseLogFile; std::ofstream LogFile; - // Natural logarithmic lookup table and its getter function - float lnArray[512]; - inline float ln(int i) { return lnArray[i]; } - - // MP related variables - int ActiveThreads = 1; + // Multi-threads related variables Depth MinimumSplitDepth; int MaxThreadsPerSplitPoint; - Thread Threads[THREAD_MAX]; - Lock MPLock; - Lock IOLock; - bool AllThreadsShouldExit = false; - SplitPoint SplitPointStack[THREAD_MAX][ACTIVE_SPLIT_POINTS_MAX]; - bool Idle = true; - -#if !defined(_MSC_VER) - pthread_cond_t WaitCond; - pthread_mutex_t WaitLock; -#else - HANDLE SitIdleEvent[THREAD_MAX]; -#endif + ThreadsManager TM; - // Node counters, used only by thread[0] but try to keep in different - // cache lines (64 bytes each) from the heavy SMP read accessed variables. + // Node counters, used only by thread[0] but try to keep in different cache + // lines (64 bytes each) from the heavy multi-thread read accessed variables. int NodesSincePoll; int NodesBetweenPolls = 30000; // History table History H; - /// Functions + /// Local functions Value id_loop(const Position& pos, Move searchMoves[]); Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta); @@ -288,32 +299,17 @@ namespace { bool ok_to_prune(const Position& pos, Move m, Move threat); bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply); Value refine_eval(const TTEntry* tte, Value defaultEval, int ply); - void reduction_parameters(float base, float Inhibitor, Depth depth, float& logLimit, float& gradient); - Depth reduction(int moveCount, const float LogLimit, const float BaseRed, const float Gradient); void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount); void update_killers(Move m, SearchStack& ss); void update_gains(const Position& pos, Move move, Value before, Value after); - bool fail_high_ply_1(); int current_search_time(); int nps(); - void poll(); + void poll(SearchStack ss[], int ply); void ponderhit(); - void print_current_line(SearchStack ss[], int ply, int threadID); void wait_for_stop_or_ponderhit(); void init_ss_array(SearchStack ss[]); - - void idle_loop(int threadID, SplitPoint* waitSp); - void init_split_point_stack(); - void destroy_split_point_stack(); - bool thread_should_stop(int threadID); - bool thread_is_available(int slave, int master); - bool idle_thread_exists(int master); - bool split(const Position& pos, SearchStack* ss, int ply, - Value *alpha, Value *beta, Value *bestValue, - const Value futilityValue, Depth depth, int *moves, - MovePicker *mp, int master, bool pvNode); - void wake_sleeping_threads(); + void print_pv_info(const Position& pos, SearchStack ss[], Value alpha, Value beta, Value value); #if !defined(_MSC_VER) void *init_thread(void *threadID); @@ -328,15 +324,23 @@ namespace { //// Functions //// +/// init_threads(), exit_threads() and nodes_searched() are helpers to +/// give accessibility to some TM methods from outside of current file. + +void init_threads() { TM.init_threads(); } +void exit_threads() { TM.exit_threads(); } +int64_t nodes_searched() { return TM.nodes_searched(); } + /// perft() is our utility to verify move generation is bug free. All the legal /// moves up to given depth are generated and counted and the sum returned. int perft(Position& pos, Depth depth) { + StateInfo st; Move move; int sum = 0; - MovePicker mp = MovePicker(pos, MOVE_NONE, depth, H); + MovePicker mp(pos, MOVE_NONE, depth, H); // If we are at the last ply we don't need to do and undo // the moves, just to count them. @@ -350,7 +354,6 @@ int perft(Position& pos, Depth depth) CheckInfo ci(pos); while ((move = mp.get_next_move()) != MOVE_NONE) { - StateInfo st; pos.do_move(move, st, ci, pos.move_is_check(move, ci)); sum += perft(pos, depth - OnePly); pos.undo_move(move); @@ -369,9 +372,9 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, int maxNodes, int maxTime, Move searchMoves[]) { // Initialize global search variables - Idle = StopOnPonderhit = AbortSearch = Quit = false; - FailHigh = FailLow = Problem = false; + StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false; NodesSincePoll = 0; + TM.resetNodeCounters(); SearchStartTime = get_system_time(); ExactMaxTime = maxTime; MaxDepth = maxDepth; @@ -381,74 +384,62 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch; // Look for a book move, only during games, not tests - if (UseTimeManagement && !ponder && get_option_value_bool("OwnBook")) + if (UseTimeManagement && get_option_value_bool("OwnBook")) { - Move bookMove; if (get_option_value_string("Book File") != OpeningBook.file_name()) OpeningBook.open(get_option_value_string("Book File")); - bookMove = OpeningBook.get_move(pos); + Move bookMove = OpeningBook.get_move(pos); if (bookMove != MOVE_NONE) { + if (PonderSearch) + wait_for_stop_or_ponderhit(); + cout << "bestmove " << bookMove << endl; return true; } } - for (int i = 0; i < THREAD_MAX; i++) - { - Threads[i].nodes = 0ULL; - Threads[i].failHighPly1 = false; - } - + // Reset loseOnTime flag at the beginning of a new game if (button_was_pressed("New Game")) - loseOnTime = false; // Reset at the beginning of a new game + loseOnTime = false; // Read UCI option values TT.set_size(get_option_value_int("Hash")); if (button_was_pressed("Clear Hash")) TT.clear(); - bool PonderingEnabled = get_option_value_bool("Ponder"); - MultiPV = get_option_value_int("MultiPV"); - - CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)")); - CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)")); - + CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)")); + CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)")); SingleEvasionExtension[1] = Depth(get_option_value_int("Single Evasion Extension (PV nodes)")); SingleEvasionExtension[0] = Depth(get_option_value_int("Single Evasion Extension (non-PV nodes)")); - PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)")); PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)")); + PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)")); + PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)")); + PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)")); + PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)")); + MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)")); + MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)")); + + MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly; + MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point"); + ShowCurrentLine = get_option_value_bool("UCI_ShowCurrLine"); + MultiPV = get_option_value_int("MultiPV"); + Chess960 = get_option_value_bool("UCI_Chess960"); + UseLogFile = get_option_value_bool("Use Search Log"); - PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)")); - PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)")); - - PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)")); - PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)")); - - MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)")); - MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)")); - - ThreatDepth = get_option_value_int("Threat Depth") * OnePly; - - Chess960 = get_option_value_bool("UCI_Chess960"); - ShowCurrentLine = get_option_value_bool("UCI_ShowCurrLine"); - UseLogFile = get_option_value_bool("Use Search Log"); if (UseLogFile) LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app); - MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly; - MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point"); - read_weights(pos.side_to_move()); // Set the number of active threads int newActiveThreads = get_option_value_int("Threads"); - if (newActiveThreads != ActiveThreads) + if (newActiveThreads != TM.active_threads()) { - ActiveThreads = newActiveThreads; - init_eval(ActiveThreads); + TM.set_active_threads(newActiveThreads); + init_eval(TM.active_threads()); // HACK: init_eval() destroys the static castleRightsMask[] array in the // Position class. The below line repairs the damage. Position p(pos.to_fen()); @@ -456,10 +447,7 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, } // Wake up sleeping threads - wake_sleeping_threads(); - - for (int i = 1; i < ActiveThreads; i++) - assert(thread_is_available(i, 0)); + TM.wake_sleeping_threads(); // Set thinking time int myTime = time[side_to_move]; @@ -493,14 +481,15 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, } } - if (PonderingEnabled) + if (get_option_value_bool("Ponder")) { MaxSearchTime += MaxSearchTime / 4; MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime); } } - // Set best NodesBetweenPolls interval + // Set best NodesBetweenPolls interval to avoid lagging under + // heavy time pressure. if (MaxNodes) NodesBetweenPolls = Min(MaxNodes, 30000); else if (myTime && myTime < 1000) @@ -510,7 +499,7 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, else NodesBetweenPolls = 30000; - // Write information to search log file + // Write search information to log file if (UseLogFile) LogFile << "Searching: " << pos.to_fen() << endl << "infinite: " << infinite @@ -519,7 +508,7 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, << " increment: " << myIncrement << " moves to go: " << movesToGo << endl; - // LSN filtering. Used only for developing purpose. Disabled by default. + // LSN filtering. Used only for developing purposes, disabled by default if ( UseLSNFiltering && loseOnTime) { @@ -531,7 +520,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, // We're ready to start thinking. Call the iterative deepening loop function Value v = id_loop(pos, searchMoves); - if (UseLSNFiltering) { // Step 1. If this is sudden death game and our position is hopeless, @@ -554,111 +542,37 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, if (UseLogFile) LogFile.close(); - Idle = true; + TM.put_threads_to_sleep(); + return !Quit; } -/// init_threads() is called during startup. It launches all helper threads, -/// and initializes the split point stack and the global locks and condition -/// objects. - -void init_threads() { - - volatile int i; - bool ok; - -#if !defined(_MSC_VER) - pthread_t pthread[1]; -#endif +/// init_search() is called during startup. It initializes various lookup tables - // Init our logarithmic lookup table - for (i = 0; i < 512; i++) - lnArray[i] = float(log(double(i))); // log() returns base-e logarithm +void init_search() { - for (i = 0; i < THREAD_MAX; i++) - Threads[i].activeSplitPoints = 0; + // Init our reduction lookup tables + for (int i = 1; i < 64; i++) // i == depth (OnePly = 1) + for (int j = 1; j < 64; j++) // j == moveNumber + { + double pvRed = 0.5 + log(double(i)) * log(double(j)) / 6.0; + double nonPVRed = 0.5 + log(double(i)) * log(double(j)) / 3.0; + PVReductionMatrix[i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0); + NonPVReductionMatrix[i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0); + } // Init futility margins array - FutilityMargins[0] = FutilityMargins[1] = Value(0); - - for (i = 2; i < 2 * PLY_MAX_PLUS_2; i++) - { - FutilityMargins[i] = Value(112 * bitScanReverse32(i * i / 2)); // FIXME: test using log instead of BSR - } - - // Initialize global locks - lock_init(&MPLock, NULL); - lock_init(&IOLock, NULL); - - init_split_point_stack(); - -#if !defined(_MSC_VER) - pthread_mutex_init(&WaitLock, NULL); - pthread_cond_init(&WaitCond, NULL); -#else - for (i = 0; i < THREAD_MAX; i++) - SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0); -#endif - - // All threads except the main thread should be initialized to idle state - for (i = 1; i < THREAD_MAX; i++) - { - Threads[i].stop = false; - Threads[i].workIsWaiting = false; - Threads[i].idle = true; - Threads[i].running = false; - } - - // Launch the helper threads - for (i = 1; i < THREAD_MAX; i++) - { -#if !defined(_MSC_VER) - ok = (pthread_create(pthread, NULL, init_thread, (void*)(&i)) == 0); -#else - DWORD iID[1]; - ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID) != NULL); -#endif - - if (!ok) + for (int i = 0; i < 16; i++) // i == depth (OnePly = 2) + for (int j = 0; j < 64; j++) // j == moveNumber { - cout << "Failed to create thread number " << i << endl; - Application::exit_with_failure(); + // FIXME: test using log instead of BSR + FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j; } - // Wait until the thread has finished launching - while (!Threads[i].running); - } -} - - -/// stop_threads() is called when the program exits. It makes all the -/// helper threads exit cleanly. - -void stop_threads() { - - ActiveThreads = THREAD_MAX; // HACK - Idle = false; // HACK - wake_sleeping_threads(); - AllThreadsShouldExit = true; - for (int i = 1; i < THREAD_MAX; i++) - { - Threads[i].stop = true; - while (Threads[i].running); - } - destroy_split_point_stack(); -} - - -/// nodes_searched() returns the total number of nodes searched so far in -/// the current search. - -int64_t nodes_searched() { - - int64_t result = 0ULL; - for (int i = 0; i < ActiveThreads; i++) - result += Threads[i].nodes; - return result; + // Init futility move count array + for (int i = 0; i < 32; i++) // i == depth (OnePly = 2) + FutilityMoveCountArray[i] = 3 + (1 << (3 * i / 8)); } @@ -670,7 +584,6 @@ void SearchStack::init(int ply) { currentMove = threatMove = MOVE_NONE; reduction = Depth(0); eval = VALUE_NONE; - evalInfo = NULL; } void SearchStack::initKillers() { @@ -691,24 +604,28 @@ namespace { Position p(pos); SearchStack ss[PLY_MAX_PLUS_2]; + Move EasyMove = MOVE_NONE; + Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE; - // searchMoves are verified, copied, scored and sorted + // Moves to search are verified, copied, scored and sorted RootMoveList rml(p, searchMoves); + // Handle special case of searching on a mate/stale position if (rml.move_count() == 0) { if (PonderSearch) wait_for_stop_or_ponderhit(); - return pos.is_check()? -VALUE_MATE : VALUE_DRAW; + return pos.is_check() ? -VALUE_MATE : VALUE_DRAW; } - // Print RootMoveList c'tor startup scoring to the standard output, - // so that we print information also for iteration 1. - cout << "info depth " << 1 << "\ninfo depth " << 1 + // Print RootMoveList startup scoring to the standard output, + // so to output information also for iteration 1. + cout << "info depth " << 1 + << "\ninfo depth " << 1 << " score " << value_to_string(rml.get_move_score(0)) << " time " << current_search_time() - << " nodes " << nodes_searched() + << " nodes " << TM.nodes_searched() << " nps " << nps() << " pv " << rml.get_move(0) << "\n"; @@ -716,11 +633,10 @@ namespace { TT.new_search(); H.clear(); init_ss_array(ss); - IterationInfo[1] = IterationInfoType(rml.get_move_score(0), rml.get_move_score(0)); + ValueByIteration[1] = rml.get_move_score(0); Iteration = 1; // Is one move significantly better than others after initial scoring ? - Move EasyMove = MOVE_NONE; if ( rml.move_count() == 1 || rml.get_move_score(0) > rml.get_move_score(1) + EasyMoveMargin) EasyMove = rml.get_move(0); @@ -737,30 +653,21 @@ namespace { cout << "info depth " << Iteration << endl; - // Calculate dynamic search window based on previous iterations - Value alpha, beta; - - if (MultiPV == 1 && Iteration >= 6 && abs(IterationInfo[Iteration - 1].value) < VALUE_KNOWN_WIN) + // Calculate dynamic aspiration window based on previous iterations + if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN) { - int prevDelta1 = IterationInfo[Iteration - 1].speculatedValue - IterationInfo[Iteration - 2].speculatedValue; - int prevDelta2 = IterationInfo[Iteration - 2].speculatedValue - IterationInfo[Iteration - 3].speculatedValue; + int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2]; + int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3]; - int delta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16); + AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16); + AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize - delta = (delta + 7) / 8 * 8; // Round to match grainSize - AspirationDelta = delta; - - alpha = Max(IterationInfo[Iteration - 1].value - delta, -VALUE_INFINITE); - beta = Min(IterationInfo[Iteration - 1].value + delta, VALUE_INFINITE); - } - else - { - alpha = - VALUE_INFINITE; - beta = VALUE_INFINITE; + alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE); + beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE); } // Search to the current depth - Value value = root_search(p, ss, rml, alpha, beta); + value = root_search(p, ss, rml, alpha, beta); // Write PV to transposition table, in case the relevant entries have // been overwritten during the search. @@ -770,39 +677,12 @@ namespace { break; // Value cannot be trusted. Break out immediately! //Save info about search result - Value speculatedValue; - bool fHigh = false; - bool fLow = false; - Value delta = value - IterationInfo[Iteration - 1].value; - - if (value >= beta) - { - assert(delta > 0); - - fHigh = true; - speculatedValue = value + delta; - BestMoveChangesByIteration[Iteration] += 2; // Allocate more time - } - else if (value <= alpha) - { - assert(value == alpha); - assert(delta < 0); - - fLow = true; - speculatedValue = value + delta; - BestMoveChangesByIteration[Iteration] += 3; // Allocate more time - } else - speculatedValue = value; + ValueByIteration[Iteration] = value; - speculatedValue = Min(Max(speculatedValue, -VALUE_INFINITE), VALUE_INFINITE); - IterationInfo[Iteration] = IterationInfoType(value, speculatedValue); - - // Drop the easy move if it differs from the new best move + // Drop the easy move if differs from the new best move if (ss[0].pv[0] != EasyMove) EasyMove = MOVE_NONE; - Problem = false; - if (UseTimeManagement) { // Time to stop? @@ -815,15 +695,13 @@ namespace { // Stop search early when the last two iterations returned a mate score if ( Iteration >= 6 - && abs(IterationInfo[Iteration].value) >= abs(VALUE_MATE) - 100 - && abs(IterationInfo[Iteration-1].value) >= abs(VALUE_MATE) - 100) + && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100 + && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100) stopSearch = true; - // Stop search early if one move seems to be much better than the rest - int64_t nodes = nodes_searched(); + // Stop search early if one move seems to be much better than the others + int64_t nodes = TM.nodes_searched(); if ( Iteration >= 8 - && !fLow - && !fHigh && EasyMove == ss[0].pv[0] && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100 && current_search_time() > MaxSearchTime / 16) @@ -844,10 +722,10 @@ namespace { if (stopSearch) { - if (!PonderSearch) - break; - else + if (PonderSearch) StopOnPonderhit = true; + else + break; } } @@ -863,7 +741,7 @@ namespace { wait_for_stop_or_ponderhit(); else // Print final search statistics - cout << "info nodes " << nodes_searched() + cout << "info nodes " << TM.nodes_searched() << " nps " << nps() << " time " << current_search_time() << " hashfull " << TT.full() << endl; @@ -874,7 +752,11 @@ namespace { ss[0].pv[0] = rml.get_move(0); ss[0].pv[1] = MOVE_NONE; } + + assert(ss[0].pv[0] != MOVE_NONE); + cout << "bestmove " << ss[0].pv[0]; + if (ss[0].pv[1] != MOVE_NONE) cout << " ponder " << ss[0].pv[1]; @@ -888,13 +770,15 @@ namespace { if (dbg_show_hit_rate) dbg_print_hit_rate(LogFile); - LogFile << "\nNodes: " << nodes_searched() + LogFile << "\nNodes: " << TM.nodes_searched() << "\nNodes/second: " << nps() << "\nBest move: " << move_to_san(p, ss[0].pv[0]); StateInfo st; p.do_move(ss[0].pv[0], st); - LogFile << "\nPonder move: " << move_to_san(p, ss[0].pv[1]) << endl; + LogFile << "\nPonder move: " + << move_to_san(p, ss[0].pv[1]) // Works also with MOVE_NONE + << endl; } return rml.get_move_score(0); } @@ -902,277 +786,219 @@ namespace { // root_search() is the function which searches the root node. It is // similar to search_pv except that it uses a different move ordering - // scheme and prints some information to the standard output. + // scheme, prints some information to the standard output and handles + // the fail low/high loops. Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta) { - Value alpha = oldAlpha; - Value value; - CheckInfo ci(pos); + EvalInfo ei; + StateInfo st; + int64_t nodes; + Move move; + Depth depth, ext, newDepth; + Value value, alpha; + bool isCheck, moveIsCheck, captureOrPromotion, dangerous; int researchCount = 0; - bool isCheck = pos.is_check(); + CheckInfo ci(pos); + alpha = oldAlpha; + isCheck = pos.is_check(); // Evaluate the position statically - EvalInfo ei; - if (!isCheck) - ss[0].eval = evaluate(pos, ei, 0); - else - ss[0].eval = VALUE_NONE; - - while(1) // Fail low loop - { + ss[0].eval = !isCheck ? evaluate(pos, ei, 0) : VALUE_NONE; - // Loop through all the moves in the root move list - for (int i = 0; i < rml.move_count() && !AbortSearch; i++) + while (1) // Fail low loop { - if (alpha >= beta) + // Loop through all the moves in the root move list + for (int i = 0; i < rml.move_count() && !AbortSearch; i++) { - // We failed high, invalidate and skip next moves, leave node-counters - // and beta-counters as they are and quickly return, we will try to do - // a research at the next iteration with a bigger aspiration window. - rml.set_move_score(i, -VALUE_INFINITE); - continue; - } - int64_t nodes; - Move move; - StateInfo st; - Depth depth, ext, newDepth; - - RootMoveNumber = i + 1; - FailHigh = false; - - // Save the current node count before the move is searched - nodes = nodes_searched(); - - // Reset beta cut-off counters - BetaCounter.clear(); - - // Pick the next root move, and print the move and the move number to - // the standard output. - move = ss[0].currentMove = rml.get_move(i); - - if (current_search_time() >= 1000) - cout << "info currmove " << move - << " currmovenumber " << RootMoveNumber << endl; - - // Decide search depth for this move - bool moveIsCheck = pos.move_is_check(move); - bool captureOrPromotion = pos.move_is_capture_or_promotion(move); - bool dangerous; - depth = (Iteration - 2) * OnePly + InitialDepth; - ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous); - newDepth = depth + ext; - - value = - VALUE_INFINITE; + if (alpha >= beta) + { + // We failed high, invalidate and skip next moves, leave node-counters + // and beta-counters as they are and quickly return, we will try to do + // a research at the next iteration with a bigger aspiration window. + rml.set_move_score(i, -VALUE_INFINITE); + continue; + } - // Precalculate reduction parameters - float LogLimit, Gradient, BaseReduction = 0.5; - reduction_parameters(BaseReduction, 6.0, depth, LogLimit, Gradient); + // This is used by time management and starts from 1 + RootMoveNumber = i + 1; - while (1) // Fail high loop - { + // Save the current node count before the move is searched + nodes = TM.nodes_searched(); - // Make the move, and search it - pos.do_move(move, st, ci, moveIsCheck); + // Reset beta cut-off counters + TM.resetBetaCounters(); - if (i < MultiPV || value > alpha) - { - // Aspiration window is disabled in multi-pv case - if (MultiPV > 1) - alpha = -VALUE_INFINITE; + // Pick the next root move, and print the move and the move number to + // the standard output. + move = ss[0].currentMove = rml.get_move(i); - value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); + if (current_search_time() >= 1000) + cout << "info currmove " << move + << " currmovenumber " << RootMoveNumber << endl; - // If the value has dropped a lot compared to the last iteration, - // set the boolean variable Problem to true. This variable is used - // for time managment: When Problem is true, we try to complete the - // current iteration before playing a move. - Problem = ( Iteration >= 2 - && value <= IterationInfo[Iteration - 1].value - ProblemMargin); + // Decide search depth for this move + moveIsCheck = pos.move_is_check(move); + captureOrPromotion = pos.move_is_capture_or_promotion(move); + depth = (Iteration - 2) * OnePly + InitialDepth; + ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous); + newDepth = depth + ext; - if (Problem && StopOnPonderhit) - StopOnPonderhit = false; - } - else - { - // Try to reduce non-pv search depth by one ply if move seems not problematic, - // if the move fails high will be re-searched at full depth. - bool doFullDepthSearch = true; - - if ( depth >= 3*OnePly // FIXME was newDepth - && !dangerous - && !captureOrPromotion - && !move_is_castle(move)) - { - ss[0].reduction = reduction(RootMoveNumber - MultiPV + 1, LogLimit, BaseReduction, Gradient); - if (ss[0].reduction) - { - value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0); - doFullDepthSearch = (value > alpha); - } - } + // Reset value before the search + value = - VALUE_INFINITE; - if (doFullDepthSearch) + while (1) // Fail high loop { - ss[0].reduction = Depth(0); - value = -search(pos, ss, -alpha, newDepth, 1, true, 0); + // Make the move, and search it + pos.do_move(move, st, ci, moveIsCheck); - if (value > alpha) + if (i < MultiPV || value > alpha) { - // Fail high! Set the boolean variable FailHigh to true, and - // re-search the move using a PV search. The variable FailHigh - // is used for time managment: We try to avoid aborting the - // search prematurely during a fail high research. - FailHigh = true; + // Aspiration window is disabled in multi-pv case + if (MultiPV > 1) + alpha = -VALUE_INFINITE; + + // Full depth PV search, done on first move or after a fail high value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); } - } - } - - pos.undo_move(move); - - if (AbortSearch || value < beta) - break; // We are not failing high - - // We are failing high and going to do a research. It's important to update score - // before research in case we run out of time while researching. - rml.set_move_score(i, value); - update_pv(ss, 0); - TT.extract_pv(pos, ss[0].pv, PLY_MAX); - rml.set_move_pv(i, ss[0].pv); - - // Print search information to the standard output - cout << "info depth " << Iteration - << " score " << value_to_string(value) - << ((value >= beta) ? " lowerbound" : - ((value <= alpha)? " upperbound" : "")) - << " time " << current_search_time() - << " nodes " << nodes_searched() - << " nps " << nps() - << " pv "; - - for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++) - cout << ss[0].pv[j] << " "; - - cout << endl; - - if (UseLogFile) - { - ValueType type = (value >= beta ? VALUE_TYPE_LOWER - : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT)); - - LogFile << pretty_pv(pos, current_search_time(), Iteration, - nodes_searched(), value, type, ss[0].pv) << endl; - } - - // Prepare for research - researchCount++; - beta = Min(beta + AspirationDelta * (1 << researchCount), VALUE_INFINITE); - - } // End of fail high loop - - // Finished searching the move. If AbortSearch is true, the search - // was aborted because the user interrupted the search or because we - // ran out of time. In this case, the return value of the search cannot - // be trusted, and we break out of the loop without updating the best - // move and/or PV. - if (AbortSearch) - break; + else + { + // Try to reduce non-pv search depth by one ply if move seems not problematic, + // if the move fails high will be re-searched at full depth. + bool doFullDepthSearch = true; + + if ( depth >= 3 * OnePly // FIXME was newDepth + && !dangerous + && !captureOrPromotion + && !move_is_castle(move)) + { + ss[0].reduction = pv_reduction(depth, i - MultiPV + 2); + if (ss[0].reduction) + { + // Reduced depth non-pv search using alpha as upperbound + value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0); + doFullDepthSearch = (value > alpha); + } + } + + if (doFullDepthSearch) + { + // Full depth non-pv search using alpha as upperbound + ss[0].reduction = Depth(0); + value = -search(pos, ss, -alpha, newDepth, 1, true, 0); + + // If we are above alpha then research at same depth but as PV + // to get a correct score or eventually a fail high above beta. + if (value > alpha) + value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); + } + } - // Remember beta-cutoff and searched nodes counts for this move. The - // info is used to sort the root moves at the next iteration. - int64_t our, their; - BetaCounter.read(pos.side_to_move(), our, their); - rml.set_beta_counters(i, our, their); - rml.set_move_nodes(i, nodes_searched() - nodes); + pos.undo_move(move); - assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE); + // Can we exit fail high loop ? + if (AbortSearch || value < beta) + break; - if (value <= alpha && i >= MultiPV) - rml.set_move_score(i, -VALUE_INFINITE); - else - { - // PV move or new best move! + // We are failing high and going to do a research. It's important to update + // the score before research in case we run out of time while researching. + rml.set_move_score(i, value); + update_pv(ss, 0); + TT.extract_pv(pos, ss[0].pv, PLY_MAX); + rml.set_move_pv(i, ss[0].pv); + + // Print information to the standard output + print_pv_info(pos, ss, alpha, beta, value); + + // Prepare for a research after a fail high, each time with a wider window + researchCount++; + beta = Min(beta + AspirationDelta * (1 << researchCount), VALUE_INFINITE); + + } // End of fail high loop + + // Finished searching the move. If AbortSearch is true, the search + // was aborted because the user interrupted the search or because we + // ran out of time. In this case, the return value of the search cannot + // be trusted, and we break out of the loop without updating the best + // move and/or PV. + if (AbortSearch) + break; + + // Remember beta-cutoff and searched nodes counts for this move. The + // info is used to sort the root moves at the next iteration. + int64_t our, their; + TM.get_beta_counters(pos.side_to_move(), our, their); + rml.set_beta_counters(i, our, their); + rml.set_move_nodes(i, TM.nodes_searched() - nodes); + + assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE); + + if (value <= alpha && i >= MultiPV) + rml.set_move_score(i, -VALUE_INFINITE); + else + { + // PV move or new best move! - // Update PV - rml.set_move_score(i, value); - update_pv(ss, 0); - TT.extract_pv(pos, ss[0].pv, PLY_MAX); - rml.set_move_pv(i, ss[0].pv); + // Update PV + rml.set_move_score(i, value); + update_pv(ss, 0); + TT.extract_pv(pos, ss[0].pv, PLY_MAX); + rml.set_move_pv(i, ss[0].pv); - if (MultiPV == 1) - { - // We record how often the best move has been changed in each - // iteration. This information is used for time managment: When - // the best move changes frequently, we allocate some more time. - if (i > 0) - BestMoveChangesByIteration[Iteration]++; - - // Print search information to the standard output - cout << "info depth " << Iteration - << " score " << value_to_string(value) - << ((value >= beta) ? " lowerbound" : - ((value <= alpha)? " upperbound" : "")) - << " time " << current_search_time() - << " nodes " << nodes_searched() - << " nps " << nps() - << " pv "; - - for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++) - cout << ss[0].pv[j] << " "; - - cout << endl; - - if (UseLogFile) + if (MultiPV == 1) { - ValueType type = (value >= beta ? VALUE_TYPE_LOWER - : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT)); - - LogFile << pretty_pv(pos, current_search_time(), Iteration, - nodes_searched(), value, type, ss[0].pv) << endl; + // We record how often the best move has been changed in each + // iteration. This information is used for time managment: When + // the best move changes frequently, we allocate some more time. + if (i > 0) + BestMoveChangesByIteration[Iteration]++; + + // Print information to the standard output + print_pv_info(pos, ss, alpha, beta, value); + + // Raise alpha to setup proper non-pv search upper bound, note + // that we can end up with alpha >= beta and so get a fail high. + if (value > alpha) + alpha = value; } - if (value > alpha) - alpha = value; - - // Reset the global variable Problem to false if the value isn't too - // far below the final value from the last iteration. - if (value > IterationInfo[Iteration - 1].value - NoProblemMargin) - Problem = false; - } - else // MultiPV > 1 - { - rml.sort_multipv(i); - for (int j = 0; j < Min(MultiPV, rml.move_count()); j++) + else // MultiPV > 1 { - cout << "info multipv " << j + 1 - << " score " << value_to_string(rml.get_move_score(j)) - << " depth " << ((j <= i)? Iteration : Iteration - 1) - << " time " << current_search_time() - << " nodes " << nodes_searched() - << " nps " << nps() - << " pv "; - - for (int k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++) - cout << rml.get_move_pv(j, k) << " "; - - cout << endl; + rml.sort_multipv(i); + for (int j = 0; j < Min(MultiPV, rml.move_count()); j++) + { + cout << "info multipv " << j + 1 + << " score " << value_to_string(rml.get_move_score(j)) + << " depth " << (j <= i ? Iteration : Iteration - 1) + << " time " << current_search_time() + << " nodes " << TM.nodes_searched() + << " nps " << nps() + << " pv "; + + for (int k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++) + cout << rml.get_move_pv(j, k) << " "; + + cout << endl; + } + alpha = rml.get_move_score(Min(i, MultiPV - 1)); } - alpha = rml.get_move_score(Min(i, MultiPV-1)); - } - } // PV move or new best move + } // PV move or new best move - assert(alpha >= oldAlpha); + assert(alpha >= oldAlpha); - FailLow = (alpha == oldAlpha); - } + AspirationFailLow = (alpha == oldAlpha); - if (AbortSearch || alpha > oldAlpha) - break; // End search, we are not failing low + if (AspirationFailLow && StopOnPonderhit) + StopOnPonderhit = false; + } - // Prepare for research - researchCount++; - alpha = Max(alpha - AspirationDelta * (1 << researchCount), -VALUE_INFINITE); - oldAlpha = alpha; + // Can we exit fail low loop ? + if (AbortSearch || alpha > oldAlpha) + break; + + // Prepare for a research after a fail low, each time with a wider window + researchCount++; + alpha = Max(alpha - AspirationDelta * (1 << researchCount), -VALUE_INFINITE); + oldAlpha = alpha; } // Fail low loop @@ -1188,54 +1014,67 @@ namespace { assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); assert(beta > alpha && beta <= VALUE_INFINITE); assert(ply >= 0 && ply < PLY_MAX); - assert(threadID >= 0 && threadID < ActiveThreads); + assert(threadID >= 0 && threadID < TM.active_threads()); Move movesSearched[256]; + EvalInfo ei; StateInfo st; const TTEntry* tte; Move ttMove, move; Depth ext, newDepth; - Value oldAlpha, value; - bool isCheck, mateThreat, singleEvasion, moveIsCheck, captureOrPromotion, dangerous; + Value bestValue, value, oldAlpha; + bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous; + bool mateThreat = false; int moveCount = 0; - Value bestValue = value = -VALUE_INFINITE; + bestValue = value = -VALUE_INFINITE; if (depth < OnePly) return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID); - // Initialize, and make an early exit in case of an aborted search, - // an instant draw, maximum ply reached, etc. + // Step 1. Initialize node and poll + // Polling can abort search. init_node(ss, ply, threadID); - // After init_node() that calls poll() - if (AbortSearch || thread_should_stop(threadID)) + // Step 2. Check for aborted search and immediate draw + if (AbortSearch || TM.thread_should_stop(threadID)) return Value(0); if (pos.is_draw() || ply >= PLY_MAX - 1) return VALUE_DRAW; - // Mate distance pruning + // Step 3. Mate distance pruning oldAlpha = alpha; alpha = Max(value_mated_in(ply), alpha); beta = Min(value_mate_in(ply+1), beta); if (alpha >= beta) return alpha; - // Transposition table lookup. At PV nodes, we don't use the TT for - // pruning, but only for move ordering. This is to avoid problems in - // the following areas: + // Step 4. Transposition table lookup + // At PV nodes, we don't use the TT for pruning, but only for move ordering. + // This is to avoid problems in the following areas: // // * Repetition draw detection // * Fifty move rule detection // * Searching for a mate // * Printing of full PV line - // tte = TT.retrieve(pos.get_key()); ttMove = (tte ? tte->move() : MOVE_NONE); - // Go with internal iterative deepening if we don't have a TT move - if ( UseIIDAtPVNodes - && depth >= 5*OnePly + // Step 5. Evaluate the position statically + // At PV nodes we do this only to update gain statistics + isCheck = pos.is_check(); + if (!isCheck) + { + ss[ply].eval = evaluate(pos, ei, threadID); + update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval); + } + + // Step 6. Razoring (is omitted in PV nodes) + // Step 7. Static null move pruning (is omitted in PV nodes) + // Step 8. Null move search with verification search (is omitted in PV nodes) + + // Step 9. Internal iterative deepening + if ( depth >= IIDDepthAtPVNodes && ttMove == MOVE_NONE) { search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID); @@ -1243,31 +1082,17 @@ namespace { tte = TT.retrieve(pos.get_key()); } - isCheck = pos.is_check(); - if (!isCheck) - { - // Update gain statistics of the previous move that lead - // us in this position. - EvalInfo ei; - ss[ply].eval = evaluate(pos, ei, threadID); - update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval); - } + // Step 10. Loop through moves + // Loop through all legal moves until no moves remain or a beta cutoff occurs - // Initialize a MovePicker object for the current position, and prepare - // to search all moves + // Initialize a MovePicker object for the current position mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move())); - CheckInfo ci(pos); MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); + CheckInfo ci(pos); - // Precalculate reduction parameters - float LogLimit, Gradient, BaseReduction = 0.5; - reduction_parameters(BaseReduction, 6.0, depth, LogLimit, Gradient); - - // Loop through all legal moves until no moves remain or a beta cutoff - // occurs. while ( alpha < beta && (move = mp.get_next_move()) != MOVE_NONE - && !thread_should_stop(threadID)) + && !TM.thread_should_stop(threadID)) { assert(move_is_ok(move)); @@ -1275,13 +1100,13 @@ namespace { moveIsCheck = pos.move_is_check(move, ci); captureOrPromotion = pos.move_is_capture_or_promotion(move); - // Decide the new search depth + // Step 11. Decide the new search depth ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous); // Singular extension search. We extend the TT move if its value is much better than // its siblings. To verify this we do a reduced search on all the other moves but the // ttMove, if result is lower then ttValue minus a margin then we extend ttMove. - if ( depth >= 6 * OnePly + if ( depth >= SingularExtensionDepthAtPVNodes && tte && move == tte->move() && ext < OnePly @@ -1292,36 +1117,40 @@ namespace { if (abs(ttValue) < VALUE_KNOWN_WIN) { - Value excValue = search(pos, ss, ttValue - SingleReplyMargin, depth / 2, ply, false, threadID, move); + Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move); - if (excValue < ttValue - SingleReplyMargin) + if (excValue < ttValue - SingularExtensionMargin) ext = OnePly; } } newDepth = depth - OnePly + ext; - // Update current move + // Update current move (this must be done after singular extension search) movesSearched[moveCount++] = ss[ply].currentMove = move; - // Make and search the move + // Step 12. Futility pruning (is omitted in PV nodes) + + // Step 13. Make the move pos.do_move(move, st, ci, moveIsCheck); - if (moveCount == 1) // The first move in list is the PV + // Step extra. pv search (only in PV nodes) + // The first move in list is the expected PV + if (moveCount == 1) value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID); else { - // Try to reduce non-pv search depth by one ply if move seems not problematic, + // Step 14. Reduced search // if the move fails high will be re-searched at full depth. bool doFullDepthSearch = true; - if ( depth >= 3*OnePly + if ( depth >= 3 * OnePly && !dangerous && !captureOrPromotion && !move_is_castle(move) && !move_is_killer(move, ss[ply])) - { - ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); + { + ss[ply].reduction = pv_reduction(depth, moveCount); if (ss[ply].reduction) { value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID); @@ -1329,31 +1158,24 @@ namespace { } } - if (doFullDepthSearch) // Go with full depth non-pv search + // Step 15. Full depth search + if (doFullDepthSearch) { ss[ply].reduction = Depth(0); value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID); + + // Step extra. pv search (only in PV nodes) if (value > alpha && value < beta) - { - // When the search fails high at ply 1 while searching the first - // move at the root, set the flag failHighPly1. This is used for - // time managment: We don't want to stop the search early in - // such cases, because resolving the fail high at ply 1 could - // result in a big drop in score at the root. - if (ply == 1 && RootMoveNumber == 1) - Threads[threadID].failHighPly1 = true; - - // A fail high occurred. Re-search at full window (pv search) value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID); - Threads[threadID].failHighPly1 = false; - } } } + + // Step 16. Undo move pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // New best move? + // Step 17. Check for new best move if (value > bestValue) { bestValue = value; @@ -1364,36 +1186,31 @@ namespace { if (value == value_mate_in(ply + 1)) ss[ply].mateKiller = move; } - // If we are at ply 1, and we are searching the first root move at - // ply 0, set the 'Problem' variable if the score has dropped a lot - // (from the computer's point of view) since the previous iteration. - if ( ply == 1 - && Iteration >= 2 - && -value <= IterationInfo[Iteration-1].value - ProblemMargin) - Problem = true; } - // Split? - if ( ActiveThreads > 1 + // Step 18. Check for split + if ( TM.active_threads() > 1 && bestValue < beta && depth >= MinimumSplitDepth && Iteration <= 99 - && idle_thread_exists(threadID) + && TM.available_thread_exists(threadID) && !AbortSearch - && !thread_should_stop(threadID) - && split(pos, ss, ply, &alpha, &beta, &bestValue, VALUE_NONE, - depth, &moveCount, &mp, threadID, true)) + && !TM.thread_should_stop(threadID) + && TM.split(pos, ss, ply, &alpha, beta, &bestValue, + depth, &moveCount, &mp, threadID, true)) break; } - // All legal moves have been searched. A special case: If there were + // Step 19. Check for mate and stalemate + // All legal moves have been searched and if there were // no legal moves, it must be mate or stalemate. if (moveCount == 0) return (isCheck ? value_mated_in(ply) : VALUE_DRAW); + // Step 20. Update tables // If the search is not aborted, update the transposition table, // history counters, and killer moves. - if (AbortSearch || thread_should_stop(threadID)) + if (AbortSearch || TM.thread_should_stop(threadID)) return bestValue; if (bestValue <= oldAlpha) @@ -1401,7 +1218,7 @@ namespace { else if (bestValue >= beta) { - BetaCounter.add(pos.side_to_move(), depth, threadID); + TM.incrementBetaCounter(pos.side_to_move(), depth, threadID); move = ss[ply].pv[ply]; if (!pos.move_is_capture_or_promotion(move)) { @@ -1424,7 +1241,7 @@ namespace { assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE); assert(ply >= 0 && ply < PLY_MAX); - assert(threadID >= 0 && threadID < ActiveThreads); + assert(threadID >= 0 && threadID < TM.active_threads()); Move movesSearched[256]; EvalInfo ei; @@ -1432,38 +1249,39 @@ namespace { const TTEntry* tte; Move ttMove, move; Depth ext, newDepth; - Value bestValue, staticValue, nullValue, value, futilityValue, futilityValueScaled; + Value bestValue, refinedValue, nullValue, value, futilityValueScaled; bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous; bool mateThreat = false; int moveCount = 0; - futilityValue = staticValue = bestValue = value = -VALUE_INFINITE; + refinedValue = bestValue = value = -VALUE_INFINITE; if (depth < OnePly) return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID); - // Initialize, and make an early exit in case of an aborted search, - // an instant draw, maximum ply reached, etc. + // Step 1. Initialize node and poll + // Polling can abort search. init_node(ss, ply, threadID); - // After init_node() that calls poll() - if (AbortSearch || thread_should_stop(threadID)) + // Step 2. Check for aborted search and immediate draw + if (AbortSearch || TM.thread_should_stop(threadID)) return Value(0); if (pos.is_draw() || ply >= PLY_MAX - 1) return VALUE_DRAW; - // Mate distance pruning + // Step 3. Mate distance pruning if (value_mated_in(ply) >= beta) return beta; if (value_mate_in(ply + 1) < beta) return beta - 1; + // Step 4. Transposition table lookup + // We don't want the score of a partial search to overwrite a previous full search - // TT value, so we use a different position key in case of an excluded move exsists. + // TT value, so we use a different position key in case of an excluded move exists. Key posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key(); - // Transposition table lookup tte = TT.retrieve(posKey); ttMove = (tte ? tte->move() : MOVE_NONE); @@ -1473,43 +1291,54 @@ namespace { return value_from_tt(tte->value(), ply); } + // Step 5. Evaluate the position statically isCheck = pos.is_check(); - // Calculate depth dependant futility pruning parameters - const int FutilityMoveCountMargin = 3 + (1 << (3 * int(depth) / 8)); - - // Evaluate the position statically if (!isCheck) { if (tte && (tte->type() & VALUE_TYPE_EVAL)) - staticValue = value_from_tt(tte->value(), ply); + ss[ply].eval = value_from_tt(tte->value(), ply); else - { - staticValue = evaluate(pos, ei, threadID); - ss[ply].evalInfo = &ei; - } + ss[ply].eval = evaluate(pos, ei, threadID); - ss[ply].eval = staticValue; - futilityValue = staticValue + FutilityMargins[int(depth)]; //FIXME: Remove me, only for split - staticValue = refine_eval(tte, staticValue, ply); // Enhance accuracy with TT value if possible + refinedValue = refine_eval(tte, ss[ply].eval, ply); // Enhance accuracy with TT value if possible update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval); } - // Do a "stand pat". If we are above beta by a good margin then - // return immediately. - if ( !isCheck - && allowNullmove + // Step 6. Razoring + if ( !value_is_mate(beta) + && !isCheck && depth < RazorDepth - && staticValue - FutilityMargins[int(depth)] >= beta) - return staticValue - FutilityMargins[int(depth)]; - - // Null move search - if ( allowNullmove + && refinedValue < beta - razor_margin(depth) + && ss[ply - 1].currentMove != MOVE_NULL + && ttMove == MOVE_NONE + && !pos.has_pawn_on_7th(pos.side_to_move())) + { + Value rbeta = beta - razor_margin(depth); + Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID); + if (v < rbeta) + return v; //FIXME: Logically should be: return (v + razor_margin(depth)); + } + + // Step 7. Static null move pruning + // We're betting that the opponent doesn't have a move that will reduce + // the score by more than fuility_margin(depth) if we do a null move. + if ( !isCheck + && allowNullmove + && depth < RazorDepth + && refinedValue - futility_margin(depth, 0) >= beta) + return refinedValue - futility_margin(depth, 0); + + // Step 8. Null move search with verification search + // When we jump directly to qsearch() we do a null move only if static value is + // at least beta. Otherwise we do a null move if static value is not more than + // NullMoveMargin under beta. + if ( allowNullmove && depth > OnePly && !isCheck && !value_is_mate(beta) && ok_to_do_nullmove(pos) - && staticValue >= beta - NullMoveMargin) + && refinedValue >= beta - (depth >= 4 * OnePly ? NullMoveMargin : 0)) { ss[ply].currentMove = MOVE_NULL; @@ -1519,7 +1348,7 @@ namespace { int R = 3 + (depth >= 5 * OnePly ? depth / 8 : 0); // Null move dynamic reduction based on value - if (staticValue - beta > PawnValueMidgame) + if (refinedValue - beta > PawnValueMidgame) R++; nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID); @@ -1552,43 +1381,28 @@ namespace { return beta - 1; } } - // Null move search not allowed, try razoring - else if ( !value_is_mate(beta) - && !isCheck - && depth < RazorDepth - && staticValue < beta - (NullMoveMargin + 16 * depth) - && ss[ply - 1].currentMove != MOVE_NULL - && ttMove == MOVE_NONE - && !pos.has_pawn_on_7th(pos.side_to_move())) - { - Value rbeta = beta - (NullMoveMargin + 16 * depth); - Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID); - if (v < rbeta) - return v; - } - // Go with internal iterative deepening if we don't have a TT move - if (UseIIDAtNonPVNodes && ttMove == MOVE_NONE && depth >= 8*OnePly && - !isCheck && ss[ply].eval >= beta - IIDMargin) + // Step 9. Internal iterative deepening + if ( depth >= IIDDepthAtNonPVNodes + && ttMove == MOVE_NONE + && !isCheck + && ss[ply].eval >= beta - IIDMargin) { - search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID); + search(pos, ss, beta, depth/2, ply, false, threadID); ttMove = ss[ply].pv[ply]; - tte = TT.retrieve(pos.get_key()); + tte = TT.retrieve(posKey); } - // Initialize a MovePicker object for the current position, and prepare - // to search all moves. - MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); - CheckInfo ci(pos); + // Step 10. Loop through moves + // Loop through all legal moves until no moves remain or a beta cutoff occurs - // Precalculate reduction parameters - float LogLimit, Gradient, BaseReduction = 0.5; - reduction_parameters(BaseReduction, 3.0, depth, LogLimit, Gradient); + // Initialize a MovePicker object for the current position + MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply], beta); + CheckInfo ci(pos); - // Loop through all legal moves until no moves remain or a beta cutoff occurs while ( bestValue < beta && (move = mp.get_next_move()) != MOVE_NONE - && !thread_should_stop(threadID)) + && !TM.thread_should_stop(threadID)) { assert(move_is_ok(move)); @@ -1599,13 +1413,13 @@ namespace { singleEvasion = (isCheck && mp.number_of_evasions() == 1); captureOrPromotion = pos.move_is_capture_or_promotion(move); - // Decide the new search depth + // Step 11. Decide the new search depth ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous); // Singular extension search. We extend the TT move if its value is much better than // its siblings. To verify this we do a reduced search on all the other moves but the // ttMove, if result is lower then ttValue minus a margin then we extend ttMove. - if ( depth >= 8 * OnePly + if ( depth >= SingularExtensionDepthAtNonPVNodes && tte && move == tte->move() && !excludedMove // Do not allow recursive single-reply search @@ -1617,19 +1431,19 @@ namespace { if (abs(ttValue) < VALUE_KNOWN_WIN) { - Value excValue = search(pos, ss, ttValue - SingleReplyMargin, depth / 2, ply, false, threadID, move); + Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move); - if (excValue < ttValue - SingleReplyMargin) + if (excValue < ttValue - SingularExtensionMargin) ext = OnePly; } } newDepth = depth - OnePly + ext; - // Update current move + // Update current move (this must be done after singular extension search) movesSearched[moveCount++] = ss[ply].currentMove = move; - // Futility pruning + // Step 12. Futility pruning if ( !isCheck && !dangerous && !captureOrPromotion @@ -1637,42 +1451,28 @@ namespace { && move != ttMove) { // Move count based pruning - if ( moveCount >= FutilityMoveCountMargin + if ( moveCount >= futility_move_count(depth) && ok_to_prune(pos, move, ss[ply].threatMove) && bestValue > value_mated_in(PLY_MAX)) continue; // Value based pruning - Depth predictedDepth = newDepth; + Depth predictedDepth = newDepth - nonpv_reduction(depth, moveCount); // We illogically ignore reduction condition depth >= 3*OnePly + futilityValueScaled = ss[ply].eval + futility_margin(predictedDepth, moveCount) + + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45; - //FIXME: We are ignoring condition: depth >= 3*OnePly, BUG?? - ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); - if (ss[ply].reduction) - predictedDepth -= ss[ply].reduction; - - if (predictedDepth < SelectiveDepth) + if (futilityValueScaled < beta) { - int preFutilityValueMargin = 0; - if (predictedDepth >= OnePly) - preFutilityValueMargin = FutilityMargins[int(predictedDepth)]; - - preFutilityValueMargin += H.gain(pos.piece_on(move_from(move)), move_from(move), move_to(move)) + 45; - - futilityValueScaled = ss[ply].eval + preFutilityValueMargin - moveCount * IncrementalFutilityMargin; - - if (futilityValueScaled < beta) - { - if (futilityValueScaled > bestValue) - bestValue = futilityValueScaled; - continue; - } + if (futilityValueScaled > bestValue) + bestValue = futilityValueScaled; + continue; } } - // Make and search the move + // Step 13. Make the move pos.do_move(move, st, ci, moveIsCheck); - // Try to reduce non-pv search depth by one ply if move seems not problematic, + // Step 14. Reduced search // if the move fails high will be re-searched at full depth. bool doFullDepthSearch = true; @@ -1682,7 +1482,7 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[ply])) { - ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); + ss[ply].reduction = nonpv_reduction(depth, moveCount); if (ss[ply].reduction) { value = -search(pos, ss, -(beta-1), newDepth-ss[ply].reduction, ply+1, true, threadID); @@ -1690,16 +1490,19 @@ namespace { } } - if (doFullDepthSearch) // Go with full depth non-pv search + // Step 15. Full depth search + if (doFullDepthSearch) { ss[ply].reduction = Depth(0); value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID); } + + // Step 16. Undo move pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // New best move? + // Step 17. Check for new best move if (value > bestValue) { bestValue = value; @@ -1710,34 +1513,37 @@ namespace { ss[ply].mateKiller = move; } - // Split? - if ( ActiveThreads > 1 + // Step 18. Check for split + if ( TM.active_threads() > 1 && bestValue < beta && depth >= MinimumSplitDepth && Iteration <= 99 - && idle_thread_exists(threadID) + && TM.available_thread_exists(threadID) && !AbortSearch - && !thread_should_stop(threadID) - && split(pos, ss, ply, &beta, &beta, &bestValue, futilityValue, //FIXME: SMP & futilityValue - depth, &moveCount, &mp, threadID, false)) + && !TM.thread_should_stop(threadID) + && TM.split(pos, ss, ply, NULL, beta, &bestValue, + depth, &moveCount, &mp, threadID, false)) break; } - // All legal moves have been searched. A special case: If there were + // Step 19. Check for mate and stalemate + // All legal moves have been searched and if there were // no legal moves, it must be mate or stalemate. + // If one move was excluded return fail low. if (!moveCount) return excludedMove ? beta - 1 : (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW); + // Step 20. Update tables // If the search is not aborted, update the transposition table, // history counters, and killer moves. - if (AbortSearch || thread_should_stop(threadID)) + if (AbortSearch || TM.thread_should_stop(threadID)) return bestValue; if (bestValue < beta) TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE); else { - BetaCounter.add(pos.side_to_move(), depth, threadID); + TM.incrementBetaCounter(pos.side_to_move(), depth, threadID); move = ss[ply].pv[ply]; TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move); if (!pos.move_is_capture_or_promotion(move)) @@ -1765,7 +1571,7 @@ namespace { assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE); assert(depth <= 0); assert(ply >= 0 && ply < PLY_MAX); - assert(threadID >= 0 && threadID < ActiveThreads); + assert(threadID >= 0 && threadID < TM.active_threads()); EvalInfo ei; StateInfo st; @@ -1782,7 +1588,7 @@ namespace { init_node(ss, ply, threadID); // After init_node() that calls poll() - if (AbortSearch || thread_should_stop(threadID)) + if (AbortSearch || TM.thread_should_stop(threadID)) return Value(0); if (pos.is_draw() || ply >= PLY_MAX - 1) @@ -1824,7 +1630,7 @@ namespace { if (bestValue >= beta) { // Store the score to avoid a future costly evaluation() call - if (!isCheck && !tte && ei.futilityMargin == 0) + if (!isCheck && !tte && ei.futilityMargin[pos.side_to_move()] == 0) TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EV_LO, Depth(-127*OnePly), MOVE_NONE); return bestValue; @@ -1843,7 +1649,7 @@ namespace { MovePicker mp = MovePicker(pos, ttMove, deepChecks ? Depth(0) : depth, H); CheckInfo ci(pos); enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame; - futilityBase = staticValue + FutilityMarginQS + ei.futilityMargin; + futilityBase = staticValue + FutilityMarginQS + ei.futilityMargin[pos.side_to_move()]; // Loop through the moves until no moves remain or a beta cutoff // occurs. @@ -1888,6 +1694,7 @@ namespace { // Don't search moves with negative SEE values if ( (!isCheck || evasionPrunable) + && !pvNode && move != ttMove && !move_is_promotion(move) && pos.see_sign(move) < 0) @@ -1923,7 +1730,7 @@ namespace { { // If bestValue isn't changed it means it is still the static evaluation // of the node, so keep this info to avoid a future evaluation() call. - ValueType type = (bestValue == staticValue && !ei.futilityMargin ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER); + ValueType type = (bestValue == staticValue && !ei.futilityMargin[pos.side_to_move()] ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER); TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE); } else if (bestValue >= beta) @@ -1951,31 +1758,32 @@ namespace { // splitting, we don't have to repeat all this work in sp_search(). We // also don't need to store anything to the hash table here: This is taken // care of after we return from the split point. + // FIXME: We are currently ignoring mateThreat flag here void sp_search(SplitPoint* sp, int threadID) { - assert(threadID >= 0 && threadID < ActiveThreads); - assert(ActiveThreads > 1); + assert(threadID >= 0 && threadID < TM.active_threads()); + assert(TM.active_threads() > 1); - Position pos(*sp->pos); - CheckInfo ci(pos); - SearchStack* ss = sp->sstack[threadID]; - Value value = -VALUE_INFINITE; + StateInfo st; Move move; + Depth ext, newDepth; + Value value, futilityValueScaled; + bool isCheck, moveIsCheck, captureOrPromotion, dangerous; int moveCount; - bool isCheck = pos.is_check(); - bool useFutilityPruning = sp->depth < SelectiveDepth - && !isCheck; + value = -VALUE_INFINITE; - const int FutilityMoveCountMargin = 3 + (1 << (3 * int(sp->depth) / 8)); + Position pos(*sp->pos); + CheckInfo ci(pos); + SearchStack* ss = sp->sstack[threadID]; + isCheck = pos.is_check(); - // Precalculate reduction parameters - float LogLimit, Gradient, BaseReduction = 0.5; - reduction_parameters(BaseReduction, 3.0, sp->depth, LogLimit, Gradient); + // Step 10. Loop through moves + // Loop through all legal moves until no moves remain or a beta cutoff occurs + lock_grab(&(sp->lock)); - while ( lock_grab_bool(&(sp->lock)) - && sp->bestValue < sp->beta - && !thread_should_stop(threadID) + while ( sp->bestValue < sp->beta + && !TM.thread_should_stop(threadID) && (move = sp->mp->get_next_move()) != MOVE_NONE) { moveCount = ++sp->moves; @@ -1983,48 +1791,50 @@ namespace { assert(move_is_ok(move)); - bool moveIsCheck = pos.move_is_check(move, ci); - bool captureOrPromotion = pos.move_is_capture_or_promotion(move); + moveIsCheck = pos.move_is_check(move, ci); + captureOrPromotion = pos.move_is_capture_or_promotion(move); + + // Step 11. Decide the new search depth + ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous); + newDepth = sp->depth - OnePly + ext; + // Update current move ss[sp->ply].currentMove = move; - // Decide the new search depth - bool dangerous; - Depth ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous); - Depth newDepth = sp->depth - OnePly + ext; - - // Prune? - if ( useFutilityPruning + // Step 12. Futility pruning + if ( !isCheck && !dangerous - && !captureOrPromotion) + && !captureOrPromotion + && !move_is_castle(move)) { // Move count based pruning - if ( moveCount >= FutilityMoveCountMargin + if ( moveCount >= futility_move_count(sp->depth) && ok_to_prune(pos, move, ss[sp->ply].threatMove) && sp->bestValue > value_mated_in(PLY_MAX)) + { + lock_grab(&(sp->lock)); continue; + } // Value based pruning - Value futilityValueScaled = sp->futilityValue - moveCount * IncrementalFutilityMargin; + Depth predictedDepth = newDepth - nonpv_reduction(sp->depth, moveCount); + futilityValueScaled = ss[sp->ply].eval + futility_margin(predictedDepth, moveCount) + + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45; if (futilityValueScaled < sp->beta) { - if (futilityValueScaled > sp->bestValue) // Less then 1% of cases - { - lock_grab(&(sp->lock)); - if (futilityValueScaled > sp->bestValue) - sp->bestValue = futilityValueScaled; - lock_release(&(sp->lock)); - } + lock_grab(&(sp->lock)); + + if (futilityValueScaled > sp->bestValue) + sp->bestValue = futilityValueScaled; continue; } } - // Make and search the move. - StateInfo st; + // Step 13. Make the move pos.do_move(move, st, ci, moveIsCheck); - // Try to reduce non-pv search depth by one ply if move seems not problematic, + // Step 14. Reduced search // if the move fails high will be re-searched at full depth. bool doFullDepthSearch = true; @@ -2033,61 +1843,44 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) { - ss[sp->ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); + ss[sp->ply].reduction = nonpv_reduction(sp->depth, moveCount); if (ss[sp->ply].reduction) { value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); - doFullDepthSearch = (value >= sp->beta); + doFullDepthSearch = (value >= sp->beta && !TM.thread_should_stop(threadID)); } } - if (doFullDepthSearch) // Go with full depth non-pv search + // Step 15. Full depth search + if (doFullDepthSearch) { ss[sp->ply].reduction = Depth(0); value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID); } + + // Step 16. Undo move pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - if (thread_should_stop(threadID)) - { - lock_grab(&(sp->lock)); - break; - } + // Step 17. Check for new best move + lock_grab(&(sp->lock)); - // New best move? - if (value > sp->bestValue) // Less then 2% of cases + if (value > sp->bestValue && !TM.thread_should_stop(threadID)) { - lock_grab(&(sp->lock)); - if (value > sp->bestValue && !thread_should_stop(threadID)) + sp->bestValue = value; + if (sp->bestValue >= sp->beta) { - sp->bestValue = value; - if (sp->bestValue >= sp->beta) - { - sp_update_pv(sp->parentSstack, ss, sp->ply); - for (int i = 0; i < ActiveThreads; i++) - if (i != threadID && (i == sp->master || sp->slaves[i])) - Threads[i].stop = true; - - sp->finished = true; - } + sp->stopRequest = true; + sp_update_pv(sp->parentSstack, ss, sp->ply); } - lock_release(&(sp->lock)); } } /* Here we have the lock still grabbed */ - // If this is the master thread and we have been asked to stop because of - // a beta cutoff higher up in the tree, stop all slave threads. - if (sp->master == threadID && thread_should_stop(threadID)) - for (int i = 0; i < ActiveThreads; i++) - if (sp->slaves[i]) - Threads[i].stop = true; - - sp->cpus--; sp->slaves[threadID] = 0; + sp->cpus--; lock_release(&(sp->lock)); } @@ -2100,26 +1893,31 @@ namespace { // don't have to repeat all this work in sp_search_pv(). We also don't // need to store anything to the hash table here: This is taken care of // after we return from the split point. + // FIXME: We are ignoring mateThreat flag! void sp_search_pv(SplitPoint* sp, int threadID) { - assert(threadID >= 0 && threadID < ActiveThreads); - assert(ActiveThreads > 1); + assert(threadID >= 0 && threadID < TM.active_threads()); + assert(TM.active_threads() > 1); + + StateInfo st; + Move move; + Depth ext, newDepth; + Value value; + bool moveIsCheck, captureOrPromotion, dangerous; + int moveCount; + value = -VALUE_INFINITE; Position pos(*sp->pos); CheckInfo ci(pos); SearchStack* ss = sp->sstack[threadID]; - Value value = -VALUE_INFINITE; - int moveCount; - Move move; - // Precalculate reduction parameters - float LogLimit, Gradient, BaseReduction = 0.5; - reduction_parameters(BaseReduction, 6.0, sp->depth, LogLimit, Gradient); + // Step 10. Loop through moves + // Loop through all legal moves until no moves remain or a beta cutoff occurs + lock_grab(&(sp->lock)); - while ( lock_grab_bool(&(sp->lock)) - && sp->alpha < sp->beta - && !thread_should_stop(threadID) + while ( sp->alpha < sp->beta + && !TM.thread_should_stop(threadID) && (move = sp->mp->get_next_move()) != MOVE_NONE) { moveCount = ++sp->moves; @@ -2127,21 +1925,22 @@ namespace { assert(move_is_ok(move)); - bool moveIsCheck = pos.move_is_check(move, ci); - bool captureOrPromotion = pos.move_is_capture_or_promotion(move); + moveIsCheck = pos.move_is_check(move, ci); + captureOrPromotion = pos.move_is_capture_or_promotion(move); + // Step 11. Decide the new search depth + ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous); + newDepth = sp->depth - OnePly + ext; + + // Update current move ss[sp->ply].currentMove = move; - // Decide the new search depth - bool dangerous; - Depth ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous); - Depth newDepth = sp->depth - OnePly + ext; + // Step 12. Futility pruning (is omitted in PV nodes) - // Make and search the move. - StateInfo st; + // Step 13. Make the move pos.do_move(move, st, ci, moveIsCheck); - // Try to reduce non-pv search depth by one ply if move seems not problematic, + // Step 14. Reduced search // if the move fails high will be re-searched at full depth. bool doFullDepthSearch = true; @@ -2150,223 +1949,66 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) { - ss[sp->ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); + ss[sp->ply].reduction = pv_reduction(sp->depth, moveCount); if (ss[sp->ply].reduction) { Value localAlpha = sp->alpha; value = -search(pos, ss, -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); - doFullDepthSearch = (value > localAlpha); + doFullDepthSearch = (value > localAlpha && !TM.thread_should_stop(threadID)); } } - if (doFullDepthSearch) // Go with full depth non-pv search + // Step 15. Full depth search + if (doFullDepthSearch) { Value localAlpha = sp->alpha; ss[sp->ply].reduction = Depth(0); value = -search(pos, ss, -localAlpha, newDepth, sp->ply+1, true, threadID); - if (value > localAlpha && value < sp->beta) + if (value > localAlpha && value < sp->beta && !TM.thread_should_stop(threadID)) { - // When the search fails high at ply 1 while searching the first - // move at the root, set the flag failHighPly1. This is used for - // time managment: We don't want to stop the search early in - // such cases, because resolving the fail high at ply 1 could - // result in a big drop in score at the root. - if (sp->ply == 1 && RootMoveNumber == 1) - Threads[threadID].failHighPly1 = true; - // If another thread has failed high then sp->alpha has been increased // to be higher or equal then beta, if so, avoid to start a PV search. localAlpha = sp->alpha; if (localAlpha < sp->beta) value = -search_pv(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, threadID); - else - assert(thread_should_stop(threadID)); - - Threads[threadID].failHighPly1 = false; - } + } } + + // Step 16. Undo move pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - if (thread_should_stop(threadID)) - { - lock_grab(&(sp->lock)); - break; - } + // Step 17. Check for new best move + lock_grab(&(sp->lock)); - // New best move? - if (value > sp->bestValue) // Less then 2% of cases + if (value > sp->bestValue && !TM.thread_should_stop(threadID)) { - lock_grab(&(sp->lock)); - if (value > sp->bestValue && !thread_should_stop(threadID)) + sp->bestValue = value; + if (value > sp->alpha) { - sp->bestValue = value; - if (value > sp->alpha) - { - // Ask threads to stop before to modify sp->alpha - if (value >= sp->beta) - { - for (int i = 0; i < ActiveThreads; i++) - if (i != threadID && (i == sp->master || sp->slaves[i])) - Threads[i].stop = true; - - sp->finished = true; - } - - sp->alpha = value; - - sp_update_pv(sp->parentSstack, ss, sp->ply); - if (value == value_mate_in(sp->ply + 1)) - ss[sp->ply].mateKiller = move; - } - // If we are at ply 1, and we are searching the first root move at - // ply 0, set the 'Problem' variable if the score has dropped a lot - // (from the computer's point of view) since the previous iteration. - if ( sp->ply == 1 - && Iteration >= 2 - && -value <= IterationInfo[Iteration-1].value - ProblemMargin) - Problem = true; + // Ask threads to stop before to modify sp->alpha + if (value >= sp->beta) + sp->stopRequest = true; + + sp->alpha = value; + + sp_update_pv(sp->parentSstack, ss, sp->ply); + if (value == value_mate_in(sp->ply + 1)) + ss[sp->ply].mateKiller = move; } - lock_release(&(sp->lock)); } } /* Here we have the lock still grabbed */ - // If this is the master thread and we have been asked to stop because of - // a beta cutoff higher up in the tree, stop all slave threads. - if (sp->master == threadID && thread_should_stop(threadID)) - for (int i = 0; i < ActiveThreads; i++) - if (sp->slaves[i]) - Threads[i].stop = true; - - sp->cpus--; sp->slaves[threadID] = 0; + sp->cpus--; lock_release(&(sp->lock)); } - /// The BetaCounterType class - - BetaCounterType::BetaCounterType() { clear(); } - - void BetaCounterType::clear() { - - for (int i = 0; i < THREAD_MAX; i++) - Threads[i].betaCutOffs[WHITE] = Threads[i].betaCutOffs[BLACK] = 0ULL; - } - - void BetaCounterType::add(Color us, Depth d, int threadID) { - - // Weighted count based on depth - Threads[threadID].betaCutOffs[us] += unsigned(d); - } - - void BetaCounterType::read(Color us, int64_t& our, int64_t& their) { - - our = their = 0UL; - for (int i = 0; i < THREAD_MAX; i++) - { - our += Threads[i].betaCutOffs[us]; - their += Threads[i].betaCutOffs[opposite_color(us)]; - } - } - - - /// The RootMoveList class - - // RootMoveList c'tor - - RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) { - - MoveStack mlist[MaxRootMoves]; - bool includeAllMoves = (searchMoves[0] == MOVE_NONE); - - // Generate all legal moves - MoveStack* last = generate_moves(pos, mlist); - - // Add each move to the moves[] array - for (MoveStack* cur = mlist; cur != last; cur++) - { - bool includeMove = includeAllMoves; - - for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++) - includeMove = (searchMoves[k] == cur->move); - - if (!includeMove) - continue; - - // Find a quick score for the move - StateInfo st; - SearchStack ss[PLY_MAX_PLUS_2]; - init_ss_array(ss); - - moves[count].move = cur->move; - pos.do_move(moves[count].move, st); - moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0); - pos.undo_move(moves[count].move); - moves[count].pv[0] = moves[count].move; - moves[count].pv[1] = MOVE_NONE; - count++; - } - sort(); - } - - - // RootMoveList simple methods definitions - - void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) { - - moves[moveNum].nodes = nodes; - moves[moveNum].cumulativeNodes += nodes; - } - - void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) { - - moves[moveNum].ourBeta = our; - moves[moveNum].theirBeta = their; - } - - void RootMoveList::set_move_pv(int moveNum, const Move pv[]) { - - int j; - - for (j = 0; pv[j] != MOVE_NONE; j++) - moves[moveNum].pv[j] = pv[j]; - - moves[moveNum].pv[j] = MOVE_NONE; - } - - - // RootMoveList::sort() sorts the root move list at the beginning of a new - // iteration. - - void RootMoveList::sort() { - - sort_multipv(count - 1); // Sort all items - } - - - // RootMoveList::sort_multipv() sorts the first few moves in the root move - // list by their scores and depths. It is used to order the different PVs - // correctly in MultiPV mode. - - void RootMoveList::sort_multipv(int n) { - - int i,j; - - for (i = 1; i <= n; i++) - { - RootMove rm = moves[i]; - for (j = i; j > 0 && moves[j - 1] < rm; j--) - moves[j] = moves[j - 1]; - - moves[j] = rm; - } - } - // init_node() is called at the beginning of all the search functions // (search(), search_pv(), qsearch(), and so on) and initializes the @@ -2377,24 +2019,21 @@ namespace { void init_node(SearchStack ss[], int ply, int threadID) { assert(ply >= 0 && ply < PLY_MAX); - assert(threadID >= 0 && threadID < ActiveThreads); + assert(threadID >= 0 && threadID < TM.active_threads()); - Threads[threadID].nodes++; + TM.incrementNodeCounter(threadID); if (threadID == 0) { NodesSincePoll++; if (NodesSincePoll >= NodesBetweenPolls) { - poll(); + poll(ss, ply); NodesSincePoll = 0; } } ss[ply].init(ply); ss[ply + 2].initKillers(); - - if (Threads[threadID].printCurrentLine) - print_current_line(ss, ply, threadID); } @@ -2678,34 +2317,6 @@ namespace { } - // reduction_parameters() precalculates some parameters used later by reduction. Becasue - // floating point operations are involved we try to recalculate reduction at each move, but - // we do the most consuming computation only once per node. - - void reduction_parameters(float baseReduction, float reductionInhibitor, Depth depth, float& logLimit, float& gradient) - { - // Precalculate some parameters to avoid to calculate the following formula for each move: - // - // red = baseReduction + ln(moveCount) * ln(depth / 2) / reductionInhibitor; - // - logLimit = depth > OnePly ? (1 - baseReduction) * reductionInhibitor / ln(depth / 2) : 1000; - gradient = depth > OnePly ? ln(depth / 2) / reductionInhibitor : 0; - } - - - // reduction() returns reduction in plies based on moveCount and depth. - // Reduction is always at least one ply. - - Depth reduction(int moveCount, float logLimit, float baseReduction, float gradient) { - - if (ln(moveCount) < logLimit) - return Depth(0); - - float red = baseReduction + ln(moveCount) * gradient; - return Depth(int(floor(red * int(OnePly)))); - } - - // update_history() registers a good move that produced a beta-cutoff // in history and marks as failures all the other moves of that ply. @@ -2754,21 +2365,7 @@ namespace { && pos.captured_piece() == NO_PIECE_TYPE && !move_is_castle(m) && !move_is_promotion(m)) - H.set_gain(pos.piece_on(move_to(m)), move_from(m), move_to(m), -(before + after)); - } - - - // fail_high_ply_1() checks if some thread is currently resolving a fail - // high at ply 1 at the node below the first root node. This information - // is used for time management. - - bool fail_high_ply_1() { - - for (int i = 0; i < ActiveThreads; i++) - if (Threads[i].failHighPly1) - return true; - - return false; + H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after)); } @@ -2786,7 +2383,7 @@ namespace { int nps() { int t = current_search_time(); - return (t > 0 ? int((nodes_searched() * 1000) / t) : 0); + return (t > 0 ? int((TM.nodes_searched() * 1000) / t) : 0); } @@ -2794,7 +2391,7 @@ namespace { // looks at the time consumed so far and decides if it's time to abort the // search. - void poll() { + void poll(SearchStack ss[], int ply) { static int lastInfoTime; int t = current_search_time(); @@ -2836,7 +2433,6 @@ namespace { else if (t - lastInfoTime >= 1000) { lastInfoTime = t; - lock_grab(&IOLock); if (dbg_show_mean) dbg_print_mean(); @@ -2844,13 +2440,18 @@ namespace { if (dbg_show_hit_rate) dbg_print_hit_rate(); - cout << "info nodes " << nodes_searched() << " nps " << nps() + cout << "info nodes " << TM.nodes_searched() << " nps " << nps() << " time " << t << " hashfull " << TT.full() << endl; - lock_release(&IOLock); + // We only support current line printing in single thread mode + if (ShowCurrentLine && TM.active_threads() == 1) + { + cout << "info currline"; + for (int p = 0; p < ply; p++) + cout << " " << ss[p].currentMove; - if (ShowCurrentLine) - Threads[0].printCurrentLine = true; + cout << endl; + } } // Should we stop the search? @@ -2858,22 +2459,15 @@ namespace { return; bool stillAtFirstMove = RootMoveNumber == 1 - && !FailLow + && !AspirationFailLow && t > MaxSearchTime + ExtraSearchTime; - bool noProblemFound = !FailHigh - && !FailLow - && !fail_high_ply_1() - && !Problem - && t > 6 * (MaxSearchTime + ExtraSearchTime); - bool noMoreTime = t > AbsoluteMaxSearchTime - || stillAtFirstMove //FIXME: We are not checking any problem flags, BUG? - || noProblemFound; + || stillAtFirstMove; if ( (Iteration >= 3 && UseTimeManagement && noMoreTime) || (ExactMaxTime && t >= ExactMaxTime) - || (Iteration >= 3 && MaxNodes && nodes_searched() >= MaxNodes)) + || (Iteration >= 3 && MaxNodes && TM.nodes_searched() >= MaxNodes)) AbortSearch = true; } @@ -2888,48 +2482,17 @@ namespace { PonderSearch = false; bool stillAtFirstMove = RootMoveNumber == 1 - && !FailLow + && !AspirationFailLow && t > MaxSearchTime + ExtraSearchTime; - bool noProblemFound = !FailHigh - && !FailLow - && !fail_high_ply_1() - && !Problem - && t > 6 * (MaxSearchTime + ExtraSearchTime); - bool noMoreTime = t > AbsoluteMaxSearchTime - || stillAtFirstMove - || noProblemFound; + || stillAtFirstMove; if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit)) AbortSearch = true; } - // print_current_line() prints the current line of search for a given - // thread. Called when the UCI option UCI_ShowCurrLine is 'true'. - - void print_current_line(SearchStack ss[], int ply, int threadID) { - - assert(ply >= 0 && ply < PLY_MAX); - assert(threadID >= 0 && threadID < ActiveThreads); - - if (!Threads[threadID].idle) - { - lock_grab(&IOLock); - cout << "info currline " << (threadID + 1); - for (int p = 0; p < ply; p++) - cout << " " << ss[p].currentMove; - - cout << endl; - lock_release(&IOLock); - } - Threads[threadID].printCurrentLine = false; - if (threadID + 1 < ActiveThreads) - Threads[threadID + 1].printCurrentLine = true; - } - - // init_ss_array() does a fast reset of the first entries of a SearchStack array void init_ss_array(SearchStack ss[]) { @@ -2969,108 +2532,273 @@ namespace { } + // print_pv_info() prints to standard output and eventually to log file information on + // the current PV line. It is called at each iteration or after a new pv is found. + + void print_pv_info(const Position& pos, SearchStack ss[], Value alpha, Value beta, Value value) { + + cout << "info depth " << Iteration + << " score " << value_to_string(value) + << ((value >= beta) ? " lowerbound" : + ((value <= alpha)? " upperbound" : "")) + << " time " << current_search_time() + << " nodes " << TM.nodes_searched() + << " nps " << nps() + << " pv "; + + for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++) + cout << ss[0].pv[j] << " "; + + cout << endl; + + if (UseLogFile) + { + ValueType type = (value >= beta ? VALUE_TYPE_LOWER + : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT)); + + LogFile << pretty_pv(pos, current_search_time(), Iteration, + TM.nodes_searched(), value, type, ss[0].pv) << endl; + } + } + + + // init_thread() is the function which is called when a new thread is + // launched. It simply calls the idle_loop() function with the supplied + // threadID. There are two versions of this function; one for POSIX + // threads and one for Windows threads. + +#if !defined(_MSC_VER) + + void* init_thread(void *threadID) { + + TM.idle_loop(*(int*)threadID, NULL); + return NULL; + } + +#else + + DWORD WINAPI init_thread(LPVOID threadID) { + + TM.idle_loop(*(int*)threadID, NULL); + return 0; + } + +#endif + + + /// The ThreadsManager class + + // resetNodeCounters(), resetBetaCounters(), searched_nodes() and + // get_beta_counters() are getters/setters for the per thread + // counters used to sort the moves at root. + + void ThreadsManager::resetNodeCounters() { + + for (int i = 0; i < MAX_THREADS; i++) + threads[i].nodes = 0ULL; + } + + void ThreadsManager::resetBetaCounters() { + + for (int i = 0; i < MAX_THREADS; i++) + threads[i].betaCutOffs[WHITE] = threads[i].betaCutOffs[BLACK] = 0ULL; + } + + int64_t ThreadsManager::nodes_searched() const { + + int64_t result = 0ULL; + for (int i = 0; i < ActiveThreads; i++) + result += threads[i].nodes; + + return result; + } + + void ThreadsManager::get_beta_counters(Color us, int64_t& our, int64_t& their) const { + + our = their = 0UL; + for (int i = 0; i < MAX_THREADS; i++) + { + our += threads[i].betaCutOffs[us]; + their += threads[i].betaCutOffs[opposite_color(us)]; + } + } + + // idle_loop() is where the threads are parked when they have no work to do. // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint // object for which the current thread is the master. - void idle_loop(int threadID, SplitPoint* waitSp) { - - assert(threadID >= 0 && threadID < THREAD_MAX); + void ThreadsManager::idle_loop(int threadID, SplitPoint* waitSp) { - Threads[threadID].running = true; + assert(threadID >= 0 && threadID < MAX_THREADS); while (true) { - if (AllThreadsShouldExit && threadID != 0) - break; + // Slave threads can exit as soon as AllThreadsShouldExit raises, + // master should exit as last one. + if (AllThreadsShouldExit) + { + assert(!waitSp); + threads[threadID].state = THREAD_TERMINATED; + return; + } // If we are not thinking, wait for a condition to be signaled // instead of wasting CPU time polling for work. - while (threadID != 0 && (Idle || threadID >= ActiveThreads)) + while (AllThreadsShouldSleep || threadID >= ActiveThreads) { + assert(!waitSp); + assert(threadID != 0); + threads[threadID].state = THREAD_SLEEPING; #if !defined(_MSC_VER) - pthread_mutex_lock(&WaitLock); - if (Idle || threadID >= ActiveThreads) + lock_grab(&WaitLock); + if (AllThreadsShouldSleep || threadID >= ActiveThreads) pthread_cond_wait(&WaitCond, &WaitLock); - - pthread_mutex_unlock(&WaitLock); + lock_release(&WaitLock); #else WaitForSingleObject(SitIdleEvent[threadID], INFINITE); #endif } - // If this thread has been assigned work, launch a search - if (Threads[threadID].workIsWaiting) - { - assert(!Threads[threadID].idle); + // If thread has just woken up, mark it as available + if (threads[threadID].state == THREAD_SLEEPING) + threads[threadID].state = THREAD_AVAILABLE; - Threads[threadID].workIsWaiting = false; - if (Threads[threadID].splitPoint->pvNode) - sp_search_pv(Threads[threadID].splitPoint, threadID); - else - sp_search(Threads[threadID].splitPoint, threadID); + // If this thread has been assigned work, launch a search + if (threads[threadID].state == THREAD_WORKISWAITING) + { + assert(!AllThreadsShouldExit && !AllThreadsShouldSleep); - Threads[threadID].idle = true; - } + threads[threadID].state = THREAD_SEARCHING; - // If this thread is the master of a split point and all threads have - // finished their work at this split point, return from the idle loop. - if (waitSp != NULL && waitSp->cpus == 0) - return; - } + if (threads[threadID].splitPoint->pvNode) + sp_search_pv(threads[threadID].splitPoint, threadID); + else + sp_search(threads[threadID].splitPoint, threadID); - Threads[threadID].running = false; + assert(threads[threadID].state == THREAD_SEARCHING); + + threads[threadID].state = THREAD_AVAILABLE; + } + + // If this thread is the master of a split point and all threads have + // finished their work at this split point, return from the idle loop. + if (waitSp != NULL && waitSp->cpus == 0) + { + assert(threads[threadID].state == THREAD_AVAILABLE); + + threads[threadID].state = THREAD_SEARCHING; + return; + } + } } - // init_split_point_stack() is called during program initialization, and - // initializes all split point objects. + // init_threads() is called during startup. It launches all helper threads, + // and initializes the split point stack and the global locks and condition + // objects. + + void ThreadsManager::init_threads() { + + volatile int i; + bool ok; + +#if !defined(_MSC_VER) + pthread_t pthread[1]; +#endif + + // Initialize global locks + lock_init(&MPLock, NULL); + lock_init(&WaitLock, NULL); - void init_split_point_stack() { +#if !defined(_MSC_VER) + pthread_cond_init(&WaitCond, NULL); +#else + for (i = 0; i < MAX_THREADS; i++) + SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0); +#endif - for (int i = 0; i < THREAD_MAX; i++) + // Initialize SplitPointStack locks + for (i = 0; i < MAX_THREADS; i++) for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++) { SplitPointStack[i][j].parent = NULL; lock_init(&(SplitPointStack[i][j].lock), NULL); } + + // Will be set just before program exits to properly end the threads + AllThreadsShouldExit = false; + + // Threads will be put to sleep as soon as created + AllThreadsShouldSleep = true; + + // All threads except the main thread should be initialized to THREAD_AVAILABLE + ActiveThreads = 1; + threads[0].state = THREAD_SEARCHING; + for (i = 1; i < MAX_THREADS; i++) + threads[i].state = THREAD_AVAILABLE; + + // Launch the helper threads + for (i = 1; i < MAX_THREADS; i++) + { + +#if !defined(_MSC_VER) + ok = (pthread_create(pthread, NULL, init_thread, (void*)(&i)) == 0); +#else + ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, NULL) != NULL); +#endif + + if (!ok) + { + cout << "Failed to create thread number " << i << endl; + Application::exit_with_failure(); + } + + // Wait until the thread has finished launching and is gone to sleep + while (threads[i].state != THREAD_SLEEPING); + } } - // destroy_split_point_stack() is called when the program exits, and - // destroys all locks in the precomputed split point objects. + // exit_threads() is called when the program exits. It makes all the + // helper threads exit cleanly. + + void ThreadsManager::exit_threads() { + + ActiveThreads = MAX_THREADS; // HACK + AllThreadsShouldSleep = true; // HACK + wake_sleeping_threads(); + + // This makes the threads to exit idle_loop() + AllThreadsShouldExit = true; - void destroy_split_point_stack() { + // Wait for thread termination + for (int i = 1; i < MAX_THREADS; i++) + while (threads[i].state != THREAD_TERMINATED); - for (int i = 0; i < THREAD_MAX; i++) + // Now we can safely destroy the locks + for (int i = 0; i < MAX_THREADS; i++) for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++) lock_destroy(&(SplitPointStack[i][j].lock)); + + lock_destroy(&WaitLock); + lock_destroy(&MPLock); } - // thread_should_stop() checks whether the thread with a given threadID has - // been asked to stop, directly or indirectly. This can happen if a beta - // cutoff has occurred in the thread's currently active split point, or in - // some ancestor of the current split point. + // thread_should_stop() checks whether the thread should stop its search. + // This can happen if a beta cutoff has occurred in the thread's currently + // active split point, or in some ancestor of the current split point. - bool thread_should_stop(int threadID) { + bool ThreadsManager::thread_should_stop(int threadID) const { assert(threadID >= 0 && threadID < ActiveThreads); SplitPoint* sp; - if (Threads[threadID].stop) - return true; - if (ActiveThreads <= 2) - return false; - for (sp = Threads[threadID].splitPoint; sp != NULL; sp = sp->parent) - if (sp->finished) - { - Threads[threadID].stop = true; - return true; - } - return false; + for (sp = threads[threadID].splitPoint; sp && !sp->stopRequest; sp = sp->parent); + return sp != NULL; } @@ -3082,17 +2810,17 @@ namespace { // threads which are busy searching the split point at the top of "slave"'s // split point stack (the "helpful master concept" in YBWC terminology). - bool thread_is_available(int slave, int master) { + bool ThreadsManager::thread_is_available(int slave, int master) const { assert(slave >= 0 && slave < ActiveThreads); assert(master >= 0 && master < ActiveThreads); assert(ActiveThreads > 1); - if (!Threads[slave].idle || slave == master) + if (threads[slave].state != THREAD_AVAILABLE || slave == master) return false; // Make a local copy to be sure doesn't change under our feet - int localActiveSplitPoints = Threads[slave].activeSplitPoints; + int localActiveSplitPoints = threads[slave].activeSplitPoints; if (localActiveSplitPoints == 0) // No active split points means that the thread is available as @@ -3103,7 +2831,7 @@ namespace { return true; // Apply the "helpful master" concept if possible. Use localActiveSplitPoints - // that is known to be > 0, instead of Threads[slave].activeSplitPoints that + // that is known to be > 0, instead of threads[slave].activeSplitPoints that // could have been set to 0 by another thread leading to an out of bound access. if (SplitPointStack[slave][localActiveSplitPoints - 1].slaves[master]) return true; @@ -3112,10 +2840,10 @@ namespace { } - // idle_thread_exists() tries to find an idle thread which is available as + // available_thread_exists() tries to find an idle thread which is available as // a slave for the thread with threadID "master". - bool idle_thread_exists(int master) { + bool ThreadsManager::available_thread_exists(int master) const { assert(master >= 0 && master < ActiveThreads); assert(ActiveThreads > 1); @@ -3140,16 +2868,18 @@ namespace { // threads have returned from sp_search_pv (or, equivalently, when // splitPoint->cpus becomes 0), split() returns true. - bool split(const Position& p, SearchStack* sstck, int ply, - Value* alpha, Value* beta, Value* bestValue, const Value futilityValue, + bool ThreadsManager::split(const Position& p, SearchStack* sstck, int ply, + Value* alpha, const Value beta, Value* bestValue, Depth depth, int* moves, MovePicker* mp, int master, bool pvNode) { assert(p.is_ok()); assert(sstck != NULL); assert(ply >= 0 && ply < PLY_MAX); - assert(*bestValue >= -VALUE_INFINITE && *bestValue <= *alpha); - assert(!pvNode || *alpha < *beta); - assert(*beta <= VALUE_INFINITE); + assert(*bestValue >= -VALUE_INFINITE); + assert( ( pvNode && *bestValue <= *alpha) + || (!pvNode && *bestValue < beta )); + assert(!pvNode || *alpha < beta); + assert(beta <= VALUE_INFINITE); assert(depth > Depth(0)); assert(master >= 0 && master < ActiveThreads); assert(ActiveThreads > 1); @@ -3160,27 +2890,25 @@ namespace { // If no other thread is available to help us, or if we have too many // active split points, don't split. - if ( !idle_thread_exists(master) - || Threads[master].activeSplitPoints >= ACTIVE_SPLIT_POINTS_MAX) + if ( !available_thread_exists(master) + || threads[master].activeSplitPoints >= ACTIVE_SPLIT_POINTS_MAX) { lock_release(&MPLock); return false; } // Pick the next available split point object from the split point stack - splitPoint = SplitPointStack[master] + Threads[master].activeSplitPoints; - Threads[master].activeSplitPoints++; + splitPoint = &SplitPointStack[master][threads[master].activeSplitPoints]; // Initialize the split point object - splitPoint->parent = Threads[master].splitPoint; - splitPoint->finished = false; + splitPoint->parent = threads[master].splitPoint; + splitPoint->stopRequest = false; splitPoint->ply = ply; splitPoint->depth = depth; - splitPoint->alpha = pvNode ? *alpha : (*beta - 1); - splitPoint->beta = *beta; + splitPoint->alpha = pvNode ? *alpha : beta - 1; + splitPoint->beta = beta; splitPoint->pvNode = pvNode; splitPoint->bestValue = *bestValue; - splitPoint->futilityValue = futilityValue; splitPoint->master = master; splitPoint->mp = mp; splitPoint->moves = *moves; @@ -3190,24 +2918,25 @@ namespace { for (int i = 0; i < ActiveThreads; i++) splitPoint->slaves[i] = 0; - Threads[master].idle = false; - Threads[master].stop = false; - Threads[master].splitPoint = splitPoint; + threads[master].splitPoint = splitPoint; + threads[master].activeSplitPoints++; - // Allocate available threads setting idle flag to false + // If we are here it means we are not available + assert(threads[master].state != THREAD_AVAILABLE); + + // Allocate available threads setting state to THREAD_BOOKED for (int i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint; i++) if (thread_is_available(i, master)) { - Threads[i].idle = false; - Threads[i].stop = false; - Threads[i].splitPoint = splitPoint; + threads[i].state = THREAD_BOOKED; + threads[i].splitPoint = splitPoint; splitPoint->slaves[i] = 1; splitPoint->cpus++; } assert(splitPoint->cpus > 1); - // We can release the lock because master and slave threads are already booked + // We can release the lock because slave threads are already booked and master is not available lock_release(&MPLock); // Tell the threads that they have work to do. This will make them leave @@ -3215,13 +2944,16 @@ namespace { for (int i = 0; i < ActiveThreads; i++) if (i == master || splitPoint->slaves[i]) { - memcpy(splitPoint->sstack[i] + ply - 1, sstck + ply - 1, 3 * sizeof(SearchStack)); - Threads[i].workIsWaiting = true; // This makes the slave to exit from idle_loop() + memcpy(splitPoint->sstack[i] + ply - 1, sstck + ply - 1, 4 * sizeof(SearchStack)); + + assert(i == master || threads[i].state == THREAD_BOOKED); + + threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop() } // Everything is set up. The master thread enters the idle loop, from - // which it will instantly launch a search, because its workIsWaiting - // slot is 'true'. We send the split point as a second parameter to the + // which it will instantly launch a search, because its state is + // THREAD_WORKISWAITING. We send the split point as a second parameter to the // idle loop, which means that the main thread will return from the idle // loop when all threads have finished their work at this split point // (i.e. when splitPoint->cpus == 0). @@ -3234,12 +2966,9 @@ namespace { if (pvNode) *alpha = splitPoint->alpha; - *beta = splitPoint->beta; *bestValue = splitPoint->bestValue; - Threads[master].stop = false; - Threads[master].idle = false; - Threads[master].activeSplitPoints--; - Threads[master].splitPoint = splitPoint->parent; + threads[master].activeSplitPoints--; + threads[master].splitPoint = splitPoint->parent; lock_release(&MPLock); return true; @@ -3249,49 +2978,129 @@ namespace { // wake_sleeping_threads() wakes up all sleeping threads when it is time // to start a new search from the root. - void wake_sleeping_threads() { + void ThreadsManager::wake_sleeping_threads() { - if (ActiveThreads > 1) - { - for (int i = 1; i < ActiveThreads; i++) - { - Threads[i].idle = true; - Threads[i].workIsWaiting = false; - } + assert(AllThreadsShouldSleep); + assert(ActiveThreads > 0); + + AllThreadsShouldSleep = false; + + if (ActiveThreads == 1) + return; #if !defined(_MSC_VER) - pthread_mutex_lock(&WaitLock); - pthread_cond_broadcast(&WaitCond); - pthread_mutex_unlock(&WaitLock); + pthread_mutex_lock(&WaitLock); + pthread_cond_broadcast(&WaitCond); + pthread_mutex_unlock(&WaitLock); #else - for (int i = 1; i < THREAD_MAX; i++) - SetEvent(SitIdleEvent[i]); + for (int i = 1; i < MAX_THREADS; i++) + SetEvent(SitIdleEvent[i]); #endif + + } + + + // put_threads_to_sleep() makes all the threads go to sleep just before + // to leave think(), at the end of the search. Threads should have already + // finished the job and should be idle. + + void ThreadsManager::put_threads_to_sleep() { + + assert(!AllThreadsShouldSleep); + + // This makes the threads to go to sleep + AllThreadsShouldSleep = true; + } + + /// The RootMoveList class + + // RootMoveList c'tor + + RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) { + + SearchStack ss[PLY_MAX_PLUS_2]; + MoveStack mlist[MaxRootMoves]; + StateInfo st; + bool includeAllMoves = (searchMoves[0] == MOVE_NONE); + + // Generate all legal moves + MoveStack* last = generate_moves(pos, mlist); + + // Add each move to the moves[] array + for (MoveStack* cur = mlist; cur != last; cur++) + { + bool includeMove = includeAllMoves; + + for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++) + includeMove = (searchMoves[k] == cur->move); + + if (!includeMove) + continue; + + // Find a quick score for the move + init_ss_array(ss); + pos.do_move(cur->move, st); + moves[count].move = cur->move; + moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0); + moves[count].pv[0] = cur->move; + moves[count].pv[1] = MOVE_NONE; + pos.undo_move(cur->move); + count++; } + sort(); } - // init_thread() is the function which is called when a new thread is - // launched. It simply calls the idle_loop() function with the supplied - // threadID. There are two versions of this function; one for POSIX - // threads and one for Windows threads. + // RootMoveList simple methods definitions -#if !defined(_MSC_VER) + void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) { - void* init_thread(void *threadID) { + moves[moveNum].nodes = nodes; + moves[moveNum].cumulativeNodes += nodes; + } - idle_loop(*(int*)threadID, NULL); - return NULL; + void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) { + + moves[moveNum].ourBeta = our; + moves[moveNum].theirBeta = their; } -#else + void RootMoveList::set_move_pv(int moveNum, const Move pv[]) { - DWORD WINAPI init_thread(LPVOID threadID) { + int j; - idle_loop(*(int*)threadID, NULL); - return NULL; + for (j = 0; pv[j] != MOVE_NONE; j++) + moves[moveNum].pv[j] = pv[j]; + + moves[moveNum].pv[j] = MOVE_NONE; } -#endif -} + // RootMoveList::sort() sorts the root move list at the beginning of a new + // iteration. + + void RootMoveList::sort() { + + sort_multipv(count - 1); // Sort all items + } + + + // RootMoveList::sort_multipv() sorts the first few moves in the root move + // list by their scores and depths. It is used to order the different PVs + // correctly in MultiPV mode. + + void RootMoveList::sort_multipv(int n) { + + int i,j; + + for (i = 1; i <= n; i++) + { + RootMove rm = moves[i]; + for (j = i; j > 0 && moves[j - 1] < rm; j--) + moves[j] = moves[j - 1]; + + moves[j] = rm; + } + } + +} // namspace