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