void put_threads_to_sleep();
void idle_loop(int threadID, SplitPoint* waitSp);
bool split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
void put_threads_to_sleep();
void idle_loop(int threadID, SplitPoint* waitSp);
bool split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
- Depth depth, int* moves, MovePicker* mp, int master, bool pvNode);
+ Depth depth, bool mateThreat, int* moves, MovePicker* mp, int master, bool pvNode);
- int RootMoveNumber, SearchStartTime, MaxNodes, MaxDepth;
- int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
+ int SearchStartTime, MaxNodes, MaxDepth, MaxSearchTime;
+ int AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
- bool AbortSearch, Quit, AspirationFailLow;
+ bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
- Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta);
+ Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE);
Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE);
Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
// Initialize global search variables
StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
// Initialize global search variables
StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
- // Search to the current depth
- value = root_search(p, ss, rml, alpha, beta);
+ // Search to the current depth, rml is updated and sorted, alpha and beta could change
+ value = root_search(p, ss, rml, &alpha, &beta);
// Write PV to transposition table, in case the relevant entries have
// been overwritten during the search.
// Write PV to transposition table, in case the relevant entries have
// been overwritten during the search.
// If we are pondering or in infinite search, we shouldn't print the
// best move before we are told to do so.
if (!AbortSearch && (PonderSearch || InfiniteSearch))
// If we are pondering or in infinite search, we shouldn't print the
// best move before we are told to do so.
if (!AbortSearch && (PonderSearch || InfiniteSearch))
// scheme, prints some information to the standard output and handles
// the fail low/high loops.
// scheme, prints some information to the standard output and handles
// the fail low/high loops.
- Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta) {
+ Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
- // Evaluate the position statically
- ss[0].eval = !isCheck ? evaluate(pos, ei, 0) : VALUE_NONE;
+ // Step 1. Initialize node and poll (omitted at root, but I can see no good reason for this, FIXME)
+ // Step 2. Check for aborted search (omitted at root, because we do not initialize root node)
+ // Step 3. Mate distance pruning (omitted at root)
+ // Step 4. Transposition table lookup (omitted at root)
+
+ // Step 5. Evaluate the position statically
+ // At root we do this only to get reference value for child nodes
+ if (!isCheck)
+ ss[0].eval = evaluate(pos, ei, 0);
+ else
+ ss[0].eval = VALUE_NONE; // HACK because we do not initialize root node
- while (1) // Fail low loop
+ // Step 6. Razoring (omitted at root)
+ // Step 7. Static null move pruning (omitted at root)
+ // Step 8. Null move search with verification search (omitted at root)
+ // Step 9. Internal iterative deepening (omitted at root)
+
+ // Step extra. Fail low loop
+ // We start with small aspiration window and in case of fail low, we research
+ // with bigger window until we are not failing low anymore.
+ while (1)
- if (alpha >= beta)
- {
- // We failed high, invalidate and skip next moves, leave node-counters
- // and beta-counters as they are and quickly return, we will try to do
- // a research at the next iteration with a bigger aspiration window.
- rml.set_move_score(i, -VALUE_INFINITE);
- continue;
- }
-
- // This is used by time management and starts from 1
- RootMoveNumber = i + 1;
+ // This is used by time management
+ FirstRootMove = (i == 0);
depth = (Iteration - 2) * OnePly + InitialDepth;
ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
newDepth = depth + ext;
depth = (Iteration - 2) * OnePly + InitialDepth;
ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
newDepth = depth + ext;
- // Reset value before the search
+ // Step 12. Futility pruning (omitted at root)
+
+ // Step extra. Fail high loop
+ // If move fails high, we research with bigger window until we are not failing
+ // high anymore.
pos.do_move(move, st, ci, moveIsCheck);
pos.do_move(move, st, ci, moveIsCheck);
- // Try to reduce non-pv search depth by one ply if move seems not problematic,
- // if the move fails high will be re-searched at full depth.
+ // Step 14. Reduced search
+ // if the move fails high will be re-searched at full depth
print_pv_info(pos, ss, alpha, beta, value);
// Prepare for a research after a fail high, each time with a wider window
print_pv_info(pos, ss, alpha, beta, value);
// Prepare for a research after a fail high, each time with a wider window
int64_t our, their;
TM.get_beta_counters(pos.side_to_move(), our, their);
rml.set_beta_counters(i, our, their);
rml.set_move_nodes(i, TM.nodes_searched() - nodes);
assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
int64_t our, their;
TM.get_beta_counters(pos.side_to_move(), our, their);
rml.set_beta_counters(i, our, their);
rml.set_move_nodes(i, TM.nodes_searched() - nodes);
assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
if (value <= alpha && i >= MultiPV)
rml.set_move_score(i, -VALUE_INFINITE);
else
if (value <= alpha && i >= MultiPV)
rml.set_move_score(i, -VALUE_INFINITE);
else
// Print information to the standard output
print_pv_info(pos, ss, alpha, beta, value);
// Print information to the standard output
print_pv_info(pos, ss, alpha, beta, value);
&& !AbortSearch
&& !TM.thread_should_stop(threadID)
&& TM.split(pos, ss, ply, &alpha, beta, &bestValue,
&& !AbortSearch
&& !TM.thread_should_stop(threadID)
&& TM.split(pos, ss, ply, &alpha, beta, &bestValue,
- depth, &moveCount, &mp, threadID, true))
+ depth, mateThreat, &moveCount, &mp, threadID, true))
Value rbeta = beta - razor_margin(depth);
Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID);
if (v < rbeta)
Value rbeta = beta - razor_margin(depth);
Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID);
if (v < rbeta)
&& !AbortSearch
&& !TM.thread_should_stop(threadID)
&& TM.split(pos, ss, ply, NULL, beta, &bestValue,
&& !AbortSearch
&& !TM.thread_should_stop(threadID)
&& TM.split(pos, ss, ply, NULL, beta, &bestValue,
- depth, &moveCount, &mp, threadID, false))
+ depth, mateThreat, &moveCount, &mp, threadID, false))
// splitting, we don't have to repeat all this work in sp_search(). We
// also don't need to store anything to the hash table here: This is taken
// care of after we return from the split point.
// splitting, we don't have to repeat all this work in sp_search(). We
// also don't need to store anything to the hash table here: This is taken
// care of after we return from the split point.
- ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous);
+ ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous);
// don't have to repeat all this work in sp_search_pv(). We also don't
// need to store anything to the hash table here: This is taken care of
// after we return from the split point.
// don't have to repeat all this work in sp_search_pv(). We also don't
// need to store anything to the hash table here: This is taken care of
// after we return from the split point.
- ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
+ ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous);
bool ThreadsManager::split(const Position& p, SearchStack* sstck, int ply,
Value* alpha, const Value beta, Value* bestValue,
bool ThreadsManager::split(const Position& p, SearchStack* sstck, int ply,
Value* alpha, const Value beta, Value* bestValue,
- Depth depth, int* moves, MovePicker* mp, int master, bool pvNode) {
+ Depth depth, bool mateThreat, int* moves, MovePicker* mp, int master, bool pvNode) {