X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=2e3f9d5663718ad4cac483c1d46b630cc5888d36;hp=987b954a6cd5554fe252f051e12de6447dfd14d0;hb=c974d9ef3311c17810be63a3f68ffd44a4de3819;hpb=770db2716470f0e805ac4ee1e010f5adacb42369 diff --git a/src/search.cpp b/src/search.cpp index 987b954a..2e3f9d56 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -53,23 +53,61 @@ namespace { /// Types - // 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. - - struct BetaCounterType { - - BetaCounterType(); - void clear(); - void add(Color us, Depth d, int threadID); - void read(Color us, int64_t& our, int64_t& their); + + // 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 print_current_line(SearchStack ss[], int ply, int threadID); + + 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, + const Value futilityValue, Depth depth, int* moves, MovePicker* mp, int master, bool pvNode); + + private: + friend void poll(); + + int ActiveThreads; + volatile bool AllThreadsShouldExit, AllThreadsShouldSleep; + Thread threads[MAX_THREADS]; + SplitPoint SplitPointStack[MAX_THREADS][ACTIVE_SPLIT_POINTS_MAX]; + + Lock MPLock, IOLock; + +#if !defined(_MSC_VER) + pthread_cond_t WaitCond; + pthread_mutex_t WaitLock; +#else + HANDLE SitIdleEvent[MAX_THREADS]; +#endif + }; - // 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). @@ -126,9 +164,6 @@ namespace { // Search depth at iteration 1 const Depth InitialDepth = OnePly; - // Depth limit for selective search - const Depth SelectiveDepth = 7 * OnePly; - // Use internal iterative deepening? const bool UseIIDAtPVNodes = true; const bool UseIIDAtNonPVNodes = true; @@ -142,17 +177,6 @@ namespace { // 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); - - // 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); - // 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); @@ -161,17 +185,25 @@ namespace { // remaining ones we will extend it. const Value SingleReplyMargin = Value(0x20); - // Margins for futility pruning in the quiescence search, and at frontier - // and near frontier nodes. - const Value FutilityMarginQS = Value(0x80); + // Depth limit for razoring + const Depth RazorDepth = 4 * OnePly; - Value FutilityMargins[2 * PLY_MAX_PLUS_2]; // Initialized at startup. + /// Lookup tables initialized at startup - // Each move futility margin is decreased - const Value IncrementalFutilityMargin = Value(0x8); + // Reduction lookup tables and their getter functions + int8_t PVReductionMatrix[64][64]; // [depth][moveNumber] + int8_t NonPVReductionMatrix[64][64]; // [depth][moveNumber] - // Depth limit for razoring - const Depth RazorDepth = 4 * OnePly; + 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)]; } + + // Futility lookup tables and their getter functions + const Value FutilityMarginQS = Value(0x80); + int32_t FutilityMarginsMatrix[14][64]; // [depth][moveNumber] + int FutilityMoveCountArray[32]; // [depth] + + 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; } /// Variables initialized by UCI options @@ -190,7 +222,6 @@ namespace { // Iteration counters int Iteration; - BetaCounterType BetaCounter; // Scores and number of times the best move changed for each iteration Value ValueByIteration[PLY_MAX_PLUS_2]; @@ -209,7 +240,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; @@ -218,27 +249,10 @@ namespace { bool UseLogFile; std::ofstream LogFile; - // Natural logarithmic lookup table and its getter function - float lnArray[512]; - inline float ln(int i) { return lnArray[i]; } - // MP related variables - int ActiveThreads = 1; 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. @@ -268,33 +282,17 @@ namespace { bool ok_to_prune(const Position& pos, Move m, Move threat); bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply); Value refine_eval(const TTEntry* tte, Value defaultEval, int ply); - void reduction_parameters(float base, float Inhibitor, Depth depth, float& logLimit, float& gradient); - Depth reduction(int moveCount, const float LogLimit, const float BaseRed, const float Gradient); void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount); void update_killers(Move m, SearchStack& ss); void update_gains(const Position& pos, Move move, Value before, Value after); - bool fail_high_ply_1(); int current_search_time(); int nps(); void poll(); void 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 @@ -308,6 +306,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. @@ -349,8 +354,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; @@ -361,7 +366,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()) @@ -370,16 +375,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 @@ -425,10 +429,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()); @@ -436,10 +440,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]; @@ -533,111 +534,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_search() is called during startup. It initializes various lookup tables - // Init our logarithmic lookup table - for (i = 0; i < 512; i++) - lnArray[i] = float(log(double(i))); // log() returns base-e logarithm +void init_search() { - for (i = 0; i < THREAD_MAX; i++) - Threads[i].activeSplitPoints = 0; + // Init our reduction lookup tables + for (int i = 1; i < 64; i++) // i == depth (OnePly = 1) + for (int j = 1; j < 64; j++) // j == moveNumber + { + double pvRed = 0.5 + log(double(i)) * log(double(j)) / 6.0; + double nonPVRed = 0.5 + log(double(i)) * log(double(j)) / 3.0; + PVReductionMatrix[i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0); + NonPVReductionMatrix[i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0); + } // Init futility margins array - FutilityMargins[0] = FutilityMargins[1] = Value(0); - - for (i = 2; i < 2 * PLY_MAX_PLUS_2; i++) - { - FutilityMargins[i] = Value(112 * bitScanReverse32(i * i / 2)); // FIXME: test using log instead of BSR - } - - // Initialize global locks - lock_init(&MPLock, NULL); - lock_init(&IOLock, NULL); - - init_split_point_stack(); - -#if !defined(_MSC_VER) - pthread_mutex_init(&WaitLock, NULL); - pthread_cond_init(&WaitCond, NULL); -#else - for (i = 0; i < THREAD_MAX; i++) - SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0); -#endif - - // All threads except the main thread should be initialized to idle state - for (i = 1; i < THREAD_MAX; i++) - { - Threads[i].stop = false; - Threads[i].workIsWaiting = false; - Threads[i].idle = true; - Threads[i].running = false; - } - - // Launch the helper threads - for (i = 1; i < THREAD_MAX; i++) - { -#if !defined(_MSC_VER) - ok = (pthread_create(pthread, NULL, init_thread, (void*)(&i)) == 0); -#else - DWORD iID[1]; - ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID) != NULL); -#endif - - if (!ok) + for (int i = 0; i < 14; i++) // i == depth (OnePly = 2) + for (int j = 0; j < 64; j++) // j == moveNumber { - cout << "Failed to create thread number " << i << endl; - Application::exit_with_failure(); + FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j; // FIXME: test using log instead of BSR } - // Wait until the thread has finished launching - while (!Threads[i].running); - } -} - - -/// stop_threads() is called when the program exits. It makes all the -/// helper threads exit cleanly. - -void stop_threads() { - - ActiveThreads = THREAD_MAX; // HACK - Idle = false; // HACK - wake_sleeping_threads(); - AllThreadsShouldExit = true; - for (int i = 1; i < THREAD_MAX; i++) - { - Threads[i].stop = true; - while (Threads[i].running); - } - destroy_split_point_stack(); -} - - -/// nodes_searched() returns the total number of nodes searched so far in -/// the current search. - -int64_t nodes_searched() { - - int64_t result = 0ULL; - for (int i = 0; i < ActiveThreads; i++) - result += Threads[i].nodes; - return result; + // Init futility move count array + for (int i = 0; i < 32; i++) // i == depth (OnePly = 2) + FutilityMoveCountArray[i] = 3 + (1 << (3 * i / 8)); } @@ -649,7 +575,6 @@ void SearchStack::init(int ply) { currentMove = threatMove = MOVE_NONE; reduction = Depth(0); eval = VALUE_NONE; - evalInfo = NULL; } void SearchStack::initKillers() { @@ -688,7 +613,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"; @@ -754,8 +679,6 @@ namespace { if (ss[0].pv[0] != EasyMove) EasyMove = MOVE_NONE; - Problem = false; - if (UseTimeManagement) { // Time to stop? @@ -773,7 +696,7 @@ namespace { 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 && EasyMove == ss[0].pv[0] && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100 @@ -814,7 +737,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; @@ -839,7 +762,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]); @@ -888,13 +811,12 @@ namespace { } RootMoveNumber = i + 1; - FailHigh = false; // Save the current node count before the move is searched - nodes = nodes_searched(); + nodes = TM.nodes_searched(); // Reset beta cut-off counters - BetaCounter.clear(); + TM.resetBetaCounters(); // Pick the next root move, and print the move and the move number to // the standard output. @@ -913,10 +835,6 @@ namespace { value = - VALUE_INFINITE; - // Precalculate reduction parameters - float LogLimit, Gradient, BaseReduction = 0.5; - reduction_parameters(BaseReduction, 6.0, depth, LogLimit, Gradient); - while (1) // Fail high loop { @@ -930,16 +848,6 @@ namespace { alpha = -VALUE_INFINITE; value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); - - // 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 <= ValueByIteration[Iteration - 1] - ProblemMargin); - - if (Problem && StopOnPonderhit) - StopOnPonderhit = false; } else { @@ -952,7 +860,7 @@ namespace { && !captureOrPromotion && !move_is_castle(move)) { - ss[0].reduction = reduction(RootMoveNumber - MultiPV + 1, LogLimit, BaseReduction, Gradient); + 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); @@ -966,14 +874,7 @@ namespace { value = -search(pos, ss, -alpha, newDepth, 1, true, 0); if (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; value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); - } } } @@ -996,7 +897,7 @@ namespace { << ((value >= beta) ? " lowerbound" : ((value <= alpha)? " upperbound" : "")) << " time " << current_search_time() - << " nodes " << nodes_searched() + << " nodes " << TM.nodes_searched() << " nps " << nps() << " pv "; @@ -1011,7 +912,7 @@ 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; } // Prepare for a research after a fail high, each time with a wider window @@ -1031,9 +932,9 @@ namespace { // 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); + TM.get_beta_counters(pos.side_to_move(), our, their); rml.set_beta_counters(i, our, their); - rml.set_move_nodes(i, nodes_searched() - nodes); + rml.set_move_nodes(i, TM.nodes_searched() - nodes); assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE); @@ -1063,7 +964,7 @@ namespace { << ((value >= beta) ? " lowerbound" : ((value <= alpha)? " upperbound" : "")) << " time " << current_search_time() - << " nodes " << nodes_searched() + << " nodes " << TM.nodes_searched() << " nps " << nps() << " pv "; @@ -1078,15 +979,10 @@ 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 > ValueByIteration[Iteration - 1] - NoProblemMargin) - Problem = false; } else // MultiPV > 1 { @@ -1097,7 +993,7 @@ namespace { << " score " << value_to_string(rml.get_move_score(j)) << " depth " << ((j <= i)? Iteration : Iteration - 1) << " time " << current_search_time() - << " nodes " << nodes_searched() + << " nodes " << TM.nodes_searched() << " nps " << nps() << " pv "; @@ -1112,7 +1008,10 @@ namespace { assert(alpha >= oldAlpha); - FailLow = (alpha == oldAlpha); + AspirationFailLow = (alpha == oldAlpha); + + if (AspirationFailLow && StopOnPonderhit) + StopOnPonderhit = false; } // Can we exit fail low loop ? @@ -1138,7 +1037,7 @@ 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]; StateInfo st; @@ -1158,7 +1057,7 @@ namespace { init_node(ss, ply, threadID); // After init_node() that calls poll() - if (AbortSearch || thread_should_stop(threadID)) + if (AbortSearch || TM.thread_should_stop(threadID)) return Value(0); if (pos.is_draw() || ply >= PLY_MAX - 1) @@ -1209,15 +1108,11 @@ namespace { CheckInfo ci(pos); MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); - // Precalculate reduction parameters - float LogLimit, Gradient, BaseReduction = 0.5; - reduction_parameters(BaseReduction, 6.0, depth, LogLimit, Gradient); - // Loop through all legal moves until no moves remain or a beta cutoff // occurs. while ( alpha < beta && (move = mp.get_next_move()) != MOVE_NONE - && !thread_should_stop(threadID)) + && !TM.thread_should_stop(threadID)) { assert(move_is_ok(move)); @@ -1271,7 +1166,7 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[ply])) { - ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); + ss[ply].reduction = pv_reduction(depth, moveCount); if (ss[ply].reduction) { value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID); @@ -1284,19 +1179,7 @@ namespace { ss[ply].reduction = Depth(0); value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID); 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; - } } } pos.undo_move(move); @@ -1314,25 +1197,18 @@ 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 <= ValueByIteration[Iteration-1] - ProblemMargin) - Problem = true; } // Split? - if ( ActiveThreads > 1 + 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, VALUE_NONE, + depth, &moveCount, &mp, threadID, true)) break; } @@ -1343,7 +1219,7 @@ namespace { // 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) @@ -1351,7 +1227,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)) { @@ -1374,7 +1250,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; @@ -1396,7 +1272,7 @@ namespace { init_node(ss, ply, threadID); // After init_node() that calls poll() - if (AbortSearch || thread_should_stop(threadID)) + if (AbortSearch || TM.thread_should_stop(threadID)) return Value(0); if (pos.is_draw() || ply >= PLY_MAX - 1) @@ -1425,22 +1301,16 @@ namespace { isCheck = pos.is_check(); - // Calculate depth dependant futility pruning parameters - const int FutilityMoveCountMargin = 3 + (1 << (3 * int(depth) / 8)); - // Evaluate the position statically if (!isCheck) { if (tte && (tte->type() & VALUE_TYPE_EVAL)) staticValue = value_from_tt(tte->value(), ply); else - { staticValue = evaluate(pos, ei, threadID); - ss[ply].evalInfo = &ei; - } ss[ply].eval = staticValue; - futilityValue = staticValue + FutilityMargins[int(depth)]; //FIXME: Remove me, only for split + futilityValue = staticValue + futility_margin(depth, 0); //FIXME: Remove me, only for split staticValue = refine_eval(tte, staticValue, ply); // Enhance accuracy with TT value if possible update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval); } @@ -1451,8 +1321,8 @@ namespace { if ( !isCheck && allowNullmove && depth < RazorDepth - && staticValue - FutilityMargins[int(depth)] >= beta) - return staticValue - FutilityMargins[int(depth)]; + && staticValue - futility_margin(depth, 0) >= beta) + return staticValue - futility_margin(depth, 0); // Null move search if ( allowNullmove @@ -1460,7 +1330,7 @@ namespace { && !isCheck && !value_is_mate(beta) && ok_to_do_nullmove(pos) - && staticValue >= beta - NullMoveMargin) + && staticValue >= beta - (depth >= 4 * OnePly ? NullMoveMargin : 0)) { ss[ply].currentMove = MOVE_NULL; @@ -1524,7 +1394,7 @@ namespace { { search(pos, ss, beta, Min(depth/2, depth-2*OnePly), 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 @@ -1532,14 +1402,10 @@ namespace { MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); CheckInfo ci(pos); - // Precalculate reduction parameters - float LogLimit, Gradient, BaseReduction = 0.5; - reduction_parameters(BaseReduction, 3.0, depth, LogLimit, Gradient); - // 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)); @@ -1588,35 +1454,21 @@ 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: We are ignoring condition: depth >= 3*OnePly, BUG?? - ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); - if (ss[ply].reduction) - predictedDepth -= ss[ply].reduction; + Depth predictedDepth = newDepth - nonpv_reduction(depth, moveCount); //FIXME: We are ignoring condition: depth >= 3*OnePly, BUG?? + 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 = FutilityMargins[int(predictedDepth)]; - - preFutilityValueMargin += H.gain(pos.piece_on(move_from(move)), move_from(move), move_to(move)) + 45; - - futilityValueScaled = ss[ply].eval + preFutilityValueMargin - moveCount * IncrementalFutilityMargin; - - if (futilityValueScaled < beta) - { - if (futilityValueScaled > bestValue) - bestValue = futilityValueScaled; - continue; - } + if (futilityValueScaled > bestValue) + bestValue = futilityValueScaled; + continue; } } @@ -1633,7 +1485,7 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[ply])) { - ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); + ss[ply].reduction = nonpv_reduction(depth, moveCount); if (ss[ply].reduction) { value = -search(pos, ss, -(beta-1), newDepth-ss[ply].reduction, ply+1, true, threadID); @@ -1662,15 +1514,15 @@ namespace { } // Split? - if ( ActiveThreads > 1 + 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, futilityValue, //FIXME: SMP & futilityValue + depth, &moveCount, &mp, threadID, false)) break; } @@ -1681,14 +1533,14 @@ namespace { // 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)) @@ -1716,7 +1568,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; @@ -1733,7 +1585,7 @@ namespace { init_node(ss, ply, threadID); // After init_node() that calls poll() - if (AbortSearch || thread_should_stop(threadID)) + if (AbortSearch || TM.thread_should_stop(threadID)) return Value(0); if (pos.is_draw() || ply >= PLY_MAX - 1) @@ -1839,6 +1691,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) @@ -1905,8 +1758,8 @@ namespace { void sp_search(SplitPoint* sp, int threadID) { - assert(threadID >= 0 && threadID < ActiveThreads); - assert(ActiveThreads > 1); + assert(threadID >= 0 && threadID < TM.active_threads()); + assert(TM.active_threads() > 1); Position pos(*sp->pos); CheckInfo ci(pos); @@ -1915,18 +1768,12 @@ namespace { Move move; int moveCount; bool isCheck = pos.is_check(); - bool useFutilityPruning = sp->depth < SelectiveDepth + bool useFutilityPruning = sp->depth < 7 * OnePly //FIXME: sync with search && !isCheck; - const int FutilityMoveCountMargin = 3 + (1 << (3 * int(sp->depth) / 8)); - - // Precalculate reduction parameters - float LogLimit, Gradient, BaseReduction = 0.5; - reduction_parameters(BaseReduction, 3.0, sp->depth, LogLimit, Gradient); - while ( lock_grab_bool(&(sp->lock)) && sp->bestValue < sp->beta - && !thread_should_stop(threadID) + && !TM.thread_should_stop(threadID) && (move = sp->mp->get_next_move()) != MOVE_NONE) { moveCount = ++sp->moves; @@ -1950,13 +1797,13 @@ namespace { && !captureOrPromotion) { // 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)) continue; // Value based pruning - Value futilityValueScaled = sp->futilityValue - moveCount * IncrementalFutilityMargin; + Value futilityValueScaled = sp->futilityValue - moveCount * 8; //FIXME: sync with search if (futilityValueScaled < sp->beta) { @@ -1984,7 +1831,7 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) { - ss[sp->ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); + ss[sp->ply].reduction = nonpv_reduction(sp->depth, moveCount); if (ss[sp->ply].reduction) { value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); @@ -2001,27 +1848,17 @@ namespace { assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - if (thread_should_stop(threadID)) - { - lock_grab(&(sp->lock)); - break; - } - // New best move? if (value > sp->bestValue) // Less then 2% of cases { lock_grab(&(sp->lock)); - if (value > sp->bestValue && !thread_should_stop(threadID)) + if (value > sp->bestValue && !TM.thread_should_stop(threadID)) { sp->bestValue = value; if (sp->bestValue >= sp->beta) { + sp->stopRequest = true; 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; } } lock_release(&(sp->lock)); @@ -2030,13 +1867,6 @@ namespace { /* 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; @@ -2054,8 +1884,8 @@ namespace { 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); Position pos(*sp->pos); CheckInfo ci(pos); @@ -2064,13 +1894,9 @@ namespace { int moveCount; Move move; - // Precalculate reduction parameters - float LogLimit, Gradient, BaseReduction = 0.5; - reduction_parameters(BaseReduction, 6.0, sp->depth, LogLimit, Gradient); - while ( lock_grab_bool(&(sp->lock)) && sp->alpha < sp->beta - && !thread_should_stop(threadID) + && !TM.thread_should_stop(threadID) && (move = sp->mp->get_next_move()) != MOVE_NONE) { moveCount = ++sp->moves; @@ -2101,7 +1927,7 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) { - ss[sp->ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); + ss[sp->ply].reduction = pv_reduction(sp->depth, moveCount); if (ss[sp->ply].reduction) { Value localAlpha = sp->alpha; @@ -2118,53 +1944,31 @@ namespace { if (value > localAlpha && value < sp->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 (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; + assert(TM.thread_should_stop(threadID)); } } pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - if (thread_should_stop(threadID)) - { - lock_grab(&(sp->lock)); - break; - } - // New best move? if (value > sp->bestValue) // Less then 2% of cases { lock_grab(&(sp->lock)); - if (value > sp->bestValue && !thread_should_stop(threadID)) + if (value > sp->bestValue && !TM.thread_should_stop(threadID)) { 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->stopRequest = true; sp->alpha = value; @@ -2172,13 +1976,6 @@ namespace { 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 <= ValueByIteration[Iteration-1] - ProblemMargin) - Problem = true; } lock_release(&(sp->lock)); } @@ -2186,137 +1983,12 @@ namespace { /* 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; 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) { - - 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(); - } - - - // 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 @@ -2327,9 +1999,9 @@ 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) { @@ -2342,9 +2014,7 @@ namespace { } ss[ply].init(ply); ss[ply + 2].initKillers(); - - if (Threads[threadID].printCurrentLine) - print_current_line(ss, ply, threadID); + TM.print_current_line(ss, ply, threadID); } @@ -2628,34 +2298,6 @@ namespace { } - // reduction_parameters() precalculates some parameters used later by reduction. Becasue - // floating point operations are involved we try to recalculate reduction at each move, but - // we do the most consuming computation only once per node. - - void reduction_parameters(float baseReduction, float reductionInhibitor, Depth depth, float& logLimit, float& gradient) - { - // Precalculate some parameters to avoid to calculate the following formula for each move: - // - // red = baseReduction + ln(moveCount) * ln(depth / 2) / reductionInhibitor; - // - logLimit = depth > OnePly ? (1 - baseReduction) * reductionInhibitor / ln(depth / 2) : 1000; - gradient = depth > OnePly ? ln(depth / 2) / reductionInhibitor : 0; - } - - - // reduction() returns reduction in plies based on moveCount and depth. - // Reduction is always at least one ply. - - Depth reduction(int moveCount, float logLimit, float baseReduction, float gradient) { - - if (ln(moveCount) < logLimit) - return Depth(0); - - float red = baseReduction + ln(moveCount) * gradient; - return Depth(int(floor(red * int(OnePly)))); - } - - // update_history() registers a good move that produced a beta-cutoff // in history and marks as failures all the other moves of that ply. @@ -2704,21 +2346,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)); } @@ -2736,7 +2364,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); } @@ -2786,7 +2414,7 @@ namespace { else if (t - lastInfoTime >= 1000) { lastInfoTime = t; - lock_grab(&IOLock); + lock_grab(&TM.IOLock); if (dbg_show_mean) dbg_print_mean(); @@ -2794,13 +2422,13 @@ 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); + lock_release(&TM.IOLock); if (ShowCurrentLine) - Threads[0].printCurrentLine = true; + TM.threads[0].printCurrentLineRequest = true; } // Should we stop the search? @@ -2808,22 +2436,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; } @@ -2838,48 +2459,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[]) { @@ -2919,108 +2509,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(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); + lock_init(&IOLock, 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(); - void destroy_split_point_stack() { + // This makes the threads to exit idle_loop() + AllThreadsShouldExit = true; - for (int i = 0; i < THREAD_MAX; i++) + // Wait for thread termination + for (int i = 1; i < MAX_THREADS; i++) + while (threads[i].state != THREAD_TERMINATED); + + // 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; } @@ -3032,17 +2755,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 @@ -3053,7 +2776,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; @@ -3062,10 +2785,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); @@ -3090,16 +2813,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, const Value futilityValue, 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); @@ -3110,24 +2835,23 @@ 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; @@ -3140,24 +2864,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++; + + // If we are here it means we are not available + assert(threads[master].state != THREAD_AVAILABLE); - // Allocate available threads setting idle flag to false + // 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 @@ -3165,13 +2890,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). @@ -3184,12 +2912,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; @@ -3199,49 +2924,171 @@ 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; + + for (int i = 1; i < ActiveThreads; i++) + assert(threads[i].state == THREAD_SLEEPING); #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; + + // Reset flags to a known state. + for (int i = 1; i < ActiveThreads; i++) + { + // This flag can be in a random state + threads[i].printCurrentLineRequest = false; } } + // print_current_line() prints _once_ the current line of search for a + // given thread and then setup the print request for the next thread. + // Called when the UCI option UCI_ShowCurrLine is 'true'. - // 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. + void ThreadsManager::print_current_line(SearchStack ss[], int ply, int threadID) { -#if !defined(_MSC_VER) + assert(ply >= 0 && ply < PLY_MAX); + assert(threadID >= 0 && threadID < ActiveThreads); - void* init_thread(void *threadID) { + if (!threads[threadID].printCurrentLineRequest) + return; - idle_loop(*(int*)threadID, NULL); - return NULL; + // One shot only + threads[threadID].printCurrentLineRequest = false; + + if (threads[threadID].state == THREAD_SEARCHING) + { + lock_grab(&IOLock); + cout << "info currline " << (threadID + 1); + for (int p = 0; p < ply; p++) + cout << " " << ss[p].currentMove; + + cout << endl; + lock_release(&IOLock); + } + + // Setup print request for the next thread ID + if (threadID + 1 < ActiveThreads) + threads[threadID + 1].printCurrentLineRequest = true; } -#else - DWORD WINAPI init_thread(LPVOID threadID) { + /// The RootMoveList class - idle_loop(*(int*)threadID, NULL); - return NULL; + // 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(); } -#endif -} + // 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; + } + } + +} // namspace