Subversion Repositories Games.Chess Giants

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
99 pmbaty 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_ */