// Futility margin
Value futility_margin(Depth d, bool noTtCutNode, bool improving) {
- return Value((140 - 40 * noTtCutNode) * (d - improving));
+ return Value((126 - 42 * noTtCutNode) * (d - improving));
}
// Reductions lookup table initialized at startup
Depth reduction(bool i, Depth d, int mn, Value delta, Value rootDelta) {
int reductionScale = Reductions[d] * Reductions[mn];
- return (reductionScale + 1372 - int(delta) * 1073 / int(rootDelta)) / 1024
- + (!i && reductionScale > 936);
+ return (reductionScale + 1560 - int(delta) * 945 / int(rootDelta)) / 1024
+ + (!i && reductionScale > 791);
}
constexpr int futility_move_count(bool improving, Depth depth) {
// History and stats update bonus, based on depth
int stat_bonus(Depth d) {
- return std::min(336 * d - 547, 1561);
+ return std::min(334 * d - 531, 1538);
}
// Add a small random component to draw evaluations to avoid 3-fold blindness
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 a 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 the master at various
+ // skill levels and various versions of the Stash engine, all ranked at CCRL.
+ // Skill 0 .. 19 now covers CCRL Blitz Elo from 1320 to 3190, approximately
+ // Reference: https://github.com/vondele/Stockfish/commit/a08b8d4e9711c20acedbfe17d618c3c384b339ec
struct Skill {
Skill(int skill_level, int uci_elo) {
if (uci_elo)
void Search::init() {
for (int i = 1; i < MAX_MOVES; ++i)
- Reductions[i] = int((20.57 + std::log(Threads.size()) / 2) * std::log(i));
+ Reductions[i] = int((20.37 + std::log(Threads.size()) / 2) * std::log(i));
}
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;
// Reset aspiration window starting size
Value prev = rootMoves[pvIdx].averageScore;
- delta = Value(10) + int(prev) * prev / 15799;
+ 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
- int opt = 109 * prev / (std::abs(prev) + 141);
+ // 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];
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);
}
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;
}
// 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(-18 * int((ss-1)->staticEval + ss->staticEval), -1817, 1817);
+ int bonus = std::clamp(-18 * int((ss-1)->staticEval + ss->staticEval), -1812, 1812);
thisThread->mainHistory[~us][from_to((ss-1)->currentMove)] << bonus;
}
: (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 - 456 - 252 * depth * depth)
+ // Adjust razor margin according to cutoffCnt. (~1 Elo)
+ if (eval < alpha - 492 - (257 - 200 * ((ss+1)->cutoffCnt > 3)) * depth * depth)
{
value = qsearch<NonPV>(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, cutNode && !ss->ttHit, improving) - (ss-1)->statScore / 306 >= beta
+ && eval - futility_margin(depth, cutNode && !ss->ttHit, improving) - (ss-1)->statScore / 321 >= beta
&& eval >= beta
- && eval < 24923) // 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 < 17329
+ && (ss-1)->statScore < 17257
&& eval >= beta
&& eval >= ss->staticEval
- && ss->staticEval >= beta - 21 * depth + 258
+ && ss->staticEval >= beta - 24 * depth + 281
&& !excludedMove
&& pos.non_pawn_material(us)
&& ss->ply >= thisThread->nmpMinPly
assert(eval - beta >= 0);
// Null move dynamic reduction based on depth and eval
- Depth R = std::min(int(eval - beta) / 173, 6) + depth / 3 + 4;
+ 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];
&& !ttMove)
depth -= 2;
- probCutBeta = beta + 168 - 61 * improving;
+ probCutBeta = beta + 168 - 70 * improving;
// Step 11. ProbCut (~10 Elo)
// If we have a good enough capture (or queen promotion) and a reduced search returns a value
moves_loop: // When in check, search starts here
// Step 12. A small Probcut idea, when we are in check (~4 Elo)
- probCutBeta = beta + 413;
+ probCutBeta = beta + 416;
if ( ss->inCheck
&& !PvNode
&& ttCapture
&& (tte->bound() & BOUND_LOWER)
&& 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;
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 that 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)
&& 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 = newDepth - r;
if ( !givesCheck
&& lmrDepth < 7
&& !ss->inCheck
- && ss->staticEval + 197 + 248 * lmrDepth + PieceValue[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;
// SEE based pruning for captures and checks (~11 Elo)
- if (!pos.see_ge(move, Value(-205) * depth))
+ if (!pos.see_ge(move, Value(-185) * depth))
continue;
}
else
// Continuation history based pruning (~2 Elo)
if ( lmrDepth < 6
- && history < -3832 * depth)
+ && history < -3232 * depth)
continue;
history += 2 * thisThread->mainHistory[us][from_to(move)];
- lmrDepth += history / 7011;
+ lmrDepth += history / 5793;
lmrDepth = std::max(lmrDepth, -2);
// Futility pruning: parent node (~13 Elo)
if ( !ss->inCheck
- && lmrDepth < 12
- && ss->staticEval + 112 + 138 * lmrDepth <= alpha)
+ && 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(-31 * lmrDepth * lmrDepth)))
+ if (!pos.see_ge(move, Value(-27 * lmrDepth * lmrDepth)))
continue;
}
}
// 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())
+ && 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 - (82 + 65 * (ss->ttPv && !PvNode)) * depth / 64;
+ Value singularBeta = ttValue - (64 + 57 * (ss->ttPv && !PvNode)) * depth / 64;
Depth singularDepth = (depth - 1) / 2;
ss->excludedMove = move;
// Avoid search explosion by limiting the number of double extensions
if ( !PvNode
- && value < singularBeta - 21
+ && value < singularBeta - 18
&& ss->doubleExtensions <= 11)
{
extension = 2;
- depth += depth < 13;
+ depth += depth < 15;
}
}
// If we are on a cutNode, reduce it based on depth (negative extension) (~1 Elo)
else if (cutNode)
- extension = depth < 17 ? -3 : -1;
+ 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)
else if ( PvNode
&& move == ttMove
&& move == ss->killers[0]
- && (*contHist[0])[movedPiece][to_sq(move)] >= 5168)
+ && (*contHist[0])[movedPiece][to_sq(move)] >= 4194)
extension = 1;
}
r -= cutNode && tte->depth() >= depth ? 3 : 2;
// Decrease reduction if opponent's move count is high (~1 Elo)
- if ((ss-1)->moveCount > 8)
+ if ((ss-1)->moveCount > 7)
r--;
// Increase reduction for cut nodes (~3 Elo)
+ (*contHist[0])[movedPiece][to_sq(move)]
+ (*contHist[1])[movedPiece][to_sq(move)]
+ (*contHist[3])[movedPiece][to_sq(move)]
- - 4006;
+ - 3848;
// Decrease/increase reduction for moves with a good/bad history (~25 Elo)
- r -= ss->statScore / (11124 + 4740 * (depth > 5 && depth < 22));
+ 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
{
// 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 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;
// Reduce other moves if we have found at least one score improvement (~2 Elo)
if ( depth > 2
&& depth < 12
- && beta < 14362
- && value > -12393)
+ && beta < 13828
+ && value > -11369)
depth -= 2;
assert(depth > 0);
// If the move is worse than some previously searched move, remember it, to update its stats later
- if (move != bestMove)
+ if (move != bestMove && moveCount <= 32)
{
- if (capture && captureCount < 32)
+ if (capture)
capturesSearched[captureCount++] = move;
- else if (!capture && quietCount < 64)
+ else
quietsSearched[quietCount++] = move;
}
}
// Bonus for prior countermove that caused the fail low
else if (!priorCapture && prevSq != SQ_NONE)
{
- int bonus = (depth > 5) + (PvNode || cutNode) + (bestValue < alpha - 800) + ((ss-1)->moveCount > 12);
+ 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;
}
Value bestValue, value, ttValue, futilityValue, futilityBase;
bool pvHit, givesCheck, capture;
int moveCount;
+ Color us = pos.side_to_move();
// Step 1. Initialize node
if (PvNode)
}
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
moveCount++;
// Step 6. Pruning.
- if (bestValue > VALUE_TB_LOSS_IN_MAX_PLY)
+ 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_KNOWN_WIN
+ && futilityBase > VALUE_TB_LOSS_IN_MAX_PLY
&& type_of(move) != PROMOTION)
{
if (moveCount > 2)
continue;
// Do not search moves with bad enough SEE values (~5 Elo)
- if (!pos.see_ge(move, Value(-95)))
+ if (!pos.see_ge(move, Value(-90)))
continue;
}
if (!pos.capture_stage(bestMove))
{
- int bestMoveBonus = bestValue > beta + 145 ? quietMoveBonus // larger 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
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 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));
}
}