X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=ef47fd22307ee9cdb31bbbbb5956d0f2869470a3;hp=5ad650d2dabf25e7c809c1d967e97fa6f37fbf14;hb=a72cec1ff854a77a92452c2afe2001e05f06e6d4;hpb=42b7dbcb5e20ae9015122601522be8b455787a4a diff --git a/src/search.cpp b/src/search.cpp index 5ad650d2..ef47fd22 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -1,8 +1,6 @@ /* 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-2020 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad + Copyright (C) 2004-2020 The Stockfish developers (see AUTHORS file) Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -65,9 +63,9 @@ namespace { constexpr uint64_t TtHitAverageResolution = 1024; // Razor and futility margins - constexpr int RazorMargin = 516; + constexpr int RazorMargin = 510; Value futility_margin(Depth d, bool improving) { - return Value(224 * (d - improving)); + return Value(223 * (d - improving)); } // Reductions lookup table, initialized at startup @@ -75,7 +73,7 @@ namespace { Depth reduction(bool i, Depth d, int mn) { int r = Reductions[d] * Reductions[mn]; - return (r + 529) / 1024 + (!i && r > 1050); + return (r + 509) / 1024 + (!i && r > 894); } constexpr int futility_move_count(bool improving, Depth depth) { @@ -84,7 +82,7 @@ namespace { // History and stats update bonus, based on depth int stat_bonus(Depth d) { - return d > 15 ? 28 : 19 * d * d + 135 * d - 136; + return d > 13 ? 29 : 17 * d * d + 134 * d - 134; } // Add a small random component to draw evaluations to avoid 3fold-blindness @@ -194,7 +192,7 @@ namespace { void Search::init() { for (int i = 1; i < MAX_MOVES; ++i) - Reductions[i] = int((24.9 + std::log(Threads.size())) * std::log(i)); + Reductions[i] = int((22.0 + std::log(Threads.size())) * std::log(i)); } @@ -227,6 +225,8 @@ void MainThread::search() { Time.init(Limits, us, rootPos.game_ply()); TT.new_search(); + Eval::verify_NNUE(); + if (rootMoves.empty()) { rootMoves.emplace_back(MOVE_NONE); @@ -263,10 +263,10 @@ void MainThread::search() { Thread* bestThread = this; - if (int(Options["MultiPV"]) == 1 && - !Limits.depth && - !(Skill(Options["Skill Level"]).enabled() || int(Options["UCI_LimitStrength"])) && - rootMoves[0].pv[0] != MOVE_NONE) + if ( int(Options["MultiPV"]) == 1 + && !Limits.depth + && !(Skill(Options["Skill Level"]).enabled() || int(Options["UCI_LimitStrength"])) + && rootMoves[0].pv[0] != MOVE_NONE) bestThread = Threads.get_best_thread(); bestPreviousScore = bestThread->rootMoves[0].score; @@ -403,12 +403,12 @@ void Thread::search() { if (rootDepth >= 4) { Value prev = rootMoves[pvIdx].previousScore; - delta = Value(21); + delta = Value(17); 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 + (104 - ct / 2) * prev / (abs(prev) + 143); + int dct = ct + (105 - ct / 2) * prev / (abs(prev) + 149); contempt = (us == WHITE ? make_score(dct, dct / 2) : -make_score(dct, dct / 2)); @@ -506,13 +506,13 @@ void Thread::search() { && !Threads.stop && !mainThread->stopOnPonderhit) { - double fallingEval = (293 + 6 * (mainThread->bestPreviousScore - bestValue) - + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 742.0; + double fallingEval = (318 + 6 * (mainThread->bestPreviousScore - bestValue) + + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 825.0; fallingEval = Utility::clamp(fallingEval, 0.5, 1.5); // If the bestMove is stable over several iterations, reduce time accordingly - timeReduction = lastBestMoveDepth + 10 < completedDepth ? 1.93 : 0.96; - double reduction = (1.36 + mainThread->previousTimeReduction) / (2.21 * timeReduction); + timeReduction = lastBestMoveDepth + 9 < completedDepth ? 1.92 : 0.95; + double reduction = (1.47 + mainThread->previousTimeReduction) / (2.32 * timeReduction); // Use part of the gained time from a previous stable move for the current move for (Thread* th : Threads) @@ -525,7 +525,7 @@ void Thread::search() { double totalTime = rootMoves.size() == 1 ? 0 : Time.optimum() * fallingEval * reduction * bestMoveInstability; - // Stop the search if we have exceeded the totalTime, at least 1ms search. + // 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 @@ -537,7 +537,7 @@ void Thread::search() { } else if ( Threads.increaseDepth && !mainThread->ponder - && Time.elapsed() > totalTime * 0.57) + && Time.elapsed() > totalTime * 0.58) Threads.increaseDepth = false; else Threads.increaseDepth = true; @@ -596,7 +596,7 @@ namespace { Key posKey; Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; - Value bestValue, value, ttValue, eval, maxValue; + Value bestValue, value, ttValue, eval, maxValue, probCutBeta; bool ttHit, ttPv, formerPv, givesCheck, improving, didLMR, priorCapture; bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture, singularQuietLMR; @@ -627,7 +627,7 @@ namespace { || pos.is_draw(ss->ply) || ss->ply >= MAX_PLY) return (ss->ply >= MAX_PLY && !ss->inCheck) ? evaluate(pos) - : value_draw(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 @@ -662,7 +662,7 @@ 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, pos.rule50_count()) : VALUE_NONE; ttMove = rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0] @@ -670,7 +670,11 @@ namespace { ttPv = PvNode || (ttHit && tte->is_pv()); formerPv = ttPv && !PvNode; - if (ttPv && depth > 12 && ss->ply - 1 < MAX_LPH && !pos.captured_piece() && is_ok((ss-1)->currentMove)) + 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 @@ -767,9 +771,10 @@ namespace { // Step 6. Static evaluation of the position 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) { @@ -811,7 +816,7 @@ namespace { // Step 8. Futility pruning: child node (~50 Elo) if ( !PvNode - && depth < 6 + && depth < 8 && eval - futility_margin(depth, improving) >= beta && eval < VALUE_KNOWN_WIN) // Do not return unproven wins return eval; @@ -819,10 +824,10 @@ namespace { // Step 9. Null move search with verification search (~40 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 24714 + && (ss-1)->statScore < 22977 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 29 * depth - 31 * improving + 119 * ttPv + 299 + && ss->staticEval >= beta - 30 * depth - 28 * improving + 84 * ttPv + 182 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -830,7 +835,7 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = (793 + 70 * depth) / 252 + std::min(int(eval - beta) / 192, 3); + Depth R = (817 + 71 * depth) / 213 + std::min(int(eval - beta) / 192, 3); ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0]; @@ -866,23 +871,39 @@ 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_TB_WIN_IN_MAX_PLY) + && depth > 4 + && abs(beta) < VALUE_TB_WIN_IN_MAX_PLY + // if value from transposition table is lower than probCutBeta, don't attempt probCut + // there and in further interactions with transposition table cutoff depth is set to depth - 3 + // because probCut search has depth set to depth - 4 but we also do a move before it + // so effective depth is equal to depth - 3 + && !( ttHit + && tte->depth() >= depth - 3 + && ttValue != VALUE_NONE + && ttValue < probCutBeta)) { - Value raisedBeta = beta + 182 - 48 * improving; - assert(raisedBeta < VALUE_INFINITE); - MovePicker mp(pos, ttMove, raisedBeta - ss->staticEval, &captureHistory); + // if ttMove is a capture and value from transposition table is good enough produce probCut + // cutoff without digging into actual probCut search + 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 - && probCutCount < 2 + 2 * cutNode - && !( move == ttMove - && tte->depth() >= depth - 4 - && ttValue < raisedBeta)) + && probCutCount < 2 + 2 * cutNode) if (move != excludedMove && pos.legal(move)) { assert(pos.capture_or_promotion(move)); @@ -900,16 +921,25 @@ 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 - 5, !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 transposition table doesn't have equal or more deep info write probCut data into it + 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; + } } } @@ -963,6 +993,10 @@ moves_loop: // When in check, search starts from here thisThread->rootMoves.begin() + thisThread->pvLast, move)) continue; + // Check for legality + if (!rootNode && !pos.legal(move)) + continue; + ss->moveCount = ++moveCount; if (rootNode && thisThread == Threads.main() && Time.elapsed() > 3000) @@ -1001,17 +1035,17 @@ moves_loop: // When in check, search starts from here continue; // Futility pruning: parent node (~5 Elo) - if ( lmrDepth < 6 + if ( lmrDepth < 7 && !ss->inCheck - && ss->staticEval + 252 + 176 * lmrDepth <= alpha + && ss->staticEval + 283 + 170 * 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 < 30251) + + (*contHist[5])[movedPiece][to_sq(move)] / 2 < 27376) continue; // Prune moves with negative SEE (~20 Elo) - if (!pos.see_ge(move, Value(-(31 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth))) + if (!pos.see_ge(move, Value(-(29 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth))) continue; } else @@ -1026,12 +1060,14 @@ moves_loop: // When in check, search starts from here 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 + 264 + 397 * lmrDepth + PieceValue[MG][type_of(pos.piece_on(to_sq(move)))] <= alpha) + && ss->staticEval + 169 + 244 * lmrDepth + + PieceValue[MG][type_of(pos.piece_on(to_sq(move)))] <= alpha) continue; // See based pruning - if (!pos.see_ge(move, Value(-192) * depth)) // (~25 Elo) + if (!pos.see_ge(move, Value(-221) * depth)) // (~25 Elo) continue; } } @@ -1042,16 +1078,15 @@ moves_loop: // When in check, search starts from here // 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. - if ( depth >= 6 + // result is lower than ttValue minus a margin, then we will extend the ttMove. + if ( depth >= 7 && move == ttMove && !rootNode && !excludedMove // Avoid recursive singular search /* && ttValue != VALUE_NONE Already implicit in the next condition */ && abs(ttValue) < VALUE_KNOWN_WIN && (tte->bound() & BOUND_LOWER) - && tte->depth() >= depth - 3 - && pos.legal(move)) + && tte->depth() >= depth - 3) { Value singularBeta = ttValue - ((formerPv + 4) * depth) / 2; Depth singularDepth = (depth - 1 + 3 * formerPv) / 2; @@ -1073,8 +1108,8 @@ moves_loop: // When in check, search starts from here else if (singularBeta >= beta) return singularBeta; - // If the eval of ttMove is greater than beta we try also if there is an other move that - // pushes it over beta, if so also produce a cutoff + // 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; @@ -1103,7 +1138,8 @@ moves_loop: // When in check, search starts from here extension = 1; // Castling extension - if (type_of(move) == CASTLING) + if ( type_of(move) == CASTLING + && popcount(pos.pieces(us) & ~pos.pieces(PAWN) & (to_sq(move) & KingSide ? KingSide : QueenSide)) <= 3) extension = 1; // Late irreversible move extension @@ -1118,13 +1154,6 @@ moves_loop: // When in check, search starts from here // Speculative prefetch as early as possible prefetch(TT.first_entry(pos.key_after(move))); - // Check for legality just before making the move - if (!rootNode && !pos.legal(move)) - { - ss->moveCount = --moveCount; - continue; - } - // Update the current move (this must be done after singular extension search) ss->currentMove = move; ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck] @@ -1138,21 +1167,28 @@ moves_loop: // When in check, search starts from here // 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 + && moveCount > 1 + 2 * rootNode + 2 * (PvNode && abs(bestValue) < 2) && (!rootNode || thisThread->best_move_count(move) == 0) && ( !captureOrPromotion || moveCountPruning || ss->staticEval + PieceValue[EG][pos.captured_piece()] <= alpha || cutNode - || thisThread->ttHitAverage < 399 * TtHitAverageResolution * TtHitAverageWindow / 1024)) + || thisThread->ttHitAverage < 427 * TtHitAverageResolution * TtHitAverageWindow / 1024)) { Depth r = reduction(improving, depth, moveCount); + // 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 > 492 * TtHitAverageResolution * TtHitAverageWindow / 1024) + if (thisThread->ttHitAverage > 509 * TtHitAverageResolution * TtHitAverageWindow / 1024) r--; - // Reduction if other threads are searching this position. + // Reduction if other threads are searching this position if (th.marked()) r++; @@ -1164,7 +1200,7 @@ moves_loop: // When in check, search starts from here r++; // Decrease reduction if opponent's move count is high (~5 Elo) - if ((ss-1)->moveCount > 14) + if ((ss-1)->moveCount > 13) r--; // Decrease reduction if ttMove has been singularly extended (~3 Elo) @@ -1186,23 +1222,23 @@ moves_loop: // When in check, search starts from here // hence break make_move(). (~2 Elo) else if ( type_of(move) == NORMAL && !pos.see_ge(reverse_move(move))) - r -= 2 + ttPv; + 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)] - - 4926; + - 5287; // Decrease/increase reduction by comparing opponent's stat score (~10 Elo) - if (ss->statScore >= -99 && (ss-1)->statScore < -116) + if (ss->statScore >= -106 && (ss-1)->statScore < -104) r--; - else if ((ss-1)->statScore >= -117 && ss->statScore < -150) + else if ((ss-1)->statScore >= -119 && ss->statScore < -140) r++; // Decrease/increase reduction for moves with a good/bad history (~30 Elo) - r -= ss->statScore / 15896; + r -= ss->statScore / 14884; } else { @@ -1212,7 +1248,7 @@ moves_loop: // When in check, search starts from here // Unless giving check, this capture is likely bad if ( !givesCheck - && ss->staticEval + PieceValue[EG][pos.captured_piece()] + 200 * depth <= alpha) + && ss->staticEval + PieceValue[EG][pos.captured_piece()] + 213 * depth <= alpha) r++; } @@ -1289,7 +1325,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; @@ -1474,7 +1510,7 @@ moves_loop: // When in check, search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + 138; + futilityBase = bestValue + 145; } const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, @@ -1483,8 +1519,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, @@ -1523,7 +1559,7 @@ moves_loop: // When in check, search starts from here } } - // Don't search moves with negative SEE values + // Do not search moves with negative SEE values if ( !ss->inCheck && !pos.see_ge(move)) continue; @@ -1570,7 +1606,7 @@ 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 (ss->inCheck && bestValue == -VALUE_INFINITE) return mated_in(ss->ply); // Plies to mate from the root @@ -1587,7 +1623,7 @@ moves_loop: // When in check, search starts from here // 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. + // "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) { @@ -1599,11 +1635,11 @@ moves_loop: // When in check, search starts from here } - // 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, return an optimal TB score instead. + // 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) { @@ -1724,7 +1760,7 @@ moves_loop: // When in check, search starts from here thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] = move; } - if (depth > 12 && ss->ply < MAX_LPH) + if (depth > 11 && ss->ply < MAX_LPH) thisThread->lowPlyHistory[ss->ply][from_to(move)] << stat_bonus(depth - 7); } @@ -1763,6 +1799,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. @@ -1831,6 +1868,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" : "");