X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=c81496d17a35aa6a00374c9ec9be9115ea720c49;hb=7678d63cf2323e51c01e60cdff4ac3d685313790;hp=28e16609203a7f8262d405ca9cabc6b3434dbf56;hpb=a6a9d828ab4cc35ca0f64207e2ff818a391d1939;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index 28e16609..c81496d1 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) { @@ -141,7 +141,7 @@ namespace { 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, int depth); + void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus); void update_all_stats(const Position& pos, Stack* ss, Move bestMove, Value bestValue, Value beta, Square prevSq, Move* quietsSearched, int quietCount, Move* capturesSearched, int captureCount, Depth depth); @@ -260,6 +260,7 @@ void MainThread::search() { bestThread = Threads.get_best_thread(); bestPreviousScore = bestThread->rootMoves[0].score; + bestPreviousAverageScore = bestThread->rootMoves[0].averageScore; // Send again PV info if we have a new best thread if (bestThread != this) @@ -316,9 +317,6 @@ void Thread::search() { mainThread->iterValue[i] = mainThread->bestPreviousScore; } - std::copy(&lowPlyHistory[2][0], &lowPlyHistory.back().back() + 1, &lowPlyHistory[0][0]); - std::fill(&lowPlyHistory[MAX_LPH - 2][0], &lowPlyHistory.back().back() + 1, 0); - size_t multiPV = size_t(Options["MultiPV"]); Skill skill(Options["Skill Level"], Options["UCI_LimitStrength"] ? int(Options["UCI_Elo"]) : 0); @@ -489,8 +487,8 @@ void Thread::search() { && !Threads.stop && !mainThread->stopOnPonderhit) { - double fallingEval = (318 + 6 * (mainThread->bestPreviousScore - bestValue) - + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 825.0; + double fallingEval = (142 + 12 * (mainThread->bestPreviousAverageScore - bestValue) + + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 825.0; fallingEval = std::clamp(fallingEval, 0.5, 1.5); // If the bestMove is stable over several iterations, reduce time accordingly @@ -552,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; @@ -589,10 +587,9 @@ namespace { Depth extension, newDepth; Value bestValue, value, ttValue, eval, maxValue, probCutBeta; bool givesCheck, improving, didLMR, priorCapture; - bool captureOrPromotion, doFullDepthSearch, moveCountPruning, - ttCapture, singularQuietLMR; + bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture; Piece movedPiece; - int moveCount, captureCount, quietCount, bestMoveCount, improvement; + int moveCount, captureCount, quietCount, bestMoveCount, improvement, complexity; // Step 1. Initialize node ss->inCheck = pos.checkers(); @@ -666,14 +663,6 @@ namespace { if (!excludedMove) ss->ttPv = PvNode || (ss->ttHit && tte->is_pv()); - // Update low ply history for previous move if we are near root and position is or has been in PV - if ( ss->ttPv - && depth > 12 - && ss->ply - 1 < MAX_LPH - && !priorCapture - && is_ok((ss-1)->currentMove)) - thisThread->lowPlyHistory[ss->ply - 1][from_to((ss-1)->currentMove)] << stat_bonus(depth - 5); - // At non-PV nodes we check for an early TT cutoff if ( !PvNode && ss->ttHit @@ -682,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), depth); + 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); @@ -771,6 +760,7 @@ namespace { ss->staticEval = eval = VALUE_NONE; improving = false; improvement = 0; + complexity = 0; goto moves_loop; } else if (ss->ttHit) @@ -784,7 +774,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; @@ -798,7 +788,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); @@ -814,8 +804,9 @@ namespace { : 200; improving = improvement > 0; + complexity = abs(ss->staticEval - (us == WHITE ? eg_value(pos.psq_score()) : -eg_value(pos.psq_score()))); - // 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 @@ -823,13 +814,13 @@ 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 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 20 * depth - improvement / 15 + 204 + && ss->staticEval >= beta - 20 * depth - improvement / 15 + 204 + complexity / 25 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -936,7 +927,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) @@ -949,9 +940,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 @@ -973,15 +962,13 @@ moves_loop: // When in check, search starts here Move countermove = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq]; MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, - &thisThread->lowPlyHistory, &captureHistory, contHist, countermove, - ss->killers, - ss->ply); + ss->killers); value = bestValue; - singularQuietLMR = moveCountPruning = false; + moveCountPruning = false; // Indicate PvNodes that will probably fail low if the node was searched // at a depth equal or greater than the current depth, and the result of this search was a fail low. @@ -1028,28 +1015,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(-217) * depth)) continue; } else @@ -1058,36 +1051,34 @@ 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) + && history < -3875 * (depth - 1)) 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) + && ss->staticEval + 138 + 137 * 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 // result is lower than ttValue minus a margin, then we will extend the ttMove. if ( !rootNode - && depth >= 7 + && depth >= 6 + 2 * (PvNode && tte->is_pv()) && move == ttMove && !excludedMove // Avoid recursive singular search /* && ttValue != VALUE_NONE Already implicit in the next condition */ @@ -1105,7 +1096,6 @@ moves_loop: // When in check, search starts here if (value < singularBeta) { extension = 1; - singularQuietLMR = !ttCapture; // Avoid search explosion by limiting the number of double extensions if ( !PvNode @@ -1127,19 +1117,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] @@ -1163,7 +1147,9 @@ moves_loop: // When in check, search starts here // Step 15. Make the move pos.do_move(move, st, givesCheck); - // Step 16. Late moves reduction / extension (LMR, ~200 Elo) + bool doDeeperSearch = false; + + // 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". @@ -1173,12 +1159,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 @@ -1187,18 +1172,10 @@ moves_loop: // When in check, search starts here && !likelyFailLow) r -= 2; - // Increase reduction at non-PV nodes - if (!PvNode) - r++; - // Decrease reduction if opponent's move count is high (~1 Elo) if ((ss-1)->moveCount > 13) r--; - // Decrease reduction if ttMove has been singularly extended (~1 Elo) - if (singularQuietLMR) - r--; - // Increase reduction for cut nodes (~3 Elo) if (cutNode && move != ss->killers[0]) r += 2; @@ -1229,12 +1206,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 + 62 + 20 * (newDepth - d)); didLMR = true; } else @@ -1246,7 +1220,7 @@ moves_loop: // When in check, search starts here // Step 17. Full depth search when LMR is skipped or fails high if (doFullDepthSearch) { - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); + value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth + doDeeperSearch, !cutNode); // If the move passed LMR update its stats if (didLMR && !captureOrPromotion) @@ -1302,7 +1276,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) @@ -1378,7 +1352,15 @@ moves_loop: // When in check, search starts here // Bonus for prior countermove that caused the fail low else if ( (depth >= 3 || PvNode) && !priorCapture) - update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * (1 + (PvNode || cutNode))); + { + //Assign extra bonus if current node is PvNode or cutNode + //or fail low was really bad + bool extraBonus = PvNode + || cutNode + || bestValue < alpha - 94 * depth; + + update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * (1 + extraBonus)); + } if (PvNode) bestValue = std::min(bestValue, maxValue); @@ -1481,7 +1463,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; @@ -1517,10 +1499,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) @@ -1536,9 +1519,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) { @@ -1561,7 +1545,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; @@ -1575,7 +1559,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 @@ -1702,7 +1686,7 @@ moves_loop: // When in check, search starts here if (!pos.capture_or_promotion(bestMove)) { // Increase stats for the best move in case it was a quiet move - update_quiet_stats(pos, ss, bestMove, bonus2, depth); + update_quiet_stats(pos, ss, bestMove, bonus2); // Decrease stats for all non-best quiet moves for (int i = 0; i < quietCount; ++i) @@ -1749,7 +1733,7 @@ moves_loop: // When in check, search starts here // update_quiet_stats() updates move sorting heuristics - void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus, int depth) { + void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus) { // Update killers if (ss->killers[0] != move) @@ -1769,10 +1753,6 @@ moves_loop: // When in check, search starts here Square prevSq = to_sq((ss-1)->currentMove); thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] = move; } - - // Update low ply history - if (depth > 11 && ss->ply < MAX_LPH) - thisThread->lowPlyHistory[ss->ply][from_to(move)] << stat_bonus(depth - 7); } // When playing with strength handicap, choose best move among a set of RootMoves