Subversion Repositories Games.Chess Giants

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. /*
  2.     Texel - A UCI chess engine.
  3.     Copyright (C) 2012-2014  Peter Österlund, peterosterlund2@gmail.com
  4.  
  5.     This program is free software: you can redistribute it and/or modify
  6.     it under the terms of the GNU General Public License as published by
  7.     the Free Software Foundation, either version 3 of the License, or
  8.     (at your option) any later version.
  9.  
  10.     This program is distributed in the hope that it will be useful,
  11.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.     GNU General Public License for more details.
  14.  
  15.     You should have received a copy of the GNU General Public License
  16.     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17. */
  18.  
  19. /*
  20.  * search.cpp
  21.  *
  22.  *  Created on: Feb 25, 2012
  23.  *      Author: petero
  24.  */
  25.  
  26. #include "search.hpp"
  27. #include "numa.hpp"
  28. #include "tbprobe.hpp"
  29. #include "treeLogger.hpp"
  30. #include "textio.hpp"
  31. #include "util/logger.hpp"
  32.  
  33. #include <iostream>
  34. #include <iomanip>
  35. #include <cmath>
  36. #include <limits>
  37.  
  38. using namespace SearchConst;
  39. using namespace Logger;
  40.  
  41. Search::Search(const Position& pos0, const std::vector<U64>& posHashList0,
  42.                int posHashListSize0, SearchTables& st, ParallelData& pd0,
  43.                const std::shared_ptr<SplitPoint>& rootSp,
  44.                TreeLogger& logFile0)
  45.     : eval(st.et), kt(st.kt), ht(st.ht), tt(st.tt), pd(pd0), threadNo(0),
  46.       mainNumaNode(true), logFile(logFile0) {
  47.     stopHandler = std::make_shared<DefaultStopHandler>(*this);
  48.     spVec.push_back(rootSp);
  49.     init(pos0, posHashList0, posHashListSize0);
  50. }
  51.  
  52. void
  53. Search::init(const Position& pos0, const std::vector<U64>& posHashList0,
  54.              int posHashListSize0) {
  55.     pos = pos0;
  56.     posHashList = posHashList0;
  57.     posHashListSize = posHashListSize0;
  58.     posHashFirstNew = posHashListSize;
  59.     initNodeStats();
  60.     minTimeMillis = -1;
  61.     maxTimeMillis = -1;
  62.     searchNeedMoreTime = false;
  63.     maxNodes = -1;
  64.     minProbeDepth = 0;
  65.     nodesBetweenTimeCheck = 10000;
  66.     strength = 1000;
  67.     weak = false;
  68.     randomSeed = 0;
  69.     tLastStats = currentTimeMillis();
  70.     totalNodes = 0;
  71.     tbHits = 0;
  72.     nodesToGo = 0;
  73.     verbose = false;
  74. }
  75.  
  76. void
  77. Search::timeLimit(int minTimeLimit, int maxTimeLimit) {
  78.     minTimeMillis = minTimeLimit;
  79.     maxTimeMillis = maxTimeLimit;
  80.     if ((maxTimeMillis >= 0) && (maxTimeMillis < 1000))
  81.         nodesBetweenTimeCheck = 1000;
  82.     else
  83.         nodesBetweenTimeCheck = 10000;
  84. }
  85.  
  86. void
  87. Search::setStrength(int strength, U64 randomSeed) {
  88.     if (strength < 0) strength = 0;
  89.     if (strength > 1000) strength = 1000;
  90.     this->strength = strength;
  91.     weak = strength < 1000;
  92.     this->randomSeed = randomSeed;
  93. }
  94.  
  95. Move
  96. Search::iterativeDeepening(const MoveList& scMovesIn,
  97.                            int maxDepth, U64 initialMaxNodes,
  98.                            bool verbose, int maxPV, bool onlyExact,
  99.                            int minProbeDepth) {
  100.     tStart = currentTimeMillis();
  101.     totalNodes = 0;
  102.     tbHits = 0;
  103.     nodesToGo = 0;
  104.     if (scMovesIn.size <= 0)
  105.         return Move(); // No moves to search
  106.  
  107.     logFile.open("/home/petero/treelog.dmp", pd, threadNo);
  108.     const U64 rootNodeIdx = logFile.logPosition(pos, 0, 0, 0);
  109.  
  110.     kt.clear();
  111.     pd.npsInfo.reset();
  112. //    pd.wq.resetStat();
  113.     const bool smp = pd.numHelperThreads() > 0;
  114.     maxNodes = initialMaxNodes;
  115.     this->minProbeDepth = (TBProbe::tbEnabled() ? minProbeDepth : MAX_SEARCH_DEPTH) * plyScale;
  116.     std::vector<MoveInfo> rootMoves;
  117.     getRootMoves(scMovesIn, rootMoves, maxDepth);
  118.  
  119.     Position origPos(pos);
  120.     bool firstIteration = true;
  121.     Move bestMove = rootMoves[0].move; // bestMove is != rootMoves[0].move when there is an unresolved fail high
  122.     Move bestExactMove = rootMoves[0].move; // Only updated when new best move has exact score
  123.     this->verbose = verbose;
  124.     if ((maxDepth < 0) || (maxDepth > MAX_SEARCH_DEPTH))
  125.         maxDepth = MAX_SEARCH_DEPTH;
  126.     maxPV = std::min(maxPV, (int)rootMoves.size());
  127.     for (size_t i = 0; i < COUNT_OF(searchTreeInfo); i++) {
  128.         searchTreeInfo[i].allowNullMove = true;
  129.         searchTreeInfo[i].singularMove.setMove(0,0,0,0);
  130.     }
  131.     ht.reScale();
  132.     int posHashFirstNew0 = posHashFirstNew;
  133.     try {
  134.     for (int depthS = plyScale; ; depthS += plyScale, firstIteration = false) {
  135.         initNodeStats();
  136.         if (listener) listener->notifyDepth(depthS/plyScale);
  137.         int aspirationDelta = 0;
  138.         int alpha = 0;
  139.         UndoInfo ui;
  140.         bool needMoreTime = false;
  141.         for (int mi = 0; mi < (int)rootMoves.size(); mi++) {
  142.             posHashFirstNew = posHashFirstNew0 + ((mi > 0 && maxPV > 1) ? 1 : 0);
  143.             if (mi < maxPV)
  144.                 aspirationDelta = isWinScore(std::abs(rootMoves[mi].score())) ? 3000 : aspirationWindow;
  145.             if (firstIteration)
  146.                 alpha = -MATE0;
  147.             else if (mi < maxPV)
  148.                 alpha = std::max(rootMoves[mi].score() - aspirationDelta, -MATE0);
  149.             else
  150.                 alpha = rootMoves[maxPV-1].score();
  151.  
  152.             searchNeedMoreTime = (mi > 0);
  153.             Move& m = rootMoves[mi].move;
  154.             pd.topMove = m;
  155.             if (currentTimeMillis() - tStart >= 1000)
  156.                 if (listener) listener->notifyCurrMove(m, mi + 1);
  157.             S64 nodesThisMove = -totalNodes;
  158.             posHashList[posHashListSize++] = pos.zobristHash();
  159.             bool givesCheck = MoveGen::givesCheck(pos, m);
  160.             int beta;
  161.             if (firstIteration)
  162.                 beta = MATE0;
  163.             else if (mi < maxPV)
  164.                 beta = std::min(rootMoves[mi].score() + aspirationDelta, MATE0);
  165.             else
  166.                 beta = alpha + 1;
  167.  
  168.             int lmrS = 0;
  169.             bool isCapture = (pos.getPiece(m.to()) != Piece::EMPTY);
  170.             bool isPromotion = (m.promoteTo() != Piece::EMPTY);
  171.             if ((depthS >= 3*plyScale) && !isCapture && !isPromotion &&
  172.                 !givesCheck && !passedPawnPush(pos, m) && (mi >= rootLMRMoveCount + maxPV)) {
  173.                 lmrS = plyScale;
  174.             }
  175.             pos.makeMove(m, ui);
  176.             totalNodes++;
  177.             SearchTreeInfo& sti = searchTreeInfo[0];
  178.             sti.currentMove = m;
  179.             sti.currentMoveNo = mi;
  180.             sti.lmr = lmrS;
  181.             sti.nodeIdx = rootNodeIdx;
  182.             int score = -negaScout(smp, true, -beta, -alpha, 1, depthS - lmrS - plyScale, -1, givesCheck);
  183.             if ((lmrS > 0) && (score > alpha)) {
  184.                 sti.lmr = 0;
  185.                 score = -negaScout(smp, true, -beta, -alpha, 1, depthS - plyScale, -1, givesCheck);
  186.             }
  187.             nodesThisMove += totalNodes;
  188.             posHashListSize--;
  189.             pos.unMakeMove(m, ui);
  190.             storeSearchResult(rootMoves, mi, depthS, alpha, beta, score);
  191.             if ((verbose && firstIteration) || (mi < maxPV) || (score > rootMoves[maxPV-1].score()))
  192.                 notifyPV(rootMoves, mi, maxPV);
  193.             int betaRetryDelta = aspirationDelta;
  194.             int alphaRetryDelta = aspirationDelta;
  195.             while ((score >= beta) || ((mi < maxPV) && (score <= alpha))) {
  196.                 nodesThisMove -= totalNodes;
  197.                 posHashList[posHashListSize++] = pos.zobristHash();
  198.                 bool fh = score >= beta;
  199.                 if (fh) {
  200.                     if (isWinScore(score))
  201.                         betaRetryDelta = MATE0; // Don't use aspiration window when searching for faster mate
  202.                     beta = std::min(score + betaRetryDelta, MATE0);
  203.                     betaRetryDelta = betaRetryDelta * 3 / 2;
  204.                     if (mi != 0)
  205.                         needMoreTime = true;
  206.                     bestMove = m;
  207.                 } else { // score <= alpha
  208.                     if (isLoseScore(score))
  209.                         alphaRetryDelta = MATE0; // Don't use aspiration window when searching for faster mate
  210.                     alpha = std::max(score - alphaRetryDelta, -MATE0);
  211.                     alphaRetryDelta = alphaRetryDelta * 3 / 2;
  212.                     needMoreTime = searchNeedMoreTime = true;
  213.                 }
  214.                 pos.makeMove(m, ui);
  215.                 totalNodes++;
  216.                 score = -negaScout(smp, true, -beta, -alpha, 1, depthS - plyScale, -1, givesCheck);
  217.                 nodesThisMove += totalNodes;
  218.                 posHashListSize--;
  219.                 pos.unMakeMove(m, ui);
  220.                 storeSearchResult(rootMoves, mi, depthS, alpha, beta, score);
  221.                 notifyPV(rootMoves, mi, maxPV);
  222.             }
  223.             rootMoves[mi].nodes += nodesThisMove;
  224.             if ((mi < maxPV) || (score > rootMoves[maxPV-1].move.score())) {
  225.                 MoveInfo tmp = rootMoves[mi];
  226.                 int i = mi;
  227.                 while ((i > 0) && (rootMoves[i-1].score() < tmp.score())) {
  228.                     rootMoves[i] = rootMoves[i-1];
  229.                     i--;
  230.                 }
  231.                 rootMoves[i] = tmp;
  232.             }
  233.             bestMove = rootMoves[0].move;
  234.             bestExactMove = bestMove;
  235.             if (!firstIteration) {
  236.                 S64 timeLimit = needMoreTime ? maxTimeMillis : minTimeMillis;
  237.                 if (timeLimit >= 0) {
  238.                     U64 tNow = currentTimeMillis();
  239.                     if (tNow - tStart >= (U64)timeLimit)
  240.                         break;
  241.                 }
  242.             }
  243.         }
  244.         S64 tNow = currentTimeMillis();
  245.         if (verbose) {
  246.             for (int i = nodesByPly.minValue(); i < nodesByPly.maxValue(); i++)
  247.                 std::cout << std::setw(2) << i
  248.                           << ' ' << std::setw(7) << nodesByPly.get(i)
  249.                           << ' ' << std::setw(7) << nodesByDepth.get(i)
  250.                           << std::endl;
  251.             std::stringstream ss;
  252.             ss.precision(3);
  253.             ss << std::fixed << "Time: " << ((tNow - tStart) * .001);
  254.             ss.precision(2);
  255.             ss << " depth:" << (depthS/(double)plyScale)
  256.                << " nps:" << ((int)(getTotalNodes() / ((tNow - tStart) * .001)));
  257.             std::cout << ss.str() << std::endl;
  258.         }
  259.         if (maxTimeMillis >= 0)
  260.             if (tNow - tStart >= minTimeMillis)
  261.                 break;
  262.         if (depthS >= maxDepth * plyScale)
  263.             break;
  264.         if (maxNodes >= 0)
  265.             if (getTotalNodes() >= maxNodes)
  266.                 break;
  267.         bool enoughDepth = true;
  268.         for (int i = 0; i < maxPV; i++) {
  269.             int plyToMate = MATE0 - std::abs(rootMoves[i].score());
  270.             if (depthS < plyToMate * plyScale)
  271.                 enoughDepth = false;
  272.         }
  273.         if (enoughDepth)
  274.             break;
  275.         if (tNow > tStart)
  276.             pd.npsInfo.setBaseNps(getTotalNodesThisThread() * 1000.0 / (tNow - tStart));
  277.         if (firstIteration) {
  278.             std::stable_sort(rootMoves.begin()+maxPV, rootMoves.end(), MoveInfo::SortByScore());
  279.         } else {
  280.             // Moves that were hard to search should be searched early in the next iteration
  281.             std::stable_sort(rootMoves.begin()+maxPV, rootMoves.end(), MoveInfo::SortByNodes());
  282.         }
  283. //        std::cout << "fhInfo depth:" << depthS / plyScale << std::endl;
  284. //        pd.fhInfo.print(std::cout);
  285. //        std::cout << "wqStats depth:" << depthS / plyScale << std::endl;
  286. //        pd.wq.printStats(std::cout, pd.numHelperThreads() + 1);
  287. //        log([&](std::ostream& os){pd.npsInfo.print(os, depthS / plyScale);});
  288.     }
  289.     } catch (const StopSearch&) {
  290.         pos = origPos;
  291.     }
  292.     notifyStats();
  293.  
  294.     logFile.close();
  295.     return onlyExact ? bestExactMove : bestMove;
  296. }
  297.  
  298. void
  299. Search::storeSearchResult(std::vector<MoveInfo>& scMoves, int mi, int depth,
  300.                           int alpha, int beta, int score) {
  301. //    std::cout << "d:" << depth/plyScale << " mi:" << mi << " a:" << alpha
  302. //              << " b:" << beta << " s:" << score << std::endl;
  303.     scMoves[mi].depth = depth;
  304.     scMoves[mi].alpha = alpha;
  305.     scMoves[mi].beta = beta;
  306.     scMoves[mi].move.setScore(score);
  307.     scMoves[mi].pv.clear();
  308.     tt.extractPVMoves(pos, scMoves[mi].move, scMoves[mi].pv);
  309.     if ((maxTimeMillis < 0) && SearchConst::isWinScore(std::abs(score)))
  310.         TBProbe::extendPV(pos, scMoves[mi].pv);
  311. }
  312.  
  313. void
  314. Search::notifyPV(const std::vector<MoveInfo>& moveInfo, int mi, int maxPV) {
  315.     bool miNotified = false;
  316.     int lastReportedDepth = -1;
  317.     for (int i = 0, n = 0; n < maxPV; i++) {
  318.         if (!miNotified && (moveInfo[mi].score() > moveInfo[i].score()) &&
  319.             (moveInfo[mi].score() > moveInfo[mi].alpha)) {
  320.             notifyPV(moveInfo[mi], maxPV > 1 ? n : -1);
  321.             lastReportedDepth = moveInfo[mi].depth;
  322.             miNotified = true;
  323.             n++;
  324.             if (n >= maxPV)
  325.                 break;
  326.         }
  327.         if (i == mi) {
  328.             if (!miNotified) {
  329.                 notifyPV(moveInfo[mi], maxPV > 1 ? n : -1);
  330.                 lastReportedDepth = moveInfo[mi].depth;
  331.                 miNotified = true;
  332.                 n++;
  333.             }
  334.         } else {
  335.             notifyPV(moveInfo[i], maxPV > 1 ? n : -1);
  336.             lastReportedDepth = moveInfo[i].depth;
  337.             n++;
  338.         }
  339.     }
  340.     if (listener && (moveInfo[mi].depth != lastReportedDepth))
  341.         listener->notifyDepth(moveInfo[mi].depth/plyScale);
  342. }
  343.  
  344. void
  345. Search::notifyPV(const MoveInfo& info, int multiPVIndex) {
  346.     if (info.depth <= 0)
  347.         return;
  348.     bool uBound = info.score() <= info.alpha;
  349.     bool lBound = info.score() >= info.beta;
  350.     int score = info.move.score();
  351.     if (verbose) {
  352.         std::stringstream ss;
  353.         ss << std::setw(6) << std::left << TextIO::moveToString(pos, info.move, false)
  354.            << ' ' << std::setw(6) << std::right << score
  355.            << ' ' << std::setw(6) << totalNodes;
  356.         if (uBound)
  357.             ss << " <=";
  358.         else if (lBound)
  359.             ss << " >=";
  360.         else {
  361.             std::string PV = TextIO::moveToString(pos, info.move, false) + " ";
  362.             UndoInfo ui;
  363.             pos.makeMove(info.move, ui);
  364.             PV += tt.extractPV(pos);
  365.             pos.unMakeMove(info.move, ui);
  366.             ss << ' ' << PV;
  367.         }
  368.         std::cout << ss.str() << std::endl;
  369.     }
  370.     if (!listener)
  371.         return;
  372.     bool isMate = false;
  373.     if (isWinScore(score)) {
  374.         isMate = true;
  375.         score = (MATE0 - score) / 2;
  376.     } else if (isLoseScore(score)) {
  377.         isMate = true;
  378.         score = -((MATE0 + score - 1) / 2);
  379.     }
  380.     U64 tNow = currentTimeMillis();
  381.     int time = (int) (tNow - tStart);
  382.     S64 totNodes = getTotalNodes();
  383.     S64 tbHits = getTbHits();
  384.     int nps = (time > 0) ? (int)(totNodes / (time / 1000.0)) : 0;
  385.     listener->notifyPV(info.depth/plyScale, score, time, totNodes, nps, isMate,
  386.                        uBound, lBound, info.pv, multiPVIndex, tbHits);
  387. }
  388.  
  389. void
  390. Search::notifyStats() {
  391.     S64 tNow = currentTimeMillis();
  392.     if (listener) {
  393.         int time = (int) (tNow - tStart);
  394.         S64 totNodes = getTotalNodes();
  395.         int nps = (time > 0) ? (int)(totNodes / (time / 1000.0)) : 0;
  396.         S64 tbHits = getTbHits();
  397.         listener->notifyStats(totNodes, nps, tbHits, time);
  398.     }
  399.     tLastStats = tNow;
  400. }
  401.  
  402. bool
  403. Search::shouldStop() {
  404.     S64 tNow = currentTimeMillis();
  405.     S64 timeLimit = searchNeedMoreTime ? maxTimeMillis : minTimeMillis;
  406.     if (    ((timeLimit >= 0) && (tNow - tStart >= timeLimit)) ||
  407.             ((maxNodes >= 0) && (getTotalNodes() >= maxNodes)))
  408.         return true;
  409.     if (tNow - tLastStats >= 1000)
  410.         notifyStats();
  411.     return false;
  412. }
  413.  
  414. template <bool smp, bool tb>
  415. int
  416. Search::negaScout(int alpha, int beta, int ply, int depth, int recaptureSquare,
  417.                   const bool inCheck) {
  418.     using SplitPointHolder = typename SplitPointTraits<smp>::SpHolder;
  419.  
  420.     // Mate distance pruning
  421.     beta = std::min(beta, MATE0-ply-1);
  422.     if (alpha >= beta)
  423.         return alpha;
  424.  
  425.     if (logFile.isOpened()) {
  426.         const SearchTreeInfo& sti = searchTreeInfo[ply-1];
  427.         U64 idx = logFile.logNodeStart(sti.nodeIdx, sti.currentMove, alpha, beta, ply, depth);
  428.         searchTreeInfo[ply].nodeIdx = idx;
  429.     }
  430.     if (nodesToGo <= 0) {
  431.         nodesToGo = nodesBetweenTimeCheck;
  432.         if (stopHandler->shouldStop())
  433.             throw StopSearch();
  434.     }
  435.  
  436.     // Collect statistics
  437.     if (verbose) {
  438.         nodesByPly.add(ply);
  439.         nodesByDepth.add(depth/plyScale);
  440.     }
  441.     const U64 hKey = pos.historyHash();
  442.     SearchTreeInfo& sti = searchTreeInfo[ply];
  443.     sti.currentMove = emptyMove;
  444.     sti.currentMoveNo = -1;
  445.  
  446.     // Draw tests
  447.     if (canClaimDraw50(pos)) {
  448.         if (inCheck) {
  449.             MoveList moves;
  450.             MoveGen::pseudoLegalMoves(pos, moves);
  451.             MoveGen::removeIllegal(pos, moves);
  452.             if (moves.size == 0) {            // Can't claim draw if already check mated.
  453.                 int score = -(MATE0-(ply+1));
  454.                 logFile.logNodeEnd(searchTreeInfo[ply].nodeIdx, score, TType::T_EXACT, UNKNOWN_SCORE, hKey);
  455.                 return score;
  456.             }
  457.         }
  458.         logFile.logNodeEnd(searchTreeInfo[ply].nodeIdx, 0, TType::T_EXACT, UNKNOWN_SCORE, hKey);
  459.         return 0;
  460.     }
  461.     if (canClaimDrawRep(pos, posHashList, posHashListSize, posHashFirstNew)) {
  462.         logFile.logNodeEnd(searchTreeInfo[ply].nodeIdx, 0, TType::T_EXACT, UNKNOWN_SCORE, hKey);
  463.         return 0;            // No need to test for mate here, since it would have been
  464.                              // discovered the first time the position came up.
  465.     }
  466.  
  467.     // Check transposition table
  468.     int evalScore = UNKNOWN_SCORE;
  469.     TranspositionTable::TTEntry ent;
  470.     ent.clear();
  471.     const bool singularSearch = !sti.singularMove.isEmpty();
  472.     const bool useTT = (mainNumaNode || (depth >= 1 * plyScale)) && // To reduce memory bandwidth
  473.                        !singularSearch;
  474.     if (useTT) tt.probe(hKey, ent);
  475.     Move hashMove;
  476.     if (ent.getType() != TType::T_EMPTY) {
  477.         int score = ent.getScore(ply);
  478.         evalScore = ent.getEvalScore();
  479.         ent.getMove(hashMove);
  480.         if (((beta == alpha + 1) || (depth <= ply*plyScale)) && ent.isCutOff(alpha, beta, ply, depth)) {
  481.             if (score >= beta) {
  482.                 if (!hashMove.isEmpty())
  483.                     if (pos.getPiece(hashMove.to()) == Piece::EMPTY)
  484.                         kt.addKiller(ply, hashMove);
  485.             }
  486.             sti.bestMove = hashMove;
  487.             logFile.logNodeEnd(sti.nodeIdx, score, ent.getType(), evalScore, hKey);
  488.             return score;
  489.         }
  490.     }
  491.     if (singularSearch)
  492.         hashMove = sti.singularMove;
  493.  
  494.     // Probe endgame tablebases
  495.     const int illegalScore = -(MATE0-(ply+1));
  496.     int tbScore = illegalScore;
  497.     if (tb && depth >= minProbeDepth && !singularSearch) {
  498.         TranspositionTable::TTEntry tbEnt;
  499.         tbEnt.clear();
  500.         if (TBProbe::tbProbe(pos, ply, alpha, beta, tbEnt)) {
  501.             tbHits++;
  502.             nodesToGo -= 1000;
  503.             int type = tbEnt.getType();
  504.             int score = tbEnt.getScore(ply);
  505.             bool cutOff = false;
  506.             if (score == 0 && type == TType::T_EXACT) {
  507.                 const int maxSwindle = 50;
  508.                 if (depth < 16 * plyScale) {
  509.                     if (evalScore == UNKNOWN_SCORE)
  510.                         evalScore = eval.evalPos(pos);
  511.                     score = Evaluate::swindleScore(evalScore);
  512.                     cutOff = true;
  513.                 } else if (alpha >= maxSwindle) {
  514.                     tbEnt.setType(TType::T_LE);
  515.                     score = maxSwindle;
  516.                     cutOff = true;
  517.                 } else if (beta <= -maxSwindle) {
  518.                     tbEnt.setType(TType::T_GE);
  519.                     score = -maxSwindle;
  520.                     cutOff = true;
  521.                 }
  522.             } else {
  523.                 if ( (type == TType::T_EXACT) ||
  524.                     ((type == TType::T_GE) && (score >= beta)) ||
  525.                     ((type == TType::T_LE) && (score <= alpha)))
  526.                     cutOff = true;
  527.             }
  528.             if (cutOff) {
  529.                 emptyMove.setScore(score);
  530.                 if (useTT) tt.insert(hKey, emptyMove, tbEnt.getType(), ply, depth, evalScore);
  531.                 logFile.logNodeEnd(sti.nodeIdx, score, tbEnt.getType(), evalScore, hKey);
  532.                 return score;
  533.             }
  534.             if ((type == TType::T_GE) && (score > alpha)) {
  535.                 tbScore = score;
  536.                 alpha = score - 1;
  537.             }
  538.         }
  539.     }
  540.  
  541.     int posExtend = inCheck ? plyScale : 0; // Check extension
  542.  
  543.     // If out of depth, perform quiescence search
  544.     if (depth + posExtend <= 0) {
  545.         q0Eval = evalScore;
  546.         sti.bestMove.setMove(0,0,0,0);
  547.         int score = quiesce(alpha, beta, ply, 0, inCheck);
  548.         int type = TType::T_EXACT;
  549.         if (score <= alpha) {
  550.             type = TType::T_LE;
  551.         } else if (score >= beta) {
  552.             type = TType::T_GE;
  553.         }
  554.         sti.bestMove.setScore(score);
  555.         if (useTT) tt.insert(hKey, sti.bestMove, type, ply, depth, q0Eval);
  556.         logFile.logNodeEnd(sti.nodeIdx, score, type, q0Eval, hKey);
  557.         return score;
  558.     }
  559.  
  560.     // Razoring
  561.     const bool normalBound = !isLoseScore(alpha) && !isWinScore(beta);
  562.     if (normalBound && (depth < 4*plyScale) && (beta == alpha + 1) && !singularSearch) {
  563.         if (evalScore == UNKNOWN_SCORE) {
  564.             evalScore = eval.evalPos(pos);
  565.         }
  566.         const int razorMargin = (depth <= plyScale) ? (int)razorMargin1 : (int)razorMargin2; // Pierre-Marie Baty -- added type cast
  567.         if (evalScore < beta - razorMargin) {
  568.             q0Eval = evalScore;
  569.             int score = quiesce(alpha-razorMargin, beta-razorMargin, ply, 0, inCheck);
  570.             if (score <= alpha-razorMargin) {
  571.                 emptyMove.setScore(score);
  572.                 if (useTT) tt.insert(hKey, emptyMove, TType::T_LE, ply, depth, q0Eval);
  573.                 logFile.logNodeEnd(sti.nodeIdx, score, TType::T_LE, q0Eval, hKey);
  574.                 return score;
  575.             }
  576.         }
  577.     }
  578.  
  579.     // Reverse futility pruning
  580.     if (!inCheck && (depth < 5*plyScale) && (posExtend == 0) && normalBound && !singularSearch) {
  581.         bool mtrlOk;
  582.         if (pos.isWhiteMove()) {
  583.             mtrlOk = (pos.wMtrl() > pos.wMtrlPawns()) && (pos.wMtrlPawns() > 0);
  584.         } else {
  585.             mtrlOk = (pos.bMtrl() > pos.bMtrlPawns()) && (pos.bMtrlPawns() > 0);
  586.         }
  587.         if (mtrlOk) {
  588.             int margin;
  589.             if (depth <= plyScale)        margin = reverseFutilityMargin1;
  590.             else if (depth <= 2*plyScale) margin = reverseFutilityMargin2;
  591.             else if (depth <= 3*plyScale) margin = reverseFutilityMargin3;
  592.             else                          margin = reverseFutilityMargin4;
  593.             if (evalScore == UNKNOWN_SCORE)
  594.                 evalScore = eval.evalPos(pos);
  595.             if (evalScore - margin >= beta) {
  596.                 emptyMove.setScore(evalScore - margin);
  597.                 if (useTT) tt.insert(hKey, emptyMove, TType::T_GE, ply, depth, evalScore);
  598.                 logFile.logNodeEnd(sti.nodeIdx, evalScore - margin, TType::T_GE, evalScore, hKey);
  599.                 return evalScore - margin;
  600.             }
  601.         }
  602.     }
  603.  
  604.     // Null-move pruning
  605.     if ((depth >= 3*plyScale) && !inCheck && sti.allowNullMove && !isWinScore(beta) && !singularSearch) {
  606.         bool nullOk;
  607.         if (pos.isWhiteMove()) {
  608.             nullOk = (pos.wMtrl() > pos.wMtrlPawns()) && (pos.wMtrlPawns() > 0);
  609.         } else {
  610.             nullOk = (pos.bMtrl() > pos.bMtrlPawns()) && (pos.bMtrlPawns() > 0);
  611.         }
  612.         const int R = (depth > 6*plyScale) ? 4*plyScale : 3*plyScale;
  613.         if (nullOk) {
  614.             if (((ent.getType() == TType::T_EXACT) || (ent.getType() == TType::T_LE)) &&
  615.                 (ent.getDepth() >= depth - R) && (ent.getScore(ply) < beta))
  616.                 nullOk = false;
  617.         }
  618.         if (nullOk) {
  619.             if (evalScore == UNKNOWN_SCORE)
  620.                 evalScore = eval.evalPos(pos);
  621.             if (evalScore < beta)
  622.                 nullOk = false;
  623.         }
  624.         if (nullOk) {
  625.             int score;
  626.             {
  627.                 SplitPointHolder sph(pd, spVec, pending);
  628.                 if (smp) {
  629.                     sph.setSp(std::make_shared<SplitPoint>(threadNo, spVec.back(),
  630.                                                            searchTreeInfo[ply-1].currentMoveNo,
  631.                                                            pos, posHashList, posHashListSize,
  632.                                                            sti, kt, ht, alpha, beta, ply, depth / plyScale));
  633.                     sph.addMove(0, SplitPointMove(Move(), 0, 0, -1, false));
  634.                     sph.addToQueue();
  635.                     sph.setOwnerCurrMove(0, alpha);
  636.                 }
  637.                 pos.setWhiteMove(!pos.isWhiteMove());
  638.                 int epSquare = pos.getEpSquare();
  639.                 pos.setEpSquare(-1);
  640.                 searchTreeInfo[ply+1].allowNullMove = false;
  641.                 searchTreeInfo[ply+1].bestMove.setMove(0,0,0,0);
  642.                 score = -negaScout(smp, tb, -beta, -(beta - 1), ply + 1, depth - R, -1, false);
  643.                 searchTreeInfo[ply+1].allowNullMove = true;
  644.                 pos.setEpSquare(epSquare);
  645.                 pos.setWhiteMove(!pos.isWhiteMove());
  646.             }
  647.             bool storeInHash = true;
  648.             if ((score >= beta) && (depth >= 10 * plyScale)) {
  649.                 // Null-move verification search
  650.                 SearchTreeInfo& sti2 = searchTreeInfo[ply-1];
  651.                 const Move savedMove = sti2.currentMove;
  652.                 const int savedMoveNo = sti2.currentMoveNo;
  653.                 const S64 savedNodeIdx2 = sti2.nodeIdx;
  654.                 sti2.currentMove = Move(1,1,0); // Represents "no move"
  655.                 sti2.currentMoveNo = -1;
  656.                 sti2.nodeIdx = sti.nodeIdx;
  657.                 const S64 savedNodeIdx = sti.nodeIdx;
  658.                 sti.allowNullMove = false;
  659.                 score = negaScout(smp, tb, beta - 1, beta, ply, depth - R, recaptureSquare, inCheck);
  660.                 sti.allowNullMove = true;
  661.                 sti.nodeIdx = savedNodeIdx;
  662.                 sti2.currentMove = savedMove;
  663.                 sti2.currentMoveNo = savedMoveNo;
  664.                 sti2.nodeIdx = savedNodeIdx2;
  665.                 searchTreeInfo[ply+1].bestMove.setMove(0,0,0,0);
  666.                 storeInHash = false;
  667.             }
  668.             if (smp && (depth - R >= MIN_SMP_DEPTH * plyScale))
  669.                 pd.fhInfo.addData(-1, searchTreeInfo[ply+1].currentMoveNo, score < beta, false);
  670.             if (score >= beta) {
  671.                 if (isWinScore(score))
  672.                     score = beta;
  673.                 emptyMove.setScore(score);
  674.                 if (storeInHash)
  675.                     if (useTT) tt.insert(hKey, emptyMove, TType::T_GE, ply, depth, evalScore);
  676.                 logFile.logNodeEnd(sti.nodeIdx, score, TType::T_GE, evalScore, hKey);
  677.                 return score;
  678.             }
  679.         }
  680.     }
  681.  
  682.     bool futilityPrune = false;
  683.     int futilityScore = alpha;
  684.     if (!inCheck && (depth < 5*plyScale) && (posExtend == 0) && normalBound && !singularSearch) {
  685.         int margin;
  686.         if (depth <= plyScale)        margin = futilityMargin1;
  687.         else if (depth <= 2*plyScale) margin = futilityMargin2;
  688.         else if (depth <= 3*plyScale) margin = futilityMargin3;
  689.         else                          margin = futilityMargin4;
  690.         if (evalScore == UNKNOWN_SCORE)
  691.             evalScore = eval.evalPos(pos);
  692.         futilityScore = evalScore + margin;
  693.         if (futilityScore <= alpha)
  694.             futilityPrune = true;
  695.     }
  696.  
  697.     // Internal iterative deepening
  698.     if ((depth > 4*plyScale) && hashMove.isEmpty()) {
  699.         bool isPv = beta > alpha + 1;
  700.         if (isPv || (depth > 8 * plyScale)) {
  701.             SearchTreeInfo& sti2 = searchTreeInfo[ply-1];
  702.             Move savedMove = sti2.currentMove;
  703.             int savedMoveNo = sti2.currentMoveNo;
  704.             S64 savedNodeIdx2 = sti2.nodeIdx;
  705.             sti2.currentMove = Move(1,1,0); // Represents "no move"
  706.             sti2.currentMoveNo = -1;
  707.             sti2.nodeIdx = sti.nodeIdx;
  708.  
  709.             S64 savedNodeIdx = sti.nodeIdx;
  710.             int newDepth = isPv ? depth  - 2 * plyScale : depth * 3 / 8;
  711.             negaScout(smp, tb, alpha, beta, ply, newDepth, -1, inCheck);
  712.             sti.nodeIdx = savedNodeIdx;
  713.  
  714.             sti2.currentMove = savedMove;
  715.             sti2.currentMoveNo = savedMoveNo;
  716.             sti2.nodeIdx = savedNodeIdx2;
  717.  
  718.             tt.probe(hKey, ent);
  719.             if (ent.getType() != TType::T_EMPTY)
  720.                 ent.getMove(hashMove);
  721.         }
  722.     }
  723.  
  724.     // Generate move list
  725.     MoveList moves;
  726.     if (inCheck)
  727.         MoveGen::checkEvasions(pos, moves);
  728.     else
  729.         MoveGen::pseudoLegalMoves(pos, moves);
  730.     bool seeDone = false;
  731.     bool hashMoveSelected = true;
  732.     if (hashMove.isEmpty() || !selectHashMove(moves, hashMove)) {
  733.         scoreMoveList(moves, ply);
  734.         seeDone = true;
  735.         hashMoveSelected = false;
  736.     }
  737.  
  738.     // Handle singular extension
  739.     bool singularExtend = false;
  740.     if ((depth > 6 * plyScale) && (posExtend == 0) &&
  741.             hashMoveSelected && sti.singularMove.isEmpty() &&
  742.             (ent.getType() != TType::T_LE) &&
  743.             (ent.getDepth() >= depth - 3 * plyScale) &&
  744.             (getMoveExtend(hashMove, recaptureSquare) <= 0) &&
  745.             (ply + depth / plyScale < MAX_SEARCH_DEPTH) &&
  746.             MoveGen::isLegal(pos, hashMove, inCheck)) {
  747.         SearchTreeInfo& sti2 = searchTreeInfo[ply-1];
  748.         Move savedMove = sti2.currentMove;
  749.         int savedMoveNo = sti2.currentMoveNo;
  750.         S64 savedNodeIdx2 = sti2.nodeIdx;
  751.         sti2.currentMove = Move(1,1,0); // Represents "no move"
  752.         sti2.currentMoveNo = -1;
  753.         sti2.nodeIdx = sti.nodeIdx;
  754.         S64 savedNodeIdx = sti.nodeIdx;
  755.  
  756.         int newDepth = depth / 2;
  757.         int newBeta = ent.getScore(ply) - 25;
  758.         sti.singularMove = hashMove;
  759.         int singScore = negaScout(smp, tb, newBeta-1, newBeta, ply, newDepth,
  760.                                   recaptureSquare, inCheck);
  761.         sti.singularMove.setMove(0,0,0,0);
  762.         if (singScore <= newBeta-1)
  763.             singularExtend = true;
  764.  
  765.         sti.nodeIdx = savedNodeIdx;
  766.         sti2.currentMove = savedMove;
  767.         sti2.currentMoveNo = savedMoveNo;
  768.         sti2.nodeIdx = savedNodeIdx2;
  769.     }
  770.  
  771.     SplitPointHolder sph(pd, spVec, pending);
  772.     if (smp) {
  773.         sph.setSp(std::make_shared<SplitPoint>(threadNo, spVec.back(),
  774.                                                searchTreeInfo[ply-1].currentMoveNo,
  775.                                                pos, posHashList, posHashListSize,
  776.                                                sti, kt, ht, alpha, beta, ply, depth/plyScale));
  777.         for (int mi = 0; mi < moves.size; mi++) {
  778.             if ((mi == 1) && !seeDone) {
  779.                 scoreMoveList(moves, ply, 1);
  780.                 seeDone = true;
  781.             }
  782.             if ((mi > 0) || !hashMoveSelected)
  783.                 selectBest(moves, mi);
  784.         }
  785.     }
  786.  
  787.     // Determine late move pruning (LMP) limit
  788.     int lmpMoveCountLimit = 256;
  789.     if (beta == alpha + 1) {
  790.         bool lmpOk;
  791.         if (pos.isWhiteMove())
  792.             lmpOk = (pos.wMtrl() > pos.wMtrlPawns()) && (pos.wMtrlPawns() > 0);
  793.         else
  794.             lmpOk = (pos.bMtrl() > pos.bMtrlPawns()) && (pos.bMtrlPawns() > 0);
  795.         if (lmpOk) {
  796.             if (depth <= plyScale)          lmpMoveCountLimit = lmpMoveCountLimit1;
  797.             else if (depth <= 2 * plyScale) lmpMoveCountLimit = lmpMoveCountLimit2;
  798.             else if (depth <= 3 * plyScale) lmpMoveCountLimit = lmpMoveCountLimit3;
  799.             else if (depth <= 4 * plyScale) lmpMoveCountLimit = lmpMoveCountLimit4;
  800.         }
  801.     }
  802.  
  803.     // Start searching move alternatives
  804.     UndoInfo ui;
  805.     for (int pass = (smp?0:1); pass < 2; pass++) {
  806.         bool haveLegalMoves = false;
  807.         int b = beta;
  808.         int bestScore = illegalScore;
  809.         int bestMove = -1;
  810.         int lmrCount = 0;
  811.         if (tb && pass == 1 && tbScore != illegalScore) {
  812.             bestScore = tbScore - 1;
  813.             bestMove = -2;
  814.             sti.bestMove.setMove(0, 0, 0, 0);
  815.         }
  816.         for (int mi = 0; mi < moves.size; mi++) {
  817.             if (!smp) {
  818.                 if ((mi == 1) && !seeDone) {
  819.                     scoreMoveList(moves, ply, 1);
  820.                     seeDone = true;
  821.                 }
  822.                 if ((mi < lmpMoveCountLimit) || (lmrCount <= lmrMoveCountLimit1))
  823.                     if ((mi > 0) || !hashMoveSelected)
  824.                         selectBest(moves, mi);
  825.             }
  826.             Move& m = moves[mi];
  827.             int newCaptureSquare = -1;
  828.             bool isCapture = (pos.getPiece(m.to()) != Piece::EMPTY);
  829.             bool isPromotion = (m.promoteTo() != Piece::EMPTY);
  830.             int sVal = std::numeric_limits<int>::min();
  831.             bool mayReduce = (m.score() < 53) && (!isCapture || m.score() < 0) && !isPromotion;
  832.             bool givesCheck = MoveGen::givesCheck(pos, m);
  833.             bool negSEECheck = (depth > 4*plyScale) && givesCheck && negSEE(m);
  834.             bool doFutility = false;
  835.             if (mayReduce && haveLegalMoves && !givesCheck && !passedPawnPush(pos, m)) {
  836.                 if (normalBound && !isLoseScore(bestScore) && (mi >= lmpMoveCountLimit))
  837.                     continue; // Late move pruning
  838.                 if (futilityPrune)
  839.                     doFutility = true;
  840.             }
  841.             int score = illegalScore;
  842.             if (doFutility) {
  843.                 score = futilityScore;
  844.             } else {
  845. #ifdef HAS_PREFETCH
  846.                 if (pass == 1)
  847.                     tt.prefetch(pos.hashAfterMove(m));
  848. #endif
  849.                 if ((mi == 0) && m.equals(sti.singularMove))
  850.                     continue;
  851.                 if (!MoveGen::isLegal(pos, m, inCheck))
  852.                     continue;
  853.                 int moveExtend = (posExtend > 0) ? 0 : getMoveExtend(m, recaptureSquare);
  854.                 int extend = std::max(posExtend, moveExtend);
  855.                 if (singularExtend && (mi == 0))
  856.                     extend = 1*plyScale;
  857.                 int lmr = 0;
  858.                 if ((depth >= 2*plyScale) && mayReduce && (extend == 0)) {
  859.                     if (!givesCheck && !passedPawnPush(pos, m)) {
  860.                         lmrCount++;
  861.                         if ((lmrCount > lmrMoveCountLimit2) && (depth > 5*plyScale) && !isCapture) {
  862.                             lmr = 3*plyScale;
  863.                         } else if ((lmrCount > lmrMoveCountLimit1) && (depth > 3*plyScale) && !isCapture) {
  864.                             lmr = 2*plyScale;
  865.                         } else {
  866.                             lmr = 1*plyScale;
  867.                         }
  868.                     }
  869.                 }
  870.                 int newDepth = depth - plyScale + extend - lmr - (negSEECheck ? plyScale : 0);
  871.                 if (isCapture && (givesCheck || (depth + extend) > plyScale)) {
  872.                     // Compute recapture target square, but only if we are not going
  873.                     // into q-search at the next ply.
  874.                     int fVal = ::pieceValue[pos.getPiece(m.from())];
  875.                     int tVal = ::pieceValue[pos.getPiece(m.to())];
  876.                     const int pV = ::pV;
  877.                     if (std::abs(tVal - fVal) < pV / 2) {    // "Equal" capture
  878.                         sVal = SEE(m);
  879.                         if (std::abs(sVal) < pV / 2)
  880.                             newCaptureSquare = m.to();
  881.                     }
  882.                 }
  883.                 if (pass == 0) {
  884.                     sph.addMove(mi, SplitPointMove(m, lmr, newDepth, newCaptureSquare, givesCheck));
  885.                 } else {
  886.                     posHashList[posHashListSize++] = pos.zobristHash();
  887.                     pos.makeMove(m, ui);
  888.                     totalNodes++;
  889.                     nodesToGo--;
  890.                     sti.currentMove = m;
  891.                     sti.currentMoveNo = mi;
  892.                     sti.lmr = lmr;
  893. //                    S64 n1 = totalNodes; int nomDepth = newDepth;
  894.                     if (smp) {
  895.                         int helperScore = sph.setOwnerCurrMove(mi, alpha);
  896.                         if (helperScore != UNKNOWN_SCORE)
  897.                             score = helperScore;
  898.                     }
  899.                     if (!smp || (score == illegalScore)) {
  900.                         score = -negaScout(smp, tb, -b, -alpha, ply + 1, newDepth, newCaptureSquare, givesCheck);
  901.                         if (((lmr > 0) && (score > alpha)) ||
  902.                             ((score > alpha) && (score < beta) && (b != beta))) {
  903.                             sti.lmr = 0;
  904.                             newDepth += lmr;
  905.                             score = -negaScout(smp, tb, -beta, -alpha, ply + 1, newDepth, newCaptureSquare, givesCheck);
  906.                         }
  907.                     }
  908.                     if (smp) {
  909. //                        if (sph.hasHelperThread())
  910. //                            log([&](std::ostream& os){os << "main seqNo:" << sph.getSeqNo() << " ply:" << ply << " m:" << mi
  911. //                                                         << " a:" << alpha << " b:" << beta << " s:" << score
  912. //                                                         << " d:" << nomDepth/plyScale << " n:" << (totalNodes-n1);});
  913.                         if (beta > alpha + 1) {
  914.                             pd.fhInfo.addPvData(mi, score > alpha);
  915.                         } else {
  916.                             pd.fhInfo.addData(mi, searchTreeInfo[ply+1].currentMoveNo,
  917.                                               score <= alpha, !sph.isAllNode());
  918.                         }
  919.                     }
  920.                     posHashListSize--;
  921.                     pos.unMakeMove(m, ui);
  922.                 }
  923.             }
  924.             if (pass == 1) {
  925.                 if (weak && haveLegalMoves)
  926.                     if (weakPlaySkipMove(pos, m, ply))
  927.                         score = illegalScore;
  928.                 m.setScore(score);
  929.  
  930.                 if (score != illegalScore)
  931.                     haveLegalMoves = true;
  932.                 bestScore = std::max(bestScore, score);
  933.                 if (score > alpha) {
  934.                     alpha = score;
  935.                     bestMove = mi;
  936.                     sti.bestMove.setMove(m.from(), m.to(), m.promoteTo(), sti.bestMove.score());
  937.                 }
  938.                 if (alpha >= beta) {
  939.                     if (pos.getPiece(m.to()) == Piece::EMPTY) {
  940.                         kt.addKiller(ply, m);
  941.                         ht.addSuccess(pos, m, depth/plyScale);
  942.                         for (int mi2 = mi - 1; mi2 >= 0; mi2--) {
  943.                             Move m2 = moves[mi2];
  944.                             if (pos.getPiece(m2.to()) == Piece::EMPTY)
  945.                                 ht.addFail(pos, m2, depth/plyScale);
  946.                         }
  947.                     }
  948.                     if (useTT) tt.insert(hKey, m, TType::T_GE, ply, depth, evalScore);
  949.                     logFile.logNodeEnd(sti.nodeIdx, alpha, TType::T_GE, evalScore, hKey);
  950.                     return alpha;
  951.                 }
  952.                 b = alpha + 1;
  953.             }
  954.         }
  955.         if (pass == 0) {
  956.             sph.addToQueue();
  957.         } else {
  958.             if (!haveLegalMoves && !inCheck) {
  959.                 if (singularSearch) {
  960.                     logFile.logNodeEnd(sti.nodeIdx, alpha, TType::T_LE, evalScore, hKey);
  961.                     return alpha; // Only one legal move, fail low to trigger singular extension
  962.                 }
  963.                 emptyMove.setScore(0);
  964.                 if (useTT) tt.insert(hKey, emptyMove, TType::T_EXACT, ply, depth, evalScore);
  965.                 logFile.logNodeEnd(sti.nodeIdx, 0, TType::T_EXACT, evalScore, hKey);
  966.                 return 0;       // Stale-mate
  967.             }
  968.             if (tb && bestMove == -2) { // TB win, unknown move
  969.                 bestScore = tbScore;
  970.                 emptyMove.setScore(bestScore);
  971.                 if (useTT) tt.insert(hKey, emptyMove, TType::T_EXACT, ply, depth, evalScore);
  972.                 logFile.logNodeEnd(sti.nodeIdx, bestScore, TType::T_EXACT, evalScore, hKey);
  973.             } else if (bestMove >= 0) {
  974.                 if (useTT) tt.insert(hKey, moves[bestMove], TType::T_EXACT, ply, depth, evalScore);
  975.                 logFile.logNodeEnd(sti.nodeIdx, bestScore, TType::T_EXACT, evalScore, hKey);
  976.             } else {
  977.                 emptyMove.setScore(bestScore);
  978.                 if (useTT) tt.insert(hKey, emptyMove, TType::T_LE, ply, depth, evalScore);
  979.                 logFile.logNodeEnd(sti.nodeIdx, bestScore, TType::T_LE, evalScore, hKey);
  980.             }
  981.             return bestScore;
  982.         }
  983.     }
  984.     assert(false);
  985.     return 0;
  986. }
  987.  
  988. int
  989. Search::getMoveExtend(const Move& m, int recaptureSquare) {
  990.     if ((m.to() == recaptureSquare)) {
  991.         int sVal = SEE(m);
  992.         int tVal = ::pieceValue[pos.getPiece(m.to())];
  993.         if (sVal > tVal - pV / 2)
  994.             return plyScale;
  995.     }
  996.     bool isCapture = (pos.getPiece(m.to()) != Piece::EMPTY);
  997.     if (isCapture && (pos.wMtrlPawns() + pos.bMtrlPawns() > pV)) {
  998.         // Extend if going into pawn endgame
  999.         int capVal = ::pieceValue[pos.getPiece(m.to())];
  1000.         if (pos.isWhiteMove()) {
  1001.             if ((pos.wMtrl() == pos.wMtrlPawns()) && (pos.bMtrl() - pos.bMtrlPawns() == capVal))
  1002.                 return plyScale;
  1003.         } else {
  1004.             if ((pos.bMtrl() == pos.bMtrlPawns()) && (pos.wMtrl() - pos.wMtrlPawns() == capVal))
  1005.                 return plyScale;
  1006.         }
  1007.     }
  1008.     return 0;
  1009. }
  1010.  
  1011. void
  1012. Search::getRootMoves(const MoveList& rootMovesIn,
  1013.                      std::vector<MoveInfo>& rootMovesOut,
  1014.                      int maxDepth) {
  1015.     MoveList rootMoves(rootMovesIn);
  1016.     if ((maxTimeMillis >= 0) || (maxNodes >= 0) || (maxDepth >= 0)) {
  1017.         MoveList legalMoves;
  1018.         MoveGen::pseudoLegalMoves(pos, legalMoves);
  1019.         MoveGen::removeIllegal(pos, legalMoves);
  1020.         if (rootMoves.size == legalMoves.size) {
  1021.             // Game mode, handle missing TBs
  1022.             std::vector<Move> movesToSearch;
  1023.             if (TBProbe::getSearchMoves(pos, legalMoves, movesToSearch))
  1024.                 rootMoves.filter(movesToSearch);
  1025.         }
  1026.     }
  1027.  
  1028.     // If strength is < 10%, only include a subset of the root moves.
  1029.     // At least one move is always included though.
  1030.     std::vector<bool> includedMoves(rootMoves.size);
  1031.     U64 rndL = pos.zobristHash() ^ randomSeed;
  1032.     includedMoves[(int)(rndL % rootMoves.size)] = true;
  1033.     double pIncl = (strength < 100) ? strength * strength * 1e-4 : 1.0;
  1034.     for (int mi = 0; mi < rootMoves.size; mi++) {
  1035.         rndL = 6364136223846793005ULL * rndL + 1442695040888963407ULL;
  1036.         double rnd = ((rndL & 0x7fffffffffffffffULL) % 1000000000) / 1e9;
  1037.         if (!includedMoves[mi] && (rnd < pIncl))
  1038.             includedMoves[mi] = true;
  1039.     }
  1040.     for (int mi = 0; mi < rootMoves.size; mi++) {
  1041.         if (includedMoves[mi]) {
  1042.             const Move& m = rootMoves[mi];
  1043.             rootMovesOut.push_back(MoveInfo(m, 0));
  1044.         }
  1045.     }
  1046. }
  1047.  
  1048. bool
  1049. Search::weakPlaySkipMove(const Position& pos, const Move& m, int ply) const {
  1050.     U64 rndL = pos.zobristHash() ^ Position::getHashKey(Piece::EMPTY, m.from()) ^
  1051.                Position::getHashKey(Piece::EMPTY, m.to()) ^ randomSeed;
  1052.     double rnd = ((rndL & 0x7fffffffffffffffULL) % 1000000000) / 1e9;
  1053.  
  1054.     double s = strength * 1e-3;
  1055.     double offs = (17 - 50 * s) / 3;
  1056.     double effPly = ply * Evaluate::interpolate(pos.wMtrl() + pos.bMtrl(), 0, 30, ::qV * 4, 100) * 1e-2;
  1057.     double t = effPly + offs;
  1058.     double p = 1/(1+exp(t)); // Probability to "see" move
  1059.     bool easyMove = ((pos.getPiece(m.to()) != Piece::EMPTY) ||
  1060.                      (ply < 2) || (searchTreeInfo[ply-2].currentMove.to() == m.from()));
  1061.     if (easyMove)
  1062.         p = 1-(1-p)*(1-p);
  1063.     if (rnd > p)
  1064.         return true;
  1065.     return false;
  1066. }
  1067.  
  1068. int
  1069. Search::quiesce(int alpha, int beta, int ply, int depth, const bool inCheck) {
  1070.     int score;
  1071.     if (inCheck) {
  1072.         score = -(MATE0 - (ply+1));
  1073.     } else {
  1074.         if ((depth == 0) && (q0Eval != UNKNOWN_SCORE)) {
  1075.             score = q0Eval;
  1076.         } else {
  1077.             score = eval.evalPos(pos);
  1078.             if (depth == 0)
  1079.                 q0Eval = score;
  1080.         }
  1081.     }
  1082.     if (score >= beta)
  1083.         return score;
  1084.     const int evalScore = score;
  1085.     if (score > alpha)
  1086.         alpha = score;
  1087.     int bestScore = score;
  1088.     const bool tryChecks = (depth > -1);
  1089.     MoveList moves;
  1090.     if (inCheck) {
  1091.         MoveGen::checkEvasions(pos, moves);
  1092.     } else if (tryChecks) {
  1093.         MoveGen::pseudoLegalCapturesAndChecks(pos, moves);
  1094.     } else {
  1095.         MoveGen::pseudoLegalCaptures(pos, moves);
  1096.     }
  1097.  
  1098.     bool realInCheckComputed = false;
  1099.     bool realInCheck = false;
  1100.     if (depth > -2) {
  1101.         realInCheckComputed = true;
  1102.         realInCheck = inCheck;
  1103.     }
  1104.     scoreMoveListMvvLva(moves);
  1105.     UndoInfo ui;
  1106.     for (int mi = 0; mi < moves.size; mi++) {
  1107.         if (mi < quiesceMaxSortMoves) {
  1108.             // If the first N moves didn't fail high this is probably an ALL-node,
  1109.             // so spending more effort on move ordering is probably wasted time.
  1110.             selectBest(moves, mi);
  1111.         }
  1112.         const Move& m = moves[mi];
  1113.         bool givesCheck = false;
  1114.         bool givesCheckComputed = false;
  1115.         if (inCheck) {
  1116.             // Allow all moves
  1117.         } else {
  1118.             if ((pos.getPiece(m.to()) == Piece::EMPTY) && (m.promoteTo() == Piece::EMPTY)) {
  1119.                 // Non-capture
  1120.                 if (!tryChecks)
  1121.                     continue;
  1122.                 givesCheck = MoveGen::givesCheck(pos, m);
  1123.                 givesCheckComputed = true;
  1124.                 if (!givesCheck)
  1125.                     continue;
  1126.                 if (negSEE(m)) // Needed because m.score() is not computed for non-captures
  1127.                     continue;
  1128.             } else {
  1129.                 if (negSEE(m))
  1130.                     continue;
  1131.                 int capt = ::pieceValue[pos.getPiece(m.to())];
  1132.                 int prom = ::pieceValue[m.promoteTo()];
  1133.                 int optimisticScore = evalScore + capt + prom + deltaPruningMargin;
  1134.                 if (optimisticScore < alpha) { // Delta pruning
  1135.                     if ((pos.wMtrlPawns() > 0) && (pos.wMtrl() > capt + pos.wMtrlPawns()) &&
  1136.                         (pos.bMtrlPawns() > 0) && (pos.bMtrl() > capt + pos.bMtrlPawns())) {
  1137.                         if (depth -1 > -2) {
  1138.                             givesCheck = MoveGen::givesCheck(pos, m);
  1139.                             givesCheckComputed = true;
  1140.                         }
  1141.                         if (!givesCheck) {
  1142.                             if (optimisticScore > bestScore)
  1143.                                 bestScore = optimisticScore;
  1144.                             continue;
  1145.                         }
  1146.                     }
  1147.                 }
  1148.             }
  1149.         }
  1150.         if (!realInCheckComputed) {
  1151.             realInCheck = MoveGen::inCheck(pos);
  1152.             realInCheckComputed = true;
  1153.         }
  1154.         if (!MoveGen::isLegal(pos, m, realInCheck))
  1155.             continue;
  1156.  
  1157.         if (!givesCheckComputed && (depth - 1 > -2))
  1158.             givesCheck = MoveGen::givesCheck(pos, m);
  1159.         const bool nextInCheck = (depth - 1) > -2 ? givesCheck : false;
  1160.  
  1161.         pos.makeMove(m, ui);
  1162.         totalNodes++;
  1163.         nodesToGo--;
  1164.         score = -quiesce(-beta, -alpha, ply + 1, depth - 1, nextInCheck);
  1165.         pos.unMakeMove(m, ui);
  1166.         if (score > bestScore) {
  1167.             bestScore = score;
  1168.             if (score > alpha) {
  1169.                 if (depth == 0) {
  1170.                     SearchTreeInfo& sti = searchTreeInfo[ply];
  1171.                     sti.bestMove.setMove(m.from(), m.to(), m.promoteTo(), score);
  1172.                 }
  1173.                 alpha = score;
  1174.                 if (alpha >= beta)
  1175.                     return alpha;
  1176.             }
  1177.         }
  1178.     }
  1179.     return bestScore;
  1180. }
  1181.  
  1182.  
  1183. int
  1184. Search::SEE(const Move& m) {
  1185.     int captures[64];   // Value of captured pieces
  1186.  
  1187.     const int kV = ::kV;
  1188.  
  1189.     const int square = m.to();
  1190.     if (square == pos.getEpSquare()) {
  1191.         captures[0] = ::pV;
  1192.     } else {
  1193.         captures[0] = ::pieceValue[pos.getPiece(square)];
  1194.         if (captures[0] == kV)
  1195.             return kV;
  1196.     }
  1197.     int nCapt = 1;                  // Number of entries in captures[]
  1198.  
  1199.     UndoInfo ui;
  1200.     pos.makeSEEMove(m, ui);
  1201.     bool white = pos.isWhiteMove();
  1202.     int valOnSquare = ::pieceValue[pos.getPiece(square)];
  1203.     U64 occupied = pos.occupiedBB();
  1204.     while (true) {
  1205.         int bestValue = std::numeric_limits<int>::max();
  1206.         U64 atk;
  1207.         if (white) {
  1208.             atk = BitBoard::bPawnAttacks[square] & pos.pieceTypeBB(Piece::WPAWN) & occupied;
  1209.             if (atk != 0) {
  1210.                 bestValue = ::pV;
  1211.             } else {
  1212.                 atk = BitBoard::knightAttacks[square] & pos.pieceTypeBB(Piece::WKNIGHT) & occupied;
  1213.                 if (atk != 0) {
  1214.                     bestValue = ::nV;
  1215.                 } else {
  1216.                     U64 bAtk = BitBoard::bishopAttacks(square, occupied) & occupied;
  1217.                     atk = bAtk & pos.pieceTypeBB(Piece::WBISHOP);
  1218.                     if (atk != 0) {
  1219.                         bestValue = ::bV;
  1220.                     } else {
  1221.                         U64 rAtk = BitBoard::rookAttacks(square, occupied) & occupied;
  1222.                         atk = rAtk & pos.pieceTypeBB(Piece::WROOK);
  1223.                         if (atk != 0) {
  1224.                             bestValue = ::rV;
  1225.                         } else {
  1226.                             atk = (bAtk | rAtk) & pos.pieceTypeBB(Piece::WQUEEN);
  1227.                             if (atk != 0) {
  1228.                                 bestValue = ::qV;
  1229.                             } else {
  1230.                                 atk = BitBoard::kingAttacks[square] & pos.pieceTypeBB(Piece::WKING) & occupied;
  1231.                                 if (atk != 0) {
  1232.                                     bestValue = kV;
  1233.                                 } else {
  1234.                                     break;
  1235.                                 }
  1236.                             }
  1237.                         }
  1238.                     }
  1239.                 }
  1240.             }
  1241.         } else {
  1242.             atk = BitBoard::wPawnAttacks[square] & pos.pieceTypeBB(Piece::BPAWN) & occupied;
  1243.             if (atk != 0) {
  1244.                 bestValue = ::pV;
  1245.             } else {
  1246.                 atk = BitBoard::knightAttacks[square] & pos.pieceTypeBB(Piece::BKNIGHT) & occupied;
  1247.                 if (atk != 0) {
  1248.                     bestValue = ::nV;
  1249.                 } else {
  1250.                     U64 bAtk = BitBoard::bishopAttacks(square, occupied) & occupied;
  1251.                     atk = bAtk & pos.pieceTypeBB(Piece::BBISHOP);
  1252.                     if (atk != 0) {
  1253.                         bestValue = ::bV;
  1254.                     } else {
  1255.                         U64 rAtk = BitBoard::rookAttacks(square, occupied) & occupied;
  1256.                         atk = rAtk & pos.pieceTypeBB(Piece::BROOK);
  1257.                         if (atk != 0) {
  1258.                             bestValue = ::rV;
  1259.                         } else {
  1260.                             atk = (bAtk | rAtk) & pos.pieceTypeBB(Piece::BQUEEN);
  1261.                             if (atk != 0) {
  1262.                                 bestValue = ::qV;
  1263.                             } else {
  1264.                                 atk = BitBoard::kingAttacks[square] & pos.pieceTypeBB(Piece::BKING) & occupied;
  1265.                                 if (atk != 0) {
  1266.                                     bestValue = kV;
  1267.                                 } else {
  1268.                                     break;
  1269.                                 }
  1270.                             }
  1271.                         }
  1272.                     }
  1273.                 }
  1274.             }
  1275.         }
  1276.         captures[nCapt++] = valOnSquare;
  1277.         if (valOnSquare == kV)
  1278.             break;
  1279.         valOnSquare = bestValue;
  1280.         occupied &= ~(atk & (0-atk)); // Pierre-Marie Baty -- signedness fix
  1281.         white = !white;
  1282.     }
  1283.     pos.unMakeSEEMove(m, ui);
  1284.  
  1285.     int score = 0;
  1286.     for (int i = nCapt - 1; i > 0; i--)
  1287.         score = std::max(0, captures[i] - score);
  1288.     return captures[0] - score;
  1289. }
  1290.  
  1291. void
  1292. Search::scoreMoveList(MoveList& moves, int ply, int startIdx) {
  1293.     for (int i = startIdx; i < moves.size; i++) {
  1294.         Move& m = moves[i];
  1295.         bool isCapture = (pos.getPiece(m.to()) != Piece::EMPTY) || (m.promoteTo() != Piece::EMPTY);
  1296.         int score = 0;
  1297.         if (isCapture) {
  1298.             int seeScore = signSEE(m);
  1299.             int v = pos.getPiece(m.to());
  1300.             int a = pos.getPiece(m.from());
  1301.             score = Evaluate::pieceValueOrder[v] * 8 - Evaluate::pieceValueOrder[a];
  1302.             if (seeScore > 0)
  1303.                 score += 100;
  1304.             else if (seeScore == 0)
  1305.                 score += 50;
  1306.             else
  1307.                 score -= 50;
  1308.             score *= 100;
  1309.         }
  1310.         int ks = kt.getKillerScore(ply, m);
  1311.         if (ks > 0) {
  1312.             score += ks + 50;
  1313.         } else {
  1314.             int hs = ht.getHistScore(pos, m);
  1315.             score += hs;
  1316.         }
  1317.         m.setScore(score);
  1318.     }
  1319. }
  1320.  
  1321. bool
  1322. Search::selectHashMove(MoveList& moves, const Move& hashMove) {
  1323.     for (int i = 0; i < moves.size; i++) {
  1324.         Move& m = moves[i];
  1325.         if (m.equals(hashMove)) {
  1326.             m.setScore(10000);
  1327.             std::swap(moves[i], moves[0]);
  1328.             return true;
  1329.         }
  1330.     }
  1331.     return false;
  1332. }
  1333.  
  1334. void
  1335. Search::initNodeStats() {
  1336.     nodesByPly.clear();
  1337.     nodesByDepth.clear();
  1338. }
  1339.  
  1340. void
  1341. Search::setThreadNo(int tNo) {
  1342.     threadNo = tNo;
  1343.     if (threadNo > 0)
  1344.         nodesBetweenTimeCheck = 1000;
  1345.     mainNumaNode = Numa::instance().isMainNode(threadNo);
  1346. }
  1347.