return (r + 520) / 1024 + (!i && r > 999);
}
- constexpr int futility_move_count(bool improving, int depth) {
- return (5 + depth * depth) * (1 + improving) / 2;
+ constexpr int futility_move_count(bool improving, Depth depth) {
+ return (5 + depth * depth) * (1 + improving) / 2 - 1;
}
// History and stats update bonus, based on depth
Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth = 0);
Value value_to_tt(Value v, int ply);
- Value value_from_tt(Value v, int ply);
+ Value value_from_tt(Value v, int ply, int r50c);
void update_pv(Move* pv, Move move, Move* childPv);
void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus);
- void update_quiet_stats(const Position& pos, Stack* ss, Move move, Move* quiets, int quietCount, int bonus);
- void update_capture_stats(const Position& pos, Move move, Move* captures, int captureCount, int bonus);
+ void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus);
+ void update_all_stats(const Position& pos, Stack* ss, Move bestMove, Value bestValue, Value beta, Square prevSq,
+ Move* quietsSearched, int quietCount, Move* capturesSearched, int captureCount, Depth depth);
// perft() is our utility to verify move generation. All the leaf nodes up
// to the given depth are generated and counted, and the sum is returned.
std::memset(ss-7, 0, 10 * sizeof(Stack));
for (int i = 7; i > 0; i--)
- (ss-i)->continuationHistory = &this->continuationHistory[0][NO_PIECE][0]; // Use as a sentinel
+ (ss-i)->continuationHistory = &this->continuationHistory[0][0][NO_PIECE][0]; // Use as a sentinel
ss->pv = pv;
if (rootDepth >= 4)
{
Value previousScore = rootMoves[pvIdx].previousScore;
- delta = Value(23);
+ delta = Value(21 + abs(previousScore) / 128);
alpha = std::max(previousScore - delta,-VALUE_INFINITE);
beta = std::min(previousScore + delta, VALUE_INFINITE);
// Adjust contempt based on root move's previousScore (dynamic contempt)
- int dct = ct + 86 * previousScore / (abs(previousScore) + 176);
+ int dct = ct + (111 - ct / 2) * previousScore / (abs(previousScore) + 176);
contempt = (us == WHITE ? make_score(dct, dct / 2)
: -make_score(dct, dct / 2));
Move ttMove, move, excludedMove, bestMove;
Depth extension, newDepth;
Value bestValue, value, ttValue, eval, maxValue;
- bool ttHit, ttPv, inCheck, givesCheck, improving, doLMR;
- bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture;
- Piece movedPiece, priorCapture;
- int moveCount, captureCount, quietCount, singularLMR;
+ bool ttHit, ttPv, inCheck, givesCheck, improving, didLMR, priorCapture;
+ bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture, singularLMR;
+ Piece movedPiece;
+ int moveCount, captureCount, quietCount;
// Step 1. Initialize node
Thread* thisThread = pos.this_thread();
inCheck = pos.checkers();
priorCapture = pos.captured_piece();
Color us = pos.side_to_move();
- moveCount = captureCount = quietCount = singularLMR = ss->moveCount = 0;
+ moveCount = captureCount = quietCount = ss->moveCount = 0;
bestValue = -VALUE_INFINITE;
maxValue = VALUE_INFINITE;
excludedMove = ss->excludedMove;
posKey = pos.key() ^ Key(excludedMove << 16); // Isn't a very good hash
tte = TT.probe(posKey, ttHit);
- ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
+ ttValue = ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE;
ttMove = rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0]
: ttHit ? tte->move() : MOVE_NONE;
ttPv = PvNode || (ttHit && tte->is_pv());
if (ttValue >= beta)
{
if (!pos.capture_or_promotion(ttMove))
- update_quiet_stats(pos, ss, ttMove, nullptr, 0, stat_bonus(depth));
+ update_quiet_stats(pos, ss, ttMove, stat_bonus(depth));
// Extra penalty for early quiet moves of the previous ply
if ((ss-1)->moveCount <= 2 && !priorCapture)
Depth R = (835 + 70 * depth) / 256 + std::min(int(eval - beta) / 185, 3);
ss->currentMove = MOVE_NULL;
- ss->continuationHistory = &thisThread->continuationHistory[0][NO_PIECE][0];
+ ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0];
pos.do_null_move(st);
&& probCutCount < 2 + 2 * cutNode)
if (move != excludedMove && pos.legal(move))
{
+ assert(pos.capture_or_promotion(move));
+ assert(depth >= 5);
+
+ captureOrPromotion = true;
probCutCount++;
ss->currentMove = move;
- ss->continuationHistory = &thisThread->continuationHistory[!!priorCapture][pos.moved_piece(move)][to_sq(move)];
-
- assert(depth >= 5);
+ ss->continuationHistory = &thisThread->continuationHistory[inCheck]
+ [captureOrPromotion]
+ [pos.moved_piece(move)]
+ [to_sq(move)];
pos.do_move(move, st);
search<NT>(pos, ss, alpha, beta, depth - 7, cutNode);
tte = TT.probe(posKey, ttHit);
- ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
+ ttValue = ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE;
ttMove = ttHit ? tte->move() : MOVE_NONE;
}
moves_loop: // When in check, search starts from here
const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory,
- nullptr, (ss-4)->continuationHistory,
- nullptr, (ss-6)->continuationHistory };
+ nullptr , (ss-4)->continuationHistory,
+ nullptr , (ss-6)->continuationHistory };
Move countermove = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq];
countermove,
ss->killers);
- value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
- moveCountPruning = false;
+ value = bestValue;
+ singularLMR = moveCountPruning = false;
ttCapture = ttMove && pos.capture_or_promotion(ttMove);
// Mark this node as being searched
movedPiece = pos.moved_piece(move);
givesCheck = pos.gives_check(move);
- // Step 13. Extensions (~70 Elo)
+ // Calculate new depth for this move
+ newDepth = depth - 1;
+
+ // Step 13. Pruning at shallow depth (~170 Elo)
+ if ( !rootNode
+ && pos.non_pawn_material(us)
+ && bestValue > VALUE_MATED_IN_MAX_PLY)
+ {
+ // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold
+ moveCountPruning = moveCount >= futility_move_count(improving, depth);
+
+ if ( !captureOrPromotion
+ && !givesCheck
+ && (!PvNode || !pos.advanced_pawn_push(move) || pos.non_pawn_material(~us) > BishopValueMg))
+ {
+ // Reduced depth of the next LMR search
+ int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), 0);
+
+ // Countermoves based pruning (~20 Elo)
+ if ( lmrDepth < 4 + ((ss-1)->statScore > 0 || (ss-1)->moveCount == 1)
+ && (*contHist[0])[movedPiece][to_sq(move)] < CounterMovePruneThreshold
+ && (*contHist[1])[movedPiece][to_sq(move)] < CounterMovePruneThreshold)
+ continue;
+
+ // Futility pruning: parent node (~2 Elo)
+ if ( lmrDepth < 6
+ && !inCheck
+ && ss->staticEval + 250 + 211 * lmrDepth <= alpha)
+ continue;
+
+ // Prune moves with negative SEE (~10 Elo)
+ if (!pos.see_ge(move, Value(-(31 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth)))
+ continue;
+ }
+ else if (!pos.see_ge(move, Value(-199) * depth)) // (~20 Elo)
+ continue;
+ }
+
+ // Step 14. Extensions (~70 Elo)
// Singular extension search (~60 Elo). If all moves but one fail low on a
// search of (alpha-s, beta-s), and just one fails high on (alpha, beta),
if (value < singularBeta)
{
extension = 1;
- singularLMR++;
-
- if (value < singularBeta - std::min(4 * depth, 36))
- singularLMR++;
+ singularLMR = true;
}
// Multi-cut pruning
&& (pos.is_discovery_check_on_king(~us, move) || pos.see_ge(move)))
extension = 1;
- // Shuffle extension
- else if ( PvNode
- && pos.rule50_count() > 18
- && depth < 3
- && ++thisThread->shuffleExts < thisThread->nodes.load(std::memory_order_relaxed) / 4) // To avoid too many extensions
- extension = 1;
-
// Passed pawn extension
else if ( move == ss->killers[0]
&& pos.advanced_pawn_push(move)
if (type_of(move) == CASTLING)
extension = 1;
- // Calculate new depth for this move
- newDepth = depth - 1 + extension;
-
- // Step 14. Pruning at shallow depth (~170 Elo)
- if ( !rootNode
- && pos.non_pawn_material(us)
- && bestValue > VALUE_MATED_IN_MAX_PLY)
- {
- // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold
- moveCountPruning = moveCount >= futility_move_count(improving, depth);
-
- if ( !captureOrPromotion
- && !givesCheck
- && (!pos.advanced_pawn_push(move) || pos.non_pawn_material(~us) > BishopValueMg))
- {
- // Move count based pruning
- if (moveCountPruning)
- continue;
-
- // Reduced depth of the next LMR search
- int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), 0);
-
- // Countermoves based pruning (~20 Elo)
- if ( lmrDepth < 4 + ((ss-1)->statScore > 0 || (ss-1)->moveCount == 1)
- && (*contHist[0])[movedPiece][to_sq(move)] < CounterMovePruneThreshold
- && (*contHist[1])[movedPiece][to_sq(move)] < CounterMovePruneThreshold)
- continue;
-
- // Futility pruning: parent node (~2 Elo)
- if ( lmrDepth < 6
- && !inCheck
- && ss->staticEval + 250 + 211 * lmrDepth <= alpha)
- continue;
-
- // Prune moves with negative SEE (~10 Elo)
- if (!pos.see_ge(move, Value(-(31 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth)))
- continue;
- }
- else if ( !(givesCheck && extension)
- && !pos.see_ge(move, Value(-199) * depth)) // (~20 Elo)
- continue;
- }
+ // Add extension to new depth
+ newDepth += extension;
// 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[!!priorCapture][movedPiece][to_sq(move)];
+ ss->continuationHistory = &thisThread->continuationHistory[inCheck]
+ [captureOrPromotion]
+ [movedPiece]
+ [to_sq(move)];
// Step 15. Make the move
pos.do_move(move, st, givesCheck);
r--;
// Decrease reduction if ttMove has been singularly extended
- r -= singularLMR;
+ if (singularLMR)
+ r -= 2;
if (!captureOrPromotion)
{
value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, true);
- doFullDepthSearch = (value > alpha && d != newDepth), doLMR = true;
+ doFullDepthSearch = (value > alpha && d != newDepth), didLMR = true;
}
else
- doFullDepthSearch = !PvNode || moveCount > 1, doLMR = false;
+ doFullDepthSearch = !PvNode || moveCount > 1, didLMR = false;
// Step 17. Full depth search when LMR is skipped or fails high
if (doFullDepthSearch)
{
value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode);
- if (doLMR && !captureOrPromotion)
+ if (didLMR && !captureOrPromotion)
{
int bonus = value > alpha ? stat_bonus(newDepth)
: -stat_bonus(newDepth);
if (!moveCount)
bestValue = excludedMove ? alpha
: inCheck ? mated_in(ss->ply) : VALUE_DRAW;
- else if (bestMove)
- {
- // Quiet best move: update move sorting heuristics
- if (!pos.capture_or_promotion(bestMove))
- update_quiet_stats(pos, ss, bestMove, quietsSearched, quietCount,
- stat_bonus(depth + (bestValue > beta + PawnValueMg)));
-
- update_capture_stats(pos, bestMove, capturesSearched, captureCount, stat_bonus(depth + 1));
- // Extra penalty for a quiet TT or main killer move in previous ply when it gets refuted
- if ( ((ss-1)->moveCount == 1 || ((ss-1)->currentMove == (ss-1)->killers[0]))
- && !priorCapture)
- update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + 1));
+ else if (bestMove)
+ update_all_stats(pos, ss, bestMove, bestValue, beta, prevSq,
+ quietsSearched, quietCount, capturesSearched, captureCount, depth);
- }
// Bonus for prior countermove that caused the fail low
else if ( (depth >= 3 || PvNode)
&& !priorCapture)
Move ttMove, move, bestMove;
Depth ttDepth;
Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha;
- Piece priorCapture;
- bool ttHit, pvHit, inCheck, givesCheck, evasionPrunable;
+ bool ttHit, pvHit, inCheck, givesCheck, captureOrPromotion, evasionPrunable;
int moveCount;
if (PvNode)
(ss+1)->ply = ss->ply + 1;
bestMove = MOVE_NONE;
inCheck = pos.checkers();
- priorCapture = pos.captured_piece();
moveCount = 0;
// Check for an immediate draw or maximum ply reached
// Transposition table lookup
posKey = pos.key();
tte = TT.probe(posKey, ttHit);
- ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
+ ttValue = ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE;
ttMove = ttHit ? tte->move() : MOVE_NONE;
pvHit = ttHit && tte->is_pv();
}
const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory,
- nullptr, (ss-4)->continuationHistory,
- nullptr, (ss-6)->continuationHistory };
+ nullptr , (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,
assert(is_ok(move));
givesCheck = pos.gives_check(move);
+ captureOrPromotion = pos.capture_or_promotion(move);
moveCount++;
// Don't search moves with negative SEE values
if ( (!inCheck || evasionPrunable)
- && (!givesCheck || !(pos.blockers_for_king(~pos.side_to_move()) & from_sq(move)))
+ && !(givesCheck && pos.is_discovery_check_on_king(~pos.side_to_move(), move))
&& !pos.see_ge(move))
continue;
}
ss->currentMove = move;
- ss->continuationHistory = &thisThread->continuationHistory[!!priorCapture][pos.moved_piece(move)][to_sq(move)];
+ ss->continuationHistory = &thisThread->continuationHistory[inCheck]
+ [captureOrPromotion]
+ [pos.moved_piece(move)]
+ [to_sq(move)];
// Make and search the move
pos.do_move(move, st, givesCheck);
// from the transposition table (which refers to the plies to mate/be mated
// from current position) to "plies to mate/be mated from the root".
- Value value_from_tt(Value v, int ply) {
+ Value value_from_tt(Value v, int ply, int r50c) {
return v == VALUE_NONE ? VALUE_NONE
- : v >= VALUE_MATE_IN_MAX_PLY ? v - ply
- : v <= VALUE_MATED_IN_MAX_PLY ? v + ply : v;
+ : v >= VALUE_MATE_IN_MAX_PLY ? VALUE_MATE - v > 99 - r50c ? VALUE_MATE_IN_MAX_PLY : v - ply
+ : v <= VALUE_MATED_IN_MAX_PLY ? VALUE_MATE + v > 99 - r50c ? VALUE_MATED_IN_MAX_PLY : v + ply : v;
}
}
- // update_continuation_histories() updates histories of the move pairs formed
- // by moves at ply -1, -2, and -4 with current move.
+ // update_all_stats() updates stats at the end of search() when a bestMove is found
- void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus) {
+ void update_all_stats(const Position& pos, Stack* ss, Move bestMove, Value bestValue, Value beta, Square prevSq,
+ Move* quietsSearched, int quietCount, Move* capturesSearched, int captureCount, Depth depth) {
- for (int i : {1, 2, 4, 6})
- if (is_ok((ss-i)->currentMove))
- (*(ss-i)->continuationHistory)[pc][to] << bonus;
- }
+ int bonus1, bonus2;
+ Color us = pos.side_to_move();
+ Thread* thisThread = pos.this_thread();
+ CapturePieceToHistory& captureHistory = thisThread->captureHistory;
+ Piece moved_piece = pos.moved_piece(bestMove);
+ PieceType captured = type_of(pos.piece_on(to_sq(bestMove)));
+
+ bonus1 = stat_bonus(depth + 1);
+ bonus2 = bestValue > beta + PawnValueMg ? bonus1 // larger bonus
+ : stat_bonus(depth); // smaller bonus
+
+ if (!pos.capture_or_promotion(bestMove))
+ {
+ update_quiet_stats(pos, ss, bestMove, bonus2);
+
+ // Decrease all the 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);
+ }
+ }
+ else
+ captureHistory[moved_piece][to_sq(bestMove)][captured] << bonus1;
+ // Extra penalty for a quiet TT or main killer move in previous ply when it gets refuted
+ if ( ((ss-1)->moveCount == 1 || ((ss-1)->currentMove == (ss-1)->killers[0]))
+ && !pos.captured_piece())
+ update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -bonus1);
- // update_capture_stats() updates move sorting heuristics when a new capture best move is found
+ // Decrease all the 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;
+ }
+ }
- void update_capture_stats(const Position& pos, Move move,
- Move* captures, int captureCount, int bonus) {
- CapturePieceToHistory& captureHistory = pos.this_thread()->captureHistory;
- Piece moved_piece = pos.moved_piece(move);
- PieceType captured = type_of(pos.piece_on(to_sq(move)));
+ // update_continuation_histories() updates histories of the move pairs formed
+ // by moves at ply -1, -2, and -4 with current move.
- if (pos.capture_or_promotion(move))
- captureHistory[moved_piece][to_sq(move)][captured] << bonus;
+ void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus) {
- // Decrease all the other played capture moves
- for (int i = 0; i < captureCount; ++i)
- {
- moved_piece = pos.moved_piece(captures[i]);
- captured = type_of(pos.piece_on(to_sq(captures[i])));
- captureHistory[moved_piece][to_sq(captures[i])][captured] << -bonus;
- }
+ for (int i : {1, 2, 4, 6})
+ if (is_ok((ss-i)->currentMove))
+ (*(ss-i)->continuationHistory)[pc][to] << bonus;
}
- // update_quiet_stats() updates move sorting heuristics when a new quiet best move is found
+ // update_quiet_stats() updates move sorting heuristics
- void update_quiet_stats(const Position& pos, Stack* ss, Move move,
- Move* quiets, int quietCount, int bonus) {
+ void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus) {
if (ss->killers[0] != move)
{
Square prevSq = to_sq((ss-1)->currentMove);
thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] = move;
}
-
- // Decrease all the other played quiet moves
- for (int i = 0; i < quietCount; ++i)
- {
- thisThread->mainHistory[us][from_to(quiets[i])] << -bonus;
- update_continuation_histories(ss, pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus);
- }
}
// When playing with strength handicap, choose best move among a set of RootMoves
projects / stockfish / blobdiff