X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=eb9f63f15bca317f4fa148bf304472f7eb204edf;hp=9d29d2798737b81f76d8fa64ad130b97eac54ebd;hb=04ac1bcabefaa5b6895b8c20c3c6e3ba7e3a5a61;hpb=f80c50bcddfd02c1b93dcde067d6a7362dda53a2 diff --git a/src/search.cpp b/src/search.cpp index 9d29d279..eb9f63f1 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -24,7 +24,6 @@ #include #include #include -#include #include "book.h" #include "evaluate.h" @@ -42,7 +41,7 @@ namespace Search { volatile SignalsType Signals; LimitsType Limits; - std::vector SearchMoves; + std::vector RootMoves; Position RootPosition; } @@ -59,33 +58,6 @@ namespace { // Different node types, used as template parameter enum NodeType { Root, PV, NonPV, SplitPointRoot, SplitPointPV, SplitPointNonPV }; - // RootMove struct is used for moves at the root of the tree. For each root - // move we store a score, a node count, and a PV (really a refutation in the - // case of moves which fail low). Score is normally set at -VALUE_INFINITE for - // all non-pv moves. - struct RootMove { - - RootMove(){} - RootMove(Move m) { - score = prevScore = -VALUE_INFINITE; - pv.push_back(m); - pv.push_back(MOVE_NONE); - } - - bool operator<(const RootMove& m) const { return score < m.score; } - bool operator==(const Move& m) const { return pv[0] == m; } - - void extract_pv_from_tt(Position& pos); - void insert_pv_in_tt(Position& pos); - - Value score; - Value prevScore; - std::vector pv; - }; - - - /// Constants - // Lookup table to check if a Piece is a slider and its access function 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]; } @@ -135,17 +107,14 @@ namespace { return (Depth) Reductions[PvNode][std::min(int(d) / ONE_PLY, 63)][std::min(mn, 63)]; } - // Easy move margin. An easy move candidate must be at least this much - // better than the second best move. + // Easy move margin. An easy move candidate must be at least this much better + // than the second best move. const Value EasyMoveMargin = Value(0x150); // This is the minimum interval in msec between two check_time() calls const int TimerResolution = 5; - /// Namespace variables - - std::vector RootMoves; size_t MultiPV, UCIMultiPV, PVIdx; TimeManager TimeMgr; int BestMoveChanges; @@ -154,8 +123,6 @@ namespace { History H; - /// Local functions - template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); @@ -200,7 +167,7 @@ namespace { 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(from_sq(m))) == PAWN) + if (type_of(pos.piece_moved(m)) == PAWN) { Color c = pos.side_to_move(); if ( relative_rank(c, to_sq(m)) == RANK_7 @@ -288,13 +255,15 @@ void Search::think() { TimeMgr.init(Limits, pos.startpos_ply_counter()); TT.new_search(); H.clear(); - RootMoves.clear(); - // Populate RootMoves with all the legal moves (default) or, if a SearchMoves - // is given, with the subset of legal moves to search. - for (MoveList ml(pos); !ml.end(); ++ml) - if (SearchMoves.empty() || count(SearchMoves.begin(), SearchMoves.end(), ml.move())) - RootMoves.push_back(RootMove(ml.move())); + if (RootMoves.empty()) + { + cout << "info depth 0 score " + << score_to_uci(pos.in_check() ? -VALUE_MATE : VALUE_DRAW) << endl; + + RootMoves.push_back(MOVE_NONE); + goto finalize; + } if (Options["OwnBook"]) { @@ -375,9 +344,9 @@ void Search::think() { finalize: - // When we reach max depth we arrive here even without a StopRequest, but if - // we are pondering or in infinite search, we shouldn't print the best move - // before we are told to do so. + // When we reach max depth we arrive here even without Signals.stop is raised, + // but if we are pondering or in infinite search, we shouldn't print the best + // move before we are told to do so. if (!Signals.stop && (Limits.ponder || Limits.infinite)) Threads.wait_for_stop_or_ponderhit(); @@ -406,16 +375,6 @@ namespace { bestValue = delta = -VALUE_INFINITE; ss->currentMove = MOVE_NULL; // Hack to skip update gains - // Handle the special case of a mated/stalemate position - if (RootMoves.empty()) - { - cout << "info depth 0 score " - << score_to_uci(pos.in_check() ? -VALUE_MATE : VALUE_DRAW) << endl; - - RootMoves.push_back(MOVE_NONE); - return; - } - // Iterative deepening loop until requested to stop or target depth reached while (!Signals.stop && ++depth <= MAX_PLY && (!Limits.maxDepth || depth <= Limits.maxDepth)) { @@ -531,15 +490,15 @@ namespace { stop = true; // Stop search early if one move seems to be much better than others - if ( depth >= 10 + if ( depth >= 12 && !stop - && ( bestMoveNeverChanged + && ( (bestMoveNeverChanged && pos.captured_piece_type()) || elapsed_time() > (TimeMgr.available_time() * 40) / 100)) { Value rBeta = bestValue - EasyMoveMargin; (ss+1)->excludedMove = RootMoves[0].pv[0]; (ss+1)->skipNullMove = true; - Value v = search(pos, ss+1, rBeta - 1, rBeta, (depth * ONE_PLY) / 2); + Value v = search(pos, ss+1, rBeta - 1, rBeta, (depth - 3) * ONE_PLY); (ss+1)->skipNullMove = false; (ss+1)->excludedMove = MOVE_NONE; @@ -585,7 +544,7 @@ namespace { const bool RootNode = (NT == Root || NT == SplitPointRoot); assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE); - assert(PvNode == (alpha != beta - 1)); + assert((alpha == beta - 1) || PvNode); assert(depth > DEPTH_ZERO); assert(pos.thread() >= 0 && pos.thread() < Threads.size()); @@ -630,6 +589,10 @@ namespace { } // Step 2. Check for aborted search and immediate draw + // Enforce node limit here. FIXME: This only works with 1 search thread. + if (Limits.maxNodes && pos.nodes_searched() >= Limits.maxNodes) + Signals.stop = true; + if (( Signals.stop || pos.is_draw() || ss->ply > MAX_PLY) && !RootNode) @@ -701,7 +664,7 @@ namespace { if ( (move = (ss-1)->currentMove) != MOVE_NULL && (ss-1)->eval != VALUE_NONE && ss->eval != VALUE_NONE - && pos.captured_piece_type() == NO_PIECE_TYPE + && !pos.captured_piece_type() && !is_special(move)) { Square to = to_sq(move); @@ -812,6 +775,7 @@ namespace { Depth rdepth = depth - ONE_PLY - 3 * ONE_PLY; assert(rdepth >= ONE_PLY); + assert((ss-1)->currentMove != MOVE_NONE); MovePicker mp(pos, ttMove, H, pos.captured_piece_type()); CheckInfo ci(pos); @@ -819,6 +783,7 @@ namespace { while ((move = mp.next_move()) != MOVE_NONE) if (pos.pl_move_is_legal(move, ci.pinned)) { + ss->currentMove = move; pos.do_move(move, st, ci, pos.move_gives_check(move, ci)); value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth); pos.undo_move(move); @@ -970,7 +935,7 @@ split_point_start: // At split points actual search starts from here // but fixing this made program slightly weaker. Depth predictedDepth = newDepth - reduction(depth, moveCount); futilityValue = futilityBase + futility_margin(predictedDepth, moveCount) - + H.gain(pos.piece_on(from_sq(move)), to_sq(move)); + + H.gain(pos.piece_moved(move), to_sq(move)); if (futilityValue < beta) { @@ -1007,7 +972,7 @@ split_point_start: // At split points actual search starts from here // Step 15. Reduced depth search (LMR). If the move fails high will be // re-searched at full depth. - if ( depth > 3 * ONE_PLY + if ( depth > 4 * ONE_PLY && !isPvMove && !captureOrPromotion && !dangerous @@ -1016,11 +981,10 @@ split_point_start: // At split points actual search starts from here && ss->killers[1] != move) { ss->reduction = reduction(depth, moveCount); - Depth d = newDepth - ss->reduction; + Depth d = std::max(newDepth - ss->reduction, ONE_PLY); alpha = SpNode ? sp->alpha : alpha; - value = d < ONE_PLY ? -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) - : - search(pos, ss+1, -(alpha+1), -alpha, d); + value = -search(pos, ss+1, -(alpha+1), -alpha, d); doFullDepthSearch = (value > alpha && ss->reduction != DEPTH_ZERO); ss->reduction = DEPTH_ZERO; @@ -1056,7 +1020,7 @@ split_point_start: // At split points actual search starts from here alpha = sp->alpha; } - // Finished searching the move. If StopRequest is true, the search + // Finished searching the move. If Signals.stop is true, the search // 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 don't update the best move and/or PV. @@ -1117,7 +1081,7 @@ split_point_start: // At split points actual search starts from here // Step 20. Check for mate and stalemate // All legal moves have been searched and if there are no legal moves, it // must be mate or stalemate. Note that we can have a false positive in - // case of StopRequest or thread.cutoff_occurred() are set, but this is + // case of Signals.stop or thread.cutoff_occurred() are set, but this is // harmless because return value is discarded anyhow in the parent nodes. // If we are in a singular extension search then return a fail low score. if (!moveCount) @@ -1154,13 +1118,13 @@ split_point_start: // At split points actual search starts from here // Increase history value of the cut-off move Value bonus = Value(int(depth) * int(depth)); - H.add(pos.piece_on(from_sq(move)), to_sq(move), bonus); + H.add(pos.piece_moved(move), to_sq(move), bonus); // Decrease history of all the other played non-capture moves for (int i = 0; i < playedMoveCount - 1; i++) { Move m = movesSearched[i]; - H.add(pos.piece_on(from_sq(m)), to_sq(m), -bonus); + H.add(pos.piece_moved(m), to_sq(m), -bonus); } } } @@ -1190,7 +1154,7 @@ split_point_start: // At split points actual search starts from here assert(NT == PV || NT == NonPV); assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE); - assert(PvNode == (alpha != beta - 1)); + assert((alpha == beta - 1) || PvNode); assert(depth <= DEPTH_ZERO); assert(pos.thread() >= 0 && pos.thread() < Threads.size()); @@ -1393,7 +1357,7 @@ split_point_start: // At split points actual search starts from here from = from_sq(move); to = to_sq(move); - them = flip(pos.side_to_move()); + them = ~pos.side_to_move(); ksq = pos.king_square(them); kingAtt = pos.attacks_from(ksq); pc = pos.piece_on(from); @@ -1801,74 +1765,74 @@ split_point_start: // At split points actual search starts from here return best; } +} // namespace - // extract_pv_from_tt() builds a PV by adding moves from the transposition table. - // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This - // allow to always have a ponder move even when we fail high at root and also a - // long PV to print that is important for position analysis. - void RootMove::extract_pv_from_tt(Position& pos) { +/// RootMove::extract_pv_from_tt() builds a PV by adding moves from the TT table. +/// We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes so +/// to allow to always have a ponder move even when we fail high at root, and +/// a long PV to print that is important for position analysis. - StateInfo state[MAX_PLY_PLUS_2], *st = state; - TTEntry* tte; - int ply = 1; - Move m = pv[0]; - - assert(m != MOVE_NONE && pos.is_pseudo_legal(m)); - - pv.clear(); - pv.push_back(m); - pos.do_move(m, *st++); - - while ( (tte = TT.probe(pos.key())) != NULL - && tte->move() != MOVE_NONE - && pos.is_pseudo_legal(tte->move()) - && pos.pl_move_is_legal(tte->move(), pos.pinned_pieces()) - && ply < MAX_PLY - && (!pos.is_draw() || ply < 2)) - { - pv.push_back(tte->move()); - pos.do_move(tte->move(), *st++); - ply++; - } - pv.push_back(MOVE_NONE); +void RootMove::extract_pv_from_tt(Position& pos) { - do pos.undo_move(pv[--ply]); while (ply); + StateInfo state[MAX_PLY_PLUS_2], *st = state; + TTEntry* tte; + int ply = 1; + Move m = pv[0]; + + assert(m != MOVE_NONE && pos.is_pseudo_legal(m)); + + pv.clear(); + pv.push_back(m); + pos.do_move(m, *st++); + + while ( (tte = TT.probe(pos.key())) != NULL + && tte->move() != MOVE_NONE + && pos.is_pseudo_legal(tte->move()) + && pos.pl_move_is_legal(tte->move(), pos.pinned_pieces()) + && ply < MAX_PLY + && (!pos.is_draw() || ply < 2)) + { + pv.push_back(tte->move()); + pos.do_move(tte->move(), *st++); + ply++; } + pv.push_back(MOVE_NONE); + do pos.undo_move(pv[--ply]); while (ply); +} - // insert_pv_in_tt() is called at the end of a search iteration, and inserts - // the PV back into the TT. This makes sure the old PV moves are searched - // first, even if the old TT entries have been overwritten. - void RootMove::insert_pv_in_tt(Position& pos) { +/// RootMove::insert_pv_in_tt() is called at the end of a search iteration, and +/// inserts the PV back into the TT. This makes sure the old PV moves are searched +/// first, even if the old TT entries have been overwritten. - StateInfo state[MAX_PLY_PLUS_2], *st = state; - TTEntry* tte; - Key k; - Value v, m = VALUE_NONE; - int ply = 0; +void RootMove::insert_pv_in_tt(Position& pos) { - assert(pv[ply] != MOVE_NONE && pos.is_pseudo_legal(pv[ply])); + StateInfo state[MAX_PLY_PLUS_2], *st = state; + TTEntry* tte; + Key k; + Value v, m = VALUE_NONE; + int ply = 0; - do { - k = pos.key(); - tte = TT.probe(k); + assert(pv[ply] != MOVE_NONE && pos.is_pseudo_legal(pv[ply])); - // Don't overwrite existing correct entries - if (!tte || tte->move() != pv[ply]) - { - v = (pos.in_check() ? VALUE_NONE : evaluate(pos, m)); - TT.store(k, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[ply], v, m); - } - pos.do_move(pv[ply], *st++); + do { + k = pos.key(); + tte = TT.probe(k); - } while (pv[++ply] != MOVE_NONE); + // Don't overwrite existing correct entries + if (!tte || tte->move() != pv[ply]) + { + v = (pos.in_check() ? VALUE_NONE : evaluate(pos, m)); + TT.store(k, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[ply], v, m); + } + pos.do_move(pv[ply], *st++); - do pos.undo_move(pv[--ply]); while (ply); - } + } while (pv[++ply] != MOVE_NONE); -} // namespace + do pos.undo_move(pv[--ply]); while (ply); +} /// Thread::idle_loop() is where the thread is parked when it has no work to do. @@ -1983,11 +1947,10 @@ void check_time() { && !Signals.failedLowAtRoot && e > TimeMgr.available_time(); - bool noMoreTime = e > TimeMgr.maximum_time() - TimerResolution + bool noMoreTime = e > TimeMgr.maximum_time() - 2 * TimerResolution || stillAtFirstMove; if ( (Limits.use_time_management() && noMoreTime) - || (Limits.maxTime && e >= Limits.maxTime) - /* missing nodes limit */ ) // FIXME + || (Limits.maxTime && e >= Limits.maxTime)) Signals.stop = true; }