X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=23402939a67bcea1ed663b821dd9fcecb742ec58;hp=651bd95b6feff4ceecc70840ef82fb37bafbb86d;hb=2bceba7f5162198834ca9f3dca0258e7eac1f797;hpb=9050eac59564fe96b3f24d2889bbef7336b28100 diff --git a/src/search.cpp b/src/search.cpp index 651bd95b..23402939 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -73,10 +73,10 @@ namespace { // Futility and reductions lookup tables, initialized at startup int FutilityMoveCounts[2][16]; // [improving][depth] - int Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber] + int Reductions[2][64][64]; // [improving][depth][moveNumber] template Depth reduction(bool i, Depth d, int mn) { - return Reductions[PvNode][i][std::min(d / ONE_PLY, 63)][std::min(mn, 63)] * ONE_PLY; + return (Reductions[i][std::min(d / ONE_PLY, 63)][std::min(mn, 63)] - PvNode) * ONE_PLY; } // History and stats update bonus, based on depth @@ -162,12 +162,11 @@ void Search::init() { { double r = log(d) * log(mc) / 1.95; - Reductions[NonPV][imp][d][mc] = int(std::round(r)); - Reductions[PV][imp][d][mc] = std::max(Reductions[NonPV][imp][d][mc] - 1, 0); + Reductions[imp][d][mc] = std::round(r); // Increase reduction for non-PV nodes when eval is not improving if (!imp && r > 1.0) - Reductions[NonPV][imp][d][mc]++; + Reductions[imp][d][mc]++; } for (int d = 0; d < 16; ++d) @@ -258,27 +257,23 @@ void MainThread::search() { // Find out minimum score and reset votes for moves which can be voted for (Thread* th: Threads) - { minScore = std::min(minScore, th->rootMoves[0].score); - votes[th->rootMoves[0].pv[0]] = 0; - } // Vote according to score and depth - auto square = [](int64_t x) { return x * x; }; for (Thread* th : Threads) - votes[th->rootMoves[0].pv[0]] += 200 + (square(th->rootMoves[0].score - minScore + 1) - * int64_t(th->completedDepth)); + { + int64_t s = th->rootMoves[0].score - minScore + 1; + votes[th->rootMoves[0].pv[0]] += 200 + s * s * int(th->completedDepth); + } // Select best thread - int64_t bestVote = votes[this->rootMoves[0].pv[0]]; + 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; @@ -306,7 +301,7 @@ void Thread::search() { // The former is needed to allow update_continuation_histories(ss-1, ...), // which accesses its argument at ss-4, also near the root. // The latter is needed for statScores and killer initialization. - Stack stack[MAX_PLY+8], *ss = stack+5; + Stack stack[MAX_PLY+10], *ss = stack+7; Move pv[MAX_PLY+1]; Value bestValue, alpha, beta, delta; Move lastBestMove = MOVE_NONE; @@ -316,8 +311,8 @@ void Thread::search() { Color us = rootPos.side_to_move(); bool failedLow; - std::memset(ss-5, 0, 8 * sizeof(Stack)); - for (int i = 5; i > 0; i--) + std::memset(ss-7, 0, 10 * sizeof(Stack)); + for (int i = 7; i > 0; i--) (ss-i)->continuationHistory = &this->continuationHistory[NO_PIECE][0]; // Use as sentinel ss->pv = pv; @@ -573,8 +568,8 @@ namespace { Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; Value bestValue, value, ttValue, eval, maxValue, pureStaticEval; - bool ttHit, pvHit, inCheck, givesCheck, improving; - bool captureOrPromotion, doFullDepthSearch, moveCountPruning, skipQuiets, ttCapture; + bool ttHit, ttPv, inCheck, givesCheck, improving; + bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture; Piece movedPiece; int moveCount, captureCount, quietCount; @@ -639,7 +634,7 @@ namespace { ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; ttMove = rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0] : ttHit ? tte->move() : MOVE_NONE; - pvHit = (ttHit && tte->pv_hit()) || (PvNode && depth > 4 * ONE_PLY); + ttPv = (ttHit && tte->is_pv()) || (PvNode && depth > 4 * ONE_PLY); // At non-PV nodes we check for an early TT cutoff if ( !PvNode @@ -706,7 +701,7 @@ namespace { if ( b == BOUND_EXACT || (b == BOUND_LOWER ? value >= beta : value <= alpha)) { - tte->save(posKey, value_to_tt(value, ss->ply), pvHit, b, + tte->save(posKey, value_to_tt(value, ss->ply), ttPv, b, std::min(DEPTH_MAX - ONE_PLY, depth + 6 * ONE_PLY), MOVE_NONE, VALUE_NONE); @@ -755,7 +750,7 @@ namespace { else ss->staticEval = eval = pureStaticEval = -(ss-1)->staticEval + 2 * Eval::Tempo; - tte->save(posKey, VALUE_NONE, pvHit, BOUND_NONE, DEPTH_NONE, MOVE_NONE, pureStaticEval); + tte->save(posKey, VALUE_NONE, ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, pureStaticEval); } // Step 7. Razoring (~2 Elo) @@ -835,7 +830,7 @@ namespace { int probCutCount = 0; while ( (move = mp.next_move()) != MOVE_NONE - && probCutCount < 3) + && probCutCount < 2 + 2 * cutNode) if (move != excludedMove && pos.legal(move)) { probCutCount++; @@ -850,7 +845,7 @@ namespace { // Perform a preliminary qsearch to verify that the move holds value = -qsearch(pos, ss+1, -raisedBeta, -raisedBeta+1); - // If the qsearch held perform the regular search + // If the qsearch held, perform the regular search if (value >= raisedBeta) value = -search(pos, ss+1, -raisedBeta, -raisedBeta+1, depth - 4 * ONE_PLY, !cutNode); @@ -874,7 +869,9 @@ namespace { moves_loop: // When in check, search starts from here - const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, nullptr, (ss-4)->continuationHistory }; + 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, @@ -884,12 +881,12 @@ moves_loop: // When in check, search starts from here ss->killers); value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc - skipQuiets = false; + moveCountPruning = false; ttCapture = ttMove && pos.capture_or_promotion(ttMove); // Step 12. Loop through all pseudo-legal moves until no moves remain // or a beta cutoff occurs. - while ((move = mp.next_move(skipQuiets)) != MOVE_NONE) + while ((move = mp.next_move(moveCountPruning)) != MOVE_NONE) { assert(is_ok(move)); @@ -918,9 +915,6 @@ moves_loop: // When in check, search starts from here movedPiece = pos.moved_piece(move); givesCheck = gives_check(pos, move); - moveCountPruning = depth < 16 * ONE_PLY - && moveCount >= FutilityMoveCounts[improving][depth / ONE_PLY]; - // Step 13. Extensions (~70 Elo) // Singular extension search (~60 Elo). If all moves but one fail low on a @@ -971,16 +965,17 @@ moves_loop: // When in check, search starts from here && pos.non_pawn_material(us) && bestValue > VALUE_MATED_IN_MAX_PLY) { + // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold + moveCountPruning = depth < 16 * ONE_PLY + && moveCount >= FutilityMoveCounts[improving][depth / ONE_PLY]; + if ( !captureOrPromotion && !givesCheck && !pos.advanced_pawn_push(move)) { // Move count based pruning (~30 Elo) if (moveCountPruning) - { - skipQuiets = true; continue; - } // Reduced depth of the next LMR search int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), DEPTH_ZERO) / ONE_PLY; @@ -1032,7 +1027,7 @@ moves_loop: // When in check, search starts from here Depth r = reduction(improving, depth, moveCount); // Decrease reduction if position is or has been on the PV - if (pvHit) + if (ttPv) r -= ONE_PLY; // Decrease reduction if opponent's move count is high (~10 Elo) @@ -1213,7 +1208,7 @@ moves_loop: // When in check, search starts from here bestValue = std::min(bestValue, maxValue); if (!excludedMove) - tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit, + tte->save(posKey, value_to_tt(bestValue, ss->ply), ttPv, bestValue >= beta ? BOUND_LOWER : PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, depth, bestMove, pureStaticEval); @@ -1277,7 +1272,7 @@ moves_loop: // When in check, search starts from here tte = TT.probe(posKey, ttHit); ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; ttMove = ttHit ? tte->move() : MOVE_NONE; - pvHit = ttHit && tte->pv_hit(); + pvHit = ttHit && tte->is_pv(); if ( !PvNode && ttHit @@ -1327,7 +1322,9 @@ moves_loop: // When in check, search starts from here futilityBase = bestValue + 128; } - const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, nullptr, (ss-4)->continuationHistory }; + const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, + nullptr, (ss-4)->continuationHistory, + nullptr, (ss-6)->continuationHistory }; // Initialize a MovePicker object for the current position, and prepare // to search the moves. Because the depth is <= 0 here, only captures, @@ -1477,7 +1474,7 @@ moves_loop: // When in check, search starts from here void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus) { - for (int i : {1, 2, 4}) + for (int i : {1, 2, 4, 6}) if (is_ok((ss-i)->currentMove)) (*(ss-i)->continuationHistory)[pc][to] << bonus; }