X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=e75db243cfcb2cb01d760c885536b29bc5a5992c;hp=6e59bb541780b37913aadc84b864b69588dd56b0;hb=a00a336946fa9e6dcfa39f8b656413d2de032a89;hpb=472de897cb7efb66cb3518f3f4924716bd8abaee diff --git a/src/search.cpp b/src/search.cpp index 6e59bb54..e75db243 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -75,8 +75,8 @@ namespace { return (r + 520) / 1024 + (!i && r > 999); } - 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 (5 + depth * depth) * (1 + improving) / 2 - 1; } // History and stats update bonus, based on depth @@ -150,11 +150,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); + 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. @@ -417,7 +418,7 @@ void Thread::search() { beta = std::min(previousScore + delta, VALUE_INFINITE); // Adjust contempt based on root move's previousScore (dynamic contempt) - int dct = ct + 86 * previousScore / (abs(previousScore) + 176); + int dct = ct + (111 - ct / 2) * previousScore / (abs(previousScore) + 176); contempt = (us == WHITE ? make_score(dct, dct / 2) : -make_score(dct, dct / 2)); @@ -594,17 +595,17 @@ namespace { 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; + bool ttHit, ttPv, inCheck, givesCheck, improving, didLMR, priorCapture; + bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture, singularLMR; Piece movedPiece; - int moveCount, captureCount, quietCount, singularLMR; + int moveCount, captureCount, quietCount; // Step 1. Initialize node Thread* thisThread = pos.this_thread(); inCheck = pos.checkers(); priorCapture = pos.captured_piece(); Color us = pos.side_to_move(); - moveCount = captureCount = quietCount = singularLMR = ss->moveCount = 0; + moveCount = captureCount = quietCount = ss->moveCount = 0; bestValue = -VALUE_INFINITE; maxValue = VALUE_INFINITE; @@ -660,7 +661,7 @@ namespace { excludedMove = ss->excludedMove; posKey = pos.key() ^ Key(excludedMove << 16); // Isn't a very good hash 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()); @@ -679,7 +680,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)); // Extra penalty for early quiet moves of the previous ply if ((ss-1)->moveCount <= 2 && !priorCapture) @@ -898,7 +899,7 @@ namespace { 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; } @@ -917,7 +918,7 @@ moves_loop: // When in check, search starts from here ss->killers); value = bestValue; - moveCountPruning = false; + singularLMR = moveCountPruning = false; ttCapture = ttMove && pos.capture_or_promotion(ttMove); // Mark this node as being searched @@ -954,7 +955,45 @@ 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 (~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 + && (!PvNode || !pos.advanced_pawn_push(move) || pos.non_pawn_material(~us) > BishopValueMg)) + { + // 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 (!pos.see_ge(move, Value(-199) * depth)) // (~20 Elo) + continue; + } + + // Step 14. Extensions (~70 Elo) // Singular extension search (~60 Elo). If all moves but one fail low on a // search of (alpha-s, beta-s), and just one fails high on (alpha, beta), @@ -980,10 +1019,7 @@ moves_loop: // When in check, search starts from here if (value < singularBeta) { extension = 1; - singularLMR++; - - if (value < singularBeta - std::min(4 * depth, 36)) - singularLMR++; + singularLMR = true; } // Multi-cut pruning @@ -1001,13 +1037,6 @@ 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) @@ -1018,48 +1047,8 @@ moves_loop: // When in check, search starts from here 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))); @@ -1106,7 +1095,8 @@ moves_loop: // When in check, search starts from here r--; // Decrease reduction if ttMove has been singularly extended - r -= singularLMR; + if (singularLMR) + r -= 2; if (!captureOrPromotion) { @@ -1153,17 +1143,17 @@ moves_loop: // When in check, search starts from here 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); @@ -1278,21 +1268,11 @@ moves_loop: // When in check, search starts from here 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))); - - 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) @@ -1362,7 +1342,7 @@ moves_loop: // When in check, search starts from here // 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(); @@ -1468,7 +1448,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))) + && !(givesCheck && pos.is_discovery_check_on_king(~pos.side_to_move(), move)) && !pos.see_ge(move)) continue; @@ -1548,11 +1528,11 @@ moves_loop: // When in check, search starts from here // 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 value_from_tt(Value v, int ply) { + Value value_from_tt(Value v, int ply, int r50c) { return v == VALUE_NONE ? VALUE_NONE - : v >= VALUE_MATE_IN_MAX_PLY ? v - ply - : v <= VALUE_MATED_IN_MAX_PLY ? v + ply : v; + : v >= VALUE_MATE_IN_MAX_PLY ? VALUE_MATE - v > 99 - r50c ? VALUE_MATE_IN_MAX_PLY : v - ply + : v <= VALUE_MATED_IN_MAX_PLY ? VALUE_MATE + v > 99 - r50c ? VALUE_MATED_IN_MAX_PLY : v + ply : v; } @@ -1566,43 +1546,65 @@ 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 - // update_capture_stats() updates move sorting heuristics when a new capture best move is found + if (!pos.capture_or_promotion(bestMove)) + { + update_quiet_stats(pos, ss, bestMove, bonus2); - void update_capture_stats(const Position& pos, Move move, - Move* captures, int captureCount, int bonus) { + // 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; - CapturePieceToHistory& captureHistory = pos.this_thread()->captureHistory; - Piece moved_piece = pos.moved_piece(move); - PieceType captured = type_of(pos.piece_on(to_sq(move))); + // 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); - if (pos.capture_or_promotion(move)) - captureHistory[moved_piece][to_sq(move)][captured] << bonus; + // 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; + } + } - // 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; - } + + // update_continuation_histories() updates histories of the move pairs formed + // by moves at ply -1, -2, and -4 with current move. + + void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus) { + + for (int i : {1, 2, 4, 6}) + 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) { if (ss->killers[0] != move) { @@ -1623,13 +1625,6 @@ moves_loop: // When in check, search starts from here Square prevSq = to_sq((ss-1)->currentMove); 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); - } } // When playing with strength handicap, choose best move among a set of RootMoves