X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=55e04ec363e90467665aa24c8c79dd578f96ea9e;hp=be296443f3d635c7e90bc9d4a7b0c711ed41e3b4;hb=b6482472a03833287dc21bdaa783f156978ac63e;hpb=5ae195ee7e3ccac01b8145f9b7022e352a288f07 diff --git a/src/search.cpp b/src/search.cpp index be296443..55e04ec3 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -61,10 +61,13 @@ namespace { // Different node types, used as a template parameter enum NodeType { NonPV, PV }; + constexpr uint64_t ttHitAverageWindow = 4096; + constexpr uint64_t ttHitAverageResolution = 1024; + // Razor and futility margins - constexpr int RazorMargin = 661; + constexpr int RazorMargin = 594; Value futility_margin(Depth d, bool improving) { - return Value(198 * (d - improving)); + return Value(232 * (d - improving)); } // Reductions lookup table, initialized at startup @@ -76,7 +79,7 @@ namespace { } constexpr int futility_move_count(bool improving, Depth depth) { - return (5 + depth * depth) * (1 + improving) / 2; + return (5 + depth * depth) * (1 + improving) / 2 - 1; } // History and stats update bonus, based on depth @@ -332,6 +335,7 @@ void Thread::search() { MainThread* mainThread = (this == Threads.main() ? Threads.main() : nullptr); double timeReduction = 1, totBestMoveChanges = 0; Color us = rootPos.side_to_move(); + int iterIdx = 0; std::memset(ss-7, 0, 10 * sizeof(Stack)); for (int i = 7; i > 0; i--) @@ -342,6 +346,16 @@ void Thread::search() { bestValue = delta = alpha = -VALUE_INFINITE; beta = VALUE_INFINITE; + if (mainThread) + { + if (mainThread->previousScore == VALUE_INFINITE) + for (int i=0; i<4; ++i) + mainThread->iterValue[i] = VALUE_ZERO; + else + for (int i=0; i<4; ++i) + mainThread->iterValue[i] = mainThread->previousScore; + } + size_t multiPV = Options["MultiPV"]; // Pick integer skill levels, but non-deterministically round up or down @@ -363,6 +377,7 @@ void Thread::search() { multiPV = std::max(multiPV, (size_t)4); multiPV = std::min(multiPV, rootMoves.size()); + ttHitAverage = ttHitAverageWindow * ttHitAverageResolution / 2; int ct = int(Options["Contempt"]) * PawnValueEg / 100; // From centipawns @@ -516,7 +531,8 @@ void Thread::search() { && !Threads.stop && !mainThread->stopOnPonderhit) { - double fallingEval = (354 + 10 * (mainThread->previousScore - bestValue)) / 692.0; + double fallingEval = (354 + 6 * (mainThread->previousScore - bestValue) + + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 692.0; fallingEval = clamp(fallingEval, 0.5, 1.5); // If the bestMove is stable over several iterations, reduce time accordingly @@ -543,6 +559,9 @@ void Thread::search() { Threads.stop = true; } } + + mainThread->iterValue[iterIdx] = bestValue; + iterIdx = (iterIdx + 1) & 3; } if (!mainThread) @@ -665,6 +684,9 @@ namespace { ttMove = rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0] : ttHit ? tte->move() : MOVE_NONE; ttPv = PvNode || (ttHit && tte->is_pv()); + // thisThread->ttHitAverage can be used to approximate the running average of ttHit + thisThread->ttHitAverage = (ttHitAverageWindow - 1) * thisThread->ttHitAverage / ttHitAverageWindow + + ttHitAverageResolution * ttHit; // At non-PV nodes we check for an early TT cutoff if ( !PvNode @@ -790,8 +812,8 @@ namespace { && eval <= alpha - RazorMargin) return qsearch(pos, ss, alpha, beta); - improving = ss->staticEval >= (ss-2)->staticEval - || (ss-2)->staticEval == VALUE_NONE; + improving = (ss-2)->staticEval == VALUE_NONE ? (ss->staticEval >= (ss-4)->staticEval + || (ss-4)->staticEval == VALUE_NONE) : ss->staticEval >= (ss-2)->staticEval; // Step 8. Futility pruning: child node (~30 Elo) if ( !PvNode @@ -955,7 +977,44 @@ moves_loop: // When in check, search starts from here movedPiece = pos.moved_piece(move); givesCheck = pos.gives_check(move); - // Step 13. Extensions (~70 Elo) + // Calculate new depth for this move + newDepth = depth - 1; + + // Step 13. Pruning at shallow depth (~170 Elo) + if ( !rootNode + && pos.non_pawn_material(us) + && bestValue > VALUE_MATED_IN_MAX_PLY) + { + // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold + moveCountPruning = moveCount >= futility_move_count(improving, depth); + + if ( !captureOrPromotion + && !givesCheck) + { + // Reduced depth of the next LMR search + int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), 0); + + // Countermoves based pruning (~20 Elo) + if ( lmrDepth < 4 + ((ss-1)->statScore > 0 || (ss-1)->moveCount == 1) + && (*contHist[0])[movedPiece][to_sq(move)] < CounterMovePruneThreshold + && (*contHist[1])[movedPiece][to_sq(move)] < CounterMovePruneThreshold) + continue; + + // Futility pruning: parent node (~2 Elo) + if ( lmrDepth < 6 + && !inCheck + && ss->staticEval + 250 + 211 * lmrDepth <= alpha) + continue; + + // Prune moves with negative SEE (~10 Elo) + if (!pos.see_ge(move, Value(-(31 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth))) + continue; + } + else if (!pos.see_ge(move, Value(-199) * depth)) // (~20 Elo) + continue; + } + + // Step 14. Extensions (~70 Elo) // Singular extension search (~60 Elo). If all moves but one fail low on a // search of (alpha-s, beta-s), and just one fails high on (alpha, beta), @@ -989,8 +1048,7 @@ moves_loop: // When in check, search starts from here // search without the ttMove. So we assume this expected Cut-node is not singular, // that multiple moves fail high, and we can prune the whole subtree by returning // a soft bound. - else if ( eval >= beta - && singularBeta >= beta) + else if (singularBeta >= beta) return singularBeta; } @@ -1005,52 +1063,17 @@ moves_loop: // When in check, search starts from here && pos.pawn_passed(us, to_sq(move))) extension = 1; + // Last captures extension + else if ( PieceValue[EG][pos.captured_piece()] > PawnValueEg + && pos.non_pawn_material() <= 2 * RookValueMg) + extension = 1; + // Castling extension if (type_of(move) == CASTLING) extension = 1; - // Calculate new depth for this move - newDepth = depth - 1 + extension; - - // Step 14. Pruning at shallow depth (~170 Elo) - if ( !rootNode - && pos.non_pawn_material(us) - && bestValue > VALUE_MATED_IN_MAX_PLY) - { - // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold - moveCountPruning = moveCount >= futility_move_count(improving, depth); - - if ( !captureOrPromotion - && !givesCheck - && (!pos.advanced_pawn_push(move) || pos.non_pawn_material(~us) > BishopValueMg)) - { - // Move count based pruning - if (moveCountPruning) - continue; - - // Reduced depth of the next LMR search - int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), 0); - - // Countermoves based pruning (~20 Elo) - if ( lmrDepth < 4 + ((ss-1)->statScore > 0 || (ss-1)->moveCount == 1) - && (*contHist[0])[movedPiece][to_sq(move)] < CounterMovePruneThreshold - && (*contHist[1])[movedPiece][to_sq(move)] < CounterMovePruneThreshold) - continue; - - // Futility pruning: parent node (~2 Elo) - if ( lmrDepth < 6 - && !inCheck - && ss->staticEval + 250 + 211 * lmrDepth <= alpha) - continue; - - // Prune moves with negative SEE (~10 Elo) - if (!pos.see_ge(move, Value(-(31 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth))) - continue; - } - else if ( !(givesCheck && extension) - && !pos.see_ge(move, Value(-199) * depth)) // (~20 Elo) - continue; - } + // Add extension to new depth + newDepth += extension; // Speculative prefetch as early as possible prefetch(TT.first_entry(pos.key_after(move))); @@ -1080,10 +1103,15 @@ moves_loop: // When in check, search starts from here && ( !captureOrPromotion || moveCountPruning || ss->staticEval + PieceValue[EG][pos.captured_piece()] <= alpha - || cutNode)) + || cutNode + || thisThread->ttHitAverage < 384 * ttHitAverageResolution * ttHitAverageWindow / 1024)) { Depth r = reduction(improving, depth, moveCount); + // Decrease reduction if the ttHit running average is large + if (thisThread->ttHitAverage > 544 * ttHitAverageResolution * ttHitAverageWindow / 1024) + r--; + // Reduction if other threads are searching this position. if (th.marked()) r++; @@ -1449,9 +1477,7 @@ moves_loop: // When in check, search starts from here && !pos.capture(move); // Don't search moves with negative SEE values - if ( (!inCheck || evasionPrunable) - && !(givesCheck && pos.is_discovery_check_on_king(~pos.side_to_move(), move)) - && !pos.see_ge(move)) + if ( (!inCheck || evasionPrunable) && !pos.see_ge(move)) continue; // Speculative prefetch as early as possible @@ -1712,7 +1738,7 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { for (size_t i = 0; i < multiPV; ++i) { - bool updated = (i <= pvIdx && rootMoves[i].score != -VALUE_INFINITE); + bool updated = rootMoves[i].score != -VALUE_INFINITE; if (depth == 1 && !updated) continue;