void extract_pv_from_tt(Position& pos);
void insert_pv_in_tt(Position& pos);
- std::string pv_info_to_uci(Position& pos, Value alpha, Value beta, int pvLine = 0);
+ std::string pv_info_to_uci(Position& pos, Depth depth, Value alpha, Value beta, int pvLine = 0);
int64_t nodes;
Value pv_score;
typedef std::vector<RootMove> Base;
- RootMoveList(Position& pos, Move searchMoves[]);
- void set_non_pv_scores(const Position& pos, Move ttm, SearchStack* ss);
-
+ void init(Position& pos, Move searchMoves[]);
void sort() { insertion_sort<RootMove, Base::iterator>(begin(), end()); }
void sort_multipv(int n) { insertion_sort<RootMove, Base::iterator>(begin(), begin() + n); }
+
+ int bestMoveChanges;
};
Book OpeningBook;
// Pointer to root move list
- RootMoveList* Rml;
-
- // Iteration counter
- int Iteration;
-
- // Scores and number of times the best move changed for each iteration
- Value ValueByIteration[PLY_MAX_PLUS_2];
- int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
-
- // Search window management
- int AspirationDelta;
+ RootMoveList Rml;
// MultiPV mode
int MultiPV;
DWORD WINAPI init_thread(LPVOID threadID);
#endif
-}
+
+ // A dispatcher to choose among different move sources according to the type of node
+ template<bool SpNode, bool Root> struct MovePickerExt;
+
+ // In Root nodes use RootMoveList Rml as source. Score and sort the moves before to search them.
+ template<> struct MovePickerExt<false, true> : private MovePicker {
+
+ MovePickerExt(const Position& p, Move, Depth, const History& h, SearchStack* ss, Value beta)
+ : MovePicker(p, Rml[0].pv[0], ONE_PLY, h, ss, beta), firstCall(true) { // FIXME use depth
+
+ Move move;
+ 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.
+ // 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)
+ for (rm = Rml.begin(); rm != Rml.end(); ++rm)
+ if (rm->pv[0] == move)
+ {
+ rm->non_pv_score = score--;
+ break;
+ }
+
+ Rml.sort();
+ rm = Rml.begin();
+ }
+
+ Move get_next_move() {
+
+ if (!firstCall)
+ ++rm;
+ else
+ firstCall = false;
+
+ return rm != Rml.end() ? rm->pv[0] : MOVE_NONE;
+ }
+ int number_of_evasions() const { return (int)Rml.size(); }
+
+ RootMoveList::iterator rm;
+ bool firstCall;
+ };
+
+ // In SpNodes use split point's shared MovePicker as move source
+ template<> struct MovePickerExt<true, false> {
+
+ MovePickerExt(const Position&, Move, Depth, const History&, SearchStack* ss, Value)
+ : mp(ss->sp->mp) {}
+
+ Move get_next_move() { return mp->get_next_move(); }
+ int number_of_evasions() const { return mp->number_of_evasions(); }
+
+ RootMoveList::iterator rm; // Dummy, never used
+ MovePicker* mp;
+ };
+
+ // Normal case, create and use a MovePicker object as source
+ template<> struct MovePickerExt<false, false> : public MovePicker {
+
+ MovePickerExt(const Position& p, Move ttm, Depth d, const History& h,
+ SearchStack* ss, Value beta) : MovePicker(p, ttm, d, h, ss, beta) {}
+
+ RootMoveList::iterator rm; // Dummy, never used
+ };
+
+} // namespace
////
Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove) {
SearchStack ss[PLY_MAX_PLUS_2];
+ Value bestValues[PLY_MAX_PLUS_2];
+ int bestMoveChanges[PLY_MAX_PLUS_2];
+ int iteration, researchCountFL, researchCountFH, aspirationDelta;
+ Value value, alpha, beta;
Depth depth;
- Move EasyMove = MOVE_NONE;
- Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
- int researchCountFL, researchCountFH;
+ Move EasyMove;
// Moves to search are verified, scored and sorted
- RootMoveList rml(pos, searchMoves);
- Rml = &rml;
+ Rml.init(pos, searchMoves);
+
+ // Initialize FIXME move before Rml.init()
+ TT.new_search();
+ H.clear();
+ init_ss_array(ss, PLY_MAX_PLUS_2);
+ alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
+ EasyMove = MOVE_NONE;
+ aspirationDelta = 0;
+ iteration = 1;
// Handle special case of searching on a mate/stale position
- if (rml.size() == 0)
+ if (Rml.size() == 0)
{
- Value s = (pos.is_check() ? -VALUE_MATE : VALUE_DRAW);
-
- cout << "info depth " << 1
- << " score " << value_to_uci(s) << endl;
+ cout << "info depth " << iteration << " score "
+ << value_to_uci(pos.is_check() ? -VALUE_MATE : VALUE_DRAW)
+ << endl;
return MOVE_NONE;
}
- // Initialize
- TT.new_search();
- H.clear();
- init_ss_array(ss, PLY_MAX_PLUS_2);
- ValueByIteration[1] = rml[0].pv_score;
- Iteration = 1;
-
- // Send initial RootMoveList scoring (iteration 1)
+ // Send initial scoring (iteration 1)
cout << set960(pos.is_chess960()) // Is enough to set once at the beginning
- << "info depth " << Iteration
- << "\n" << rml[0].pv_info_to_uci(pos, alpha, beta) << endl;
+ << "info depth " << iteration
+ << "\n" << Rml[0].pv_info_to_uci(pos, ONE_PLY, alpha, beta) << endl;
// 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];
+ 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)
+ while (++iteration <= PLY_MAX && (!MaxDepth || iteration <= MaxDepth) && !StopRequest)
{
- // Initialize iteration
- Iteration++;
- BestMoveChangesByIteration[Iteration] = 0;
+ cout << "info depth " << iteration << endl;
- cout << "info depth " << Iteration << endl;
+ Rml.bestMoveChanges = researchCountFL = researchCountFH = 0;
+ depth = (iteration - 2) * ONE_PLY + InitialDepth;
// Calculate dynamic aspiration window based on previous iterations
- if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
+ if (MultiPV == 1 && iteration >= 6 && abs(bestValues[iteration - 1]) < VALUE_KNOWN_WIN)
{
- int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
- int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
+ int prevDelta1 = bestValues[iteration - 1] - bestValues[iteration - 2];
+ int prevDelta2 = bestValues[iteration - 2] - bestValues[iteration - 3];
- AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
- AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
+ aspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
+ aspirationDelta = (aspirationDelta + 7) / 8 * 8; // Round to match grainSize
- alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
- beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
+ alpha = Max(bestValues[iteration - 1] - aspirationDelta, -VALUE_INFINITE);
+ beta = Min(bestValues[iteration - 1] + aspirationDelta, VALUE_INFINITE);
}
- depth = (Iteration - 2) * ONE_PLY + InitialDepth;
-
- researchCountFL = researchCountFH = 0;
-
// We start with small aspiration window and in case of fail high/low, we
// research with bigger window until we are not failing high/low anymore.
while (true)
{
- // Sort the moves before to (re)search
- rml.set_non_pv_scores(pos, rml[0].pv[0], ss);
- rml.sort();
-
- // Search to the current depth, rml is updated and sorted
+ // Search to the current depth
value = search<PV, false, true>(pos, ss, alpha, beta, depth, 0);
- // Sort the moves before to return
- rml.sort();
-
- // Write PV lines to transposition table, in case the relevant entries
- // have been overwritten during the search.
- for (int i = 0; i < Min(MultiPV, (int)rml.size()); i++)
- rml[i].insert_pv_in_tt(pos);
+ // Sort root moves and write PV lines to transposition table, in case
+ // the relevant entries have been overwritten during the search.
+ Rml.sort();
+ for (int i = 0; i < Min(MultiPV, (int)Rml.size()); i++)
+ Rml[i].insert_pv_in_tt(pos);
+ // Value cannot be trusted. Break out immediately!
if (StopRequest)
- break;
+ break; // FIXME move to 'while' condition
assert(value >= alpha);
+ bestMoveChanges[iteration] = Rml.bestMoveChanges; // FIXME move outside fail high/low loop
+
+ // In case of failing high/low increase aspiration window and research,
+ // otherwise exit the fail high/low loop.
if (value >= beta)
{
- // Prepare for a research after a fail high, each time with a wider window
- beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
+ beta = Min(beta + aspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
researchCountFH++;
}
else if (value <= alpha)
AspirationFailLow = true;
StopOnPonderhit = false;
- // Prepare for a research after a fail low, each time with a wider window
- alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
+ alpha = Max(alpha - aspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
researchCountFL++;
}
else
break;
}
- if (StopRequest)
- break; // Value cannot be trusted. Break out immediately!
-
//Save info about search result
- ValueByIteration[Iteration] = value;
+ bestValues[iteration] = value;
// Drop the easy move if differs from the new best move
- if (rml[0].pv[0] != EasyMove)
+ if (Rml[0].pv[0] != EasyMove)
EasyMove = MOVE_NONE;
- if (UseTimeManagement)
+ if (UseTimeManagement && !StopRequest)
{
// Time to stop?
- bool stopSearch = false;
+ bool noMoreTime = false;
// Stop search early if there is only a single legal move,
// we search up to Iteration 6 anyway to get a proper score.
- if (Iteration >= 6 && rml.size() == 1)
- stopSearch = true;
+ if (iteration >= 6 && Rml.size() == 1)
+ noMoreTime = true;
// Stop search early when the last two iterations returned a mate score
- if ( Iteration >= 6
- && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
- && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
- stopSearch = true;
+ if ( iteration >= 6
+ && abs(bestValues[iteration]) >= abs(VALUE_MATE) - 100
+ && abs(bestValues[iteration-1]) >= abs(VALUE_MATE) - 100)
+ noMoreTime = true;
// Stop search early if one move seems to be much better than the others
- if ( Iteration >= 8
- && EasyMove == rml[0].pv[0]
- && ( ( rml[0].nodes > (pos.nodes_searched() * 85) / 100
+ if ( iteration >= 8
+ && EasyMove == Rml[0].pv[0]
+ && ( ( Rml[0].nodes > (pos.nodes_searched() * 85) / 100
&& current_search_time() > TimeMgr.available_time() / 16)
- ||( rml[0].nodes > (pos.nodes_searched() * 98) / 100
+ ||( Rml[0].nodes > (pos.nodes_searched() * 98) / 100
&& current_search_time() > TimeMgr.available_time() / 32)))
- stopSearch = true;
+ noMoreTime = true;
// Add some extra time if the best move has changed during the last two iterations
- if (Iteration > 5 && Iteration <= 50)
- TimeMgr.pv_instability(BestMoveChangesByIteration[Iteration],
- BestMoveChangesByIteration[Iteration-1]);
+ if (iteration > 5 && iteration <= 50)
+ TimeMgr.pv_instability(bestMoveChanges[iteration], bestMoveChanges[iteration-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
// move at the next iteration anyway.
if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
- stopSearch = true;
+ noMoreTime = true;
- if (stopSearch)
+ if (noMoreTime)
{
if (Pondering)
StopOnPonderhit = true;
break;
}
}
-
- if (MaxDepth && Iteration >= MaxDepth)
- break;
}
- *ponderMove = rml[0].pv[1];
- return rml[0].pv[0];
+ *ponderMove = Rml[0].pv[1];
+ return Rml[0].pv[0];
}
Move movesSearched[MOVES_MAX];
int64_t nodes;
- RootMoveList::iterator rm;
StateInfo st;
const TTEntry *tte;
Key posKey;
mateThreat = sp->mateThreat;
goto split_point_start;
}
- else {} // Hack to fix icc's "statement is unreachable" warning
+ else if (Root)
+ bestValue = alpha;
// Step 1. Initialize node and poll. Polling can abort search
ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
(ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
- if (!Root)
+ if (!Root) // FIXME remove
{
if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
{
split_point_start: // At split points actual search starts from here
// Initialize a MovePicker object for the current position
- // FIXME currently MovePicker() c'tor is needless called also in SplitPoint
- MovePicker mpBase(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
- MovePicker& mp = SpNode ? *sp->mp : mpBase;
+ MovePickerExt<SpNode, Root> mp(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
CheckInfo ci(pos);
ss->bestMove = MOVE_NONE;
singleEvasion = !SpNode && isCheck && mp.number_of_evasions() == 1;
&& !excludedMove // Do not allow recursive singular extension search
&& (tte->type() & VALUE_TYPE_LOWER)
&& tte->depth() >= depth - 3 * ONE_PLY;
- if (Root)
- {
- rm = Rml->begin();
- bestValue = alpha;
- }
-
if (SpNode)
{
lock_grab(&(sp->lock));
// Step 10. Loop through moves
// Loop through all legal moves until no moves remain or a beta cutoff occurs
while ( bestValue < beta
- && (!Root || rm != Rml->end())
- && ( Root || (move = mp.get_next_move()) != MOVE_NONE)
+ && (move = mp.get_next_move()) != MOVE_NONE
&& !ThreadsMgr.cutoff_at_splitpoint(threadID))
{
- if (Root)
+ assert(move_is_ok(move));
+
+ if (SpNode)
{
- move = rm->pv[0];
+ moveCount = ++sp->moveCount;
+ lock_release(&(sp->lock));
+ }
+ else if (move == excludedMove)
+ continue;
+ else
+ movesSearched[moveCount++] = move;
+ if (Root)
+ {
// This is used by time management
- FirstRootMove = (rm == Rml->begin());
+ FirstRootMove = (moveCount == 1);
// Save the current node count before the move is searched
nodes = pos.nodes_searched();
<< " currmovenumber " << moveCount << endl;
}
- assert(move_is_ok(move));
-
- if (SpNode)
- {
- moveCount = ++sp->moveCount;
- lock_release(&(sp->lock));
- }
- else if (move == excludedMove)
- continue;
- else
- movesSearched[moveCount++] = move;
-
isPvMove = (PvNode && moveCount <= (Root ? MultiPV : 1));
moveIsCheck = pos.move_is_check(move, ci);
captureOrPromotion = pos.move_is_capture_or_promotion(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
break;
// Remember searched nodes counts for this move
- rm->nodes += pos.nodes_searched() - nodes;
+ mp.rm->nodes += pos.nodes_searched() - nodes;
// Step 17. Check for new best move
if (!isPvMove && value <= alpha)
- rm->pv_score = -VALUE_INFINITE;
+ mp.rm->pv_score = -VALUE_INFINITE;
else
{
// PV move or new best move!
// Update PV
ss->bestMove = move;
- rm->pv_score = value;
- rm->extract_pv_from_tt(pos);
+ 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
// the best move changes frequently, we allocate some more time.
if (!isPvMove && MultiPV == 1)
- BestMoveChangesByIteration[Iteration]++;
+ Rml.bestMoveChanges++;
// Inform GUI that PV has changed, in case of multi-pv UCI protocol
// requires we send all the PV lines properly sorted.
- Rml->sort_multipv(moveCount);
+ Rml.sort_multipv(moveCount);
- for (int j = 0; j < Min(MultiPV, (int)Rml->size()); j++)
- cout << (*Rml)[j].pv_info_to_uci(pos, alpha, beta, j) << endl;
+ for (int j = 0; j < Min(MultiPV, (int)Rml.size()); j++)
+ cout << Rml[j].pv_info_to_uci(pos, depth, alpha, beta, j) << endl;
- // Update alpha. In multi-pv we don't use aspiration window
- if (MultiPV == 1)
- {
- // Raise alpha to setup proper non-pv search upper bound
- if (value > alpha)
- alpha = bestValue = value;
- }
- else // Set alpha equal to minimum score among the PV lines
- alpha = bestValue = (*Rml)[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount?
+ // Update alpha. In multi-pv we don't use aspiration window, so
+ // set alpha equal to minimum score among the PV lines.
+ if (MultiPV > 1)
+ alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount?
+ else if (value > alpha)
+ alpha = value;
} // PV move or new best move
-
- ++rm;
}
// Step 18. Check for split
&& bestValue < beta
&& ThreadsMgr.available_thread_exists(threadID)
&& !StopRequest
- && !ThreadsMgr.cutoff_at_splitpoint(threadID)
- && Iteration <= 99)
+ && !ThreadsMgr.cutoff_at_splitpoint(threadID))
ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
- threatMove, mateThreat, moveCount, &mp, PvNode);
+ threatMove, mateThreat, moveCount, (MovePicker*)&mp, PvNode);
}
// Step 19. Check for mate and stalemate
// 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.
- std::string RootMove::pv_info_to_uci(Position& pos, Value alpha, Value beta, int pvLine) {
+ std::string RootMove::pv_info_to_uci(Position& pos, Depth depth, Value alpha, Value beta, int pvLine) {
std::stringstream s, l;
Move* m = pv;
while (*m != MOVE_NONE)
l << *m++ << " ";
- s << "info depth " << Iteration // FIXME
+ s << "info depth " << depth / ONE_PLY
<< " seldepth " << int(m - pv)
<< " multipv " << pvLine + 1
<< " score " << value_to_uci(pv_score)
ValueType t = pv_score >= beta ? VALUE_TYPE_LOWER :
pv_score <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
- LogFile << pretty_pv(pos, current_search_time(), Iteration, pv_score, t, pv) << endl;
+ LogFile << pretty_pv(pos, current_search_time(), depth / ONE_PLY, pv_score, t, pv) << endl;
}
return s.str();
}
- RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) {
+ void RootMoveList::init(Position& pos, Move searchMoves[]) {
SearchStack ss[PLY_MAX_PLUS_2];
MoveStack mlist[MOVES_MAX];
// Initialize search stack
init_ss_array(ss, PLY_MAX_PLUS_2);
ss[0].eval = ss[0].evalMargin = VALUE_NONE;
+ bestMoveChanges = 0;
+ clear();
// Generate all legal moves
MoveStack* last = generate<MV_LEGAL>(pos, mlist);
sort();
}
- // 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.
- // This is the second order score that is used to compare the moves when
- // the first order pv scores of both moves are equal.
-
- void RootMoveList::set_non_pv_scores(const Position& pos, Move ttm, SearchStack* ss)
- {
- Move move;
- Value score = VALUE_ZERO;
- MovePicker mp(pos, ttm, ONE_PLY, H, ss);
-
- while ((move = mp.get_next_move()) != MOVE_NONE)
- for (Base::iterator it = begin(); it != end(); ++it)
- if (it->pv[0] == move)
- {
- it->non_pv_score = score--;
- break;
- }
- }
-
} // namespace