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