Use only cumulativeNodes in RootMoveList
[stockfish] / src / search.cpp
1 /*
2   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3   Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4   Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad
5
6   Stockfish is free software: you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation, either version 3 of the License, or
9   (at your option) any later version.
10
11   Stockfish is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15
16   You should have received a copy of the GNU General Public License
17   along with this program.  If not, see <http://www.gnu.org/licenses/>.
18 */
19
20
21 ////
22 //// Includes
23 ////
24
25 #include <cassert>
26 #include <cmath>
27 #include <cstring>
28 #include <fstream>
29 #include <iostream>
30 #include <sstream>
31
32 #include "book.h"
33 #include "evaluate.h"
34 #include "history.h"
35 #include "misc.h"
36 #include "movegen.h"
37 #include "movepick.h"
38 #include "lock.h"
39 #include "san.h"
40 #include "search.h"
41 #include "timeman.h"
42 #include "thread.h"
43 #include "tt.h"
44 #include "ucioption.h"
45
46 using std::cout;
47 using std::endl;
48
49 ////
50 //// Local definitions
51 ////
52
53 namespace {
54
55   /// Types
56   enum NodeType { NonPV, PV };
57
58   // Set to true to force running with one thread.
59   // Used for debugging SMP code.
60   const bool FakeSplit = false;
61
62   // ThreadsManager class is used to handle all the threads related stuff in search,
63   // init, starting, parking and, the most important, launching a slave thread at a
64   // split point are what this class does. All the access to shared thread data is
65   // done through this class, so that we avoid using global variables instead.
66
67   class ThreadsManager {
68     /* As long as the single ThreadsManager object is defined as a global we don't
69        need to explicitly initialize to zero its data members because variables with
70        static storage duration are automatically set to zero before enter main()
71     */
72   public:
73     void init_threads();
74     void exit_threads();
75
76     int active_threads() const { return ActiveThreads; }
77     void set_active_threads(int newActiveThreads) { ActiveThreads = newActiveThreads; }
78     void incrementNodeCounter(int threadID) { threads[threadID].nodes++; }
79
80     void resetNodeCounters();
81     int64_t nodes_searched() const;
82     bool available_thread_exists(int master) const;
83     bool thread_is_available(int slave, int master) const;
84     bool thread_should_stop(int threadID) const;
85     void wake_sleeping_threads();
86     void put_threads_to_sleep();
87     void idle_loop(int threadID, SplitPoint* sp);
88
89     template <bool Fake>
90     void split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
91                Depth depth, Move threatMove, bool mateThreat, int* moveCount, MovePicker* mp, bool pvNode);
92
93   private:
94     friend void poll();
95
96     int ActiveThreads;
97     volatile bool AllThreadsShouldExit, AllThreadsShouldSleep;
98     Thread threads[MAX_THREADS];
99
100     Lock MPLock, WaitLock;
101
102 #if !defined(_MSC_VER)
103     pthread_cond_t WaitCond;
104 #else
105     HANDLE SitIdleEvent[MAX_THREADS];
106 #endif
107
108   };
109
110
111   // RootMove struct is used for moves at the root at the tree. For each
112   // root move, we store a score, a node count, and a PV (really a refutation
113   // in the case of moves which fail low).
114
115   struct RootMove {
116
117     RootMove() : mp_score(0), nodes(0) {}
118
119     // RootMove::operator<() is the comparison function used when
120     // sorting the moves. A move m1 is considered to be better
121     // than a move m2 if it has a higher score, or if the moves
122     // have equal score but m1 has the higher beta cut-off count.
123     bool operator<(const RootMove& m) const {
124
125         return score != m.score ? score < m.score : mp_score <= m.mp_score;
126     }
127
128     Move move;
129     Value score;
130     int mp_score;
131     int64_t nodes;
132     Move pv[PLY_MAX_PLUS_2];
133   };
134
135
136   // The RootMoveList class is essentially an array of RootMove objects, with
137   // a handful of methods for accessing the data in the individual moves.
138
139   class RootMoveList {
140
141   public:
142     RootMoveList(Position& pos, Move searchMoves[]);
143
144     int move_count() const { return count; }
145     Move get_move(int moveNum) const { return moves[moveNum].move; }
146     Value get_move_score(int moveNum) const { return moves[moveNum].score; }
147     void set_move_score(int moveNum, Value score) { moves[moveNum].score = score; }
148     Move get_move_pv(int moveNum, int i) const { return moves[moveNum].pv[i]; }
149     int64_t get_move_nodes(int moveNum) const { return moves[moveNum].nodes; }
150     void score_moves(const Position& pos);
151
152     void add_move_nodes(int moveNum, int64_t nodes) { moves[moveNum].nodes += nodes; }
153     void set_move_pv(int moveNum, const Move pv[]);
154     void sort();
155     void sort_multipv(int n);
156
157   private:
158     static const int MaxRootMoves = 500;
159     RootMove moves[MaxRootMoves];
160     int count;
161   };
162
163
164   // When formatting a move for std::cout we must know if we are in Chess960
165   // or not. To keep using the handy operator<<() on the move the trick is to
166   // embed this flag in the stream itself. Function-like named enum set960 is
167   // used as a custom manipulator and the stream internal general-purpose array,
168   // accessed through ios_base::iword(), is used to pass the flag to the move's
169   // operator<<() that will use it to properly format castling moves.
170   enum set960 {};
171
172   std::ostream& operator<< (std::ostream& os, const set960& m) {
173
174     os.iword(0) = int(m);
175     return os;
176   }
177
178
179   /// Adjustments
180
181   // Step 6. Razoring
182
183   // Maximum depth for razoring
184   const Depth RazorDepth = 4 * ONE_PLY;
185
186   // Dynamic razoring margin based on depth
187   inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
188
189   // Step 8. Null move search with verification search
190
191   // Null move margin. A null move search will not be done if the static
192   // evaluation of the position is more than NullMoveMargin below beta.
193   const Value NullMoveMargin = Value(0x200);
194
195   // Maximum depth for use of dynamic threat detection when null move fails low
196   const Depth ThreatDepth = 5 * ONE_PLY;
197
198   // Step 9. Internal iterative deepening
199
200   // Minimum depth for use of internal iterative deepening
201   const Depth IIDDepth[2] = { 8 * ONE_PLY /* non-PV */, 5 * ONE_PLY /* PV */};
202
203   // At Non-PV nodes we do an internal iterative deepening search
204   // when the static evaluation is bigger then beta - IIDMargin.
205   const Value IIDMargin = Value(0x100);
206
207   // Step 11. Decide the new search depth
208
209   // Extensions. Configurable UCI options
210   // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
211   Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
212   Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
213
214   // Minimum depth for use of singular extension
215   const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */};
216
217   // If the TT move is at least SingularExtensionMargin better then the
218   // remaining ones we will extend it.
219   const Value SingularExtensionMargin = Value(0x20);
220
221   // Step 12. Futility pruning
222
223   // Futility margin for quiescence search
224   const Value FutilityMarginQS = Value(0x80);
225
226   // Futility lookup tables (initialized at startup) and their getter functions
227   int32_t FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
228   int FutilityMoveCountArray[32]; // [depth]
229
230   inline Value futility_margin(Depth d, int mn) { return Value(d < 7 * ONE_PLY ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE); }
231   inline int futility_move_count(Depth d) { return d < 16 * ONE_PLY ? FutilityMoveCountArray[d] : 512; }
232
233   // Step 14. Reduced search
234
235   // Reduction lookup tables (initialized at startup) and their getter functions
236   int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
237
238   template <NodeType PV>
239   inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
240
241   // Common adjustments
242
243   // Search depth at iteration 1
244   const Depth InitialDepth = ONE_PLY;
245
246   // Easy move margin. An easy move candidate must be at least this much
247   // better than the second best move.
248   const Value EasyMoveMargin = Value(0x200);
249
250
251   /// Global variables
252
253   // Iteration counter
254   int Iteration;
255
256   // Scores and number of times the best move changed for each iteration
257   Value ValueByIteration[PLY_MAX_PLUS_2];
258   int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
259
260   // Search window management
261   int AspirationDelta;
262
263   // MultiPV mode
264   int MultiPV;
265
266   // Time managment variables
267   int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
268   bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
269   bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
270   TimeManager TimeMgr;
271
272   // Log file
273   bool UseLogFile;
274   std::ofstream LogFile;
275
276   // Multi-threads related variables
277   Depth MinimumSplitDepth;
278   int MaxThreadsPerSplitPoint;
279   ThreadsManager ThreadsMgr;
280
281   // Node counters, used only by thread[0] but try to keep in different cache
282   // lines (64 bytes each) from the heavy multi-thread read accessed variables.
283   int NodesSincePoll;
284   int NodesBetweenPolls = 30000;
285
286   // History table
287   History H;
288
289   /// Local functions
290
291   Value id_loop(const Position& pos, Move searchMoves[]);
292   Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
293
294   template <NodeType PvNode>
295   Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
296
297   template <NodeType PvNode>
298   Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
299
300   template <NodeType PvNode>
301   void sp_search(SplitPoint* sp, int threadID);
302
303   template <NodeType PvNode>
304   Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
305
306   bool connected_moves(const Position& pos, Move m1, Move m2);
307   bool value_is_mate(Value value);
308   Value value_to_tt(Value v, int ply);
309   Value value_from_tt(Value v, int ply);
310   bool move_is_killer(Move m, SearchStack* ss);
311   bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
312   bool connected_threat(const Position& pos, Move m, Move threat);
313   Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
314   void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
315   void update_killers(Move m, SearchStack* ss);
316   void update_gains(const Position& pos, Move move, Value before, Value after);
317
318   int current_search_time();
319   std::string value_to_uci(Value v);
320   int nps();
321   void poll();
322   void ponderhit();
323   void wait_for_stop_or_ponderhit();
324   void init_ss_array(SearchStack* ss, int size);
325   void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value);
326   void insert_pv_in_tt(const Position& pos, Move pv[]);
327   void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]);
328
329 #if !defined(_MSC_VER)
330   void *init_thread(void *threadID);
331 #else
332   DWORD WINAPI init_thread(LPVOID threadID);
333 #endif
334
335 }
336
337
338 ////
339 //// Functions
340 ////
341
342 /// init_threads(), exit_threads() and nodes_searched() are helpers to
343 /// give accessibility to some TM methods from outside of current file.
344
345 void init_threads() { ThreadsMgr.init_threads(); }
346 void exit_threads() { ThreadsMgr.exit_threads(); }
347 int64_t nodes_searched() { return ThreadsMgr.nodes_searched(); }
348
349
350 /// init_search() is called during startup. It initializes various lookup tables
351
352 void init_search() {
353
354   int d;  // depth (ONE_PLY == 2)
355   int hd; // half depth (ONE_PLY == 1)
356   int mc; // moveCount
357
358   // Init reductions array
359   for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
360   {
361       double    pvRed = 0.33 + log(double(hd)) * log(double(mc)) / 4.5;
362       double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
363       ReductionMatrix[PV][hd][mc]    = (int8_t) (   pvRed >= 1.0 ? floor(   pvRed * int(ONE_PLY)) : 0);
364       ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0);
365   }
366
367   // Init futility margins array
368   for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
369       FutilityMarginsMatrix[d][mc] = 112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45;
370
371   // Init futility move count array
372   for (d = 0; d < 32; d++)
373       FutilityMoveCountArray[d] = 3 + (1 << (3 * d / 8));
374 }
375
376
377 /// perft() is our utility to verify move generation is bug free. All the legal
378 /// moves up to given depth are generated and counted and the sum returned.
379
380 int perft(Position& pos, Depth depth)
381 {
382     MoveStack mlist[256];
383     StateInfo st;
384     Move m;
385     int sum = 0;
386
387     // Generate all legal moves
388     MoveStack* last = generate_moves(pos, mlist);
389
390     // If we are at the last ply we don't need to do and undo
391     // the moves, just to count them.
392     if (depth <= ONE_PLY)
393         return int(last - mlist);
394
395     // Loop through all legal moves
396     CheckInfo ci(pos);
397     for (MoveStack* cur = mlist; cur != last; cur++)
398     {
399         m = cur->move;
400         pos.do_move(m, st, ci, pos.move_is_check(m, ci));
401         sum += perft(pos, depth - ONE_PLY);
402         pos.undo_move(m);
403     }
404     return sum;
405 }
406
407
408 /// think() is the external interface to Stockfish's search, and is called when
409 /// the program receives the UCI 'go' command. It initializes various
410 /// search-related global variables, and calls root_search(). It returns false
411 /// when a quit command is received during the search.
412
413 bool think(const Position& pos, bool infinite, bool ponder, int time[], int increment[],
414            int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) {
415
416   // Initialize global search variables
417   StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
418   NodesSincePoll = 0;
419   ThreadsMgr.resetNodeCounters();
420   SearchStartTime = get_system_time();
421   ExactMaxTime = maxTime;
422   MaxDepth = maxDepth;
423   MaxNodes = maxNodes;
424   InfiniteSearch = infinite;
425   PonderSearch = ponder;
426   UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
427
428   // Look for a book move, only during games, not tests
429   if (UseTimeManagement && get_option_value_bool("OwnBook"))
430   {
431       if (get_option_value_string("Book File") != OpeningBook.file_name())
432           OpeningBook.open(get_option_value_string("Book File"));
433
434       Move bookMove = OpeningBook.get_move(pos, get_option_value_bool("Best Book Move"));
435       if (bookMove != MOVE_NONE)
436       {
437           if (PonderSearch)
438               wait_for_stop_or_ponderhit();
439
440           cout << "bestmove " << bookMove << endl;
441           return true;
442       }
443   }
444
445   // Read UCI option values
446   TT.set_size(get_option_value_int("Hash"));
447   if (button_was_pressed("Clear Hash"))
448       TT.clear();
449
450   CheckExtension[1]         = Depth(get_option_value_int("Check Extension (PV nodes)"));
451   CheckExtension[0]         = Depth(get_option_value_int("Check Extension (non-PV nodes)"));
452   SingleEvasionExtension[1] = Depth(get_option_value_int("Single Evasion Extension (PV nodes)"));
453   SingleEvasionExtension[0] = Depth(get_option_value_int("Single Evasion Extension (non-PV nodes)"));
454   PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)"));
455   PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
456   PassedPawnExtension[1]    = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
457   PassedPawnExtension[0]    = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
458   PawnEndgameExtension[1]   = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
459   PawnEndgameExtension[0]   = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)"));
460   MateThreatExtension[1]    = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
461   MateThreatExtension[0]    = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
462
463   MinimumSplitDepth       = get_option_value_int("Minimum Split Depth") * ONE_PLY;
464   MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point");
465   MultiPV                 = get_option_value_int("MultiPV");
466   UseLogFile              = get_option_value_bool("Use Search Log");
467
468   if (UseLogFile)
469       LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app);
470
471   read_weights(pos.side_to_move());
472
473   // Set the number of active threads
474   int newActiveThreads = get_option_value_int("Threads");
475   if (newActiveThreads != ThreadsMgr.active_threads())
476   {
477       ThreadsMgr.set_active_threads(newActiveThreads);
478       init_eval(ThreadsMgr.active_threads());
479   }
480
481   // Wake up sleeping threads
482   ThreadsMgr.wake_sleeping_threads();
483
484   // Set thinking time
485   int myTime = time[pos.side_to_move()];
486   int myIncrement = increment[pos.side_to_move()];
487   if (UseTimeManagement)
488       TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter());
489
490   // Set best NodesBetweenPolls interval to avoid lagging under
491   // heavy time pressure.
492   if (MaxNodes)
493       NodesBetweenPolls = Min(MaxNodes, 30000);
494   else if (myTime && myTime < 1000)
495       NodesBetweenPolls = 1000;
496   else if (myTime && myTime < 5000)
497       NodesBetweenPolls = 5000;
498   else
499       NodesBetweenPolls = 30000;
500
501   // Write search information to log file
502   if (UseLogFile)
503       LogFile << "Searching: " << pos.to_fen() << endl
504               << "infinite: "  << infinite
505               << " ponder: "   << ponder
506               << " time: "     << myTime
507               << " increment: " << myIncrement
508               << " moves to go: " << movesToGo << endl;
509
510   // We're ready to start thinking. Call the iterative deepening loop function
511   id_loop(pos, searchMoves);
512
513   if (UseLogFile)
514       LogFile.close();
515
516   ThreadsMgr.put_threads_to_sleep();
517
518   return !Quit;
519 }
520
521
522 namespace {
523
524   // id_loop() is the main iterative deepening loop. It calls root_search
525   // repeatedly with increasing depth until the allocated thinking time has
526   // been consumed, the user stops the search, or the maximum search depth is
527   // reached.
528
529   Value id_loop(const Position& pos, Move searchMoves[]) {
530
531     Position p(pos, pos.thread());
532     SearchStack ss[PLY_MAX_PLUS_2];
533     Move pv[PLY_MAX_PLUS_2];
534     Move EasyMove = MOVE_NONE;
535     Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
536
537     // Moves to search are verified, copied, scored and sorted
538     RootMoveList rml(p, searchMoves);
539
540     // Handle special case of searching on a mate/stale position
541     if (rml.move_count() == 0)
542     {
543         if (PonderSearch)
544             wait_for_stop_or_ponderhit();
545
546         return pos.is_check() ? -VALUE_MATE : VALUE_DRAW;
547     }
548
549     // Print RootMoveList startup scoring to the standard output,
550     // so to output information also for iteration 1.
551     cout << set960(p.is_chess960()) // Is enough to set once at the beginning
552          << "info depth " << 1
553          << "\ninfo depth " << 1
554          << " score " << value_to_uci(rml.get_move_score(0))
555          << " time " << current_search_time()
556          << " nodes " << ThreadsMgr.nodes_searched()
557          << " nps " << nps()
558          << " pv " << rml.get_move(0) << "\n";
559
560     // Initialize
561     TT.new_search();
562     H.clear();
563     init_ss_array(ss, PLY_MAX_PLUS_2);
564     pv[0] = pv[1] = MOVE_NONE;
565     ValueByIteration[1] = rml.get_move_score(0);
566     Iteration = 1;
567
568     // Is one move significantly better than others after initial scoring ?
569     if (   rml.move_count() == 1
570         || rml.get_move_score(0) > rml.get_move_score(1) + EasyMoveMargin)
571         EasyMove = rml.get_move(0);
572
573     // Iterative deepening loop
574     while (Iteration < PLY_MAX)
575     {
576         // Initialize iteration
577         Iteration++;
578         BestMoveChangesByIteration[Iteration] = 0;
579
580         cout << "info depth " << Iteration << endl;
581
582         // Calculate dynamic aspiration window based on previous iterations
583         if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
584         {
585             int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
586             int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
587
588             AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
589             AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
590
591             alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
592             beta  = Min(ValueByIteration[Iteration - 1] + AspirationDelta,  VALUE_INFINITE);
593         }
594
595         // Search to the current depth, rml is updated and sorted, alpha and beta could change
596         value = root_search(p, ss, pv, rml, &alpha, &beta);
597
598         // Write PV to transposition table, in case the relevant entries have
599         // been overwritten during the search.
600         insert_pv_in_tt(p, pv);
601
602         if (AbortSearch)
603             break; // Value cannot be trusted. Break out immediately!
604
605         //Save info about search result
606         ValueByIteration[Iteration] = value;
607
608         // Drop the easy move if differs from the new best move
609         if (pv[0] != EasyMove)
610             EasyMove = MOVE_NONE;
611
612         if (UseTimeManagement)
613         {
614             // Time to stop?
615             bool stopSearch = false;
616
617             // Stop search early if there is only a single legal move,
618             // we search up to Iteration 6 anyway to get a proper score.
619             if (Iteration >= 6 && rml.move_count() == 1)
620                 stopSearch = true;
621
622             // Stop search early when the last two iterations returned a mate score
623             if (  Iteration >= 6
624                 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
625                 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
626                 stopSearch = true;
627
628             // Stop search early if one move seems to be much better than the others
629             int64_t nodes = ThreadsMgr.nodes_searched();
630             if (   Iteration >= 8
631                 && EasyMove == pv[0]
632                 && (  (   rml.get_move_nodes(0) > (nodes * 85) / 100
633                        && current_search_time() > TimeMgr.available_time() / 16)
634                     ||(   rml.get_move_nodes(0) > (nodes * 98) / 100
635                        && current_search_time() > TimeMgr.available_time() / 32)))
636                 stopSearch = true;
637
638             // Add some extra time if the best move has changed during the last two iterations
639             if (Iteration > 5 && Iteration <= 50)
640                 TimeMgr.pv_unstability(BestMoveChangesByIteration[Iteration],
641                                        BestMoveChangesByIteration[Iteration-1]);
642
643             // Stop search if most of MaxSearchTime is consumed at the end of the
644             // iteration. We probably don't have enough time to search the first
645             // move at the next iteration anyway.
646             if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
647                 stopSearch = true;
648
649             if (stopSearch)
650             {
651                 if (PonderSearch)
652                     StopOnPonderhit = true;
653                 else
654                     break;
655             }
656         }
657
658         if (MaxDepth && Iteration >= MaxDepth)
659             break;
660     }
661
662     // If we are pondering or in infinite search, we shouldn't print the
663     // best move before we are told to do so.
664     if (!AbortSearch && (PonderSearch || InfiniteSearch))
665         wait_for_stop_or_ponderhit();
666     else
667         // Print final search statistics
668         cout << "info nodes " << ThreadsMgr.nodes_searched()
669              << " nps " << nps()
670              << " time " << current_search_time() << endl;
671
672     // Print the best move and the ponder move to the standard output
673     if (pv[0] == MOVE_NONE)
674     {
675         pv[0] = rml.get_move(0);
676         pv[1] = MOVE_NONE;
677     }
678
679     assert(pv[0] != MOVE_NONE);
680
681     cout << "bestmove " << pv[0];
682
683     if (pv[1] != MOVE_NONE)
684         cout << " ponder " << pv[1];
685
686     cout << endl;
687
688     if (UseLogFile)
689     {
690         if (dbg_show_mean)
691             dbg_print_mean(LogFile);
692
693         if (dbg_show_hit_rate)
694             dbg_print_hit_rate(LogFile);
695
696         LogFile << "\nNodes: " << ThreadsMgr.nodes_searched()
697                 << "\nNodes/second: " << nps()
698                 << "\nBest move: " << move_to_san(p, pv[0]);
699
700         StateInfo st;
701         p.do_move(pv[0], st);
702         LogFile << "\nPonder move: "
703                 << move_to_san(p, pv[1]) // Works also with MOVE_NONE
704                 << endl;
705     }
706     return rml.get_move_score(0);
707   }
708
709
710   // root_search() is the function which searches the root node. It is
711   // similar to search_pv except that it uses a different move ordering
712   // scheme, prints some information to the standard output and handles
713   // the fail low/high loops.
714
715   Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
716
717     Value margins[2];
718     StateInfo st;
719     CheckInfo ci(pos);
720     int64_t nodes;
721     Move move;
722     Depth depth, ext, newDepth;
723     Value value, alpha, beta;
724     bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
725     int researchCountFH, researchCountFL;
726
727     researchCountFH = researchCountFL = 0;
728     alpha = *alphaPtr;
729     beta = *betaPtr;
730     isCheck = pos.is_check();
731     depth = (Iteration - 2) * ONE_PLY + InitialDepth;
732
733     // Step 1. Initialize node (polling is omitted at root)
734     ss->currentMove = ss->bestMove = MOVE_NONE;
735
736     // Step 2. Check for aborted search (omitted at root)
737     // Step 3. Mate distance pruning (omitted at root)
738     // Step 4. Transposition table lookup (omitted at root)
739
740     // Step 5. Evaluate the position statically
741     // At root we do this only to get reference value for child nodes
742     ss->eval = isCheck ? VALUE_NONE : evaluate(pos, margins);
743
744     // Step 6. Razoring (omitted at root)
745     // Step 7. Static null move pruning (omitted at root)
746     // Step 8. Null move search with verification search (omitted at root)
747     // Step 9. Internal iterative deepening (omitted at root)
748
749     // Step extra. Fail low loop
750     // We start with small aspiration window and in case of fail low, we research
751     // with bigger window until we are not failing low anymore.
752     while (1)
753     {
754         // Sort the moves before to (re)search
755         rml.score_moves(pos);
756         rml.sort();
757
758         // Step 10. Loop through all moves in the root move list
759         for (int i = 0; i <  rml.move_count() && !AbortSearch; i++)
760         {
761             // This is used by time management
762             FirstRootMove = (i == 0);
763
764             // Save the current node count before the move is searched
765             nodes = ThreadsMgr.nodes_searched();
766
767             // Pick the next root move, and print the move and the move number to
768             // the standard output.
769             move = ss->currentMove = rml.get_move(i);
770
771             if (current_search_time() >= 1000)
772                 cout << "info currmove " << move
773                      << " currmovenumber " << i + 1 << endl;
774
775             moveIsCheck = pos.move_is_check(move);
776             captureOrPromotion = pos.move_is_capture_or_promotion(move);
777
778             // Step 11. Decide the new search depth
779             ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
780             newDepth = depth + ext;
781
782             // Step 12. Futility pruning (omitted at root)
783
784             // Step extra. Fail high loop
785             // If move fails high, we research with bigger window until we are not failing
786             // high anymore.
787             value = - VALUE_INFINITE;
788
789             while (1)
790             {
791                 // Step 13. Make the move
792                 pos.do_move(move, st, ci, moveIsCheck);
793
794                 // Step extra. pv search
795                 // We do pv search for first moves (i < MultiPV)
796                 // and for fail high research (value > alpha)
797                 if (i < MultiPV || value > alpha)
798                 {
799                     // Aspiration window is disabled in multi-pv case
800                     if (MultiPV > 1)
801                         alpha = -VALUE_INFINITE;
802
803                     // Full depth PV search, done on first move or after a fail high
804                     value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
805                 }
806                 else
807                 {
808                     // Step 14. Reduced search
809                     // if the move fails high will be re-searched at full depth
810                     bool doFullDepthSearch = true;
811
812                     if (    depth >= 3 * ONE_PLY
813                         && !dangerous
814                         && !captureOrPromotion
815                         && !move_is_castle(move))
816                     {
817                         ss->reduction = reduction<PV>(depth, i - MultiPV + 2);
818                         if (ss->reduction)
819                         {
820                             assert(newDepth-ss->reduction >= ONE_PLY);
821
822                             // Reduced depth non-pv search using alpha as upperbound
823                             value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
824                             doFullDepthSearch = (value > alpha);
825                         }
826
827                         // The move failed high, but if reduction is very big we could
828                         // face a false positive, retry with a less aggressive reduction,
829                         // if the move fails high again then go with full depth search.
830                         if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
831                         {
832                             assert(newDepth - ONE_PLY >= ONE_PLY);
833
834                             ss->reduction = ONE_PLY;
835                             value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
836                             doFullDepthSearch = (value > alpha);
837                         }
838                         ss->reduction = DEPTH_ZERO; // Restore original reduction
839                     }
840
841                     // Step 15. Full depth search
842                     if (doFullDepthSearch)
843                     {
844                         // Full depth non-pv search using alpha as upperbound
845                         value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, 1);
846
847                         // If we are above alpha then research at same depth but as PV
848                         // to get a correct score or eventually a fail high above beta.
849                         if (value > alpha)
850                             value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
851                     }
852                 }
853
854                 // Step 16. Undo move
855                 pos.undo_move(move);
856
857                 // Can we exit fail high loop ?
858                 if (AbortSearch || value < beta)
859                     break;
860
861                 // We are failing high and going to do a research. It's important to update
862                 // the score before research in case we run out of time while researching.
863                 rml.set_move_score(i, value);
864                 ss->bestMove = move;
865                 extract_pv_from_tt(pos, move, pv);
866                 rml.set_move_pv(i, pv);
867
868                 // Print information to the standard output
869                 print_pv_info(pos, pv, alpha, beta, value);
870
871                 // Prepare for a research after a fail high, each time with a wider window
872                 *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
873                 researchCountFH++;
874
875             } // End of fail high loop
876
877             // Finished searching the move. If AbortSearch is true, the search
878             // was aborted because the user interrupted the search or because we
879             // ran out of time. In this case, the return value of the search cannot
880             // be trusted, and we break out of the loop without updating the best
881             // move and/or PV.
882             if (AbortSearch)
883                 break;
884
885             // Remember searched nodes counts for this move
886             rml.add_move_nodes(i, ThreadsMgr.nodes_searched() - nodes);
887
888             assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
889             assert(value < beta);
890
891             // Step 17. Check for new best move
892             if (value <= alpha && i >= MultiPV)
893                 rml.set_move_score(i, -VALUE_INFINITE);
894             else
895             {
896                 // PV move or new best move!
897
898                 // Update PV
899                 rml.set_move_score(i, value);
900                 ss->bestMove = move;
901                 extract_pv_from_tt(pos, move, pv);
902                 rml.set_move_pv(i, pv);
903
904                 if (MultiPV == 1)
905                 {
906                     // We record how often the best move has been changed in each
907                     // iteration. This information is used for time managment: When
908                     // the best move changes frequently, we allocate some more time.
909                     if (i > 0)
910                         BestMoveChangesByIteration[Iteration]++;
911
912                     // Print information to the standard output
913                     print_pv_info(pos, pv, alpha, beta, value);
914
915                     // Raise alpha to setup proper non-pv search upper bound
916                     if (value > alpha)
917                         alpha = value;
918                 }
919                 else // MultiPV > 1
920                 {
921                     rml.sort_multipv(i);
922                     for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
923                     {
924                         cout << "info multipv " << j + 1
925                              << " score " << value_to_uci(rml.get_move_score(j))
926                              << " depth " << (j <= i ? Iteration : Iteration - 1)
927                              << " time " << current_search_time()
928                              << " nodes " << ThreadsMgr.nodes_searched()
929                              << " nps " << nps()
930                              << " pv ";
931
932                         for (int k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
933                             cout << rml.get_move_pv(j, k) << " ";
934
935                         cout << endl;
936                     }
937                     alpha = rml.get_move_score(Min(i, MultiPV - 1));
938                 }
939             } // PV move or new best move
940
941             assert(alpha >= *alphaPtr);
942
943             AspirationFailLow = (alpha == *alphaPtr);
944
945             if (AspirationFailLow && StopOnPonderhit)
946                 StopOnPonderhit = false;
947         }
948
949         // Can we exit fail low loop ?
950         if (AbortSearch || !AspirationFailLow)
951             break;
952
953         // Prepare for a research after a fail low, each time with a wider window
954         *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
955         researchCountFL++;
956
957     } // Fail low loop
958
959     // Sort the moves before to return
960     rml.sort();
961
962     return alpha;
963   }
964
965
966   // search<>() is the main search function for both PV and non-PV nodes
967
968   template <NodeType PvNode>
969   Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
970
971     assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
972     assert(beta > alpha && beta <= VALUE_INFINITE);
973     assert(PvNode || alpha == beta - 1);
974     assert(ply > 0 && ply < PLY_MAX);
975     assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
976
977     Move movesSearched[256];
978     Value margins[2];
979     StateInfo st;
980     const TTEntry *tte;
981     Key posKey;
982     Move ttMove, move, excludedMove, threatMove;
983     Depth ext, newDepth;
984     Value bestValue, value, oldAlpha;
985     Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
986     bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
987     bool mateThreat = false;
988     int moveCount = 0;
989     int threadID = pos.thread();
990     refinedValue = bestValue = value = -VALUE_INFINITE;
991     oldAlpha = alpha;
992
993     // Step 1. Initialize node and poll. Polling can abort search
994     ThreadsMgr.incrementNodeCounter(threadID);
995     ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
996     (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
997
998     if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
999     {
1000         NodesSincePoll = 0;
1001         poll();
1002     }
1003
1004     // Step 2. Check for aborted search and immediate draw
1005     if (AbortSearch || ThreadsMgr.thread_should_stop(threadID))
1006         return VALUE_ZERO;
1007
1008     if (pos.is_draw() || ply >= PLY_MAX - 1)
1009         return VALUE_DRAW;
1010
1011     // Step 3. Mate distance pruning
1012     alpha = Max(value_mated_in(ply), alpha);
1013     beta = Min(value_mate_in(ply+1), beta);
1014     if (alpha >= beta)
1015         return alpha;
1016
1017     // Step 4. Transposition table lookup
1018
1019     // We don't want the score of a partial search to overwrite a previous full search
1020     // TT value, so we use a different position key in case of an excluded move exists.
1021     excludedMove = ss->excludedMove;
1022     posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1023
1024     tte = TT.retrieve(posKey);
1025     ttMove = (tte ? tte->move() : MOVE_NONE);
1026
1027     // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1028     // This is to avoid problems in the following areas:
1029     //
1030     // * Repetition draw detection
1031     // * Fifty move rule detection
1032     // * Searching for a mate
1033     // * Printing of full PV line
1034
1035     if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1036     {
1037         // Refresh tte entry to avoid aging
1038         TT.store(posKey, tte->value(), tte->type(), tte->depth(), ttMove, tte->static_value(), tte->static_value_margin());
1039
1040         ss->bestMove = ttMove; // Can be MOVE_NONE
1041         return value_from_tt(tte->value(), ply);
1042     }
1043
1044     // Step 5. Evaluate the position statically and
1045     // update gain statistics of parent move.
1046     isCheck = pos.is_check();
1047     if (isCheck)
1048         ss->eval = VALUE_NONE;
1049     else if (tte)
1050     {
1051         assert(tte->static_value() != VALUE_NONE);
1052
1053         ss->eval = tte->static_value();
1054         margins[pos.side_to_move()] = tte->static_value_margin();
1055         refinedValue = refine_eval(tte, ss->eval, ply);
1056     }
1057     else
1058     {
1059         refinedValue = ss->eval = evaluate(pos, margins);
1060         TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, margins[pos.side_to_move()]);
1061     }
1062
1063     // Save gain for the parent non-capture move
1064     update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1065
1066     // Step 6. Razoring (is omitted in PV nodes)
1067     if (   !PvNode
1068         &&  depth < RazorDepth
1069         && !isCheck
1070         &&  refinedValue < beta - razor_margin(depth)
1071         &&  ttMove == MOVE_NONE
1072         &&  (ss-1)->currentMove != MOVE_NULL
1073         && !value_is_mate(beta)
1074         && !pos.has_pawn_on_7th(pos.side_to_move()))
1075     {
1076         Value rbeta = beta - razor_margin(depth);
1077         Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply);
1078         if (v < rbeta)
1079             // Logically we should return (v + razor_margin(depth)), but
1080             // surprisingly this did slightly weaker in tests.
1081             return v;
1082     }
1083
1084     // Step 7. Static null move pruning (is omitted in PV nodes)
1085     // We're betting that the opponent doesn't have a move that will reduce
1086     // the score by more than futility_margin(depth) if we do a null move.
1087     if (   !PvNode
1088         && !ss->skipNullMove
1089         &&  depth < RazorDepth
1090         && !isCheck
1091         &&  refinedValue >= beta + futility_margin(depth, 0)
1092         && !value_is_mate(beta)
1093         &&  pos.non_pawn_material(pos.side_to_move()))
1094         return refinedValue - futility_margin(depth, 0);
1095
1096     // Step 8. Null move search with verification search (is omitted in PV nodes)
1097     // When we jump directly to qsearch() we do a null move only if static value is
1098     // at least beta. Otherwise we do a null move if static value is not more than
1099     // NullMoveMargin under beta.
1100     if (   !PvNode
1101         && !ss->skipNullMove
1102         &&  depth > ONE_PLY
1103         && !isCheck
1104         &&  refinedValue >= beta - (depth >= 4 * ONE_PLY ? NullMoveMargin : 0)
1105         && !value_is_mate(beta)
1106         &&  pos.non_pawn_material(pos.side_to_move()))
1107     {
1108         ss->currentMove = MOVE_NULL;
1109
1110         // Null move dynamic reduction based on depth
1111         int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
1112
1113         // Null move dynamic reduction based on value
1114         if (refinedValue - beta > PawnValueMidgame)
1115             R++;
1116
1117         pos.do_null_move(st);
1118         (ss+1)->skipNullMove = true;
1119
1120         nullValue = depth-R*ONE_PLY < ONE_PLY ? -qsearch<NonPV>(pos, ss+1, -beta, -alpha, DEPTH_ZERO, ply+1)
1121                                               : - search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1);
1122         (ss+1)->skipNullMove = false;
1123         pos.undo_null_move();
1124
1125         if (nullValue >= beta)
1126         {
1127             // Do not return unproven mate scores
1128             if (nullValue >= value_mate_in(PLY_MAX))
1129                 nullValue = beta;
1130
1131             if (depth < 6 * ONE_PLY)
1132                 return nullValue;
1133
1134             // Do verification search at high depths
1135             ss->skipNullMove = true;
1136             Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY, ply);
1137             ss->skipNullMove = false;
1138
1139             if (v >= beta)
1140                 return nullValue;
1141         }
1142         else
1143         {
1144             // The null move failed low, which means that we may be faced with
1145             // some kind of threat. If the previous move was reduced, check if
1146             // the move that refuted the null move was somehow connected to the
1147             // move which was reduced. If a connection is found, return a fail
1148             // low score (which will cause the reduced move to fail high in the
1149             // parent node, which will trigger a re-search with full depth).
1150             if (nullValue == value_mated_in(ply + 2))
1151                 mateThreat = true;
1152
1153             threatMove = (ss+1)->bestMove;
1154             if (   depth < ThreatDepth
1155                 && (ss-1)->reduction
1156                 && connected_moves(pos, (ss-1)->currentMove, threatMove))
1157                 return beta - 1;
1158         }
1159     }
1160
1161     // Step 9. Internal iterative deepening
1162     if (    depth >= IIDDepth[PvNode]
1163         &&  ttMove == MOVE_NONE
1164         && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
1165     {
1166         Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
1167
1168         ss->skipNullMove = true;
1169         search<PvNode>(pos, ss, alpha, beta, d, ply);
1170         ss->skipNullMove = false;
1171
1172         ttMove = ss->bestMove;
1173         tte = TT.retrieve(posKey);
1174     }
1175
1176     // Expensive mate threat detection (only for PV nodes)
1177     if (PvNode)
1178         mateThreat = pos.has_mate_threat();
1179
1180     // Initialize a MovePicker object for the current position
1181     MovePicker mp = MovePicker(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
1182     CheckInfo ci(pos);
1183     ss->bestMove = MOVE_NONE;
1184     singleEvasion = isCheck && mp.number_of_evasions() == 1;
1185     futilityBase = ss->eval + margins[pos.side_to_move()];
1186     singularExtensionNode =   depth >= SingularExtensionDepth[PvNode]
1187                            && tte
1188                            && tte->move()
1189                            && !excludedMove // Do not allow recursive singular extension search
1190                            && (tte->type() & VALUE_TYPE_LOWER)
1191                            && tte->depth() >= depth - 3 * ONE_PLY;
1192
1193     // Step 10. Loop through moves
1194     // Loop through all legal moves until no moves remain or a beta cutoff occurs
1195     while (   bestValue < beta
1196            && (move = mp.get_next_move()) != MOVE_NONE
1197            && !ThreadsMgr.thread_should_stop(threadID))
1198     {
1199       assert(move_is_ok(move));
1200
1201       if (move == excludedMove)
1202           continue;
1203
1204       moveIsCheck = pos.move_is_check(move, ci);
1205       captureOrPromotion = pos.move_is_capture_or_promotion(move);
1206
1207       // Step 11. Decide the new search depth
1208       ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1209
1210       // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s),
1211       // and just one fails high on (alpha, beta), then that move is singular and should be extended.
1212       // To verify this we do a reduced search on all the other moves but the ttMove, if result is
1213       // lower then ttValue minus a margin then we extend ttMove.
1214       if (   singularExtensionNode
1215           && move == tte->move()
1216           && ext < ONE_PLY)
1217       {
1218           Value ttValue = value_from_tt(tte->value(), ply);
1219
1220           if (abs(ttValue) < VALUE_KNOWN_WIN)
1221           {
1222               Value b = ttValue - SingularExtensionMargin;
1223               ss->excludedMove = move;
1224               ss->skipNullMove = true;
1225               Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
1226               ss->skipNullMove = false;
1227               ss->excludedMove = MOVE_NONE;
1228               ss->bestMove = MOVE_NONE;
1229               if (v < b)
1230                   ext = ONE_PLY;
1231           }
1232       }
1233
1234       newDepth = depth - ONE_PLY + ext;
1235
1236       // Update current move (this must be done after singular extension search)
1237       movesSearched[moveCount++] = ss->currentMove = move;
1238
1239       // Step 12. Futility pruning (is omitted in PV nodes)
1240       if (   !PvNode
1241           && !captureOrPromotion
1242           && !isCheck
1243           && !dangerous
1244           &&  move != ttMove
1245           && !move_is_castle(move))
1246       {
1247           // Move count based pruning
1248           if (   moveCount >= futility_move_count(depth)
1249               && !(threatMove && connected_threat(pos, move, threatMove))
1250               && bestValue > value_mated_in(PLY_MAX))
1251               continue;
1252
1253           // Value based pruning
1254           // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
1255           // but fixing this made program slightly weaker.
1256           Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1257           futilityValueScaled =  futilityBase + futility_margin(predictedDepth, moveCount)
1258                                + H.gain(pos.piece_on(move_from(move)), move_to(move));
1259
1260           if (futilityValueScaled < beta)
1261           {
1262               if (futilityValueScaled > bestValue)
1263                   bestValue = futilityValueScaled;
1264               continue;
1265           }
1266       }
1267
1268       // Step 13. Make the move
1269       pos.do_move(move, st, ci, moveIsCheck);
1270
1271       // Step extra. pv search (only in PV nodes)
1272       // The first move in list is the expected PV
1273       if (PvNode && moveCount == 1)
1274           value = newDepth < ONE_PLY ? -qsearch<PV>(pos, ss+1, -beta, -alpha, DEPTH_ZERO, ply+1)
1275                                      : - search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1276       else
1277       {
1278           // Step 14. Reduced depth search
1279           // If the move fails high will be re-searched at full depth.
1280           bool doFullDepthSearch = true;
1281
1282           if (    depth >= 3 * ONE_PLY
1283               && !captureOrPromotion
1284               && !dangerous
1285               && !move_is_castle(move)
1286               && !move_is_killer(move, ss))
1287           {
1288               ss->reduction = reduction<PvNode>(depth, moveCount);
1289               if (ss->reduction)
1290               {
1291                   Depth d = newDepth - ss->reduction;
1292                   value = d < ONE_PLY ? -qsearch<NonPV>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO, ply+1)
1293                                       : - search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1294
1295                   doFullDepthSearch = (value > alpha);
1296               }
1297
1298               // The move failed high, but if reduction is very big we could
1299               // face a false positive, retry with a less aggressive reduction,
1300               // if the move fails high again then go with full depth search.
1301               if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
1302               {
1303                   assert(newDepth - ONE_PLY >= ONE_PLY);
1304
1305                   ss->reduction = ONE_PLY;
1306                   value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, ply+1);
1307                   doFullDepthSearch = (value > alpha);
1308               }
1309               ss->reduction = DEPTH_ZERO; // Restore original reduction
1310           }
1311
1312           // Step 15. Full depth search
1313           if (doFullDepthSearch)
1314           {
1315               value = newDepth < ONE_PLY ? -qsearch<NonPV>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO, ply+1)
1316                                          : - search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1317
1318               // Step extra. pv search (only in PV nodes)
1319               // Search only for possible new PV nodes, if instead value >= beta then
1320               // parent node fails low with value <= alpha and tries another move.
1321               if (PvNode && value > alpha && value < beta)
1322                   value = newDepth < ONE_PLY ? -qsearch<PV>(pos, ss+1, -beta, -alpha, DEPTH_ZERO, ply+1)
1323                                              : - search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1324           }
1325       }
1326
1327       // Step 16. Undo move
1328       pos.undo_move(move);
1329
1330       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1331
1332       // Step 17. Check for new best move
1333       if (value > bestValue)
1334       {
1335           bestValue = value;
1336           if (value > alpha)
1337           {
1338               if (PvNode && value < beta) // We want always alpha < beta
1339                   alpha = value;
1340
1341               if (value == value_mate_in(ply + 1))
1342                   ss->mateKiller = move;
1343
1344               ss->bestMove = move;
1345           }
1346       }
1347
1348       // Step 18. Check for split
1349       if (   depth >= MinimumSplitDepth
1350           && ThreadsMgr.active_threads() > 1
1351           && bestValue < beta
1352           && ThreadsMgr.available_thread_exists(threadID)
1353           && !AbortSearch
1354           && !ThreadsMgr.thread_should_stop(threadID)
1355           && Iteration <= 99)
1356           ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1357                                       threatMove, mateThreat, &moveCount, &mp, PvNode);
1358     }
1359
1360     // Step 19. Check for mate and stalemate
1361     // All legal moves have been searched and if there are
1362     // no legal moves, it must be mate or stalemate.
1363     // If one move was excluded return fail low score.
1364     if (!moveCount)
1365         return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW;
1366
1367     // Step 20. Update tables
1368     // If the search is not aborted, update the transposition table,
1369     // history counters, and killer moves.
1370     if (AbortSearch || ThreadsMgr.thread_should_stop(threadID))
1371         return bestValue;
1372
1373     ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1374     move = (bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove);
1375     TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, margins[pos.side_to_move()]);
1376
1377     // Update killers and history only for non capture moves that fails high
1378     if (    bestValue >= beta
1379         && !pos.move_is_capture_or_promotion(move))
1380     {
1381             update_history(pos, move, depth, movesSearched, moveCount);
1382             update_killers(move, ss);
1383     }
1384
1385     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1386
1387     return bestValue;
1388   }
1389
1390
1391   // qsearch() is the quiescence search function, which is called by the main
1392   // search function when the remaining depth is zero (or, to be more precise,
1393   // less than ONE_PLY).
1394
1395   template <NodeType PvNode>
1396   Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1397
1398     assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1399     assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1400     assert(PvNode || alpha == beta - 1);
1401     assert(depth <= 0);
1402     assert(ply > 0 && ply < PLY_MAX);
1403     assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1404
1405     Value margins[2];
1406     StateInfo st;
1407     Move ttMove, move;
1408     Value bestValue, value, futilityValue, futilityBase;
1409     bool isCheck, deepChecks, enoughMaterial, moveIsCheck, evasionPrunable;
1410     const TTEntry* tte;
1411     Value oldAlpha = alpha;
1412
1413     ThreadsMgr.incrementNodeCounter(pos.thread());
1414     ss->bestMove = ss->currentMove = MOVE_NONE;
1415
1416     // Check for an instant draw or maximum ply reached
1417     if (pos.is_draw() || ply >= PLY_MAX - 1)
1418         return VALUE_DRAW;
1419
1420     // Transposition table lookup. At PV nodes, we don't use the TT for
1421     // pruning, but only for move ordering.
1422     tte = TT.retrieve(pos.get_key());
1423     ttMove = (tte ? tte->move() : MOVE_NONE);
1424
1425     if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1426     {
1427         ss->bestMove = ttMove; // Can be MOVE_NONE
1428         return value_from_tt(tte->value(), ply);
1429     }
1430
1431     isCheck = pos.is_check();
1432
1433     // Evaluate the position statically
1434     if (isCheck)
1435     {
1436         bestValue = futilityBase = -VALUE_INFINITE;
1437         ss->eval = VALUE_NONE;
1438         deepChecks = enoughMaterial = false;
1439     }
1440     else
1441     {
1442         if (tte)
1443         {
1444             assert(tte->static_value() != VALUE_NONE);
1445
1446             margins[pos.side_to_move()] = tte->static_value_margin();
1447             bestValue = tte->static_value();
1448         }
1449         else
1450             bestValue = evaluate(pos, margins);
1451
1452         ss->eval = bestValue;
1453         update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1454
1455         // Stand pat. Return immediately if static value is at least beta
1456         if (bestValue >= beta)
1457         {
1458             if (!tte)
1459                 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, margins[pos.side_to_move()]);
1460
1461             return bestValue;
1462         }
1463
1464         if (PvNode && bestValue > alpha)
1465             alpha = bestValue;
1466
1467         // If we are near beta then try to get a cutoff pushing checks a bit further
1468         deepChecks = (depth == -ONE_PLY && bestValue >= beta - PawnValueMidgame / 8);
1469
1470         // Futility pruning parameters, not needed when in check
1471         futilityBase = bestValue + FutilityMarginQS + margins[pos.side_to_move()];
1472         enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1473     }
1474
1475     // Initialize a MovePicker object for the current position, and prepare
1476     // to search the moves. Because the depth is <= 0 here, only captures,
1477     // queen promotions and checks (only if depth == 0 or depth == -ONE_PLY
1478     // and we are near beta) will be generated.
1479     MovePicker mp = MovePicker(pos, ttMove, deepChecks ? DEPTH_ZERO : depth, H);
1480     CheckInfo ci(pos);
1481
1482     // Loop through the moves until no moves remain or a beta cutoff occurs
1483     while (   alpha < beta
1484            && (move = mp.get_next_move()) != MOVE_NONE)
1485     {
1486       assert(move_is_ok(move));
1487
1488       moveIsCheck = pos.move_is_check(move, ci);
1489
1490       // Futility pruning
1491       if (   !PvNode
1492           && !isCheck
1493           && !moveIsCheck
1494           &&  move != ttMove
1495           &&  enoughMaterial
1496           && !move_is_promotion(move)
1497           && !pos.move_is_passed_pawn_push(move))
1498       {
1499           futilityValue =  futilityBase
1500                          + pos.endgame_value_of_piece_on(move_to(move))
1501                          + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1502
1503           if (futilityValue < alpha)
1504           {
1505               if (futilityValue > bestValue)
1506                   bestValue = futilityValue;
1507               continue;
1508           }
1509       }
1510
1511       // Detect blocking evasions that are candidate to be pruned
1512       evasionPrunable =   isCheck
1513                        && bestValue > value_mated_in(PLY_MAX)
1514                        && !pos.move_is_capture(move)
1515                        && pos.type_of_piece_on(move_from(move)) != KING
1516                        && !pos.can_castle(pos.side_to_move());
1517
1518       // Don't search moves with negative SEE values
1519       if (   !PvNode
1520           && (!isCheck || evasionPrunable)
1521           &&  move != ttMove
1522           && !move_is_promotion(move)
1523           &&  pos.see_sign(move) < 0)
1524           continue;
1525
1526       // Update current move
1527       ss->currentMove = move;
1528
1529       // Make and search the move
1530       pos.do_move(move, st, ci, moveIsCheck);
1531       value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1);
1532       pos.undo_move(move);
1533
1534       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1535
1536       // New best move?
1537       if (value > bestValue)
1538       {
1539           bestValue = value;
1540           if (value > alpha)
1541           {
1542               alpha = value;
1543               ss->bestMove = move;
1544           }
1545        }
1546     }
1547
1548     // All legal moves have been searched. A special case: If we're in check
1549     // and no legal moves were found, it is checkmate.
1550     if (isCheck && bestValue == -VALUE_INFINITE)
1551         return value_mated_in(ply);
1552
1553     // Update transposition table
1554     Depth d = (depth == DEPTH_ZERO ? DEPTH_ZERO : DEPTH_ZERO - ONE_PLY);
1555     ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1556     TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, d, ss->bestMove, ss->eval, margins[pos.side_to_move()]);
1557
1558     // Update killers only for checking moves that fails high
1559     if (    bestValue >= beta
1560         && !pos.move_is_capture_or_promotion(ss->bestMove))
1561         update_killers(ss->bestMove, ss);
1562
1563     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1564
1565     return bestValue;
1566   }
1567
1568
1569   // sp_search() is used to search from a split point.  This function is called
1570   // by each thread working at the split point.  It is similar to the normal
1571   // search() function, but simpler.  Because we have already probed the hash
1572   // table, done a null move search, and searched the first move before
1573   // splitting, we don't have to repeat all this work in sp_search().  We
1574   // also don't need to store anything to the hash table here:  This is taken
1575   // care of after we return from the split point.
1576
1577   template <NodeType PvNode>
1578   void sp_search(SplitPoint* sp, int threadID) {
1579
1580     assert(threadID >= 0 && threadID < ThreadsMgr.active_threads());
1581     assert(ThreadsMgr.active_threads() > 1);
1582
1583     StateInfo st;
1584     Move move;
1585     Depth ext, newDepth;
1586     Value value;
1587     Value futilityValueScaled; // NonPV specific
1588     bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
1589     int moveCount;
1590     value = -VALUE_INFINITE;
1591
1592     Position pos(*sp->pos, threadID);
1593     CheckInfo ci(pos);
1594     SearchStack* ss = sp->sstack[threadID] + 1;
1595     isCheck = pos.is_check();
1596
1597     // Step 10. Loop through moves
1598     // Loop through all legal moves until no moves remain or a beta cutoff occurs
1599     lock_grab(&(sp->lock));
1600
1601     while (    sp->bestValue < sp->beta
1602            && (move = sp->mp->get_next_move()) != MOVE_NONE
1603            && !ThreadsMgr.thread_should_stop(threadID))
1604     {
1605       moveCount = ++sp->moveCount;
1606       lock_release(&(sp->lock));
1607
1608       assert(move_is_ok(move));
1609
1610       moveIsCheck = pos.move_is_check(move, ci);
1611       captureOrPromotion = pos.move_is_capture_or_promotion(move);
1612
1613       // Step 11. Decide the new search depth
1614       ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous);
1615       newDepth = sp->depth - ONE_PLY + ext;
1616
1617       // Update current move
1618       ss->currentMove = move;
1619
1620       // Step 12. Futility pruning (is omitted in PV nodes)
1621       if (   !PvNode
1622           && !captureOrPromotion
1623           && !isCheck
1624           && !dangerous
1625           && !move_is_castle(move))
1626       {
1627           // Move count based pruning
1628           if (   moveCount >= futility_move_count(sp->depth)
1629               && !(sp->threatMove && connected_threat(pos, move, sp->threatMove))
1630               && sp->bestValue > value_mated_in(PLY_MAX))
1631           {
1632               lock_grab(&(sp->lock));
1633               continue;
1634           }
1635
1636           // Value based pruning
1637           Depth predictedDepth = newDepth - reduction<NonPV>(sp->depth, moveCount);
1638           futilityValueScaled =  ss->eval + futility_margin(predictedDepth, moveCount)
1639                                + H.gain(pos.piece_on(move_from(move)), move_to(move));
1640
1641           if (futilityValueScaled < sp->beta)
1642           {
1643               lock_grab(&(sp->lock));
1644
1645               if (futilityValueScaled > sp->bestValue)
1646                   sp->bestValue = futilityValueScaled;
1647               continue;
1648           }
1649       }
1650
1651       // Step 13. Make the move
1652       pos.do_move(move, st, ci, moveIsCheck);
1653
1654       // Step 14. Reduced search
1655       // If the move fails high will be re-searched at full depth.
1656       bool doFullDepthSearch = true;
1657
1658       if (   !captureOrPromotion
1659           && !dangerous
1660           && !move_is_castle(move)
1661           && !move_is_killer(move, ss))
1662       {
1663           ss->reduction = reduction<PvNode>(sp->depth, moveCount);
1664           if (ss->reduction)
1665           {
1666               Value localAlpha = sp->alpha;
1667               Depth d = newDepth - ss->reduction;
1668               value = d < ONE_PLY ? -qsearch<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, DEPTH_ZERO, sp->ply+1)
1669                                   : - search<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, d, sp->ply+1);
1670
1671               doFullDepthSearch = (value > localAlpha);
1672           }
1673
1674           // The move failed high, but if reduction is very big we could
1675           // face a false positive, retry with a less aggressive reduction,
1676           // if the move fails high again then go with full depth search.
1677           if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
1678           {
1679               assert(newDepth - ONE_PLY >= ONE_PLY);
1680
1681               ss->reduction = ONE_PLY;
1682               Value localAlpha = sp->alpha;
1683               value = -search<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, newDepth-ss->reduction, sp->ply+1);
1684               doFullDepthSearch = (value > localAlpha);
1685           }
1686           ss->reduction = DEPTH_ZERO; // Restore original reduction
1687       }
1688
1689       // Step 15. Full depth search
1690       if (doFullDepthSearch)
1691       {
1692           Value localAlpha = sp->alpha;
1693           value = newDepth < ONE_PLY ? -qsearch<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, DEPTH_ZERO, sp->ply+1)
1694                                      : - search<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, newDepth, sp->ply+1);
1695
1696           // Step extra. pv search (only in PV nodes)
1697           // Search only for possible new PV nodes, if instead value >= beta then
1698           // parent node fails low with value <= alpha and tries another move.
1699           if (PvNode && value > localAlpha && value < sp->beta)
1700               value = newDepth < ONE_PLY ? -qsearch<PV>(pos, ss+1, -sp->beta, -sp->alpha, DEPTH_ZERO, sp->ply+1)
1701                                          : - search<PV>(pos, ss+1, -sp->beta, -sp->alpha, newDepth, sp->ply+1);
1702       }
1703
1704       // Step 16. Undo move
1705       pos.undo_move(move);
1706
1707       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1708
1709       // Step 17. Check for new best move
1710       lock_grab(&(sp->lock));
1711
1712       if (value > sp->bestValue && !ThreadsMgr.thread_should_stop(threadID))
1713       {
1714           sp->bestValue = value;
1715
1716           if (sp->bestValue > sp->alpha)
1717           {
1718               if (!PvNode || value >= sp->beta)
1719                   sp->stopRequest = true;
1720
1721               if (PvNode && value < sp->beta) // This guarantees that always: sp->alpha < sp->beta
1722                   sp->alpha = value;
1723
1724               sp->parentSstack->bestMove = ss->bestMove = move;
1725           }
1726       }
1727     }
1728
1729     /* Here we have the lock still grabbed */
1730
1731     sp->slaves[threadID] = 0;
1732
1733     lock_release(&(sp->lock));
1734   }
1735
1736
1737   // connected_moves() tests whether two moves are 'connected' in the sense
1738   // that the first move somehow made the second move possible (for instance
1739   // if the moving piece is the same in both moves). The first move is assumed
1740   // to be the move that was made to reach the current position, while the
1741   // second move is assumed to be a move from the current position.
1742
1743   bool connected_moves(const Position& pos, Move m1, Move m2) {
1744
1745     Square f1, t1, f2, t2;
1746     Piece p;
1747
1748     assert(move_is_ok(m1));
1749     assert(move_is_ok(m2));
1750
1751     if (m2 == MOVE_NONE)
1752         return false;
1753
1754     // Case 1: The moving piece is the same in both moves
1755     f2 = move_from(m2);
1756     t1 = move_to(m1);
1757     if (f2 == t1)
1758         return true;
1759
1760     // Case 2: The destination square for m2 was vacated by m1
1761     t2 = move_to(m2);
1762     f1 = move_from(m1);
1763     if (t2 == f1)
1764         return true;
1765
1766     // Case 3: Moving through the vacated square
1767     if (   piece_is_slider(pos.piece_on(f2))
1768         && bit_is_set(squares_between(f2, t2), f1))
1769       return true;
1770
1771     // Case 4: The destination square for m2 is defended by the moving piece in m1
1772     p = pos.piece_on(t1);
1773     if (bit_is_set(pos.attacks_from(p, t1), t2))
1774         return true;
1775
1776     // Case 5: Discovered check, checking piece is the piece moved in m1
1777     if (    piece_is_slider(p)
1778         &&  bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1779         && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1780     {
1781         // discovered_check_candidates() works also if the Position's side to
1782         // move is the opposite of the checking piece.
1783         Color them = opposite_color(pos.side_to_move());
1784         Bitboard dcCandidates = pos.discovered_check_candidates(them);
1785
1786         if (bit_is_set(dcCandidates, f2))
1787             return true;
1788     }
1789     return false;
1790   }
1791
1792
1793   // value_is_mate() checks if the given value is a mate one eventually
1794   // compensated for the ply.
1795
1796   bool value_is_mate(Value value) {
1797
1798     assert(abs(value) <= VALUE_INFINITE);
1799
1800     return   value <= value_mated_in(PLY_MAX)
1801           || value >= value_mate_in(PLY_MAX);
1802   }
1803
1804
1805   // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1806   // "plies to mate from the current ply".  Non-mate scores are unchanged.
1807   // The function is called before storing a value to the transposition table.
1808
1809   Value value_to_tt(Value v, int ply) {
1810
1811     if (v >= value_mate_in(PLY_MAX))
1812       return v + ply;
1813
1814     if (v <= value_mated_in(PLY_MAX))
1815       return v - ply;
1816
1817     return v;
1818   }
1819
1820
1821   // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1822   // the transposition table to a mate score corrected for the current ply.
1823
1824   Value value_from_tt(Value v, int ply) {
1825
1826     if (v >= value_mate_in(PLY_MAX))
1827       return v - ply;
1828
1829     if (v <= value_mated_in(PLY_MAX))
1830       return v + ply;
1831
1832     return v;
1833   }
1834
1835
1836   // move_is_killer() checks if the given move is among the killer moves
1837
1838   bool move_is_killer(Move m, SearchStack* ss) {
1839
1840       if (ss->killers[0] == m || ss->killers[1] == m)
1841           return true;
1842
1843       return false;
1844   }
1845
1846
1847   // extension() decides whether a move should be searched with normal depth,
1848   // or with extended depth. Certain classes of moves (checking moves, in
1849   // particular) are searched with bigger depth than ordinary moves and in
1850   // any case are marked as 'dangerous'. Note that also if a move is not
1851   // extended, as example because the corresponding UCI option is set to zero,
1852   // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1853   template <NodeType PvNode>
1854   Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1855                   bool singleEvasion, bool mateThreat, bool* dangerous) {
1856
1857     assert(m != MOVE_NONE);
1858
1859     Depth result = DEPTH_ZERO;
1860     *dangerous = moveIsCheck | singleEvasion | mateThreat;
1861
1862     if (*dangerous)
1863     {
1864         if (moveIsCheck && pos.see_sign(m) >= 0)
1865             result += CheckExtension[PvNode];
1866
1867         if (singleEvasion)
1868             result += SingleEvasionExtension[PvNode];
1869
1870         if (mateThreat)
1871             result += MateThreatExtension[PvNode];
1872     }
1873
1874     if (pos.type_of_piece_on(move_from(m)) == PAWN)
1875     {
1876         Color c = pos.side_to_move();
1877         if (relative_rank(c, move_to(m)) == RANK_7)
1878         {
1879             result += PawnPushTo7thExtension[PvNode];
1880             *dangerous = true;
1881         }
1882         if (pos.pawn_is_passed(c, move_to(m)))
1883         {
1884             result += PassedPawnExtension[PvNode];
1885             *dangerous = true;
1886         }
1887     }
1888
1889     if (   captureOrPromotion
1890         && pos.type_of_piece_on(move_to(m)) != PAWN
1891         && (  pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1892             - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1893         && !move_is_promotion(m)
1894         && !move_is_ep(m))
1895     {
1896         result += PawnEndgameExtension[PvNode];
1897         *dangerous = true;
1898     }
1899
1900     if (   PvNode
1901         && captureOrPromotion
1902         && pos.type_of_piece_on(move_to(m)) != PAWN
1903         && pos.see_sign(m) >= 0)
1904     {
1905         result += ONE_PLY / 2;
1906         *dangerous = true;
1907     }
1908
1909     return Min(result, ONE_PLY);
1910   }
1911
1912
1913   // connected_threat() tests whether it is safe to forward prune a move or if
1914   // is somehow coonected to the threat move returned by null search.
1915
1916   bool connected_threat(const Position& pos, Move m, Move threat) {
1917
1918     assert(move_is_ok(m));
1919     assert(threat && move_is_ok(threat));
1920     assert(!pos.move_is_check(m));
1921     assert(!pos.move_is_capture_or_promotion(m));
1922     assert(!pos.move_is_passed_pawn_push(m));
1923
1924     Square mfrom, mto, tfrom, tto;
1925
1926     mfrom = move_from(m);
1927     mto = move_to(m);
1928     tfrom = move_from(threat);
1929     tto = move_to(threat);
1930
1931     // Case 1: Don't prune moves which move the threatened piece
1932     if (mfrom == tto)
1933         return true;
1934
1935     // Case 2: If the threatened piece has value less than or equal to the
1936     // value of the threatening piece, don't prune move which defend it.
1937     if (   pos.move_is_capture(threat)
1938         && (   pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1939             || pos.type_of_piece_on(tfrom) == KING)
1940         && pos.move_attacks_square(m, tto))
1941         return true;
1942
1943     // Case 3: If the moving piece in the threatened move is a slider, don't
1944     // prune safe moves which block its ray.
1945     if (   piece_is_slider(pos.piece_on(tfrom))
1946         && bit_is_set(squares_between(tfrom, tto), mto)
1947         && pos.see_sign(m) >= 0)
1948         return true;
1949
1950     return false;
1951   }
1952
1953
1954   // ok_to_use_TT() returns true if a transposition table score
1955   // can be used at a given point in search.
1956
1957   bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1958
1959     Value v = value_from_tt(tte->value(), ply);
1960
1961     return   (   tte->depth() >= depth
1962               || v >= Max(value_mate_in(PLY_MAX), beta)
1963               || v < Min(value_mated_in(PLY_MAX), beta))
1964
1965           && (   ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1966               || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1967   }
1968
1969
1970   // refine_eval() returns the transposition table score if
1971   // possible otherwise falls back on static position evaluation.
1972
1973   Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1974
1975       assert(tte);
1976
1977       Value v = value_from_tt(tte->value(), ply);
1978
1979       if (   ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1980           || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1981           return v;
1982
1983       return defaultEval;
1984   }
1985
1986
1987   // update_history() registers a good move that produced a beta-cutoff
1988   // in history and marks as failures all the other moves of that ply.
1989
1990   void update_history(const Position& pos, Move move, Depth depth,
1991                       Move movesSearched[], int moveCount) {
1992
1993     Move m;
1994
1995     H.success(pos.piece_on(move_from(move)), move_to(move), depth);
1996
1997     for (int i = 0; i < moveCount - 1; i++)
1998     {
1999         m = movesSearched[i];
2000
2001         assert(m != move);
2002
2003         if (!pos.move_is_capture_or_promotion(m))
2004             H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
2005     }
2006   }
2007
2008
2009   // update_killers() add a good move that produced a beta-cutoff
2010   // among the killer moves of that ply.
2011
2012   void update_killers(Move m, SearchStack* ss) {
2013
2014     if (m == ss->killers[0])
2015         return;
2016
2017     ss->killers[1] = ss->killers[0];
2018     ss->killers[0] = m;
2019   }
2020
2021
2022   // update_gains() updates the gains table of a non-capture move given
2023   // the static position evaluation before and after the move.
2024
2025   void update_gains(const Position& pos, Move m, Value before, Value after) {
2026
2027     if (   m != MOVE_NULL
2028         && before != VALUE_NONE
2029         && after != VALUE_NONE
2030         && pos.captured_piece_type() == PIECE_TYPE_NONE
2031         && !move_is_special(m))
2032         H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
2033   }
2034
2035
2036   // current_search_time() returns the number of milliseconds which have passed
2037   // since the beginning of the current search.
2038
2039   int current_search_time() {
2040
2041     return get_system_time() - SearchStartTime;
2042   }
2043
2044
2045   // value_to_uci() converts a value to a string suitable for use with the UCI protocol
2046
2047   std::string value_to_uci(Value v) {
2048
2049     std::stringstream s;
2050
2051     if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
2052       s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100
2053     else
2054       s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
2055
2056     return s.str();
2057   }
2058
2059   // nps() computes the current nodes/second count.
2060
2061   int nps() {
2062
2063     int t = current_search_time();
2064     return (t > 0 ? int((ThreadsMgr.nodes_searched() * 1000) / t) : 0);
2065   }
2066
2067
2068   // poll() performs two different functions: It polls for user input, and it
2069   // looks at the time consumed so far and decides if it's time to abort the
2070   // search.
2071
2072   void poll() {
2073
2074     static int lastInfoTime;
2075     int t = current_search_time();
2076
2077     //  Poll for input
2078     if (Bioskey())
2079     {
2080         // We are line oriented, don't read single chars
2081         std::string command;
2082
2083         if (!std::getline(std::cin, command))
2084             command = "quit";
2085
2086         if (command == "quit")
2087         {
2088             AbortSearch = true;
2089             PonderSearch = false;
2090             Quit = true;
2091             return;
2092         }
2093         else if (command == "stop")
2094         {
2095             AbortSearch = true;
2096             PonderSearch = false;
2097         }
2098         else if (command == "ponderhit")
2099             ponderhit();
2100     }
2101
2102     // Print search information
2103     if (t < 1000)
2104         lastInfoTime = 0;
2105
2106     else if (lastInfoTime > t)
2107         // HACK: Must be a new search where we searched less than
2108         // NodesBetweenPolls nodes during the first second of search.
2109         lastInfoTime = 0;
2110
2111     else if (t - lastInfoTime >= 1000)
2112     {
2113         lastInfoTime = t;
2114
2115         if (dbg_show_mean)
2116             dbg_print_mean();
2117
2118         if (dbg_show_hit_rate)
2119             dbg_print_hit_rate();
2120
2121         cout << "info nodes " << ThreadsMgr.nodes_searched() << " nps " << nps()
2122              << " time " << t << endl;
2123     }
2124
2125     // Should we stop the search?
2126     if (PonderSearch)
2127         return;
2128
2129     bool stillAtFirstMove =    FirstRootMove
2130                            && !AspirationFailLow
2131                            &&  t > TimeMgr.available_time();
2132
2133     bool noMoreTime =   t > TimeMgr.maximum_time()
2134                      || stillAtFirstMove;
2135
2136     if (   (Iteration >= 3 && UseTimeManagement && noMoreTime)
2137         || (ExactMaxTime && t >= ExactMaxTime)
2138         || (Iteration >= 3 && MaxNodes && ThreadsMgr.nodes_searched() >= MaxNodes))
2139         AbortSearch = true;
2140   }
2141
2142
2143   // ponderhit() is called when the program is pondering (i.e. thinking while
2144   // it's the opponent's turn to move) in order to let the engine know that
2145   // it correctly predicted the opponent's move.
2146
2147   void ponderhit() {
2148
2149     int t = current_search_time();
2150     PonderSearch = false;
2151
2152     bool stillAtFirstMove =    FirstRootMove
2153                            && !AspirationFailLow
2154                            &&  t > TimeMgr.available_time();
2155
2156     bool noMoreTime =   t > TimeMgr.maximum_time()
2157                      || stillAtFirstMove;
2158
2159     if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2160         AbortSearch = true;
2161   }
2162
2163
2164   // init_ss_array() does a fast reset of the first entries of a SearchStack
2165   // array and of all the excludedMove and skipNullMove entries.
2166
2167   void init_ss_array(SearchStack* ss, int size) {
2168
2169     for (int i = 0; i < size; i++, ss++)
2170     {
2171         ss->excludedMove = MOVE_NONE;
2172         ss->skipNullMove = false;
2173         ss->reduction = DEPTH_ZERO;
2174
2175         if (i < 3)
2176             ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE;
2177     }
2178   }
2179
2180
2181   // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2182   // while the program is pondering. The point is to work around a wrinkle in
2183   // the UCI protocol: When pondering, the engine is not allowed to give a
2184   // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2185   // We simply wait here until one of these commands is sent, and return,
2186   // after which the bestmove and pondermove will be printed (in id_loop()).
2187
2188   void wait_for_stop_or_ponderhit() {
2189
2190     std::string command;
2191
2192     while (true)
2193     {
2194         if (!std::getline(std::cin, command))
2195             command = "quit";
2196
2197         if (command == "quit")
2198         {
2199             Quit = true;
2200             break;
2201         }
2202         else if (command == "ponderhit" || command == "stop")
2203             break;
2204     }
2205   }
2206
2207
2208   // print_pv_info() prints to standard output and eventually to log file information on
2209   // the current PV line. It is called at each iteration or after a new pv is found.
2210
2211   void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) {
2212
2213     cout << "info depth " << Iteration
2214          << " score "     << value_to_uci(value)
2215          << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
2216          << " time "  << current_search_time()
2217          << " nodes " << ThreadsMgr.nodes_searched()
2218          << " nps "   << nps()
2219          << " pv ";
2220
2221     for (Move* m = pv; *m != MOVE_NONE; m++)
2222         cout << *m << " ";
2223
2224     cout << endl;
2225
2226     if (UseLogFile)
2227     {
2228         ValueType t = value >= beta  ? VALUE_TYPE_LOWER :
2229                       value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
2230
2231         LogFile << pretty_pv(pos, current_search_time(), Iteration,
2232                              ThreadsMgr.nodes_searched(), value, t, pv) << endl;
2233     }
2234   }
2235
2236
2237   // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2238   // the PV back into the TT. This makes sure the old PV moves are searched
2239   // first, even if the old TT entries have been overwritten.
2240
2241   void insert_pv_in_tt(const Position& pos, Move pv[]) {
2242
2243     StateInfo st;
2244     TTEntry* tte;
2245     Position p(pos, pos.thread());
2246     Value margins[2];
2247     Value v;
2248
2249     for (int i = 0; pv[i] != MOVE_NONE; i++)
2250     {
2251         tte = TT.retrieve(p.get_key());
2252         if (!tte || tte->move() != pv[i])
2253         {
2254             v = (p.is_check() ? VALUE_NONE : evaluate(p, margins));
2255             TT.store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[i], v, margins[pos.side_to_move()]);
2256         }
2257         p.do_move(pv[i], st);
2258     }
2259   }
2260
2261
2262   // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2263   // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2264   // allow to always have a ponder move even when we fail high at root and also a
2265   // long PV to print that is important for position analysis.
2266
2267   void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]) {
2268
2269     StateInfo st;
2270     TTEntry* tte;
2271     Position p(pos, pos.thread());
2272     int ply = 0;
2273
2274     assert(bestMove != MOVE_NONE);
2275
2276     pv[ply] = bestMove;
2277     p.do_move(pv[ply++], st);
2278
2279     while (   (tte = TT.retrieve(p.get_key())) != NULL
2280            && tte->move() != MOVE_NONE
2281            && move_is_legal(p, tte->move())
2282            && ply < PLY_MAX
2283            && (!p.is_draw() || ply < 2))
2284     {
2285         pv[ply] = tte->move();
2286         p.do_move(pv[ply++], st);
2287     }
2288     pv[ply] = MOVE_NONE;
2289   }
2290
2291
2292   // init_thread() is the function which is called when a new thread is
2293   // launched. It simply calls the idle_loop() function with the supplied
2294   // threadID. There are two versions of this function; one for POSIX
2295   // threads and one for Windows threads.
2296
2297 #if !defined(_MSC_VER)
2298
2299   void* init_thread(void *threadID) {
2300
2301     ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2302     return NULL;
2303   }
2304
2305 #else
2306
2307   DWORD WINAPI init_thread(LPVOID threadID) {
2308
2309     ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2310     return 0;
2311   }
2312
2313 #endif
2314
2315
2316   /// The ThreadsManager class
2317
2318   // resetNodeCounters(), resetBetaCounters(), searched_nodes() and
2319   // get_beta_counters() are getters/setters for the per thread
2320   // counters used to sort the moves at root.
2321
2322   void ThreadsManager::resetNodeCounters() {
2323
2324     for (int i = 0; i < MAX_THREADS; i++)
2325         threads[i].nodes = 0ULL;
2326   }
2327
2328   int64_t ThreadsManager::nodes_searched() const {
2329
2330     int64_t result = 0ULL;
2331     for (int i = 0; i < ActiveThreads; i++)
2332         result += threads[i].nodes;
2333
2334     return result;
2335   }
2336
2337
2338   // idle_loop() is where the threads are parked when they have no work to do.
2339   // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2340   // object for which the current thread is the master.
2341
2342   void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2343
2344     assert(threadID >= 0 && threadID < MAX_THREADS);
2345
2346     while (true)
2347     {
2348         // Slave threads can exit as soon as AllThreadsShouldExit raises,
2349         // master should exit as last one.
2350         if (AllThreadsShouldExit)
2351         {
2352             assert(!sp);
2353             threads[threadID].state = THREAD_TERMINATED;
2354             return;
2355         }
2356
2357         // If we are not thinking, wait for a condition to be signaled
2358         // instead of wasting CPU time polling for work.
2359         while (AllThreadsShouldSleep || threadID >= ActiveThreads)
2360         {
2361             assert(!sp);
2362             assert(threadID != 0);
2363             threads[threadID].state = THREAD_SLEEPING;
2364
2365 #if !defined(_MSC_VER)
2366             lock_grab(&WaitLock);
2367             if (AllThreadsShouldSleep || threadID >= ActiveThreads)
2368                 pthread_cond_wait(&WaitCond, &WaitLock);
2369             lock_release(&WaitLock);
2370 #else
2371             WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2372 #endif
2373         }
2374
2375         // If thread has just woken up, mark it as available
2376         if (threads[threadID].state == THREAD_SLEEPING)
2377             threads[threadID].state = THREAD_AVAILABLE;
2378
2379         // If this thread has been assigned work, launch a search
2380         if (threads[threadID].state == THREAD_WORKISWAITING)
2381         {
2382             assert(!AllThreadsShouldExit && !AllThreadsShouldSleep);
2383
2384             threads[threadID].state = THREAD_SEARCHING;
2385
2386             if (threads[threadID].splitPoint->pvNode)
2387                 sp_search<PV>(threads[threadID].splitPoint, threadID);
2388             else
2389                 sp_search<NonPV>(threads[threadID].splitPoint, threadID);
2390
2391             assert(threads[threadID].state == THREAD_SEARCHING);
2392
2393             threads[threadID].state = THREAD_AVAILABLE;
2394         }
2395
2396         // If this thread is the master of a split point and all slaves have
2397         // finished their work at this split point, return from the idle loop.
2398         int i = 0;
2399         for ( ; sp && i < ActiveThreads && !sp->slaves[i]; i++) {}
2400
2401         if (i == ActiveThreads)
2402         {
2403             // Because sp->slaves[] is reset under lock protection,
2404             // be sure sp->lock has been released before to return.
2405             lock_grab(&(sp->lock));
2406             lock_release(&(sp->lock));
2407
2408             assert(threads[threadID].state == THREAD_AVAILABLE);
2409
2410             threads[threadID].state = THREAD_SEARCHING;
2411             return;
2412         }
2413     }
2414   }
2415
2416
2417   // init_threads() is called during startup. It launches all helper threads,
2418   // and initializes the split point stack and the global locks and condition
2419   // objects.
2420
2421   void ThreadsManager::init_threads() {
2422
2423     volatile int i;
2424     bool ok;
2425
2426 #if !defined(_MSC_VER)
2427     pthread_t pthread[1];
2428 #endif
2429
2430     // Initialize global locks
2431     lock_init(&MPLock);
2432     lock_init(&WaitLock);
2433
2434 #if !defined(_MSC_VER)
2435     pthread_cond_init(&WaitCond, NULL);
2436 #else
2437     for (i = 0; i < MAX_THREADS; i++)
2438         SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0);
2439 #endif
2440
2441     // Initialize splitPoints[] locks
2442     for (i = 0; i < MAX_THREADS; i++)
2443         for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2444             lock_init(&(threads[i].splitPoints[j].lock));
2445
2446     // Will be set just before program exits to properly end the threads
2447     AllThreadsShouldExit = false;
2448
2449     // Threads will be put to sleep as soon as created
2450     AllThreadsShouldSleep = true;
2451
2452     // All threads except the main thread should be initialized to THREAD_AVAILABLE
2453     ActiveThreads = 1;
2454     threads[0].state = THREAD_SEARCHING;
2455     for (i = 1; i < MAX_THREADS; i++)
2456         threads[i].state = THREAD_AVAILABLE;
2457
2458     // Launch the helper threads
2459     for (i = 1; i < MAX_THREADS; i++)
2460     {
2461
2462 #if !defined(_MSC_VER)
2463         ok = (pthread_create(pthread, NULL, init_thread, (void*)(&i)) == 0);
2464 #else
2465         ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, NULL) != NULL);
2466 #endif
2467
2468         if (!ok)
2469         {
2470             cout << "Failed to create thread number " << i << endl;
2471             Application::exit_with_failure();
2472         }
2473
2474         // Wait until the thread has finished launching and is gone to sleep
2475         while (threads[i].state != THREAD_SLEEPING) {}
2476     }
2477   }
2478
2479
2480   // exit_threads() is called when the program exits. It makes all the
2481   // helper threads exit cleanly.
2482
2483   void ThreadsManager::exit_threads() {
2484
2485     ActiveThreads = MAX_THREADS;  // HACK
2486     AllThreadsShouldSleep = true;  // HACK
2487     wake_sleeping_threads();
2488
2489     // This makes the threads to exit idle_loop()
2490     AllThreadsShouldExit = true;
2491
2492     // Wait for thread termination
2493     for (int i = 1; i < MAX_THREADS; i++)
2494         while (threads[i].state != THREAD_TERMINATED) {}
2495
2496     // Now we can safely destroy the locks
2497     for (int i = 0; i < MAX_THREADS; i++)
2498         for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2499             lock_destroy(&(threads[i].splitPoints[j].lock));
2500
2501     lock_destroy(&WaitLock);
2502     lock_destroy(&MPLock);
2503   }
2504
2505
2506   // thread_should_stop() checks whether the thread should stop its search.
2507   // This can happen if a beta cutoff has occurred in the thread's currently
2508   // active split point, or in some ancestor of the current split point.
2509
2510   bool ThreadsManager::thread_should_stop(int threadID) const {
2511
2512     assert(threadID >= 0 && threadID < ActiveThreads);
2513
2514     SplitPoint* sp;
2515
2516     for (sp = threads[threadID].splitPoint; sp && !sp->stopRequest; sp = sp->parent) {}
2517     return sp != NULL;
2518   }
2519
2520
2521   // thread_is_available() checks whether the thread with threadID "slave" is
2522   // available to help the thread with threadID "master" at a split point. An
2523   // obvious requirement is that "slave" must be idle. With more than two
2524   // threads, this is not by itself sufficient:  If "slave" is the master of
2525   // some active split point, it is only available as a slave to the other
2526   // threads which are busy searching the split point at the top of "slave"'s
2527   // split point stack (the "helpful master concept" in YBWC terminology).
2528
2529   bool ThreadsManager::thread_is_available(int slave, int master) const {
2530
2531     assert(slave >= 0 && slave < ActiveThreads);
2532     assert(master >= 0 && master < ActiveThreads);
2533     assert(ActiveThreads > 1);
2534
2535     if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2536         return false;
2537
2538     // Make a local copy to be sure doesn't change under our feet
2539     int localActiveSplitPoints = threads[slave].activeSplitPoints;
2540
2541     if (localActiveSplitPoints == 0)
2542         // No active split points means that the thread is available as
2543         // a slave for any other thread.
2544         return true;
2545
2546     if (ActiveThreads == 2)
2547         return true;
2548
2549     // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2550     // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2551     // could have been set to 0 by another thread leading to an out of bound access.
2552     if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2553         return true;
2554
2555     return false;
2556   }
2557
2558
2559   // available_thread_exists() tries to find an idle thread which is available as
2560   // a slave for the thread with threadID "master".
2561
2562   bool ThreadsManager::available_thread_exists(int master) const {
2563
2564     assert(master >= 0 && master < ActiveThreads);
2565     assert(ActiveThreads > 1);
2566
2567     for (int i = 0; i < ActiveThreads; i++)
2568         if (thread_is_available(i, master))
2569             return true;
2570
2571     return false;
2572   }
2573
2574
2575   // split() does the actual work of distributing the work at a node between
2576   // several available threads. If it does not succeed in splitting the
2577   // node (because no idle threads are available, or because we have no unused
2578   // split point objects), the function immediately returns. If splitting is
2579   // possible, a SplitPoint object is initialized with all the data that must be
2580   // copied to the helper threads and we tell our helper threads that they have
2581   // been assigned work. This will cause them to instantly leave their idle loops
2582   // and call sp_search(). When all threads have returned from sp_search() then
2583   // split() returns.
2584
2585   template <bool Fake>
2586   void ThreadsManager::split(const Position& p, SearchStack* ss, int ply, Value* alpha,
2587                              const Value beta, Value* bestValue, Depth depth, Move threatMove,
2588                              bool mateThreat, int* moveCount, MovePicker* mp, bool pvNode) {
2589     assert(p.is_ok());
2590     assert(ply > 0 && ply < PLY_MAX);
2591     assert(*bestValue >= -VALUE_INFINITE);
2592     assert(*bestValue <= *alpha);
2593     assert(*alpha < beta);
2594     assert(beta <= VALUE_INFINITE);
2595     assert(depth > DEPTH_ZERO);
2596     assert(p.thread() >= 0 && p.thread() < ActiveThreads);
2597     assert(ActiveThreads > 1);
2598
2599     int i, master = p.thread();
2600     Thread& masterThread = threads[master];
2601
2602     lock_grab(&MPLock);
2603
2604     // If no other thread is available to help us, or if we have too many
2605     // active split points, don't split.
2606     if (   !available_thread_exists(master)
2607         || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2608     {
2609         lock_release(&MPLock);
2610         return;
2611     }
2612
2613     // Pick the next available split point object from the split point stack
2614     SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2615
2616     // Initialize the split point object
2617     splitPoint.parent = masterThread.splitPoint;
2618     splitPoint.stopRequest = false;
2619     splitPoint.ply = ply;
2620     splitPoint.depth = depth;
2621     splitPoint.threatMove = threatMove;
2622     splitPoint.mateThreat = mateThreat;
2623     splitPoint.alpha = *alpha;
2624     splitPoint.beta = beta;
2625     splitPoint.pvNode = pvNode;
2626     splitPoint.bestValue = *bestValue;
2627     splitPoint.mp = mp;
2628     splitPoint.moveCount = *moveCount;
2629     splitPoint.pos = &p;
2630     splitPoint.parentSstack = ss;
2631     for (i = 0; i < ActiveThreads; i++)
2632         splitPoint.slaves[i] = 0;
2633
2634     masterThread.splitPoint = &splitPoint;
2635
2636     // If we are here it means we are not available
2637     assert(masterThread.state != THREAD_AVAILABLE);
2638
2639     int workersCnt = 1; // At least the master is included
2640
2641     // Allocate available threads setting state to THREAD_BOOKED
2642     for (i = 0; !Fake && i < ActiveThreads && workersCnt < MaxThreadsPerSplitPoint; i++)
2643         if (thread_is_available(i, master))
2644         {
2645             threads[i].state = THREAD_BOOKED;
2646             threads[i].splitPoint = &splitPoint;
2647             splitPoint.slaves[i] = 1;
2648             workersCnt++;
2649         }
2650
2651     assert(Fake || workersCnt > 1);
2652
2653     // We can release the lock because slave threads are already booked and master is not available
2654     lock_release(&MPLock);
2655
2656     // Tell the threads that they have work to do. This will make them leave
2657     // their idle loop. But before copy search stack tail for each thread.
2658     for (i = 0; i < ActiveThreads; i++)
2659         if (i == master || splitPoint.slaves[i])
2660         {
2661             memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
2662
2663             assert(i == master || threads[i].state == THREAD_BOOKED);
2664
2665             threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2666         }
2667
2668     // Everything is set up. The master thread enters the idle loop, from
2669     // which it will instantly launch a search, because its state is
2670     // THREAD_WORKISWAITING.  We send the split point as a second parameter to the
2671     // idle loop, which means that the main thread will return from the idle
2672     // loop when all threads have finished their work at this split point.
2673     idle_loop(master, &splitPoint);
2674
2675     // We have returned from the idle loop, which means that all threads are
2676     // finished. Update alpha and bestValue, and return.
2677     lock_grab(&MPLock);
2678
2679     *alpha = splitPoint.alpha;
2680     *bestValue = splitPoint.bestValue;
2681     masterThread.activeSplitPoints--;
2682     masterThread.splitPoint = splitPoint.parent;
2683
2684     lock_release(&MPLock);
2685   }
2686
2687
2688   // wake_sleeping_threads() wakes up all sleeping threads when it is time
2689   // to start a new search from the root.
2690
2691   void ThreadsManager::wake_sleeping_threads() {
2692
2693     assert(AllThreadsShouldSleep);
2694     assert(ActiveThreads > 0);
2695
2696     AllThreadsShouldSleep = false;
2697
2698     if (ActiveThreads == 1)
2699         return;
2700
2701 #if !defined(_MSC_VER)
2702     pthread_mutex_lock(&WaitLock);
2703     pthread_cond_broadcast(&WaitCond);
2704     pthread_mutex_unlock(&WaitLock);
2705 #else
2706     for (int i = 1; i < MAX_THREADS; i++)
2707         SetEvent(SitIdleEvent[i]);
2708 #endif
2709
2710   }
2711
2712
2713   // put_threads_to_sleep() makes all the threads go to sleep just before
2714   // to leave think(), at the end of the search. Threads should have already
2715   // finished the job and should be idle.
2716
2717   void ThreadsManager::put_threads_to_sleep() {
2718
2719     assert(!AllThreadsShouldSleep);
2720
2721     // This makes the threads to go to sleep
2722     AllThreadsShouldSleep = true;
2723   }
2724
2725   /// The RootMoveList class
2726
2727   // RootMoveList c'tor
2728
2729   RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
2730
2731     SearchStack ss[PLY_MAX_PLUS_2];
2732     MoveStack mlist[MaxRootMoves];
2733     StateInfo st;
2734     bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
2735
2736     // Initialize search stack
2737     init_ss_array(ss, PLY_MAX_PLUS_2);
2738     ss[0].currentMove = ss[0].bestMove = MOVE_NONE;
2739     ss[0].eval = VALUE_NONE;
2740
2741     // Generate all legal moves
2742     MoveStack* last = generate_moves(pos, mlist);
2743
2744     // Add each move to the moves[] array
2745     for (MoveStack* cur = mlist; cur != last; cur++)
2746     {
2747         bool includeMove = includeAllMoves;
2748
2749         for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
2750             includeMove = (searchMoves[k] == cur->move);
2751
2752         if (!includeMove)
2753             continue;
2754
2755         // Find a quick score for the move
2756         pos.do_move(cur->move, st);
2757         ss[0].currentMove = cur->move;
2758         moves[count].move = cur->move;
2759         moves[count].score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
2760         moves[count].pv[0] = cur->move;
2761         moves[count].pv[1] = MOVE_NONE;
2762         pos.undo_move(cur->move);
2763         count++;
2764     }
2765     sort();
2766   }
2767
2768   // Score root moves using the standard way used in main search, the moves
2769   // are scored according to the order in which are returned by MovePicker.
2770
2771   void RootMoveList::score_moves(const Position& pos)
2772   {
2773       Move move;
2774       int score = 1000;
2775       MovePicker mp = MovePicker(pos, MOVE_NONE, ONE_PLY, H);
2776
2777       while ((move = mp.get_next_move()) != MOVE_NONE)
2778           for (int i = 0; i < count; i++)
2779               if (moves[i].move == move)
2780               {
2781                   moves[i].mp_score = score--;
2782                   break;
2783               }
2784   }
2785
2786   // RootMoveList simple methods definitions
2787
2788   void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
2789
2790     int j;
2791
2792     for (j = 0; pv[j] != MOVE_NONE; j++)
2793         moves[moveNum].pv[j] = pv[j];
2794
2795     moves[moveNum].pv[j] = MOVE_NONE;
2796   }
2797
2798
2799   // RootMoveList::sort() sorts the root move list at the beginning of a new
2800   // iteration.
2801
2802   void RootMoveList::sort() {
2803
2804     sort_multipv(count - 1); // Sort all items
2805   }
2806
2807
2808   // RootMoveList::sort_multipv() sorts the first few moves in the root move
2809   // list by their scores and depths. It is used to order the different PVs
2810   // correctly in MultiPV mode.
2811
2812   void RootMoveList::sort_multipv(int n) {
2813
2814     int i,j;
2815
2816     for (i = 1; i <= n; i++)
2817     {
2818         RootMove rm = moves[i];
2819         for (j = i; j > 0 && moves[j - 1] < rm; j--)
2820             moves[j] = moves[j - 1];
2821
2822         moves[j] = rm;
2823     }
2824   }
2825
2826 } // namspace