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