X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=32eeedab4ae281d707ef5d4da067f2121c75302a;hb=cedd73f4aa9f83c2891105695ac11e743e6ceab7;hp=8ce9c56e42d0849e2caf9b2528d463faf524fe21;hpb=21d6b69f7c8d0c0a71fe627714913a59d39a3b57;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index 8ce9c56e..32eeedab 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -64,7 +64,7 @@ namespace { // Futility margin Value futility_margin(Depth d, bool improving) { - return Value(154 * (d - improving)); + return Value(148 * (d - improving)); } // Reductions lookup table, initialized at startup @@ -72,7 +72,7 @@ namespace { Depth reduction(bool i, Depth d, int mn, Value delta, Value rootDelta) { int r = Reductions[d] * Reductions[mn]; - return (r + 1449 - int(delta) * 937 / int(rootDelta)) / 1024 + (!i && r > 941); + return (r + 1356 - int(delta) * 983 / int(rootDelta)) / 1024 + (!i && r > 901); } constexpr int futility_move_count(bool improving, Depth depth) { @@ -82,7 +82,7 @@ namespace { // History and stats update bonus, based on depth int stat_bonus(Depth d) { - return std::min(341 * d - 470, 1710); + return std::min(337 * d - 497, 1632); } // Add a small random component to draw evaluations to avoid 3-fold blindness @@ -162,7 +162,7 @@ namespace { void Search::init() { for (int i = 1; i < MAX_MOVES; ++i) - Reductions[i] = int((19.47 + std::log(Threads.size()) / 2) * std::log(i)); + Reductions[i] = int((20.89 + std::log(Threads.size()) / 2) * std::log(i)); } @@ -348,12 +348,12 @@ void Thread::search() { // Reset aspiration window starting size Value prev = rootMoves[pvIdx].averageScore; - delta = Value(10) + int(prev) * prev / 16502; + delta = Value(11) + int(prev) * prev / 15368; alpha = std::max(prev - delta,-VALUE_INFINITE); beta = std::min(prev + delta, VALUE_INFINITE); // Adjust optimism based on root move's previousScore - int opt = 102 * prev / (std::abs(prev) + 147); + int opt = 116 * prev / (std::abs(prev) + 143); optimism[ us] = Value(opt); optimism[~us] = -optimism[us]; @@ -409,7 +409,7 @@ void Thread::search() { else break; - delta += delta / 4 + 2; + delta += delta / 3; assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE); } @@ -724,11 +724,8 @@ namespace { ss->staticEval = eval = tte->eval(); if (eval == VALUE_NONE) ss->staticEval = eval = evaluate(pos); - else - { - if (PvNode) - Eval::NNUE::hint_common_parent_position(pos); - } + else if (PvNode) + Eval::NNUE::hint_common_parent_position(pos); // ttValue can be used as a better position evaluation (~7 Elo) if ( ttValue != VALUE_NONE @@ -745,7 +742,7 @@ namespace { // Use static evaluation difference to improve quiet move ordering (~4 Elo) if (is_ok((ss-1)->currentMove) && !(ss-1)->inCheck && !priorCapture) { - int bonus = std::clamp(-19 * int((ss-1)->staticEval + ss->staticEval), -1920, 1920); + int bonus = std::clamp(-19 * int((ss-1)->staticEval + ss->staticEval), -1717, 1717); thisThread->mainHistory[~us][from_to((ss-1)->currentMove)] << bonus; } @@ -755,13 +752,13 @@ namespace { // margin and the improving flag are used in various pruning heuristics. improvement = (ss-2)->staticEval != VALUE_NONE ? ss->staticEval - (ss-2)->staticEval : (ss-4)->staticEval != VALUE_NONE ? ss->staticEval - (ss-4)->staticEval - : 156; + : 163; improving = improvement > 0; // Step 7. Razoring (~1 Elo). // If eval is really low check with qsearch if it can exceed alpha, if it can't, // return a fail low. - if (eval < alpha - 426 - 256 * depth * depth) + if (eval < alpha - 467 - 266 * depth * depth) { value = qsearch(pos, ss, alpha - 1, alpha); if (value < alpha) @@ -772,18 +769,18 @@ namespace { // The depth condition is important for mate finding. if ( !ss->ttPv && depth < 9 - && eval - futility_margin(depth, improving) - (ss-1)->statScore / 280 >= beta + && eval - futility_margin(depth, improving) - (ss-1)->statScore / 306 >= beta && eval >= beta - && eval < 25128) // larger than VALUE_KNOWN_WIN, but smaller than TB wins + && eval < 22761) // larger than VALUE_KNOWN_WIN, but smaller than TB wins return eval; // Step 9. Null move search with verification search (~35 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 18755 + && (ss-1)->statScore < 18404 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 20 * depth - improvement / 13 + 253 + && ss->staticEval >= beta - 19 * depth - improvement / 13 + 257 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly)) @@ -826,13 +823,13 @@ namespace { } } - probCutBeta = beta + 186 - 54 * improving; + probCutBeta = beta + 174 - 60 * improving; // Step 10. ProbCut (~10 Elo) // If we have a good enough capture (or queen promotion) and a reduced search returns a value // much above beta, we can (almost) safely prune the previous move. if ( !PvNode - && depth > 4 + && depth > 3 && abs(beta) < VALUE_TB_WIN_IN_MAX_PLY // if value from transposition table is lower than probCutBeta, don't attempt probCut // there and in further interactions with transposition table cutoff depth is set to depth - 3 @@ -884,26 +881,26 @@ namespace { // Use qsearch if depth is equal or below zero (~9 Elo) if ( PvNode && !ttMove) - depth -= 2 + 2 * (ss->ttHit && tte->depth() >= depth); + depth -= 2 + 2 * (ss->ttHit && tte->depth() >= depth); if (depth <= 0) return qsearch(pos, ss, alpha, beta); if ( cutNode - && depth >= 7 + && depth >= 8 && !ttMove) depth -= 2; moves_loop: // When in check, search starts here // Step 12. A small Probcut idea, when we are in check (~4 Elo) - probCutBeta = beta + 391; + probCutBeta = beta + 430; if ( ss->inCheck && !PvNode && depth >= 2 && ttCapture && (tte->bound() & BOUND_LOWER) - && tte->depth() >= depth - 3 + && tte->depth() >= depth - 4 && ttValue >= probCutBeta && abs(ttValue) <= VALUE_KNOWN_WIN && abs(beta) <= VALUE_KNOWN_WIN) @@ -982,26 +979,24 @@ moves_loop: // When in check, search starts here moveCountPruning = moveCount >= futility_move_count(improving, depth); // Reduced depth of the next LMR search - int lmrDepth = std::max(newDepth - r, 0); + int lmrDepth = newDepth - r; if ( capture || givesCheck) { // Futility pruning for captures (~2 Elo) if ( !givesCheck - && lmrDepth < 6 + && lmrDepth < 7 && !ss->inCheck - && ss->staticEval + 182 + 230 * lmrDepth + PieceValue[EG][pos.piece_on(to_sq(move))] + && ss->staticEval + 207 + 223 * lmrDepth + PieceValue[EG][pos.piece_on(to_sq(move))] + captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))] / 7 < alpha) continue; Bitboard occupied; // SEE based pruning (~11 Elo) - if (!pos.see_ge(move, occupied, Value(-206) * depth)) + if (!pos.see_ge(move, occupied, Value(-205) * depth)) { - if (depth < 2 - capture) - continue; - // Don't prune the move if opp. King/Queen/Rook gets a discovered attack during or after the exchanges + // Don't prune the move if opponent King/Queen/Rook gets a discovered attack during or after the exchanges Bitboard leftEnemies = pos.pieces(~us, KING, QUEEN, ROOK); Bitboard attacks = 0; occupied |= to_sq(move); @@ -1009,7 +1004,7 @@ moves_loop: // When in check, search starts here { Square sq = pop_lsb(leftEnemies); attacks = pos.attackers_to(sq, occupied) & pos.pieces(us) & occupied; - // Exclude Queen/Rook(s) which were already threatened before SEE (opp King can't be in check when it's our turn) + // Exclude Queen/Rook(s) which were already threatened before SEE (opponent King can't be in check when it's our turn) if (attacks && sq != pos.square(~us) && (pos.attackers_to(sq, pos.pieces()) & pos.pieces(us))) attacks = 0; } @@ -1024,25 +1019,25 @@ moves_loop: // When in check, search starts here + (*contHist[3])[movedPiece][to_sq(move)]; // Continuation history based pruning (~2 Elo) - if ( lmrDepth < 5 - && history < -4405 * (depth - 1)) + if ( lmrDepth < 6 + && history < -3792 * depth) continue; history += 2 * thisThread->mainHistory[us][from_to(move)]; - lmrDepth += history / 7278; + lmrDepth += history / 7019; lmrDepth = std::max(lmrDepth, -2); // Futility pruning: parent node (~13 Elo) if ( !ss->inCheck - && lmrDepth < 13 - && ss->staticEval + 103 + 138 * lmrDepth <= alpha) + && lmrDepth < 12 + && ss->staticEval + 111 + 136 * lmrDepth <= alpha) continue; lmrDepth = std::max(lmrDepth, 0); // Prune moves with negative SEE (~4 Elo) - if (!pos.see_ge(move, Value(-24 * lmrDepth * lmrDepth - 16 * lmrDepth))) + if (!pos.see_ge(move, Value(-27 * lmrDepth * lmrDepth - 16 * lmrDepth))) continue; } } @@ -1057,7 +1052,7 @@ moves_loop: // When in check, search starts here // a reduced search on all the other moves but the ttMove and if the // result is lower than ttValue minus a margin, then we will extend the ttMove. if ( !rootNode - && depth >= 4 - (thisThread->completedDepth > 21) + 2 * (PvNode && tte->is_pv()) + && depth >= 4 - (thisThread->completedDepth > 22) + 2 * (PvNode && tte->is_pv()) && move == ttMove && !excludedMove // Avoid recursive singular search /* && ttValue != VALUE_NONE Already implicit in the next condition */ @@ -1065,7 +1060,7 @@ moves_loop: // When in check, search starts here && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3) { - Value singularBeta = ttValue - (3 + 2 * (ss->ttPv && !PvNode)) * depth / 2; + Value singularBeta = ttValue - (99 + 65 * (ss->ttPv && !PvNode)) * depth / 64; Depth singularDepth = (depth - 1) / 2; ss->excludedMove = move; @@ -1079,8 +1074,8 @@ moves_loop: // When in check, search starts here // Avoid search explosion by limiting the number of double extensions if ( !PvNode - && value < singularBeta - 25 - && ss->doubleExtensions <= 10) + && value < singularBeta - 22 + && ss->doubleExtensions <= 11) { extension = 2; depth += depth < 13; @@ -1110,15 +1105,15 @@ moves_loop: // When in check, search starts here // Check extensions (~1 Elo) else if ( givesCheck - && depth > 10 - && abs(ss->staticEval) > 88) + && depth > 9 + && abs(ss->staticEval) > 87) extension = 1; // Quiet ttMove extensions (~1 Elo) else if ( PvNode && move == ttMove && move == ss->killers[0] - && (*contHist[0])[movedPiece][to_sq(move)] >= 5705) + && (*contHist[0])[movedPiece][to_sq(move)] >= 5480) extension = 1; } @@ -1141,12 +1136,13 @@ moves_loop: // When in check, search starts here // Decrease reduction if position is or has been on the PV // and node is not likely to fail low. (~3 Elo) + // Decrease further on cutNodes. (~1 Elo) if ( ss->ttPv && !likelyFailLow) - r -= 2; + r -= cutNode && tte->depth() >= depth + 3 ? 3 : 2; // Decrease reduction if opponent's move count is high (~1 Elo) - if ((ss-1)->moveCount > 7) + if ((ss-1)->moveCount > 8) r--; // Increase reduction for cut nodes (~3 Elo) @@ -1159,7 +1155,7 @@ moves_loop: // When in check, search starts here // Decrease reduction for PvNodes based on depth (~2 Elo) if (PvNode) - r -= 1 + 12 / (3 + depth); + r -= 1 + 11 / (3 + depth); // Decrease reduction if ttMove has been singularly extended (~1 Elo) if (singularQuietLMR) @@ -1176,10 +1172,10 @@ moves_loop: // When in check, search starts here + (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] + (*contHist[3])[movedPiece][to_sq(move)] - - 4082; + - 3755; // Decrease/increase reduction for moves with a good/bad history (~25 Elo) - r -= ss->statScore / (11079 + 4626 * (depth > 6 && depth < 19)); + r -= ss->statScore / (10445 + 4762 * (depth > 6 && depth < 21)); // Step 17. Late moves reduction / extension (LMR, ~117 Elo) // We use various heuristics for the sons of a node after the first son has @@ -1203,8 +1199,8 @@ moves_loop: // When in check, search starts here { // Adjust full depth search based on LMR results - if result // was good enough search deeper, if it was bad enough search shallower - const bool doDeeperSearch = value > (alpha + 58 + 12 * (newDepth - d)); - const bool doEvenDeeperSearch = value > alpha + 588 && ss->doubleExtensions <= 5; + const bool doDeeperSearch = value > (bestValue + 63 + 11 * (newDepth - d)); + const bool doEvenDeeperSearch = value > alpha + 662 && ss->doubleExtensions <= 6; const bool doShallowerSearch = value < bestValue + newDepth; ss->doubleExtensions = ss->doubleExtensions + doEvenDeeperSearch; @@ -1229,7 +1225,7 @@ moves_loop: // When in check, search starts here if (!ttMove && cutNode) r += 2; - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth - (r > 4), !cutNode); + value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth - (r > 3), !cutNode); } // For PV nodes only, do a full PV search on the first move or after a fail @@ -1312,22 +1308,23 @@ moves_loop: // When in check, search starts here if (PvNode && !rootNode) // Update pv even in fail-high case update_pv(ss->pv, move, (ss+1)->pv); - if (PvNode && value < beta) // Update alpha! Always alpha < beta + if (value >= beta) + { + ss->cutoffCnt += 1 + !ttMove; + assert(value >= beta); // Fail high + break; + } + else { // Reduce other moves if we have found at least one score improvement (~1 Elo) + // Reduce more for depth > 3 and depth < 12 (~1 Elo) if ( depth > 1 - && beta < 12535 - && value > -12535) - depth -= 1; + && beta < 14001 + && value > -12754) + depth -= depth > 3 && depth < 12 ? 2 : 1; assert(depth > 0); - alpha = value; - } - else - { - ss->cutoffCnt++; - assert(value >= beta); // Fail high - break; + alpha = value; // Update alpha! Always alpha < beta } } } @@ -1372,7 +1369,7 @@ moves_loop: // When in check, search starts here // Bonus for prior countermove that caused the fail low else if (!priorCapture && prevSq != SQ_NONE) { - int bonus = (depth > 5) + (PvNode || cutNode) + (bestValue < alpha - 97 * depth) + ((ss-1)->moveCount > 10); + int bonus = (depth > 5) + (PvNode || cutNode) + (bestValue < alpha - 100 * depth) + ((ss-1)->moveCount > 11); update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * bonus); } @@ -1501,7 +1498,7 @@ moves_loop: // When in check, search starts here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + 168; + futilityBase = bestValue + 190; } const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, @@ -1574,7 +1571,7 @@ moves_loop: // When in check, search starts here continue; // Do not search moves with bad enough SEE values (~5 Elo) - if (!pos.see_ge(move, Value(-110))) + if (!pos.see_ge(move, Value(-94))) continue; } @@ -1707,7 +1704,7 @@ moves_loop: // When in check, search starts here if (!pos.capture_stage(bestMove)) { - int bonus2 = bestValue > beta + 153 ? bonus1 // larger bonus + int bonus2 = bestValue > beta + 143 ? bonus1 // larger bonus : stat_bonus(depth); // smaller bonus // Increase stats for the best move in case it was a quiet move