X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=5d753e8ea7be3281332731b0617ecde637c266ee;hp=51c2a27d330a7b12626185d74100b5bbc0bcbc6f;hb=47bcb892af24c35e7757a4e46544cb90a08d2b64;hpb=348f8241041a26cd9458beb8098306099f44a46a diff --git a/src/search.cpp b/src/search.cpp index 51c2a27d..5d753e8e 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -30,7 +30,6 @@ #include "evaluate.h" #include "history.h" #include "misc.h" -#include "move.h" #include "movegen.h" #include "movepick.h" #include "search.h" @@ -39,12 +38,6 @@ #include "tt.h" #include "ucioption.h" -using std::cout; -using std::endl; -using std::string; -using Search::Signals; -using Search::Limits; - namespace Search { volatile SignalsType Signals; @@ -53,6 +46,11 @@ namespace Search { Position RootPosition; } +using std::cout; +using std::endl; +using std::string; +using namespace Search; + namespace { // Set to true to force running with one thread. Used for debugging @@ -97,8 +95,6 @@ namespace { const bool Slidings[18] = { 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1 }; inline bool piece_is_slider(Piece p) { return Slidings[p]; } - // Step 6. Razoring - // Maximum depth for razoring const Depth RazorDepth = 4 * ONE_PLY; @@ -108,8 +104,6 @@ namespace { // Maximum depth for use of dynamic threat detection when null move fails low const Depth ThreatDepth = 5 * ONE_PLY; - // Step 9. Internal iterative deepening - // Minimum depth for use of internal iterative deepening const Depth IIDDepth[] = { 8 * ONE_PLY, 5 * ONE_PLY }; @@ -117,19 +111,9 @@ namespace { // when the static evaluation is bigger then beta - IIDMargin. const Value IIDMargin = Value(0x100); - // Step 11. Decide the new search depth - - // Extensions. Array index 0 is used for non-PV nodes, index 1 for PV nodes - const Depth CheckExtension[] = { ONE_PLY / 2, ONE_PLY / 1 }; - const Depth PawnEndgameExtension[] = { ONE_PLY / 1, ONE_PLY / 1 }; - const Depth PawnPushTo7thExtension[] = { ONE_PLY / 2, ONE_PLY / 2 }; - const Depth PassedPawnExtension[] = { DEPTH_ZERO, ONE_PLY / 2 }; - // Minimum depth for use of singular extension const Depth SingularExtensionDepth[] = { 8 * ONE_PLY, 6 * ONE_PLY }; - // Step 12. Futility pruning - // Futility margin for quiescence search const Value FutilityMarginQS = Value(0x80); @@ -148,8 +132,6 @@ namespace { return d < 16 * ONE_PLY ? FutilityMoveCounts[d] : MAX_MOVES; } - // Step 14. Reduced search - // Reduction lookup tables (initialized at startup) and their access function int8_t Reductions[2][64][64]; // [pv][depth][moveNumber] @@ -169,7 +151,7 @@ namespace { RootMoveList Rml; // MultiPV mode - int MultiPV, UCIMultiPV, MultiPVIdx; + size_t MultiPV, UCIMultiPV, MultiPVIdx; // Time management variables TimeManager TimeMgr; @@ -187,10 +169,10 @@ namespace { Move id_loop(Position& pos, Move rootMoves[], Move* ponderMove); template - Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth); + Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); template - Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth); + Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue); bool connected_moves(const Position& pos, Move m1, Move m2); @@ -214,14 +196,14 @@ namespace { // we simply create and use a standard MovePicker object. template struct MovePickerExt : public MovePicker { - MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) + MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, Stack* ss, Value b) : MovePicker(p, ttm, d, h, ss, b) {} }; // In case of a SpNode we use split point's shared MovePicker object as moves source template<> struct MovePickerExt : public MovePicker { - MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) + MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, Stack* ss, Value b) : MovePicker(p, ttm, d, h, ss, b), mp(ss->sp->mp) {} Move get_next_move() { return mp->get_next_move(); } @@ -250,49 +232,28 @@ namespace { return os; } - // extension() decides whether a move should be searched with normal depth, - // or with extended depth. Certain classes of moves (checking moves, in - // particular) are searched with bigger depth than ordinary moves and in - // any case are marked as 'dangerous'. Note that also if a move is not - // extended, as example because the corresponding UCI option is set to zero, - // the move is marked as 'dangerous' so, at least, we avoid to prune it. - template - FORCE_INLINE Depth extension(const Position& pos, Move m, bool captureOrPromotion, - bool moveIsCheck, bool* dangerous) { - assert(m != MOVE_NONE); - - Depth result = DEPTH_ZERO; - *dangerous = moveIsCheck; - - if (moveIsCheck && pos.see_sign(m) >= 0) - result += CheckExtension[PvNode]; + // is_dangerous() checks whether a move belongs to some classes of known + // 'dangerous' moves so that we avoid to prune it. + FORCE_INLINE bool is_dangerous(const Position& pos, Move m, bool captureOrPromotion) { + // Test for a pawn pushed to 7th or a passed pawn move if (type_of(pos.piece_on(move_from(m))) == PAWN) { Color c = pos.side_to_move(); - if (relative_rank(c, move_to(m)) == RANK_7) - { - result += PawnPushTo7thExtension[PvNode]; - *dangerous = true; - } - if (pos.pawn_is_passed(c, move_to(m))) - { - result += PassedPawnExtension[PvNode]; - *dangerous = true; - } + if ( relative_rank(c, move_to(m)) == RANK_7 + || pos.pawn_is_passed(c, move_to(m))) + return true; } + // Test for a capture that triggers a pawn endgame if ( captureOrPromotion && type_of(pos.piece_on(move_to(m))) != PAWN && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) - PieceValueMidgame[pos.piece_on(move_to(m))] == VALUE_ZERO) && !is_special(m)) - { - result += PawnEndgameExtension[PvNode]; - *dangerous = true; - } + return true; - return std::min(result, ONE_PLY); + return false; } } // namespace @@ -353,10 +314,9 @@ int64_t Search::perft(Position& pos, Depth depth) { } -/// think() is the external interface to Stockfish's search, and is called when -/// the program receives the UCI 'go' command. It initializes various global -/// variables, and calls id_loop(). It returns false when a "quit" command is -/// received during the search. +/// think() is the external interface to Stockfish's search, and is called by the +/// main thread when the program receives the UCI 'go' command. It searches from +/// RootPosition and at the end prints the "bestmove" to output. void Search::think() { @@ -400,13 +360,13 @@ void Search::think() { TT.clear(); } - UCIMultiPV = Options["MultiPV"].value(); - SkillLevel = Options["Skill Level"].value(); + UCIMultiPV = Options["MultiPV"].value(); + SkillLevel = Options["Skill Level"].value(); // Do we have to play with skill handicap? In this case enable MultiPV that // we will use behind the scenes to retrieve a set of possible moves. SkillLevelEnabled = (SkillLevel < 20); - MultiPV = (SkillLevelEnabled ? std::max(UCIMultiPV, 4) : UCIMultiPV); + MultiPV = (SkillLevelEnabled ? std::max(UCIMultiPV, (size_t)4) : UCIMultiPV); // Write current search header to log file if (Options["Use Search Log"].value()) @@ -489,7 +449,7 @@ namespace { Move id_loop(Position& pos, Move rootMoves[], Move* ponderMove) { - SearchStack ss[PLY_MAX_PLUS_2]; + Stack ss[PLY_MAX_PLUS_2]; Value bestValues[PLY_MAX_PLUS_2]; int bestMoveChanges[PLY_MAX_PLUS_2]; int depth, aspirationDelta; @@ -498,7 +458,7 @@ namespace { bool bestMoveNeverChanged = true; // Initialize stuff before a new search - memset(ss, 0, 4 * sizeof(SearchStack)); + memset(ss, 0, 4 * sizeof(Stack)); TT.new_search(); H.clear(); *ponderMove = bestMove = skillBest = skillPonder = MOVE_NONE; @@ -510,7 +470,7 @@ namespace { Rml.init(pos, rootMoves); // Handle special case of searching on a mate/stalemate position - if (!Rml.size()) + if (Rml.empty()) { cout << "info" << depth_to_uci(DEPTH_ZERO) << score_to_uci(pos.in_check() ? -VALUE_MATE : VALUE_DRAW, alpha, beta) << endl; @@ -528,7 +488,7 @@ namespace { Rml.bestMoveChanges = 0; // MultiPV loop. We perform a full root search for each PV line - for (MultiPVIdx = 0; MultiPVIdx < std::min(MultiPV, (int)Rml.size()); MultiPVIdx++) + for (MultiPVIdx = 0; MultiPVIdx < std::min(MultiPV, Rml.size()); MultiPVIdx++) { // Calculate dynamic aspiration window based on previous iterations if (depth >= 5 && abs(Rml[MultiPVIdx].prevScore) < VALUE_KNOWN_WIN) @@ -572,7 +532,7 @@ namespace { // Write PV back to transposition table in case the relevant entries // have been overwritten during the search. - for (int i = 0; i <= MultiPVIdx; i++) + for (size_t i = 0; i <= MultiPVIdx; i++) Rml[i].insert_pv_in_tt(pos); // If search has been stopped exit the aspiration window loop, @@ -586,7 +546,7 @@ namespace { // protocol requires to send all the PV lines also if are still // to be searched and so refer to the previous search's score. if ((bestValue > alpha && bestValue < beta) || elapsed_time() > 2000) - for (int i = 0; i < std::min(UCIMultiPV, (int)Rml.size()); i++) + for (size_t i = 0; i < std::min(UCIMultiPV, Rml.size()); i++) { bool updated = (i <= MultiPVIdx); @@ -710,7 +670,7 @@ namespace { // here: This is taken care of after we return from the split point. template - Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) { + Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV || NT == SplitPointRoot); const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot); @@ -1035,11 +995,17 @@ split_point_start: // At split points actual search starts from here } isPvMove = (PvNode && moveCount <= 1); - givesCheck = pos.move_gives_check(move, ci); captureOrPromotion = pos.is_capture_or_promotion(move); + givesCheck = pos.move_gives_check(move, ci); + dangerous = givesCheck || is_dangerous(pos, move, captureOrPromotion); + ext = DEPTH_ZERO; + + // Step 12. Extend checks and, in PV nodes, also dangerous moves + if (PvNode && dangerous) + ext = ONE_PLY; - // Step 12. Decide the new search depth - ext = extension(pos, move, captureOrPromotion, givesCheck, &dangerous); + else if (givesCheck && pos.see_sign(move) >= 0) + ext = PvNode ? ONE_PLY : ONE_PLY / 2; // Singular extension search. If all moves but one fail low on a search of // (alpha-s, beta-s), and just one fails high on (alpha, beta), then that move @@ -1047,9 +1013,9 @@ split_point_start: // At split points actual search starts from here // on all the other moves but the ttMove, if result is lower than ttValue minus // a margin then we extend ttMove. if ( singularExtensionNode + && !ext && move == ttMove - && pos.pl_move_is_legal(move, ci.pinned) - && ext < ONE_PLY) + && pos.pl_move_is_legal(move, ci.pinned)) { Value ttValue = value_from_tt(tte->value(), ss->ply); @@ -1299,7 +1265,7 @@ split_point_start: // At split points actual search starts from here // less than ONE_PLY). template - Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) { + Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { const bool PvNode = (NT == PV); @@ -1914,8 +1880,8 @@ split_point_start: // At split points actual search starts from here // Rml list is already sorted by score in descending order int s; + size_t size = std::min(MultiPV, Rml.size()); int max_s = -VALUE_INFINITE; - int size = std::min(MultiPV, (int)Rml.size()); int max = Rml[0].score; int var = std::min(max - Rml[size - 1].score, int(PawnValueMidgame)); int wk = 120 - 2 * SkillLevel; @@ -1927,7 +1893,7 @@ split_point_start: // At split points actual search starts from here // Choose best move. For each move's score we add two terms both dependent // on wk, one deterministic and bigger for weaker moves, and one random, // then we choose the move with the resulting highest score. - for (int i = 0; i < size; i++) + for (size_t i = 0; i < size; i++) { s = Rml[i].score; @@ -2103,11 +2069,11 @@ void Thread::idle_loop(SplitPoint* sp) { assert(!do_terminate); // Copy split point position and search stack and call search() - SearchStack ss[PLY_MAX_PLUS_2]; + Stack ss[PLY_MAX_PLUS_2]; SplitPoint* tsp = splitPoint; Position pos(*tsp->pos, threadID); - memcpy(ss, tsp->ss - 1, 4 * sizeof(SearchStack)); + memcpy(ss, tsp->ss - 1, 4 * sizeof(Stack)); (ss+1)->sp = tsp; if (tsp->nodeType == Root)