X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=061bbafca0cd1a4b7e0885407ce76a68938c1b23;hp=915e1af25d69ccee4e5faead5f68cf58b14ecd96;hb=f5b8db7a1efc4ecaa6e1b385d1579abf5f5840fe;hpb=ce2845d3334520d07e38750ff481212f092a3ceb diff --git a/src/search.cpp b/src/search.cpp index 915e1af2..061bbafc 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -243,7 +243,7 @@ namespace { RootMoveList Rml; // MultiPV mode - int MultiPV; + int MultiPV, UCIMultiPV; // Time management variables int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime; @@ -255,6 +255,10 @@ namespace { bool UseLogFile; std::ofstream LogFile; + // Skill level adjustment + int SkillLevel; + RKISS RK; + // Multi-threads manager object ThreadsManager ThreadsMgr; @@ -296,7 +300,6 @@ namespace { bool connected_threat(const Position& pos, Move m, Move threat); Value refine_eval(const TTEntry* tte, Value defaultEval, int ply); void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount); - void update_killers(Move m, Move killers[]); void update_gains(const Position& pos, Move move, Value before, Value after); int current_search_time(); @@ -503,11 +506,16 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[ PawnEndgameExtension[0] = Options["Pawn Endgame Extension (non-PV nodes)"].value(); MateThreatExtension[1] = Options["Mate Threat Extension (PV nodes)"].value(); MateThreatExtension[0] = Options["Mate Threat Extension (non-PV nodes)"].value(); - MultiPV = Options["MultiPV"].value(); + UCIMultiPV = Options["MultiPV"].value(); + SkillLevel = Options["Skill level"].value(); UseLogFile = Options["Use Search Log"].value(); read_evaluation_uci_options(pos.side_to_move()); + // 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. + MultiPV = (SkillLevel < 20 ? Max(UCIMultiPV, 4) : UCIMultiPV); + // Set the number of active threads ThreadsMgr.read_uci_options(); init_eval(ThreadsMgr.active_threads()); @@ -578,8 +586,15 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[ if (!StopRequest && (Pondering || InfiniteSearch)) wait_for_stop_or_ponderhit(); - // Could be both MOVE_NONE when searching on a stalemate position - cout << "bestmove " << bestMove << " ponder " << ponderMove << endl; + // Could be MOVE_NONE when searching on a stalemate position + cout << "bestmove " << bestMove; + + // UCI protol is not clear on allowing sending an empty ponder move, instead + // it is clear that ponder move is optional. So skip it if empty. + if (ponderMove != MOVE_NONE) + cout << " ponder " << ponderMove; + + cout << endl; return !QuitRequest; } @@ -596,21 +611,21 @@ namespace { SearchStack ss[PLY_MAX_PLUS_2]; Value bestValues[PLY_MAX_PLUS_2]; int bestMoveChanges[PLY_MAX_PLUS_2]; - int depth, researchCountFL, researchCountFH, aspirationDelta; + int depth, aspirationDelta; Value value, alpha, beta; Move bestMove, easyMove; - // Moves to search are verified and copied - Rml.init(pos, searchMoves); - - // Initialize FIXME move before Rml.init() + // Initialize stuff before a new search + memset(ss, 0, 4 * sizeof(SearchStack)); TT.new_search(); H.clear(); - memset(ss, 0, 4 * sizeof(SearchStack)); *ponderMove = bestMove = easyMove = MOVE_NONE; depth = aspirationDelta = 0; - ss->currentMove = MOVE_NULL; // Hack to skip update_gains() alpha = -VALUE_INFINITE, beta = VALUE_INFINITE; + ss->currentMove = MOVE_NULL; // Hack to skip update_gains() + + // Moves to search are verified and copied + Rml.init(pos, searchMoves); // Handle special case of searching on a mate/stalemate position if (Rml.size() == 0) @@ -625,8 +640,8 @@ namespace { // Iterative deepening loop while (++depth <= PLY_MAX && (!MaxDepth || depth <= MaxDepth) && !StopRequest) { - Rml.bestMoveChanges = researchCountFL = researchCountFH = 0; - cout << "info depth " << depth << endl; + 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) @@ -643,19 +658,14 @@ namespace { // Start with a small aspiration window and, in case of fail high/low, // research with bigger window until not failing high/low anymore. - while (true) - { + do { // Search starting from ss+1 to allow calling update_gains() value = search(pos, ss+1, alpha, beta, depth * ONE_PLY, 0); - // Send PV line to GUI and write to transposition table in case the - // relevant entries have been overwritten during the search. + // Write PV back to transposition table in case the relevant entries + // have been overwritten during the search. for (int i = 0; i < Min(MultiPV, (int)Rml.size()); i++) - { Rml[i].insert_pv_in_tt(pos); - cout << set960(pos.is_chess960()) - << Rml[i].pv_info_to_uci(pos, depth, alpha, beta, i) << endl; - } // Value cannot be trusted. Break out immediately! if (StopRequest) @@ -667,26 +677,32 @@ namespace { // otherwise exit the fail high/low loop. if (value >= beta) { - beta = Min(beta + aspirationDelta * (1 << researchCountFH), VALUE_INFINITE); - researchCountFH++; + beta = Min(beta + aspirationDelta, VALUE_INFINITE); + aspirationDelta += aspirationDelta / 2; } else if (value <= alpha) { AspirationFailLow = true; StopOnPonderhit = false; - alpha = Max(alpha - aspirationDelta * (1 << researchCountFL), -VALUE_INFINITE); - researchCountFL++; + alpha = Max(alpha - aspirationDelta, -VALUE_INFINITE); + aspirationDelta += aspirationDelta / 2; } else break; - } + + } while (abs(value) < VALUE_KNOWN_WIN); // Collect info about search result bestMove = Rml[0].pv[0]; + *ponderMove = Rml[0].pv[1]; bestValues[depth] = value; bestMoveChanges[depth] = Rml.bestMoveChanges; + // 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, alpha, beta, i) << endl; + if (UseLogFile) LogFile << pretty_pv(pos, depth, value, current_search_time(), Rml[0].pv) << endl; @@ -739,7 +755,47 @@ namespace { } } - *ponderMove = Rml[0].pv[1]; + // When playing with strength handicap choose best move among the MultiPV set + // using a statistical rule dependent on SkillLevel. Idea by Heinz van Saanen. + if (SkillLevel < 20) + { + assert(MultiPV > 1); + + // Rml list is already sorted by pv_score in descending order + int s; + int max_s = -VALUE_INFINITE; + int size = Min(MultiPV, (int)Rml.size()); + int max = Rml[0].pv_score; + int var = Min(max - Rml[size - 1].pv_score, PawnValueMidgame); + int wk = 120 - 2 * SkillLevel; + + // PRNG sequence should be non deterministic + for (int i = abs(get_system_time() % 50); i > 0; i--) + RK.rand(); + + // 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++) + { + s = Rml[i].pv_score; + + // Don't allow crazy blunders even at very low skills + if (i > 0 && Rml[i-1].pv_score > s + EasyMoveMargin) + break; + + // This is our magical formula + s += ((max - s) * wk + var * (RK.rand() % wk)) / 128; + + if (s > max_s) + { + max_s = s; + bestMove = Rml[i].pv[0]; + *ponderMove = Rml[i].pv[1]; + } + } + } + return bestMove; } @@ -1049,7 +1105,7 @@ split_point_start: // At split points actual search starts from here if (abs(ttValue) < VALUE_KNOWN_WIN) { - Value b = ttValue - depth; + Value b = ttValue - int(depth); ss->excludedMove = move; ss->skipNullMove = true; Value v = search(pos, ss, b - 1, b, depth / 2, ply); @@ -1290,8 +1346,12 @@ split_point_start: // At split points actual search starts from here if ( bestValue >= beta && !pos.move_is_capture_or_promotion(move)) { + if (move != ss->killers[0]) + { + ss->killers[1] = ss->killers[0]; + ss->killers[0] = move; + } update_history(pos, move, depth, movesSearched, playedMoveCount); - update_killers(move, ss->killers); } } @@ -1810,19 +1870,6 @@ split_point_start: // At split points actual search starts from here } - // update_killers() add a good move that produced a beta-cutoff - // among the killer moves of that ply. - - void update_killers(Move m, Move killers[]) { - - if (m != killers[0]) - { - killers[1] = killers[0]; - killers[0] = m; - } - } - - // update_gains() updates the gains table of a non-capture move given // the static position evaluation before and after the move. @@ -1836,6 +1883,7 @@ split_point_start: // At split points actual search starts from here H.update_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after)); } + // current_search_time() returns the number of milliseconds which have passed // since the beginning of the current search. @@ -1896,10 +1944,7 @@ split_point_start: // At split points actual search starts from here // We are line oriented, don't read single chars std::string command; - if (!std::getline(std::cin, command)) - command = "quit"; - - if (command == "quit") + if (!std::getline(std::cin, command) || command == "quit") { // Quit the program as soon as possible Pondering = false; @@ -1977,20 +2022,12 @@ split_point_start: // At split points actual search starts from here std::string command; - while (true) - { - // Wait for a command from stdin - if (!std::getline(std::cin, command)) - command = "quit"; + // Wait for a command from stdin + while ( std::getline(std::cin, command) + && command != "ponderhit" && command != "stop" && command != "quit") {}; - if (command == "quit") - { - QuitRequest = true; - break; - } - else if (command == "ponderhit" || command == "stop") - break; - } + if (command != "ponderhit" && command != "stop") + QuitRequest = true; // Must be "quit" or getline() returned false }