X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;ds=sidebyside;f=src%2Fsearch.cpp;h=672abc05b27296165df1286890d1f658f56187bc;hb=e31f97e3baa52042fe60d6f4eeb50fe0d9e61013;hp=c0f77f8afbcd2a35581a13a9d3daa5db17e57179;hpb=95d7369e54f20715345cf5408040f3c7d1ec8415;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index c0f77f8a..672abc05 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -63,7 +63,7 @@ namespace { // Futility margin Value futility_margin(Depth d, bool improving) { - return Value(214 * (d - improving)); + return Value(168 * (d - improving)); } // Reductions lookup table, initialized at startup @@ -71,7 +71,7 @@ namespace { Depth reduction(bool i, Depth d, int mn, Value delta, Value rootDelta) { int r = Reductions[d] * Reductions[mn]; - return (r + 1358 - int(delta) * 1024 / int(rootDelta)) / 1024 + (!i && r > 904); + return (r + 1463 - int(delta) * 1024 / int(rootDelta)) / 1024 + (!i && r > 1010); } constexpr int futility_move_count(bool improving, Depth depth) { @@ -80,7 +80,7 @@ namespace { // History and stats update bonus, based on depth int stat_bonus(Depth d) { - return std::min((6 * d + 229) * d - 215 , 2000); + return std::min((9 * d + 270) * d - 311 , 2145); } // Add a small random component to draw evaluations to avoid 3-fold blindness @@ -157,7 +157,7 @@ namespace { void Search::init() { for (int i = 1; i < MAX_MOVES; ++i) - Reductions[i] = int((21.9 + std::log(Threads.size()) / 2) * std::log(i)); + Reductions[i] = int((20.81 + std::log(Threads.size()) / 2) * std::log(i)); } @@ -303,10 +303,10 @@ void Thread::search() { multiPV = std::min(multiPV, rootMoves.size()); - complexityAverage.set(232, 1); + complexityAverage.set(202, 1); trend = SCORE_ZERO; - optimism[ us] = Value(25); + optimism[ us] = Value(39); optimism[~us] = -optimism[us]; int searchAgainCounter = 0; @@ -349,16 +349,16 @@ void Thread::search() { if (rootDepth >= 4) { Value prev = rootMoves[pvIdx].averageScore; - delta = Value(17) + int(prev) * prev / 16384; + delta = Value(16) + int(prev) * prev / 19178; alpha = std::max(prev - delta,-VALUE_INFINITE); beta = std::min(prev + delta, VALUE_INFINITE); // Adjust trend and optimism based on root move's previousScore - int tr = sigmoid(prev, 0, 0, 147, 113, 1); + int tr = sigmoid(prev, 3, 8, 90, 125, 1); trend = (us == WHITE ? make_score(tr, tr / 2) : -make_score(tr, tr / 2)); - int opt = sigmoid(prev, 0, 25, 147, 14464, 256); + int opt = sigmoid(prev, 8, 17, 144, 13966, 183); optimism[ us] = Value(opt); optimism[~us] = -optimism[us]; } @@ -413,7 +413,7 @@ void Thread::search() { else break; - delta += delta / 4 + 5; + delta += delta / 4 + 2; assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE); } @@ -459,17 +459,17 @@ void Thread::search() { && !Threads.stop && !mainThread->stopOnPonderhit) { - double fallingEval = (142 + 12 * (mainThread->bestPreviousAverageScore - bestValue) - + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 825.0; + double fallingEval = (69 + 12 * (mainThread->bestPreviousAverageScore - bestValue) + + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 781.4; fallingEval = std::clamp(fallingEval, 0.5, 1.5); // If the bestMove is stable over several iterations, reduce time accordingly - timeReduction = lastBestMoveDepth + 9 < completedDepth ? 1.92 : 0.95; - double reduction = (1.47 + mainThread->previousTimeReduction) / (2.32 * timeReduction); + timeReduction = lastBestMoveDepth + 10 < completedDepth ? 1.63 : 0.73; + double reduction = (1.56 + mainThread->previousTimeReduction) / (2.20 * timeReduction); double bestMoveInstability = 1.073 + std::max(1.0, 2.25 - 9.9 / rootDepth) * totBestMoveChanges / Threads.size(); int complexity = mainThread->complexityAverage.value(); - double complexPosition = std::clamp(1.0 + (complexity - 232) / 1750.0, 0.5, 1.5); + double complexPosition = std::clamp(1.0 + (complexity - 326) / 1618.1, 0.5, 1.5); double totalTime = Time.optimum() * fallingEval * reduction * bestMoveInstability * complexPosition; @@ -490,7 +490,7 @@ void Thread::search() { } else if ( Threads.increaseDepth && !mainThread->ponder - && Time.elapsed() > totalTime * 0.58) + && Time.elapsed() > totalTime * 0.43) Threads.increaseDepth = false; else Threads.increaseDepth = true; @@ -766,37 +766,49 @@ 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 - : 200; + : 175; improving = improvement > 0; complexity = abs(ss->staticEval - (us == WHITE ? eg_value(pos.psq_score()) : -eg_value(pos.psq_score()))); thisThread->complexityAverage.update(complexity); - // Step 7. Futility pruning: child node (~25 Elo). + // Step 7. Razoring. + // If eval is really low check with qsearch if it can exceed alpha, if it can't, + // return a fail low. + if ( !PvNode + && depth <= 7 + && eval < alpha - 348 - 258 * depth * depth) + { + value = qsearch(pos, ss, alpha - 1, alpha); + if (value < alpha) + return value; + } + + // Step 8. Futility pruning: child node (~25 Elo). // The depth condition is important for mate finding. if ( !ss->ttPv - && depth < 9 + && depth < 8 && eval - futility_margin(depth, improving) - (ss-1)->statScore / 256 >= beta && eval >= beta - && eval < 15000) // 50% larger than VALUE_KNOWN_WIN, but smaller than TB wins. + && eval < 26305) // larger than VALUE_KNOWN_WIN, but smaller than TB wins. return eval; - // Step 8. Null move search with verification search (~22 Elo) + // Step 9. Null move search with verification search (~22 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 23767 + && (ss-1)->statScore < 14695 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 20 * depth - improvement / 15 + 204 + complexity / 25 + && ss->staticEval >= beta - 15 * depth - improvement / 15 + 198 + complexity / 28 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) { assert(eval - beta >= 0); - // Null move dynamic reduction based on depth and value - Depth R = std::min(int(eval - beta) / 205, 3) + depth / 3 + 4; + // Null move dynamic reduction based on depth, eval and complexity of position + Depth R = std::min(int(eval - beta) / 147, 5) + depth / 3 + 4 - (complexity > 753); ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0]; @@ -832,9 +844,9 @@ namespace { } } - probCutBeta = beta + 209 - 44 * improving; + probCutBeta = beta + 179 - 46 * improving; - // Step 9. ProbCut (~4 Elo) + // Step 10. ProbCut (~4 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 @@ -851,7 +863,7 @@ namespace { { assert(probCutBeta < VALUE_INFINITE); - MovePicker mp(pos, ttMove, probCutBeta - ss->staticEval, &captureHistory); + MovePicker mp(pos, ttMove, probCutBeta - ss->staticEval, depth - 3, &captureHistory); bool ttPv = ss->ttPv; ss->ttPv = false; @@ -859,7 +871,6 @@ namespace { if (move != excludedMove && pos.legal(move)) { assert(pos.capture_or_promotion(move)); - assert(depth >= 5); captureOrPromotion = true; @@ -895,24 +906,24 @@ namespace { ss->ttPv = ttPv; } - // Step 10. If the position is not in TT, decrease depth by 2 or 1 depending on node type (~3 Elo) + // Step 11. If the position is not in TT, decrease depth by 2 or 1 depending on node type (~3 Elo) if ( PvNode - && depth >= 6 + && depth >= 3 && !ttMove) depth -= 2; if ( cutNode - && depth >= 9 + && depth >= 8 && !ttMove) depth--; moves_loop: // When in check, search starts here - // Step 11. A small Probcut idea, when we are in check (~0 Elo) - probCutBeta = beta + 409; + // Step 12. A small Probcut idea, when we are in check (~0 Elo) + probCutBeta = beta + 481; if ( ss->inCheck && !PvNode - && depth >= 4 + && depth >= 2 && ttCapture && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3 @@ -945,7 +956,7 @@ moves_loop: // When in check, search starts here && (tte->bound() & BOUND_UPPER) && tte->depth() >= depth; - // Step 12. Loop through all pseudo-legal moves until no moves remain + // Step 13. Loop through all pseudo-legal moves until no moves remain // or a beta cutoff occurs. while ((move = mp.next_move(moveCountPruning)) != MOVE_NONE) { @@ -985,7 +996,7 @@ moves_loop: // When in check, search starts here Value delta = beta - alpha; - // Step 13. Pruning at shallow depth (~98 Elo). Depth conditions are important for mate finding. + // Step 14. 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) @@ -1005,12 +1016,12 @@ moves_loop: // When in check, search starts here && !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) + && ss->staticEval + 281 + 179 * lmrDepth + PieceValue[EG][pos.piece_on(to_sq(move))] + + captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))] / 6 < alpha) continue; // SEE based pruning (~9 Elo) - if (!pos.see_ge(move, Value(-217) * depth)) + if (!pos.see_ge(move, Value(-203) * depth)) continue; } else @@ -1028,17 +1039,17 @@ moves_loop: // When in check, search starts here // Futility pruning: parent node (~9 Elo) if ( !ss->inCheck - && lmrDepth < 8 - && ss->staticEval + 138 + 137 * lmrDepth + history / 64 <= alpha) + && lmrDepth < 11 + && ss->staticEval + 122 + 138 * lmrDepth + history / 60 <= alpha) continue; // Prune moves with negative SEE (~3 Elo) - if (!pos.see_ge(move, Value(-21 * lmrDepth * lmrDepth - 21 * lmrDepth))) + if (!pos.see_ge(move, Value(-25 * lmrDepth * lmrDepth - 20 * lmrDepth))) continue; } } - // Step 14. Extensions (~66 Elo) + // Step 15. Extensions (~66 Elo) // We take care to not overdo to avoid search getting stuck. if (ss->ply < thisThread->rootDepth * 2) { @@ -1048,7 +1059,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 >= 6 + 2 * (PvNode && tte->is_pv()) + && depth >= 4 + 2 * (PvNode && tte->is_pv()) && move == ttMove && !excludedMove // Avoid recursive singular search /* && ttValue != VALUE_NONE Already implicit in the next condition */ @@ -1069,8 +1080,8 @@ moves_loop: // When in check, search starts here // Avoid search explosion by limiting the number of double extensions if ( !PvNode - && value < singularBeta - 75 - && ss->doubleExtensions <= 6) + && value < singularBeta - 26 + && ss->doubleExtensions <= 8) extension = 2; } @@ -1089,15 +1100,15 @@ moves_loop: // When in check, search starts here // Check extensions (~1 Elo) else if ( givesCheck - && depth > 6 - && abs(ss->staticEval) > 100) + && depth > 9 + && abs(ss->staticEval) > 71) extension = 1; // Quiet ttMove extensions (~0 Elo) else if ( PvNode && move == ttMove && move == ss->killers[0] - && (*contHist[0])[movedPiece][to_sq(move)] >= 10000) + && (*contHist[0])[movedPiece][to_sq(move)] >= 5491) extension = 1; } @@ -1115,17 +1126,17 @@ moves_loop: // When in check, search starts here [movedPiece] [to_sq(move)]; - // Step 15. Make the move + // Step 16. Make the move pos.do_move(move, st, givesCheck); bool doDeeperSearch = false; - // Step 16. Late moves reduction / extension (LMR, ~98 Elo) + // Step 17. 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". - if ( depth >= 3 - && moveCount > 1 + 2 * rootNode + if ( depth >= 2 + && moveCount > 1 + (PvNode && ss->ply <= 1) && ( !ss->ttPv || !captureOrPromotion || (cutNode && (ss-1)->moveCount > 1))) @@ -1144,7 +1155,7 @@ moves_loop: // When in check, search starts here r -= 2; // Decrease reduction if opponent's move count is high (~1 Elo) - if ((ss-1)->moveCount > 13) + if ((ss-1)->moveCount > 7) r--; // Increase reduction for cut nodes (~3 Elo) @@ -1155,22 +1166,27 @@ moves_loop: // When in check, search starts here if (ttCapture) r++; + // Decrease reduction at PvNodes if bestvalue + // is vastly different from static evaluation + if (PvNode && !ss->inCheck && abs(ss->staticEval - bestValue) > 250) + r--; + ss->statScore = thisThread->mainHistory[us][from_to(move)] + (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] + (*contHist[3])[movedPiece][to_sq(move)] - - 4923; + - 4334; // Decrease/increase reduction for moves with a good/bad history (~30 Elo) - r -= ss->statScore / 14721; + r -= ss->statScore / 15914; // In general we want to cap the LMR depth search at newDepth. But if reductions // are really negative and movecount is low, we allow this move to be searched // deeper than the first move (this may lead to hidden double extensions). int deeper = r >= -1 ? 0 - : moveCount <= 5 ? 2 - : PvNode && depth > 6 ? 1 - : cutNode && moveCount <= 7 ? 1 + : moveCount <= 4 ? 2 + : PvNode && depth > 4 ? 1 + : cutNode && moveCount <= 8 ? 1 : 0; Depth d = std::clamp(newDepth - r, 1, newDepth + deeper); @@ -1179,7 +1195,7 @@ moves_loop: // When in check, search starts here // 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)); + doDeeperSearch = value > (alpha + 78 + 11 * (newDepth - d)); didLMR = true; } else @@ -1188,7 +1204,7 @@ moves_loop: // When in check, search starts here didLMR = false; } - // Step 17. Full depth search when LMR is skipped or fails high + // Step 18. Full depth search when LMR is skipped or fails high if (doFullDepthSearch) { value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth + doDeeperSearch, !cutNode); @@ -1200,7 +1216,7 @@ moves_loop: // When in check, search starts here : -stat_bonus(newDepth); if (captureOrPromotion) - bonus /= 4; + bonus /= 6; update_continuation_histories(ss, movedPiece, to_sq(move), bonus); } @@ -1218,12 +1234,12 @@ moves_loop: // When in check, search starts here std::min(maxNextDepth, newDepth), false); } - // Step 18. Undo move + // Step 19. Undo move pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // Step 19. Check for a new best move + // Step 20. 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. @@ -1306,7 +1322,7 @@ moves_loop: // When in check, search starts here return VALUE_DRAW; */ - // Step 20. Check for mate and stalemate + // Step 21. 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. @@ -1324,14 +1340,14 @@ moves_loop: // When in check, search starts here quietsSearched, quietCount, capturesSearched, captureCount, depth); // Bonus for prior countermove that caused the fail low - else if ( (depth >= 3 || PvNode) + else if ( (depth >= 4 || PvNode) && !priorCapture) { //Assign extra bonus if current node is PvNode or cutNode //or fail low was really bad bool extraBonus = PvNode || cutNode - || bestValue < alpha - 94 * depth; + || bestValue < alpha - 70 * depth; update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * (1 + extraBonus)); } @@ -1343,10 +1359,6 @@ moves_loop: // When in check, search starts here // opponent move is probably good and the new position is added to the search tree. if (bestValue <= alpha) ss->ttPv = ss->ttPv || ((ss-1)->ttPv && depth > 3); - // Otherwise, a counter move has been found and if the position is the last leaf - // in the search tree, remove the position from the search tree. - else if (depth > 3) - ss->ttPv = ss->ttPv && (ss+1)->ttPv; // Write gathered information in transposition table if (!excludedMove && !(rootNode && thisThread->pvIdx)) @@ -1462,7 +1474,7 @@ moves_loop: // When in check, search starts here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + 155; + futilityBase = bestValue + 118; } const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory,