Subversion Repositories Games.Chess Giants

Rev

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