X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=e773a36a72af9b40915dfede7c9a79ed45a9c5b1;hb=f6f1d2422303923927c0c088dee1d6df22dc4b98;hp=006834a7513c739df066ccc6fd72728a948fa88c;hpb=91cc82aa2566e6b6fa60cf82298250d6e4e2dd46;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index 006834a7..e773a36a 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -1,7 +1,7 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) - Copyright (C) 2008-2014 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -105,22 +105,14 @@ namespace { string uci_pv(const Position& pos, Depth depth, Value alpha, Value beta); struct Skill { - Skill(int l, size_t rootSize) : level(l), - candidates(l < 20 ? std::min(4, (int)rootSize) : 0), - best(MOVE_NONE) {} - ~Skill() { - 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())); - } - - size_t candidates_size() const { return candidates; } + Skill(int l) : level(l) {} + bool enabled() const { return level < 20; } bool time_to_pick(Depth depth) const { return depth / ONE_PLY == 1 + level; } - Move pick_move(); + Move best_move(size_t multiPV) { return best ? best : pick_best(multiPV); } + Move pick_best(size_t multiPV); int level; - size_t candidates; - Move best; + Move best = MOVE_NONE; }; } // namespace @@ -167,19 +159,19 @@ uint64_t Search::perft(Position& pos, Depth depth) { CheckInfo ci(pos); const bool leaf = (depth == 2 * ONE_PLY); - for (MoveList it(pos); *it; ++it) + for (const ExtMove& ms : MoveList(pos)) { if (Root && depth <= ONE_PLY) cnt = 1, nodes++; else { - pos.do_move(*it, st, ci, pos.gives_check(*it, ci)); + pos.do_move(ms.move, st, ci, pos.gives_check(ms.move, ci)); cnt = leaf ? MoveList(pos).size() : perft(pos, depth - ONE_PLY); nodes += cnt; - pos.undo_move(*it); + pos.undo_move(ms.move); } if (Root) - sync_cout << UCI::move(*it, pos.is_chess960()) << ": " << cnt << sync_endl; + sync_cout << UCI::move(ms.move, pos.is_chess960()) << ": " << cnt << sync_endl; } return nodes; } @@ -252,8 +244,8 @@ void Search::think() { } } - for (size_t i = 0; i < Threads.size(); ++i) - Threads[i]->maxPly = 0; + for (Thread* th : Threads) + th->maxPly = 0; Threads.timer->run = true; Threads.timer->notify_one(); // Wake up the recurring timer @@ -276,7 +268,7 @@ void Search::think() { sync_cout << "bestmove " << UCI::move(RootMoves[0].pv[0], RootPos.is_chess960()); - if (RootMoves[0].pv.size() > 1) + if (RootMoves[0].pv.size() > 1 || RootMoves[0].extract_ponder_from_tt(RootPos)) std::cout << " ponder " << UCI::move(RootMoves[0].pv[1], RootPos.is_chess960()); std::cout << sync_endl; @@ -309,11 +301,14 @@ namespace { Followupmoves.clear(); size_t multiPV = Options["MultiPV"]; - Skill skill(Options["Skill Level"], RootMoves.size()); + Skill skill(Options["Skill Level"]); + + // When playing with strength handicap enable MultiPV search that we will + // use behind the scenes to retrieve a set of possible moves. + if (skill.enabled()) + multiPV = std::max(multiPV, (size_t)4); - // 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. - multiPV = std::max(multiPV, skill.candidates_size()); + multiPV = std::min(multiPV, RootMoves.size()); // Iterative deepening loop until requested to stop or target depth reached while (++depth < DEPTH_MAX && !Signals.stop && (!Limits.depth || depth <= Limits.depth)) @@ -323,11 +318,11 @@ namespace { // Save the last iteration's scores before first PV line is searched and // all the move scores except the (new) PV are set to -VALUE_INFINITE. - for (size_t i = 0; i < RootMoves.size(); ++i) - RootMoves[i].previousScore = RootMoves[i].score; + for (RootMove& rm : RootMoves) + rm.previousScore = rm.score; // MultiPV loop. We perform a full root search for each PV line - for (PVIdx = 0; PVIdx < std::min(multiPV, RootMoves.size()) && !Signals.stop; ++PVIdx) + for (PVIdx = 0; PVIdx < multiPV && !Signals.stop; ++PVIdx) { // Reset aspiration window starting size if (depth >= 5 * ONE_PLY) @@ -365,7 +360,8 @@ namespace { // When failing high/low give some update (without cluttering // the UI) before a re-search. - if ( (bestValue <= alpha || bestValue >= beta) + if ( multiPV == 1 + && (bestValue <= alpha || bestValue >= beta) && Time::now() - SearchTime > 3000) sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; @@ -399,14 +395,13 @@ namespace { sync_cout << "info nodes " << RootPos.nodes_searched() << " time " << Time::now() - SearchTime << sync_endl; - else if ( PVIdx + 1 == std::min(multiPV, RootMoves.size()) - || Time::now() - SearchTime > 3000) + else 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.candidates_size() && skill.time_to_pick(depth)) - skill.pick_move(); + // If skill level is enabled and time is up, pick a sub-optimal best move + if (skill.enabled() && skill.time_to_pick(depth)) + skill.pick_best(multiPV); // Have we found a "mate in x"? if ( Limits.mate @@ -435,6 +430,11 @@ namespace { } } } + + // If skill level is enabled, swap best PV line with the sub-optimal one + if (skill.enabled()) + std::swap(RootMoves[0], *std::find(RootMoves.begin(), + RootMoves.end(), skill.best_move(multiPV))); } @@ -476,7 +476,7 @@ namespace { splitPoint = ss->splitPoint; bestMove = splitPoint->bestMove; bestValue = splitPoint->bestValue; - tte = NULL; + tte = nullptr; ttHit = false; ttMove = excludedMove = MOVE_NONE; ttValue = VALUE_NONE; @@ -539,7 +539,7 @@ namespace { // If ttMove is quiet, update killers, history, counter move and followup move on TT hit if (ttValue >= beta && ttMove && !pos.capture_or_promotion(ttMove) && !inCheck) - update_stats(pos, ss, ttMove, depth, NULL, 0); + update_stats(pos, ss, ttMove, depth, nullptr, 0); return ttValue; } @@ -584,7 +584,7 @@ namespace { else if (ttHit) { // Never assume anything on values stored in TT - if ((ss->staticEval = eval = tte->eval_value()) == VALUE_NONE) + if ((ss->staticEval = eval = tte->eval()) == VALUE_NONE) eval = ss->staticEval = evaluate(pos); // Can ttValue be used as a better position evaluation? @@ -632,7 +632,7 @@ namespace { } // Step 7. Futility pruning: child node (skipped when in check) - if ( !PvNode + if ( !RootNode && depth < 7 * ONE_PLY && eval - futility_margin(depth) >= beta && eval < VALUE_KNOWN_WIN // Do not return unproven wins @@ -650,7 +650,7 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = (3 + depth / 4 + std::min((eval - beta) / PawnValueMg, 3)) * ONE_PLY; + Depth R = ((823 + 67 * depth) / 256 + std::min((eval - beta) / PawnValueMg, 3)) * ONE_PLY; pos.do_null_move(st); (ss+1)->skipEarlyPruning = true; @@ -788,7 +788,7 @@ moves_loop: // When in check and at SpNode search starts from here } if (PvNode) - (ss+1)->pv = NULL; + (ss+1)->pv = nullptr; extension = DEPTH_ZERO; captureOrPromotion = pos.capture_or_promotion(move); @@ -829,8 +829,8 @@ moves_loop: // When in check and at SpNode search starts from here // Update the current move (this must be done after singular extension search) newDepth = depth - ONE_PLY + extension; - // Step 13. Pruning at shallow depth (exclude PV nodes) - if ( !PvNode + // Step 13. Pruning at shallow depth + if ( !RootNode && !captureOrPromotion && !inCheck && !dangerous @@ -906,7 +906,7 @@ moves_loop: // When in check and at SpNode search starts from here ss->reduction = reduction(improving, depth, moveCount); if ( (!PvNode && cutNode) - || History[pos.piece_on(to_sq(move))][to_sq(move)] < 0) + || History[pos.piece_on(to_sq(move))][to_sq(move)] < VALUE_ZERO) ss->reduction += ONE_PLY; if (move == countermoves[0] || move == countermoves[1]) @@ -916,7 +916,7 @@ moves_loop: // When in check and at SpNode search starts from here 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) + && pos.see(make_move(to_sq(move), from_sq(move))) < VALUE_ZERO) ss->reduction = std::max(DEPTH_ZERO, ss->reduction - ONE_PLY); Depth d = std::max(newDepth - ss->reduction, ONE_PLY); @@ -1165,7 +1165,7 @@ moves_loop: // When in check and at SpNode search starts from here if (ttHit) { // Never assume anything on values stored in TT - if ((ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE) + if ((ss->staticEval = bestValue = tte->eval()) == VALUE_NONE) ss->staticEval = bestValue = evaluate(pos); // Can ttValue be used as a better position evaluation? @@ -1210,8 +1210,7 @@ moves_loop: // When in check and at SpNode search starts from here : pos.gives_check(move, ci); // Futility pruning - if ( !PvNode - && !InCheck + if ( !InCheck && !givesCheck && futilityBase > -VALUE_KNOWN_WIN && !pos.advanced_pawn_push(move)) @@ -1220,13 +1219,13 @@ moves_loop: // When in check and at SpNode search starts from here futilityValue = futilityBase + PieceValue[EG][pos.piece_on(to_sq(move))]; - if (futilityValue < beta) + if (futilityValue <= alpha) { bestValue = std::max(bestValue, futilityValue); continue; } - if (futilityBase < beta && pos.see(move) <= VALUE_ZERO) + if (futilityBase <= alpha && pos.see(move) <= VALUE_ZERO) { bestValue = std::max(bestValue, futilityBase); continue; @@ -1240,8 +1239,7 @@ moves_loop: // When in check and at SpNode search starts from here && !pos.can_castle(pos.side_to_move()); // Don't search moves with negative SEE values - if ( !PvNode - && (!InCheck || evasionPrunable) + if ( (!InCheck || evasionPrunable) && type_of(move) != PROMOTION && pos.see_sign(move) < VALUE_ZERO) continue; @@ -1373,31 +1371,26 @@ moves_loop: // When in check and at SpNode search starts from here } - // 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. + // When playing with strength handicap, choose best move among a set of RootMoves + // using a statistical rule dependent on 'level'. Idea by Heinz van Saanen. - Move Skill::pick_move() { + Move Skill::pick_best(size_t multiPV) { // PRNG sequence should be non-deterministic, so we seed it with the time at init static PRNG rng(Time::now()); // RootMoves are already sorted by score in descending order - int variance = std::min(RootMoves[0].score - RootMoves[candidates - 1].score, PawnValueMg); + int variance = std::min(RootMoves[0].score - RootMoves[multiPV - 1].score, PawnValueMg); int weakness = 120 - 2 * level; int maxScore = -VALUE_INFINITE; - best = MOVE_NONE; // 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, + // weakness. One deterministic and bigger for weaker levels, and one random, // then we choose the move with the resulting highest score. - for (size_t i = 0; i < candidates; ++i) + for (size_t i = 0; i < multiPV; ++i) { int score = RootMoves[i].score; - // Don't allow crazy blunders even at very low skills - if (i > 0 && RootMoves[i - 1].score > score + 2 * PawnValueMg) - break; - // This is our magic formula score += ( weakness * int(RootMoves[0].score - score) + variance * (rng.rand() % weakness)) / 128; @@ -1423,9 +1416,9 @@ moves_loop: // When in check and at SpNode search starts from here size_t uciPVSize = std::min((size_t)Options["MultiPV"], RootMoves.size()); int selDepth = 0; - for (size_t i = 0; i < Threads.size(); ++i) - if (Threads[i]->maxPly > selDepth) - selDepth = Threads[i]->maxPly; + for (Thread* th : Threads) + if (th->maxPly > selDepth) + selDepth = th->maxPly; for (size_t i = 0; i < uciPVSize; ++i) { @@ -1446,8 +1439,12 @@ moves_loop: // When in check and at SpNode search starts from here ss << "info depth " << d / ONE_PLY << " seldepth " << selDepth << " multipv " << i + 1 - << " score " << ((!tb && i == PVIdx) ? UCI::value(v, alpha, beta) : UCI::value(v)) - << " nodes " << pos.nodes_searched() + << " score " << UCI::value(v); + + if (!tb && i == PVIdx) + ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : ""); + + ss << " nodes " << pos.nodes_searched() << " nps " << pos.nodes_searched() * 1000 / elapsed << " tbhits " << TB::Hits << " time " << elapsed @@ -1489,13 +1486,37 @@ void RootMove::insert_pv_in_tt(Position& pos) { } +/// RootMove::extract_ponder_from_tt() is called in case we have no ponder move before +/// exiting the search, for instance in case we stop the search during a fail high at +/// root. We try hard to have a ponder move to return to the GUI, otherwise in case of +/// 'ponder on' we have nothing to think on. + +Move RootMove::extract_ponder_from_tt(Position& pos) +{ + StateInfo st; + bool found; + + assert(pv.size() == 1); + + pos.do_move(pv[0], st); + TTEntry* tte = TT.probe(pos.key(), found); + Move m = found ? tte->move() : MOVE_NONE; + if (!MoveList(pos).contains(m)) + m = MOVE_NONE; + + pos.undo_move(pv[0]); + pv.push_back(m); + return m; +} + + /// Thread::idle_loop() is where the thread is parked when it has no work to do void Thread::idle_loop() { // Pointer 'this_sp' is not null only if we are called from split(), and not // at the thread creation. This means we are the split point's master. - SplitPoint* this_sp = splitPointsSize ? activeSplitPoint : NULL; + SplitPoint* this_sp = splitPointsSize ? activeSplitPoint : nullptr; assert(!this_sp || (this_sp->masterThread == this && searching)); @@ -1519,7 +1540,7 @@ void Thread::idle_loop() { sp->mutex.lock(); - assert(activePosition == NULL); + assert(activePosition == nullptr); activePosition = &pos; @@ -1538,7 +1559,7 @@ void Thread::idle_loop() { assert(searching); searching = false; - activePosition = NULL; + activePosition = nullptr; sp->slavesMask.reset(idx); sp->allSlavesSearching = false; sp->nodes += pos.nodes_searched(); @@ -1563,7 +1584,7 @@ void Thread::idle_loop() { for (size_t i = 0; i < Threads.size(); ++i) { const int size = Threads[i]->splitPointsSize; // Local copy - sp = size ? &Threads[i]->splitPoints[size - 1] : NULL; + sp = size ? &Threads[i]->splitPoints[size - 1] : nullptr; if ( sp && sp->allSlavesSearching @@ -1590,22 +1611,19 @@ void Thread::idle_loop() { } // Grab the lock to avoid races with Thread::notify_one() - mutex.lock(); + std::unique_lock lk(mutex); // If we are master and all slaves have finished then exit idle_loop if (this_sp && this_sp->slavesMask.none()) { assert(!searching); - mutex.unlock(); break; } // If we are not searching, wait for a condition to be signaled instead of // wasting CPU time polling for work. if (!searching && !exit) - sleepCondition.wait(mutex); - - mutex.unlock(); + sleepCondition.wait(lk); } } @@ -1650,10 +1668,10 @@ void check_time() { // Loop across all split points and sum accumulated SplitPoint nodes plus // all the currently active positions nodes. - for (size_t i = 0; i < Threads.size(); ++i) - for (int j = 0; j < Threads[i]->splitPointsSize; ++j) + for (Thread* th : Threads) + for (int i = 0; i < th->splitPointsSize; ++i) { - SplitPoint& sp = Threads[i]->splitPoints[j]; + SplitPoint& sp = th->splitPoints[i]; sp.mutex.lock();