X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=b2c2344ac0aaff10a249bfb7f64a22fa0e648d6f;hb=e1dd005583bd6c2aaf58468efc5de86a3936380a;hp=93212e239b98def5e19c1f7b451f0b7555c33353;hpb=c701745cf243f4816754167e85bf5fabf5b34e47;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index 93212e23..b2c2344a 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(148 * (d - improving)); + return Value(140 * (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 + 1356 - int(delta) * 983 / int(rootDelta)) / 1024 + (!i && r > 901); + return (r + 1372 - int(delta) * 1073 / int(rootDelta)) / 1024 + (!i && r > 936); } 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(337 * d - 497, 1632); + return std::min(336 * d - 547, 1561); } // 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((20.89 + std::log(Threads.size()) / 2) * std::log(i)); + Reductions[i] = int((20.57 + 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(11) + int(prev) * prev / 15368; + delta = Value(10) + int(prev) * prev / 15799; alpha = std::max(prev - delta,-VALUE_INFINITE); beta = std::min(prev + delta, VALUE_INFINITE); // Adjust optimism based on root move's previousScore - int opt = 116 * prev / (std::abs(prev) + 143); + int opt = 109 * prev / (std::abs(prev) + 141); optimism[ us] = Value(opt); optimism[~us] = -optimism[us]; @@ -741,7 +741,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), -1717, 1717); + int bonus = std::clamp(-18 * int((ss-1)->staticEval + ss->staticEval), -1817, 1817); thisThread->mainHistory[~us][from_to((ss-1)->currentMove)] << bonus; } @@ -751,13 +751,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 - : 163; + : 173; 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 - 467 - 266 * depth * depth) + if (eval < alpha - 456 - 252 * depth * depth) { value = qsearch(pos, ss, alpha - 1, alpha); if (value < alpha) @@ -770,16 +770,16 @@ namespace { && depth < 9 && eval - futility_margin(depth, improving) - (ss-1)->statScore / 306 >= beta && eval >= beta - && eval < 22761) // larger than VALUE_KNOWN_WIN, but smaller than TB wins + && eval < 24923) // 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 < 18404 + && (ss-1)->statScore < 17329 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 19 * depth - improvement / 13 + 257 + && ss->staticEval >= beta - 21 * depth - improvement / 13 + 258 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly)) @@ -787,7 +787,7 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and eval - Depth R = std::min(int(eval - beta) / 172, 6) + depth / 3 + 4; + Depth R = std::min(int(eval - beta) / 173, 6) + depth / 3 + 4; ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0]; @@ -822,9 +822,24 @@ namespace { } } - probCutBeta = beta + 174 - 60 * improving; + // Step 10. If the position doesn't a have ttMove, decrease depth by 2 + // (or by 4 if the TT entry for the current position was hit and the stored depth is greater than or equal to the current depth). + // Use qsearch if depth is equal or below zero (~9 Elo) + if ( PvNode + && !ttMove) + depth -= 2 + 2 * (ss->ttHit && tte->depth() >= depth); + + if (depth <= 0) + return qsearch(pos, ss, alpha, beta); - // Step 10. ProbCut (~10 Elo) + if ( cutNode + && depth >= 8 + && !ttMove) + depth -= 2; + + probCutBeta = beta + 168 - 61 * improving; + + // Step 11. 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 @@ -875,27 +890,12 @@ namespace { Eval::NNUE::hint_common_parent_position(pos); } - // Step 11. If the position is not in TT, decrease depth by 2 (or by 4 if the TT entry for the current position was hit and the stored depth is greater than or equal to the current depth). - // Use qsearch if depth is equal or below zero (~9 Elo) - if ( PvNode - && !ttMove) - depth -= 2 + 2 * (ss->ttHit && tte->depth() >= depth); - - if (depth <= 0) - return qsearch(pos, ss, alpha, beta); - - if ( cutNode - && 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 + 430; + probCutBeta = beta + 413; if ( ss->inCheck && !PvNode - && depth >= 2 && ttCapture && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 4 @@ -986,7 +986,7 @@ moves_loop: // When in check, search starts here if ( !givesCheck && lmrDepth < 7 && !ss->inCheck - && ss->staticEval + 207 + 223 * lmrDepth + PieceValue[EG][pos.piece_on(to_sq(move))] + && ss->staticEval + 197 + 248 * 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; @@ -994,20 +994,23 @@ moves_loop: // When in check, search starts here // SEE based pruning (~11 Elo) if (!pos.see_ge(move, occupied, Value(-205) * depth)) { - // 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); - while (leftEnemies && !attacks) - { + if (depth < 2 - capture) + continue; + // Don't prune the move if opponent Queen/Rook is under discovered attack after the exchanges + // Don't prune the move if opponent King is under discovered attack after or during the exchanges + Bitboard leftEnemies = (pos.pieces(~us, KING, QUEEN, ROOK)) & occupied; + Bitboard attacks = 0; + occupied |= to_sq(move); + while (leftEnemies && !attacks) + { 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 (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; - } - if (!attacks) - continue; + attacks |= pos.attackers_to(sq, occupied) & pos.pieces(us) & occupied; + // don't consider pieces which were already threatened/hanging before SEE exchanges + if (attacks && (sq != pos.square(~us) && (pos.attackers_to(sq, pos.pieces()) & pos.pieces(us)))) + attacks = 0; + } + if (!attacks) + continue; } } else @@ -1018,18 +1021,18 @@ moves_loop: // When in check, search starts here // Continuation history based pruning (~2 Elo) if ( lmrDepth < 6 - && history < -3792 * depth) + && history < -3832 * depth) continue; history += 2 * thisThread->mainHistory[us][from_to(move)]; - lmrDepth += history / 7019; + lmrDepth += history / 7011; lmrDepth = std::max(lmrDepth, -2); // Futility pruning: parent node (~13 Elo) if ( !ss->inCheck && lmrDepth < 12 - && ss->staticEval + 111 + 136 * lmrDepth <= alpha) + && ss->staticEval + 112 + 138 * lmrDepth <= alpha) continue; lmrDepth = std::max(lmrDepth, 0); @@ -1058,7 +1061,7 @@ moves_loop: // When in check, search starts here && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3) { - Value singularBeta = ttValue - (99 + 65 * (ss->ttPv && !PvNode)) * depth / 64; + Value singularBeta = ttValue - (82 + 65 * (ss->ttPv && !PvNode)) * depth / 64; Depth singularDepth = (depth - 1) / 2; ss->excludedMove = move; @@ -1072,7 +1075,7 @@ moves_loop: // When in check, search starts here // Avoid search explosion by limiting the number of double extensions if ( !PvNode - && value < singularBeta - 22 + && value < singularBeta - 21 && ss->doubleExtensions <= 11) { extension = 2; @@ -1103,15 +1106,14 @@ moves_loop: // When in check, search starts here // Check extensions (~1 Elo) else if ( givesCheck - && depth > 9 - && abs(ss->staticEval) > 87) + && depth > 9) extension = 1; // Quiet ttMove extensions (~1 Elo) else if ( PvNode && move == ttMove && move == ss->killers[0] - && (*contHist[0])[movedPiece][to_sq(move)] >= 5480) + && (*contHist[0])[movedPiece][to_sq(move)] >= 5168) extension = 1; } @@ -1153,7 +1155,7 @@ moves_loop: // When in check, search starts here // Decrease reduction for PvNodes based on depth (~2 Elo) if (PvNode) - r -= 1 + 11 / (3 + depth); + r -= 1 + 12 / (3 + depth); // Decrease reduction if ttMove has been singularly extended (~1 Elo) if (singularQuietLMR) @@ -1170,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)] - - 3755; + - 4006; // Decrease/increase reduction for moves with a good/bad history (~25 Elo) - r -= ss->statScore / (10445 + 4762 * (depth > 6 && depth < 21)); + r -= ss->statScore / (11124 + 4740 * (depth > 5 && depth < 22)); // Step 17. Late moves reduction / extension (LMR, ~117 Elo) // We use various heuristics for the sons of a node after the first son has @@ -1197,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 > (bestValue + 63 + 11 * (newDepth - d)); - const bool doEvenDeeperSearch = value > alpha + 662 && ss->doubleExtensions <= 6; + const bool doDeeperSearch = value > (bestValue + 64 + 11 * (newDepth - d)); + const bool doEvenDeeperSearch = value > alpha + 711 && ss->doubleExtensions <= 6; const bool doShallowerSearch = value < bestValue + newDepth; ss->doubleExtensions = ss->doubleExtensions + doEvenDeeperSearch; @@ -1317,8 +1319,8 @@ moves_loop: // When in check, search starts here // 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 < 14001 - && value > -12754) + && beta < 14362 + && value > -12393) depth -= depth > 3 && depth < 12 ? 2 : 1; assert(depth > 0); @@ -1367,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 - 100 * depth) + ((ss-1)->moveCount > 11); + int bonus = (depth > 5) + (PvNode || cutNode) + (bestValue < alpha - 113 * depth) + ((ss-1)->moveCount > 12); update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * bonus); } @@ -1495,7 +1497,7 @@ moves_loop: // When in check, search starts here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + 190; + futilityBase = bestValue + 200; } const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, @@ -1506,7 +1508,7 @@ moves_loop: // When in check, search starts here // to search the moves. Because the depth is <= 0 here, only captures, // queen promotions, and other checks (only if depth >= DEPTH_QS_CHECKS) // will be generated. - Square prevSq = (ss-1)->currentMove != MOVE_NULL ? to_sq((ss-1)->currentMove) : SQ_NONE; + Square prevSq = is_ok((ss-1)->currentMove) ? to_sq((ss-1)->currentMove) : SQ_NONE; MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &thisThread->captureHistory, contHist, @@ -1568,7 +1570,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(-94))) + if (!pos.see_ge(move, Value(-95))) continue; } @@ -1701,7 +1703,7 @@ moves_loop: // When in check, search starts here if (!pos.capture_stage(bestMove)) { - int bonus2 = bestValue > beta + 143 ? bonus1 // larger bonus + int bonus2 = bestValue > beta + 145 ? bonus1 // larger bonus : stat_bonus(depth); // smaller bonus // Increase stats for the best move in case it was a quiet move