Move MovePickerExt specializations away from headings
[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 #include <cassert>
21 #include <cmath>
22 #include <cstring>
23 #include <fstream>
24 #include <iostream>
25 #include <sstream>
26 #include <vector>
27
28 #include "book.h"
29 #include "evaluate.h"
30 #include "history.h"
31 #include "misc.h"
32 #include "move.h"
33 #include "movegen.h"
34 #include "movepick.h"
35 #include "search.h"
36 #include "timeman.h"
37 #include "thread.h"
38 #include "tt.h"
39 #include "ucioption.h"
40
41 using std::cout;
42 using std::endl;
43
44 namespace {
45
46   // Set to true to force running with one thread. Used for debugging
47   const bool FakeSplit = false;
48
49   // Different node types, used as template parameter
50   enum NodeType { NonPV, PV };
51
52   // RootMove struct is used for moves at the root of the tree. For each root
53   // move, we store two scores, a node count, and a PV (really a refutation
54   // in the case of moves which fail low). Value pv_score is normally set at
55   // -VALUE_INFINITE for all non-pv moves, while non_pv_score is computed
56   // according to the order in which moves are returned by MovePicker.
57   struct RootMove {
58
59     RootMove();
60     RootMove(const RootMove& rm) { *this = rm; }
61     RootMove& operator=(const RootMove& rm);
62
63     // RootMove::operator<() is the comparison function used when
64     // sorting the moves. A move m1 is considered to be better
65     // than a move m2 if it has an higher pv_score, or if it has
66     // equal pv_score but m1 has the higher non_pv_score. In this way
67     // we are guaranteed that PV moves are always sorted as first.
68     bool operator<(const RootMove& m) const {
69       return pv_score != m.pv_score ? pv_score < m.pv_score
70                                     : non_pv_score < m.non_pv_score;
71     }
72
73     void extract_pv_from_tt(Position& pos);
74     void insert_pv_in_tt(Position& pos);
75     std::string pv_info_to_uci(Position& pos, int depth, int selDepth,
76                                Value alpha, Value beta, int pvIdx);
77     int64_t nodes;
78     Value pv_score;
79     Value non_pv_score;
80     Move pv[PLY_MAX_PLUS_2];
81   };
82
83   // RootMoveList struct is just a vector of RootMove objects,
84   // with an handful of methods above the standard ones.
85   struct RootMoveList : public std::vector<RootMove> {
86
87     typedef std::vector<RootMove> Base;
88
89     void init(Position& pos, Move searchMoves[]);
90     void sort() { insertion_sort<RootMove, Base::iterator>(begin(), end()); }
91     void sort_multipv(int n) { insertion_sort<RootMove, Base::iterator>(begin(), begin() + n); }
92
93     int bestMoveChanges;
94   };
95
96   // MovePickerExt template class extends MovePicker and allows to choose at compile
97   // time the proper moves source according to the type of node. In the default case
98   // we simply create and use a standard MovePicker object.
99   template<bool SpNode, bool Root> struct MovePickerExt : public MovePicker {
100
101     MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b)
102                   : MovePicker(p, ttm, d, h, ss, b) {}
103
104     RootMoveList::iterator rm; // Dummy, needed to compile
105   };
106
107   // In case of a SpNode we use split point's shared MovePicker object as moves source
108   template<> struct MovePickerExt<true, false> : public MovePicker {
109
110     MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b)
111                   : MovePicker(p, ttm, d, h, ss, b), mp(ss->sp->mp) {}
112
113     Move get_next_move() { return mp->get_next_move(); }
114
115     RootMoveList::iterator rm; // Dummy, needed to compile
116     MovePicker* mp;
117   };
118
119   // In case of a Root node we use RootMoveList as moves source
120   template<> struct MovePickerExt<false, true> : public MovePicker {
121
122     MovePickerExt(const Position&, Move, Depth, const History&, SearchStack*, Value);
123     Move get_next_move();
124
125     RootMoveList::iterator rm;
126     bool firstCall;
127   };
128
129
130   /// Constants
131
132   // Lookup table to check if a Piece is a slider and its access function
133   const bool Slidings[18] = { 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1 };
134   inline bool piece_is_slider(Piece p) { return Slidings[p]; }
135
136   // Step 6. Razoring
137
138   // Maximum depth for razoring
139   const Depth RazorDepth = 4 * ONE_PLY;
140
141   // Dynamic razoring margin based on depth
142   inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
143
144   // Maximum depth for use of dynamic threat detection when null move fails low
145   const Depth ThreatDepth = 5 * ONE_PLY;
146
147   // Step 9. Internal iterative deepening
148
149   // Minimum depth for use of internal iterative deepening
150   const Depth IIDDepth[] = { 8 * ONE_PLY, 5 * ONE_PLY };
151
152   // At Non-PV nodes we do an internal iterative deepening search
153   // when the static evaluation is bigger then beta - IIDMargin.
154   const Value IIDMargin = Value(0x100);
155
156   // Step 11. Decide the new search depth
157
158   // Extensions. Array index 0 is used for non-PV nodes, index 1 for PV nodes
159   const Depth CheckExtension[]         = { ONE_PLY / 2, ONE_PLY / 1 };
160   const Depth PawnEndgameExtension[]   = { ONE_PLY / 1, ONE_PLY / 1 };
161   const Depth PawnPushTo7thExtension[] = { ONE_PLY / 2, ONE_PLY / 2 };
162   const Depth PassedPawnExtension[]    = {  DEPTH_ZERO, ONE_PLY / 2 };
163
164   // Minimum depth for use of singular extension
165   const Depth SingularExtensionDepth[] = { 8 * ONE_PLY, 6 * ONE_PLY };
166
167   // Step 12. Futility pruning
168
169   // Futility margin for quiescence search
170   const Value FutilityMarginQS = Value(0x80);
171
172   // Futility lookup tables (initialized at startup) and their access functions
173   Value FutilityMargins[16][64]; // [depth][moveNumber]
174   int FutilityMoveCounts[32];    // [depth]
175
176   inline Value futility_margin(Depth d, int mn) {
177
178     return d < 7 * ONE_PLY ? FutilityMargins[Max(d, 1)][Min(mn, 63)]
179                            : 2 * VALUE_INFINITE;
180   }
181
182   inline int futility_move_count(Depth d) {
183
184     return d < 16 * ONE_PLY ? FutilityMoveCounts[d] : MAX_MOVES;
185   }
186
187   // Step 14. Reduced search
188
189   // Reduction lookup tables (initialized at startup) and their access function
190   int8_t Reductions[2][64][64]; // [pv][depth][moveNumber]
191
192   template <NodeType PV> inline Depth reduction(Depth d, int mn) {
193
194     return (Depth) Reductions[PV][Min(d / ONE_PLY, 63)][Min(mn, 63)];
195   }
196
197   // Easy move margin. An easy move candidate must be at least this much
198   // better than the second best move.
199   const Value EasyMoveMargin = Value(0x200);
200
201
202   /// Namespace variables
203
204   // Book
205   Book OpeningBook;
206
207   // Root move list
208   RootMoveList Rml;
209
210   // MultiPV mode
211   int MultiPV, UCIMultiPV;
212
213   // Time management variables
214   bool StopOnPonderhit, FirstRootMove, StopRequest, QuitRequest, AspirationFailLow;
215   TimeManager TimeMgr;
216   SearchLimits Limits;
217
218   // Log file
219   std::ofstream LogFile;
220
221   // Skill level adjustment
222   int SkillLevel;
223   bool SkillLevelEnabled;
224   RKISS RK;
225
226   // Node counters, used only by thread[0] but try to keep in different cache
227   // lines (64 bytes each) from the heavy multi-thread read accessed variables.
228   bool SendSearchedNodes;
229   int NodesSincePoll;
230   int NodesBetweenPolls = 30000;
231
232   // History table
233   History H;
234
235
236   /// Local functions
237
238   Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove);
239
240   template <NodeType PvNode, bool SpNode, bool Root>
241   Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth);
242
243   template <NodeType PvNode>
244   Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth);
245
246   template <NodeType PvNode>
247   inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) {
248
249     return depth < ONE_PLY ? qsearch<PvNode>(pos, ss, alpha, beta, DEPTH_ZERO)
250                            : search<PvNode, false, false>(pos, ss, alpha, beta, depth);
251   }
252
253   template <NodeType PvNode>
254   Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool* dangerous);
255
256   bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue);
257   bool connected_moves(const Position& pos, Move m1, Move m2);
258   Value value_to_tt(Value v, int ply);
259   Value value_from_tt(Value v, int ply);
260   bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
261   bool connected_threat(const Position& pos, Move m, Move threat);
262   Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
263   void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
264   void update_gains(const Position& pos, Move move, Value before, Value after);
265   void do_skill_level(Move* best, Move* ponder);
266
267   int current_search_time(int set = 0);
268   std::string value_to_uci(Value v);
269   std::string speed_to_uci(int64_t nodes);
270   void poll(const Position& pos);
271   void wait_for_stop_or_ponderhit();
272
273   // Overload operator<<() to make it easier to print moves in a coordinate
274   // notation compatible with UCI protocol.
275   std::ostream& operator<<(std::ostream& os, Move m) {
276
277     bool chess960 = (os.iword(0) != 0); // See set960()
278     return os << move_to_uci(m, chess960);
279   }
280
281   // When formatting a move for std::cout we must know if we are in Chess960
282   // or not. To keep using the handy operator<<() on the move the trick is to
283   // embed this flag in the stream itself. Function-like named enum set960 is
284   // used as a custom manipulator and the stream internal general-purpose array,
285   // accessed through ios_base::iword(), is used to pass the flag to the move's
286   // operator<<() that will read it to properly format castling moves.
287   enum set960 {};
288
289   std::ostream& operator<< (std::ostream& os, const set960& f) {
290
291     os.iword(0) = int(f);
292     return os;
293   }
294
295 } // namespace
296
297
298 /// init_search() is called during startup to initialize various lookup tables
299
300 void init_search() {
301
302   int d;  // depth (ONE_PLY == 2)
303   int hd; // half depth (ONE_PLY == 1)
304   int mc; // moveCount
305
306   // Init reductions array
307   for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
308   {
309       double    pvRed = log(double(hd)) * log(double(mc)) / 3.0;
310       double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
311       Reductions[PV][hd][mc]    = (int8_t) (   pvRed >= 1.0 ? floor(   pvRed * int(ONE_PLY)) : 0);
312       Reductions[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0);
313   }
314
315   // Init futility margins array
316   for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
317       FutilityMargins[d][mc] = Value(112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45);
318
319   // Init futility move count array
320   for (d = 0; d < 32; d++)
321       FutilityMoveCounts[d] = int(3.001 + 0.25 * pow(d, 2.0));
322 }
323
324
325 /// perft() is our utility to verify move generation. All the legal moves up to
326 /// given depth are generated and counted and the sum returned.
327
328 int64_t perft(Position& pos, Depth depth) {
329
330   MoveStack mlist[MAX_MOVES];
331   StateInfo st;
332   Move m;
333   int64_t sum = 0;
334
335   // Generate all legal moves
336   MoveStack* last = generate<MV_LEGAL>(pos, mlist);
337
338   // If we are at the last ply we don't need to do and undo
339   // the moves, just to count them.
340   if (depth <= ONE_PLY)
341       return int(last - mlist);
342
343   // Loop through all legal moves
344   CheckInfo ci(pos);
345   for (MoveStack* cur = mlist; cur != last; cur++)
346   {
347       m = cur->move;
348       pos.do_move(m, st, ci, pos.move_is_check(m, ci));
349       sum += perft(pos, depth - ONE_PLY);
350       pos.undo_move(m);
351   }
352   return sum;
353 }
354
355
356 /// think() is the external interface to Stockfish's search, and is called when
357 /// the program receives the UCI 'go' command. It initializes various global
358 /// variables, and calls id_loop(). It returns false when a "quit" command is
359 /// received during the search.
360
361 bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) {
362
363   // Initialize global search-related variables
364   StopOnPonderhit = StopRequest = QuitRequest = AspirationFailLow = SendSearchedNodes = false;
365   NodesSincePoll = 0;
366   current_search_time(get_system_time());
367   Limits = limits;
368   TimeMgr.init(Limits, pos.startpos_ply_counter());
369
370   // Set best NodesBetweenPolls interval to avoid lagging under time pressure
371   if (Limits.maxNodes)
372       NodesBetweenPolls = Min(Limits.maxNodes, 30000);
373   else if (Limits.time && Limits.time < 1000)
374       NodesBetweenPolls = 1000;
375   else if (Limits.time && Limits.time < 5000)
376       NodesBetweenPolls = 5000;
377   else
378       NodesBetweenPolls = 30000;
379
380   // Look for a book move
381   if (Options["OwnBook"].value<bool>())
382   {
383       if (Options["Book File"].value<std::string>() != OpeningBook.name())
384           OpeningBook.open(Options["Book File"].value<std::string>());
385
386       Move bookMove = OpeningBook.get_move(pos, Options["Best Book Move"].value<bool>());
387       if (bookMove != MOVE_NONE)
388       {
389           if (Limits.ponder)
390               wait_for_stop_or_ponderhit();
391
392           cout << "bestmove " << bookMove << endl;
393           return !QuitRequest;
394       }
395   }
396
397   // Read UCI options
398   UCIMultiPV = Options["MultiPV"].value<int>();
399   SkillLevel = Options["Skill level"].value<int>();
400
401   read_evaluation_uci_options(pos.side_to_move());
402   Threads.read_uci_options();
403
404   // If needed allocate pawn and material hash tables and adjust TT size
405   Threads.init_hash_tables();
406   TT.set_size(Options["Hash"].value<int>());
407
408   if (Options["Clear Hash"].value<bool>())
409   {
410       Options["Clear Hash"].set_value("false");
411       TT.clear();
412   }
413
414   // Do we have to play with skill handicap? In this case enable MultiPV that
415   // we will use behind the scenes to retrieve a set of possible moves.
416   SkillLevelEnabled = (SkillLevel < 20);
417   MultiPV = (SkillLevelEnabled ? Max(UCIMultiPV, 4) : UCIMultiPV);
418
419   // Wake up needed threads and reset maxPly counter
420   for (int i = 0; i < Threads.size(); i++)
421   {
422       Threads[i].wake_up();
423       Threads[i].maxPly = 0;
424   }
425
426   // Write to log file and keep it open to be accessed during the search
427   if (Options["Use Search Log"].value<bool>())
428   {
429       std::string name = Options["Search Log Filename"].value<std::string>();
430       LogFile.open(name.c_str(), std::ios::out | std::ios::app);
431
432       if (LogFile.is_open())
433           LogFile << "\nSearching: "  << pos.to_fen()
434                   << "\ninfinite: "   << Limits.infinite
435                   << " ponder: "      << Limits.ponder
436                   << " time: "        << Limits.time
437                   << " increment: "   << Limits.increment
438                   << " moves to go: " << Limits.movesToGo
439                   << endl;
440   }
441
442   // We're ready to start thinking. Call the iterative deepening loop function
443   Move ponderMove = MOVE_NONE;
444   Move bestMove = id_loop(pos, searchMoves, &ponderMove);
445
446   cout << "info" << speed_to_uci(pos.nodes_searched()) << endl;
447
448   // Write final search statistics and close log file
449   if (LogFile.is_open())
450   {
451       int t = current_search_time();
452
453       LogFile << "Nodes: "          << pos.nodes_searched()
454               << "\nNodes/second: " << (t > 0 ? pos.nodes_searched() * 1000 / t : 0)
455               << "\nBest move: "    << move_to_san(pos, bestMove);
456
457       StateInfo st;
458       pos.do_move(bestMove, st);
459       LogFile << "\nPonder move: " << move_to_san(pos, ponderMove) << endl;
460       pos.undo_move(bestMove); // Return from think() with unchanged position
461       LogFile.close();
462   }
463
464   // This makes all the threads to go to sleep
465   Threads.set_size(1);
466
467   // If we are pondering or in infinite search, we shouldn't print the
468   // best move before we are told to do so.
469   if (!StopRequest && (Limits.ponder || Limits.infinite))
470       wait_for_stop_or_ponderhit();
471
472   // Could be MOVE_NONE when searching on a stalemate position
473   cout << "bestmove " << bestMove;
474
475   // UCI protol is not clear on allowing sending an empty ponder move, instead
476   // it is clear that ponder move is optional. So skip it if empty.
477   if (ponderMove != MOVE_NONE)
478       cout << " ponder " << ponderMove;
479
480   cout << endl;
481
482   return !QuitRequest;
483 }
484
485
486 namespace {
487
488   // id_loop() is the main iterative deepening loop. It calls search() repeatedly
489   // with increasing depth until the allocated thinking time has been consumed,
490   // user stops the search, or the maximum search depth is reached.
491
492   Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove) {
493
494     SearchStack ss[PLY_MAX_PLUS_2];
495     Value bestValues[PLY_MAX_PLUS_2];
496     int bestMoveChanges[PLY_MAX_PLUS_2];
497     int depth, selDepth, aspirationDelta;
498     Value value, alpha, beta;
499     Move bestMove, easyMove, skillBest, skillPonder;
500
501     // Initialize stuff before a new search
502     memset(ss, 0, 4 * sizeof(SearchStack));
503     TT.new_search();
504     H.clear();
505     *ponderMove = bestMove = easyMove = skillBest = skillPonder = MOVE_NONE;
506     depth = aspirationDelta = 0;
507     alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
508     ss->currentMove = MOVE_NULL; // Hack to skip update_gains()
509
510     // Moves to search are verified and copied
511     Rml.init(pos, searchMoves);
512
513     // Handle special case of searching on a mate/stalemate position
514     if (Rml.size() == 0)
515     {
516         cout << "info depth 0 score "
517              << value_to_uci(pos.is_check() ? -VALUE_MATE : VALUE_DRAW)
518              << endl;
519
520         return MOVE_NONE;
521     }
522
523     // Iterative deepening loop until requested to stop or target depth reached
524     while (!StopRequest && ++depth <= PLY_MAX && (!Limits.maxDepth || depth <= Limits.maxDepth))
525     {
526         Rml.bestMoveChanges = 0;
527         cout << set960(pos.is_chess960()) << "info depth " << depth << endl;
528
529         // Calculate dynamic aspiration window based on previous iterations
530         if (MultiPV == 1 && depth >= 5 && abs(bestValues[depth - 1]) < VALUE_KNOWN_WIN)
531         {
532             int prevDelta1 = bestValues[depth - 1] - bestValues[depth - 2];
533             int prevDelta2 = bestValues[depth - 2] - bestValues[depth - 3];
534
535             aspirationDelta = Min(Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16), 24);
536             aspirationDelta = (aspirationDelta + 7) / 8 * 8; // Round to match grainSize
537
538             alpha = Max(bestValues[depth - 1] - aspirationDelta, -VALUE_INFINITE);
539             beta  = Min(bestValues[depth - 1] + aspirationDelta,  VALUE_INFINITE);
540         }
541
542         // Start with a small aspiration window and, in case of fail high/low,
543         // research with bigger window until not failing high/low anymore.
544         do {
545             // Search starting from ss+1 to allow calling update_gains()
546             value = search<PV, false, true>(pos, ss+1, alpha, beta, depth * ONE_PLY);
547
548             // Write PV back to transposition table in case the relevant entries
549             // have been overwritten during the search.
550             for (int i = 0; i < Min(MultiPV, (int)Rml.size()); i++)
551                 Rml[i].insert_pv_in_tt(pos);
552
553             // Value cannot be trusted. Break out immediately!
554             if (StopRequest)
555                 break;
556
557             assert(value >= alpha);
558
559             // In case of failing high/low increase aspiration window and research,
560             // otherwise exit the fail high/low loop.
561             if (value >= beta)
562             {
563                 beta = Min(beta + aspirationDelta, VALUE_INFINITE);
564                 aspirationDelta += aspirationDelta / 2;
565             }
566             else if (value <= alpha)
567             {
568                 AspirationFailLow = true;
569                 StopOnPonderhit = false;
570
571                 alpha = Max(alpha - aspirationDelta, -VALUE_INFINITE);
572                 aspirationDelta += aspirationDelta / 2;
573             }
574             else
575                 break;
576
577         } while (abs(value) < VALUE_KNOWN_WIN);
578
579         // Collect info about search result
580         bestMove = Rml[0].pv[0];
581         *ponderMove = Rml[0].pv[1];
582         bestValues[depth] = value;
583         bestMoveChanges[depth] = Rml.bestMoveChanges;
584
585         // Do we need to pick now the best and the ponder moves ?
586         if (SkillLevelEnabled && depth == 1 + SkillLevel)
587             do_skill_level(&skillBest, &skillPonder);
588
589         // Retrieve max searched depth among threads
590         selDepth = 0;
591         for (int i = 0; i < Threads.size(); i++)
592             if (Threads[i].maxPly > selDepth)
593                 selDepth = Threads[i].maxPly;
594
595         // Send PV line to GUI and to log file
596         for (int i = 0; i < Min(UCIMultiPV, (int)Rml.size()); i++)
597             cout << Rml[i].pv_info_to_uci(pos, depth, selDepth, alpha, beta, i) << endl;
598
599         if (LogFile.is_open())
600             LogFile << pretty_pv(pos, depth, value, current_search_time(), Rml[0].pv) << endl;
601
602         // Init easyMove after first iteration or drop if differs from the best move
603         if (depth == 1 && (Rml.size() == 1 || Rml[0].pv_score > Rml[1].pv_score + EasyMoveMargin))
604             easyMove = bestMove;
605         else if (bestMove != easyMove)
606             easyMove = MOVE_NONE;
607
608         // Check for some early stop condition
609         if (!StopRequest && Limits.useTimeManagement())
610         {
611             // Stop search early when the last two iterations returned a mate score
612             if (   depth >= 5
613                 && abs(bestValues[depth])     >= VALUE_MATE_IN_PLY_MAX
614                 && abs(bestValues[depth - 1]) >= VALUE_MATE_IN_PLY_MAX)
615                 StopRequest = true;
616
617             // Stop search early if one move seems to be much better than the
618             // others or if there is only a single legal move. Also in the latter
619             // case we search up to some depth anyway to get a proper score.
620             if (   depth >= 7
621                 && easyMove == bestMove
622                 && (   Rml.size() == 1
623                     ||(   Rml[0].nodes > (pos.nodes_searched() * 85) / 100
624                        && current_search_time() > TimeMgr.available_time() / 16)
625                     ||(   Rml[0].nodes > (pos.nodes_searched() * 98) / 100
626                        && current_search_time() > TimeMgr.available_time() / 32)))
627                 StopRequest = true;
628
629             // Take in account some extra time if the best move has changed
630             if (depth > 4 && depth < 50)
631                 TimeMgr.pv_instability(bestMoveChanges[depth], bestMoveChanges[depth - 1]);
632
633             // Stop search if most of available time is already consumed. We probably don't
634             // have enough time to search the first move at the next iteration anyway.
635             if (current_search_time() > (TimeMgr.available_time() * 62) / 100)
636                 StopRequest = true;
637
638             // If we are allowed to ponder do not stop the search now but keep pondering
639             if (StopRequest && Limits.ponder)
640             {
641                 StopRequest = false;
642                 StopOnPonderhit = true;
643             }
644         }
645     }
646
647     // When using skills overwrite best and ponder moves with the sub-optimal ones
648     if (SkillLevelEnabled)
649     {
650         if (skillBest == MOVE_NONE) // Still unassigned ?
651             do_skill_level(&skillBest, &skillPonder);
652
653         bestMove = skillBest;
654         *ponderMove = skillPonder;
655     }
656
657     return bestMove;
658   }
659
660
661   // search<>() is the main search function for both PV and non-PV nodes and for
662   // normal and SplitPoint nodes. When called just after a split point the search
663   // is simpler because we have already probed the hash table, done a null move
664   // search, and searched the first move before splitting, we don't have to repeat
665   // all this work again. We also don't need to store anything to the hash table
666   // here: This is taken care of after we return from the split point.
667
668   template <NodeType PvNode, bool SpNode, bool Root>
669   Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) {
670
671     assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
672     assert(beta > alpha && beta <= VALUE_INFINITE);
673     assert(PvNode || alpha == beta - 1);
674     assert(pos.thread() >= 0 && pos.thread() < Threads.size());
675
676     Move movesSearched[MAX_MOVES];
677     int64_t nodes;
678     StateInfo st;
679     const TTEntry *tte;
680     Key posKey;
681     Move ttMove, move, excludedMove, threatMove;
682     Depth ext, newDepth;
683     ValueType vt;
684     Value bestValue, value, oldAlpha;
685     Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
686     bool isPvMove, isCheck, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous, isBadCap;
687     int moveCount = 0, playedMoveCount = 0;
688     int threadID = pos.thread();
689     SplitPoint* sp = NULL;
690
691     refinedValue = bestValue = value = -VALUE_INFINITE;
692     oldAlpha = alpha;
693     isCheck = pos.is_check();
694     ss->ply = (ss-1)->ply + 1;
695
696     // Used to send selDepth info to GUI
697     if (PvNode && Threads[threadID].maxPly < ss->ply)
698         Threads[threadID].maxPly = ss->ply;
699
700     if (SpNode)
701     {
702         sp = ss->sp;
703         tte = NULL;
704         ttMove = excludedMove = MOVE_NONE;
705         threatMove = sp->threatMove;
706         goto split_point_start;
707     }
708     else if (Root)
709         bestValue = alpha;
710
711     // Step 1. Initialize node and poll. Polling can abort search
712     ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE;
713     (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO;
714     (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
715
716     if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
717     {
718         NodesSincePoll = 0;
719         poll(pos);
720     }
721
722     // Step 2. Check for aborted search and immediate draw
723     if ((   StopRequest
724          || Threads[threadID].cutoff_occurred()
725          || pos.is_draw()
726          || ss->ply > PLY_MAX) && !Root)
727         return VALUE_DRAW;
728
729     // Step 3. Mate distance pruning
730     alpha = Max(value_mated_in(ss->ply), alpha);
731     beta = Min(value_mate_in(ss->ply+1), beta);
732     if (alpha >= beta)
733         return alpha;
734
735     // Step 4. Transposition table lookup
736     // We don't want the score of a partial search to overwrite a previous full search
737     // TT value, so we use a different position key in case of an excluded move.
738     excludedMove = ss->excludedMove;
739     posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
740
741     tte = TT.retrieve(posKey);
742     ttMove = tte ? tte->move() : MOVE_NONE;
743
744     // At PV nodes we check for exact scores, while at non-PV nodes we check for
745     // a fail high/low. Biggest advantage at probing at PV nodes is to have a
746     // smooth experience in analysis mode.
747     if (   !Root
748         && tte
749         && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT
750                    : ok_to_use_TT(tte, depth, beta, ss->ply)))
751     {
752         TT.refresh(tte);
753         ss->bestMove = ttMove; // Can be MOVE_NONE
754         return value_from_tt(tte->value(), ss->ply);
755     }
756
757     // Step 5. Evaluate the position statically and update parent's gain statistics
758     if (isCheck)
759         ss->eval = ss->evalMargin = VALUE_NONE;
760     else if (tte)
761     {
762         assert(tte->static_value() != VALUE_NONE);
763
764         ss->eval = tte->static_value();
765         ss->evalMargin = tte->static_value_margin();
766         refinedValue = refine_eval(tte, ss->eval, ss->ply);
767     }
768     else
769     {
770         refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
771         TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
772     }
773
774     // Save gain for the parent non-capture move
775     update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
776
777     // Step 6. Razoring (is omitted in PV nodes)
778     if (   !PvNode
779         &&  depth < RazorDepth
780         && !isCheck
781         &&  refinedValue + razor_margin(depth) < beta
782         &&  ttMove == MOVE_NONE
783         &&  abs(beta) < VALUE_MATE_IN_PLY_MAX
784         && !pos.has_pawn_on_7th(pos.side_to_move()))
785     {
786         Value rbeta = beta - razor_margin(depth);
787         Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO);
788         if (v < rbeta)
789             // Logically we should return (v + razor_margin(depth)), but
790             // surprisingly this did slightly weaker in tests.
791             return v;
792     }
793
794     // Step 7. Static null move pruning (is omitted in PV nodes)
795     // We're betting that the opponent doesn't have a move that will reduce
796     // the score by more than futility_margin(depth) if we do a null move.
797     if (   !PvNode
798         && !ss->skipNullMove
799         &&  depth < RazorDepth
800         && !isCheck
801         &&  refinedValue - futility_margin(depth, 0) >= beta
802         &&  abs(beta) < VALUE_MATE_IN_PLY_MAX
803         &&  pos.non_pawn_material(pos.side_to_move()))
804         return refinedValue - futility_margin(depth, 0);
805
806     // Step 8. Null move search with verification search (is omitted in PV nodes)
807     if (   !PvNode
808         && !ss->skipNullMove
809         &&  depth > ONE_PLY
810         && !isCheck
811         &&  refinedValue >= beta
812         &&  abs(beta) < VALUE_MATE_IN_PLY_MAX
813         &&  pos.non_pawn_material(pos.side_to_move()))
814     {
815         ss->currentMove = MOVE_NULL;
816
817         // Null move dynamic reduction based on depth
818         int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
819
820         // Null move dynamic reduction based on value
821         if (refinedValue - PawnValueMidgame > beta)
822             R++;
823
824         pos.do_null_move(st);
825         (ss+1)->skipNullMove = true;
826         nullValue = -search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY);
827         (ss+1)->skipNullMove = false;
828         pos.undo_null_move();
829
830         if (nullValue >= beta)
831         {
832             // Do not return unproven mate scores
833             if (nullValue >= VALUE_MATE_IN_PLY_MAX)
834                 nullValue = beta;
835
836             if (depth < 6 * ONE_PLY)
837                 return nullValue;
838
839             // Do verification search at high depths
840             ss->skipNullMove = true;
841             Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY);
842             ss->skipNullMove = false;
843
844             if (v >= beta)
845                 return nullValue;
846         }
847         else
848         {
849             // The null move failed low, which means that we may be faced with
850             // some kind of threat. If the previous move was reduced, check if
851             // the move that refuted the null move was somehow connected to the
852             // move which was reduced. If a connection is found, return a fail
853             // low score (which will cause the reduced move to fail high in the
854             // parent node, which will trigger a re-search with full depth).
855             threatMove = (ss+1)->bestMove;
856
857             if (   depth < ThreatDepth
858                 && (ss-1)->reduction
859                 && threatMove != MOVE_NONE
860                 && connected_moves(pos, (ss-1)->currentMove, threatMove))
861                 return beta - 1;
862         }
863     }
864
865     // Step 9. Internal iterative deepening
866     if (   depth >= IIDDepth[PvNode]
867         && ttMove == MOVE_NONE
868         && (PvNode || (!isCheck && ss->eval + IIDMargin >= beta)))
869     {
870         Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
871
872         ss->skipNullMove = true;
873         search<PvNode>(pos, ss, alpha, beta, d);
874         ss->skipNullMove = false;
875
876         ttMove = ss->bestMove;
877         tte = TT.retrieve(posKey);
878     }
879
880 split_point_start: // At split points actual search starts from here
881
882     // Initialize a MovePicker object for the current position
883     MovePickerExt<SpNode, Root> mp(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
884     CheckInfo ci(pos);
885     ss->bestMove = MOVE_NONE;
886     futilityBase = ss->eval + ss->evalMargin;
887     singularExtensionNode =   !Root
888                            && !SpNode
889                            && depth >= SingularExtensionDepth[PvNode]
890                            && tte
891                            && tte->move()
892                            && !excludedMove // Do not allow recursive singular extension search
893                            && (tte->type() & VALUE_TYPE_LOWER)
894                            && tte->depth() >= depth - 3 * ONE_PLY;
895     if (SpNode)
896     {
897         lock_grab(&(sp->lock));
898         bestValue = sp->bestValue;
899     }
900
901     // Step 10. Loop through moves
902     // Loop through all legal moves until no moves remain or a beta cutoff occurs
903     while (   bestValue < beta
904            && (move = mp.get_next_move()) != MOVE_NONE
905            && !Threads[threadID].cutoff_occurred())
906     {
907       assert(move_is_ok(move));
908
909       if (SpNode)
910       {
911           moveCount = ++sp->moveCount;
912           lock_release(&(sp->lock));
913       }
914       else if (move == excludedMove)
915           continue;
916       else
917           moveCount++;
918
919       if (Root)
920       {
921           // This is used by time management
922           FirstRootMove = (moveCount == 1);
923
924           // Save the current node count before the move is searched
925           nodes = pos.nodes_searched();
926
927           // If it's time to send nodes info, do it here where we have the
928           // correct accumulated node counts searched by each thread.
929           if (SendSearchedNodes)
930           {
931               SendSearchedNodes = false;
932               cout << "info" << speed_to_uci(pos.nodes_searched()) << endl;
933           }
934
935           if (current_search_time() > 2000)
936               cout << "info currmove " << move
937                    << " currmovenumber " << moveCount << endl;
938       }
939
940       // At Root and at first iteration do a PV search on all the moves to score root moves
941       isPvMove = (PvNode && moveCount <= (Root ? depth <= ONE_PLY ? 1000 : MultiPV : 1));
942       moveIsCheck = pos.move_is_check(move, ci);
943       captureOrPromotion = pos.move_is_capture_or_promotion(move);
944
945       // Step 11. Decide the new search depth
946       ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, &dangerous);
947
948       // Singular extension search. If all moves but one fail low on a search of
949       // (alpha-s, beta-s), and just one fails high on (alpha, beta), then that move
950       // is singular and should be extended. To verify this we do a reduced search
951       // on all the other moves but the ttMove, if result is lower than ttValue minus
952       // a margin then we extend ttMove.
953       if (   singularExtensionNode
954           && move == tte->move()
955           && ext < ONE_PLY)
956       {
957           Value ttValue = value_from_tt(tte->value(), ss->ply);
958
959           if (abs(ttValue) < VALUE_KNOWN_WIN)
960           {
961               Value rBeta = ttValue - int(depth);
962               ss->excludedMove = move;
963               ss->skipNullMove = true;
964               Value v = search<NonPV>(pos, ss, rBeta - 1, rBeta, depth / 2);
965               ss->skipNullMove = false;
966               ss->excludedMove = MOVE_NONE;
967               ss->bestMove = MOVE_NONE;
968               if (v < rBeta)
969                   ext = ONE_PLY;
970           }
971       }
972
973       // Update current move (this must be done after singular extension search)
974       ss->currentMove = move;
975       newDepth = depth - ONE_PLY + ext;
976
977       // Step 12. Futility pruning (is omitted in PV nodes)
978       if (   !PvNode
979           && !captureOrPromotion
980           && !isCheck
981           && !dangerous
982           &&  move != ttMove
983           && !move_is_castle(move))
984       {
985           // Move count based pruning
986           if (   moveCount >= futility_move_count(depth)
987               && (!threatMove || !connected_threat(pos, move, threatMove))
988               && bestValue > VALUE_MATED_IN_PLY_MAX) // FIXME bestValue is racy
989           {
990               if (SpNode)
991                   lock_grab(&(sp->lock));
992
993               continue;
994           }
995
996           // Value based pruning
997           // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
998           // but fixing this made program slightly weaker.
999           Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1000           futilityValueScaled =  futilityBase + futility_margin(predictedDepth, moveCount)
1001                                + H.gain(pos.piece_on(move_from(move)), move_to(move));
1002
1003           if (futilityValueScaled < beta)
1004           {
1005               if (SpNode)
1006               {
1007                   lock_grab(&(sp->lock));
1008                   if (futilityValueScaled > sp->bestValue)
1009                       sp->bestValue = bestValue = futilityValueScaled;
1010               }
1011               else if (futilityValueScaled > bestValue)
1012                   bestValue = futilityValueScaled;
1013
1014               continue;
1015           }
1016
1017           // Prune moves with negative SEE at low depths
1018           if (   predictedDepth < 2 * ONE_PLY
1019               && bestValue > VALUE_MATED_IN_PLY_MAX
1020               && pos.see_sign(move) < 0)
1021           {
1022               if (SpNode)
1023                   lock_grab(&(sp->lock));
1024
1025               continue;
1026           }
1027       }
1028
1029       // Bad capture detection. Will be used by prob-cut search
1030       isBadCap =   depth >= 3 * ONE_PLY
1031                 && depth < 8 * ONE_PLY
1032                 && captureOrPromotion
1033                 && move != ttMove
1034                 && !dangerous
1035                 && !move_is_promotion(move)
1036                 &&  abs(alpha) < VALUE_MATE_IN_PLY_MAX
1037                 &&  pos.see_sign(move) < 0;
1038
1039       // Step 13. Make the move
1040       pos.do_move(move, st, ci, moveIsCheck);
1041
1042       if (!SpNode && !captureOrPromotion)
1043           movesSearched[playedMoveCount++] = move;
1044
1045       // Step extra. pv search (only in PV nodes)
1046       // The first move in list is the expected PV
1047       if (isPvMove)
1048       {
1049           // Aspiration window is disabled in multi-pv case
1050           if (Root && MultiPV > 1)
1051               alpha = -VALUE_INFINITE;
1052
1053           value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth);
1054       }
1055       else
1056       {
1057           // Step 14. Reduced depth search
1058           // If the move fails high will be re-searched at full depth.
1059           bool doFullDepthSearch = true;
1060           alpha = SpNode ? sp->alpha : alpha;
1061
1062           if (    depth >= 3 * ONE_PLY
1063               && !captureOrPromotion
1064               && !dangerous
1065               && !move_is_castle(move)
1066               &&  ss->killers[0] != move
1067               &&  ss->killers[1] != move)
1068           {
1069               ss->reduction = reduction<PvNode>(depth, moveCount);
1070               if (ss->reduction)
1071               {
1072                   alpha = SpNode ? sp->alpha : alpha;
1073                   Depth d = newDepth - ss->reduction;
1074                   value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d);
1075
1076                   doFullDepthSearch = (value > alpha);
1077               }
1078               ss->reduction = DEPTH_ZERO; // Restore original reduction
1079           }
1080
1081           // Probcut search for bad captures. If a reduced search returns a value
1082           // very below beta then we can (almost) safely prune the bad capture.
1083           if (isBadCap)
1084           {
1085               ss->reduction = 3 * ONE_PLY;
1086               Value rAlpha = alpha - 300;
1087               Depth d = newDepth - ss->reduction;
1088               value = -search<NonPV>(pos, ss+1, -(rAlpha+1), -rAlpha, d);
1089               doFullDepthSearch = (value > rAlpha);
1090               ss->reduction = DEPTH_ZERO; // Restore original reduction
1091           }
1092
1093           // Step 15. Full depth search
1094           if (doFullDepthSearch)
1095           {
1096               alpha = SpNode ? sp->alpha : alpha;
1097               value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth);
1098
1099               // Step extra. pv search (only in PV nodes)
1100               // Search only for possible new PV nodes, if instead value >= beta then
1101               // parent node fails low with value <= alpha and tries another move.
1102               if (PvNode && value > alpha && (Root || value < beta))
1103                   value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth);
1104           }
1105       }
1106
1107       // Step 16. Undo move
1108       pos.undo_move(move);
1109
1110       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1111
1112       // Step 17. Check for new best move
1113       if (SpNode)
1114       {
1115           lock_grab(&(sp->lock));
1116           bestValue = sp->bestValue;
1117           alpha = sp->alpha;
1118       }
1119
1120       if (value > bestValue && !(SpNode && Threads[threadID].cutoff_occurred()))
1121       {
1122           bestValue = value;
1123
1124           if (SpNode)
1125               sp->bestValue = value;
1126
1127           if (!Root && value > alpha)
1128           {
1129               if (PvNode && value < beta) // We want always alpha < beta
1130               {
1131                   alpha = value;
1132
1133                   if (SpNode)
1134                       sp->alpha = value;
1135               }
1136               else if (SpNode)
1137                   sp->is_betaCutoff = true;
1138
1139               if (value == value_mate_in(ss->ply + 1))
1140                   ss->mateKiller = move;
1141
1142               ss->bestMove = move;
1143
1144               if (SpNode)
1145                   sp->ss->bestMove = move;
1146           }
1147       }
1148
1149       if (Root)
1150       {
1151           // Finished searching the move. If StopRequest is true, the search
1152           // was aborted because the user interrupted the search or because we
1153           // ran out of time. In this case, the return value of the search cannot
1154           // be trusted, and we break out of the loop without updating the best
1155           // move and/or PV.
1156           if (StopRequest)
1157               break;
1158
1159           // Remember searched nodes counts for this move
1160           mp.rm->nodes += pos.nodes_searched() - nodes;
1161
1162           // PV move or new best move ?
1163           if (isPvMove || value > alpha)
1164           {
1165               // Update PV
1166               ss->bestMove = move;
1167               mp.rm->pv_score = value;
1168               mp.rm->extract_pv_from_tt(pos);
1169
1170               // We record how often the best move has been changed in each
1171               // iteration. This information is used for time management: When
1172               // the best move changes frequently, we allocate some more time.
1173               if (!isPvMove && MultiPV == 1)
1174                   Rml.bestMoveChanges++;
1175
1176               Rml.sort_multipv(moveCount);
1177
1178               // Update alpha. In multi-pv we don't use aspiration window, so
1179               // set alpha equal to minimum score among the PV lines.
1180               if (MultiPV > 1)
1181                   alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount?
1182               else if (value > alpha)
1183                   alpha = value;
1184           }
1185           else
1186               mp.rm->pv_score = -VALUE_INFINITE;
1187
1188       } // Root
1189
1190       // Step 18. Check for split
1191       if (   !Root
1192           && !SpNode
1193           && depth >= Threads.min_split_depth()
1194           && bestValue < beta
1195           && Threads.available_slave_exists(threadID)
1196           && !StopRequest
1197           && !Threads[threadID].cutoff_occurred())
1198           Threads.split<FakeSplit>(pos, ss, &alpha, beta, &bestValue, depth,
1199                                    threatMove, moveCount, &mp, PvNode);
1200     }
1201
1202     // Step 19. Check for mate and stalemate
1203     // All legal moves have been searched and if there are
1204     // no legal moves, it must be mate or stalemate.
1205     // If one move was excluded return fail low score.
1206     if (!SpNode && !moveCount)
1207         return excludedMove ? oldAlpha : isCheck ? value_mated_in(ss->ply) : VALUE_DRAW;
1208
1209     // Step 20. Update tables
1210     // If the search is not aborted, update the transposition table,
1211     // history counters, and killer moves.
1212     if (!SpNode && !StopRequest && !Threads[threadID].cutoff_occurred())
1213     {
1214         move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
1215         vt   = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
1216              : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
1217
1218         TT.store(posKey, value_to_tt(bestValue, ss->ply), vt, depth, move, ss->eval, ss->evalMargin);
1219
1220         // Update killers and history only for non capture moves that fails high
1221         if (    bestValue >= beta
1222             && !pos.move_is_capture_or_promotion(move))
1223         {
1224             if (move != ss->killers[0])
1225             {
1226                 ss->killers[1] = ss->killers[0];
1227                 ss->killers[0] = move;
1228             }
1229             update_history(pos, move, depth, movesSearched, playedMoveCount);
1230         }
1231     }
1232
1233     if (SpNode)
1234     {
1235         // Here we have the lock still grabbed
1236         sp->is_slave[threadID] = false;
1237         sp->nodes += pos.nodes_searched();
1238         lock_release(&(sp->lock));
1239     }
1240
1241     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1242
1243     return bestValue;
1244   }
1245
1246   // qsearch() is the quiescence search function, which is called by the main
1247   // search function when the remaining depth is zero (or, to be more precise,
1248   // less than ONE_PLY).
1249
1250   template <NodeType PvNode>
1251   Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) {
1252
1253     assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1254     assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1255     assert(PvNode || alpha == beta - 1);
1256     assert(depth <= 0);
1257     assert(pos.thread() >= 0 && pos.thread() < Threads.size());
1258
1259     StateInfo st;
1260     Move ttMove, move;
1261     Value bestValue, value, evalMargin, futilityValue, futilityBase;
1262     bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1263     const TTEntry* tte;
1264     Depth ttDepth;
1265     Value oldAlpha = alpha;
1266
1267     ss->bestMove = ss->currentMove = MOVE_NONE;
1268     ss->ply = (ss-1)->ply + 1;
1269
1270     // Check for an instant draw or maximum ply reached
1271     if (ss->ply > PLY_MAX || pos.is_draw())
1272         return VALUE_DRAW;
1273
1274     // Decide whether or not to include checks, this fixes also the type of
1275     // TT entry depth that we are going to use. Note that in qsearch we use
1276     // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
1277     isCheck = pos.is_check();
1278     ttDepth = (isCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS);
1279
1280     // Transposition table lookup. At PV nodes, we don't use the TT for
1281     // pruning, but only for move ordering.
1282     tte = TT.retrieve(pos.get_key());
1283     ttMove = (tte ? tte->move() : MOVE_NONE);
1284
1285     if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ss->ply))
1286     {
1287         ss->bestMove = ttMove; // Can be MOVE_NONE
1288         return value_from_tt(tte->value(), ss->ply);
1289     }
1290
1291     // Evaluate the position statically
1292     if (isCheck)
1293     {
1294         bestValue = futilityBase = -VALUE_INFINITE;
1295         ss->eval = evalMargin = VALUE_NONE;
1296         enoughMaterial = false;
1297     }
1298     else
1299     {
1300         if (tte)
1301         {
1302             assert(tte->static_value() != VALUE_NONE);
1303
1304             evalMargin = tte->static_value_margin();
1305             ss->eval = bestValue = tte->static_value();
1306         }
1307         else
1308             ss->eval = bestValue = evaluate(pos, evalMargin);
1309
1310         update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1311
1312         // Stand pat. Return immediately if static value is at least beta
1313         if (bestValue >= beta)
1314         {
1315             if (!tte)
1316                 TT.store(pos.get_key(), value_to_tt(bestValue, ss->ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1317
1318             return bestValue;
1319         }
1320
1321         if (PvNode && bestValue > alpha)
1322             alpha = bestValue;
1323
1324         // Futility pruning parameters, not needed when in check
1325         futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1326         enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1327     }
1328
1329     // Initialize a MovePicker object for the current position, and prepare
1330     // to search the moves. Because the depth is <= 0 here, only captures,
1331     // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
1332     // be generated.
1333     MovePicker mp(pos, ttMove, depth, H);
1334     CheckInfo ci(pos);
1335
1336     // Loop through the moves until no moves remain or a beta cutoff occurs
1337     while (   alpha < beta
1338            && (move = mp.get_next_move()) != MOVE_NONE)
1339     {
1340       assert(move_is_ok(move));
1341
1342       moveIsCheck = pos.move_is_check(move, ci);
1343
1344       // Futility pruning
1345       if (   !PvNode
1346           && !isCheck
1347           && !moveIsCheck
1348           &&  move != ttMove
1349           &&  enoughMaterial
1350           && !move_is_promotion(move)
1351           && !pos.move_is_passed_pawn_push(move))
1352       {
1353           futilityValue =  futilityBase
1354                          + pos.endgame_value_of_piece_on(move_to(move))
1355                          + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1356
1357           if (futilityValue < alpha)
1358           {
1359               if (futilityValue > bestValue)
1360                   bestValue = futilityValue;
1361               continue;
1362           }
1363
1364           // Prune moves with negative or equal SEE
1365           if (   futilityBase < beta
1366               && depth < DEPTH_ZERO
1367               && pos.see(move) <= 0)
1368               continue;
1369       }
1370
1371       // Detect non-capture evasions that are candidate to be pruned
1372       evasionPrunable =   isCheck
1373                        && bestValue > VALUE_MATED_IN_PLY_MAX
1374                        && !pos.move_is_capture(move)
1375                        && !pos.can_castle(pos.side_to_move());
1376
1377       // Don't search moves with negative SEE values
1378       if (   !PvNode
1379           && (!isCheck || evasionPrunable)
1380           &&  move != ttMove
1381           && !move_is_promotion(move)
1382           &&  pos.see_sign(move) < 0)
1383           continue;
1384
1385       // Don't search useless checks
1386       if (   !PvNode
1387           && !isCheck
1388           &&  moveIsCheck
1389           &&  move != ttMove
1390           && !pos.move_is_capture_or_promotion(move)
1391           &&  ss->eval + PawnValueMidgame / 4 < beta
1392           && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue))
1393       {
1394           if (ss->eval + PawnValueMidgame / 4 > bestValue)
1395               bestValue = ss->eval + PawnValueMidgame / 4;
1396
1397           continue;
1398       }
1399
1400       // Update current move
1401       ss->currentMove = move;
1402
1403       // Make and search the move
1404       pos.do_move(move, st, ci, moveIsCheck);
1405       value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY);
1406       pos.undo_move(move);
1407
1408       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1409
1410       // New best move?
1411       if (value > bestValue)
1412       {
1413           bestValue = value;
1414           if (value > alpha)
1415           {
1416               alpha = value;
1417               ss->bestMove = move;
1418           }
1419        }
1420     }
1421
1422     // All legal moves have been searched. A special case: If we're in check
1423     // and no legal moves were found, it is checkmate.
1424     if (isCheck && bestValue == -VALUE_INFINITE)
1425         return value_mated_in(ss->ply);
1426
1427     // Update transposition table
1428     ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1429     TT.store(pos.get_key(), value_to_tt(bestValue, ss->ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin);
1430
1431     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1432
1433     return bestValue;
1434   }
1435
1436
1437   // check_is_dangerous() tests if a checking move can be pruned in qsearch().
1438   // bestValue is updated only when returning false because in that case move
1439   // will be pruned.
1440
1441   bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bestValue)
1442   {
1443     Bitboard b, occ, oldAtt, newAtt, kingAtt;
1444     Square from, to, ksq, victimSq;
1445     Piece pc;
1446     Color them;
1447     Value futilityValue, bv = *bestValue;
1448
1449     from = move_from(move);
1450     to = move_to(move);
1451     them = opposite_color(pos.side_to_move());
1452     ksq = pos.king_square(them);
1453     kingAtt = pos.attacks_from<KING>(ksq);
1454     pc = pos.piece_on(from);
1455
1456     occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL << ksq);
1457     oldAtt = pos.attacks_from(pc, from, occ);
1458     newAtt = pos.attacks_from(pc,   to, occ);
1459
1460     // Rule 1. Checks which give opponent's king at most one escape square are dangerous
1461     b = kingAtt & ~pos.pieces_of_color(them) & ~newAtt & ~(1ULL << to);
1462
1463     if (!(b && (b & (b - 1))))
1464         return true;
1465
1466     // Rule 2. Queen contact check is very dangerous
1467     if (   type_of_piece(pc) == QUEEN
1468         && bit_is_set(kingAtt, to))
1469         return true;
1470
1471     // Rule 3. Creating new double threats with checks
1472     b = pos.pieces_of_color(them) & newAtt & ~oldAtt & ~(1ULL << ksq);
1473
1474     while (b)
1475     {
1476         victimSq = pop_1st_bit(&b);
1477         futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq);
1478
1479         // Note that here we generate illegal "double move"!
1480         if (   futilityValue >= beta
1481             && pos.see_sign(make_move(from, victimSq)) >= 0)
1482             return true;
1483
1484         if (futilityValue > bv)
1485             bv = futilityValue;
1486     }
1487
1488     // Update bestValue only if check is not dangerous (because we will prune the move)
1489     *bestValue = bv;
1490     return false;
1491   }
1492
1493
1494   // connected_moves() tests whether two moves are 'connected' in the sense
1495   // that the first move somehow made the second move possible (for instance
1496   // if the moving piece is the same in both moves). The first move is assumed
1497   // to be the move that was made to reach the current position, while the
1498   // second move is assumed to be a move from the current position.
1499
1500   bool connected_moves(const Position& pos, Move m1, Move m2) {
1501
1502     Square f1, t1, f2, t2;
1503     Piece p;
1504
1505     assert(m1 && move_is_ok(m1));
1506     assert(m2 && move_is_ok(m2));
1507
1508     // Case 1: The moving piece is the same in both moves
1509     f2 = move_from(m2);
1510     t1 = move_to(m1);
1511     if (f2 == t1)
1512         return true;
1513
1514     // Case 2: The destination square for m2 was vacated by m1
1515     t2 = move_to(m2);
1516     f1 = move_from(m1);
1517     if (t2 == f1)
1518         return true;
1519
1520     // Case 3: Moving through the vacated square
1521     if (   piece_is_slider(pos.piece_on(f2))
1522         && bit_is_set(squares_between(f2, t2), f1))
1523       return true;
1524
1525     // Case 4: The destination square for m2 is defended by the moving piece in m1
1526     p = pos.piece_on(t1);
1527     if (bit_is_set(pos.attacks_from(p, t1), t2))
1528         return true;
1529
1530     // Case 5: Discovered check, checking piece is the piece moved in m1
1531     if (    piece_is_slider(p)
1532         &&  bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1533         && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1534     {
1535         // discovered_check_candidates() works also if the Position's side to
1536         // move is the opposite of the checking piece.
1537         Color them = opposite_color(pos.side_to_move());
1538         Bitboard dcCandidates = pos.discovered_check_candidates(them);
1539
1540         if (bit_is_set(dcCandidates, f2))
1541             return true;
1542     }
1543     return false;
1544   }
1545
1546
1547   // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1548   // "plies to mate from the current ply".  Non-mate scores are unchanged.
1549   // The function is called before storing a value to the transposition table.
1550
1551   Value value_to_tt(Value v, int ply) {
1552
1553     if (v >= VALUE_MATE_IN_PLY_MAX)
1554       return v + ply;
1555
1556     if (v <= VALUE_MATED_IN_PLY_MAX)
1557       return v - ply;
1558
1559     return v;
1560   }
1561
1562
1563   // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1564   // the transposition table to a mate score corrected for the current ply.
1565
1566   Value value_from_tt(Value v, int ply) {
1567
1568     if (v >= VALUE_MATE_IN_PLY_MAX)
1569       return v - ply;
1570
1571     if (v <= VALUE_MATED_IN_PLY_MAX)
1572       return v + ply;
1573
1574     return v;
1575   }
1576
1577
1578   // extension() decides whether a move should be searched with normal depth,
1579   // or with extended depth. Certain classes of moves (checking moves, in
1580   // particular) are searched with bigger depth than ordinary moves and in
1581   // any case are marked as 'dangerous'. Note that also if a move is not
1582   // extended, as example because the corresponding UCI option is set to zero,
1583   // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1584   template <NodeType PvNode>
1585   Depth extension(const Position& pos, Move m, bool captureOrPromotion,
1586                   bool moveIsCheck, bool* dangerous) {
1587
1588     assert(m != MOVE_NONE);
1589
1590     Depth result = DEPTH_ZERO;
1591     *dangerous = moveIsCheck;
1592
1593     if (moveIsCheck && pos.see_sign(m) >= 0)
1594         result += CheckExtension[PvNode];
1595
1596     if (pos.type_of_piece_on(move_from(m)) == PAWN)
1597     {
1598         Color c = pos.side_to_move();
1599         if (relative_rank(c, move_to(m)) == RANK_7)
1600         {
1601             result += PawnPushTo7thExtension[PvNode];
1602             *dangerous = true;
1603         }
1604         if (pos.pawn_is_passed(c, move_to(m)))
1605         {
1606             result += PassedPawnExtension[PvNode];
1607             *dangerous = true;
1608         }
1609     }
1610
1611     if (   captureOrPromotion
1612         && pos.type_of_piece_on(move_to(m)) != PAWN
1613         && (  pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1614             - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1615         && !move_is_special(m))
1616     {
1617         result += PawnEndgameExtension[PvNode];
1618         *dangerous = true;
1619     }
1620
1621     return Min(result, ONE_PLY);
1622   }
1623
1624
1625   // connected_threat() tests whether it is safe to forward prune a move or if
1626   // is somehow connected to the threat move returned by null search.
1627
1628   bool connected_threat(const Position& pos, Move m, Move threat) {
1629
1630     assert(move_is_ok(m));
1631     assert(threat && move_is_ok(threat));
1632     assert(!pos.move_is_check(m));
1633     assert(!pos.move_is_capture_or_promotion(m));
1634     assert(!pos.move_is_passed_pawn_push(m));
1635
1636     Square mfrom, mto, tfrom, tto;
1637
1638     mfrom = move_from(m);
1639     mto = move_to(m);
1640     tfrom = move_from(threat);
1641     tto = move_to(threat);
1642
1643     // Case 1: Don't prune moves which move the threatened piece
1644     if (mfrom == tto)
1645         return true;
1646
1647     // Case 2: If the threatened piece has value less than or equal to the
1648     // value of the threatening piece, don't prune moves which defend it.
1649     if (   pos.move_is_capture(threat)
1650         && (   pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1651             || pos.type_of_piece_on(tfrom) == KING)
1652         && pos.move_attacks_square(m, tto))
1653         return true;
1654
1655     // Case 3: If the moving piece in the threatened move is a slider, don't
1656     // prune safe moves which block its ray.
1657     if (   piece_is_slider(pos.piece_on(tfrom))
1658         && bit_is_set(squares_between(tfrom, tto), mto)
1659         && pos.see_sign(m) >= 0)
1660         return true;
1661
1662     return false;
1663   }
1664
1665
1666   // ok_to_use_TT() returns true if a transposition table score
1667   // can be used at a given point in search.
1668
1669   bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1670
1671     Value v = value_from_tt(tte->value(), ply);
1672
1673     return   (   tte->depth() >= depth
1674               || v >= Max(VALUE_MATE_IN_PLY_MAX, beta)
1675               || v < Min(VALUE_MATED_IN_PLY_MAX, beta))
1676
1677           && (   ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1678               || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1679   }
1680
1681
1682   // refine_eval() returns the transposition table score if
1683   // possible otherwise falls back on static position evaluation.
1684
1685   Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1686
1687       assert(tte);
1688
1689       Value v = value_from_tt(tte->value(), ply);
1690
1691       if (   ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1692           || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1693           return v;
1694
1695       return defaultEval;
1696   }
1697
1698
1699   // update_history() registers a good move that produced a beta-cutoff
1700   // in history and marks as failures all the other moves of that ply.
1701
1702   void update_history(const Position& pos, Move move, Depth depth,
1703                       Move movesSearched[], int moveCount) {
1704     Move m;
1705     Value bonus = Value(int(depth) * int(depth));
1706
1707     H.update(pos.piece_on(move_from(move)), move_to(move), bonus);
1708
1709     for (int i = 0; i < moveCount - 1; i++)
1710     {
1711         m = movesSearched[i];
1712
1713         assert(m != move);
1714
1715         H.update(pos.piece_on(move_from(m)), move_to(m), -bonus);
1716     }
1717   }
1718
1719
1720   // update_gains() updates the gains table of a non-capture move given
1721   // the static position evaluation before and after the move.
1722
1723   void update_gains(const Position& pos, Move m, Value before, Value after) {
1724
1725     if (   m != MOVE_NULL
1726         && before != VALUE_NONE
1727         && after != VALUE_NONE
1728         && pos.captured_piece_type() == PIECE_TYPE_NONE
1729         && !move_is_special(m))
1730         H.update_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
1731   }
1732
1733
1734   // current_search_time() returns the number of milliseconds which have passed
1735   // since the beginning of the current search.
1736
1737   int current_search_time(int set) {
1738
1739     static int searchStartTime;
1740
1741     if (set)
1742         searchStartTime = set;
1743
1744     return get_system_time() - searchStartTime;
1745   }
1746
1747
1748   // value_to_uci() converts a value to a string suitable for use with the UCI
1749   // protocol specifications:
1750   //
1751   // cp <x>     The score from the engine's point of view in centipawns.
1752   // mate <y>   Mate in y moves, not plies. If the engine is getting mated
1753   //            use negative values for y.
1754
1755   std::string value_to_uci(Value v) {
1756
1757     std::stringstream s;
1758
1759     if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
1760         s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to centipawns
1761     else
1762         s << "mate " << (v > 0 ? VALUE_MATE - v + 1 : -VALUE_MATE - v) / 2;
1763
1764     return s.str();
1765   }
1766
1767
1768   // speed_to_uci() returns a string with time stats of current search suitable
1769   // to be sent to UCI gui.
1770
1771   std::string speed_to_uci(int64_t nodes) {
1772
1773     std::stringstream s;
1774     int t = current_search_time();
1775
1776     s << " nodes " << nodes
1777       << " nps "   << (t > 0 ? int(nodes * 1000 / t) : 0)
1778       << " time "  << t;
1779
1780     return s.str();
1781   }
1782
1783
1784   // poll() performs two different functions: It polls for user input, and it
1785   // looks at the time consumed so far and decides if it's time to abort the
1786   // search.
1787
1788   void poll(const Position& pos) {
1789
1790     static int lastInfoTime;
1791     int t = current_search_time();
1792
1793     //  Poll for input
1794     if (input_available())
1795     {
1796         // We are line oriented, don't read single chars
1797         std::string command;
1798
1799         if (!std::getline(std::cin, command) || command == "quit")
1800         {
1801             // Quit the program as soon as possible
1802             Limits.ponder = false;
1803             QuitRequest = StopRequest = true;
1804             return;
1805         }
1806         else if (command == "stop")
1807         {
1808             // Stop calculating as soon as possible, but still send the "bestmove"
1809             // and possibly the "ponder" token when finishing the search.
1810             Limits.ponder = false;
1811             StopRequest = true;
1812         }
1813         else if (command == "ponderhit")
1814         {
1815             // The opponent has played the expected move. GUI sends "ponderhit" if
1816             // we were told to ponder on the same move the opponent has played. We
1817             // should continue searching but switching from pondering to normal search.
1818             Limits.ponder = false;
1819
1820             if (StopOnPonderhit)
1821                 StopRequest = true;
1822         }
1823     }
1824
1825     // Print search information
1826     if (t < 1000)
1827         lastInfoTime = 0;
1828
1829     else if (lastInfoTime > t)
1830         // HACK: Must be a new search where we searched less than
1831         // NodesBetweenPolls nodes during the first second of search.
1832         lastInfoTime = 0;
1833
1834     else if (t - lastInfoTime >= 1000)
1835     {
1836         lastInfoTime = t;
1837
1838         dbg_print_mean();
1839         dbg_print_hit_rate();
1840
1841         // Send info on searched nodes as soon as we return to root
1842         SendSearchedNodes = true;
1843     }
1844
1845     // Should we stop the search?
1846     if (Limits.ponder)
1847         return;
1848
1849     bool stillAtFirstMove =    FirstRootMove
1850                            && !AspirationFailLow
1851                            &&  t > TimeMgr.available_time();
1852
1853     bool noMoreTime =   t > TimeMgr.maximum_time()
1854                      || stillAtFirstMove;
1855
1856     if (   (Limits.useTimeManagement() && noMoreTime)
1857         || (Limits.maxTime && t >= Limits.maxTime)
1858         || (Limits.maxNodes && pos.nodes_searched() >= Limits.maxNodes)) // FIXME
1859         StopRequest = true;
1860   }
1861
1862
1863   // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
1864   // while the program is pondering. The point is to work around a wrinkle in
1865   // the UCI protocol: When pondering, the engine is not allowed to give a
1866   // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
1867   // We simply wait here until one of these commands is sent, and return,
1868   // after which the bestmove and pondermove will be printed.
1869
1870   void wait_for_stop_or_ponderhit() {
1871
1872     std::string command;
1873
1874     // Wait for a command from stdin
1875     while (   std::getline(std::cin, command)
1876            && command != "ponderhit" && command != "stop" && command != "quit") {};
1877
1878     if (command != "ponderhit" && command != "stop")
1879         QuitRequest = true; // Must be "quit" or getline() returned false
1880   }
1881
1882
1883   // When playing with strength handicap choose best move among the MultiPV set
1884   // using a statistical rule dependent on SkillLevel. Idea by Heinz van Saanen.
1885   void do_skill_level(Move* best, Move* ponder) {
1886
1887     assert(MultiPV > 1);
1888
1889     // Rml list is already sorted by pv_score in descending order
1890     int s;
1891     int max_s = -VALUE_INFINITE;
1892     int size = Min(MultiPV, (int)Rml.size());
1893     int max = Rml[0].pv_score;
1894     int var = Min(max - Rml[size - 1].pv_score, PawnValueMidgame);
1895     int wk = 120 - 2 * SkillLevel;
1896
1897     // PRNG sequence should be non deterministic
1898     for (int i = abs(get_system_time() % 50); i > 0; i--)
1899         RK.rand<unsigned>();
1900
1901     // Choose best move. For each move's score we add two terms both dependent
1902     // on wk, one deterministic and bigger for weaker moves, and one random,
1903     // then we choose the move with the resulting highest score.
1904     for (int i = 0; i < size; i++)
1905     {
1906         s = Rml[i].pv_score;
1907
1908         // Don't allow crazy blunders even at very low skills
1909         if (i > 0 && Rml[i-1].pv_score > s + EasyMoveMargin)
1910             break;
1911
1912         // This is our magical formula
1913         s += ((max - s) * wk + var * (RK.rand<unsigned>() % wk)) / 128;
1914
1915         if (s > max_s)
1916         {
1917             max_s = s;
1918             *best = Rml[i].pv[0];
1919             *ponder = Rml[i].pv[1];
1920         }
1921     }
1922   }
1923
1924
1925   /// RootMove and RootMoveList method's definitions
1926
1927   RootMove::RootMove() {
1928
1929     nodes = 0;
1930     pv_score = non_pv_score = -VALUE_INFINITE;
1931     pv[0] = MOVE_NONE;
1932   }
1933
1934   RootMove& RootMove::operator=(const RootMove& rm) {
1935
1936     const Move* src = rm.pv;
1937     Move* dst = pv;
1938
1939     // Avoid a costly full rm.pv[] copy
1940     do *dst++ = *src; while (*src++ != MOVE_NONE);
1941
1942     nodes = rm.nodes;
1943     pv_score = rm.pv_score;
1944     non_pv_score = rm.non_pv_score;
1945     return *this;
1946   }
1947
1948   void RootMoveList::init(Position& pos, Move searchMoves[]) {
1949
1950     MoveStack mlist[MAX_MOVES];
1951     Move* sm;
1952
1953     clear();
1954     bestMoveChanges = 0;
1955
1956     // Generate all legal moves and add them to RootMoveList
1957     MoveStack* last = generate<MV_LEGAL>(pos, mlist);
1958     for (MoveStack* cur = mlist; cur != last; cur++)
1959     {
1960         // If we have a searchMoves[] list then verify cur->move
1961         // is in the list before to add it.
1962         for (sm = searchMoves; *sm && *sm != cur->move; sm++) {}
1963
1964         if (searchMoves[0] && *sm != cur->move)
1965             continue;
1966
1967         RootMove rm;
1968         rm.pv[0] = cur->move;
1969         rm.pv[1] = MOVE_NONE;
1970         rm.pv_score = -VALUE_INFINITE;
1971         push_back(rm);
1972     }
1973   }
1974
1975   // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
1976   // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
1977   // allow to always have a ponder move even when we fail high at root and also a
1978   // long PV to print that is important for position analysis.
1979
1980   void RootMove::extract_pv_from_tt(Position& pos) {
1981
1982     StateInfo state[PLY_MAX_PLUS_2], *st = state;
1983     TTEntry* tte;
1984     int ply = 1;
1985
1986     assert(pv[0] != MOVE_NONE && pos.move_is_legal(pv[0]));
1987
1988     pos.do_move(pv[0], *st++);
1989
1990     while (   (tte = TT.retrieve(pos.get_key())) != NULL
1991            && tte->move() != MOVE_NONE
1992            && pos.move_is_legal(tte->move())
1993            && ply < PLY_MAX
1994            && (!pos.is_draw() || ply < 2))
1995     {
1996         pv[ply] = tte->move();
1997         pos.do_move(pv[ply++], *st++);
1998     }
1999     pv[ply] = MOVE_NONE;
2000
2001     do pos.undo_move(pv[--ply]); while (ply);
2002   }
2003
2004   // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2005   // the PV back into the TT. This makes sure the old PV moves are searched
2006   // first, even if the old TT entries have been overwritten.
2007
2008   void RootMove::insert_pv_in_tt(Position& pos) {
2009
2010     StateInfo state[PLY_MAX_PLUS_2], *st = state;
2011     TTEntry* tte;
2012     Key k;
2013     Value v, m = VALUE_NONE;
2014     int ply = 0;
2015
2016     assert(pv[0] != MOVE_NONE && pos.move_is_legal(pv[0]));
2017
2018     do {
2019         k = pos.get_key();
2020         tte = TT.retrieve(k);
2021
2022         // Don't overwrite existing correct entries
2023         if (!tte || tte->move() != pv[ply])
2024         {
2025             v = (pos.is_check() ? VALUE_NONE : evaluate(pos, m));
2026             TT.store(k, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[ply], v, m);
2027         }
2028         pos.do_move(pv[ply], *st++);
2029
2030     } while (pv[++ply] != MOVE_NONE);
2031
2032     do pos.undo_move(pv[--ply]); while (ply);
2033   }
2034
2035   // pv_info_to_uci() returns a string with information on the current PV line
2036   // formatted according to UCI specification.
2037
2038   std::string RootMove::pv_info_to_uci(Position& pos, int depth, int selDepth, Value alpha,
2039                                        Value beta, int pvIdx) {
2040     std::stringstream s;
2041
2042     s << "info depth " << depth
2043       << " seldepth " << selDepth
2044       << " multipv " << pvIdx + 1
2045       << " score " << value_to_uci(pv_score)
2046       << (pv_score >= beta ? " lowerbound" : pv_score <= alpha ? " upperbound" : "")
2047       << speed_to_uci(pos.nodes_searched())
2048       << " pv ";
2049
2050     for (Move* m = pv; *m != MOVE_NONE; m++)
2051         s << *m << " ";
2052
2053     return s.str();
2054   }
2055
2056   // Specializations for MovePickerExt in case of Root node
2057   MovePickerExt<false, true>::MovePickerExt(const Position& p, Move ttm, Depth d,
2058                                             const History& h, SearchStack* ss, Value b)
2059                             : MovePicker(p, ttm, d, h, ss, b), firstCall(true) {
2060     Move move;
2061     Value score = VALUE_ZERO;
2062
2063     // Score root moves using standard ordering used in main search, the moves
2064     // are scored according to the order in which they are returned by MovePicker.
2065     // This is the second order score that is used to compare the moves when
2066     // the first orders pv_score of both moves are equal.
2067     while ((move = MovePicker::get_next_move()) != MOVE_NONE)
2068         for (rm = Rml.begin(); rm != Rml.end(); ++rm)
2069             if (rm->pv[0] == move)
2070             {
2071                 rm->non_pv_score = score--;
2072                 break;
2073             }
2074
2075     Rml.sort();
2076     rm = Rml.begin();
2077   }
2078
2079   Move MovePickerExt<false, true>::get_next_move() {
2080
2081     if (!firstCall)
2082         ++rm;
2083     else
2084         firstCall = false;
2085
2086     return rm != Rml.end() ? rm->pv[0] : MOVE_NONE;
2087   };
2088
2089 } // namespace
2090
2091
2092 // ThreadsManager::idle_loop() is where the threads are parked when they have no work
2093 // to do. The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2094 // object for which the current thread is the master.
2095
2096 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2097
2098   assert(threadID >= 0 && threadID < MAX_THREADS);
2099
2100   int i;
2101   bool allFinished;
2102
2103   while (true)
2104   {
2105       // Slave threads can exit as soon as AllThreadsShouldExit raises,
2106       // master should exit as last one.
2107       if (allThreadsShouldExit)
2108       {
2109           assert(!sp);
2110           threads[threadID].state = Thread::TERMINATED;
2111           return;
2112       }
2113
2114       // If we are not thinking, wait for a condition to be signaled
2115       // instead of wasting CPU time polling for work.
2116       while (   threadID >= activeThreads
2117              || threads[threadID].state == Thread::INITIALIZING
2118              || (useSleepingThreads && threads[threadID].state == Thread::AVAILABLE))
2119       {
2120           assert(!sp || useSleepingThreads);
2121           assert(threadID != 0 || useSleepingThreads);
2122
2123           if (threads[threadID].state == Thread::INITIALIZING)
2124               threads[threadID].state = Thread::AVAILABLE;
2125
2126           // Grab the lock to avoid races with Thread::wake_up()
2127           lock_grab(&threads[threadID].sleepLock);
2128
2129           // If we are master and all slaves have finished do not go to sleep
2130           for (i = 0; sp && i < activeThreads && !sp->is_slave[i]; i++) {}
2131           allFinished = (i == activeThreads);
2132
2133           if (allFinished || allThreadsShouldExit)
2134           {
2135               lock_release(&threads[threadID].sleepLock);
2136               break;
2137           }
2138
2139           // Do sleep here after retesting sleep conditions
2140           if (threadID >= activeThreads || threads[threadID].state == Thread::AVAILABLE)
2141               cond_wait(&threads[threadID].sleepCond, &threads[threadID].sleepLock);
2142
2143           lock_release(&threads[threadID].sleepLock);
2144       }
2145
2146       // If this thread has been assigned work, launch a search
2147       if (threads[threadID].state == Thread::WORKISWAITING)
2148       {
2149           assert(!allThreadsShouldExit);
2150
2151           threads[threadID].state = Thread::SEARCHING;
2152
2153           // Copy split point position and search stack and call search()
2154           // with SplitPoint template parameter set to true.
2155           SearchStack ss[PLY_MAX_PLUS_2];
2156           SplitPoint* tsp = threads[threadID].splitPoint;
2157           Position pos(*tsp->pos, threadID);
2158
2159           memcpy(ss, tsp->ss - 1, 4 * sizeof(SearchStack));
2160           (ss+1)->sp = tsp;
2161
2162           if (tsp->pvNode)
2163               search<PV, true, false>(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth);
2164           else
2165               search<NonPV, true, false>(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth);
2166
2167           assert(threads[threadID].state == Thread::SEARCHING);
2168
2169           threads[threadID].state = Thread::AVAILABLE;
2170
2171           // Wake up master thread so to allow it to return from the idle loop in
2172           // case we are the last slave of the split point.
2173           if (   useSleepingThreads
2174               && threadID != tsp->master
2175               && threads[tsp->master].state == Thread::AVAILABLE)
2176               threads[tsp->master].wake_up();
2177       }
2178
2179       // If this thread is the master of a split point and all slaves have
2180       // finished their work at this split point, return from the idle loop.
2181       for (i = 0; sp && i < activeThreads && !sp->is_slave[i]; i++) {}
2182       allFinished = (i == activeThreads);
2183
2184       if (allFinished)
2185       {
2186           // Because sp->slaves[] is reset under lock protection,
2187           // be sure sp->lock has been released before to return.
2188           lock_grab(&(sp->lock));
2189           lock_release(&(sp->lock));
2190
2191           // In helpful master concept a master can help only a sub-tree, and
2192           // because here is all finished is not possible master is booked.
2193           assert(threads[threadID].state == Thread::AVAILABLE);
2194
2195           threads[threadID].state = Thread::SEARCHING;
2196           return;
2197       }
2198   }
2199 }