// Different node types, used as a template parameter
enum NodeType { NonPV, PV };
+ constexpr uint64_t ttHitAverageWindow = 4096;
+ constexpr uint64_t ttHitAverageResolution = 1024;
+
// Razor and futility margins
constexpr int RazorMargin = 661;
Value futility_margin(Depth d, bool improving) {
}
constexpr int futility_move_count(bool improving, Depth depth) {
- return (5 + depth * depth) * (1 + improving) / 2;
+ 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, int bonus);
multiPV = std::max(multiPV, (size_t)4);
multiPV = std::min(multiPV, rootMoves.size());
+ ttHitAverage = ttHitAverageWindow * ttHitAverageResolution / 2;
int ct = int(Options["Contempt"]) * PawnValueEg / 100; // From centipawns
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());
+ // thisThread->ttHitAverage can be used to approximate the running average of ttHit
+ thisThread->ttHitAverage = (ttHitAverageWindow - 1) * thisThread->ttHitAverage / ttHitAverageWindow
+ + ttHitAverageResolution * ttHit;
// At non-PV nodes we check for an early TT cutoff
if ( !PvNode
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;
}
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)
+ {
+ // 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),
&& (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)));
&& ( !captureOrPromotion
|| moveCountPruning
|| ss->staticEval + PieceValue[EG][pos.captured_piece()] <= alpha
- || cutNode))
+ || cutNode
+ || thisThread->ttHitAverage < 384 * ttHitAverageResolution * ttHitAverageWindow / 1024))
{
Depth r = reduction(improving, depth, moveCount);
+ // Decrease reduction if the ttHit running average is large
+ if (thisThread->ttHitAverage > 544 * ttHitAverageResolution * ttHitAverageWindow / 1024)
+ r--;
+
// Reduction if other threads are searching this position.
if (th.marked())
r++;
// 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();
// 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;
}