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