X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=c369bac3a98d0f64c2336f3cab725e380bc384ed;hp=2fece7cee10cf9e3891db8afe3641d845e09ed78;hb=14dbeb22dd04f0954322a58c26833506fb4532a9;hpb=f37741cc83e620588d49bbb3a2349c9505e87f61 diff --git a/src/search.cpp b/src/search.cpp index 2fece7ce..c369bac3 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -53,43 +53,60 @@ 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; - struct BetaCounterType { +#if !defined(_MSC_VER) + pthread_cond_t WaitCond; + pthread_mutex_t WaitLock; +#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,60 +158,80 @@ namespace { }; - /// Constants + /// Adjustments - // Search depth at iteration 1 - const Depth InitialDepth = OnePly; + // Step 6. Razoring + + // Maximum depth for razoring + const Depth RazorDepth = 4 * OnePly; + + // Dynamic razoring margin based on depth + inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * d); } + + // 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); + + // Maximum depth for use of dynamic threat detection when null move fails low + const Depth ThreatDepth = 5 * OnePly; - // Depth limit for selective search - const Depth SelectiveDepth = 7 * OnePly; + // Step 9. Internal iterative deepening - // Use internal iterative deepening? - const bool UseIIDAtPVNodes = true; - const bool UseIIDAtNonPVNodes = true; + // Minimum depth for use of internal iterative deepening + const Depth IIDDepthAtPVNodes = 5 * OnePly; + const Depth IIDDepthAtNonPVNodes = 8 * OnePly; - // Internal iterative deepening margin. At Non-PV moves, when - // UseIIDAtNonPVNodes is true, we do an internal iterative deepening + // Internal iterative deepening margin. 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); - // Easy move margin. An easy move candidate must be at least this much - // better than the second best move. - const Value EasyMoveMargin = Value(0x200); - - // 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); + // Step 11. Decide the new search depth - // 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); + // 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]; - // 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); + // Minimum depth for use of singular extension + const Depth SingularExtensionDepthAtPVNodes = 6 * OnePly; + const Depth SingularExtensionDepthAtNonPVNodes = 8 * OnePly; - // If the TT move is at least SingleReplyMargin better then the + // 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); - // Each move futility margin is decreased - const Value IncrementalFutilityMargin = Value(0x8); + // Futility lookup tables (initialized at startup) and their getter functions + int32_t FutilityMarginsMatrix[14][64]; // [depth][moveNumber] + int FutilityMoveCountArray[32]; // [depth] - // Depth limit for razoring - const Depth RazorDepth = 4 * OnePly; + 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; } + + // Step 14. Reduced search - /// Variables initialized by UCI options + // Reduction lookup tables (initialized at startup) and their getter functions + int8_t PVReductionMatrix[64][64]; // [depth][moveNumber] + int8_t NonPVReductionMatrix[64][64]; // [depth][moveNumber] - // Depth limit for use of dynamic threat detection - Depth ThreatDepth; + 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)]; } + + // Step. 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; @@ -202,18 +239,19 @@ 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]; + + /// Global variables // Iteration counters 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 + int AspirationDelta; + // MultiPV mode int MultiPV; @@ -224,7 +262,7 @@ namespace { int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime; bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit; bool AbortSearch, Quit; - bool FailHigh, FailLow, Problem; + bool AspirationFailLow; // Show current line? bool ShowCurrentLine; @@ -233,27 +271,10 @@ namespace { bool UseLogFile; std::ofstream LogFile; - // Natural logarithmic lookup table and its getter function - double lnArray[512]; - inline double ln(int i) { return lnArray[i]; } - // MP related variables - int ActiveThreads = 1; 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. @@ -266,7 +287,7 @@ namespace { /// Functions Value id_loop(const Position& pos, Move searchMoves[]); - Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta); + Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta); Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID); Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE); Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID); @@ -287,27 +308,13 @@ namespace { 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(); - #if !defined(_MSC_VER) void *init_thread(void *threadID); #else @@ -321,6 +328,13 @@ 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. @@ -362,8 +376,8 @@ 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 = false; + AspirationFailLow = false; NodesSincePoll = 0; SearchStartTime = get_system_time(); ExactMaxTime = maxTime; @@ -374,7 +388,7 @@ 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()) @@ -383,16 +397,15 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_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; - } + TM.resetNodeCounters(); if (button_was_pressed("New Game")) loseOnTime = false; // Reset at the beginning of a new game @@ -423,8 +436,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, 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"); @@ -438,10 +449,10 @@ bool think(const Position& pos, bool infinite, bool ponder, int 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()); @@ -449,10 +460,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]; @@ -524,7 +532,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, @@ -547,103 +554,36 @@ 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 our logarithmic lookup table - for (i = 0; i < 512; i++) - lnArray[i] = log(double(i)); // log() returns base-e logarithm - - for (i = 0; i < THREAD_MAX; i++) - Threads[i].activeSplitPoints = 0; - - // 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; - } +/// init_search() is called during startup. It initializes various lookup tables - // 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 +void init_search() { - if (!ok) + // 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 { - cout << "Failed to create thread number " << i << endl; - Application::exit_with_failure(); + 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); } - // 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() { + // Init futility margins array + for (int i = 0; i < 14; i++) // i == depth (OnePly = 2) + for (int j = 0; j < 64; j++) // j == moveNumber + { + FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j; // FIXME: test using log instead of BSR + } - 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)); } @@ -655,7 +595,6 @@ void SearchStack::init(int ply) { currentMove = threatMove = MOVE_NONE; reduction = Depth(0); eval = VALUE_NONE; - evalInfo = NULL; } void SearchStack::initKillers() { @@ -680,6 +619,7 @@ namespace { // searchMoves 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) @@ -693,7 +633,7 @@ namespace { 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"; @@ -701,7 +641,7 @@ 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 ? @@ -725,15 +665,16 @@ namespace { // Calculate dynamic search window based on previous iterations Value alpha, beta; - if (MultiPV == 1 && Iteration >= 6 && abs(IterationInfo[Iteration - 1].value) < VALUE_KNOWN_WIN) + 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(2 * abs(prevDelta1) + abs(prevDelta2), ProblemMargin); + AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16); + AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize - alpha = Max(IterationInfo[Iteration - 1].value - delta, -VALUE_INFINITE); - beta = Min(IterationInfo[Iteration - 1].value + delta, VALUE_INFINITE); + alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE); + beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE); } else { @@ -752,39 +693,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; - - speculatedValue = Min(Max(speculatedValue, -VALUE_INFINITE), VALUE_INFINITE); - IterationInfo[Iteration] = IterationInfoType(value, speculatedValue); + ValueByIteration[Iteration] = value; // Drop the easy move if it differs from the new best move if (ss[0].pv[0] != EasyMove) EasyMove = MOVE_NONE; - Problem = false; - if (UseTimeManagement) { // Time to stop? @@ -797,15 +711,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(); + 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) @@ -845,7 +757,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; @@ -870,7 +782,7 @@ 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]); @@ -886,156 +798,118 @@ namespace { // similar to search_pv except that it uses a different move ordering // scheme and prints some information to the standard output. - Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta) { + Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta) { - Value oldAlpha = alpha; - Value value = -VALUE_INFINITE; + int64_t nodes; + Move move; + StateInfo st; + Depth depth, ext, newDepth; + Value value; CheckInfo ci(pos); + int researchCount = 0; + bool moveIsCheck, captureOrPromotion, dangerous; + Value alpha = oldAlpha; bool 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; + 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) - { - // 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(); + // Loop through all the moves in the root move list + for (int i = 0; i < rml.move_count() && !AbortSearch; i++) + { + 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; + } - // 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); + RootMoveNumber = i + 1; - if (current_search_time() >= 1000) - cout << "info currmove " << move - << " currmovenumber " << RootMoveNumber << endl; + // Save the current node count before the move is searched + nodes = TM.nodes_searched(); - // 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; + // Reset beta cut-off counters + TM.resetBetaCounters(); - // Make the move, and search it - pos.do_move(move, st, ci, moveIsCheck); + // 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 (i < MultiPV) - { - // Aspiration window is disabled in multi-pv case - if (MultiPV > 1) - alpha = -VALUE_INFINITE; + if (current_search_time() >= 1000) + cout << "info currmove " << move + << " currmovenumber " << RootMoveNumber << endl; - value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); + // 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 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); + value = - VALUE_INFINITE; - 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)) + while (1) // Fail high loop { - double red = 0.5 + ln(RootMoveNumber - MultiPV + 1) * ln(depth / 2) / 6.0; - if (red >= 1.0) - { - ss[0].reduction = Depth(int(floor(red * int(OnePly)))); - value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0); - doFullDepthSearch = (value > alpha); - } - } - if (doFullDepthSearch) - { - 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; + value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); } - } - } - - pos.undo_move(move); - - // 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; - BetaCounter.read(pos.side_to_move(), our, their); - rml.set_beta_counters(i, our, their); - rml.set_move_nodes(i, nodes_searched() - nodes); - - assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE); + 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, RootMoveNumber - MultiPV + 1); + if (ss[0].reduction) + { + value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0); + doFullDepthSearch = (value > alpha); + } + } + + if (doFullDepthSearch) + { + ss[0].reduction = Depth(0); + value = -search(pos, ss, -alpha, newDepth, 1, true, 0); + + if (value > alpha) + value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); + } + } - if (value <= alpha && i >= MultiPV) - rml.set_move_score(i, -VALUE_INFINITE); - else - { - // PV move or new best move! + pos.undo_move(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); + // Can we exit fail high loop ? + if (AbortSearch || value < beta) + break; - 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]++; + // 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 @@ -1043,7 +917,7 @@ namespace { << ((value >= beta) ? " lowerbound" : ((value <= alpha)? " upperbound" : "")) << " time " << current_search_time() - << " nodes " << nodes_searched() + << " nodes " << TM.nodes_searched() << " nps " << nps() << " pv "; @@ -1058,42 +932,119 @@ namespace { : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT)); LogFile << pretty_pv(pos, current_search_time(), Iteration, - nodes_searched(), value, type, ss[0].pv) << endl; + TM.nodes_searched(), value, type, ss[0].pv) << endl; } - 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 + // 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 { - rml.sort_multipv(i); - for (int j = 0; j < Min(MultiPV, rml.move_count()); j++) + // 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); + + if (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() + // 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 " << 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) << " "; + 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; + } + if (value > alpha) + alpha = value; } - alpha = rml.get_move_score(Min(i, MultiPV-1)); - } - } // PV move or new best move + else // MultiPV > 1 + { + 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)); + } + } // PV move or new best move - assert(alpha >= oldAlpha); + assert(alpha >= oldAlpha); + + AspirationFailLow = (alpha == oldAlpha); + + if (AspirationFailLow && StopOnPonderhit) + StopOnPonderhit = false; + } + + // 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 - FailLow = (alpha == oldAlpha); - } return alpha; } @@ -1106,54 +1057,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); @@ -1161,27 +1125,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); - // 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)); @@ -1189,13 +1143,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 @@ -1206,26 +1160,30 @@ 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; @@ -1235,40 +1193,32 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[ply])) { - double red = 0.5 + ln(moveCount) * ln(depth / 2) / 6.0; - if (red >= 1.0) - { - ss[ply].reduction = Depth(int(floor(red * int(OnePly)))); - value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID); - doFullDepthSearch = (value > alpha); - } + ss[ply].reduction = pv_reduction(depth, moveCount); + if (ss[ply].reduction) + { + value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID); + doFullDepthSearch = (value > alpha); + } } - 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; @@ -1279,36 +1229,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) @@ -1316,7 +1261,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)) { @@ -1339,7 +1284,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; @@ -1347,38 +1292,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); @@ -1388,40 +1334,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)); - const int PostFutilityValueMargin = 112 * bitScanReverse32(int(depth) * int(depth) / 2); - - // 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 + PostFutilityValueMargin; //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); } - // Post futility pruning - if (depth < SelectiveDepth && staticValue - PostFutilityValueMargin >= beta) - return (staticValue - PostFutilityValueMargin); + // Step 6. Razoring + if ( !value_is_mate(beta) + && !isCheck + && depth < RazorDepth + && 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)); + } - // Null move search + // 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; @@ -1431,7 +1391,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); @@ -1464,39 +1424,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]); + // 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 + 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)); @@ -1507,13 +1456,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 @@ -1525,42 +1474,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 for captures - Color them = opposite_color(pos.side_to_move()); - - if ( !isCheck - && newDepth < SelectiveDepth - && !dangerous - && pos.move_is_capture(move) - && !pos.move_is_check(move, ci) - && !move_is_promotion(move) - && move != ttMove - && !move_is_ep(move) - && (pos.type_of_piece_on(move_to(move)) != PAWN || !pos.pawn_is_passed(them, move_to(move)))) // Do not prune passed pawn captures - { - int preFutilityValueMargin = 0; - - if (newDepth >= OnePly) - preFutilityValueMargin = 112 * bitScanReverse32(int(newDepth) * int(newDepth) / 2); - - if (ss[ply].eval + pos.endgame_value_of_piece_on(move_to(move)) + preFutilityValueMargin + ei.futilityMargin + 90 < beta) - continue; - } - - - // Futility pruning + // Step 12. Futility pruning if ( !isCheck && !dangerous && !captureOrPromotion @@ -1568,42 +1494,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; - - //FIXME HACK: awful code duplication - double red = 0.5 + ln(moveCount) * ln(depth / 2) / 3.0; - if (red >= 1.0) - predictedDepth -= int(floor(red * int(OnePly))); + 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; - if (predictedDepth < SelectiveDepth) + if (futilityValueScaled < beta) { - int preFutilityValueMargin = 0; - if (predictedDepth >= OnePly) - preFutilityValueMargin = 112 * bitScanReverse32(int(predictedDepth) * int(predictedDepth) / 2); - - 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; @@ -1611,28 +1523,29 @@ namespace { && !dangerous && !captureOrPromotion && !move_is_castle(move) - && !move_is_killer(move, ss[ply]) - /* && move != ttMove*/) + && !move_is_killer(move, ss[ply])) { - double red = 0.5 + ln(moveCount) * ln(depth / 2) / 3.0; - if (red >= 1.0) + ss[ply].reduction = nonpv_reduction(depth, moveCount); + if (ss[ply].reduction) { - ss[ply].reduction = Depth(int(floor(red * int(OnePly)))); value = -search(pos, ss, -(beta-1), newDepth-ss[ply].reduction, ply+1, true, threadID); doFullDepthSearch = (value >= beta); } } - 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; @@ -1643,34 +1556,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)) @@ -1698,7 +1614,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; @@ -1708,13 +1624,14 @@ namespace { const TTEntry* tte = NULL; int moveCount = 0; bool pvNode = (beta - alpha != 1); + Value oldAlpha = alpha; // Initialize, and make an early exit in case of an aborted search, // an instant draw, maximum ply reached, etc. 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) @@ -1756,7 +1673,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; @@ -1775,7 +1692,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. @@ -1820,6 +1737,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) @@ -1851,14 +1769,14 @@ namespace { // Update transposition table Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1)); - if (bestValue < beta) + if (bestValue <= oldAlpha) { // 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 + else if (bestValue >= beta) { move = ss[ply].pv[ply]; TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, move); @@ -1867,6 +1785,8 @@ namespace { if (!pos.move_is_capture_or_promotion(move)) update_killers(move, ss[ply]); } + else + TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, d, ss[ply].pv[ply]); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1881,75 +1801,83 @@ 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); + + StateInfo st; + Move move; + Depth ext, newDepth; + Value value, futilityValueScaled; + bool isCheck, moveIsCheck, captureOrPromotion, dangerous; + int moveCount; + value = -VALUE_INFINITE; Position pos(*sp->pos); CheckInfo ci(pos); SearchStack* ss = sp->sstack[threadID]; - Value value = -VALUE_INFINITE; - Move move; - bool isCheck = pos.is_check(); - bool useFutilityPruning = sp->depth < SelectiveDepth - && !isCheck; + isCheck = pos.is_check(); - const int FutilityMoveCountMargin = 3 + (1 << (3 * int(sp->depth) / 8)); + // Step 10. Loop through moves + // Loop through all legal moves until no moves remain or a beta cutoff occurs + lock_grab(&(sp->lock)); while ( sp->bestValue < sp->beta - && !thread_should_stop(threadID) - && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE) + && !TM.thread_should_stop(threadID) + && (move = sp->mp->get_next_move()) != MOVE_NONE) { + moveCount = ++sp->moves; + lock_release(&(sp->lock)); + 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); - lock_grab(&(sp->lock)); - int moveCount = ++sp->moves; - lock_release(&(sp->lock)); + // 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; @@ -1958,59 +1886,44 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) { - double red = 0.5 + ln(moveCount) * ln(sp->depth / 2) / 3.0; - if (red >= 1.0) + ss[sp->ply].reduction = nonpv_reduction(sp->depth, moveCount); + if (ss[sp->ply].reduction) { - ss[sp->ply].reduction = Depth(int(floor(red * int(OnePly)))); 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)) - 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)); } } - lock_grab(&(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)); } @@ -2023,43 +1936,54 @@ 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; - Move move; + + // Step 10. Loop through moves + // Loop through all legal moves until no moves remain or a beta cutoff occurs + lock_grab(&(sp->lock)); while ( sp->alpha < sp->beta - && !thread_should_stop(threadID) - && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE) + && !TM.thread_should_stop(threadID) + && (move = sp->mp->get_next_move()) != MOVE_NONE) { - bool moveIsCheck = pos.move_is_check(move, ci); - bool captureOrPromotion = pos.move_is_capture_or_promotion(move); + moveCount = ++sp->moves; + lock_release(&(sp->lock)); assert(move_is_ok(move)); - lock_grab(&(sp->lock)); - int moveCount = ++sp->moves; - lock_release(&(sp->lock)); + 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; @@ -2068,221 +1992,66 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) { - double red = 0.5 + ln(moveCount) * ln(sp->depth / 2) / 6.0; - if (red >= 1.0) + ss[sp->ply].reduction = pv_reduction(sp->depth, moveCount); + if (ss[sp->ply].reduction) { Value localAlpha = sp->alpha; - ss[sp->ply].reduction = Depth(int(floor(red * int(OnePly)))); 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)) - 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)); } } - lock_grab(&(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 @@ -2293,24 +2062,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); } @@ -2593,6 +2359,7 @@ namespace { return defaultEval; } + // update_history() registers a good move that produced a beta-cutoff // in history and marks as failures all the other moves of that ply. @@ -2641,21 +2408,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)); } @@ -2673,7 +2426,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); } @@ -2681,7 +2434,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(); @@ -2723,7 +2476,6 @@ namespace { else if (t - lastInfoTime >= 1000) { lastInfoTime = t; - lock_grab(&IOLock); if (dbg_show_mean) dbg_print_mean(); @@ -2731,13 +2483,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? @@ -2745,22 +2502,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; } @@ -2775,48 +2525,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[]) { @@ -2856,108 +2575,241 @@ namespace { } + // 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 NULL; + } + +#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) + if (AllThreadsShouldSleep || threadID >= ActiveThreads) pthread_cond_wait(&WaitCond, &WaitLock); - pthread_mutex_unlock(&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); + + assert(threads[threadID].state == THREAD_SEARCHING); - Threads[threadID].running = false; + 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() { - void init_split_point_stack() { + volatile int i; + bool ok; - for (int i = 0; i < THREAD_MAX; i++) +#if !defined(_MSC_VER) + pthread_t pthread[1]; +#endif + + // Initialize global locks + lock_init(&MPLock, NULL); + + // 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); } + +#if !defined(_MSC_VER) + pthread_mutex_init(&WaitLock, NULL); + pthread_cond_init(&WaitCond, NULL); +#else + for (i = 0; i < MAX_THREADS; i++) + SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0); +#endif + + // 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 + DWORD iID[1]; + ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID) != 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)); } - // 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; } @@ -2969,17 +2821,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 @@ -2990,7 +2842,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; @@ -2999,10 +2851,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); @@ -3027,16 +2879,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); @@ -3047,27 +2901,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; @@ -3077,24 +2929,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 @@ -3102,13 +2955,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). @@ -3121,12 +2977,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; @@ -3136,49 +2989,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