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