Subversion Repositories Games.Chess Giants

Rev

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

  1. /*
  2.     Texel - A UCI chess engine.
  3.     Copyright (C) 2013-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.  * parallel.cpp
  21.  *
  22.  *  Created on: Jul 9, 2013
  23.  *      Author: petero
  24.  */
  25.  
  26. #include "parallel.hpp"
  27. #include "numa.hpp"
  28. #include "search.hpp"
  29. #include "tbprobe.hpp"
  30. #include "textio.hpp"
  31. #include "util/logger.hpp"
  32.  
  33. #include <cmath>
  34. #include <cassert>
  35.  
  36. using namespace Logger;
  37.  
  38. U64 SplitPoint::nextSeqNo = 0;
  39.  
  40. // ----------------------------------------------------------------------------
  41.  
  42. WorkerThread::WorkerThread(int threadNo0, ParallelData& pd0,
  43.                            TranspositionTable& tt0)
  44.     : threadNo(threadNo0), pd(pd0), tt(tt0),
  45.       pUseful(0.0) {
  46. }
  47.  
  48. WorkerThread::~WorkerThread() {
  49.     assert(!thread);
  50. }
  51.  
  52. void
  53. WorkerThread::start() {
  54.     assert(!thread);
  55.     const int minProbeDepth = TBProbe::tbEnabled() ? UciParams::minProbeDepth->getIntPar() : 100;
  56.     thread = std::make_shared<std::thread>([this,minProbeDepth](){ mainLoop(minProbeDepth); });
  57. }
  58.  
  59. void
  60. WorkerThread::join() {
  61.     if (thread) {
  62.         thread->join();
  63.         thread.reset();
  64.     }
  65. }
  66.  
  67. class ThreadStopHandler : public Search::StopHandler {
  68. public:
  69.     ThreadStopHandler(WorkerThread& wt, ParallelData& pd,
  70.                       const SplitPoint& sp, const SplitPointMove& spm,
  71.                       const Search& sc, int initialAlpha,
  72.                       S64 totalNodes, int myPrio);
  73.  
  74.     /** Destructor. Report searched nodes to ParallelData object. */
  75.     ~ThreadStopHandler();
  76.  
  77.     ThreadStopHandler(const ThreadStopHandler&) = delete;
  78.     ThreadStopHandler& operator=(const ThreadStopHandler&) = delete;
  79.  
  80.     bool shouldStop();
  81.  
  82. private:
  83.     /** Report searched nodes since last call to ParallelData object. */
  84.     void reportNodes(bool force);
  85.  
  86.     const WorkerThread& wt;
  87.     ParallelData& pd;
  88.     const SplitPoint& sp;
  89.     const SplitPointMove& spMove;
  90.     const Search& sc;
  91.     int counter;             // Counts number of calls to shouldStop
  92.     int nextProbCheck;       // Next time test for SplitPoint switch should be performed
  93.     S64 lastReportedNodes;
  94.     S64 lastReportedTbHits;
  95.     int initialAlpha;
  96.     const S64 totalNodes;
  97.     const int myPrio;
  98. };
  99.  
  100. ThreadStopHandler::ThreadStopHandler(WorkerThread& wt0, ParallelData& pd0,
  101.                                      const SplitPoint& sp0, const SplitPointMove& spm0,
  102.                                      const Search& sc0, int initialAlpha0,
  103.                                      S64 totalNodes0, int myPrio0)
  104.     : wt(wt0), pd(pd0), sp(sp0), spMove(spm0),
  105.       sc(sc0), counter(0), nextProbCheck(1),
  106.       lastReportedNodes(0), lastReportedTbHits(0),
  107.       initialAlpha(initialAlpha0), totalNodes(totalNodes0), myPrio(myPrio0) {
  108. }
  109.  
  110. ThreadStopHandler::~ThreadStopHandler() {
  111.     reportNodes(true);
  112. }
  113.  
  114. bool
  115. ThreadStopHandler::shouldStop() {
  116.     if (pd.wq.isStopped() || spMove.isCanceled())
  117.         return true;
  118.     if (sp.getAlpha() != initialAlpha)
  119.         return true;
  120.  
  121.     counter++;
  122.     if (counter >= nextProbCheck) {
  123.         nextProbCheck = counter + 1 + counter / 4;
  124.         int bestPrio = pd.wq.getBestPrio();
  125. //        log([&](std::ostream& os){os << "shouldStop, th:" << wt.getThreadNo() << " myP:" << myPrio << " bestP:" << bestPrio;});
  126.         if ((bestPrio > myPrio + 20) && (bestPrio >= (myPrio + (1000 - myPrio) * 0.25)) &&
  127.             (sp.owningThread() != wt.getThreadNo()))
  128.             return true;
  129.         reportNodes(false);
  130.     }
  131.  
  132.     return false;
  133. }
  134.  
  135. void
  136. ThreadStopHandler::reportNodes(bool force) {
  137.     S64 totNodes = sc.getTotalNodesThisThread();
  138.     S64 nodes = totNodes - lastReportedNodes;
  139.     if (force || (nodes * 1024 > totalNodes)) {
  140.         lastReportedNodes = totNodes;
  141.         pd.addSearchedNodes(nodes);
  142.         S64 totTbHits = sc.getTbHitsThisThread();
  143.         S64 tbHits = totTbHits - lastReportedTbHits;
  144.         lastReportedTbHits = totTbHits;
  145.         pd.addTbHits(tbHits);
  146.     }
  147. }
  148.  
  149. void
  150. WorkerThread::mainLoop(int minProbeDepth) {
  151. //    log([&](std::ostream& os){os << "mainLoop, th:" << threadNo;});
  152.     Numa::instance().bindThread(threadNo);
  153.     if (!et)
  154.         et = Evaluate::getEvalHashTables();
  155.     if (!kt)
  156.         kt = std::make_shared<KillerTable>();
  157.     if (!ht)
  158.         ht = std::make_shared<History>();
  159.  
  160.     TreeLogger logFile;
  161.     logFile.open("/home/petero/treelog.dmp", pd, threadNo);
  162.  
  163. //    UtilizationTimer uTimer;
  164.     std::mutex m;
  165.     std::unique_lock<std::mutex> lock(m);
  166.     Position pos;
  167.     std::shared_ptr<SplitPoint> sp;
  168.     for (int iter = 0; ; iter++) {
  169.         const bool doTiming = (iter & 15) == 0;
  170.         int moveNo = -1;
  171. //        uTimer.setPUseful(-1);
  172.         const double t0 = doTiming ? currentTime() : -1;
  173.         int prio;
  174.         std::shared_ptr<SplitPoint> newSp = pd.wq.getWork(moveNo, pd, threadNo, prio, pUseful);
  175.         if (!newSp)
  176.             break;
  177.         const double tStart = doTiming ? currentTime() : -1;
  178.  
  179.         const SplitPointMove& spMove = newSp->getSpMove(moveNo);
  180.         const int depth = spMove.getDepth();
  181.         if (depth < 0) { // Move skipped by forward pruning or legality check
  182.             pd.wq.moveFinished(newSp, moveNo, false, SearchConst::UNKNOWN_SCORE);
  183.             continue;
  184.         }
  185.         if (sp != newSp) {
  186.             sp = newSp;
  187.             *ht = sp->getHistory();
  188.             *kt = sp->getKillerTable();
  189.         }
  190.         Search::SearchTables st(tt, *kt, *ht, *et);
  191.         sp->getPos(pos, spMove.getMove());
  192.         std::vector<U64> posHashList;
  193.         int posHashListSize;
  194.         sp->getPosHashList(pos, posHashList, posHashListSize);
  195.         Search sc(pos, posHashList, posHashListSize, st, pd, sp, logFile);
  196.         const U64 rootNodeIdx = logFile.logPosition(pos, sp->owningThread(),
  197.                                                     sp->getSearchTreeInfo().nodeIdx, moveNo);
  198.         sc.setThreadNo(threadNo);
  199.         sc.setMinProbeDepth(minProbeDepth);
  200.         const int alpha = sp->getAlpha();
  201.         const int beta = sp->getBeta();
  202.         const S64 nodes0 = pd.getNumSearchedNodes();
  203.         auto stopHandler(std::make_shared<ThreadStopHandler>(*this, pd, *sp, spMove,
  204.                                                              sc, alpha, nodes0, prio));
  205.         sc.setStopHandler(stopHandler);
  206.         const int ply = sp->getPly();
  207.         const int lmr = spMove.getLMR();
  208.         const int captSquare = spMove.getRecaptureSquare();
  209.         const bool inCheck = spMove.getInCheck();
  210.         sc.setSearchTreeInfo(ply, sp->getSearchTreeInfo(), spMove.getMove(), moveNo, lmr, rootNodeIdx);
  211.         try {
  212. //            log([&](std::ostream& os){os << "th:" << threadNo << " seqNo:" << sp->getSeqNo() << " ply:" << ply
  213. //                                         << " c:" << sp->getCurrMoveNo() << " m:" << moveNo
  214. //                                         << " a:" << alpha << " b:" << beta
  215. //                                         << " d:" << depth/SearchConst::plyScale
  216. //                                         << " p:" << sp->getPMoveUseful(pd.fhInfo, moveNo) << " start";});
  217. //            uTimer.setPUseful(pUseful);
  218.             const bool smp = pd.numHelperThreads() > 1;
  219.             int score = -sc.negaScout(smp, true, -(alpha+1), -alpha, ply+1,
  220.                                       depth, captSquare, inCheck);
  221.             if (((lmr > 0) && (score > alpha)) ||
  222.                     ((score > alpha) && (score < beta))) {
  223.                 sc.setSearchTreeInfo(ply, sp->getSearchTreeInfo(), spMove.getMove(), moveNo, 0, rootNodeIdx);
  224.                 score = -sc.negaScout(smp, true, -beta, -alpha, ply+1,
  225.                                       depth + lmr, captSquare, inCheck);
  226.             }
  227. //            uTimer.setPUseful(0);
  228.             bool cancelRemaining = score >= beta;
  229. //            log([&](std::ostream& os){os << "th:" << threadNo << " seqNo:" << sp->getSeqNo() << " ply:" << ply
  230. //                                         << " c:" << sp->getCurrMoveNo() << " m:" << moveNo
  231. //                                         << " a:" << alpha << " b:" << beta << " s:" << score
  232. //                                         << " d:" << depth/SearchConst::plyScale << " n:" << sc.getTotalNodesThisThread();});
  233.             pd.wq.moveFinished(sp, moveNo, cancelRemaining, score);
  234.         } catch (const Search::StopSearch&) {
  235. //            log([&](std::ostream& os){os << "th:" << threadNo << " seqNo:" << sp->getSeqNo() << " m:" << moveNo
  236. //                                         << " aborted n:" << sc.getTotalNodesThisThread();});
  237.             if (!spMove.isCanceled() && !pd.wq.isStopped())
  238.                 pd.wq.returnMove(sp, moveNo);
  239.         }
  240.         if (doTiming) {
  241.             const double tEnd = currentTime();
  242.             pd.npsInfo.addData(sp->getDepth(), sc.getTotalNodesThisThread(), tStart - t0, tEnd - tStart);
  243.         }
  244.         pUseful = 0.0;
  245.     }
  246. //    double tElapsed, tUseful, tSleep;
  247. //    uTimer.getStats(tElapsed, tUseful, tSleep);
  248. //    log([&](std::ostream& os){
  249. //        os << "~mainLoop, th:" << threadNo << " useful:" << tUseful / tElapsed
  250. //           << " sleep:" << tSleep / tElapsed;
  251. //    });
  252. //    log([&](std::ostream& os){os << "~mainLoop, th:" << threadNo;});
  253. }
  254.  
  255. // ----------------------------------------------------------------------------
  256.  
  257. void
  258. WorkQueue::setStopped(bool stop) {
  259.     Lock L(this);
  260.     stopped = stop;
  261.     if (stopped)
  262.         cv.notify_all();
  263. }
  264.  
  265. void
  266. WorkQueue::addWork(const std::shared_ptr<SplitPoint>& sp) {
  267.     Lock L(this);
  268. //    ScopedTimeSample sts { getAddWorkStat(sp->owningThread()) };
  269.     addWorkInternal(sp);
  270. }
  271.  
  272. void
  273. WorkQueue::tryAddWork(const std::shared_ptr<SplitPoint>& sp,
  274.                       std::vector<std::shared_ptr<SplitPoint>>& pending) {
  275.     std::unique_lock<std::mutex> lock(mutex, std::defer_lock);
  276.     if (!lock.try_lock()) {
  277.         pending.push_back(sp);
  278.         return;
  279.     }
  280.     for (const auto& sp : pending)
  281.         addWorkInternal(sp);
  282.     pending.clear();
  283.     addWorkInternal(sp);
  284. }
  285.  
  286. void
  287. WorkQueue::addWorkInternal(const std::shared_ptr<SplitPoint>& sp) {
  288.     sp->setSeqNo();
  289.     std::shared_ptr<SplitPoint> parent = sp->getParent();
  290.     if (parent) {
  291.         if (parent->isCanceled())
  292.             sp->cancel();
  293.         else
  294.             parent->addChild(sp);
  295.     }
  296.     if (sp->hasUnFinishedMove()) {
  297.         sp->computeProbabilities(fhInfo, npsInfo);
  298.         insertInQueue(sp);
  299.     }
  300. }
  301.  
  302. std::shared_ptr<SplitPoint>
  303. WorkQueue::getWork(int& spMove, ParallelData& pd, int threadNo) {
  304.     int prio;
  305.     double pUseful;
  306.     return getWork(spMove, pd, threadNo, prio, pUseful);
  307. }
  308.  
  309. std::shared_ptr<SplitPoint>
  310. WorkQueue::getWork(int& spMove, ParallelData& pd, int threadNo, int& prio, double& pUseful) {
  311.     Lock L(this);
  312.     while (true) {
  313.         while (queue.empty() && !isStopped())
  314.             L.wait(cv);
  315. //        ScopedTimeSample sts { getGetWorkStat(threadNo) };
  316.         if (isStopped())
  317.             return nullptr;
  318.         std::shared_ptr<SplitPoint> ret = queue.front();
  319.         spMove = ret->getNextMove(pd.fhInfo);
  320.         if (spMove < 0) {
  321.             L.wait(cv);
  322.             continue;
  323.         }
  324. //        log([&](std::ostream& os){printSpTree(os, pd, threadNo, ret, spMove);});
  325.         prio = ret->getPrio();
  326.         updateProbabilities(ret);
  327.         pUseful = ret->getPMoveUseful(pd.fhInfo, spMove);
  328.         return ret;
  329.     }
  330. }
  331.  
  332. void
  333. WorkQueue::returnMove(const std::shared_ptr<SplitPoint>& sp, int moveNo) {
  334.     Lock L(this);
  335.     sp->returnMove(moveNo);
  336.     updateProbabilities(sp);
  337. }
  338.  
  339. int
  340. WorkQueue::setOwnerCurrMove(const std::shared_ptr<SplitPoint>& sp, int moveNo, int alpha) {
  341.     Lock L(this);
  342.     int score = sp->setOwnerCurrMove(moveNo, alpha);
  343.     updateProbabilities(sp);
  344.     return score;
  345. }
  346.  
  347. void
  348. WorkQueue::cancel(const std::shared_ptr<SplitPoint>& sp) {
  349.     Lock L(this);
  350.     cancelInternal(sp);
  351. }
  352.  
  353. void
  354. WorkQueue::moveFinished(const std::shared_ptr<SplitPoint>& sp, int moveNo,
  355.                         bool cancelRemaining, int score) {
  356.     Lock L(this);
  357.     sp->moveFinished(moveNo, cancelRemaining, score);
  358.     updateProbabilities(sp);
  359. }
  360.  
  361. double
  362. WorkQueue::getBestProbability(std::shared_ptr<SplitPoint>& bestSp) const {
  363.     Lock L(this);
  364.     if (queue.empty())
  365.         return 0.0;
  366.     bestSp = queue.front();
  367.     return bestSp->getPNextMoveUseful();
  368. }
  369.  
  370. int
  371. WorkQueue::getBestPrio() const {
  372.     Lock L(this);
  373.     if (queue.empty())
  374.         return -1;
  375.     return queue.front()->getPrio();
  376. }
  377.  
  378. double
  379. WorkQueue::getBestProbability() const {
  380.     std::shared_ptr<SplitPoint> bestSp;
  381.     return getBestProbability(bestSp);
  382. }
  383.  
  384. void
  385. WorkQueue::updateProbabilities(const std::shared_ptr<SplitPoint>& sp) {
  386.     if (!sp->hasUnFinishedMove())
  387.         queue.remove(sp);
  388.     sp->computeProbabilities(fhInfo, npsInfo);
  389. }
  390.  
  391. void
  392. WorkQueue::cancelInternal(const std::shared_ptr<SplitPoint>& sp) {
  393.     sp->cancel();
  394.     queue.remove(sp);
  395.  
  396.     for (const auto& wChild : sp->getChildren()) {
  397.         std::shared_ptr<SplitPoint> child = wChild.lock();
  398.         if (child)
  399.             cancelInternal(child);
  400.     }
  401. }
  402.  
  403. static std::string toPercentStr(double p) {
  404.     std::stringstream ss;
  405.     int pc = (int)(p * 100);
  406.     if (pc == 100)
  407.         pc = 99;
  408.     ss << std::setfill('0') << std::setw(2) << pc;
  409.     return ss.str();
  410. }
  411.  
  412. void
  413. WorkQueue::printSpTree(std::ostream& os, const ParallelData& pd,
  414.                        int threadNo, const std::shared_ptr<SplitPoint> selectedSp,
  415.                        int selectedMove) {
  416.     const int numThreads = pd.numHelperThreads() + 1;
  417.     std::shared_ptr<SplitPoint> rootSp = queue.front();
  418.     assert(rootSp);
  419.     while (rootSp->getParent())
  420.         rootSp = rootSp->getParent();
  421.     std::vector<int> parentThreads(numThreads, -1);
  422.     std::vector<std::shared_ptr<SplitPoint>> leaves(numThreads, nullptr);
  423.     findLeaves(rootSp, parentThreads, leaves);
  424.  
  425.     os << "th:" << threadNo << " m: " << selectedMove << ':'
  426.        << TextIO::moveToUCIString(selectedSp->getSpMove(selectedMove).getMove())
  427.        << " p:" << selectedSp->getPMoveUseful(pd.fhInfo, selectedMove)
  428.        << std::endl;
  429.     for (int i = 0; i < numThreads; i++) {
  430.         std::vector<std::shared_ptr<SplitPoint>> thVec;
  431.         for (auto sp = leaves[i]; sp; sp = sp->getParent())
  432.             thVec.push_back(sp);
  433.         std::reverse(thVec.begin(), thVec.end());
  434.         os << "th " << i << ' ';
  435.         if (parentThreads[i] < 0)
  436.             os << '-';
  437.         else
  438.             os << parentThreads[i];
  439.         os << ' ' << toPercentStr(i == 0 ? 1 : pd.getHelperThread(i-1).getPUseful());
  440.         if (!thVec.empty()) {
  441.             for (const auto& sp : thVec)
  442.                 if (sp->owningThread() == i) {
  443.                     os << ' ' << std::setw(6) << sp->getSeqNo();
  444.                     break;
  445.                 }
  446.         }
  447.         for (const auto& sp : thVec) {
  448.             if (sp->owningThread() == i) {
  449.                 int pMove = sp->getParentMoveNo();
  450.                 os << ' ' << std::setw(2) << pMove << (sp == selectedSp ? '*' : ':');
  451.                 if (pMove < 0)
  452.                     os << "null";
  453.                 else if (sp->getParent())
  454.                     os << TextIO::moveToUCIString(sp->getParent()->getSpMove(pMove).getMove());
  455.                 else
  456.                     os << TextIO::moveToUCIString(pd.topMove);
  457.                 os << ',' << toPercentStr(sp->getPSpUseful())
  458.                    << ':' << toPercentStr(sp->getPNextMoveUseful());
  459.                 os << ',' << std::setw(2) << sp->getCurrMoveNo() << ':' << std::setw(2) << sp->findNextMove(pd.fhInfo);
  460.             } else {
  461.                 os << "                    ";
  462.             }
  463.         }
  464.         os << std::endl;
  465.     }
  466. }
  467.  
  468. void
  469. WorkQueue::findLeaves(const std::shared_ptr<SplitPoint>& sp,
  470.                       std::vector<int>& parentThreads,
  471.                       std::vector<std::shared_ptr<SplitPoint>>& leaves) {
  472.     bool isLeaf = true;
  473.     const std::vector<std::weak_ptr<SplitPoint>>& children = sp->getChildren();
  474.     for (const auto& wChild : children) {
  475.         std::shared_ptr<SplitPoint> child = wChild.lock();
  476.         if (child && !child->isCanceled()) {
  477.             if (child->owningThread() == sp->owningThread()) {
  478.                 isLeaf = false;
  479.             } else {
  480.                 assert(parentThreads[child->owningThread()] == -1);
  481.                 parentThreads[child->owningThread()] = sp->owningThread();
  482.             }
  483.             findLeaves(child, parentThreads, leaves);
  484.         }
  485.     }
  486.     if (isLeaf) {
  487.         assert(sp->owningThread() >= 0);
  488.         assert(sp->owningThread() < (int)leaves.size());
  489.         leaves[sp->owningThread()] = sp;
  490.     }
  491. }
  492.  
  493. WorkQueue::Lock::Lock(const WorkQueue* wq0)
  494.     : wq(*wq0), lock(wq.mutex, std::defer_lock) {
  495.     bool contended = false;
  496.     if (!lock.try_lock()) {
  497.         contended = true;
  498.         lock.lock();
  499.     }
  500.     if (wq.queue.empty())
  501.         contended = false;
  502.     U64 c = wq.nContended;
  503.     U64 n = wq.nNonContended;
  504.     if (contended)
  505.         c++;
  506.     else
  507.         n++;
  508.     if (n + c > 30000) {
  509.         c /= 2;
  510.         n /= 2;
  511.         if (c * 100 > n * 50) {
  512.             wq.minSplitDepth++;
  513. //            std::cout << "contended stat: " << wq.minSplitDepth << " " << c << " " << n << std::endl;
  514.         } else if ((c * 100 < n * 25) && (wq.minSplitDepth > SearchConst::MIN_SMP_DEPTH)) {
  515.             wq.minSplitDepth--;
  516. //            std::cout << "contended stat: " << wq.minSplitDepth << " " << c << " " << n << std::endl;
  517.         }
  518.     }
  519.     wq.nContended = c;
  520.     wq.nNonContended = n;
  521. }
  522.  
  523. // ----------------------------------------------------------------------------
  524.  
  525. void
  526. ParallelData::addRemoveWorkers(int numWorkers) {
  527.     while (numWorkers < (int)threads.size()) {
  528.         assert(!threads.back()->threadRunning());
  529.         threads.pop_back();
  530.     }
  531.     for (int i = threads.size(); i < numWorkers; i++)
  532.         threads.push_back(std::make_shared<WorkerThread>(i+1, *this, tt));
  533. }
  534.  
  535. void
  536. ParallelData::startAll() {
  537.     totalHelperNodes = 0;
  538.     helperTbHits = 0;
  539.     wq.setStopped(false);
  540.     for (auto& thread : threads)
  541.         thread->start();
  542. }
  543.  
  544. void
  545. ParallelData::stopAll() {
  546.     wq.setStopped(true);
  547.     for (auto& thread : threads)
  548.         thread->join();
  549. }
  550.  
  551. // ----------------------------------------------------------------------------
  552.  
  553. SplitPoint::SplitPoint(int threadNo0,
  554.                        const std::shared_ptr<SplitPoint>& parentSp0, int parentMoveNo0,
  555.                        const Position& pos0, const std::vector<U64>& posHashList0,
  556.                        int posHashListSize0, const SearchTreeInfo& sti0,
  557.                        const KillerTable& kt0, const History& ht0,
  558.                        int alpha0, int beta0, int ply0, int depth0)
  559.     : pos(pos0), posHashList(posHashList0), posHashListSize(posHashListSize0),
  560.       searchTreeInfo(sti0), kt(kt0), ht(ht0),
  561.       alpha(alpha0), beta(beta0), ply(ply0), depth(depth0),
  562.       isPV(beta0 > alpha0 + 1),
  563.       pSpUseful(0.0), pNextMoveUseful(0.0),
  564.       threadNo(threadNo0), parent(parentSp0), parentMoveNo(parentMoveNo0),
  565.       seqNo(0), currMoveNo(0), inserted(false), canceled(false) {
  566. }
  567.  
  568. void
  569. SplitPoint::addMove(int moveNo, const SplitPointMove& spMove) {
  570.     assert(moveNo >= (int)spMoves.size());
  571.     while ((int)spMoves.size() < moveNo)
  572.         spMoves.push_back(SplitPointMove(Move(), 0, -1, -1, false));
  573.     spMoves.push_back(spMove);
  574. }
  575.  
  576. void
  577. SplitPoint::computeProbabilities(const FailHighInfo& fhInfo, const DepthNpsInfo& npsInfo) {
  578.     if (parent) {
  579.         double pMoveUseful = 1.0;
  580.         if (parentMoveNo >= 0)
  581.             pMoveUseful = parent->getMoveNeededProbability(fhInfo, parentMoveNo);
  582.         pSpUseful = parent->pSpUseful * pMoveUseful;
  583.     } else {
  584.         pSpUseful = 1.0;
  585.     }
  586.     double pNextUseful = getMoveNeededProbability(fhInfo, findNextMove(fhInfo));
  587.     pNextMoveUseful = pSpUseful * pNextUseful;
  588.     newPrio(getSpPrio(npsInfo));
  589.  
  590.     bool deleted = false;
  591.     for (const auto& wChild : children) {
  592.         std::shared_ptr<SplitPoint> child = wChild.lock();
  593.         if (child)
  594.             child->computeProbabilities(fhInfo, npsInfo);
  595.         else
  596.             deleted = true;
  597.     }
  598.     if (deleted)
  599.         cleanUpChildren();
  600. }
  601.  
  602. double
  603. SplitPoint::getPMoveUseful(const FailHighInfo& fhInfo, int moveNo) const {
  604.     return pSpUseful * getMoveNeededProbability(fhInfo, moveNo);
  605. }
  606.  
  607. void
  608. SplitPoint::getPos(Position& pos, const Move& move) const {
  609.     pos = this->pos;
  610.     UndoInfo ui;
  611.     pos.makeMove(move, ui);
  612. }
  613.  
  614. void
  615. SplitPoint::getPosHashList(const Position& pos, std::vector<U64>& posHashList,
  616.                            int& posHashListSize) const {
  617.     posHashList = this->posHashList;
  618.     posHashListSize = this->posHashListSize;
  619.     posHashList[posHashListSize++] = pos.zobristHash();
  620. }
  621.  
  622. int
  623. SplitPoint::getNextMove(const FailHighInfo& fhInfo) {
  624.     int m = findNextMove(fhInfo);
  625.     if (m < 0)
  626.         return m;
  627.     spMoves[m].setSearching(true);
  628.     return m;
  629. }
  630.  
  631. void
  632. SplitPoint::moveFinished(int moveNo, bool cancelRemaining, int score) {
  633.     assert((moveNo >= 0) && (moveNo < (int)spMoves.size()));
  634.     spMoves[moveNo].setScore(score);
  635.     spMoves[moveNo].setSearching(false);
  636.     spMoves[moveNo].setCanceled(true);
  637.     if (cancelRemaining)
  638.         for (int i = moveNo+1; i < (int)spMoves.size(); i++)
  639.             spMoves[i].setCanceled(true);
  640. }
  641.  
  642. bool
  643. SplitPoint::hasUnStartedMove() const {
  644.     if (canceled)
  645.         return false;
  646.     for (int i = currMoveNo + 1; i < (int)spMoves.size(); i++)
  647.         if (!spMoves[i].isCanceled() && !spMoves[i].isSearching())
  648.             return true;
  649.     return false;
  650. }
  651.  
  652. bool
  653. SplitPoint::hasUnFinishedMove() const {
  654.     if (canceled)
  655.         return false;
  656.     for (int i = currMoveNo + 1; i < (int)spMoves.size(); i++)
  657.         if (!spMoves[i].isCanceled())
  658.             return true;
  659.     return false;
  660. }
  661.  
  662. int
  663. SplitPoint::findNextMove(const FailHighInfo& fhInfo) const {
  664.     int i0 = -1;
  665.     const double pGood = 0.98;
  666.     for (int i = currMoveNo+1; i < (int)spMoves.size(); i++)
  667.         if (!spMoves[i].isCanceled() && !spMoves[i].isSearching()) {
  668.             if ((getPNextMoveUseful() > pGood) && (i0 == -1))
  669.                 i0 = i;
  670.             else {
  671.                 if ((i0 != -1) && (getPMoveUseful(fhInfo, i) <= pGood))
  672.                     return i0;
  673.                 return i;
  674.             }
  675.         }
  676.     return i0;
  677. }
  678.  
  679. double
  680. SplitPoint::getMoveNeededProbability(const FailHighInfo& fhInfo, int moveNo) const {
  681.     if (isPvNode())
  682.         return fhInfo.getMoveNeededProbabilityPv(currMoveNo, moveNo);
  683.     else
  684.         return fhInfo.getMoveNeededProbability(parentMoveNo,
  685.                                                currMoveNo,
  686.                                                moveNo, isAllNode());
  687. }
  688.  
  689. void
  690. SplitPoint::cleanUpChildren() {
  691.     std::vector<std::weak_ptr<SplitPoint>> toKeep;
  692.     for (const auto& wChild : children)
  693.         if (wChild.lock())
  694.             toKeep.push_back(wChild);
  695.     children = toKeep;
  696. }
  697.  
  698. bool
  699. SplitPoint::hasHelperThread() const {
  700.     for (const auto& wChild : children) {
  701.         std::shared_ptr<SplitPoint> child = wChild.lock();
  702.         if (child && child->owningThread() != owningThread())
  703.             return true;
  704.     }
  705.     return false;
  706. }
  707.  
  708. bool
  709. SplitPoint::isAncestorTo(const SplitPoint& sp) const {
  710.     const SplitPoint* tmp = &sp;
  711.     while (tmp) {
  712.         if (tmp == this)
  713.             return true;
  714.         tmp = &*(tmp->parent);
  715.     }
  716.     return false;
  717. }
  718.  
  719. bool
  720. SplitPoint::isAllNode() const {
  721.     int nFirst = 0;
  722.     const SplitPoint* tmp = this;
  723.     while (tmp) {
  724.         if (tmp->parentMoveNo == 0)
  725.             nFirst++;
  726.         else
  727.             break;
  728.         tmp = &*(tmp->parent);
  729.     }
  730.     return (nFirst % 2) != 0;
  731. }
  732.  
  733. void
  734. SplitPoint::print(std::ostream& os, int level, const FailHighInfo& fhInfo) const {
  735.     std::string pad(level*2, ' ');
  736.     os << pad << "seq:" << seqNo << " pos:" << TextIO::toFEN(pos) << std::endl;
  737.     os << pad << "parent:" << parentMoveNo << " hashListSize:" << posHashListSize <<
  738.         " a:" << alpha << " b:" << beta << " ply:" << ply << " canceled:" << canceled << std::endl;
  739.     os << pad << "p1:" << pSpUseful << " p2:" << pNextMoveUseful << " curr:" << currMoveNo << std::endl;
  740.     os << pad << "moves:";
  741.     for (int mi = 0; mi < (int)spMoves.size(); mi++) {
  742.         const auto& spm = spMoves[mi];
  743.         os << ' ' << TextIO::moveToUCIString(spm.getMove());
  744.         if (spm.isCanceled())
  745.             os << ",c";
  746.         if (spm.isSearching())
  747.             os << ",s";
  748.         os << "," << getMoveNeededProbability(fhInfo, mi);
  749.     }
  750.     os << std::endl;
  751.     for (const auto& wChild : children) {
  752.         std::shared_ptr<SplitPoint> child = wChild.lock();
  753.         if (child)
  754.             child->print(os, level+1, fhInfo);
  755.     }
  756. }
  757.  
  758. // ----------------------------------------------------------------------------
  759.  
  760. void
  761. SplitPointHolder::setSp(const std::shared_ptr<SplitPoint>& sp0) {
  762.     assert(state == State::EMPTY);
  763.     assert(sp0);
  764.     sp = sp0;
  765.     if (sp->getBeta() > sp->getAlpha() + 1)
  766.         pd.fhInfo.addPvData(-1, false);
  767.     state = State::CREATED;
  768. }
  769.  
  770. void
  771. SplitPointHolder::addToQueue() {
  772.     assert(state == State::CREATED);
  773.     pd.wq.tryAddWork(sp, pending);
  774.     spVec.push_back(sp);
  775. //    log([&](std::ostream& os){os << "add seqNo:" << sp->getSeqNo() << " ply:" << sp->getPly()
  776. //                                 << " pNext:" << sp->getPNextMoveUseful()
  777. //                                 << " pMove:" << sp->getParentMoveNo() << " vec:" << spVec.size();});
  778.     state = State::QUEUED;
  779. }
  780.  
  781. // ----------------------------------------------------------------------------
  782.  
  783. FailHighInfo::FailHighInfo()
  784.     : totCount(0) {
  785.     for (int i = 0; i < NUM_NODE_TYPES; i++)
  786.         failLoCount[i] = 0;
  787.     for (int j = 0; j < NUM_STAT_MOVES; j++)
  788.         newAlpha[j] = 0;
  789.     totPvCount = 0;
  790. }
  791.  
  792. double
  793. FailHighInfo::getMoveNeededProbability(int parentMoveNo,
  794.                                        int currMoveNo, int moveNo, bool allNode) const {
  795.     const int pIdx = getNodeType(parentMoveNo, allNode);
  796.     moveNo = std::min(moveNo, NUM_STAT_MOVES-1);
  797.     if (moveNo < 0)
  798.         return 0.0;
  799.  
  800.     int nNeeded = failLoCount[pIdx] + failHiCount[pIdx].sum(moveNo, NUM_STAT_MOVES);
  801.     int nTotal = nNeeded + failHiCount[pIdx].sum(currMoveNo, moveNo);
  802.  
  803.     return (nTotal > 0) ? nNeeded / (double)nTotal : 0.5;
  804. }
  805.  
  806. double
  807. FailHighInfo::getMoveNeededProbabilityPv(int currMoveNo, int moveNo) const {
  808.     moveNo = std::min(moveNo, NUM_STAT_MOVES-1);
  809.     if (moveNo < 0)
  810.         return 0.0;
  811.     if (totPvCount <= 0)
  812.         return 0.5;
  813.  
  814.     double prob = 1.0;
  815.     double inv = 1.0 / totPvCount;
  816.     for (int i = currMoveNo; i < moveNo; i++)
  817.         prob *= std::max(0.0, 1.0 - newAlpha[i] * inv);
  818.     return prob;
  819. }
  820.  
  821. void
  822. FailHighInfo::addData(int parentMoveNo, int nSearched, bool failHigh, bool allNode) {
  823.     if (nSearched < 0)
  824.         return;
  825.     const int pIdx = getNodeType(parentMoveNo, allNode);
  826.     if (failHigh) {
  827.         nSearched = std::min(nSearched, NUM_STAT_MOVES-1);
  828.         failHiCount[pIdx].add(nSearched, 1);
  829.     } else {
  830.         failLoCount[pIdx]++;
  831.     }
  832.     totCount++;
  833.     if (totCount >= 1000000) {
  834.         std::lock_guard<std::mutex> L(mutex);
  835.         if (totCount >= 1000000)
  836.             reScaleInternal(2);
  837.     }
  838. }
  839.  
  840. void
  841. FailHighInfo::addPvData(int nSearched, bool alphaChanged) {
  842.     if (nSearched >= 0) {
  843.         if (alphaChanged && nSearched < NUM_STAT_MOVES)
  844.             newAlpha[nSearched]++;
  845.     } else {
  846.         totPvCount++;
  847.         if (totPvCount >= 10000) {
  848.             std::lock_guard<std::mutex> L(mutex);
  849.             if (totPvCount >= 10000)
  850.                 reScalePv(2);
  851.         }
  852.     }
  853. }
  854.  
  855. void
  856. FailHighInfo::reScale() {
  857.     reScaleInternal(4);
  858.     reScalePv(4);
  859. }
  860.  
  861. void
  862. FailHighInfo::reScaleInternal(int factor) {
  863.     for (int i = 0; i < NUM_NODE_TYPES; i++) {
  864.         for (int j = 0; j < NUM_STAT_MOVES; j++) {
  865.             int val = failHiCount[i].get(j);
  866.             failHiCount[i].add(j, val / factor - val);
  867.         }
  868.         failLoCount[i] = failLoCount[i] / factor;
  869.     }
  870.     totCount = totCount / factor;
  871. }
  872.  
  873. void
  874. FailHighInfo::reScalePv(int factor) {
  875.     for (int j = 0; j < NUM_STAT_MOVES; j++)
  876.         newAlpha[j] = newAlpha[j] / factor;
  877.     totPvCount = totPvCount / factor;
  878. }
  879.  
  880. void
  881. FailHighInfo::print(std::ostream& os) const {
  882.     for (int i = 0; i < NUM_NODE_TYPES; i++) {
  883.         os << "fhInfo: " << i << ' ' << std::setw(6) << failLoCount[i];
  884.         for (int j = 0; j < NUM_STAT_MOVES; j++)
  885.             os << ' ' << std::setw(6) << failHiCount[i].get(j);
  886.         os << std::endl;
  887.     }
  888.     os << "fhInfo: " << NUM_NODE_TYPES << ' ' << std::setw(6) << totPvCount;
  889.     for (int j = 0; j < NUM_STAT_MOVES; j++)
  890.         os << ' ' << std::setw(6) << newAlpha[j];
  891.     os << std::endl;
  892. }
  893.  
  894. // ----------------------------------------------------------------------------
  895.  
  896. void
  897. DepthNpsInfo::print(std::ostream& os, int iterDepth) {
  898.     std::lock_guard<std::mutex> L(mutex);
  899.     os << "npsInfo: depth:" << iterDepth << " nps0:" << nps0
  900.        << " wait:" << waitTime / nSearches << std::endl;
  901.     for (int i = SearchConst::MIN_SMP_DEPTH; i < maxDepth; i++) {
  902.         os << "npsInfo: d:" << i
  903.            << " n:" << npsData[i].nSearches
  904.            << " nodes:" << npsData[i].nodes
  905.            << " time:" << npsData[i].time
  906.            << " nps:" << npsData[i].nodes / npsData[i].time
  907.            << " ts:" << npsData[i].nodes / (double)npsData[i].nSearches
  908.            << " eff:" << efficiencyInternal(i) << std::endl;
  909.     }
  910. }
  911.