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