X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=86af39183fbb7631c355095506def88daf16e1b8;hb=ad926d34c0105d523bfa5cb92cbcf9f337d54c08;hp=2abfbaf2f3dd35d6f0fb414a03fa13b327bcca90;hpb=dc5d9bdfee70f4267d9a49ad71e5ee478dd50ca5;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index 2abfbaf2..86af3918 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -1,6 +1,6 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 - Copyright (C) 2004-2021 The Stockfish developers (see AUTHORS file) + Copyright (C) 2004-2022 The Stockfish developers (see AUTHORS file) Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -69,9 +69,9 @@ namespace { // Reductions lookup table, initialized at startup int Reductions[MAX_MOVES]; // [depth or moveNumber] - Depth reduction(bool i, Depth d, int mn, bool rangeReduction) { + Depth reduction(bool i, Depth d, int mn, Value delta, Value rootDelta) { int r = Reductions[d] * Reductions[mn]; - return (r + 534) / 1024 + (!i && r > 904) + rangeReduction; + return (r + 1358 - int(delta) * 1024 / int(rootDelta)) / 1024 + (!i && r > 904); } constexpr int futility_move_count(bool improving, Depth depth) { @@ -550,7 +550,7 @@ namespace { if ( ss->ply > 10 && search_explosion(thisThread) == MUST_CALM_DOWN && depth > (ss-1)->depth) - depth = (ss-1)->depth; + depth = (ss-1)->depth; constexpr bool PvNode = nodeType != NonPV; constexpr bool rootNode = nodeType == Root; @@ -671,20 +671,20 @@ namespace { && (ttValue >= beta ? (tte->bound() & BOUND_LOWER) : (tte->bound() & BOUND_UPPER))) { - // If ttMove is quiet, update move sorting heuristics on TT hit + // If ttMove is quiet, update move sorting heuristics on TT hit (~1 Elo) if (ttMove) { if (ttValue >= beta) { - // Bonus for a quiet ttMove that fails high + // Bonus for a quiet ttMove that fails high (~3 Elo) if (!ttCapture) update_quiet_stats(pos, ss, ttMove, stat_bonus(depth)); - // Extra penalty for early quiet moves of the previous ply + // Extra penalty for early quiet moves of the previous ply (~0 Elo) if ((ss-1)->moveCount <= 2 && !priorCapture) update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + 1)); } - // Penalty for a quiet ttMove that fails low + // Penalty for a quiet ttMove that fails low (~1 Elo) else if (!ttCapture) { int penalty = -stat_bonus(depth); @@ -773,7 +773,7 @@ namespace { if (eval == VALUE_DRAW) eval = value_draw(thisThread); - // Can ttValue be used as a better position evaluation? + // ttValue can be used as a better position evaluation (~4 Elo) if ( ttValue != VALUE_NONE && (tte->bound() & (ttValue > eval ? BOUND_LOWER : BOUND_UPPER))) eval = ttValue; @@ -787,7 +787,7 @@ namespace { tte->save(posKey, VALUE_NONE, ss->ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); } - // Use static evaluation difference to improve quiet move ordering + // Use static evaluation difference to improve quiet move ordering (~3 Elo) if (is_ok((ss-1)->currentMove) && !(ss-1)->inCheck && !priorCapture) { int bonus = std::clamp(-16 * int((ss-1)->staticEval + ss->staticEval), -2000, 2000); @@ -804,7 +804,7 @@ namespace { improving = improvement > 0; - // Step 7. Futility pruning: child node (~50 Elo). + // Step 7. Futility pruning: child node (~25 Elo). // The depth condition is important for mate finding. if ( !ss->ttPv && depth < 9 @@ -812,7 +812,7 @@ namespace { && eval < 15000) // 50% larger than VALUE_KNOWN_WIN, but smaller than TB wins. return eval; - // Step 8. Null move search with verification search (~40 Elo) + // Step 8. Null move search with verification search (~22 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL && (ss-1)->statScore < 23767 @@ -925,7 +925,7 @@ namespace { ss->ttPv = ttPv; } - // Step 10. If the position is not in TT, decrease depth by 2 or 1 depending on node type + // Step 10. If the position is not in TT, decrease depth by 2 or 1 depending on node type (~3 Elo) if ( PvNode && depth >= 6 && !ttMove) @@ -938,9 +938,7 @@ namespace { moves_loop: // When in check, search starts here - int rangeReduction = 0; - - // Step 11. A small Probcut idea, when we are in check + // Step 11. A small Probcut idea, when we are in check (~0 Elo) probCutBeta = beta + 409; if ( ss->inCheck && !PvNode @@ -1015,28 +1013,34 @@ moves_loop: // When in check, search starts here // Calculate new depth for this move newDepth = depth - 1; - // Step 13. Pruning at shallow depth (~200 Elo). Depth conditions are important for mate finding. + Value delta = beta - alpha; + + // Step 13. Pruning at shallow depth (~98 Elo). Depth conditions are important for mate finding. if ( !rootNode && pos.non_pawn_material(us) && bestValue > VALUE_TB_LOSS_IN_MAX_PLY) { - // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold + // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold (~7 Elo) moveCountPruning = moveCount >= futility_move_count(improving, depth); // Reduced depth of the next LMR search - int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount, rangeReduction > 2), 0); + int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount, delta, thisThread->rootDelta), 0); if ( captureOrPromotion || givesCheck) { - // Capture history based pruning when the move doesn't give check - if ( !givesCheck - && lmrDepth < 1 - && captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))] < 0) + // Futility pruning for captures (~0 Elo) + if ( !pos.empty(to_sq(move)) + && !givesCheck + && !PvNode + && lmrDepth < 6 + && !ss->inCheck + && ss->staticEval + 342 + 238 * lmrDepth + PieceValue[EG][pos.piece_on(to_sq(move))] + + captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))] / 8 < alpha) continue; - // SEE based pruning - if (!pos.see_ge(move, Value(-218) * depth)) // (~25 Elo) + // SEE based pruning (~9 Elo) + if (!pos.see_ge(move, Value(-218) * depth)) continue; } else @@ -1045,30 +1049,28 @@ moves_loop: // When in check, search starts here + (*contHist[1])[movedPiece][to_sq(move)] + (*contHist[3])[movedPiece][to_sq(move)]; - // Continuation history based pruning (~20 Elo) + // Continuation history based pruning (~2 Elo) if ( lmrDepth < 5 && history < -3000 * depth + 3000) continue; history += thisThread->mainHistory[us][from_to(move)]; - lmrDepth = std::max(0, lmrDepth - (beta - alpha < thisThread->rootDelta / 4)); - - // Futility pruning: parent node (~5 Elo) + // Futility pruning: parent node (~9 Elo) if ( !ss->inCheck && lmrDepth < 8 && ss->staticEval + 142 + 139 * lmrDepth + history / 64 <= alpha) continue; - // Prune moves with negative SEE (~20 Elo) + // Prune moves with negative SEE (~3 Elo) if (!pos.see_ge(move, Value(-21 * lmrDepth * lmrDepth - 21 * lmrDepth))) continue; } } - // Step 14. Extensions (~75 Elo) + // Step 14. Extensions (~66 Elo) - // Singular extension search (~70 Elo). If all moves but one fail low on a + // Singular extension search (~58 Elo). If all moves but one fail low on a // search of (alpha-s, beta-s), and just one fails high on (alpha, beta), // then that move is singular and should be extended. To verify this we do // a reduced search on all the other moves but the ttMove and if the @@ -1113,19 +1115,13 @@ moves_loop: // When in check, search starts here extension = -2; } - // Capture extensions for PvNodes and cutNodes - else if ( (PvNode || cutNode) - && captureOrPromotion - && moveCount != 1) - extension = 1; - - // Check extensions + // Check extensions (~1 Elo) else if ( givesCheck && depth > 6 && abs(ss->staticEval) > 100) extension = 1; - // Quiet ttMove extensions + // Quiet ttMove extensions (~0 Elo) else if ( PvNode && move == ttMove && move == ss->killers[0] @@ -1151,7 +1147,7 @@ moves_loop: // When in check, search starts here bool doDeeperSearch = false; - // Step 16. Late moves reduction / extension (LMR, ~200 Elo) + // Step 16. Late moves reduction / extension (LMR, ~98 Elo) // We use various heuristics for the sons of a node after the first son has // been searched. In general we would like to reduce them, but there are many // cases where we extend a son if it has good chances to be "interesting". @@ -1161,12 +1157,11 @@ moves_loop: // When in check, search starts here || !captureOrPromotion || (cutNode && (ss-1)->moveCount > 1))) { - Depth r = reduction(improving, depth, moveCount, rangeReduction > 2); + Depth r = reduction(improving, depth, moveCount, delta, thisThread->rootDelta); // Decrease reduction at some PvNodes (~2 Elo) if ( PvNode - && bestMoveCount <= 3 - && beta - alpha >= thisThread->rootDelta / 4) + && bestMoveCount <= 3) r--; // Decrease reduction if position is or has been on the PV @@ -1175,10 +1170,6 @@ moves_loop: // When in check, search starts here && !likelyFailLow) r -= 2; - // Increase reduction at non-PV nodes (~3 Elo) - if (!PvNode) - r++; - // Decrease reduction if opponent's move count is high (~1 Elo) if ((ss-1)->moveCount > 13) r--; @@ -1213,13 +1204,9 @@ moves_loop: // When in check, search starts here value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - // Range reductions (~3 Elo) - if (ss->staticEval - value < 30 && depth > 7) - rangeReduction++; - // If the son is reduced and fails high it will be re-searched at full depth doFullDepthSearch = value > alpha && d < newDepth; - doDeeperSearch = value > alpha + 88; + doDeeperSearch = value > (alpha + 62 + 20 * (newDepth - d)); didLMR = true; } else @@ -1287,7 +1274,7 @@ moves_loop: // When in check, search starts here rm.pv.push_back(*m); // We record how often the best move has been changed in each iteration. - // This information is used for time management and LMR. In MultiPV mode, + // This information is used for time management. In MultiPV mode, // we must take care to only do this for the first PV line. if ( moveCount > 1 && !thisThread->pvIdx) @@ -1474,7 +1461,7 @@ moves_loop: // When in check, search starts here if ((ss->staticEval = bestValue = tte->eval()) == VALUE_NONE) ss->staticEval = bestValue = evaluate(pos); - // Can ttValue be used as a better position evaluation? + // ttValue can be used as a better position evaluation (~7 Elo) if ( ttValue != VALUE_NONE && (tte->bound() & (ttValue > bestValue ? BOUND_LOWER : BOUND_UPPER))) bestValue = ttValue; @@ -1510,10 +1497,11 @@ 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 = to_sq((ss-1)->currentMove); MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &thisThread->captureHistory, contHist, - to_sq((ss-1)->currentMove)); + prevSq); // Loop through the moves until no moves remain or a beta cutoff occurs while ((move = mp.next_move()) != MOVE_NONE) @@ -1529,9 +1517,10 @@ moves_loop: // When in check, search starts here moveCount++; - // Futility pruning and moveCount pruning + // Futility pruning and moveCount pruning (~5 Elo) if ( bestValue > VALUE_TB_LOSS_IN_MAX_PLY && !givesCheck + && to_sq(move) != prevSq && futilityBase > -VALUE_KNOWN_WIN && type_of(move) != PROMOTION) { @@ -1554,7 +1543,7 @@ moves_loop: // When in check, search starts here } } - // Do not search moves with negative SEE values + // Do not search moves with negative SEE values (~5 Elo) if ( bestValue > VALUE_TB_LOSS_IN_MAX_PLY && !pos.see_ge(move)) continue; @@ -1568,7 +1557,7 @@ moves_loop: // When in check, search starts here [pos.moved_piece(move)] [to_sq(move)]; - // Continuation history based pruning + // Continuation history based pruning (~2 Elo) if ( !captureOrPromotion && bestValue > VALUE_TB_LOSS_IN_MAX_PLY && (*contHist[0])[pos.moved_piece(move)][to_sq(move)] < CounterMovePruneThreshold