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