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