X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=b0bcc57a44ee05f8f71fe2205d187f25622613fb;hp=086761a3561b879227231d72279b5c191f015a31;hb=13f70d0392ca3ce7f1c8e34dd0a10c3537d2fbab;hpb=648c7ec25db2040c0af34dd846dfa3f57af5ad0a diff --git a/src/search.cpp b/src/search.cpp index 086761a3..b0bcc57a 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 = 531; Value futility_margin(Depth d, bool improving) { - return Value(198 * (d - improving)); + return Value(217 * (d - improving)); } // Reductions lookup table, initialized at startup @@ -72,16 +75,16 @@ namespace { Depth reduction(bool i, Depth d, int mn) { int r = Reductions[d] * Reductions[mn]; - return (r + 520) / 1024 + (!i && r > 999); + return (r + 511) / 1024 + (!i && r > 1007); } 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 int stat_bonus(Depth d) { - return d > 17 ? -8 : 22 * d * d + 151 * d - 140; + return d > 15 ? -8 : 19 * d * d + 155 * d - 132; } // Add a small random component to draw evaluations to avoid 3fold-blindness @@ -150,7 +153,7 @@ namespace { Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth = 0); Value value_to_tt(Value v, int ply); - Value value_from_tt(Value v, int ply); + Value value_from_tt(Value v, int ply, int r50c); void update_pv(Move* pv, Move move, Move* childPv); void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus); void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus); @@ -191,7 +194,7 @@ namespace { void Search::init() { for (int i = 1; i < MAX_MOVES; ++i) - Reductions[i] = int((23.4 + std::log(Threads.size()) / 2) * std::log(i)); + Reductions[i] = int((24.8 + std::log(Threads.size()) / 2) * std::log(i)); } @@ -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 @@ -413,12 +428,12 @@ void Thread::search() { if (rootDepth >= 4) { Value previousScore = rootMoves[pvIdx].previousScore; - delta = Value(21 + abs(previousScore) / 128); + delta = Value(21 + abs(previousScore) / 256); alpha = std::max(previousScore - delta,-VALUE_INFINITE); beta = std::min(previousScore + delta, VALUE_INFINITE); // Adjust contempt based on root move's previousScore (dynamic contempt) - int dct = ct + 86 * previousScore / (abs(previousScore) + 176); + int dct = ct + (102 - ct / 2) * previousScore / (abs(previousScore) + 157); contempt = (us == WHITE ? make_score(dct, dct / 2) : -make_score(dct, dct / 2)); @@ -516,12 +531,13 @@ void Thread::search() { && !Threads.stop && !mainThread->stopOnPonderhit) { - double fallingEval = (354 + 10 * (mainThread->previousScore - bestValue)) / 692.0; + double fallingEval = (332 + 6 * (mainThread->previousScore - bestValue) + + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 704.0; fallingEval = clamp(fallingEval, 0.5, 1.5); // If the bestMove is stable over several iterations, reduce time accordingly - timeReduction = lastBestMoveDepth + 9 < completedDepth ? 1.97 : 0.98; - double reduction = (1.36 + mainThread->previousTimeReduction) / (2.29 * timeReduction); + timeReduction = lastBestMoveDepth + 9 < completedDepth ? 1.94 : 0.91; + double reduction = (1.41 + mainThread->previousTimeReduction) / (2.27 * timeReduction); // Use part of the gained time from a previous stable move for the current move for (Thread* th : Threads) @@ -543,6 +559,9 @@ void Thread::search() { Threads.stop = true; } } + + mainThread->iterValue[iterIdx] = bestValue; + iterIdx = (iterIdx + 1) & 3; } if (!mainThread) @@ -661,10 +680,13 @@ namespace { excludedMove = ss->excludedMove; posKey = pos.key() ^ Key(excludedMove << 16); // Isn't a very good hash tte = TT.probe(posKey, ttHit); - ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; + ttValue = ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE; 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,12 +812,12 @@ 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 - && depth < 7 + && depth < 6 && eval - futility_margin(depth, improving) >= beta && eval < VALUE_KNOWN_WIN) // Do not return unproven wins return eval; @@ -803,10 +825,10 @@ namespace { // Step 9. Null move search with verification search (~40 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 22661 + && (ss-1)->statScore < 23405 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 33 * depth + 299 - improving * 30 + && ss->staticEval >= beta - 32 * depth + 317 - improving * 30 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -814,7 +836,7 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = (835 + 70 * depth) / 256 + std::min(int(eval - beta) / 185, 3); + Depth R = (854 + 68 * depth) / 258 + std::min(int(eval - beta) / 192, 3); ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0]; @@ -857,7 +879,7 @@ namespace { && depth >= 5 && abs(beta) < VALUE_MATE_IN_MAX_PLY) { - Value raisedBeta = std::min(beta + 191 - 46 * improving, VALUE_INFINITE); + Value raisedBeta = std::min(beta + 189 - 45 * improving, VALUE_INFINITE); MovePicker mp(pos, ttMove, raisedBeta - ss->staticEval, &thisThread->captureHistory); int probCutCount = 0; @@ -899,7 +921,7 @@ namespace { search(pos, ss, alpha, beta, depth - 7, cutNode); tte = TT.probe(posKey, ttHit); - ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; + ttValue = ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE; ttMove = ttHit ? tte->move() : MOVE_NONE; } @@ -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 + 255 + 182 * lmrDepth <= alpha) + continue; + + // Prune moves with negative SEE (~10 Elo) + if (!pos.see_ge(move, Value(-(32 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth))) + continue; + } + else if (!pos.see_ge(move, Value(-194) * 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; } @@ -999,65 +1057,23 @@ moves_loop: // When in check, search starts from here && (pos.is_discovery_check_on_king(~us, move) || pos.see_ge(move))) extension = 1; - // Shuffle extension - else if ( PvNode - && pos.rule50_count() > 18 - && depth < 3 - && ++thisThread->shuffleExts < thisThread->nodes.load(std::memory_order_relaxed) / 4) // To avoid too many extensions - extension = 1; - // Passed pawn extension else if ( move == ss->killers[0] && pos.advanced_pawn_push(move) && 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))); @@ -1087,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 < 375 * ttHitAverageResolution * ttHitAverageWindow / 1024)) { Depth r = reduction(improving, depth, moveCount); + // Decrease reduction if the ttHit running average is large + if (thisThread->ttHitAverage > 500 * ttHitAverageResolution * ttHitAverageWindow / 1024) + r--; + // Reduction if other threads are searching this position. if (th.marked()) r++; @@ -1100,7 +1121,7 @@ moves_loop: // When in check, search starts from here r -= 2; // Decrease reduction if opponent's move count is high (~10 Elo) - if ((ss-1)->moveCount > 15) + if ((ss-1)->moveCount > 14) r--; // Decrease reduction if ttMove has been singularly extended @@ -1128,7 +1149,7 @@ moves_loop: // When in check, search starts from here + (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] + (*contHist[3])[movedPiece][to_sq(move)] - - 4729; + - 4926; // Reset statScore to zero if negative and most stats shows >= 0 if ( ss->statScore < 0 @@ -1138,10 +1159,10 @@ moves_loop: // When in check, search starts from here ss->statScore = 0; // Decrease/increase reduction by comparing opponent's stat score (~10 Elo) - if (ss->statScore >= -99 && (ss-1)->statScore < -116) + if (ss->statScore >= -102 && (ss-1)->statScore < -114) r--; - else if ((ss-1)->statScore >= -117 && ss->statScore < -144) + else if ((ss-1)->statScore >= -116 && ss->statScore < -154) r++; // Decrease/increase reduction for moves with a good/bad history (~30 Elo) @@ -1351,7 +1372,7 @@ moves_loop: // When in check, search starts from here // Transposition table lookup posKey = pos.key(); tte = TT.probe(posKey, ttHit); - ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; + ttValue = ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE; ttMove = ttHit ? tte->move() : MOVE_NONE; pvHit = ttHit && tte->is_pv(); @@ -1400,7 +1421,7 @@ moves_loop: // When in check, search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + 153; + futilityBase = bestValue + 154; } const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, @@ -1456,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 @@ -1537,11 +1556,11 @@ moves_loop: // When in check, search starts from here // from the transposition table (which refers to the plies to mate/be mated // from current position) to "plies to mate/be mated from the root". - Value value_from_tt(Value v, int ply) { + Value value_from_tt(Value v, int ply, int r50c) { return v == VALUE_NONE ? VALUE_NONE - : v >= VALUE_MATE_IN_MAX_PLY ? v - ply - : v <= VALUE_MATED_IN_MAX_PLY ? v + ply : v; + : v >= VALUE_MATE_IN_MAX_PLY ? VALUE_MATE - v > 99 - r50c ? VALUE_MATE_IN_MAX_PLY : v - ply + : v <= VALUE_MATED_IN_MAX_PLY ? VALUE_MATE + v > 99 - r50c ? VALUE_MATED_IN_MAX_PLY : v + ply : v; } @@ -1719,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;