X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=b5d21b9d5585c2cfbeed24a6470f9df69c8aa907;hp=b96efad09aa615af0dd6fda0db756dcaef402905;hb=40cb0f076a62115af030c4524825d9ba73d61023;hpb=8985c210a1c40770fb81085bd908f757c486963c diff --git a/src/search.cpp b/src/search.cpp index b96efad0..b5d21b9d 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-2020 The Stockfish developers (see AUTHORS file) + Copyright (C) 2004-2021 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 @@ -62,8 +62,7 @@ namespace { constexpr uint64_t TtHitAverageWindow = 4096; constexpr uint64_t TtHitAverageResolution = 1024; - // Razor and futility margins - constexpr int RazorMargin = 510; + // Futility margin Value futility_margin(Depth d, bool improving) { return Value(234 * (d - improving)); } @@ -82,10 +81,10 @@ namespace { // History and stats update bonus, based on depth int stat_bonus(Depth d) { - return d > 14 ? 29 : 8 * d * d + 224 * d - 215; + return d > 14 ? 66 : 6 * d * d + 231 * d - 206; } - // Add a small random component to draw evaluations to avoid 3fold-blindness + // Add a small random component to draw evaluations to avoid 3-fold blindness Value value_draw(Thread* thisThread) { return VALUE_DRAW + Value(2 * (thisThread->nodes & 1) - 1); } @@ -822,12 +821,6 @@ namespace { thisThread->mainHistory[~us][from_to((ss-1)->currentMove)] << bonus; } - // Step 7. Razoring (~1 Elo) - if ( !rootNode // The required rootNode PV handling is not available in qsearch - && depth == 1 - && eval <= alpha - RazorMargin) - return qsearch(pos, ss, alpha, beta); - // Set up improving flag that is used in various pruning heuristics // We define position as improving if static evaluation of position is better // Than the previous static evaluation at our turn @@ -836,20 +829,20 @@ namespace { ? ss->staticEval > (ss-4)->staticEval || (ss-4)->staticEval == VALUE_NONE : ss->staticEval > (ss-2)->staticEval; - // Step 8. Futility pruning: child node (~50 Elo) + // Step 7. Futility pruning: child node (~50 Elo) if ( !PvNode && depth < 9 && eval - futility_margin(depth, improving) >= beta && eval < VALUE_KNOWN_WIN) // Do not return unproven wins return eval; - // Step 9. Null move search with verification search (~40 Elo) + // Step 8. Null move search with verification search (~40 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 22977 + && (ss-1)->statScore < 22661 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 30 * depth - 28 * improving + 84 * ss->ttPv + 168 + && ss->staticEval >= beta - 24 * depth - 34 * improving + 162 * ss->ttPv + 159 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -857,7 +850,7 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = (1015 + 85 * depth) / 256 + std::min(int(eval - beta) / 191, 3); + Depth R = (1062 + 68 * depth) / 256 + std::min(int(eval - beta) / 190, 3); ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0]; @@ -893,9 +886,9 @@ namespace { } } - probCutBeta = beta + 194 - 49 * improving; + probCutBeta = beta + 209 - 44 * improving; - // Step 10. ProbCut (~10 Elo) + // Step 9. ProbCut (~10 Elo) // If we have a good enough capture and a reduced search returns a value // much above beta, we can (almost) safely prune the previous move. if ( !PvNode @@ -968,7 +961,7 @@ namespace { ss->ttPv = ttPv; } - // Step 11. If the position is not in TT, decrease depth by 2 + // Step 10. If the position is not in TT, decrease depth by 2 if ( PvNode && depth >= 6 && !ttMove) @@ -997,7 +990,7 @@ moves_loop: // When in check, search starts from here // Mark this node as being searched ThreadHolding th(thisThread, posKey, ss->ply); - // Step 12. Loop through all pseudo-legal moves until no moves remain + // Step 11. Loop through all pseudo-legal moves until no moves remain // or a beta cutoff occurs. while ((move = mp.next_move(moveCountPruning)) != MOVE_NONE) { @@ -1032,10 +1025,18 @@ moves_loop: // When in check, search starts from here movedPiece = pos.moved_piece(move); givesCheck = pos.gives_check(move); + // Indicate PvNodes that will probably fail low if node was searched with non-PV search + // at depth equal or greater to current depth and result of this search was far below alpha + bool likelyFailLow = PvNode + && ttMove + && (tte->bound() & BOUND_UPPER) + && ttValue < alpha + 200 + 100 * depth + && tte->depth() >= depth; + // Calculate new depth for this move newDepth = depth - 1; - // Step 13. Pruning at shallow depth (~200 Elo) + // Step 12. Pruning at shallow depth (~200 Elo) if ( !rootNode && pos.non_pawn_material(us) && bestValue > VALUE_TB_LOSS_IN_MAX_PLY) @@ -1046,8 +1047,20 @@ moves_loop: // When in check, search starts from here // Reduced depth of the next LMR search int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), 0); - if ( !captureOrPromotion - && !givesCheck) + 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) + continue; + + // SEE based pruning + if (!pos.see_ge(move, Value(-218) * depth)) // (~25 Elo) + continue; + } + else { // Countermoves based pruning (~20 Elo) if ( lmrDepth < 4 + ((ss-1)->statScore > 0 || (ss-1)->moveCount == 1) @@ -1058,32 +1071,20 @@ moves_loop: // When in check, search starts from here // Futility pruning: parent node (~5 Elo) if ( lmrDepth < 7 && !ss->inCheck - && ss->staticEval + 254 + 159 * lmrDepth <= alpha + && ss->staticEval + 174 + 157 * lmrDepth <= alpha && (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] + (*contHist[3])[movedPiece][to_sq(move)] - + (*contHist[5])[movedPiece][to_sq(move)] / 2 < 26394) + + (*contHist[5])[movedPiece][to_sq(move)] / 3 < 26237) continue; // Prune moves with negative SEE (~20 Elo) if (!pos.see_ge(move, Value(-(30 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth))) continue; } - else - { - // 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) - continue; - - // SEE based pruning - if (!pos.see_ge(move, Value(-218) * depth)) // (~25 Elo) - continue; - } } - // Step 14. Extensions (~75 Elo) + // Step 13. Extensions (~75 Elo) // Singular extension search (~70 Elo). If all moves but one fail low on a // search of (alpha-s, beta-s), and just one fails high on (alpha, beta), @@ -1134,7 +1135,7 @@ moves_loop: // When in check, search starts from here // Check extension (~2 Elo) else if ( givesCheck - && (pos.is_discovery_check_on_king(~us, move) || pos.see_ge(move))) + && (pos.is_discovered_check_on_king(~us, move) || pos.see_ge(move))) extension = 1; // Last captures extension @@ -1155,10 +1156,10 @@ moves_loop: // When in check, search starts from here [movedPiece] [to_sq(move)]; - // Step 15. Make the move + // Step 14. Make the move pos.do_move(move, st, givesCheck); - // Step 16. Reduced depth search (LMR, ~200 Elo). If the move fails high it will be + // Step 15. Reduced depth search (LMR, ~200 Elo). If the move fails high it will be // re-searched at full depth. if ( depth >= 3 && moveCount > 1 + 2 * rootNode @@ -1166,7 +1167,7 @@ moves_loop: // When in check, search starts from here || moveCountPruning || ss->staticEval + PieceValue[EG][pos.captured_piece()] <= alpha || cutNode - || (!PvNode && !formerPv && thisThread->captureHistory[movedPiece][to_sq(move)][type_of(pos.captured_piece())] < 4506) + || (!PvNode && !formerPv && captureHistory[movedPiece][to_sq(move)][type_of(pos.captured_piece())] < 4506) || thisThread->ttHitAverage < 432 * TtHitAverageResolution * TtHitAverageWindow / 1024)) { Depth r = reduction(improving, depth, moveCount); @@ -1179,8 +1180,9 @@ moves_loop: // When in check, search starts from here if (th.marked()) r++; - // Decrease reduction if position is or has been on the PV (~10 Elo) - if (ss->ttPv) + // Decrease reduction if position is or has been on the PV + // and node is not likely to fail low. (~10 Elo) + if (ss->ttPv && !likelyFailLow) r -= 2; // Increase reduction at root and non-PV nodes when the best move does not change frequently @@ -1199,7 +1201,14 @@ moves_loop: // When in check, search starts from here if (singularQuietLMR) r--; - if (!captureOrPromotion) + if (captureOrPromotion) + { + // Unless giving check, this capture is likely bad + if ( !givesCheck + && ss->staticEval + PieceValue[EG][pos.captured_piece()] + 210 * depth <= alpha) + r++; + } + else { // Increase reduction if ttMove is a capture (~5 Elo) if (ttCapture) @@ -1223,24 +1232,23 @@ 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)] - - 5287; + - 5337; // Decrease/increase reduction by comparing opponent's stat score (~10 Elo) - if (ss->statScore >= -105 && (ss-1)->statScore < -103) + if (ss->statScore >= -89 && (ss-1)->statScore < -116) r--; - else if ((ss-1)->statScore >= -122 && ss->statScore < -129) + else if ((ss-1)->statScore >= -112 && ss->statScore < -100) r++; // Decrease/increase reduction for moves with a good/bad history (~30 Elo) - r -= ss->statScore / 14884; - } - else - { - // Unless giving check, this capture is likely bad - if ( !givesCheck - && ss->staticEval + PieceValue[EG][pos.captured_piece()] + 210 * depth <= alpha) - r++; + // If we are not in check use statScore, if we are in check + // use sum of main history and first continuation history with an offset + if (ss->inCheck) + r -= (thisThread->mainHistory[us][from_to(move)] + + (*contHist[0])[movedPiece][to_sq(move)] - 4341) / 16384; + else + r -= ss->statScore / 14382; } Depth d = std::clamp(newDepth - r, 1, newDepth); @@ -1258,7 +1266,7 @@ moves_loop: // When in check, search starts from here didLMR = false; } - // Step 17. Full depth search when LMR is skipped or fails high + // Step 16. Full depth search when LMR is skipped or fails high if (doFullDepthSearch) { value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); @@ -1285,12 +1293,12 @@ moves_loop: // When in check, search starts from here std::min(maxNextDepth, newDepth), false); } - // Step 18. Undo move + // Step 17. Undo move pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // Step 19. Check for a new best move + // Step 18. Check for a new best move // Finished searching the move. If a stop occurred, the return value of // the search cannot be trusted, and we return immediately without // updating best move, PV and TT. @@ -1367,7 +1375,7 @@ moves_loop: // When in check, search starts from here return VALUE_DRAW; */ - // Step 20. Check for mate and stalemate + // Step 19. Check for mate and stalemate // All legal moves have been searched and if there are no legal moves, it // must be a mate or a stalemate. If we are in a singular extension search then // return a fail low score. @@ -1548,7 +1556,7 @@ moves_loop: // When in check, search starts from here && futilityBase > -VALUE_KNOWN_WIN && !pos.advanced_pawn_push(move)) { - assert(type_of(move) != ENPASSANT); // Due to !pos.advanced_pawn_push + assert(type_of(move) != EN_PASSANT); // Due to !pos.advanced_pawn_push // moveCount pruning if (moveCount > 2) @@ -1712,8 +1720,8 @@ moves_loop: // When in check, search starts from here PieceType captured = type_of(pos.piece_on(to_sq(bestMove))); bonus1 = stat_bonus(depth + 1); - bonus2 = bestValue > beta + PawnValueMg ? bonus1 // larger bonus - : stat_bonus(depth); // smaller bonus + bonus2 = bestValue > beta + PawnValueMg ? bonus1 // larger bonus + : std::min(bonus1, stat_bonus(depth)); // smaller bonus if (!pos.capture_or_promotion(bestMove)) {