X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=4b6b497a5b49b504031519b5fcb8137d6a76d1b9;hb=f436bf77ad2eb42228747d9aa58eeb7403e23d49;hp=9b747e78e41fd96f86e1592b3b2bf88b50cf79c3;hpb=675f6a038ba98b6b906a4767f009cf6fe91b0c52;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index 9b747e78..4b6b497a 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(168 * (d - improving)); + return Value(165 * (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 + 1463 - int(delta) * 1024 / int(rootDelta)) / 1024 + (!i && r > 1010); + return (r + 1642 - int(delta) * 1024 / int(rootDelta)) / 1024 + (!i && r > 916); } constexpr int futility_move_count(bool improving, Depth depth) { @@ -81,7 +81,7 @@ namespace { // History and stats update bonus, based on depth int stat_bonus(Depth d) { - return std::min((8 * d + 240) * d - 276 , 1907); + return std::min((12 * d + 282) * d - 349 , 1594); } // Add a small random component to draw evaluations to avoid 3-fold blindness @@ -158,7 +158,7 @@ namespace { void Search::init() { for (int i = 1; i < MAX_MOVES; ++i) - Reductions[i] = int((20.81 + std::log(Threads.size()) / 2) * std::log(i)); + Reductions[i] = int((20.26 + std::log(Threads.size()) / 2) * std::log(i)); } @@ -307,11 +307,10 @@ void Thread::search() { multiPV = std::min(multiPV, rootMoves.size()); - complexityAverage.set(174, 1); + complexityAverage.set(155, 1); - trend = SCORE_ZERO; - optimism[ us] = Value(39); - optimism[~us] = -optimism[us]; + trend = SCORE_ZERO; + optimism[us] = optimism[~us] = VALUE_ZERO; int searchAgainCounter = 0; @@ -353,16 +352,16 @@ void Thread::search() { if (rootDepth >= 4) { Value prev = rootMoves[pvIdx].averageScore; - delta = Value(16) + int(prev) * prev / 19178; + delta = Value(10) + int(prev) * prev / 15620; 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, 3, 8, 90, 125, 1); + int tr = 116 * prev / (std::abs(prev) + 89); trend = (us == WHITE ? make_score(tr, tr / 2) : -make_score(tr, tr / 2)); - int opt = sigmoid(prev, 8, 17, 144, 13966, 183); + int opt = 118 * prev / (std::abs(prev) + 169); optimism[ us] = Value(opt); optimism[~us] = -optimism[us]; } @@ -465,16 +464,16 @@ void Thread::search() { && !Threads.stop && !mainThread->stopOnPonderhit) { - double fallingEval = (69 + 12 * (mainThread->bestPreviousAverageScore - bestValue) - + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 781.4; + double fallingEval = (71 + 12 * (mainThread->bestPreviousAverageScore - bestValue) + + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 656.7; fallingEval = std::clamp(fallingEval, 0.5, 1.5); // If the bestMove is stable over several iterations, reduce time accordingly - timeReduction = lastBestMoveDepth + 10 < completedDepth ? 1.63 : 0.73; - double reduction = (1.56 + mainThread->previousTimeReduction) / (2.20 * timeReduction); + timeReduction = lastBestMoveDepth + 9 < completedDepth ? 1.37 : 0.65; + double reduction = (1.4 + mainThread->previousTimeReduction) / (2.15 * timeReduction); double bestMoveInstability = 1 + 1.7 * totBestMoveChanges / Threads.size(); int complexity = mainThread->complexityAverage.value(); - double complexPosition = std::min(1.0 + (complexity - 277) / 1819.1, 1.5); + double complexPosition = std::min(1.0 + (complexity - 261) / 1738.7, 1.5); double totalTime = Time.optimum() * fallingEval * reduction * bestMoveInstability * complexPosition; @@ -495,7 +494,7 @@ void Thread::search() { } else if ( Threads.increaseDepth && !mainThread->ponder - && Time.elapsed() > totalTime * 0.43) + && Time.elapsed() > totalTime * 0.53) Threads.increaseDepth = false; else Threads.increaseDepth = true; @@ -558,14 +557,13 @@ namespace { Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; Value bestValue, value, ttValue, eval, maxValue, probCutBeta; - bool givesCheck, improving, didLMR, priorCapture; - bool capture, doFullDepthSearch, moveCountPruning, ttCapture; + bool givesCheck, improving, priorCapture, singularQuietLMR; + bool capture, moveCountPruning, ttCapture; Piece movedPiece; int moveCount, captureCount, quietCount, improvement, complexity; // Step 1. Initialize node Thread* thisThread = pos.this_thread(); - thisThread->depth = depth; ss->inCheck = pos.checkers(); priorCapture = pos.captured_piece(); Color us = pos.side_to_move(); @@ -637,7 +635,7 @@ namespace { // At non-PV nodes we check for an early TT cutoff if ( !PvNode && ss->ttHit - && tte->depth() > depth - ((int)thisThread->id() & 0x1) - (tte->bound() == BOUND_EXACT) + && tte->depth() > depth - (tte->bound() == BOUND_EXACT) && ttValue != VALUE_NONE // Possible in case of TT access race && (tte->bound() & (ttValue >= beta ? BOUND_LOWER : BOUND_UPPER))) { @@ -742,10 +740,6 @@ namespace { else // Fall back to (semi)classical complexity for TT hits, the NNUE complexity is lost complexity = abs(ss->staticEval - pos.psq_eg_stm()); - // Randomize draw evaluation - if (eval == VALUE_DRAW) - eval = value_draw(thisThread); - // ttValue can be used as a better position evaluation (~4 Elo) if ( ttValue != VALUE_NONE && (tte->bound() & (ttValue > eval ? BOUND_LOWER : BOUND_UPPER))) @@ -765,7 +759,7 @@ namespace { // 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); + int bonus = std::clamp(-19 * int((ss-1)->staticEval + ss->staticEval), -1914, 1914); thisThread->mainHistory[~us][from_to((ss-1)->currentMove)] << bonus; } @@ -775,15 +769,14 @@ 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 - : 175; + : 168; improving = improvement > 0; // 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) + if ( depth <= 7 + && eval < alpha - 369 - 254 * depth * depth) { value = qsearch(pos, ss, alpha - 1, alpha); if (value < alpha) @@ -794,18 +787,18 @@ namespace { // The depth condition is important for mate finding. if ( !ss->ttPv && depth < 8 - && eval - futility_margin(depth, improving) - (ss-1)->statScore / 256 >= beta + && eval - futility_margin(depth, improving) - (ss-1)->statScore / 303 >= beta && eval >= beta - && eval < 26305) // larger than VALUE_KNOWN_WIN, but smaller than TB wins. + && eval < 28031) // larger than VALUE_KNOWN_WIN, but smaller than TB wins return eval; // Step 9. Null move search with verification search (~22 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 14695 + && (ss-1)->statScore < 17139 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 15 * depth - improvement / 15 + 201 + complexity / 24 + && ss->staticEval >= beta - 20 * depth - improvement / 13 + 233 + complexity / 25 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -813,7 +806,7 @@ namespace { assert(eval - beta >= 0); // 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 > 650); + Depth R = std::min(int(eval - beta) / 168, 7) + depth / 3 + 4 - (complexity > 861); ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0]; @@ -849,7 +842,7 @@ namespace { } } - probCutBeta = beta + 179 - 46 * improving; + probCutBeta = beta + 191 - 54 * improving; // Step 10. ProbCut (~4 Elo) // If we have a good enough capture and a reduced search returns a value @@ -911,14 +904,14 @@ namespace { return qsearch(pos, ss, alpha, beta); if ( cutNode - && depth >= 8 + && depth >= 9 && !ttMove) - depth--; + depth -= 2; moves_loop: // When in check, search starts here // Step 12. A small Probcut idea, when we are in check (~0 Elo) - probCutBeta = beta + 481; + probCutBeta = beta + 417; if ( ss->inCheck && !PvNode && depth >= 2 @@ -945,7 +938,7 @@ moves_loop: // When in check, search starts here ss->killers); value = bestValue; - moveCountPruning = false; + moveCountPruning = singularQuietLMR = 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. @@ -1012,14 +1005,14 @@ moves_loop: // When in check, search starts here if ( !pos.empty(to_sq(move)) && !givesCheck && !PvNode - && lmrDepth < 6 + && lmrDepth < 7 && !ss->inCheck - && ss->staticEval + 281 + 179 * lmrDepth + PieceValue[EG][pos.piece_on(to_sq(move))] + && ss->staticEval + 180 + 201 * 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(-203) * depth)) + if (!pos.see_ge(move, Value(-222) * depth)) continue; } else @@ -1037,12 +1030,12 @@ moves_loop: // When in check, search starts here // Futility pruning: parent node (~9 Elo) if ( !ss->inCheck - && lmrDepth < 11 - && ss->staticEval + 122 + 138 * lmrDepth + history / 60 <= alpha) + && lmrDepth < 13 + && ss->staticEval + 106 + 145 * lmrDepth + history / 52 <= alpha) continue; // Prune moves with negative SEE (~3 Elo) - if (!pos.see_ge(move, Value(-25 * lmrDepth * lmrDepth - 20 * lmrDepth))) + if (!pos.see_ge(move, Value(-24 * lmrDepth * lmrDepth - 15 * lmrDepth))) continue; } } @@ -1057,7 +1050,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 >= 4 - (thisThread->previousDepth > 27) + 2 * (PvNode && tte->is_pv()) + && depth >= 4 - (thisThread->previousDepth > 24) + 2 * (PvNode && tte->is_pv()) && move == ttMove && !excludedMove // Avoid recursive singular search /* && ttValue != VALUE_NONE Already implicit in the next condition */ @@ -1065,7 +1058,7 @@ moves_loop: // When in check, search starts here && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3) { - Value singularBeta = ttValue - 3 * depth; + Value singularBeta = ttValue - (3 + (ss->ttPv && !PvNode)) * depth; Depth singularDepth = (depth - 1) / 2; ss->excludedMove = move; @@ -1075,11 +1068,12 @@ 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 - && value < singularBeta - 26 - && ss->doubleExtensions <= 8) + && value < singularBeta - 25 + && ss->doubleExtensions <= 9) extension = 2; } @@ -1103,14 +1097,14 @@ moves_loop: // When in check, search starts here // Check extensions (~1 Elo) else if ( givesCheck && depth > 9 - && abs(ss->staticEval) > 71) + && abs(ss->staticEval) > 82) extension = 1; // Quiet ttMove extensions (~0 Elo) else if ( PvNode && move == ttMove && move == ss->killers[0] - && (*contHist[0])[movedPiece][to_sq(move)] >= 5491) + && (*contHist[0])[movedPiece][to_sq(move)] >= 5177) extension = 1; } @@ -1131,8 +1125,6 @@ moves_loop: // When in check, search starts here // Step 16. Make the move pos.do_move(move, st, givesCheck); - bool doDeeperSearch = false; - // 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 @@ -1165,9 +1157,18 @@ moves_loop: // When in check, search starts here // Decrease reduction for PvNodes based on depth if (PvNode) - r -= 1 + 15 / (3 + depth); + r -= 1 + 11 / (3 + depth); + + // Decrease reduction if ttMove has been singularly extended (~1 Elo) + if (singularQuietLMR) + r--; - // Increase reduction if next ply has a lot of fail high else reset count to 0 + // Dicrease reduction if we move a threatened piece (~1 Elo) + if ( depth > 9 + && (mp.threatenedPieces & from_sq(move))) + r--; + + // Increase reduction if next ply has a lot of fail high if ((ss+1)->cutoffCnt > 3 && !PvNode) r++; @@ -1175,10 +1176,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)] - - 4334; + - 4433; // Decrease/increase reduction for moves with a good/bad history (~30 Elo) - r -= ss->statScore / 15914; + r -= ss->statScore / 13628; // In general we want to cap the LMR depth search at newDepth, but when // reduction is negative, we allow this move a limited search extension @@ -1187,25 +1188,12 @@ moves_loop: // When in check, search starts here value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - // If the son is reduced and fails high it will be re-searched at full depth - doFullDepthSearch = value > alpha && d < newDepth; - doDeeperSearch = value > (alpha + 78 + 11 * (newDepth - d)); - didLMR = true; - } - else - { - doFullDepthSearch = !PvNode || moveCount > 1; - didLMR = false; - } - - // 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); - - // If the move passed LMR update its stats - if (didLMR) + // Do full depth search when reduced LMR search fails high + if (value > alpha && d < newDepth) { + const bool doDeeperSearch = value > (alpha + 64 + 11 * (newDepth - d)); + value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth + doDeeperSearch, !cutNode); + int bonus = value > alpha ? stat_bonus(newDepth) : -stat_bonus(newDepth); @@ -1216,6 +1204,12 @@ moves_loop: // When in check, search starts here } } + // Step 18. Full depth search when LMR is skipped + else if (!PvNode || moveCount > 1) + { + value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); + } + // For PV nodes only, do a full PV search on the first move or after a fail // high (in the latter case search only if value < beta), otherwise let the // parent node fail low with value <= alpha and try another move. @@ -1289,8 +1283,8 @@ moves_loop: // When in check, search starts here alpha = value; // Reduce other moves if we have found at least one score improvement - if ( depth > 2 - && depth < 7 + if ( depth > 1 + && depth < 6 && beta < VALUE_KNOWN_WIN && alpha > -VALUE_KNOWN_WIN) depth -= 1; @@ -1346,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 >= 4 || PvNode) + else if ( (depth >= 5 || PvNode) && !priorCapture) { //Assign extra bonus if current node is PvNode or cutNode //or fail low was really bad bool extraBonus = PvNode || cutNode - || bestValue < alpha - 70 * depth; + || bestValue < alpha - 62 * depth; update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * (1 + extraBonus)); } @@ -1480,7 +1474,7 @@ moves_loop: // When in check, search starts here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + 118; + futilityBase = bestValue + 153; } const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, @@ -1684,8 +1678,8 @@ moves_loop: // When in check, search starts here if (!pos.capture(bestMove)) { - int bonus2 = bestValue > beta + PawnValueMg ? bonus1 // larger bonus - : stat_bonus(depth); // smaller bonus + int bonus2 = bestValue > beta + 137 ? bonus1 // larger bonus + : stat_bonus(depth); // smaller bonus // Increase stats for the best move in case it was a quiet move update_quiet_stats(pos, ss, bestMove, bonus2); @@ -1871,12 +1865,9 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : ""); ss << " nodes " << nodesSearched - << " nps " << nodesSearched * 1000 / elapsed; - - if (elapsed > 1000) // Earlier makes little sense - ss << " hashfull " << TT.hashfull(); - - ss << " tbhits " << tbHits + << " nps " << nodesSearched * 1000 / elapsed + << " hashfull " << TT.hashfull() + << " tbhits " << tbHits << " time " << elapsed << " pv";