/*
Stockfish, a UCI chess playing engine derived from Glaurung 2.1
- Copyright (C) 2004-2022 The Stockfish developers (see AUTHORS file)
+ Copyright (C) 2004-2023 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
// History and stats update bonus, based on depth
int stat_bonus(Depth d) {
- return std::min((12 * d + 282) * d - 349 , 1594);
+ return std::min((12 * d + 282) * d - 349 , 1480);
}
// Add a small random component to draw evaluations to avoid 3-fold blindness
// Send again PV info if we have a new best thread
if (bestThread != this)
- sync_cout << UCI::pv(bestThread->rootPos, bestThread->completedDepth, -VALUE_INFINITE, VALUE_INFINITE) << sync_endl;
+ sync_cout << UCI::pv(bestThread->rootPos, bestThread->completedDepth) << sync_endl;
sync_cout << "bestmove " << UCI::move(bestThread->rootMoves[0].pv[0], rootPos.is_chess960());
&& multiPV == 1
&& (bestValue <= alpha || bestValue >= beta)
&& Time.elapsed() > 3000)
- sync_cout << UCI::pv(rootPos, rootDepth, alpha, beta) << sync_endl;
+ sync_cout << UCI::pv(rootPos, rootDepth) << sync_endl;
// In case of failing low/high increase aspiration window and
// re-search, otherwise exit the loop.
if ( mainThread
&& (Threads.stop || pvIdx + 1 == multiPV || Time.elapsed() > 3000))
- sync_cout << UCI::pv(rootPos, rootDepth, alpha, beta) << sync_endl;
+ sync_cout << UCI::pv(rootPos, rootDepth) << sync_endl;
}
if (!Threads.stop)
else
Threads.stop = true;
}
- else if ( Threads.increaseDepth
- && !mainThread->ponder
+ else if ( !mainThread->ponder
&& Time.elapsed() > totalTime * 0.53)
- Threads.increaseDepth = false;
+ Threads.increaseDepth = false;
else
- Threads.increaseDepth = true;
+ Threads.increaseDepth = true;
}
mainThread->iterValue[iterIdx] = bestValue;
&& ttValue != VALUE_NONE // Possible in case of TT access race
&& (tte->bound() & (ttValue >= beta ? BOUND_LOWER : BOUND_UPPER)))
{
- // If ttMove is quiet, update move sorting heuristics on TT hit (~1 Elo)
+ // If ttMove is quiet, update move sorting heuristics on TT hit (~2 Elo)
if (ttMove)
{
if (ttValue >= beta)
{
- // Bonus for a quiet ttMove that fails high (~3 Elo)
+ // Bonus for a quiet ttMove that fails high (~2 Elo)
if (!ttCapture)
update_quiet_stats(pos, ss, ttMove, stat_bonus(depth));
- // Extra penalty for early quiet moves of the previous ply (~0 Elo)
+ // Extra penalty for early quiet moves of the previous ply (~0 Elo on STC, ~2 Elo on LTC)
if ((ss-1)->moveCount <= 2 && !priorCapture)
update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + 1));
}
else // Fall back to (semi)classical complexity for TT hits, the NNUE complexity is lost
complexity = abs(ss->staticEval - pos.psq_eg_stm());
- // ttValue can be used as a better position evaluation (~4 Elo)
+ // ttValue can be used as a better position evaluation (~7 Elo)
if ( ttValue != VALUE_NONE
&& (tte->bound() & (ttValue > eval ? BOUND_LOWER : BOUND_UPPER)))
eval = ttValue;
thisThread->complexityAverage.update(complexity);
- // Use static evaluation difference to improve quiet move ordering (~3 Elo)
+ // Use static evaluation difference to improve quiet move ordering (~4 Elo)
if (is_ok((ss-1)->currentMove) && !(ss-1)->inCheck && !priorCapture)
{
int bonus = std::clamp(-19 * int((ss-1)->staticEval + ss->staticEval), -1914, 1914);
: 168;
improving = improvement > 0;
- // Step 7. Razoring.
+ // Step 7. Razoring (~1 Elo).
// If eval is really low check with qsearch if it can exceed alpha, if it can't,
// return a fail low.
if (eval < alpha - 369 - 254 * depth * depth)
return value;
}
- // Step 8. Futility pruning: child node (~25 Elo).
+ // Step 8. Futility pruning: child node (~40 Elo).
// The depth condition is important for mate finding.
if ( !ss->ttPv
&& depth < 8
&& eval < 28031) // larger than VALUE_KNOWN_WIN, but smaller than TB wins
return eval;
- // Step 9. Null move search with verification search (~22 Elo)
+ // Step 9. Null move search with verification search (~35 Elo)
if ( !PvNode
&& (ss-1)->currentMove != MOVE_NULL
&& (ss-1)->statScore < 17139
probCutBeta = beta + 191 - 54 * improving;
- // Step 10. ProbCut (~4 Elo)
+ // 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
{
assert(probCutBeta < VALUE_INFINITE);
- MovePicker mp(pos, ttMove, probCutBeta - ss->staticEval, depth - 3, &captureHistory);
+ MovePicker mp(pos, ttMove, probCutBeta - ss->staticEval, &captureHistory);
while ((move = mp.next_move()) != MOVE_NONE)
if (move != excludedMove && pos.legal(move))
}
// Step 11. If the position is not in TT, decrease depth by 3.
- // Use qsearch if depth is equal or below zero (~4 Elo)
+ // Use qsearch if depth is equal or below zero (~9 Elo)
if ( PvNode
&& !ttMove)
depth -= 3;
moves_loop: // When in check, search starts here
- // Step 12. A small Probcut idea, when we are in check (~0 Elo)
+ // Step 12. A small Probcut idea, when we are in check (~4 Elo)
probCutBeta = beta + 417;
if ( ss->inCheck
&& !PvNode
Value delta = beta - alpha;
- // Step 14. Pruning at shallow depth (~98 Elo). Depth conditions are important for mate finding.
+ // Step 14. Pruning at shallow depth (~120 Elo). Depth conditions are important for mate finding.
if ( !rootNode
&& pos.non_pawn_material(us)
&& bestValue > VALUE_TB_LOSS_IN_MAX_PLY)
{
- // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold (~7 Elo)
+ // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold (~8 Elo)
moveCountPruning = moveCount >= futility_move_count(improving, depth);
// Reduced depth of the next LMR search
if ( capture
|| givesCheck)
{
- // Futility pruning for captures (~0 Elo)
+ // Futility pruning for captures (~2 Elo)
if ( !givesCheck
&& !PvNode
&& lmrDepth < 7
+ captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))] / 6 < alpha)
continue;
- // SEE based pruning (~9 Elo)
+ // SEE based pruning (~11 Elo)
if (!pos.see_ge(move, Value(-222) * depth))
continue;
}
history += 2 * thisThread->mainHistory[us][from_to(move)];
- // Futility pruning: parent node (~9 Elo)
+ // Futility pruning: parent node (~13 Elo)
if ( !ss->inCheck
&& lmrDepth < 13
&& ss->staticEval + 106 + 145 * lmrDepth + history / 52 <= alpha)
continue;
- // Prune moves with negative SEE (~3 Elo)
+ // Prune moves with negative SEE (~4 Elo)
if (!pos.see_ge(move, Value(-24 * lmrDepth * lmrDepth - 15 * lmrDepth)))
continue;
}
}
- // Step 15. Extensions (~66 Elo)
+ // Step 15. Extensions (~100 Elo)
// We take care to not overdo to avoid search getting stuck.
if (ss->ply < thisThread->rootDepth * 2)
{
- // Singular extension search (~58 Elo). If all moves but one fail low on a
+ // Singular extension search (~94 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
// Avoid search explosion by limiting the number of double extensions
if ( !PvNode
&& value < singularBeta - 25
- && ss->doubleExtensions <= 9)
+ && ss->doubleExtensions <= 10)
+ {
extension = 2;
+ depth += depth < 12;
+ }
}
// Multi-cut pruning
&& abs(ss->staticEval) > 82)
extension = 1;
- // Quiet ttMove extensions (~0 Elo)
+ // Quiet ttMove extensions (~1 Elo)
else if ( PvNode
&& move == ttMove
&& move == ss->killers[0]
// Step 16. Make the move
pos.do_move(move, st, givesCheck);
- // Step 17. Late moves reduction / extension (LMR, ~98 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 >= 2
- && moveCount > 1 + (PvNode && ss->ply <= 1)
- && ( !ss->ttPv
- || !capture
- || (cutNode && (ss-1)->moveCount > 1)))
- {
- Depth r = reduction(improving, depth, moveCount, delta, thisThread->rootDelta);
+ Depth r = reduction(improving, depth, moveCount, delta, thisThread->rootDelta);
- // Decrease reduction if position is or has been on the PV
- // and node is not likely to fail low. (~3 Elo)
- if ( ss->ttPv
- && !likelyFailLow)
- r -= 2;
+ // Decrease reduction if position is or has been on the PV
+ // and node is not likely to fail low. (~3 Elo)
+ if ( ss->ttPv
+ && !likelyFailLow)
+ r -= 2;
- // Decrease reduction if opponent's move count is high (~1 Elo)
- if ((ss-1)->moveCount > 7)
- r--;
+ // Decrease reduction if opponent's move count is high (~1 Elo)
+ if ((ss-1)->moveCount > 7)
+ r--;
- // Increase reduction for cut nodes (~3 Elo)
- if (cutNode)
- r += 2;
+ // Increase reduction for cut nodes (~3 Elo)
+ if (cutNode)
+ r += 2;
- // Increase reduction if ttMove is a capture (~3 Elo)
- if (ttCapture)
- r++;
+ // Increase reduction if ttMove is a capture (~3 Elo)
+ if (ttCapture)
+ r++;
- // Decrease reduction for PvNodes based on depth
- if (PvNode)
- r -= 1 + 11 / (3 + depth);
+ // Decrease reduction for PvNodes based on depth
+ if (PvNode)
+ r -= 1 + 11 / (3 + depth);
- // Decrease reduction if ttMove has been singularly extended (~1 Elo)
- if (singularQuietLMR)
- r--;
+ // Decrease reduction if ttMove has been singularly extended (~1 Elo)
+ if (singularQuietLMR)
+ r--;
- // Dicrease reduction if we move a threatened piece (~1 Elo)
- if ( depth > 9
- && (mp.threatenedPieces & from_sq(move)))
- r--;
+ // Decrease reduction if we move a threatened piece (~1 Elo)
+ if ( depth > 9
+ && (mp.threatenedPieces & from_sq(move)))
+ r--;
- // Increase reduction if next ply has a lot of fail high
- if ((ss+1)->cutoffCnt > 3 && !PvNode)
- r++;
+ // Increase reduction if next ply has a lot of fail high
+ if ((ss+1)->cutoffCnt > 3)
+ r++;
- ss->statScore = 2 * thisThread->mainHistory[us][from_to(move)]
- + (*contHist[0])[movedPiece][to_sq(move)]
- + (*contHist[1])[movedPiece][to_sq(move)]
- + (*contHist[3])[movedPiece][to_sq(move)]
- - 4433;
+ ss->statScore = 2 * thisThread->mainHistory[us][from_to(move)]
+ + (*contHist[0])[movedPiece][to_sq(move)]
+ + (*contHist[1])[movedPiece][to_sq(move)]
+ + (*contHist[3])[movedPiece][to_sq(move)]
+ - 4433;
- // Decrease/increase reduction for moves with a good/bad history (~30 Elo)
- r -= ss->statScore / (13628 + 4000 * (depth > 7 && depth < 19));
+ // Decrease/increase reduction for moves with a good/bad history (~30 Elo)
+ r -= ss->statScore / (13000 + 4152 * (depth > 7 && depth < 19));
+ // Step 17. Late moves reduction / extension (LMR, ~117 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 >= 2
+ && moveCount > 1 + (PvNode && ss->ply <= 1)
+ && ( !ss->ttPv
+ || !capture
+ || (cutNode && (ss-1)->moveCount > 1)))
+ {
// In general we want to cap the LMR depth search at newDepth, but when
// reduction is negative, we allow this move a limited search extension
// beyond the first move depth. This may lead to hidden double extensions.
// Adjust full depth search based on LMR results - if result
// was good enough search deeper, if it was bad enough search shallower
const bool doDeeperSearch = value > (alpha + 64 + 11 * (newDepth - d));
+ const bool doEvenDeeperSearch = value > alpha + 582 && ss->doubleExtensions <= 5;
const bool doShallowerSearch = value < bestValue + newDepth;
- value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth + doDeeperSearch - doShallowerSearch, !cutNode);
+
+ ss->doubleExtensions = ss->doubleExtensions + doEvenDeeperSearch;
+
+ newDepth += doDeeperSearch - doShallowerSearch + doEvenDeeperSearch;
+
+ if (newDepth > d)
+ value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode);
int bonus = value > alpha ? stat_bonus(newDepth)
: -stat_bonus(newDepth);
}
}
- // Step 18. Full depth search when LMR is skipped
+ // Step 18. Full depth search when LMR is skipped. If expected reduction is high, reduce its depth by 1.
else if (!PvNode || moveCount > 1)
{
- value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode);
+ value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth - (r > 4), !cutNode);
}
// For PV nodes only, do a full PV search on the first move or after a fail
// PV move or new best move?
if (moveCount == 1 || value > alpha)
{
- rm.score = value;
+ rm.score = rm.uciScore = value;
rm.selDepth = thisThread->selDepth;
+ rm.scoreLowerbound = rm.scoreUpperbound = false;
+
+ if (value >= beta) {
+ rm.scoreLowerbound = true;
+ rm.uciScore = beta;
+ }
+ else if (value <= alpha) {
+ rm.scoreUpperbound = true;
+ rm.uciScore = alpha;
+ }
rm.pv.resize(1);
assert((ss+1)->pv);
&& depth < 6
&& beta < VALUE_KNOWN_WIN
&& alpha > -VALUE_KNOWN_WIN)
- depth -= 1;
+ depth -= 1;
assert(depth > 0);
}
}
}
}
- else
- ss->cutoffCnt = 0;
// If the move is worse than some previously searched move, remember it to update its stats later
quietsSearched, quietCount, capturesSearched, captureCount, depth);
// Bonus for prior countermove that caused the fail low
- else if ( (depth >= 5 || PvNode)
+ else if ( (depth >= 5 || PvNode || bestValue < alpha - 62 * depth)
&& !priorCapture)
{
//Assign extra bonus if current node is PvNode or cutNode
//or fail low was really bad
bool extraBonus = PvNode
- || cutNode
- || bestValue < alpha - 62 * depth;
+ || cutNode;
- update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * (1 + extraBonus));
+ bool doubleExtraBonus = extraBonus && bestValue < alpha - 85 * depth;
+
+ update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * (1 + extraBonus + doubleExtraBonus));
}
if (PvNode)
if ((ss->staticEval = bestValue = tte->eval()) == VALUE_NONE)
ss->staticEval = bestValue = evaluate(pos);
- // ttValue can be used as a better position evaluation (~7 Elo)
+ // ttValue can be used as a better position evaluation (~13 Elo)
if ( ttValue != VALUE_NONE
&& (tte->bound() & (ttValue > bestValue ? BOUND_LOWER : BOUND_UPPER)))
bestValue = ttValue;
moveCount++;
- // Futility pruning and moveCount pruning (~5 Elo)
+ // Futility pruning and moveCount pruning (~10 Elo)
if ( bestValue > VALUE_TB_LOSS_IN_MAX_PLY
&& !givesCheck
&& to_sq(move) != prevSq
&& futilityBase > -VALUE_KNOWN_WIN
&& type_of(move) != PROMOTION)
{
-
if (moveCount > 2)
continue;
[pos.moved_piece(move)]
[to_sq(move)];
- // Continuation history based pruning (~2 Elo)
+ // Continuation history based pruning (~3 Elo)
if ( !capture
&& bestValue > VALUE_TB_LOSS_IN_MAX_PLY
&& (*contHist[0])[pos.moved_piece(move)][to_sq(move)] < 0
&& (*contHist[1])[pos.moved_piece(move)][to_sq(move)] < 0)
continue;
- // movecount pruning for quiet check evasions
+ // We prune after 2nd quiet check evasion where being 'in check' is implicitly checked through the counter
+ // and being a 'quiet' apart from being a tt move is assumed after an increment because captures are pushed ahead.
if ( bestValue > VALUE_TB_LOSS_IN_MAX_PLY
- && quietCheckEvasions > 1
- && !capture
- && ss->inCheck)
- continue;
+ && quietCheckEvasions > 1)
+ break;
quietCheckEvasions += !capture && ss->inCheck;
/// UCI::pv() formats PV information according to the UCI protocol. UCI requires
/// that all (if any) unsearched PV lines are sent using a previous search score.
-string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) {
+string UCI::pv(const Position& pos, Depth depth) {
std::stringstream ss;
TimePoint elapsed = Time.elapsed() + 1;
continue;
Depth d = updated ? depth : std::max(1, depth - 1);
- Value v = updated ? rootMoves[i].score : rootMoves[i].previousScore;
+ Value v = updated ? rootMoves[i].uciScore : rootMoves[i].previousScore;
if (v == -VALUE_INFINITE)
v = VALUE_ZERO;
if (Options["UCI_ShowWDL"])
ss << UCI::wdl(v, pos.game_ply());
- if (!tb && i == pvIdx)
- ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : "");
+ if (i == pvIdx && !tb && updated) // tablebase- and previous-scores are exact
+ ss << (rootMoves[i].scoreLowerbound ? " lowerbound" : (rootMoves[i].scoreUpperbound ? " upperbound" : ""));
ss << " nodes " << nodesSearched
<< " nps " << nodesSearched * 1000 / elapsed
projects / stockfish / blobdiff