X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=93014bd0ac8a30bcf2288092192ab38638a35cd9;hp=ef247420d161345abb37ed6e18127a61db9c575b;hb=c19a6ef82d97840f3d5f06d587bce4f8b861b86d;hpb=af4fadebda5766b2c73a08227ddfb2911b43017e diff --git a/src/search.cpp b/src/search.cpp index ef247420..93014bd0 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-2010 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2008-2012 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 @@ -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,15 +40,22 @@ 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 std::string; +using Eval::evaluate; using namespace Search; +// For some reason argument-dependent lookup (ADL) doesn't work for Android's +// STLPort, so explicitly qualify following functions. +using std::count; +using std::find; + namespace { // Set to true to force running with one thread. Used for debugging @@ -59,35 +64,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) { - nodes = 0; - 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); - - int64_t nodes; - 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]; } @@ -96,7 +72,7 @@ namespace { const Depth RazorDepth = 4 * ONE_PLY; // Dynamic razoring margin based on depth - inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); } + inline Value razor_margin(Depth d) { return Value(512 + 16 * int(d)); } // Maximum depth for use of dynamic threat detection when null move fails low const Depth ThreatDepth = 5 * ONE_PLY; @@ -106,13 +82,13 @@ namespace { // At Non-PV nodes we do an internal iterative deepening search // when the static evaluation is bigger then beta - IIDMargin. - const Value IIDMargin = Value(0x100); + const Value IIDMargin = Value(256); // Minimum depth for use of singular extension const Depth SingularExtensionDepth[] = { 8 * ONE_PLY, 6 * ONE_PLY }; // Futility margin for quiescence search - const Value FutilityMarginQS = Value(0x80); + const Value FutilityMarginQS = Value(128); // Futility lookup tables (initialized at startup) and their access functions Value FutilityMargins[16][64]; // [depth][moveNumber] @@ -137,42 +113,37 @@ 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; int SkillLevel; - bool SkillLevelEnabled; + bool SkillLevelEnabled, Chess960; History H; - /// Local functions - - void id_loop(Position& pos); - template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); template Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); - bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue); + void id_loop(Position& pos); + 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); - void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount); + 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); @@ -192,51 +163,29 @@ namespace { MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, Stack* ss, Value b) : MovePicker(p, ttm, d, h, ss, b), mp(ss->sp->mp) {} - Move get_next_move() { return mp->get_next_move(); } + Move next_move() { return mp->next_move(); } MovePicker* mp; }; - // 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) { - - bool chess960 = (os.iword(0) != 0); // See set960() - return os << move_to_uci(m, chess960); - } - - // When formatting a move for std::cout we must know if we are in Chess960 or - // not. To keep using the handy operator<<() on the move the trick is to embed - // this flag in the stream itself. Function-like named enum set960 is used as - // a custom manipulator and the stream internal general-purpose array, accessed - // through ios_base::iword(), is used to pass the flag to the move's operator<< - // that will read it to properly format castling moves. - enum set960 {}; - - std::ostream& operator<<(std::ostream& os, const set960& f) { - - os.iword(0) = f; - return os; - } - // is_dangerous() checks whether a move belongs to some classes of known // 'dangerous' moves so that we avoid to prune it. 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(move_from(m))) == PAWN) + if (type_of(pos.piece_moved(m)) == PAWN) { Color c = pos.side_to_move(); - if ( relative_rank(c, move_to(m)) == RANK_7 - || pos.pawn_is_passed(c, move_to(m))) + if ( relative_rank(c, to_sq(m)) == RANK_7 + || pos.pawn_is_passed(c, to_sq(m))) return true; } // Test for a capture that triggers a pawn endgame - if ( captureOrPromotion - && type_of(pos.piece_on(move_to(m))) != PAWN + if ( captureOrPromotion + && type_of(pos.piece_on(to_sq(m))) != PAWN + && !is_special(m) && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) - - PieceValueMidgame[pos.piece_on(move_to(m))] == VALUE_ZERO) - && !is_special(m)) + - PieceValueMidgame[pos.piece_on(to_sq(m))] == VALUE_ZERO)) return true; return false; @@ -278,22 +227,22 @@ void Search::init() { int64_t Search::perft(Position& pos, Depth depth) { StateInfo st; - int64_t sum = 0; + int64_t cnt = 0; MoveList ml(pos); // At the last ply just return the number of moves (leaf nodes) - if (depth <= ONE_PLY) + if (depth == ONE_PLY) return ml.size(); CheckInfo ci(pos); for ( ; !ml.end(); ++ml) { pos.do_move(ml.move(), st, ci, pos.move_gives_check(ml.move(), ci)); - sum += perft(pos, depth - ONE_PLY); + cnt += perft(pos, depth - ONE_PLY); pos.undo_move(ml.move()); } - return sum; + return cnt; } @@ -306,94 +255,72 @@ void Search::think() { static Book book; // Defined static to initialize the PRNG only once Position& pos = RootPosition; - elapsed_time(true); - TimeMgr.init(Limits, pos.startpos_ply_counter()); + Chess960 = pos.is_chess960(); + 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() - || std::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; - // Set output stream mode: normal or chess960. Castling notation is different - cout << set960(pos.is_chess960()); + RootMoves.push_back(MOVE_NONE); + goto finalize; + } - if (Options["OwnBook"].value()) + if (Options["OwnBook"] && !Limits.infinite) { - if (Options["Book File"].value() != book.name()) - book.open(Options["Book File"].value()); + Move bookMove = book.probe(pos, Options["Book File"], Options["Best Book Move"]); - Move bookMove = book.probe(pos, Options["Best Book Move"].value()); - if (bookMove != MOVE_NONE) + if (bookMove && count(RootMoves.begin(), RootMoves.end(), bookMove)) { - if (!Signals.stop && (Limits.ponder || Limits.infinite)) - Threads.wait_for_stop_or_ponderhit(); - - cout << "bestmove " << bookMove << endl; - return; + std::swap(RootMoves[0], *find(RootMoves.begin(), RootMoves.end(), bookMove)); + goto finalize; } } - // 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"].value()); - if (Options["Clear Hash"].value()) - { - Options["Clear Hash"].set_value("false"); - TT.clear(); - } - - UCIMultiPV = Options["MultiPV"].value(); - SkillLevel = Options["Skill Level"].value(); + UCIMultiPV = Options["MultiPV"]; + SkillLevel = Options["Skill Level"]; // 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. SkillLevelEnabled = (SkillLevel < 20); MultiPV = (SkillLevelEnabled ? std::max(UCIMultiPV, (size_t)4) : UCIMultiPV); - if (Options["Use Search Log"].value()) + if (Options["Use Search Log"]) { - Log log(Options["Search Log Filename"].value()); + Log log(Options["Search Log Filename"]); 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. - if (TimeMgr.available_time()) - Threads.set_timer(std::min(100, std::max(TimeMgr.available_time() / 8, 20))); + if (Limits.use_time_management()) + Threads.set_timer(std::min(100, std::max(TimeMgr.available_time() / 16, TimerResolution))); else Threads.set_timer(100); // 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"].value()) + if (Options["Use Search Log"]) { - int e = elapsed_time(); + int e = SearchTime.elapsed(); - Log log(Options["Search Log Filename"].value()); + Log log(Options["Search Log Filename"]); log << "Nodes: " << pos.nodes_searched() << "\nNodes/second: " << (e > 0 ? pos.nodes_searched() * 1000 / e : 0) << "\nBest move: " << move_to_san(pos, RootMoves[0].pv[0]); @@ -404,21 +331,17 @@ void Search::think() { pos.undo_move(RootMoves[0].pv[0]); } - // 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. - if (!Signals.stop && (Limits.ponder || Limits.infinite)) - Threads.wait_for_stop_or_ponderhit(); +finalize: - // Could be MOVE_NONE when searching on a stalemate position - cout << "bestmove " << RootMoves[0].pv[0]; - - // 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 (RootMoves[0].pv[1] != MOVE_NONE) - cout << " ponder " << RootMoves[0].pv[1]; + // 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)) + pos.this_thread()->wait_for_stop_or_ponderhit(); - cout << endl; + // Best move could be MOVE_NONE when searching on a stalemate position + cout << "bestmove " << move_to_uci(RootMoves[0].pv[0], Chess960) + << " ponder " << move_to_uci(RootMoves[0].pv[1], Chess960) << endl; } @@ -430,7 +353,7 @@ namespace { void id_loop(Position& pos) { - Stack ss[PLY_MAX_PLUS_2]; + Stack ss[MAX_PLY_PLUS_2]; int depth, prevBestMoveChanges; Value bestValue, alpha, beta, delta; bool bestMoveNeverChanged = true; @@ -441,18 +364,8 @@ namespace { bestValue = delta = -VALUE_INFINITE; ss->currentMove = MOVE_NULL; // Hack to skip update gains - // Handle the special case of a mate/stalemate position - if (RootMoves.empty()) - { - cout << "info depth 0" - << 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 <= PLY_MAX && (!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. @@ -507,13 +420,13 @@ namespace { // If search has been stopped exit the aspiration window loop. // Sorting and writing PV back to TT is safe becuase RootMoves - // is still valid, although refers to previous iteration. + // is still valid, although refers to previous iteration. if (Signals.stop) break; // 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 @@ -543,15 +456,15 @@ namespace { if (SkillLevelEnabled && depth == 1 + SkillLevel) skillBest = do_skill_level(); - if (Options["Use Search Log"].value()) - 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) bestMoveNeverChanged = false; // Do we have time for the next iteration? Can we stop searching now? - if (!Signals.stop && !Signals.stopOnPonderhit && Limits.useTimeManagement()) + if (!Signals.stop && !Signals.stopOnPonderhit && Limits.use_time_management()) { bool stop = false; // Local variable, not the volatile Signals.stop @@ -562,19 +475,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; @@ -600,7 +513,7 @@ namespace { if (skillBest == MOVE_NONE) // Still unassigned ? skillBest = do_skill_level(); - std::swap(RootMoves[0], *std::find(RootMoves.begin(), RootMoves.end(), skillBest)); + std::swap(RootMoves[0], *find(RootMoves.begin(), RootMoves.end(), skillBest)); } } @@ -619,25 +532,23 @@ namespace { const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot); const bool RootNode = (NT == Root || NT == SplitPointRoot); - assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); - assert(beta > alpha && beta <= VALUE_INFINITE); - assert(PvNode || alpha == beta - 1); - assert(pos.thread() >= 0 && pos.thread() < Threads.size()); + assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE); + assert((alpha == beta - 1) || PvNode); + assert(depth > DEPTH_ZERO); - Move movesSearched[MAX_MOVES]; - int64_t nodes; + Move movesSearched[64]; 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* thisThread = pos.this_thread(); SplitPoint* sp = NULL; refinedValue = bestValue = value = -VALUE_INFINITE; @@ -646,36 +557,53 @@ namespace { ss->ply = (ss-1)->ply + 1; // Used to send selDepth info to GUI - if (PvNode && thread.maxPly < ss->ply) - thread.maxPly = ss->ply; + if (PvNode && thisThread->maxPly < ss->ply) + thisThread->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 > PLY_MAX) && !RootNode) + || ss->ply > MAX_PLY) && !RootNode) return VALUE_DRAW; - // Step 3. Mate distance pruning + // Step 3. Mate distance pruning. Even if we mate at the next move our score + // would be at best mate_in(ss->ply+1), but if alpha is already bigger because + // a shorter mate was found upward in the tree then there is no need to search + // further, we will never beat current alpha. Same logic but with reversed signs + // applies also in the opposite condition of being mated instead of giving mate, + // in this case return a fail-high score. if (!RootNode) { - alpha = std::max(value_mated_in(ss->ply), alpha); - beta = std::min(value_mate_in(ss->ply+1), beta); + alpha = std::max(mated_in(ss->ply), alpha); + beta = std::min(mate_in(ss->ply+1), beta); if (alpha >= beta) return alpha; } @@ -684,30 +612,30 @@ namespace { // We don't want the score of a partial search to overwrite a previous full search // TT value, so we use a different position key in case of an excluded move. excludedMove = ss->excludedMove; - posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key(); + 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 @@ -719,23 +647,23 @@ 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 // evaluation before and after the move. - if ( (move = (ss-1)->currentMove) != MOVE_NULL - && (ss-1)->eval != VALUE_NONE - && ss->eval != VALUE_NONE - && pos.captured_piece_type() == PIECE_TYPE_NONE + if ( (move = (ss-1)->currentMove) != MOVE_NULL + && (ss-1)->eval != VALUE_NONE + && ss->eval != VALUE_NONE + && !pos.captured_piece_type() && !is_special(move)) { - Square to = move_to(move); + Square to = to_sq(move); H.update_gain(pos.piece_on(to), to, -(ss-1)->eval - ss->eval); } @@ -745,8 +673,8 @@ namespace { && !inCheck && refinedValue + razor_margin(depth) < beta && ttMove == MOVE_NONE - && abs(beta) < VALUE_MATE_IN_PLY_MAX - && !pos.has_pawn_on_7th(pos.side_to_move())) + && abs(beta) < VALUE_MATE_IN_MAX_PLY + && !pos.pawn_on_7th(pos.side_to_move())) { Value rbeta = beta - razor_margin(depth); Value v = qsearch(pos, ss, rbeta-1, rbeta, DEPTH_ZERO); @@ -764,7 +692,7 @@ namespace { && depth < RazorDepth && !inCheck && refinedValue - futility_margin(depth, 0) >= beta - && abs(beta) < VALUE_MATE_IN_PLY_MAX + && abs(beta) < VALUE_MATE_IN_MAX_PLY && pos.non_pawn_material(pos.side_to_move())) return refinedValue - futility_margin(depth, 0); @@ -774,7 +702,7 @@ namespace { && depth > ONE_PLY && !inCheck && refinedValue >= beta - && abs(beta) < VALUE_MATE_IN_PLY_MAX + && abs(beta) < VALUE_MATE_IN_MAX_PLY && pos.non_pawn_material(pos.side_to_move())) { ss->currentMove = MOVE_NULL; @@ -796,7 +724,7 @@ namespace { if (nullValue >= beta) { // Do not return unproven mate scores - if (nullValue >= VALUE_MATE_IN_PLY_MAX) + if (nullValue >= VALUE_MATE_IN_MAX_PLY) nullValue = beta; if (depth < 6 * ONE_PLY) @@ -818,7 +746,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 @@ -837,19 +765,22 @@ namespace { && !inCheck && !ss->skipNullMove && excludedMove == MOVE_NONE - && abs(beta) < VALUE_MATE_IN_PLY_MAX) + && abs(beta) < VALUE_MATE_IN_MAX_PLY) { Value rbeta = beta + 200; 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); - while ((move = mp.get_next_move()) != MOVE_NONE) + 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); @@ -877,29 +808,21 @@ 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 + && depth >= SingularExtensionDepth[PvNode] + && ttMove != MOVE_NONE && !excludedMove // Recursive singular search is not allowed - && (tte->type() & VALUE_TYPE_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); - } + && (tte->type() & BOUND_LOWER) + && tte->depth() >= depth - 3 * ONE_PLY; // Step 11. Loop through moves // Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs - while ( bestValue < beta - && (move = mp.get_next_move()) != MOVE_NONE - && !thread.cutoff_occurred()) + while ( bestValue < beta + && (move = mp.next_move()) != MOVE_NONE + && !thisThread->cutoff_occurred() + && !Signals.stop) { assert(is_ok(move)); @@ -909,7 +832,7 @@ split_point_start: // At split points actual search starts from here // At root obey the "searchmoves" option and skip moves not listed in Root // Move List, as a consequence any illegal move is also skipped. In MultiPV // mode we also skip PV moves which have been already searched. - if (RootNode && !std::count(RootMoves.begin() + PVIdx, RootMoves.end(), move)) + if (RootNode && !count(RootMoves.begin() + PVIdx, RootMoves.end(), move)) continue; // At PV and SpNode nodes we want all moves to be legal since the beginning @@ -919,21 +842,18 @@ 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++; if (RootNode) { - // This is used by time management Signals.firstRootMove = (moveCount == 1); - nodes = pos.nodes_searched(); - - if (pos.thread() == 0 && elapsed_time() > 2000) + if (thisThread == Threads.main_thread() && SearchTime.elapsed() > 2000) cout << "info depth " << depth / ONE_PLY - << " currmove " << move + << " currmove " << move_to_uci(move, Chess960) << " currmovenumber " << moveCount + PVIdx << endl; } @@ -948,20 +868,18 @@ split_point_start: // At split points actual search starts from here ext = ONE_PLY; else if (givesCheck && pos.see_sign(move) >= 0) - ext = PvNode ? ONE_PLY : ONE_PLY / 2; + ext = ONE_PLY / 2; // Singular extension search. If all moves but one fail low on a search of // (alpha-s, beta-s), and just one fails high on (alpha, beta), then that move // is singular and should be extended. To verify this we do a reduced search // on all the other moves but the ttMove, if result is lower than ttValue minus // a margin then we extend ttMove. - if ( singularExtensionNode + if ( singularExtensionNode && !ext - && move == ttMove - && pos.pl_move_is_legal(move, ci.pinned)) + && 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); @@ -970,7 +888,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; } @@ -986,14 +903,14 @@ split_point_start: // At split points actual search starts from here && !dangerous && move != ttMove && !is_castle(move) - && (bestValue > VALUE_MATED_IN_PLY_MAX || bestValue == -VALUE_INFINITE)) + && (bestValue > VALUE_MATED_IN_MAX_PLY || bestValue == -VALUE_INFINITE)) { // Move count based pruning if ( moveCount >= futility_move_count(depth) && (!threatMove || !connected_threat(pos, move, threatMove))) { if (SpNode) - lock_grab(&(sp->lock)); + lock_grab(sp->lock); continue; } @@ -1003,12 +920,12 @@ 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(move_from(move)), move_to(move)); + + H.gain(pos.piece_moved(move), to_sq(move)); if (futilityValue < beta) { if (SpNode) - lock_grab(&(sp->lock)); + lock_grab(sp->lock); continue; } @@ -1018,7 +935,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; } @@ -1032,7 +949,7 @@ split_point_start: // At split points actual search starts from here } ss->currentMove = move; - if (!SpNode && !captureOrPromotion) + if (!SpNode && !captureOrPromotion && playedMoveCount < 64) movesSearched[playedMoveCount++] = move; // Step 14. Make the move @@ -1040,7 +957,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 > 3 * ONE_PLY && !isPvMove && !captureOrPromotion && !dangerous @@ -1049,11 +966,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; @@ -1084,19 +1000,18 @@ 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. if (RootNode && !Signals.stop) { - RootMove& rm = *std::find(RootMoves.begin(), RootMoves.end(), move); - rm.nodes += pos.nodes_searched() - nodes; + RootMove& rm = *find(RootMoves.begin(), RootMoves.end(), move); // PV move or new best move ? if (isPvMove || value > alpha) @@ -1121,79 +1036,84 @@ 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 && value < beta) // We want always alpha < beta alpha = value; - if (SpNode && !thread.cutoff_occurred()) + if (SpNode && !thisThread->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; } } // Step 19. Check for split if ( !SpNode - && depth >= Threads.min_split_depth() - && bestValue < beta - && Threads.available_slave_exists(pos.thread()) + && depth >= Threads.min_split_depth() + && bestValue < beta + && Threads.available_slave_exists(thisThread) && !Signals.stop - && !thread.cutoff_occurred()) - bestValue = Threads.split(pos, ss, alpha, beta, bestValue, depth, - threatMove, moveCount, &mp, NT); + && !thisThread->cutoff_occurred()) + 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) - return excludedMove ? oldAlpha : inCheck ? value_mated_in(ss->ply) : VALUE_DRAW; + return excludedMove ? oldAlpha : inCheck ? mated_in(ss->ply) : VALUE_DRAW; // If we have pruned all the moves without searching return a fail-low score if (bestValue == -VALUE_INFINITE) { assert(!playedMoveCount); - bestValue = alpha; + bestValue = oldAlpha; } // Step 21. Update tables - // Update transposition table entry, history and killers - if (!SpNode && !Signals.stop && !thread.cutoff_occurred()) + // Update transposition table entry, killers and history + if (!SpNode && !Signals.stop && !thisThread->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 only for non capture moves that fails high + // Update killers and history for non capture cut-off moves if ( bestValue >= beta - && !pos.is_capture_or_promotion(move)) + && !pos.is_capture_or_promotion(move) + && !inCheck) { if (move != ss->killers[0]) { ss->killers[1] = ss->killers[0]; ss->killers[0] = move; } - update_history(pos, move, depth, movesSearched, playedMoveCount); - } - } - if (SpNode) - { - // Here we have the lock still grabbed - sp->is_slave[pos.thread()] = false; - sp->nodes += pos.nodes_searched(); - lock_release(&(sp->lock)); + // Increase history value of the cut-off move + Value bonus = Value(int(depth) * int(depth)); + 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_moved(m), to_sq(m), -bonus); + } + } } assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1212,26 +1132,24 @@ split_point_start: // At split points actual search starts from here const bool PvNode = (NT == PV); assert(NT == PV || NT == NonPV); - assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); - assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE); - assert(PvNode || alpha == beta - 1); - assert(depth <= 0); - assert(pos.thread() >= 0 && pos.thread() < Threads.size()); + assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE); + assert((alpha == beta - 1) || PvNode); + assert(depth <= DEPTH_ZERO); 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 - if (pos.is_draw() || ss->ply > PLY_MAX) + if (pos.is_draw() || ss->ply > MAX_PLY) return VALUE_DRAW; // Decide whether or not to include checks, this fixes also the type of @@ -1242,13 +1160,14 @@ split_point_start: // At split points actual search starts from here // Transposition table lookup. At PV nodes, we don't use the TT for // pruning, but only for move ordering. - tte = TT.probe(pos.get_key()); + 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 @@ -1274,7 +1193,7 @@ split_point_start: // At split points actual search starts from here if (bestValue >= beta) { if (!tte) - TT.store(pos.get_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; } @@ -1290,12 +1209,12 @@ 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, move_to((ss-1)->currentMove)); + MovePicker mp(pos, ttMove, depth, H, to_sq((ss-1)->currentMove)); CheckInfo ci(pos); // Loop through the moves until no moves remain or a beta cutoff occurs while ( bestValue < beta - && (move = mp.get_next_move()) != MOVE_NONE) + && (move = mp.next_move()) != MOVE_NONE) { assert(is_ok(move)); @@ -1311,7 +1230,7 @@ split_point_start: // At split points actual search starts from here && !pos.is_passed_pawn_push(move)) { futilityValue = futilityBase - + PieceValueEndgame[pos.piece_on(move_to(move))] + + PieceValueEndgame[pos.piece_on(to_sq(move))] + (is_enpassant(move) ? PawnValueEndgame : VALUE_ZERO); if (futilityValue < beta) @@ -1331,8 +1250,8 @@ split_point_start: // At split points actual search starts from here // Detect non-capture evasions that are candidate to be pruned evasionPrunable = !PvNode - && inCheck - && bestValue > VALUE_MATED_IN_PLY_MAX + && inCheck + && bestValue > VALUE_MATED_IN_MAX_PLY && !pos.is_capture(move) && !pos.can_castle(pos.side_to_move()); @@ -1351,13 +1270,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)) @@ -1376,7 +1290,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 @@ -1388,14 +1302,14 @@ split_point_start: // At split points actual search starts from here // All legal moves have been searched. A special case: If we're in check // and no legal moves were found, it is checkmate. if (inCheck && bestValue == -VALUE_INFINITE) - return value_mated_in(ss->ply); + 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.get_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); @@ -1407,55 +1321,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 = move_from(move); - to = move_to(move); - them = flip(pos.side_to_move()); + 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 (!more_than_one(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; } @@ -1476,67 +1378,64 @@ split_point_start: // At split points actual search starts from here assert(is_ok(m2)); // Case 1: The moving piece is the same in both moves - f2 = move_from(m2); - t1 = move_to(m1); + f2 = from_sq(m2); + t1 = to_sq(m1); if (f2 == t1) return true; // Case 2: The destination square for m2 was vacated by m1 - t2 = move_to(m2); - f1 = move_from(m1); + t2 = to_sq(m2); + f1 = from_sq(m1); if (t2 == f1) return true; // 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) && (between_bb(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; - } + && (between_bb(t1, ksq) & f2) + && (pos.attacks_from(p1, t1, pos.pieces() ^ f2) & ksq)) + return true; + return false; } // value_to_tt() adjusts a mate score from "plies to mate from the root" to - // "plies to mate from the current ply". Non-mate scores are unchanged. + // "plies to mate from the current position". Non-mate scores are unchanged. // The function is called before storing a value to the transposition table. Value value_to_tt(Value v, int ply) { - if (v >= VALUE_MATE_IN_PLY_MAX) + if (v >= VALUE_MATE_IN_MAX_PLY) return v + ply; - if (v <= VALUE_MATED_IN_PLY_MAX) + if (v <= VALUE_MATED_IN_MAX_PLY) return v - ply; return v; } - // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from - // the transposition table to a mate score corrected for the current ply. + // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score + // from the transposition table (where refers to the plies to mate/be mated + // from current position) to "plies to mate/be mated from the root". Value value_from_tt(Value v, int ply) { - if (v >= VALUE_MATE_IN_PLY_MAX) + if (v >= VALUE_MATE_IN_MAX_PLY) return v - ply; - if (v <= VALUE_MATED_IN_PLY_MAX) + if (v <= VALUE_MATED_IN_MAX_PLY) return v + ply; return v; @@ -1555,10 +1454,10 @@ split_point_start: // At split points actual search starts from here Square mfrom, mto, tfrom, tto; - mfrom = move_from(m); - mto = move_to(m); - tfrom = move_from(threat); - tto = move_to(threat); + mfrom = from_sq(m); + mto = to_sq(m); + tfrom = from_sq(threat); + tto = to_sq(threat); // Case 1: Don't prune moves which move the threatened piece if (mfrom == tto) @@ -1574,9 +1473,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)) + && (between_bb(tfrom, tto) & mto) + && pos.see_sign(m) >= 0) return true; return false; @@ -1586,71 +1485,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_PLY_MAX, beta) - || v < std::min(VALUE_MATED_IN_PLY_MAX, beta)) + || 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; } - // update_history() registers a good move that produced a beta-cutoff in - // history and marks as failures all the other moves of that ply. - - void update_history(const Position& pos, Move move, Depth depth, - Move movesSearched[], int moveCount) { - Move m; - Value bonus = Value(int(depth) * int(depth)); - - H.update(pos.piece_on(move_from(move)), move_to(move), bonus); - - for (int i = 0; i < moveCount - 1; i++) - { - m = movesSearched[i]; - - assert(m != move); - - H.update(pos.piece_on(move_from(m)), move_to(m), -bonus); - } - } - - - // 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 = get_system_time(); - - return get_system_time() - searchStartTime; - } - - // score_to_uci() converts a value to a string suitable for use with the UCI // protocol specifications: // @@ -1662,10 +1522,10 @@ split_point_start: // At split points actual search starts from here std::stringstream s; - if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY) - s << " score cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to centipawns + if (abs(v) < VALUE_MATE_IN_MAX_PLY) + s << "cp " << v * 100 / int(PawnValueMidgame); else - s << " score mate " << (v > 0 ? VALUE_MATE - v + 1 : -VALUE_MATE - v) / 2; + s << "mate " << (v > 0 ? VALUE_MATE - v + 1 : -VALUE_MATE - v) / 2; s << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : ""); @@ -1679,7 +1539,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++) @@ -1694,21 +1554,20 @@ split_point_start: // At split points actual search starts from here continue; int d = (updated ? depth : depth - 1); - Value s = (updated ? RootMoves[i].score : RootMoves[i].prevScore); + Value v = (updated ? RootMoves[i].score : RootMoves[i].prevScore); + std::stringstream s; - cout << "info" - << " depth " << d + for (int j = 0; RootMoves[i].pv[j] != MOVE_NONE; j++) + s << " " << move_to_uci(RootMoves[i].pv[j], Chess960); + + cout << "info depth " << d << " seldepth " << selDepth - << (i == PVIdx ? score_to_uci(s, alpha, beta) : score_to_uci(s)) + << " score " << (i == PVIdx ? score_to_uci(v, alpha, beta) : score_to_uci(v)) << " nodes " << pos.nodes_searched() << " nps " << (t > 0 ? pos.nodes_searched() * 1000 / t : 0) << " time " << t - << " multipv " << i + 1 << " pv"; - - for (int j = 0; RootMoves[i].pv[j] != MOVE_NONE; j++) - cout << " " << RootMoves[i].pv[j]; - - cout << endl; + << " multipv " << i + 1 + << " pv" << s.str() << endl; } } @@ -1740,9 +1599,9 @@ split_point_start: // At split points actual search starts from here std::stringstream s; - if (v >= VALUE_MATE_IN_PLY_MAX) + if (v >= VALUE_MATE_IN_MAX_PLY) s << "#" << (VALUE_MATE - v + 1) / 2; - else if (v <= VALUE_MATED_IN_PLY_MAX) + else if (v <= VALUE_MATED_IN_MAX_PLY) s << "-#" << (VALUE_MATE + v) / 2; else s << std::setprecision(2) << std::fixed << std::showpos @@ -1756,14 +1615,13 @@ split_point_start: // At split points actual search starts from here const int64_t K = 1000; const int64_t M = 1000000; - StateInfo state[PLY_MAX_PLUS_2], *st = state; + StateInfo state[MAX_PLY_PLUS_2], *st = state; Move* m = pv; string san, padding; size_t length; std::stringstream s; - s << set960(pos.is_chess960()) - << std::setw(2) << depth + s << std::setw(2) << depth << std::setw(8) << score_to_string(value) << std::setw(8) << time_to_string(time); @@ -1798,7 +1656,7 @@ split_point_start: // At split points actual search starts from here while (m != pv) pos.undo_move(*--m); - Log l(Options["Search Log Filename"].value()); + Log l(Options["Search Log Filename"]); l << s.str() << endl; } @@ -1813,10 +1671,10 @@ split_point_start: // At split points actual search starts from here static RKISS rk; // PRNG sequence should be not deterministic - for (int i = abs(get_system_time() % 50); i > 0; i--) + for (int i = Time::current_time().msec() % 50; i > 0; i--) rk.rand(); - // Rml list is already sorted by score in descending order + // RootMoves are already sorted by score in descending order size_t size = std::min(MultiPV, RootMoves.size()); int variance = std::min(RootMoves[0].score - RootMoves[size - 1].score, PawnValueMidgame); int weakness = 120 - 2 * SkillLevel; @@ -1847,105 +1705,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[PLY_MAX_PLUS_2], *st = state; - TTEntry* tte; - int ply = 1; - Move m = pv[0]; +void RootMove::extract_pv_from_tt(Position& pos) { - assert(m != MOVE_NONE && pos.is_pseudo_legal(m)); + StateInfo state[MAX_PLY_PLUS_2], *st = state; + TTEntry* tte; + int ply = 1; + Move m = pv[0]; - pv.clear(); - pv.push_back(m); - pos.do_move(m, *st++); + assert(m != MOVE_NONE && pos.is_pseudo_legal(m)); - while ( (tte = TT.probe(pos.get_key())) != NULL - && tte->move() != MOVE_NONE - && pos.is_pseudo_legal(tte->move()) - && pos.pl_move_is_legal(tte->move(), pos.pinned_pieces()) - && ply < PLY_MAX - && (!pos.is_draw() || ply < 2)) - { - pv.push_back(tte->move()); - pos.do_move(tte->move(), *st++); - ply++; - } - pv.push_back(MOVE_NONE); + 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[PLY_MAX_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.get_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; } @@ -1954,88 +1812,89 @@ 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); - - // Copy split point position and search stack and call search() - Stack ss[PLY_MAX_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); + assert(!do_sleep && !do_exit); + + lock_grab(Threads.splitLock); + + assert(is_searching); + SplitPoint* sp = curSplitPoint; + + lock_release(Threads.splitLock); + + Stack ss[MAX_PLY_PLUS_2]; + Position pos(*sp->pos, this); + + 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(); // 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; + if ( Threads.use_sleeping_threads() + && this != sp->master + && !sp->master->is_searching) + sp->master->wake_up(); + + // After releasing the lock we cannot access anymore any SplitPoint + // related data in a safe way becuase it could have been released under + // our feet by the sp master. Also accessing other Thread objects is + // unsafe because if we are exiting there is a chance are already freed. + lock_release(sp->lock); } } } -/// do_timer_event() is called by the timer thread when the timer triggers. It -/// is used to print debug info and, more important, to detect when we are out of +/// check_time() is called by the timer thread when the timer triggers. It is +/// used to print debug info and, more important, to detect when we are out of /// available time and so stop the search. -void do_timer_event() { +void check_time() { - static int lastInfoTime; - int e = elapsed_time(); + static Time lastInfoTime = Time::current_time(); - if (get_system_time() - lastInfoTime >= 1000 || !lastInfoTime) + if (lastInfoTime.elapsed() >= 1000) { - lastInfoTime = get_system_time(); - - dbg_print_mean(); - dbg_print_hit_rate(); + lastInfoTime.restart(); + dbg_print(); } if (Limits.ponder) return; + int e = SearchTime.elapsed(); bool stillAtFirstMove = Signals.firstRootMove && !Signals.failedLowAtRoot && e > TimeMgr.available_time(); - bool noMoreTime = e > TimeMgr.maximum_time() + bool noMoreTime = e > TimeMgr.maximum_time() - 2 * TimerResolution || stillAtFirstMove; - if ( (Limits.useTimeManagement() && noMoreTime) - || (Limits.maxTime && e >= Limits.maxTime) - /* missing nodes limit */ ) // FIXME + if ( (Limits.use_time_management() && noMoreTime) + || (Limits.movetime && e >= Limits.movetime)) Signals.stop = true; }