X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=1d84102303989cce47a9e3ea2615ec623d8fd159;hb=b748b46714d5f8e0acca0a042ede1fc95e4f5190;hp=80c3e4c245fe5e5be672fb5587d6275e0ddbdcba;hpb=29ed22de8cd347cacb0ba826ee43fa587985a98d;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index 80c3e4c2..1d841023 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -35,6 +35,8 @@ #include "uci.h" #include "syzygy/tbprobe.h" +namespace Stockfish { + namespace Search { LimitsType Limits; @@ -163,7 +165,7 @@ namespace { uint64_t perft(Position& pos, Depth depth) { StateInfo st; - ASSERT_ALIGNED(&st, Eval::NNUE::kCacheLineSize); + ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize); uint64_t cnt, nodes = 0; const bool leaf = (depth == 2); @@ -422,7 +424,7 @@ void Thread::search() { while (true) { Depth adjustedDepth = std::max(1, rootDepth - failedHighCnt - searchAgainCounter); - bestValue = ::search(rootPos, ss, alpha, beta, adjustedDepth, false); + bestValue = Stockfish::search(rootPos, ss, alpha, beta, adjustedDepth, false); // Bring the best move to the front. It is critical that sorting // is done with a stable algorithm because all the values but the @@ -595,7 +597,7 @@ namespace { Move pv[MAX_PLY+1], capturesSearched[32], quietsSearched[64]; StateInfo st; - ASSERT_ALIGNED(&st, Eval::NNUE::kCacheLineSize); + ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize); TTEntry* tte; Key posKey; @@ -610,12 +612,12 @@ namespace { // Step 1. Initialize node Thread* thisThread = pos.this_thread(); - ss->inCheck = pos.checkers(); - priorCapture = pos.captured_piece(); - Color us = pos.side_to_move(); - moveCount = captureCount = quietCount = ss->moveCount = 0; - bestValue = -VALUE_INFINITE; - maxValue = VALUE_INFINITE; + ss->inCheck = pos.checkers(); + priorCapture = pos.captured_piece(); + Color us = pos.side_to_move(); + moveCount = captureCount = quietCount = ss->moveCount = 0; + bestValue = -VALUE_INFINITE; + maxValue = VALUE_INFINITE; // Check for the available remaining time if (thisThread == Threads.main()) @@ -839,7 +841,7 @@ namespace { // Step 8. Null move search with verification search (~40 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 22661 + && (ss-1)->statScore < 24185 && eval >= beta && eval >= ss->staticEval && ss->staticEval >= beta - 24 * depth - 34 * improving + 162 * ss->ttPv + 159 @@ -914,6 +916,7 @@ namespace { return probCutBeta; assert(probCutBeta < VALUE_INFINITE); + MovePicker mp(pos, ttMove, probCutBeta - ss->staticEval, &captureHistory); int probCutCount = 0; bool ttPv = ss->ttPv; @@ -969,6 +972,23 @@ namespace { moves_loop: // When in check, search starts from here + ttCapture = ttMove && pos.capture_or_promotion(ttMove); + + // Step 11. A small Probcut idea, when we are in check + probCutBeta = beta + 400; + if ( ss->inCheck + && !PvNode + && depth >= 4 + && ttCapture + && (tte->bound() & BOUND_LOWER) + && tte->depth() >= depth - 3 + && ttValue >= probCutBeta + && abs(ttValue) <= VALUE_KNOWN_WIN + && abs(beta) <= VALUE_KNOWN_WIN + ) + return probCutBeta; + + const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, nullptr , (ss-4)->continuationHistory, nullptr , (ss-6)->continuationHistory }; @@ -985,12 +1005,11 @@ moves_loop: // When in check, search starts from here value = bestValue; singularQuietLMR = moveCountPruning = false; - ttCapture = ttMove && pos.capture_or_promotion(ttMove); // Mark this node as being searched ThreadHolding th(thisThread, posKey, ss->ply); - // Step 11. Loop through all pseudo-legal moves until no moves remain + // 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) { @@ -1025,10 +1044,18 @@ moves_loop: // When in check, search starts from here movedPiece = pos.moved_piece(move); givesCheck = pos.gives_check(move); + // Indicate PvNodes that will probably fail low if node was searched with non-PV search + // at depth equal or greater to current depth and result of this search was far below alpha + bool likelyFailLow = PvNode + && ttMove + && (tte->bound() & BOUND_UPPER) + && ttValue < alpha + 200 + 100 * depth + && tte->depth() >= depth; + // Calculate new depth for this move newDepth = depth - 1; - // Step 12. Pruning at shallow depth (~200 Elo) + // Step 13. Pruning at shallow depth (~200 Elo) if ( !rootNode && pos.non_pawn_material(us) && bestValue > VALUE_TB_LOSS_IN_MAX_PLY) @@ -1067,7 +1094,7 @@ moves_loop: // When in check, search starts from here && (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] + (*contHist[3])[movedPiece][to_sq(move)] - + (*contHist[5])[movedPiece][to_sq(move)] / 3 < 26237) + + (*contHist[5])[movedPiece][to_sq(move)] / 3 < 28255) continue; // Prune moves with negative SEE (~20 Elo) @@ -1076,7 +1103,7 @@ moves_loop: // When in check, search starts from here } } - // Step 13. Extensions (~75 Elo) + // 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), @@ -1094,6 +1121,7 @@ moves_loop: // When in check, search starts from here { Value singularBeta = ttValue - ((formerPv + 4) * depth) / 2; Depth singularDepth = (depth - 1 + 3 * formerPv) / 2; + ss->excludedMove = move; value = search(pos, ss, singularBeta - 1, singularBeta, singularDepth, cutNode); ss->excludedMove = MOVE_NONE; @@ -1130,11 +1158,6 @@ moves_loop: // When in check, search starts from here && (pos.is_discovered_check_on_king(~us, move) || pos.see_ge(move))) extension = 1; - // Last captures extension - else if ( PieceValue[EG][pos.captured_piece()] > PawnValueEg - && pos.non_pawn_material() <= 2 * RookValueMg) - extension = 1; - // Add extension to new depth newDepth += extension; @@ -1148,18 +1171,20 @@ moves_loop: // When in check, search starts from here [movedPiece] [to_sq(move)]; - // Step 14. Make the move + // Step 15. Make the move pos.do_move(move, st, givesCheck); - // Step 15. Reduced depth search (LMR, ~200 Elo). If the move fails high it will be - // re-searched at full depth. + // Step 16. Late moves reduction / extension (LMR, ~200 Elo) + // We use various heuristics for the sons of a node after the first son has + // been searched. In general we would like to reduce them, but there are many + // cases where we extend a son if it has good chances to be "interesting". if ( depth >= 3 && moveCount > 1 + 2 * rootNode && ( !captureOrPromotion || moveCountPruning || ss->staticEval + PieceValue[EG][pos.captured_piece()] <= alpha || cutNode - || (!PvNode && !formerPv && captureHistory[movedPiece][to_sq(move)][type_of(pos.captured_piece())] < 4506) + || (!PvNode && !formerPv && captureHistory[movedPiece][to_sq(move)][type_of(pos.captured_piece())] < 3678) || thisThread->ttHitAverage < 432 * TtHitAverageResolution * TtHitAverageWindow / 1024)) { Depth r = reduction(improving, depth, moveCount); @@ -1172,16 +1197,21 @@ moves_loop: // When in check, search starts from here if (th.marked()) r++; - // Decrease reduction if position is or has been on the PV (~10 Elo) - if (ss->ttPv) + // Decrease reduction if position is or has been on the PV + // and node is not likely to fail low. (~10 Elo) + if ( ss->ttPv + && !likelyFailLow) r -= 2; // Increase reduction at root and non-PV nodes when the best move does not change frequently - if ((rootNode || !PvNode) && thisThread->rootDepth > 10 && thisThread->bestMoveChanges <= 2) + if ( (rootNode || !PvNode) + && thisThread->rootDepth > 10 + && thisThread->bestMoveChanges <= 2) r++; // More reductions for late moves if position was not in previous PV - if (moveCountPruning && !formerPv) + if ( moveCountPruning + && !formerPv) r++; // Decrease reduction if opponent's move count is high (~5 Elo) @@ -1194,7 +1224,7 @@ moves_loop: // When in check, search starts from here if (captureOrPromotion) { - // Unless giving check, this capture is likely bad + // Increase reduction for non-checking captures likely to be bad if ( !givesCheck && ss->staticEval + PieceValue[EG][pos.captured_piece()] + 210 * depth <= alpha) r++; @@ -1214,7 +1244,7 @@ moves_loop: // When in check, search starts from here // 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(). (~2 Elo) + // hence break reverse_move() (~2 Elo) else if ( type_of(move) == NORMAL && !pos.see_ge(reverse_move(move))) r -= 2 + ss->ttPv - (type_of(movedPiece) == PAWN); @@ -1223,7 +1253,7 @@ moves_loop: // When in check, search starts from here + (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] + (*contHist[3])[movedPiece][to_sq(move)] - - 5337; + - 4741; // Decrease/increase reduction by comparing opponent's stat score (~10 Elo) if (ss->statScore >= -89 && (ss-1)->statScore < -116) @@ -1233,31 +1263,33 @@ moves_loop: // When in check, search starts from here r++; // Decrease/increase reduction for moves with a good/bad history (~30 Elo) - // If we are not in check use statScore, if we are in check - // use sum of main history and first continuation history with an offset + // If we are not in check use statScore, but if we are in check we use + // the sum of main history and first continuation history with an offset. if (ss->inCheck) r -= (thisThread->mainHistory[us][from_to(move)] - + (*contHist[0])[movedPiece][to_sq(move)] - 4341) / 16384; + + (*contHist[0])[movedPiece][to_sq(move)] - 3833) / 16384; else - r -= ss->statScore / 14382; + r -= ss->statScore / 14790; } - Depth d = std::clamp(newDepth - r, 1, newDepth); + // In general we want to cap the LMR depth search at newDepth. But if + // reductions are really negative and movecount is low, we allow this move + // to be searched deeper than the first move. + Depth d = std::clamp(newDepth - r, 1, newDepth + (r < -1 && moveCount <= 5)); value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - doFullDepthSearch = value > alpha && d != newDepth; - + // If the son is reduced and fails high it will be re-searched at full depth + doFullDepthSearch = value > alpha && d < newDepth; didLMR = true; } else { doFullDepthSearch = !PvNode || moveCount > 1; - didLMR = false; } - // Step 16. Full depth search when LMR is skipped or fails high + // Step 17. Full depth search when LMR is skipped or fails high if (doFullDepthSearch) { value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); @@ -1284,12 +1316,12 @@ moves_loop: // When in check, search starts from here std::min(maxNextDepth, newDepth), false); } - // Step 17. Undo move + // Step 18. Undo move pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // Step 18. Check for a new best move + // Step 19. Check for a new best move // Finished searching the move. If a stop occurred, the return value of // the search cannot be trusted, and we return immediately without // updating best move, PV and TT. @@ -1366,7 +1398,7 @@ moves_loop: // When in check, search starts from here return VALUE_DRAW; */ - // Step 19. Check for mate and stalemate + // Step 20. Check for mate and stalemate // All legal moves have been searched and if there are no legal moves, it // must be a mate or a stalemate. If we are in a singular extension search then // return a fail low score. @@ -1374,8 +1406,9 @@ moves_loop: // When in check, search starts from here assert(moveCount || !ss->inCheck || excludedMove || !MoveList(pos).size()); if (!moveCount) - bestValue = excludedMove ? alpha - : ss->inCheck ? mated_in(ss->ply) : VALUE_DRAW; + bestValue = excludedMove ? alpha : + ss->inCheck ? mated_in(ss->ply) + : VALUE_DRAW; // If there is a move which produces search value greater than alpha we update stats of searched moves else if (bestMove) @@ -1425,7 +1458,7 @@ moves_loop: // When in check, search starts from here Move pv[MAX_PLY+1]; StateInfo st; - ASSERT_ALIGNED(&st, Eval::NNUE::kCacheLineSize); + ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize); TTEntry* tte; Key posKey; @@ -1541,15 +1574,13 @@ moves_loop: // When in check, search starts from here moveCount++; - // Futility pruning + // Futility pruning and moveCount pruning if ( bestValue > VALUE_TB_LOSS_IN_MAX_PLY && !givesCheck && futilityBase > -VALUE_KNOWN_WIN - && !pos.advanced_pawn_push(move)) + && type_of(move) != PROMOTION) { - assert(type_of(move) != EN_PASSANT); // Due to !pos.advanced_pawn_push - // moveCount pruning if (moveCount > 2) continue; @@ -1933,7 +1964,7 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { bool RootMove::extract_ponder_from_tt(Position& pos) { StateInfo st; - ASSERT_ALIGNED(&st, Eval::NNUE::kCacheLineSize); + ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize); bool ttHit; @@ -2002,3 +2033,5 @@ void Tablebases::rank_root_moves(Position& pos, Search::RootMoves& rootMoves) { m.tbRank = 0; } } + +} // namespace Stockfish