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