X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=94fa063fa5274e6a1c3194597b1ceb10203d4978;hp=3dde96d8a0c893290124e980ad7c4bfff88129d5;hb=673bc5526fa3d352f823ad144fb521b5dc98f45c;hpb=d98150dffc69a810b0b842244aec0d29deddabfb diff --git a/src/search.cpp b/src/search.cpp index 3dde96d8..94fa063f 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -24,12 +24,10 @@ #include #include #include -#include #include "book.h" #include "evaluate.h" #include "history.h" -#include "misc.h" #include "movegen.h" #include "movepick.h" #include "search.h" @@ -42,13 +40,15 @@ namespace Search { volatile SignalsType Signals; LimitsType Limits; - std::vector SearchMoves; + std::vector RootMoves; Position RootPosition; + Time SearchTime; } using std::string; using std::cout; using std::endl; +using Eval::evaluate; using namespace Search; namespace { @@ -59,33 +59,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 +108,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 +124,6 @@ namespace { History H; - /// Local functions - template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); @@ -163,15 +131,14 @@ namespace { Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); void id_loop(Position& pos); - bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue); + bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta); bool connected_moves(const Position& pos, Move m1, Move m2); Value value_to_tt(Value v, int ply); Value value_from_tt(Value v, int ply); - bool can_return_tt(const TTEntry* tte, Depth depth, Value beta, int ply); + bool can_return_tt(const TTEntry* tte, Depth depth, Value ttValue, Value beta); bool connected_threat(const Position& pos, Move m, Move threat); - Value refine_eval(const TTEntry* tte, Value defaultEval, int ply); + Value refine_eval(const TTEntry* tte, Value ttValue, Value defaultEval); Move do_skill_level(); - int elapsed_time(bool reset = false); string score_to_uci(Value v, Value alpha = -VALUE_INFINITE, Value beta = VALUE_INFINITE); void pv_info_to_log(Position& pos, int depth, Value score, int time, Move pv[]); void pv_info_to_uci(const Position& pos, int depth, Value alpha, Value beta); @@ -284,17 +251,19 @@ void Search::think() { Position& pos = RootPosition; Chess960 = pos.is_chess960(); - elapsed_time(true); - TimeMgr.init(Limits, pos.startpos_ply_counter()); + Eval::RootColor = pos.side_to_move(); + TimeMgr.init(Limits, pos.startpos_ply_counter(), pos.side_to_move()); 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"]) { @@ -307,17 +276,6 @@ void Search::think() { } } - // Read UCI options: GUI could change UCI parameters during the game - read_evaluation_uci_options(pos.side_to_move()); - Threads.read_uci_options(); - - TT.set_size(Options["Hash"]); - if (Options["Clear Hash"]) - { - Options["Clear Hash"] = false; - TT.clear(); - } - UCIMultiPV = Options["MultiPV"]; SkillLevel = Options["Skill Level"]; @@ -332,17 +290,13 @@ void Search::think() { log << "\nSearching: " << pos.to_fen() << "\ninfinite: " << Limits.infinite << " ponder: " << Limits.ponder - << " time: " << Limits.time - << " increment: " << Limits.increment - << " moves to go: " << Limits.movesToGo + << " time: " << Limits.time[pos.side_to_move()] + << " increment: " << Limits.inc[pos.side_to_move()] + << " moves to go: " << Limits.movestogo << endl; } - for (int i = 0; i < Threads.size(); i++) - { - Threads[i].maxPly = 0; - Threads[i].wake_up(); - } + Threads.wake_up(); // Set best timer interval to avoid lagging under time pressure. Timer is // used to check for remaining available thinking time. @@ -354,13 +308,12 @@ void Search::think() { // We're ready to start searching. Call the iterative deepening loop function id_loop(pos); - // Stop timer and send all the slaves to sleep, if not already sleeping - Threads.set_timer(0); - Threads.set_size(1); + Threads.set_timer(0); // Stop timer + Threads.sleep(); if (Options["Use Search Log"]) { - int e = elapsed_time(); + int e = SearchTime.elapsed(); Log log(Options["Search Log Filename"]); log << "Nodes: " << pos.nodes_searched() @@ -375,11 +328,11 @@ 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(); + pos.this_thread().wait_for_stop_or_ponderhit(); // Best move could be MOVE_NONE when searching on a stalemate position cout << "bestmove " << move_to_uci(RootMoves[0].pv[0], Chess960) @@ -406,18 +359,8 @@ 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)) + while (!Signals.stop && ++depth <= MAX_PLY && (!Limits.depth || depth <= Limits.depth)) { // Save last iteration's scores before first PV line is searched and all // the move scores but the (new) PV are set to -VALUE_INFINITE. @@ -478,7 +421,7 @@ namespace { // 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 ((bestValue > alpha && bestValue < beta) || elapsed_time() > 2000) + if ((bestValue > alpha && bestValue < beta) || SearchTime.elapsed() > 2000) pv_info_to_uci(pos, depth, alpha, beta); // In case of failing high/low increase aspiration window and @@ -508,8 +451,8 @@ namespace { if (SkillLevelEnabled && depth == 1 + SkillLevel) skillBest = do_skill_level(); - if (Options["Use Search Log"]) - pv_info_to_log(pos, depth, bestValue, elapsed_time(), &RootMoves[0].pv[0]); + if (!Signals.stop && Options["Use Search Log"]) + pv_info_to_log(pos, depth, bestValue, SearchTime.elapsed(), &RootMoves[0].pv[0]); // Filter out startup noise when monitoring best move stability if (depth > 2 && BestMoveChanges) @@ -527,19 +470,19 @@ namespace { // Stop search if most of available time is already consumed. We // probably don't have enough time to search the first move at the // next iteration anyway. - if (elapsed_time() > (TimeMgr.available_time() * 62) / 100) + if (SearchTime.elapsed() > (TimeMgr.available_time() * 62) / 100) stop = true; // Stop search early if one move seems to be much better than others - if ( depth >= 10 + if ( depth >= 12 && !stop - && ( bestMoveNeverChanged - || elapsed_time() > (TimeMgr.available_time() * 40) / 100)) + && ( (bestMoveNeverChanged && pos.captured_piece_type()) + || SearchTime.elapsed() > (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,23 +528,22 @@ 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()); Move movesSearched[MAX_MOVES]; StateInfo st; const TTEntry *tte; Key posKey; - Move ttMove, move, excludedMove, threatMove; + Move ttMove, move, excludedMove, bestMove, threatMove; Depth ext, newDepth; - ValueType vt; - Value bestValue, value, oldAlpha; + Bound bt; + Value bestValue, value, oldAlpha, ttValue; Value refinedValue, nullValue, futilityBase, futilityValue; bool isPvMove, inCheck, singularExtensionNode, givesCheck; bool captureOrPromotion, dangerous, doFullDepthSearch; int moveCount = 0, playedMoveCount = 0; - Thread& thread = Threads[pos.thread()]; + Thread& thread = pos.this_thread(); SplitPoint* sp = NULL; refinedValue = bestValue = value = -VALUE_INFINITE; @@ -614,22 +556,34 @@ namespace { thread.maxPly = ss->ply; // Step 1. Initialize node - if (!SpNode) - { - ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE; - (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; - (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; - } - else + if (SpNode) { - sp = ss->sp; tte = NULL; ttMove = excludedMove = MOVE_NONE; + ttValue = VALUE_ZERO; + sp = ss->sp; + bestMove = sp->bestMove; threatMove = sp->threatMove; + bestValue = sp->bestValue; + moveCount = sp->moveCount; // Lock must be held here + + assert(bestValue > -VALUE_INFINITE && moveCount > 0); + goto split_point_start; } + else + { + ss->currentMove = threatMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; + (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; + (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; + + } // Step 2. Check for aborted search and immediate draw + // Enforce node limit here. FIXME: This only works with 1 search thread. + if (Limits.nodes && pos.nodes_searched() >= Limits.nodes) + Signals.stop = true; + if (( Signals.stop || pos.is_draw() || ss->ply > MAX_PLY) && !RootNode) @@ -656,27 +610,27 @@ namespace { posKey = excludedMove ? pos.exclusion_key() : pos.key(); tte = TT.probe(posKey); ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE; + ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_ZERO; // At PV nodes we check for exact scores, while at non-PV nodes we check for // a fail high/low. Biggest advantage at probing at PV nodes is to have a // smooth experience in analysis mode. We don't probe at Root nodes otherwise // we should also update RootMoveList to avoid bogus output. - if (!RootNode && tte && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT - : can_return_tt(tte, depth, beta, ss->ply))) + if (!RootNode && tte && (PvNode ? tte->depth() >= depth && tte->type() == BOUND_EXACT + : can_return_tt(tte, depth, ttValue, beta))) { TT.refresh(tte); - ss->bestMove = move = ttMove; // Can be MOVE_NONE - value = value_from_tt(tte->value(), ss->ply); + ss->currentMove = ttMove; // Can be MOVE_NONE - if ( value >= beta - && move - && !pos.is_capture_or_promotion(move) - && move != ss->killers[0]) + if ( ttValue >= beta + && ttMove + && !pos.is_capture_or_promotion(ttMove) + && ttMove != ss->killers[0]) { ss->killers[1] = ss->killers[0]; - ss->killers[0] = move; + ss->killers[0] = ttMove; } - return value; + return ttValue; } // Step 5. Evaluate the position statically and update parent's gain statistics @@ -688,12 +642,12 @@ namespace { ss->eval = tte->static_value(); ss->evalMargin = tte->static_value_margin(); - refinedValue = refine_eval(tte, ss->eval, ss->ply); + refinedValue = refine_eval(tte, ttValue, ss->eval); } else { refinedValue = ss->eval = evaluate(pos, ss->evalMargin); - TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin); + TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin); } // Update gain for the parent non-capture move given the static position @@ -701,7 +655,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); @@ -715,7 +669,7 @@ namespace { && refinedValue + razor_margin(depth) < beta && ttMove == MOVE_NONE && abs(beta) < VALUE_MATE_IN_MAX_PLY - && !pos.has_pawn_on_7th(pos.side_to_move())) + && !pos.pawn_on_7th(pos.side_to_move())) { Value rbeta = beta - razor_margin(depth); Value v = qsearch(pos, ss, rbeta-1, rbeta, DEPTH_ZERO); @@ -787,7 +741,7 @@ namespace { // move which was reduced. If a connection is found, return a fail // low score (which will cause the reduced move to fail high in the // parent node, which will trigger a re-search with full depth). - threatMove = (ss+1)->bestMove; + threatMove = (ss+1)->currentMove; if ( depth < ThreatDepth && (ss-1)->reduction @@ -812,6 +766,8 @@ namespace { Depth rdepth = depth - ONE_PLY - 3 * ONE_PLY; assert(rdepth >= ONE_PLY); + assert((ss-1)->currentMove != MOVE_NONE); + assert((ss-1)->currentMove != MOVE_NULL); MovePicker mp(pos, ttMove, H, pos.captured_piece_type()); CheckInfo ci(pos); @@ -819,6 +775,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); @@ -846,23 +803,14 @@ split_point_start: // At split points actual search starts from here MovePickerExt mp(pos, ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta); CheckInfo ci(pos); - ss->bestMove = MOVE_NONE; futilityBase = ss->eval + ss->evalMargin; singularExtensionNode = !RootNode && !SpNode && depth >= SingularExtensionDepth[PvNode] && ttMove != MOVE_NONE && !excludedMove // Recursive singular search is not allowed - && (tte->type() & VALUE_TYPE_LOWER) + && (tte->type() & BOUND_LOWER) && tte->depth() >= depth - 3 * ONE_PLY; - if (SpNode) - { - lock_grab(&(sp->lock)); - bestValue = sp->bestValue; - moveCount = sp->moveCount; - - assert(bestValue > -VALUE_INFINITE && moveCount > 0); - } // Step 11. Loop through moves // Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs @@ -889,7 +837,7 @@ split_point_start: // At split points actual search starts from here if (SpNode) { moveCount = ++sp->moveCount; - lock_release(&(sp->lock)); + lock_release(sp->lock); } else moveCount++; @@ -898,7 +846,7 @@ split_point_start: // At split points actual search starts from here { Signals.firstRootMove = (moveCount == 1); - if (pos.thread() == 0 && elapsed_time() > 2000) + if (&thread == Threads.main_thread() && SearchTime.elapsed() > 2000) cout << "info depth " << depth / ONE_PLY << " currmove " << move_to_uci(move, Chess960) << " currmovenumber " << moveCount + PVIdx << endl; @@ -927,8 +875,6 @@ split_point_start: // At split points actual search starts from here && move == ttMove && pos.pl_move_is_legal(move, ci.pinned)) { - Value ttValue = value_from_tt(tte->value(), ss->ply); - if (abs(ttValue) < VALUE_KNOWN_WIN) { Value rBeta = ttValue - int(depth); @@ -937,7 +883,6 @@ split_point_start: // At split points actual search starts from here value = search(pos, ss, rBeta - 1, rBeta, depth / 2); ss->skipNullMove = false; ss->excludedMove = MOVE_NONE; - ss->bestMove = MOVE_NONE; if (value < rBeta) ext = ONE_PLY; } @@ -960,7 +905,7 @@ split_point_start: // At split points actual search starts from here && (!threatMove || !connected_threat(pos, move, threatMove))) { if (SpNode) - lock_grab(&(sp->lock)); + lock_grab(sp->lock); continue; } @@ -975,7 +920,7 @@ split_point_start: // At split points actual search starts from here if (futilityValue < beta) { if (SpNode) - lock_grab(&(sp->lock)); + lock_grab(sp->lock); continue; } @@ -985,7 +930,7 @@ split_point_start: // At split points actual search starts from here && pos.see_sign(move) < 0) { if (SpNode) - lock_grab(&(sp->lock)); + lock_grab(sp->lock); continue; } @@ -1016,11 +961,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; @@ -1051,12 +995,12 @@ split_point_start: // At split points actual search starts from here // Step 18. Check for new best move if (SpNode) { - lock_grab(&(sp->lock)); + lock_grab(sp->lock); bestValue = sp->bestValue; 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. @@ -1087,7 +1031,7 @@ split_point_start: // At split points actual search starts from here if (value > bestValue) { bestValue = value; - ss->bestMove = move; + bestMove = move; if ( PvNode && value > alpha @@ -1097,9 +1041,11 @@ split_point_start: // At split points actual search starts from here if (SpNode && !thread.cutoff_occurred()) { sp->bestValue = value; - sp->ss->bestMove = move; + sp->bestMove = move; sp->alpha = alpha; - sp->is_betaCutoff = (value >= beta); + + if (value >= beta) + sp->cutoff = true; } } @@ -1107,17 +1053,17 @@ split_point_start: // At split points actual search starts from here if ( !SpNode && depth >= Threads.min_split_depth() && bestValue < beta - && Threads.available_slave_exists(pos.thread()) + && Threads.available_slave_exists(thread) && !Signals.stop && !thread.cutoff_occurred()) - bestValue = Threads.split(pos, ss, alpha, beta, bestValue, depth, - threatMove, moveCount, &mp, NT); + bestValue = Threads.split(pos, ss, alpha, beta, bestValue, &bestMove, + depth, threatMove, moveCount, &mp, NT); } // 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) @@ -1128,18 +1074,18 @@ split_point_start: // At split points actual search starts from here { assert(!playedMoveCount); - bestValue = alpha; + bestValue = oldAlpha; } // Step 21. Update tables // Update transposition table entry, killers and history if (!SpNode && !Signals.stop && !thread.cutoff_occurred()) { - move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove; - vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER - : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT; + move = bestValue <= oldAlpha ? MOVE_NONE : bestMove; + bt = bestValue <= oldAlpha ? BOUND_UPPER + : bestValue >= beta ? BOUND_LOWER : BOUND_EXACT; - TT.store(posKey, value_to_tt(bestValue, ss->ply), vt, depth, move, ss->eval, ss->evalMargin); + TT.store(posKey, value_to_tt(bestValue, ss->ply), bt, depth, move, ss->eval, ss->evalMargin); // Update killers and history for non capture cut-off moves if ( bestValue >= beta @@ -1165,14 +1111,6 @@ split_point_start: // At split points actual search starts from here } } - if (SpNode) - { - // Here we have the lock still grabbed - sp->is_slave[pos.thread()] = false; - sp->nodes += pos.nodes_searched(); - lock_release(&(sp->lock)); - } - assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); return bestValue; @@ -1190,20 +1128,19 @@ 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()); StateInfo st; - Move ttMove, move; - Value bestValue, value, evalMargin, futilityValue, futilityBase; + Move ttMove, move, bestMove; + Value ttValue, bestValue, value, evalMargin, futilityValue, futilityBase; bool inCheck, enoughMaterial, givesCheck, evasionPrunable; const TTEntry* tte; Depth ttDepth; - ValueType vt; + Bound bt; Value oldAlpha = alpha; - ss->bestMove = ss->currentMove = MOVE_NONE; + ss->currentMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; // Check for an instant draw or maximum ply reached @@ -1220,11 +1157,12 @@ split_point_start: // At split points actual search starts from here // pruning, but only for move ordering. tte = TT.probe(pos.key()); ttMove = (tte ? tte->move() : MOVE_NONE); + ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_ZERO; - if (!PvNode && tte && can_return_tt(tte, ttDepth, beta, ss->ply)) + if (!PvNode && tte && can_return_tt(tte, ttDepth, ttValue, beta)) { - ss->bestMove = ttMove; // Can be MOVE_NONE - return value_from_tt(tte->value(), ss->ply); + ss->currentMove = ttMove; // Can be MOVE_NONE + return ttValue; } // Evaluate the position statically @@ -1250,7 +1188,7 @@ split_point_start: // At split points actual search starts from here if (bestValue >= beta) { if (!tte) - TT.store(pos.key(), value_to_tt(bestValue, ss->ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin); + TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin); return bestValue; } @@ -1327,13 +1265,8 @@ split_point_start: // At split points actual search starts from here && move != ttMove && !pos.is_capture_or_promotion(move) && ss->eval + PawnValueMidgame / 4 < beta - && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue)) - { - if (ss->eval + PawnValueMidgame / 4 > bestValue) - bestValue = ss->eval + PawnValueMidgame / 4; - + && !check_is_dangerous(pos, move, futilityBase, beta)) continue; - } // Check for legality only before to do the move if (!pos.pl_move_is_legal(move, ci.pinned)) @@ -1352,7 +1285,7 @@ split_point_start: // At split points actual search starts from here if (value > bestValue) { bestValue = value; - ss->bestMove = move; + bestMove = move; if ( PvNode && value > alpha @@ -1367,11 +1300,11 @@ split_point_start: // At split points actual search starts from here return mated_in(ss->ply); // Plies to mate from the root // Update transposition table - move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove; - vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER - : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT; + move = bestValue <= oldAlpha ? MOVE_NONE : bestMove; + bt = bestValue <= oldAlpha ? BOUND_UPPER + : bestValue >= beta ? BOUND_LOWER : BOUND_EXACT; - TT.store(pos.key(), value_to_tt(bestValue, ss->ply), vt, ttDepth, move, ss->eval, evalMargin); + TT.store(pos.key(), value_to_tt(bestValue, ss->ply), bt, ttDepth, move, ss->eval, evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1383,55 +1316,43 @@ split_point_start: // At split points actual search starts from here // bestValue is updated only when returning false because in that case move // will be pruned. - bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bestValue) + bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta) { Bitboard b, occ, oldAtt, newAtt, kingAtt; - Square from, to, ksq, victimSq; + Square from, to, ksq; Piece pc; Color them; - Value futilityValue, bv = *bestValue; from = from_sq(move); to = to_sq(move); them = ~pos.side_to_move(); ksq = pos.king_square(them); kingAtt = pos.attacks_from(ksq); - pc = pos.piece_on(from); + pc = pos.piece_moved(move); - occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL << ksq); + occ = pos.pieces() ^ from ^ ksq; oldAtt = pos.attacks_from(pc, from, occ); newAtt = pos.attacks_from(pc, to, occ); // Rule 1. Checks which give opponent's king at most one escape square are dangerous b = kingAtt & ~pos.pieces(them) & ~newAtt & ~(1ULL << to); - if (!(b && (b & (b - 1)))) + if (single_bit(b)) // Catches also !b return true; // Rule 2. Queen contact check is very dangerous - if ( type_of(pc) == QUEEN - && bit_is_set(kingAtt, to)) + if (type_of(pc) == QUEEN && (kingAtt & to)) return true; // Rule 3. Creating new double threats with checks b = pos.pieces(them) & newAtt & ~oldAtt & ~(1ULL << ksq); - while (b) { - victimSq = pop_1st_bit(&b); - futilityValue = futilityBase + PieceValueEndgame[pos.piece_on(victimSq)]; - // Note that here we generate illegal "double move"! - if ( futilityValue >= beta - && pos.see_sign(make_move(from, victimSq)) >= 0) + if (futilityBase + PieceValueEndgame[pos.piece_on(pop_1st_bit(&b))] >= beta) return true; - - if (futilityValue > bv) - bv = futilityValue; } - // Update bestValue only if check is not dangerous (because we will prune the move) - *bestValue = bv; return false; } @@ -1465,25 +1386,21 @@ split_point_start: // At split points actual search starts from here // Case 3: Moving through the vacated square p2 = pos.piece_on(f2); - if ( piece_is_slider(p2) - && bit_is_set(squares_between(f2, t2), f1)) + if (piece_is_slider(p2) && (squares_between(f2, t2) & f1)) return true; // Case 4: The destination square for m2 is defended by the moving piece in m1 p1 = pos.piece_on(t1); - if (bit_is_set(pos.attacks_from(p1, t1), t2)) + if (pos.attacks_from(p1, t1) & t2) return true; // Case 5: Discovered check, checking piece is the piece moved in m1 ksq = pos.king_square(pos.side_to_move()); if ( piece_is_slider(p1) - && bit_is_set(squares_between(t1, ksq), f2)) - { - Bitboard occ = pos.occupied_squares(); - clear_bit(&occ, f2); - if (bit_is_set(pos.attacks_from(p1, t1, occ), ksq)) - return true; - } + && (squares_between(t1, ksq) & f2) + && (pos.attacks_from(p1, t1, pos.pieces() ^ f2) & ksq)) + return true; + return false; } @@ -1551,9 +1468,9 @@ split_point_start: // At split points actual search starts from here // Case 3: If the moving piece in the threatened move is a slider, don't // prune safe moves which block its ray. - if ( piece_is_slider(pos.piece_on(tfrom)) - && bit_is_set(squares_between(tfrom, tto), mto) - && pos.see_sign(m) >= 0) + if ( piece_is_slider(pos.piece_on(tfrom)) + && (squares_between(tfrom, tto) & mto) + && pos.see_sign(m) >= 0) return true; return false; @@ -1563,50 +1480,32 @@ split_point_start: // At split points actual search starts from here // can_return_tt() returns true if a transposition table score can be used to // cut-off at a given point in search. - bool can_return_tt(const TTEntry* tte, Depth depth, Value beta, int ply) { - - Value v = value_from_tt(tte->value(), ply); + bool can_return_tt(const TTEntry* tte, Depth depth, Value v, Value beta) { return ( tte->depth() >= depth || v >= std::max(VALUE_MATE_IN_MAX_PLY, beta) || v < std::min(VALUE_MATED_IN_MAX_PLY, beta)) - && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta) - || ((tte->type() & VALUE_TYPE_UPPER) && v < beta)); + && ( ((tte->type() & BOUND_LOWER) && v >= beta) + || ((tte->type() & BOUND_UPPER) && v < beta)); } // refine_eval() returns the transposition table score if possible, otherwise // falls back on static position evaluation. - Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) { + Value refine_eval(const TTEntry* tte, Value v, Value defaultEval) { assert(tte); - Value v = value_from_tt(tte->value(), ply); - - if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval) - || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval)) + if ( ((tte->type() & BOUND_LOWER) && v >= defaultEval) + || ((tte->type() & BOUND_UPPER) && v < defaultEval)) return v; return defaultEval; } - // current_search_time() returns the number of milliseconds which have passed - // since the beginning of the current search. - - int elapsed_time(bool reset) { - - static int searchStartTime; - - if (reset) - searchStartTime = system_time(); - - return system_time() - searchStartTime; - } - - // score_to_uci() converts a value to a string suitable for use with the UCI // protocol specifications: // @@ -1635,7 +1534,7 @@ split_point_start: // At split points actual search starts from here void pv_info_to_uci(const Position& pos, int depth, Value alpha, Value beta) { - int t = elapsed_time(); + int t = SearchTime.elapsed(); int selDepth = 0; for (int i = 0; i < Threads.size(); i++) @@ -1767,7 +1666,7 @@ split_point_start: // At split points actual search starts from here static RKISS rk; // PRNG sequence should be not deterministic - for (int i = abs(system_time() % 50); i > 0; i--) + for (int i = Time::current_time().msec() % 50; i > 0; i--) rk.rand(); // RootMoves are already sorted by score in descending order @@ -1801,105 +1700,105 @@ 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 BOUND_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) { + + 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++); - do pos.undo_move(pv[--ply]); while (ply); + while ( (tte = TT.probe(pos.key())) != NULL + && (m = tte->move()) != MOVE_NONE // Local copy, TT entry could change + && pos.is_pseudo_legal(m) + && pos.pl_move_is_legal(m, pos.pinned_pieces()) + && ply < MAX_PLY + && (!pos.is_draw() || ply < 2)) + { + pv.push_back(m); + pos.do_move(m, *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, BOUND_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. -/// The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint object -/// for which the thread is the master. +/// The parameter 'master_sp', if non-NULL, is a pointer to an active SplitPoint +/// object for which the thread is the master. -void Thread::idle_loop(SplitPoint* sp) { +void Thread::idle_loop(SplitPoint* sp_master) { - while (true) + // If this thread is the master of a split point and all slaves have + // finished their work at this split point, return from the idle loop. + while (!sp_master || sp_master->slavesMask) { // If we are not searching, wait for a condition to be signaled // instead of wasting CPU time polling for work. while ( do_sleep - || do_terminate - || (Threads.use_sleeping_threads() && !is_searching)) + || do_exit + || (!is_searching && Threads.use_sleeping_threads())) { - assert((!sp && threadID) || Threads.use_sleeping_threads()); - - if (do_terminate) + if (do_exit) { - assert(!sp); + assert(!sp_master); return; } // Grab the lock to avoid races with Thread::wake_up() - lock_grab(&sleepLock); + lock_grab(sleepLock); // If we are master and all slaves have finished don't go to sleep - if (sp && Threads.split_point_finished(sp)) + if (sp_master && !sp_master->slavesMask) { - lock_release(&sleepLock); + lock_release(sleepLock); break; } @@ -1908,54 +1807,58 @@ void Thread::idle_loop(SplitPoint* sp) { // in the meanwhile, allocated us and sent the wake_up() call before we // had the chance to grab the lock. if (do_sleep || !is_searching) - cond_wait(&sleepCond, &sleepLock); + cond_wait(sleepCond, sleepLock); - lock_release(&sleepLock); + lock_release(sleepLock); } // If this thread has been assigned work, launch a search if (is_searching) { - assert(!do_terminate); + assert(!do_sleep && !do_exit); + + lock_grab(Threads.splitLock); + + assert(is_searching); + SplitPoint* sp = curSplitPoint; + + lock_release(Threads.splitLock); - // Copy split point position and search stack and call search() Stack ss[MAX_PLY_PLUS_2]; - SplitPoint* tsp = splitPoint; - Position pos(*tsp->pos, threadID); - - memcpy(ss, tsp->ss - 1, 4 * sizeof(Stack)); - (ss+1)->sp = tsp; - - if (tsp->nodeType == Root) - search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); - else if (tsp->nodeType == PV) - search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); - else if (tsp->nodeType == NonPV) - search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); + Position pos(*sp->pos, this); + Thread* master = sp->master; + + memcpy(ss, sp->ss - 1, 4 * sizeof(Stack)); + (ss+1)->sp = sp; + + lock_grab(sp->lock); + + if (sp->nodeType == Root) + search(pos, ss+1, sp->alpha, sp->beta, sp->depth); + else if (sp->nodeType == PV) + search(pos, ss+1, sp->alpha, sp->beta, sp->depth); + else if (sp->nodeType == NonPV) + search(pos, ss+1, sp->alpha, sp->beta, sp->depth); else assert(false); assert(is_searching); is_searching = false; + sp->slavesMask &= ~(1ULL << idx); + sp->nodes += pos.nodes_searched(); + + // After releasing the lock we cannot access anymore any SplitPoint + // related data in a reliably way becuase it could have been released + // under our feet by the sp master. + lock_release(sp->lock); // Wake up master thread so to allow it to return from the idle loop in // case we are the last slave of the split point. if ( Threads.use_sleeping_threads() - && threadID != tsp->master - && !Threads[tsp->master].is_searching) - Threads[tsp->master].wake_up(); - } - - // If this thread is the master of a split point and all slaves have - // finished their work at this split point, return from the idle loop. - if (sp && Threads.split_point_finished(sp)) - { - // Because sp->is_slave[] is reset under lock protection, - // be sure sp->lock has been released before to return. - lock_grab(&(sp->lock)); - lock_release(&(sp->lock)); - return; + && this != master + && !master->is_searching) + master->wake_up(); } } } @@ -1967,18 +1870,18 @@ void Thread::idle_loop(SplitPoint* sp) { void check_time() { - static int lastInfoTime; - int e = elapsed_time(); + static Time lastInfoTime = Time::current_time(); - if (system_time() - lastInfoTime >= 1000 || !lastInfoTime) + if (lastInfoTime.elapsed() >= 1000) { - lastInfoTime = system_time(); + lastInfoTime.restart(); dbg_print(); } if (Limits.ponder) return; + int e = SearchTime.elapsed(); bool stillAtFirstMove = Signals.firstRootMove && !Signals.failedLowAtRoot && e > TimeMgr.available_time(); @@ -1987,7 +1890,6 @@ void check_time() { || stillAtFirstMove; if ( (Limits.use_time_management() && noMoreTime) - || (Limits.maxTime && e >= Limits.maxTime) - /* missing nodes limit */ ) // FIXME + || (Limits.movetime && e >= Limits.movetime)) Signals.stop = true; }