void extract_pv_from_tt(Position& pos);
void insert_pv_in_tt(Position& pos);
- std::string pv_info_to_uci(Position& pos, Depth depth, Value alpha, Value beta, int pvLine = 0);
+ std::string pv_info_to_uci(Position& pos, int depth, Value alpha, Value beta, int pvLine);
int64_t nodes;
Value pv_score;
// 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 then the
- // remaining ones we will extend it.
- const Value SingularExtensionMargin = Value(0x20);
-
// Step 12. Futility pruning
// Futility margin for quiescence search
// MultiPV mode
int MultiPV;
- // Time managment variables
+ // Time management variables
int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
bool UseTimeManagement, InfiniteSearch, Pondering, StopOnPonderhit;
bool FirstRootMove, StopRequest, QuitRequest, AspirationFailLow;
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();
Value score = VALUE_ZERO;
// Score root moves using the standard way used in main search, the moves
- // are scored according to the order in which are returned by MovePicker.
+ // are scored according to the order in which they are returned by MovePicker.
// This is the second order score that is used to compare the moves when
// the first order pv scores of both moves are equal.
while ((move = MovePicker::get_next_move()) != MOVE_NONE)
std::string name = Options["Search Log Filename"].value<std::string>();
LogFile.open(name.c_str(), std::ios::out | std::ios::app);
- LogFile << "Searching: " << pos.to_fen()
- << "\ninfinite: " << infinite
- << " ponder: " << ponder
- << " time: " << myTime
- << " increment: " << myIncrement
- << " moves to go: " << movesToGo << endl;
+ LogFile << "\nSearching: " << pos.to_fen()
+ << "\ninfinite: " << infinite
+ << " ponder: " << ponder
+ << " time: " << myTime
+ << " increment: " << myIncrement
+ << " moves to go: " << movesToGo
+ << endl;
}
// We're ready to start thinking. Call the iterative deepening loop function
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)
{
- LogFile << "\nNodes: " << pos.nodes_searched()
- << "\nNodes/second: " << nps(pos)
- << "\nBest move: " << move_to_san(pos, bestMove);
+ int t = current_search_time();
+
+ LogFile << "Nodes: " << pos.nodes_searched()
+ << "\nNodes/second: " << (t > 0 ? int(pos.nodes_searched() * 1000 / t) : 0)
+ << "\nBest move: " << move_to_san(pos, bestMove);
StateInfo st;
pos.do_move(bestMove, st);
- LogFile << "\nPonder move: "
- << move_to_san(pos, ponderMove) // Works also with MOVE_NONE
- << endl;
-
- // Return from think() with unchanged position
- pos.undo_move(bestMove);
-
+ LogFile << "\nPonder move: " << move_to_san(pos, ponderMove) << endl;
+ pos.undo_move(bestMove); // Return from think() with unchanged position
LogFile.close();
}
SearchStack ss[PLY_MAX_PLUS_2];
Value bestValues[PLY_MAX_PLUS_2];
int bestMoveChanges[PLY_MAX_PLUS_2];
- int iteration, researchCountFL, researchCountFH, aspirationDelta;
+ int depth, researchCountFL, researchCountFH, aspirationDelta;
Value value, alpha, beta;
- Depth depth;
Move bestMove, easyMove;
- // Moves to search are verified, scored and sorted
+ // Moves to search are verified and copied
Rml.init(pos, searchMoves);
// Initialize FIXME move before Rml.init()
TT.new_search();
H.clear();
- memset(ss, 0, PLY_MAX_PLUS_2 * sizeof(SearchStack));
+ memset(ss, 0, 4 * sizeof(SearchStack));
*ponderMove = bestMove = easyMove = MOVE_NONE;
- iteration = aspirationDelta = 0;
+ depth = aspirationDelta = 0;
ss->currentMove = MOVE_NULL; // Hack to skip update_gains()
alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
- // Handle special case of searching on a mate/stale position
+ // Handle special case of searching on a mate/stalemate position
if (Rml.size() == 0)
{
cout << "info depth 0 score "
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 (++iteration <= PLY_MAX && !StopRequest)
+ while (++depth <= PLY_MAX && (!MaxDepth || depth <= MaxDepth) && !StopRequest)
{
Rml.bestMoveChanges = researchCountFL = researchCountFH = 0;
- depth = iteration * ONE_PLY;
-
- if (MaxDepth && depth > MaxDepth * ONE_PLY)
- break;
-
- cout << "info depth " << depth / ONE_PLY << endl;
+ cout << "info depth " << depth << endl;
// Calculate dynamic aspiration window based on previous iterations
- if (MultiPV == 1 && iteration >= 5 && abs(bestValues[iteration - 1]) < VALUE_KNOWN_WIN)
+ if (MultiPV == 1 && depth >= 5 && abs(bestValues[depth - 1]) < VALUE_KNOWN_WIN)
{
- int prevDelta1 = bestValues[iteration - 1] - bestValues[iteration - 2];
- int prevDelta2 = bestValues[iteration - 2] - bestValues[iteration - 3];
+ int prevDelta1 = bestValues[depth - 1] - bestValues[depth - 2];
+ int prevDelta2 = bestValues[depth - 2] - bestValues[depth - 3];
aspirationDelta = Min(Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16), 24);
aspirationDelta = (aspirationDelta + 7) / 8 * 8; // Round to match grainSize
- alpha = Max(bestValues[iteration - 1] - aspirationDelta, -VALUE_INFINITE);
- beta = Min(bestValues[iteration - 1] + aspirationDelta, VALUE_INFINITE);
+ alpha = Max(bestValues[depth - 1] - aspirationDelta, -VALUE_INFINITE);
+ beta = Min(bestValues[depth - 1] + aspirationDelta, VALUE_INFINITE);
}
// Start with a small aspiration window and, in case of fail high/low,
while (true)
{
// Search starting from ss+1 to allow calling update_gains()
- value = search<PV, false, true>(pos, ss+1, alpha, beta, depth, 0);
+ value = search<PV, false, true>(pos, ss+1, alpha, beta, depth * ONE_PLY, 0);
// Send PV line to GUI and write to transposition table in case the
// relevant entries have been overwritten during the search.
// Collect info about search result
bestMove = Rml[0].pv[0];
- bestValues[iteration] = value;
- bestMoveChanges[iteration] = Rml.bestMoveChanges;
+ bestValues[depth] = value;
+ bestMoveChanges[depth] = Rml.bestMoveChanges;
+
+ 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)
bool noMoreTime = false;
// Stop search early when the last two iterations returned a mate score
- if ( iteration >= 5
- && abs(bestValues[iteration]) >= abs(VALUE_MATE) - 100
- && abs(bestValues[iteration - 1]) >= abs(VALUE_MATE) - 100)
+ if ( depth >= 5
+ && abs(bestValues[depth]) >= abs(VALUE_MATE) - 100
+ && abs(bestValues[depth - 1]) >= abs(VALUE_MATE) - 100)
noMoreTime = true;
// Stop search early if one move seems to be much better than the
// others or if there is only a single legal move. In this latter
// case we search up to Iteration 8 anyway to get a proper score.
- if ( iteration >= 7
+ if ( depth >= 7
&& easyMove == bestMove
&& ( Rml.size() == 1
||( Rml[0].nodes > (pos.nodes_searched() * 85) / 100
noMoreTime = true;
// Add some extra time if the best move has changed during the last two iterations
- if (iteration > 4 && iteration < 50)
- TimeMgr.pv_instability(bestMoveChanges[iteration], bestMoveChanges[iteration-1]);
+ if (depth > 4 && depth < 50)
+ TimeMgr.pv_instability(bestMoveChanges[depth], bestMoveChanges[depth-1]);
// Stop search if most of MaxSearchTime is consumed at the end of the
// iteration. We probably don't have enough time to search the first
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)
// Step 4. Transposition table lookup
// We don't want the score of a partial search to overwrite a previous full search
- // TT value, so we use a different position key in case of an excluded move exists.
+ // TT value, so we use a different position key in case of an excluded move.
excludedMove = ss->excludedMove;
posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
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);
// Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s),
// and just one fails high on (alpha, beta), then that move is singular and should be extended.
// To verify this we do a reduced search on all the other moves but the ttMove, if result is
- // lower then ttValue minus a margin then we extend ttMove.
+ // lower than ttValue minus a margin then we extend ttMove.
if ( singularExtensionNode
&& move == tte->move()
&& ext < ONE_PLY)
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
&& ss->killers[0] != move
&& ss->killers[1] != move)
{
- ss->reduction = Root ? reduction<PvNode>(depth, moveCount - MultiPV + 1)
- : reduction<PvNode>(depth, moveCount);
+ ss->reduction = reduction<PvNode>(depth, moveCount);
if (ss->reduction)
{
alpha = SpNode ? sp->alpha : alpha;
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;
mp.rm->extract_pv_from_tt(pos);
// We record how often the best move has been changed in each
- // iteration. This information is used for time managment: When
+ // iteration. This information is used for time management: When
// the best move changes frequently, we allocate some more time.
if (!isPvMove && MultiPV == 1)
Rml.bestMoveChanges++;
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.
// connected_threat() tests whether it is safe to forward prune a move or if
- // is somehow coonected to the threat move returned by null search.
+ // is somehow connected to the threat move returned by null search.
bool connected_threat(const Position& pos, Move m, Move threat) {
return true;
// Case 2: If the threatened piece has value less than or equal to the
- // value of the threatening piece, don't prune move which defend it.
+ // value of the threatening piece, don't prune moves which defend it.
if ( pos.move_is_capture(threat)
&& ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
|| pos.type_of_piece_on(tfrom) == KING)
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:
if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to centipawns
else
- s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
+ s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2);
return s.str();
}
- // 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()
k = pos.get_key();
tte = TT.retrieve(k);
- // Don't overwrite exsisting correct entries
+ // Don't overwrite existing correct entries
if (!tte || tte->move() != pv[ply])
{
v = (pos.is_check() ? VALUE_NONE : evaluate(pos, m));
}
// pv_info_to_uci() returns a string with information on the current PV line
- // formatted according to UCI specification and eventually writes the info
- // to a log file. It is called at each iteration or after a new pv is found.
+ // formatted according to UCI specification. It is called at each iteration
+ // or after a new pv is found.
- std::string RootMove::pv_info_to_uci(Position& pos, Depth depth, Value alpha, Value beta, int pvLine) {
+ std::string RootMove::pv_info_to_uci(Position& pos, int depth, Value alpha, Value beta, int pvLine) {
std::stringstream s, l;
Move* m = pv;
while (*m != MOVE_NONE)
l << *m++ << " ";
- s << "info depth " << depth / ONE_PLY
+ s << "info depth " << depth
<< " seldepth " << int(m - pv)
<< " 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();
- if (UseLogFile && pvLine == 0)
- {
- ValueType t = pv_score >= beta ? VALUE_TYPE_LOWER :
- pv_score <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
-
- LogFile << pretty_pv(pos, current_search_time(), depth / ONE_PLY, pv_score, t, pv) << endl;
- }
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
projects / stockfish / blobdiff