X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=d34e182392843b4874a07b1b5858610a4e78a143;hp=2e7dd6989736fa786c2a0b5ada5d681d35cb7136;hb=abd4400c874ab178d04c08d3668f3843aece114e;hpb=badb2aca44d6507f35dafc8b5c3921a6649a40f8 diff --git a/src/search.cpp b/src/search.cpp index 2e7dd698..d34e1823 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -61,35 +61,33 @@ namespace { // Different node types, used as a template parameter enum NodeType { NonPV, PV }; - // Sizes and phases of the skip-blocks, used for distributing search depths across the threads - constexpr int SkipSize[] = { 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4 }; - constexpr int SkipPhase[] = { 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 7 }; - // Razor and futility margins - constexpr int RazorMargin = 600; + constexpr int RazorMargin = 661; Value futility_margin(Depth d, bool improving) { - return Value((175 - 50 * improving) * d / ONE_PLY); + return Value(198 * (d / ONE_PLY - improving)); } - // Futility and reductions lookup tables, initialized at startup - int FutilityMoveCounts[2][16]; // [improving][depth] - int Reductions[2][64][64]; // [improving][depth][moveNumber] + // Reductions lookup table, initialized at startup + int Reductions[MAX_MOVES]; // [depth or moveNumber] + + Depth reduction(bool i, Depth d, int mn) { + int r = Reductions[d / ONE_PLY] * Reductions[mn]; + return ((r + 520) / 1024 + (!i && r > 999)) * ONE_PLY; + } - template Depth reduction(bool i, Depth d, int mn) { - return (Reductions[i][std::min(d / ONE_PLY, 63)][std::min(mn, 63)] - PvNode) * ONE_PLY; + constexpr int futility_move_count(bool improving, int depth) { + return (5 + depth * depth) * (1 + improving) / 2; } // History and stats update bonus, based on depth int stat_bonus(Depth depth) { int d = depth / ONE_PLY; - return d > 17 ? 0 : 29 * d * d + 138 * d - 134; + return d > 17 ? -8 : 22 * d * d + 151 * d - 140; } - // Add a small random component to draw evaluations to keep search dynamic - // and 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); + // Add a small random component to draw evaluations to avoid 3fold-blindness + Value value_draw(Thread* thisThread) { + return VALUE_DRAW + Value(2 * (thisThread->nodes & 1) - 1); } // Skill structure is used to implement strength limit @@ -103,6 +101,49 @@ namespace { Move best = MOVE_NONE; }; + // Breadcrumbs are used to mark nodes as being searched by a given thread + struct Breadcrumb { + std::atomic thread; + std::atomic key; + }; + std::array breadcrumbs; + + // ThreadHolding structure keeps track of which thread left breadcrumbs at the given + // node for potential reductions. A free node will be marked upon entering the moves + // loop by the constructor, and unmarked upon leaving that loop by the destructor. + struct ThreadHolding { + explicit ThreadHolding(Thread* thisThread, Key posKey, int ply) { + location = ply < 8 ? &breadcrumbs[posKey & (breadcrumbs.size() - 1)] : nullptr; + otherThread = false; + owning = false; + if (location) + { + // See if another already marked this location, if not, mark it ourselves + Thread* tmp = (*location).thread.load(std::memory_order_relaxed); + if (tmp == nullptr) + { + (*location).thread.store(thisThread, std::memory_order_relaxed); + (*location).key.store(posKey, std::memory_order_relaxed); + owning = true; + } + else if ( tmp != thisThread + && (*location).key.load(std::memory_order_relaxed) == posKey) + otherThread = true; + } + } + + ~ThreadHolding() { + if (owning) // Free the marked location + (*location).thread.store(nullptr, std::memory_order_relaxed); + } + + bool marked() { return otherThread; } + + private: + Breadcrumb* location; + bool otherThread, owning; + }; + template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); @@ -116,13 +157,6 @@ namespace { void update_quiet_stats(const Position& pos, Stack* ss, Move move, Move* quiets, int quietCount, int bonus); void update_capture_stats(const Position& pos, Move move, Move* captures, int captureCount, int bonus); - inline bool gives_check(const Position& pos, Move move) { - Color us = pos.side_to_move(); - return type_of(move) == NORMAL && !(pos.blockers_for_king(~us) & pos.pieces(us)) - ? pos.check_squares(type_of(pos.moved_piece(move))) & to_sq(move) - : pos.gives_check(move); - } - // perft() is our utility to verify move generation. All the leaf nodes up // to the given depth are generated and counted, and the sum is returned. template @@ -156,24 +190,8 @@ namespace { void Search::init() { - for (int imp = 0; imp <= 1; ++imp) - for (int d = 1; d < 64; ++d) - for (int mc = 1; mc < 64; ++mc) - { - double r = log(d) * log(mc) / 1.95; - - Reductions[imp][d][mc] = std::round(r); - - // Increase reduction for non-PV nodes when eval is not improving - if (!imp && r > 1.0) - Reductions[imp][d][mc]++; - } - - for (int d = 0; d < 16; ++d) - { - FutilityMoveCounts[0][d] = int(2.4 + 0.74 * pow(d, 1.78)); - FutilityMoveCounts[1][d] = int(5.0 + 1.00 * pow(d, 2.00)); - } + for (int i = 1; i < MAX_MOVES; ++i) + Reductions[i] = int(23.4 * std::log(i)); } @@ -186,12 +204,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() { @@ -216,8 +234,11 @@ void MainThread::search() { else { for (Thread* th : Threads) + { + th->bestMoveChanges = 0; if (th != this) th->start_searching(); + } Thread::search(); // Let's start searching! } @@ -245,35 +266,37 @@ 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() + && !(Skill(Options["Skill Level"]).enabled() || Options["UCI_LimitStrength"]) && rootMoves[0].pv[0] != MOVE_NONE) { std::map votes; Value minScore = this->rootMoves[0].score; - // Find out minimum score and reset votes for moves which can be voted + // Find out minimum score 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 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) + if (bestThread->rootMoves[0].score >= VALUE_MATE_IN_MAX_PLY) { - bestVote = votes[th->rootMoves[0].pv[0]]; - bestThread = th; + // Make sure we pick the shortest mate + if (th->rootMoves[0].score > bestThread->rootMoves[0].score) + bestThread = th; } + else if ( th->rootMoves[0].score >= VALUE_MATE_IN_MAX_PLY + || votes[th->rootMoves[0].pv[0]] > votes[bestThread->rootMoves[0].pv[0]]) + bestThread = th; + } } previousScore = bestThread->rootMoves[0].score; @@ -297,33 +320,41 @@ 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+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; 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(); - 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; bestValue = delta = alpha = -VALUE_INFINITE; beta = VALUE_INFINITE; - if (mainThread) - mainThread->bestMoveChanges = 0, failedLow = false; - size_t multiPV = Options["MultiPV"]; - Skill skill(Options["Skill Level"]); + + // Pick integer skill levels, but non-deterministically round up or down + // such that the average integer skill corresponds to the input floating point one. + // UCI_Elo is converted 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) results spanning a wide range of k values. + PRNG rng(now()); + double floatLevel = Options["UCI_LimitStrength"] ? + clamp(std::pow((Options["UCI_Elo"] - 1346.6) / 143.4, 1 / 0.806), 0.0, 20.0) : + double(Options["Skill Level"]); + int intLevel = int(floatLevel) + + ((floatLevel - int(floatLevel)) * 1024 > rng.rand() % 1024 ? 1 : 0); + Skill skill(intLevel); // When playing with strength handicap enable MultiPV search that we will // use behind the scenes to retrieve a set of possible moves. @@ -342,7 +373,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)); @@ -351,17 +382,9 @@ void Thread::search() { && !Threads.stop && !(Limits.depth && mainThread && rootDepth / ONE_PLY > Limits.depth)) { - // Distribute search depths across the helper threads - if (idx > 0) - { - int i = (idx - 1) % 20; - if (((rootDepth / ONE_PLY + SkipPhase[i]) / SkipSize[i]) % 2) - continue; // Retry with an incremented rootDepth - } - // Age out PV variability metric if (mainThread) - mainThread->bestMoveChanges *= 0.517, failedLow = false; + 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. @@ -386,15 +409,15 @@ void Thread::search() { selDepth = 0; // Reset aspiration window starting size - if (rootDepth >= 5 * ONE_PLY) + if (rootDepth >= 4 * ONE_PLY) { Value previousScore = rootMoves[pvIdx].previousScore; - delta = Value(20); + delta = Value(23); alpha = std::max(previousScore - delta,-VALUE_INFINITE); beta = std::min(previousScore + delta, VALUE_INFINITE); // Adjust contempt based on root move's previousScore (dynamic contempt) - int dct = ct + 88 * previousScore / (abs(previousScore) + 200); + int dct = ct + 86 * previousScore / (abs(previousScore) + 176); contempt = (us == WHITE ? make_score(dct, dct / 2) : -make_score(dct, dct / 2)); @@ -438,21 +461,20 @@ void Thread::search() { beta = (alpha + beta) / 2; alpha = std::max(bestValue - delta, -VALUE_INFINITE); + failedHighCnt = 0; if (mainThread) - { - failedHighCnt = 0; - failedLow = true; mainThread->stopOnPonderhit = false; - } } else if (bestValue >= beta) { beta = std::min(bestValue + delta, VALUE_INFINITE); - if (mainThread) - ++failedHighCnt; + ++failedHighCnt; } else + { + ++rootMoves[pvIdx].bestMoveCount; break; + } delta += delta / 4 + 5; @@ -493,19 +515,24 @@ void Thread::search() { && !Threads.stop && !mainThread->stopOnPonderhit) { - double fallingEval = (306 + 119 * failedLow + 6 * (mainThread->previousScore - bestValue)) / 581.0; - fallingEval = std::max(0.5, std::min(1.5, fallingEval)); + double fallingEval = (354 + 10 * (mainThread->previousScore - bestValue)) / 692.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; + timeReduction = lastBestMoveDepth + 9 * ONE_PLY < completedDepth ? 1.97 : 0.98; + double reduction = (1.36 + mainThread->previousTimeReduction) / (2.29 * timeReduction); // Use part of the gained time from a previous stable move for the current move - double bestMoveInstability = 1.0 + mainThread->bestMoveChanges; - bestMoveInstability *= std::pow(mainThread->previousTimeReduction, 0.528) / timeReduction; + 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 - || Time.elapsed() > Time.optimum() * bestMoveInstability * fallingEval) + || Time.elapsed() > Time.optimum() * fallingEval * reduction * bestMoveInstability) { // If we are allowed to ponder do not stop the search now but // keep pondering until the GUI sends "ponderhit" or "stop". @@ -546,7 +573,7 @@ namespace { && !rootNode && pos.has_game_cycle(ss->ply)) { - alpha = value_draw(depth, pos.this_thread()); + alpha = value_draw(pos.this_thread()); if (alpha >= beta) return alpha; } @@ -567,17 +594,17 @@ namespace { Key posKey; Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; - Value bestValue, value, ttValue, eval, maxValue, pureStaticEval; - bool ttHit, ttPv, inCheck, givesCheck, improving; + Value bestValue, value, ttValue, eval, maxValue; + bool ttHit, ttPv, inCheck, givesCheck, improving, doLMR; bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture; Piece movedPiece; - int moveCount, captureCount, quietCount; + int moveCount, captureCount, quietCount, singularLMR; // Step 1. Initialize node Thread* thisThread = pos.this_thread(); inCheck = pos.checkers(); Color us = pos.side_to_move(); - moveCount = captureCount = quietCount = ss->moveCount = 0; + moveCount = captureCount = quietCount = singularLMR = ss->moveCount = 0; bestValue = -VALUE_INFINITE; maxValue = VALUE_INFINITE; @@ -596,7 +623,7 @@ namespace { || pos.is_draw(ss->ply) || ss->ply >= MAX_PLY) return (ss->ply >= MAX_PLY && !inCheck) ? evaluate(pos) - : value_draw(depth, pos.this_thread()); + : value_draw(pos.this_thread()); // Step 3. Mate distance pruning. Even if we mate at the next move our score // would be at best mate_in(ss->ply+1), but if alpha is already bigger because @@ -613,8 +640,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); @@ -623,7 +649,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 @@ -634,7 +663,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; - ttPv = (ttHit && tte->is_pv()) || (PvNode && depth > 4 * ONE_PLY); + ttPv = PvNode || (ttHit && tte->is_pv()); // At non-PV nodes we check for an early TT cutoff if ( !PvNode @@ -652,10 +681,9 @@ 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()) - update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + ONE_PLY)); + // 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 else if (!pos.capture_or_promotion(ttMove)) @@ -722,16 +750,19 @@ 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(); + // Never assume anything about values stored in TT + ss->staticEval = eval = tte->eval(); if (eval == VALUE_NONE) - ss->staticEval = eval = pureStaticEval = evaluate(pos); + ss->staticEval = eval = evaluate(pos); + + if (eval == VALUE_DRAW) + eval = value_draw(thisThread); // Can ttValue be used as a better position evaluation? if ( ttValue != VALUE_NONE @@ -744,13 +775,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) @@ -772,9 +802,10 @@ namespace { // Step 9. Null move search with verification search (~40 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 23200 + && (ss-1)->statScore < 22661 && eval >= beta - && pureStaticEval >= beta - 36 * depth / ONE_PLY + 225 + && eval >= ss->staticEval + && ss->staticEval >= beta - 33 * depth / ONE_PLY + 299 - improving * 30 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -782,7 +813,7 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = ((823 + 67 * depth / ONE_PLY) / 256 + std::min(int(eval - beta) / 200, 3)) * ONE_PLY; + Depth R = ((835 + 70 * depth / ONE_PLY) / 256 + std::min(int(eval - beta) / 185, 3)) * ONE_PLY; ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0]; @@ -799,14 +830,14 @@ namespace { if (nullValue >= VALUE_MATE_IN_MAX_PLY) nullValue = beta; - if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 12 * ONE_PLY)) + if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 13 * ONE_PLY)) return nullValue; assert(!thisThread->nmpMinPly); // Recursive verification is not allowed // 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); @@ -825,7 +856,7 @@ namespace { && depth >= 5 * ONE_PLY && abs(beta) < VALUE_MATE_IN_MAX_PLY) { - Value raisedBeta = std::min(beta + 216 - 48 * improving, VALUE_INFINITE); + Value raisedBeta = std::min(beta + 191 - 46 * improving, VALUE_INFINITE); MovePicker mp(pos, ttMove, raisedBeta - ss->staticEval, &thisThread->captureHistory); int probCutCount = 0; @@ -845,7 +876,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); @@ -857,8 +888,7 @@ namespace { } // Step 11. Internal iterative deepening (~2 Elo) - if ( depth >= 8 * ONE_PLY - && !ttMove) + if (depth >= 7 * ONE_PLY && !ttMove) { search(pos, ss, alpha, beta, depth - 7 * ONE_PLY, cutNode); @@ -869,7 +899,10 @@ 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, @@ -877,11 +910,14 @@ 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); + // Mark this node as being searched + ThreadHolding th(thisThread, posKey, ss->ply); + // Step 12. Loop through all pseudo-legal moves until no moves remain // or a beta cutoff occurs. while ((move = mp.next_move(moveCountPruning)) != MOVE_NONE) @@ -911,11 +947,7 @@ moves_loop: // When in check, search starts from here extension = DEPTH_ZERO; captureOrPromotion = pos.capture_or_promotion(move); movedPiece = pos.moved_piece(move); - givesCheck = gives_check(pos, move); - - // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold - moveCountPruning = depth < 16 * ONE_PLY - && moveCount >= FutilityMoveCounts[improving][depth / ONE_PLY]; + givesCheck = pos.gives_check(move); // Step 13. Extensions (~70 Elo) @@ -924,39 +956,61 @@ 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 >= 8 * ONE_PLY + if ( depth >= 6 * ONE_PLY && move == ttMove && !rootNode && !excludedMove // Avoid recursive singular search - && ttValue != VALUE_NONE + /* && 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 = std::max(ttValue - 2 * depth / ONE_PLY, -VALUE_MATE); + 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; + singularLMR++; + + if (value < singularBeta - std::min(4 * depth / ONE_PLY, 36)) + singularLMR++; + } // Multi-cut pruning // 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 is multiple moves fail high, and we can prune the whole subtree by returning - // the hard beta bound. - else if (cutNode && singularBeta > beta) - return beta; + // that multiple moves fail high, and we can prune the whole subtree by returning + // a soft bound. + else if ( eval >= beta + && singularBeta >= beta) + return singularBeta; } // Check extension (~2 Elo) else if ( givesCheck - && (pos.blockers_for_king(~us) & from_sq(move) || pos.see_ge(move))) + && (pos.is_discovery_check_on_king(~us, move) || pos.see_ge(move))) + extension = ONE_PLY; + + // Shuffle extension + else if ( PvNode + && pos.rule50_count() > 18 + && depth < 3 * ONE_PLY + && ++thisThread->shuffleExts < thisThread->nodes.load(std::memory_order_relaxed) / 4) // To avoid too many extensions + 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; // Castling extension - else if (type_of(move) == CASTLING) + if (type_of(move) == CASTLING) extension = ONE_PLY; // Calculate new depth for this move @@ -967,35 +1021,39 @@ 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 = moveCount >= futility_move_count(improving, depth / ONE_PLY); + if ( !captureOrPromotion && !givesCheck - && !pos.advanced_pawn_push(move)) + && (!pos.advanced_pawn_push(move) || pos.non_pawn_material(~us) > BishopValueMg)) { - // Move count based pruning (~30 Elo) + // Move count based pruning if (moveCountPruning) 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) + if ( lmrDepth < 4 + ((ss-1)->statScore > 0 || (ss-1)->moveCount == 1) && (*contHist[0])[movedPiece][to_sq(move)] < CounterMovePruneThreshold && (*contHist[1])[movedPiece][to_sq(move)] < CounterMovePruneThreshold) continue; // Futility pruning: parent node (~2 Elo) - if ( lmrDepth < 7 + if ( lmrDepth < 6 && !inCheck - && ss->staticEval + 256 + 200 * lmrDepth <= alpha) + && ss->staticEval + 250 + 211 * lmrDepth <= alpha) continue; // Prune moves with negative SEE (~10 Elo) - if (!pos.see_ge(move, Value(-29 * lmrDepth * lmrDepth))) + if (!pos.see_ge(move, Value(-(31 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth))) continue; } - else if ( !extension // (~20 Elo) - && !pos.see_ge(move, -PawnValueEg * (depth / ONE_PLY))) + else if ( !(givesCheck && extension) + && !pos.see_ge(move, Value(-199) * (depth / ONE_PLY))) // (~20 Elo) continue; } @@ -1019,19 +1077,30 @@ 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 + 2 * rootNode + && (!rootNode || thisThread->best_move_count(move) == 0) + && ( !captureOrPromotion + || moveCountPruning + || ss->staticEval + PieceValue[EG][pos.captured_piece()] <= alpha + || cutNode)) { - Depth r = reduction(improving, depth, moveCount); + Depth r = reduction(improving, depth, moveCount); + + // Reduction if other threads are searching this position. + if (th.marked()) + r += ONE_PLY; // 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 ttMove has been singularly extended + r -= singularLMR * ONE_PLY; + if (!captureOrPromotion) { // Increase reduction if ttMove is a capture (~0 Elo) @@ -1046,39 +1115,59 @@ moves_loop: // When in check, search starts from here // castling moves, because they are coded as "king captures rook" and // hence break make_move(). (~5 Elo) else if ( type_of(move) == NORMAL - && !pos.see_ge(make_move(to_sq(move), from_sq(move)))) + && !pos.see_ge(reverse_move(move))) r -= 2 * ONE_PLY; 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)] - - 4000; + - 4729; + + // Reset statScore to zero if negative and most stats shows >= 0 + if ( ss->statScore < 0 + && (*contHist[0])[movedPiece][to_sq(move)] >= 0 + && (*contHist[1])[movedPiece][to_sq(move)] >= 0 + && thisThread->mainHistory[us][from_to(move)] >= 0) + ss->statScore = 0; // Decrease/increase reduction by comparing opponent's stat score (~10 Elo) - if (ss->statScore >= 0 && (ss-1)->statScore < 0) + if (ss->statScore >= -99 && (ss-1)->statScore < -116) r -= ONE_PLY; - else if ((ss-1)->statScore >= 0 && ss->statScore < 0) + else if ((ss-1)->statScore >= -117 && ss->statScore < -144) r += ONE_PLY; // Decrease/increase reduction for moves with a good/bad history (~30 Elo) - r -= ss->statScore / 20000 * ONE_PLY; + r -= ss->statScore / 16384 * ONE_PLY; } - Depth d = std::max(newDepth - std::max(r, DEPTH_ZERO), ONE_PLY); + Depth d = clamp(newDepth - r, ONE_PLY, newDepth); value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - doFullDepthSearch = (value > alpha && d != newDepth); + doFullDepthSearch = (value > alpha && d != newDepth), doLMR = true; } else - doFullDepthSearch = !PvNode || moveCount > 1; + doFullDepthSearch = !PvNode || moveCount > 1, doLMR = false; // Step 17. Full depth search when LMR is skipped or fails high if (doFullDepthSearch) + { value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); + if (doLMR && !captureOrPromotion) + { + int bonus = value > alpha ? stat_bonus(newDepth) + : -stat_bonus(newDepth); + + if (move == ss->killers[0]) + bonus += bonus / 4; + + update_continuation_histories(ss, movedPiece, to_sq(move), bonus); + } + } + // For PV nodes only, do a full PV search on the first move or after a fail // high (in the latter case search only if value < beta), otherwise let the // parent node fail low with value <= alpha and try another move. @@ -1122,8 +1211,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 @@ -1209,7 +1298,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); @@ -1217,8 +1306,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) { @@ -1248,8 +1337,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; @@ -1290,7 +1378,7 @@ moves_loop: // When in check, search starts from here { if (ttHit) { - // Never assume anything on values stored in TT + // Never assume anything about values stored in TT if ((ss->staticEval = bestValue = tte->eval()) == VALUE_NONE) ss->staticEval = bestValue = evaluate(pos); @@ -1317,10 +1405,12 @@ moves_loop: // When in check, search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + 128; + futilityBase = bestValue + 153; } - 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, @@ -1336,7 +1426,7 @@ moves_loop: // When in check, search starts from here { assert(is_ok(move)); - givesCheck = gives_check(pos, move); + givesCheck = pos.gives_check(move); moveCount++; @@ -1371,6 +1461,7 @@ moves_loop: // When in check, search starts from here // Don't search moves with negative SEE values if ( (!inCheck || evasionPrunable) + && (!givesCheck || !(pos.blockers_for_king(~pos.side_to_move()) & from_sq(move))) && !pos.see_ge(move)) continue; @@ -1470,7 +1561,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; } @@ -1481,7 +1572,7 @@ moves_loop: // When in check, search starts from here void update_capture_stats(const Position& pos, Move move, Move* captures, int captureCount, int bonus) { - CapturePieceToHistory& captureHistory = pos.this_thread()->captureHistory; + CapturePieceToHistory& captureHistory = pos.this_thread()->captureHistory; Piece moved_piece = pos.moved_piece(move); PieceType captured = type_of(pos.piece_on(to_sq(move))); @@ -1514,6 +1605,9 @@ moves_loop: // When in check, search starts from here thisThread->mainHistory[us][from_to(move)] << bonus; update_continuation_histories(ss, pos.moved_piece(move), to_sq(move), bonus); + if (type_of(pos.moved_piece(move)) != PAWN) + thisThread->mainHistory[us][from_to(reverse_move(move))] << -bonus; + if (is_ok((ss-1)->currentMove)) { Square prevSq = to_sq((ss-1)->currentMove); @@ -1722,7 +1816,7 @@ void Tablebases::rank_root_moves(Position& pos, Search::RootMoves& rootMoves) { } else { - // Assign the same rank to all moves + // Clean up if root_probe() and root_probe_wdl() have failed for (auto& m : rootMoves) m.tbRank = 0; }