// Set to true to force running with one thread. Used for debugging
const bool FakeSplit = false;
+ // This is the minimum interval in msec between two check_time() calls
+ const int TimerResolution = 5;
+
// Different node types, used as template parameter
enum NodeType { Root, PV, NonPV, SplitPointRoot, SplitPointPV, SplitPointNonPV };
const bool Slidings[18] = { 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1 };
inline bool piece_is_slider(Piece p) { return Slidings[p]; }
- // Maximum depth for razoring
- const Depth RazorDepth = 4 * ONE_PLY;
-
// Dynamic razoring margin based on depth
inline Value razor_margin(Depth d) { return Value(512 + 16 * int(d)); }
- // Maximum depth for use of dynamic threat detection when null move fails low
- const Depth ThreatDepth = 5 * ONE_PLY;
-
- // Minimum depth for use of internal iterative deepening
- const Depth IIDDepth[] = { 8 * ONE_PLY, 5 * ONE_PLY };
-
- // At Non-PV nodes we do an internal iterative deepening search
- // when the static evaluation is bigger then beta - IIDMargin.
- const Value IIDMargin = Value(256);
-
- // Minimum depth for use of singular extension
- const Depth SingularExtensionDepth[] = { 8 * ONE_PLY, 6 * ONE_PLY };
-
- // Futility margin for quiescence search
- const Value FutilityMarginQS = Value(128);
-
// Futility lookup tables (initialized at startup) and their access functions
Value FutilityMargins[16][64]; // [depth][moveNumber]
int FutilityMoveCounts[32]; // [depth]
: 2 * VALUE_INFINITE;
}
- inline int futility_move_count(Depth d) {
-
- return d < 16 * ONE_PLY ? FutilityMoveCounts[d] : MAX_MOVES;
- }
-
// Reduction lookup tables (initialized at startup) and their access function
int8_t Reductions[2][64][64]; // [pv][depth][moveNumber]
return (Depth) Reductions[PvNode][std::min(int(d) / ONE_PLY, 63)][std::min(mn, 63)];
}
- // Easy move margin. An easy move candidate must be at least this much better
- // than the second best move.
- const Value EasyMoveMargin = Value(0x150);
-
- // This is the minimum interval in msec between two check_time() calls
- const int TimerResolution = 5;
-
-
size_t MultiPV, UCIMultiPV, PVIdx;
TimeManager TimeMgr;
int BestMoveChanges;
bool SkillLevelEnabled, Chess960;
History H;
-
template <NodeType NT>
Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth);
Position& pos = RootPosition;
Chess960 = pos.is_chess960();
Eval::RootColor = pos.side_to_move();
+ Eval::ValueDraw[ Eval::RootColor] = VALUE_DRAW - Eval::ContemptFactor;
+ Eval::ValueDraw[~Eval::RootColor] = VALUE_DRAW + Eval::ContemptFactor;
TimeMgr.init(Limits, pos.startpos_ply_counter(), pos.side_to_move());
TT.new_search();
H.clear();
// used to check for remaining available thinking time.
if (Limits.use_time_management())
Threads.set_timer(std::min(100, std::max(TimeMgr.available_time() / 16, TimerResolution)));
+ else if (Limits.nodes)
+ Threads.set_timer(2 * TimerResolution);
else
Threads.set_timer(100);
&& ( (bestMoveNeverChanged && pos.captured_piece_type())
|| Time::now() - SearchTime > (TimeMgr.available_time() * 40) / 100))
{
- Value rBeta = bestValue - EasyMoveMargin;
+ Value rBeta = bestValue - 2 * PawnValueMg;
(ss+1)->excludedMove = RootMoves[0].pv[0];
(ss+1)->skipNullMove = true;
Value v = search<NonPV>(pos, ss+1, rBeta - 1, rBeta, (depth - 3) * ONE_PLY);
const bool RootNode = (NT == Root || NT == SplitPointRoot);
assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE);
- assert((alpha == beta - 1) || PvNode);
+ assert(PvNode || (alpha == beta - 1));
assert(depth > DEPTH_ZERO);
Move movesSearched[64];
StateInfo st;
const TTEntry *tte;
+ SplitPoint* sp;
Key posKey;
Move ttMove, move, excludedMove, bestMove, threatMove;
Depth ext, newDepth;
- Bound bt;
- Value bestValue, value, oldAlpha, ttValue;
- Value refinedValue, nullValue, futilityBase, futilityValue;
+ Value bestValue, value, ttValue;
+ Value refinedValue, nullValue, futilityValue;
bool pvMove, inCheck, singularExtensionNode, givesCheck;
bool captureOrPromotion, dangerous, doFullDepthSearch;
- int moveCount = 0, playedMoveCount = 0;
- Thread* thisThread = pos.this_thread();
- SplitPoint* sp = NULL;
+ int moveCount, playedMoveCount;
- refinedValue = bestValue = value = -VALUE_INFINITE;
- oldAlpha = alpha;
+ // Step 1. Initialize node
+ Thread* thisThread = pos.this_thread();
+ moveCount = playedMoveCount = 0;
inCheck = pos.in_check();
- ss->ply = (ss-1)->ply + 1;
- // Used to send selDepth info to GUI
- if (PvNode && thisThread->maxPly < ss->ply)
- thisThread->maxPly = ss->ply;
-
- // Step 1. Initialize node
if (SpNode)
{
- tte = NULL;
- ttMove = excludedMove = MOVE_NONE;
- ttValue = VALUE_ZERO;
sp = ss->sp;
- bestMove = sp->bestMove;
+ bestMove = sp->bestMove;
threatMove = sp->threatMove;
- bestValue = sp->bestValue;
- moveCount = sp->moveCount; // Lock must be held here
+ bestValue = sp->bestValue;
+ tte = NULL;
+ ttMove = excludedMove = MOVE_NONE;
+ ttValue = VALUE_NONE;
- assert(bestValue > -VALUE_INFINITE && moveCount > 0);
+ assert(sp->bestValue > -VALUE_INFINITE && sp->moveCount > 0);
goto split_point_start;
}
- else
- {
- ss->currentMove = threatMove = (ss+1)->excludedMove = bestMove = MOVE_NONE;
- (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO;
- (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE;
- }
+ bestValue = -VALUE_INFINITE;
+ ss->currentMove = threatMove = (ss+1)->excludedMove = bestMove = MOVE_NONE;
+ ss->ply = (ss-1)->ply + 1;
+ (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO;
+ (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE;
+
+ // Used to send selDepth info to GUI
+ if (PvNode && thisThread->maxPly < ss->ply)
+ thisThread->maxPly = ss->ply;
- // Step 2. Check for aborted search and immediate draw
- // Enforce node limit here. FIXME: This only works with 1 search thread.
- if (Limits.nodes && pos.nodes_searched() >= Limits.nodes)
- Signals.stop = true;
-
- if (( Signals.stop
- || pos.is_draw<false>()
- || ss->ply > MAX_PLY) && !RootNode)
- return VALUE_DRAW;
-
- // Step 3. Mate distance pruning. Even if we mate at the next move our score
- // would be at best mate_in(ss->ply+1), but if alpha is already bigger because
- // a shorter mate was found upward in the tree then there is no need to search
- // further, we will never beat current alpha. Same logic but with reversed signs
- // applies also in the opposite condition of being mated instead of giving mate,
- // in this case return a fail-high score.
if (!RootNode)
{
+ // Step 2. Check for aborted search and immediate draw
+ if (Signals.stop || pos.is_draw<false>() || ss->ply > MAX_PLY)
+ return Eval::ValueDraw[pos.side_to_move()];
+
+ // Step 3. Mate distance pruning. Even if we mate at the next move our score
+ // would be at best mate_in(ss->ply+1), but if alpha is already bigger because
+ // a shorter mate was found upward in the tree then there is no need to search
+ // further, we will never beat current alpha. Same logic but with reversed signs
+ // applies also in the opposite condition of being mated instead of giving mate,
+ // in this case return a fail-high score.
alpha = std::max(mated_in(ss->ply), alpha);
beta = std::min(mate_in(ss->ply+1), beta);
if (alpha >= beta)
posKey = excludedMove ? pos.exclusion_key() : pos.key();
tte = TT.probe(posKey);
ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE;
- ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_ZERO;
+ ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
// At PV nodes we check for exact scores, while at non-PV nodes we check for
// a fail high/low. Biggest advantage at probing at PV nodes is to have a
// Step 5. Evaluate the position statically and update parent's gain statistics
if (inCheck)
- ss->eval = ss->evalMargin = VALUE_NONE;
+ ss->eval = ss->evalMargin = refinedValue = VALUE_NONE;
else if (tte)
{
assert(tte->static_value() != VALUE_NONE);
// Step 6. Razoring (is omitted in PV nodes)
if ( !PvNode
- && depth < RazorDepth
+ && depth < 4 * ONE_PLY
&& !inCheck
&& refinedValue + razor_margin(depth) < beta
&& ttMove == MOVE_NONE
// the score by more than futility_margin(depth) if we do a null move.
if ( !PvNode
&& !ss->skipNullMove
- && depth < RazorDepth
+ && depth < 4 * ONE_PLY
&& !inCheck
- && refinedValue - futility_margin(depth, 0) >= beta
+ && refinedValue - FutilityMargins[depth][0] >= beta
&& abs(beta) < VALUE_MATE_IN_MAX_PLY
&& pos.non_pawn_material(pos.side_to_move()))
- return refinedValue - futility_margin(depth, 0);
+ return refinedValue - FutilityMargins[depth][0];
// Step 8. Null move search with verification search (is omitted in PV nodes)
if ( !PvNode
// parent node, which will trigger a re-search with full depth).
threatMove = (ss+1)->currentMove;
- if ( depth < ThreatDepth
+ if ( depth < 5 * ONE_PLY
&& (ss-1)->reduction
&& threatMove != MOVE_NONE
&& connected_moves(pos, (ss-1)->currentMove, threatMove))
// and a reduced search returns a value much above beta, we can (almost) safely
// prune the previous move.
if ( !PvNode
- && depth >= RazorDepth + ONE_PLY
+ && depth >= 5 * ONE_PLY
&& !inCheck
&& !ss->skipNullMove
&& excludedMove == MOVE_NONE
}
// Step 10. Internal iterative deepening
- if ( depth >= IIDDepth[PvNode]
+ if ( depth >= (PvNode ? 5 * ONE_PLY : 8 * ONE_PLY)
&& ttMove == MOVE_NONE
- && (PvNode || (!inCheck && ss->eval + IIDMargin >= beta)))
+ && (PvNode || (!inCheck && ss->eval + Value(256) >= beta)))
{
Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
MovePicker mp(pos, ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta);
CheckInfo ci(pos);
- futilityBase = ss->eval + ss->evalMargin;
+ value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
singularExtensionNode = !RootNode
&& !SpNode
- && depth >= SingularExtensionDepth[PvNode]
+ && depth >= (PvNode ? 6 * ONE_PLY : 8 * ONE_PLY)
&& ttMove != MOVE_NONE
&& !excludedMove // Recursive singular search is not allowed
&& (tte->type() & BOUND_LOWER)
// Step 11. Loop through moves
// Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs
- while ( bestValue < beta
- && (move = mp.next_move<SpNode>()) != MOVE_NONE
- && !thisThread->cutoff_occurred()
- && !Signals.stop)
+ while ((move = mp.next_move<SpNode>()) != MOVE_NONE)
{
assert(is_ok(move));
ss->excludedMove = MOVE_NONE;
if (value < rBeta)
- ext = ONE_PLY;
+ ext = rBeta >= beta ? ONE_PLY + ONE_PLY / 2 : ONE_PLY;
}
// Update current move (this must be done after singular extension search)
&& (bestValue > VALUE_MATED_IN_MAX_PLY || bestValue == -VALUE_INFINITE))
{
// Move count based pruning
- if ( moveCount >= futility_move_count(depth)
+ if ( depth < 16 * ONE_PLY
+ && moveCount >= FutilityMoveCounts[depth]
&& (!threatMove || !connected_threat(pos, move, threatMove)))
{
if (SpNode)
// We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
// but fixing this made program slightly weaker.
Depth predictedDepth = newDepth - reduction<PvNode>(depth, moveCount);
- futilityValue = futilityBase + futility_margin(predictedDepth, moveCount)
+ futilityValue = ss->eval + ss->evalMargin + futility_margin(predictedDepth, moveCount)
+ H.gain(pos.piece_moved(move), to_sq(move));
if (futilityValue < beta)
continue;
}
- pvMove = PvNode ? moveCount <= 1 : false;
+ pvMove = PvNode ? moveCount == 1 : false;
ss->currentMove = move;
if (!SpNode && !captureOrPromotion && playedMoveCount < 64)
movesSearched[playedMoveCount++] = move;
// was aborted because the user interrupted the search or because we
// ran out of time. In this case, the return value of the search cannot
// be trusted, and we don't update the best move and/or PV.
- if (RootNode && !Signals.stop)
+ if (Signals.stop || thisThread->cutoff_occurred())
+ return bestValue;
+
+ if (RootNode)
{
RootMove& rm = *std::find(RootMoves.begin(), RootMoves.end(), move);
// is not a problem when sorting becuase sort is stable and move
// position in the list is preserved, just the PV is pushed up.
rm.score = -VALUE_INFINITE;
-
}
if (value > bestValue)
{
bestValue = value;
- bestMove = move;
-
- if ( PvNode
- && value > alpha
- && value < beta) // We want always alpha < beta
- alpha = value;
+ if (SpNode) sp->bestValue = value;
- if (SpNode && !thisThread->cutoff_occurred())
+ if (value > alpha)
{
- sp->bestValue = value;
- sp->bestMove = move;
- sp->alpha = alpha;
-
- if (value >= beta)
- sp->cutoff = true;
+ bestMove = move;
+ if (SpNode) sp->bestMove = move;
+
+ if (PvNode && value < beta)
+ {
+ alpha = value; // Update alpha here! Always alpha < beta
+ if (SpNode) sp->alpha = alpha;
+ }
+ else // Fail high
+ {
+ if (SpNode) sp->cutoff = true;
+ break;
+ }
}
}
- // Step 19. Check for split
+ // Step 19. Check for splitting the search
if ( !SpNode
&& depth >= Threads.min_split_depth()
&& bestValue < beta
- && Threads.available_slave_exists(thisThread)
- && !Signals.stop
- && !thisThread->cutoff_occurred())
+ && Threads.available_slave_exists(thisThread))
+ {
bestValue = Threads.split<FakeSplit>(pos, ss, alpha, beta, bestValue, &bestMove,
- depth, threatMove, moveCount, &mp, NT);
+ depth, threatMove, moveCount, mp, NT);
+ break;
+ }
}
+ if (SpNode)
+ return bestValue;
+
// Step 20. Check for mate and stalemate
// All legal moves have been searched and if there are no legal moves, it
// must be mate or stalemate. Note that we can have a false positive in
// case of Signals.stop or thread.cutoff_occurred() are set, but this is
// harmless because return value is discarded anyhow in the parent nodes.
// If we are in a singular extension search then return a fail low score.
+ // A split node has at least one move, the one tried before to be splitted.
if (!moveCount)
- return excludedMove ? oldAlpha : inCheck ? mated_in(ss->ply) : VALUE_DRAW;
+ return excludedMove ? alpha : inCheck ? mated_in(ss->ply) : VALUE_DRAW;
// If we have pruned all the moves without searching return a fail-low score
if (bestValue == -VALUE_INFINITE)
{
assert(!playedMoveCount);
- bestValue = oldAlpha;
+ bestValue = alpha;
}
- // Step 21. Update tables
- // Update transposition table entry, killers and history
- if (!SpNode && !Signals.stop && !thisThread->cutoff_occurred())
+ if (bestValue >= beta) // Failed high
{
- move = bestValue <= oldAlpha ? MOVE_NONE : bestMove;
- bt = bestValue <= oldAlpha ? BOUND_UPPER
- : bestValue >= beta ? BOUND_LOWER : BOUND_EXACT;
+ TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth,
+ bestMove, ss->eval, ss->evalMargin);
- TT.store(posKey, value_to_tt(bestValue, ss->ply), bt, depth, move, ss->eval, ss->evalMargin);
-
- // Update killers and history for non capture cut-off moves
- if ( bestValue >= beta
- && !pos.is_capture_or_promotion(move)
- && !inCheck)
+ if (!pos.is_capture_or_promotion(bestMove) && !inCheck)
{
- if (move != ss->killers[0])
+ if (bestMove != ss->killers[0])
{
ss->killers[1] = ss->killers[0];
- ss->killers[0] = move;
+ ss->killers[0] = bestMove;
}
// Increase history value of the cut-off move
Value bonus = Value(int(depth) * int(depth));
- H.add(pos.piece_moved(move), to_sq(move), bonus);
+ H.add(pos.piece_moved(bestMove), to_sq(bestMove), bonus);
// Decrease history of all the other played non-capture moves
for (int i = 0; i < playedMoveCount - 1; i++)
}
}
}
+ else // Failed low or PV search
+ TT.store(posKey, value_to_tt(bestValue, ss->ply),
+ PvNode && bestMove != MOVE_NONE ? BOUND_EXACT : BOUND_UPPER,
+ depth, bestMove, ss->eval, ss->evalMargin);
assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
// Check for an instant draw or maximum ply reached
if (pos.is_draw<true>() || ss->ply > MAX_PLY)
- return VALUE_DRAW;
+ return Eval::ValueDraw[pos.side_to_move()];
// Decide whether or not to include checks, this fixes also the type of
// TT entry depth that we are going to use. Note that in qsearch we use
if (PvNode && bestValue > alpha)
alpha = bestValue;
- futilityBase = ss->eval + evalMargin + FutilityMarginQS;
+ futilityBase = ss->eval + evalMargin + Value(128);
enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMg;
}
int s = RootMoves[i].score;
// Don't allow crazy blunders even at very low skills
- if (i > 0 && RootMoves[i-1].score > s + EasyMoveMargin)
+ if (i > 0 && RootMoves[i-1].score > s + 2 * PawnValueMg)
break;
// This is our magic formula
sp->mutex.lock();
+ assert(sp->activePositions[idx] == NULL);
+
+ sp->activePositions[idx] = &pos;
+
if (sp->nodeType == Root)
search<SplitPointRoot>(pos, ss+1, sp->alpha, sp->beta, sp->depth);
else if (sp->nodeType == PV)
assert(is_searching);
is_searching = false;
+ sp->activePositions[idx] = NULL;
sp->slavesMask &= ~(1ULL << idx);
sp->nodes += pos.nodes_searched();
void check_time() {
static Time::point lastInfoTime = Time::now();
+ int64_t nodes = 0; // Workaround silly 'uninitialized' gcc warning
if (Time::now() - lastInfoTime >= 1000)
{
if (Limits.ponder)
return;
+ if (Limits.nodes)
+ {
+ Threads.mutex.lock();
+
+ nodes = RootPosition.nodes_searched();
+
+ // Loop across all split points and sum accumulated SplitPoint nodes plus
+ // all the currently active slaves positions.
+ for (size_t i = 0; i < Threads.size(); i++)
+ for (int j = 0; j < Threads[i].splitPointsCnt; j++)
+ {
+ SplitPoint& sp = Threads[i].splitPoints[j];
+
+ sp.mutex.lock();
+
+ nodes += sp.nodes;
+ Bitboard sm = sp.slavesMask;
+ while (sm)
+ {
+ Position* pos = sp.activePositions[pop_lsb(&sm)];
+ nodes += pos ? pos->nodes_searched() : 0;
+ }
+
+ sp.mutex.unlock();
+ }
+
+ Threads.mutex.unlock();
+ }
+
Time::point elapsed = Time::now() - SearchTime;
bool stillAtFirstMove = Signals.firstRootMove
&& !Signals.failedLowAtRoot
|| stillAtFirstMove;
if ( (Limits.use_time_management() && noMoreTime)
- || (Limits.movetime && elapsed >= Limits.movetime))
+ || (Limits.movetime && elapsed >= Limits.movetime)
+ || (Limits.nodes && nodes >= Limits.nodes))
Signals.stop = true;
}
projects / stockfish / blobdiff