along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
+#include "search.h"
+
#include <algorithm>
+#include <array>
+#include <atomic>
#include <cassert>
#include <cmath>
-#include <cstring> // For std::memset
+#include <cstdlib>
+#include <cstring>
+#include <initializer_list>
#include <iostream>
#include <sstream>
+#include <string>
+#include <utility>
+#include "bitboard.h"
#include "evaluate.h"
#include "misc.h"
#include "movegen.h"
#include "movepick.h"
+#include "nnue/evaluate_nnue.h"
+#include "nnue/nnue_common.h"
#include "position.h"
-#include "search.h"
+#include "syzygy/tbprobe.h"
#include "thread.h"
#include "timeman.h"
#include "tt.h"
#include "uci.h"
-#include "syzygy/tbprobe.h"
-#include "nnue/evaluate_nnue.h"
namespace Stockfish {
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) {
// 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
- && pos.rule50_count() >= 3
&& alpha < VALUE_DRAW
&& pos.has_game_cycle(ss->ply))
{
// At non-PV nodes we check for an early TT cutoff
if ( !PvNode
&& !excludedMove
- && tte->depth() > depth - (tte->bound() == BOUND_EXACT)
+ && tte->depth() > depth
&& ttValue != VALUE_NONE // Possible in case of TT access race or if !ttHit
&& (tte->bound() & (ttValue >= beta ? BOUND_LOWER : BOUND_UPPER)))
{
}
// Set up the improving flag, which is true if current static evaluation is
- // bigger than the previous static evaluation at our turn (if we were in
- // check at our previous move we look at static evaluaion at move prior to it
+ // bigger than the previous static evaluation at our turn (if we were in
+ // check at our previous move we look at static evaluation at move prior to it
// and if we were in check at move prior to it flag is set to true) and is
// false otherwise. The improving flag is used in various pruning heuristics.
improving = (ss-2)->staticEval != VALUE_NONE ? ss->staticEval > (ss-2)->staticEval
if ( !givesCheck
&& lmrDepth < 7
&& !ss->inCheck
- && ss->staticEval + 197 + 248 * lmrDepth + PieceValue[EG][pos.piece_on(to_sq(move))]
+ && ss->staticEval + 197 + 248 * lmrDepth + PieceValue[pos.piece_on(to_sq(move))]
+ captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))] / 7 < alpha)
continue;
- Bitboard occupied;
- // SEE based pruning (~11 Elo)
- if (!pos.see_ge(move, occupied, Value(-205) * depth))
- {
- if (depth < 2 - capture)
- continue;
- // Don't prune the move if opponent Queen/Rook is under discovered attack after the exchanges
- // Don't prune the move if opponent King is under discovered attack after or during the exchanges
- Bitboard leftEnemies = (pos.pieces(~us, KING, QUEEN, ROOK)) & occupied;
- Bitboard attacks = 0;
- occupied |= to_sq(move);
- while (leftEnemies && !attacks)
- {
- Square sq = pop_lsb(leftEnemies);
- attacks |= pos.attackers_to(sq, occupied) & pos.pieces(us) & occupied;
- // Don't consider pieces that were already threatened/hanging before SEE exchanges
- if (attacks && (sq != pos.square<KING>(~us) && (pos.attackers_to(sq, pos.pieces()) & pos.pieces(us))))
- attacks = 0;
- }
- if (!attacks)
- continue;
- }
+ // SEE based pruning for captures and checks (~11 Elo)
+ if (!pos.see_ge(move, Value(-205) * depth))
+ continue;
}
else
{
lmrDepth = std::max(lmrDepth, 0);
// Prune moves with negative SEE (~4 Elo)
- if (!pos.see_ge(move, Value(-27 * lmrDepth * lmrDepth - 16 * lmrDepth)))
+ if (!pos.see_ge(move, Value(-31 * lmrDepth * lmrDepth)))
continue;
}
}
// If we are on a cutNode, reduce it based on depth (negative extension) (~1 Elo)
else if (cutNode)
- extension = depth > 8 && depth < 17 ? -3 : -1;
+ 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;
-
- // If the eval of ttMove is less than alpha, we reduce it (negative extension) (~1 Elo)
- else if (ttValue <= alpha)
- extension = -1;
}
// Check extensions (~1 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 (ttCapture)
r++;
- // Decrease reduction for PvNodes based on depth (~2 Elo)
+ // Decrease reduction for PvNodes (~2 Elo)
if (PvNode)
- r -= 1 + (depth < 6);
+ 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++;
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 (in the latter case search only if value < beta), otherwise let the
- // parent node fail low with value <= alpha and try another move.
- if (PvNode && (moveCount == 1 || (value > alpha && (rootNode || value < beta))))
+ // 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;
// Bonus for prior countermove that caused the fail low
else if (!priorCapture && prevSq != SQ_NONE)
{
- int bonus = (depth > 5) + (PvNode || cutNode) + (bestValue < alpha - 113 * depth) + ((ss-1)->moveCount > 12);
+ int bonus = (depth > 5) + (PvNode || cutNode) + (bestValue < alpha - 800) + ((ss-1)->moveCount > 12);
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;
}
if (PvNode)
assert(PvNode || (alpha == beta - 1));
assert(depth <= 0);
+ // 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
+ && pos.has_game_cycle(ss->ply))
+ {
+ alpha = value_draw(pos.this_thread());
+ if (alpha >= beta)
+ return alpha;
+ }
+
Move pv[MAX_PLY+1];
StateInfo st;
ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize);
return bestValue;
}
- if (PvNode && bestValue > alpha)
+ if (bestValue > alpha)
alpha = bestValue;
- futilityBase = bestValue + 200;
+ futilityBase = std::min(ss->staticEval, bestValue) + 200;
}
const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory,
if (moveCount > 2)
continue;
- futilityValue = futilityBase + PieceValue[EG][pos.piece_on(to_sq(move))];
+ futilityValue = futilityBase + PieceValue[pos.piece_on(to_sq(move))];
if (futilityValue <= alpha)
{
if (PvNode) // Update pv even in fail-high case
update_pv(ss->pv, move, (ss+1)->pv);
- if (PvNode && value < beta) // Update alpha here!
+ if (value < beta) // Update alpha here!
alpha = value;
else
break; // Fail high
// RootMoves are already sorted by score in descending order
Value topScore = rootMoves[0].score;
- int delta = std::min(topScore - rootMoves[multiPV - 1].score, PawnValueMg);
+ int delta = std::min(topScore - rootMoves[multiPV - 1].score, PawnValue);
int maxScore = -VALUE_INFINITE;
double weakness = 120 - 2 * level;
projects / stockfish / blobdiff