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 + 1372 - int(delta) * 1073 / int(rootDelta)) / 1024 + (!i && r > 936);
+ int reductionScale = Reductions[d] * Reductions[mn];
+ return (reductionScale + 1372 - int(delta) * 1073 / int(rootDelta)) / 1024
+ + (!i && reductionScale > 936);
}
constexpr int futility_move_count(bool improving, Depth depth) {
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 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;
// When playing with strength handicap enable MultiPV search that we will
// 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());
alpha = std::max(prev - delta,-VALUE_INFINITE);
beta = std::min(prev + delta, VALUE_INFINITE);
- // Adjust optimism based on root move's previousScore
+ // Adjust optimism based on root move's previousScore (~4 Elo)
int opt = 109 * prev / (std::abs(prev) + 141);
optimism[ us] = Value(opt);
optimism[~us] = -optimism[us];
constexpr bool PvNode = nodeType != NonPV;
constexpr bool rootNode = nodeType == Root;
+ // Dive into quiescence search when the depth reaches zero
+ if (depth <= 0)
+ return qsearch<PvNode ? PV : NonPV>(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
return alpha;
}
- // Dive into quiescence search when the depth reaches zero
- if (depth <= 0)
- return qsearch<PvNode ? PV : NonPV>(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);
}
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;
}
: (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 - 456 - (252 - 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 >= beta
- && eval < 24923) // larger than VALUE_KNOWN_WIN, but smaller than TB wins
+ && eval < 24923 // 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)
&& (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,
moveCountPruning = singularQuietLMR = false;
// Indicate PvNodes that will probably fail low if the node was searched
- // at a depth equal to 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)
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;
// 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
+ // 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 > 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
+ && abs(ttValue) < VALUE_TB_WIN_IN_MAX_PLY
&& (tte->bound() & BOUND_LOWER)
&& tte->depth() >= depth - 3)
{
}
// 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.
+ // 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;
// 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 and 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;
+ 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)->cutoffCnt > 3)
r++;
+ // Decrease reduction for first generated move (ttMove)
else if (move == ttMove)
r--;
// 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;
}
}
// Check if we have an upcoming move that draws by repetition, or
// if the opponent had an alternative move earlier to this position.
- if ( depth < 0
- && alpha < VALUE_DRAW
+ if ( alpha < VALUE_DRAW
&& pos.has_game_cycle(ss->ply))
{
alpha = value_draw(pos.this_thread());
Value bestValue, value, ttValue, futilityValue, futilityBase;
bool pvHit, givesCheck, capture;
int moveCount;
+ Color us = pos.side_to_move();
// Step 1. Initialize node
if (PvNode)
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)
futilityValue = futilityBase + PieceValue[pos.piece_on(to_sq(move))];
+ // 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;
}
+ // 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;
}
+
+ // 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;
+ }
}
// We prune after the second quiet check evasion move, where being 'in check' is
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;
}
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);
projects / stockfish / blobdiff