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