X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=697c8cfed1f3100eb25f80b7ab43cbb50c6c87fa;hb=3322349c1a3dbe2f4c42f84141745c4d94efde2e;hp=e322a1c99aa5ca094c05ec186ce54dcfe55f862b;hpb=d64d4ac426e06cdd52249b0464d22f3cdb7fcf79;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index e322a1c9..697c8cfe 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -63,16 +63,16 @@ namespace { enum NodeType { NonPV, PV, Root }; // Futility margin - Value futility_margin(Depth d, bool improving) { - return Value(154 * (d - improving)); + Value futility_margin(Depth d, bool noTtCutNode, bool improving) { + return Value((140 - 40 * noTtCutNode) * (d - improving)); } - // Reductions lookup table, initialized at startup + // Reductions lookup table initialized at startup int Reductions[MAX_MOVES]; // [depth or moveNumber] Depth reduction(bool i, Depth d, int mn, Value delta, Value rootDelta) { int r = Reductions[d] * Reductions[mn]; - return (r + 1449 - int(delta) * 937 / int(rootDelta)) / 1024 + (!i && r > 941); + return (r + 1372 - int(delta) * 1073 / int(rootDelta)) / 1024 + (!i && r > 936); } constexpr int futility_move_count(bool improving, Depth depth) { @@ -82,7 +82,7 @@ namespace { // History and stats update bonus, based on depth int stat_bonus(Depth d) { - return std::min(341 * d - 470, 1710); + return std::min(336 * d - 547, 1561); } // Add a small random component to draw evaluations to avoid 3-fold blindness @@ -92,7 +92,7 @@ namespace { // Skill structure is used to implement strength limit. If we have an uci_elo then // we convert it to a suitable fractional skill level using anchoring to CCRL Elo - // (goldfish 1.13 = 2000) and a fit through Ordo derived Elo for match (TC 60+0.6) + // (goldfish 1.13 = 2000) and a fit through Ordo derived Elo for a match (TC 60+0.6) // results spanning a wide range of k values. struct Skill { Skill(int skill_level, int uci_elo) { @@ -162,7 +162,7 @@ namespace { void Search::init() { for (int i = 1; i < MAX_MOVES; ++i) - Reductions[i] = int((19.47 + std::log(Threads.size()) / 2) * std::log(i)); + Reductions[i] = int((20.57 + std::log(Threads.size()) / 2) * std::log(i)); } @@ -304,7 +304,7 @@ void Thread::search() { Skill skill(Options["Skill Level"], Options["UCI_LimitStrength"] ? int(Options["UCI_Elo"]) : 0); // When playing with strength handicap enable MultiPV search that we will - // use behind the scenes to retrieve a set of possible moves. + // use behind-the-scenes to retrieve a set of possible moves. if (skill.enabled()) multiPV = std::max(multiPV, (size_t)4); @@ -321,7 +321,7 @@ void Thread::search() { if (mainThread) totBestMoveChanges /= 2; - // Save the last iteration's scores before first PV line is searched and + // Save the last iteration's scores before the first PV line is searched and // all the move scores except the (new) PV are set to -VALUE_INFINITE. for (RootMove& rm : rootMoves) rm.previousScore = rm.score; @@ -348,12 +348,12 @@ void Thread::search() { // Reset aspiration window starting size Value prev = rootMoves[pvIdx].averageScore; - delta = Value(10) + int(prev) * prev / 16502; + delta = Value(10) + int(prev) * prev / 15799; alpha = std::max(prev - delta,-VALUE_INFINITE); beta = std::min(prev + delta, VALUE_INFINITE); // Adjust optimism based on root move's previousScore - int opt = 120 * prev / (std::abs(prev) + 161); + int opt = 109 * prev / (std::abs(prev) + 141); optimism[ us] = Value(opt); optimism[~us] = -optimism[us]; @@ -363,16 +363,16 @@ void Thread::search() { int failedHighCnt = 0; while (true) { - // Adjust the effective depth searched, but ensuring at least one effective increment for every + // Adjust the effective depth searched, but ensure at least one effective increment for every // four searchAgain steps (see issue #2717). Depth adjustedDepth = std::max(1, rootDepth - failedHighCnt - 3 * (searchAgainCounter + 1) / 4); bestValue = Stockfish::search(rootPos, ss, alpha, beta, adjustedDepth, false); // Bring the best move to the front. It is critical that sorting // is done with a stable algorithm because all the values but the - // first and eventually the new best one are set to -VALUE_INFINITE + // first and eventually the new best one is set to -VALUE_INFINITE // and we want to keep the same order for all the moves except the - // new PV that goes to the front. Note that in case of MultiPV + // new PV that goes to the front. Note that in the case of MultiPV // search the already searched PV lines are preserved. std::stable_sort(rootMoves.begin() + pvIdx, rootMoves.begin() + pvLast); @@ -409,7 +409,7 @@ void Thread::search() { else break; - delta += delta / 4 + 2; + delta += delta / 3; assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE); } @@ -440,7 +440,7 @@ void Thread::search() { if (!mainThread) continue; - // If skill level is enabled and time is up, pick a sub-optimal best move + // If the skill level is enabled and time is up, pick a sub-optimal best move if (skill.enabled() && skill.time_to_pick(rootDepth)) skill.pick_best(multiPV); @@ -498,7 +498,7 @@ void Thread::search() { mainThread->previousTimeReduction = timeReduction; - // If skill level is enabled, swap best PV line with the sub-optimal one + // If the skill level is enabled, swap the best PV line with the sub-optimal one if (skill.enabled()) std::swap(rootMoves[0], *std::find(rootMoves.begin(), rootMoves.end(), skill.best ? skill.best : skill.pick_best(multiPV))); @@ -515,7 +515,7 @@ namespace { constexpr bool PvNode = nodeType != NonPV; constexpr bool rootNode = nodeType == Root; - // Check if we have an upcoming move which draws by repetition, or + // Check if we have an upcoming move that draws by repetition, or // if the opponent had an alternative move earlier to this position. if ( !rootNode && pos.rule50_count() >= 3 @@ -548,7 +548,7 @@ namespace { bool givesCheck, improving, priorCapture, singularQuietLMR; bool capture, moveCountPruning, ttCapture; Piece movedPiece; - int moveCount, captureCount, quietCount, improvement; + int moveCount, captureCount, quietCount; // Step 1. Initialize node Thread* thisThread = pos.this_thread(); @@ -580,8 +580,8 @@ namespace { // would be at best mate_in(ss->ply+1), but if alpha is already bigger because // a shorter mate was found upward in the tree then there is no need to search // because we will never beat the current alpha. Same logic but with reversed - // signs applies also in the opposite condition of being mated instead of giving - // mate. In this case return a fail-high score. + // signs apply also in the opposite condition of being mated instead of giving + // mate. In this case, return a fail-high score. alpha = std::max(mated_in(ss->ply), alpha); beta = std::min(mate_in(ss->ply+1), beta); if (alpha >= beta) @@ -615,10 +615,9 @@ namespace { // At non-PV nodes we check for an early TT cutoff if ( !PvNode - && ss->ttHit && !excludedMove - && tte->depth() > depth - (tte->bound() == BOUND_EXACT) - && ttValue != VALUE_NONE // Possible in case of TT access race + && tte->depth() > depth + && ttValue != VALUE_NONE // Possible in case of TT access race or if !ttHit && (tte->bound() & (ttValue >= beta ? BOUND_LOWER : BOUND_UPPER))) { // If ttMove is quiet, update move sorting heuristics on TT hit (~2 Elo) @@ -709,7 +708,6 @@ namespace { // Skip early pruning when in check ss->staticEval = eval = VALUE_NONE; improving = false; - improvement = 0; goto moves_loop; } else if (excludedMove) @@ -724,11 +722,8 @@ namespace { ss->staticEval = eval = tte->eval(); if (eval == VALUE_NONE) ss->staticEval = eval = evaluate(pos); - else - { - if (PvNode) - Eval::NNUE::hint_common_parent_position(pos); - } + else if (PvNode) + Eval::NNUE::hint_common_parent_position(pos); // ttValue can be used as a better position evaluation (~7 Elo) if ( ttValue != VALUE_NONE @@ -738,30 +733,30 @@ namespace { else { ss->staticEval = eval = evaluate(pos); - // Save static evaluation into transposition table + // Save static evaluation into the transposition table tte->save(posKey, VALUE_NONE, ss->ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); } // Use static evaluation difference to improve quiet move ordering (~4 Elo) if (is_ok((ss-1)->currentMove) && !(ss-1)->inCheck && !priorCapture) { - int bonus = std::clamp(-19 * int((ss-1)->staticEval + ss->staticEval), -1920, 1920); + int bonus = std::clamp(-18 * int((ss-1)->staticEval + ss->staticEval), -1817, 1817); thisThread->mainHistory[~us][from_to((ss-1)->currentMove)] << bonus; } - // Set up the improvement variable, which is the difference between the current - // static evaluation and the previous static evaluation at our turn (if we were - // in check at our previous move we look at the move prior to it). The improvement - // 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 - : 156; - improving = improvement > 0; + // Set up the improving flag, which is true if current static evaluation is + // bigger than the previous static evaluation at our turn (if we were in + // check at our previous move we look at static evaluation at move prior to it + // and if we were in check at move prior to it flag is set to true) and is + // false otherwise. The improving flag is used in various pruning heuristics. + improving = (ss-2)->staticEval != VALUE_NONE ? ss->staticEval > (ss-2)->staticEval + : (ss-4)->staticEval != VALUE_NONE ? ss->staticEval > (ss-4)->staticEval + : true; // Step 7. Razoring (~1 Elo). // If eval is really low check with qsearch if it can exceed alpha, if it can't, // return a fail low. - if (eval < alpha - 426 - 256 * depth * depth) + if (eval < alpha - 456 - 252 * depth * depth) { value = qsearch(pos, ss, alpha - 1, alpha); if (value < alpha) @@ -772,26 +767,27 @@ namespace { // The depth condition is important for mate finding. if ( !ss->ttPv && depth < 9 - && eval - futility_margin(depth, improving) - (ss-1)->statScore / 280 >= beta + && eval - futility_margin(depth, cutNode && !ss->ttHit, improving) - (ss-1)->statScore / 306 >= beta && eval >= beta - && eval < 25128) // larger than VALUE_KNOWN_WIN, but smaller than TB wins + && eval < 24923) // larger than VALUE_KNOWN_WIN, but smaller than TB wins return eval; // Step 9. Null move search with verification search (~35 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 18755 + && (ss-1)->statScore < 17329 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 20 * depth - improvement / 13 + 253 + && ss->staticEval >= beta - 21 * depth + 258 && !excludedMove && pos.non_pawn_material(us) - && (ss->ply >= thisThread->nmpMinPly)) + && ss->ply >= thisThread->nmpMinPly + && beta > VALUE_TB_LOSS_IN_MAX_PLY) { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and eval - Depth R = std::min(int(eval - beta) / 172, 6) + depth / 3 + 4; + Depth R = std::min(int(eval - beta) / 173, 6) + depth / 3 + 4; ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0]; @@ -805,10 +801,9 @@ namespace { if (nullValue >= beta) { // Do not return unproven mate or TB scores - if (nullValue >= VALUE_TB_WIN_IN_MAX_PLY) - nullValue = beta; + nullValue = std::min(nullValue, VALUE_TB_WIN_IN_MAX_PLY-1); - if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 14)) + if (thisThread->nmpMinPly || depth < 14) return nullValue; assert(!thisThread->nmpMinPly); // Recursive verification is not allowed @@ -826,20 +821,34 @@ namespace { } } - probCutBeta = beta + 186 - 54 * improving; + // Step 10. If the position doesn't have a ttMove, decrease depth by 2 + // (or by 4 if the TT entry for the current position was hit and the stored depth is greater than or equal to the current depth). + // Use qsearch if depth is equal or below zero (~9 Elo) + if ( PvNode + && !ttMove) + depth -= 2 + 2 * (ss->ttHit && tte->depth() >= depth); + + if (depth <= 0) + return qsearch(pos, ss, alpha, beta); + + if ( cutNode + && depth >= 8 + && !ttMove) + depth -= 2; + + probCutBeta = beta + 168 - 61 * improving; - // Step 10. ProbCut (~10 Elo) + // Step 11. ProbCut (~10 Elo) // If we have a good enough capture (or queen promotion) and a reduced search returns a value // much above beta, we can (almost) safely prune the previous move. if ( !PvNode - && depth > 4 + && depth > 3 && abs(beta) < VALUE_TB_WIN_IN_MAX_PLY - // if value from transposition table is lower than probCutBeta, don't attempt probCut + // If value from transposition table is lower than probCutBeta, don't attempt probCut // there and in further interactions with transposition table cutoff depth is set to depth - 3 // because probCut search has depth set to depth - 4 but we also do a move before it - // so effective depth is equal to depth - 3 - && !( ss->ttHit - && tte->depth() >= depth - 3 + // So effective depth is equal to depth - 3 + && !( tte->depth() >= depth - 3 && ttValue != VALUE_NONE && ttValue < probCutBeta)) { @@ -880,30 +889,15 @@ namespace { Eval::NNUE::hint_common_parent_position(pos); } - // Step 11. If the position is not in TT, decrease depth by 2 (or by 4 if the TT entry for the current position was hit and the stored depth is greater than or equal to the current depth). - // Use qsearch if depth is equal or below zero (~9 Elo) - if ( PvNode - && !ttMove) - depth -= 2 + 2 * (ss->ttHit && tte->depth() >= depth); - - if (depth <= 0) - return qsearch(pos, ss, alpha, beta); - - if ( cutNode - && depth >= 7 - && !ttMove) - depth -= 2; - moves_loop: // When in check, search starts here // Step 12. A small Probcut idea, when we are in check (~4 Elo) - probCutBeta = beta + 391; + probCutBeta = beta + 413; if ( ss->inCheck && !PvNode - && depth >= 2 && ttCapture && (tte->bound() & BOUND_LOWER) - && tte->depth() >= depth - 3 + && tte->depth() >= depth - 4 && ttValue >= probCutBeta && abs(ttValue) <= VALUE_KNOWN_WIN && abs(beta) <= VALUE_KNOWN_WIN) @@ -925,7 +919,7 @@ moves_loop: // When in check, search starts here 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. + // at a depth equal to or greater than the current depth, and the result of this search was a fail low. bool likelyFailLow = PvNode && ttMove && (tte->bound() & BOUND_UPPER) @@ -941,8 +935,8 @@ moves_loop: // When in check, search starts here continue; // At root obey the "searchmoves" option and skip moves not listed in Root - // Move List. As a consequence any illegal move is also skipped. In MultiPV - // mode we also skip PV moves which have been already searched and those + // Move List. As a consequence, any illegal move is also skipped. In MultiPV + // mode we also skip PV moves that have been already searched and those // of lower "TB rank" if we are in a TB root position. if (rootNode && !std::count(thisThread->rootMoves.begin() + thisThread->pvIdx, thisThread->rootMoves.begin() + thisThread->pvLast, move)) @@ -982,40 +976,22 @@ moves_loop: // When in check, search starts here moveCountPruning = moveCount >= futility_move_count(improving, depth); // Reduced depth of the next LMR search - int lmrDepth = std::max(newDepth - r, 0); + int lmrDepth = newDepth - r; if ( capture || givesCheck) { // Futility pruning for captures (~2 Elo) if ( !givesCheck - && lmrDepth < 6 + && lmrDepth < 7 && !ss->inCheck - && ss->staticEval + 182 + 230 * lmrDepth + PieceValue[EG][pos.piece_on(to_sq(move))] + && ss->staticEval + 197 + 248 * lmrDepth + PieceValue[pos.piece_on(to_sq(move))] + captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))] / 7 < alpha) continue; - Bitboard occupied; - // SEE based pruning (~11 Elo) - if (!pos.see_ge(move, occupied, Value(-206) * depth)) - { - if (depth < 2 - capture) - continue; - // Don't prune the move if opp. King/Queen/Rook gets a discovered attack during or after the exchanges - Bitboard leftEnemies = pos.pieces(~us, KING, QUEEN, ROOK); - Bitboard attacks = 0; - occupied |= to_sq(move); - while (leftEnemies && !attacks) - { - Square sq = pop_lsb(leftEnemies); - attacks = pos.attackers_to(sq, occupied) & pos.pieces(us) & occupied; - // Exclude Queen/Rook(s) which were already threatened before SEE (opp King can't be in check when it's our turn) - if (attacks && sq != pos.square(~us) && (pos.attackers_to(sq, pos.pieces()) & pos.pieces(us))) - attacks = 0; - } - if (!attacks) - continue; - } + // SEE based pruning for captures and checks (~11 Elo) + if (!pos.see_ge(move, Value(-205) * depth)) + continue; } else { @@ -1024,25 +1000,25 @@ moves_loop: // When in check, search starts here + (*contHist[3])[movedPiece][to_sq(move)]; // Continuation history based pruning (~2 Elo) - if ( lmrDepth < 5 - && history < -4405 * (depth - 1)) + if ( lmrDepth < 6 + && history < -3832 * depth) continue; history += 2 * thisThread->mainHistory[us][from_to(move)]; - lmrDepth += history / 7278; + lmrDepth += history / 7011; lmrDepth = std::max(lmrDepth, -2); // Futility pruning: parent node (~13 Elo) if ( !ss->inCheck - && lmrDepth < 13 - && ss->staticEval + 103 + 138 * lmrDepth <= alpha) + && lmrDepth < 12 + && ss->staticEval + 112 + 138 * lmrDepth <= alpha) continue; lmrDepth = std::max(lmrDepth, 0); // Prune moves with negative SEE (~4 Elo) - if (!pos.see_ge(move, Value(-24 * lmrDepth * lmrDepth - 16 * lmrDepth))) + if (!pos.see_ge(move, Value(-31 * lmrDepth * lmrDepth))) continue; } } @@ -1056,8 +1032,11 @@ moves_loop: // When in check, search starts here // 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. + // Depth margin and singularBeta margin are known for having non-linear scaling. + // Their values are optimized to time controls of 180+1.8 and longer + // so changing them requires tests at this type of time controls. if ( !rootNode - && depth >= 4 - (thisThread->completedDepth > 21) + 2 * (PvNode && tte->is_pv()) + && depth >= 4 - (thisThread->completedDepth > 22) + 2 * (PvNode && tte->is_pv()) && move == ttMove && !excludedMove // Avoid recursive singular search /* && ttValue != VALUE_NONE Already implicit in the next condition */ @@ -1065,7 +1044,7 @@ moves_loop: // When in check, search starts here && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3) { - Value singularBeta = ttValue - (3 + 2 * (ss->ttPv && !PvNode)) * depth / 2; + Value singularBeta = ttValue - (82 + 65 * (ss->ttPv && !PvNode)) * depth / 64; Depth singularDepth = (depth - 1) / 2; ss->excludedMove = move; @@ -1079,8 +1058,8 @@ moves_loop: // When in check, search starts here // Avoid search explosion by limiting the number of double extensions if ( !PvNode - && value < singularBeta - 25 - && ss->doubleExtensions <= 10) + && value < singularBeta - 21 + && ss->doubleExtensions <= 11) { extension = 2; depth += depth < 13; @@ -1091,7 +1070,7 @@ moves_loop: // When in check, search starts here // Our ttMove is assumed to fail high, and now we failed high also on a reduced // search without the ttMove. So we assume this expected Cut-node is not singular, // that multiple moves fail high, and we can prune the whole subtree by returning - // a soft bound. + // a softbound. else if (singularBeta >= beta) return singularBeta; @@ -1099,26 +1078,25 @@ moves_loop: // When in check, search starts here else if (ttValue >= beta) extension = -2 - !PvNode; + // If we are on a cutNode, reduce it based on depth (negative extension) (~1 Elo) + else if (cutNode) + extension = depth < 17 ? -3 : -1; + // If the eval of ttMove is less than value, we reduce it (negative extension) (~1 Elo) else if (ttValue <= value) extension = -1; - - // If the eval of ttMove is less than alpha, we reduce it (negative extension) (~1 Elo) - else if (ttValue <= alpha) - extension = -1; } // Check extensions (~1 Elo) else if ( givesCheck - && depth > 10 - && abs(ss->staticEval) > 88) + && depth > 9) extension = 1; // Quiet ttMove extensions (~1 Elo) else if ( PvNode && move == ttMove && move == ss->killers[0] - && (*contHist[0])[movedPiece][to_sq(move)] >= 5705) + && (*contHist[0])[movedPiece][to_sq(move)] >= 5168) extension = 1; } @@ -1141,12 +1119,13 @@ moves_loop: // When in check, search starts here // Decrease reduction if position is or has been on the PV // and node is not likely to fail low. (~3 Elo) + // Decrease further on cutNodes. (~1 Elo) if ( ss->ttPv && !likelyFailLow) - r -= 2; + r -= cutNode && tte->depth() >= depth + 3 ? 3 : 2; // Decrease reduction if opponent's move count is high (~1 Elo) - if ((ss-1)->moveCount > 7) + if ((ss-1)->moveCount > 8) r--; // Increase reduction for cut nodes (~3 Elo) @@ -1159,7 +1138,7 @@ moves_loop: // When in check, search starts here // Decrease reduction for PvNodes based on depth (~2 Elo) if (PvNode) - r -= 1 + 12 / (3 + depth); + r -= 1 + (depth < 6); // Decrease reduction if ttMove has been singularly extended (~1 Elo) if (singularQuietLMR) @@ -1169,18 +1148,21 @@ moves_loop: // When in check, search starts here if ((ss+1)->cutoffCnt > 3) r++; + else if (move == ttMove) + r--; + ss->statScore = 2 * thisThread->mainHistory[us][from_to(move)] + (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] + (*contHist[3])[movedPiece][to_sq(move)] - - 4082; + - 4006; // Decrease/increase reduction for moves with a good/bad history (~25 Elo) - r -= ss->statScore / (11079 + 4626 * (depth > 6 && depth < 19)); + r -= ss->statScore / (11124 + 4740 * (depth > 5 && depth < 22)); // Step 17. Late moves reduction / extension (LMR, ~117 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 + // 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 >= 2 && moveCount > 1 + (PvNode && ss->ply <= 1) @@ -1195,13 +1177,13 @@ moves_loop: // When in check, search starts here value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - // Do full depth search when reduced LMR search fails high + // Do a full-depth search when reduced LMR search fails high if (value > alpha && d < newDepth) { - // Adjust full depth search based on LMR results - if result + // Adjust full-depth search based on LMR results - if the result // was good enough search deeper, if it was bad enough search shallower - const bool doDeeperSearch = value > (alpha + 58 + 12 * (newDepth - d)); - const bool doEvenDeeperSearch = value > alpha + 588 && ss->doubleExtensions <= 5; + const bool doDeeperSearch = value > (bestValue + 64 + 11 * (newDepth - d)); + const bool doEvenDeeperSearch = value > alpha + 711 && ss->doubleExtensions <= 6; const bool doShallowerSearch = value < bestValue + newDepth; ss->doubleExtensions = ss->doubleExtensions + doEvenDeeperSearch; @@ -1219,14 +1201,14 @@ moves_loop: // When in check, search starts here } } - // Step 18. Full depth search when LMR is skipped. If expected reduction is high, reduce its depth by 1. + // Step 18. Full-depth search when LMR is skipped. If expected reduction is high, reduce its depth by 1. else if (!PvNode || moveCount > 1) { // Increase reduction for cut nodes and not ttMove (~1 Elo) if (!ttMove && cutNode) r += 2; - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth - (r > 4), !cutNode); + value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth - (r > 3), !cutNode); } // For PV nodes only, do a full PV search on the first move or after a fail @@ -1292,7 +1274,7 @@ moves_loop: // When in check, search starts here ++thisThread->bestMoveChanges; } else - // All other moves but the PV are set to the lowest value: this + // All other moves but the PV, are set to the lowest value: this // is not a problem when sorting because the sort is stable and the // move position in the list is preserved - just the PV is pushed up. rm.score = -VALUE_INFINITE; @@ -1309,28 +1291,29 @@ moves_loop: // When in check, search starts here if (PvNode && !rootNode) // Update pv even in fail-high case update_pv(ss->pv, move, (ss+1)->pv); - if (PvNode && value < beta) // Update alpha! Always alpha < beta + if (value >= beta) { - // Reduce other moves if we have found at least one score improvement (~1 Elo) - if ( depth > 1 - && beta < 12535 - && value > -12535) - depth -= 1; - - assert(depth > 0); - alpha = value; + ss->cutoffCnt += 1 + !ttMove; + assert(value >= beta); // Fail high + break; } else { - ss->cutoffCnt++; - assert(value >= beta); // Fail high - break; + // Reduce other moves if we have found at least one score improvement (~2 Elo) + if ( depth > 2 + && depth < 12 + && beta < 14362 + && value > -12393) + depth -= 2; + + assert(depth > 0); + alpha = value; // Update alpha! Always alpha < beta } } } - // If the move is worse than some previously searched move, remember it to update its stats later + // If the move is worse than some previously searched move, remember it, to update its stats later if (move != bestMove) { if (capture && captureCount < 32) @@ -1342,7 +1325,7 @@ moves_loop: // When in check, search starts here } // The following condition would detect a stop only after move loop has been - // completed. But in this case bestValue is valid because we have fully + // completed. But in this case, bestValue is valid because we have fully // searched our subtree, and we can anyhow save the result in TT. /* if (Threads.stop) @@ -1361,7 +1344,7 @@ moves_loop: // When in check, search starts here ss->inCheck ? mated_in(ss->ply) : VALUE_DRAW; - // If there is a move which produces search value greater than alpha we update stats of searched moves + // If there is a move that produces search value greater than alpha we update the stats of searched moves else if (bestMove) update_all_stats(pos, ss, bestMove, bestValue, beta, prevSq, quietsSearched, quietCount, capturesSearched, captureCount, depth); @@ -1369,8 +1352,9 @@ moves_loop: // When in check, search starts here // Bonus for prior countermove that caused the fail low else if (!priorCapture && prevSq != SQ_NONE) { - int bonus = (depth > 5) + (PvNode || cutNode) + (bestValue < alpha - 97 * depth) + ((ss-1)->moveCount > 10); + int bonus = (depth > 5) + (PvNode || cutNode) + (bestValue < alpha - 800) + ((ss-1)->moveCount > 12); update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * bonus); + thisThread->mainHistory[~us][from_to((ss-1)->currentMove)] << stat_bonus(depth) * bonus / 2; } if (PvNode) @@ -1407,6 +1391,18 @@ moves_loop: // When in check, search starts here assert(PvNode || (alpha == beta - 1)); assert(depth <= 0); + // Check if we have an upcoming move that draws by repetition, or + // if the opponent had an alternative move earlier to this position. + if ( depth < 0 + && pos.rule50_count() >= 3 + && alpha < VALUE_DRAW + && pos.has_game_cycle(ss->ply)) + { + alpha = value_draw(pos.this_thread()); + if (alpha >= beta) + return alpha; + } + Move pv[MAX_PLY+1]; StateInfo st; ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize); @@ -1453,18 +1449,14 @@ moves_loop: // When in check, search starts here // At non-PV nodes we check for an early TT cutoff if ( !PvNode - && ss->ttHit && tte->depth() >= ttDepth - && ttValue != VALUE_NONE // Only in case of TT access race + && ttValue != VALUE_NONE // Only in case of TT access race or if !ttHit && (tte->bound() & (ttValue >= beta ? BOUND_LOWER : BOUND_UPPER))) return ttValue; // Step 4. Static evaluation of the position if (ss->inCheck) - { - ss->staticEval = VALUE_NONE; bestValue = futilityBase = -VALUE_INFINITE; - } else { if (ss->ttHit) @@ -1480,9 +1472,8 @@ moves_loop: // When in check, search starts here } else // In case of null move search use previous static eval with a different sign - ss->staticEval = bestValue = - (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) - : -(ss-1)->staticEval; + ss->staticEval = bestValue = (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) + : -(ss-1)->staticEval; // Stand pat. Return immediately if static value is at least beta if (bestValue >= beta) @@ -1495,10 +1486,10 @@ moves_loop: // When in check, search starts here return bestValue; } - if (PvNode && bestValue > alpha) + if (bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + 168; + futilityBase = std::min(ss->staticEval, bestValue) + 200; } const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, @@ -1509,7 +1500,7 @@ 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 = (ss-1)->currentMove != MOVE_NULL ? to_sq((ss-1)->currentMove) : SQ_NONE; + Square prevSq = is_ok((ss-1)->currentMove) ? to_sq((ss-1)->currentMove) : SQ_NONE; MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &thisThread->captureHistory, contHist, @@ -1521,97 +1512,98 @@ moves_loop: // When in check, search starts here // or a beta cutoff occurs. while ((move = mp.next_move()) != MOVE_NONE) { - assert(is_ok(move)); + assert(is_ok(move)); - // Check for legality - if (!pos.legal(move)) - continue; + // Check for legality + if (!pos.legal(move)) + continue; - givesCheck = pos.gives_check(move); - capture = pos.capture_stage(move); - - moveCount++; - - // Step 6. Pruning. - if (bestValue > VALUE_TB_LOSS_IN_MAX_PLY) - { - // Futility pruning and moveCount pruning (~10 Elo) - if ( !givesCheck - && to_sq(move) != prevSq - && futilityBase > -VALUE_KNOWN_WIN - && type_of(move) != PROMOTION) - { - if (moveCount > 2) - continue; + givesCheck = pos.gives_check(move); + capture = pos.capture_stage(move); - futilityValue = futilityBase + PieceValue[EG][pos.piece_on(to_sq(move))]; + moveCount++; - if (futilityValue <= alpha) - { - bestValue = std::max(bestValue, futilityValue); - continue; - } + // Step 6. Pruning. + if (bestValue > VALUE_TB_LOSS_IN_MAX_PLY) + { + // Futility pruning and moveCount pruning (~10 Elo) + if ( !givesCheck + && to_sq(move) != prevSq + && futilityBase > -VALUE_KNOWN_WIN + && type_of(move) != PROMOTION) + { + if (moveCount > 2) + continue; - if (futilityBase <= alpha && !pos.see_ge(move, VALUE_ZERO + 1)) - { - bestValue = std::max(bestValue, futilityBase); - continue; - } - } + futilityValue = futilityBase + PieceValue[pos.piece_on(to_sq(move))]; - // We prune after 2nd quiet check evasion where being 'in check' is implicitly checked through the counter - // and being a 'quiet' apart from being a tt move is assumed after an increment because captures are pushed ahead. - if (quietCheckEvasions > 1) - break; + if (futilityValue <= alpha) + { + bestValue = std::max(bestValue, futilityValue); + continue; + } - // Continuation history based pruning (~3 Elo) - if ( !capture - && (*contHist[0])[pos.moved_piece(move)][to_sq(move)] < 0 - && (*contHist[1])[pos.moved_piece(move)][to_sq(move)] < 0) - continue; + if (futilityBase <= alpha && !pos.see_ge(move, VALUE_ZERO + 1)) + { + bestValue = std::max(bestValue, futilityBase); + continue; + } + } - // Do not search moves with bad enough SEE values (~5 Elo) - if (!pos.see_ge(move, Value(-110))) - continue; - } + // We prune after the second quiet check evasion move, where being 'in check' is + // implicitly checked through the counter, and being a 'quiet move' apart from + // being a tt move is assumed after an increment because captures are pushed ahead. + if (quietCheckEvasions > 1) + break; + + // Continuation history based pruning (~3 Elo) + if ( !capture + && (*contHist[0])[pos.moved_piece(move)][to_sq(move)] < 0 + && (*contHist[1])[pos.moved_piece(move)][to_sq(move)] < 0) + continue; + + // Do not search moves with bad enough SEE values (~5 Elo) + if (!pos.see_ge(move, Value(-95))) + continue; + } - // Speculative prefetch as early as possible - prefetch(TT.first_entry(pos.key_after(move))); + // Speculative prefetch as early as possible + prefetch(TT.first_entry(pos.key_after(move))); - // Update the current move - ss->currentMove = move; - ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck] - [capture] - [pos.moved_piece(move)] - [to_sq(move)]; + // Update the current move + ss->currentMove = move; + ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck] + [capture] + [pos.moved_piece(move)] + [to_sq(move)]; - quietCheckEvasions += !capture && ss->inCheck; + quietCheckEvasions += !capture && ss->inCheck; - // Step 7. Make and search the move - pos.do_move(move, st, givesCheck); - value = -qsearch(pos, ss+1, -beta, -alpha, depth - 1); - pos.undo_move(move); + // Step 7. Make and search the move + pos.do_move(move, st, givesCheck); + value = -qsearch(pos, ss+1, -beta, -alpha, depth - 1); + pos.undo_move(move); - assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); + assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // Step 8. Check for a new best move - if (value > bestValue) - { - bestValue = value; + // Step 8. Check for a new best move + if (value > bestValue) + { + bestValue = value; - if (value > alpha) - { - bestMove = move; + if (value > alpha) + { + bestMove = move; - if (PvNode) // Update pv even in fail-high case - update_pv(ss->pv, move, (ss+1)->pv); + if (PvNode) // Update pv even in fail-high case + update_pv(ss->pv, move, (ss+1)->pv); - if (PvNode && value < beta) // Update alpha here! - alpha = value; - else - break; // Fail high - } - } + if (value < beta) // Update alpha here! + alpha = value; + else + break; // Fail high + } + } } // Step 9. Check for mate @@ -1700,28 +1692,28 @@ moves_loop: // When in check, search starts here Piece moved_piece = pos.moved_piece(bestMove); PieceType captured; - int bonus1 = stat_bonus(depth + 1); + int quietMoveBonus = stat_bonus(depth + 1); if (!pos.capture_stage(bestMove)) { - int bonus2 = bestValue > beta + 153 ? bonus1 // larger bonus - : stat_bonus(depth); // smaller bonus + int bestMoveBonus = bestValue > beta + 145 ? quietMoveBonus // 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); + update_quiet_stats(pos, ss, bestMove, bestMoveBonus); // Decrease stats for all non-best quiet moves for (int i = 0; i < quietCount; ++i) { - thisThread->mainHistory[us][from_to(quietsSearched[i])] << -bonus2; - update_continuation_histories(ss, pos.moved_piece(quietsSearched[i]), to_sq(quietsSearched[i]), -bonus2); + thisThread->mainHistory[us][from_to(quietsSearched[i])] << -bestMoveBonus; + update_continuation_histories(ss, pos.moved_piece(quietsSearched[i]), to_sq(quietsSearched[i]), -bestMoveBonus); } } else { // Increase stats for the best move in case it was a capture move captured = type_of(pos.piece_on(to_sq(bestMove))); - captureHistory[moved_piece][to_sq(bestMove)][captured] << bonus1; + captureHistory[moved_piece][to_sq(bestMove)][captured] << quietMoveBonus; } // Extra penalty for a quiet early move that was not a TT move or @@ -1729,14 +1721,14 @@ moves_loop: // When in check, search starts here if ( prevSq != SQ_NONE && ((ss-1)->moveCount == 1 + (ss-1)->ttHit || ((ss-1)->currentMove == (ss-1)->killers[0])) && !pos.captured_piece()) - update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -bonus1); + update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -quietMoveBonus); // Decrease stats for all non-best capture moves for (int i = 0; i < captureCount; ++i) { moved_piece = pos.moved_piece(capturesSearched[i]); captured = type_of(pos.piece_on(to_sq(capturesSearched[i]))); - captureHistory[moved_piece][to_sq(capturesSearched[i])][captured] << -bonus1; + captureHistory[moved_piece][to_sq(capturesSearched[i])][captured] << -quietMoveBonus; } } @@ -1748,7 +1740,7 @@ moves_loop: // When in check, search starts here for (int i : {1, 2, 4, 6}) { - // Only update first 2 continuation histories if we are in check + // Only update the first 2 continuation histories if we are in check if (ss->inCheck && i > 2) break; if (is_ok((ss-i)->currentMove)) @@ -1781,7 +1773,7 @@ moves_loop: // When in check, search starts here } } - // When playing with strength handicap, choose best move among a set of RootMoves + // When playing with strength handicap, choose the best move among a set of RootMoves // using a statistical rule dependent on 'level'. Idea by Heinz van Saanen. Move Skill::pick_best(size_t multiPV) { @@ -1791,7 +1783,7 @@ moves_loop: // When in check, search starts here // RootMoves are already sorted by score in descending order Value topScore = rootMoves[0].score; - int delta = std::min(topScore - rootMoves[multiPV - 1].score, PawnValueMg); + int delta = std::min(topScore - rootMoves[multiPV - 1].score, PawnValue); int maxScore = -VALUE_INFINITE; double weakness = 120 - 2 * level; @@ -1826,7 +1818,7 @@ void MainThread::check_time() { return; // When using nodes, ensure checking rate is not lower than 0.1% of nodes - callsCnt = Limits.nodes ? std::min(1024, int(Limits.nodes / 1024)) : 1024; + callsCnt = Limits.nodes ? std::min(512, int(Limits.nodes / 1024)) : 512; static TimePoint lastInfoTime = now(); @@ -1843,7 +1835,7 @@ void MainThread::check_time() { if (ponder) return; - if ( (Limits.use_time_management() && (elapsed > Time.maximum() - 10 || stopOnPonderhit)) + if ( (Limits.use_time_management() && (elapsed > Time.maximum() || stopOnPonderhit)) || (Limits.movetime && elapsed >= Limits.movetime) || (Limits.nodes && Threads.nodes_searched() >= (uint64_t)Limits.nodes)) Threads.stop = true; @@ -1912,7 +1904,7 @@ string UCI::pv(const Position& pos, Depth depth) { /// RootMove::extract_ponder_from_tt() is called in case we have no ponder move /// before exiting the search, for instance, in case we stop the search during a /// fail high at root. We try hard to have a ponder move to return to the GUI, -/// otherwise in case of 'ponder on' we have nothing to think on. +/// otherwise in case of 'ponder on' we have nothing to think about. bool RootMove::extract_ponder_from_tt(Position& pos) {