X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=81f96ccdc74162d7ac63e1b37eece83b23ad9a60;hp=b9fdcea119a51b4761ebf94c3a2eacdc250991ff;hb=351ef5c85b6d4b9c71e9da367f0be5ab6e6f8117;hpb=181cc3f93feb00fbf00febadf7e63323e828ebe5 diff --git a/src/search.cpp b/src/search.cpp index b9fdcea1..81f96ccd 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -72,8 +72,7 @@ namespace { void extract_pv_from_tt(Position& pos); void insert_pv_in_tt(Position& pos); - std::string pv_info_to_uci(Position& pos, int depth, int selDepth, - Value alpha, Value beta, int pvIdx); + int64_t nodes; Value pv_score; Value non_pv_score; @@ -88,48 +87,11 @@ namespace { void init(Position& pos, Move searchMoves[]); void sort() { insertion_sort(begin(), end()); } - void sort_multipv(int n) { insertion_sort(begin(), begin() + n); } + void sort_first(int n) { insertion_sort(begin(), begin() + n); } int bestMoveChanges; }; - // MovePickerExt template class extends MovePicker and allows to choose at compile - // time the proper moves source according to the type of node. In the default case - // 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) - : MovePicker(p, ttm, d, h, ss, b) {} - - RootMoveList::iterator rm; // Dummy, needed to compile - }; - - // In case of a SpNode we use split point's shared MovePicker object as moves source - template<> struct MovePickerExt : public MovePickerExt { - - MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) - : MovePickerExt(p, ttm, d, h, ss, b), mp(ss->sp->mp) {} - - Move get_next_move() { return mp->get_next_move(); } - MovePicker* mp; - }; - - template<> struct MovePickerExt : public MovePickerExt { - - MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) - : MovePickerExt(p, ttm, d, h, ss, b) {} - }; - - // In case of a Root node we use RootMoveList as moves source - template<> struct MovePickerExt : public MovePicker { - - MovePickerExt(const Position&, Move, Depth, const History&, SearchStack*, Value); - Move get_next_move(); - - RootMoveList::iterator rm; - bool firstCall; - }; - /// Constants @@ -255,11 +217,50 @@ namespace { void do_skill_level(Move* best, Move* ponder); int current_search_time(int set = 0); - std::string value_to_uci(Value v); + std::string score_to_uci(Value v, Value alpha, Value beta); std::string speed_to_uci(int64_t nodes); + std::string pv_to_uci(Move pv[], int pvNum); + std::string depth_to_uci(Depth depth); void poll(const Position& pos); void wait_for_stop_or_ponderhit(); + // MovePickerExt template class extends MovePicker and allows to choose at compile + // time the proper moves source according to the type of node. In the default case + // 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) + : MovePicker(p, ttm, d, h, ss, b) {} + + RootMove& current() { assert(false); return Rml[0]; } // Dummy, needed to compile + }; + + // In case of a SpNode we use split point's shared MovePicker object as moves source + template<> struct MovePickerExt : public MovePickerExt { + + MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) + : MovePickerExt(p, ttm, d, h, ss, b), mp(ss->sp->mp) {} + + Move get_next_move() { return mp->get_next_move(); } + MovePicker* mp; + }; + + template<> struct MovePickerExt : public MovePickerExt { + + MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) + : MovePickerExt(p, ttm, d, h, ss, b) {} + }; + + // In case of a Root node we use RootMoveList as moves source + template<> struct MovePickerExt : public MovePicker { + + MovePickerExt(const Position&, Move, Depth, const History&, SearchStack*, Value); + RootMove& current() { return Rml[cur]; } + Move get_next_move() { return ++cur < (int)Rml.size() ? Rml[cur].pv[0] : MOVE_NONE; } + + int cur; + }; + // Overload operator<<() to make it easier to print moves in a coordinate // notation compatible with UCI protocol. std::ostream& operator<<(std::ostream& os, Move m) { @@ -317,7 +318,7 @@ namespace { if ( captureOrPromotion && pos.type_of_piece_on(move_to(m)) != PAWN && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) - - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO) + - piece_value_midgame(pos.piece_on(move_to(m))) == VALUE_ZERO) && !move_is_special(m)) { result += PawnEndgameExtension[PvNode]; @@ -404,6 +405,9 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { Limits = limits; TimeMgr.init(Limits, pos.startpos_ply_counter()); + // Set output steram in normal or chess960 mode + cout << set960(pos.is_chess960()); + // Set best NodesBetweenPolls interval to avoid lagging under time pressure if (Limits.maxNodes) NodesBetweenPolls = Min(Limits.maxNodes, 30000); @@ -480,8 +484,6 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { Move ponderMove = MOVE_NONE; Move bestMove = id_loop(pos, searchMoves, &ponderMove); - cout << "info" << speed_to_uci(pos.nodes_searched()) << endl; - // Write final search statistics and close log file if (LogFile.is_open()) { @@ -531,7 +533,7 @@ namespace { SearchStack ss[PLY_MAX_PLUS_2]; Value bestValues[PLY_MAX_PLUS_2]; int bestMoveChanges[PLY_MAX_PLUS_2]; - int depth, selDepth, aspirationDelta; + int depth, aspirationDelta; Value value, alpha, beta; Move bestMove, easyMove, skillBest, skillPonder; @@ -548,11 +550,10 @@ namespace { Rml.init(pos, searchMoves); // Handle special case of searching on a mate/stalemate position - if (Rml.size() == 0) + if (!Rml.size()) { - cout << "info depth 0 score " - << value_to_uci(pos.in_check() ? -VALUE_MATE : VALUE_DRAW) - << endl; + cout << "info" << depth_to_uci(DEPTH_ZERO) + << score_to_uci(pos.in_check() ? -VALUE_MATE : VALUE_DRAW, alpha, beta) << endl; return MOVE_NONE; } @@ -561,7 +562,6 @@ namespace { while (!StopRequest && ++depth <= PLY_MAX && (!Limits.maxDepth || depth <= Limits.maxDepth)) { Rml.bestMoveChanges = 0; - cout << set960(pos.is_chess960()) << "info depth " << depth << endl; // Calculate dynamic aspiration window based on previous iterations if (MultiPV == 1 && depth >= 5 && abs(bestValues[depth - 1]) < VALUE_KNOWN_WIN) @@ -591,7 +591,15 @@ namespace { if (StopRequest) break; - assert(value >= alpha); + // Send full PV info to GUI if we are going to leave the loop or + // if we have a fail high/low and we are deep in the search. + if ((value > alpha && value < beta) || current_search_time() > 2000) + for (int i = 0; i < Min(UCIMultiPV, (int)Rml.size()); i++) + cout << "info" + << depth_to_uci(depth * ONE_PLY) + << score_to_uci(Rml[i].pv_score, alpha, beta) + << speed_to_uci(pos.nodes_searched()) + << pv_to_uci(Rml[i].pv, i + 1) << endl; // In case of failing high/low increase aspiration window and research, // otherwise exit the fail high/low loop. @@ -623,16 +631,6 @@ namespace { if (SkillLevelEnabled && depth == 1 + SkillLevel) do_skill_level(&skillBest, &skillPonder); - // Retrieve max searched depth among threads - selDepth = 0; - for (int i = 0; i < Threads.size(); i++) - if (Threads[i].maxPly > selDepth) - selDepth = Threads[i].maxPly; - - // Send PV line to GUI and to log file - for (int i = 0; i < Min(UCIMultiPV, (int)Rml.size()); i++) - cout << Rml[i].pv_info_to_uci(pos, depth, selDepth, alpha, beta, i) << endl; - if (LogFile.is_open()) LogFile << pretty_pv(pos, depth, value, current_search_time(), Rml[0].pv) << endl; @@ -719,7 +717,6 @@ namespace { StateInfo st; const TTEntry *tte; Key posKey; - Bitboard pinned; Move ttMove, move, excludedMove, threatMove; Depth ext, newDepth; ValueType vt; @@ -747,8 +744,6 @@ namespace { threatMove = sp->threatMove; goto split_point_start; } - else if (RootNode) - bestValue = alpha; // Step 1. Initialize node and poll. Polling can abort search ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE; @@ -763,15 +758,18 @@ namespace { // Step 2. Check for aborted search and immediate draw if (( StopRequest - || pos.is_draw() + || pos.is_draw() || ss->ply > PLY_MAX) && !RootNode) return VALUE_DRAW; // Step 3. Mate distance pruning - alpha = Max(value_mated_in(ss->ply), alpha); - beta = Min(value_mate_in(ss->ply+1), beta); - if (alpha >= beta) - return alpha; + if (!RootNode) + { + alpha = Max(value_mated_in(ss->ply), alpha); + beta = Min(value_mate_in(ss->ply+1), beta); + if (alpha >= beta) + return alpha; + } // Step 4. Transposition table lookup // We don't want the score of a partial search to overwrite a previous full search @@ -918,13 +916,13 @@ namespace { assert(rdepth >= ONE_PLY); - MovePicker mp(pos, ttMove, H, Position::see_value(pos.captured_piece_type())); - pinned = pos.pinned_pieces(pos.side_to_move()); + MovePicker mp(pos, ttMove, H, pos.captured_piece_type()); + CheckInfo ci(pos); while ((move = mp.get_next_move()) != MOVE_NONE) - if (pos.pl_move_is_legal(move, pinned)) + if (pos.pl_move_is_legal(move, ci.pinned)) { - pos.do_move(move, st); + 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); if (value >= rbeta) @@ -952,7 +950,6 @@ split_point_start: // At split points actual search starts from here // Initialize a MovePicker object for the current position MovePickerExt mp(pos, ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta); CheckInfo ci(pos); - pinned = pos.pinned_pieces(pos.side_to_move()); ss->bestMove = MOVE_NONE; futilityBase = ss->eval + ss->evalMargin; singularExtensionNode = !RootNode @@ -980,7 +977,7 @@ split_point_start: // At split points actual search starts from here continue; // At PV and SpNode nodes we want the moves to be legal - if ((PvNode || SpNode) && !pos.pl_move_is_legal(move, pinned)) + if ((PvNode || SpNode) && !pos.pl_move_is_legal(move, ci.pinned)) continue; if (SpNode) @@ -1007,15 +1004,16 @@ split_point_start: // At split points actual search starts from here cout << "info" << speed_to_uci(pos.nodes_searched()) << endl; } + // For long searches send to GUI current move if (current_search_time() > 2000) - cout << "info currmove " << move - << " currmovenumber " << moveCount << endl; + cout << "info" << depth_to_uci(depth) + << " currmove " << move << " currmovenumber " << moveCount << endl; } // At Root and at first iteration do a PV search on all the moves to score root moves - isPvMove = (PvNode && moveCount <= (RootNode ? depth <= ONE_PLY ? 1000 : MultiPV : 1)); + isPvMove = (PvNode && moveCount <= (RootNode ? depth <= ONE_PLY ? MAX_MOVES : MultiPV : 1)); givesCheck = pos.move_gives_check(move, ci); - captureOrPromotion = pos.move_is_capture(move) || move_is_promotion(move); + captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 12. Decide the new search depth ext = extension(pos, move, captureOrPromotion, givesCheck, &dangerous); @@ -1027,7 +1025,7 @@ split_point_start: // At split points actual search starts from here // a margin then we extend ttMove. if ( singularExtensionNode && move == ttMove - && pos.pl_move_is_legal(move, pinned) + && pos.pl_move_is_legal(move, ci.pinned) && ext < ONE_PLY) { Value ttValue = value_from_tt(tte->value(), ss->ply); @@ -1102,7 +1100,7 @@ split_point_start: // At split points actual search starts from here } // Check for legality only before to do the move - if (!pos.pl_move_is_legal(move, pinned)) + if (!pos.pl_move_is_legal(move, ci.pinned)) { moveCount--; continue; @@ -1119,14 +1117,8 @@ split_point_start: // At split points actual search starts from here // Step extra. pv search (only in PV nodes) // The first move in list is the expected PV if (isPvMove) - { - // Aspiration window is disabled in multi-pv case - if (RootNode && MultiPV > 1) - alpha = -VALUE_INFINITE; - value = newDepth < ONE_PLY ? -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) : - search(pos, ss+1, -beta, -alpha, newDepth); - } else { // Step 15. Reduced depth search @@ -1134,7 +1126,7 @@ split_point_start: // At split points actual search starts from here bool doFullDepthSearch = true; alpha = SpNode ? sp->alpha : alpha; - if ( depth >= 3 * ONE_PLY + if ( depth > 3 * ONE_PLY && !captureOrPromotion && !dangerous && !move_is_castle(move) @@ -1218,15 +1210,15 @@ split_point_start: // At split points actual search starts from here break; // Remember searched nodes counts for this move - mp.rm->nodes += pos.nodes_searched() - nodes; + mp.current().nodes += pos.nodes_searched() - nodes; // PV move or new best move ? if (isPvMove || value > alpha) { // Update PV ss->bestMove = move; - mp.rm->pv_score = value; - mp.rm->extract_pv_from_tt(pos); + mp.current().pv_score = value; + mp.current().extract_pv_from_tt(pos); // We record how often the best move has been changed in each // iteration. This information is used for time management: When @@ -1234,17 +1226,24 @@ split_point_start: // At split points actual search starts from here if (!isPvMove && MultiPV == 1) Rml.bestMoveChanges++; - Rml.sort_multipv(moveCount); + // It is critical that sorting is done with a stable algorithm + // because all the values but the first are usually set to + // -VALUE_INFINITE and we want to keep the same order for all + // the moves but the new PV that goes to head. + Rml.sort_first(moveCount); - // Update alpha. In multi-pv we don't use aspiration window, so - // set alpha equal to minimum score among the PV lines. + // Update alpha. In multi-pv we don't use aspiration window, so set + // alpha equal to minimum score among the PV lines searched so far. if (MultiPV > 1) - alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount? + alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score; else if (value > alpha) alpha = value; } else - mp.rm->pv_score = -VALUE_INFINITE; + // All other moves but the PV are set to the lowest value, this + // is not a problem when sorting becuase sort is stable and move + // position in the list is preserved, just the PV is pushed up. + mp.current().pv_score = -VALUE_INFINITE; } // RootNode @@ -1280,8 +1279,7 @@ split_point_start: // At split points actual search starts from here // Update killers and history only for non capture moves that fails high if ( bestValue >= beta - && !pos.move_is_capture(move) - && !move_is_promotion(move)) + && !pos.move_is_capture_or_promotion(move)) { if (move != ss->killers[0]) { @@ -1333,7 +1331,7 @@ split_point_start: // At split points actual search starts from here ss->ply = (ss-1)->ply + 1; // Check for an instant draw or maximum ply reached - if (ss->ply > PLY_MAX || pos.is_draw()) + if (pos.is_draw() || ss->ply > PLY_MAX) return VALUE_DRAW; // Decide whether or not to include checks, this fixes also the type of @@ -1372,8 +1370,6 @@ split_point_start: // At split points actual search starts from here else ss->eval = bestValue = evaluate(pos, evalMargin); - update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval); - // Stand pat. Return immediately if static value is at least beta if (bestValue >= beta) { @@ -1395,9 +1391,8 @@ split_point_start: // At split points actual search starts from here // to search the moves. Because the depth is <= 0 here, only captures, // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will // be generated. - MovePicker mp(pos, ttMove, depth, H); + MovePicker mp(pos, ttMove, depth, H, move_to((ss-1)->currentMove)); CheckInfo ci(pos); - Bitboard pinned = pos.pinned_pieces(pos.side_to_move()); // Loop through the moves until no moves remain or a beta cutoff occurs while ( alpha < beta @@ -1417,7 +1412,7 @@ split_point_start: // At split points actual search starts from here && !pos.move_is_passed_pawn_push(move)) { futilityValue = futilityBase - + pos.endgame_value_of_piece_on(move_to(move)) + + piece_value_endgame(pos.piece_on(move_to(move))) + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO); if (futilityValue < alpha) @@ -1454,8 +1449,7 @@ split_point_start: // At split points actual search starts from here && !inCheck && givesCheck && move != ttMove - && !pos.move_is_capture(move) - && !move_is_promotion(move) + && !pos.move_is_capture_or_promotion(move) && ss->eval + PawnValueMidgame / 4 < beta && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue)) { @@ -1466,7 +1460,7 @@ split_point_start: // At split points actual search starts from here } // Check for legality only before to do the move - if (!pos.pl_move_is_legal(move, pinned)) + if (!pos.pl_move_is_legal(move, ci.pinned)) continue; // Update current move @@ -1546,7 +1540,7 @@ split_point_start: // At split points actual search starts from here while (b) { victimSq = pop_1st_bit(&b); - futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq); + futilityValue = futilityBase + piece_value_endgame(pos.piece_on(victimSq)); // Note that here we generate illegal "double move"! if ( futilityValue >= beta @@ -1654,8 +1648,7 @@ split_point_start: // At split points actual search starts from here assert(move_is_ok(m)); assert(threat && move_is_ok(threat)); - assert(!pos.move_gives_check(m)); - assert(!pos.move_is_capture(m) && !move_is_promotion(m)); + assert(!pos.move_is_capture_or_promotion(m)); assert(!pos.move_is_passed_pawn_push(m)); Square mfrom, mto, tfrom, tto; @@ -1672,7 +1665,7 @@ split_point_start: // At split points actual search starts from here // Case 2: If the threatened piece has value less than or equal to the // value of the threatening piece, don't prune moves which defend it. if ( pos.move_is_capture(threat) - && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto) + && ( piece_value_midgame(pos.piece_on(tfrom)) >= piece_value_midgame(pos.piece_on(tto)) || pos.type_of_piece_on(tfrom) == KING) && pos.move_attacks_square(m, tto)) return true; @@ -1770,21 +1763,23 @@ split_point_start: // At split points actual search starts from here } - // value_to_uci() converts a value to a string suitable for use with the UCI + // score_to_uci() converts a value to a string suitable for use with the UCI // protocol specifications: // // cp The score from the engine's point of view in centipawns. // mate Mate in y moves, not plies. If the engine is getting mated // use negative values for y. - std::string value_to_uci(Value v) { + std::string score_to_uci(Value v, Value alpha, Value beta) { std::stringstream s; if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY) - s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to centipawns + s << " score cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to centipawns else - s << "mate " << (v > 0 ? VALUE_MATE - v + 1 : -VALUE_MATE - v) / 2; + s << " score mate " << (v > 0 ? VALUE_MATE - v + 1 : -VALUE_MATE - v) / 2; + + s << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : ""); return s.str(); } @@ -1799,12 +1794,45 @@ split_point_start: // At split points actual search starts from here int t = current_search_time(); s << " nodes " << nodes - << " nps " << (t > 0 ? int(nodes * 1000 / t) : 0) + << " nps " << (t > 0 ? int(nodes * 1000 / t) : 0) << " time " << t; return s.str(); } + // pv_to_uci() returns a string with information on the current PV line + // formatted according to UCI specification. + + std::string pv_to_uci(Move pv[], int pvNum) { + + std::stringstream s; + + s << " multipv " << pvNum << " pv "; + + for ( ; *pv != MOVE_NONE; pv++) + s << *pv << " "; + + return s.str(); + } + + // depth_to_uci() returns a string with information on the current depth and + // seldepth formatted according to UCI specification. + + std::string depth_to_uci(Depth depth) { + + std::stringstream s; + + // Retrieve max searched depth among threads + int selDepth = 0; + for (int i = 0; i < Threads.size(); i++) + if (Threads[i].maxPly > selDepth) + selDepth = Threads[i].maxPly; + + s << " depth " << depth / ONE_PLY << " seldepth " << selDepth; + + return s.str(); + } + // poll() performs two different functions: It polls for user input, and it // looks at the time consumed so far and decides if it's time to abort the @@ -2019,7 +2047,7 @@ split_point_start: // At split points actual search starts from here && pos.move_is_pl(tte->move()) && pos.pl_move_is_legal(tte->move(), pos.pinned_pieces(pos.side_to_move())) && ply < PLY_MAX - && (!pos.is_draw() || ply < 2)) + && (!pos.is_draw() || ply < 2)) { pv[ply] = tte->move(); pos.do_move(pv[ply++], *st++); @@ -2060,31 +2088,10 @@ split_point_start: // At split points actual search starts from here do pos.undo_move(pv[--ply]); while (ply); } - // pv_info_to_uci() returns a string with information on the current PV line - // formatted according to UCI specification. - - std::string RootMove::pv_info_to_uci(Position& pos, int depth, int selDepth, Value alpha, - Value beta, int pvIdx) { - std::stringstream s; - - s << "info depth " << depth - << " seldepth " << selDepth - << " multipv " << pvIdx + 1 - << " score " << value_to_uci(pv_score) - << (pv_score >= beta ? " lowerbound" : pv_score <= alpha ? " upperbound" : "") - << speed_to_uci(pos.nodes_searched()) - << " pv "; - - for (Move* m = pv; *m != MOVE_NONE; m++) - s << *m << " "; - - return s.str(); - } - // Specializations for MovePickerExt in case of Root node MovePickerExt::MovePickerExt(const Position& p, Move ttm, Depth d, - const History& h, SearchStack* ss, Value b) - : MovePicker(p, ttm, d, h, ss, b), firstCall(true) { + const History& h, SearchStack* ss, Value b) + : MovePicker(p, ttm, d, h, ss, b), cur(-1) { Move move; Value score = VALUE_ZERO; @@ -2093,7 +2100,7 @@ split_point_start: // At split points actual search starts from here // This is the second order score that is used to compare the moves when // the first orders pv_score of both moves are equal. while ((move = MovePicker::get_next_move()) != MOVE_NONE) - for (rm = Rml.begin(); rm != Rml.end(); ++rm) + for (RootMoveList::iterator rm = Rml.begin(); rm != Rml.end(); ++rm) if (rm->pv[0] == move) { rm->non_pv_score = score--; @@ -2101,17 +2108,6 @@ split_point_start: // At split points actual search starts from here } Rml.sort(); - rm = Rml.begin(); - } - - Move MovePickerExt::get_next_move() { - - if (!firstCall) - ++rm; - else - firstCall = false; - - return rm != Rml.end() ? rm->pv[0] : MOVE_NONE; } } // namespace