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