// Depth limit for selective search:
Depth SelectiveDepth = 7*OnePly;
+ // Use dynamic LMR?
+ const bool UseDynamicLMR = false;
+
// Use internal iterative deepening?
const bool UseIIDAtPVNodes = true;
const bool UseIIDAtNonPVNodes = false;
- // Use null move driven internal iterative deepening?
- bool UseNullDrivenIID = false;
-
// Internal iterative deepening margin. At Non-PV moves, when
// UseIIDAtNonPVNodes is true, we do an internal iterative deepening search
// when the static evaluation is at most IIDMargin below beta.
// Iteration counters
int Iteration;
- bool LastIterations;
BetaCounterType BetaCounter;
// Scores and number of times the best move changed for each iteration:
int SearchStartTime;
int MaxNodes, MaxDepth;
int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime;
- Move BestRootMove, PonderMove, EasyMove;
+ Move EasyMove;
int RootMoveNumber;
bool InfiniteSearch;
bool PonderSearch;
Depth depth, int ply, int threadID);
void sp_search(SplitPoint *sp, int threadID);
void sp_search_pv(SplitPoint *sp, int threadID);
- void init_search_stack(SearchStack& ss);
- void init_search_stack(SearchStack ss[]);
void init_node(const Position &pos, SearchStack ss[], int ply, int threadID);
void update_pv(SearchStack ss[], int ply);
void sp_update_pv(SearchStack *pss, SearchStack ss[], int ply);
bool thread_is_available(int slave, int master);
bool idle_thread_exists(int master);
bool split(const Position &pos, SearchStack *ss, int ply,
- Value *alpha, Value *beta, Value *bestValue, Depth depth,
- int *moves, MovePicker *mp, int master, bool pvNode);
+ Value *alpha, Value *beta, Value *bestValue, Depth depth, int *moves,
+ MovePicker *mp, Bitboard dcCandidates, int master, bool pvNode);
void wake_sleeping_threads();
#if !defined(_MSC_VER)
SearchStack EmptySearchStack;
+// SearchStack::init() initializes a search stack. Used at the beginning of a
+// new search from the root.
+void SearchStack::init(int ply) {
+
+ pv[ply] = pv[ply + 1] = MOVE_NONE;
+ currentMove = threatMove = MOVE_NONE;
+ reduction = Depth(0);
+ currentMoveCaptureValue = Value(0);
+}
+
+void SearchStack::initKillers() {
+
+ mateKiller = MOVE_NONE;
+ for (int i = 0; i < KILLER_MAX; i++)
+ killers[i] = MOVE_NONE;
+}
+
+
////
//// Functions
////
// Initialize global search variables
Idle = false;
SearchStartTime = get_system_time();
- BestRootMove = MOVE_NONE;
- PonderMove = MOVE_NONE;
EasyMove = MOVE_NONE;
for (int i = 0; i < THREAD_MAX; i++)
{
if (UseLogFile)
LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app);
- UseNullDrivenIID = get_option_value_bool("Null driven IID");
UseQSearchFutilityPruning = get_option_value_bool("Futility Pruning (Quiescence Search)");
UseFutilityPruning = get_option_value_bool("Futility Pruning (Main Search)");
}
// Init also the empty search stack
- init_search_stack(EmptySearchStack);
+ EmptySearchStack.init(0);
+ EmptySearchStack.initKillers();
}
// Initialize
TT.new_search();
H.clear();
- init_search_stack(ss);
-
+ for (int i = 0; i < 3; i++)
+ {
+ ss[i].init(i);
+ ss[i].initKillers();
+ }
ValueByIteration[0] = Value(0);
ValueByIteration[1] = rml.get_move_score(0);
Iteration = 1;
- LastIterations = false;
EasyMove = rml.scan_for_easy_move();
ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2)
+ BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3);
- // Try to guess if the current iteration is the last one or the last two
- LastIterations = (current_search_time() > ((MaxSearchTime + ExtraSearchTime)*58) / 128);
-
// 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.
<< " hashfull " << TT.full() << std::endl;
// Print the best move and the ponder move to the standard output
+ if (ss[0].pv[0] == MOVE_NONE)
+ {
+ ss[0].pv[0] = rml.get_move(0);
+ ss[0].pv[1] = MOVE_NONE;
+ }
std::cout << "bestmove " << ss[0].pv[0];
if (ss[0].pv[1] != MOVE_NONE)
std::cout << " ponder " << ss[0].pv[1];
if (dbg_show_hit_rate)
dbg_print_hit_rate(LogFile);
- UndoInfo u;
+ StateInfo st;
LogFile << "Nodes: " << nodes_searched() << std::endl
<< "Nodes/second: " << nps() << std::endl
<< "Best move: " << move_to_san(p, ss[0].pv[0]) << std::endl;
- p.do_move(ss[0].pv[0], u);
+ p.do_move(ss[0].pv[0], st);
LogFile << "Ponder move: " << move_to_san(p, ss[0].pv[1])
<< std::endl << std::endl;
}
Value alpha = -VALUE_INFINITE;
Value beta = VALUE_INFINITE, 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++)
{
int64_t nodes;
Move move;
- UndoInfo u;
+ StateInfo st;
Depth ext, newDepth;
RootMoveNumber = i + 1;
newDepth = (Iteration - 2) * OnePly + ext + InitialDepth;
// Make the move, and search it
- pos.do_move(move, u);
+ pos.do_move(move, st, dcCandidates);
if (i < MultiPV)
{
}
}
- pos.undo_move(move, u);
+ pos.undo_move(move);
// Finished searching the move. If AbortSearch is true, the search
// was aborted because the user interrupted the search or because we
Move move, movesSearched[256];
int moveCount = 0;
Value value, bestValue = -VALUE_INFINITE;
+ Bitboard dcCandidates = mp.discovered_check_candidates();
Color us = pos.side_to_move();
bool isCheck = pos.is_check();
bool mateThreat = pos.has_mate_threat(opposite_color(us));
assert(move_is_ok(move));
bool singleReply = (isCheck && mp.number_of_moves() == 1);
- bool moveIsCheck = pos.move_is_check(move);
+ bool moveIsCheck = pos.move_is_check(move, dcCandidates);
bool moveIsCapture = pos.move_is_capture(move);
movesSearched[moveCount++] = ss[ply].currentMove = move;
Depth newDepth = depth - OnePly + ext;
// Make and search the move
- UndoInfo u;
- pos.do_move(move, u);
+ StateInfo st;
+ pos.do_move(move, st, dcCandidates);
if (moveCount == 1) // The first move in list is the PV
value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
}
}
}
- pos.undo_move(move, u);
+ pos.undo_move(move);
assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
&& !AbortSearch
&& !thread_should_stop(threadID)
&& split(pos, ss, ply, &alpha, &beta, &bestValue, depth,
- &moveCount, &mp, threadID, true))
+ &moveCount, &mp, dcCandidates, threadID, true))
break;
}
Value approximateEval = quick_evaluate(pos);
bool mateThreat = false;
- bool nullDrivenIID = false;
bool isCheck = pos.is_check();
// Null move search
{
ss[ply].currentMove = MOVE_NULL;
- UndoInfo u;
- pos.do_null_move(u);
+ StateInfo st;
+ pos.do_null_move(st);
int R = (depth >= 4 * OnePly ? 4 : 3); // Null move dynamic reduction
Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);
- // Check for a null capture artifact, if the value without the null capture
- // is above beta then mark the node as a suspicious failed low. We will verify
- // later if we are really under threat.
- if ( UseNullDrivenIID
- && nullValue < beta
- && depth > 6 * OnePly
- &&!value_is_mate(nullValue)
- && ttMove == MOVE_NONE
- && ss[ply + 1].currentMove != MOVE_NONE
- && pos.move_is_capture(ss[ply + 1].currentMove)
- && pos.see(ss[ply + 1].currentMove) + nullValue >= beta)
- nullDrivenIID = true;
-
- pos.undo_null_move(u);
+ pos.undo_null_move();
if (value_is_mate(nullValue))
{
// low score (which will cause the reduced move to fail high in the
// parent node, which will trigger a re-search with full depth).
if (nullValue == value_mated_in(ply + 2))
- {
mateThreat = true;
- nullDrivenIID = false;
- }
+
ss[ply].threatMove = ss[ply + 1].currentMove;
if ( depth < ThreatDepth
&& ss[ply - 1].reduction
{
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;
}
search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID);
ttMove = ss[ply].pv[ply];
}
- else if (nullDrivenIID)
- {
- // The null move failed low due to a suspicious capture. Perhaps we
- // are facing a null capture artifact due to the side to move change
- // and this position should fail high. So do a normal search with a
- // reduced depth to get a good ttMove to use in the following full
- // depth search.
- Move tm = ss[ply].threatMove;
-
- assert(tm != MOVE_NONE);
- assert(ttMove == MOVE_NONE);
-
- search(pos, ss, beta, depth/2, ply, false, threadID);
- ttMove = ss[ply].pv[ply];
- ss[ply].threatMove = tm;
- }
// Initialize a MovePicker object for the current position, and prepare
// to search all moves:
Move move, movesSearched[256];
int moveCount = 0;
Value value, bestValue = -VALUE_INFINITE;
+ Bitboard dcCandidates = mp.discovered_check_candidates();
Value futilityValue = VALUE_NONE;
bool useFutilityPruning = UseFutilityPruning
&& depth < SelectiveDepth
assert(move_is_ok(move));
bool singleReply = (isCheck && mp.number_of_moves() == 1);
- bool moveIsCheck = pos.move_is_check(move);
+ bool moveIsCheck = pos.move_is_check(move, dcCandidates);
bool moveIsCapture = pos.move_is_capture(move);
movesSearched[moveCount++] = ss[ply].currentMove = move;
}
// Make and search the move
- UndoInfo u;
- pos.do_move(move, u);
+ StateInfo st;
+ pos.do_move(move, st, dcCandidates);
// 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.
&& !move_is_castle(move)
&& !move_is_killer(move, ss[ply]))
{
- ss[ply].reduction = OnePly;
- value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);
+ // LMR dynamic reduction
+ Depth R = UseDynamicLMR
+ && 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);
}
else
value = beta; // Just to trigger next condition
ss[ply].reduction = Depth(0);
value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID);
}
- pos.undo_move(move, u);
+ pos.undo_move(move);
assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
&& !AbortSearch
&& !thread_should_stop(threadID)
&& split(pos, ss, ply, &beta, &beta, &bestValue, depth, &moveCount,
- &mp, threadID, false))
+ &mp, dcCandidates, threadID, false))
break;
}
}
TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER);
}
+
+ assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
+
return bestValue;
}
if (pos.is_draw())
return VALUE_DRAW;
- // Transposition table lookup
- const TTEntry* tte = TT.retrieve(pos);
- if (tte && ok_to_use_TT(tte, depth, beta, ply))
- return value_from_tt(tte->value(), ply);
+ // Transposition table lookup, only when not in PV
+ TTEntry* tte = NULL;
+ bool pvNode = (beta - alpha != 1);
+ if (!pvNode)
+ {
+ 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);
+ }
+ }
// Evaluate the position statically
EvalInfo ei;
+ Value staticValue;
bool isCheck = pos.is_check();
- Value staticValue = (isCheck ? -VALUE_INFINITE : evaluate(pos, ei, threadID));
+
+ if (isCheck)
+ staticValue = -VALUE_INFINITE;
+
+ else if (tte && (tte->type() == VALUE_TYPE_EVAL || tte->staticValue()))
+ {
+ // Use the cached evaluation score if possible
+ assert(tte->value() == evaluate(pos, ei, threadID));
+ assert(ei.futilityMargin == Value(0));
+
+ staticValue = tte->value();
+ ei.futilityMargin = Value(0); // manually initialize futilityMargin
+ }
+ 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.
- bool pvNode = (beta - alpha != 1);
- MovePicker mp = MovePicker(pos, pvNode, MOVE_NONE, EmptySearchStack, depth, isCheck ? NULL : &ei);
+ MovePicker mp = MovePicker(pos, pvNode, MOVE_NONE, EmptySearchStack, depth);
Move move;
int moveCount = 0;
+ Bitboard dcCandidates = mp.discovered_check_candidates();
Color us = pos.side_to_move();
bool enoughMaterial = pos.non_pawn_material(us) > RookValueMidgame;
&& !isCheck
&& !pvNode
&& !move_promotion(move)
- && !pos.move_is_check(move)
+ && !pos.move_is_check(move, dcCandidates)
&& !pos.move_is_passed_pawn_push(move))
{
Value futilityValue = staticValue
continue;
// Make and search the move.
- UndoInfo u;
- pos.do_move(move, u);
+ StateInfo st;
+ pos.do_move(move, st, dcCandidates);
Value value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID);
- pos.undo_move(move, u);
+ pos.undo_move(move);
assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
// Update transposition table
- TT.store(pos, value_to_tt(bestValue, ply), depth, MOVE_NONE, VALUE_TYPE_EXACT);
+ if (!pvNode)
+ {
+ Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
+ Value v = value_to_tt(bestValue, ply);
+ TTEntry* e;
+ if (bestValue < beta)
+ e = TT.store(pos, v, d, MOVE_NONE, VALUE_TYPE_UPPER);
+ else
+ e = TT.store(pos, v, d, MOVE_NONE, VALUE_TYPE_LOWER);
+
+ assert(e && e == TT.retrieve(pos));
+ assert(!e->staticValue());
+
+ // If the just stored value happens to be equal to the static evaluation
+ // score then set the flag, so to avoid calling evaluation() next time we
+ // hit this position.
+ if (staticValue == v && !ei.futilityMargin)
+ e->setStaticValue();
+ }
// Update killers only for good check moves
Move m = ss[ply].currentMove;
{
assert(move_is_ok(move));
- bool moveIsCheck = pos.move_is_check(move);
+ bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates);
bool moveIsCapture = pos.move_is_capture(move);
lock_grab(&(sp->lock));
continue;
// Make and search the move.
- UndoInfo u;
- pos.do_move(move, u);
+ StateInfo st;
+ pos.do_move(move, st, sp->dcCandidates);
// 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.
ss[sp->ply].reduction = Depth(0);
value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID);
}
- pos.undo_move(move, u);
+ pos.undo_move(move);
assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
&& !thread_should_stop(threadID)
&& (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE)
{
- bool moveIsCheck = pos.move_is_check(move);
+ bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates);
bool moveIsCapture = pos.move_is_capture(move);
assert(move_is_ok(move));
Depth newDepth = sp->depth - OnePly + ext;
// Make and search the move.
- UndoInfo u;
- pos.do_move(move, u);
+ StateInfo st;
+ pos.do_move(move, st, sp->dcCandidates);
// 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.
Threads[threadID].failHighPly1 = false;
}
}
- pos.undo_move(move, u);
+ pos.undo_move(move);
assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
if (includeMove)
{
// Find a quick score for the move
- UndoInfo u;
+ StateInfo st;
SearchStack ss[PLY_MAX_PLUS_2];
moves[count].move = mlist[i].move;
moves[count].nodes = 0ULL;
- pos.do_move(moves[count].move, u);
+ pos.do_move(moves[count].move, st);
moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE,
Depth(0), 1, 0);
- pos.undo_move(moves[count].move, u);
+ pos.undo_move(moves[count].move);
moves[count].pv[0] = moves[i].move;
moves[count].pv[1] = MOVE_NONE; // FIXME
count++;
}
- // init_search_stack() initializes a search stack at the beginning of a
- // new search from the root.
- void init_search_stack(SearchStack& ss) {
-
- ss.pv[0] = MOVE_NONE;
- ss.pv[1] = MOVE_NONE;
- ss.currentMove = MOVE_NONE;
- ss.threatMove = MOVE_NONE;
- ss.reduction = Depth(0);
- for (int j = 0; j < KILLER_MAX; j++)
- ss.killers[j] = MOVE_NONE;
- }
-
- void init_search_stack(SearchStack ss[]) {
-
- for (int i = 0; i < 3; i++)
- {
- ss[i].pv[i] = MOVE_NONE;
- ss[i].pv[i+1] = MOVE_NONE;
- ss[i].currentMove = MOVE_NONE;
- ss[i].threatMove = MOVE_NONE;
- ss[i].reduction = Depth(0);
- for (int j = 0; j < KILLER_MAX; j++)
- ss[i].killers[j] = MOVE_NONE;
- }
- }
-
-
// init_node() is called at the beginning of all the search functions
// (search(), search_pv(), qsearch(), and so on) and initializes the search
// stack object corresponding to the current node. Once every
NodesSincePoll = 0;
}
}
- ss[ply].pv[ply] = ss[ply].pv[ply+1] = ss[ply].currentMove = MOVE_NONE;
- ss[ply+2].mateKiller = MOVE_NONE;
- ss[ply].threatMove = MOVE_NONE;
- ss[ply].reduction = Depth(0);
- ss[ply].currentMoveCaptureValue = Value(0);
- for (int j = 0; j < KILLER_MAX; j++)
- ss[ply+2].killers[j] = MOVE_NONE;
+
+ ss[ply].init(ply);
+ ss[ply+2].initKillers();
if(Threads[threadID].printCurrentLine)
print_current_line(ss, ply, threadID);
|| ( !FailHigh && !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 &&
// splitPoint->cpus becomes 0), split() returns true.
bool split(const Position &p, SearchStack *sstck, int ply,
- Value *alpha, Value *beta, Value *bestValue,
- Depth depth, int *moves, MovePicker *mp, int master, bool pvNode) {
+ Value *alpha, Value *beta, Value *bestValue, Depth depth, int *moves,
+ MovePicker *mp, Bitboard dcCandidates, int master, bool pvNode) {
+
assert(p.is_ok());
assert(sstck != NULL);
assert(ply >= 0 && ply < PLY_MAX);
splitPoint->alpha = pvNode? *alpha : (*beta - 1);
splitPoint->beta = *beta;
splitPoint->pvNode = pvNode;
+ splitPoint->dcCandidates = dcCandidates;
splitPoint->bestValue = *bestValue;
splitPoint->master = master;
splitPoint->mp = mp;
projects / stockfish / blobdiff