Subversion Repositories Games.Chess Giants

Rev

Rev 169 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
  3.   Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
  4.   Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad
  5.   Copyright (C) 2015-2019 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
  6.  
  7.   Stockfish is free software: you can redistribute it and/or modify
  8.   it under the terms of the GNU General Public License as published by
  9.   the Free Software Foundation, either version 3 of the License, or
  10.   (at your option) any later version.
  11.  
  12.   Stockfish is distributed in the hope that it will be useful,
  13.   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14.   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15.   GNU General Public License for more details.
  16.  
  17.   You should have received a copy of the GNU General Public License
  18.   along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19. */
  20.  
  21. #include <algorithm>
  22. #include <cassert>
  23. #include <cmath>
  24. #include <cstring>   // For std::memset
  25. #include <iostream>
  26. #include <sstream>
  27.  
  28. #include "evaluate.h"
  29. #include "misc.h"
  30. #include "movegen.h"
  31. #include "movepick.h"
  32. #include "position.h"
  33. #include "search.h"
  34. #include "thread.h"
  35. #include "timeman.h"
  36. #include "tt.h"
  37. #include "uci.h"
  38. #include "syzygy/tbprobe.h"
  39.  
  40. namespace Search {
  41.  
  42.   LimitsType Limits;
  43. }
  44.  
  45. namespace Tablebases {
  46.  
  47.   int Cardinality;
  48.   bool RootInTB;
  49.   bool UseRule50;
  50.   Depth ProbeDepth;
  51. }
  52.  
  53. namespace TB = Tablebases;
  54.  
  55. using std::string;
  56. using Eval::evaluate;
  57. using namespace Search;
  58.  
  59. namespace {
  60.  
  61.   // Different node types, used as a template parameter
  62.   enum NodeType { NonPV, PV };
  63.  
  64.   // Sizes and phases of the skip-blocks, used for distributing search depths across the threads
  65.   constexpr int SkipSize[]  = { 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4 };
  66.   constexpr int SkipPhase[] = { 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 7 };
  67.  
  68.   // Razor and futility margins
  69.   constexpr int RazorMargin = 600;
  70.   Value futility_margin(Depth d, bool improving) {
  71.     return Value((175 - 50 * improving) * d / ONE_PLY);
  72.   }
  73.  
  74.   // Futility and reductions lookup tables, initialized at startup
  75.   int FutilityMoveCounts[2][16]; // [improving][depth]
  76.   int Reductions[2][2][64][64];  // [pv][improving][depth][moveNumber]
  77.  
  78.   template <bool PvNode> Depth reduction(bool i, Depth d, int mn) {
  79.     return Reductions[PvNode][i][std::min(d / ONE_PLY, 63)][std::min(mn, 63)] * ONE_PLY;
  80.   }
  81.  
  82.   // History and stats update bonus, based on depth
  83.   int stat_bonus(Depth depth) {
  84.     int d = depth / ONE_PLY;
  85.     return d > 17 ? 0 : 29 * d * d + 138 * d - 134;
  86.   }
  87.  
  88.   // Add a small random component to draw evaluations to keep search dynamic
  89.   // and to avoid 3fold-blindness.
  90.   Value value_draw(Depth depth, Thread* thisThread) {
  91.     return depth < 4 ? VALUE_DRAW
  92.                      : VALUE_DRAW + Value(2 * (thisThread->nodes.load(std::memory_order_relaxed) % 2) - 1);
  93.   }
  94.  
  95.   // Skill structure is used to implement strength limit
  96.   struct Skill {
  97.     explicit Skill(int l) : level(l) {}
  98.     bool enabled() const { return level < 20; }
  99.     bool time_to_pick(Depth depth) const { return depth / ONE_PLY == 1 + level; }
  100.     Move pick_best(size_t multiPV);
  101.  
  102.     int level;
  103.     Move best = MOVE_NONE;
  104.   };
  105.  
  106.   template <NodeType NT>
  107.   Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode);
  108.  
  109.   template <NodeType NT>
  110.   Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth = DEPTH_ZERO);
  111.  
  112.   Value value_to_tt(Value v, int ply);
  113.   Value value_from_tt(Value v, int ply);
  114.   void update_pv(Move* pv, Move move, Move* childPv);
  115.   void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus);
  116.   void update_quiet_stats(const Position& pos, Stack* ss, Move move, Move* quiets, int quietsCnt, int bonus);
  117.   void update_capture_stats(const Position& pos, Move move, Move* captures, int captureCnt, int bonus);
  118.  
  119.   inline bool gives_check(const Position& pos, Move move) {
  120.     Color us = pos.side_to_move();
  121.     return  type_of(move) == NORMAL && !(pos.blockers_for_king(~us) & pos.pieces(us))
  122.           ? pos.check_squares(type_of(pos.moved_piece(move))) & to_sq(move)
  123.           : pos.gives_check(move);
  124.   }
  125.  
  126.   // perft() is our utility to verify move generation. All the leaf nodes up
  127.   // to the given depth are generated and counted, and the sum is returned.
  128.   template<bool Root>
  129.   uint64_t perft(Position& pos, Depth depth) {
  130.  
  131.     StateInfo st;
  132.     uint64_t cnt, nodes = 0;
  133.     const bool leaf = (depth == 2 * ONE_PLY);
  134.  
  135.     for (const auto& m : MoveList<LEGAL>(pos))
  136.     {
  137.         if (Root && depth <= ONE_PLY)
  138.             cnt = 1, nodes++;
  139.         else
  140.         {
  141.             pos.do_move(m, st);
  142.             cnt = leaf ? MoveList<LEGAL>(pos).size() : perft<false>(pos, depth - ONE_PLY);
  143.             nodes += cnt;
  144.             pos.undo_move(m);
  145.         }
  146.         if (Root)
  147.             sync_cout << UCI::move(m, pos.is_chess960()) << ": " << cnt << sync_endl;
  148.     }
  149.     return nodes;
  150.   }
  151.  
  152. } // namespace
  153.  
  154.  
  155. /// Search::init() is called at startup to initialize various lookup tables
  156.  
  157. void Search::init() {
  158.  
  159.   for (int imp = 0; imp <= 1; ++imp)
  160.       for (int d = 1; d < 64; ++d)
  161.           for (int mc = 1; mc < 64; ++mc)
  162.           {
  163.               double r = log(d) * log(mc) / 1.95;
  164.  
  165.               Reductions[NonPV][imp][d][mc] = int(std::round(r));
  166.               Reductions[PV][imp][d][mc] = std::max(Reductions[NonPV][imp][d][mc] - 1, 0);
  167.  
  168.               // Increase reduction for non-PV nodes when eval is not improving
  169.               if (!imp && r > 1.0)
  170.                 Reductions[NonPV][imp][d][mc]++;
  171.           }
  172.  
  173.   for (int d = 0; d < 16; ++d)
  174.   {
  175.       FutilityMoveCounts[0][d] = int(2.4 + 0.74 * pow(d, 1.78));
  176.       FutilityMoveCounts[1][d] = int(5.0 + 1.00 * pow(d, 2.00));
  177.   }
  178. }
  179.  
  180.  
  181. /// Search::clear() resets search state to its initial value
  182.  
  183. void Search::clear() {
  184.  
  185.   Threads.main()->wait_for_search_finished();
  186.  
  187.   Time.availableNodes = 0;
  188.   TT.clear();
  189.   Threads.clear();
  190.   Tablebases::init(Options["SyzygyPath"]); // Free up mapped files
  191. }
  192.  
  193.  
  194. /// MainThread::search() is called by the main thread when the program receives
  195. /// the UCI 'go' command. It searches from the root position and outputs the "bestmove".
  196.  
  197. void MainThread::search() {
  198.  
  199.   if (Limits.perft)
  200.   {
  201.       nodes = perft<true>(rootPos, Limits.perft * ONE_PLY);
  202.       sync_cout << "\nNodes searched: " << nodes << "\n" << sync_endl;
  203.       return;
  204.   }
  205.  
  206.   Color us = rootPos.side_to_move();
  207.   Time.init(Limits, us, rootPos.game_ply());
  208.   TT.new_search();
  209.  
  210.   if (rootMoves.empty())
  211.   {
  212.       rootMoves.emplace_back(MOVE_NONE);
  213.       sync_cout << "info depth 0 score "
  214.                 << UCI::value(rootPos.checkers() ? -VALUE_MATE : VALUE_DRAW)
  215.                 << sync_endl;
  216.   }
  217.   else
  218.   {
  219.       for (Thread* th : Threads)
  220.           if (th != this)
  221.               th->start_searching();
  222.  
  223.       Thread::search(); // Let's start searching!
  224.   }
  225.  
  226.   // When we reach the maximum depth, we can arrive here without a raise of
  227.   // Threads.stop. However, if we are pondering or in an infinite search,
  228.   // the UCI protocol states that we shouldn't print the best move before the
  229.   // GUI sends a "stop" or "ponderhit" command. We therefore simply wait here
  230.   // until the GUI sends one of those commands (which also raises Threads.stop).
  231.   Threads.stopOnPonderhit = true;
  232.  
  233.   while (!Threads.stop && (Threads.ponder || Limits.infinite))
  234.   {} // Busy wait for a stop or a ponder reset
  235.  
  236.   // Stop the threads if not already stopped (also raise the stop if
  237.   // "ponderhit" just reset Threads.ponder).
  238.   Threads.stop = true;
  239.  
  240.   // Wait until all threads have finished
  241.   for (Thread* th : Threads)
  242.       if (th != this)
  243.           th->wait_for_search_finished();
  244.  
  245.   // When playing in 'nodes as time' mode, subtract the searched nodes from
  246.   // the available ones before exiting.
  247.   if (Limits.npmsec)
  248.       Time.availableNodes += Limits.inc[us] - Threads.nodes_searched();
  249.  
  250.   // Check if there are threads with a better score than main thread
  251.   Thread* bestThread = this;
  252.   if (    Options["MultiPV"] == 1
  253.       && !Limits.depth
  254.       && !Skill(Options["Skill Level"]).enabled()
  255.       &&  rootMoves[0].pv[0] != MOVE_NONE)
  256.   {
  257.       std::map<Move, int> votes;
  258.       Value minScore = this->rootMoves[0].score;
  259.  
  260.       // Find out minimum score and reset votes for moves which can be voted
  261.       for (Thread* th: Threads)
  262.       {
  263.           minScore = std::min(minScore, th->rootMoves[0].score);
  264.           votes[th->rootMoves[0].pv[0]] = 0;
  265.       }
  266.  
  267.       // Vote according to score and depth
  268.       for (Thread* th : Threads)
  269.           votes[th->rootMoves[0].pv[0]] +=  int(th->rootMoves[0].score - minScore)
  270.                                           + int(th->completedDepth);
  271.  
  272.       // Select best thread
  273.       int bestVote = votes[this->rootMoves[0].pv[0]];
  274.       for (Thread* th : Threads)
  275.       {
  276.           if (votes[th->rootMoves[0].pv[0]] > bestVote)
  277.           {
  278.               bestVote = votes[th->rootMoves[0].pv[0]];
  279.               bestThread = th;
  280.           }
  281.       }
  282.   }
  283.  
  284.   previousScore = bestThread->rootMoves[0].score;
  285.  
  286.   // Send again PV info if we have a new best thread
  287.   if (bestThread != this)
  288.       sync_cout << UCI::pv(bestThread->rootPos, bestThread->completedDepth, -VALUE_INFINITE, VALUE_INFINITE) << sync_endl;
  289.  
  290.   sync_cout << "bestmove " << UCI::move(bestThread->rootMoves[0].pv[0], rootPos.is_chess960());
  291.  
  292.   if (bestThread->rootMoves[0].pv.size() > 1 || bestThread->rootMoves[0].extract_ponder_from_tt(rootPos))
  293.       std::cout << " ponder " << UCI::move(bestThread->rootMoves[0].pv[1], rootPos.is_chess960());
  294.  
  295.   std::cout << sync_endl;
  296. }
  297.  
  298.  
  299. /// Thread::search() is the main iterative deepening loop. It calls search()
  300. /// repeatedly with increasing depth until the allocated thinking time has been
  301. /// consumed, the user stops the search, or the maximum search depth is reached.
  302.  
  303. void Thread::search() {
  304.  
  305.   Stack stack[MAX_PLY+7], *ss = stack+4; // To reference from (ss-4) to (ss+2)
  306.   Value bestValue, alpha, beta, delta;
  307.   Move  lastBestMove = MOVE_NONE;
  308.   Depth lastBestMoveDepth = DEPTH_ZERO;
  309.   MainThread* mainThread = (this == Threads.main() ? Threads.main() : nullptr);
  310.   double timeReduction = 1.0;
  311.   Color us = rootPos.side_to_move();
  312.   bool failedLow;
  313.  
  314.   std::memset(ss-4, 0, 7 * sizeof(Stack));
  315.   for (int i = 4; i > 0; i--)
  316.      (ss-i)->continuationHistory = &this->continuationHistory[NO_PIECE][0]; // Use as sentinel
  317.  
  318.   bestValue = delta = alpha = -VALUE_INFINITE;
  319.   beta = VALUE_INFINITE;
  320.  
  321.   if (mainThread)
  322.       mainThread->bestMoveChanges = 0, failedLow = false;
  323.  
  324.   size_t multiPV = Options["MultiPV"];
  325.   Skill skill(Options["Skill Level"]);
  326.  
  327.   // When playing with strength handicap enable MultiPV search that we will
  328.   // use behind the scenes to retrieve a set of possible moves.
  329.   if (skill.enabled())
  330.       multiPV = std::max(multiPV, (size_t)4);
  331.  
  332.   multiPV = std::min(multiPV, rootMoves.size());
  333.  
  334.   int ct = int(Options["Contempt"]) * PawnValueEg / 100; // From centipawns
  335.  
  336.   // In analysis mode, adjust contempt in accordance with user preference
  337.   if (Limits.infinite || Options["UCI_AnalyseMode"])
  338.       ct =  Options["Analysis Contempt"] == "Off"  ? 0
  339.           : Options["Analysis Contempt"] == "Both" ? ct
  340.           : Options["Analysis Contempt"] == "White" && us == BLACK ? -ct
  341.           : Options["Analysis Contempt"] == "Black" && us == WHITE ? -ct
  342.           : ct;
  343.  
  344.   // In evaluate.cpp the evaluation is from the white point of view
  345.   contempt = (us == WHITE ?  make_score(ct, ct / 2)
  346.                           : -make_score(ct, ct / 2));
  347.  
  348.   // Iterative deepening loop until requested to stop or the target depth is reached
  349.   while (   (rootDepth += ONE_PLY) < DEPTH_MAX
  350.          && !Threads.stop
  351.          && !(Limits.depth && mainThread && rootDepth / ONE_PLY > Limits.depth))
  352.   {
  353.       // Distribute search depths across the helper threads
  354.       if (idx > 0)
  355.       {
  356.           int i = (idx - 1) % 20;
  357.           if (((rootDepth / ONE_PLY + SkipPhase[i]) / SkipSize[i]) % 2)
  358.               continue;  // Retry with an incremented rootDepth
  359.       }
  360.  
  361.       // Age out PV variability metric
  362.       if (mainThread)
  363.           mainThread->bestMoveChanges *= 0.517, failedLow = false;
  364.  
  365.       // Save the last iteration's scores before first PV line is searched and
  366.       // all the move scores except the (new) PV are set to -VALUE_INFINITE.
  367.       for (RootMove& rm : rootMoves)
  368.           rm.previousScore = rm.score;
  369.  
  370.       size_t pvFirst = 0;
  371.       pvLast = 0;
  372.  
  373.       // MultiPV loop. We perform a full root search for each PV line
  374.       for (pvIdx = 0; pvIdx < multiPV && !Threads.stop; ++pvIdx)
  375.       {
  376.           if (pvIdx == pvLast)
  377.           {
  378.               pvFirst = pvLast;
  379.               for (pvLast++; pvLast < rootMoves.size(); pvLast++)
  380.                   if (rootMoves[pvLast].tbRank != rootMoves[pvFirst].tbRank)
  381.                       break;
  382.           }
  383.  
  384.           // Reset UCI info selDepth for each depth and each PV line
  385.           selDepth = 0;
  386.  
  387.           // Reset aspiration window starting size
  388.           if (rootDepth >= 5 * ONE_PLY)
  389.           {
  390.               Value previousScore = rootMoves[pvIdx].previousScore;
  391.               delta = Value(20);
  392.               alpha = std::max(previousScore - delta,-VALUE_INFINITE);
  393.               beta  = std::min(previousScore + delta, VALUE_INFINITE);
  394.  
  395.               // Adjust contempt based on root move's previousScore (dynamic contempt)
  396.               int dct = ct + 88 * previousScore / (abs(previousScore) + 200);
  397.  
  398.               contempt = (us == WHITE ?  make_score(dct, dct / 2)
  399.                                       : -make_score(dct, dct / 2));
  400.           }
  401.  
  402.           // Start with a small aspiration window and, in the case of a fail
  403.           // high/low, re-search with a bigger window until we don't fail
  404.           // high/low anymore.
  405.           int failedHighCnt = 0;
  406.           while (true)
  407.           {
  408.               Depth adjustedDepth = std::max(ONE_PLY, rootDepth - failedHighCnt * ONE_PLY);
  409.               bestValue = ::search<PV>(rootPos, ss, alpha, beta, adjustedDepth, false);
  410.  
  411.               // Bring the best move to the front. It is critical that sorting
  412.               // is done with a stable algorithm because all the values but the
  413.               // first and eventually the new best one are set to -VALUE_INFINITE
  414.               // and we want to keep the same order for all the moves except the
  415.               // new PV that goes to the front. Note that in case of MultiPV
  416.               // search the already searched PV lines are preserved.
  417.               std::stable_sort(rootMoves.begin() + pvIdx, rootMoves.begin() + pvLast);
  418.  
  419.               // If search has been stopped, we break immediately. Sorting is
  420.               // safe because RootMoves is still valid, although it refers to
  421.               // the previous iteration.
  422.               if (Threads.stop)
  423.                   break;
  424.  
  425.               // When failing high/low give some update (without cluttering
  426.               // the UI) before a re-search.
  427.               if (   mainThread
  428.                   && multiPV == 1
  429.                   && (bestValue <= alpha || bestValue >= beta)
  430.                   && Time.elapsed() > 3000)
  431.                   sync_cout << UCI::pv(rootPos, rootDepth, alpha, beta) << sync_endl;
  432.  
  433.               // In case of failing low/high increase aspiration window and
  434.               // re-search, otherwise exit the loop.
  435.               if (bestValue <= alpha)
  436.               {
  437.                   beta = (alpha + beta) / 2;
  438.                   alpha = std::max(bestValue - delta, -VALUE_INFINITE);
  439.  
  440.                   if (mainThread)
  441.                   {
  442.                       failedHighCnt = 0;
  443.                       failedLow = true;
  444.                       Threads.stopOnPonderhit = false;
  445.                   }
  446.               }
  447.               else if (bestValue >= beta)
  448.               {
  449.                   beta = std::min(bestValue + delta, VALUE_INFINITE);
  450.                   if (mainThread)
  451.                           ++failedHighCnt;
  452.               }
  453.               else
  454.                   break;
  455.  
  456.               delta += delta / 4 + 5;
  457.  
  458.               assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
  459.           }
  460.  
  461.           // Sort the PV lines searched so far and update the GUI
  462.           std::stable_sort(rootMoves.begin() + pvFirst, rootMoves.begin() + pvIdx + 1);
  463.  
  464.           if (    mainThread
  465.               && (Threads.stop || pvIdx + 1 == multiPV || Time.elapsed() > 3000))
  466.               sync_cout << UCI::pv(rootPos, rootDepth, alpha, beta) << sync_endl;
  467.       }
  468.  
  469.       if (!Threads.stop)
  470.           completedDepth = rootDepth;
  471.  
  472.       if (rootMoves[0].pv[0] != lastBestMove) {
  473.          lastBestMove = rootMoves[0].pv[0];
  474.          lastBestMoveDepth = rootDepth;
  475.       }
  476.  
  477.       // Have we found a "mate in x"?
  478.       if (   Limits.mate
  479.           && bestValue >= VALUE_MATE_IN_MAX_PLY
  480.           && VALUE_MATE - bestValue <= 2 * Limits.mate)
  481.           Threads.stop = true;
  482.  
  483.       if (!mainThread)
  484.           continue;
  485.  
  486.       // If skill level is enabled and time is up, pick a sub-optimal best move
  487.       if (skill.enabled() && skill.time_to_pick(rootDepth))
  488.           skill.pick_best(multiPV);
  489.  
  490.       // Do we have time for the next iteration? Can we stop searching now?
  491.       if (    Limits.use_time_management()
  492.           && !Threads.stop
  493.           && !Threads.stopOnPonderhit)
  494.           {
  495.               const int F[] = { failedLow,
  496.                                 bestValue - mainThread->previousScore };
  497.  
  498.               int improvingFactor = std::max(246, std::min(832, 306 + 119 * F[0] - 6 * F[1]));
  499.  
  500.               // If the bestMove is stable over several iterations, reduce time accordingly
  501.               timeReduction = 1.0;
  502.               for (int i : {3, 4, 5})
  503.                   if (lastBestMoveDepth * i < completedDepth)
  504.                      timeReduction *= 1.25;
  505.  
  506.               // Use part of the gained time from a previous stable move for the current move
  507.               double bestMoveInstability = 1.0 + mainThread->bestMoveChanges;
  508.               bestMoveInstability *= std::pow(mainThread->previousTimeReduction, 0.528) / timeReduction;
  509.  
  510.               // Stop the search if we have only one legal move, or if available time elapsed
  511.               if (   rootMoves.size() == 1
  512.                   || Time.elapsed() > Time.optimum() * bestMoveInstability * improvingFactor / 581)
  513.               {
  514.                   // If we are allowed to ponder do not stop the search now but
  515.                   // keep pondering until the GUI sends "ponderhit" or "stop".
  516.                   if (Threads.ponder)
  517.                       Threads.stopOnPonderhit = true;
  518.                   else
  519.                       Threads.stop = true;
  520.               }
  521.           }
  522.   }
  523.  
  524.   if (!mainThread)
  525.       return;
  526.  
  527.   mainThread->previousTimeReduction = timeReduction;
  528.  
  529.   // If skill level is enabled, swap best PV line with the sub-optimal one
  530.   if (skill.enabled())
  531.       std::swap(rootMoves[0], *std::find(rootMoves.begin(), rootMoves.end(),
  532.                 skill.best ? skill.best : skill.pick_best(multiPV)));
  533. }
  534.  
  535.  
  536. namespace {
  537.  
  538.   // search<>() is the main search function for both PV and non-PV nodes
  539.  
  540.   template <NodeType NT>
  541.   Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) {
  542.  
  543.     constexpr bool PvNode = NT == PV;
  544.     const bool rootNode = PvNode && ss->ply == 0;
  545.  
  546.     // Check if we have an upcoming move which draws by repetition, or
  547.     // if the opponent had an alternative move earlier to this position.
  548.     if (   pos.rule50_count() >= 3
  549.         && alpha < VALUE_DRAW
  550.         && !rootNode
  551.         && pos.has_game_cycle(ss->ply))
  552.     {
  553.         alpha = value_draw(depth, pos.this_thread());
  554.         if (alpha >= beta)
  555.             return alpha;
  556.     }
  557.  
  558.     // Dive into quiescence search when the depth reaches zero
  559.     if (depth < ONE_PLY)
  560.         return qsearch<NT>(pos, ss, alpha, beta);
  561.  
  562.     assert(-VALUE_INFINITE <= alpha && alpha < beta && beta <= VALUE_INFINITE);
  563.     assert(PvNode || (alpha == beta - 1));
  564.     assert(DEPTH_ZERO < depth && depth < DEPTH_MAX);
  565.     assert(!(PvNode && cutNode));
  566.     assert(depth / ONE_PLY * ONE_PLY == depth);
  567.  
  568.     Move pv[MAX_PLY+1], capturesSearched[32], quietsSearched[64];
  569.     StateInfo st;
  570.     TTEntry* tte;
  571.     Key posKey;
  572.     Move ttMove, move, excludedMove, bestMove;
  573.     Depth extension, newDepth;
  574.     Value bestValue, value, ttValue, eval, maxValue, pureStaticEval;
  575.     bool ttHit, inCheck, givesCheck, improving;
  576.     bool captureOrPromotion, doFullDepthSearch, moveCountPruning, skipQuiets, ttCapture, pvExact;
  577.     Piece movedPiece;
  578.     int moveCount, captureCount, quietCount;
  579.  
  580.     // Step 1. Initialize node
  581.     Thread* thisThread = pos.this_thread();
  582.     inCheck = pos.checkers();
  583.     Color us = pos.side_to_move();
  584.     moveCount = captureCount = quietCount = ss->moveCount = 0;
  585.     bestValue = -VALUE_INFINITE;
  586.     maxValue = VALUE_INFINITE;
  587.  
  588.     // Check for the available remaining time
  589.     if (thisThread == Threads.main())
  590.         static_cast<MainThread*>(thisThread)->check_time();
  591.  
  592.     // Used to send selDepth info to GUI (selDepth counts from 1, ply from 0)
  593.     if (PvNode && thisThread->selDepth < ss->ply + 1)
  594.         thisThread->selDepth = ss->ply + 1;
  595.  
  596.     if (!rootNode)
  597.     {
  598.         // Step 2. Check for aborted search and immediate draw
  599.         if (   Threads.stop.load(std::memory_order_relaxed)
  600.             || pos.is_draw(ss->ply)
  601.             || ss->ply >= MAX_PLY)
  602.             return (ss->ply >= MAX_PLY && !inCheck) ? evaluate(pos)
  603.                                                     : value_draw(depth, pos.this_thread());
  604.  
  605.         // Step 3. Mate distance pruning. Even if we mate at the next move our score
  606.         // would be at best mate_in(ss->ply+1), but if alpha is already bigger because
  607.         // a shorter mate was found upward in the tree then there is no need to search
  608.         // because we will never beat the current alpha. Same logic but with reversed
  609.         // signs applies also in the opposite condition of being mated instead of giving
  610.         // mate. In this case return a fail-high score.
  611.         alpha = std::max(mated_in(ss->ply), alpha);
  612.         beta = std::min(mate_in(ss->ply+1), beta);
  613.         if (alpha >= beta)
  614.             return alpha;
  615.     }
  616.  
  617.     assert(0 <= ss->ply && ss->ply < MAX_PLY);
  618.  
  619.     (ss+1)->ply = ss->ply + 1;
  620.     ss->currentMove = (ss+1)->excludedMove = bestMove = MOVE_NONE;
  621.     ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0];
  622.     (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE;
  623.     Square prevSq = to_sq((ss-1)->currentMove);
  624.  
  625.     // Initialize statScore to zero for the grandchildren of the current position.
  626.     // So statScore is shared between all grandchildren and only the first grandchild
  627.     // starts with statScore = 0. Later grandchildren start with the last calculated
  628.     // statScore of the previous grandchild. This influences the reduction rules in
  629.     // LMR which are based on the statScore of parent position.
  630.     (ss+2)->statScore = 0;
  631.  
  632.     // Step 4. Transposition table lookup. We don't want the score of a partial
  633.     // search to overwrite a previous full search TT value, so we use a different
  634.     // position key in case of an excluded move.
  635.     excludedMove = ss->excludedMove;
  636.     posKey = pos.key() ^ Key(excludedMove << 16); // Isn't a very good hash
  637.     tte = TT.probe(posKey, ttHit);
  638.     ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
  639.     ttMove =  rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0]
  640.             : ttHit    ? tte->move() : MOVE_NONE;
  641.  
  642.     // At non-PV nodes we check for an early TT cutoff
  643.     if (  !PvNode
  644.         && ttHit
  645.         && tte->depth() >= depth
  646.         && ttValue != VALUE_NONE // Possible in case of TT access race
  647.         && (ttValue >= beta ? (tte->bound() & BOUND_LOWER)
  648.                             : (tte->bound() & BOUND_UPPER)))
  649.     {
  650.         // If ttMove is quiet, update move sorting heuristics on TT hit
  651.         if (ttMove)
  652.         {
  653.             if (ttValue >= beta)
  654.             {
  655.                 if (!pos.capture_or_promotion(ttMove))
  656.                     update_quiet_stats(pos, ss, ttMove, nullptr, 0, stat_bonus(depth));
  657.  
  658.                 // Extra penalty for a quiet TT move in previous ply when it gets refuted
  659.                 if ((ss-1)->moveCount == 1 && !pos.captured_piece())
  660.                     update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + ONE_PLY));
  661.             }
  662.             // Penalty for a quiet ttMove that fails low
  663.             else if (!pos.capture_or_promotion(ttMove))
  664.             {
  665.                 int penalty = -stat_bonus(depth);
  666.                 thisThread->mainHistory[us][from_to(ttMove)] << penalty;
  667.                 update_continuation_histories(ss, pos.moved_piece(ttMove), to_sq(ttMove), penalty);
  668.             }
  669.         }
  670.         return ttValue;
  671.     }
  672.  
  673.     // Step 5. Tablebases probe
  674.     if (!rootNode && TB::Cardinality)
  675.     {
  676.         int piecesCount = pos.count<ALL_PIECES>();
  677.  
  678.         if (    piecesCount <= TB::Cardinality
  679.             && (piecesCount <  TB::Cardinality || depth >= TB::ProbeDepth)
  680.             &&  pos.rule50_count() == 0
  681.             && !pos.can_castle(ANY_CASTLING))
  682.         {
  683.             TB::ProbeState err;
  684.             TB::WDLScore wdl = Tablebases::probe_wdl(pos, &err);
  685.  
  686.             // Force check of time on the next occasion
  687.             if (thisThread == Threads.main())
  688.                 static_cast<MainThread*>(thisThread)->callsCnt = 0;
  689.  
  690.             if (err != TB::ProbeState::FAIL)
  691.             {
  692.                 thisThread->tbHits.fetch_add(1, std::memory_order_relaxed);
  693.  
  694.                 int drawScore = TB::UseRule50 ? 1 : 0;
  695.  
  696.                 value =  wdl < -drawScore ? -VALUE_MATE + MAX_PLY + ss->ply + 1
  697.                        : wdl >  drawScore ?  VALUE_MATE - MAX_PLY - ss->ply - 1
  698.                                           :  VALUE_DRAW + 2 * wdl * drawScore;
  699.  
  700.                 Bound b =  wdl < -drawScore ? BOUND_UPPER
  701.                          : wdl >  drawScore ? BOUND_LOWER : BOUND_EXACT;
  702.  
  703.                 if (    b == BOUND_EXACT
  704.                     || (b == BOUND_LOWER ? value >= beta : value <= alpha))
  705.                 {
  706.                     tte->save(posKey, value_to_tt(value, ss->ply), b,
  707.                               std::min(DEPTH_MAX - ONE_PLY, depth + 6 * ONE_PLY),
  708.                               MOVE_NONE, VALUE_NONE);
  709.  
  710.                     return value;
  711.                 }
  712.  
  713.                 if (PvNode)
  714.                 {
  715.                     if (b == BOUND_LOWER)
  716.                         bestValue = value, alpha = std::max(alpha, bestValue);
  717.                     else
  718.                         maxValue = value;
  719.                 }
  720.             }
  721.         }
  722.     }
  723.  
  724.     // Step 6. Static evaluation of the position
  725.     if (inCheck)
  726.     {
  727.         ss->staticEval = eval = pureStaticEval = VALUE_NONE;
  728.         improving = false;
  729.         goto moves_loop;  // Skip early pruning when in check
  730.     }
  731.     else if (ttHit)
  732.     {
  733.         // Never assume anything on values stored in TT
  734.         ss->staticEval = eval = pureStaticEval = tte->eval();
  735.         if (eval == VALUE_NONE)
  736.             ss->staticEval = eval = pureStaticEval = evaluate(pos);
  737.  
  738.         // Can ttValue be used as a better position evaluation?
  739.         if (    ttValue != VALUE_NONE
  740.             && (tte->bound() & (ttValue > eval ? BOUND_LOWER : BOUND_UPPER)))
  741.             eval = ttValue;
  742.     }
  743.     else
  744.     {
  745.         if ((ss-1)->currentMove != MOVE_NULL)
  746.         {
  747.             int p = (ss-1)->statScore;
  748.             int bonus = p > 0 ? (-p - 2500) / 512 :
  749.                         p < 0 ? (-p + 2500) / 512 : 0;
  750.  
  751.             pureStaticEval = evaluate(pos);
  752.             ss->staticEval = eval = pureStaticEval + bonus;
  753.         }
  754.         else
  755.             ss->staticEval = eval = pureStaticEval = -(ss-1)->staticEval + 2 * Eval::Tempo;
  756.  
  757.         tte->save(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, pureStaticEval);
  758.     }
  759.  
  760.     // Step 7. Razoring (~2 Elo)
  761.     if (   depth < 2 * ONE_PLY
  762.         && eval <= alpha - RazorMargin)
  763.         return qsearch<NT>(pos, ss, alpha, beta);
  764.  
  765.     improving =   ss->staticEval >= (ss-2)->staticEval
  766.                || (ss-2)->staticEval == VALUE_NONE;
  767.  
  768.     // Step 8. Futility pruning: child node (~30 Elo)
  769.     if (   !rootNode
  770.         &&  depth < 7 * ONE_PLY
  771.         &&  eval - futility_margin(depth, improving) >= beta
  772.         &&  eval < VALUE_KNOWN_WIN) // Do not return unproven wins
  773.         return eval;
  774.  
  775.     // Step 9. Null move search with verification search (~40 Elo)
  776.     if (   !PvNode
  777.         && (ss-1)->currentMove != MOVE_NULL
  778.         && (ss-1)->statScore < 23200
  779.         &&  eval >= beta
  780.         &&  pureStaticEval >= beta - 36 * depth / ONE_PLY + 225
  781.         && !excludedMove
  782.         &&  pos.non_pawn_material(us)
  783.         && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor))
  784.     {
  785.         assert(eval - beta >= 0);
  786.  
  787.         // Null move dynamic reduction based on depth and value
  788.         Depth R = ((823 + 67 * depth / ONE_PLY) / 256 + std::min(int(eval - beta) / 200, 3)) * ONE_PLY;
  789.  
  790.         ss->currentMove = MOVE_NULL;
  791.         ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0];
  792.  
  793.         pos.do_null_move(st);
  794.  
  795.         Value nullValue = -search<NonPV>(pos, ss+1, -beta, -beta+1, depth-R, !cutNode);
  796.  
  797.         pos.undo_null_move();
  798.  
  799.         if (nullValue >= beta)
  800.         {
  801.             // Do not return unproven mate scores
  802.             if (nullValue >= VALUE_MATE_IN_MAX_PLY)
  803.                 nullValue = beta;
  804.  
  805.             if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 12 * ONE_PLY))
  806.                 return nullValue;
  807.  
  808.             assert(!thisThread->nmpMinPly); // Recursive verification is not allowed
  809.  
  810.             // Do verification search at high depths, with null move pruning disabled
  811.             // for us, until ply exceeds nmpMinPly.
  812.             thisThread->nmpMinPly = ss->ply + 3 * (depth-R) / 4;
  813.             thisThread->nmpColor = us;
  814.  
  815.             Value v = search<NonPV>(pos, ss, beta-1, beta, depth-R, false);
  816.  
  817.             thisThread->nmpMinPly = 0;
  818.  
  819.             if (v >= beta)
  820.                 return nullValue;
  821.         }
  822.     }
  823.  
  824.     // Step 10. ProbCut (~10 Elo)
  825.     // If we have a good enough capture and a reduced search returns a value
  826.     // much above beta, we can (almost) safely prune the previous move.
  827.     if (   !PvNode
  828.         &&  depth >= 5 * ONE_PLY
  829.         &&  abs(beta) < VALUE_MATE_IN_MAX_PLY)
  830.     {
  831.         Value rbeta = std::min(beta + 216 - 48 * improving, VALUE_INFINITE);
  832.         MovePicker mp(pos, ttMove, rbeta - ss->staticEval, &thisThread->captureHistory);
  833.         int probCutCount = 0;
  834.  
  835.         while (  (move = mp.next_move()) != MOVE_NONE
  836.                && probCutCount < 3)
  837.             if (move != excludedMove && pos.legal(move))
  838.             {
  839.                 probCutCount++;
  840.  
  841.                 ss->currentMove = move;
  842.                 ss->continuationHistory = &thisThread->continuationHistory[pos.moved_piece(move)][to_sq(move)];
  843.  
  844.                 assert(depth >= 5 * ONE_PLY);
  845.  
  846.                 pos.do_move(move, st);
  847.  
  848.                 // Perform a preliminary qsearch to verify that the move holds
  849.                 value = -qsearch<NonPV>(pos, ss+1, -rbeta, -rbeta+1);
  850.  
  851.                 // If the qsearch held perform the regular search
  852.                 if (value >= rbeta)
  853.                     value = -search<NonPV>(pos, ss+1, -rbeta, -rbeta+1, depth - 4 * ONE_PLY, !cutNode);
  854.  
  855.                 pos.undo_move(move);
  856.  
  857.                 if (value >= rbeta)
  858.                     return value;
  859.             }
  860.     }
  861.  
  862.     // Step 11. Internal iterative deepening (~2 Elo)
  863.     if (    depth >= 8 * ONE_PLY
  864.         && !ttMove)
  865.     {
  866.         search<NT>(pos, ss, alpha, beta, depth - 7 * ONE_PLY, cutNode);
  867.  
  868.         tte = TT.probe(posKey, ttHit);
  869.         ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
  870.         ttMove = ttHit ? tte->move() : MOVE_NONE;
  871.     }
  872.  
  873. moves_loop: // When in check, search starts from here
  874.  
  875.     const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, nullptr, (ss-4)->continuationHistory };
  876.     Move countermove = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq];
  877.  
  878.     MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory,
  879.                                       &thisThread->captureHistory,
  880.                                       contHist,
  881.                                       countermove,
  882.                                       ss->killers);
  883.     value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
  884.  
  885.     skipQuiets = false;
  886.     ttCapture = ttMove && pos.capture_or_promotion(ttMove);
  887.     pvExact = PvNode && ttHit && tte->bound() == BOUND_EXACT;
  888.  
  889.     // Step 12. Loop through all pseudo-legal moves until no moves remain
  890.     // or a beta cutoff occurs.
  891.     while ((move = mp.next_move(skipQuiets)) != MOVE_NONE)
  892.     {
  893.       assert(is_ok(move));
  894.  
  895.       if (move == excludedMove)
  896.           continue;
  897.  
  898.       // At root obey the "searchmoves" option and skip moves not listed in Root
  899.       // Move List. As a consequence any illegal move is also skipped. In MultiPV
  900.       // mode we also skip PV moves which have been already searched and those
  901.       // of lower "TB rank" if we are in a TB root position.
  902.       if (rootNode && !std::count(thisThread->rootMoves.begin() + thisThread->pvIdx,
  903.                                   thisThread->rootMoves.begin() + thisThread->pvLast, move))
  904.           continue;
  905.  
  906.       ss->moveCount = ++moveCount;
  907.  
  908.       if (rootNode && thisThread == Threads.main() && Time.elapsed() > 3000)
  909.           sync_cout << "info depth " << depth / ONE_PLY
  910.                     << " currmove " << UCI::move(move, pos.is_chess960())
  911.                     << " currmovenumber " << moveCount + thisThread->pvIdx << sync_endl;
  912.       if (PvNode)
  913.           (ss+1)->pv = nullptr;
  914.  
  915.       extension = DEPTH_ZERO;
  916.       captureOrPromotion = pos.capture_or_promotion(move);
  917.       movedPiece = pos.moved_piece(move);
  918.       givesCheck = gives_check(pos, move);
  919.  
  920.       moveCountPruning =   depth < 16 * ONE_PLY
  921.                         && moveCount >= FutilityMoveCounts[improving][depth / ONE_PLY];
  922.  
  923.       // Step 13. Extensions (~70 Elo)
  924.  
  925.       // Singular extension search (~60 Elo). If all moves but one fail low on a
  926.       // search of (alpha-s, beta-s), and just one fails high on (alpha, beta),
  927.       // then that move is singular and should be extended. To verify this we do
  928.       // a reduced search on all the other moves but the ttMove and if the
  929.       // result is lower than ttValue minus a margin then we will extend the ttMove.
  930.       if (    depth >= 8 * ONE_PLY
  931.           &&  move == ttMove
  932.           && !rootNode
  933.           && !excludedMove // Recursive singular search is not allowed
  934.           &&  ttValue != VALUE_NONE
  935.           && (tte->bound() & BOUND_LOWER)
  936.           &&  tte->depth() >= depth - 3 * ONE_PLY
  937.           &&  pos.legal(move))
  938.       {
  939.           Value rBeta = std::max(ttValue - 2 * depth / ONE_PLY, -VALUE_MATE);
  940.           ss->excludedMove = move;
  941.           value = search<NonPV>(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode);
  942.           ss->excludedMove = MOVE_NONE;
  943.  
  944.           if (value < rBeta)
  945.               extension = ONE_PLY;
  946.       }
  947.       else if (    givesCheck // Check extension (~2 Elo)
  948.                &&  pos.see_ge(move))
  949.           extension = ONE_PLY;
  950.  
  951.       // Extension if castling
  952.       else if (type_of(move) == CASTLING)
  953.           extension = ONE_PLY;
  954.  
  955.       // Calculate new depth for this move
  956.       newDepth = depth - ONE_PLY + extension;
  957.  
  958.       // Step 14. Pruning at shallow depth (~170 Elo)
  959.       if (  !rootNode
  960.           && pos.non_pawn_material(us)
  961.           && bestValue > VALUE_MATED_IN_MAX_PLY)
  962.       {
  963.           if (   !captureOrPromotion
  964.               && !givesCheck
  965.               && (!pos.advanced_pawn_push(move) || pos.non_pawn_material() >= Value(5000)))
  966.           {
  967.               // Move count based pruning (~30 Elo)
  968.               if (moveCountPruning)
  969.               {
  970.                   skipQuiets = true;
  971.                   continue;
  972.               }
  973.  
  974.               // Reduced depth of the next LMR search
  975.               int lmrDepth = std::max(newDepth - reduction<PvNode>(improving, depth, moveCount), DEPTH_ZERO) / ONE_PLY;
  976.  
  977.               // Countermoves based pruning (~20 Elo)
  978.               if (   lmrDepth < 3 + ((ss-1)->statScore > 0)
  979.                   && (*contHist[0])[movedPiece][to_sq(move)] < CounterMovePruneThreshold
  980.                   && (*contHist[1])[movedPiece][to_sq(move)] < CounterMovePruneThreshold)
  981.                   continue;
  982.  
  983.               // Futility pruning: parent node (~2 Elo)
  984.               if (   lmrDepth < 7
  985.                   && !inCheck
  986.                   && ss->staticEval + 256 + 200 * lmrDepth <= alpha)
  987.                   continue;
  988.  
  989.               // Prune moves with negative SEE (~10 Elo)
  990.               if (!pos.see_ge(move, Value(-29 * lmrDepth * lmrDepth)))
  991.                   continue;
  992.           }
  993.           else if (   !extension // (~20 Elo)
  994.                    && !pos.see_ge(move, -PawnValueEg * (depth / ONE_PLY)))
  995.                   continue;
  996.       }
  997.  
  998.       // Speculative prefetch as early as possible
  999.       prefetch(TT.first_entry(pos.key_after(move)));
  1000.  
  1001.       // Check for legality just before making the move
  1002.       if (!rootNode && !pos.legal(move))
  1003.       {
  1004.           ss->moveCount = --moveCount;
  1005.           continue;
  1006.       }
  1007.  
  1008.       // Update the current move (this must be done after singular extension search)
  1009.       ss->currentMove = move;
  1010.       ss->continuationHistory = &thisThread->continuationHistory[movedPiece][to_sq(move)];
  1011.  
  1012.       // Step 15. Make the move
  1013.       pos.do_move(move, st, givesCheck);
  1014.  
  1015.       // Step 16. Reduced depth search (LMR). If the move fails high it will be
  1016.       // re-searched at full depth.
  1017.       if (    depth >= 3 * ONE_PLY
  1018.           &&  moveCount > 1
  1019.           && (!captureOrPromotion || moveCountPruning))
  1020.       {
  1021.           Depth r = reduction<PvNode>(improving, depth, moveCount);
  1022.  
  1023.           // Decrease reduction if opponent's move count is high (~10 Elo)
  1024.           if ((ss-1)->moveCount > 15)
  1025.               r -= ONE_PLY;
  1026.  
  1027.           if (!captureOrPromotion)
  1028.           {
  1029.               // Decrease reduction for exact PV nodes (~0 Elo)
  1030.               if (pvExact)
  1031.                   r -= ONE_PLY;
  1032.  
  1033.               // Increase reduction if ttMove is a capture (~0 Elo)
  1034.               if (ttCapture)
  1035.                   r += ONE_PLY;
  1036.  
  1037.               // Increase reduction for cut nodes (~5 Elo)
  1038.               if (cutNode)
  1039.                   r += 2 * ONE_PLY;
  1040.  
  1041.               // Decrease reduction for moves that escape a capture. Filter out
  1042.               // castling moves, because they are coded as "king captures rook" and
  1043.               // hence break make_move(). (~5 Elo)
  1044.               else if (    type_of(move) == NORMAL
  1045.                        && !pos.see_ge(make_move(to_sq(move), from_sq(move))))
  1046.                   r -= 2 * ONE_PLY;
  1047.  
  1048.               ss->statScore =  thisThread->mainHistory[us][from_to(move)]
  1049.                              + (*contHist[0])[movedPiece][to_sq(move)]
  1050.                              + (*contHist[1])[movedPiece][to_sq(move)]
  1051.                              + (*contHist[3])[movedPiece][to_sq(move)]
  1052.                              - 4000;
  1053.  
  1054.               // Decrease/increase reduction by comparing opponent's stat score (~10 Elo)
  1055.               if (ss->statScore >= 0 && (ss-1)->statScore < 0)
  1056.                   r -= ONE_PLY;
  1057.  
  1058.               else if ((ss-1)->statScore >= 0 && ss->statScore < 0)
  1059.                   r += ONE_PLY;
  1060.  
  1061.               // Decrease/increase reduction for moves with a good/bad history (~30 Elo)
  1062.               r -= ss->statScore / 20000 * ONE_PLY;
  1063.           }
  1064.  
  1065.           Depth d = std::max(newDepth - std::max(r, DEPTH_ZERO), ONE_PLY);
  1066.  
  1067.           value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, true);
  1068.  
  1069.           doFullDepthSearch = (value > alpha && d != newDepth);
  1070.       }
  1071.       else
  1072.           doFullDepthSearch = !PvNode || moveCount > 1;
  1073.  
  1074.       // Step 17. Full depth search when LMR is skipped or fails high
  1075.       if (doFullDepthSearch)
  1076.           value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode);
  1077.  
  1078.       // For PV nodes only, do a full PV search on the first move or after a fail
  1079.       // high (in the latter case search only if value < beta), otherwise let the
  1080.       // parent node fail low with value <= alpha and try another move.
  1081.       if (PvNode && (moveCount == 1 || (value > alpha && (rootNode || value < beta))))
  1082.       {
  1083.           (ss+1)->pv = pv;
  1084.           (ss+1)->pv[0] = MOVE_NONE;
  1085.  
  1086.           value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, false);
  1087.       }
  1088.  
  1089.       // Step 18. Undo move
  1090.       pos.undo_move(move);
  1091.  
  1092.       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
  1093.  
  1094.       // Step 19. Check for a new best move
  1095.       // Finished searching the move. If a stop occurred, the return value of
  1096.       // the search cannot be trusted, and we return immediately without
  1097.       // updating best move, PV and TT.
  1098.       if (Threads.stop.load(std::memory_order_relaxed))
  1099.           return VALUE_ZERO;
  1100.  
  1101.       if (rootNode)
  1102.       {
  1103.           RootMove& rm = *std::find(thisThread->rootMoves.begin(),
  1104.                                     thisThread->rootMoves.end(), move);
  1105.  
  1106.           // PV move or new best move?
  1107.           if (moveCount == 1 || value > alpha)
  1108.           {
  1109.               rm.score = value;
  1110.               rm.selDepth = thisThread->selDepth;
  1111.               rm.pv.resize(1);
  1112.  
  1113.               assert((ss+1)->pv);
  1114.  
  1115.               for (Move* m = (ss+1)->pv; *m != MOVE_NONE; ++m)
  1116.                   rm.pv.push_back(*m);
  1117.  
  1118.               // We record how often the best move has been changed in each
  1119.               // iteration. This information is used for time management: When
  1120.               // the best move changes frequently, we allocate some more time.
  1121.               if (moveCount > 1 && thisThread == Threads.main())
  1122.                   ++static_cast<MainThread*>(thisThread)->bestMoveChanges;
  1123.           }
  1124.           else
  1125.               // All other moves but the PV are set to the lowest value: this
  1126.               // is not a problem when sorting because the sort is stable and the
  1127.               // move position in the list is preserved - just the PV is pushed up.
  1128.               rm.score = -VALUE_INFINITE;
  1129.       }
  1130.  
  1131.       if (value > bestValue)
  1132.       {
  1133.           bestValue = value;
  1134.  
  1135.           if (value > alpha)
  1136.           {
  1137.               bestMove = move;
  1138.  
  1139.               if (PvNode && !rootNode) // Update pv even in fail-high case
  1140.                   update_pv(ss->pv, move, (ss+1)->pv);
  1141.  
  1142.               if (PvNode && value < beta) // Update alpha! Always alpha < beta
  1143.                   alpha = value;
  1144.               else
  1145.               {
  1146.                   assert(value >= beta); // Fail high
  1147.                   ss->statScore = 0;
  1148.                   break;
  1149.               }
  1150.           }
  1151.       }
  1152.  
  1153.       if (move != bestMove)
  1154.       {
  1155.           if (captureOrPromotion && captureCount < 32)
  1156.               capturesSearched[captureCount++] = move;
  1157.  
  1158.           else if (!captureOrPromotion && quietCount < 64)
  1159.               quietsSearched[quietCount++] = move;
  1160.       }
  1161.     }
  1162.  
  1163.     // The following condition would detect a stop only after move loop has been
  1164.     // completed. But in this case bestValue is valid because we have fully
  1165.     // searched our subtree, and we can anyhow save the result in TT.
  1166.     /*
  1167.        if (Threads.stop)
  1168.         return VALUE_DRAW;
  1169.     */
  1170.  
  1171.     // Step 20. Check for mate and stalemate
  1172.     // All legal moves have been searched and if there are no legal moves, it
  1173.     // must be a mate or a stalemate. If we are in a singular extension search then
  1174.     // return a fail low score.
  1175.  
  1176.     assert(moveCount || !inCheck || excludedMove || !MoveList<LEGAL>(pos).size());
  1177.  
  1178.     if (!moveCount)
  1179.         bestValue = excludedMove ? alpha
  1180.                    :     inCheck ? mated_in(ss->ply) : VALUE_DRAW;
  1181.     else if (bestMove)
  1182.     {
  1183.         // Quiet best move: update move sorting heuristics
  1184.         if (!pos.capture_or_promotion(bestMove))
  1185.             update_quiet_stats(pos, ss, bestMove, quietsSearched, quietCount,
  1186.                                stat_bonus(depth + (bestValue > beta + PawnValueMg ? ONE_PLY : DEPTH_ZERO)));
  1187.  
  1188.         update_capture_stats(pos, bestMove, capturesSearched, captureCount, stat_bonus(depth + ONE_PLY));
  1189.  
  1190.         // Extra penalty for a quiet TT move in previous ply when it gets refuted
  1191.         if ((ss-1)->moveCount == 1 && !pos.captured_piece())
  1192.             update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + ONE_PLY));
  1193.     }
  1194.     // Bonus for prior countermove that caused the fail low
  1195.     else if (   (depth >= 3 * ONE_PLY || PvNode)
  1196.              && !pos.captured_piece()
  1197.              && is_ok((ss-1)->currentMove))
  1198.         update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth));
  1199.  
  1200.     if (PvNode)
  1201.         bestValue = std::min(bestValue, maxValue);
  1202.  
  1203.     if (!excludedMove)
  1204.         tte->save(posKey, value_to_tt(bestValue, ss->ply),
  1205.                   bestValue >= beta ? BOUND_LOWER :
  1206.                   PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER,
  1207.                   depth, bestMove, pureStaticEval);
  1208.  
  1209.     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
  1210.  
  1211.     return bestValue;
  1212.   }
  1213.  
  1214.  
  1215.   // qsearch() is the quiescence search function, which is called by the main
  1216.   // search function with depth zero, or recursively with depth less than ONE_PLY.
  1217.   template <NodeType NT>
  1218.   Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) {
  1219.  
  1220.     constexpr bool PvNode = NT == PV;
  1221.  
  1222.     assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE);
  1223.     assert(PvNode || (alpha == beta - 1));
  1224.     assert(depth <= DEPTH_ZERO);
  1225.     assert(depth / ONE_PLY * ONE_PLY == depth);
  1226.  
  1227.     Move pv[MAX_PLY+1];
  1228.     StateInfo st;
  1229.     TTEntry* tte;
  1230.     Key posKey;
  1231.     Move ttMove, move, bestMove;
  1232.     Depth ttDepth;
  1233.     Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha;
  1234.     bool ttHit, inCheck, givesCheck, evasionPrunable;
  1235.     int moveCount;
  1236.  
  1237.     if (PvNode)
  1238.     {
  1239.         oldAlpha = alpha; // To flag BOUND_EXACT when eval above alpha and no available moves
  1240.         (ss+1)->pv = pv;
  1241.         ss->pv[0] = MOVE_NONE;
  1242.     }
  1243.  
  1244.     Thread* thisThread = pos.this_thread();
  1245.     (ss+1)->ply = ss->ply + 1;
  1246.     ss->currentMove = bestMove = MOVE_NONE;
  1247.     ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0];
  1248.     inCheck = pos.checkers();
  1249.     moveCount = 0;
  1250.  
  1251.     // Check for an immediate draw or maximum ply reached
  1252.     if (   pos.is_draw(ss->ply)
  1253.         || ss->ply >= MAX_PLY)
  1254.         return (ss->ply >= MAX_PLY && !inCheck) ? evaluate(pos) : VALUE_DRAW;
  1255.  
  1256.     assert(0 <= ss->ply && ss->ply < MAX_PLY);
  1257.  
  1258.     // Decide whether or not to include checks: this fixes also the type of
  1259.     // TT entry depth that we are going to use. Note that in qsearch we use
  1260.     // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
  1261.     ttDepth = inCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS
  1262.                                                   : DEPTH_QS_NO_CHECKS;
  1263.     // Transposition table lookup
  1264.     posKey = pos.key();
  1265.     tte = TT.probe(posKey, ttHit);
  1266.     ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
  1267.     ttMove = ttHit ? tte->move() : MOVE_NONE;
  1268.  
  1269.     if (  !PvNode
  1270.         && ttHit
  1271.         && tte->depth() >= ttDepth
  1272.         && ttValue != VALUE_NONE // Only in case of TT access race
  1273.         && (ttValue >= beta ? (tte->bound() & BOUND_LOWER)
  1274.                             : (tte->bound() & BOUND_UPPER)))
  1275.         return ttValue;
  1276.  
  1277.     // Evaluate the position statically
  1278.     if (inCheck)
  1279.     {
  1280.         ss->staticEval = VALUE_NONE;
  1281.         bestValue = futilityBase = -VALUE_INFINITE;
  1282.     }
  1283.     else
  1284.     {
  1285.         if (ttHit)
  1286.         {
  1287.             // Never assume anything on values stored in TT
  1288.             if ((ss->staticEval = bestValue = tte->eval()) == VALUE_NONE)
  1289.                 ss->staticEval = bestValue = evaluate(pos);
  1290.  
  1291.             // Can ttValue be used as a better position evaluation?
  1292.             if (    ttValue != VALUE_NONE
  1293.                 && (tte->bound() & (ttValue > bestValue ? BOUND_LOWER : BOUND_UPPER)))
  1294.                 bestValue = ttValue;
  1295.         }
  1296.         else
  1297.             ss->staticEval = bestValue =
  1298.             (ss-1)->currentMove != MOVE_NULL ? evaluate(pos)
  1299.                                              : -(ss-1)->staticEval + 2 * Eval::Tempo;
  1300.  
  1301.         // Stand pat. Return immediately if static value is at least beta
  1302.         if (bestValue >= beta)
  1303.         {
  1304.             if (!ttHit)
  1305.                 tte->save(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER,
  1306.                           DEPTH_NONE, MOVE_NONE, ss->staticEval);
  1307.  
  1308.             return bestValue;
  1309.         }
  1310.  
  1311.         if (PvNode && bestValue > alpha)
  1312.             alpha = bestValue;
  1313.  
  1314.         futilityBase = bestValue + 128;
  1315.     }
  1316.  
  1317.     const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, nullptr, (ss-4)->continuationHistory };
  1318.  
  1319.     // Initialize a MovePicker object for the current position, and prepare
  1320.     // to search the moves. Because the depth is <= 0 here, only captures,
  1321.     // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
  1322.     // be generated.
  1323.     MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory,
  1324.                                       &thisThread->captureHistory,
  1325.                                       contHist,
  1326.                                       to_sq((ss-1)->currentMove));
  1327.  
  1328.     // Loop through the moves until no moves remain or a beta cutoff occurs
  1329.     while ((move = mp.next_move()) != MOVE_NONE)
  1330.     {
  1331.       assert(is_ok(move));
  1332.  
  1333.       givesCheck = gives_check(pos, move);
  1334.  
  1335.       moveCount++;
  1336.  
  1337.       // Futility pruning
  1338.       if (   !inCheck
  1339.           && !givesCheck
  1340.           &&  futilityBase > -VALUE_KNOWN_WIN
  1341.           && !pos.advanced_pawn_push(move))
  1342.       {
  1343.           assert(type_of(move) != ENPASSANT); // Due to !pos.advanced_pawn_push
  1344.  
  1345.           futilityValue = futilityBase + PieceValue[EG][pos.piece_on(to_sq(move))];
  1346.  
  1347.           if (futilityValue <= alpha)
  1348.           {
  1349.               bestValue = std::max(bestValue, futilityValue);
  1350.               continue;
  1351.           }
  1352.  
  1353.           if (futilityBase <= alpha && !pos.see_ge(move, VALUE_ZERO + 1))
  1354.           {
  1355.               bestValue = std::max(bestValue, futilityBase);
  1356.               continue;
  1357.           }
  1358.       }
  1359.  
  1360.       // Detect non-capture evasions that are candidates to be pruned
  1361.       evasionPrunable =    inCheck
  1362.                        &&  (depth != DEPTH_ZERO || moveCount > 2)
  1363.                        &&  bestValue > VALUE_MATED_IN_MAX_PLY
  1364.                        && !pos.capture(move);
  1365.  
  1366.       // Don't search moves with negative SEE values
  1367.       if (  (!inCheck || evasionPrunable)
  1368.           && !pos.see_ge(move))
  1369.           continue;
  1370.  
  1371.       // Speculative prefetch as early as possible
  1372.       prefetch(TT.first_entry(pos.key_after(move)));
  1373.  
  1374.       // Check for legality just before making the move
  1375.       if (!pos.legal(move))
  1376.       {
  1377.           moveCount--;
  1378.           continue;
  1379.       }
  1380.  
  1381.       ss->currentMove = move;
  1382.       ss->continuationHistory = &thisThread->continuationHistory[pos.moved_piece(move)][to_sq(move)];
  1383.  
  1384.       // Make and search the move
  1385.       pos.do_move(move, st, givesCheck);
  1386.       value = -qsearch<NT>(pos, ss+1, -beta, -alpha, depth - ONE_PLY);
  1387.       pos.undo_move(move);
  1388.  
  1389.       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
  1390.  
  1391.       // Check for a new best move
  1392.       if (value > bestValue)
  1393.       {
  1394.           bestValue = value;
  1395.  
  1396.           if (value > alpha)
  1397.           {
  1398.               bestMove = move;
  1399.  
  1400.               if (PvNode) // Update pv even in fail-high case
  1401.                   update_pv(ss->pv, move, (ss+1)->pv);
  1402.  
  1403.               if (PvNode && value < beta) // Update alpha here!
  1404.                   alpha = value;
  1405.               else
  1406.                   break; // Fail high
  1407.           }
  1408.        }
  1409.     }
  1410.  
  1411.     // All legal moves have been searched. A special case: If we're in check
  1412.     // and no legal moves were found, it is checkmate.
  1413.     if (inCheck && bestValue == -VALUE_INFINITE)
  1414.         return mated_in(ss->ply); // Plies to mate from the root
  1415.  
  1416.     tte->save(posKey, value_to_tt(bestValue, ss->ply),
  1417.               bestValue >= beta ? BOUND_LOWER :
  1418.               PvNode && bestValue > oldAlpha  ? BOUND_EXACT : BOUND_UPPER,
  1419.               ttDepth, bestMove, ss->staticEval);
  1420.  
  1421.     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
  1422.  
  1423.     return bestValue;
  1424.   }
  1425.  
  1426.  
  1427.   // value_to_tt() adjusts a mate score from "plies to mate from the root" to
  1428.   // "plies to mate from the current position". Non-mate scores are unchanged.
  1429.   // The function is called before storing a value in the transposition table.
  1430.  
  1431.   Value value_to_tt(Value v, int ply) {
  1432.  
  1433.     assert(v != VALUE_NONE);
  1434.  
  1435.     return  v >= VALUE_MATE_IN_MAX_PLY  ? v + ply
  1436.           : v <= VALUE_MATED_IN_MAX_PLY ? v - ply : v;
  1437.   }
  1438.  
  1439.  
  1440.   // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score
  1441.   // from the transposition table (which refers to the plies to mate/be mated
  1442.   // from current position) to "plies to mate/be mated from the root".
  1443.  
  1444.   Value value_from_tt(Value v, int ply) {
  1445.  
  1446.     return  v == VALUE_NONE             ? VALUE_NONE
  1447.           : v >= VALUE_MATE_IN_MAX_PLY  ? v - ply
  1448.           : v <= VALUE_MATED_IN_MAX_PLY ? v + ply : v;
  1449.   }
  1450.  
  1451.  
  1452.   // update_pv() adds current move and appends child pv[]
  1453.  
  1454.   void update_pv(Move* pv, Move move, Move* childPv) {
  1455.  
  1456.     for (*pv++ = move; childPv && *childPv != MOVE_NONE; )
  1457.         *pv++ = *childPv++;
  1458.     *pv = MOVE_NONE;
  1459.   }
  1460.  
  1461.  
  1462.   // update_continuation_histories() updates histories of the move pairs formed
  1463.   // by moves at ply -1, -2, and -4 with current move.
  1464.  
  1465.   void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus) {
  1466.  
  1467.     for (int i : {1, 2, 4})
  1468.         if (is_ok((ss-i)->currentMove))
  1469.             (*(ss-i)->continuationHistory)[pc][to] << bonus;
  1470.   }
  1471.  
  1472.  
  1473.   // update_capture_stats() updates move sorting heuristics when a new capture best move is found
  1474.  
  1475.   void update_capture_stats(const Position& pos, Move move,
  1476.                             Move* captures, int captureCnt, int bonus) {
  1477.  
  1478.       CapturePieceToHistory& captureHistory =  pos.this_thread()->captureHistory;
  1479.       Piece moved_piece = pos.moved_piece(move);
  1480.       PieceType captured = type_of(pos.piece_on(to_sq(move)));
  1481.  
  1482.       if (pos.capture_or_promotion(move))
  1483.           captureHistory[moved_piece][to_sq(move)][captured] << bonus;
  1484.  
  1485.       // Decrease all the other played capture moves
  1486.       for (int i = 0; i < captureCnt; ++i)
  1487.       {
  1488.           moved_piece = pos.moved_piece(captures[i]);
  1489.           captured = type_of(pos.piece_on(to_sq(captures[i])));
  1490.           captureHistory[moved_piece][to_sq(captures[i])][captured] << -bonus;
  1491.       }
  1492.   }
  1493.  
  1494.  
  1495.   // update_quiet_stats() updates move sorting heuristics when a new quiet best move is found
  1496.  
  1497.   void update_quiet_stats(const Position& pos, Stack* ss, Move move,
  1498.                           Move* quiets, int quietsCnt, int bonus) {
  1499.  
  1500.     if (ss->killers[0] != move)
  1501.     {
  1502.         ss->killers[1] = ss->killers[0];
  1503.         ss->killers[0] = move;
  1504.     }
  1505.  
  1506.     Color us = pos.side_to_move();
  1507.     Thread* thisThread = pos.this_thread();
  1508.     thisThread->mainHistory[us][from_to(move)] << bonus;
  1509.     update_continuation_histories(ss, pos.moved_piece(move), to_sq(move), bonus);
  1510.  
  1511.     if (is_ok((ss-1)->currentMove))
  1512.     {
  1513.         Square prevSq = to_sq((ss-1)->currentMove);
  1514.         thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] = move;
  1515.     }
  1516.  
  1517.     // Decrease all the other played quiet moves
  1518.     for (int i = 0; i < quietsCnt; ++i)
  1519.     {
  1520.         thisThread->mainHistory[us][from_to(quiets[i])] << -bonus;
  1521.         update_continuation_histories(ss, pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus);
  1522.     }
  1523.   }
  1524.  
  1525.   // When playing with strength handicap, choose best move among a set of RootMoves
  1526.   // using a statistical rule dependent on 'level'. Idea by Heinz van Saanen.
  1527.  
  1528.   Move Skill::pick_best(size_t multiPV) {
  1529.  
  1530.     const RootMoves& rootMoves = Threads.main()->rootMoves;
  1531.     static PRNG rng(now()); // PRNG sequence should be non-deterministic
  1532.  
  1533.     // RootMoves are already sorted by score in descending order
  1534.     Value topScore = rootMoves[0].score;
  1535.     int delta = std::min(topScore - rootMoves[multiPV - 1].score, PawnValueMg);
  1536.     int weakness = 120 - 2 * level;
  1537.     int maxScore = -VALUE_INFINITE;
  1538.  
  1539.     // Choose best move. For each move score we add two terms, both dependent on
  1540.     // weakness. One is deterministic and bigger for weaker levels, and one is
  1541.     // random. Then we choose the move with the resulting highest score.
  1542.     for (size_t i = 0; i < multiPV; ++i)
  1543.     {
  1544.         // This is our magic formula
  1545.         int push = (  weakness * int(topScore - rootMoves[i].score)
  1546.                     + delta * (rng.rand<unsigned>() % weakness)) / 128;
  1547.  
  1548.         if (rootMoves[i].score + push >= maxScore)
  1549.         {
  1550.             maxScore = rootMoves[i].score + push;
  1551.             best = rootMoves[i].pv[0];
  1552.         }
  1553.     }
  1554.  
  1555.     return best;
  1556.   }
  1557.  
  1558. } // namespace
  1559.  
  1560. /// MainThread::check_time() is used to print debug info and, more importantly,
  1561. /// to detect when we are out of available time and thus stop the search.
  1562.  
  1563. void MainThread::check_time() {
  1564.  
  1565.   if (--callsCnt > 0)
  1566.       return;
  1567.  
  1568.   // When using nodes, ensure checking rate is not lower than 0.1% of nodes
  1569.   callsCnt = Limits.nodes ? std::min(1024, int(Limits.nodes / 1024)) : 1024;
  1570.  
  1571.   static TimePoint lastInfoTime = now();
  1572.  
  1573.   TimePoint elapsed = Time.elapsed();
  1574.   TimePoint tick = Limits.startTime + elapsed;
  1575.  
  1576.   if (tick - lastInfoTime >= 1000)
  1577.   {
  1578.       lastInfoTime = tick;
  1579.       dbg_print();
  1580.   }
  1581.  
  1582.   // We should not stop pondering until told so by the GUI
  1583.   if (Threads.ponder)
  1584.       return;
  1585.  
  1586.   if (   (Limits.use_time_management() && elapsed > Time.maximum() - 10)
  1587.       || (Limits.movetime && elapsed >= Limits.movetime)
  1588.       || (Limits.nodes && Threads.nodes_searched() >= (uint64_t)Limits.nodes))
  1589.       Threads.stop = true;
  1590. }
  1591.  
  1592.  
  1593. /// UCI::pv() formats PV information according to the UCI protocol. UCI requires
  1594. /// that all (if any) unsearched PV lines are sent using a previous search score.
  1595.  
  1596. string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) {
  1597.  
  1598.   std::stringstream ss;
  1599.   TimePoint elapsed = Time.elapsed() + 1;
  1600.   const RootMoves& rootMoves = pos.this_thread()->rootMoves;
  1601.   size_t pvIdx = pos.this_thread()->pvIdx;
  1602.   size_t multiPV = std::min((size_t)Options["MultiPV"], rootMoves.size());
  1603.   uint64_t nodesSearched = Threads.nodes_searched();
  1604.   uint64_t tbHits = Threads.tb_hits() + (TB::RootInTB ? rootMoves.size() : 0);
  1605.  
  1606.   for (size_t i = 0; i < multiPV; ++i)
  1607.   {
  1608.       bool updated = (i <= pvIdx && rootMoves[i].score != -VALUE_INFINITE);
  1609.  
  1610.       if (depth == ONE_PLY && !updated)
  1611.           continue;
  1612.  
  1613.       Depth d = updated ? depth : depth - ONE_PLY;
  1614.       Value v = updated ? rootMoves[i].score : rootMoves[i].previousScore;
  1615.  
  1616.       bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY;
  1617.       v = tb ? rootMoves[i].tbScore : v;
  1618.  
  1619.       if (ss.rdbuf()->in_avail()) // Not at first line
  1620.           ss << "\n";
  1621.  
  1622.       ss << "info"
  1623.          << " depth "    << d / ONE_PLY
  1624.          << " seldepth " << rootMoves[i].selDepth
  1625.          << " multipv "  << i + 1
  1626.          << " score "    << UCI::value(v);
  1627.  
  1628.       if (!tb && i == pvIdx)
  1629.           ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : "");
  1630.  
  1631.       ss << " nodes "    << nodesSearched
  1632.          << " nps "      << nodesSearched * 1000 / elapsed;
  1633.  
  1634.       if (elapsed > 1000) // Earlier makes little sense
  1635.           ss << " hashfull " << TT.hashfull();
  1636.  
  1637.       ss << " tbhits "   << tbHits
  1638.          << " time "     << elapsed
  1639.          << " pv";
  1640.  
  1641.       for (Move m : rootMoves[i].pv)
  1642.           ss << " " << UCI::move(m, pos.is_chess960());
  1643.   }
  1644.  
  1645.   return ss.str();
  1646. }
  1647.  
  1648.  
  1649. /// RootMove::extract_ponder_from_tt() is called in case we have no ponder move
  1650. /// before exiting the search, for instance, in case we stop the search during a
  1651. /// fail high at root. We try hard to have a ponder move to return to the GUI,
  1652. /// otherwise in case of 'ponder on' we have nothing to think on.
  1653.  
  1654. bool RootMove::extract_ponder_from_tt(Position& pos) {
  1655.  
  1656.     StateInfo st;
  1657.     bool ttHit;
  1658.  
  1659.     assert(pv.size() == 1);
  1660.  
  1661.     if (!pv[0])
  1662.         return false;
  1663.  
  1664.     pos.do_move(pv[0], st);
  1665.     TTEntry* tte = TT.probe(pos.key(), ttHit);
  1666.  
  1667.     if (ttHit)
  1668.     {
  1669.         Move m = tte->move(); // Local copy to be SMP safe
  1670.         if (MoveList<LEGAL>(pos).contains(m))
  1671.             pv.push_back(m);
  1672.     }
  1673.  
  1674.     pos.undo_move(pv[0]);
  1675.     return pv.size() > 1;
  1676. }
  1677.  
  1678. void Tablebases::rank_root_moves(Position& pos, Search::RootMoves& rootMoves) {
  1679.  
  1680.     RootInTB = false;
  1681.     UseRule50 = bool(Options["Syzygy50MoveRule"]);
  1682.     ProbeDepth = int(Options["SyzygyProbeDepth"]) * ONE_PLY;
  1683.     Cardinality = int(Options["SyzygyProbeLimit"]);
  1684.     bool dtz_available = true;
  1685.  
  1686.     // Tables with fewer pieces than SyzygyProbeLimit are searched with
  1687.     // ProbeDepth == DEPTH_ZERO
  1688.     if (Cardinality > MaxCardinality)
  1689.     {
  1690.         Cardinality = MaxCardinality;
  1691.         ProbeDepth = DEPTH_ZERO;
  1692.     }
  1693.  
  1694.     if (Cardinality >= popcount(pos.pieces()) && !pos.can_castle(ANY_CASTLING))
  1695.     {
  1696.         // Rank moves using DTZ tables
  1697.         RootInTB = root_probe(pos, rootMoves);
  1698.  
  1699.         if (!RootInTB)
  1700.         {
  1701.             // DTZ tables are missing; try to rank moves using WDL tables
  1702.             dtz_available = false;
  1703.             RootInTB = root_probe_wdl(pos, rootMoves);
  1704.         }
  1705.     }
  1706.  
  1707.     if (RootInTB)
  1708.     {
  1709.         // Sort moves according to TB rank
  1710.         std::sort(rootMoves.begin(), rootMoves.end(),
  1711.                   [](const RootMove &a, const RootMove &b) { return a.tbRank > b.tbRank; } );
  1712.  
  1713.         // Probe during search only if DTZ is not available and we are winning
  1714.         if (dtz_available || rootMoves[0].tbScore <= VALUE_DRAW)
  1715.             Cardinality = 0;
  1716.     }
  1717.     else
  1718.     {
  1719.         // Assign the same rank to all moves
  1720.         for (auto& m : rootMoves)
  1721.             m.tbRank = 0;
  1722.     }
  1723. }
  1724.