X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=4ea31a0b36dcde97bda492310b681fcec6025cf5;hp=7b9b5b370b5aac62a916e6dcb3d020dbaa065e10;hb=35ada63174bbec6289d6dea6d3cfc5b5f14d1d27;hpb=bdd61b174452f13336159fab6954bc37589a4c06 diff --git a/src/search.cpp b/src/search.cpp index 7b9b5b37..4ea31a0b 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -239,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; @@ -288,7 +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); - Depth calculate_reduction(double baseReduction, int moveCount, Depth depth, double reductionInhibitor); + 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); @@ -530,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, @@ -573,7 +573,7 @@ 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; @@ -694,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) @@ -744,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); - - delta = (delta + 7) / 8 * 8; // Round to match grainSize - AspirationDelta = delta; + AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16); + AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize - alpha = Max(IterationInfo[Iteration - 1].value - delta, -VALUE_INFINITE); - beta = Min(IterationInfo[Iteration - 1].value + delta, VALUE_INFINITE); + alpha = Max(IterationInfo[Iteration - 1].value - AspirationDelta, -VALUE_INFINITE); + beta = Min(IterationInfo[Iteration - 1].value + AspirationDelta, VALUE_INFINITE); } else { @@ -905,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 @@ -932,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; @@ -955,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 { @@ -999,7 +999,7 @@ namespace { && !captureOrPromotion && !move_is_castle(move)) { - ss[0].reduction = calculate_reduction(0.5, RootMoveNumber - MultiPV + 1, depth, 6.0); + ss[0].reduction = reduction(RootMoveNumber - MultiPV + 1, LogLimit, BaseReduction, Gradient); if (ss[0].reduction) { value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0); @@ -1026,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. @@ -1060,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); @@ -1161,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; @@ -1254,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 @@ -1312,7 +1318,7 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[ply])) { - ss[ply].reduction = calculate_reduction(0.5, moveCount, depth, 6.0); + 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); @@ -1488,10 +1494,9 @@ namespace { // 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 + && allowNullmove + && depth < RazorDepth && staticValue - FutilityMargins[int(depth)] >= beta) return staticValue - FutilityMargins[int(depth)]; @@ -1573,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 @@ -1617,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 = FutilityMargins[int(newDepth)]; - - 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 @@ -1664,7 +1643,7 @@ namespace { Depth predictedDepth = newDepth; //FIXME: We are ignoring condition: depth >= 3*OnePly, BUG?? - ss[ply].reduction = calculate_reduction(0.5, moveCount, depth, 3.0); + ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); if (ss[ply].reduction) predictedDepth -= ss[ply].reduction; @@ -1700,7 +1679,7 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[ply])) { - ss[ply].reduction = calculate_reduction(0.5, moveCount, depth, 3.0); + ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); if (ss[ply].reduction) { value = -search(pos, ss, -(beta-1), newDepth-ss[ply].reduction, ply+1, true, threadID); @@ -1793,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. @@ -1841,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; @@ -1860,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. @@ -1936,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); @@ -1952,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); @@ -1984,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) @@ -2044,7 +2030,7 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) { - ss[sp->ply].reduction = calculate_reduction(0.5, moveCount, sp->depth, 3.0); + ss[sp->ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); if (ss[sp->ply].reduction) { value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); @@ -2124,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) @@ -2157,7 +2147,7 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) { - ss[sp->ply].reduction = calculate_reduction(0.5, moveCount, sp->depth, 6.0); + ss[sp->ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient); if (ss[sp->ply].reduction) { Value localAlpha = sp->alpha; @@ -2288,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 @@ -2306,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(); @@ -2684,20 +2673,35 @@ namespace { return defaultEval; } - // calculate_reduction() returns reduction in plies based on - // moveCount and depth. Reduction is always at least one ply. - Depth calculate_reduction(double baseReduction, int moveCount, Depth depth, double reductionInhibitor) { + // 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. - double red = baseReduction + ln(moveCount) * ln(depth / 2) / reductionInhibitor; + 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; + } - if (red >= 1.0) - return Depth(int(floor(red * int(OnePly)))); - else + + // 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.