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