X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=6090233089bdcacd7d1f514507925e029e4730cf;hp=a7b7c88b3252641e48de11c04a1f8943ba74bb33;hb=9429d2d028f91863c63b0072b64cc9da99823017;hpb=21d32aa7fe110cb84ec5ed349bf42e328c0bea5a diff --git a/src/search.cpp b/src/search.cpp index a7b7c88b..60902330 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -142,17 +142,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); @@ -209,7 +198,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,9 +207,13 @@ 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]; } + // Reduction lookup tables and their getter functions + // Initialized at startup + int8_t PVReductionMatrix[64][64]; // [depth][moveNumber] + int8_t NonPVReductionMatrix[64][64]; // [depth][moveNumber] + + 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)]; } // MP related variables int ActiveThreads = 1; @@ -268,13 +261,10 @@ 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(); @@ -350,7 +340,7 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, // Initialize global search variables Idle = StopOnPonderhit = AbortSearch = Quit = false; - FailHigh = FailLow = Problem = false; + AspirationFailLow = false; NodesSincePoll = 0; SearchStartTime = get_system_time(); ExactMaxTime = maxTime; @@ -361,7 +351,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,6 +360,9 @@ 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; } @@ -378,7 +371,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, for (int i = 0; i < THREAD_MAX; i++) { Threads[i].nodes = 0ULL; - Threads[i].failHighPly1 = false; } if (button_was_pressed("New Game")) @@ -551,12 +543,15 @@ void init_threads() { pthread_t pthread[1]; #endif - // Init our logarithmic lookup table - for (i = 0; i < 512; i++) - lnArray[i] = float(log(double(i))); // log() returns base-e logarithm - - for (i = 0; i < THREAD_MAX; i++) - Threads[i].activeSplitPoints = 0; + // Init our reduction lookup tables + for (i = 1; i < 64; i++) // i == depth + 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); @@ -566,6 +561,9 @@ void init_threads() { FutilityMargins[i] = Value(112 * bitScanReverse32(i * i / 2)); // FIXME: test using log instead of BSR } + for (i = 0; i < THREAD_MAX; i++) + Threads[i].activeSplitPoints = 0; + // Initialize global locks lock_init(&MPLock, NULL); lock_init(&IOLock, NULL); @@ -748,14 +746,12 @@ namespace { break; // Value cannot be trusted. Break out immediately! //Save info about search result - ValueByIterationInfo[Iteration] = value; + 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? @@ -888,7 +884,6 @@ namespace { } RootMoveNumber = i + 1; - FailHigh = false; // Save the current node count before the move is searched nodes = nodes_searched(); @@ -913,10 +908,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 +921,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 +933,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 +947,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); - } } } @@ -1082,11 +1056,6 @@ namespace { } 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 { @@ -1112,7 +1081,10 @@ namespace { assert(alpha >= oldAlpha); - FailLow = (alpha == oldAlpha); + AspirationFailLow = (alpha == oldAlpha); + + if (AspirationFailLow && StopOnPonderhit) + StopOnPonderhit = false; } // Can we exit fail low loop ? @@ -1209,10 +1181,6 @@ 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 @@ -1271,7 +1239,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 +1252,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,13 +1270,6 @@ 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? @@ -1524,7 +1473,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,10 +1481,6 @@ 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 @@ -1597,7 +1542,7 @@ namespace { Depth predictedDepth = newDepth; //FIXME: We are ignoring condition: depth >= 3*OnePly, BUG?? - ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); + ss[ply].reduction = nonpv_reduction(depth, moveCount); if (ss[ply].reduction) predictedDepth -= ss[ply].reduction; @@ -1607,7 +1552,7 @@ namespace { if (predictedDepth >= OnePly) preFutilityValueMargin = FutilityMargins[int(predictedDepth)]; - preFutilityValueMargin += H.gain(pos.piece_on(move_from(move)), move_from(move), move_to(move)) + 45; + preFutilityValueMargin += H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45; futilityValueScaled = ss[ply].eval + preFutilityValueMargin - moveCount * IncrementalFutilityMargin; @@ -1633,7 +1578,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); @@ -1920,10 +1865,6 @@ namespace { 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) @@ -1984,7 +1925,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); @@ -2064,10 +2005,6 @@ 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) @@ -2101,7 +2038,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,14 +2055,6 @@ 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; @@ -2133,8 +2062,6 @@ namespace { value = -search_pv(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, threadID); else assert(thread_should_stop(threadID)); - - Threads[threadID].failHighPly1 = false; } } pos.undo_move(move); @@ -2172,13 +2099,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)); } @@ -2628,34 +2548,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 +2596,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)); } @@ -2808,18 +2686,11 @@ 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) @@ -2838,18 +2709,11 @@ 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; @@ -3165,7 +3029,7 @@ 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)); + memcpy(splitPoint->sstack[i] + ply - 1, sstck + ply - 1, 4 * sizeof(SearchStack)); Threads[i].workIsWaiting = true; // This makes the slave to exit from idle_loop() }