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