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]
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;
// 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 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;
+ // Step 1. Initialize node
+ Thread* thisThread = pos.this_thread();
+ moveCount = playedMoveCount = 0;
oldAlpha = alpha;
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;
-
- }
- // 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;
+ 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;
- if (( Signals.stop
- || pos.is_draw<false>()
- || ss->ply > MAX_PLY) && !RootNode)
- return VALUE_DRAW;
+ // Used to send selDepth info to GUI
+ if (PvNode && thisThread->maxPly < ss->ply)
+ thisThread->maxPly = ss->ply;
- // 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 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.
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
&& abs(beta) < VALUE_MATE_IN_MAX_PLY
// 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)
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)
// 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;
// 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)
if ( PvNode
&& value > alpha
&& value < beta) // We want always alpha < beta
- alpha = value;
+ {
+ alpha = bestValue; // Update alpha here!
+ }
if (SpNode && !thisThread->cutoff_occurred())
{
- sp->bestValue = value;
- sp->bestMove = move;
+ sp->bestValue = bestValue;
+ sp->bestMove = bestMove;
sp->alpha = alpha;
- if (value >= beta)
+ if (bestValue >= beta)
sp->cutoff = true;
}
}
&& !Signals.stop
&& !thisThread->cutoff_occurred())
bestValue = Threads.split<FakeSplit>(pos, ss, alpha, beta, bestValue, &bestMove,
- depth, threatMove, moveCount, &mp, NT);
+ depth, threatMove, moveCount, mp, NT);
}
// Step 20. Check for mate and stalemate
// 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.
- if (!moveCount)
- return excludedMove ? oldAlpha : inCheck ? mated_in(ss->ply) : VALUE_DRAW;
+ // A split node has at least one move, the one tried before to be splitted.
+ if (!SpNode && !moveCount)
+ 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())
{
- move = bestValue <= oldAlpha ? MOVE_NONE : bestMove;
- bt = bestValue <= oldAlpha ? BOUND_UPPER
- : bestValue >= beta ? BOUND_LOWER : BOUND_EXACT;
+ Move ttm = bestValue <= oldAlpha ? MOVE_NONE : bestMove;
+ Bound bt = bestValue <= oldAlpha ? BOUND_UPPER
+ : bestValue >= beta ? BOUND_LOWER : BOUND_EXACT;
- TT.store(posKey, value_to_tt(bestValue, ss->ply), bt, depth, move, ss->eval, ss->evalMargin);
+ TT.store(posKey, value_to_tt(bestValue, ss->ply), bt, depth, ttm, ss->eval, ss->evalMargin);
// Update killers and history for non capture cut-off moves
if ( bestValue >= beta
- && !pos.is_capture_or_promotion(move)
+ && !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++)
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