/*
Stockfish, a UCI chess playing engine derived from Glaurung 2.1
Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
/*
Stockfish, a UCI chess playing engine derived from Glaurung 2.1
Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
Stockfish is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
Stockfish is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
template <NodeType NT>
Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth);
template <NodeType NT>
Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth);
void id_loop(Position& pos);
Value value_to_tt(Value v, int ply);
Value value_from_tt(Value v, int ply);
void id_loop(Position& pos);
Value value_to_tt(Value v, int ply);
Value value_from_tt(Value v, int ply);
- bool check_is_dangerous(Position& pos, Move move, Value futilityBase, Value beta);
- bool yields_to_threat(const Position& pos, Move move, Move threat);
- bool prevents_threat(const Position& pos, Move move, Move threat);
+ bool check_is_dangerous(const Position& pos, Move move, Value futilityBase, Value beta);
+ bool allows(const Position& pos, Move first, Move second);
+ bool refutes(const Position& pos, Move first, Move second);
string uci_pv(const Position& pos, int depth, Value alpha, Value beta);
struct Skill {
string uci_pv(const Position& pos, int depth, Value alpha, Value beta);
struct Skill {
static PolyglotBook book; // Defined static to initialize the PRNG only once
RootColor = RootPos.side_to_move();
static PolyglotBook book; // Defined static to initialize the PRNG only once
RootColor = RootPos.side_to_move();
if (Options["Contempt Factor"] && !Options["UCI_AnalyseMode"])
{
int cf = Options["Contempt Factor"] * PawnValueMg / 100; // From centipawns
if (Options["Contempt Factor"] && !Options["UCI_AnalyseMode"])
{
int cf = Options["Contempt Factor"] * PawnValueMg / 100; // From centipawns
+ // Reset the threads, still sleeping: will be wake up at split time
+ for (size_t i = 0; i < Threads.size(); i++)
+ Threads[i]->maxPly = 0;
+
+ Threads.sleepWhileIdle = Options["Use Sleeping Threads"];
// Set best timer interval to avoid lagging under time pressure. Timer is
// used to check for remaining available thinking time.
// Set best timer interval to avoid lagging under time pressure. Timer is
// 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);
+ Threads.timer->msec =
+ Limits.use_time_management() ? std::min(100, std::max(TimeMgr.available_time() / 16, TimerResolution)) :
+ Limits.nodes ? 2 * TimerResolution
+ : 100;
+
+ Threads.timer->notify_one(); // Wake up the recurring timer
- // but if we are pondering or in infinite search, we shouldn't print the best
- // move before we are told to do so.
+ // but if we are pondering or in infinite search, according to UCI protocol,
+ // we shouldn't print the best move before the GUI sends a "stop" or "ponderhit"
+ // command. We simply wait here until GUI sends one of those commands (that
+ // raise Signals.stop).
// Best move could be MOVE_NONE when searching on a stalemate position
sync_cout << "bestmove " << move_to_uci(RootMoves[0].pv[0], RootPos.is_chess960())
// Best move could be MOVE_NONE when searching on a stalemate position
sync_cout << "bestmove " << move_to_uci(RootMoves[0].pv[0], RootPos.is_chess960())
// we want to keep the same order for all the moves but the new
// PV that goes to the front. Note that in case of MultiPV search
// the already searched PV lines are preserved.
// we want to keep the same order for all the moves but the new
// PV that goes to the front. Note that in case of MultiPV search
// the already searched PV lines are preserved.
// Write PV back to transposition table in case the relevant
// entries have been overwritten during the search.
// Write PV back to transposition table in case the relevant
// entries have been overwritten during the search.
if (PVIdx + 1 == PVSize || Time::now() - SearchTime > 3000)
sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl;
}
if (PVIdx + 1 == PVSize || Time::now() - SearchTime > 3000)
sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl;
}
// Do we have time for the next iteration? Can we stop searching now?
if (Limits.use_time_management() && !Signals.stopOnPonderhit)
{
// Do we have time for the next iteration? Can we stop searching now?
if (Limits.use_time_management() && !Signals.stopOnPonderhit)
{
// Step 1. Initialize node
Thread* thisThread = pos.this_thread();
moveCount = playedMoveCount = 0;
// Step 1. Initialize node
Thread* thisThread = pos.this_thread();
moveCount = playedMoveCount = 0;
return DrawValue[pos.side_to_move()];
// Step 3. Mate distance pruning. Even if we mate at the next move our score
return DrawValue[pos.side_to_move()];
// Step 3. Mate distance pruning. Even if we mate at the next move our score
- // Following asserts are valid only in single thread condition because
- // TT access is always racy and its contents cannot be trusted.
- assert(tte->static_value() != VALUE_NONE || Threads.size() > 1);
- assert(ttValue != VALUE_NONE || tte->type() == BOUND_NONE || Threads.size() > 1);
-
- ss->staticEval = eval = tte->static_value();
- ss->evalMargin = tte->static_value_margin();
-
- if (eval == VALUE_NONE || ss->evalMargin == VALUE_NONE) // Due to a race
+ // Never assume anything on values stored in TT
+ if ( (ss->staticEval = eval = tte->eval_value()) == VALUE_NONE
+ ||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE)
eval = ss->staticEval = evaluate(pos, ss->evalMargin);
// Can ttValue be used as a better position evaluation?
eval = ss->staticEval = evaluate(pos, ss->evalMargin);
// Can ttValue be used as a better position evaluation?
(ss+1)->skipNullMove = true;
nullValue = depth-R < ONE_PLY ? -qsearch<NonPV, false>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
: - search<NonPV>(pos, ss+1, -beta, -alpha, depth-R);
(ss+1)->skipNullMove = false;
(ss+1)->skipNullMove = true;
nullValue = depth-R < ONE_PLY ? -qsearch<NonPV, false>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
: - search<NonPV>(pos, ss+1, -beta, -alpha, depth-R);
(ss+1)->skipNullMove = false;
- MovePicker mp(pos, ttMove, H, pos.captured_piece_type());
+ MovePicker mp(pos, ttMove, Hist, pos.captured_piece_type());
- MovePicker mp(pos, ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta);
+ MovePicker mp(pos, ttMove, depth, Hist, ss, PvNode ? -VALUE_INFINITE : beta);
CheckInfo ci(pos);
value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
singularExtensionNode = !RootNode
CheckInfo ci(pos);
value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
singularExtensionNode = !RootNode
// Move count based pruning
if ( depth < 16 * ONE_PLY
&& moveCount >= FutilityMoveCounts[depth]
// Move count based pruning
if ( depth < 16 * ONE_PLY
&& moveCount >= FutilityMoveCounts[depth]
// but fixing this made program slightly weaker.
Depth predictedDepth = newDepth - reduction<PvNode>(depth, moveCount);
futilityValue = ss->staticEval + ss->evalMargin + futility_margin(predictedDepth, moveCount)
// but fixing this made program slightly weaker.
Depth predictedDepth = newDepth - reduction<PvNode>(depth, moveCount);
futilityValue = ss->staticEval + ss->evalMargin + futility_margin(predictedDepth, moveCount)
{
ss->reduction = reduction<PvNode>(depth, moveCount);
Depth d = std::max(newDepth - ss->reduction, ONE_PLY);
{
ss->reduction = reduction<PvNode>(depth, moveCount);
Depth d = std::max(newDepth - ss->reduction, ONE_PLY);
- if (PvNode && value < beta)
- {
- alpha = value; // Update alpha here! Always alpha < beta
- if (SpNode) sp->alpha = value;
- }
+ if (PvNode && value < beta) // Update alpha! Always alpha < beta
+ alpha = SpNode ? sp->alpha = value : value;
- && depth >= Threads.min_split_depth()
- && bestValue < beta
- && Threads.available_slave_exists(thisThread))
+ && depth >= Threads.minimumSplitDepth
+ && Threads.available_slave(thisThread)
+ && thisThread->splitPointsSize < MAX_SPLITPOINTS_PER_THREAD)
- bestValue = Threads.split<FakeSplit>(pos, ss, alpha, beta, bestValue, &bestMove,
- depth, threatMove, moveCount, mp, NT);
+ assert(bestValue < beta);
+
+ thisThread->split<FakeSplit>(pos, ss, alpha, beta, &bestValue, &bestMove,
+ depth, threatMove, moveCount, &mp, NT);
// Decrease history of all the other played non-capture moves
for (int i = 0; i < playedMoveCount - 1; i++)
{
Move m = movesSearched[i];
// Decrease history of all the other played non-capture moves
for (int i = 0; i < playedMoveCount - 1; i++)
{
Move m = movesSearched[i];
assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE);
assert(PvNode || (alpha == beta - 1));
assert(depth <= DEPTH_ZERO);
assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE);
assert(PvNode || (alpha == beta - 1));
assert(depth <= DEPTH_ZERO);
Key posKey;
Move ttMove, move, bestMove;
Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha;
Key posKey;
Move ttMove, move, bestMove;
Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha;
- bool givesCheck, enoughMaterial, evasionPrunable, fromNull;
+ bool givesCheck, enoughMaterial, evasionPrunable;
return DrawValue[pos.side_to_move()];
// Transposition table lookup. At PV nodes, we don't use the TT for
return DrawValue[pos.side_to_move()];
// Transposition table lookup. At PV nodes, we don't use the TT for
- assert(tte->static_value() != VALUE_NONE || Threads.size() > 1);
-
- ss->staticEval = bestValue = tte->static_value();
- ss->evalMargin = tte->static_value_margin();
-
- if (ss->staticEval == VALUE_NONE || ss->evalMargin == VALUE_NONE) // Due to a race
+ // Never assume anything on values stored in TT
+ if ( (ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE
+ ||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE)
// to search the moves. Because the depth is <= 0 here, only captures,
// queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
// be generated.
// to search the moves. Because the depth is <= 0 here, only captures,
// queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
// be generated.
- MovePicker mp(pos, ttMove, depth, H, to_sq((ss-1)->currentMove));
+ MovePicker mp(pos, ttMove, depth, Hist, to_sq((ss-1)->currentMove));
- bool check_is_dangerous(Position& pos, Move move, Value futilityBase, Value beta)
+ bool check_is_dangerous(const Position& pos, Move move, Value futilityBase, Value beta)
- // yields_to_threat() tests whether the move at previous ply yields to the so
- // called threat move (the best move returned from a null search that fails
- // low). Here 'yields to' means that the move somehow made the threat possible
- // for instance if the moving piece is the same in both moves.
+ // allows() tests whether the 'first' move at previous ply somehow makes the
+ // 'second' move possible, for instance if the moving piece is the same in
+ // both moves. Normally the second move is the threat (the best move returned
+ // from a null search that fails low).
- Square mfrom = from_sq(move);
- Square mto = to_sq(move);
- Square tfrom = from_sq(threat);
- Square tto = to_sq(threat);
+ Square m1from = from_sq(first);
+ Square m2from = from_sq(second);
+ Square m1to = to_sq(first);
+ Square m2to = to_sq(second);
- // The piece is the same or threat's destination was vacated by the move
- if (mto == tfrom || tto == mfrom)
+ // The piece is the same or second's destination was vacated by the first move
+ if (m1to == m2from || m2to == m1from)
- // Threat moves through the vacated square
- if (between_bb(tfrom, tto) & mfrom)
+ // Second one moves through the square vacated by first one
+ if (between_bb(m2from, m2to) & m1from)
- // Threat's destination is defended by the move's piece
- Bitboard matt = pos.attacks_from(pos.piece_on(mto), mto, pos.pieces() ^ tfrom);
- if (matt & tto)
+ // Second's destination is defended by the first move's piece
+ Bitboard m1att = pos.attacks_from(pos.piece_on(m1to), m1to, pos.pieces() ^ m2from);
+ if (m1att & m2to)
- // Threat gives a discovered check through the move's checking piece
- if (matt & pos.king_square(pos.side_to_move()))
+ // Second move gives a discovered check through the first's checking piece
+ if (m1att & pos.king_square(pos.side_to_move()))
- // prevents_threat() tests whether a move is able to defend against the so
- // called threat move (the best move returned from a null search that fails
- // low). In this case will not be pruned.
+ // refutes() tests whether a 'first' move is able to defend against a 'second'
+ // opponent's move. In this case will not be pruned. Normally the second move
+ // is the threat (the best move returned from a null search that fails low).
- Square mfrom = from_sq(move);
- Square mto = to_sq(move);
- Square tfrom = from_sq(threat);
- Square tto = to_sq(threat);
+ Square m1from = from_sq(first);
+ Square m2from = from_sq(second);
+ Square m1to = to_sq(first);
+ Square m2to = to_sq(second);
return true;
// If the threatened piece has value less than or equal to the value of the
// threat piece, don't prune moves which defend it.
return true;
// If the threatened piece has value less than or equal to the value of the
// threat piece, don't prune moves which defend it.
- if ( pos.is_capture(threat)
- && ( PieceValue[MG][pos.piece_on(tfrom)] >= PieceValue[MG][pos.piece_on(tto)]
- || type_of(pos.piece_on(tfrom)) == KING))
+ if ( pos.is_capture(second)
+ && ( PieceValue[MG][pos.piece_on(m2from)] >= PieceValue[MG][pos.piece_on(m2to)]
+ || type_of(pos.piece_on(m2from)) == KING))
- Bitboard xray = (attacks_bb< ROOK>(tto, occ) & pos.pieces(color_of(piece), QUEEN, ROOK))
- | (attacks_bb<BISHOP>(tto, occ) & pos.pieces(color_of(piece), QUEEN, BISHOP));
+ Bitboard xray = (attacks_bb< ROOK>(m2to, occ) & pos.pieces(color_of(piece), QUEEN, ROOK))
+ | (attacks_bb<BISHOP>(m2to, occ) & pos.pieces(color_of(piece), QUEEN, BISHOP));
pos.do_move(pv[ply++], *st++);
tte = TT.probe(pos.key());
pos.do_move(pv[ply++], *st++);
tte = TT.probe(pos.key());
&& pos.is_pseudo_legal(m = tte->move()) // Local copy, TT could change
&& pos.pl_move_is_legal(m, pos.pinned_pieces())
&& ply < MAX_PLY
&& pos.is_pseudo_legal(m = tte->move()) // Local copy, TT could change
&& pos.pl_move_is_legal(m, pos.pinned_pieces())
&& ply < MAX_PLY
- TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], v, m);
- }
+ assert(MoveList<LEGAL>(pos).contains(pv[ply]));
pos.do_move(pv[ply++], *st++);
} while (pv[ply] != MOVE_NONE);
pos.do_move(pv[ply++], *st++);
} while (pv[ply] != MOVE_NONE);
- // Pointer 'sp_master', if non-NULL, points to the active SplitPoint
- // object for which the thread is the master.
- const SplitPoint* sp_master = splitPointsCnt ? curSplitPoint : NULL;
+ // Pointer 'this_sp' is not null only if we are called from split(), and not
+ // at the thread creation. So it means we are the split point's master.
+ const SplitPoint* this_sp = splitPointsSize ? activeSplitPoint : NULL;
- // If this thread is the master of a split point and all slaves have
- // finished their work at this split point, return from the idle loop.
- while (!sp_master || sp_master->slavesMask)
+ // If this thread is the master of a split point and all slaves have finished
+ // their work at this split point, return from the idle loop.
+ while (!this_sp || this_sp->slavesMask)
- // If we are not searching, wait for a condition to be signaled
- // instead of wasting CPU time polling for work.
- while ( do_sleep
- || do_exit
- || (!is_searching && Threads.use_sleeping_threads()))
+ // If we are not searching, wait for a condition to be signaled instead of
+ // wasting CPU time polling for work.
+ while ((!searching && Threads.sleepWhileIdle) || exit)
- // If we are master and all slaves have finished don't go to sleep
- if (sp_master && !sp_master->slavesMask)
+ // If we are master and all slaves have finished then exit idle_loop
+ if (this_sp && !this_sp->slavesMask)
// Do sleep after retesting sleep conditions under lock protection, in
// particular we need to avoid a deadlock in case a master thread has,
// Do sleep after retesting sleep conditions under lock protection, in
// particular we need to avoid a deadlock in case a master thread has,
- // in the meanwhile, allocated us and sent the wake_up() call before we
- // had the chance to grab the lock.
- if (do_sleep || !is_searching)
+ // in the meanwhile, allocated us and sent the notify_one() call before
+ // we had the chance to grab the lock.
+ if (!searching && !exit)
sleepCondition.wait(mutex);
mutex.unlock();
}
// If this thread has been assigned work, launch a search
sleepCondition.wait(mutex);
mutex.unlock();
}
// If this thread has been assigned work, launch a search
search<SplitPointRoot>(pos, ss+1, sp->alpha, sp->beta, sp->depth);
search<SplitPointRoot>(pos, ss+1, sp->alpha, sp->beta, sp->depth);
search<SplitPointPV>(pos, ss+1, sp->alpha, sp->beta, sp->depth);
search<SplitPointPV>(pos, ss+1, sp->alpha, sp->beta, sp->depth);
search<SplitPointNonPV>(pos, ss+1, sp->alpha, sp->beta, sp->depth);
search<SplitPointNonPV>(pos, ss+1, sp->alpha, sp->beta, sp->depth);
- // Wake up master thread so to allow it to return from the idle loop in
- // case we are the last slave of the split point.
- if ( Threads.use_sleeping_threads()
- && this != sp->master
+ // Wake up master thread so to allow it to return from the idle loop
+ // in case we are the last slave of the split point.
+ if ( Threads.sleepWhileIdle
+ && this != sp->masterThread
nodes = RootPos.nodes_searched();
// Loop across all split points and sum accumulated SplitPoint nodes plus
nodes = RootPos.nodes_searched();
// Loop across all split points and sum accumulated SplitPoint nodes plus