X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=16c6b0f38f85ad9efd8c1eda19e4d7ca0ef4b105;hb=edb4ab924f09abd7c6836c7017365dceccd76b80;hp=411befdedfb460459902ffd8d9fc62fede6cc0d4;hpb=9829bceda90d025a5f5d7c04457902413e367041;p=stockfish
diff --git a/src/search.cpp b/src/search.cpp
index 411befde..16c6b0f3 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -16,25 +16,34 @@
along with this program. If not, see .
*/
+#include "search.h"
+
#include
+#include
+#include
#include
#include
-#include // For std::memset
+#include
+#include
+#include
#include
#include
+#include
+#include
+#include "bitboard.h"
#include "evaluate.h"
#include "misc.h"
#include "movegen.h"
#include "movepick.h"
+#include "nnue/evaluate_nnue.h"
+#include "nnue/nnue_common.h"
#include "position.h"
-#include "search.h"
+#include "syzygy/tbprobe.h"
#include "thread.h"
#include "timeman.h"
#include "tt.h"
#include "uci.h"
-#include "syzygy/tbprobe.h"
-#include "nnue/evaluate_nnue.h"
namespace Stockfish {
@@ -63,16 +72,17 @@ namespace {
enum NodeType { NonPV, PV, Root };
// Futility margin
- Value futility_margin(Depth d, bool improving) {
- return Value(154 * (d - improving));
+ Value futility_margin(Depth d, bool noTtCutNode, bool improving) {
+ return Value((126 - 42 * noTtCutNode) * (d - improving));
}
- // Reductions lookup table, initialized at startup
+ // Reductions lookup table initialized at startup
int Reductions[MAX_MOVES]; // [depth or moveNumber]
Depth reduction(bool i, Depth d, int mn, Value delta, Value rootDelta) {
- int r = Reductions[d] * Reductions[mn];
- return (r + 1449 - int(delta) * 937 / int(rootDelta)) / 1024 + (!i && r > 941);
+ int reductionScale = Reductions[d] * Reductions[mn];
+ return (reductionScale + 1560 - int(delta) * 945 / int(rootDelta)) / 1024
+ + (!i && reductionScale > 791);
}
constexpr int futility_move_count(bool improving, Depth depth) {
@@ -82,7 +92,7 @@ namespace {
// History and stats update bonus, based on depth
int stat_bonus(Depth d) {
- return std::min(341 * d - 470, 1710);
+ return std::min(334 * d - 531, 1538);
}
// Add a small random component to draw evaluations to avoid 3-fold blindness
@@ -90,10 +100,12 @@ namespace {
return VALUE_DRAW - 1 + Value(thisThread->nodes & 0x2);
}
- // Skill structure is used to implement strength limit. If we have an uci_elo then
- // we convert it to a suitable fractional skill level using anchoring to CCRL Elo
- // (goldfish 1.13 = 2000) and a fit through Ordo derived Elo for match (TC 60+0.6)
- // results spanning a wide range of k values.
+ // Skill structure is used to implement strength limit. If we have a UCI_Elo,
+ // we convert it to an appropriate skill level, anchored to the Stash engine.
+ // This method is based on a fit of the Elo results for games played between
+ // Stockfish at various skill levels and various versions of the Stash engine.
+ // Skill 0 .. 19 now covers CCRL Blitz Elo from 1320 to 3190, approximately
+ // Reference: https://github.com/vondele/Stockfish/commit/a08b8d4e9711c2
struct Skill {
Skill(int skill_level, int uci_elo) {
if (uci_elo)
@@ -157,16 +169,16 @@ namespace {
} // namespace
-/// Search::init() is called at startup to initialize various lookup tables
+// Search::init() is called at startup to initialize various lookup tables
void Search::init() {
for (int i = 1; i < MAX_MOVES; ++i)
- Reductions[i] = int((19.47 + std::log(Threads.size()) / 2) * std::log(i));
+ Reductions[i] = int((20.37 + std::log(Threads.size()) / 2) * std::log(i));
}
-/// Search::clear() resets search state to its initial value
+// Search::clear() resets search state to its initial value
void Search::clear() {
@@ -179,8 +191,8 @@ void Search::clear() {
}
-/// MainThread::search() is started when the program receives the UCI 'go'
-/// command. It searches from the root position and outputs the "bestmove".
+// MainThread::search() is started when the program receives the UCI 'go'
+// command. It searches from the root position and outputs the "bestmove".
void MainThread::search() {
@@ -256,16 +268,15 @@ void MainThread::search() {
}
-/// Thread::search() is the main iterative deepening loop. It calls search()
-/// repeatedly with increasing depth until the allocated thinking time has been
-/// consumed, the user stops the search, or the maximum search depth is reached.
+// Thread::search() is the main iterative deepening loop. It calls search()
+// repeatedly with increasing depth until the allocated thinking time has been
+// consumed, the user stops the search, or the maximum search depth is reached.
void Thread::search() {
- // To allow access to (ss-7) up to (ss+2), the stack must be oversized.
- // The former is needed to allow update_continuation_histories(ss-1, ...),
- // which accesses its argument at ss-6, also near the root.
- // The latter is needed for statScore and killer initialization.
+ // Allocate stack with extra size to allow access from (ss-7) to (ss+2):
+ // (ss-7) is needed for update_continuation_histories(ss-1) which accesses (ss-6),
+ // (ss+2) is needed for initialization of statScore and killers.
Stack stack[MAX_PLY+10], *ss = stack+7;
Move pv[MAX_PLY+1];
Value alpha, beta, delta;
@@ -288,20 +299,10 @@ void Thread::search() {
ss->pv = pv;
- bestValue = delta = alpha = -VALUE_INFINITE;
- beta = VALUE_INFINITE;
- optimism[WHITE] = optimism[BLACK] = VALUE_ZERO;
+ bestValue = -VALUE_INFINITE;
if (mainThread)
{
-
- if (!rootPos.checkers())
- {
- int rootComplexity;
- Eval::evaluate(rootPos, &rootComplexity);
- mainThread->complexity = std::min(1.03 + (rootComplexity - 241) / 1552.0, 1.45);
- }
-
if (mainThread->bestPreviousScore == VALUE_INFINITE)
for (int i = 0; i < 4; ++i)
mainThread->iterValue[i] = VALUE_ZERO;
@@ -314,9 +315,9 @@ void Thread::search() {
Skill skill(Options["Skill Level"], Options["UCI_LimitStrength"] ? int(Options["UCI_Elo"]) : 0);
// When playing with strength handicap enable MultiPV search that we will
- // use behind the scenes to retrieve a set of possible moves.
+ // use behind-the-scenes to retrieve a set of possible moves.
if (skill.enabled())
- multiPV = std::max(multiPV, (size_t)4);
+ multiPV = std::max(multiPV, size_t(4));
multiPV = std::min(multiPV, rootMoves.size());
@@ -331,7 +332,7 @@ void Thread::search() {
if (mainThread)
totBestMoveChanges /= 2;
- // Save the last iteration's scores before first PV line is searched and
+ // Save the last iteration's scores before the first PV line is searched and
// all the move scores except the (new) PV are set to -VALUE_INFINITE.
for (RootMove& rm : rootMoves)
rm.previousScore = rm.score;
@@ -357,18 +358,15 @@ void Thread::search() {
selDepth = 0;
// Reset aspiration window starting size
- if (rootDepth >= 4)
- {
- Value prev = rootMoves[pvIdx].averageScore;
- delta = Value(10) + int(prev) * prev / 16502;
- alpha = std::max(prev - delta,-VALUE_INFINITE);
- beta = std::min(prev + delta, VALUE_INFINITE);
-
- // Adjust optimism based on root move's previousScore
- int opt = 120 * prev / (std::abs(prev) + 161);
- optimism[ us] = Value(opt);
- optimism[~us] = -optimism[us];
- }
+ Value prev = rootMoves[pvIdx].averageScore;
+ delta = Value(10) + int(prev) * prev / 17470;
+ alpha = std::max(prev - delta,-VALUE_INFINITE);
+ beta = std::min(prev + delta, VALUE_INFINITE);
+
+ // Adjust optimism based on root move's previousScore (~4 Elo)
+ int opt = 113 * prev / (std::abs(prev) + 109);
+ optimism[ us] = Value(opt);
+ optimism[~us] = -optimism[us];
// Start with a small aspiration window and, in the case of a fail
// high/low, re-search with a bigger window until we don't fail
@@ -376,16 +374,16 @@ void Thread::search() {
int failedHighCnt = 0;
while (true)
{
- // Adjust the effective depth searched, but ensuring at least one effective increment for every
+ // Adjust the effective depth searched, but ensure at least one effective increment for every
// four searchAgain steps (see issue #2717).
Depth adjustedDepth = std::max(1, rootDepth - failedHighCnt - 3 * (searchAgainCounter + 1) / 4);
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
- // first and eventually the new best one are set to -VALUE_INFINITE
+ // first and eventually the new best one is set to -VALUE_INFINITE
// and we want to keep the same order for all the moves except the
- // new PV that goes to the front. Note that in case of MultiPV
+ // new PV that goes to the front. Note that in the case of MultiPV
// search the already searched PV lines are preserved.
std::stable_sort(rootMoves.begin() + pvIdx, rootMoves.begin() + pvLast);
@@ -422,7 +420,7 @@ void Thread::search() {
else
break;
- delta += delta / 4 + 2;
+ delta += delta / 3;
assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
}
@@ -453,7 +451,7 @@ void Thread::search() {
if (!mainThread)
continue;
- // If skill level is enabled and time is up, pick a sub-optimal best move
+ // If the skill level is enabled and time is up, pick a sub-optimal best move
if (skill.enabled() && skill.time_to_pick(rootDepth))
skill.pick_best(multiPV);
@@ -478,10 +476,9 @@ void Thread::search() {
double reduction = (1.4 + mainThread->previousTimeReduction) / (2.08 * timeReduction);
double bestMoveInstability = 1 + 1.8 * totBestMoveChanges / Threads.size();
- double totalTime = Time.optimum() * fallingEval * reduction * bestMoveInstability * mainThread->complexity;
+ double totalTime = Time.optimum() * fallingEval * reduction * bestMoveInstability;
- // Cap used time in case of a single legal move for a better viewer experience in tournaments
- // yielding correct scores and sufficiently fast moves.
+ // Cap used time in case of a single legal move for a better viewer experience
if (rootMoves.size() == 1)
totalTime = std::min(500.0, totalTime);
@@ -511,7 +508,7 @@ void Thread::search() {
mainThread->previousTimeReduction = timeReduction;
- // If skill level is enabled, swap best PV line with the sub-optimal one
+ // If the skill level is enabled, swap the best PV line with the sub-optimal one
if (skill.enabled())
std::swap(rootMoves[0], *std::find(rootMoves.begin(), rootMoves.end(),
skill.best ? skill.best : skill.pick_best(multiPV)));
@@ -528,10 +525,13 @@ namespace {
constexpr bool PvNode = nodeType != NonPV;
constexpr bool rootNode = nodeType == Root;
- // Check if we have an upcoming move which draws by repetition, or
+ // Dive into quiescence search when the depth reaches zero
+ if (depth <= 0)
+ return qsearch(pos, ss, alpha, beta);
+
+ // Check if we have an upcoming move that draws by repetition, or
// if the opponent had an alternative move earlier to this position.
if ( !rootNode
- && pos.rule50_count() >= 3
&& alpha < VALUE_DRAW
&& pos.has_game_cycle(ss->ply))
{
@@ -540,16 +540,12 @@ namespace {
return alpha;
}
- // Dive into quiescence search when the depth reaches zero
- if (depth <= 0)
- return qsearch(pos, ss, alpha, beta);
-
assert(-VALUE_INFINITE <= alpha && alpha < beta && beta <= VALUE_INFINITE);
assert(PvNode || (alpha == beta - 1));
assert(0 < depth && depth < MAX_PLY);
assert(!(PvNode && cutNode));
- Move pv[MAX_PLY+1], capturesSearched[32], quietsSearched[64];
+ Move pv[MAX_PLY+1], capturesSearched[32], quietsSearched[32];
StateInfo st;
ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize);
@@ -561,7 +557,7 @@ namespace {
bool givesCheck, improving, priorCapture, singularQuietLMR;
bool capture, moveCountPruning, ttCapture;
Piece movedPiece;
- int moveCount, captureCount, quietCount, improvement, complexity;
+ int moveCount, captureCount, quietCount;
// Step 1. Initialize node
Thread* thisThread = pos.this_thread();
@@ -577,7 +573,8 @@ namespace {
static_cast(thisThread)->check_time();
// Used to send selDepth info to GUI (selDepth counts from 1, ply from 0)
- if (PvNode && thisThread->selDepth < ss->ply + 1)
+ if ( PvNode
+ && thisThread->selDepth < ss->ply + 1)
thisThread->selDepth = ss->ply + 1;
if (!rootNode)
@@ -593,8 +590,8 @@ namespace {
// would be at best mate_in(ss->ply+1), but if alpha is already bigger because
// a shorter mate was found upward in the tree then there is no need to search
// because we will never beat the current alpha. Same logic but with reversed
- // signs applies also in the opposite condition of being mated instead of giving
- // mate. In this case return a fail-high score.
+ // signs apply also in the opposite condition of being mated instead of giving
+ // mate. In this case, return a fail-high score.
alpha = std::max(mated_in(ss->ply), alpha);
beta = std::min(mate_in(ss->ply+1), beta);
if (alpha >= beta)
@@ -628,10 +625,9 @@ namespace {
// At non-PV nodes we check for an early TT cutoff
if ( !PvNode
- && ss->ttHit
&& !excludedMove
- && tte->depth() > depth - (tte->bound() == BOUND_EXACT)
- && ttValue != VALUE_NONE // Possible in case of TT access race
+ && tte->depth() > depth
+ && ttValue != VALUE_NONE // Possible in case of TT access race or if !ttHit
&& (tte->bound() & (ttValue >= beta ? BOUND_LOWER : BOUND_UPPER)))
{
// If ttMove is quiet, update move sorting heuristics on TT hit (~2 Elo)
@@ -644,7 +640,9 @@ namespace {
update_quiet_stats(pos, ss, ttMove, stat_bonus(depth));
// Extra penalty for early quiet moves of the previous ply (~0 Elo on STC, ~2 Elo on LTC)
- if (prevSq != SQ_NONE && (ss-1)->moveCount <= 2 && !priorCapture)
+ if ( prevSq != SQ_NONE
+ && (ss-1)->moveCount <= 2
+ && !priorCapture)
update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + 1));
}
// Penalty for a quiet ttMove that fails low (~1 Elo)
@@ -722,29 +720,22 @@ namespace {
// Skip early pruning when in check
ss->staticEval = eval = VALUE_NONE;
improving = false;
- improvement = 0;
- complexity = 0;
goto moves_loop;
}
else if (excludedMove)
{
- // Providing the hint that this node's accumulator will be used often brings significant Elo gain (13 Elo)
+ // Providing the hint that this node's accumulator will be used often brings significant Elo gain (~13 Elo)
Eval::NNUE::hint_common_parent_position(pos);
eval = ss->staticEval;
- complexity = abs(ss->staticEval - pos.psq_eg_stm());
}
else if (ss->ttHit)
{
// Never assume anything about values stored in TT
ss->staticEval = eval = tte->eval();
if (eval == VALUE_NONE)
- ss->staticEval = eval = evaluate(pos, &complexity);
- else // Fall back to (semi)classical complexity for TT hits, the NNUE complexity is lost
- {
- complexity = abs(ss->staticEval - pos.psq_eg_stm());
- if (PvNode)
- Eval::NNUE::hint_common_parent_position(pos);
- }
+ ss->staticEval = eval = evaluate(pos);
+ else if (PvNode)
+ Eval::NNUE::hint_common_parent_position(pos);
// ttValue can be used as a better position evaluation (~7 Elo)
if ( ttValue != VALUE_NONE
@@ -753,61 +744,68 @@ namespace {
}
else
{
- ss->staticEval = eval = evaluate(pos, &complexity);
- // Save static evaluation into transposition table
+ ss->staticEval = eval = evaluate(pos);
+ // Save static evaluation into the transposition table
tte->save(posKey, VALUE_NONE, ss->ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval);
}
// Use static evaluation difference to improve quiet move ordering (~4 Elo)
- if (is_ok((ss-1)->currentMove) && !(ss-1)->inCheck && !priorCapture)
+ if ( is_ok((ss-1)->currentMove)
+ && !(ss-1)->inCheck
+ && !priorCapture)
{
- int bonus = std::clamp(-19 * int((ss-1)->staticEval + ss->staticEval), -1920, 1920);
+ int bonus = std::clamp(-18 * int((ss-1)->staticEval + ss->staticEval), -1812, 1812);
thisThread->mainHistory[~us][from_to((ss-1)->currentMove)] << bonus;
}
- // Set up the improvement variable, which is the difference between the current
- // static evaluation and the previous static evaluation at our turn (if we were
- // in check at our previous move we look at the move prior to it). The improvement
- // margin and the improving flag are used in various pruning heuristics.
- improvement = (ss-2)->staticEval != VALUE_NONE ? ss->staticEval - (ss-2)->staticEval
- : (ss-4)->staticEval != VALUE_NONE ? ss->staticEval - (ss-4)->staticEval
- : 156;
- improving = improvement > 0;
+ // Set up the improving flag, which is true if current static evaluation is
+ // bigger than the previous static evaluation at our turn (if we were in
+ // check at our previous move we look at static evaluation at move prior to it
+ // and if we were in check at move prior to it flag is set to true) and is
+ // false otherwise. The improving flag is used in various pruning heuristics.
+ improving = (ss-2)->staticEval != VALUE_NONE ? ss->staticEval > (ss-2)->staticEval
+ : (ss-4)->staticEval != VALUE_NONE ? ss->staticEval > (ss-4)->staticEval
+ : true;
- // Step 7. Razoring (~1 Elo).
+ // 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 - 426 - 256 * depth * depth)
+ // Adjust razor margin according to cutoffCnt. (~1 Elo)
+ if (eval < alpha - 492 - (257 - 200 * ((ss+1)->cutoffCnt > 3)) * depth * depth)
{
value = qsearch(pos, ss, alpha - 1, alpha);
if (value < alpha)
return value;
}
- // Step 8. Futility pruning: child node (~40 Elo).
+ // Step 8. Futility pruning: child node (~40 Elo)
// The depth condition is important for mate finding.
if ( !ss->ttPv
&& depth < 9
- && eval - futility_margin(depth, improving) - (ss-1)->statScore / 280 >= beta
+ && eval - futility_margin(depth, cutNode && !ss->ttHit, improving) - (ss-1)->statScore / 321 >= beta
&& eval >= beta
- && eval < 25128) // larger than VALUE_KNOWN_WIN, but smaller than TB wins
+ && eval < 29462 // smaller than TB wins
+ && !( !ttCapture
+ && ttMove
+ && thisThread->mainHistory[us][from_to(ttMove)] < 989))
return eval;
// Step 9. Null move search with verification search (~35 Elo)
if ( !PvNode
&& (ss-1)->currentMove != MOVE_NULL
- && (ss-1)->statScore < 18755
+ && (ss-1)->statScore < 17257
&& eval >= beta
&& eval >= ss->staticEval
- && ss->staticEval >= beta - 20 * depth - improvement / 13 + 253 + complexity / 25
+ && ss->staticEval >= beta - 24 * depth + 281
&& !excludedMove
&& pos.non_pawn_material(us)
- && (ss->ply >= thisThread->nmpMinPly))
+ && ss->ply >= thisThread->nmpMinPly
+ && beta > VALUE_TB_LOSS_IN_MAX_PLY)
{
assert(eval - beta >= 0);
- // Null move dynamic reduction based on depth, eval and complexity of position
- Depth R = std::min(int(eval - beta) / 172, 6) + depth / 3 + 4 - (complexity > 825);
+ // Null move dynamic reduction based on depth and eval
+ Depth R = std::min(int(eval - beta) / 152, 6) + depth / 3 + 4;
ss->currentMove = MOVE_NULL;
ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0];
@@ -818,13 +816,10 @@ namespace {
pos.undo_null_move();
- if (nullValue >= beta)
+ // Do not return unproven mate or TB scores
+ if (nullValue >= beta && nullValue < VALUE_TB_WIN_IN_MAX_PLY)
{
- // Do not return unproven mate or TB scores
- if (nullValue >= VALUE_TB_WIN_IN_MAX_PLY)
- nullValue = beta;
-
- if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 14))
+ if (thisThread->nmpMinPly || depth < 14)
return nullValue;
assert(!thisThread->nmpMinPly); // Recursive verification is not allowed
@@ -842,20 +837,34 @@ namespace {
}
}
- probCutBeta = beta + 186 - 54 * improving;
+ // Step 10. If the position doesn't have a ttMove, decrease depth by 2
+ // (or by 4 if the TT entry for the current position was hit and the stored depth is greater than or equal to the current depth).
+ // Use qsearch if depth is equal or below zero (~9 Elo)
+ if ( PvNode
+ && !ttMove)
+ depth -= 2 + 2 * (ss->ttHit && tte->depth() >= depth);
+
+ if (depth <= 0)
+ return qsearch(pos, ss, alpha, beta);
+
+ if ( cutNode
+ && depth >= 8
+ && !ttMove)
+ depth -= 2;
+
+ probCutBeta = beta + 168 - 70 * improving;
- // Step 10. ProbCut (~10 Elo)
+ // Step 11. ProbCut (~10 Elo)
// If we have a good enough capture (or queen promotion) and a reduced search returns a value
// much above beta, we can (almost) safely prune the previous move.
if ( !PvNode
- && depth > 4
+ && depth > 3
&& abs(beta) < VALUE_TB_WIN_IN_MAX_PLY
- // if value from transposition table is lower than probCutBeta, don't attempt probCut
+ // 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
- && !( ss->ttHit
- && tte->depth() >= depth - 3
+ // So effective depth is equal to depth - 3
+ && !( tte->depth() >= depth - 3
&& ttValue != VALUE_NONE
&& ttValue < probCutBeta))
{
@@ -896,37 +905,22 @@ namespace {
Eval::NNUE::hint_common_parent_position(pos);
}
- // Step 11. If the position is not in TT, decrease depth by 2 (or by 4 if the TT entry for the current position was hit and the stored depth is greater than or equal to the current depth).
- // Use qsearch if depth is equal or below zero (~9 Elo)
- if ( PvNode
- && !ttMove)
- depth -= 2 + 2 * (ss->ttHit && tte->depth() >= depth);
-
- if (depth <= 0)
- return qsearch(pos, ss, alpha, beta);
-
- if ( cutNode
- && depth >= 7
- && !ttMove)
- depth -= 2;
-
moves_loop: // When in check, search starts here
// Step 12. A small Probcut idea, when we are in check (~4 Elo)
- probCutBeta = beta + 391;
+ probCutBeta = beta + 416;
if ( ss->inCheck
&& !PvNode
- && depth >= 2
&& ttCapture
&& (tte->bound() & BOUND_LOWER)
- && tte->depth() >= depth - 3
+ && tte->depth() >= depth - 4
&& ttValue >= probCutBeta
- && abs(ttValue) <= VALUE_KNOWN_WIN
- && abs(beta) <= VALUE_KNOWN_WIN)
+ && abs(ttValue) < VALUE_TB_WIN_IN_MAX_PLY
+ && abs(beta) < VALUE_TB_WIN_IN_MAX_PLY)
return probCutBeta;
const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory,
- nullptr , (ss-4)->continuationHistory,
+ (ss-3)->continuationHistory, (ss-4)->continuationHistory,
nullptr , (ss-6)->continuationHistory };
Move countermove = prevSq != SQ_NONE ? thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] : MOVE_NONE;
@@ -941,7 +935,8 @@ moves_loop: // When in check, search starts here
moveCountPruning = singularQuietLMR = false;
// Indicate PvNodes that will probably fail low if the node was searched
- // at a depth equal or greater than the current depth, and the result of this search was a fail low.
+ // at a depth equal to or greater than the current depth, and the result
+ // of this search was a fail low.
bool likelyFailLow = PvNode
&& ttMove
&& (tte->bound() & BOUND_UPPER)
@@ -956,18 +951,17 @@ moves_loop: // When in check, search starts here
if (move == excludedMove)
continue;
+ // Check for legality
+ if (!pos.legal(move))
+ continue;
+
// At root obey the "searchmoves" option and skip moves not listed in Root
- // Move List. As a consequence any illegal move is also skipped. In MultiPV
- // mode we also skip PV moves which have been already searched and those
- // of lower "TB rank" if we are in a TB root position.
+ // Move List. In MultiPV mode we also skip PV moves that have been already
+ // searched and those of lower "TB rank" if we are in a TB root position.
if (rootNode && !std::count(thisThread->rootMoves.begin() + thisThread->pvIdx,
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)
@@ -989,51 +983,33 @@ moves_loop: // When in check, search starts here
Depth r = reduction(improving, depth, moveCount, delta, thisThread->rootDelta);
- // Step 14. Pruning at shallow depth (~120 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 (~8 Elo)
- moveCountPruning = moveCount >= futility_move_count(improving, depth);
+ if (!moveCountPruning)
+ moveCountPruning = moveCount >= futility_move_count(improving, depth);
// Reduced depth of the next LMR search
- int lmrDepth = std::max(newDepth - r, 0);
+ int lmrDepth = newDepth - r;
if ( capture
|| givesCheck)
{
// Futility pruning for captures (~2 Elo)
if ( !givesCheck
- && lmrDepth < 6
+ && lmrDepth < 7
&& !ss->inCheck
- && ss->staticEval + 182 + 230 * lmrDepth + PieceValue[EG][pos.piece_on(to_sq(move))]
+ && ss->staticEval + 188 + 206 * lmrDepth + PieceValue[pos.piece_on(to_sq(move))]
+ captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))] / 7 < alpha)
continue;
- Bitboard occupied;
- // SEE based pruning (~11 Elo)
- if (!pos.see_ge(move, occupied, Value(-206) * depth))
- {
- if (depth < 2 - capture)
- continue;
- // Don't prune the move if opp. King/Queen/Rook is attacked by a slider after the exchanges.
- // Since in see_ge we don't update occupied when the king recaptures, we also don't prune the
- // move when the opp. King gets a discovered slider attack DURING the exchanges.
- Bitboard leftEnemies = pos.pieces(~us, ROOK, QUEEN, KING) & occupied;
- Bitboard attacks = 0;
- occupied |= to_sq(move);
- while (leftEnemies && !attacks)
- {
- Square sq = pop_lsb(leftEnemies);
- attacks = pos.attackers_to(sq, occupied) & pos.pieces(us) & occupied;
- // Exclude Queen/Rook(s) which were already threatened before SEE
- if (attacks && sq != pos.square(~us) && (pos.attackers_to(sq, pos.pieces()) & pos.pieces(us)))
- attacks = 0;
- }
- if (!attacks)
- continue;
- }
+ // SEE based pruning for captures and checks (~11 Elo)
+ if (!pos.see_ge(move, Value(-185) * depth))
+ continue;
}
else
{
@@ -1042,25 +1018,25 @@ moves_loop: // When in check, search starts here
+ (*contHist[3])[movedPiece][to_sq(move)];
// Continuation history based pruning (~2 Elo)
- if ( lmrDepth < 5
- && history < -4405 * (depth - 1))
+ if ( lmrDepth < 6
+ && history < -3232 * depth)
continue;
history += 2 * thisThread->mainHistory[us][from_to(move)];
- lmrDepth += history / 7278;
+ lmrDepth += history / 5793;
lmrDepth = std::max(lmrDepth, -2);
// Futility pruning: parent node (~13 Elo)
if ( !ss->inCheck
&& lmrDepth < 13
- && ss->staticEval + 103 + 138 * lmrDepth <= alpha)
+ && ss->staticEval + 115 + 122 * lmrDepth <= alpha)
continue;
lmrDepth = std::max(lmrDepth, 0);
// Prune moves with negative SEE (~4 Elo)
- if (!pos.see_ge(move, Value(-24 * lmrDepth * lmrDepth - 16 * lmrDepth)))
+ if (!pos.see_ge(move, Value(-27 * lmrDepth * lmrDepth)))
continue;
}
}
@@ -1072,18 +1048,20 @@ moves_loop: // When in check, search starts here
// 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
- // result is lower than ttValue minus a margin, then we will extend the ttMove.
+ // 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. Note
+ // that depth margin and singularBeta margin are known for having non-linear
+ // scaling. Their values are optimized to time controls of 180+1.8 and longer
+ // so changing them requires tests at this type of time controls.
if ( !rootNode
- && depth >= 4 - (thisThread->completedDepth > 21) + 2 * (PvNode && tte->is_pv())
+ && depth >= 4 - (thisThread->completedDepth > 24) + 2 * (PvNode && tte->is_pv())
&& move == ttMove
&& !excludedMove // Avoid recursive singular search
- /* && ttValue != VALUE_NONE Already implicit in the next condition */
- && abs(ttValue) < VALUE_KNOWN_WIN
+ && abs(ttValue) < VALUE_TB_WIN_IN_MAX_PLY
&& (tte->bound() & BOUND_LOWER)
&& tte->depth() >= depth - 3)
{
- Value singularBeta = ttValue - (3 + 2 * (ss->ttPv && !PvNode)) * depth / 2;
+ Value singularBeta = ttValue - (64 + 57 * (ss->ttPv && !PvNode)) * depth / 64;
Depth singularDepth = (depth - 1) / 2;
ss->excludedMove = move;
@@ -1097,19 +1075,19 @@ moves_loop: // When in check, search starts here
// Avoid search explosion by limiting the number of double extensions
if ( !PvNode
- && value < singularBeta - 25
- && ss->doubleExtensions <= 10)
+ && value < singularBeta - 18
+ && ss->doubleExtensions <= 11)
{
extension = 2;
- depth += depth < 13;
+ depth += depth < 15;
}
}
// Multi-cut pruning
- // Our ttMove is assumed to fail high, and now we failed high also on a reduced
- // search without the ttMove. So we assume this expected Cut-node is not singular,
- // that multiple moves fail high, and we can prune the whole subtree by returning
- // a soft bound.
+ // Our ttMove is assumed to fail high, and now we failed high also on a
+ // reduced search without the ttMove. So we assume this expected cut-node
+ // is not singular, that multiple moves fail high, and we can prune the
+ // whole subtree by returning a softbound.
else if (singularBeta >= beta)
return singularBeta;
@@ -1117,26 +1095,25 @@ moves_loop: // When in check, search starts here
else if (ttValue >= beta)
extension = -2 - !PvNode;
+ // If we are on a cutNode, reduce it based on depth (negative extension) (~1 Elo)
+ else if (cutNode)
+ extension = depth < 19 ? -2 : -1;
+
// If the eval of ttMove is less than value, we reduce it (negative extension) (~1 Elo)
else if (ttValue <= value)
extension = -1;
-
- // If the eval of ttMove is less than alpha, we reduce it (negative extension) (~1 Elo)
- else if (ttValue <= alpha)
- extension = -1;
}
// Check extensions (~1 Elo)
else if ( givesCheck
- && depth > 10
- && abs(ss->staticEval) > 88)
+ && depth > 9)
extension = 1;
// Quiet ttMove extensions (~1 Elo)
else if ( PvNode
&& move == ttMove
&& move == ss->killers[0]
- && (*contHist[0])[movedPiece][to_sq(move)] >= 5705)
+ && (*contHist[0])[movedPiece][to_sq(move)] >= 4194)
extension = 1;
}
@@ -1157,11 +1134,10 @@ moves_loop: // When in check, search starts here
// Step 16. Make the move
pos.do_move(move, st, givesCheck);
- // Decrease reduction if position is or has been on the PV
- // and node is not likely to fail low. (~3 Elo)
+ // Decrease reduction if position is or has been on the PV (~4 Elo)
if ( ss->ttPv
&& !likelyFailLow)
- r -= 2;
+ r -= cutNode && tte->depth() >= depth ? 3 : 2;
// Decrease reduction if opponent's move count is high (~1 Elo)
if ((ss-1)->moveCount > 7)
@@ -1175,30 +1151,39 @@ moves_loop: // When in check, search starts here
if (ttCapture)
r++;
- // Decrease reduction for PvNodes based on depth (~2 Elo)
+ // Decrease reduction for PvNodes (~2 Elo)
if (PvNode)
- r -= 1 + 12 / (3 + depth);
+ r--;
// Decrease reduction if ttMove has been singularly extended (~1 Elo)
if (singularQuietLMR)
r--;
+ // Increase reduction on repetition (~1 Elo)
+ if ( move == (ss-4)->currentMove
+ && pos.has_repeated())
+ r += 2;
+
// Increase reduction if next ply has a lot of fail high (~5 Elo)
if ((ss+1)->cutoffCnt > 3)
r++;
+ // Decrease reduction for first generated move (ttMove)
+ else if (move == ttMove)
+ 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)]
- - 4082;
+ - 3848;
// Decrease/increase reduction for moves with a good/bad history (~25 Elo)
- r -= ss->statScore / (11079 + 4626 * (depth > 6 && depth < 19));
+ r -= ss->statScore / (10216 + 3855 * (depth > 5 && depth < 23));
// 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
+ // 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)
@@ -1213,13 +1198,14 @@ moves_loop: // When in check, search starts here
value = -search(pos, ss+1, -(alpha+1), -alpha, d, true);
- // Do full depth search when reduced LMR search fails high
- if (value > alpha && d < newDepth)
+ // Do a full-depth search when reduced LMR search fails high
+ if ( value > alpha
+ && d < newDepth)
{
- // 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 + 58 + 12 * (newDepth - d));
- const bool doEvenDeeperSearch = value > alpha + 588 && ss->doubleExtensions <= 5;
+ // Adjust full-depth search based on LMR results - if the result
+ // was good enough search deeper, if it was bad enough search shallower.
+ const bool doDeeperSearch = value > (bestValue + 51 + 10 * (newDepth - d));
+ const bool doEvenDeeperSearch = value > alpha + 700 && ss->doubleExtensions <= 6;
const bool doShallowerSearch = value < bestValue + newDepth;
ss->doubleExtensions = ss->doubleExtensions + doEvenDeeperSearch;
@@ -1229,35 +1215,35 @@ moves_loop: // When in check, search starts here
if (newDepth > d)
value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode);
- int bonus = value > alpha ? stat_bonus(newDepth)
- : -stat_bonus(newDepth);
+ int bonus = value <= alpha ? -stat_bonus(newDepth)
+ : value >= beta ? stat_bonus(newDepth)
+ : 0;
update_continuation_histories(ss, movedPiece, to_sq(move), bonus);
}
}
- // Step 18. Full depth search when LMR is skipped. If expected reduction is high, reduce its depth by 1.
+ // Step 18. Full-depth search when LMR is skipped
else if (!PvNode || moveCount > 1)
{
// Increase reduction for cut nodes and not ttMove (~1 Elo)
- if (!ttMove && cutNode)
+ if ( !ttMove
+ && cutNode)
r += 2;
- value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth - (r > 4), !cutNode);
+ // Note that if expected reduction is high, we reduce search depth by 1 here
+ value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth - (r > 3), !cutNode);
}
- // For PV nodes only, do a full PV search on the first move or after a fail
- // high (in the latter case search only if value < beta), otherwise let the
- // parent node fail low with value <= alpha and try another move.
- if (PvNode && (moveCount == 1 || (value > alpha && (rootNode || value < beta))))
+ // For PV nodes only, do a full PV search on the first move or after a fail high,
+ // otherwise let the parent node fail low with value <= alpha and try another move.
+ if ( PvNode
+ && (moveCount == 1 || value > alpha))
{
(ss+1)->pv = pv;
(ss+1)->pv[0] = MOVE_NONE;
value = -search(pos, ss+1, -beta, -alpha, newDepth, false);
-
- if (moveCount > 1 && newDepth >= depth && !capture)
- update_continuation_histories(ss, movedPiece, to_sq(move), -stat_bonus(newDepth));
}
// Step 19. Undo move
@@ -1312,7 +1298,7 @@ moves_loop: // When in check, search starts here
++thisThread->bestMoveChanges;
}
else
- // All other moves but the PV are set to the lowest value: this
+ // All other moves but the PV, are set to the lowest value: this
// is not a problem when sorting because the sort is stable and the
// move position in the list is preserved - just the PV is pushed up.
rm.score = -VALUE_INFINITE;
@@ -1329,49 +1315,39 @@ moves_loop: // When in check, search starts here
if (PvNode && !rootNode) // Update pv even in fail-high case
update_pv(ss->pv, move, (ss+1)->pv);
- if (PvNode && value < beta) // Update alpha! Always alpha < beta
+ if (value >= beta)
{
- // Reduce other moves if we have found at least one score improvement (~1 Elo)
- if ( depth > 1
- && ( (improving && complexity > 971)
- || value < (5 * alpha + 75 * beta) / 87
- || depth < 6)
- && beta < 12535
- && value > -12535)
- depth -= 1;
-
- assert(depth > 0);
- alpha = value;
+ ss->cutoffCnt += 1 + !ttMove;
+ assert(value >= beta); // Fail high
+ break;
}
else
{
- ss->cutoffCnt++;
- assert(value >= beta); // Fail high
- break;
+ // Reduce other moves if we have found at least one score improvement (~2 Elo)
+ if ( depth > 2
+ && depth < 12
+ && beta < 13828
+ && value > -11369)
+ depth -= 2;
+
+ assert(depth > 0);
+ alpha = value; // Update alpha! Always alpha < beta
}
}
}
-
- // If the move is worse than some previously searched move, remember it to update its stats later
- if (move != bestMove)
+ // If the move is worse than some previously searched move,
+ // remember it, to update its stats later.
+ if (move != bestMove && moveCount <= 32)
{
- if (capture && captureCount < 32)
+ if (capture)
capturesSearched[captureCount++] = move;
- else if (!capture && quietCount < 64)
+ else
quietsSearched[quietCount++] = move;
}
}
- // The following condition would detect a stop only after move loop has been
- // completed. But in this case bestValue is valid because we have fully
- // searched our subtree, and we can anyhow save the result in TT.
- /*
- if (Threads.stop)
- return VALUE_DRAW;
- */
-
// Step 21. 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
@@ -1384,7 +1360,7 @@ moves_loop: // When in check, search starts here
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
+ // If there is a move that produces search value greater than alpha we update the stats of searched moves
else if (bestMove)
update_all_stats(pos, ss, bestMove, bestValue, beta, prevSq,
quietsSearched, quietCount, capturesSearched, captureCount, depth);
@@ -1392,8 +1368,9 @@ moves_loop: // When in check, search starts here
// Bonus for prior countermove that caused the fail low
else if (!priorCapture && prevSq != SQ_NONE)
{
- int bonus = (depth > 5) + (PvNode || cutNode) + (bestValue < alpha - 97 * depth) + ((ss-1)->moveCount > 10);
+ int bonus = (depth > 6) + (PvNode || cutNode) + (bestValue < alpha - 653) + ((ss-1)->moveCount > 11);
update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * bonus);
+ thisThread->mainHistory[~us][from_to((ss-1)->currentMove)] << stat_bonus(depth) * bonus / 2;
}
if (PvNode)
@@ -1430,6 +1407,16 @@ moves_loop: // When in check, search starts here
assert(PvNode || (alpha == beta - 1));
assert(depth <= 0);
+ // Check if we have an upcoming move that draws by repetition, or
+ // if the opponent had an alternative move earlier to this position.
+ if ( alpha < VALUE_DRAW
+ && pos.has_game_cycle(ss->ply))
+ {
+ alpha = value_draw(pos.this_thread());
+ if (alpha >= beta)
+ return alpha;
+ }
+
Move pv[MAX_PLY+1];
StateInfo st;
ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize);
@@ -1441,6 +1428,7 @@ moves_loop: // When in check, search starts here
Value bestValue, value, ttValue, futilityValue, futilityBase;
bool pvHit, givesCheck, capture;
int moveCount;
+ Color us = pos.side_to_move();
// Step 1. Initialize node
if (PvNode)
@@ -1476,18 +1464,14 @@ moves_loop: // When in check, search starts here
// At non-PV nodes we check for an early TT cutoff
if ( !PvNode
- && ss->ttHit
&& tte->depth() >= ttDepth
- && ttValue != VALUE_NONE // Only in case of TT access race
+ && ttValue != VALUE_NONE // Only in case of TT access race or if !ttHit
&& (tte->bound() & (ttValue >= beta ? BOUND_LOWER : BOUND_UPPER)))
return ttValue;
// Step 4. Static evaluation of the position
if (ss->inCheck)
- {
- ss->staticEval = VALUE_NONE;
bestValue = futilityBase = -VALUE_INFINITE;
- }
else
{
if (ss->ttHit)
@@ -1503,14 +1487,12 @@ moves_loop: // When in check, search starts here
}
else
// In case of null move search use previous static eval with a different sign
- ss->staticEval = bestValue =
- (ss-1)->currentMove != MOVE_NULL ? evaluate(pos)
- : -(ss-1)->staticEval;
+ ss->staticEval = bestValue = (ss-1)->currentMove != MOVE_NULL ? evaluate(pos)
+ : -(ss-1)->staticEval;
// Stand pat. Return immediately if static value is at least beta
if (bestValue >= beta)
{
- // Save gathered info in transposition table
if (!ss->ttHit)
tte->save(posKey, value_to_tt(bestValue, ss->ply), false, BOUND_LOWER,
DEPTH_NONE, MOVE_NONE, ss->staticEval);
@@ -1518,21 +1500,21 @@ moves_loop: // When in check, search starts here
return bestValue;
}
- if (PvNode && bestValue > alpha)
+ if (bestValue > alpha)
alpha = bestValue;
- futilityBase = bestValue + 168;
+ futilityBase = std::min(ss->staticEval, bestValue) + 200;
}
const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory,
- nullptr , (ss-4)->continuationHistory,
+ (ss-3)->continuationHistory, (ss-4)->continuationHistory,
nullptr , (ss-6)->continuationHistory };
// 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 other checks (only if depth >= DEPTH_QS_CHECKS)
// will be generated.
- Square prevSq = (ss-1)->currentMove != MOVE_NULL ? to_sq((ss-1)->currentMove) : SQ_NONE;
+ Square prevSq = is_ok((ss-1)->currentMove) ? to_sq((ss-1)->currentMove) : SQ_NONE;
MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory,
&thisThread->captureHistory,
contHist,
@@ -1544,97 +1526,112 @@ moves_loop: // When in check, search starts here
// or a beta cutoff occurs.
while ((move = mp.next_move()) != MOVE_NONE)
{
- assert(is_ok(move));
+ assert(is_ok(move));
- // Check for legality
- if (!pos.legal(move))
- continue;
+ // Check for legality
+ if (!pos.legal(move))
+ continue;
- givesCheck = pos.gives_check(move);
- capture = pos.capture_stage(move);
+ givesCheck = pos.gives_check(move);
+ capture = pos.capture_stage(move);
- moveCount++;
+ moveCount++;
- // Step 6. Pruning.
- if (bestValue > VALUE_TB_LOSS_IN_MAX_PLY)
- {
- // Futility pruning and moveCount pruning (~10 Elo)
- if ( !givesCheck
- && to_sq(move) != prevSq
- && futilityBase > -VALUE_KNOWN_WIN
- && type_of(move) != PROMOTION)
- {
- if (moveCount > 2)
- continue;
-
- futilityValue = futilityBase + PieceValue[EG][pos.piece_on(to_sq(move))];
+ // Step 6. Pruning
+ if ( bestValue > VALUE_TB_LOSS_IN_MAX_PLY
+ && pos.non_pawn_material(us))
+ {
+ // Futility pruning and moveCount pruning (~10 Elo)
+ if ( !givesCheck
+ && to_sq(move) != prevSq
+ && futilityBase > VALUE_TB_LOSS_IN_MAX_PLY
+ && type_of(move) != PROMOTION)
+ {
+ if (moveCount > 2)
+ continue;
- if (futilityValue <= alpha)
- {
- bestValue = std::max(bestValue, futilityValue);
- continue;
- }
+ futilityValue = futilityBase + PieceValue[pos.piece_on(to_sq(move))];
- if (futilityBase <= alpha && !pos.see_ge(move, VALUE_ZERO + 1))
- {
- bestValue = std::max(bestValue, futilityBase);
- continue;
- }
- }
+ // If static eval + value of piece we are going to capture is much lower
+ // than alpha we can prune this move.
+ if (futilityValue <= alpha)
+ {
+ bestValue = std::max(bestValue, futilityValue);
+ continue;
+ }
- // 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 (quietCheckEvasions > 1)
- break;
+ // If static eval is much lower than alpha and move is not winning material
+ // we can prune this move.
+ if ( futilityBase <= alpha
+ && !pos.see_ge(move, VALUE_ZERO + 1))
+ {
+ bestValue = std::max(bestValue, futilityBase);
+ continue;
+ }
- // Continuation history based pruning (~3 Elo)
- if ( !capture
- && (*contHist[0])[pos.moved_piece(move)][to_sq(move)] < 0
- && (*contHist[1])[pos.moved_piece(move)][to_sq(move)] < 0)
- continue;
+ // If static exchange evaluation is much worse than what is needed to not
+ // fall below alpha we can prune this move.
+ if (futilityBase > alpha && !pos.see_ge(move, (alpha - futilityBase) * 4))
+ {
+ bestValue = alpha;
+ continue;
+ }
+ }
- // Do not search moves with bad enough SEE values (~5 Elo)
- if (!pos.see_ge(move, Value(-110)))
- continue;
- }
+ // We prune after the second quiet check evasion move, where being 'in check' is
+ // implicitly checked through the counter, and being a 'quiet move' apart from
+ // being a tt move is assumed after an increment because captures are pushed ahead.
+ if (quietCheckEvasions > 1)
+ break;
+
+ // Continuation history based pruning (~3 Elo)
+ if ( !capture
+ && (*contHist[0])[pos.moved_piece(move)][to_sq(move)] < 0
+ && (*contHist[1])[pos.moved_piece(move)][to_sq(move)] < 0)
+ continue;
+
+ // Do not search moves with bad enough SEE values (~5 Elo)
+ if (!pos.see_ge(move, Value(-90)))
+ continue;
+ }
- // Speculative prefetch as early as possible
- prefetch(TT.first_entry(pos.key_after(move)));
+ // Speculative prefetch as early as possible
+ prefetch(TT.first_entry(pos.key_after(move)));
- // Update the current move
- ss->currentMove = move;
- ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck]
- [capture]
- [pos.moved_piece(move)]
- [to_sq(move)];
+ // Update the current move
+ ss->currentMove = move;
+ ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck]
+ [capture]
+ [pos.moved_piece(move)]
+ [to_sq(move)];
- quietCheckEvasions += !capture && ss->inCheck;
+ quietCheckEvasions += !capture && ss->inCheck;
- // Step 7. Make and search the move
- pos.do_move(move, st, givesCheck);
- value = -qsearch(pos, ss+1, -beta, -alpha, depth - 1);
- pos.undo_move(move);
+ // Step 7. Make and search the move
+ pos.do_move(move, st, givesCheck);
+ value = -qsearch(pos, ss+1, -beta, -alpha, depth - 1);
+ pos.undo_move(move);
- assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
+ assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
- // Step 8. Check for a new best move
- if (value > bestValue)
- {
- bestValue = value;
+ // Step 8. Check for a new best move
+ if (value > bestValue)
+ {
+ bestValue = value;
- if (value > alpha)
- {
- bestMove = move;
+ if (value > alpha)
+ {
+ bestMove = move;
- if (PvNode) // Update pv even in fail-high case
- update_pv(ss->pv, move, (ss+1)->pv);
+ if (PvNode) // Update pv even in fail-high case
+ update_pv(ss->pv, move, (ss+1)->pv);
- if (PvNode && value < beta) // Update alpha here!
- alpha = value;
- else
- break; // Fail high
- }
- }
+ if (value < beta) // Update alpha here!
+ alpha = value;
+ else
+ break; // Fail high
+ }
+ }
}
// Step 9. Check for mate
@@ -1658,8 +1655,8 @@ moves_loop: // When in check, search starts 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.
+ // 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.
// The function is called before storing a value in the transposition table.
Value value_to_tt(Value v, int ply) {
@@ -1673,9 +1670,9 @@ moves_loop: // When in check, search starts 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, we return an optimal TB score instead.
+ // current position) to "plies to mate/be mated (TB win/loss) from the root".
+ // However, to avoid potentially false mate scores related to the 50 moves rule
+ // and the graph history interaction problem, we return an optimal TB score instead.
Value value_from_tt(Value v, int ply, int r50c) {
@@ -1723,28 +1720,28 @@ moves_loop: // When in check, search starts here
Piece moved_piece = pos.moved_piece(bestMove);
PieceType captured;
- int bonus1 = stat_bonus(depth + 1);
+ int quietMoveBonus = stat_bonus(depth + 1);
if (!pos.capture_stage(bestMove))
{
- int bonus2 = bestValue > beta + 153 ? bonus1 // larger bonus
- : stat_bonus(depth); // smaller bonus
+ int bestMoveBonus = bestValue > beta + 168 ? quietMoveBonus // larger bonus
+ : stat_bonus(depth); // smaller bonus
// Increase stats for the best move in case it was a quiet move
- update_quiet_stats(pos, ss, bestMove, bonus2);
+ update_quiet_stats(pos, ss, bestMove, bestMoveBonus);
// Decrease stats for all 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);
+ thisThread->mainHistory[us][from_to(quietsSearched[i])] << -bestMoveBonus;
+ update_continuation_histories(ss, pos.moved_piece(quietsSearched[i]), to_sq(quietsSearched[i]), -bestMoveBonus);
}
}
else
{
// Increase stats for the best move in case it was a capture move
captured = type_of(pos.piece_on(to_sq(bestMove)));
- captureHistory[moved_piece][to_sq(bestMove)][captured] << bonus1;
+ captureHistory[moved_piece][to_sq(bestMove)][captured] << quietMoveBonus;
}
// Extra penalty for a quiet early move that was not a TT move or
@@ -1752,14 +1749,14 @@ moves_loop: // When in check, search starts here
if ( prevSq != SQ_NONE
&& ((ss-1)->moveCount == 1 + (ss-1)->ttHit || ((ss-1)->currentMove == (ss-1)->killers[0]))
&& !pos.captured_piece())
- update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -bonus1);
+ update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -quietMoveBonus);
// Decrease stats for all 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;
+ captureHistory[moved_piece][to_sq(capturesSearched[i])][captured] << -quietMoveBonus;
}
}
@@ -1769,13 +1766,13 @@ moves_loop: // When in check, search starts here
void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus) {
- for (int i : {1, 2, 4, 6})
+ for (int i : {1, 2, 3, 4, 6})
{
- // Only update first 2 continuation histories if we are in check
+ // Only update the first 2 continuation histories if we are in check
if (ss->inCheck && i > 2)
break;
if (is_ok((ss-i)->currentMove))
- (*(ss-i)->continuationHistory)[pc][to] << bonus;
+ (*(ss-i)->continuationHistory)[pc][to] << bonus / (1 + 3 * (i == 3));
}
}
@@ -1804,7 +1801,7 @@ moves_loop: // When in check, search starts here
}
}
- // When playing with strength handicap, choose best move among a set of RootMoves
+ // When playing with strength handicap, choose the best move among a set of RootMoves
// using a statistical rule dependent on 'level'. Idea by Heinz van Saanen.
Move Skill::pick_best(size_t multiPV) {
@@ -1814,7 +1811,7 @@ moves_loop: // When in check, search starts here
// RootMoves are already sorted by score in descending order
Value topScore = rootMoves[0].score;
- int delta = std::min(topScore - rootMoves[multiPV - 1].score, PawnValueMg);
+ int delta = std::min(topScore - rootMoves[multiPV - 1].score, PawnValue);
int maxScore = -VALUE_INFINITE;
double weakness = 120 - 2 * level;
@@ -1840,8 +1837,8 @@ moves_loop: // When in check, search starts 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.
+// 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.
void MainThread::check_time() {
@@ -1849,7 +1846,7 @@ void MainThread::check_time() {
return;
// When using nodes, ensure checking rate is not lower than 0.1% of nodes
- callsCnt = Limits.nodes ? std::min(1024, int(Limits.nodes / 1024)) : 1024;
+ callsCnt = Limits.nodes ? std::min(512, int(Limits.nodes / 1024)) : 512;
static TimePoint lastInfoTime = now();
@@ -1866,15 +1863,15 @@ void MainThread::check_time() {
if (ponder)
return;
- if ( (Limits.use_time_management() && (elapsed > Time.maximum() - 10 || stopOnPonderhit))
+ if ( (Limits.use_time_management() && (elapsed > Time.maximum() || stopOnPonderhit))
|| (Limits.movetime && elapsed >= Limits.movetime)
- || (Limits.nodes && Threads.nodes_searched() >= (uint64_t)Limits.nodes))
+ || (Limits.nodes && Threads.nodes_searched() >= uint64_t(Limits.nodes)))
Threads.stop = true;
}
-/// 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.
+// 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) {
@@ -1882,7 +1879,7 @@ string UCI::pv(const Position& pos, Depth depth) {
TimePoint elapsed = Time.elapsed() + 1;
const RootMoves& rootMoves = pos.this_thread()->rootMoves;
size_t pvIdx = pos.this_thread()->pvIdx;
- size_t multiPV = std::min((size_t)Options["MultiPV"], rootMoves.size());
+ size_t multiPV = std::min(size_t(Options["MultiPV"]), rootMoves.size());
uint64_t nodesSearched = Threads.nodes_searched();
uint64_t tbHits = Threads.tb_hits() + (TB::RootInTB ? rootMoves.size() : 0);
@@ -1932,10 +1929,10 @@ string UCI::pv(const Position& pos, Depth depth) {
}
-/// RootMove::extract_ponder_from_tt() is called in case we have no ponder move
-/// before exiting the search, for instance, in case we stop the search during a
-/// fail high at root. We try hard to have a ponder move to return to the GUI,
-/// otherwise in case of 'ponder on' we have nothing to think on.
+// RootMove::extract_ponder_from_tt() is called in case we have no ponder move
+// before exiting the search, for instance, in case we stop the search during a
+// fail high at root. We try hard to have a ponder move to return to the GUI,
+// otherwise in case of 'ponder on' we have nothing to think about.
bool RootMove::extract_ponder_from_tt(Position& pos) {