2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2009 Marco Costalba
6 Stockfish is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 Stockfish is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
43 #include "ucioption.h"
47 //// Local definitions
54 // IterationInfoType stores search results for each iteration
56 // Because we use relatively small (dynamic) aspiration window,
57 // there happens many fail highs and fail lows in root. And
58 // because we don't do researches in those cases, "value" stored
59 // here is not necessarily exact. Instead in case of fail high/low
60 // we guess what the right value might be and store our guess
61 // as a "speculated value" and then move on. Speculated values are
62 // used just to calculate aspiration window width, so also if are
63 // not exact is not big a problem.
65 struct IterationInfoType {
67 IterationInfoType(Value v = Value(0), Value sv = Value(0))
68 : value(v), speculatedValue(sv) {}
70 Value value, speculatedValue;
74 // The BetaCounterType class is used to order moves at ply one.
75 // Apart for the first one that has its score, following moves
76 // normally have score -VALUE_INFINITE, so are ordered according
77 // to the number of beta cutoffs occurred under their subtree during
78 // the last iteration. The counters are per thread variables to avoid
79 // concurrent accessing under SMP case.
81 struct BetaCounterType {
85 void add(Color us, Depth d, int threadID);
86 void read(Color us, int64_t& our, int64_t& their);
90 // The RootMove class is used for moves at the root at the tree. For each
91 // root move, we store a score, a node count, and a PV (really a refutation
92 // in the case of moves which fail low).
97 bool operator<(const RootMove&); // used to sort
101 int64_t nodes, cumulativeNodes;
102 Move pv[PLY_MAX_PLUS_2];
103 int64_t ourBeta, theirBeta;
107 // The RootMoveList class is essentially an array of RootMove objects, with
108 // a handful of methods for accessing the data in the individual moves.
113 RootMoveList(Position& pos, Move searchMoves[]);
114 inline Move get_move(int moveNum) const;
115 inline Value get_move_score(int moveNum) const;
116 inline void set_move_score(int moveNum, Value score);
117 inline void set_move_nodes(int moveNum, int64_t nodes);
118 inline void set_beta_counters(int moveNum, int64_t our, int64_t their);
119 void set_move_pv(int moveNum, const Move pv[]);
120 inline Move get_move_pv(int moveNum, int i) const;
121 inline int64_t get_move_cumulative_nodes(int moveNum) const;
122 inline int move_count() const;
123 Move scan_for_easy_move() const;
125 void sort_multipv(int n);
128 static const int MaxRootMoves = 500;
129 RootMove moves[MaxRootMoves];
136 // Search depth at iteration 1
137 const Depth InitialDepth = OnePly /*+ OnePly/2*/;
139 // Depth limit for selective search
140 const Depth SelectiveDepth = 7 * OnePly;
142 // Use internal iterative deepening?
143 const bool UseIIDAtPVNodes = true;
144 const bool UseIIDAtNonPVNodes = false;
146 // Internal iterative deepening margin. At Non-PV moves, when
147 // UseIIDAtNonPVNodes is true, we do an internal iterative deepening
148 // search when the static evaluation is at most IIDMargin below beta.
149 const Value IIDMargin = Value(0x100);
151 // Easy move margin. An easy move candidate must be at least this much
152 // better than the second best move.
153 const Value EasyMoveMargin = Value(0x200);
155 // Problem margin. If the score of the first move at iteration N+1 has
156 // dropped by more than this since iteration N, the boolean variable
157 // "Problem" is set to true, which will make the program spend some extra
158 // time looking for a better move.
159 const Value ProblemMargin = Value(0x28);
161 // No problem margin. If the boolean "Problem" is true, and a new move
162 // is found at the root which is less than NoProblemMargin worse than the
163 // best move from the previous iteration, Problem is set back to false.
164 const Value NoProblemMargin = Value(0x14);
166 // Null move margin. A null move search will not be done if the approximate
167 // evaluation of the position is more than NullMoveMargin below beta.
168 const Value NullMoveMargin = Value(0x300);
170 // Pruning criterions. See the code and comments in ok_to_prune() to
171 // understand their precise meaning.
172 const bool PruneEscapeMoves = false;
173 const bool PruneDefendingMoves = false;
174 const bool PruneBlockingMoves = false;
176 // Margins for futility pruning in the quiescence search, and at frontier
177 // and near frontier nodes.
178 const Value FutilityMarginQS = Value(0x80);
180 // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply
181 const Value FutilityMargins[12] = { Value(0x100), Value(0x120), Value(0x200), Value(0x220), Value(0x250), Value(0x270),
182 // 4 ply 4.5 ply 5 ply 5.5 ply 6 ply 6.5 ply
183 Value(0x2A0), Value(0x2C0), Value(0x340), Value(0x360), Value(0x3A0), Value(0x3C0) };
185 const Depth RazorDepth = 4*OnePly;
187 // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply
188 const Value RazorMargins[6] = { Value(0x180), Value(0x300), Value(0x300), Value(0x3C0), Value(0x3C0), Value(0x3C0) };
190 // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply
191 const Value RazorApprMargins[6] = { Value(0x520), Value(0x300), Value(0x300), Value(0x300), Value(0x300), Value(0x300) };
193 // The main transposition table
194 TranspositionTable TT;
197 /// Variables initialized by UCI options
199 // Adjustable playing strength
201 const int SlowdownArray[32] = {
202 19, 41, 70, 110, 160, 230, 320, 430, 570, 756, 1000, 1300, 1690, 2197,
203 2834, 3600, 4573, 5809, 7700, 9863, 12633, 16181, 20726, 26584, 34005,
204 43557, 55792, 71463, 91536, 117247, 150180, 192363
207 const int MaxStrength = 25;
209 // Minimum number of full depth (i.e. non-reduced) moves at PV and non-PV nodes
210 int LMRPVMoves, LMRNonPVMoves; // heavy SMP read access for the latter
212 // Depth limit for use of dynamic threat detection
213 Depth ThreatDepth; // heavy SMP read access
215 // Last seconds noise filtering (LSN)
216 const bool UseLSNFiltering = true;
217 const int LSNTime = 4000; // In milliseconds
218 const Value LSNValue = value_from_centipawns(200);
219 bool loseOnTime = false;
221 // Extensions. Array index 0 is used at non-PV nodes, index 1 at PV nodes.
222 // There is heavy SMP read access on these arrays
223 Depth CheckExtension[2], SingleReplyExtension[2], PawnPushTo7thExtension[2];
224 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
226 // Iteration counters
228 BetaCounterType BetaCounter; // has per-thread internal data
230 // Scores and number of times the best move changed for each iteration
231 IterationInfoType IterationInfo[PLY_MAX_PLUS_2];
232 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
237 // Time managment variables
239 int MaxNodes, MaxDepth;
240 int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
244 bool StopOnPonderhit;
245 bool AbortSearch; // heavy SMP read access
251 // Show current line?
252 bool ShowCurrentLine;
256 std::ofstream LogFile;
258 // MP related variables
259 int ActiveThreads = 1;
260 Depth MinimumSplitDepth;
261 int MaxThreadsPerSplitPoint;
262 Thread Threads[THREAD_MAX];
265 bool AllThreadsShouldExit = false;
266 const int MaxActiveSplitPoints = 8;
267 SplitPoint SplitPointStack[THREAD_MAX][MaxActiveSplitPoints];
270 #if !defined(_MSC_VER)
271 pthread_cond_t WaitCond;
272 pthread_mutex_t WaitLock;
274 HANDLE SitIdleEvent[THREAD_MAX];
277 // Node counters, used only by thread[0] but try to keep in different
278 // cache lines (64 bytes each) from the heavy SMP read accessed variables.
280 int NodesBetweenPolls = 30000;
288 Value id_loop(const Position& pos, Move searchMoves[]);
289 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta);
290 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
291 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID);
292 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
293 void sp_search(SplitPoint* sp, int threadID);
294 void sp_search_pv(SplitPoint* sp, int threadID);
295 void init_node(const Position& pos, SearchStack ss[], int ply, int threadID);
296 void update_pv(SearchStack ss[], int ply);
297 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply);
298 bool connected_moves(const Position& pos, Move m1, Move m2);
299 bool value_is_mate(Value value);
300 bool move_is_killer(Move m, const SearchStack& ss);
301 Depth extension(const Position& pos, Move m, bool pvNode, bool capture, bool check, bool singleReply, bool mateThreat, bool* dangerous);
302 bool ok_to_do_nullmove(const Position& pos);
303 bool ok_to_prune(const Position& pos, Move m, Move threat, Depth d);
304 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
305 bool ok_to_history(const Position& pos, Move m);
306 void update_history(const Position& pos, Move m, Depth depth, Move movesSearched[], int moveCount);
307 void update_killers(Move m, SearchStack& ss);
308 void slowdown(const Position& pos);
310 bool fail_high_ply_1();
311 int current_search_time();
315 void print_current_line(SearchStack ss[], int ply, int threadID);
316 void wait_for_stop_or_ponderhit();
318 void idle_loop(int threadID, SplitPoint* waitSp);
319 void init_split_point_stack();
320 void destroy_split_point_stack();
321 bool thread_should_stop(int threadID);
322 bool thread_is_available(int slave, int master);
323 bool idle_thread_exists(int master);
324 bool split(const Position& pos, SearchStack* ss, int ply,
325 Value *alpha, Value *beta, Value *bestValue, Depth depth, int *moves,
326 MovePicker *mp, Bitboard dcCandidates, int master, bool pvNode);
327 void wake_sleeping_threads();
329 #if !defined(_MSC_VER)
330 void *init_thread(void *threadID);
332 DWORD WINAPI init_thread(LPVOID threadID);
342 /// think() is the external interface to Stockfish's search, and is called when
343 /// the program receives the UCI 'go' command. It initializes various
344 /// search-related global variables, and calls root_search(). It returns false
345 /// when a quit command is received during the search.
347 bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
348 int time[], int increment[], int movesToGo, int maxDepth,
349 int maxNodes, int maxTime, Move searchMoves[]) {
351 // Look for a book move
352 if (!infinite && !ponder && get_option_value_bool("OwnBook"))
355 if (get_option_value_string("Book File") != OpeningBook.file_name())
356 OpeningBook.open("book.bin");
358 bookMove = OpeningBook.get_move(pos);
359 if (bookMove != MOVE_NONE)
361 std::cout << "bestmove " << bookMove << std::endl;
366 // Initialize global search variables
368 SearchStartTime = get_system_time();
369 for (int i = 0; i < THREAD_MAX; i++)
371 Threads[i].nodes = 0ULL;
372 Threads[i].failHighPly1 = false;
375 InfiniteSearch = infinite;
376 PonderSearch = ponder;
377 StopOnPonderhit = false;
383 ExactMaxTime = maxTime;
385 // Read UCI option values
386 TT.set_size(get_option_value_int("Hash"));
387 if (button_was_pressed("Clear Hash"))
390 loseOnTime = false; // reset at the beginning of a new game
393 bool PonderingEnabled = get_option_value_bool("Ponder");
394 MultiPV = get_option_value_int("MultiPV");
396 CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)"));
397 CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)"));
399 SingleReplyExtension[1] = Depth(get_option_value_int("Single Reply Extension (PV nodes)"));
400 SingleReplyExtension[0] = Depth(get_option_value_int("Single Reply Extension (non-PV nodes)"));
402 PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)"));
403 PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
405 PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
406 PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
408 PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
409 PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)"));
411 MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
412 MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
414 LMRPVMoves = get_option_value_int("Full Depth Moves (PV nodes)") + 1;
415 LMRNonPVMoves = get_option_value_int("Full Depth Moves (non-PV nodes)") + 1;
416 ThreatDepth = get_option_value_int("Threat Depth") * OnePly;
418 Chess960 = get_option_value_bool("UCI_Chess960");
419 ShowCurrentLine = get_option_value_bool("UCI_ShowCurrLine");
420 UseLogFile = get_option_value_bool("Use Search Log");
422 LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app);
424 MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly;
425 MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point");
427 read_weights(pos.side_to_move());
429 // Set the number of active threads. If UCI_LimitStrength is enabled, never
430 // use more than one thread.
431 int newActiveThreads =
432 get_option_value_bool("UCI_LimitStrength")? 1 : get_option_value_int("Threads");
433 if (newActiveThreads != ActiveThreads)
435 ActiveThreads = newActiveThreads;
436 init_eval(ActiveThreads);
439 // Wake up sleeping threads
440 wake_sleeping_threads();
442 for (int i = 1; i < ActiveThreads; i++)
443 assert(thread_is_available(i, 0));
445 // Set playing strength
446 if (get_option_value_bool("UCI_LimitStrength"))
448 Strength = (get_option_value_int("UCI_Elo") - 2100) / 25;
450 (Strength == MaxStrength)? 0 : SlowdownArray[Max(0, 31-Strength)];
454 Strength = MaxStrength;
459 int myTime = time[side_to_move];
460 int myIncrement = increment[side_to_move];
462 if (!movesToGo) // Sudden death time control
466 MaxSearchTime = myTime / 30 + myIncrement;
467 AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
468 } else { // Blitz game without increment
469 MaxSearchTime = myTime / 30;
470 AbsoluteMaxSearchTime = myTime / 8;
473 else // (x moves) / (y minutes)
477 MaxSearchTime = myTime / 2;
478 AbsoluteMaxSearchTime = Min(myTime / 2, myTime - 500);
480 MaxSearchTime = myTime / Min(movesToGo, 20);
481 AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
485 if (PonderingEnabled)
487 MaxSearchTime += MaxSearchTime / 4;
488 MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime);
491 // Fixed depth or fixed number of nodes?
494 InfiniteSearch = true; // HACK
499 NodesBetweenPolls = Min(MaxNodes, 30000);
500 InfiniteSearch = true; // HACK
503 if (Slowdown > 50000) NodesBetweenPolls = 30;
504 else if (Slowdown > 10000) NodesBetweenPolls = 100;
505 else if (Slowdown > 1000) NodesBetweenPolls = 500;
506 else if (Slowdown > 100) NodesBetweenPolls = 3000;
507 else NodesBetweenPolls = 15000;
510 NodesBetweenPolls = 30000;
512 // Write information to search log file
514 LogFile << "Searching: " << pos.to_fen() << std::endl
515 << "infinite: " << infinite
516 << " ponder: " << ponder
517 << " time: " << myTime
518 << " increment: " << myIncrement
519 << " moves to go: " << movesToGo << std::endl;
522 // We're ready to start thinking. Call the iterative deepening loop function
524 // FIXME we really need to cleanup all this LSN ugliness
527 Value v = id_loop(pos, searchMoves);
528 loseOnTime = ( UseLSNFiltering
535 loseOnTime = false; // reset for next match
536 while (SearchStartTime + myTime + 1000 > get_system_time())
538 id_loop(pos, searchMoves); // to fail gracefully
549 /// init_threads() is called during startup. It launches all helper threads,
550 /// and initializes the split point stack and the global locks and condition
553 void init_threads() {
557 #if !defined(_MSC_VER)
558 pthread_t pthread[1];
561 for (i = 0; i < THREAD_MAX; i++)
562 Threads[i].activeSplitPoints = 0;
564 // Initialize global locks
565 lock_init(&MPLock, NULL);
566 lock_init(&IOLock, NULL);
568 init_split_point_stack();
570 #if !defined(_MSC_VER)
571 pthread_mutex_init(&WaitLock, NULL);
572 pthread_cond_init(&WaitCond, NULL);
574 for (i = 0; i < THREAD_MAX; i++)
575 SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0);
578 // All threads except the main thread should be initialized to idle state
579 for (i = 1; i < THREAD_MAX; i++)
581 Threads[i].stop = false;
582 Threads[i].workIsWaiting = false;
583 Threads[i].idle = true;
584 Threads[i].running = false;
587 // Launch the helper threads
588 for(i = 1; i < THREAD_MAX; i++)
590 #if !defined(_MSC_VER)
591 pthread_create(pthread, NULL, init_thread, (void*)(&i));
594 CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID);
597 // Wait until the thread has finished launching
598 while (!Threads[i].running);
603 /// stop_threads() is called when the program exits. It makes all the
604 /// helper threads exit cleanly.
606 void stop_threads() {
608 ActiveThreads = THREAD_MAX; // HACK
609 Idle = false; // HACK
610 wake_sleeping_threads();
611 AllThreadsShouldExit = true;
612 for (int i = 1; i < THREAD_MAX; i++)
614 Threads[i].stop = true;
615 while(Threads[i].running);
617 destroy_split_point_stack();
621 /// nodes_searched() returns the total number of nodes searched so far in
622 /// the current search.
624 int64_t nodes_searched() {
626 int64_t result = 0ULL;
627 for (int i = 0; i < ActiveThreads; i++)
628 result += Threads[i].nodes;
633 // SearchStack::init() initializes a search stack. Used at the beginning of a
634 // new search from the root.
635 void SearchStack::init(int ply) {
637 pv[ply] = pv[ply + 1] = MOVE_NONE;
638 currentMove = threatMove = MOVE_NONE;
639 reduction = Depth(0);
642 void SearchStack::initKillers() {
644 mateKiller = MOVE_NONE;
645 for (int i = 0; i < KILLER_MAX; i++)
646 killers[i] = MOVE_NONE;
651 // id_loop() is the main iterative deepening loop. It calls root_search
652 // repeatedly with increasing depth until the allocated thinking time has
653 // been consumed, the user stops the search, or the maximum search depth is
656 Value id_loop(const Position& pos, Move searchMoves[]) {
659 SearchStack ss[PLY_MAX_PLUS_2];
661 // searchMoves are verified, copied, scored and sorted
662 RootMoveList rml(p, searchMoves);
667 for (int i = 0; i < 3; i++)
672 IterationInfo[1] = IterationInfoType(rml.get_move_score(0), rml.get_move_score(0));
675 Move EasyMove = rml.scan_for_easy_move();
677 // Iterative deepening loop
678 while (Iteration < PLY_MAX)
680 // Initialize iteration
683 BestMoveChangesByIteration[Iteration] = 0;
687 std::cout << "info depth " << Iteration << std::endl;
689 // Calculate dynamic search window based on previous iterations
692 if (MultiPV == 1 && Iteration >= 6 && abs(IterationInfo[Iteration - 1].value) < VALUE_KNOWN_WIN)
694 int prevDelta1 = IterationInfo[Iteration - 1].speculatedValue - IterationInfo[Iteration - 2].speculatedValue;
695 int prevDelta2 = IterationInfo[Iteration - 2].speculatedValue - IterationInfo[Iteration - 3].speculatedValue;
697 int delta = Max(2 * abs(prevDelta1) + abs(prevDelta2), ProblemMargin);
699 alpha = Max(IterationInfo[Iteration - 1].value - delta, -VALUE_INFINITE);
700 beta = Min(IterationInfo[Iteration - 1].value + delta, VALUE_INFINITE);
704 alpha = - VALUE_INFINITE;
705 beta = VALUE_INFINITE;
708 // Search to the current depth
709 Value value = root_search(p, ss, rml, alpha, beta);
711 // Write PV to transposition table, in case the relevant entries have
712 // been overwritten during the search.
713 TT.insert_pv(p, ss[0].pv);
716 break; // Value cannot be trusted. Break out immediately!
718 //Save info about search result
719 Value speculatedValue;
722 Value delta = value - IterationInfo[Iteration - 1].value;
729 speculatedValue = value + delta;
730 BestMoveChangesByIteration[Iteration] += 2; // Allocate more time
732 else if (value <= alpha)
734 assert(value == alpha);
738 speculatedValue = value + delta;
739 BestMoveChangesByIteration[Iteration] += 3; // Allocate more time
741 speculatedValue = value;
743 speculatedValue = Min(Max(speculatedValue, -VALUE_INFINITE), VALUE_INFINITE);
744 IterationInfo[Iteration] = IterationInfoType(value, speculatedValue);
746 // Erase the easy move if it differs from the new best move
747 if (ss[0].pv[0] != EasyMove)
748 EasyMove = MOVE_NONE;
755 bool stopSearch = false;
757 // Stop search early if there is only a single legal move
758 if (Iteration >= 6 && rml.move_count() == 1)
761 // Stop search early when the last two iterations returned a mate score
763 && abs(IterationInfo[Iteration].value) >= abs(VALUE_MATE) - 100
764 && abs(IterationInfo[Iteration-1].value) >= abs(VALUE_MATE) - 100)
767 // Stop search early if one move seems to be much better than the rest
768 int64_t nodes = nodes_searched();
772 && EasyMove == ss[0].pv[0]
773 && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
774 && current_search_time() > MaxSearchTime / 16)
775 ||( rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100
776 && current_search_time() > MaxSearchTime / 32)))
779 // Add some extra time if the best move has changed during the last two iterations
780 if (Iteration > 5 && Iteration <= 50)
781 ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2)
782 + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3);
784 // Stop search if most of MaxSearchTime is consumed at the end of the
785 // iteration. We probably don't have enough time to search the first
786 // move at the next iteration anyway.
787 if (current_search_time() > ((MaxSearchTime + ExtraSearchTime)*80) / 128)
792 //FIXME: Implement fail-low emergency measures
796 StopOnPonderhit = true;
800 if (MaxDepth && Iteration >= MaxDepth)
806 // If we are pondering, we shouldn't print the best move before we
809 wait_for_stop_or_ponderhit();
811 // Print final search statistics
812 std::cout << "info nodes " << nodes_searched()
814 << " time " << current_search_time()
815 << " hashfull " << TT.full() << std::endl;
817 // Print the best move and the ponder move to the standard output
818 if (ss[0].pv[0] == MOVE_NONE)
820 ss[0].pv[0] = rml.get_move(0);
821 ss[0].pv[1] = MOVE_NONE;
823 std::cout << "bestmove " << ss[0].pv[0];
824 if (ss[0].pv[1] != MOVE_NONE)
825 std::cout << " ponder " << ss[0].pv[1];
827 std::cout << std::endl;
832 dbg_print_mean(LogFile);
834 if (dbg_show_hit_rate)
835 dbg_print_hit_rate(LogFile);
838 LogFile << "Nodes: " << nodes_searched() << std::endl
839 << "Nodes/second: " << nps() << std::endl
840 << "Best move: " << move_to_san(p, ss[0].pv[0]) << std::endl;
842 p.do_move(ss[0].pv[0], st);
843 LogFile << "Ponder move: " << move_to_san(p, ss[0].pv[1])
844 << std::endl << std::endl;
846 return rml.get_move_score(0);
850 // root_search() is the function which searches the root node. It is
851 // similar to search_pv except that it uses a different move ordering
852 // scheme (perhaps we should try to use this at internal PV nodes, too?)
853 // and prints some information to the standard output.
855 Value root_search(Position& pos, SearchStack ss[], RootMoveList &rml, Value alpha, Value beta) {
857 Value oldAlpha = alpha;
859 Bitboard dcCandidates = pos.discovered_check_candidates(pos.side_to_move());
861 // Loop through all the moves in the root move list
862 for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
866 // We failed high, invalidate and skip next moves, leave node-counters
867 // and beta-counters as they are and quickly return, we will try to do
868 // a research at the next iteration with a bigger aspiration window.
869 rml.set_move_score(i, -VALUE_INFINITE);
877 RootMoveNumber = i + 1;
880 // Remember the node count before the move is searched. The node counts
881 // are used to sort the root moves at the next iteration.
882 nodes = nodes_searched();
884 // Reset beta cut-off counters
887 // Pick the next root move, and print the move and the move number to
888 // the standard output.
889 move = ss[0].currentMove = rml.get_move(i);
890 if (current_search_time() >= 1000)
891 std::cout << "info currmove " << move
892 << " currmovenumber " << i + 1 << std::endl;
894 // Decide search depth for this move
895 bool moveIsCapture = pos.move_is_capture(move);
897 ext = extension(pos, move, true, pos.move_is_capture(move), pos.move_is_check(move), false, false, &dangerous);
898 newDepth = (Iteration - 2) * OnePly + ext + InitialDepth;
900 // Make the move, and search it
901 pos.do_move(move, st, dcCandidates);
905 // Aspiration window is disabled in multi-pv case
907 alpha = -VALUE_INFINITE;
909 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
910 // If the value has dropped a lot compared to the last iteration,
911 // set the boolean variable Problem to true. This variable is used
912 // for time managment: When Problem is true, we try to complete the
913 // current iteration before playing a move.
914 Problem = (Iteration >= 2 && value <= IterationInfo[Iteration-1].value - ProblemMargin);
916 if (Problem && StopOnPonderhit)
917 StopOnPonderhit = false;
921 if (newDepth >= 3*OnePly
922 && i + MultiPV >= LMRPVMoves
925 && !move_is_promotion(move)
926 && !move_is_castle(move))
928 ss[0].reduction = OnePly;
929 value = -search(pos, ss, -alpha, newDepth-OnePly, 1, true, 0);
932 value = alpha + 1; // Just to trigger next condition
935 value = -search(pos, ss, -alpha, newDepth, 1, true, 0);
938 // Fail high! Set the boolean variable FailHigh to true, and
939 // re-search the move with a big window. The variable FailHigh is
940 // used for time managment: We try to avoid aborting the search
941 // prematurely during a fail high research.
943 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
950 // Finished searching the move. If AbortSearch is true, the search
951 // was aborted because the user interrupted the search or because we
952 // ran out of time. In this case, the return value of the search cannot
953 // be trusted, and we break out of the loop without updating the best
958 // Remember the node count for this move. The node counts are used to
959 // sort the root moves at the next iteration.
960 rml.set_move_nodes(i, nodes_searched() - nodes);
962 // Remember the beta-cutoff statistics
964 BetaCounter.read(pos.side_to_move(), our, their);
965 rml.set_beta_counters(i, our, their);
967 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
969 if (value <= alpha && i >= MultiPV)
970 rml.set_move_score(i, -VALUE_INFINITE);
973 // PV move or new best move!
976 rml.set_move_score(i, value);
978 TT.extract_pv(pos, ss[0].pv);
979 rml.set_move_pv(i, ss[0].pv);
983 // We record how often the best move has been changed in each
984 // iteration. This information is used for time managment: When
985 // the best move changes frequently, we allocate some more time.
987 BestMoveChangesByIteration[Iteration]++;
989 // Print search information to the standard output
990 std::cout << "info depth " << Iteration
991 << " score " << value_to_string(value)
992 << " time " << current_search_time()
993 << " nodes " << nodes_searched()
997 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
998 std::cout << ss[0].pv[j] << " ";
1000 std::cout << std::endl;
1003 LogFile << pretty_pv(pos, current_search_time(), Iteration, nodes_searched(), value, ss[0].pv)
1009 // Reset the global variable Problem to false if the value isn't too
1010 // far below the final value from the last iteration.
1011 if (value > IterationInfo[Iteration - 1].value - NoProblemMargin)
1016 rml.sort_multipv(i);
1017 for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
1020 std::cout << "info multipv " << j + 1
1021 << " score " << value_to_string(rml.get_move_score(j))
1022 << " depth " << ((j <= i)? Iteration : Iteration - 1)
1023 << " time " << current_search_time()
1024 << " nodes " << nodes_searched()
1028 for (k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
1029 std::cout << rml.get_move_pv(j, k) << " ";
1031 std::cout << std::endl;
1033 alpha = rml.get_move_score(Min(i, MultiPV-1));
1035 } // New best move case
1037 assert(alpha >= oldAlpha);
1039 FailLow = (alpha == oldAlpha);
1045 // search_pv() is the main search function for PV nodes.
1047 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta,
1048 Depth depth, int ply, int threadID) {
1050 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1051 assert(beta > alpha && beta <= VALUE_INFINITE);
1052 assert(ply >= 0 && ply < PLY_MAX);
1053 assert(threadID >= 0 && threadID < ActiveThreads);
1056 return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID);
1058 // Initialize, and make an early exit in case of an aborted search,
1059 // an instant draw, maximum ply reached, etc.
1060 init_node(pos, ss, ply, threadID);
1062 // After init_node() that calls poll()
1063 if (AbortSearch || thread_should_stop(threadID))
1071 if (ply >= PLY_MAX - 1)
1072 return evaluate(pos, ei, threadID);
1074 // Mate distance pruning
1075 Value oldAlpha = alpha;
1076 alpha = Max(value_mated_in(ply), alpha);
1077 beta = Min(value_mate_in(ply+1), beta);
1081 // Transposition table lookup. At PV nodes, we don't use the TT for
1082 // pruning, but only for move ordering.
1083 const TTEntry* tte = TT.retrieve(pos.get_key());
1084 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1086 // Go with internal iterative deepening if we don't have a TT move
1087 if (UseIIDAtPVNodes && ttMove == MOVE_NONE && depth >= 5*OnePly)
1089 search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID);
1090 ttMove = ss[ply].pv[ply];
1093 // Initialize a MovePicker object for the current position, and prepare
1094 // to search all moves
1095 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1097 Move move, movesSearched[256];
1099 Value value, bestValue = -VALUE_INFINITE;
1100 Bitboard dcCandidates = mp.discovered_check_candidates();
1101 Color us = pos.side_to_move();
1102 bool isCheck = pos.is_check();
1103 bool mateThreat = pos.has_mate_threat(opposite_color(us));
1105 // Loop through all legal moves until no moves remain or a beta cutoff
1107 while ( alpha < beta
1108 && (move = mp.get_next_move()) != MOVE_NONE
1109 && !thread_should_stop(threadID))
1111 assert(move_is_ok(move));
1113 bool singleReply = (isCheck && mp.number_of_moves() == 1);
1114 bool moveIsCheck = pos.move_is_check(move, dcCandidates);
1115 bool moveIsCapture = pos.move_is_capture(move);
1117 movesSearched[moveCount++] = ss[ply].currentMove = move;
1119 // Decide the new search depth
1121 Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous);
1122 Depth newDepth = depth - OnePly + ext;
1124 // Make and search the move
1126 pos.do_move(move, st, dcCandidates);
1128 if (moveCount == 1) // The first move in list is the PV
1129 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1132 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1133 // if the move fails high will be re-searched at full depth.
1134 if ( depth >= 3*OnePly
1135 && moveCount >= LMRPVMoves
1138 && !move_is_promotion(move)
1139 && !move_is_castle(move)
1140 && !move_is_killer(move, ss[ply]))
1142 ss[ply].reduction = OnePly;
1143 value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, threadID);
1146 value = alpha + 1; // Just to trigger next condition
1148 if (value > alpha) // Go with full depth non-pv search
1150 ss[ply].reduction = Depth(0);
1151 value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID);
1152 if (value > alpha && value < beta)
1154 // When the search fails high at ply 1 while searching the first
1155 // move at the root, set the flag failHighPly1. This is used for
1156 // time managment: We don't want to stop the search early in
1157 // such cases, because resolving the fail high at ply 1 could
1158 // result in a big drop in score at the root.
1159 if (ply == 1 && RootMoveNumber == 1)
1160 Threads[threadID].failHighPly1 = true;
1162 // A fail high occurred. Re-search at full window (pv search)
1163 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1164 Threads[threadID].failHighPly1 = false;
1168 pos.undo_move(move);
1170 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1173 if (value > bestValue)
1180 if (value == value_mate_in(ply + 1))
1181 ss[ply].mateKiller = move;
1183 // If we are at ply 1, and we are searching the first root move at
1184 // ply 0, set the 'Problem' variable if the score has dropped a lot
1185 // (from the computer's point of view) since the previous iteration.
1188 && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
1193 if ( ActiveThreads > 1
1195 && depth >= MinimumSplitDepth
1197 && idle_thread_exists(threadID)
1199 && !thread_should_stop(threadID)
1200 && split(pos, ss, ply, &alpha, &beta, &bestValue, depth,
1201 &moveCount, &mp, dcCandidates, threadID, true))
1205 // All legal moves have been searched. A special case: If there were
1206 // no legal moves, it must be mate or stalemate.
1208 return (isCheck ? value_mated_in(ply) : VALUE_DRAW);
1210 // If the search is not aborted, update the transposition table,
1211 // history counters, and killer moves.
1212 if (AbortSearch || thread_should_stop(threadID))
1215 if (bestValue <= oldAlpha)
1216 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1218 else if (bestValue >= beta)
1220 BetaCounter.add(pos.side_to_move(), depth, threadID);
1221 Move m = ss[ply].pv[ply];
1222 if (ok_to_history(pos, m)) // Only non capture moves are considered
1224 update_history(pos, m, depth, movesSearched, moveCount);
1225 update_killers(m, ss[ply]);
1227 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m);
1230 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
1236 // search() is the search function for zero-width nodes.
1238 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth,
1239 int ply, bool allowNullmove, int threadID) {
1241 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1242 assert(ply >= 0 && ply < PLY_MAX);
1243 assert(threadID >= 0 && threadID < ActiveThreads);
1246 return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1248 // Initialize, and make an early exit in case of an aborted search,
1249 // an instant draw, maximum ply reached, etc.
1250 init_node(pos, ss, ply, threadID);
1252 // After init_node() that calls poll()
1253 if (AbortSearch || thread_should_stop(threadID))
1261 if (ply >= PLY_MAX - 1)
1262 return evaluate(pos, ei, threadID);
1264 // Mate distance pruning
1265 if (value_mated_in(ply) >= beta)
1268 if (value_mate_in(ply + 1) < beta)
1271 // Transposition table lookup
1272 const TTEntry* tte = TT.retrieve(pos.get_key());
1273 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1275 if (tte && ok_to_use_TT(tte, depth, beta, ply))
1277 ss[ply].currentMove = ttMove; // can be MOVE_NONE
1278 return value_from_tt(tte->value(), ply);
1281 Value approximateEval = quick_evaluate(pos);
1282 bool mateThreat = false;
1283 bool isCheck = pos.is_check();
1289 && !value_is_mate(beta)
1290 && ok_to_do_nullmove(pos)
1291 && approximateEval >= beta - NullMoveMargin)
1293 ss[ply].currentMove = MOVE_NULL;
1296 pos.do_null_move(st);
1297 int R = (depth >= 5 * OnePly ? 4 : 3); // Null move dynamic reduction
1299 Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);
1301 pos.undo_null_move();
1303 if (nullValue >= beta)
1305 if (depth < 6 * OnePly)
1308 // Do zugzwang verification search
1309 Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
1313 // The null move failed low, which means that we may be faced with
1314 // some kind of threat. If the previous move was reduced, check if
1315 // the move that refuted the null move was somehow connected to the
1316 // move which was reduced. If a connection is found, return a fail
1317 // low score (which will cause the reduced move to fail high in the
1318 // parent node, which will trigger a re-search with full depth).
1319 if (nullValue == value_mated_in(ply + 2))
1322 ss[ply].threatMove = ss[ply + 1].currentMove;
1323 if ( depth < ThreatDepth
1324 && ss[ply - 1].reduction
1325 && connected_moves(pos, ss[ply - 1].currentMove, ss[ply].threatMove))
1329 // Null move search not allowed, try razoring
1330 else if ( !value_is_mate(beta)
1331 && depth < RazorDepth
1332 && approximateEval < beta - RazorApprMargins[int(depth) - 2]
1333 && ss[ply - 1].currentMove != MOVE_NULL
1334 && ttMove == MOVE_NONE
1335 && !pos.has_pawn_on_7th(pos.side_to_move()))
1337 Value v = qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1338 if (v < beta - RazorMargins[int(depth) - 2])
1342 // Go with internal iterative deepening if we don't have a TT move
1343 if (UseIIDAtNonPVNodes && ttMove == MOVE_NONE && depth >= 8*OnePly &&
1344 evaluate(pos, ei, threadID) >= beta - IIDMargin)
1346 search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID);
1347 ttMove = ss[ply].pv[ply];
1350 // Initialize a MovePicker object for the current position, and prepare
1351 // to search all moves.
1352 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1354 Move move, movesSearched[256];
1356 Value value, bestValue = -VALUE_INFINITE;
1357 Bitboard dcCandidates = mp.discovered_check_candidates();
1358 Value futilityValue = VALUE_NONE;
1359 bool useFutilityPruning = depth < SelectiveDepth
1362 // Loop through all legal moves until no moves remain or a beta cutoff
1364 while ( bestValue < beta
1365 && (move = mp.get_next_move()) != MOVE_NONE
1366 && !thread_should_stop(threadID))
1368 assert(move_is_ok(move));
1370 bool singleReply = (isCheck && mp.number_of_moves() == 1);
1371 bool moveIsCheck = pos.move_is_check(move, dcCandidates);
1372 bool moveIsCapture = pos.move_is_capture(move);
1374 movesSearched[moveCount++] = ss[ply].currentMove = move;
1376 // Decide the new search depth
1378 Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous);
1379 Depth newDepth = depth - OnePly + ext;
1382 if ( useFutilityPruning
1385 && !move_is_promotion(move))
1387 // History pruning. See ok_to_prune() definition
1388 if ( moveCount >= 2 + int(depth)
1389 && ok_to_prune(pos, move, ss[ply].threatMove, depth))
1392 // Value based pruning
1393 if (approximateEval < beta)
1395 if (futilityValue == VALUE_NONE)
1396 futilityValue = evaluate(pos, ei, threadID)
1397 + FutilityMargins[int(depth) - 2];
1399 if (futilityValue < beta)
1401 if (futilityValue > bestValue)
1402 bestValue = futilityValue;
1408 // Make and search the move
1410 pos.do_move(move, st, dcCandidates);
1412 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1413 // if the move fails high will be re-searched at full depth.
1414 if ( depth >= 3*OnePly
1415 && moveCount >= LMRNonPVMoves
1418 && !move_is_promotion(move)
1419 && !move_is_castle(move)
1420 && !move_is_killer(move, ss[ply]))
1422 ss[ply].reduction = OnePly;
1423 value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);
1426 value = beta; // Just to trigger next condition
1428 if (value >= beta) // Go with full depth non-pv search
1430 ss[ply].reduction = Depth(0);
1431 value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID);
1433 pos.undo_move(move);
1435 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1438 if (value > bestValue)
1444 if (value == value_mate_in(ply + 1))
1445 ss[ply].mateKiller = move;
1449 if ( ActiveThreads > 1
1451 && depth >= MinimumSplitDepth
1453 && idle_thread_exists(threadID)
1455 && !thread_should_stop(threadID)
1456 && split(pos, ss, ply, &beta, &beta, &bestValue, depth, &moveCount,
1457 &mp, dcCandidates, threadID, false))
1461 // All legal moves have been searched. A special case: If there were
1462 // no legal moves, it must be mate or stalemate.
1464 return (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW);
1466 // If the search is not aborted, update the transposition table,
1467 // history counters, and killer moves.
1468 if (AbortSearch || thread_should_stop(threadID))
1471 if (bestValue < beta)
1472 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1475 BetaCounter.add(pos.side_to_move(), depth, threadID);
1476 Move m = ss[ply].pv[ply];
1477 if (ok_to_history(pos, m)) // Only non capture moves are considered
1479 update_history(pos, m, depth, movesSearched, moveCount);
1480 update_killers(m, ss[ply]);
1482 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m);
1485 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1491 // qsearch() is the quiescence search function, which is called by the main
1492 // search function when the remaining depth is zero (or, to be more precise,
1493 // less than OnePly).
1495 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta,
1496 Depth depth, int ply, int threadID) {
1498 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1499 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1501 assert(ply >= 0 && ply < PLY_MAX);
1502 assert(threadID >= 0 && threadID < ActiveThreads);
1504 // Initialize, and make an early exit in case of an aborted search,
1505 // an instant draw, maximum ply reached, etc.
1506 init_node(pos, ss, ply, threadID);
1508 // After init_node() that calls poll()
1509 if (AbortSearch || thread_should_stop(threadID))
1515 // Transposition table lookup, only when not in PV
1516 TTEntry* tte = NULL;
1517 bool pvNode = (beta - alpha != 1);
1520 tte = TT.retrieve(pos.get_key());
1521 if (tte && ok_to_use_TT(tte, depth, beta, ply))
1523 assert(tte->type() != VALUE_TYPE_EVAL);
1525 return value_from_tt(tte->value(), ply);
1528 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1530 // Evaluate the position statically
1533 bool isCheck = pos.is_check();
1534 ei.futilityMargin = Value(0); // Manually initialize futilityMargin
1537 staticValue = -VALUE_INFINITE;
1539 else if (tte && tte->type() == VALUE_TYPE_EVAL)
1541 // Use the cached evaluation score if possible
1542 assert(ei.futilityMargin == Value(0));
1544 staticValue = tte->value();
1547 staticValue = evaluate(pos, ei, threadID);
1549 if (ply == PLY_MAX - 1)
1550 return evaluate(pos, ei, threadID);
1552 // Initialize "stand pat score", and return it immediately if it is
1554 Value bestValue = staticValue;
1556 if (bestValue >= beta)
1558 // Store the score to avoid a future costly evaluation() call
1559 if (!isCheck && !tte && ei.futilityMargin == 0)
1560 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EVAL, Depth(-127*OnePly), MOVE_NONE);
1565 if (bestValue > alpha)
1568 // Initialize a MovePicker object for the current position, and prepare
1569 // to search the moves. Because the depth is <= 0 here, only captures,
1570 // queen promotions and checks (only if depth == 0) will be generated.
1571 MovePicker mp = MovePicker(pos, ttMove, depth, H);
1574 Bitboard dcCandidates = mp.discovered_check_candidates();
1575 Color us = pos.side_to_move();
1576 bool enoughMaterial = pos.non_pawn_material(us) > RookValueMidgame;
1578 // Loop through the moves until no moves remain or a beta cutoff
1580 while ( alpha < beta
1581 && (move = mp.get_next_move()) != MOVE_NONE)
1583 assert(move_is_ok(move));
1586 ss[ply].currentMove = move;
1592 && !move_is_promotion(move)
1593 && !pos.move_is_check(move, dcCandidates)
1594 && !pos.move_is_passed_pawn_push(move))
1596 Value futilityValue = staticValue
1597 + Max(pos.midgame_value_of_piece_on(move_to(move)),
1598 pos.endgame_value_of_piece_on(move_to(move)))
1599 + (move_is_ep(move) ? PawnValueEndgame : Value(0))
1601 + ei.futilityMargin;
1603 if (futilityValue < alpha)
1605 if (futilityValue > bestValue)
1606 bestValue = futilityValue;
1611 // Don't search captures and checks with negative SEE values
1613 && !move_is_promotion(move)
1614 && pos.see_sign(move) < 0)
1617 // Make and search the move.
1619 pos.do_move(move, st, dcCandidates);
1620 Value value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID);
1621 pos.undo_move(move);
1623 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1626 if (value > bestValue)
1637 // All legal moves have been searched. A special case: If we're in check
1638 // and no legal moves were found, it is checkmate.
1639 if (pos.is_check() && moveCount == 0) // Mate!
1640 return value_mated_in(ply);
1642 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1644 // Update transposition table
1645 Move m = ss[ply].pv[ply];
1648 Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
1649 if (bestValue < beta)
1650 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, d, MOVE_NONE);
1652 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, m);
1655 // Update killers only for good check moves
1656 if (alpha >= beta && ok_to_history(pos, m)) // Only non capture moves are considered
1657 update_killers(m, ss[ply]);
1663 // sp_search() is used to search from a split point. This function is called
1664 // by each thread working at the split point. It is similar to the normal
1665 // search() function, but simpler. Because we have already probed the hash
1666 // table, done a null move search, and searched the first move before
1667 // splitting, we don't have to repeat all this work in sp_search(). We
1668 // also don't need to store anything to the hash table here: This is taken
1669 // care of after we return from the split point.
1671 void sp_search(SplitPoint* sp, int threadID) {
1673 assert(threadID >= 0 && threadID < ActiveThreads);
1674 assert(ActiveThreads > 1);
1676 Position pos = Position(sp->pos);
1677 SearchStack* ss = sp->sstack[threadID];
1680 bool isCheck = pos.is_check();
1681 bool useFutilityPruning = sp->depth < SelectiveDepth
1684 while ( sp->bestValue < sp->beta
1685 && !thread_should_stop(threadID)
1686 && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE)
1688 assert(move_is_ok(move));
1690 bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates);
1691 bool moveIsCapture = pos.move_is_capture(move);
1693 lock_grab(&(sp->lock));
1694 int moveCount = ++sp->moves;
1695 lock_release(&(sp->lock));
1697 ss[sp->ply].currentMove = move;
1699 // Decide the new search depth.
1701 Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, false, false, &dangerous);
1702 Depth newDepth = sp->depth - OnePly + ext;
1705 if ( useFutilityPruning
1708 && !move_is_promotion(move)
1709 && moveCount >= 2 + int(sp->depth)
1710 && ok_to_prune(pos, move, ss[sp->ply].threatMove, sp->depth))
1713 // Make and search the move.
1715 pos.do_move(move, st, sp->dcCandidates);
1717 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1718 // if the move fails high will be re-searched at full depth.
1720 && moveCount >= LMRNonPVMoves
1722 && !move_is_promotion(move)
1723 && !move_is_castle(move)
1724 && !move_is_killer(move, ss[sp->ply]))
1726 ss[sp->ply].reduction = OnePly;
1727 value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, true, threadID);
1730 value = sp->beta; // Just to trigger next condition
1732 if (value >= sp->beta) // Go with full depth non-pv search
1734 ss[sp->ply].reduction = Depth(0);
1735 value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID);
1737 pos.undo_move(move);
1739 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1741 if (thread_should_stop(threadID))
1745 lock_grab(&(sp->lock));
1746 if (value > sp->bestValue && !thread_should_stop(threadID))
1748 sp->bestValue = value;
1749 if (sp->bestValue >= sp->beta)
1751 sp_update_pv(sp->parentSstack, ss, sp->ply);
1752 for (int i = 0; i < ActiveThreads; i++)
1753 if (i != threadID && (i == sp->master || sp->slaves[i]))
1754 Threads[i].stop = true;
1756 sp->finished = true;
1759 lock_release(&(sp->lock));
1762 lock_grab(&(sp->lock));
1764 // If this is the master thread and we have been asked to stop because of
1765 // a beta cutoff higher up in the tree, stop all slave threads.
1766 if (sp->master == threadID && thread_should_stop(threadID))
1767 for (int i = 0; i < ActiveThreads; i++)
1769 Threads[i].stop = true;
1772 sp->slaves[threadID] = 0;
1774 lock_release(&(sp->lock));
1778 // sp_search_pv() is used to search from a PV split point. This function
1779 // is called by each thread working at the split point. It is similar to
1780 // the normal search_pv() function, but simpler. Because we have already
1781 // probed the hash table and searched the first move before splitting, we
1782 // don't have to repeat all this work in sp_search_pv(). We also don't
1783 // need to store anything to the hash table here: This is taken care of
1784 // after we return from the split point.
1786 void sp_search_pv(SplitPoint* sp, int threadID) {
1788 assert(threadID >= 0 && threadID < ActiveThreads);
1789 assert(ActiveThreads > 1);
1791 Position pos = Position(sp->pos);
1792 SearchStack* ss = sp->sstack[threadID];
1796 while ( sp->alpha < sp->beta
1797 && !thread_should_stop(threadID)
1798 && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE)
1800 bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates);
1801 bool moveIsCapture = pos.move_is_capture(move);
1803 assert(move_is_ok(move));
1805 lock_grab(&(sp->lock));
1806 int moveCount = ++sp->moves;
1807 lock_release(&(sp->lock));
1809 ss[sp->ply].currentMove = move;
1811 // Decide the new search depth.
1813 Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, false, false, &dangerous);
1814 Depth newDepth = sp->depth - OnePly + ext;
1816 // Make and search the move.
1818 pos.do_move(move, st, sp->dcCandidates);
1820 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1821 // if the move fails high will be re-searched at full depth.
1823 && moveCount >= LMRPVMoves
1825 && !move_is_promotion(move)
1826 && !move_is_castle(move)
1827 && !move_is_killer(move, ss[sp->ply]))
1829 ss[sp->ply].reduction = OnePly;
1830 value = -search(pos, ss, -sp->alpha, newDepth - OnePly, sp->ply+1, true, threadID);
1833 value = sp->alpha + 1; // Just to trigger next condition
1835 if (value > sp->alpha) // Go with full depth non-pv search
1837 ss[sp->ply].reduction = Depth(0);
1838 value = -search(pos, ss, -sp->alpha, newDepth, sp->ply+1, true, threadID);
1840 if (value > sp->alpha && value < sp->beta)
1842 // When the search fails high at ply 1 while searching the first
1843 // move at the root, set the flag failHighPly1. This is used for
1844 // time managment: We don't want to stop the search early in
1845 // such cases, because resolving the fail high at ply 1 could
1846 // result in a big drop in score at the root.
1847 if (sp->ply == 1 && RootMoveNumber == 1)
1848 Threads[threadID].failHighPly1 = true;
1850 value = -search_pv(pos, ss, -sp->beta, -sp->alpha, newDepth, sp->ply+1, threadID);
1851 Threads[threadID].failHighPly1 = false;
1854 pos.undo_move(move);
1856 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1858 if (thread_should_stop(threadID))
1862 lock_grab(&(sp->lock));
1863 if (value > sp->bestValue && !thread_should_stop(threadID))
1865 sp->bestValue = value;
1866 if (value > sp->alpha)
1869 sp_update_pv(sp->parentSstack, ss, sp->ply);
1870 if (value == value_mate_in(sp->ply + 1))
1871 ss[sp->ply].mateKiller = move;
1873 if (value >= sp->beta)
1875 for (int i = 0; i < ActiveThreads; i++)
1876 if (i != threadID && (i == sp->master || sp->slaves[i]))
1877 Threads[i].stop = true;
1879 sp->finished = true;
1882 // If we are at ply 1, and we are searching the first root move at
1883 // ply 0, set the 'Problem' variable if the score has dropped a lot
1884 // (from the computer's point of view) since the previous iteration.
1887 && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
1890 lock_release(&(sp->lock));
1893 lock_grab(&(sp->lock));
1895 // If this is the master thread and we have been asked to stop because of
1896 // a beta cutoff higher up in the tree, stop all slave threads.
1897 if (sp->master == threadID && thread_should_stop(threadID))
1898 for (int i = 0; i < ActiveThreads; i++)
1900 Threads[i].stop = true;
1903 sp->slaves[threadID] = 0;
1905 lock_release(&(sp->lock));
1908 /// The BetaCounterType class
1910 BetaCounterType::BetaCounterType() { clear(); }
1912 void BetaCounterType::clear() {
1914 for (int i = 0; i < THREAD_MAX; i++)
1915 Threads[i].betaCutOffs[WHITE] = Threads[i].betaCutOffs[BLACK] = 0ULL;
1918 void BetaCounterType::add(Color us, Depth d, int threadID) {
1920 // Weighted count based on depth
1921 Threads[threadID].betaCutOffs[us] += unsigned(d);
1924 void BetaCounterType::read(Color us, int64_t& our, int64_t& their) {
1927 for (int i = 0; i < THREAD_MAX; i++)
1929 our += Threads[i].betaCutOffs[us];
1930 their += Threads[i].betaCutOffs[opposite_color(us)];
1935 /// The RootMove class
1939 RootMove::RootMove() {
1940 nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL;
1943 // RootMove::operator<() is the comparison function used when
1944 // sorting the moves. A move m1 is considered to be better
1945 // than a move m2 if it has a higher score, or if the moves
1946 // have equal score but m1 has the higher node count.
1948 bool RootMove::operator<(const RootMove& m) {
1950 if (score != m.score)
1951 return (score < m.score);
1953 return theirBeta <= m.theirBeta;
1956 /// The RootMoveList class
1960 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
1962 MoveStack mlist[MaxRootMoves];
1963 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
1965 // Generate all legal moves
1966 int lm_count = generate_legal_moves(pos, mlist);
1968 // Add each move to the moves[] array
1969 for (int i = 0; i < lm_count; i++)
1971 bool includeMove = includeAllMoves;
1973 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
1974 includeMove = (searchMoves[k] == mlist[i].move);
1979 // Find a quick score for the move
1981 SearchStack ss[PLY_MAX_PLUS_2];
1983 moves[count].move = mlist[i].move;
1984 pos.do_move(moves[count].move, st);
1985 moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0);
1986 pos.undo_move(moves[count].move);
1987 moves[count].pv[0] = moves[count].move;
1988 moves[count].pv[1] = MOVE_NONE; // FIXME
1995 // Simple accessor methods for the RootMoveList class
1997 inline Move RootMoveList::get_move(int moveNum) const {
1998 return moves[moveNum].move;
2001 inline Value RootMoveList::get_move_score(int moveNum) const {
2002 return moves[moveNum].score;
2005 inline void RootMoveList::set_move_score(int moveNum, Value score) {
2006 moves[moveNum].score = score;
2009 inline void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
2010 moves[moveNum].nodes = nodes;
2011 moves[moveNum].cumulativeNodes += nodes;
2014 inline void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
2015 moves[moveNum].ourBeta = our;
2016 moves[moveNum].theirBeta = their;
2019 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
2021 for(j = 0; pv[j] != MOVE_NONE; j++)
2022 moves[moveNum].pv[j] = pv[j];
2023 moves[moveNum].pv[j] = MOVE_NONE;
2026 inline Move RootMoveList::get_move_pv(int moveNum, int i) const {
2027 return moves[moveNum].pv[i];
2030 inline int64_t RootMoveList::get_move_cumulative_nodes(int moveNum) const {
2031 return moves[moveNum].cumulativeNodes;
2034 inline int RootMoveList::move_count() const {
2039 // RootMoveList::scan_for_easy_move() is called at the end of the first
2040 // iteration, and is used to detect an "easy move", i.e. a move which appears
2041 // to be much bester than all the rest. If an easy move is found, the move
2042 // is returned, otherwise the function returns MOVE_NONE. It is very
2043 // important that this function is called at the right moment: The code
2044 // assumes that the first iteration has been completed and the moves have
2045 // been sorted. This is done in RootMoveList c'tor.
2047 Move RootMoveList::scan_for_easy_move() const {
2054 // moves are sorted so just consider the best and the second one
2055 if (get_move_score(0) > get_move_score(1) + EasyMoveMargin)
2061 // RootMoveList::sort() sorts the root move list at the beginning of a new
2064 inline void RootMoveList::sort() {
2066 sort_multipv(count - 1); // all items
2070 // RootMoveList::sort_multipv() sorts the first few moves in the root move
2071 // list by their scores and depths. It is used to order the different PVs
2072 // correctly in MultiPV mode.
2074 void RootMoveList::sort_multipv(int n) {
2076 for (int i = 1; i <= n; i++)
2078 RootMove rm = moves[i];
2080 for (j = i; j > 0 && moves[j-1] < rm; j--)
2081 moves[j] = moves[j-1];
2087 // init_node() is called at the beginning of all the search functions
2088 // (search(), search_pv(), qsearch(), and so on) and initializes the search
2089 // stack object corresponding to the current node. Once every
2090 // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
2091 // for user input and checks whether it is time to stop the search.
2093 void init_node(const Position& pos, SearchStack ss[], int ply, int threadID) {
2095 assert(ply >= 0 && ply < PLY_MAX);
2096 assert(threadID >= 0 && threadID < ActiveThreads);
2098 if (Slowdown && Iteration >= 3)
2101 Threads[threadID].nodes++;
2106 if (NodesSincePoll >= NodesBetweenPolls)
2113 ss[ply+2].initKillers();
2115 if (Threads[threadID].printCurrentLine)
2116 print_current_line(ss, ply, threadID);
2120 // update_pv() is called whenever a search returns a value > alpha. It
2121 // updates the PV in the SearchStack object corresponding to the current
2124 void update_pv(SearchStack ss[], int ply) {
2125 assert(ply >= 0 && ply < PLY_MAX);
2127 ss[ply].pv[ply] = ss[ply].currentMove;
2129 for(p = ply + 1; ss[ply+1].pv[p] != MOVE_NONE; p++)
2130 ss[ply].pv[p] = ss[ply+1].pv[p];
2131 ss[ply].pv[p] = MOVE_NONE;
2135 // sp_update_pv() is a variant of update_pv for use at split points. The
2136 // difference between the two functions is that sp_update_pv also updates
2137 // the PV at the parent node.
2139 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply) {
2140 assert(ply >= 0 && ply < PLY_MAX);
2142 ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
2144 for(p = ply + 1; ss[ply+1].pv[p] != MOVE_NONE; p++)
2145 ss[ply].pv[p] = pss[ply].pv[p] = ss[ply+1].pv[p];
2146 ss[ply].pv[p] = pss[ply].pv[p] = MOVE_NONE;
2150 // connected_moves() tests whether two moves are 'connected' in the sense
2151 // that the first move somehow made the second move possible (for instance
2152 // if the moving piece is the same in both moves). The first move is
2153 // assumed to be the move that was made to reach the current position, while
2154 // the second move is assumed to be a move from the current position.
2156 bool connected_moves(const Position& pos, Move m1, Move m2) {
2157 Square f1, t1, f2, t2;
2159 assert(move_is_ok(m1));
2160 assert(move_is_ok(m2));
2162 if (m2 == MOVE_NONE)
2165 // Case 1: The moving piece is the same in both moves
2171 // Case 2: The destination square for m2 was vacated by m1
2177 // Case 3: Moving through the vacated square
2178 if ( piece_is_slider(pos.piece_on(f2))
2179 && bit_is_set(squares_between(f2, t2), f1))
2182 // Case 4: The destination square for m2 is attacked by the moving piece in m1
2183 if (pos.piece_attacks_square(pos.piece_on(t1), t1, t2))
2186 // Case 5: Discovered check, checking piece is the piece moved in m1
2187 if ( piece_is_slider(pos.piece_on(t1))
2188 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
2189 && !bit_is_set(squares_between(t2, pos.king_square(pos.side_to_move())), t2))
2191 Bitboard occ = pos.occupied_squares();
2192 Color us = pos.side_to_move();
2193 Square ksq = pos.king_square(us);
2194 clear_bit(&occ, f2);
2195 if (pos.type_of_piece_on(t1) == BISHOP)
2197 if (bit_is_set(bishop_attacks_bb(ksq, occ), t1))
2200 else if (pos.type_of_piece_on(t1) == ROOK)
2202 if (bit_is_set(rook_attacks_bb(ksq, occ), t1))
2207 assert(pos.type_of_piece_on(t1) == QUEEN);
2208 if (bit_is_set(queen_attacks_bb(ksq, occ), t1))
2216 // value_is_mate() checks if the given value is a mate one
2217 // eventually compensated for the ply.
2219 bool value_is_mate(Value value) {
2221 assert(abs(value) <= VALUE_INFINITE);
2223 return value <= value_mated_in(PLY_MAX)
2224 || value >= value_mate_in(PLY_MAX);
2228 // move_is_killer() checks if the given move is among the
2229 // killer moves of that ply.
2231 bool move_is_killer(Move m, const SearchStack& ss) {
2233 const Move* k = ss.killers;
2234 for (int i = 0; i < KILLER_MAX; i++, k++)
2242 // extension() decides whether a move should be searched with normal depth,
2243 // or with extended depth. Certain classes of moves (checking moves, in
2244 // particular) are searched with bigger depth than ordinary moves and in
2245 // any case are marked as 'dangerous'. Note that also if a move is not
2246 // extended, as example because the corresponding UCI option is set to zero,
2247 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
2249 Depth extension(const Position& pos, Move m, bool pvNode, bool capture, bool check,
2250 bool singleReply, bool mateThreat, bool* dangerous) {
2252 assert(m != MOVE_NONE);
2254 Depth result = Depth(0);
2255 *dangerous = check | singleReply | mateThreat;
2260 result += CheckExtension[pvNode];
2263 result += SingleReplyExtension[pvNode];
2266 result += MateThreatExtension[pvNode];
2269 if (pos.type_of_piece_on(move_from(m)) == PAWN)
2271 if (pos.move_is_pawn_push_to_7th(m))
2273 result += PawnPushTo7thExtension[pvNode];
2276 if (pos.move_is_passed_pawn_push(m))
2278 result += PassedPawnExtension[pvNode];
2284 && pos.type_of_piece_on(move_to(m)) != PAWN
2285 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
2286 - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))
2287 && !move_is_promotion(m)
2290 result += PawnEndgameExtension[pvNode];
2296 && pos.type_of_piece_on(move_to(m)) != PAWN
2297 && pos.see_sign(m) >= 0)
2303 return Min(result, OnePly);
2307 // ok_to_do_nullmove() looks at the current position and decides whether
2308 // doing a 'null move' should be allowed. In order to avoid zugzwang
2309 // problems, null moves are not allowed when the side to move has very
2310 // little material left. Currently, the test is a bit too simple: Null
2311 // moves are avoided only when the side to move has only pawns left. It's
2312 // probably a good idea to avoid null moves in at least some more
2313 // complicated endgames, e.g. KQ vs KR. FIXME
2315 bool ok_to_do_nullmove(const Position& pos) {
2317 return pos.non_pawn_material(pos.side_to_move()) != Value(0);
2321 // ok_to_prune() tests whether it is safe to forward prune a move. Only
2322 // non-tactical moves late in the move list close to the leaves are
2323 // candidates for pruning.
2325 bool ok_to_prune(const Position& pos, Move m, Move threat, Depth d) {
2327 assert(move_is_ok(m));
2328 assert(threat == MOVE_NONE || move_is_ok(threat));
2329 assert(!move_is_promotion(m));
2330 assert(!pos.move_is_check(m));
2331 assert(!pos.move_is_capture(m));
2332 assert(!pos.move_is_passed_pawn_push(m));
2333 assert(d >= OnePly);
2335 Square mfrom, mto, tfrom, tto;
2337 mfrom = move_from(m);
2339 tfrom = move_from(threat);
2340 tto = move_to(threat);
2342 // Case 1: Castling moves are never pruned
2343 if (move_is_castle(m))
2346 // Case 2: Don't prune moves which move the threatened piece
2347 if (!PruneEscapeMoves && threat != MOVE_NONE && mfrom == tto)
2350 // Case 3: If the threatened piece has value less than or equal to the
2351 // value of the threatening piece, don't prune move which defend it.
2352 if ( !PruneDefendingMoves
2353 && threat != MOVE_NONE
2354 && pos.move_is_capture(threat)
2355 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
2356 || pos.type_of_piece_on(tfrom) == KING)
2357 && pos.move_attacks_square(m, tto))
2360 // Case 4: Don't prune moves with good history
2361 if (!H.ok_to_prune(pos.piece_on(mfrom), mto, d))
2364 // Case 5: If the moving piece in the threatened move is a slider, don't
2365 // prune safe moves which block its ray.
2366 if ( !PruneBlockingMoves
2367 && threat != MOVE_NONE
2368 && piece_is_slider(pos.piece_on(tfrom))
2369 && bit_is_set(squares_between(tfrom, tto), mto)
2370 && pos.see_sign(m) >= 0)
2377 // ok_to_use_TT() returns true if a transposition table score
2378 // can be used at a given point in search.
2380 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
2382 Value v = value_from_tt(tte->value(), ply);
2384 return ( tte->depth() >= depth
2385 || v >= Max(value_mate_in(100), beta)
2386 || v < Min(value_mated_in(100), beta))
2388 && ( (is_lower_bound(tte->type()) && v >= beta)
2389 || (is_upper_bound(tte->type()) && v < beta));
2393 // ok_to_history() returns true if a move m can be stored
2394 // in history. Should be a non capturing move nor a promotion.
2396 bool ok_to_history(const Position& pos, Move m) {
2398 return !pos.move_is_capture(m) && !move_is_promotion(m);
2402 // update_history() registers a good move that produced a beta-cutoff
2403 // in history and marks as failures all the other moves of that ply.
2405 void update_history(const Position& pos, Move m, Depth depth,
2406 Move movesSearched[], int moveCount) {
2408 H.success(pos.piece_on(move_from(m)), move_to(m), depth);
2410 for (int i = 0; i < moveCount - 1; i++)
2412 assert(m != movesSearched[i]);
2413 if (ok_to_history(pos, movesSearched[i]))
2414 H.failure(pos.piece_on(move_from(movesSearched[i])), move_to(movesSearched[i]));
2419 // update_killers() add a good move that produced a beta-cutoff
2420 // among the killer moves of that ply.
2422 void update_killers(Move m, SearchStack& ss) {
2424 if (m == ss.killers[0])
2427 for (int i = KILLER_MAX - 1; i > 0; i--)
2428 ss.killers[i] = ss.killers[i - 1];
2434 // slowdown() simply wastes CPU cycles doing nothing useful. It's used
2435 // in strength handicap mode.
2437 void slowdown(const Position &pos) {
2440 for (i = 0; i < n; i++) {
2441 Square s = Square(i&63);
2442 if (count_1s(pos.attacks_to(s)) > 63)
2443 std::cout << "This can't happen, but I put this string here anyway, in order to prevent the compiler from optimizing away the useless computation." << std::endl;
2448 // fail_high_ply_1() checks if some thread is currently resolving a fail
2449 // high at ply 1 at the node below the first root node. This information
2450 // is used for time managment.
2452 bool fail_high_ply_1() {
2454 for(int i = 0; i < ActiveThreads; i++)
2455 if (Threads[i].failHighPly1)
2462 // current_search_time() returns the number of milliseconds which have passed
2463 // since the beginning of the current search.
2465 int current_search_time() {
2466 return get_system_time() - SearchStartTime;
2470 // nps() computes the current nodes/second count.
2473 int t = current_search_time();
2474 return (t > 0)? int((nodes_searched() * 1000) / t) : 0;
2478 // poll() performs two different functions: It polls for user input, and it
2479 // looks at the time consumed so far and decides if it's time to abort the
2484 static int lastInfoTime;
2485 int t = current_search_time();
2490 // We are line oriented, don't read single chars
2491 std::string command;
2492 if (!std::getline(std::cin, command))
2495 if (command == "quit")
2498 PonderSearch = false;
2502 else if (command == "stop")
2505 PonderSearch = false;
2507 else if (command == "ponderhit")
2510 // Print search information
2514 else if (lastInfoTime > t)
2515 // HACK: Must be a new search where we searched less than
2516 // NodesBetweenPolls nodes during the first second of search.
2519 else if (t - lastInfoTime >= 1000)
2526 if (dbg_show_hit_rate)
2527 dbg_print_hit_rate();
2529 std::cout << "info nodes " << nodes_searched() << " nps " << nps()
2530 << " time " << t << " hashfull " << TT.full() << std::endl;
2531 lock_release(&IOLock);
2532 if (ShowCurrentLine)
2533 Threads[0].printCurrentLine = true;
2535 // Should we stop the search?
2539 bool overTime = t > AbsoluteMaxSearchTime
2540 || (RootMoveNumber == 1 && t > MaxSearchTime + ExtraSearchTime && !FailLow) //FIXME: We are not checking any problem flags, BUG?
2541 || ( !FailHigh && !FailLow && !fail_high_ply_1() && !Problem
2542 && t > 6*(MaxSearchTime + ExtraSearchTime));
2544 if ( (Iteration >= 3 && (!InfiniteSearch && overTime))
2545 || (ExactMaxTime && t >= ExactMaxTime)
2546 || (Iteration >= 3 && MaxNodes && nodes_searched() >= MaxNodes))
2551 // ponderhit() is called when the program is pondering (i.e. thinking while
2552 // it's the opponent's turn to move) in order to let the engine know that
2553 // it correctly predicted the opponent's move.
2557 int t = current_search_time();
2558 PonderSearch = false;
2559 if (Iteration >= 3 &&
2560 (!InfiniteSearch && (StopOnPonderhit ||
2561 t > AbsoluteMaxSearchTime ||
2562 (RootMoveNumber == 1 &&
2563 t > MaxSearchTime + ExtraSearchTime && !FailLow) ||
2564 (!FailHigh && !FailLow && !fail_high_ply_1() && !Problem &&
2565 t > 6*(MaxSearchTime + ExtraSearchTime)))))
2570 // print_current_line() prints the current line of search for a given
2571 // thread. Called when the UCI option UCI_ShowCurrLine is 'true'.
2573 void print_current_line(SearchStack ss[], int ply, int threadID) {
2575 assert(ply >= 0 && ply < PLY_MAX);
2576 assert(threadID >= 0 && threadID < ActiveThreads);
2578 if (!Threads[threadID].idle)
2581 std::cout << "info currline " << (threadID + 1);
2582 for (int p = 0; p < ply; p++)
2583 std::cout << " " << ss[p].currentMove;
2585 std::cout << std::endl;
2586 lock_release(&IOLock);
2588 Threads[threadID].printCurrentLine = false;
2589 if (threadID + 1 < ActiveThreads)
2590 Threads[threadID + 1].printCurrentLine = true;
2594 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2595 // while the program is pondering. The point is to work around a wrinkle in
2596 // the UCI protocol: When pondering, the engine is not allowed to give a
2597 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2598 // We simply wait here until one of these commands is sent, and return,
2599 // after which the bestmove and pondermove will be printed (in id_loop()).
2601 void wait_for_stop_or_ponderhit() {
2603 std::string command;
2607 if (!std::getline(std::cin, command))
2610 if (command == "quit")
2615 else if (command == "ponderhit" || command == "stop")
2621 // idle_loop() is where the threads are parked when they have no work to do.
2622 // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint
2623 // object for which the current thread is the master.
2625 void idle_loop(int threadID, SplitPoint* waitSp) {
2626 assert(threadID >= 0 && threadID < THREAD_MAX);
2628 Threads[threadID].running = true;
2631 if(AllThreadsShouldExit && threadID != 0)
2634 // If we are not thinking, wait for a condition to be signaled instead
2635 // of wasting CPU time polling for work:
2636 while(threadID != 0 && (Idle || threadID >= ActiveThreads)) {
2637 #if !defined(_MSC_VER)
2638 pthread_mutex_lock(&WaitLock);
2639 if(Idle || threadID >= ActiveThreads)
2640 pthread_cond_wait(&WaitCond, &WaitLock);
2641 pthread_mutex_unlock(&WaitLock);
2643 WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2647 // If this thread has been assigned work, launch a search
2648 if(Threads[threadID].workIsWaiting) {
2649 Threads[threadID].workIsWaiting = false;
2650 if(Threads[threadID].splitPoint->pvNode)
2651 sp_search_pv(Threads[threadID].splitPoint, threadID);
2653 sp_search(Threads[threadID].splitPoint, threadID);
2654 Threads[threadID].idle = true;
2657 // If this thread is the master of a split point and all threads have
2658 // finished their work at this split point, return from the idle loop.
2659 if(waitSp != NULL && waitSp->cpus == 0)
2663 Threads[threadID].running = false;
2667 // init_split_point_stack() is called during program initialization, and
2668 // initializes all split point objects.
2670 void init_split_point_stack() {
2671 for(int i = 0; i < THREAD_MAX; i++)
2672 for(int j = 0; j < MaxActiveSplitPoints; j++) {
2673 SplitPointStack[i][j].parent = NULL;
2674 lock_init(&(SplitPointStack[i][j].lock), NULL);
2679 // destroy_split_point_stack() is called when the program exits, and
2680 // destroys all locks in the precomputed split point objects.
2682 void destroy_split_point_stack() {
2683 for(int i = 0; i < THREAD_MAX; i++)
2684 for(int j = 0; j < MaxActiveSplitPoints; j++)
2685 lock_destroy(&(SplitPointStack[i][j].lock));
2689 // thread_should_stop() checks whether the thread with a given threadID has
2690 // been asked to stop, directly or indirectly. This can happen if a beta
2691 // cutoff has occured in thre thread's currently active split point, or in
2692 // some ancestor of the current split point.
2694 bool thread_should_stop(int threadID) {
2695 assert(threadID >= 0 && threadID < ActiveThreads);
2699 if(Threads[threadID].stop)
2701 if(ActiveThreads <= 2)
2703 for(sp = Threads[threadID].splitPoint; sp != NULL; sp = sp->parent)
2705 Threads[threadID].stop = true;
2712 // thread_is_available() checks whether the thread with threadID "slave" is
2713 // available to help the thread with threadID "master" at a split point. An
2714 // obvious requirement is that "slave" must be idle. With more than two
2715 // threads, this is not by itself sufficient: If "slave" is the master of
2716 // some active split point, it is only available as a slave to the other
2717 // threads which are busy searching the split point at the top of "slave"'s
2718 // split point stack (the "helpful master concept" in YBWC terminology).
2720 bool thread_is_available(int slave, int master) {
2721 assert(slave >= 0 && slave < ActiveThreads);
2722 assert(master >= 0 && master < ActiveThreads);
2723 assert(ActiveThreads > 1);
2725 if(!Threads[slave].idle || slave == master)
2728 if(Threads[slave].activeSplitPoints == 0)
2729 // No active split points means that the thread is available as a slave
2730 // for any other thread.
2733 if(ActiveThreads == 2)
2736 // Apply the "helpful master" concept if possible.
2737 if(SplitPointStack[slave][Threads[slave].activeSplitPoints-1].slaves[master])
2744 // idle_thread_exists() tries to find an idle thread which is available as
2745 // a slave for the thread with threadID "master".
2747 bool idle_thread_exists(int master) {
2748 assert(master >= 0 && master < ActiveThreads);
2749 assert(ActiveThreads > 1);
2751 for(int i = 0; i < ActiveThreads; i++)
2752 if(thread_is_available(i, master))
2758 // split() does the actual work of distributing the work at a node between
2759 // several threads at PV nodes. If it does not succeed in splitting the
2760 // node (because no idle threads are available, or because we have no unused
2761 // split point objects), the function immediately returns false. If
2762 // splitting is possible, a SplitPoint object is initialized with all the
2763 // data that must be copied to the helper threads (the current position and
2764 // search stack, alpha, beta, the search depth, etc.), and we tell our
2765 // helper threads that they have been assigned work. This will cause them
2766 // to instantly leave their idle loops and call sp_search_pv(). When all
2767 // threads have returned from sp_search_pv (or, equivalently, when
2768 // splitPoint->cpus becomes 0), split() returns true.
2770 bool split(const Position& p, SearchStack* sstck, int ply,
2771 Value* alpha, Value* beta, Value* bestValue, Depth depth, int* moves,
2772 MovePicker* mp, Bitboard dcCandidates, int master, bool pvNode) {
2775 assert(sstck != NULL);
2776 assert(ply >= 0 && ply < PLY_MAX);
2777 assert(*bestValue >= -VALUE_INFINITE && *bestValue <= *alpha);
2778 assert(!pvNode || *alpha < *beta);
2779 assert(*beta <= VALUE_INFINITE);
2780 assert(depth > Depth(0));
2781 assert(master >= 0 && master < ActiveThreads);
2782 assert(ActiveThreads > 1);
2784 SplitPoint* splitPoint;
2789 // If no other thread is available to help us, or if we have too many
2790 // active split points, don't split.
2791 if(!idle_thread_exists(master) ||
2792 Threads[master].activeSplitPoints >= MaxActiveSplitPoints) {
2793 lock_release(&MPLock);
2797 // Pick the next available split point object from the split point stack
2798 splitPoint = SplitPointStack[master] + Threads[master].activeSplitPoints;
2799 Threads[master].activeSplitPoints++;
2801 // Initialize the split point object
2802 splitPoint->parent = Threads[master].splitPoint;
2803 splitPoint->finished = false;
2804 splitPoint->ply = ply;
2805 splitPoint->depth = depth;
2806 splitPoint->alpha = pvNode? *alpha : (*beta - 1);
2807 splitPoint->beta = *beta;
2808 splitPoint->pvNode = pvNode;
2809 splitPoint->dcCandidates = dcCandidates;
2810 splitPoint->bestValue = *bestValue;
2811 splitPoint->master = master;
2812 splitPoint->mp = mp;
2813 splitPoint->moves = *moves;
2814 splitPoint->cpus = 1;
2815 splitPoint->pos.copy(p);
2816 splitPoint->parentSstack = sstck;
2817 for(i = 0; i < ActiveThreads; i++)
2818 splitPoint->slaves[i] = 0;
2820 // Copy the current position and the search stack to the master thread
2821 memcpy(splitPoint->sstack[master], sstck, (ply+1)*sizeof(SearchStack));
2822 Threads[master].splitPoint = splitPoint;
2824 // Make copies of the current position and search stack for each thread
2825 for(i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint;
2827 if(thread_is_available(i, master)) {
2828 memcpy(splitPoint->sstack[i], sstck, (ply+1)*sizeof(SearchStack));
2829 Threads[i].splitPoint = splitPoint;
2830 splitPoint->slaves[i] = 1;
2834 // Tell the threads that they have work to do. This will make them leave
2836 for(i = 0; i < ActiveThreads; i++)
2837 if(i == master || splitPoint->slaves[i]) {
2838 Threads[i].workIsWaiting = true;
2839 Threads[i].idle = false;
2840 Threads[i].stop = false;
2843 lock_release(&MPLock);
2845 // Everything is set up. The master thread enters the idle loop, from
2846 // which it will instantly launch a search, because its workIsWaiting
2847 // slot is 'true'. We send the split point as a second parameter to the
2848 // idle loop, which means that the main thread will return from the idle
2849 // loop when all threads have finished their work at this split point
2850 // (i.e. when // splitPoint->cpus == 0).
2851 idle_loop(master, splitPoint);
2853 // We have returned from the idle loop, which means that all threads are
2854 // finished. Update alpha, beta and bestvalue, and return.
2856 if(pvNode) *alpha = splitPoint->alpha;
2857 *beta = splitPoint->beta;
2858 *bestValue = splitPoint->bestValue;
2859 Threads[master].stop = false;
2860 Threads[master].idle = false;
2861 Threads[master].activeSplitPoints--;
2862 Threads[master].splitPoint = splitPoint->parent;
2863 lock_release(&MPLock);
2869 // wake_sleeping_threads() wakes up all sleeping threads when it is time
2870 // to start a new search from the root.
2872 void wake_sleeping_threads() {
2873 if(ActiveThreads > 1) {
2874 for(int i = 1; i < ActiveThreads; i++) {
2875 Threads[i].idle = true;
2876 Threads[i].workIsWaiting = false;
2878 #if !defined(_MSC_VER)
2879 pthread_mutex_lock(&WaitLock);
2880 pthread_cond_broadcast(&WaitCond);
2881 pthread_mutex_unlock(&WaitLock);
2883 for(int i = 1; i < THREAD_MAX; i++)
2884 SetEvent(SitIdleEvent[i]);
2890 // init_thread() is the function which is called when a new thread is
2891 // launched. It simply calls the idle_loop() function with the supplied
2892 // threadID. There are two versions of this function; one for POSIX threads
2893 // and one for Windows threads.
2895 #if !defined(_MSC_VER)
2897 void *init_thread(void *threadID) {
2898 idle_loop(*(int *)threadID, NULL);
2904 DWORD WINAPI init_thread(LPVOID threadID) {
2905 idle_loop(*(int *)threadID, NULL);