////
#include <cassert>
+#include <cstring>
#include <fstream>
#include <iostream>
#include <sstream>
/// Types
- //The IterationInfoType is used to store search history
- //iteration by iteration.
+ // IterationInfoType stores search results for each iteration
//
- //Because we use relatively small (dynamic) aspiration window,
- //there happens many fail highs and fail lows in root. And
- //because we don't do researches in those cases, "value" stored
- //here is not necessarily exact. Instead in case of fail high/low
- //we guess what the right value might be and store our guess
- //as "speculated value" and then move on...
-
- class IterationInfoType {
- private:
- Value _value;
- Value _speculatedValue;
- bool _failHigh;
- bool _failLow;
- public:
- IterationInfoType() {
- clear();
- }
-
- inline void clear() {
- set(Value(0));
- }
-
- inline void set(Value v) {
- set(v, v, false, false);
- }
-
- inline void set(Value v, Value specV, bool fHigh, bool fLow) {
- _value = v;
- _speculatedValue = specV;
- _failHigh = fHigh;
- _failLow = fLow;
- }
-
- inline Value value() {
- return _value;
- }
+ // Because we use relatively small (dynamic) aspiration window,
+ // there happens many fail highs and fail lows in root. And
+ // because we don't do researches in those cases, "value" stored
+ // here is not necessarily exact. Instead in case of fail high/low
+ // we guess what the right value might be and store our guess
+ // as a "speculated value" and then move on. Speculated values are
+ // used just to calculate aspiration window width, so also if are
+ // not exact is not big a problem.
- inline Value speculated_value() {
- return _speculatedValue;
- }
+ struct IterationInfoType {
- inline bool fail_high() {
- return _failHigh;
- }
+ IterationInfoType(Value v = Value(0), Value sv = Value(0))
+ : value(v), speculatedValue(sv) {}
- inline bool fail_low() {
- return _failLow;
- }
+ Value value, speculatedValue;
};
};
- /// Constants and variables
+ /// Constants and variables initialized from UCI options
// Minimum number of full depth (i.e. non-reduced) moves at PV and non-PV
- // nodes:
- int LMRPVMoves = 15;
- int LMRNonPVMoves = 4;
+ // nodes
+ int LMRPVMoves, LMRNonPVMoves;
- // Depth limit for use of dynamic threat detection:
- Depth ThreatDepth = 5*OnePly;
+ // Depth limit for use of dynamic threat detection
+ Depth ThreatDepth;
- // Depth limit for selective search:
- Depth SelectiveDepth = 7*OnePly;
+ // Depth limit for selective search
+ Depth SelectiveDepth;
// Use internal iterative deepening?
const bool UseIIDAtPVNodes = true;
const bool PruneBlockingMoves = false;
// Use futility pruning?
- bool UseQSearchFutilityPruning = true;
- bool UseFutilityPruning = true;
+ bool UseQSearchFutilityPruning, UseFutilityPruning;
// Margins for futility pruning in the quiescence search, and at frontier
// and near frontier nodes
- Value FutilityMarginQS = Value(0x80);
- Value FutilityMargins[6] = { Value(0x100), Value(0x200), Value(0x250),
- Value(0x2A0), Value(0x340), Value(0x3A0) };
+ const Value FutilityMarginQS = Value(0x80);
+
+ //remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply
+ const Value FutilityMargins[12] = { Value(0x100), Value(0x120), Value(0x200), Value(0x220), Value(0x250), Value(0x270),
+ // 4 ply 4.5 ply 5 ply 5.5 ply 6 ply 6.5 ply
+ Value(0x2A0), Value(0x2C0), Value(0x340), Value(0x360), Value(0x3A0), Value(0x3C0)};
// Razoring
- const bool RazorAtDepthOne = false;
- Depth RazorDepth = 4*OnePly;
- Value RazorMargin = Value(0x300);
+ const Depth RazorDepth = 4*OnePly;
+
+ //remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply
+ const Value RazorMargins[6] = { Value(0x180), Value(0x300), Value(0x300), Value(0x3C0), Value(0x3C0), Value(0x3C0) };
+
+ //remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply
+ const Value RazorApprMargins[6] = { Value(0x100000), Value(0x300), Value(0x300), Value(0x300), Value(0x300), Value(0x300) };
// Last seconds noise filtering (LSN)
- bool UseLSNFiltering = false;
+ bool UseLSNFiltering;
bool looseOnTime = false;
- int LSNTime = 4 * 1000; // In milliseconds
- Value LSNValue = Value(0x200);
+ int LSNTime; // In milliseconds
+ Value LSNValue;
- // Extensions. Array index 0 is used at non-PV nodes, index 1 at PV nodes.
- Depth CheckExtension[2] = {OnePly, OnePly};
- Depth SingleReplyExtension[2] = {OnePly / 2, OnePly / 2};
- Depth PawnPushTo7thExtension[2] = {OnePly / 2, OnePly / 2};
- Depth PassedPawnExtension[2] = {Depth(0), Depth(0)};
- Depth PawnEndgameExtension[2] = {OnePly, OnePly};
- Depth MateThreatExtension[2] = {Depth(0), Depth(0)};
+ // Extensions. Array index 0 is used at non-PV nodes, index 1 at PV nodes.
+ Depth CheckExtension[2], SingleReplyExtension[2], PawnPushTo7thExtension[2];
+ Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
// Search depth at iteration 1
const Depth InitialDepth = OnePly /*+ OnePly/2*/;
int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
// MultiPV mode
- int MultiPV = 1;
+ int MultiPV;
// Time managment variables
int SearchStartTime;
int MaxNodes, MaxDepth;
- int MaxSearchTime, AbsoluteMaxSearchTime, EmergencyMaxSearchTime, ExtraSearchTime;
+ int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime;
Move EasyMove;
int RootMoveNumber;
bool InfiniteSearch;
int ExactMaxTime;
// Show current line?
- bool ShowCurrentLine = false;
+ bool ShowCurrentLine;
// Log file
- bool UseLogFile = false;
+ bool UseLogFile;
std::ofstream LogFile;
// MP related variables
- Depth MinimumSplitDepth = 4*OnePly;
- int MaxThreadsPerSplitPoint = 4;
+ Depth MinimumSplitDepth;
+ int MaxThreadsPerSplitPoint;
Thread Threads[THREAD_MAX];
Lock MPLock;
bool AllThreadsShouldExit = false;
/// Functions
Value id_loop(const Position &pos, Move searchMoves[]);
- Value root_search(Position &pos, SearchStack ss[], RootMoveList &rml,
- Value alpha, Value beta);
- 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);
- Value qsearch(Position &pos, SearchStack ss[], Value alpha, Value beta,
- Depth depth, int ply, int threadID);
+ Value root_search(Position &pos, SearchStack ss[], RootMoveList &rml, Value alpha, Value beta);
+ 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);
+ Value qsearch(Position &pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
void sp_search(SplitPoint *sp, int threadID);
void sp_search_pv(SplitPoint *sp, int threadID);
void init_node(SearchStack ss[], int ply, int threadID);
UseQSearchFutilityPruning = get_option_value_bool("Futility Pruning (Quiescence Search)");
UseFutilityPruning = get_option_value_bool("Futility Pruning (Main Search)");
- FutilityMarginQS = value_from_centipawns(get_option_value_int("Futility Margin (Quiescence Search)"));
- int fmScale = get_option_value_int("Futility Margin Scale Factor (Main Search)");
- for (int i = 0; i < 6; i++)
- FutilityMargins[i] = (FutilityMargins[i] * fmScale) / 100;
+ //FutilityMarginQS = value_from_centipawns(get_option_value_int("Futility Margin (Quiescence Search)"));
+ //int fmScale = get_option_value_int("Futility Margin Scale Factor (Main Search)");
+ //for (int i = 0; i < 6; i++)
+ // FutilityMargins[i] = (FutilityMargins[i] * fmScale) / 100;
- RazorDepth = (get_option_value_int("Maximum Razoring Depth") + 1) * OnePly;
- RazorMargin = value_from_centipawns(get_option_value_int("Razoring Margin"));
+ //RazorDepth = (get_option_value_int("Maximum Razoring Depth") + 1) * OnePly;
+ //RazorMargin = value_from_centipawns(get_option_value_int("Razoring Margin"));
UseLSNFiltering = get_option_value_bool("LSN filtering");
LSNTime = get_option_value_int("LSN Time Margin (sec)") * 1000;
{
MaxSearchTime = myTime / 30 + myIncrement;
AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
- EmergencyMaxSearchTime = Max(myTime / 2, myIncrement - 100);
} else { // Blitz game without increment
MaxSearchTime = myTime / 30;
AbsoluteMaxSearchTime = myTime / 8;
- EmergencyMaxSearchTime = myTime / 4;
}
}
else // (x moves) / (y minutes)
{
MaxSearchTime = myTime / 2;
AbsoluteMaxSearchTime = Min(myTime / 2, myTime - 500);
- EmergencyMaxSearchTime = myTime - 500;
} else {
MaxSearchTime = myTime / Min(movesToGo, 20);
AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
- EmergencyMaxSearchTime = Min((8 * myTime) / movesToGo, myTime / 2);
}
}
Position p(pos);
SearchStack ss[PLY_MAX_PLUS_2];
- Value alpha;
- Value beta;
-
// searchMoves are verified, copied, scored and sorted
RootMoveList rml(p, searchMoves);
ss[i].init(i);
ss[i].initKillers();
}
- IterationInfo[1].set(rml.get_move_score(0));
+ IterationInfo[1] = IterationInfoType(rml.get_move_score(0), rml.get_move_score(0));
Iteration = 1;
EasyMove = rml.scan_for_easy_move();
std::cout << "info depth " << Iteration << std::endl;
- //Calculate dynamic search window based on previous iterations.
- if (MultiPV == 1 && Iteration >= 6) {
- Value prevDelta1 = IterationInfo[Iteration - 1].speculated_value() - IterationInfo[Iteration - 2].speculated_value();
- Value prevDelta2 = IterationInfo[Iteration - 2].speculated_value() - IterationInfo[Iteration - 3].speculated_value();
+ // Calculate dynamic search window based on previous iterations
+ Value alpha, beta;
- Value delta = Max((2 * Abs(prevDelta1) + Abs(prevDelta2)) , ProblemMargin);
+ if (MultiPV == 1 && Iteration >= 6)
+ {
+ int prevDelta1 = IterationInfo[Iteration - 1].speculatedValue - IterationInfo[Iteration - 2].speculatedValue;
+ int prevDelta2 = IterationInfo[Iteration - 2].speculatedValue - IterationInfo[Iteration - 3].speculatedValue;
- alpha = IterationInfo[Iteration - 1].value() - delta;
- beta = IterationInfo[Iteration - 1].value() + delta;
- if (alpha < - VALUE_INFINITE) alpha = - VALUE_INFINITE;
- if (beta > VALUE_INFINITE) beta = VALUE_INFINITE;
+ int delta = Max(2 * abs(prevDelta1) + abs(prevDelta2), ProblemMargin);
- } else {
- alpha = - VALUE_INFINITE;
- beta = VALUE_INFINITE;
+ alpha = Max(IterationInfo[Iteration - 1].value - delta, -VALUE_INFINITE);
+ beta = Min(IterationInfo[Iteration - 1].value + delta, VALUE_INFINITE);
+ }
+ else
+ {
+ alpha = - VALUE_INFINITE;
+ beta = VALUE_INFINITE;
}
// Search to the current depth
Value value = root_search(p, ss, rml, alpha, beta);
// Write PV to transposition table, in case the relevant entries have
- // been overwritten during the search:
+ // been overwritten during the search.
TT.insert_pv(p, ss[0].pv);
if (AbortSearch)
- break; //Value cannot be trusted. Break out immediately!
+ break; // Value cannot be trusted. Break out immediately!
//Save info about search result
- Value speculated_value = value;
+ Value speculatedValue;
bool fHigh = false;
bool fLow = false;
+ Value delta = value - IterationInfo[Iteration - 1].value;
- Value prev_value = IterationInfo[Iteration - 1].value();
- Value delta = value - prev_value;
-
- if (value >= beta) {
- fHigh = true;
- speculated_value = prev_value + 2 * delta;
- BestMoveChangesByIteration[Iteration] += 2; //This is used to tell time management to allocate more time
- } else if (value <= alpha) {
- fLow = true;
- speculated_value = prev_value + 2 * delta;
- BestMoveChangesByIteration[Iteration] += 3; //This is used to tell time management to allocate more time
- } else {
- //nothing
+ if (value >= beta)
+ {
+ assert(delta > 0);
+
+ fHigh = true;
+ speculatedValue = value + delta;
+ BestMoveChangesByIteration[Iteration] += 2; // Allocate more time
}
+ else if (value <= alpha)
+ {
+ assert(value == alpha);
+ assert(delta < 0);
- if (speculated_value < - VALUE_INFINITE) speculated_value = - VALUE_INFINITE;
- if (speculated_value > VALUE_INFINITE) speculated_value = VALUE_INFINITE;
+ fLow = true;
+ speculatedValue = value + delta;
+ BestMoveChangesByIteration[Iteration] += 3; // Allocate more time
+ } else
+ speculatedValue = value;
- IterationInfo[Iteration].set(value, speculated_value, fHigh, fLow);
+ speculatedValue = Min(Max(speculatedValue, -VALUE_INFINITE), VALUE_INFINITE);
+ IterationInfo[Iteration] = IterationInfoType(value, speculatedValue);
// Erase the easy move if it differs from the new best move
if (ss[0].pv[0] != EasyMove)
// Stop search early when the last two iterations returned a mate score
if ( Iteration >= 6
- && abs(IterationInfo[Iteration].value()) >= abs(VALUE_MATE) - 100
- && abs(IterationInfo[Iteration-1].value()) >= abs(VALUE_MATE) - 100)
+ && abs(IterationInfo[Iteration].value) >= abs(VALUE_MATE) - 100
+ && abs(IterationInfo[Iteration-1].value) >= abs(VALUE_MATE) - 100)
stopSearch = true;
// Stop search early if one move seems to be much better than the rest
int64_t nodes = nodes_searched();
- if ( Iteration >= 8 && !fLow && !fHigh
+ if ( Iteration >= 8
+ && !fLow
+ && !fHigh
&& EasyMove == ss[0].pv[0]
&& ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
&& current_search_time() > MaxSearchTime / 16)
if (stopSearch)
{
+ //FIXME: Implement fail-low emergency measures
if (!PonderSearch)
break;
else
break;
}
- if (FailLow)
- {
- //Here we face the rare, but extremely difficult case:
- //Our aspiration search has failed low and we've run out of time!
- //So we have no move to play!
- //Now use the emergency time and try as quickly as possible to
- //find even one playable move.
-
- //FIXME: this is only for grepping logs purpose. Remove me when we are sure that this stuff really works!!
- if (AbortSearch)
- std::cout << "info depth " << 999 << std::endl;
- else
- std::cout << "info depth " << 998 << std::endl;
-
- //Prepare variables for emergency search
- AbortSearch = false;
- FailLow = false;
- AbsoluteMaxSearchTime = EmergencyMaxSearchTime;
- MaxSearchTime = EmergencyMaxSearchTime;
- ExtraSearchTime = 0;
- rml.sort();
-
- std::cout << "info depth " << Iteration << std::endl;
-
- //Cause we failed low, it's _likely_ that we couldn't get over alpha anyway.
- root_search(p, ss, rml, -VALUE_INFINITE, alpha);
- }
-
rml.sort();
// If we are pondering, we shouldn't print the best move before we
// Loop through all the moves in the root move list
for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
{
- if (alpha >= beta) {
- rml.set_move_score(i, -VALUE_INFINITE);
- //Leave node-counters and beta-counters as they are.
- continue;
+ 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;
}
-
int64_t nodes;
Move move;
StateInfo st;
// set the boolean variable Problem to true. This variable is used
// for time managment: When Problem is true, we try to complete the
// current iteration before playing a move.
- Problem = (Iteration >= 2 && value <= IterationInfo[Iteration-1].value() - ProblemMargin);
+ Problem = (Iteration >= 2 && value <= IterationInfo[Iteration-1].value - ProblemMargin);
if (Problem && StopOnPonderhit)
StopOnPonderhit = false;
// 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
// be trusted, and we break out of the loop without updating the best
- // move and/or PV:
+ // move and/or PV.
if (AbortSearch)
break;
rml.set_move_score(i, -VALUE_INFINITE);
else
{
- // New best move!
+ // PV move or new best move!
// Update PV
rml.set_move_score(i, value);
<< std::endl;
if (value > alpha)
- alpha = value;
+ alpha = value;
// Reset the global variable Problem to false if the value isn't too
// far below the final value from the last iteration.
- if (value > IterationInfo[Iteration - 1].value() - NoProblemMargin)
+ if (value > IterationInfo[Iteration - 1].value - NoProblemMargin)
Problem = false;
}
else // MultiPV > 1
}
alpha = rml.get_move_score(Min(i, MultiPV-1));
}
- }
+ } // New best move case
- if (alpha <= oldAlpha)
- FailLow = true;
- else
- FailLow = false;
+ assert(alpha >= oldAlpha);
+ FailLow = (alpha == oldAlpha);
}
return alpha;
}
// (from the computer's point of view) since the previous iteration:
if ( ply == 1
&& Iteration >= 2
- && -value <= IterationInfo[Iteration-1].value() - ProblemMargin)
+ && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
Problem = true;
}
}
// Null move search not allowed, try razoring
else if ( !value_is_mate(beta)
- && approximateEval < beta - RazorMargin
&& depth < RazorDepth
- && (RazorAtDepthOne || depth > OnePly)
+ && approximateEval < beta - RazorApprMargins[int(depth) - 2]
&& ttMove == MOVE_NONE
&& !pos.has_pawn_on_7th(pos.side_to_move()))
{
Value v = qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
- if ( (v < beta - RazorMargin - RazorMargin / 4)
- || (depth <= 2*OnePly && v < beta - RazorMargin)
- || (depth <= OnePly && v < beta - RazorMargin / 2))
- return v;
+ if (v < beta - RazorMargins[int(depth) - 2])
+ return v;
}
// Go with internal iterative deepening if we don't have a TT move
{
if (futilityValue == VALUE_NONE)
futilityValue = evaluate(pos, ei, threadID)
- + FutilityMargins[int(depth)/2 - 1]
- + 32 * (depth & 1);
+ + FutilityMargins[int(depth) - 2];
if (futilityValue < beta)
{
return value_from_tt(tte->value(), ply);
}
}
+ Move ttMove = (tte ? tte->move() : MOVE_NONE);
// Evaluate the position statically
EvalInfo ei;
// Initialize a MovePicker object for the current position, and prepare
// to search the moves. Because the depth is <= 0 here, only captures,
// queen promotions and checks (only if depth == 0) will be generated.
- MovePicker mp = MovePicker(pos, pvNode, MOVE_NONE, EmptySearchStack, depth);
+ MovePicker mp = MovePicker(pos, pvNode, ttMove, EmptySearchStack, depth);
Move move;
int moveCount = 0;
Bitboard dcCandidates = mp.discovered_check_candidates();
assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
// Update transposition table
+ Move m = ss[ply].pv[ply];
if (!pvNode)
{
Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
if (bestValue < beta)
TT.store(pos, value_to_tt(bestValue, ply), d, MOVE_NONE, VALUE_TYPE_UPPER);
else
- TT.store(pos, value_to_tt(bestValue, ply), d, MOVE_NONE, VALUE_TYPE_LOWER);
+ TT.store(pos, value_to_tt(bestValue, ply), d, m, VALUE_TYPE_LOWER);
}
// Update killers only for good check moves
- Move m = ss[ply].currentMove;
if (alpha >= beta && ok_to_history(pos, m)) // Only non capture moves are considered
- {
- // Wrong to update history when depth is <= 0
update_killers(m, ss[ply]);
- }
+
return bestValue;
}
// (from the computer's point of view) since the previous iteration.
if ( sp->ply == 1
&& Iteration >= 2
- && -value <= IterationInfo[Iteration-1].value() - ProblemMargin)
+ && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
Problem = true;
}
lock_release(&(sp->lock));
return;
bool overTime = t > AbsoluteMaxSearchTime
- || (RootMoveNumber == 1 && t > MaxSearchTime + ExtraSearchTime && !FailLow) //FIXME: BUG??
+ || (RootMoveNumber == 1 && t > MaxSearchTime + ExtraSearchTime && !FailLow) //FIXME: We are not checking any problem flags, BUG?
|| ( !FailHigh && !FailLow && !fail_high_ply_1() && !Problem
&& t > 6*(MaxSearchTime + ExtraSearchTime));
projects / stockfish / blobdiff