X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=a3ce4c2d3a49c2a257dc9a74a35e5e3f3a2aa7bf;hp=3319ee94798ea234dee492d3ebd338e033df127f;hb=190f38a7c2a64f7e89f06871533d87ba7b287fdc;hpb=d1f76ebcd8cc475d08b468efe4b467e014efef14 diff --git a/src/search.cpp b/src/search.cpp index 3319ee94..a3ce4c2d 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -68,11 +68,11 @@ namespace { } // Reductions lookup table, initialized at startup - int Reductions[64]; // [depth or moveNumber] + int Reductions[MAX_MOVES]; // [depth or moveNumber] - template Depth reduction(bool i, Depth d, int mn) { - int r = Reductions[std::min(d / ONE_PLY, 63)] * Reductions[std::min(mn, 63)] / 1024; - return ((r + 512) / 1024 + (!i && r > 1024) - PvNode) * ONE_PLY; + Depth reduction(bool i, Depth d, int mn) { + int r = Reductions[d / ONE_PLY] * Reductions[mn]; + return ((r + 512) / 1024 + (!i && r > 1024)) * ONE_PLY; } constexpr int futility_move_count(bool improving, int depth) { @@ -85,11 +85,10 @@ namespace { return d > 17 ? 0 : 29 * d * d + 138 * d - 134; } - // Add a small random component to draw evaluations to keep search dynamic - // and to avoid 3fold-blindness. + // Add a small random component to draw evaluations to avoid 3fold-blindness Value value_draw(Depth depth, Thread* thisThread) { - return depth < 4 ? VALUE_DRAW - : VALUE_DRAW + Value(2 * (thisThread->nodes.load(std::memory_order_relaxed) % 2) - 1); + return depth < 4 * ONE_PLY ? VALUE_DRAW + : VALUE_DRAW + Value(2 * (thisThread->nodes & 1) - 1); } // Skill structure is used to implement strength limit @@ -149,8 +148,8 @@ namespace { void Search::init() { - for (int i = 1; i < 64; ++i) - Reductions[i] = int(1024 * std::log(i) / std::sqrt(1.95)); + for (int i = 1; i < MAX_MOVES; ++i) + Reductions[i] = int(22.9 * std::log(i)); } @@ -163,12 +162,12 @@ void Search::clear() { Time.availableNodes = 0; TT.clear(); Threads.clear(); - Tablebases::init(Options["SyzygyPath"]); // Free up mapped files + Tablebases::init(Options["SyzygyPath"]); // Free mapped files } -/// MainThread::search() is called by the main thread when the program receives -/// the UCI 'go' command. It searches from the root position and outputs the "bestmove". +/// MainThread::search() is started when the program receives the UCI 'go' +/// command. It searches from the root position and outputs the "bestmove". void MainThread::search() { @@ -193,8 +192,11 @@ void MainThread::search() { else { for (Thread* th : Threads) + { + th->bestMoveChanges = 0; if (th != this) th->start_searching(); + } Thread::search(); // Let's start searching! } @@ -222,8 +224,9 @@ void MainThread::search() { if (Limits.npmsec) Time.availableNodes += Limits.inc[us] - Threads.nodes_searched(); - // Check if there are threads with a better score than main thread Thread* bestThread = this; + + // Check if there are threads with a better score than main thread if ( Options["MultiPV"] == 1 && !Limits.depth && !Skill(Options["Skill Level"]).enabled() @@ -236,21 +239,19 @@ void MainThread::search() { for (Thread* th: Threads) minScore = std::min(minScore, th->rootMoves[0].score); - // Vote according to score and depth + // Vote according to score and depth, and select the best thread + int64_t bestVote = 0; for (Thread* th : Threads) { - int64_t s = th->rootMoves[0].score - minScore + 1; - votes[th->rootMoves[0].pv[0]] += 200 + s * s * int(th->completedDepth); - } + votes[th->rootMoves[0].pv[0]] += + (th->rootMoves[0].score - minScore + 14) * int(th->completedDepth); - // Select best thread - auto bestVote = votes[this->rootMoves[0].pv[0]]; - for (Thread* th : Threads) if (votes[th->rootMoves[0].pv[0]] > bestVote) { bestVote = votes[th->rootMoves[0].pv[0]]; bestThread = th; } + } } previousScore = bestThread->rootMoves[0].score; @@ -274,9 +275,9 @@ void MainThread::search() { void Thread::search() { - // To allow access to (ss-5) up to (ss+2), the stack must be oversized. + // 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-4, also near the root. + // which accesses its argument at ss-6, also near the root. // The latter is needed for statScores and killer initialization. Stack stack[MAX_PLY+10], *ss = stack+7; Move pv[MAX_PLY+1]; @@ -284,7 +285,7 @@ void Thread::search() { Move lastBestMove = MOVE_NONE; Depth lastBestMoveDepth = DEPTH_ZERO; MainThread* mainThread = (this == Threads.main() ? Threads.main() : nullptr); - double timeReduction = 1.0; + double timeReduction = 1, totBestMoveChanges = 0; Color us = rootPos.side_to_move(); std::memset(ss-7, 0, 10 * sizeof(Stack)); @@ -295,9 +296,6 @@ void Thread::search() { bestValue = delta = alpha = -VALUE_INFINITE; beta = VALUE_INFINITE; - if (mainThread) - mainThread->bestMoveChanges = 0; - size_t multiPV = Options["MultiPV"]; Skill skill(Options["Skill Level"]); @@ -318,7 +316,7 @@ void Thread::search() { : Options["Analysis Contempt"] == "Black" && us == WHITE ? -ct : ct; - // In evaluate.cpp the evaluation is from the white point of view + // Evaluation score is from the white point of view contempt = (us == WHITE ? make_score(ct, ct / 2) : -make_score(ct, ct / 2)); @@ -329,7 +327,7 @@ void Thread::search() { { // Age out PV variability metric if (mainThread) - mainThread->bestMoveChanges *= 0.517; + totBestMoveChanges /= 2; // Save the last iteration's scores before first PV line is searched and // all the move scores except the (new) PV are set to -VALUE_INFINITE. @@ -406,17 +404,14 @@ void Thread::search() { beta = (alpha + beta) / 2; alpha = std::max(bestValue - delta, -VALUE_INFINITE); + failedHighCnt = 0; if (mainThread) - { - failedHighCnt = 0; mainThread->stopOnPonderhit = false; - } } else if (bestValue >= beta) { beta = std::min(bestValue + delta, VALUE_INFINITE); - if (mainThread) - ++failedHighCnt; + ++failedHighCnt; } else break; @@ -460,15 +455,20 @@ void Thread::search() { && !Threads.stop && !mainThread->stopOnPonderhit) { - double fallingEval = (306 + 9 * (mainThread->previousScore - bestValue)) / 581.0; - fallingEval = std::max(0.5, std::min(1.5, fallingEval)); + double fallingEval = (314 + 9 * (mainThread->previousScore - bestValue)) / 581.0; + fallingEval = clamp(fallingEval, 0.5, 1.5); // If the bestMove is stable over several iterations, reduce time accordingly timeReduction = lastBestMoveDepth + 10 * ONE_PLY < completedDepth ? 1.95 : 1.0; double reduction = std::pow(mainThread->previousTimeReduction, 0.528) / timeReduction; // Use part of the gained time from a previous stable move for the current move - double bestMoveInstability = 1.0 + mainThread->bestMoveChanges; + for (Thread* th : Threads) + { + totBestMoveChanges += th->bestMoveChanges; + th->bestMoveChanges = 0; + } + double bestMoveInstability = 1 + totBestMoveChanges / Threads.size(); // Stop the search if we have only one legal move, or if available time elapsed if ( rootMoves.size() == 1 @@ -534,7 +534,7 @@ namespace { Key posKey; Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; - Value bestValue, value, ttValue, eval, maxValue, pureStaticEval; + Value bestValue, value, ttValue, eval, maxValue; bool ttHit, ttPv, inCheck, givesCheck, improving; bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture; Piece movedPiece; @@ -580,8 +580,7 @@ namespace { assert(0 <= ss->ply && ss->ply < MAX_PLY); (ss+1)->ply = ss->ply + 1; - ss->currentMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; - ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0]; + (ss+1)->excludedMove = bestMove = MOVE_NONE; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; Square prevSq = to_sq((ss-1)->currentMove); @@ -590,7 +589,10 @@ namespace { // starts with statScore = 0. Later grandchildren start with the last calculated // statScore of the previous grandchild. This influences the reduction rules in // LMR which are based on the statScore of parent position. - (ss+2)->statScore = 0; + if (rootNode) + (ss + 4)->statScore = 0; + else + (ss + 2)->statScore = 0; // Step 4. Transposition table lookup. We don't want the score of a partial // search to overwrite a previous full search TT value, so we use a different @@ -619,9 +621,8 @@ namespace { if (!pos.capture_or_promotion(ttMove)) update_quiet_stats(pos, ss, ttMove, nullptr, 0, stat_bonus(depth)); - // Extra penalty for a quiet TT or main killer move in previous ply when it gets refuted - if ( ((ss-1)->moveCount == 1 || (ss-1)->currentMove == (ss-1)->killers[0]) - && !pos.captured_piece()) + // Extra penalty for early quiet moves of the previous ply + if ((ss-1)->moveCount <= 2 && !pos.captured_piece()) update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + ONE_PLY)); } // Penalty for a quiet ttMove that fails low @@ -689,16 +690,16 @@ namespace { // Step 6. Static evaluation of the position if (inCheck) { - ss->staticEval = eval = pureStaticEval = VALUE_NONE; + ss->staticEval = eval = VALUE_NONE; improving = false; goto moves_loop; // Skip early pruning when in check } else if (ttHit) { // Never assume anything on values stored in TT - ss->staticEval = eval = pureStaticEval = tte->eval(); + ss->staticEval = eval = tte->eval(); if (eval == VALUE_NONE) - ss->staticEval = eval = pureStaticEval = evaluate(pos); + ss->staticEval = eval = evaluate(pos); // Can ttValue be used as a better position evaluation? if ( ttValue != VALUE_NONE @@ -711,13 +712,12 @@ namespace { { int bonus = -(ss-1)->statScore / 512; - pureStaticEval = evaluate(pos); - ss->staticEval = eval = pureStaticEval + bonus; + ss->staticEval = eval = evaluate(pos) + bonus; } else - ss->staticEval = eval = pureStaticEval = -(ss-1)->staticEval + 2 * Eval::Tempo; + ss->staticEval = eval = -(ss-1)->staticEval + 2 * Eval::Tempo; - tte->save(posKey, VALUE_NONE, ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, pureStaticEval); + tte->save(posKey, VALUE_NONE, ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); } // Step 7. Razoring (~2 Elo) @@ -741,7 +741,7 @@ namespace { && (ss-1)->currentMove != MOVE_NULL && (ss-1)->statScore < 23200 && eval >= beta - && pureStaticEval >= beta - 36 * depth / ONE_PLY + 225 + && ss->staticEval >= beta - 36 * depth / ONE_PLY + 225 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -773,7 +773,7 @@ namespace { // Do verification search at high depths, with null move pruning disabled // for us, until ply exceeds nmpMinPly. - thisThread->nmpMinPly = ss->ply + 3 * (depth-R) / 4; + thisThread->nmpMinPly = ss->ply + 3 * (depth-R) / (4 * ONE_PLY); thisThread->nmpColor = us; Value v = search(pos, ss, beta-1, beta, depth-R, false); @@ -824,8 +824,7 @@ namespace { } // Step 11. Internal iterative deepening (~2 Elo) - if ( depth >= 8 * ONE_PLY - && !ttMove) + if (depth >= 8 * ONE_PLY && !ttMove) { search(pos, ss, alpha, beta, depth - 7 * ONE_PLY, cutNode); @@ -839,6 +838,7 @@ moves_loop: // When in check, search starts from here const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, nullptr, (ss-4)->continuationHistory, nullptr, (ss-6)->continuationHistory }; + Move countermove = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq]; MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, @@ -846,10 +846,11 @@ moves_loop: // When in check, search starts from here contHist, countermove, ss->killers); - value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc + value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc moveCountPruning = false; ttCapture = ttMove && pos.capture_or_promotion(ttMove); + int singularExtensionLMRmultiplier = 0; // Step 12. Loop through all pseudo-legal moves until no moves remain // or a beta cutoff occurs. @@ -893,19 +894,25 @@ moves_loop: // When in check, search starts from here && move == ttMove && !rootNode && !excludedMove // Avoid recursive singular search - /* && ttValue != VALUE_NONE Already implicit in the next condition */ + /* && ttValue != VALUE_NONE Already implicit in the next condition */ && abs(ttValue) < VALUE_KNOWN_WIN && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3 * ONE_PLY && pos.legal(move)) { Value singularBeta = ttValue - 2 * depth / ONE_PLY; + Depth halfDepth = depth / (2 * ONE_PLY) * ONE_PLY; // ONE_PLY invariant ss->excludedMove = move; - value = search(pos, ss, singularBeta - 1, singularBeta, depth / 2, cutNode); + value = search(pos, ss, singularBeta - 1, singularBeta, halfDepth, cutNode); ss->excludedMove = MOVE_NONE; if (value < singularBeta) + { extension = ONE_PLY; + singularExtensionLMRmultiplier++; + if (value < singularBeta - std::min(3 * depth / ONE_PLY, 39)) + singularExtensionLMRmultiplier++; + } // Multi-cut pruning // Our ttMove is assumed to fail high, and now we failed high also on a reduced @@ -925,6 +932,19 @@ moves_loop: // When in check, search starts from here else if (type_of(move) == CASTLING) extension = ONE_PLY; + // Shuffle extension + else if ( PvNode + && pos.rule50_count() > 18 + && depth < 3 * ONE_PLY + && ss->ply < 3 * thisThread->rootDepth / ONE_PLY) // To avoid too deep searches + extension = ONE_PLY; + + // Passed pawn extension + else if ( move == ss->killers[0] + && pos.advanced_pawn_push(move) + && pos.pawn_passed(us, to_sq(move))) + extension = ONE_PLY; + // Calculate new depth for this move newDepth = depth - ONE_PLY + extension; @@ -934,7 +954,7 @@ moves_loop: // When in check, search starts from here && bestValue > VALUE_MATED_IN_MAX_PLY) { // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold - moveCountPruning = moveCount >= futility_move_count(improving,depth / ONE_PLY); + moveCountPruning = moveCount >= futility_move_count(improving, depth / ONE_PLY); if ( !captureOrPromotion && !givesCheck @@ -945,7 +965,8 @@ moves_loop: // When in check, search starts from here continue; // Reduced depth of the next LMR search - int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), DEPTH_ZERO) / ONE_PLY; + int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), DEPTH_ZERO); + lmrDepth /= ONE_PLY; // Countermoves based pruning (~20 Elo) if ( lmrDepth < 3 + ((ss-1)->statScore > 0 || (ss-1)->moveCount == 1) @@ -987,18 +1008,22 @@ moves_loop: // When in check, search starts from here // Step 16. Reduced depth search (LMR). If the move fails high it will be // re-searched at full depth. if ( depth >= 3 * ONE_PLY - && moveCount > 1 - && (!captureOrPromotion || moveCountPruning)) + && moveCount > 1 + 3 * rootNode + && ( !captureOrPromotion + || moveCountPruning + || ss->staticEval + PieceValue[EG][pos.captured_piece()] <= alpha)) { - Depth r = reduction(improving, depth, moveCount); + Depth r = reduction(improving, depth, moveCount); // Decrease reduction if position is or has been on the PV if (ttPv) - r -= ONE_PLY; + r -= 2 * ONE_PLY; // Decrease reduction if opponent's move count is high (~10 Elo) if ((ss-1)->moveCount > 15) r -= ONE_PLY; + // Decrease reduction if move has been singularly extended + r -= singularExtensionLMRmultiplier * ONE_PLY; if (!captureOrPromotion) { @@ -1090,8 +1115,8 @@ moves_loop: // When in check, search starts from here // We record how often the best move has been changed in each // iteration. This information is used for time management: When // the best move changes frequently, we allocate some more time. - if (moveCount > 1 && thisThread == Threads.main()) - ++static_cast(thisThread)->bestMoveChanges; + if (moveCount > 1) + ++thisThread->bestMoveChanges; } else // All other moves but the PV are set to the lowest value: this @@ -1177,7 +1202,7 @@ moves_loop: // When in check, search starts from here tte->save(posKey, value_to_tt(bestValue, ss->ply), ttPv, bestValue >= beta ? BOUND_LOWER : PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, - depth, bestMove, pureStaticEval); + depth, bestMove, ss->staticEval); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1185,8 +1210,8 @@ moves_loop: // When in check, search starts from here } - // qsearch() is the quiescence search function, which is called by the main - // search function with depth zero, or recursively with depth less than ONE_PLY. + // 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 Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { @@ -1216,8 +1241,7 @@ moves_loop: // When in check, search starts from here Thread* thisThread = pos.this_thread(); (ss+1)->ply = ss->ply + 1; - ss->currentMove = bestMove = MOVE_NONE; - ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0]; + bestMove = MOVE_NONE; inCheck = pos.checkers(); moveCount = 0;