X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=0d290eec65dae9451fc7c96a2c4a38fda23d0870;hp=6a4e352f279f95b242d14cee95a23a303bc2bce7;hb=6b82a234d03bb70e538ace708c128238811f06e7;hpb=e46a72dd1df5142cbbbd67ccff9ce2cbd3364450 diff --git a/src/search.cpp b/src/search.cpp index 6a4e352f..0d290eec 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -25,11 +25,11 @@ #include #include -#include "book.h" #include "evaluate.h" #include "movegen.h" #include "movepick.h" #include "notation.h" +#include "rkiss.h" #include "search.h" #include "timeman.h" #include "thread.h" @@ -42,7 +42,6 @@ namespace Search { LimitsType Limits; std::vector RootMoves; Position RootPos; - Color RootColor; Time::point SearchTime; StateStackPtr SetupStates; } @@ -53,9 +52,6 @@ using namespace Search; namespace { - // Set to true to force running with one thread. Used for debugging - const bool FakeSplit = false; - // Different node types, used as template parameter enum NodeType { Root, PV, NonPV }; @@ -77,7 +73,7 @@ namespace { return (Depth) Reductions[PvNode][i][std::min(int(d) / ONE_PLY, 63)][std::min(mn, 63)]; } - size_t MultiPV, PVIdx; + size_t PVIdx; TimeManager TimeMgr; double BestMoveChanges; Value DrawValue[COLOR_NB]; @@ -98,18 +94,21 @@ namespace { string uci_pv(const Position& pos, int depth, Value alpha, Value beta); struct Skill { - Skill(int l) : level(l), best(MOVE_NONE) {} + Skill(int l, int rootSize) : level(l), + candidates(l < 20 ? std::min(4, rootSize) : 0), + best(MOVE_NONE) {} ~Skill() { - if (enabled()) // Swap best PV line with the sub-optimal one + if (candidates) // Swap best PV line with the sub-optimal one std::swap(RootMoves[0], *std::find(RootMoves.begin(), RootMoves.end(), best ? best : pick_move())); } - bool enabled() const { return level < 20; } + size_t candidates_size() const { return candidates; } bool time_to_pick(int depth) const { return depth == 1 + level; } Move pick_move(); int level; + size_t candidates; Move best; }; @@ -180,14 +179,11 @@ uint64_t Search::perft(Position& pos, Depth depth) { void Search::think() { - static PolyglotBook book; // Defined static to initialize the PRNG only once - - RootColor = RootPos.side_to_move(); - TimeMgr.init(Limits, RootPos.game_ply(), RootColor); + TimeMgr.init(Limits, RootPos.game_ply(), RootPos.side_to_move()); int cf = Options["Contempt Factor"] * PawnValueEg / 100; // From centipawns - DrawValue[ RootColor] = VALUE_DRAW - Value(cf); - DrawValue[~RootColor] = VALUE_DRAW + Value(cf); + DrawValue[ RootPos.side_to_move()] = VALUE_DRAW - Value(cf); + DrawValue[~RootPos.side_to_move()] = VALUE_DRAW + Value(cf); if (RootMoves.empty()) { @@ -199,25 +195,14 @@ void Search::think() { goto finalize; } - if (Options["OwnBook"] && !Limits.infinite && !Limits.mate) - { - Move bookMove = book.probe(RootPos, Options["Book File"], Options["Best Book Move"]); - - if (bookMove && std::count(RootMoves.begin(), RootMoves.end(), bookMove)) - { - std::swap(RootMoves[0], *std::find(RootMoves.begin(), RootMoves.end(), bookMove)); - goto finalize; - } - } - if (Options["Write Search Log"]) { Log log(Options["Search Log Filename"]); log << "\nSearching: " << RootPos.fen() << "\ninfinite: " << Limits.infinite << " ponder: " << Limits.ponder - << " time: " << Limits.time[RootColor] - << " increment: " << Limits.inc[RootColor] + << " time: " << Limits.time[RootPos.side_to_move()] + << " increment: " << Limits.inc[RootPos.side_to_move()] << " moves to go: " << Limits.movestogo << "\n" << std::endl; } @@ -285,7 +270,6 @@ namespace { Value bestValue, alpha, beta, delta; std::memset(ss-2, 0, 5 * sizeof(Stack)); - (ss-1)->currentMove = MOVE_NULL; // Hack to skip update gains depth = 0; BestMoveChanges = 0; @@ -298,15 +282,12 @@ namespace { Countermoves.clear(); Followupmoves.clear(); - MultiPV = Options["MultiPV"]; - Skill skill(Options["Skill Level"]); + size_t multiPV = Options["MultiPV"]; + Skill skill(Options["Skill Level"], RootMoves.size()); // Do we have to play with skill handicap? In this case enable MultiPV search // that we will use behind the scenes to retrieve a set of possible moves. - if (skill.enabled() && MultiPV < 4) - MultiPV = 4; - - MultiPV = std::min(MultiPV, RootMoves.size()); + multiPV = std::max(multiPV, skill.candidates_size()); // Iterative deepening loop until requested to stop or target depth reached while (++depth <= MAX_PLY && !Signals.stop && (!Limits.depth || depth <= Limits.depth)) @@ -320,7 +301,7 @@ namespace { RootMoves[i].prevScore = RootMoves[i].score; // MultiPV loop. We perform a full root search for each PV line - for (PVIdx = 0; PVIdx < MultiPV && !Signals.stop; ++PVIdx) + for (PVIdx = 0; PVIdx < multiPV && PVIdx < RootMoves.size() && !Signals.stop; ++PVIdx) { // Reset aspiration window starting size if (depth >= 5) @@ -377,7 +358,7 @@ namespace { else break; - delta += delta / 2; + delta += 3 * delta / 8; assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE); } @@ -385,12 +366,12 @@ namespace { // Sort the PV lines searched so far and update the GUI std::stable_sort(RootMoves.begin(), RootMoves.begin() + PVIdx + 1); - if (PVIdx + 1 == MultiPV || Time::now() - SearchTime > 3000) + if (PVIdx + 1 == multiPV || Time::now() - SearchTime > 3000) sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; } // If skill levels are enabled and time is up, pick a sub-optimal best move - if (skill.enabled() && skill.time_to_pick(depth)) + if (skill.candidates_size() && skill.time_to_pick(depth)) skill.pick_move(); if (Options["Write Search Log"]) @@ -414,7 +395,7 @@ namespace { if (Limits.use_time_management() && !Signals.stop && !Signals.stopOnPonderhit) { // Take some extra time if the best move has changed - if (depth > 4 && depth < 50 && MultiPV == 1) + if (depth > 4 && multiPV == 1) TimeMgr.pv_instability(BestMoveChanges); // Stop the search if only one legal move is available or all @@ -560,7 +541,9 @@ namespace { } else { - eval = ss->staticEval = evaluate(pos); + eval = ss->staticEval = + (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) : -(ss-1)->staticEval + 2 * Eval::Tempo; + TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval); } @@ -568,6 +551,7 @@ namespace { && ss->staticEval != VALUE_NONE && (ss-1)->staticEval != VALUE_NONE && (move = (ss-1)->currentMove) != MOVE_NULL + && move != MOVE_NONE && type_of(move) == NORMAL) { Square to = to_sq(move); @@ -579,7 +563,6 @@ namespace { && depth < 4 * ONE_PLY && eval + razor_margin(depth) <= alpha && ttMove == MOVE_NONE - && abs(beta) < VALUE_MATE_IN_MAX_PLY && !pos.pawn_on_7th(pos.side_to_move())) { if ( depth <= ONE_PLY @@ -607,7 +590,6 @@ namespace { && !ss->skipNullMove && depth >= 2 * ONE_PLY && eval >= beta - && abs(beta) < VALUE_MATE_IN_MAX_PLY && pos.non_pawn_material(pos.side_to_move())) { ss->currentMove = MOVE_NULL; @@ -617,7 +599,8 @@ namespace { // Null move dynamic reduction based on depth and value Depth R = 3 * ONE_PLY + depth / 4 - + int(eval - beta) / PawnValueMg * ONE_PLY; + + (abs(beta) < VALUE_KNOWN_WIN ? int(eval - beta) / PawnValueMg * ONE_PLY + : DEPTH_ZERO); pos.do_null_move(st); (ss+1)->skipNullMove = true; @@ -632,7 +615,7 @@ namespace { if (nullValue >= VALUE_MATE_IN_MAX_PLY) nullValue = beta; - if (depth < 12 * ONE_PLY) + if (depth < 12 * ONE_PLY && abs(beta) < VALUE_KNOWN_WIN) return nullValue; // Do verification search at high depths @@ -712,7 +695,10 @@ moves_loop: // When in check and at SpNode search starts from here singularExtensionNode = !RootNode && !SpNode && depth >= 8 * ONE_PLY + && abs(beta) < VALUE_KNOWN_WIN && ttMove != MOVE_NONE + /* && ttValue != VALUE_NONE Already implicit in the next condition */ + && abs(ttValue) < VALUE_KNOWN_WIN && !excludedMove // Recursive singular search is not allowed && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3 * ONE_PLY; @@ -777,11 +763,8 @@ moves_loop: // When in check and at SpNode search starts from here if ( singularExtensionNode && move == ttMove && !ext - && pos.legal(move, ci.pinned) - && abs(ttValue) < VALUE_KNOWN_WIN) + && pos.legal(move, ci.pinned)) { - assert(ttValue != VALUE_NONE); - Value rBeta = ttValue - int(depth); ss->excludedMove = move; ss->skipNullMove = true; @@ -881,6 +864,13 @@ moves_loop: // When in check and at SpNode search starts from here if (move == countermoves[0] || move == countermoves[1]) ss->reduction = std::max(DEPTH_ZERO, ss->reduction - ONE_PLY); + // Decrease reduction for moves that escape a capture + if ( ss->reduction + && type_of(move) == NORMAL + && type_of(pos.piece_on(to_sq(move))) != PAWN + && pos.see(make_move(to_sq(move), from_sq(move))) < 0) + ss->reduction = std::max(DEPTH_ZERO, ss->reduction - ONE_PLY); + Depth d = std::max(newDepth - ss->reduction, ONE_PLY); if (SpNode) alpha = splitPoint->alpha; @@ -994,8 +984,8 @@ moves_loop: // When in check and at SpNode search starts from here { assert(bestValue > -VALUE_INFINITE && bestValue < beta); - thisThread->split(pos, ss, alpha, beta, &bestValue, &bestMove, - depth, moveCount, &mp, NT, cutNode); + thisThread->split(pos, ss, alpha, beta, &bestValue, &bestMove, + depth, moveCount, &mp, NT, cutNode); if (Signals.stop || thisThread->cutoff_occurred()) return VALUE_ZERO; @@ -1116,7 +1106,8 @@ moves_loop: // When in check and at SpNode search starts from here bestValue = ttValue; } else - ss->staticEval = bestValue = evaluate(pos); + ss->staticEval = bestValue = + (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) : -(ss-1)->staticEval + 2 * Eval::Tempo; // Stand pat. Return immediately if static value is at least beta if (bestValue >= beta) @@ -1301,8 +1292,8 @@ moves_loop: // When in check and at SpNode search starts from here } - // When playing with a strength handicap, choose best move among the MultiPV - // set using a statistical rule dependent on 'level'. Idea by Heinz van Saanen. + // When playing with a strength handicap, choose best move among the first 'candidates' + // RootMoves using a statistical rule dependent on 'level'. Idea by Heinz van Saanen. Move Skill::pick_move() { @@ -1313,7 +1304,7 @@ moves_loop: // When in check and at SpNode search starts from here rk.rand(); // RootMoves are already sorted by score in descending order - int variance = std::min(RootMoves[0].score - RootMoves[MultiPV - 1].score, PawnValueMg); + int variance = std::min(RootMoves[0].score - RootMoves[candidates - 1].score, PawnValueMg); int weakness = 120 - 2 * level; int max_s = -VALUE_INFINITE; best = MOVE_NONE; @@ -1321,12 +1312,12 @@ moves_loop: // When in check and at SpNode search starts from here // Choose best move. For each move score we add two terms both dependent on // weakness. One deterministic and bigger for weaker moves, and one random, // then we choose the move with the resulting highest score. - for (size_t i = 0; i < MultiPV; ++i) + for (size_t i = 0; i < candidates; ++i) { int s = RootMoves[i].score; // Don't allow crazy blunders even at very low skills - if (i > 0 && RootMoves[i-1].score > s + 2 * PawnValueMg) + if (i > 0 && RootMoves[i - 1].score > s + 2 * PawnValueMg) break; // This is our magic formula @@ -1399,8 +1390,8 @@ void RootMove::extract_pv_from_tt(Position& pos) { StateInfo state[MAX_PLY_PLUS_6], *st = state; const TTEntry* tte; - int ply = 0; - Move m = pv[0]; + int ply = 1; // At root ply is 1... + Move m = pv[0]; // ...instead pv[] array starts from 0 Value expectedScore = score; pv.clear(); @@ -1408,9 +1399,9 @@ void RootMove::extract_pv_from_tt(Position& pos) { do { pv.push_back(m); - assert(MoveList(pos).contains(pv[ply])); + assert(MoveList(pos).contains(pv[ply - 1])); - pos.do_move(pv[ply++], *st++); + pos.do_move(pv[ply++ - 1], *st++); tte = TT.probe(pos.key()); expectedScore = -expectedScore; @@ -1419,11 +1410,11 @@ void RootMove::extract_pv_from_tt(Position& pos) { && pos.pseudo_legal(m = tte->move()) // Local copy, TT could change && pos.legal(m, pos.pinned_pieces(pos.side_to_move())) && ply < MAX_PLY - && (!pos.is_draw() || ply < 2)); + && (!pos.is_draw() || ply <= 2)); pv.push_back(MOVE_NONE); // Must be zero-terminating - while (ply) pos.undo_move(pv[--ply]); + while (--ply) pos.undo_move(pv[ply - 1]); } @@ -1435,21 +1426,21 @@ void RootMove::insert_pv_in_tt(Position& pos) { StateInfo state[MAX_PLY_PLUS_6], *st = state; const TTEntry* tte; - int ply = 0; + int idx = 0; // Ply starts from 1, we need to start from 0 do { tte = TT.probe(pos.key()); - if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries - TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], VALUE_NONE); + if (!tte || tte->move() != pv[idx]) // Don't overwrite correct entries + TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[idx], VALUE_NONE); - assert(MoveList(pos).contains(pv[ply])); + assert(MoveList(pos).contains(pv[idx])); - pos.do_move(pv[ply++], *st++); + pos.do_move(pv[idx++], *st++); - } while (pv[ply] != MOVE_NONE); + } while (pv[idx] != MOVE_NONE); - while (ply) pos.undo_move(pv[--ply]); + while (idx) pos.undo_move(pv[--idx]); } @@ -1559,7 +1550,7 @@ void Thread::idle_loop() { if (Threads.size() > 2) for (size_t i = 0; i < Threads.size(); ++i) { - int size = Threads[i]->splitPointsSize; // Local copy + const int size = Threads[i]->splitPointsSize; // Local copy sp = size ? &Threads[i]->splitPoints[size - 1] : NULL; if ( sp