////
#include <cassert>
+#include <cstring>
#include <fstream>
#include <iostream>
#include <sstream>
/// Types
+ // 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 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.
+
+ struct IterationInfoType {
+
+ IterationInfoType(Value v = Value(0), Value sv = Value(0))
+ : value(v), speculatedValue(sv) {}
+
+ Value value, speculatedValue;
+ };
+
+
// The BetaCounterType class is used to order moves at ply one.
// Apart for the first one that has its score, following moves
// normally have score -VALUE_INFINITE, so are ordered according
BetaCounterType BetaCounter;
// Scores and number of times the best move changed for each iteration:
- Value ValueByIteration[PLY_MAX_PLUS_2];
+ IterationInfoType IterationInfo[PLY_MAX_PLUS_2];
int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
// MultiPV mode
bool AbortSearch;
bool Quit;
bool FailHigh;
+ bool FailLow;
bool Problem;
bool PonderingEnabled;
int ExactMaxTime;
/// Functions
Value id_loop(const Position &pos, Move searchMoves[]);
- Value root_search(Position &pos, SearchStack ss[], RootMoveList &rml);
- 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(const Position &pos, SearchStack ss[], int ply, int threadID);
+ void init_node(SearchStack ss[], int ply, int threadID);
void update_pv(SearchStack ss[], int ply);
void sp_update_pv(SearchStack *pss, SearchStack ss[], int ply);
bool connected_moves(const Position &pos, Move m1, Move m2);
pv[ply] = pv[ply + 1] = MOVE_NONE;
currentMove = threatMove = MOVE_NONE;
reduction = Depth(0);
- currentMoveCaptureValue = Value(0);
}
void SearchStack::initKillers() {
AbortSearch = false;
Quit = false;
FailHigh = false;
+ FailLow = false;
Problem = false;
ExactMaxTime = maxTime;
ss[i].init(i);
ss[i].initKillers();
}
- ValueByIteration[0] = Value(0);
- ValueByIteration[1] = 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();
// Iterative deepening loop
- while (!AbortSearch && Iteration < PLY_MAX)
+ while (Iteration < PLY_MAX)
{
// Initialize iteration
rml.sort();
std::cout << "info depth " << Iteration << std::endl;
+ // Calculate dynamic search window based on previous iterations
+ Value alpha, beta;
+
+ 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;
+
+ int delta = Max(2 * abs(prevDelta1) + abs(prevDelta2), ProblemMargin);
+
+ 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
- ValueByIteration[Iteration] = root_search(p, ss, rml);
+ 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.
+ TT.insert_pv(p, ss[0].pv);
+
+ if (AbortSearch)
+ break; // Value cannot be trusted. Break out immediately!
+
+ //Save info about search result
+ Value speculatedValue;
+ bool fHigh = false;
+ bool fLow = false;
+ Value delta = value - IterationInfo[Iteration - 1].value;
+
+ 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);
+
+ fLow = true;
+ speculatedValue = value + delta;
+ BestMoveChangesByIteration[Iteration] += 3; // Allocate more time
+ } else
+ speculatedValue = value;
+
+ 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(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
- && abs(ValueByIteration[Iteration-1]) >= 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
&& 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
StopOnPonderhit = true;
}
}
- // Write PV to transposition table, in case the relevant entries have
- // been overwritten during the search:
- TT.insert_pv(p, ss[0].pv);
if (MaxDepth && Iteration >= MaxDepth)
break;
// scheme (perhaps we should try to use this at internal PV nodes, too?)
// and prints some information to the standard output.
- Value root_search(Position &pos, SearchStack ss[], RootMoveList &rml) {
+ Value root_search(Position &pos, SearchStack ss[], RootMoveList &rml, Value alpha, Value beta) {
- Value alpha = -VALUE_INFINITE;
- Value beta = VALUE_INFINITE, value;
+ Value oldAlpha = alpha;
+ Value value;
Bitboard dcCandidates = pos.discovered_check_candidates(pos.side_to_move());
// Loop through all the moves in the root move list
for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
{
+ 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;
if (i < MultiPV)
{
- value = -search_pv(pos, ss, -beta, VALUE_INFINITE, newDepth, 1, 0);
+ value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
// If the value has dropped a lot compared to the last iteration,
// 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 <= ValueByIteration[Iteration-1] - 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);
LogFile << pretty_pv(pos, current_search_time(), Iteration, nodes_searched(), value, ss[0].pv)
<< std::endl;
- alpha = value;
+ if (value > alpha)
+ 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 > ValueByIteration[Iteration - 1] - 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
+
+ assert(alpha >= oldAlpha);
+
+ FailLow = (alpha == oldAlpha);
}
return alpha;
}
// Initialize, and make an early exit in case of an aborted search,
// an instant draw, maximum ply reached, etc.
- init_node(pos, ss, ply, threadID);
+ init_node(ss, ply, threadID);
// After init_node() that calls poll()
if (AbortSearch || thread_should_stop(threadID))
movesSearched[moveCount++] = ss[ply].currentMove = move;
- if (moveIsCapture)
- ss[ply].currentMoveCaptureValue =
- move_is_ep(move)? PawnValueMidgame : pos.midgame_value_of_piece_on(move_to(move));
- else
- ss[ply].currentMoveCaptureValue = Value(0);
-
// Decide the new search depth
bool dangerous;
Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous);
// (from the computer's point of view) since the previous iteration:
if ( ply == 1
&& Iteration >= 2
- && -value <= ValueByIteration[Iteration-1] - ProblemMargin)
+ && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
Problem = true;
}
// Initialize, and make an early exit in case of an aborted search,
// an instant draw, maximum ply reached, etc.
- init_node(pos, ss, ply, threadID);
+ init_node(ss, ply, threadID);
// After init_node() that calls poll()
if (AbortSearch || thread_should_stop(threadID))
StateInfo st;
pos.do_null_move(st);
- int R = (depth >= 4 * OnePly ? 4 : 3); // Null move dynamic reduction
+ int R = (depth >= 5 * OnePly ? 4 : 3); // Null move dynamic reduction
Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);
{
Value v = qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
if ( (v < beta - RazorMargin - RazorMargin / 4)
- || (depth < 3*OnePly && v < beta - RazorMargin)
- || (depth < 2*OnePly && v < beta - RazorMargin / 2))
+ || (depth <= 2*OnePly && v < beta - RazorMargin)
+ || (depth <= OnePly && v < beta - RazorMargin / 2))
return v;
}
&& !move_is_castle(move)
&& !move_is_killer(move, ss[ply]))
{
- // LMR dynamic reduction
- Depth R = (moveCount >= 2 * LMRNonPVMoves && depth > 7*OnePly ? 2*OnePly : OnePly);
-
- ss[ply].reduction = R;
- value = -search(pos, ss, -(beta-1), newDepth-R, ply+1, true, threadID);
+ ss[ply].reduction = OnePly;
+ value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);
}
else
value = beta; // Just to trigger next condition
// Initialize, and make an early exit in case of an aborted search,
// an instant draw, maximum ply reached, etc.
- init_node(pos, ss, ply, threadID);
+ init_node(ss, ply, threadID);
// After init_node() that calls poll()
if (AbortSearch || thread_should_stop(threadID))
return VALUE_DRAW;
// Transposition table lookup, only when not in PV
+ TTEntry* tte = NULL;
bool pvNode = (beta - alpha != 1);
if (!pvNode)
{
- const TTEntry* tte = TT.retrieve(pos);
+ tte = TT.retrieve(pos);
if (tte && ok_to_use_TT(tte, depth, beta, ply))
+ {
+ assert(tte->type() != VALUE_TYPE_EVAL);
+
return value_from_tt(tte->value(), ply);
+ }
}
+ Move ttMove = (tte ? tte->move() : MOVE_NONE);
// Evaluate the position statically
EvalInfo ei;
+ Value staticValue;
bool isCheck = pos.is_check();
- Value staticValue = (isCheck ? -VALUE_INFINITE : evaluate(pos, ei, threadID));
+ ei.futilityMargin = Value(0); // Manually initialize futilityMargin
+
+ if (isCheck)
+ staticValue = -VALUE_INFINITE;
+
+ else if (tte && tte->type() == VALUE_TYPE_EVAL)
+ {
+ // Use the cached evaluation score if possible
+ assert(tte->value() == evaluate(pos, ei, threadID));
+ assert(ei.futilityMargin == Value(0));
+
+ staticValue = tte->value();
+ }
+ else
+ staticValue = evaluate(pos, ei, threadID);
if (ply == PLY_MAX - 1)
return evaluate(pos, ei, threadID);
Value bestValue = staticValue;
if (bestValue >= beta)
+ {
+ // Store the score to avoid a future costly evaluation() call
+ if (!isCheck && !tte && ei.futilityMargin == 0)
+ TT.store(pos, value_to_tt(bestValue, ply), Depth(-127*OnePly), MOVE_NONE, VALUE_TYPE_EVAL);
+
return bestValue;
+ }
if (bestValue > alpha)
alpha = bestValue;
// 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, isCheck ? NULL : &ei);
+ 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
- TT.store(pos, value_to_tt(bestValue, ply), depth, MOVE_NONE, VALUE_TYPE_EXACT);
+ 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, 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;
}
assert(move_is_ok(move));
- if (moveIsCapture)
- ss[sp->ply].currentMoveCaptureValue =
- move_is_ep(move)? PawnValueMidgame : pos.midgame_value_of_piece_on(move_to(move));
- else
- ss[sp->ply].currentMoveCaptureValue = Value(0);
-
lock_grab(&(sp->lock));
int moveCount = ++sp->moves;
lock_release(&(sp->lock));
// (from the computer's point of view) since the previous iteration.
if ( sp->ply == 1
&& Iteration >= 2
- && -value <= ValueByIteration[Iteration-1] - ProblemMargin)
+ && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
Problem = true;
}
lock_release(&(sp->lock));
// NodesBetweenPolls nodes, init_node() also calls poll(), which polls
// for user input and checks whether it is time to stop the search.
- void init_node(const Position &pos, SearchStack ss[], int ply, int threadID) {
+ void init_node(SearchStack ss[], int ply, int threadID) {
assert(ply >= 0 && ply < PLY_MAX);
assert(threadID >= 0 && threadID < ActiveThreads);
return;
bool overTime = t > AbsoluteMaxSearchTime
- || (RootMoveNumber == 1 && t > MaxSearchTime + ExtraSearchTime)
- || ( !FailHigh && !fail_high_ply_1() && !Problem
+ || (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));
- if ( (Iteration >= 2 && (!InfiniteSearch && overTime))
+ if ( (Iteration >= 3 && (!InfiniteSearch && overTime))
|| (ExactMaxTime && t >= ExactMaxTime)
|| (Iteration >= 3 && MaxNodes && nodes_searched() >= MaxNodes))
AbortSearch = true;
void ponderhit() {
int t = current_search_time();
PonderSearch = false;
- if(Iteration >= 2 &&
+ if(Iteration >= 3 &&
(!InfiniteSearch && (StopOnPonderhit ||
t > AbsoluteMaxSearchTime ||
(RootMoveNumber == 1 &&
- t > MaxSearchTime + ExtraSearchTime) ||
- (!FailHigh && !fail_high_ply_1() && !Problem &&
+ t > MaxSearchTime + ExtraSearchTime && !FailLow) ||
+ (!FailHigh && !FailLow && !fail_high_ply_1() && !Problem &&
t > 6*(MaxSearchTime + ExtraSearchTime)))))
AbortSearch = true;
}
projects / stockfish / blobdiff