X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=4ea31a0b36dcde97bda492310b681fcec6025cf5;hp=c894403cc452337c87abfc2d3cd99227b892a645;hb=35ada63174bbec6289d6dea6d3cfc5b5f14d1d27;hpb=c83fd08fd4fa91702ef0f727bc777c613524403d diff --git a/src/search.cpp b/src/search.cpp index c894403c..4ea31a0b 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -185,6 +185,8 @@ namespace { // and near frontier nodes. const Value FutilityMarginQS = Value(0x80); + Value FutilityMargins[2 * PLY_MAX_PLUS_2]; // Initialized at startup. + // Each move futility margin is decreased const Value IncrementalFutilityMargin = Value(0x8); @@ -237,8 +239,8 @@ namespace { std::ofstream LogFile; // Natural logarithmic lookup table and its getter function - double lnArray[512]; - inline double ln(int i) { return lnArray[i]; } + float lnArray[512]; + inline float ln(int i) { return lnArray[i]; } // MP related variables int ActiveThreads = 1; @@ -286,6 +288,8 @@ 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); @@ -527,7 +531,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, @@ -570,11 +573,19 @@ void init_threads() { // Init our logarithmic lookup table for (i = 0; i < 512; i++) - lnArray[i] = log(double(i)); // log() returns base-e logarithm + lnArray[i] = float(log(double(i))); // log() returns base-e logarithm for (i = 0; i < THREAD_MAX; i++) Threads[i].activeSplitPoints = 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); @@ -683,6 +694,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) @@ -733,13 +745,11 @@ namespace { int prevDelta1 = IterationInfo[Iteration - 1].speculatedValue - IterationInfo[Iteration - 2].speculatedValue; int prevDelta2 = IterationInfo[Iteration - 2].speculatedValue - IterationInfo[Iteration - 3].speculatedValue; - int delta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16); + AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16); + AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize - delta = (delta + 7) / 8 * 8; // Round to match grainSize - AspirationDelta = delta; - - alpha = Max(IterationInfo[Iteration - 1].value - delta, -VALUE_INFINITE); - beta = Min(IterationInfo[Iteration - 1].value + delta, VALUE_INFINITE); + alpha = Max(IterationInfo[Iteration - 1].value - AspirationDelta, -VALUE_INFINITE); + beta = Min(IterationInfo[Iteration - 1].value + AspirationDelta, VALUE_INFINITE); } else { @@ -894,20 +904,22 @@ namespace { Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta) { - Value alpha = oldAlpha; + 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; - while(1) // Fail low loop + while (1) // Fail low loop { // Loop through all the moves in the root move list @@ -921,10 +933,6 @@ namespace { rml.set_move_score(i, -VALUE_INFINITE); continue; } - int64_t nodes; - Move move; - StateInfo st; - Depth depth, ext, newDepth; RootMoveNumber = i + 1; FailHigh = false; @@ -944,15 +952,18 @@ namespace { << " currmovenumber " << RootMoveNumber << endl; // Decide search depth for this move - bool moveIsCheck = pos.move_is_check(move); - bool captureOrPromotion = pos.move_is_capture_or_promotion(move); - bool dangerous; - depth = (Iteration - 2) * OnePly + InitialDepth; + 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; 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 { @@ -988,10 +999,9 @@ namespace { && !captureOrPromotion && !move_is_castle(move)) { - double red = 0.5 + ln(RootMoveNumber - MultiPV + 1) * ln(depth / 2) / 6.0; - if (red >= 1.0) + ss[0].reduction = reduction(RootMoveNumber - MultiPV + 1, LogLimit, BaseReduction, Gradient); + if (ss[0].reduction) { - ss[0].reduction = Depth(int(floor(red * int(OnePly)))); value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0); doFullDepthSearch = (value > alpha); } @@ -999,6 +1009,7 @@ namespace { if (doFullDepthSearch) { + ss[0].reduction = Depth(0); value = -search(pos, ss, -alpha, newDepth, 1, true, 0); if (value > alpha) @@ -1015,8 +1026,9 @@ namespace { pos.undo_move(move); + // Can we exit fail high loop ? if (AbortSearch || value < beta) - break; // We are not failing high + break; // 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. @@ -1049,7 +1061,7 @@ namespace { nodes_searched(), value, type, ss[0].pv) << endl; } - // Prepare for research + // Prepare for a research after a fail high, each time with a wider window researchCount++; beta = Min(beta + AspirationDelta * (1 << researchCount), VALUE_INFINITE); @@ -1150,10 +1162,11 @@ namespace { FailLow = (alpha == oldAlpha); } + // Can we exit fail low loop ? if (AbortSearch || alpha > oldAlpha) - break; // End search, we are not failing low + break; - // Prepare for research + // 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; @@ -1243,6 +1256,10 @@ 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 @@ -1301,13 +1318,12 @@ 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 = reduction(moveCount, LogLimit, BaseReduction, Gradient); + 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 @@ -1458,7 +1474,6 @@ namespace { // 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) @@ -1472,19 +1487,18 @@ namespace { } ss[ply].eval = staticValue; - futilityValue = staticValue + PostFutilityValueMargin; //FIXME: Remove me, only for split + futilityValue = staticValue + FutilityMargins[int(depth)]; //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); } // Do a "stand pat". If we are above beta by a good margin then // return immediately. - // FIXME: test with added condition 'allowNullmove || depth <= OnePly' and !value_is_mate(beta) - // FIXME: test with modified condition 'depth < RazorDepth' if ( !isCheck - && depth < SelectiveDepth - && staticValue - PostFutilityValueMargin >= beta) - return staticValue - PostFutilityValueMargin; + && allowNullmove + && depth < RazorDepth + && staticValue - FutilityMargins[int(depth)] >= beta) + return staticValue - FutilityMargins[int(depth)]; // Null move search if ( allowNullmove @@ -1564,6 +1578,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 @@ -1608,36 +1626,6 @@ namespace { // Update current move movesSearched[moveCount++] = ss[ply].currentMove = move; - // Futility pruning for captures - // FIXME: test disabling 'Futility pruning for captures' - // FIXME: test with 'newDepth < RazorDepth' - 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); - - Value futilityCaptureValue = ss[ply].eval + pos.endgame_value_of_piece_on(move_to(move)) + preFutilityValueMargin + ei.futilityMargin + 90; - - if (futilityCaptureValue < beta) - { - if (futilityCaptureValue > bestValue) - bestValue = futilityCaptureValue; - continue; - } - } - // Futility pruning if ( !isCheck && !dangerous @@ -1654,16 +1642,16 @@ namespace { // 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))); + //FIXME: We are ignoring condition: depth >= 3*OnePly, BUG?? + ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); + if (ss[ply].reduction) + predictedDepth -= ss[ply].reduction; if (predictedDepth < SelectiveDepth) { int preFutilityValueMargin = 0; if (predictedDepth >= OnePly) - preFutilityValueMargin = 112 * bitScanReverse32(int(predictedDepth) * int(predictedDepth) / 2); + preFutilityValueMargin = FutilityMargins[int(predictedDepth)]; preFutilityValueMargin += H.gain(pos.piece_on(move_from(move)), move_from(move), move_to(move)) + 45; @@ -1689,13 +1677,11 @@ 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 = reduction(moveCount, LogLimit, BaseReduction, Gradient); + 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); } @@ -1786,6 +1772,7 @@ 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. @@ -1834,7 +1821,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; @@ -1853,7 +1840,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. @@ -1929,14 +1916,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); @@ -1945,6 +1932,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); @@ -1977,6 +1966,10 @@ 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) @@ -2037,10 +2030,9 @@ 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 = reduction(moveCount, LogLimit, BaseReduction, Gradient); + 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); } @@ -2118,6 +2110,10 @@ 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) @@ -2151,11 +2147,10 @@ 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 = reduction(moveCount, LogLimit, BaseReduction, Gradient); + 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); } @@ -2283,7 +2278,9 @@ namespace { 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 @@ -2301,16 +2298,13 @@ namespace { continue; // Find a quick score for the move - StateInfo st; - SearchStack ss[PLY_MAX_PLUS_2]; init_ss_array(ss); - + pos.do_move(cur->move, st); 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[0] = cur->move; moves[count].pv[1] = MOVE_NONE; + pos.undo_move(cur->move); count++; } sort(); @@ -2679,6 +2673,35 @@ namespace { return defaultEval; } + + // 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.