X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=28049e87dcd8dd49a4f21242c88bf8ffa1d9a1bd;hp=008a60ede4a6138c47901d8c359fbcc64aa2707c;hb=673841301b0cc6ed78c4db3e6ec2a0b9a010c8cb;hpb=09b6d28391cf582d99897360b225bcbbe38dd1c6 diff --git a/src/search.cpp b/src/search.cpp index 008a60ed..28049e87 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -61,9 +61,6 @@ namespace { // Different node types, used as a template parameter enum NodeType { NonPV, PV, Root }; - constexpr uint64_t TtHitAverageWindow = 4096; - constexpr uint64_t TtHitAverageResolution = 1024; - // Futility margin Value futility_margin(Depth d, bool improving) { return Value(214 * (d - improving)); @@ -72,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) { + Depth reduction(bool i, Depth d, int mn, bool rangeReduction) { int r = Reductions[d] * Reductions[mn]; - return (r + 534) / 1024 + (!i && r > 904); + return (r + 534) / 1024 + (!i && r > 904) + rangeReduction; } constexpr int futility_move_count(bool improving, Depth depth) { @@ -83,7 +80,7 @@ namespace { // History and stats update bonus, based on depth int stat_bonus(Depth d) { - return d > 14 ? 73 : 6 * d * d + 229 * d - 215; + return std::min((6 * d + 229) * d - 215 , 2000); } // Add a small random component to draw evaluations to avoid 3-fold blindness @@ -91,6 +88,30 @@ namespace { return VALUE_DRAW + Value(2 * (thisThread->nodes & 1) - 1); } + // Check if the current thread is in a search explosion + ExplosionState search_explosion(Thread* thisThread) { + + uint64_t nodesNow = thisThread->nodes; + bool explosive = thisThread->doubleExtensionAverage[WHITE].is_greater(2, 100) + || thisThread->doubleExtensionAverage[BLACK].is_greater(2, 100); + + if (explosive) + thisThread->nodesLastExplosive = nodesNow; + else + thisThread->nodesLastNormal = nodesNow; + + if ( explosive + && thisThread->state == EXPLOSION_NONE + && nodesNow - thisThread->nodesLastNormal > 6000000) + thisThread->state = MUST_CALM_DOWN; + + if ( thisThread->state == MUST_CALM_DOWN + && nodesNow - thisThread->nodesLastExplosive > 6000000) + thisThread->state = EXPLOSION_NONE; + + return thisThread->state; + } + // Skill structure is used to implement strength limit struct Skill { explicit Skill(int l) : level(l) {} @@ -152,7 +173,7 @@ namespace { void Search::init() { for (int i = 1; i < MAX_MOVES; ++i) - Reductions[i] = int(21.9 * std::log(i)); + Reductions[i] = int((21.9 + std::log(Threads.size()) / 2) * std::log(i)); } @@ -310,8 +331,14 @@ void Thread::search() { multiPV = std::max(multiPV, (size_t)4); multiPV = std::min(multiPV, rootMoves.size()); - ttHitAverage = TtHitAverageWindow * TtHitAverageResolution / 2; + ttHitAverage.set(50, 100); // initialize the running average at 50% + doubleExtensionAverage[WHITE].set(0, 100); // initialize the running average at 0% + doubleExtensionAverage[BLACK].set(0, 100); // initialize the running average at 0% + + nodesLastExplosive = nodes; + nodesLastNormal = nodes; + state = EXPLOSION_NONE; trend = SCORE_ZERO; int searchAgainCounter = 0; @@ -518,6 +545,14 @@ namespace { template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) { + Thread* thisThread = pos.this_thread(); + + // Step 0. Limit search explosion + if ( ss->ply > 10 + && search_explosion(thisThread) == MUST_CALM_DOWN + && depth > (ss-1)->depth) + depth = (ss-1)->depth; + constexpr bool PvNode = nodeType != NonPV; constexpr bool rootNode = nodeType == Root; const Depth maxNextDepth = rootNode ? depth : depth + 1; @@ -554,16 +589,15 @@ namespace { Value bestValue, value, ttValue, eval, maxValue, probCutBeta; bool givesCheck, improving, didLMR, priorCapture; bool captureOrPromotion, doFullDepthSearch, moveCountPruning, - ttCapture, singularQuietLMR; + ttCapture, singularQuietLMR, noLMRExtension; Piece movedPiece; - int moveCount, captureCount, quietCount; + int moveCount, captureCount, quietCount, bestMoveCount; // Step 1. Initialize node - Thread* thisThread = pos.this_thread(); ss->inCheck = pos.checkers(); priorCapture = pos.captured_piece(); Color us = pos.side_to_move(); - moveCount = captureCount = quietCount = ss->moveCount = 0; + moveCount = bestMoveCount = captureCount = quietCount = ss->moveCount = 0; bestValue = -VALUE_INFINITE; maxValue = VALUE_INFINITE; @@ -602,8 +636,12 @@ namespace { (ss+1)->excludedMove = bestMove = MOVE_NONE; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; ss->doubleExtensions = (ss-1)->doubleExtensions; + ss->depth = depth; Square prevSq = to_sq((ss-1)->currentMove); + // Update the running average statistics for double extensions + thisThread->doubleExtensionAverage[us].update(ss->depth > (ss-1)->depth); + // Initialize statScore to zero for the grandchildren of the current position. // So statScore is shared between all grandchildren and only the first grandchild // starts with statScore = 0. Later grandchildren start with the last calculated @@ -632,9 +670,8 @@ namespace { && is_ok((ss-1)->currentMove)) thisThread->lowPlyHistory[ss->ply - 1][from_to((ss-1)->currentMove)] << stat_bonus(depth - 5); - // thisThread->ttHitAverage can be used to approximate the running average of ttHit - thisThread->ttHitAverage = (TtHitAverageWindow - 1) * thisThread->ttHitAverage / TtHitAverageWindow - + TtHitAverageResolution * ss->ttHit; + // running average of ttHit + thisThread->ttHitAverage.update(ss->ttHit); // At non-PV nodes we check for an early TT cutoff if ( !PvNode @@ -753,13 +790,13 @@ namespace { else { // In case of null move search use previous static eval with a different sign - // and addition of two tempos if ((ss-1)->currentMove != MOVE_NULL) ss->staticEval = eval = evaluate(pos); else ss->staticEval = eval = -(ss-1)->staticEval; // Save static evaluation into transposition table + if(!excludedMove) tte->save(posKey, VALUE_NONE, ss->ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); } @@ -778,8 +815,10 @@ namespace { ? ss->staticEval > (ss-4)->staticEval || (ss-4)->staticEval == VALUE_NONE : ss->staticEval > (ss-2)->staticEval; - // Step 7. Futility pruning: child node (~50 Elo) + // Step 7. Futility pruning: child node (~50 Elo). + // The depth condition is important for mate finding. if ( !PvNode + && depth < 9 && eval - futility_margin(depth, improving) >= beta && eval < VALUE_KNOWN_WIN) // Do not return unproven wins return eval; @@ -790,7 +829,7 @@ namespace { && (ss-1)->statScore < 23767 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 20 * depth - 22 * improving + 168 * ss->ttPv + 159 + && ss->staticEval >= beta - 20 * depth - 22 * improving + 168 * ss->ttPv + 177 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -798,7 +837,7 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = (1090 + 81 * depth) / 256 + std::min(int(eval - beta) / 205, 3); + Depth R = std::min(int(eval - beta) / 205, 3) + depth / 3 + 4; ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0]; @@ -900,15 +939,21 @@ namespace { ss->ttPv = ttPv; } - // Step 10. If the position is not in TT, decrease depth by 2 + // Step 10. If the position is not in TT, decrease depth by 2 or 1 depending on node type if ( PvNode && depth >= 6 && !ttMove) depth -= 2; -moves_loop: // When in check, search starts from here + if ( cutNode + && depth >= 9 + && !ttMove) + depth--; + +moves_loop: // When in check, search starts here ttCapture = ttMove && pos.capture_or_promotion(ttMove); + int rangeReduction = 0; // Step 11. A small Probcut idea, when we are in check probCutBeta = beta + 409; @@ -940,8 +985,7 @@ moves_loop: // When in check, search starts from here ss->ply); value = bestValue; - singularQuietLMR = moveCountPruning = false; - bool doubleExtension = false; + singularQuietLMR = moveCountPruning = noLMRExtension = 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. @@ -988,7 +1032,7 @@ moves_loop: // When in check, search starts from here // Calculate new depth for this move newDepth = depth - 1; - // Step 13. Pruning at shallow depth (~200 Elo) + // Step 13. Pruning at shallow depth (~200 Elo). Depth conditions are important for mate finding. if ( !rootNode && pos.non_pawn_material(us) && bestValue > VALUE_TB_LOSS_IN_MAX_PLY) @@ -997,7 +1041,7 @@ moves_loop: // When in check, search starts from here moveCountPruning = moveCount >= futility_move_count(improving, depth); // Reduced depth of the next LMR search - int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), 0); + int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount, rangeReduction > 2), 0); if ( captureOrPromotion || givesCheck) @@ -1015,23 +1059,20 @@ moves_loop: // When in check, search starts from here else { // Continuation history based pruning (~20 Elo) - if ( lmrDepth < 5 - && (*contHist[0])[movedPiece][to_sq(move)] < CounterMovePruneThreshold - && (*contHist[1])[movedPiece][to_sq(move)] < CounterMovePruneThreshold) + if (lmrDepth < 5 + && (*contHist[0])[movedPiece][to_sq(move)] + + (*contHist[1])[movedPiece][to_sq(move)] + + (*contHist[3])[movedPiece][to_sq(move)] < -3000 * depth + 3000) continue; // Futility pruning: parent node (~5 Elo) - if ( lmrDepth < 7 - && !ss->inCheck - && 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)] / 3 < 28255) + if ( !ss->inCheck + && lmrDepth < 8 + && ss->staticEval + 172 + 145 * lmrDepth <= alpha) continue; // Prune moves with negative SEE (~20 Elo) - if (!pos.see_ge(move, Value(-(30 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth))) + if (!pos.see_ge(move, Value(-21 * lmrDepth * lmrDepth - 21 * lmrDepth))) continue; } } @@ -1052,7 +1093,7 @@ moves_loop: // When in check, search starts from here && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3) { - Value singularBeta = ttValue - 2 * depth; + Value singularBeta = ttValue - 3 * depth; Depth singularDepth = (depth - 1) / 2; ss->excludedMove = move; @@ -1064,13 +1105,13 @@ moves_loop: // When in check, search starts from here extension = 1; singularQuietLMR = !ttCapture; - // Avoid search explosion by limiting the number of double extensions to at most 3 + // Avoid search explosion by limiting the number of double extensions if ( !PvNode - && value < singularBeta - 93 - && ss->doubleExtensions < 3) + && value < singularBeta - 75 + && ss->doubleExtensions <= 6) { extension = 2; - doubleExtension = true; + noLMRExtension = true; } } @@ -1082,21 +1123,28 @@ moves_loop: // When in check, search starts from here else if (singularBeta >= beta) return singularBeta; - // If the eval of ttMove is greater than beta we try also if there is another - // move that pushes it over beta, if so also produce a cutoff. + // If the eval of ttMove is greater than beta, we reduce it (negative extension) else if (ttValue >= beta) - { - ss->excludedMove = move; - value = search(pos, ss, beta - 1, beta, (depth + 3) / 2, cutNode); - ss->excludedMove = MOVE_NONE; - - if (value >= beta) - return beta; - } + extension = -2; } + + // Capture extensions for PvNodes and cutNodes + else if ( (PvNode || cutNode) + && captureOrPromotion + && moveCount != 1) + extension = 1; + + // Check extensions else if ( givesCheck && depth > 6 - && abs(ss->staticEval) > Value(100)) + && abs(ss->staticEval) > 100) + extension = 1; + + // Quiet ttMove extensions + else if ( PvNode + && move == ttMove + && move == ss->killers[0] + && (*contHist[0])[movedPiece][to_sq(move)] >= 10000) extension = 1; // Add extension to new depth @@ -1127,13 +1175,15 @@ moves_loop: // When in check, search starts from here || !ss->ttPv) && (!PvNode || ss->ply > 1 || thisThread->id() % 4 != 3)) { - Depth r = reduction(improving, depth, moveCount); + Depth r = reduction(improving, depth, moveCount, rangeReduction > 2); - if (PvNode) + // Decrease reduction if on the PV (~2 Elo) + if ( PvNode + && bestMoveCount <= 3) r--; // Decrease reduction if the ttHit running average is large (~0 Elo) - if (thisThread->ttHitAverage > 537 * TtHitAverageResolution * TtHitAverageWindow / 1024) + if (thisThread->ttHitAverage.is_greater(537, 1024)) r--; // Decrease reduction if position is or has been on the PV @@ -1159,30 +1209,37 @@ moves_loop: // When in check, search starts from here if (cutNode && move != ss->killers[0]) r += 2; - if (!captureOrPromotion) - { - // Increase reduction if ttMove is a capture (~3 Elo) - if (ttCapture) - 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; - - // Decrease/increase reduction for moves with a good/bad history (~30 Elo) - if (!ss->inCheck) - r -= ss->statScore / 14721; - } + // Increase reduction if ttMove is a capture (~3 Elo) + if (ttCapture) + r++; - // 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, unless ttMove was extended by 2. - Depth d = std::clamp(newDepth - r, 1, newDepth + (r < -1 && moveCount <= 5 && !doubleExtension)); + 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; + + // Decrease/increase reduction for moves with a good/bad history (~30 Elo) + r -= ss->statScore / 14721; + + // 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 if + // newDepth got its own extension before). + int deeper = r >= -1 ? 0 + : noLMRExtension ? 0 + : moveCount <= 5 ? 1 + : (depth > 6 && PvNode) ? 1 + : 0; + + Depth d = std::clamp(newDepth - r, 1, newDepth + deeper); 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; didLMR = true; @@ -1249,9 +1306,11 @@ moves_loop: // When in check, search starts from here for (Move* m = (ss+1)->pv; *m != MOVE_NONE; ++m) 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 - if (moveCount > 1) + // 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, + // we must take care to only do this for the first PV line. + if ( moveCount > 1 + && !thisThread->pvIdx) ++thisThread->bestMoveChanges; } else @@ -1273,7 +1332,10 @@ moves_loop: // When in check, search starts from here update_pv(ss->pv, move, (ss+1)->pv); if (PvNode && value < beta) // Update alpha! Always alpha < beta + { alpha = value; + bestMoveCount++; + } else { assert(value >= beta); // Fail high @@ -1321,7 +1383,7 @@ moves_loop: // When in check, search starts from 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)); + update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * (1 + (PvNode || cutNode))); if (PvNode) bestValue = std::min(bestValue, maxValue); @@ -1432,7 +1494,6 @@ moves_loop: // When in check, search starts from here } else // In case of null move search use previous static eval with a different sign - // and addition of two tempos ss->staticEval = bestValue = (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) : -(ss-1)->staticEval; @@ -1472,6 +1533,10 @@ moves_loop: // When in check, search starts from here { assert(is_ok(move)); + // Check for legality + if (!pos.legal(move)) + continue; + givesCheck = pos.gives_check(move); captureOrPromotion = pos.capture_or_promotion(move); @@ -1510,13 +1575,6 @@ moves_loop: // When in check, search starts from here // Speculative prefetch as early as possible prefetch(TT.first_entry(pos.key_after(move))); - // Check for legality just before making the move - if (!pos.legal(move)) - { - moveCount--; - continue; - } - ss->currentMove = move; ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck] [captureOrPromotion] @@ -1645,8 +1703,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 - : std::min(bonus1, stat_bonus(depth)); // smaller bonus + bonus2 = bestValue > beta + PawnValueMg ? bonus1 // larger bonus + : stat_bonus(depth); // smaller bonus if (!pos.capture_or_promotion(bestMove)) {