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