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