- // Continuation history based pruning (~2 Elo)
- if ( lmrDepth < 6
- && history < -3832 * depth)
- continue;
-
- history += 2 * thisThread->mainHistory[us][from_to(move)];
-
- lmrDepth += history / 7011;
- lmrDepth = std::max(lmrDepth, -2);
-
- // Futility pruning: parent node (~13 Elo)
- if ( !ss->inCheck
- && lmrDepth < 12
- && ss->staticEval + 112 + 138 * lmrDepth <= alpha)
- continue;
-
- lmrDepth = std::max(lmrDepth, 0);
-
- // Prune moves with negative SEE (~4 Elo)
- if (!pos.see_ge(move, Value(-31 * lmrDepth * lmrDepth)))
- continue;
- }
- }
-
- // 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 (~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.
- // 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 > 22) + 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
- && (tte->bound() & BOUND_LOWER)
- && tte->depth() >= depth - 3)
- {
- Value singularBeta = ttValue - (82 + 65 * (ss->ttPv && !PvNode)) * depth / 64;
- Depth singularDepth = (depth - 1) / 2;
-
- ss->excludedMove = move;
- value = search<NonPV>(pos, ss, singularBeta - 1, singularBeta, singularDepth, cutNode);
- ss->excludedMove = MOVE_NONE;
-
- if (value < singularBeta)
- {
- extension = 1;
- singularQuietLMR = !ttCapture;
-
- // Avoid search explosion by limiting the number of double extensions
- if ( !PvNode
- && value < singularBeta - 21
- && ss->doubleExtensions <= 11)
- {
- extension = 2;
- depth += depth < 13;
- }
- }
-
- // 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 softbound.
- else if (singularBeta >= beta)
- return singularBeta;
-
- // If the eval of ttMove is greater than beta, we reduce it (negative extension) (~7 Elo)
- 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 < 17 ? -3 : -1;
-
- // If the eval of ttMove is less than value, we reduce it (negative extension) (~1 Elo)
- else if (ttValue <= value)
- extension = -1;
- }
-
- // Check extensions (~1 Elo)
- else if ( givesCheck
- && depth > 9)
- extension = 1;
-
- // Quiet ttMove extensions (~1 Elo)
- else if ( PvNode
- && move == ttMove
- && move == ss->killers[0]
- && (*contHist[0])[movedPiece][to_sq(move)] >= 5168)
- extension = 1;
- }
-
- // Add extension to new depth
- newDepth += extension;
- ss->doubleExtensions = (ss-1)->doubleExtensions + (extension == 2);
-
- // Speculative prefetch as early as possible
- prefetch(TT.first_entry(pos.key_after(move)));
-
- // Update the current move (this must be done after singular extension search)
- ss->currentMove = move;
- ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck]
- [capture]
- [movedPiece]
- [to_sq(move)];
-
- // 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 further on cutNodes. (~1 Elo)
- if ( ss->ttPv
- && !likelyFailLow)
- r -= cutNode && tte->depth() >= depth + 3 ? 3 : 2;
-
- // Decrease reduction if opponent's move count is high (~1 Elo)
- if ((ss-1)->moveCount > 8)
- r--;
-
- // Increase reduction for cut nodes (~3 Elo)
- if (cutNode)
- r += 2;
-
- // Increase reduction if ttMove is a capture (~3 Elo)
- if (ttCapture)
- r++;
-
- // Decrease reduction for PvNodes (~2 Elo)
- if (PvNode)
- 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++;
-
- 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)]
- - 4006;
-
- // Decrease/increase reduction for moves with a good/bad history (~25 Elo)
- r -= ss->statScore / (11124 + 4740 * (depth > 5 && depth < 22));
-
- // 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.
- Depth d = std::clamp(newDepth - r, 1, newDepth + 1);
-
- value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, true);
-
- // 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 the result
- // was good enough search deeper, if it was bad enough search shallower
- const bool doDeeperSearch = value > (bestValue + 64 + 11 * (newDepth - d));
- const bool doEvenDeeperSearch = value > alpha + 711 && ss->doubleExtensions <= 6;
- const bool doShallowerSearch = value < bestValue + newDepth;
-
- 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)
- : 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.
- else if (!PvNode || moveCount > 1)
- {
- // Increase reduction for cut nodes and not ttMove (~1 Elo)
- if (!ttMove && cutNode)
- r += 2;
-
- value = -search<NonPV>(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,
- // 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<PV>(pos, ss+1, -beta, -alpha, newDepth, false);
- }
-
- // Step 19. Undo move
- pos.undo_move(move);
-
- assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
-
- // Step 20. Check for a new best move
- // Finished searching the move. If a stop occurred, the return value of
- // the search cannot be trusted, and we return immediately without
- // updating best move, PV and TT.
- if (Threads.stop.load(std::memory_order_relaxed))
- return VALUE_ZERO;
-
- if (rootNode)
- {
- RootMove& rm = *std::find(thisThread->rootMoves.begin(),
- thisThread->rootMoves.end(), move);
-
- rm.averageScore = rm.averageScore != -VALUE_INFINITE ? (2 * value + rm.averageScore) / 3 : value;
-
- // PV move or new best move?
- if (moveCount == 1 || value > alpha)
- {
- 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);
-
- for (Move* m = (ss+1)->pv; *m != MOVE_NONE; ++m)
- rm.pv.push_back(*m);
-
- // We record how often the best move has been changed in each iteration.
- // This information is used for time management. In MultiPV mode,
- // we must take care to only do this for the first PV line.
- if ( moveCount > 1
- && !thisThread->pvIdx)
- ++thisThread->bestMoveChanges;
- }
- else
- // 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;
- }
-
- if (value > bestValue)
- {
- bestValue = value;
-
- if (value > alpha)
- {
- bestMove = move;
-
- if (PvNode && !rootNode) // Update pv even in fail-high case
- update_pv(ss->pv, move, (ss+1)->pv);
-
- if (value >= beta)
- {
- ss->cutoffCnt += 1 + !ttMove;
- assert(value >= beta); // Fail high
- break;
- }
- else
- {
- // Reduce other moves if we have found at least one score improvement (~2 Elo)
- if ( depth > 2
- && depth < 12
- && beta < 14362
- && value > -12393)
- 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 (capture && captureCount < 32)
- capturesSearched[captureCount++] = move;
-
- else if (!capture && quietCount < 64)
- quietsSearched[quietCount++] = move;
- }
- }
+ // Continuation history based pruning (~2 Elo)
+ if (lmrDepth < 6 && history < -3232 * depth)
+ continue;
+
+ history += 2 * thisThread->mainHistory[us][from_to(move)];
+
+ lmrDepth += history / 5793;
+ lmrDepth = std::max(lmrDepth, -2);
+
+ // Futility pruning: parent node (~13 Elo)
+ if (!ss->inCheck && lmrDepth < 13 && 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(-27 * lmrDepth * lmrDepth)))
+ continue;
+ }
+ }
+
+ // 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 (~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. 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 > 24) + 2 * (PvNode && tte->is_pv())
+ && move == ttMove && !excludedMove // Avoid recursive singular search
+ && abs(ttValue) < VALUE_TB_WIN_IN_MAX_PLY && (tte->bound() & BOUND_LOWER)
+ && tte->depth() >= depth - 3)
+ {
+ Value singularBeta = ttValue - (64 + 57 * (ss->ttPv && !PvNode)) * depth / 64;
+ Depth singularDepth = (depth - 1) / 2;
+
+ ss->excludedMove = move;
+ value =
+ search<NonPV>(pos, ss, singularBeta - 1, singularBeta, singularDepth, cutNode);
+ ss->excludedMove = MOVE_NONE;
+
+ if (value < singularBeta)
+ {
+ extension = 1;
+ singularQuietLMR = !ttCapture;
+
+ // Avoid search explosion by limiting the number of double extensions
+ if (!PvNode && value < singularBeta - 18 && ss->doubleExtensions <= 11)
+ {
+ extension = 2;
+ 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 softbound.
+ else if (singularBeta >= beta)
+ return singularBeta;
+
+ // If the eval of ttMove is greater than beta, we reduce it (negative extension) (~7 Elo)
+ 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;
+ }
+
+ // Check extensions (~1 Elo)
+ else if (givesCheck && depth > 9)
+ extension = 1;
+
+ // Quiet ttMove extensions (~1 Elo)
+ else if (PvNode && move == ttMove && move == ss->killers[0]
+ && (*contHist[0])[movedPiece][to_sq(move)] >= 4194)
+ extension = 1;
+ }
+
+ // Add extension to new depth
+ newDepth += extension;
+ ss->doubleExtensions = (ss - 1)->doubleExtensions + (extension == 2);
+
+ // Speculative prefetch as early as possible
+ prefetch(TT.first_entry(pos.key_after(move)));
+
+ // Update the current move (this must be done after singular extension search)
+ ss->currentMove = move;
+ ss->continuationHistory =
+ &thisThread->continuationHistory[ss->inCheck][capture][movedPiece][to_sq(move)];
+
+ // Step 16. Make the move
+ pos.do_move(move, st, givesCheck);
+
+ // Decrease reduction if position is or has been on the PV (~4 Elo)
+ if (ss->ttPv && !likelyFailLow)
+ r -= cutNode && tte->depth() >= depth ? 3 : 2;
+
+ // 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 if ttMove is a capture (~3 Elo)
+ if (ttCapture)
+ r++;
+
+ // Decrease reduction for PvNodes (~2 Elo)
+ if (PvNode)
+ 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)] - 3848;
+
+ // Decrease/increase reduction for moves with a good/bad history (~25 Elo)
+ 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
+ // 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.
+ Depth d = std::clamp(newDepth - r, 1, newDepth + 1);
+
+ value = -search<NonPV>(pos, ss + 1, -(alpha + 1), -alpha, d, true);
+
+ // 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 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;
+
+ 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)
+ : value >= beta ? stat_bonus(newDepth)
+ : 0;
+
+ update_continuation_histories(ss, movedPiece, to_sq(move), bonus);
+ }
+ }
+
+ // 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)
+ r += 2;
+
+ // Note that if expected reduction is high, we reduce search depth by 1 here
+ value = -search<NonPV>(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,
+ // 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<PV>(pos, ss + 1, -beta, -alpha, newDepth, false);
+ }