359c99c66aba1df979d60c47f4436f02db076a58
[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, pos.move_is_capture(move), 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
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             }
931             else
932                 value = alpha + 1; // Just to trigger next condition
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
1130       if (moveCount == 1) // The first move in list is the PV
1131           value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1132       else
1133       {
1134         // Try to reduce non-pv search depth by one ply if move seems not problematic,
1135         // if the move fails high will be re-searched at full depth.
1136         if (    depth >= 3*OnePly
1137             &&  moveCount >= LMRPVMoves
1138             && !dangerous
1139             && !moveIsCapture
1140             && !move_is_promotion(move)
1141             && !move_is_castle(move)
1142             && !move_is_killer(move, ss[ply]))
1143         {
1144             ss[ply].reduction = OnePly;
1145             value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, threadID);
1146         }
1147         else
1148             value = alpha + 1; // Just to trigger next condition
1149
1150         if (value > alpha) // Go with full depth non-pv search
1151         {
1152             ss[ply].reduction = Depth(0);
1153             value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID);
1154             if (value > alpha && value < beta)
1155             {
1156                 // When the search fails high at ply 1 while searching the first
1157                 // move at the root, set the flag failHighPly1. This is used for
1158                 // time managment:  We don't want to stop the search early in
1159                 // such cases, because resolving the fail high at ply 1 could
1160                 // result in a big drop in score at the root.
1161                 if (ply == 1 && RootMoveNumber == 1)
1162                     Threads[threadID].failHighPly1 = true;
1163
1164                 // A fail high occurred. Re-search at full window (pv search)
1165                 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1166                 Threads[threadID].failHighPly1 = false;
1167           }
1168         }
1169       }
1170       pos.undo_move(move);
1171
1172       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1173
1174       // New best move?
1175       if (value > bestValue)
1176       {
1177           bestValue = value;
1178           if (value > alpha)
1179           {
1180               alpha = value;
1181               update_pv(ss, ply);
1182               if (value == value_mate_in(ply + 1))
1183                   ss[ply].mateKiller = move;
1184           }
1185           // If we are at ply 1, and we are searching the first root move at
1186           // ply 0, set the 'Problem' variable if the score has dropped a lot
1187           // (from the computer's point of view) since the previous iteration.
1188           if (   ply == 1
1189               && Iteration >= 2
1190               && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
1191               Problem = true;
1192       }
1193
1194       // Split?
1195       if (   ActiveThreads > 1
1196           && bestValue < beta
1197           && depth >= MinimumSplitDepth
1198           && Iteration <= 99
1199           && idle_thread_exists(threadID)
1200           && !AbortSearch
1201           && !thread_should_stop(threadID)
1202           && split(pos, ss, ply, &alpha, &beta, &bestValue, depth,
1203                    &moveCount, &mp, dcCandidates, threadID, true))
1204           break;
1205     }
1206
1207     // All legal moves have been searched.  A special case: If there were
1208     // no legal moves, it must be mate or stalemate.
1209     if (moveCount == 0)
1210         return (isCheck ? value_mated_in(ply) : VALUE_DRAW);
1211
1212     // If the search is not aborted, update the transposition table,
1213     // history counters, and killer moves.
1214     if (AbortSearch || thread_should_stop(threadID))
1215         return bestValue;
1216
1217     if (bestValue <= oldAlpha)
1218         TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1219
1220     else if (bestValue >= beta)
1221     {
1222         BetaCounter.add(pos.side_to_move(), depth, threadID);
1223         Move m = ss[ply].pv[ply];
1224         if (ok_to_history(pos, m)) // Only non capture moves are considered
1225         {
1226             update_history(pos, m, depth, movesSearched, moveCount);
1227             update_killers(m, ss[ply]);
1228         }
1229         TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m);
1230     }
1231     else
1232         TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
1233
1234     return bestValue;
1235   }
1236
1237
1238   // search() is the search function for zero-width nodes.
1239
1240   Value search(Position& pos, SearchStack ss[], Value beta, Depth depth,
1241                int ply, bool allowNullmove, int threadID) {
1242
1243     assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1244     assert(ply >= 0 && ply < PLY_MAX);
1245     assert(threadID >= 0 && threadID < ActiveThreads);
1246
1247     if (depth < OnePly)
1248         return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1249
1250     // Initialize, and make an early exit in case of an aborted search,
1251     // an instant draw, maximum ply reached, etc.
1252     init_node(pos, ss, ply, threadID);
1253
1254     // After init_node() that calls poll()
1255     if (AbortSearch || thread_should_stop(threadID))
1256         return Value(0);
1257
1258     if (pos.is_draw())
1259         return VALUE_DRAW;
1260
1261     EvalInfo ei;
1262
1263     if (ply >= PLY_MAX - 1)
1264         return evaluate(pos, ei, threadID);
1265
1266     // Mate distance pruning
1267     if (value_mated_in(ply) >= beta)
1268         return beta;
1269
1270     if (value_mate_in(ply + 1) < beta)
1271         return beta - 1;
1272
1273     // Transposition table lookup
1274     const TTEntry* tte = TT.retrieve(pos.get_key());
1275     Move ttMove = (tte ? tte->move() : MOVE_NONE);
1276
1277     if (tte && ok_to_use_TT(tte, depth, beta, ply))
1278     {
1279         ss[ply].currentMove = ttMove; // can be MOVE_NONE
1280         return value_from_tt(tte->value(), ply);
1281     }
1282
1283     Value approximateEval = quick_evaluate(pos);
1284     bool mateThreat = false;
1285     bool isCheck = pos.is_check();
1286
1287     // Null move search
1288     if (    allowNullmove
1289         &&  depth > OnePly
1290         && !isCheck
1291         && !value_is_mate(beta)
1292         &&  ok_to_do_nullmove(pos)
1293         &&  approximateEval >= beta - NullMoveMargin)
1294     {
1295         ss[ply].currentMove = MOVE_NULL;
1296
1297         StateInfo st;
1298         pos.do_null_move(st);
1299         int R = (depth >= 5 * OnePly ? 4 : 3); // Null move dynamic reduction
1300
1301         Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);
1302
1303         pos.undo_null_move();
1304
1305         if (nullValue >= beta)
1306         {
1307             if (depth < 6 * OnePly)
1308                 return beta;
1309
1310             // Do zugzwang verification search
1311             Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
1312             if (v >= beta)
1313                 return beta;
1314         } else {
1315             // The null move failed low, which means that we may be faced with
1316             // some kind of threat. If the previous move was reduced, check if
1317             // the move that refuted the null move was somehow connected to the
1318             // move which was reduced. If a connection is found, return a fail
1319             // low score (which will cause the reduced move to fail high in the
1320             // parent node, which will trigger a re-search with full depth).
1321             if (nullValue == value_mated_in(ply + 2))
1322                 mateThreat = true;
1323
1324             ss[ply].threatMove = ss[ply + 1].currentMove;
1325             if (   depth < ThreatDepth
1326                 && ss[ply - 1].reduction
1327                 && connected_moves(pos, ss[ply - 1].currentMove, ss[ply].threatMove))
1328                 return beta - 1;
1329         }
1330     }
1331     // Null move search not allowed, try razoring
1332     else if (   !value_is_mate(beta)
1333              && depth < RazorDepth
1334              && approximateEval < beta - RazorApprMargins[int(depth) - 2]
1335              && ss[ply - 1].currentMove != MOVE_NULL
1336              && ttMove == MOVE_NONE
1337              && !pos.has_pawn_on_7th(pos.side_to_move()))
1338     {
1339         Value v = qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1340         if (v < beta - RazorMargins[int(depth) - 2])
1341           return v;
1342     }
1343
1344     // Go with internal iterative deepening if we don't have a TT move
1345     if (UseIIDAtNonPVNodes && ttMove == MOVE_NONE && depth >= 8*OnePly &&
1346         evaluate(pos, ei, threadID) >= beta - IIDMargin)
1347     {
1348         search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID);
1349         ttMove = ss[ply].pv[ply];
1350     }
1351
1352     // Initialize a MovePicker object for the current position, and prepare
1353     // to search all moves.
1354     MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1355
1356     Move move, movesSearched[256];
1357     int moveCount = 0;
1358     Value value, bestValue = -VALUE_INFINITE;
1359     Bitboard dcCandidates = mp.discovered_check_candidates();
1360     Value futilityValue = VALUE_NONE;
1361     bool useFutilityPruning =   depth < SelectiveDepth
1362                              && !isCheck;
1363
1364     // Loop through all legal moves until no moves remain or a beta cutoff
1365     // occurs.
1366     while (   bestValue < beta
1367            && (move = mp.get_next_move()) != MOVE_NONE
1368            && !thread_should_stop(threadID))
1369     {
1370       assert(move_is_ok(move));
1371
1372       bool singleReply = (isCheck && mp.number_of_moves() == 1);
1373       bool moveIsCheck = pos.move_is_check(move, dcCandidates);
1374       bool moveIsCapture = pos.move_is_capture(move);
1375
1376       movesSearched[moveCount++] = ss[ply].currentMove = move;
1377
1378       // Decide the new search depth
1379       bool dangerous;
1380       Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous);
1381       Depth newDepth = depth - OnePly + ext;
1382
1383       // Futility pruning
1384       if (    useFutilityPruning
1385           && !dangerous
1386           && !moveIsCapture
1387           && !move_is_promotion(move))
1388       {
1389           // History pruning. See ok_to_prune() definition
1390           if (   moveCount >= 2 + int(depth)
1391               && ok_to_prune(pos, move, ss[ply].threatMove, depth))
1392               continue;
1393
1394           // Value based pruning
1395           if (approximateEval < beta)
1396           {
1397               if (futilityValue == VALUE_NONE)
1398                   futilityValue =  evaluate(pos, ei, threadID)
1399                                  + FutilityMargins[int(depth) - 2];
1400
1401               if (futilityValue < beta)
1402               {
1403                   if (futilityValue > bestValue)
1404                       bestValue = futilityValue;
1405                   continue;
1406               }
1407           }
1408       }
1409
1410       // Make and search the move
1411       StateInfo st;
1412       pos.do_move(move, st, dcCandidates);
1413
1414       // Try to reduce non-pv search depth by one ply if move seems not problematic,
1415       // if the move fails high will be re-searched at full depth.
1416       if (    depth >= 3*OnePly
1417           &&  moveCount >= LMRNonPVMoves
1418           && !dangerous
1419           && !moveIsCapture
1420           && !move_is_promotion(move)
1421           && !move_is_castle(move)
1422           && !move_is_killer(move, ss[ply]))
1423       {
1424           ss[ply].reduction = OnePly;
1425           value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);
1426       }
1427       else
1428         value = beta; // Just to trigger next condition
1429
1430       if (value >= beta) // Go with full depth non-pv search
1431       {
1432           ss[ply].reduction = Depth(0);
1433           value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID);
1434       }
1435       pos.undo_move(move);
1436
1437       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1438
1439       // New best move?
1440       if (value > bestValue)
1441       {
1442         bestValue = value;
1443         if (value >= beta)
1444             update_pv(ss, ply);
1445
1446         if (value == value_mate_in(ply + 1))
1447             ss[ply].mateKiller = move;
1448       }
1449
1450       // Split?
1451       if (   ActiveThreads > 1
1452           && bestValue < beta
1453           && depth >= MinimumSplitDepth
1454           && Iteration <= 99
1455           && idle_thread_exists(threadID)
1456           && !AbortSearch
1457           && !thread_should_stop(threadID)
1458           && split(pos, ss, ply, &beta, &beta, &bestValue, depth, &moveCount,
1459                    &mp, dcCandidates, threadID, false))
1460         break;
1461     }
1462
1463     // All legal moves have been searched.  A special case: If there were
1464     // no legal moves, it must be mate or stalemate.
1465     if (moveCount == 0)
1466         return (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW);
1467
1468     // If the search is not aborted, update the transposition table,
1469     // history counters, and killer moves.
1470     if (AbortSearch || thread_should_stop(threadID))
1471         return bestValue;
1472
1473     if (bestValue < beta)
1474         TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1475     else
1476     {
1477         BetaCounter.add(pos.side_to_move(), depth, threadID);
1478         Move m = ss[ply].pv[ply];
1479         if (ok_to_history(pos, m)) // Only non capture moves are considered
1480         {
1481             update_history(pos, m, depth, movesSearched, moveCount);
1482             update_killers(m, ss[ply]);
1483         }
1484         TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m);
1485     }
1486
1487     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1488
1489     return bestValue;
1490   }
1491
1492
1493   // qsearch() is the quiescence search function, which is called by the main
1494   // search function when the remaining depth is zero (or, to be more precise,
1495   // less than OnePly).
1496
1497   Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta,
1498                 Depth depth, int ply, int threadID) {
1499
1500     assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1501     assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1502     assert(depth <= 0);
1503     assert(ply >= 0 && ply < PLY_MAX);
1504     assert(threadID >= 0 && threadID < ActiveThreads);
1505
1506     // Initialize, and make an early exit in case of an aborted search,
1507     // an instant draw, maximum ply reached, etc.
1508     init_node(pos, ss, ply, threadID);
1509
1510     // After init_node() that calls poll()
1511     if (AbortSearch || thread_should_stop(threadID))
1512         return Value(0);
1513
1514     if (pos.is_draw())
1515         return VALUE_DRAW;
1516
1517     // Transposition table lookup, only when not in PV
1518     TTEntry* tte = NULL;
1519     bool pvNode = (beta - alpha != 1);
1520     if (!pvNode)
1521     {
1522         tte = TT.retrieve(pos.get_key());
1523         if (tte && ok_to_use_TT(tte, depth, beta, ply))
1524         {
1525             assert(tte->type() != VALUE_TYPE_EVAL);
1526
1527             return value_from_tt(tte->value(), ply);
1528         }
1529     }
1530     Move ttMove = (tte ? tte->move() : MOVE_NONE);
1531
1532     // Evaluate the position statically
1533     EvalInfo ei;
1534     Value staticValue;
1535     bool isCheck = pos.is_check();
1536     ei.futilityMargin = Value(0); // Manually initialize futilityMargin
1537
1538     if (isCheck)
1539         staticValue = -VALUE_INFINITE;
1540
1541     else if (tte && tte->type() == VALUE_TYPE_EVAL)
1542     {
1543         // Use the cached evaluation score if possible
1544         assert(ei.futilityMargin == Value(0));
1545
1546         staticValue = tte->value();
1547     }
1548     else
1549         staticValue = evaluate(pos, ei, threadID);
1550
1551     if (ply == PLY_MAX - 1)
1552         return evaluate(pos, ei, threadID);
1553
1554     // Initialize "stand pat score", and return it immediately if it is
1555     // at least beta.
1556     Value bestValue = staticValue;
1557
1558     if (bestValue >= beta)
1559     {
1560         // Store the score to avoid a future costly evaluation() call
1561         if (!isCheck && !tte && ei.futilityMargin == 0)
1562             TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EVAL, Depth(-127*OnePly), MOVE_NONE);
1563
1564         return bestValue;
1565     }
1566
1567     if (bestValue > alpha)
1568         alpha = bestValue;
1569
1570     // Initialize a MovePicker object for the current position, and prepare
1571     // to search the moves.  Because the depth is <= 0 here, only captures,
1572     // queen promotions and checks (only if depth == 0) will be generated.
1573     MovePicker mp = MovePicker(pos, ttMove, depth, H);
1574     Move move;
1575     int moveCount = 0;
1576     Bitboard dcCandidates = mp.discovered_check_candidates();
1577     Color us = pos.side_to_move();
1578     bool enoughMaterial = pos.non_pawn_material(us) > RookValueMidgame;
1579
1580     // Loop through the moves until no moves remain or a beta cutoff
1581     // occurs.
1582     while (   alpha < beta
1583            && (move = mp.get_next_move()) != MOVE_NONE)
1584     {
1585       assert(move_is_ok(move));
1586
1587       moveCount++;
1588       ss[ply].currentMove = move;
1589
1590       // Futility pruning
1591       if (   enoughMaterial
1592           && !isCheck
1593           && !pvNode
1594           && !move_is_promotion(move)
1595           && !pos.move_is_check(move, dcCandidates)
1596           && !pos.move_is_passed_pawn_push(move))
1597       {
1598           Value futilityValue = staticValue
1599                               + Max(pos.midgame_value_of_piece_on(move_to(move)),
1600                                     pos.endgame_value_of_piece_on(move_to(move)))
1601                               + (move_is_ep(move) ? PawnValueEndgame : Value(0))
1602                               + FutilityMarginQS
1603                               + ei.futilityMargin;
1604
1605           if (futilityValue < alpha)
1606           {
1607               if (futilityValue > bestValue)
1608                   bestValue = futilityValue;
1609               continue;
1610           }
1611       }
1612
1613       // Don't search captures and checks with negative SEE values
1614       if (   !isCheck
1615           && !move_is_promotion(move)
1616           &&  pos.see_sign(move) < 0)
1617           continue;
1618
1619       // Make and search the move.
1620       StateInfo st;
1621       pos.do_move(move, st, dcCandidates);
1622       Value value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID);
1623       pos.undo_move(move);
1624
1625       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1626
1627       // New best move?
1628       if (value > bestValue)
1629       {
1630           bestValue = value;
1631           if (value > alpha)
1632           {
1633               alpha = value;
1634               update_pv(ss, ply);
1635           }
1636        }
1637     }
1638
1639     // All legal moves have been searched.  A special case: If we're in check
1640     // and no legal moves were found, it is checkmate.
1641     if (pos.is_check() && moveCount == 0) // Mate!
1642         return value_mated_in(ply);
1643
1644     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1645
1646     // Update transposition table
1647     Move m = ss[ply].pv[ply];
1648     if (!pvNode)
1649     {
1650         Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
1651         if (bestValue < beta)
1652             TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, d, MOVE_NONE);
1653         else
1654             TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, m);
1655     }
1656
1657     // Update killers only for good check moves
1658     if (alpha >= beta && ok_to_history(pos, m)) // Only non capture moves are considered
1659         update_killers(m, ss[ply]);
1660
1661     return bestValue;
1662   }
1663
1664
1665   // sp_search() is used to search from a split point.  This function is called
1666   // by each thread working at the split point.  It is similar to the normal
1667   // search() function, but simpler.  Because we have already probed the hash
1668   // table, done a null move search, and searched the first move before
1669   // splitting, we don't have to repeat all this work in sp_search().  We
1670   // also don't need to store anything to the hash table here:  This is taken
1671   // care of after we return from the split point.
1672
1673   void sp_search(SplitPoint* sp, int threadID) {
1674
1675     assert(threadID >= 0 && threadID < ActiveThreads);
1676     assert(ActiveThreads > 1);
1677
1678     Position pos = Position(sp->pos);
1679     SearchStack* ss = sp->sstack[threadID];
1680     Value value;
1681     Move move;
1682     bool isCheck = pos.is_check();
1683     bool useFutilityPruning =     sp->depth < SelectiveDepth
1684                               && !isCheck;
1685
1686     while (    sp->bestValue < sp->beta
1687            && !thread_should_stop(threadID)
1688            && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE)
1689     {
1690       assert(move_is_ok(move));
1691
1692       bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates);
1693       bool moveIsCapture = pos.move_is_capture(move);
1694
1695       lock_grab(&(sp->lock));
1696       int moveCount = ++sp->moves;
1697       lock_release(&(sp->lock));
1698
1699       ss[sp->ply].currentMove = move;
1700
1701       // Decide the new search depth.
1702       bool dangerous;
1703       Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, false, false, &dangerous);
1704       Depth newDepth = sp->depth - OnePly + ext;
1705
1706       // Prune?
1707       if (    useFutilityPruning
1708           && !dangerous
1709           && !moveIsCapture
1710           && !move_is_promotion(move)
1711           &&  moveCount >= 2 + int(sp->depth)
1712           &&  ok_to_prune(pos, move, ss[sp->ply].threatMove, sp->depth))
1713         continue;
1714
1715       // Make and search the move.
1716       StateInfo st;
1717       pos.do_move(move, st, sp->dcCandidates);
1718
1719       // Try to reduce non-pv search depth by one ply if move seems not problematic,
1720       // if the move fails high will be re-searched at full depth.
1721       if (   !dangerous
1722           &&  moveCount >= LMRNonPVMoves
1723           && !moveIsCapture
1724           && !move_is_promotion(move)
1725           && !move_is_castle(move)
1726           && !move_is_killer(move, ss[sp->ply]))
1727       {
1728           ss[sp->ply].reduction = OnePly;
1729           value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, true, threadID);
1730       }
1731       else
1732           value = sp->beta; // Just to trigger next condition
1733
1734       if (value >= sp->beta) // Go with full depth non-pv search
1735       {
1736           ss[sp->ply].reduction = Depth(0);
1737           value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID);
1738       }
1739       pos.undo_move(move);
1740
1741       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1742
1743       if (thread_should_stop(threadID))
1744           break;
1745
1746       // New best move?
1747       lock_grab(&(sp->lock));
1748       if (value > sp->bestValue && !thread_should_stop(threadID))
1749       {
1750           sp->bestValue = value;
1751           if (sp->bestValue >= sp->beta)
1752           {
1753               sp_update_pv(sp->parentSstack, ss, sp->ply);
1754               for (int i = 0; i < ActiveThreads; i++)
1755                   if (i != threadID && (i == sp->master || sp->slaves[i]))
1756                       Threads[i].stop = true;
1757
1758               sp->finished = true;
1759         }
1760       }
1761       lock_release(&(sp->lock));
1762     }
1763
1764     lock_grab(&(sp->lock));
1765
1766     // If this is the master thread and we have been asked to stop because of
1767     // a beta cutoff higher up in the tree, stop all slave threads.
1768     if (sp->master == threadID && thread_should_stop(threadID))
1769         for (int i = 0; i < ActiveThreads; i++)
1770             if (sp->slaves[i])
1771                 Threads[i].stop = true;
1772
1773     sp->cpus--;
1774     sp->slaves[threadID] = 0;
1775
1776     lock_release(&(sp->lock));
1777   }
1778
1779
1780   // sp_search_pv() is used to search from a PV split point.  This function
1781   // is called by each thread working at the split point.  It is similar to
1782   // the normal search_pv() function, but simpler.  Because we have already
1783   // probed the hash table and searched the first move before splitting, we
1784   // don't have to repeat all this work in sp_search_pv().  We also don't
1785   // need to store anything to the hash table here: This is taken care of
1786   // after we return from the split point.
1787
1788   void sp_search_pv(SplitPoint* sp, int threadID) {
1789
1790     assert(threadID >= 0 && threadID < ActiveThreads);
1791     assert(ActiveThreads > 1);
1792
1793     Position pos = Position(sp->pos);
1794     SearchStack* ss = sp->sstack[threadID];
1795     Value value;
1796     Move move;
1797
1798     while (    sp->alpha < sp->beta
1799            && !thread_should_stop(threadID)
1800            && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE)
1801     {
1802       bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates);
1803       bool moveIsCapture = pos.move_is_capture(move);
1804
1805       assert(move_is_ok(move));
1806
1807       lock_grab(&(sp->lock));
1808       int moveCount = ++sp->moves;
1809       lock_release(&(sp->lock));
1810
1811       ss[sp->ply].currentMove = move;
1812
1813       // Decide the new search depth.
1814       bool dangerous;
1815       Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, false, false, &dangerous);
1816       Depth newDepth = sp->depth - OnePly + ext;
1817
1818       // Make and search the move.
1819       StateInfo st;
1820       pos.do_move(move, st, sp->dcCandidates);
1821
1822       // Try to reduce non-pv search depth by one ply if move seems not problematic,
1823       // if the move fails high will be re-searched at full depth.
1824       if (   !dangerous
1825           &&  moveCount >= LMRPVMoves
1826           && !moveIsCapture
1827           && !move_is_promotion(move)
1828           && !move_is_castle(move)
1829           && !move_is_killer(move, ss[sp->ply]))
1830       {
1831           ss[sp->ply].reduction = OnePly;
1832           value = -search(pos, ss, -sp->alpha, newDepth - OnePly, sp->ply+1, true, threadID);
1833       }
1834       else
1835           value = sp->alpha + 1; // Just to trigger next condition
1836
1837       if (value > sp->alpha) // Go with full depth non-pv search
1838       {
1839           ss[sp->ply].reduction = Depth(0);
1840           value = -search(pos, ss, -sp->alpha, newDepth, sp->ply+1, true, threadID);
1841
1842           if (value > sp->alpha && value < sp->beta)
1843           {
1844               // When the search fails high at ply 1 while searching the first
1845               // move at the root, set the flag failHighPly1.  This is used for
1846               // time managment: We don't want to stop the search early in
1847               // such cases, because resolving the fail high at ply 1 could
1848               // result in a big drop in score at the root.
1849               if (sp->ply == 1 && RootMoveNumber == 1)
1850                   Threads[threadID].failHighPly1 = true;
1851
1852               value = -search_pv(pos, ss, -sp->beta, -sp->alpha, newDepth, sp->ply+1, threadID);
1853               Threads[threadID].failHighPly1 = false;
1854         }
1855       }
1856       pos.undo_move(move);
1857
1858       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1859
1860       if (thread_should_stop(threadID))
1861           break;
1862
1863       // New best move?
1864       lock_grab(&(sp->lock));
1865       if (value > sp->bestValue && !thread_should_stop(threadID))
1866       {
1867           sp->bestValue = value;
1868           if (value > sp->alpha)
1869           {
1870               sp->alpha = value;
1871               sp_update_pv(sp->parentSstack, ss, sp->ply);
1872               if (value == value_mate_in(sp->ply + 1))
1873                   ss[sp->ply].mateKiller = move;
1874
1875               if (value >= sp->beta)
1876               {
1877                   for (int i = 0; i < ActiveThreads; i++)
1878                       if (i != threadID && (i == sp->master || sp->slaves[i]))
1879                           Threads[i].stop = true;
1880
1881                   sp->finished = true;
1882               }
1883         }
1884         // If we are at ply 1, and we are searching the first root move at
1885         // ply 0, set the 'Problem' variable if the score has dropped a lot
1886         // (from the computer's point of view) since the previous iteration.
1887         if (   sp->ply == 1
1888             && Iteration >= 2
1889             && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
1890             Problem = true;
1891       }
1892       lock_release(&(sp->lock));
1893     }
1894
1895     lock_grab(&(sp->lock));
1896
1897     // If this is the master thread and we have been asked to stop because of
1898     // a beta cutoff higher up in the tree, stop all slave threads.
1899     if (sp->master == threadID && thread_should_stop(threadID))
1900         for (int i = 0; i < ActiveThreads; i++)
1901             if (sp->slaves[i])
1902                 Threads[i].stop = true;
1903
1904     sp->cpus--;
1905     sp->slaves[threadID] = 0;
1906
1907     lock_release(&(sp->lock));
1908   }
1909
1910   /// The BetaCounterType class
1911
1912   BetaCounterType::BetaCounterType() { clear(); }
1913
1914   void BetaCounterType::clear() {
1915
1916     for (int i = 0; i < THREAD_MAX; i++)
1917         Threads[i].betaCutOffs[WHITE] = Threads[i].betaCutOffs[BLACK] = 0ULL;
1918   }
1919
1920   void BetaCounterType::add(Color us, Depth d, int threadID) {
1921
1922     // Weighted count based on depth
1923     Threads[threadID].betaCutOffs[us] += unsigned(d);
1924   }
1925
1926   void BetaCounterType::read(Color us, int64_t& our, int64_t& their) {
1927
1928     our = their = 0UL;
1929     for (int i = 0; i < THREAD_MAX; i++)
1930     {
1931         our += Threads[i].betaCutOffs[us];
1932         their += Threads[i].betaCutOffs[opposite_color(us)];
1933     }
1934   }
1935
1936
1937   /// The RootMove class
1938
1939   // Constructor
1940
1941   RootMove::RootMove() {
1942     nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL;
1943   }
1944
1945   // RootMove::operator<() is the comparison function used when
1946   // sorting the moves.  A move m1 is considered to be better
1947   // than a move m2 if it has a higher score, or if the moves
1948   // have equal score but m1 has the higher node count.
1949
1950   bool RootMove::operator<(const RootMove& m) {
1951
1952     if (score != m.score)
1953         return (score < m.score);
1954
1955     return theirBeta <= m.theirBeta;
1956   }
1957
1958   /// The RootMoveList class
1959
1960   // Constructor
1961
1962   RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
1963
1964     MoveStack mlist[MaxRootMoves];
1965     bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
1966
1967     // Generate all legal moves
1968     int lm_count = generate_legal_moves(pos, mlist);
1969
1970     // Add each move to the moves[] array
1971     for (int i = 0; i < lm_count; i++)
1972     {
1973         bool includeMove = includeAllMoves;
1974
1975         for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
1976             includeMove = (searchMoves[k] == mlist[i].move);
1977
1978         if (!includeMove)
1979             continue;
1980
1981         // Find a quick score for the move
1982         StateInfo st;
1983         SearchStack ss[PLY_MAX_PLUS_2];
1984
1985         moves[count].move = mlist[i].move;
1986         pos.do_move(moves[count].move, st);
1987         moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0);
1988         pos.undo_move(moves[count].move);
1989         moves[count].pv[0] = moves[count].move;
1990         moves[count].pv[1] = MOVE_NONE; // FIXME
1991         count++;
1992     }
1993     sort();
1994   }
1995
1996
1997   // Simple accessor methods for the RootMoveList class
1998
1999   inline Move RootMoveList::get_move(int moveNum) const {
2000     return moves[moveNum].move;
2001   }
2002
2003   inline Value RootMoveList::get_move_score(int moveNum) const {
2004     return moves[moveNum].score;
2005   }
2006
2007   inline void RootMoveList::set_move_score(int moveNum, Value score) {
2008     moves[moveNum].score = score;
2009   }
2010
2011   inline void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
2012     moves[moveNum].nodes = nodes;
2013     moves[moveNum].cumulativeNodes += nodes;
2014   }
2015
2016   inline void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
2017     moves[moveNum].ourBeta = our;
2018     moves[moveNum].theirBeta = their;
2019   }
2020
2021   void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
2022     int j;
2023     for(j = 0; pv[j] != MOVE_NONE; j++)
2024       moves[moveNum].pv[j] = pv[j];
2025     moves[moveNum].pv[j] = MOVE_NONE;
2026   }
2027
2028   inline Move RootMoveList::get_move_pv(int moveNum, int i) const {
2029     return moves[moveNum].pv[i];
2030   }
2031
2032   inline int64_t RootMoveList::get_move_cumulative_nodes(int moveNum) const {
2033     return moves[moveNum].cumulativeNodes;
2034   }
2035
2036   inline int RootMoveList::move_count() const {
2037     return count;
2038   }
2039
2040
2041   // RootMoveList::scan_for_easy_move() is called at the end of the first
2042   // iteration, and is used to detect an "easy move", i.e. a move which appears
2043   // to be much bester than all the rest.  If an easy move is found, the move
2044   // is returned, otherwise the function returns MOVE_NONE.  It is very
2045   // important that this function is called at the right moment:  The code
2046   // assumes that the first iteration has been completed and the moves have
2047   // been sorted. This is done in RootMoveList c'tor.
2048
2049   Move RootMoveList::scan_for_easy_move() const {
2050
2051     assert(count);
2052
2053     if (count == 1)
2054         return get_move(0);
2055
2056     // moves are sorted so just consider the best and the second one
2057     if (get_move_score(0) > get_move_score(1) + EasyMoveMargin)
2058         return get_move(0);
2059
2060     return MOVE_NONE;
2061   }
2062
2063   // RootMoveList::sort() sorts the root move list at the beginning of a new
2064   // iteration.
2065
2066   inline void RootMoveList::sort() {
2067
2068     sort_multipv(count - 1); // all items
2069   }
2070
2071
2072   // RootMoveList::sort_multipv() sorts the first few moves in the root move
2073   // list by their scores and depths. It is used to order the different PVs
2074   // correctly in MultiPV mode.
2075
2076   void RootMoveList::sort_multipv(int n) {
2077
2078     for (int i = 1; i <= n; i++)
2079     {
2080       RootMove rm = moves[i];
2081       int j;
2082       for (j = i; j > 0 && moves[j-1] < rm; j--)
2083           moves[j] = moves[j-1];
2084       moves[j] = rm;
2085     }
2086   }
2087
2088
2089   // init_node() is called at the beginning of all the search functions
2090   // (search(), search_pv(), qsearch(), and so on) and initializes the search
2091   // stack object corresponding to the current node.  Once every
2092   // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
2093   // for user input and checks whether it is time to stop the search.
2094
2095   void init_node(const Position& pos, SearchStack ss[], int ply, int threadID) {
2096
2097     assert(ply >= 0 && ply < PLY_MAX);
2098     assert(threadID >= 0 && threadID < ActiveThreads);
2099
2100     if (Slowdown && Iteration >= 3)
2101       slowdown(pos);
2102
2103     Threads[threadID].nodes++;
2104
2105     if (threadID == 0)
2106     {
2107         NodesSincePoll++;
2108         if (NodesSincePoll >= NodesBetweenPolls)
2109         {
2110             poll();
2111             NodesSincePoll = 0;
2112         }
2113     }
2114     ss[ply].init(ply);
2115     ss[ply+2].initKillers();
2116
2117     if (Threads[threadID].printCurrentLine)
2118         print_current_line(ss, ply, threadID);
2119   }
2120
2121
2122   // update_pv() is called whenever a search returns a value > alpha.  It
2123   // updates the PV in the SearchStack object corresponding to the current
2124   // node.
2125
2126   void update_pv(SearchStack ss[], int ply) {
2127     assert(ply >= 0 && ply < PLY_MAX);
2128
2129     ss[ply].pv[ply] = ss[ply].currentMove;
2130     int p;
2131     for(p = ply + 1; ss[ply+1].pv[p] != MOVE_NONE; p++)
2132       ss[ply].pv[p] = ss[ply+1].pv[p];
2133     ss[ply].pv[p] = MOVE_NONE;
2134   }
2135
2136
2137   // sp_update_pv() is a variant of update_pv for use at split points.  The
2138   // difference between the two functions is that sp_update_pv also updates
2139   // the PV at the parent node.
2140
2141   void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply) {
2142     assert(ply >= 0 && ply < PLY_MAX);
2143
2144     ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
2145     int p;
2146     for(p = ply + 1; ss[ply+1].pv[p] != MOVE_NONE; p++)
2147       ss[ply].pv[p] = pss[ply].pv[p] = ss[ply+1].pv[p];
2148     ss[ply].pv[p] = pss[ply].pv[p] = MOVE_NONE;
2149   }
2150
2151
2152   // connected_moves() tests whether two moves are 'connected' in the sense
2153   // that the first move somehow made the second move possible (for instance
2154   // if the moving piece is the same in both moves).  The first move is
2155   // assumed to be the move that was made to reach the current position, while
2156   // the second move is assumed to be a move from the current position.
2157
2158   bool connected_moves(const Position& pos, Move m1, Move m2) {
2159     Square f1, t1, f2, t2;
2160
2161     assert(move_is_ok(m1));
2162     assert(move_is_ok(m2));
2163
2164     if (m2 == MOVE_NONE)
2165         return false;
2166
2167     // Case 1: The moving piece is the same in both moves
2168     f2 = move_from(m2);
2169     t1 = move_to(m1);
2170     if (f2 == t1)
2171         return true;
2172
2173     // Case 2: The destination square for m2 was vacated by m1
2174     t2 = move_to(m2);
2175     f1 = move_from(m1);
2176     if (t2 == f1)
2177         return true;
2178
2179     // Case 3: Moving through the vacated square
2180     if (   piece_is_slider(pos.piece_on(f2))
2181         && bit_is_set(squares_between(f2, t2), f1))
2182       return true;
2183
2184     // Case 4: The destination square for m2 is attacked by the moving piece in m1
2185     if (pos.piece_attacks_square(pos.piece_on(t1), t1, t2))
2186         return true;
2187
2188     // Case 5: Discovered check, checking piece is the piece moved in m1
2189     if (   piece_is_slider(pos.piece_on(t1))
2190         && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
2191         && !bit_is_set(squares_between(t2, pos.king_square(pos.side_to_move())), t2))
2192     {
2193         Bitboard occ = pos.occupied_squares();
2194         Color us = pos.side_to_move();
2195         Square ksq = pos.king_square(us);
2196         clear_bit(&occ, f2);
2197         if (pos.type_of_piece_on(t1) == BISHOP)
2198         {
2199             if (bit_is_set(bishop_attacks_bb(ksq, occ), t1))
2200                 return true;
2201         }
2202         else if (pos.type_of_piece_on(t1) == ROOK)
2203         {
2204             if (bit_is_set(rook_attacks_bb(ksq, occ), t1))
2205                 return true;
2206         }
2207         else
2208         {
2209             assert(pos.type_of_piece_on(t1) == QUEEN);
2210             if (bit_is_set(queen_attacks_bb(ksq, occ), t1))
2211                 return true;
2212         }
2213     }
2214     return false;
2215   }
2216
2217
2218   // value_is_mate() checks if the given value is a mate one
2219   // eventually compensated for the ply.
2220
2221   bool value_is_mate(Value value) {
2222
2223     assert(abs(value) <= VALUE_INFINITE);
2224
2225     return   value <= value_mated_in(PLY_MAX)
2226           || value >= value_mate_in(PLY_MAX);
2227   }
2228
2229
2230   // move_is_killer() checks if the given move is among the
2231   // killer moves of that ply.
2232
2233   bool move_is_killer(Move m, const SearchStack& ss) {
2234
2235       const Move* k = ss.killers;
2236       for (int i = 0; i < KILLER_MAX; i++, k++)
2237           if (*k == m)
2238               return true;
2239
2240       return false;
2241   }
2242
2243
2244   // extension() decides whether a move should be searched with normal depth,
2245   // or with extended depth.  Certain classes of moves (checking moves, in
2246   // particular) are searched with bigger depth than ordinary moves and in
2247   // any case are marked as 'dangerous'. Note that also if a move is not
2248   // extended, as example because the corresponding UCI option is set to zero,
2249   // the move is marked as 'dangerous' so, at least, we avoid to prune it.
2250
2251   Depth extension(const Position& pos, Move m, bool pvNode, bool capture, bool check,
2252                   bool singleReply, bool mateThreat, bool* dangerous) {
2253
2254     assert(m != MOVE_NONE);
2255
2256     Depth result = Depth(0);
2257     *dangerous = check | singleReply | mateThreat;
2258
2259     if (*dangerous)
2260     {
2261         if (check)
2262             result += CheckExtension[pvNode];
2263
2264         if (singleReply)
2265             result += SingleReplyExtension[pvNode];
2266
2267         if (mateThreat)
2268             result += MateThreatExtension[pvNode];
2269     }
2270
2271     if (pos.type_of_piece_on(move_from(m)) == PAWN)
2272     {
2273         if (pos.move_is_pawn_push_to_7th(m))
2274         {
2275             result += PawnPushTo7thExtension[pvNode];
2276             *dangerous = true;
2277         }
2278         if (pos.move_is_passed_pawn_push(m))
2279         {
2280             result += PassedPawnExtension[pvNode];
2281             *dangerous = true;
2282         }
2283     }
2284
2285     if (   capture
2286         && pos.type_of_piece_on(move_to(m)) != PAWN
2287         && (  pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
2288             - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))
2289         && !move_is_promotion(m)
2290         && !move_is_ep(m))
2291     {
2292         result += PawnEndgameExtension[pvNode];
2293         *dangerous = true;
2294     }
2295
2296     if (   pvNode
2297         && capture
2298         && pos.type_of_piece_on(move_to(m)) != PAWN
2299         && pos.see_sign(m) >= 0)
2300     {
2301         result += OnePly/2;
2302         *dangerous = true;
2303     }
2304
2305     return Min(result, OnePly);
2306   }
2307
2308
2309   // ok_to_do_nullmove() looks at the current position and decides whether
2310   // doing a 'null move' should be allowed.  In order to avoid zugzwang
2311   // problems, null moves are not allowed when the side to move has very
2312   // little material left.  Currently, the test is a bit too simple:  Null
2313   // moves are avoided only when the side to move has only pawns left.  It's
2314   // probably a good idea to avoid null moves in at least some more
2315   // complicated endgames, e.g. KQ vs KR.  FIXME
2316
2317   bool ok_to_do_nullmove(const Position& pos) {
2318
2319     return pos.non_pawn_material(pos.side_to_move()) != Value(0);
2320   }
2321
2322
2323   // ok_to_prune() tests whether it is safe to forward prune a move.  Only
2324   // non-tactical moves late in the move list close to the leaves are
2325   // candidates for pruning.
2326
2327   bool ok_to_prune(const Position& pos, Move m, Move threat, Depth d) {
2328
2329     assert(move_is_ok(m));
2330     assert(threat == MOVE_NONE || move_is_ok(threat));
2331     assert(!move_is_promotion(m));
2332     assert(!pos.move_is_check(m));
2333     assert(!pos.move_is_capture(m));
2334     assert(!pos.move_is_passed_pawn_push(m));
2335     assert(d >= OnePly);
2336
2337     Square mfrom, mto, tfrom, tto;
2338
2339     mfrom = move_from(m);
2340     mto = move_to(m);
2341     tfrom = move_from(threat);
2342     tto = move_to(threat);
2343
2344     // Case 1: Castling moves are never pruned
2345     if (move_is_castle(m))
2346         return false;
2347
2348     // Case 2: Don't prune moves which move the threatened piece
2349     if (!PruneEscapeMoves && threat != MOVE_NONE && mfrom == tto)
2350         return false;
2351
2352     // Case 3: If the threatened piece has value less than or equal to the
2353     // value of the threatening piece, don't prune move which defend it.
2354     if (   !PruneDefendingMoves
2355         && threat != MOVE_NONE
2356         && pos.move_is_capture(threat)
2357         && (   pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
2358             || pos.type_of_piece_on(tfrom) == KING)
2359         && pos.move_attacks_square(m, tto))
2360         return false;
2361
2362     // Case 4: Don't prune moves with good history
2363     if (!H.ok_to_prune(pos.piece_on(mfrom), mto, d))
2364         return false;
2365
2366     // Case 5: If the moving piece in the threatened move is a slider, don't
2367     // prune safe moves which block its ray.
2368     if (  !PruneBlockingMoves
2369         && threat != MOVE_NONE
2370         && piece_is_slider(pos.piece_on(tfrom))
2371         && bit_is_set(squares_between(tfrom, tto), mto)
2372         && pos.see_sign(m) >= 0)
2373         return false;
2374
2375     return true;
2376   }
2377
2378
2379   // ok_to_use_TT() returns true if a transposition table score
2380   // can be used at a given point in search.
2381
2382   bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
2383
2384     Value v = value_from_tt(tte->value(), ply);
2385
2386     return   (   tte->depth() >= depth
2387               || v >= Max(value_mate_in(100), beta)
2388               || v < Min(value_mated_in(100), beta))
2389
2390           && (   (is_lower_bound(tte->type()) && v >= beta)
2391               || (is_upper_bound(tte->type()) && v < beta));
2392   }
2393
2394
2395   // ok_to_history() returns true if a move m can be stored
2396   // in history. Should be a non capturing move nor a promotion.
2397
2398   bool ok_to_history(const Position& pos, Move m) {
2399
2400     return !pos.move_is_capture(m) && !move_is_promotion(m);
2401   }
2402
2403
2404   // update_history() registers a good move that produced a beta-cutoff
2405   // in history and marks as failures all the other moves of that ply.
2406
2407   void update_history(const Position& pos, Move m, Depth depth,
2408                       Move movesSearched[], int moveCount) {
2409
2410     H.success(pos.piece_on(move_from(m)), move_to(m), depth);
2411
2412     for (int i = 0; i < moveCount - 1; i++)
2413     {
2414         assert(m != movesSearched[i]);
2415         if (ok_to_history(pos, movesSearched[i]))
2416             H.failure(pos.piece_on(move_from(movesSearched[i])), move_to(movesSearched[i]));
2417     }
2418   }
2419
2420
2421   // update_killers() add a good move that produced a beta-cutoff
2422   // among the killer moves of that ply.
2423
2424   void update_killers(Move m, SearchStack& ss) {
2425
2426     if (m == ss.killers[0])
2427         return;
2428
2429     for (int i = KILLER_MAX - 1; i > 0; i--)
2430         ss.killers[i] = ss.killers[i - 1];
2431
2432     ss.killers[0] = m;
2433   }
2434
2435
2436   // slowdown() simply wastes CPU cycles doing nothing useful. It's used
2437   // in strength handicap mode.
2438
2439   void slowdown(const Position &pos) {
2440     int i, n;
2441     n = Slowdown;
2442     for (i = 0; i < n; i++)  {
2443         Square s = Square(i&63);
2444         if (count_1s(pos.attacks_to(s)) > 63)
2445             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;
2446     }
2447   }
2448
2449
2450   // fail_high_ply_1() checks if some thread is currently resolving a fail
2451   // high at ply 1 at the node below the first root node.  This information
2452   // is used for time managment.
2453
2454   bool fail_high_ply_1() {
2455
2456     for(int i = 0; i < ActiveThreads; i++)
2457         if (Threads[i].failHighPly1)
2458             return true;
2459
2460     return false;
2461   }
2462
2463
2464   // current_search_time() returns the number of milliseconds which have passed
2465   // since the beginning of the current search.
2466
2467   int current_search_time() {
2468     return get_system_time() - SearchStartTime;
2469   }
2470
2471
2472   // nps() computes the current nodes/second count.
2473
2474   int nps() {
2475     int t = current_search_time();
2476     return (t > 0)? int((nodes_searched() * 1000) / t) : 0;
2477   }
2478
2479
2480   // poll() performs two different functions:  It polls for user input, and it
2481   // looks at the time consumed so far and decides if it's time to abort the
2482   // search.
2483
2484   void poll() {
2485
2486     static int lastInfoTime;
2487     int t = current_search_time();
2488
2489     //  Poll for input
2490     if (Bioskey())
2491     {
2492         // We are line oriented, don't read single chars
2493         std::string command;
2494         if (!std::getline(std::cin, command))
2495             command = "quit";
2496
2497         if (command == "quit")
2498         {
2499             AbortSearch = true;
2500             PonderSearch = false;
2501             Quit = true;
2502             return;
2503         }
2504         else if (command == "stop")
2505         {
2506             AbortSearch = true;
2507             PonderSearch = false;
2508         }
2509         else if (command == "ponderhit")
2510             ponderhit();
2511     }
2512     // Print search information
2513     if (t < 1000)
2514         lastInfoTime = 0;
2515
2516     else if (lastInfoTime > t)
2517         // HACK: Must be a new search where we searched less than
2518         // NodesBetweenPolls nodes during the first second of search.
2519         lastInfoTime = 0;
2520
2521     else if (t - lastInfoTime >= 1000)
2522     {
2523         lastInfoTime = t;
2524         lock_grab(&IOLock);
2525         if (dbg_show_mean)
2526             dbg_print_mean();
2527
2528         if (dbg_show_hit_rate)
2529             dbg_print_hit_rate();
2530
2531         std::cout << "info nodes " << nodes_searched() << " nps " << nps()
2532                   << " time " << t << " hashfull " << TT.full() << std::endl;
2533         lock_release(&IOLock);
2534         if (ShowCurrentLine)
2535             Threads[0].printCurrentLine = true;
2536     }
2537     // Should we stop the search?
2538     if (PonderSearch)
2539         return;
2540
2541     bool overTime =     t > AbsoluteMaxSearchTime
2542                      || (RootMoveNumber == 1 && t > MaxSearchTime + ExtraSearchTime && !FailLow) //FIXME: We are not checking any problem flags, BUG?
2543                      || (  !FailHigh && !FailLow && !fail_high_ply_1() && !Problem
2544                          && t > 6*(MaxSearchTime + ExtraSearchTime));
2545
2546     if (   (Iteration >= 3 && (!InfiniteSearch && overTime))
2547         || (ExactMaxTime && t >= ExactMaxTime)
2548         || (Iteration >= 3 && MaxNodes && nodes_searched() >= MaxNodes))
2549         AbortSearch = true;
2550   }
2551
2552
2553   // ponderhit() is called when the program is pondering (i.e. thinking while
2554   // it's the opponent's turn to move) in order to let the engine know that
2555   // it correctly predicted the opponent's move.
2556
2557   void ponderhit() {
2558
2559     int t = current_search_time();
2560     PonderSearch = false;
2561     if (Iteration >= 3 &&
2562        (!InfiniteSearch && (StopOnPonderhit ||
2563                             t > AbsoluteMaxSearchTime ||
2564                             (RootMoveNumber == 1 &&
2565                              t > MaxSearchTime + ExtraSearchTime && !FailLow) ||
2566                             (!FailHigh && !FailLow && !fail_high_ply_1() && !Problem &&
2567                              t > 6*(MaxSearchTime + ExtraSearchTime)))))
2568       AbortSearch = true;
2569   }
2570
2571
2572   // print_current_line() prints the current line of search for a given
2573   // thread.  Called when the UCI option UCI_ShowCurrLine is 'true'.
2574
2575   void print_current_line(SearchStack ss[], int ply, int threadID) {
2576
2577     assert(ply >= 0 && ply < PLY_MAX);
2578     assert(threadID >= 0 && threadID < ActiveThreads);
2579
2580     if (!Threads[threadID].idle)
2581     {
2582         lock_grab(&IOLock);
2583         std::cout << "info currline " << (threadID + 1);
2584         for (int p = 0; p < ply; p++)
2585             std::cout << " " << ss[p].currentMove;
2586
2587         std::cout << std::endl;
2588         lock_release(&IOLock);
2589     }
2590     Threads[threadID].printCurrentLine = false;
2591     if (threadID + 1 < ActiveThreads)
2592         Threads[threadID + 1].printCurrentLine = true;
2593   }
2594
2595
2596   // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2597   // while the program is pondering.  The point is to work around a wrinkle in
2598   // the UCI protocol:  When pondering, the engine is not allowed to give a
2599   // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2600   // We simply wait here until one of these commands is sent, and return,
2601   // after which the bestmove and pondermove will be printed (in id_loop()).
2602
2603   void wait_for_stop_or_ponderhit() {
2604
2605     std::string command;
2606
2607     while (true)
2608     {
2609         if (!std::getline(std::cin, command))
2610             command = "quit";
2611
2612         if (command == "quit")
2613         {
2614             Quit = true;
2615             break;
2616         }
2617         else if (command == "ponderhit" || command == "stop")
2618             break;
2619     }
2620   }
2621
2622
2623   // idle_loop() is where the threads are parked when they have no work to do.
2624   // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint
2625   // object for which the current thread is the master.
2626
2627   void idle_loop(int threadID, SplitPoint* waitSp) {
2628     assert(threadID >= 0 && threadID < THREAD_MAX);
2629
2630     Threads[threadID].running = true;
2631
2632     while(true) {
2633       if(AllThreadsShouldExit && threadID != 0)
2634         break;
2635
2636       // If we are not thinking, wait for a condition to be signaled instead
2637       // of wasting CPU time polling for work:
2638       while(threadID != 0 && (Idle || threadID >= ActiveThreads)) {
2639 #if !defined(_MSC_VER)
2640         pthread_mutex_lock(&WaitLock);
2641         if(Idle || threadID >= ActiveThreads)
2642           pthread_cond_wait(&WaitCond, &WaitLock);
2643         pthread_mutex_unlock(&WaitLock);
2644 #else
2645         WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2646 #endif
2647       }
2648
2649       // If this thread has been assigned work, launch a search
2650       if(Threads[threadID].workIsWaiting) {
2651         Threads[threadID].workIsWaiting = false;
2652         if(Threads[threadID].splitPoint->pvNode)
2653           sp_search_pv(Threads[threadID].splitPoint, threadID);
2654         else
2655           sp_search(Threads[threadID].splitPoint, threadID);
2656         Threads[threadID].idle = true;
2657       }
2658
2659       // If this thread is the master of a split point and all threads have
2660       // finished their work at this split point, return from the idle loop.
2661       if(waitSp != NULL && waitSp->cpus == 0)
2662         return;
2663     }
2664
2665     Threads[threadID].running = false;
2666   }
2667
2668
2669   // init_split_point_stack() is called during program initialization, and
2670   // initializes all split point objects.
2671
2672   void init_split_point_stack() {
2673     for(int i = 0; i < THREAD_MAX; i++)
2674       for(int j = 0; j < MaxActiveSplitPoints; j++) {
2675         SplitPointStack[i][j].parent = NULL;
2676         lock_init(&(SplitPointStack[i][j].lock), NULL);
2677       }
2678   }
2679
2680
2681   // destroy_split_point_stack() is called when the program exits, and
2682   // destroys all locks in the precomputed split point objects.
2683
2684   void destroy_split_point_stack() {
2685     for(int i = 0; i < THREAD_MAX; i++)
2686       for(int j = 0; j < MaxActiveSplitPoints; j++)
2687         lock_destroy(&(SplitPointStack[i][j].lock));
2688   }
2689
2690
2691   // thread_should_stop() checks whether the thread with a given threadID has
2692   // been asked to stop, directly or indirectly.  This can happen if a beta
2693   // cutoff has occured in thre thread's currently active split point, or in
2694   // some ancestor of the current split point.
2695
2696   bool thread_should_stop(int threadID) {
2697     assert(threadID >= 0 && threadID < ActiveThreads);
2698
2699     SplitPoint* sp;
2700
2701     if(Threads[threadID].stop)
2702       return true;
2703     if(ActiveThreads <= 2)
2704       return false;
2705     for(sp = Threads[threadID].splitPoint; sp != NULL; sp = sp->parent)
2706       if(sp->finished) {
2707         Threads[threadID].stop = true;
2708         return true;
2709       }
2710     return false;
2711   }
2712
2713
2714   // thread_is_available() checks whether the thread with threadID "slave" is
2715   // available to help the thread with threadID "master" at a split point.  An
2716   // obvious requirement is that "slave" must be idle.  With more than two
2717   // threads, this is not by itself sufficient:  If "slave" is the master of
2718   // some active split point, it is only available as a slave to the other
2719   // threads which are busy searching the split point at the top of "slave"'s
2720   // split point stack (the "helpful master concept" in YBWC terminology).
2721
2722   bool thread_is_available(int slave, int master) {
2723     assert(slave >= 0 && slave < ActiveThreads);
2724     assert(master >= 0 && master < ActiveThreads);
2725     assert(ActiveThreads > 1);
2726
2727     if(!Threads[slave].idle || slave == master)
2728       return false;
2729
2730     if(Threads[slave].activeSplitPoints == 0)
2731       // No active split points means that the thread is available as a slave
2732       // for any other thread.
2733       return true;
2734
2735     if(ActiveThreads == 2)
2736       return true;
2737
2738     // Apply the "helpful master" concept if possible.
2739     if(SplitPointStack[slave][Threads[slave].activeSplitPoints-1].slaves[master])
2740       return true;
2741
2742     return false;
2743   }
2744
2745
2746   // idle_thread_exists() tries to find an idle thread which is available as
2747   // a slave for the thread with threadID "master".
2748
2749   bool idle_thread_exists(int master) {
2750     assert(master >= 0 && master < ActiveThreads);
2751     assert(ActiveThreads > 1);
2752
2753     for(int i = 0; i < ActiveThreads; i++)
2754       if(thread_is_available(i, master))
2755         return true;
2756     return false;
2757   }
2758
2759
2760   // split() does the actual work of distributing the work at a node between
2761   // several threads at PV nodes.  If it does not succeed in splitting the
2762   // node (because no idle threads are available, or because we have no unused
2763   // split point objects), the function immediately returns false.  If
2764   // splitting is possible, a SplitPoint object is initialized with all the
2765   // data that must be copied to the helper threads (the current position and
2766   // search stack, alpha, beta, the search depth, etc.), and we tell our
2767   // helper threads that they have been assigned work.  This will cause them
2768   // to instantly leave their idle loops and call sp_search_pv().  When all
2769   // threads have returned from sp_search_pv (or, equivalently, when
2770   // splitPoint->cpus becomes 0), split() returns true.
2771
2772   bool split(const Position& p, SearchStack* sstck, int ply,
2773              Value* alpha, Value* beta, Value* bestValue, Depth depth, int* moves,
2774              MovePicker* mp, Bitboard dcCandidates, int master, bool pvNode) {
2775
2776     assert(p.is_ok());
2777     assert(sstck != NULL);
2778     assert(ply >= 0 && ply < PLY_MAX);
2779     assert(*bestValue >= -VALUE_INFINITE && *bestValue <= *alpha);
2780     assert(!pvNode || *alpha < *beta);
2781     assert(*beta <= VALUE_INFINITE);
2782     assert(depth > Depth(0));
2783     assert(master >= 0 && master < ActiveThreads);
2784     assert(ActiveThreads > 1);
2785
2786     SplitPoint* splitPoint;
2787     int i;
2788
2789     lock_grab(&MPLock);
2790
2791     // If no other thread is available to help us, or if we have too many
2792     // active split points, don't split.
2793     if(!idle_thread_exists(master) ||
2794        Threads[master].activeSplitPoints >= MaxActiveSplitPoints) {
2795       lock_release(&MPLock);
2796       return false;
2797     }
2798
2799     // Pick the next available split point object from the split point stack
2800     splitPoint = SplitPointStack[master] + Threads[master].activeSplitPoints;
2801     Threads[master].activeSplitPoints++;
2802
2803     // Initialize the split point object
2804     splitPoint->parent = Threads[master].splitPoint;
2805     splitPoint->finished = false;
2806     splitPoint->ply = ply;
2807     splitPoint->depth = depth;
2808     splitPoint->alpha = pvNode? *alpha : (*beta - 1);
2809     splitPoint->beta = *beta;
2810     splitPoint->pvNode = pvNode;
2811     splitPoint->dcCandidates = dcCandidates;
2812     splitPoint->bestValue = *bestValue;
2813     splitPoint->master = master;
2814     splitPoint->mp = mp;
2815     splitPoint->moves = *moves;
2816     splitPoint->cpus = 1;
2817     splitPoint->pos.copy(p);
2818     splitPoint->parentSstack = sstck;
2819     for(i = 0; i < ActiveThreads; i++)
2820       splitPoint->slaves[i] = 0;
2821
2822     // Copy the current position and the search stack to the master thread
2823     memcpy(splitPoint->sstack[master], sstck, (ply+1)*sizeof(SearchStack));
2824     Threads[master].splitPoint = splitPoint;
2825
2826     // Make copies of the current position and search stack for each thread
2827     for(i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint;
2828         i++)
2829       if(thread_is_available(i, master)) {
2830         memcpy(splitPoint->sstack[i], sstck, (ply+1)*sizeof(SearchStack));
2831         Threads[i].splitPoint = splitPoint;
2832         splitPoint->slaves[i] = 1;
2833         splitPoint->cpus++;
2834       }
2835
2836     // Tell the threads that they have work to do.  This will make them leave
2837     // their idle loop.
2838     for(i = 0; i < ActiveThreads; i++)
2839       if(i == master || splitPoint->slaves[i]) {
2840         Threads[i].workIsWaiting = true;
2841         Threads[i].idle = false;
2842         Threads[i].stop = false;
2843       }
2844
2845     lock_release(&MPLock);
2846
2847     // Everything is set up.  The master thread enters the idle loop, from
2848     // which it will instantly launch a search, because its workIsWaiting
2849     // slot is 'true'.  We send the split point as a second parameter to the
2850     // idle loop, which means that the main thread will return from the idle
2851     // loop when all threads have finished their work at this split point
2852     // (i.e. when // splitPoint->cpus == 0).
2853     idle_loop(master, splitPoint);
2854
2855     // We have returned from the idle loop, which means that all threads are
2856     // finished. Update alpha, beta and bestvalue, and return.
2857     lock_grab(&MPLock);
2858     if(pvNode) *alpha = splitPoint->alpha;
2859     *beta = splitPoint->beta;
2860     *bestValue = splitPoint->bestValue;
2861     Threads[master].stop = false;
2862     Threads[master].idle = false;
2863     Threads[master].activeSplitPoints--;
2864     Threads[master].splitPoint = splitPoint->parent;
2865     lock_release(&MPLock);
2866
2867     return true;
2868   }
2869
2870
2871   // wake_sleeping_threads() wakes up all sleeping threads when it is time
2872   // to start a new search from the root.
2873
2874   void wake_sleeping_threads() {
2875     if(ActiveThreads > 1) {
2876       for(int i = 1; i < ActiveThreads; i++) {
2877         Threads[i].idle = true;
2878         Threads[i].workIsWaiting = false;
2879       }
2880 #if !defined(_MSC_VER)
2881       pthread_mutex_lock(&WaitLock);
2882       pthread_cond_broadcast(&WaitCond);
2883       pthread_mutex_unlock(&WaitLock);
2884 #else
2885       for(int i = 1; i < THREAD_MAX; i++)
2886         SetEvent(SitIdleEvent[i]);
2887 #endif
2888     }
2889   }
2890
2891
2892   // init_thread() is the function which is called when a new thread is
2893   // launched.  It simply calls the idle_loop() function with the supplied
2894   // threadID.  There are two versions of this function; one for POSIX threads
2895   // and one for Windows threads.
2896
2897 #if !defined(_MSC_VER)
2898
2899   void *init_thread(void *threadID) {
2900     idle_loop(*(int *)threadID, NULL);
2901     return NULL;
2902   }
2903
2904 #else
2905
2906   DWORD WINAPI init_thread(LPVOID threadID) {
2907     idle_loop(*(int *)threadID, NULL);
2908     return NULL;
2909   }
2910
2911 #endif
2912
2913 }