// Minimum depth for use of singular extension
const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */};
- // If the TT move is at least SingularExtensionMargin better than the
- // remaining ones we will extend it.
- const Value SingularExtensionMargin = Value(0x20);
-
// Step 12. Futility pruning
// Futility margin for quiescence search
void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
void update_killers(Move m, Move killers[]);
void update_gains(const Position& pos, Move move, Value before, Value after);
- void qsearch_scoring(Position& pos, MoveStack* mlist, MoveStack* last);
int current_search_time();
std::string value_to_uci(Value v);
- int nps(const Position& pos);
+ std::string speed_to_uci(int64_t nodes);
void poll(const Position& pos);
void wait_for_stop_or_ponderhit();
Move bestMove = id_loop(pos, searchMoves, &ponderMove);
// Print final search statistics
- cout << "info nodes " << pos.nodes_searched()
- << " nps " << nps(pos)
- << " time " << current_search_time() << endl;
+ cout << "info" << speed_to_uci(pos.nodes_searched()) << endl;
if (UseLogFile)
{
+ int t = current_search_time();
+
LogFile << "Nodes: " << pos.nodes_searched()
- << "\nNodes/second: " << nps(pos)
+ << "\nNodes/second: " << (t > 0 ? int(pos.nodes_searched() * 1000 / t) : 0)
<< "\nBest move: " << move_to_san(pos, bestMove);
StateInfo st;
if (!StopRequest && (Pondering || InfiniteSearch))
wait_for_stop_or_ponderhit();
- // Could be both MOVE_NONE when searching on a stalemate position
- cout << "bestmove " << bestMove << " ponder " << ponderMove << endl;
+ // Could be MOVE_NONE when searching on a stalemate position
+ cout << "bestmove " << bestMove;
+
+ // UCI protol is not clear on allowing sending an empty ponder move, instead
+ // it is clear that ponder move is optional. So skip it if empty.
+ if (ponderMove != MOVE_NONE)
+ cout << " ponder " << ponderMove;
+
+ cout << endl;
return !QuitRequest;
}
SearchStack ss[PLY_MAX_PLUS_2];
Value bestValues[PLY_MAX_PLUS_2];
int bestMoveChanges[PLY_MAX_PLUS_2];
- int depth, researchCountFL, researchCountFH, aspirationDelta;
+ int depth, aspirationDelta;
Value value, alpha, beta;
Move bestMove, easyMove;
- // Moves to search are verified, scored and sorted
- Rml.init(pos, searchMoves);
-
- // Initialize FIXME move before Rml.init()
+ // Initialize stuff before a new search
+ memset(ss, 0, 4 * sizeof(SearchStack));
TT.new_search();
H.clear();
- memset(ss, 0, PLY_MAX_PLUS_2 * sizeof(SearchStack));
*ponderMove = bestMove = easyMove = MOVE_NONE;
depth = aspirationDelta = 0;
- ss->currentMove = MOVE_NULL; // Hack to skip update_gains()
alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
+ ss->currentMove = MOVE_NULL; // Hack to skip update_gains()
+
+ // Moves to search are verified and copied
+ Rml.init(pos, searchMoves);
// Handle special case of searching on a mate/stalemate position
if (Rml.size() == 0)
return MOVE_NONE;
}
- // Is one move significantly better than others after initial scoring ?
- if ( Rml.size() == 1
- || Rml[0].pv_score > Rml[1].pv_score + EasyMoveMargin)
- easyMove = Rml[0].pv[0];
-
// Iterative deepening loop
while (++depth <= PLY_MAX && (!MaxDepth || depth <= MaxDepth) && !StopRequest)
{
- Rml.bestMoveChanges = researchCountFL = researchCountFH = 0;
+ Rml.bestMoveChanges = 0;
cout << "info depth " << depth << endl;
// Calculate dynamic aspiration window based on previous iterations
// Start with a small aspiration window and, in case of fail high/low,
// research with bigger window until not failing high/low anymore.
- while (true)
- {
+ do {
// Search starting from ss+1 to allow calling update_gains()
value = search<PV, false, true>(pos, ss+1, alpha, beta, depth * ONE_PLY, 0);
// otherwise exit the fail high/low loop.
if (value >= beta)
{
- beta = Min(beta + aspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
- researchCountFH++;
+ beta = Min(beta + aspirationDelta, VALUE_INFINITE);
+ aspirationDelta += aspirationDelta / 2;
}
else if (value <= alpha)
{
AspirationFailLow = true;
StopOnPonderhit = false;
- alpha = Max(alpha - aspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
- researchCountFL++;
+ alpha = Max(alpha - aspirationDelta, -VALUE_INFINITE);
+ aspirationDelta += aspirationDelta / 2;
}
else
break;
- }
+
+ } while (abs(value) < VALUE_KNOWN_WIN);
// Collect info about search result
bestMove = Rml[0].pv[0];
if (UseLogFile)
LogFile << pretty_pv(pos, depth, value, current_search_time(), Rml[0].pv) << endl;
- // Drop the easy move if differs from the new best move
- if (bestMove != easyMove)
+ // Init easyMove after first iteration or drop if differs from the best move
+ if (depth == 1 && (Rml.size() == 1 || Rml[0].pv_score > Rml[1].pv_score + EasyMoveMargin))
+ easyMove = bestMove;
+ else if (bestMove != easyMove)
easyMove = MOVE_NONE;
if (UseTimeManagement && !StopRequest)
bestValue = alpha;
// Step 1. Initialize node and poll. Polling can abort search
- ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
+ ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE;
+ (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO;
(ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
if (SendSearchedNodes)
{
SendSearchedNodes = false;
- cout << "info nodes " << nodes
- << " nps " << nps(pos)
- << " time " << current_search_time() << endl;
+ cout << "info" << speed_to_uci(pos.nodes_searched()) << endl;
}
if (current_search_time() >= 1000)
<< " currmovenumber " << moveCount << endl;
}
- isPvMove = (PvNode && moveCount <= (Root ? MultiPV : 1));
+ // At Root and at first iteration do a PV search on all the moves
+ // to score root moves. Otherwise only the first one is the PV.
+ isPvMove = (PvNode && moveCount <= (Root ? MultiPV + 1000 * (depth <= ONE_PLY) : 1));
moveIsCheck = pos.move_is_check(move, ci);
captureOrPromotion = pos.move_is_capture_or_promotion(move);
if (abs(ttValue) < VALUE_KNOWN_WIN)
{
- Value b = ttValue - SingularExtensionMargin;
+ Value b = ttValue - depth;
ss->excludedMove = move;
ss->skipNullMove = true;
Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
// Update current move (this must be done after singular extension search)
ss->currentMove = move;
- newDepth = depth - (!Root ? ONE_PLY : DEPTH_ZERO) + ext;
+ newDepth = depth - ONE_PLY + ext;
// Step 12. Futility pruning (is omitted in PV nodes)
if ( !PvNode
alpha = sp->alpha;
}
- if (!Root && value > bestValue && !(SpNode && ThreadsMgr.cutoff_at_splitpoint(threadID)))
+ if (value > bestValue && !(SpNode && ThreadsMgr.cutoff_at_splitpoint(threadID)))
{
bestValue = value;
if (SpNode)
sp->bestValue = value;
- if (value > alpha)
+ if (!Root && value > alpha)
{
if (PvNode && value < beta) // We want always alpha < beta
{
ss->bestMove = move;
if (SpNode)
- sp->parentSstack->bestMove = move;
+ sp->ss->bestMove = move;
}
}
if (Root)
{
- // To avoid to exit with bestValue == -VALUE_INFINITE
- if (value > bestValue)
- bestValue = value;
-
// Finished searching the move. If StopRequest is true, the search
// 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
// Remember searched nodes counts for this move
mp.rm->nodes += pos.nodes_searched() - nodes;
- // Step 17. Check for new best move
- if (!isPvMove && value <= alpha)
- mp.rm->pv_score = -VALUE_INFINITE;
- else
+ // PV move or new best move ?
+ if (isPvMove || value > alpha)
{
- // PV move or new best move!
-
// Update PV
ss->bestMove = move;
mp.rm->pv_score = value;
alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount?
else if (value > alpha)
alpha = value;
+ }
+ else
+ mp.rm->pv_score = -VALUE_INFINITE;
- } // PV move or new best move
- }
+ } // Root
// Step 18. Check for split
if ( !Root
bestValue = futilityValue;
continue;
}
+
+ // Prune moves with negative or equal SEE
+ if ( futilityBase < beta
+ && depth < DEPTH_ZERO
+ && pos.see(move) <= 0)
+ continue;
}
// Detect non-capture evasions that are candidate to be pruned
}
- // qsearch_scoring() scores each move of a list using a qsearch() evaluation,
- // it is used in RootMoveList to get an initial scoring.
- void qsearch_scoring(Position& pos, MoveStack* mlist, MoveStack* last) {
-
- SearchStack ss[PLY_MAX_PLUS_2];
- StateInfo st;
-
- memset(ss, 0, 4 * sizeof(SearchStack));
- ss[0].eval = ss[0].evalMargin = VALUE_NONE;
-
- for (MoveStack* cur = mlist; cur != last; cur++)
- {
- ss[0].currentMove = cur->move;
- pos.do_move(cur->move, st);
- cur->score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
- pos.undo_move(cur->move);
- }
- }
-
-
// check_is_dangerous() tests if a checking move can be pruned in qsearch().
// bestValue is updated only when returning false because in that case move
// will be pruned.
H.update_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
}
+ // current_search_time() returns the number of milliseconds which have passed
+ // since the beginning of the current search.
+
+ int current_search_time() {
+
+ return get_system_time() - SearchStartTime;
+ }
+
// value_to_uci() converts a value to a string suitable for use with the UCI
// protocol specifications:
}
- // current_search_time() returns the number of milliseconds which have passed
- // since the beginning of the current search.
-
- int current_search_time() {
-
- return get_system_time() - SearchStartTime;
- }
+ // speed_to_uci() returns a string with time stats of current search suitable
+ // to be sent to UCI gui.
+ std::string speed_to_uci(int64_t nodes) {
- // nps() computes the current nodes/second count
+ std::stringstream s;
+ int t = current_search_time();
- int nps(const Position& pos) {
+ s << " nodes " << nodes
+ << " nps " << (t > 0 ? int(nodes * 1000 / t) : 0)
+ << " time " << t;
- int t = current_search_time();
- return (t > 0 ? int((pos.nodes_searched() * 1000) / t) : 0);
+ return s.str();
}
threads[threadID].state = THREAD_SEARCHING;
- // Here we call search() with SplitPoint template parameter set to true
+ // Copy SplitPoint position and search stack and call search()
+ // with SplitPoint template parameter set to true.
+ SearchStack ss[PLY_MAX_PLUS_2];
SplitPoint* tsp = threads[threadID].splitPoint;
Position pos(*tsp->pos, threadID);
- SearchStack* ss = tsp->sstack[threadID] + 1;
- ss->sp = tsp;
+
+ memcpy(ss, tsp->ss - 1, 4 * sizeof(SearchStack));
+ (ss+1)->sp = tsp;
if (tsp->pvNode)
- search<PV, true, false>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
+ search<PV, true, false>(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
else
- search<NonPV, true, false>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
+ search<NonPV, true, false>(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
assert(threads[threadID].state == THREAD_SEARCHING);
splitPoint.moveCount = moveCount;
splitPoint.pos = &pos;
splitPoint.nodes = 0;
- splitPoint.parentSstack = ss;
+ splitPoint.ss = ss;
for (i = 0; i < activeThreads; i++)
splitPoint.slaves[i] = 0;
lock_release(&mpLock);
// Tell the threads that they have work to do. This will make them leave
- // their idle loop. But before copy search stack tail for each thread.
+ // their idle loop.
for (i = 0; i < activeThreads; i++)
if (i == master || splitPoint.slaves[i])
{
- memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
-
assert(i == master || threads[i].state == THREAD_BOOKED);
threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
<< " multipv " << pvLine + 1
<< " score " << value_to_uci(pv_score)
<< (pv_score >= beta ? " lowerbound" : pv_score <= alpha ? " upperbound" : "")
- << " time " << current_search_time()
- << " nodes " << pos.nodes_searched()
- << " nps " << nps(pos)
+ << speed_to_uci(pos.nodes_searched())
<< " pv " << l.str();
return s.str();
clear();
bestMoveChanges = 0;
- // Generate all legal moves and score them
+ // Generate all legal moves and add them to RootMoveList
MoveStack* last = generate<MV_LEGAL>(pos, mlist);
- qsearch_scoring(pos, mlist, last);
-
- // Add each move to the RootMoveList's vector
for (MoveStack* cur = mlist; cur != last; cur++)
{
// If we have a searchMoves[] list then verify cur->move
RootMove rm;
rm.pv[0] = cur->move;
rm.pv[1] = MOVE_NONE;
- rm.pv_score = Value(cur->score);
+ rm.pv_score = -VALUE_INFINITE;
push_back(rm);
}
- sort();
}
} // namespace