Depth reduction(bool i, Depth d, int mn, Value delta, Value rootDelta) {
int reductionScale = Reductions[d] * Reductions[mn];
Depth reduction(bool i, Depth d, int mn, Value delta, Value rootDelta) {
int reductionScale = Reductions[d] * Reductions[mn];
- return (reductionScale + 1487 - int(delta) * 976 / int(rootDelta)) / 1024
- + (!i && reductionScale > 808);
+ return (reductionScale + 1346 - int(delta) * 896 / int(rootDelta)) / 1024
+ + (!i && reductionScale > 880);
// Add a small random component to draw evaluations to avoid 3-fold blindness
Value value_draw(const Thread* thisThread) {
// Add a small random component to draw evaluations to avoid 3-fold blindness
Value value_draw(const Thread* thisThread) {
alpha = std::max(avg - delta, -VALUE_INFINITE);
beta = std::min(avg + delta, VALUE_INFINITE);
// Adjust optimism based on root move's averageScore (~4 Elo)
alpha = std::max(avg - delta, -VALUE_INFINITE);
beta = std::min(avg + delta, VALUE_INFINITE);
// Adjust optimism based on root move's averageScore (~4 Elo)
// 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
// 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
{
double fallingEval = (66 + 14 * (mainThread->bestPreviousAverageScore - bestValue)
+ 6 * (mainThread->iterValue[iterIdx] - bestValue))
{
double fallingEval = (66 + 14 * (mainThread->bestPreviousAverageScore - bestValue)
+ 6 * (mainThread->iterValue[iterIdx] - bestValue))
// If the bestMove is stable over several iterations, reduce time accordingly
timeReduction = lastBestMoveDepth + 8 < completedDepth ? 1.56 : 0.69;
// If the bestMove is stable over several iterations, reduce time accordingly
timeReduction = lastBestMoveDepth + 8 < completedDepth ? 1.56 : 0.69;
double bestMoveInstability = 1 + 1.79 * totBestMoveChanges / Threads.size();
double totalTime = Time.optimum() * fallingEval * reduction * bestMoveInstability;
double bestMoveInstability = 1 + 1.79 * totBestMoveChanges / Threads.size();
double totalTime = Time.optimum() * fallingEval * reduction * bestMoveInstability;
- // use the range VALUE_MATE_IN_MAX_PLY to VALUE_TB_WIN_IN_MAX_PLY to score
- value = wdl < -drawScore ? VALUE_MATED_IN_MAX_PLY + ss->ply + 1
- : wdl > drawScore ? VALUE_MATE_IN_MAX_PLY - ss->ply - 1
+ Value tbValue = VALUE_TB - ss->ply;
+
+ // use the range VALUE_TB to VALUE_TB_WIN_IN_MAX_PLY to score
+ value = wdl < -drawScore ? -tbValue
+ : wdl > drawScore ? tbValue
// Use static evaluation difference to improve quiet move ordering (~4 Elo)
if (is_ok((ss - 1)->currentMove) && !(ss - 1)->inCheck && !priorCapture)
{
// Use static evaluation difference to improve quiet move ordering (~4 Elo)
if (is_ok((ss - 1)->currentMove) && !(ss - 1)->inCheck && !priorCapture)
{
thisThread->mainHistory[~us][from_to((ss - 1)->currentMove)] << bonus;
if (type_of(pos.piece_on(prevSq)) != PAWN && type_of((ss - 1)->currentMove) != PROMOTION)
thisThread->pawnHistory[pawn_structure(pos)][pos.piece_on(prevSq)][prevSq] << bonus / 4;
thisThread->mainHistory[~us][from_to((ss - 1)->currentMove)] << bonus;
if (type_of(pos.piece_on(prevSq)) != PAWN && type_of((ss - 1)->currentMove) != PROMOTION)
thisThread->pawnHistory[pawn_structure(pos)][pos.piece_on(prevSq)][prevSq] << bonus / 4;
// If eval is really low check with qsearch if it can exceed alpha, if it can't,
// return a fail low.
// Adjust razor margin according to cutoffCnt. (~1 Elo)
// If eval is really low check with qsearch if it can exceed alpha, if it can't,
// return a fail low.
// Adjust razor margin according to cutoffCnt. (~1 Elo)
{
value = qsearch<NonPV>(pos, ss, alpha - 1, alpha);
if (value < alpha)
{
value = qsearch<NonPV>(pos, ss, alpha - 1, alpha);
if (value < alpha)
// The depth condition is important for mate finding.
if (!ss->ttPv && depth < 9
&& eval - futility_margin(depth, cutNode && !ss->ttHit, improving)
// The depth condition is important for mate finding.
if (!ss->ttPv && depth < 9
&& eval - futility_margin(depth, cutNode && !ss->ttHit, improving)
- if (!PvNode && (ss - 1)->currentMove != MOVE_NULL && (ss - 1)->statScore < 17257 && eval >= beta
- && eval >= ss->staticEval && ss->staticEval >= beta - 24 * depth + 281 && !excludedMove
+ if (!PvNode && (ss - 1)->currentMove != MOVE_NULL && (ss - 1)->statScore < 17496 && eval >= beta
+ && eval >= ss->staticEval && ss->staticEval >= beta - 23 * depth + 304 && !excludedMove
&& pos.non_pawn_material(us) && ss->ply >= thisThread->nmpMinPly
&& beta > VALUE_TB_LOSS_IN_MAX_PLY)
{
assert(eval - beta >= 0);
// Null move dynamic reduction based on depth and eval
&& pos.non_pawn_material(us) && ss->ply >= thisThread->nmpMinPly
&& beta > VALUE_TB_LOSS_IN_MAX_PLY)
{
assert(eval - beta >= 0);
// Null move dynamic reduction based on depth and eval
ss->currentMove = MOVE_NULL;
ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0];
ss->currentMove = MOVE_NULL;
ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0];
// 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 >= beta && nullValue < VALUE_TB_WIN_IN_MAX_PLY)
{
if (depth <= 0)
return qsearch<PV>(pos, ss, alpha, beta);
if (depth <= 0)
return qsearch<PV>(pos, ss, alpha, beta);
// 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 > 3
// 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 > 3
// 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
// 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
moves_loop: // When in check, search starts here
// Step 12. A small Probcut idea, when we are in check (~4 Elo)
moves_loop: // When in check, search starts here
// Step 12. A small Probcut idea, when we are in check (~4 Elo)
if (ss->inCheck && !PvNode && ttCapture && (tte->bound() & BOUND_LOWER)
&& tte->depth() >= depth - 4 && ttValue >= probCutBeta
if (ss->inCheck && !PvNode && ttCapture && (tte->bound() & BOUND_LOWER)
&& tte->depth() >= depth - 4 && ttValue >= probCutBeta
+ captureHistory[movedPiece][to_sq(move)][type_of(capturedPiece)] / 7;
if (futilityEval < alpha)
continue;
}
// SEE based pruning for captures and checks (~11 Elo)
+ captureHistory[movedPiece][to_sq(move)][type_of(capturedPiece)] / 7;
if (futilityEval < alpha)
continue;
}
// SEE based pruning for captures and checks (~11 Elo)
+ thisThread->pawnHistory[pawn_structure(pos)][movedPiece][to_sq(move)];
// Continuation history based pruning (~2 Elo)
+ thisThread->pawnHistory[pawn_structure(pos)][movedPiece][to_sq(move)];
// Continuation history based pruning (~2 Elo)
lmrDepth = std::max(lmrDepth, -1);
// Futility pruning: parent node (~13 Elo)
lmrDepth = std::max(lmrDepth, -1);
// Futility pruning: parent node (~13 Elo)
- if (!ss->inCheck && lmrDepth < 13
- && ss->staticEval + (bestValue < ss->staticEval - 62 ? 123 : 77)
- + 127 * lmrDepth
+ if (!ss->inCheck && lmrDepth < 14
+ && ss->staticEval + (bestValue < ss->staticEval - 57 ? 124 : 71)
+ + 118 * lmrDepth
// Note: the 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
// Note: the 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
- && depth >= 4 - (thisThread->completedDepth > 24) + 2 * (PvNode && tte->is_pv())
- && abs(ttValue) < VALUE_TB_WIN_IN_MAX_PLY && (tte->bound() & BOUND_LOWER)
+ && depth >= 4 - (thisThread->completedDepth > 27) + 2 * (PvNode && tte->is_pv())
+ && std::abs(ttValue) < VALUE_TB_WIN_IN_MAX_PLY && (tte->bound() & BOUND_LOWER)
- Value singularBeta = ttValue - (64 + 57 * (ss->ttPv && !PvNode)) * depth / 64;
- Depth singularDepth = (depth - 1) / 2;
+ Value singularBeta = ttValue - (66 + 58 * (ss->ttPv && !PvNode)) * depth / 64;
+ Depth singularDepth = newDepth / 2;
// we do not know if the ttMove is singular or can do a multi-cut,
// so we reduce the ttMove in favor of other moves based on some conditions:
// we do not know if the ttMove is singular or can do a multi-cut,
// so we reduce the ttMove in favor of other moves based on some conditions:
- && (*contHist[0])[movedPiece][to_sq(move)] >= 4194)
+ && (*contHist[0])[movedPiece][to_sq(move)] >= 4325)
+ extension = 1;
+
+ // Recapture extensions (~1 Elo)
+ else if (PvNode && move == ttMove && to_sq(move) == prevSq
+ && captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))]
+ > 4146)
ss->statScore = 2 * thisThread->mainHistory[us][from_to(move)]
+ (*contHist[0])[movedPiece][to_sq(move)]
+ (*contHist[1])[movedPiece][to_sq(move)]
ss->statScore = 2 * thisThread->mainHistory[us][from_to(move)]
+ (*contHist[0])[movedPiece][to_sq(move)]
+ (*contHist[1])[movedPiece][to_sq(move)]
// 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".
// 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".
&& (!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.
&& (!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.
- Depth d = std::clamp(newDepth - r, 1, newDepth + 1);
+ // To prevent problems when the max value is less than the min value,
+ // std::clamp has been replaced by a more robust implementation.
+ Depth d = std::max(1, std::min(newDepth - r, newDepth + 1));
value = -search<NonPV>(pos, ss + 1, -(alpha + 1), -alpha, d, true);
value = -search<NonPV>(pos, ss + 1, -(alpha + 1), -alpha, d, true);
{
// Adjust full-depth search based on LMR results - if the result
// was good enough search deeper, if it was bad enough search shallower.
{
// 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;
+ const bool doDeeperSearch = value > (bestValue + 53 + 2 * newDepth); // (~1 Elo)
+ const bool doShallowerSearch = value < bestValue + newDepth; // (~2 Elo)
if (newDepth > d)
value = -search<NonPV>(pos, ss + 1, -(alpha + 1), -alpha, newDepth, !cutNode);
if (newDepth > d)
value = -search<NonPV>(pos, ss + 1, -(alpha + 1), -alpha, newDepth, !cutNode);
+ ((ss - 1)->moveCount > 10);
update_continuation_histories(ss - 1, pos.piece_on(prevSq), prevSq,
stat_bonus(depth) * bonus);
+ ((ss - 1)->moveCount > 10);
update_continuation_histories(ss - 1, pos.piece_on(prevSq), prevSq,
stat_bonus(depth) * bonus);
// Step 2. Check for an immediate draw or maximum ply reached
if (pos.is_draw(ss->ply) || ss->ply >= MAX_PLY)
return (ss->ply >= MAX_PLY && !ss->inCheck) ? evaluate(pos) : VALUE_DRAW;
// Step 2. Check for an immediate draw or maximum ply reached
if (pos.is_draw(ss->ply) || ss->ply >= MAX_PLY)
return (ss->ply >= MAX_PLY && !ss->inCheck) ? evaluate(pos) : VALUE_DRAW;
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;
// will be generated.
Square prevSq = is_ok((ss - 1)->currentMove) ? to_sq((ss - 1)->currentMove) : SQ_NONE;
MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &thisThread->captureHistory,
// will be generated.
Square prevSq = is_ok((ss - 1)->currentMove) ? to_sq((ss - 1)->currentMove) : SQ_NONE;
MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &thisThread->captureHistory,
// Save gathered info in transposition table
tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit,
bestValue >= beta ? BOUND_LOWER : BOUND_UPPER, ttDepth, bestMove, ss->staticEval);
// Save gathered info in transposition table
tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit,
bestValue >= beta ? BOUND_LOWER : BOUND_UPPER, ttDepth, bestMove, ss->staticEval);
// 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".
// 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, 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.
+// However, to avoid potentially false mate or TB scores related to the 50 moves rule
+// and the graph history interaction, we return highest non-TB score instead.
+
- if (v >= VALUE_MATE_IN_MAX_PLY && VALUE_MATE - v > 99 - r50c)
- return VALUE_MATE_IN_MAX_PLY - 1; // do not return a potentially false mate score
+ // Downgrade a potentially false mate score
+ if (v >= VALUE_MATE_IN_MAX_PLY && VALUE_MATE - v > 100 - r50c)
+ return VALUE_TB_WIN_IN_MAX_PLY - 1;
+
+ // Downgrade a potentially false TB score.
+ if (VALUE_TB - v > 100 - r50c)
+ return VALUE_TB_WIN_IN_MAX_PLY - 1;
- if (v <= VALUE_MATED_IN_MAX_PLY && VALUE_MATE + v > 99 - r50c)
- return VALUE_MATED_IN_MAX_PLY + 1; // do not return a potentially false mate score
+ // Downgrade a potentially false mate score.
+ if (v <= VALUE_MATED_IN_MAX_PLY && VALUE_MATE + v > 100 - r50c)
+ return VALUE_TB_LOSS_IN_MAX_PLY + 1;
+
+ // Downgrade a potentially false TB score.
+ if (VALUE_TB + v > 100 - r50c)
+ return VALUE_TB_LOSS_IN_MAX_PLY + 1;
: stat_bonus(depth); // smaller bonus
// Increase stats for the best move in case it was a quiet move
: stat_bonus(depth); // smaller bonus
// Increase stats for the best move in case it was a quiet move
// Decrease stats for all non-best quiet moves
for (int i = 0; i < quietCount; ++i)
{
thisThread->pawnHistory[pawn_structure(pos)][pos.moved_piece(quietsSearched[i])]
[to_sq(quietsSearched[i])]
// Decrease stats for all non-best quiet moves
for (int i = 0; i < quietCount; ++i)
{
thisThread->pawnHistory[pawn_structure(pos)][pos.moved_piece(quietsSearched[i])]
[to_sq(quietsSearched[i])]
-// 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,
+// 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) {
// otherwise in case of 'ponder on' we have nothing to think about.
bool RootMove::extract_ponder_from_tt(Position& pos) {