X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=d9543899a0f7844e2b817b3e2095f321a8ca51fc;hp=a9a62dbf8477926c2a53ae2759eee4f4cb4a0f56;hb=46ce245763705c89dba60dcfda549dc1f64eb48b;hpb=49a1fdd3fe894d170a2c2781238c0f0f907c08cc
diff --git a/src/search.cpp b/src/search.cpp
index a9a62dbf..d9543899 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -18,6 +18,7 @@
along with this program. If not, see .
*/
+#include
#include
#include
#include // For std::memset
@@ -67,11 +68,11 @@ namespace {
}
// Reductions lookup table, initialized at startup
- int Reductions[64]; // [depth or moveNumber]
+ int Reductions[MAX_MOVES]; // [depth or moveNumber]
- template Depth reduction(bool i, Depth d, int mn) {
- int r = Reductions[std::min(d / ONE_PLY, 63)] * Reductions[std::min(mn, 63)] / 1024;
- return ((r + 512) / 1024 + (!i && r > 1024) - PvNode) * ONE_PLY;
+ Depth reduction(bool i, Depth d, int mn) {
+ int r = Reductions[d / ONE_PLY] * Reductions[mn];
+ return ((r + 512) / 1024 + (!i && r > 1024)) * ONE_PLY;
}
constexpr int futility_move_count(bool improving, int depth) {
@@ -147,8 +148,8 @@ namespace {
void Search::init() {
- for (int i = 1; i < 64; ++i)
- Reductions[i] = int(1024 * std::log(i) / std::sqrt(1.95));
+ for (int i = 1; i < MAX_MOVES; ++i)
+ Reductions[i] = int(22.9 * std::log(i));
}
@@ -238,21 +239,15 @@ void MainThread::search() {
for (Thread* th: Threads)
minScore = std::min(minScore, th->rootMoves[0].score);
- // Vote according to score and depth
+ // Vote according to score and depth, and select the best thread
for (Thread* th : Threads)
{
- int64_t s = th->rootMoves[0].score - minScore + 1;
- votes[th->rootMoves[0].pv[0]] += 200 + s * s * int(th->completedDepth);
- }
+ votes[th->rootMoves[0].pv[0]] +=
+ (th->rootMoves[0].score - minScore + 14) * int(th->completedDepth);
- // Select best thread
- auto bestVote = votes[this->rootMoves[0].pv[0]];
- for (Thread* th : Threads)
- if (votes[th->rootMoves[0].pv[0]] > bestVote)
- {
- bestVote = votes[th->rootMoves[0].pv[0]];
+ if (votes[th->rootMoves[0].pv[0]] > votes[bestThread->rootMoves[0].pv[0]])
bestThread = th;
- }
+ }
}
previousScore = bestThread->rootMoves[0].score;
@@ -405,17 +400,14 @@ void Thread::search() {
beta = (alpha + beta) / 2;
alpha = std::max(bestValue - delta, -VALUE_INFINITE);
+ failedHighCnt = 0;
if (mainThread)
- {
- failedHighCnt = 0;
mainThread->stopOnPonderhit = false;
- }
}
else if (bestValue >= beta)
{
beta = std::min(bestValue + delta, VALUE_INFINITE);
- if (mainThread)
- ++failedHighCnt;
+ ++failedHighCnt;
}
else
break;
@@ -542,13 +534,13 @@ namespace {
bool ttHit, ttPv, inCheck, givesCheck, improving;
bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture;
Piece movedPiece;
- int moveCount, captureCount, quietCount;
+ int moveCount, captureCount, quietCount, singularLMR;
// Step 1. Initialize node
Thread* thisThread = pos.this_thread();
inCheck = pos.checkers();
Color us = pos.side_to_move();
- moveCount = captureCount = quietCount = ss->moveCount = 0;
+ moveCount = captureCount = quietCount = singularLMR = ss->moveCount = 0;
bestValue = -VALUE_INFINITE;
maxValue = VALUE_INFINITE;
@@ -584,8 +576,7 @@ namespace {
assert(0 <= ss->ply && ss->ply < MAX_PLY);
(ss+1)->ply = ss->ply + 1;
- ss->currentMove = (ss+1)->excludedMove = bestMove = MOVE_NONE;
- ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0];
+ (ss+1)->excludedMove = bestMove = MOVE_NONE;
(ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE;
Square prevSq = to_sq((ss-1)->currentMove);
@@ -594,7 +585,10 @@ namespace {
// starts with statScore = 0. Later grandchildren start with the last calculated
// statScore of the previous grandchild. This influences the reduction rules in
// LMR which are based on the statScore of parent position.
- (ss+2)->statScore = 0;
+ if (rootNode)
+ (ss + 4)->statScore = 0;
+ else
+ (ss + 2)->statScore = 0;
// Step 4. Transposition table lookup. We don't want the score of a partial
// search to overwrite a previous full search TT value, so we use a different
@@ -605,16 +599,7 @@ namespace {
ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
ttMove = rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0]
: ttHit ? tte->move() : MOVE_NONE;
- ttPv = (ttHit && tte->is_pv()) || (PvNode && depth > 4 * ONE_PLY);
-
- // if position has been searched at higher depths and we are shuffling, return value_draw
- if (pos.rule50_count() > 36
- && ss->ply > 36
- && depth < 3 * ONE_PLY
- && ttHit
- && tte->depth() > depth
- && pos.count() > 0)
- return VALUE_DRAW;
+ ttPv = PvNode || (ttHit && tte->is_pv());
// At non-PV nodes we check for an early TT cutoff
if ( !PvNode
@@ -632,9 +617,8 @@ namespace {
if (!pos.capture_or_promotion(ttMove))
update_quiet_stats(pos, ss, ttMove, nullptr, 0, stat_bonus(depth));
- // Extra penalty for a quiet TT or main killer move in previous ply when it gets refuted
- if ( ((ss-1)->moveCount == 1 || (ss-1)->currentMove == (ss-1)->killers[0])
- && !pos.captured_piece())
+ // Extra penalty for early quiet moves of the previous ply
+ if ((ss-1)->moveCount <= 2 && !pos.captured_piece())
update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + ONE_PLY));
}
// Penalty for a quiet ttMove that fails low
@@ -905,7 +889,7 @@ moves_loop: // When in check, search starts from here
&& move == ttMove
&& !rootNode
&& !excludedMove // Avoid recursive singular search
- /* && ttValue != VALUE_NONE Already implicit in the next condition */
+ /* && ttValue != VALUE_NONE Already implicit in the next condition */
&& abs(ttValue) < VALUE_KNOWN_WIN
&& (tte->bound() & BOUND_LOWER)
&& tte->depth() >= depth - 3 * ONE_PLY
@@ -918,7 +902,13 @@ moves_loop: // When in check, search starts from here
ss->excludedMove = MOVE_NONE;
if (value < singularBeta)
+ {
extension = ONE_PLY;
+ singularLMR++;
+
+ if (value < singularBeta - std::min(3 * depth / ONE_PLY, 39))
+ singularLMR++;
+ }
// Multi-cut pruning
// Our ttMove is assumed to fail high, and now we failed high also on a reduced
@@ -934,12 +924,21 @@ moves_loop: // When in check, search starts from here
&& (pos.blockers_for_king(~us) & from_sq(move) || pos.see_ge(move)))
extension = ONE_PLY;
+ // Castling extension
+ else if (type_of(move) == CASTLING)
+ extension = ONE_PLY;
+
// Shuffle extension
- else if(pos.rule50_count() > 14 && ss->ply > 14 && depth < 3 * ONE_PLY && PvNode)
+ else if ( PvNode
+ && pos.rule50_count() > 18
+ && depth < 3 * ONE_PLY
+ && ss->ply < 3 * thisThread->rootDepth / ONE_PLY) // To avoid too deep searches
extension = ONE_PLY;
- // Castling extension
- else if (type_of(move) == CASTLING)
+ // Passed pawn extension
+ else if ( move == ss->killers[0]
+ && pos.advanced_pawn_push(move)
+ && pos.pawn_passed(us, to_sq(move)))
extension = ONE_PLY;
// Calculate new depth for this move
@@ -955,14 +954,14 @@ moves_loop: // When in check, search starts from here
if ( !captureOrPromotion
&& !givesCheck
- && !pos.advanced_pawn_push(move))
+ && (!pos.advanced_pawn_push(move) || pos.non_pawn_material(~us) > BishopValueMg))
{
// Move count based pruning (~30 Elo)
if (moveCountPruning)
continue;
// Reduced depth of the next LMR search
- int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), DEPTH_ZERO);
+ int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), DEPTH_ZERO);
lmrDepth /= ONE_PLY;
// Countermoves based pruning (~20 Elo)
@@ -981,7 +980,8 @@ moves_loop: // When in check, search starts from here
if (!pos.see_ge(move, Value(-29 * lmrDepth * lmrDepth)))
continue;
}
- else if (!pos.see_ge(move, -PawnValueEg * (depth / ONE_PLY))) // (~20 Elo)
+ else if ((!givesCheck || !extension)
+ && !pos.see_ge(move, -PawnValueEg * (depth / ONE_PLY))) // (~20 Elo)
continue;
}
@@ -1005,19 +1005,24 @@ moves_loop: // When in check, search starts from here
// Step 16. Reduced depth search (LMR). If the move fails high it will be
// re-searched at full depth.
if ( depth >= 3 * ONE_PLY
- && moveCount > 1
- && (!captureOrPromotion || moveCountPruning))
+ && moveCount > 1 + 3 * rootNode
+ && ( !captureOrPromotion
+ || moveCountPruning
+ || ss->staticEval + PieceValue[EG][pos.captured_piece()] <= alpha))
{
- Depth r = reduction(improving, depth, moveCount);
+ Depth r = reduction(improving, depth, moveCount);
// Decrease reduction if position is or has been on the PV
if (ttPv)
- r -= ONE_PLY;
+ r -= 2 * ONE_PLY;
// Decrease reduction if opponent's move count is high (~10 Elo)
if ((ss-1)->moveCount > 15)
r -= ONE_PLY;
+ // Decrease reduction if move has been singularly extended
+ r -= singularLMR * ONE_PLY;
+
if (!captureOrPromotion)
{
// Increase reduction if ttMove is a capture (~0 Elo)
@@ -1052,7 +1057,7 @@ moves_loop: // When in check, search starts from here
r -= ss->statScore / 20000 * ONE_PLY;
}
- Depth d = std::max(newDepth - std::max(r, DEPTH_ZERO), ONE_PLY);
+ Depth d = clamp(newDepth - r, ONE_PLY, newDepth);
value = -search(pos, ss+1, -(alpha+1), -alpha, d, true);
@@ -1203,8 +1208,8 @@ moves_loop: // When in check, search starts from here
}
- // qsearch() is the quiescence search function, which is called by the main
- // search function with depth zero, or recursively with depth less than ONE_PLY.
+ // qsearch() is the quiescence search function, which is called by the main search
+ // function with zero depth, or recursively with further decreasing depth per call.
template
Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) {
@@ -1234,8 +1239,7 @@ moves_loop: // When in check, search starts from here
Thread* thisThread = pos.this_thread();
(ss+1)->ply = ss->ply + 1;
- ss->currentMove = bestMove = MOVE_NONE;
- ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0];
+ bestMove = MOVE_NONE;
inCheck = pos.checkers();
moveCount = 0;
@@ -1359,6 +1363,7 @@ moves_loop: // When in check, search starts from here
// Don't search moves with negative SEE values
if ( (!inCheck || evasionPrunable)
+ && (!givesCheck || !(pos.blockers_for_king(~pos.side_to_move()) & from_sq(move)))
&& !pos.see_ge(move))
continue;
@@ -1469,7 +1474,7 @@ moves_loop: // When in check, search starts from here
void update_capture_stats(const Position& pos, Move move,
Move* captures, int captureCount, int bonus) {
- CapturePieceToHistory& captureHistory = pos.this_thread()->captureHistory;
+ CapturePieceToHistory& captureHistory = pos.this_thread()->captureHistory;
Piece moved_piece = pos.moved_piece(move);
PieceType captured = type_of(pos.piece_on(to_sq(move)));
@@ -1708,10 +1713,4 @@ void Tablebases::rank_root_moves(Position& pos, Search::RootMoves& rootMoves) {
if (dtz_available || rootMoves[0].tbScore <= VALUE_DRAW)
Cardinality = 0;
}
- else
- {
- // Assign the same rank to all moves
- for (auto& m : rootMoves)
- m.tbRank = 0;
- }
}