X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=91ac60ad4b2615f47864631e139b1108a4266012;hp=c70fbf60cd6c1efa9b9599d31c898cfd116960d7;hb=9587eeeb5ed29f834d4f956b92e0e732877c47a7;hpb=7e89a71624e07c735c2230dbbf2c7dbae864916e diff --git a/src/search.cpp b/src/search.cpp index c70fbf60..91ac60ad 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -2,7 +2,7 @@ Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad - Copyright (C) 2015-2019 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad + Copyright (C) 2015-2020 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -61,10 +61,13 @@ namespace { // Different node types, used as a template parameter enum NodeType { NonPV, PV }; + constexpr uint64_t TtHitAverageWindow = 4096; + constexpr uint64_t TtHitAverageResolution = 1024; + // Razor and futility margins - constexpr int RazorMargin = 661; + constexpr int RazorMargin = 527; Value futility_margin(Depth d, bool improving) { - return Value(198 * (d - improving)); + return Value(227 * (d - improving)); } // Reductions lookup table, initialized at startup @@ -72,16 +75,16 @@ namespace { Depth reduction(bool i, Depth d, int mn) { int r = Reductions[d] * Reductions[mn]; - return (r + 520) / 1024 + (!i && r > 999); + return (r + 570) / 1024 + (!i && r > 1018); } - constexpr int futility_move_count(bool improving, int depth) { - return (5 + depth * depth) * (1 + improving) / 2; + constexpr int futility_move_count(bool improving, Depth depth) { + return (3 + depth * depth) / (2 - improving); } // History and stats update bonus, based on depth int stat_bonus(Depth d) { - return d > 17 ? -8 : 22 * d * d + 151 * d - 140; + return d > 15 ? 27 : 17 * d * d + 133 * d - 134; } // Add a small random component to draw evaluations to avoid 3fold-blindness @@ -150,11 +153,12 @@ namespace { Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth = 0); Value value_to_tt(Value v, int ply); - Value value_from_tt(Value v, int ply); + Value value_from_tt(Value v, int ply, int r50c); void update_pv(Move* pv, Move move, Move* childPv); void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus); - 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); + void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus, int depth); + void update_all_stats(const Position& pos, Stack* ss, Move bestMove, Value bestValue, Value beta, Square prevSq, + Move* quietsSearched, int quietCount, Move* capturesSearched, int captureCount, Depth depth); // 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. @@ -190,7 +194,7 @@ namespace { void Search::init() { for (int i = 1; i < MAX_MOVES; ++i) - Reductions[i] = int((23.4 + std::log(Threads.size()) / 2) * std::log(i)); + Reductions[i] = int((24.8 + std::log(Threads.size())) * std::log(i)); } @@ -232,14 +236,8 @@ void MainThread::search() { } else { - for (Thread* th : Threads) - { - th->bestMoveChanges = 0; - if (th != this) - th->start_searching(); - } - - Thread::search(); // Let's start searching! + Threads.start_searching(); // start non-main threads + Thread::search(); // main thread start searching } // When we reach the maximum depth, we can arrive here without a raise of @@ -256,9 +254,7 @@ void MainThread::search() { Threads.stop = true; // Wait until all threads have finished - for (Thread* th : Threads) - if (th != this) - th->wait_for_search_finished(); + Threads.wait_for_search_finished(); // When playing in 'nodes as time' mode, subtract the searched nodes from // the available ones before exiting. @@ -267,38 +263,13 @@ void MainThread::search() { Thread* bestThread = this; - // Check if there are threads with a better score than main thread - if ( Options["MultiPV"] == 1 + if ( int(Options["MultiPV"]) == 1 && !Limits.depth - && !(Skill(Options["Skill Level"]).enabled() || Options["UCI_LimitStrength"]) - && rootMoves[0].pv[0] != MOVE_NONE) - { - std::map votes; - Value minScore = this->rootMoves[0].score; + && !(Skill(Options["Skill Level"]).enabled() || int(Options["UCI_LimitStrength"])) + && rootMoves[0].pv[0] != MOVE_NONE) + bestThread = Threads.get_best_thread(); - // Find out minimum score - for (Thread* th: Threads) - minScore = std::min(minScore, th->rootMoves[0].score); - - // Vote according to score and depth, and select the best thread - for (Thread* th : Threads) - { - votes[th->rootMoves[0].pv[0]] += - (th->rootMoves[0].score - minScore + 14) * int(th->completedDepth); - - if (bestThread->rootMoves[0].score >= VALUE_MATE_IN_MAX_PLY) - { - // 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; + bestPreviousScore = bestThread->rootMoves[0].score; // Send again PV info if we have a new best thread if (bestThread != this) @@ -331,6 +302,7 @@ void Thread::search() { MainThread* mainThread = (this == Threads.main() ? Threads.main() : nullptr); double timeReduction = 1, totBestMoveChanges = 0; Color us = rootPos.side_to_move(); + int iterIdx = 0; std::memset(ss-7, 0, 10 * sizeof(Stack)); for (int i = 7; i > 0; i--) @@ -341,7 +313,20 @@ void Thread::search() { bestValue = delta = alpha = -VALUE_INFINITE; beta = VALUE_INFINITE; - size_t multiPV = Options["MultiPV"]; + if (mainThread) + { + if (mainThread->bestPreviousScore == VALUE_INFINITE) + for (int i = 0; i < 4; ++i) + mainThread->iterValue[i] = VALUE_ZERO; + else + for (int i = 0; i < 4; ++i) + mainThread->iterValue[i] = mainThread->bestPreviousScore; + } + + std::copy(&lowPlyHistory[2][0], &lowPlyHistory.back().back() + 1, &lowPlyHistory[0][0]); + std::fill(&lowPlyHistory[MAX_LPH - 2][0], &lowPlyHistory.back().back() + 1, 0); + + size_t multiPV = size_t(Options["MultiPV"]); // Pick integer skill levels, but non-deterministically round up or down // such that the average integer skill corresponds to the input floating point one. @@ -350,7 +335,7 @@ void Thread::search() { // 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) : + Utility::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); @@ -362,6 +347,7 @@ void Thread::search() { multiPV = std::max(multiPV, (size_t)4); multiPV = std::min(multiPV, rootMoves.size()); + ttHitAverage = TtHitAverageWindow * TtHitAverageResolution / 2; int ct = int(Options["Contempt"]) * PawnValueEg / 100; // From centipawns @@ -377,6 +363,8 @@ void Thread::search() { contempt = (us == WHITE ? make_score(ct, ct / 2) : -make_score(ct, ct / 2)); + int searchAgainCounter = 0; + // Iterative deepening loop until requested to stop or the target depth is reached while ( ++rootDepth < MAX_PLY && !Threads.stop @@ -394,6 +382,9 @@ void Thread::search() { size_t pvFirst = 0; pvLast = 0; + if (!Threads.increaseDepth) + searchAgainCounter++; + // MultiPV loop. We perform a full root search for each PV line for (pvIdx = 0; pvIdx < multiPV && !Threads.stop; ++pvIdx) { @@ -411,13 +402,13 @@ void Thread::search() { // Reset aspiration window starting size if (rootDepth >= 4) { - Value previousScore = rootMoves[pvIdx].previousScore; - delta = Value(21 + abs(previousScore) / 128); - alpha = std::max(previousScore - delta,-VALUE_INFINITE); - beta = std::min(previousScore + delta, VALUE_INFINITE); + Value prev = rootMoves[pvIdx].previousScore; + delta = Value(19); + 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 + 86 * previousScore / (abs(previousScore) + 176); + int dct = ct + (110 - ct / 2) * prev / (abs(prev) + 140); contempt = (us == WHITE ? make_score(dct, dct / 2) : -make_score(dct, dct / 2)); @@ -429,7 +420,7 @@ void Thread::search() { int failedHighCnt = 0; while (true) { - Depth adjustedDepth = std::max(1, rootDepth - failedHighCnt); + Depth adjustedDepth = std::max(1, rootDepth - failedHighCnt - searchAgainCounter); bestValue = ::search(rootPos, ss, alpha, beta, adjustedDepth, false); // Bring the best move to the front. It is critical that sorting @@ -515,12 +506,13 @@ void Thread::search() { && !Threads.stop && !mainThread->stopOnPonderhit) { - double fallingEval = (354 + 10 * (mainThread->previousScore - bestValue)) / 692.0; - fallingEval = clamp(fallingEval, 0.5, 1.5); + double fallingEval = (296 + 6 * (mainThread->bestPreviousScore - bestValue) + + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 725.0; + fallingEval = Utility::clamp(fallingEval, 0.5, 1.5); // If the bestMove is stable over several iterations, reduce time accordingly - timeReduction = lastBestMoveDepth + 9 < completedDepth ? 1.97 : 0.98; - double reduction = (1.36 + mainThread->previousTimeReduction) / (2.29 * timeReduction); + timeReduction = lastBestMoveDepth + 10 < completedDepth ? 1.92 : 0.95; + double reduction = (1.47 + mainThread->previousTimeReduction) / (2.22 * timeReduction); // Use part of the gained time from a previous stable move for the current move for (Thread* th : Threads) @@ -530,9 +522,11 @@ void Thread::search() { } 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() * fallingEval * reduction * bestMoveInstability) + double totalTime = rootMoves.size() == 1 ? 0 : + Time.optimum() * fallingEval * reduction * bestMoveInstability; + + // Stop the search if we have exceeded the totalTime, at least 1ms search + if (Time.elapsed() > totalTime) { // If we are allowed to ponder do not stop the search now but // keep pondering until the GUI sends "ponderhit" or "stop". @@ -541,7 +535,16 @@ void Thread::search() { else Threads.stop = true; } + else if ( Threads.increaseDepth + && !mainThread->ponder + && Time.elapsed() > totalTime * 0.56) + Threads.increaseDepth = false; + else + Threads.increaseDepth = true; } + + mainThread->iterValue[iterIdx] = bestValue; + iterIdx = (iterIdx + 1) & 3; } if (!mainThread) @@ -593,15 +596,16 @@ namespace { Key posKey; Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; - Value bestValue, value, ttValue, eval, maxValue; - bool ttHit, ttPv, inCheck, givesCheck, improving, doLMR, priorCapture; - bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture, singularLMR; + Value bestValue, value, ttValue, eval, maxValue, probcutBeta; + bool ttHit, ttPv, formerPv, givesCheck, improving, didLMR, priorCapture; + bool captureOrPromotion, doFullDepthSearch, moveCountPruning, + ttCapture, singularQuietLMR; Piece movedPiece; int moveCount, captureCount, quietCount; // Step 1. Initialize node Thread* thisThread = pos.this_thread(); - inCheck = pos.checkers(); + ss->inCheck = pos.checkers(); priorCapture = pos.captured_piece(); Color us = pos.side_to_move(); moveCount = captureCount = quietCount = ss->moveCount = 0; @@ -622,8 +626,8 @@ namespace { if ( Threads.stop.load(std::memory_order_relaxed) || pos.is_draw(ss->ply) || ss->ply >= MAX_PLY) - return (ss->ply >= MAX_PLY && !inCheck) ? evaluate(pos) - : value_draw(pos.this_thread()); + return (ss->ply >= MAX_PLY && !ss->inCheck) ? evaluate(pos) + : 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 @@ -658,12 +662,24 @@ namespace { // search to overwrite a previous full search TT value, so we use a different // position key in case of an excluded move. excludedMove = ss->excludedMove; - posKey = pos.key() ^ Key(excludedMove << 16); // Isn't a very good hash + posKey = excludedMove == MOVE_NONE ? pos.key() : pos.key() ^ make_key(excludedMove); tte = TT.probe(posKey, ttHit); - ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; + ttValue = ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE; ttMove = rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0] : ttHit ? tte->move() : MOVE_NONE; ttPv = PvNode || (ttHit && tte->is_pv()); + formerPv = ttPv && !PvNode; + + if ( ttPv + && depth > 12 + && ss->ply - 1 < MAX_LPH + && !priorCapture + && 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 * ttHit; // At non-PV nodes we check for an early TT cutoff if ( !PvNode @@ -679,7 +695,7 @@ namespace { if (ttValue >= beta) { if (!pos.capture_or_promotion(ttMove)) - update_quiet_stats(pos, ss, ttMove, nullptr, 0, stat_bonus(depth)); + update_quiet_stats(pos, ss, ttMove, stat_bonus(depth), depth); // Extra penalty for early quiet moves of the previous ply if ((ss-1)->moveCount <= 2 && !priorCapture) @@ -693,7 +709,9 @@ namespace { update_continuation_histories(ss, pos.moved_piece(ttMove), to_sq(ttMove), penalty); } } - return ttValue; + + if (pos.rule50_count() < 90) + return ttValue; } // Step 5. Tablebases probe @@ -719,9 +737,10 @@ namespace { int drawScore = TB::UseRule50 ? 1 : 0; - value = wdl < -drawScore ? -VALUE_MATE + MAX_PLY + ss->ply + 1 - : wdl > drawScore ? VALUE_MATE - MAX_PLY - ss->ply - 1 - : VALUE_DRAW + 2 * wdl * drawScore; + // use the range VALUE_MATE_IN_MAX_PLY to VALUE_TB_WIN_IN_MAX_PLY to score + value = wdl < -drawScore ? VALUE_MATED_IN_MAX_PLY + ss->ply + 1 + : wdl > drawScore ? VALUE_MATE_IN_MAX_PLY - ss->ply - 1 + : VALUE_DRAW + 2 * wdl * drawScore; Bound b = wdl < -drawScore ? BOUND_UPPER : wdl > drawScore ? BOUND_LOWER : BOUND_EXACT; @@ -747,12 +766,15 @@ namespace { } } + CapturePieceToHistory& captureHistory = thisThread->captureHistory; + // Step 6. Static evaluation of the position - if (inCheck) + if (ss->inCheck) { + // Skip early pruning when in check ss->staticEval = eval = VALUE_NONE; improving = false; - goto moves_loop; // Skip early pruning when in check + goto moves_loop; } else if (ttHit) { @@ -778,23 +800,23 @@ namespace { ss->staticEval = eval = evaluate(pos) + bonus; } else - ss->staticEval = eval = -(ss-1)->staticEval + 2 * Eval::Tempo; + ss->staticEval = eval = -(ss-1)->staticEval + 2 * Tempo; tte->save(posKey, VALUE_NONE, ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); } - // Step 7. Razoring (~2 Elo) + // Step 7. Razoring (~1 Elo) if ( !rootNode // The required rootNode PV handling is not available in qsearch - && depth < 2 + && depth == 1 && eval <= alpha - RazorMargin) return qsearch(pos, ss, alpha, beta); - improving = ss->staticEval >= (ss-2)->staticEval - || (ss-2)->staticEval == VALUE_NONE; + improving = (ss-2)->staticEval == VALUE_NONE ? (ss->staticEval > (ss-4)->staticEval + || (ss-4)->staticEval == VALUE_NONE) : ss->staticEval > (ss-2)->staticEval; - // Step 8. Futility pruning: child node (~30 Elo) + // Step 8. Futility pruning: child node (~50 Elo) if ( !PvNode - && depth < 7 + && depth < 6 && eval - futility_margin(depth, improving) >= beta && eval < VALUE_KNOWN_WIN) // Do not return unproven wins return eval; @@ -802,10 +824,10 @@ namespace { // Step 9. Null move search with verification search (~40 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 22661 + && (ss-1)->statScore < 23824 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 33 * depth + 299 - improving * 30 + && ss->staticEval >= beta - 33 * depth - 33 * improving + 112 * ttPv + 311 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -813,7 +835,7 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = (835 + 70 * depth) / 256 + std::min(int(eval - beta) / 185, 3); + Depth R = (737 + 77 * depth) / 246 + std::min(int(eval - beta) / 192, 3); ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0]; @@ -826,8 +848,8 @@ namespace { if (nullValue >= beta) { - // Do not return unproven mate scores - if (nullValue >= VALUE_MATE_IN_MAX_PLY) + // Do not return unproven mate or TB scores + if (nullValue >= VALUE_TB_WIN_IN_MAX_PLY) nullValue = beta; if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 13)) @@ -849,18 +871,32 @@ namespace { } } + probcutBeta = beta + 176 - 49 * improving; + // Step 10. ProbCut (~10 Elo) // If we have a good enough capture and a reduced search returns a value // much above beta, we can (almost) safely prune the previous move. if ( !PvNode - && depth >= 5 - && abs(beta) < VALUE_MATE_IN_MAX_PLY) + && depth > 4 + && abs(beta) < VALUE_TB_WIN_IN_MAX_PLY + && !( ttHit + && tte->depth() >= depth - 3 + && ttValue != VALUE_NONE + && ttValue < probcutBeta)) { - Value raisedBeta = std::min(beta + 191 - 46 * improving, VALUE_INFINITE); - MovePicker mp(pos, ttMove, raisedBeta - ss->staticEval, &thisThread->captureHistory); + if ( ttHit + && tte->depth() >= depth - 3 + && ttValue != VALUE_NONE + && ttValue >= probcutBeta + && ttMove + && pos.capture_or_promotion(ttMove)) + return probcutBeta; + + assert(probcutBeta < VALUE_INFINITE); + MovePicker mp(pos, ttMove, probcutBeta - ss->staticEval, &captureHistory); int probCutCount = 0; - while ( (move = mp.next_move()) != MOVE_NONE + while ( (move = mp.next_move()) != MOVE_NONE && probCutCount < 2 + 2 * cutNode) if (move != excludedMove && pos.legal(move)) { @@ -871,7 +907,7 @@ namespace { probCutCount++; ss->currentMove = move; - ss->continuationHistory = &thisThread->continuationHistory[inCheck] + ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck] [captureOrPromotion] [pos.moved_piece(move)] [to_sq(move)]; @@ -879,26 +915,34 @@ namespace { pos.do_move(move, st); // Perform a preliminary qsearch to verify that the move holds - value = -qsearch(pos, ss+1, -raisedBeta, -raisedBeta+1); + value = -qsearch(pos, ss+1, -probcutBeta, -probcutBeta+1); // If the qsearch held, perform the regular search - if (value >= raisedBeta) - value = -search(pos, ss+1, -raisedBeta, -raisedBeta+1, depth - 4, !cutNode); + if (value >= probcutBeta) + value = -search(pos, ss+1, -probcutBeta, -probcutBeta+1, depth - 4, !cutNode); pos.undo_move(move); - if (value >= raisedBeta) + if (value >= probcutBeta) + { + if ( !(ttHit + && tte->depth() >= depth - 3 + && ttValue != VALUE_NONE)) + tte->save(posKey, value_to_tt(value, ss->ply), ttPv, + BOUND_LOWER, + depth - 3, move, ss->staticEval); return value; + } } } - // Step 11. Internal iterative deepening (~2 Elo) + // Step 11. Internal iterative deepening (~1 Elo) if (depth >= 7 && !ttMove) { search(pos, ss, alpha, beta, depth - 7, cutNode); tte = TT.probe(posKey, ttHit); - ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; + ttValue = ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE; ttMove = ttHit ? tte->move() : MOVE_NONE; } @@ -911,13 +955,15 @@ moves_loop: // When in check, search starts from here Move countermove = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq]; MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, - &thisThread->captureHistory, + &thisThread->lowPlyHistory, + &captureHistory, contHist, countermove, - ss->killers); + ss->killers, + ss->ply); value = bestValue; - singularLMR = moveCountPruning = false; + singularQuietLMR = moveCountPruning = false; ttCapture = ttMove && pos.capture_or_promotion(ttMove); // Mark this node as being searched @@ -954,13 +1000,74 @@ moves_loop: // When in check, search starts from here movedPiece = pos.moved_piece(move); givesCheck = pos.gives_check(move); - // Step 13. Extensions (~70 Elo) + // Calculate new depth for this move + newDepth = depth - 1; + + // Step 13. Pruning at shallow depth (~200 Elo) + if ( !rootNode + && pos.non_pawn_material(us) + && bestValue > VALUE_TB_LOSS_IN_MAX_PLY) + { + // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold + moveCountPruning = moveCount >= futility_move_count(improving, depth); + + // Reduced depth of the next LMR search + int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), 0); - // Singular extension search (~60 Elo). If all moves but one fail low on a + if ( !captureOrPromotion + && !givesCheck) + { + // Countermoves based pruning (~20 Elo) + 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 (~5 Elo) + if ( lmrDepth < 6 + && !ss->inCheck + && ss->staticEval + 284 + 188 * 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)] / 2 < 28388) + continue; + + // Prune moves with negative SEE (~20 Elo) + if (!pos.see_ge(move, Value(-(29 - std::min(lmrDepth, 17)) * lmrDepth * lmrDepth))) + continue; + } + else + { + // Capture history based pruning when the move doesn't give check + if ( !givesCheck + && lmrDepth < 1 + && captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))] < 0) + continue; + + // Futility pruning for captures + if ( !givesCheck + && lmrDepth < 6 + && !(PvNode && abs(bestValue) < 2) + && PieceValue[MG][type_of(movedPiece)] >= PieceValue[MG][type_of(pos.piece_on(to_sq(move)))] + && !ss->inCheck + && ss->staticEval + 267 + 391 * lmrDepth + + PieceValue[MG][type_of(pos.piece_on(to_sq(move)))] <= alpha) + continue; + + // See based pruning + if (!pos.see_ge(move, Value(-202) * depth)) // (~25 Elo) + continue; + } + } + + // Step 14. Extensions (~75 Elo) + + // Singular extension search (~70 Elo). If all moves but one fail low on a // search of (alpha-s, beta-s), and just one fails high on (alpha, beta), // 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. + // result is lower than ttValue minus a margin, then we will extend the ttMove. if ( depth >= 6 && move == ttMove && !rootNode @@ -971,16 +1078,16 @@ moves_loop: // When in check, search starts from here && tte->depth() >= depth - 3 && pos.legal(move)) { - Value singularBeta = ttValue - 2 * depth; - Depth halfDepth = depth / 2; + Value singularBeta = ttValue - ((formerPv + 4) * depth) / 2; + Depth singularDepth = (depth - 1 + 3 * formerPv) / 2; ss->excludedMove = move; - value = search(pos, ss, singularBeta - 1, singularBeta, halfDepth, cutNode); + value = search(pos, ss, singularBeta - 1, singularBeta, singularDepth, cutNode); ss->excludedMove = MOVE_NONE; if (value < singularBeta) { extension = 1; - singularLMR = true; + singularQuietLMR = !ttCapture; } // Multi-cut pruning @@ -988,9 +1095,20 @@ moves_loop: // When in check, search starts from here // search without the ttMove. So we assume this expected Cut-node is not singular, // that multiple moves fail high, and we can prune the whole subtree by returning // a soft bound. - else if ( eval >= beta - && singularBeta >= beta) + 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. + 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; + } } // Check extension (~2 Elo) @@ -998,65 +1116,23 @@ moves_loop: // When in check, search starts from here && (pos.is_discovery_check_on_king(~us, move) || pos.see_ge(move))) extension = 1; - // Shuffle extension - else if ( PvNode - && pos.rule50_count() > 18 - && depth < 3 - && ++thisThread->shuffleExts < thisThread->nodes.load(std::memory_order_relaxed) / 4) // To avoid too many extensions - extension = 1; - // Passed pawn extension else if ( move == ss->killers[0] && pos.advanced_pawn_push(move) && pos.pawn_passed(us, to_sq(move))) extension = 1; + // Last captures extension + else if ( PieceValue[EG][pos.captured_piece()] > PawnValueEg + && pos.non_pawn_material() <= 2 * RookValueMg) + extension = 1; + // Castling extension if (type_of(move) == CASTLING) extension = 1; - // Calculate new depth for this move - newDepth = depth - 1 + extension; - - // Step 14. Pruning at shallow depth (~170 Elo) - if ( !rootNode - && 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); - - if ( !captureOrPromotion - && !givesCheck - && (!pos.advanced_pawn_push(move) || pos.non_pawn_material(~us) > BishopValueMg)) - { - // Move count based pruning - if (moveCountPruning) - continue; - - // Reduced depth of the next LMR search - int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), 0); - - // Countermoves based pruning (~20 Elo) - 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 < 6 - && !inCheck - && ss->staticEval + 250 + 211 * lmrDepth <= alpha) - continue; - - // Prune moves with negative SEE (~10 Elo) - if (!pos.see_ge(move, Value(-(31 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth))) - continue; - } - else if ( !(givesCheck && extension) - && !pos.see_ge(move, Value(-199) * depth)) // (~20 Elo) - continue; - } + // Add extension to new depth + newDepth += extension; // Speculative prefetch as early as possible prefetch(TT.first_entry(pos.key_after(move))); @@ -1070,7 +1146,7 @@ moves_loop: // When in check, search starts from here // Update the current move (this must be done after singular extension search) ss->currentMove = move; - ss->continuationHistory = &thisThread->continuationHistory[inCheck] + ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck] [captureOrPromotion] [movedPiece] [to_sq(move)]; @@ -1078,7 +1154,7 @@ moves_loop: // When in check, search starts from here // Step 15. Make the move pos.do_move(move, st, givesCheck); - // Step 16. Reduced depth search (LMR). If the move fails high it will be + // Step 16. Reduced depth search (LMR, ~200 Elo). If the move fails high it will be // re-searched at full depth. if ( depth >= 3 && moveCount > 1 + 2 * rootNode @@ -1086,82 +1162,107 @@ moves_loop: // When in check, search starts from here && ( !captureOrPromotion || moveCountPruning || ss->staticEval + PieceValue[EG][pos.captured_piece()] <= alpha - || cutNode)) + || cutNode + || thisThread->ttHitAverage < 415 * TtHitAverageResolution * TtHitAverageWindow / 1024)) { Depth r = reduction(improving, depth, moveCount); - // Reduction if other threads are searching this position. + // Decrease reduction at non-check cut nodes for second move at low depths + if ( cutNode + && depth <= 10 + && moveCount <= 2 + && !ss->inCheck) + r--; + + // Decrease reduction if the ttHit running average is large + if (thisThread->ttHitAverage > 473 * TtHitAverageResolution * TtHitAverageWindow / 1024) + r--; + + // Reduction if other threads are searching this position if (th.marked()) r++; - // Decrease reduction if position is or has been on the PV + // Decrease reduction if position is or has been on the PV (~10 Elo) if (ttPv) r -= 2; - // Decrease reduction if opponent's move count is high (~10 Elo) - if ((ss-1)->moveCount > 15) + if (moveCountPruning && !formerPv) + r++; + + // Decrease reduction if opponent's move count is high (~5 Elo) + if ((ss-1)->moveCount > 13) r--; - // Decrease reduction if ttMove has been singularly extended - if (singularLMR) - r -= 2; + // Decrease reduction if ttMove has been singularly extended (~3 Elo) + if (singularQuietLMR) + r -= 1 + formerPv; if (!captureOrPromotion) { - // Increase reduction if ttMove is a capture (~0 Elo) + // Increase reduction if ttMove is a capture (~5 Elo) if (ttCapture) r++; - // Increase reduction for cut nodes (~5 Elo) + // Increase reduction for cut nodes (~10 Elo) if (cutNode) r += 2; // Decrease reduction for moves that escape a capture. Filter out // castling moves, because they are coded as "king captures rook" and - // hence break make_move(). (~5 Elo) + // hence break make_move(). (~2 Elo) else if ( type_of(move) == NORMAL && !pos.see_ge(reverse_move(move))) - r -= 2; + r -= 2 + ttPv - (type_of(movedPiece) == PAWN); 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)] - - 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; + - 4826; // Decrease/increase reduction by comparing opponent's stat score (~10 Elo) - if (ss->statScore >= -99 && (ss-1)->statScore < -116) + if (ss->statScore >= -100 && (ss-1)->statScore < -112) r--; - else if ((ss-1)->statScore >= -117 && ss->statScore < -144) + else if ((ss-1)->statScore >= -125 && ss->statScore < -138) r++; // Decrease/increase reduction for moves with a good/bad history (~30 Elo) - r -= ss->statScore / 16384; + r -= ss->statScore / 14615; + } + else + { + // Increase reduction for captures/promotions if late move and at low depth + if (depth < 8 && moveCount > 2) + r++; + + // Unless giving check, this capture is likely bad + if ( !givesCheck + && ss->staticEval + PieceValue[EG][pos.captured_piece()] + 211 * depth <= alpha) + r++; } - Depth d = clamp(newDepth - r, 1, newDepth); + Depth d = Utility::clamp(newDepth - r, 1, newDepth); value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - doFullDepthSearch = (value > alpha && d != newDepth), doLMR = true; + doFullDepthSearch = value > alpha && d != newDepth; + + didLMR = true; } else - doFullDepthSearch = !PvNode || moveCount > 1, doLMR = false; + { + doFullDepthSearch = !PvNode || moveCount > 1; + + didLMR = 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) + if (didLMR && !captureOrPromotion) { int bonus = value > alpha ? stat_bonus(newDepth) : -stat_bonus(newDepth); @@ -1214,7 +1315,7 @@ moves_loop: // When in check, search starts from here 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: When + // iteration. This information is used for time management: when // the best move changes frequently, we allocate some more time. if (moveCount > 1) ++thisThread->bestMoveChanges; @@ -1271,26 +1372,16 @@ moves_loop: // When in check, search starts from here // must be a mate or a stalemate. If we are in a singular extension search then // return a fail low score. - assert(moveCount || !inCheck || excludedMove || !MoveList(pos).size()); + assert(moveCount || !ss->inCheck || excludedMove || !MoveList(pos).size()); if (!moveCount) bestValue = excludedMove ? alpha - : inCheck ? mated_in(ss->ply) : VALUE_DRAW; - else if (bestMove) - { - // Quiet best move: update move sorting heuristics - if (!pos.capture_or_promotion(bestMove)) - update_quiet_stats(pos, ss, bestMove, quietsSearched, quietCount, - stat_bonus(depth + (bestValue > beta + PawnValueMg))); + : ss->inCheck ? mated_in(ss->ply) : VALUE_DRAW; - update_capture_stats(pos, bestMove, capturesSearched, captureCount, stat_bonus(depth + 1)); - - // 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])) - && !priorCapture) - update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + 1)); + else if (bestMove) + update_all_stats(pos, ss, bestMove, bestValue, beta, prevSq, + quietsSearched, quietCount, capturesSearched, captureCount, depth); - } // Bonus for prior countermove that caused the fail low else if ( (depth >= 3 || PvNode) && !priorCapture) @@ -1299,7 +1390,7 @@ moves_loop: // When in check, search starts from here if (PvNode) bestValue = std::min(bestValue, maxValue); - if (!excludedMove) + if (!excludedMove && !(rootNode && thisThread->pvIdx)) tte->save(posKey, value_to_tt(bestValue, ss->ply), ttPv, bestValue >= beta ? BOUND_LOWER : PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, @@ -1329,7 +1420,7 @@ moves_loop: // When in check, search starts from here Move ttMove, move, bestMove; Depth ttDepth; Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; - bool ttHit, pvHit, inCheck, givesCheck, captureOrPromotion, evasionPrunable; + bool ttHit, pvHit, givesCheck, captureOrPromotion; int moveCount; if (PvNode) @@ -1342,25 +1433,25 @@ moves_loop: // When in check, search starts from here Thread* thisThread = pos.this_thread(); (ss+1)->ply = ss->ply + 1; bestMove = MOVE_NONE; - inCheck = pos.checkers(); + ss->inCheck = pos.checkers(); moveCount = 0; // Check for an immediate draw or maximum ply reached if ( pos.is_draw(ss->ply) || ss->ply >= MAX_PLY) - return (ss->ply >= MAX_PLY && !inCheck) ? evaluate(pos) : VALUE_DRAW; + return (ss->ply >= MAX_PLY && !ss->inCheck) ? evaluate(pos) : VALUE_DRAW; assert(0 <= ss->ply && ss->ply < MAX_PLY); // Decide whether or not to include checks: this fixes also the type of // TT entry depth that we are going to use. Note that in qsearch we use // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS. - ttDepth = inCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS + ttDepth = ss->inCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS; // Transposition table lookup posKey = pos.key(); tte = TT.probe(posKey, ttHit); - ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; + ttValue = ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE; ttMove = ttHit ? tte->move() : MOVE_NONE; pvHit = ttHit && tte->is_pv(); @@ -1373,7 +1464,7 @@ moves_loop: // When in check, search starts from here return ttValue; // Evaluate the position statically - if (inCheck) + if (ss->inCheck) { ss->staticEval = VALUE_NONE; bestValue = futilityBase = -VALUE_INFINITE; @@ -1394,13 +1485,13 @@ moves_loop: // When in check, search starts from here else ss->staticEval = bestValue = (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) - : -(ss-1)->staticEval + 2 * Eval::Tempo; + : -(ss-1)->staticEval + 2 * Tempo; // Stand pat. Return immediately if static value is at least beta if (bestValue >= beta) { if (!ttHit) - tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit, BOUND_LOWER, + tte->save(posKey, value_to_tt(bestValue, ss->ply), false, BOUND_LOWER, DEPTH_NONE, MOVE_NONE, ss->staticEval); return bestValue; @@ -1409,7 +1500,7 @@ moves_loop: // When in check, search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + 153; + futilityBase = bestValue + 141; } const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, @@ -1418,8 +1509,8 @@ 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 promotions and checks (only if depth >= DEPTH_QS_CHECKS) will - // be generated. + // queen and checking knight promotions, and other checks(only if depth >= DEPTH_QS_CHECKS) + // will be generated. MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &thisThread->captureHistory, contHist, @@ -1436,7 +1527,7 @@ moves_loop: // When in check, search starts from here moveCount++; // Futility pruning - if ( !inCheck + if ( !ss->inCheck && !givesCheck && futilityBase > -VALUE_KNOWN_WIN && !pos.advanced_pawn_push(move)) @@ -1458,16 +1549,8 @@ moves_loop: // When in check, search starts from here } } - // Detect non-capture evasions that are candidates to be pruned - evasionPrunable = inCheck - && (depth != 0 || moveCount > 2) - && bestValue > VALUE_MATED_IN_MAX_PLY - && !pos.capture(move); - - // 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)) + // Do not search moves with negative SEE values + if ( !ss->inCheck && !pos.see_ge(move)) continue; // Speculative prefetch as early as possible @@ -1481,7 +1564,7 @@ moves_loop: // When in check, search starts from here } ss->currentMove = move; - ss->continuationHistory = &thisThread->continuationHistory[inCheck] + ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck] [captureOrPromotion] [pos.moved_piece(move)] [to_sq(move)]; @@ -1513,9 +1596,9 @@ moves_loop: // When in check, search starts from here } } - // All legal moves have been searched. A special case: If we're in check + // All legal moves have been searched. A special case: if we're in check // and no legal moves were found, it is checkmate. - if (inCheck && bestValue == -VALUE_INFINITE) + if (ss->inCheck && bestValue == -VALUE_INFINITE) return mated_in(ss->ply); // Plies to mate from the root tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit, @@ -1529,28 +1612,47 @@ moves_loop: // When in check, search starts from here } - // value_to_tt() adjusts a mate score from "plies to mate from the root" to - // "plies to mate from the current position". Non-mate scores are unchanged. + // value_to_tt() adjusts a mate or TB score from "plies to mate from the root" to + // "plies to mate from the current position". Standard scores are unchanged. // The function is called before storing a value in the transposition table. Value value_to_tt(Value v, int ply) { assert(v != VALUE_NONE); - return v >= VALUE_MATE_IN_MAX_PLY ? v + ply - : v <= VALUE_MATED_IN_MAX_PLY ? v - ply : v; + return v >= VALUE_TB_WIN_IN_MAX_PLY ? v + ply + : v <= VALUE_TB_LOSS_IN_MAX_PLY ? v - ply : v; } - // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score - // from the transposition table (which refers to the plies to mate/be mated - // from current position) to "plies to mate/be mated from the root". + // value_from_tt() is the inverse of value_to_tt(): it adjusts a mate or TB score + // from the transposition table (which refers to the plies to mate/be mated from + // current position) to "plies to mate/be mated (TB win/loss) from the root". However, + // for mate scores, to avoid potentially false mate scores related to the 50 moves rule + // and the graph history interaction, we return an optimal TB score instead. + + Value value_from_tt(Value v, int ply, int r50c) { - Value value_from_tt(Value v, int ply) { + if (v == VALUE_NONE) + return VALUE_NONE; - return v == VALUE_NONE ? VALUE_NONE - : v >= VALUE_MATE_IN_MAX_PLY ? v - ply - : v <= VALUE_MATED_IN_MAX_PLY ? v + ply : v; + if (v >= VALUE_TB_WIN_IN_MAX_PLY) // TB win or better + { + if (v >= VALUE_MATE_IN_MAX_PLY && VALUE_MATE - v > 99 - r50c) + return VALUE_MATE_IN_MAX_PLY - 1; // do not return a potentially false mate score + + return v - ply; + } + + if (v <= VALUE_TB_LOSS_IN_MAX_PLY) // TB loss or worse + { + if (v <= VALUE_MATED_IN_MAX_PLY && VALUE_MATE + v > 99 - r50c) + return VALUE_MATED_IN_MAX_PLY + 1; // do not return a potentially false mate score + + return v + ply; + } + + return v; } @@ -1564,43 +1666,69 @@ moves_loop: // When in check, search starts from here } - // update_continuation_histories() updates histories of the move pairs formed - // by moves at ply -1, -2, and -4 with current move. + // update_all_stats() updates stats at the end of search() when a bestMove is found - void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus) { + void update_all_stats(const Position& pos, Stack* ss, Move bestMove, Value bestValue, Value beta, Square prevSq, + Move* quietsSearched, int quietCount, Move* capturesSearched, int captureCount, Depth depth) { - for (int i : {1, 2, 4, 6}) - if (is_ok((ss-i)->currentMove)) - (*(ss-i)->continuationHistory)[pc][to] << bonus; - } + int bonus1, bonus2; + Color us = pos.side_to_move(); + Thread* thisThread = pos.this_thread(); + CapturePieceToHistory& captureHistory = thisThread->captureHistory; + Piece moved_piece = pos.moved_piece(bestMove); + PieceType captured = type_of(pos.piece_on(to_sq(bestMove))); + + bonus1 = stat_bonus(depth + 1); + bonus2 = bestValue > beta + PawnValueMg ? bonus1 // larger bonus + : stat_bonus(depth); // smaller bonus + + if (!pos.capture_or_promotion(bestMove)) + { + update_quiet_stats(pos, ss, bestMove, bonus2, depth); + + // Decrease all the non-best quiet moves + for (int i = 0; i < quietCount; ++i) + { + thisThread->mainHistory[us][from_to(quietsSearched[i])] << -bonus2; + update_continuation_histories(ss, pos.moved_piece(quietsSearched[i]), to_sq(quietsSearched[i]), -bonus2); + } + } + else + captureHistory[moved_piece][to_sq(bestMove)][captured] << bonus1; + // 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, -bonus1); - // update_capture_stats() updates move sorting heuristics when a new capture best move is found + // Decrease all the non-best capture moves + for (int i = 0; i < captureCount; ++i) + { + moved_piece = pos.moved_piece(capturesSearched[i]); + captured = type_of(pos.piece_on(to_sq(capturesSearched[i]))); + captureHistory[moved_piece][to_sq(capturesSearched[i])][captured] << -bonus1; + } + } - void update_capture_stats(const Position& pos, Move move, - Move* captures, int captureCount, int bonus) { - CapturePieceToHistory& captureHistory = pos.this_thread()->captureHistory; - Piece moved_piece = pos.moved_piece(move); - PieceType captured = type_of(pos.piece_on(to_sq(move))); + // update_continuation_histories() updates histories of the move pairs formed + // by moves at ply -1, -2, -4, and -6 with current move. - if (pos.capture_or_promotion(move)) - captureHistory[moved_piece][to_sq(move)][captured] << bonus; + void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus) { - // Decrease all the other played capture moves - for (int i = 0; i < captureCount; ++i) - { - moved_piece = pos.moved_piece(captures[i]); - captured = type_of(pos.piece_on(to_sq(captures[i]))); - captureHistory[moved_piece][to_sq(captures[i])][captured] << -bonus; - } + for (int i : {1, 2, 4, 6}) + { + if (ss->inCheck && i > 2) + break; + if (is_ok((ss-i)->currentMove)) + (*(ss-i)->continuationHistory)[pc][to] << bonus; + } } - // update_quiet_stats() updates move sorting heuristics when a new quiet best move is found + // update_quiet_stats() updates move sorting heuristics - void update_quiet_stats(const Position& pos, Stack* ss, Move move, - Move* quiets, int quietCount, int bonus) { + void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus, int depth) { if (ss->killers[0] != move) { @@ -1622,12 +1750,8 @@ moves_loop: // When in check, search starts from here thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] = move; } - // Decrease all the other played quiet moves - for (int i = 0; i < quietCount; ++i) - { - thisThread->mainHistory[us][from_to(quiets[i])] << -bonus; - update_continuation_histories(ss, pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus); - } + if (depth > 11 && ss->ply < MAX_LPH) + thisThread->lowPlyHistory[ss->ply][from_to(move)] << stat_bonus(depth - 6); } // When playing with strength handicap, choose best move among a set of RootMoves @@ -1665,6 +1789,7 @@ moves_loop: // When in check, search starts from here } // namespace + /// MainThread::check_time() is used to print debug info and, more importantly, /// to detect when we are out of available time and thus stop the search. @@ -1713,7 +1838,7 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { for (size_t i = 0; i < multiPV; ++i) { - bool updated = (i <= pvIdx && rootMoves[i].score != -VALUE_INFINITE); + bool updated = rootMoves[i].score != -VALUE_INFINITE; if (depth == 1 && !updated) continue; @@ -1721,7 +1846,7 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { Depth d = updated ? depth : depth - 1; Value v = updated ? rootMoves[i].score : rootMoves[i].previousScore; - bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY; + bool tb = TB::RootInTB && abs(v) < VALUE_MATE_IN_MAX_PLY; v = tb ? rootMoves[i].tbScore : v; if (ss.rdbuf()->in_avail()) // Not at first line @@ -1733,6 +1858,9 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { << " multipv " << i + 1 << " score " << UCI::value(v); + if (Options["UCI_ShowWDL"]) + ss << UCI::wdl(v, pos.game_ply()); + if (!tb && i == pvIdx) ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : "");