X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=fef1b518160abf00e7e6e4ac14a7e656d2ed4046;hp=9de8cc9c092bf9b82e4db12d52bafd378af2dcb4;hb=d558f8a673b56b32ab6da8050f41b9e02fe1758b;hpb=1b325bf86d02e02af8f693e7e1e70c8be5c7967b diff --git a/src/search.cpp b/src/search.cpp index 9de8cc9c..fef1b518 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -59,7 +59,7 @@ using namespace Search; namespace { // Different node types, used as a template parameter - enum NodeType { NonPV, PV }; + enum NodeType { NonPV, PV, Root }; constexpr uint64_t TtHitAverageWindow = 4096; constexpr uint64_t TtHitAverageResolution = 1024; @@ -102,10 +102,10 @@ namespace { Move best = MOVE_NONE; }; - template + template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); - template + template Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth = 0); Value value_to_tt(Value v, int ply); @@ -152,7 +152,7 @@ namespace { void Search::init() { for (int i = 1; i < MAX_MOVES; ++i) - Reductions[i] = int(21.3 * std::log(i + 0.25 * std::log(i))); + Reductions[i] = int(21.9 * std::log(i)); } @@ -253,7 +253,7 @@ void Thread::search() { // To allow access to (ss-7) up to (ss+2), the stack must be oversized. // The former is needed to allow update_continuation_histories(ss-1, ...), // which accesses its argument at ss-6, also near the root. - // The latter is needed for statScores and killer initialization. + // The latter is needed for statScore and killer initialization. Stack stack[MAX_PLY+10], *ss = stack+7; Move pv[MAX_PLY+1]; Value bestValue, alpha, beta, delta; @@ -268,6 +268,9 @@ void Thread::search() { for (int i = 7; i > 0; i--) (ss-i)->continuationHistory = &this->continuationHistory[0][0][NO_PIECE][0]; // Use as a sentinel + for (int i = 0; i <= MAX_PLY + 2; ++i) + (ss+i)->ply = i; + ss->pv = pv; bestValue = delta = alpha = -VALUE_INFINITE; @@ -309,19 +312,7 @@ void Thread::search() { multiPV = std::min(multiPV, rootMoves.size()); ttHitAverage = TtHitAverageWindow * TtHitAverageResolution / 2; - int ct = int(Options["Contempt"]) * PawnValueEg / 100; // From centipawns - - // In analysis mode, adjust contempt in accordance with user preference - if (Limits.infinite || Options["UCI_AnalyseMode"]) - ct = Options["Analysis Contempt"] == "Off" ? 0 - : Options["Analysis Contempt"] == "Both" ? ct - : Options["Analysis Contempt"] == "White" && us == BLACK ? -ct - : Options["Analysis Contempt"] == "Black" && us == WHITE ? -ct - : ct; - - // Evaluation score is from the white point of view - contempt = (us == WHITE ? make_score(ct, ct / 2) - : -make_score(ct, ct / 2)); + trend = SCORE_ZERO; int searchAgainCounter = 0; @@ -367,11 +358,11 @@ void Thread::search() { alpha = std::max(prev - delta,-VALUE_INFINITE); beta = std::min(prev + delta, VALUE_INFINITE); - // Adjust contempt based on root move's previousScore (dynamic contempt) - int dct = ct + (113 - ct / 2) * prev / (abs(prev) + 147); + // Adjust trend based on root move's previousScore (dynamic contempt) + int tr = 113 * prev / (abs(prev) + 147); - contempt = (us == WHITE ? make_score(dct, dct / 2) - : -make_score(dct, dct / 2)); + trend = (us == WHITE ? make_score(tr, tr / 2) + : -make_score(tr, tr / 2)); } // Start with a small aspiration window and, in the case of a fail @@ -381,7 +372,7 @@ void Thread::search() { while (true) { Depth adjustedDepth = std::max(1, rootDepth - failedHighCnt - searchAgainCounter); - bestValue = Stockfish::search(rootPos, ss, alpha, beta, adjustedDepth, false); + 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 @@ -477,8 +468,8 @@ void Thread::search() { totBestMoveChanges += th->bestMoveChanges; th->bestMoveChanges = 0; } - double bestMoveInstability = 1 + 2 * totBestMoveChanges / Threads.size(); - + double bestMoveInstability = 1.073 + std::max(1.0, 2.25 - 9.9 / rootDepth) + * totBestMoveChanges / Threads.size(); double totalTime = Time.optimum() * fallingEval * reduction * bestMoveInstability; // Cap used time in case of a single legal move for a better viewer experience in tournaments @@ -524,18 +515,18 @@ namespace { // search<>() is the main search function for both PV and non-PV nodes - template + template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) { - constexpr bool PvNode = NT == PV; - const bool rootNode = PvNode && ss->ply == 0; + constexpr bool PvNode = nodeType != NonPV; + constexpr bool rootNode = nodeType == Root; const Depth maxNextDepth = rootNode ? depth : depth + 1; // Check if we have an upcoming move which draws by repetition, or // if the opponent had an alternative move earlier to this position. - if ( pos.rule50_count() >= 3 + if ( !rootNode + && pos.rule50_count() >= 3 && alpha < VALUE_DRAW - && !rootNode && pos.has_game_cycle(ss->ply)) { alpha = value_draw(pos.this_thread()); @@ -545,7 +536,7 @@ namespace { // Dive into quiescence search when the depth reaches zero if (depth <= 0) - return qsearch(pos, ss, alpha, beta); + return qsearch(pos, ss, alpha, beta); assert(-VALUE_INFINITE <= alpha && alpha < beta && beta <= VALUE_INFINITE); assert(PvNode || (alpha == beta - 1)); @@ -561,7 +552,7 @@ namespace { Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; Value bestValue, value, ttValue, eval, maxValue, probCutBeta; - bool formerPv, givesCheck, improving, didLMR, priorCapture; + bool givesCheck, improving, didLMR, priorCapture; bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture, singularQuietLMR; Piece movedPiece; @@ -607,11 +598,11 @@ namespace { assert(0 <= ss->ply && ss->ply < MAX_PLY); - (ss+1)->ply = ss->ply + 1; - (ss+1)->ttPv = false; + (ss+1)->ttPv = false; (ss+1)->excludedMove = bestMove = MOVE_NONE; - (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; - Square prevSq = to_sq((ss-1)->currentMove); + (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; + ss->doubleExtensions = (ss-1)->doubleExtensions; + Square prevSq = to_sq((ss-1)->currentMove); // Initialize statScore to zero for the grandchildren of the current position. // So statScore is shared between all grandchildren and only the first grandchild @@ -632,7 +623,6 @@ namespace { : ss->ttHit ? tte->move() : MOVE_NONE; if (!excludedMove) ss->ttPv = PvNode || (ss->ttHit && tte->is_pv()); - formerPv = ss->ttPv && !PvNode; // Update low ply history for previous move if we are near root and position is or has been in PV if ( ss->ttPv @@ -770,6 +760,7 @@ namespace { 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); } @@ -790,7 +781,6 @@ namespace { // Step 7. Futility pruning: child node (~50 Elo) if ( !PvNode - && depth < 9 && eval - futility_margin(depth, improving) >= beta && eval < VALUE_KNOWN_WIN) // Do not return unproven wins return eval; @@ -952,6 +942,7 @@ moves_loop: // When in check, search starts from here value = bestValue; singularQuietLMR = moveCountPruning = false; + bool doubleExtension = 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. @@ -1031,8 +1022,7 @@ moves_loop: // When in check, search starts from here continue; // Futility pruning: parent node (~5 Elo) - if ( lmrDepth < 7 - && !ss->inCheck + if ( !ss->inCheck && ss->staticEval + 174 + 157 * lmrDepth <= alpha && (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] @@ -1053,17 +1043,17 @@ moves_loop: // When in check, search starts from 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. - if ( depth >= 7 + if ( !rootNode + && depth >= 7 && move == ttMove - && !rootNode && !excludedMove // Avoid recursive singular search /* && ttValue != VALUE_NONE Already implicit in the next condition */ && abs(ttValue) < VALUE_KNOWN_WIN && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3) { - Value singularBeta = ttValue - ((formerPv + 4) * depth) / 2; - Depth singularDepth = (depth - 1 + 3 * formerPv) / 2; + Value singularBeta = ttValue - 2 * depth; + Depth singularDepth = (depth - 1) / 2; ss->excludedMove = move; value = search(pos, ss, singularBeta - 1, singularBeta, singularDepth, cutNode); @@ -1073,8 +1063,15 @@ moves_loop: // When in check, search starts from here { extension = 1; singularQuietLMR = !ttCapture; - if (!PvNode && value < singularBeta - 93) + + // Avoid search explosion by limiting the number of double extensions to at most 3 + if ( !PvNode + && value < singularBeta - 93 + && ss->doubleExtensions < 3) + { extension = 2; + doubleExtension = true; + } } // Multi-cut pruning @@ -1097,9 +1094,14 @@ moves_loop: // When in check, search starts from here return beta; } } + else if ( givesCheck + && depth > 6 + && abs(ss->staticEval) > Value(100)) + extension = 1; // Add extension to new depth newDepth += extension; + ss->doubleExtensions = (ss-1)->doubleExtensions + (extension == 2); // Speculative prefetch as early as possible prefetch(TT.first_entry(pos.key_after(move))); @@ -1122,11 +1124,14 @@ moves_loop: // When in check, search starts from here && moveCount > 1 + 2 * rootNode && ( !captureOrPromotion || (cutNode && (ss-1)->moveCount > 1) - || (!PvNode && !formerPv)) + || !ss->ttPv) && (!PvNode || ss->ply > 1 || thisThread->id() % 4 != 3)) { Depth r = reduction(improving, depth, moveCount); + if (PvNode) + r--; + // Decrease reduction if the ttHit running average is large (~0 Elo) if (thisThread->ttHitAverage > 537 * TtHitAverageResolution * TtHitAverageWindow / 1024) r--; @@ -1139,7 +1144,6 @@ moves_loop: // When in check, search starts from here // Increase reduction at root and non-PV nodes when the best move does not change frequently if ( (rootNode || !PvNode) - && thisThread->rootDepth > 10 && thisThread->bestMoveChanges <= 2) r++; @@ -1152,8 +1156,8 @@ moves_loop: // When in check, search starts from here r--; // Increase reduction for cut nodes (~3 Elo) - if (cutNode) - r += 1 + !captureOrPromotion; + if (cutNode && move != ss->killers[0]) + r += 2; if (!captureOrPromotion) { @@ -1174,8 +1178,8 @@ moves_loop: // When in check, search starts from here // 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. - Depth d = std::clamp(newDepth - r, 1, newDepth + (r < -1 && moveCount <= 5)); + // 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)); value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); @@ -1273,7 +1277,6 @@ moves_loop: // When in check, search starts from here else { assert(value >= beta); // Fail high - ss->statScore = 0; break; } } @@ -1347,10 +1350,11 @@ moves_loop: // When in check, search starts from here // qsearch() is the quiescence search function, which is called by the main search // function with zero depth, or recursively with further decreasing depth per call. - template + template Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { - constexpr bool PvNode = NT == PV; + static_assert(nodeType != Root); + constexpr bool PvNode = nodeType == PV; assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE); assert(PvNode || (alpha == beta - 1)); @@ -1376,7 +1380,6 @@ moves_loop: // When in check, search starts from here } Thread* thisThread = pos.this_thread(); - (ss+1)->ply = ss->ply + 1; bestMove = MOVE_NONE; ss->inCheck = pos.checkers(); moveCount = 0; @@ -1457,7 +1460,7 @@ moves_loop: // When in check, search starts from here // Initialize a MovePicker object for the current position, and prepare // to search the moves. Because the depth is <= 0 here, only captures, - // queen and checking knight promotions, and other checks(only if depth >= DEPTH_QS_CHECKS) + // queen promotions, and other checks (only if depth >= DEPTH_QS_CHECKS) // will be generated. MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &thisThread->captureHistory, @@ -1529,7 +1532,7 @@ moves_loop: // When in check, search starts from here // Make and search the move pos.do_move(move, st, givesCheck); - value = -qsearch(pos, ss+1, -beta, -alpha, depth - 1); + value = -qsearch(pos, ss+1, -beta, -alpha, depth - 1); pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);