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.hpp
  21.  *
  22.  *  Created on: Jul 9, 2013
  23.  *      Author: petero
  24.  */
  25.  
  26. #ifndef PARALLEL_HPP_
  27. #define PARALLEL_HPP_
  28.  
  29. #include "killerTable.hpp"
  30. #include "history.hpp"
  31. #include "transpositionTable.hpp"
  32. #include "evaluate.hpp"
  33. #include "searchUtil.hpp"
  34. #include "constants.hpp"
  35. #include "util/timeUtil.hpp"
  36. #include "util/heap.hpp"
  37.  
  38. #include <memory>
  39. #include <vector>
  40. #include <set>
  41. #include <thread>
  42. #include <mutex>
  43. #include <condition_variable>
  44. #include <atomic>
  45.  
  46.  
  47. class Search;
  48. class SearchTreeInfo;
  49.  
  50. class ParallelData;
  51. class SplitPoint;
  52. class SplitPointMove;
  53. class FailHighInfo;
  54. class DepthNpsInfo;
  55.  
  56.  
  57. class WorkerThread {
  58. public:
  59.     /** Constructor. Does not start new thread. */
  60.     WorkerThread(int threadNo, ParallelData& pd, TranspositionTable& tt);
  61.  
  62.     /** Destructor. Waits for thread to terminate. */
  63.     ~WorkerThread();
  64.  
  65.     WorkerThread(const WorkerThread&) = delete;
  66.     WorkerThread& operator=(const WorkerThread&) = delete;
  67.  
  68.     /** Start thread. */
  69.     void start();
  70.  
  71.     /** Wait for thread to stop. */
  72.     void join();
  73.  
  74.     /** Return true if thread is running. */
  75.     bool threadRunning() const;
  76.  
  77.     /** Return thread number. The first worker thread is number 1. */
  78.     int getThreadNo() const;
  79.  
  80.     /** For debugging. */
  81.     double getPUseful() const;
  82.  
  83. private:
  84.     /** Thread main loop. */
  85.     void mainLoop(int minProbeDepth);
  86.  
  87.     int threadNo;
  88.     ParallelData& pd;
  89.     std::shared_ptr<std::thread> thread;
  90.  
  91.     std::shared_ptr<Evaluate::EvalHashTables> et;
  92.     std::shared_ptr<KillerTable> kt;
  93.     std::shared_ptr<History> ht;
  94.     TranspositionTable& tt;
  95.  
  96.     double pUseful; // Probability that thread is currently doing something useful, for debugging
  97. };
  98.  
  99.  
  100. /** Priority queue of pending search tasks. Handles thread safety. */
  101. class WorkQueue {
  102.     friend class ParallelTest;
  103. public:
  104.     /** Constructor. */
  105.     WorkQueue(const FailHighInfo& fhInfo, const DepthNpsInfo& npsInfo);
  106.  
  107.     /** Set/get stopped flag. */
  108.     void setStopped(bool stop);
  109.     bool isStopped() const;
  110.  
  111.     /** Reset dynamic minimum split depth to default value. */
  112.     void resetSplitDepth();
  113.  
  114.     /** Add SplitPoint to work queue. */
  115.     void addWork(const std::shared_ptr<SplitPoint>& sp);
  116.  
  117.     /** Try to add SplitPoint to work queue. If queue is contended add SplitPoint
  118.      * to pending instead. */
  119.     void tryAddWork(const std::shared_ptr<SplitPoint>& sp,
  120.                     std::vector<std::shared_ptr<SplitPoint>>& pending);
  121.  
  122.     /** Get best move for helper thread to work on. */
  123.     std::shared_ptr<SplitPoint> getWork(int& moveNo, ParallelData& pd, int threadNo);
  124.     std::shared_ptr<SplitPoint> getWork(int& moveNo, ParallelData& pd, int threadNo,
  125.                                         int& prio, double& pUseful);
  126.  
  127.     /** A helper thread stopped working on a move before it was finished. */
  128.     void returnMove(const std::shared_ptr<SplitPoint>& sp, int moveNo);
  129.  
  130.     /** Set which move number the SplitPoint owner is currently searching.
  131.      * @return Score from helper search thread. UNKNOWN_SCORE if no helper has
  132.      *         searched the move. */
  133.     int setOwnerCurrMove(const std::shared_ptr<SplitPoint>& sp, int moveNo, int alpha);
  134.  
  135.     /** Cancel this SplitPoint and all children. */
  136.     void cancel(const std::shared_ptr<SplitPoint>& sp);
  137.  
  138.     /** Set move to canceled after helper thread finished searching it. */
  139.     void moveFinished(const std::shared_ptr<SplitPoint>& sp, int moveNo,
  140.                       bool cancelRemaining, int score);
  141.  
  142.     /** Return probability that the best unstarted move needs to be searched.
  143.      *  Also return the corresponding SplitPoint. */
  144.     double getBestProbability(std::shared_ptr<SplitPoint>& bestSp) const;
  145.     double getBestProbability() const;
  146.     int getBestPrio() const;
  147.  
  148.     /** Return current dynamic minimum split depth. */
  149.     int getMinSplitDepth() const;
  150.  
  151.     /** For performance measurements on queue operations. */
  152.     void resetStat();
  153.     TimeSampleStatistics& getAddWorkStat(int th);
  154.     TimeSampleStatistics& getGetWorkStat(int th);
  155.     void printStats(std::ostream& os, int nThreads);
  156.  
  157. private:
  158.     /** Insert sp in queue. Notify condition variable if queue becomes non-empty. */
  159.     void insertInQueue(const std::shared_ptr<SplitPoint>& sp);
  160.  
  161.     /** Recompute probabilities for "sp" and all children. Update "queue" and "waiting". */
  162.     void updateProbabilities(const std::shared_ptr<SplitPoint>& sp);
  163.  
  164.     /** Cancel "sp" and all children. Assumes mutex already locked. */
  165.     void cancelInternal(const std::shared_ptr<SplitPoint>& sp);
  166.  
  167.     void printSpTree(std::ostream& os, const ParallelData& pd,
  168.                      int threadNo, const std::shared_ptr<SplitPoint> selectedSp,
  169.                      int selectedMove);
  170.     void findLeaves(const std::shared_ptr<SplitPoint>& sp, std::vector<int>& parentThreads,
  171.                     std::vector<std::shared_ptr<SplitPoint>>& leaves);
  172.  
  173.     /** Helper for addWork() and tryAddWork(). */
  174.     void addWorkInternal(const std::shared_ptr<SplitPoint>& sp);
  175.  
  176.     /** Scoped lock that measures lock contention and adjusts minSplitDepth accordingly. */
  177.     class Lock {
  178.     public:
  179.         Lock(const WorkQueue* wq0);
  180.         void wait(std::condition_variable& cv);
  181.     private:
  182.         const WorkQueue& wq;
  183.         std::unique_lock<std::mutex> lock;
  184.     };
  185.     friend class Lock;
  186.     std::atomic<bool> stopped;
  187.  
  188.     mutable int minSplitDepth;      // Dynamic minimum split depth
  189.     mutable U64 nContended;         // Number of times mutex has been contended
  190.     mutable U64 nNonContended;      // Number of times mutex has not been contended
  191.  
  192.     std::condition_variable cv;     // Notified when wq becomes non-empty and when search should stop
  193.     const FailHighInfo& fhInfo;
  194.     const DepthNpsInfo& npsInfo;
  195.     mutable std::mutex mutex;
  196.  
  197.     // SplitPoints with unstarted SplitPointMoves
  198.     // SplitPoints with no unstarted moves have negative priority.
  199.     Heap<SplitPoint> queue;
  200.  
  201.     // For performance debugging
  202.     static const int maxStatThreads = 64;
  203.     TimeSampleStatisticsVector<maxStatThreads*2> wqStat;
  204. };
  205.  
  206.  
  207. /** Fail high statistics, for estimating SplitPoint usefulness probabilities. */
  208. class FailHighInfo {
  209. public:
  210.     /** Constructor. */
  211.     FailHighInfo();
  212.  
  213.     /** Return probability that move moveNo needs to be searched.
  214.      * @param parentMoveNo  Move number of move leading to this position.
  215.      * @param currMoveNo    Move currently being searched.
  216.      * @param moveNo        Move number to get probability for.
  217.      * @param allNode       True if this is an expected ALL node. */
  218.     double getMoveNeededProbability(int parentMoveNo, int currMoveNo, int moveNo, bool allNode) const;
  219.  
  220.     /** Return probability that move moveNo needs to be searched in a PV node.
  221.      * @param currMoveNo    Move currently being searched.
  222.      * @param moveNo        Move number to get probability for.
  223.      * @param allNode       True if this is an expected ALL node. */
  224.     double getMoveNeededProbabilityPv(int currMoveNo, int moveNo) const;
  225.  
  226.     /** Add fail high information.
  227.      * @param parentMoveNo  Move number of move leading to this position.
  228.      * @param nSearched     Number of moves searched at this node.
  229.      * @param failHigh      True if the node failed high.
  230.      * @param allNode       True if this is an expected ALL node. */
  231.     void addData(int parentMoveNo, int nSearched, bool failHigh, bool allNode);
  232.  
  233.     /** Add "alpha increased" information for PV nodes.
  234.      * @param  nSearched     Number of moves searched at this node.
  235.      * @param  alphaChanged  True if alpha increased after searching move. */
  236.     void addPvData(int nSearched, bool alphaChanged);
  237.  
  238.     /** Rescale the counters so that future updates have more weight. */
  239.     void reScale();
  240.  
  241.     /** Print object state to "os", for debugging. */
  242.     void print(std::ostream& os) const;
  243.  
  244. private:
  245.     void reScaleInternal(int factor);
  246.     void reScalePv(int factor);
  247.  
  248.     int getNodeType(int moveNo, bool allNode) const;
  249.  
  250.     mutable std::mutex mutex;
  251.  
  252.     static const int NUM_NODE_TYPES = 4;
  253.     static const int NUM_STAT_MOVES = 15;
  254.  
  255.     RangeSumArray<NUM_STAT_MOVES> failHiCount[NUM_NODE_TYPES]; // [parentMoveNo>0?1:0][moveNo]
  256.     std::atomic<int> failLoCount[NUM_NODE_TYPES];              // [parentMoveNo>0?1:0]
  257.     std::atomic<int> totCount;                                 // Sum of all counts
  258.  
  259.     std::atomic<int> newAlpha[NUM_STAT_MOVES];
  260.     std::atomic<int> totPvCount;
  261. };
  262.  
  263. class DepthNpsInfo {
  264. public:
  265.     /** Constructor. */
  266.     DepthNpsInfo();
  267.  
  268.     /** Reset */
  269.     void reset();
  270.  
  271.     /** Set thread 0 estimated nps. Used to scale efficiency calculations
  272.      *  to [0,1] interval. */
  273.     void setBaseNps(double nps);
  274.  
  275.     /** Add one data point. */
  276.     void addData(int depth, U64 nodes, double waitTime, double searchTime);
  277.  
  278.     /** Return estimate search efficiency when searching to a given depth. */
  279.     double efficiency(int depth) const;
  280.  
  281.     /** Print object state to "os", for debugging. */
  282.     void print(std::ostream& os, int iterDepth);
  283.  
  284.     /** Maximum depth statistics is kept for. */
  285.     static const int maxDepth = 48;
  286.  
  287. private:
  288.     /** Helper method for efficiency() and print(). */
  289.     double efficiencyInternal(int depth) const;
  290.  
  291.     mutable std::mutex mutex;
  292.  
  293.     struct NpsData {
  294.         NpsData();
  295.         U32 nSearches;
  296.         U64 nodes;
  297.         double time;
  298.     };
  299.     NpsData npsData[maxDepth];
  300.     double nps0;
  301.     U32 nSearches;      // Total number of searches
  302.     double waitTime;    // Total waiting time
  303. };
  304.  
  305. /** Top-level parallel search data structure. */
  306. class ParallelData {
  307. public:
  308.     /** Constructor. */
  309.     ParallelData(TranspositionTable& tt);
  310.  
  311.     /** Create/delete worker threads so that there are numWorkers in total. */
  312.     void addRemoveWorkers(int numWorkers);
  313.  
  314.     /** Start all worker threads. */
  315.     void startAll();
  316.  
  317.     /** Stop all worker threads. */
  318.     void stopAll();
  319.  
  320.  
  321.     /** Return number of helper threads in use. */
  322.     int numHelperThreads() const;
  323.  
  324.     /** Get number of nodes searched by all helper threads. */
  325.     S64 getNumSearchedNodes() const;
  326.  
  327.     /** Get number of TB hits for all helper threads. */
  328.     S64 getTbHits() const;
  329.  
  330.     /** Add nNodes to total number of searched nodes. */
  331.     void addSearchedNodes(S64 nNodes);
  332.  
  333.     /** Add nTbHits to number of TB hits. */
  334.     void addTbHits(S64 nTbHits);
  335.  
  336.  
  337.     /** For debugging. */
  338.     const WorkerThread& getHelperThread(int i) const;
  339.  
  340.     FailHighInfo fhInfo;
  341.     DepthNpsInfo npsInfo;
  342.  
  343.     WorkQueue wq;
  344.  
  345.     /** Move played in Search::iterativeDeepening before calling negaScout. For debugging. */
  346.     Move topMove;
  347.  
  348.     /** Current node index in thread 0. Used by tree logging code. */
  349.     std::atomic<U32> t0Index;
  350.  
  351. private:
  352.     /** Vector of helper threads. Master thread not included. */
  353.     std::vector<std::shared_ptr<WorkerThread>> threads;
  354.  
  355.     TranspositionTable& tt;
  356.  
  357.     std::atomic<S64> totalHelperNodes; // Number of nodes searched by all helper threads
  358.     std::atomic<S64> helperTbHits;     // Number of TB hits for all helper threads
  359. };
  360.  
  361.  
  362. /** SplitPoint does not handle thread safety, WorkQueue must do that.  */
  363. class SplitPoint : public Heap<SplitPoint>::HeapObject {
  364.     friend class ParallelTest;
  365. public:
  366.     /** Constructor. */
  367.     SplitPoint(int threadNo,
  368.                const std::shared_ptr<SplitPoint>& parentSp, int parentMoveNo,
  369.                const Position& pos, const std::vector<U64>& posHashList,
  370.                int posHashListSize, const SearchTreeInfo& sti,
  371.                const KillerTable& kt, const History& ht,
  372.                int alpha, int beta, int ply, int depth);
  373.  
  374.     SplitPoint(const SplitPoint&) = delete;
  375.     SplitPoint& operator=(const SplitPoint&) = delete;
  376.  
  377.     /** Add a child SplitPoint */
  378.     void addChild(const std::weak_ptr<SplitPoint>& child);
  379.  
  380.     /** Add a move to the SplitPoint. */
  381.     void addMove(int moveNo, const SplitPointMove& spMove);
  382.  
  383.     /** Assign sequence number. */
  384.     void setSeqNo();
  385.  
  386.     /** compute pSpUseful and pnextMoveUseful. */
  387.     void computeProbabilities(const FailHighInfo& fhInfo, const DepthNpsInfo& npsInfo);
  388.  
  389.     /** Get parent SplitPoint, or null for root SplitPoint. */
  390.     std::shared_ptr<SplitPoint> getParent() const;
  391.  
  392.     /** Get children SplitPoints. */
  393.     const std::vector<std::weak_ptr<SplitPoint>>& getChildren() const;
  394.  
  395.  
  396.     U64 getSeqNo() const;
  397.     double getPSpUseful() const;
  398.     double getPNextMoveUseful() const;
  399.     const History& getHistory() const;
  400.     const KillerTable& getKillerTable() const;
  401.     const SplitPointMove& getSpMove(int moveNo) const;
  402.  
  403.     /** Return probability that moveNo needs to be searched. */
  404.     double getPMoveUseful(const FailHighInfo& fhInfo, int moveNo) const;
  405.  
  406.     void getPos(Position& pos, const Move& move) const;
  407.     void getPosHashList(const Position& pos, std::vector<U64>& posHashList,
  408.                         int& posHashListSize) const;
  409.     const SearchTreeInfo& getSearchTreeInfo() const;
  410.     int getAlpha() const;
  411.     int getBeta() const;
  412.     int getPly() const;
  413.     int getDepth() const;
  414.  
  415.  
  416.     /** Get index of first unstarted move. Mark move as being searched.
  417.      * Return -1 if there are no unstarted moves. */
  418.     int getNextMove(const FailHighInfo& fhInfo);
  419.  
  420.     /** A helper thread stopped working on a move before it was finished. */
  421.     void returnMove(int moveNo);
  422.  
  423.     /** Set which move number the SplitPoint owner is currently searching.
  424.      * @return Score from helper search thread. UNKNOWN_SCORE if no helper has
  425.      *         searched the move. */
  426.     int setOwnerCurrMove(int moveNo, int alpha);
  427.  
  428.     /** Cancel this SplitPoint and all children. */
  429.     void cancel();
  430.  
  431.     /** Return true if this SplitPoint has been canceled. */
  432.     bool isCanceled() const;
  433.  
  434.     /** Set move to canceled after helper thread finished searching it. */
  435.     void moveFinished(int moveNo, bool cancelRemaining, int score);
  436.  
  437.     /** Return true if there are moves that have not been started to be searched. */
  438.     bool hasUnStartedMove() const;
  439.  
  440.     /** Return true if there are moves that have not been finished (canceled) yet. */
  441.     bool hasUnFinishedMove() const;
  442.  
  443.     /** Return true if this SplitPoint is an ancestor to "sp". */
  444.     bool isAncestorTo(const SplitPoint& sp) const;
  445.  
  446.     /** Return true if some other thread is helping the SplitPoint owner. */
  447.     bool hasHelperThread() const;
  448.  
  449.     /** Return true if the held SplitPoint is an estimated ALL node. */
  450.     bool isAllNode() const;
  451.  
  452.     /** Return true if beta > alpha + 1. */
  453.     bool isPvNode() const;
  454.  
  455.     /** Compute SplitPoint priority. The SplitPoint with highest
  456.      * priority will be selected first by the next available thread. */
  457.     int getSpPrio(const DepthNpsInfo& npsInfo) const;
  458.  
  459.     /** Thread that created this SplitPoint. */
  460.     int owningThread() const;
  461.  
  462.     /** Return true if object is or has been inserted in WorkQueue. */
  463.     bool wasInserted() const;
  464.  
  465.     /** Mark SplitPoint as inserted in WorkQueue. */
  466.     void setInserted();
  467.  
  468.     /** Print object state to "os", for debugging. */
  469.     void print(std::ostream& os, int level, const FailHighInfo& fhInfo) const;
  470.  
  471.     /** For debugging. */
  472.     int getParentMoveNo() const;
  473.  
  474.     /** For debugging. */
  475.     int getCurrMoveNo() const;
  476.  
  477.     /** Get index of first unstarted move, or -1 if there is no unstarted move. */
  478.     int findNextMove(const FailHighInfo& fhInfo) const;
  479.  
  480. private:
  481.     /** Return probability that moveNo needs to be searched, by calling corresponding
  482.      * function in fhInfo. */
  483.     double getMoveNeededProbability(const FailHighInfo& fhInfo, int moveNo) const;
  484.  
  485.     /** Remove null entries from children vector. */
  486.     void cleanUpChildren();
  487.  
  488.     const Position pos;
  489.     const std::vector<U64> posHashList; // List of hashes for previous positions up to the last "zeroing" move.
  490.     const int posHashListSize;
  491.     const SearchTreeInfo searchTreeInfo;   // For ply-1
  492.     const KillerTable& kt;
  493.     const History& ht;
  494.  
  495.     RelaxedShared<int> alpha;
  496.     const int beta;
  497.     const int ply;
  498.     const int depth;
  499.     const bool isPV;
  500.  
  501.     double pSpUseful;       // Probability that this SplitPoint is needed. 100% if parent is null.
  502.     double pNextMoveUseful; // Probability that next unstarted move needs to be searched.
  503.  
  504.     const int threadNo;     // Owning thread
  505.     const std::shared_ptr<SplitPoint> parent;
  506.     const int parentMoveNo; // Move number in parent SplitPoint that generated this SplitPoint
  507.     std::vector<std::weak_ptr<SplitPoint>> children;
  508.  
  509.     static U64 nextSeqNo;
  510.     U64 seqNo;      // To break ties when two objects have same priority. Set by addWork() under lock
  511.     int currMoveNo;
  512.     std::vector<SplitPointMove> spMoves;
  513.  
  514.     bool inserted; // True if sp has been inserted in WorkQueue. Remains true after deletion.
  515.     bool canceled;
  516. };
  517.  
  518.  
  519. /** Represents one move at a SplitPoint. */
  520. class SplitPointMove {
  521. public:
  522.     /** Constructor */
  523.     SplitPointMove(const Move& move, int lmr, int depth,
  524.                    int captSquare, bool inCheck);
  525.  
  526.     const Move& getMove() const;
  527.     int getLMR() const;
  528.     int getDepth() const;
  529.     int getRecaptureSquare() const;
  530.     bool getInCheck() const;
  531.  
  532.     bool isCanceled() const;
  533.     void setCanceled(bool value);
  534.  
  535.     bool isSearching() const;
  536.     void setSearching(bool value);
  537.  
  538.     void setScore(int s);
  539.     int getScore() const;
  540.  
  541. private:
  542.     Move move;      // Position defined by sp->pos + move
  543.     int lmr;        // Amount of LMR reduction
  544.     int depth;
  545.     int captSquare; // Recapture square, or -1 if no recapture
  546.     bool inCheck;   // True if side to move is in check
  547.  
  548.     RelaxedShared<bool> canceled; // Result is no longer needed
  549.     bool searching; // True if currently searched by a helper thread
  550.     int score;
  551. };
  552.  
  553.  
  554. /** Handle a SplitPoint object using RAII. */
  555. class SplitPointHolder {
  556. public:
  557.     /** Constructor. */
  558.     SplitPointHolder(ParallelData& pd, std::vector<std::shared_ptr<SplitPoint>>& spVec,
  559.                      std::vector<std::shared_ptr<SplitPoint>>& pending);
  560.  
  561.     /** Destructor. Cancel SplitPoint. */
  562.     ~SplitPointHolder();
  563.  
  564.     SplitPointHolder(const SplitPointHolder&) = delete;
  565.     SplitPointHolder& operator=(const SplitPointHolder&) = delete;
  566.  
  567.     /** Set the SplitPoint object. */
  568.     void setSp(const std::shared_ptr<SplitPoint>& sp);
  569.  
  570.     /** Add a move to the SplitPoint. */
  571.     void addMove(int moveNo, const SplitPointMove& spMove);
  572.  
  573.     /** Add SplitPoint to work queue. If the queue is contended, store SplitPoint
  574.      * in pending vector instead. If queue is not contended, also insert all
  575.      * objects from the pending vector and clear the pending vector. */
  576.     void addToQueue();
  577.  
  578.     /** Set which move number the SplitPoint owner is currently searching.
  579.      * @return Score from helper search thread. UNKNOWN_SCORE if no helper has
  580.      *         searched the move. */
  581.     int setOwnerCurrMove(int moveNo, int alpha);
  582.  
  583.     /** For debugging. */
  584.     U64 getSeqNo() const;
  585.  
  586.     /** Return true if the held SplitPoint is an estimated ALL node. */
  587.     bool isAllNode() const;
  588.  
  589.     /** Return true if some other thread is helping the help SplitPoint. */
  590.     bool hasHelperThread() const;
  591.  
  592. private:
  593.     ParallelData& pd;
  594.     std::vector<std::shared_ptr<SplitPoint>>& spVec;
  595.     std::vector<std::shared_ptr<SplitPoint>>& pending;
  596.     std::shared_ptr<SplitPoint> sp;
  597.     enum class State { EMPTY, CREATED, QUEUED } state;
  598. };
  599.  
  600. /** Dummy version of SplitPointHolder class. */
  601. struct DummySplitPointHolder {
  602.     DummySplitPointHolder(ParallelData& pd, std::vector<std::shared_ptr<SplitPoint>>& spVec,
  603.                           std::vector<std::shared_ptr<SplitPoint>>& pending) {}
  604.     void setSp(const std::shared_ptr<SplitPoint>& sp) {}
  605.     void addMove(int moveNo, const SplitPointMove& spMove) {}
  606.     void addToQueue() {}
  607.     int setOwnerCurrMove(int moveNo, int alpha) { return SearchConst::UNKNOWN_SCORE; }
  608.     bool isAllNode() const { return false; }
  609. };
  610.  
  611. template <bool smp> struct SplitPointTraits {
  612. };
  613. template<> struct SplitPointTraits<true> {
  614.     using SpHolder = SplitPointHolder;
  615. };
  616. template<> struct SplitPointTraits<false> {
  617.     using SpHolder = DummySplitPointHolder;
  618. };
  619.  
  620.  
  621. inline bool
  622. WorkerThread::threadRunning() const {
  623.     return thread != nullptr;
  624. }
  625.  
  626. inline int
  627. WorkerThread::getThreadNo() const {
  628.     return threadNo;
  629. }
  630.  
  631. inline double
  632. WorkerThread::getPUseful() const {
  633.     return pUseful;
  634. }
  635.  
  636. inline
  637. WorkQueue::WorkQueue(const FailHighInfo& fhInfo0, const DepthNpsInfo& npsInfo0)
  638.     : stopped(false), fhInfo(fhInfo0), npsInfo(npsInfo0) {
  639.     resetSplitDepth();
  640. }
  641.  
  642. inline bool
  643. WorkQueue::isStopped() const {
  644.     return stopped;
  645. }
  646.  
  647. inline void
  648. WorkQueue::resetSplitDepth() {
  649.     minSplitDepth = SearchConst::MIN_SMP_DEPTH;
  650.     nContended = 0;
  651.     nNonContended = 0;
  652. }
  653.  
  654. inline int
  655. WorkQueue::getMinSplitDepth() const {
  656.     return minSplitDepth;
  657. }
  658.  
  659. inline void
  660. WorkQueue::insertInQueue(const std::shared_ptr<SplitPoint>& sp) {
  661.     bool wasEmpty = queue.empty() || (queue.front()->getPrio() < 0);
  662.     queue.insert(sp, sp->getSpPrio(npsInfo));
  663.     sp->setInserted();
  664.     if (wasEmpty)
  665.         cv.notify_all();
  666. }
  667.  
  668. inline void
  669. WorkQueue::resetStat() {
  670.     for (auto& s : wqStat)
  671.         s.reset();
  672. }
  673.  
  674. inline TimeSampleStatistics&
  675. WorkQueue::getAddWorkStat(int th) {
  676.     assert(th < maxStatThreads);
  677.     return wqStat[th];
  678. }
  679.  
  680. inline TimeSampleStatistics&
  681. WorkQueue::getGetWorkStat(int th) {
  682.     assert(th < maxStatThreads);
  683.     return wqStat[maxStatThreads+th];
  684. }
  685.  
  686. inline void
  687. WorkQueue::printStats(std::ostream& os, int nThreads) {
  688.     for (int i = 0; i < nThreads; i++) {
  689.         os << "th:" << i << " add: ";
  690.         getAddWorkStat(i).printNs(os);
  691.         os << " get: ";
  692.         getGetWorkStat(i).printNs(os);
  693.         os << std::endl;
  694.     }
  695. }
  696.  
  697.  
  698. inline int
  699. FailHighInfo::getNodeType(int moveNo, bool allNode) const {
  700.     if (moveNo == 0)
  701.         return allNode ? 0 : 3;
  702.     else if (moveNo > 0)
  703.         return 1;
  704.     else
  705.         return 2;
  706. }
  707.  
  708. inline
  709. DepthNpsInfo::DepthNpsInfo() {
  710.     reset();
  711. }
  712.  
  713. inline
  714. DepthNpsInfo::NpsData::NpsData()
  715.     : nSearches(0), nodes(0), time(0) {
  716. }
  717.  
  718. inline void
  719. DepthNpsInfo::reset() {
  720.     std::lock_guard<std::mutex> L(mutex);
  721.     for (int i = 0; i < maxDepth; i++) {
  722.         npsData[i].nSearches = 0;
  723.         npsData[i].nodes = 0;
  724.         npsData[i].time = 0;
  725.     }
  726.     nps0 = 0;
  727.     nSearches = 0;
  728.     waitTime = 0;
  729. }
  730.  
  731. inline void
  732. DepthNpsInfo::setBaseNps(double nps) {
  733.     std::lock_guard<std::mutex> L(mutex);
  734.     nps0 = nps;
  735. }
  736.  
  737. inline void
  738. DepthNpsInfo::addData(int depth, U64 nodes, double wTime, double searchTime) {
  739.     if (depth >= maxDepth)
  740.         depth = maxDepth - 1;
  741.     std::lock_guard<std::mutex> L(mutex);
  742.     npsData[depth].nSearches++;
  743.     npsData[depth].nodes += nodes;
  744.     npsData[depth].time += searchTime;
  745.     nSearches++;
  746.     waitTime += wTime;
  747. }
  748.  
  749. inline double
  750. DepthNpsInfo::efficiency(int depth) const {
  751.     if (depth >= maxDepth)
  752.         depth = maxDepth - 1;
  753.     std::lock_guard<std::mutex> L(mutex);
  754.     return efficiencyInternal(depth);
  755. }
  756.  
  757. inline double
  758. DepthNpsInfo::efficiencyInternal(int depth) const {
  759.     if ((npsData[depth].time > 0) && (nps0 > 0)) {
  760.         U64 nodes = npsData[depth].nodes;
  761.         double time = npsData[depth].time;
  762.         const U32 ns = npsData[depth].nSearches;
  763.         if (nSearches > 0)
  764.             time += waitTime / nSearches * ns;
  765.         double nps = nodes / time;
  766.         double eff = nps / nps0;
  767.         if (eff > 1.0)
  768.             eff = 1.0;
  769.         return (eff * ns + 1 * 500) / (ns + 500);
  770.     } else
  771.         return 1.0;
  772. }
  773.  
  774. inline void
  775. WorkQueue::Lock::wait(std::condition_variable& cv) {
  776.     cv.wait(lock);
  777. }
  778.  
  779.  
  780. inline ParallelData::ParallelData(TranspositionTable& tt0)
  781.     : wq(fhInfo, npsInfo), t0Index(0), tt(tt0),
  782.       totalHelperNodes(0), helperTbHits(0) {
  783. }
  784.  
  785. inline int
  786. ParallelData::numHelperThreads() const {
  787.     return (int)threads.size();
  788. }
  789.  
  790. inline S64
  791. ParallelData::getNumSearchedNodes() const {
  792.     return totalHelperNodes;
  793. }
  794.  
  795. inline S64
  796. ParallelData::getTbHits() const {
  797.     return helperTbHits;
  798. }
  799.  
  800. inline void
  801. ParallelData::addSearchedNodes(S64 nNodes) {
  802.     totalHelperNodes += nNodes;
  803. }
  804.  
  805. inline void
  806. ParallelData::addTbHits(S64 nTbHits) {
  807.     helperTbHits += nTbHits;
  808. }
  809.  
  810. inline const WorkerThread&
  811. ParallelData::getHelperThread(int i) const {
  812.     return *threads[i];
  813. }
  814.  
  815.  
  816. inline bool
  817. SplitPoint::isCanceled() const {
  818.     return canceled;
  819. }
  820.  
  821. inline void
  822. SplitPoint::setSeqNo() {
  823.     seqNo = nextSeqNo++;
  824. }
  825.  
  826. inline std::shared_ptr<SplitPoint>
  827. SplitPoint::getParent() const {
  828.     return parent;
  829. }
  830.  
  831. inline const std::vector<std::weak_ptr<SplitPoint>>&
  832. SplitPoint::getChildren() const {
  833.     return children;
  834. }
  835.  
  836. inline U64
  837. SplitPoint::getSeqNo() const {
  838.     return seqNo;
  839. }
  840.  
  841. inline double
  842. SplitPoint::getPSpUseful() const {
  843.     return pSpUseful;
  844. }
  845.  
  846. inline double
  847. SplitPoint::getPNextMoveUseful() const {
  848.     return pNextMoveUseful;
  849. }
  850.  
  851. inline const History&
  852. SplitPoint::getHistory() const {
  853.     return ht;
  854. }
  855.  
  856. inline const KillerTable&
  857. SplitPoint::getKillerTable() const {
  858.     return kt;
  859. }
  860.  
  861. inline const SplitPointMove&
  862. SplitPoint::getSpMove(int moveNo) const {
  863.     return spMoves[moveNo];
  864. }
  865.  
  866. inline const SearchTreeInfo&
  867. SplitPoint::getSearchTreeInfo() const {
  868.     return searchTreeInfo;
  869. }
  870.  
  871. inline int
  872. SplitPoint::getAlpha() const {
  873.     return alpha;
  874. }
  875.  
  876. inline int
  877. SplitPoint::getBeta() const {
  878.     return beta;
  879. }
  880.  
  881. inline int
  882. SplitPoint::getPly() const {
  883.     return ply;
  884. }
  885.  
  886. inline int
  887. SplitPoint::getDepth() const {
  888.     return depth;
  889. }
  890.  
  891. inline void
  892. SplitPoint::returnMove(int moveNo) {
  893.     assert((moveNo >= 0) && (moveNo < (int)spMoves.size()));
  894.     SplitPointMove& spm = spMoves[moveNo];
  895.     spm.setSearching(false);
  896. }
  897.  
  898. inline int
  899. SplitPoint::setOwnerCurrMove(int moveNo, int newAlpha) {
  900.     assert((moveNo >= 0) && (moveNo < (int)spMoves.size()));
  901.     int score = spMoves[moveNo].getScore();
  902.     spMoves[moveNo].setCanceled(true);
  903.     currMoveNo = moveNo;
  904.     if (newAlpha > alpha)
  905.         alpha = newAlpha;
  906.     return score;
  907. }
  908.  
  909. inline void
  910. SplitPoint::cancel() {
  911.     canceled = true;
  912.     for (SplitPointMove& spMove : spMoves)
  913.         spMove.setCanceled(true);
  914. }
  915.  
  916. inline void
  917. SplitPoint::addChild(const std::weak_ptr<SplitPoint>& child) {
  918.     children.push_back(child);
  919. }
  920.  
  921. inline bool
  922. SplitPoint::isPvNode() const {
  923.     return isPV;
  924. }
  925.  
  926. inline int
  927. SplitPoint::getSpPrio(const DepthNpsInfo& npsInfo) const {
  928.     if (!hasUnStartedMove())
  929.         return -1;
  930.     return (int)(getPNextMoveUseful() * npsInfo.efficiency(getDepth()) * 1000);
  931. }
  932.  
  933. inline int
  934. SplitPoint::owningThread() const {
  935.     return threadNo;
  936. }
  937.  
  938. inline bool
  939. SplitPoint::wasInserted() const {
  940.     return inserted;
  941. }
  942.  
  943. inline void
  944. SplitPoint::setInserted() {
  945.     inserted = true;
  946. }
  947.  
  948. inline int
  949. SplitPoint::getParentMoveNo() const {
  950.     return parentMoveNo;
  951. }
  952.  
  953. inline int
  954. SplitPoint::getCurrMoveNo() const {
  955.     return currMoveNo;
  956. }
  957.  
  958.  
  959. inline
  960. SplitPointMove::SplitPointMove(const Move& move0, int lmr0, int depth0,
  961.                               int captSquare0, bool inCheck0)
  962.     : move(move0), lmr(lmr0), depth(depth0), captSquare(captSquare0),
  963.       inCheck(inCheck0), canceled(false), searching(false),
  964.       score(SearchConst::UNKNOWN_SCORE) {
  965. }
  966.  
  967. inline const Move&
  968. SplitPointMove::getMove() const {
  969.     return move;
  970. }
  971.  
  972. inline int
  973. SplitPointMove::getLMR() const {
  974.     return lmr;
  975. }
  976.  
  977. inline int
  978. SplitPointMove::getDepth() const {
  979.     return depth;
  980. }
  981.  
  982. inline int
  983. SplitPointMove::getRecaptureSquare() const {
  984.     return captSquare;
  985. }
  986.  
  987. inline bool
  988. SplitPointMove::getInCheck() const {
  989.     return inCheck;
  990. }
  991.  
  992. inline bool
  993. SplitPointMove::isCanceled() const {
  994.     return canceled;
  995. }
  996.  
  997. inline void
  998. SplitPointMove::setCanceled(bool value) {
  999.     canceled = value;
  1000. }
  1001.  
  1002. inline bool
  1003. SplitPointMove::isSearching() const {
  1004.     return searching;
  1005. }
  1006.  
  1007. inline void
  1008. SplitPointMove::setSearching(bool value) {
  1009.     searching = value;
  1010. }
  1011.  
  1012. inline void
  1013. SplitPointMove::setScore(int s) {
  1014.     score = s;
  1015. }
  1016.  
  1017. inline int
  1018. SplitPointMove::getScore() const {
  1019.     return score;
  1020. }
  1021.  
  1022.  
  1023. inline
  1024. SplitPointHolder::SplitPointHolder(ParallelData& pd0,
  1025.                                    std::vector<std::shared_ptr<SplitPoint>>& spVec0,
  1026.                                    std::vector<std::shared_ptr<SplitPoint>>& pending0)
  1027.     : pd(pd0), spVec(spVec0), pending(pending0),
  1028.       state(State::EMPTY) {
  1029. }
  1030.  
  1031. inline
  1032. SplitPointHolder::~SplitPointHolder() {
  1033.     if (state == State::QUEUED) {
  1034. //        log([&](std::ostream& os){os << "cancel seqNo:" << sp->getSeqNo();});
  1035.         if (sp->wasInserted())
  1036.             pd.wq.cancel(sp);
  1037.         else {
  1038.             if (pending.size() > 0) {
  1039.                 assert(pending[pending.size()-1] == sp);
  1040.                 pending.pop_back();
  1041.             }
  1042.         }
  1043.         assert(!spVec.empty());
  1044.         spVec.pop_back();
  1045.     }
  1046. }
  1047.  
  1048. inline void
  1049. SplitPointHolder::addMove(int moveNo, const SplitPointMove& spMove) {
  1050.     assert(state == State::CREATED);
  1051.     sp->addMove(moveNo, spMove);
  1052. }
  1053.  
  1054. inline int
  1055. SplitPointHolder::setOwnerCurrMove(int moveNo, int alpha) {
  1056. //    if (sp->hasHelperThread())
  1057. //        log([&](std::ostream& os){os << "seqNo:" << sp->getSeqNo() << " currMove:" << moveNo
  1058. //                                     << " a:" << alpha;});
  1059.     if (sp->wasInserted())
  1060.         return pd.wq.setOwnerCurrMove(sp, moveNo, alpha);
  1061.     else
  1062.         return sp->setOwnerCurrMove(moveNo, alpha);
  1063. }
  1064.  
  1065. inline U64
  1066. SplitPointHolder::getSeqNo() const {
  1067.     return sp->getSeqNo();
  1068. }
  1069.  
  1070. inline bool
  1071. SplitPointHolder::isAllNode() const {
  1072.     return sp->isAllNode();
  1073. }
  1074.  
  1075. inline bool
  1076. SplitPointHolder::hasHelperThread() const {
  1077.     return sp->hasHelperThread();
  1078. }
  1079.  
  1080. #endif /* PARALLEL_HPP_ */
  1081.