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-2010 Marco Costalba, Joona Kiiski, Tord Romstad
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"
49 //// Local definitions
55 enum NodeType { NonPV, PV };
57 // ThreadsManager class is used to handle all the threads related stuff in search,
58 // init, starting, parking and, the most important, launching a slave thread at a
59 // split point are what this class does. All the access to shared thread data is
60 // done through this class, so that we avoid using global variables instead.
62 class ThreadsManager {
63 /* As long as the single ThreadsManager object is defined as a global we don't
64 need to explicitly initialize to zero its data members because variables with
65 static storage duration are automatically set to zero before enter main()
71 int active_threads() const { return ActiveThreads; }
72 void set_active_threads(int newActiveThreads) { ActiveThreads = newActiveThreads; }
73 void incrementNodeCounter(int threadID) { threads[threadID].nodes++; }
74 void incrementBetaCounter(Color us, Depth d, int threadID) { threads[threadID].betaCutOffs[us] += unsigned(d); }
76 void resetNodeCounters();
77 void resetBetaCounters();
78 int64_t nodes_searched() const;
79 void get_beta_counters(Color us, int64_t& our, int64_t& their) const;
80 bool available_thread_exists(int master) const;
81 bool thread_is_available(int slave, int master) const;
82 bool thread_should_stop(int threadID) const;
83 void wake_sleeping_threads();
84 void put_threads_to_sleep();
85 void idle_loop(int threadID, SplitPoint* sp);
88 bool split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
89 Depth depth, bool mateThreat, int* moves, MovePicker* mp, int master, bool pvNode);
95 volatile bool AllThreadsShouldExit, AllThreadsShouldSleep;
96 Thread threads[MAX_THREADS];
97 SplitPoint SplitPointStack[MAX_THREADS][ACTIVE_SPLIT_POINTS_MAX];
99 Lock MPLock, WaitLock;
101 #if !defined(_MSC_VER)
102 pthread_cond_t WaitCond;
104 HANDLE SitIdleEvent[MAX_THREADS];
110 // RootMove struct is used for moves at the root at the tree. For each
111 // root move, we store a score, a node count, and a PV (really a refutation
112 // in the case of moves which fail low).
116 RootMove() { nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL; }
118 // RootMove::operator<() is the comparison function used when
119 // sorting the moves. A move m1 is considered to be better
120 // than a move m2 if it has a higher score, or if the moves
121 // have equal score but m1 has the higher node count.
122 bool operator<(const RootMove& m) const {
124 return score != m.score ? score < m.score : theirBeta <= m.theirBeta;
129 int64_t nodes, cumulativeNodes, ourBeta, theirBeta;
130 Move pv[PLY_MAX_PLUS_2];
134 // The RootMoveList class is essentially an array of RootMove objects, with
135 // a handful of methods for accessing the data in the individual moves.
140 RootMoveList(Position& pos, Move searchMoves[]);
142 int move_count() const { return count; }
143 Move get_move(int moveNum) const { return moves[moveNum].move; }
144 Value get_move_score(int moveNum) const { return moves[moveNum].score; }
145 void set_move_score(int moveNum, Value score) { moves[moveNum].score = score; }
146 Move get_move_pv(int moveNum, int i) const { return moves[moveNum].pv[i]; }
147 int64_t get_move_cumulative_nodes(int moveNum) const { return moves[moveNum].cumulativeNodes; }
149 void set_move_nodes(int moveNum, int64_t nodes);
150 void set_beta_counters(int moveNum, int64_t our, int64_t their);
151 void set_move_pv(int moveNum, const Move pv[]);
153 void sort_multipv(int n);
156 static const int MaxRootMoves = 500;
157 RootMove moves[MaxRootMoves];
166 // Maximum depth for razoring
167 const Depth RazorDepth = 4 * OnePly;
169 // Dynamic razoring margin based on depth
170 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
172 // Step 8. Null move search with verification search
174 // Null move margin. A null move search will not be done if the static
175 // evaluation of the position is more than NullMoveMargin below beta.
176 const Value NullMoveMargin = Value(0x200);
178 // Maximum depth for use of dynamic threat detection when null move fails low
179 const Depth ThreatDepth = 5 * OnePly;
181 // Step 9. Internal iterative deepening
183 // Minimum depth for use of internal iterative deepening
184 const Depth IIDDepth[2] = { 8 * OnePly /* non-PV */, 5 * OnePly /* PV */};
186 // At Non-PV nodes we do an internal iterative deepening search
187 // when the static evaluation is at most IIDMargin below beta.
188 const Value IIDMargin = Value(0x100);
190 // Step 11. Decide the new search depth
192 // Extensions. Configurable UCI options
193 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
194 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
195 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
197 // Minimum depth for use of singular extension
198 const Depth SingularExtensionDepth[2] = { 8 * OnePly /* non-PV */, 6 * OnePly /* PV */};
200 // If the TT move is at least SingularExtensionMargin better then the
201 // remaining ones we will extend it.
202 const Value SingularExtensionMargin = Value(0x20);
204 // Step 12. Futility pruning
206 // Futility margin for quiescence search
207 const Value FutilityMarginQS = Value(0x80);
209 // Futility lookup tables (initialized at startup) and their getter functions
210 int32_t FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
211 int FutilityMoveCountArray[32]; // [depth]
213 inline Value futility_margin(Depth d, int mn) { return Value(d < 7 * OnePly ? FutilityMarginsMatrix[Max(d, 0)][Min(mn, 63)] : 2 * VALUE_INFINITE); }
214 inline int futility_move_count(Depth d) { return d < 16 * OnePly ? FutilityMoveCountArray[d] : 512; }
216 // Step 14. Reduced search
218 // Reduction lookup tables (initialized at startup) and their getter functions
219 int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
221 template <NodeType PV>
222 inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
224 // Common adjustments
226 // Search depth at iteration 1
227 const Depth InitialDepth = OnePly;
229 // Easy move margin. An easy move candidate must be at least this much
230 // better than the second best move.
231 const Value EasyMoveMargin = Value(0x200);
233 // Last seconds noise filtering (LSN)
234 const bool UseLSNFiltering = true;
235 const int LSNTime = 4000; // In milliseconds
236 const Value LSNValue = value_from_centipawns(200);
237 bool loseOnTime = false;
245 // Scores and number of times the best move changed for each iteration
246 Value ValueByIteration[PLY_MAX_PLUS_2];
247 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
249 // Search window management
255 // Time managment variables
256 int SearchStartTime, MaxNodes, MaxDepth, MaxSearchTime;
257 int AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
258 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
259 bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
263 std::ofstream LogFile;
265 // Multi-threads related variables
266 Depth MinimumSplitDepth;
267 int MaxThreadsPerSplitPoint;
270 // Node counters, used only by thread[0] but try to keep in different cache
271 // lines (64 bytes each) from the heavy multi-thread read accessed variables.
273 int NodesBetweenPolls = 30000;
280 Value id_loop(const Position& pos, Move searchMoves[]);
281 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
283 template <NodeType PvNode>
284 Value search(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE);
286 template <NodeType PvNode>
287 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
289 template <NodeType PvNode>
290 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
292 void sp_search(SplitPoint* sp, int threadID);
293 void sp_search_pv(SplitPoint* sp, int threadID);
294 void init_node(SearchStack ss[], int ply, int threadID);
295 void update_pv(SearchStack ss[], int ply);
296 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply);
297 bool connected_moves(const Position& pos, Move m1, Move m2);
298 bool value_is_mate(Value value);
299 bool move_is_killer(Move m, const SearchStack& ss);
300 bool ok_to_do_nullmove(const Position& pos);
301 bool ok_to_prune(const Position& pos, Move m, Move threat);
302 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
303 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
304 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
305 void update_killers(Move m, SearchStack& ss);
306 void update_gains(const Position& pos, Move move, Value before, Value after);
308 int current_search_time();
312 void wait_for_stop_or_ponderhit();
313 void init_ss_array(SearchStack ss[]);
314 void print_pv_info(const Position& pos, SearchStack ss[], Value alpha, Value beta, Value value);
316 #if !defined(_MSC_VER)
317 void *init_thread(void *threadID);
319 DWORD WINAPI init_thread(LPVOID threadID);
329 /// init_threads(), exit_threads() and nodes_searched() are helpers to
330 /// give accessibility to some TM methods from outside of current file.
332 void init_threads() { TM.init_threads(); }
333 void exit_threads() { TM.exit_threads(); }
334 int64_t nodes_searched() { return TM.nodes_searched(); }
337 /// perft() is our utility to verify move generation is bug free. All the legal
338 /// moves up to given depth are generated and counted and the sum returned.
340 int perft(Position& pos, Depth depth)
345 MovePicker mp(pos, MOVE_NONE, depth, H);
347 // If we are at the last ply we don't need to do and undo
348 // the moves, just to count them.
349 if (depth <= OnePly) // Replace with '<' to test also qsearch
351 while (mp.get_next_move()) sum++;
355 // Loop through all legal moves
357 while ((move = mp.get_next_move()) != MOVE_NONE)
359 pos.do_move(move, st, ci, pos.move_is_check(move, ci));
360 sum += perft(pos, depth - OnePly);
367 /// think() is the external interface to Stockfish's search, and is called when
368 /// the program receives the UCI 'go' command. It initializes various
369 /// search-related global variables, and calls root_search(). It returns false
370 /// when a quit command is received during the search.
372 bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
373 int time[], int increment[], int movesToGo, int maxDepth,
374 int maxNodes, int maxTime, Move searchMoves[]) {
376 // Initialize global search variables
377 StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
378 MaxSearchTime = AbsoluteMaxSearchTime = ExtraSearchTime = 0;
380 TM.resetNodeCounters();
381 SearchStartTime = get_system_time();
382 ExactMaxTime = maxTime;
385 InfiniteSearch = infinite;
386 PonderSearch = ponder;
387 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
389 // Look for a book move, only during games, not tests
390 if (UseTimeManagement && get_option_value_bool("OwnBook"))
392 if (get_option_value_string("Book File") != OpeningBook.file_name())
393 OpeningBook.open(get_option_value_string("Book File"));
395 Move bookMove = OpeningBook.get_move(pos, get_option_value_bool("Best Book Move"));
396 if (bookMove != MOVE_NONE)
399 wait_for_stop_or_ponderhit();
401 cout << "bestmove " << bookMove << endl;
406 // Reset loseOnTime flag at the beginning of a new game
407 if (button_was_pressed("New Game"))
410 // Read UCI option values
411 TT.set_size(get_option_value_int("Hash"));
412 if (button_was_pressed("Clear Hash"))
415 CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)"));
416 CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)"));
417 SingleEvasionExtension[1] = Depth(get_option_value_int("Single Evasion Extension (PV nodes)"));
418 SingleEvasionExtension[0] = Depth(get_option_value_int("Single Evasion Extension (non-PV nodes)"));
419 PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)"));
420 PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
421 PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
422 PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
423 PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
424 PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)"));
425 MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
426 MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
428 MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly;
429 MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point");
430 MultiPV = get_option_value_int("MultiPV");
431 Chess960 = get_option_value_bool("UCI_Chess960");
432 UseLogFile = get_option_value_bool("Use Search Log");
435 LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app);
437 read_weights(pos.side_to_move());
439 // Set the number of active threads
440 int newActiveThreads = get_option_value_int("Threads");
441 if (newActiveThreads != TM.active_threads())
443 TM.set_active_threads(newActiveThreads);
444 init_eval(TM.active_threads());
447 // Wake up sleeping threads
448 TM.wake_sleeping_threads();
451 int myTime = time[side_to_move];
452 int myIncrement = increment[side_to_move];
453 if (UseTimeManagement)
455 if (!movesToGo) // Sudden death time control
459 MaxSearchTime = myTime / 30 + myIncrement;
460 AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
462 else // Blitz game without increment
464 MaxSearchTime = myTime / 30;
465 AbsoluteMaxSearchTime = myTime / 8;
468 else // (x moves) / (y minutes)
472 MaxSearchTime = myTime / 2;
473 AbsoluteMaxSearchTime = (myTime > 3000)? (myTime - 500) : ((myTime * 3) / 4);
477 MaxSearchTime = myTime / Min(movesToGo, 20);
478 AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
482 if (get_option_value_bool("Ponder"))
484 MaxSearchTime += MaxSearchTime / 4;
485 MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime);
489 // Set best NodesBetweenPolls interval to avoid lagging under
490 // heavy time pressure.
492 NodesBetweenPolls = Min(MaxNodes, 30000);
493 else if (myTime && myTime < 1000)
494 NodesBetweenPolls = 1000;
495 else if (myTime && myTime < 5000)
496 NodesBetweenPolls = 5000;
498 NodesBetweenPolls = 30000;
500 // Write search information to log file
502 LogFile << "Searching: " << pos.to_fen() << endl
503 << "infinite: " << infinite
504 << " ponder: " << ponder
505 << " time: " << myTime
506 << " increment: " << myIncrement
507 << " moves to go: " << movesToGo << endl;
509 // LSN filtering. Used only for developing purposes, disabled by default
513 // Step 2. If after last move we decided to lose on time, do it now!
514 while (SearchStartTime + myTime + 1000 > get_system_time())
518 // We're ready to start thinking. Call the iterative deepening loop function
519 Value v = id_loop(pos, searchMoves);
523 // Step 1. If this is sudden death game and our position is hopeless,
524 // decide to lose on time.
525 if ( !loseOnTime // If we already lost on time, go to step 3.
535 // Step 3. Now after stepping over the time limit, reset flag for next match.
543 TM.put_threads_to_sleep();
549 /// init_search() is called during startup. It initializes various lookup tables
553 // Init our reduction lookup tables
554 for (int i = 1; i < 64; i++) // i == depth (OnePly = 1)
555 for (int j = 1; j < 64; j++) // j == moveNumber
557 double pvRed = log(double(i)) * log(double(j)) / 3.0;
558 double nonPVRed = log(double(i)) * log(double(j)) / 1.5;
559 ReductionMatrix[PV][i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0);
560 ReductionMatrix[NonPV][i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0);
563 // Init futility margins array
564 for (int i = 0; i < 16; i++) // i == depth (OnePly = 2)
565 for (int j = 0; j < 64; j++) // j == moveNumber
567 // FIXME: test using log instead of BSR
568 FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j + 45;
571 // Init futility move count array
572 for (int i = 0; i < 32; i++) // i == depth (OnePly = 2)
573 FutilityMoveCountArray[i] = 3 + (1 << (3 * i / 8));
577 // SearchStack::init() initializes a search stack. Used at the beginning of a
578 // new search from the root.
579 void SearchStack::init(int ply) {
581 pv[ply] = pv[ply + 1] = MOVE_NONE;
582 currentMove = threatMove = MOVE_NONE;
583 reduction = Depth(0);
587 void SearchStack::initKillers() {
589 mateKiller = MOVE_NONE;
590 for (int i = 0; i < KILLER_MAX; i++)
591 killers[i] = MOVE_NONE;
596 // id_loop() is the main iterative deepening loop. It calls root_search
597 // repeatedly with increasing depth until the allocated thinking time has
598 // been consumed, the user stops the search, or the maximum search depth is
601 Value id_loop(const Position& pos, Move searchMoves[]) {
604 SearchStack ss[PLY_MAX_PLUS_2];
605 Move EasyMove = MOVE_NONE;
606 Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
608 // Moves to search are verified, copied, scored and sorted
609 RootMoveList rml(p, searchMoves);
611 // Handle special case of searching on a mate/stale position
612 if (rml.move_count() == 0)
615 wait_for_stop_or_ponderhit();
617 return pos.is_check() ? -VALUE_MATE : VALUE_DRAW;
620 // Print RootMoveList startup scoring to the standard output,
621 // so to output information also for iteration 1.
622 cout << "info depth " << 1
623 << "\ninfo depth " << 1
624 << " score " << value_to_string(rml.get_move_score(0))
625 << " time " << current_search_time()
626 << " nodes " << TM.nodes_searched()
628 << " pv " << rml.get_move(0) << "\n";
634 ValueByIteration[1] = rml.get_move_score(0);
637 // Is one move significantly better than others after initial scoring ?
638 if ( rml.move_count() == 1
639 || rml.get_move_score(0) > rml.get_move_score(1) + EasyMoveMargin)
640 EasyMove = rml.get_move(0);
642 // Iterative deepening loop
643 while (Iteration < PLY_MAX)
645 // Initialize iteration
647 BestMoveChangesByIteration[Iteration] = 0;
649 cout << "info depth " << Iteration << endl;
651 // Calculate dynamic aspiration window based on previous iterations
652 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
654 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
655 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
657 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
658 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
660 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
661 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
664 // Search to the current depth, rml is updated and sorted, alpha and beta could change
665 value = root_search(p, ss, rml, &alpha, &beta);
667 // Write PV to transposition table, in case the relevant entries have
668 // been overwritten during the search.
669 TT.insert_pv(p, ss[0].pv);
672 break; // Value cannot be trusted. Break out immediately!
674 //Save info about search result
675 ValueByIteration[Iteration] = value;
677 // Drop the easy move if differs from the new best move
678 if (ss[0].pv[0] != EasyMove)
679 EasyMove = MOVE_NONE;
681 if (UseTimeManagement)
684 bool stopSearch = false;
686 // Stop search early if there is only a single legal move,
687 // we search up to Iteration 6 anyway to get a proper score.
688 if (Iteration >= 6 && rml.move_count() == 1)
691 // Stop search early when the last two iterations returned a mate score
693 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
694 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
697 // Stop search early if one move seems to be much better than the others
698 int64_t nodes = TM.nodes_searched();
700 && EasyMove == ss[0].pv[0]
701 && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
702 && current_search_time() > MaxSearchTime / 16)
703 ||( rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100
704 && current_search_time() > MaxSearchTime / 32)))
707 // Add some extra time if the best move has changed during the last two iterations
708 if (Iteration > 5 && Iteration <= 50)
709 ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2)
710 + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3);
712 // Stop search if most of MaxSearchTime is consumed at the end of the
713 // iteration. We probably don't have enough time to search the first
714 // move at the next iteration anyway.
715 if (current_search_time() > ((MaxSearchTime + ExtraSearchTime) * 80) / 128)
721 StopOnPonderhit = true;
727 if (MaxDepth && Iteration >= MaxDepth)
731 // If we are pondering or in infinite search, we shouldn't print the
732 // best move before we are told to do so.
733 if (!AbortSearch && (PonderSearch || InfiniteSearch))
734 wait_for_stop_or_ponderhit();
736 // Print final search statistics
737 cout << "info nodes " << TM.nodes_searched()
739 << " time " << current_search_time()
740 << " hashfull " << TT.full() << endl;
742 // Print the best move and the ponder move to the standard output
743 if (ss[0].pv[0] == MOVE_NONE)
745 ss[0].pv[0] = rml.get_move(0);
746 ss[0].pv[1] = MOVE_NONE;
749 assert(ss[0].pv[0] != MOVE_NONE);
751 cout << "bestmove " << ss[0].pv[0];
753 if (ss[0].pv[1] != MOVE_NONE)
754 cout << " ponder " << ss[0].pv[1];
761 dbg_print_mean(LogFile);
763 if (dbg_show_hit_rate)
764 dbg_print_hit_rate(LogFile);
766 LogFile << "\nNodes: " << TM.nodes_searched()
767 << "\nNodes/second: " << nps()
768 << "\nBest move: " << move_to_san(p, ss[0].pv[0]);
771 p.do_move(ss[0].pv[0], st);
772 LogFile << "\nPonder move: "
773 << move_to_san(p, ss[0].pv[1]) // Works also with MOVE_NONE
776 return rml.get_move_score(0);
780 // root_search() is the function which searches the root node. It is
781 // similar to search_pv except that it uses a different move ordering
782 // scheme, prints some information to the standard output and handles
783 // the fail low/high loops.
785 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
792 Depth depth, ext, newDepth;
793 Value value, alpha, beta;
794 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
795 int researchCountFH, researchCountFL;
797 researchCountFH = researchCountFL = 0;
800 isCheck = pos.is_check();
802 // Step 1. Initialize node and poll (omitted at root, but I can see no good reason for this, FIXME)
803 // Step 2. Check for aborted search (omitted at root, because we do not initialize root node)
804 // Step 3. Mate distance pruning (omitted at root)
805 // Step 4. Transposition table lookup (omitted at root)
807 // Step 5. Evaluate the position statically
808 // At root we do this only to get reference value for child nodes
810 ss[0].eval = evaluate(pos, ei, 0);
812 ss[0].eval = VALUE_NONE; // HACK because we do not initialize root node
814 // Step 6. Razoring (omitted at root)
815 // Step 7. Static null move pruning (omitted at root)
816 // Step 8. Null move search with verification search (omitted at root)
817 // Step 9. Internal iterative deepening (omitted at root)
819 // Step extra. Fail low loop
820 // We start with small aspiration window and in case of fail low, we research
821 // with bigger window until we are not failing low anymore.
824 // Sort the moves before to (re)search
827 // Step 10. Loop through all moves in the root move list
828 for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
830 // This is used by time management
831 FirstRootMove = (i == 0);
833 // Save the current node count before the move is searched
834 nodes = TM.nodes_searched();
836 // Reset beta cut-off counters
837 TM.resetBetaCounters();
839 // Pick the next root move, and print the move and the move number to
840 // the standard output.
841 move = ss[0].currentMove = rml.get_move(i);
843 if (current_search_time() >= 1000)
844 cout << "info currmove " << move
845 << " currmovenumber " << i + 1 << endl;
847 moveIsCheck = pos.move_is_check(move);
848 captureOrPromotion = pos.move_is_capture_or_promotion(move);
850 // Step 11. Decide the new search depth
851 depth = (Iteration - 2) * OnePly + InitialDepth;
852 ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
853 newDepth = depth + ext;
855 // Step 12. Futility pruning (omitted at root)
857 // Step extra. Fail high loop
858 // If move fails high, we research with bigger window until we are not failing
860 value = - VALUE_INFINITE;
864 // Step 13. Make the move
865 pos.do_move(move, st, ci, moveIsCheck);
867 // Step extra. pv search
868 // We do pv search for first moves (i < MultiPV)
869 // and for fail high research (value > alpha)
870 if (i < MultiPV || value > alpha)
872 // Aspiration window is disabled in multi-pv case
874 alpha = -VALUE_INFINITE;
876 // Full depth PV search, done on first move or after a fail high
877 value = -search<PV>(pos, ss, -beta, -alpha, newDepth, 1, false, 0);
881 // Step 14. Reduced search
882 // if the move fails high will be re-searched at full depth
883 bool doFullDepthSearch = true;
885 if ( depth >= 3 * OnePly
887 && !captureOrPromotion
888 && !move_is_castle(move))
890 ss[0].reduction = reduction<PV>(depth, i - MultiPV + 2);
893 // Reduced depth non-pv search using alpha as upperbound
894 value = -search<NonPV>(pos, ss, -(alpha+1), -alpha, newDepth-ss[0].reduction, 1, true, 0);
895 doFullDepthSearch = (value > alpha);
899 // Step 15. Full depth search
900 if (doFullDepthSearch)
902 // Full depth non-pv search using alpha as upperbound
903 ss[0].reduction = Depth(0);
904 value = -search<NonPV>(pos, ss, -(alpha+1), -alpha, newDepth, 1, true, 0);
906 // If we are above alpha then research at same depth but as PV
907 // to get a correct score or eventually a fail high above beta.
909 value = -search<PV>(pos, ss, -beta, -alpha, newDepth, 1, false, 0);
913 // Step 16. Undo move
916 // Can we exit fail high loop ?
917 if (AbortSearch || value < beta)
920 // We are failing high and going to do a research. It's important to update
921 // the score before research in case we run out of time while researching.
922 rml.set_move_score(i, value);
924 TT.extract_pv(pos, ss[0].pv, PLY_MAX);
925 rml.set_move_pv(i, ss[0].pv);
927 // Print information to the standard output
928 print_pv_info(pos, ss, alpha, beta, value);
930 // Prepare for a research after a fail high, each time with a wider window
931 *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
934 } // End of fail high loop
936 // Finished searching the move. If AbortSearch is true, the search
937 // was aborted because the user interrupted the search or because we
938 // ran out of time. In this case, the return value of the search cannot
939 // be trusted, and we break out of the loop without updating the best
944 // Remember beta-cutoff and searched nodes counts for this move. The
945 // info is used to sort the root moves for the next iteration.
947 TM.get_beta_counters(pos.side_to_move(), our, their);
948 rml.set_beta_counters(i, our, their);
949 rml.set_move_nodes(i, TM.nodes_searched() - nodes);
951 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
952 assert(value < beta);
954 // Step 17. Check for new best move
955 if (value <= alpha && i >= MultiPV)
956 rml.set_move_score(i, -VALUE_INFINITE);
959 // PV move or new best move!
962 rml.set_move_score(i, value);
964 TT.extract_pv(pos, ss[0].pv, PLY_MAX);
965 rml.set_move_pv(i, ss[0].pv);
969 // We record how often the best move has been changed in each
970 // iteration. This information is used for time managment: When
971 // the best move changes frequently, we allocate some more time.
973 BestMoveChangesByIteration[Iteration]++;
975 // Print information to the standard output
976 print_pv_info(pos, ss, alpha, beta, value);
978 // Raise alpha to setup proper non-pv search upper bound
985 for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
987 cout << "info multipv " << j + 1
988 << " score " << value_to_string(rml.get_move_score(j))
989 << " depth " << (j <= i ? Iteration : Iteration - 1)
990 << " time " << current_search_time()
991 << " nodes " << TM.nodes_searched()
995 for (int k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
996 cout << rml.get_move_pv(j, k) << " ";
1000 alpha = rml.get_move_score(Min(i, MultiPV - 1));
1002 } // PV move or new best move
1004 assert(alpha >= *alphaPtr);
1006 AspirationFailLow = (alpha == *alphaPtr);
1008 if (AspirationFailLow && StopOnPonderhit)
1009 StopOnPonderhit = false;
1012 // Can we exit fail low loop ?
1013 if (AbortSearch || !AspirationFailLow)
1016 // Prepare for a research after a fail low, each time with a wider window
1017 *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
1022 // Sort the moves before to return
1029 // search<>() is the main search function for both PV and non-PV nodes
1031 template <NodeType PvNode>
1032 Value search(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth,
1033 int ply, bool allowNullmove, int threadID, Move excludedMove) {
1035 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1036 assert(beta > alpha && beta <= VALUE_INFINITE);
1037 assert(PvNode || alpha == beta - 1);
1038 assert(ply >= 0 && ply < PLY_MAX);
1039 assert(threadID >= 0 && threadID < TM.active_threads());
1041 Move movesSearched[256];
1046 Depth ext, newDepth;
1047 Value bestValue, value, oldAlpha;
1048 Value refinedValue, nullValue, futilityValueScaled; // Non-PV specific
1049 bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
1050 bool mateThreat = false;
1052 refinedValue = bestValue = value = -VALUE_INFINITE;
1056 return qsearch<PvNode>(pos, ss, alpha, beta, Depth(0), ply, threadID);
1058 // Step 1. Initialize node and poll
1059 // Polling can abort search.
1060 init_node(ss, ply, threadID);
1062 // Step 2. Check for aborted search and immediate draw
1063 if (AbortSearch || TM.thread_should_stop(threadID))
1066 if (pos.is_draw() || ply >= PLY_MAX - 1)
1069 // Step 3. Mate distance pruning
1070 alpha = Max(value_mated_in(ply), alpha);
1071 beta = Min(value_mate_in(ply+1), beta);
1075 // Step 4. Transposition table lookup
1077 // We don't want the score of a partial search to overwrite a previous full search
1078 // TT value, so we use a different position key in case of an excluded move exists.
1079 Key posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1081 tte = TT.retrieve(posKey);
1082 ttMove = (tte ? tte->move() : MOVE_NONE);
1084 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1085 // This is to avoid problems in the following areas:
1087 // * Repetition draw detection
1088 // * Fifty move rule detection
1089 // * Searching for a mate
1090 // * Printing of full PV line
1092 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1094 // Refresh tte entry to avoid aging
1095 TT.store(posKey, tte->value(), tte->type(), tte->depth(), ttMove);
1097 ss[ply].currentMove = ttMove; // Can be MOVE_NONE
1098 return value_from_tt(tte->value(), ply);
1101 // Step 5. Evaluate the position statically
1102 // At PV nodes we do this only to update gain statistics
1103 isCheck = pos.is_check();
1106 if (tte && (tte->type() & VALUE_TYPE_EVAL))
1107 ss[ply].eval = value_from_tt(tte->value(), ply);
1109 ss[ply].eval = evaluate(pos, ei, threadID);
1111 refinedValue = refine_eval(tte, ss[ply].eval, ply); // Enhance accuracy with TT value if possible
1112 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1115 // Step 6. Razoring (is omitted in PV nodes)
1117 && refinedValue < beta - razor_margin(depth)
1118 && ttMove == MOVE_NONE
1119 && ss[ply - 1].currentMove != MOVE_NULL
1120 && depth < RazorDepth
1122 && !value_is_mate(beta)
1123 && !pos.has_pawn_on_7th(pos.side_to_move()))
1125 Value rbeta = beta - razor_margin(depth);
1126 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID);
1128 // Logically we should return (v + razor_margin(depth)), but
1129 // surprisingly this did slightly weaker in tests.
1133 // Step 7. Static null move pruning (is omitted in PV nodes)
1134 // We're betting that the opponent doesn't have a move that will reduce
1135 // the score by more than futility_margin(depth) if we do a null move.
1138 && depth < RazorDepth
1140 && !value_is_mate(beta)
1141 && ok_to_do_nullmove(pos)
1142 && refinedValue >= beta + futility_margin(depth, 0))
1143 return refinedValue - futility_margin(depth, 0);
1145 // Step 8. Null move search with verification search (is omitted in PV nodes)
1146 // When we jump directly to qsearch() we do a null move only if static value is
1147 // at least beta. Otherwise we do a null move if static value is not more than
1148 // NullMoveMargin under beta.
1153 && !value_is_mate(beta)
1154 && ok_to_do_nullmove(pos)
1155 && refinedValue >= beta - (depth >= 4 * OnePly ? NullMoveMargin : 0))
1157 ss[ply].currentMove = MOVE_NULL;
1159 // Null move dynamic reduction based on depth
1160 int R = 3 + (depth >= 5 * OnePly ? depth / 8 : 0);
1162 // Null move dynamic reduction based on value
1163 if (refinedValue - beta > PawnValueMidgame)
1166 pos.do_null_move(st);
1168 nullValue = -search<NonPV>(pos, ss, -beta, -alpha, depth-R*OnePly, ply+1, false, threadID);
1170 pos.undo_null_move();
1172 if (nullValue >= beta)
1174 // Do not return unproven mate scores
1175 if (nullValue >= value_mate_in(PLY_MAX))
1178 if (depth < 6 * OnePly)
1181 // Do zugzwang verification search
1182 Value v = search<NonPV>(pos, ss, alpha, beta, depth-5*OnePly, ply, false, threadID);
1186 // The null move failed low, which means that we may be faced with
1187 // some kind of threat. If the previous move was reduced, check if
1188 // the move that refuted the null move was somehow connected to the
1189 // move which was reduced. If a connection is found, return a fail
1190 // low score (which will cause the reduced move to fail high in the
1191 // parent node, which will trigger a re-search with full depth).
1192 if (nullValue == value_mated_in(ply + 2))
1195 ss[ply].threatMove = ss[ply + 1].currentMove;
1196 if ( depth < ThreatDepth
1197 && ss[ply - 1].reduction
1198 && connected_moves(pos, ss[ply - 1].currentMove, ss[ply].threatMove))
1203 // Step 9. Internal iterative deepening
1204 if ( depth >= IIDDepth[PvNode]
1205 && ttMove == MOVE_NONE
1206 && (PvNode || (!isCheck && ss[ply].eval >= beta - IIDMargin)))
1208 Depth d = (PvNode ? depth - 2 * OnePly : depth / 2);
1209 search<PvNode>(pos, ss, alpha, beta, d, ply, false, threadID);
1210 ttMove = ss[ply].pv[ply];
1211 tte = TT.retrieve(posKey);
1214 // Expensive mate threat detection (only for PV nodes)
1216 mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move()));
1218 // Initialize a MovePicker object for the current position
1219 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply], (PvNode ? -VALUE_INFINITE : beta));
1222 // Step 10. Loop through moves
1223 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1224 while ( bestValue < beta
1225 && (move = mp.get_next_move()) != MOVE_NONE
1226 && !TM.thread_should_stop(threadID))
1228 assert(move_is_ok(move));
1230 if (move == excludedMove)
1233 singleEvasion = (isCheck && mp.number_of_evasions() == 1);
1234 moveIsCheck = pos.move_is_check(move, ci);
1235 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1237 // Step 11. Decide the new search depth
1238 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1240 // Singular extension search. We extend the TT move if its value is much better than
1241 // its siblings. To verify this we do a reduced search on all the other moves but the
1242 // ttMove, if result is lower then ttValue minus a margin then we extend ttMove.
1243 if ( depth >= SingularExtensionDepth[PvNode]
1245 && move == tte->move()
1246 && !excludedMove // Do not allow recursive singular extension search
1248 && is_lower_bound(tte->type())
1249 && tte->depth() >= depth - 3 * OnePly)
1251 Value ttValue = value_from_tt(tte->value(), ply);
1253 if (abs(ttValue) < VALUE_KNOWN_WIN)
1255 Value b = ttValue - SingularExtensionMargin;
1256 Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply, false, threadID, move);
1258 if (v < ttValue - SingularExtensionMargin)
1263 newDepth = depth - OnePly + ext;
1265 // Update current move (this must be done after singular extension search)
1266 movesSearched[moveCount++] = ss[ply].currentMove = move;
1268 // Step 12. Futility pruning (is omitted in PV nodes)
1272 && !captureOrPromotion
1273 && !move_is_castle(move)
1276 // Move count based pruning
1277 if ( moveCount >= futility_move_count(depth)
1278 && ok_to_prune(pos, move, ss[ply].threatMove)
1279 && bestValue > value_mated_in(PLY_MAX))
1282 // Value based pruning
1283 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount); // FIXME We illogically ignore reduction condition depth >= 3*OnePly
1284 futilityValueScaled = ss[ply].eval + futility_margin(predictedDepth, moveCount)
1285 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1287 if (futilityValueScaled < beta)
1289 if (futilityValueScaled > bestValue)
1290 bestValue = futilityValueScaled;
1295 // Step 13. Make the move
1296 pos.do_move(move, st, ci, moveIsCheck);
1298 // Step extra. pv search (only in PV nodes)
1299 // The first move in list is the expected PV
1300 if (PvNode && moveCount == 1)
1301 value = -search<PV>(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID);
1304 // Step 14. Reduced search
1305 // if the move fails high will be re-searched at full depth.
1306 bool doFullDepthSearch = true;
1308 if ( depth >= 3 * OnePly
1310 && !captureOrPromotion
1311 && !move_is_castle(move)
1312 && !move_is_killer(move, ss[ply]))
1314 ss[ply].reduction = reduction<PvNode>(depth, moveCount);
1315 if (ss[ply].reduction)
1317 value = -search<NonPV>(pos, ss, -(alpha+1), -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
1318 doFullDepthSearch = (value > alpha);
1322 // Step 15. Full depth search
1323 if (doFullDepthSearch)
1325 ss[ply].reduction = Depth(0);
1326 value = -search<NonPV>(pos, ss, -(alpha+1), -alpha, newDepth, ply+1, true, threadID);
1328 // Step extra. pv search (only in PV nodes)
1329 // Search only for possible new PV nodes, if instead value >= beta then
1330 // parent node fails low with value <= alpha and tries another move.
1331 if (PvNode && value > alpha && value < beta)
1332 value = -search<PV>(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID);
1336 // Step 16. Undo move
1337 pos.undo_move(move);
1339 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1341 // Step 17. Check for new best move
1342 if (value > bestValue)
1349 if (value == value_mate_in(ply + 1))
1350 ss[ply].mateKiller = move;
1354 // Step 18. Check for split
1355 if ( TM.active_threads() > 1
1357 && depth >= MinimumSplitDepth
1359 && TM.available_thread_exists(threadID)
1361 && !TM.thread_should_stop(threadID)
1362 && TM.split<false>(pos, ss, ply, &alpha, beta, &bestValue,
1363 depth, mateThreat, &moveCount, &mp, threadID, PvNode))
1366 // Uncomment to debug sp_search() in single thread mode
1367 if ( bestValue < beta
1371 && !TM.thread_should_stop(threadID)
1372 && TM.split<true>(pos, ss, ply, &alpha, beta, &bestValue,
1373 depth, mateThreat, &moveCount, &mp, threadID, PvNode))
1377 // Step 19. Check for mate and stalemate
1378 // All legal moves have been searched and if there are
1379 // no legal moves, it must be mate or stalemate.
1380 // If one move was excluded return fail low score.
1382 return excludedMove ? oldAlpha : (isCheck ? value_mated_in(ply) : VALUE_DRAW);
1384 // Step 20. Update tables
1385 // If the search is not aborted, update the transposition table,
1386 // history counters, and killer moves.
1387 if (AbortSearch || TM.thread_should_stop(threadID))
1390 if (bestValue <= oldAlpha)
1391 TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1393 else if (bestValue >= beta)
1395 TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
1396 move = ss[ply].pv[ply];
1397 TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
1398 if (!pos.move_is_capture_or_promotion(move))
1400 update_history(pos, move, depth, movesSearched, moveCount);
1401 update_killers(move, ss[ply]);
1405 TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
1407 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1413 // qsearch() is the quiescence search function, which is called by the main
1414 // search function when the remaining depth is zero (or, to be more precise,
1415 // less than OnePly).
1417 template <NodeType PvNode>
1418 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta,
1419 Depth depth, int ply, int threadID) {
1421 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1422 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1423 assert(PvNode || alpha == beta - 1);
1425 assert(ply >= 0 && ply < PLY_MAX);
1426 assert(threadID >= 0 && threadID < TM.active_threads());
1431 Value staticValue, bestValue, value, futilityBase, futilityValue;
1432 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1433 const TTEntry* tte = NULL;
1435 Value oldAlpha = alpha;
1437 // Initialize, and make an early exit in case of an aborted search,
1438 // an instant draw, maximum ply reached, etc.
1439 init_node(ss, ply, threadID);
1441 // After init_node() that calls poll()
1442 if (AbortSearch || TM.thread_should_stop(threadID))
1445 if (pos.is_draw() || ply >= PLY_MAX - 1)
1448 // Transposition table lookup. At PV nodes, we don't use the TT for
1449 // pruning, but only for move ordering.
1450 tte = TT.retrieve(pos.get_key());
1451 ttMove = (tte ? tte->move() : MOVE_NONE);
1453 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1455 assert(tte->type() != VALUE_TYPE_EVAL);
1457 ss[ply].currentMove = ttMove; // Can be MOVE_NONE
1458 return value_from_tt(tte->value(), ply);
1461 isCheck = pos.is_check();
1463 // Evaluate the position statically
1465 staticValue = -VALUE_INFINITE;
1466 else if (tte && (tte->type() & VALUE_TYPE_EVAL))
1467 staticValue = value_from_tt(tte->value(), ply);
1469 staticValue = evaluate(pos, ei, threadID);
1473 ss[ply].eval = staticValue;
1474 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1477 // Initialize "stand pat score", and return it immediately if it is
1479 bestValue = staticValue;
1481 if (bestValue >= beta)
1483 // Store the score to avoid a future costly evaluation() call
1484 if (!isCheck && !tte && ei.kingDanger[pos.side_to_move()] == 0)
1485 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EV_LO, Depth(-127*OnePly), MOVE_NONE);
1490 if (bestValue > alpha)
1493 // If we are near beta then try to get a cutoff pushing checks a bit further
1494 bool deepChecks = (depth == -OnePly && staticValue >= beta - PawnValueMidgame / 8);
1496 // Initialize a MovePicker object for the current position, and prepare
1497 // to search the moves. Because the depth is <= 0 here, only captures,
1498 // queen promotions and checks (only if depth == 0 or depth == -OnePly
1499 // and we are near beta) will be generated.
1500 MovePicker mp = MovePicker(pos, ttMove, deepChecks ? Depth(0) : depth, H);
1502 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1503 futilityBase = staticValue + FutilityMarginQS + ei.kingDanger[pos.side_to_move()];
1505 // Loop through the moves until no moves remain or a beta cutoff occurs
1506 while ( alpha < beta
1507 && (move = mp.get_next_move()) != MOVE_NONE)
1509 assert(move_is_ok(move));
1511 moveIsCheck = pos.move_is_check(move, ci);
1513 // Update current move
1515 ss[ply].currentMove = move;
1523 && !move_is_promotion(move)
1524 && !pos.move_is_passed_pawn_push(move))
1526 futilityValue = futilityBase
1527 + pos.endgame_value_of_piece_on(move_to(move))
1528 + (move_is_ep(move) ? PawnValueEndgame : Value(0));
1530 if (futilityValue < alpha)
1532 if (futilityValue > bestValue)
1533 bestValue = futilityValue;
1538 // Detect blocking evasions that are candidate to be pruned
1539 evasionPrunable = isCheck
1540 && bestValue > value_mated_in(PLY_MAX)
1541 && !pos.move_is_capture(move)
1542 && pos.type_of_piece_on(move_from(move)) != KING
1543 && !pos.can_castle(pos.side_to_move());
1545 // Don't search moves with negative SEE values
1547 && (!isCheck || evasionPrunable)
1549 && !move_is_promotion(move)
1550 && pos.see_sign(move) < 0)
1553 // Make and search the move
1554 pos.do_move(move, st, ci, moveIsCheck);
1555 value = -qsearch<PvNode>(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID);
1556 pos.undo_move(move);
1558 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1561 if (value > bestValue)
1572 // All legal moves have been searched. A special case: If we're in check
1573 // and no legal moves were found, it is checkmate.
1574 if (!moveCount && isCheck) // Mate!
1575 return value_mated_in(ply);
1577 // Update transposition table
1578 Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
1579 if (bestValue <= oldAlpha)
1581 // If bestValue isn't changed it means it is still the static evaluation
1582 // of the node, so keep this info to avoid a future evaluation() call.
1583 ValueType type = (bestValue == staticValue && !ei.kingDanger[pos.side_to_move()] ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER);
1584 TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE);
1586 else if (bestValue >= beta)
1588 move = ss[ply].pv[ply];
1589 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, move);
1591 // Update killers only for good checking moves
1592 if (!pos.move_is_capture_or_promotion(move))
1593 update_killers(move, ss[ply]);
1596 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, d, ss[ply].pv[ply]);
1598 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1604 // sp_search() is used to search from a split point. This function is called
1605 // by each thread working at the split point. It is similar to the normal
1606 // search() function, but simpler. Because we have already probed the hash
1607 // table, done a null move search, and searched the first move before
1608 // splitting, we don't have to repeat all this work in sp_search(). We
1609 // also don't need to store anything to the hash table here: This is taken
1610 // care of after we return from the split point.
1612 void sp_search(SplitPoint* sp, int threadID) {
1614 assert(threadID >= 0 && threadID < TM.active_threads());
1615 //assert(TM.active_threads() > 1);
1619 Depth ext, newDepth;
1620 Value value, futilityValueScaled;
1621 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
1623 value = -VALUE_INFINITE;
1625 Position pos(*sp->pos);
1627 SearchStack* ss = sp->sstack[threadID];
1628 isCheck = pos.is_check();
1630 // Step 10. Loop through moves
1631 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1632 lock_grab(&(sp->lock));
1634 while ( sp->bestValue < sp->beta
1635 && !TM.thread_should_stop(threadID)
1636 && (move = sp->mp->get_next_move()) != MOVE_NONE)
1638 moveCount = ++sp->moves;
1639 lock_release(&(sp->lock));
1641 assert(move_is_ok(move));
1643 moveIsCheck = pos.move_is_check(move, ci);
1644 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1646 // Step 11. Decide the new search depth
1647 ext = extension<NonPV>(pos, move, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous);
1648 newDepth = sp->depth - OnePly + ext;
1650 // Update current move
1651 ss[sp->ply].currentMove = move;
1653 // Step 12. Futility pruning
1656 && !captureOrPromotion
1657 && !move_is_castle(move))
1659 // Move count based pruning
1660 if ( moveCount >= futility_move_count(sp->depth)
1661 && ok_to_prune(pos, move, ss[sp->ply].threatMove)
1662 && sp->bestValue > value_mated_in(PLY_MAX))
1664 lock_grab(&(sp->lock));
1668 // Value based pruning
1669 Depth predictedDepth = newDepth - reduction<NonPV>(sp->depth, moveCount);
1670 futilityValueScaled = ss[sp->ply].eval + futility_margin(predictedDepth, moveCount)
1671 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1673 if (futilityValueScaled < sp->beta)
1675 lock_grab(&(sp->lock));
1677 if (futilityValueScaled > sp->bestValue)
1678 sp->bestValue = futilityValueScaled;
1683 // Step 13. Make the move
1684 pos.do_move(move, st, ci, moveIsCheck);
1686 // Step 14. Reduced search
1687 // if the move fails high will be re-searched at full depth.
1688 bool doFullDepthSearch = true;
1691 && !captureOrPromotion
1692 && !move_is_castle(move)
1693 && !move_is_killer(move, ss[sp->ply]))
1695 ss[sp->ply].reduction = reduction<NonPV>(sp->depth, moveCount);
1696 if (ss[sp->ply].reduction)
1698 value = -search<NonPV>(pos, ss, -(sp->alpha+1), -(sp->alpha), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
1699 doFullDepthSearch = (value >= sp->beta && !TM.thread_should_stop(threadID));
1703 // Step 15. Full depth search
1704 if (doFullDepthSearch)
1706 ss[sp->ply].reduction = Depth(0);
1707 value = -search<NonPV>(pos, ss, -(sp->alpha+1), -(sp->alpha), newDepth, sp->ply+1, true, threadID);
1710 // Step 16. Undo move
1711 pos.undo_move(move);
1713 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1715 // Step 17. Check for new best move
1716 lock_grab(&(sp->lock));
1718 if (value > sp->bestValue && !TM.thread_should_stop(threadID))
1720 sp->bestValue = value;
1721 if (sp->bestValue >= sp->beta)
1723 sp->stopRequest = true;
1724 sp_update_pv(sp->parentSstack, ss, sp->ply);
1729 /* Here we have the lock still grabbed */
1731 sp->slaves[threadID] = 0;
1734 lock_release(&(sp->lock));
1738 // sp_search_pv() is used to search from a PV split point. This function
1739 // is called by each thread working at the split point. It is similar to
1740 // the normal search_pv() function, but simpler. Because we have already
1741 // probed the hash table and searched the first move before splitting, we
1742 // don't have to repeat all this work in sp_search_pv(). We also don't
1743 // need to store anything to the hash table here: This is taken care of
1744 // after we return from the split point.
1746 void sp_search_pv(SplitPoint* sp, int threadID) {
1748 assert(threadID >= 0 && threadID < TM.active_threads());
1749 //assert(TM.active_threads() > 1);
1753 Depth ext, newDepth;
1755 bool moveIsCheck, captureOrPromotion, dangerous;
1757 value = -VALUE_INFINITE;
1759 Position pos(*sp->pos);
1761 SearchStack* ss = sp->sstack[threadID];
1763 // Step 10. Loop through moves
1764 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1765 lock_grab(&(sp->lock));
1767 while ( sp->alpha < sp->beta
1768 && !TM.thread_should_stop(threadID)
1769 && (move = sp->mp->get_next_move()) != MOVE_NONE)
1771 moveCount = ++sp->moves;
1772 lock_release(&(sp->lock));
1774 assert(move_is_ok(move));
1776 moveIsCheck = pos.move_is_check(move, ci);
1777 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1779 // Step 11. Decide the new search depth
1780 ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous);
1781 newDepth = sp->depth - OnePly + ext;
1783 // Update current move
1784 ss[sp->ply].currentMove = move;
1786 // Step 12. Futility pruning (is omitted in PV nodes)
1788 // Step 13. Make the move
1789 pos.do_move(move, st, ci, moveIsCheck);
1791 // Step 14. Reduced search
1792 // if the move fails high will be re-searched at full depth.
1793 bool doFullDepthSearch = true;
1796 && !captureOrPromotion
1797 && !move_is_castle(move)
1798 && !move_is_killer(move, ss[sp->ply]))
1800 ss[sp->ply].reduction = reduction<PV>(sp->depth, moveCount);
1801 if (ss[sp->ply].reduction)
1803 Value localAlpha = sp->alpha;
1804 value = -search<NonPV>(pos, ss, -(localAlpha+1), -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
1805 doFullDepthSearch = (value > localAlpha && !TM.thread_should_stop(threadID));
1809 // Step 15. Full depth search
1810 if (doFullDepthSearch)
1812 Value localAlpha = sp->alpha;
1813 ss[sp->ply].reduction = Depth(0);
1814 value = -search<NonPV>(pos, ss, -(localAlpha+1), -localAlpha, newDepth, sp->ply+1, true, threadID);
1816 if (value > localAlpha && value < sp->beta && !TM.thread_should_stop(threadID))
1818 // If another thread has failed high then sp->alpha has been increased
1819 // to be higher or equal then beta, if so, avoid to start a PV search.
1820 localAlpha = sp->alpha;
1821 if (localAlpha < sp->beta)
1822 value = -search<PV>(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, false, threadID);
1826 // Step 16. Undo move
1827 pos.undo_move(move);
1829 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1831 // Step 17. Check for new best move
1832 lock_grab(&(sp->lock));
1834 if (value > sp->bestValue && !TM.thread_should_stop(threadID))
1836 sp->bestValue = value;
1837 if (value > sp->alpha)
1839 // Ask threads to stop before to modify sp->alpha
1840 if (value >= sp->beta)
1841 sp->stopRequest = true;
1845 sp_update_pv(sp->parentSstack, ss, sp->ply);
1846 if (value == value_mate_in(sp->ply + 1))
1847 ss[sp->ply].mateKiller = move;
1852 /* Here we have the lock still grabbed */
1854 sp->slaves[threadID] = 0;
1857 lock_release(&(sp->lock));
1861 // init_node() is called at the beginning of all the search functions
1862 // (search() qsearch(), and so on) and initializes the
1863 // search stack object corresponding to the current node. Once every
1864 // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
1865 // for user input and checks whether it is time to stop the search.
1867 void init_node(SearchStack ss[], int ply, int threadID) {
1869 assert(ply >= 0 && ply < PLY_MAX);
1870 assert(threadID >= 0 && threadID < TM.active_threads());
1872 TM.incrementNodeCounter(threadID);
1877 if (NodesSincePoll >= NodesBetweenPolls)
1884 ss[ply + 2].initKillers();
1888 // update_pv() is called whenever a search returns a value > alpha.
1889 // It updates the PV in the SearchStack object corresponding to the
1892 void update_pv(SearchStack ss[], int ply) {
1894 assert(ply >= 0 && ply < PLY_MAX);
1898 ss[ply].pv[ply] = ss[ply].currentMove;
1900 for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
1901 ss[ply].pv[p] = ss[ply + 1].pv[p];
1903 ss[ply].pv[p] = MOVE_NONE;
1907 // sp_update_pv() is a variant of update_pv for use at split points. The
1908 // difference between the two functions is that sp_update_pv also updates
1909 // the PV at the parent node.
1911 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply) {
1913 assert(ply >= 0 && ply < PLY_MAX);
1917 ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
1919 for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
1920 ss[ply].pv[p] = pss[ply].pv[p] = ss[ply + 1].pv[p];
1922 ss[ply].pv[p] = pss[ply].pv[p] = MOVE_NONE;
1926 // connected_moves() tests whether two moves are 'connected' in the sense
1927 // that the first move somehow made the second move possible (for instance
1928 // if the moving piece is the same in both moves). The first move is assumed
1929 // to be the move that was made to reach the current position, while the
1930 // second move is assumed to be a move from the current position.
1932 bool connected_moves(const Position& pos, Move m1, Move m2) {
1934 Square f1, t1, f2, t2;
1937 assert(move_is_ok(m1));
1938 assert(move_is_ok(m2));
1940 if (m2 == MOVE_NONE)
1943 // Case 1: The moving piece is the same in both moves
1949 // Case 2: The destination square for m2 was vacated by m1
1955 // Case 3: Moving through the vacated square
1956 if ( piece_is_slider(pos.piece_on(f2))
1957 && bit_is_set(squares_between(f2, t2), f1))
1960 // Case 4: The destination square for m2 is defended by the moving piece in m1
1961 p = pos.piece_on(t1);
1962 if (bit_is_set(pos.attacks_from(p, t1), t2))
1965 // Case 5: Discovered check, checking piece is the piece moved in m1
1966 if ( piece_is_slider(p)
1967 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1968 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1970 // discovered_check_candidates() works also if the Position's side to
1971 // move is the opposite of the checking piece.
1972 Color them = opposite_color(pos.side_to_move());
1973 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1975 if (bit_is_set(dcCandidates, f2))
1982 // value_is_mate() checks if the given value is a mate one
1983 // eventually compensated for the ply.
1985 bool value_is_mate(Value value) {
1987 assert(abs(value) <= VALUE_INFINITE);
1989 return value <= value_mated_in(PLY_MAX)
1990 || value >= value_mate_in(PLY_MAX);
1994 // move_is_killer() checks if the given move is among the
1995 // killer moves of that ply.
1997 bool move_is_killer(Move m, const SearchStack& ss) {
1999 const Move* k = ss.killers;
2000 for (int i = 0; i < KILLER_MAX; i++, k++)
2008 // extension() decides whether a move should be searched with normal depth,
2009 // or with extended depth. Certain classes of moves (checking moves, in
2010 // particular) are searched with bigger depth than ordinary moves and in
2011 // any case are marked as 'dangerous'. Note that also if a move is not
2012 // extended, as example because the corresponding UCI option is set to zero,
2013 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
2014 template <NodeType PvNode>
2015 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
2016 bool singleEvasion, bool mateThreat, bool* dangerous) {
2018 assert(m != MOVE_NONE);
2020 Depth result = Depth(0);
2021 *dangerous = moveIsCheck | singleEvasion | mateThreat;
2026 result += CheckExtension[PvNode];
2029 result += SingleEvasionExtension[PvNode];
2032 result += MateThreatExtension[PvNode];
2035 if (pos.type_of_piece_on(move_from(m)) == PAWN)
2037 Color c = pos.side_to_move();
2038 if (relative_rank(c, move_to(m)) == RANK_7)
2040 result += PawnPushTo7thExtension[PvNode];
2043 if (pos.pawn_is_passed(c, move_to(m)))
2045 result += PassedPawnExtension[PvNode];
2050 if ( captureOrPromotion
2051 && pos.type_of_piece_on(move_to(m)) != PAWN
2052 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
2053 - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))
2054 && !move_is_promotion(m)
2057 result += PawnEndgameExtension[PvNode];
2062 && captureOrPromotion
2063 && pos.type_of_piece_on(move_to(m)) != PAWN
2064 && pos.see_sign(m) >= 0)
2070 return Min(result, OnePly);
2074 // ok_to_do_nullmove() looks at the current position and decides whether
2075 // doing a 'null move' should be allowed. In order to avoid zugzwang
2076 // problems, null moves are not allowed when the side to move has very
2077 // little material left. Currently, the test is a bit too simple: Null
2078 // moves are avoided only when the side to move has only pawns left.
2079 // It's probably a good idea to avoid null moves in at least some more
2080 // complicated endgames, e.g. KQ vs KR. FIXME
2082 bool ok_to_do_nullmove(const Position& pos) {
2084 return pos.non_pawn_material(pos.side_to_move()) != Value(0);
2088 // ok_to_prune() tests whether it is safe to forward prune a move. Only
2089 // non-tactical moves late in the move list close to the leaves are
2090 // candidates for pruning.
2092 bool ok_to_prune(const Position& pos, Move m, Move threat) {
2094 assert(move_is_ok(m));
2095 assert(threat == MOVE_NONE || move_is_ok(threat));
2096 assert(!pos.move_is_check(m));
2097 assert(!pos.move_is_capture_or_promotion(m));
2098 assert(!pos.move_is_passed_pawn_push(m));
2100 Square mfrom, mto, tfrom, tto;
2102 // Prune if there isn't any threat move
2103 if (threat == MOVE_NONE)
2106 mfrom = move_from(m);
2108 tfrom = move_from(threat);
2109 tto = move_to(threat);
2111 // Case 1: Don't prune moves which move the threatened piece
2115 // Case 2: If the threatened piece has value less than or equal to the
2116 // value of the threatening piece, don't prune move which defend it.
2117 if ( pos.move_is_capture(threat)
2118 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
2119 || pos.type_of_piece_on(tfrom) == KING)
2120 && pos.move_attacks_square(m, tto))
2123 // Case 3: If the moving piece in the threatened move is a slider, don't
2124 // prune safe moves which block its ray.
2125 if ( piece_is_slider(pos.piece_on(tfrom))
2126 && bit_is_set(squares_between(tfrom, tto), mto)
2127 && pos.see_sign(m) >= 0)
2134 // ok_to_use_TT() returns true if a transposition table score
2135 // can be used at a given point in search.
2137 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
2139 Value v = value_from_tt(tte->value(), ply);
2141 return ( tte->depth() >= depth
2142 || v >= Max(value_mate_in(PLY_MAX), beta)
2143 || v < Min(value_mated_in(PLY_MAX), beta))
2145 && ( (is_lower_bound(tte->type()) && v >= beta)
2146 || (is_upper_bound(tte->type()) && v < beta));
2150 // refine_eval() returns the transposition table score if
2151 // possible otherwise falls back on static position evaluation.
2153 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
2158 Value v = value_from_tt(tte->value(), ply);
2160 if ( (is_lower_bound(tte->type()) && v >= defaultEval)
2161 || (is_upper_bound(tte->type()) && v < defaultEval))
2168 // update_history() registers a good move that produced a beta-cutoff
2169 // in history and marks as failures all the other moves of that ply.
2171 void update_history(const Position& pos, Move move, Depth depth,
2172 Move movesSearched[], int moveCount) {
2176 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
2178 for (int i = 0; i < moveCount - 1; i++)
2180 m = movesSearched[i];
2184 if (!pos.move_is_capture_or_promotion(m))
2185 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
2190 // update_killers() add a good move that produced a beta-cutoff
2191 // among the killer moves of that ply.
2193 void update_killers(Move m, SearchStack& ss) {
2195 if (m == ss.killers[0])
2198 for (int i = KILLER_MAX - 1; i > 0; i--)
2199 ss.killers[i] = ss.killers[i - 1];
2205 // update_gains() updates the gains table of a non-capture move given
2206 // the static position evaluation before and after the move.
2208 void update_gains(const Position& pos, Move m, Value before, Value after) {
2211 && before != VALUE_NONE
2212 && after != VALUE_NONE
2213 && pos.captured_piece() == NO_PIECE_TYPE
2214 && !move_is_castle(m)
2215 && !move_is_promotion(m))
2216 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
2220 // current_search_time() returns the number of milliseconds which have passed
2221 // since the beginning of the current search.
2223 int current_search_time() {
2225 return get_system_time() - SearchStartTime;
2229 // nps() computes the current nodes/second count.
2233 int t = current_search_time();
2234 return (t > 0 ? int((TM.nodes_searched() * 1000) / t) : 0);
2238 // poll() performs two different functions: It polls for user input, and it
2239 // looks at the time consumed so far and decides if it's time to abort the
2244 static int lastInfoTime;
2245 int t = current_search_time();
2250 // We are line oriented, don't read single chars
2251 std::string command;
2253 if (!std::getline(std::cin, command))
2256 if (command == "quit")
2259 PonderSearch = false;
2263 else if (command == "stop")
2266 PonderSearch = false;
2268 else if (command == "ponderhit")
2272 // Print search information
2276 else if (lastInfoTime > t)
2277 // HACK: Must be a new search where we searched less than
2278 // NodesBetweenPolls nodes during the first second of search.
2281 else if (t - lastInfoTime >= 1000)
2288 if (dbg_show_hit_rate)
2289 dbg_print_hit_rate();
2291 cout << "info nodes " << TM.nodes_searched() << " nps " << nps()
2292 << " time " << t << " hashfull " << TT.full() << endl;
2295 // Should we stop the search?
2299 bool stillAtFirstMove = FirstRootMove
2300 && !AspirationFailLow
2301 && t > MaxSearchTime + ExtraSearchTime;
2303 bool noMoreTime = t > AbsoluteMaxSearchTime
2304 || stillAtFirstMove;
2306 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2307 || (ExactMaxTime && t >= ExactMaxTime)
2308 || (Iteration >= 3 && MaxNodes && TM.nodes_searched() >= MaxNodes))
2313 // ponderhit() is called when the program is pondering (i.e. thinking while
2314 // it's the opponent's turn to move) in order to let the engine know that
2315 // it correctly predicted the opponent's move.
2319 int t = current_search_time();
2320 PonderSearch = false;
2322 bool stillAtFirstMove = FirstRootMove
2323 && !AspirationFailLow
2324 && t > MaxSearchTime + ExtraSearchTime;
2326 bool noMoreTime = t > AbsoluteMaxSearchTime
2327 || stillAtFirstMove;
2329 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2334 // init_ss_array() does a fast reset of the first entries of a SearchStack array
2336 void init_ss_array(SearchStack ss[]) {
2338 for (int i = 0; i < 3; i++)
2341 ss[i].initKillers();
2346 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2347 // while the program is pondering. The point is to work around a wrinkle in
2348 // the UCI protocol: When pondering, the engine is not allowed to give a
2349 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2350 // We simply wait here until one of these commands is sent, and return,
2351 // after which the bestmove and pondermove will be printed (in id_loop()).
2353 void wait_for_stop_or_ponderhit() {
2355 std::string command;
2359 if (!std::getline(std::cin, command))
2362 if (command == "quit")
2367 else if (command == "ponderhit" || command == "stop")
2373 // print_pv_info() prints to standard output and eventually to log file information on
2374 // the current PV line. It is called at each iteration or after a new pv is found.
2376 void print_pv_info(const Position& pos, SearchStack ss[], Value alpha, Value beta, Value value) {
2378 cout << "info depth " << Iteration
2379 << " score " << value_to_string(value)
2380 << ((value >= beta) ? " lowerbound" :
2381 ((value <= alpha)? " upperbound" : ""))
2382 << " time " << current_search_time()
2383 << " nodes " << TM.nodes_searched()
2387 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
2388 cout << ss[0].pv[j] << " ";
2394 ValueType type = (value >= beta ? VALUE_TYPE_LOWER
2395 : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT));
2397 LogFile << pretty_pv(pos, current_search_time(), Iteration,
2398 TM.nodes_searched(), value, type, ss[0].pv) << endl;
2403 // init_thread() is the function which is called when a new thread is
2404 // launched. It simply calls the idle_loop() function with the supplied
2405 // threadID. There are two versions of this function; one for POSIX
2406 // threads and one for Windows threads.
2408 #if !defined(_MSC_VER)
2410 void* init_thread(void *threadID) {
2412 TM.idle_loop(*(int*)threadID, NULL);
2418 DWORD WINAPI init_thread(LPVOID threadID) {
2420 TM.idle_loop(*(int*)threadID, NULL);
2427 /// The ThreadsManager class
2429 // resetNodeCounters(), resetBetaCounters(), searched_nodes() and
2430 // get_beta_counters() are getters/setters for the per thread
2431 // counters used to sort the moves at root.
2433 void ThreadsManager::resetNodeCounters() {
2435 for (int i = 0; i < MAX_THREADS; i++)
2436 threads[i].nodes = 0ULL;
2439 void ThreadsManager::resetBetaCounters() {
2441 for (int i = 0; i < MAX_THREADS; i++)
2442 threads[i].betaCutOffs[WHITE] = threads[i].betaCutOffs[BLACK] = 0ULL;
2445 int64_t ThreadsManager::nodes_searched() const {
2447 int64_t result = 0ULL;
2448 for (int i = 0; i < ActiveThreads; i++)
2449 result += threads[i].nodes;
2454 void ThreadsManager::get_beta_counters(Color us, int64_t& our, int64_t& their) const {
2457 for (int i = 0; i < MAX_THREADS; i++)
2459 our += threads[i].betaCutOffs[us];
2460 their += threads[i].betaCutOffs[opposite_color(us)];
2465 // idle_loop() is where the threads are parked when they have no work to do.
2466 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2467 // object for which the current thread is the master.
2469 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2471 assert(threadID >= 0 && threadID < MAX_THREADS);
2475 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2476 // master should exit as last one.
2477 if (AllThreadsShouldExit)
2480 threads[threadID].state = THREAD_TERMINATED;
2484 // If we are not thinking, wait for a condition to be signaled
2485 // instead of wasting CPU time polling for work.
2486 while (AllThreadsShouldSleep || threadID >= ActiveThreads)
2489 assert(threadID != 0);
2490 threads[threadID].state = THREAD_SLEEPING;
2492 #if !defined(_MSC_VER)
2493 lock_grab(&WaitLock);
2494 if (AllThreadsShouldSleep || threadID >= ActiveThreads)
2495 pthread_cond_wait(&WaitCond, &WaitLock);
2496 lock_release(&WaitLock);
2498 WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2502 // If thread has just woken up, mark it as available
2503 if (threads[threadID].state == THREAD_SLEEPING)
2504 threads[threadID].state = THREAD_AVAILABLE;
2506 // If this thread has been assigned work, launch a search
2507 if (threads[threadID].state == THREAD_WORKISWAITING)
2509 assert(!AllThreadsShouldExit && !AllThreadsShouldSleep);
2511 threads[threadID].state = THREAD_SEARCHING;
2513 if (threads[threadID].splitPoint->pvNode)
2514 sp_search_pv(threads[threadID].splitPoint, threadID);
2516 sp_search(threads[threadID].splitPoint, threadID);
2518 assert(threads[threadID].state == THREAD_SEARCHING);
2520 threads[threadID].state = THREAD_AVAILABLE;
2523 // If this thread is the master of a split point and all threads have
2524 // finished their work at this split point, return from the idle loop.
2525 if (sp && sp->cpus == 0)
2527 // Because sp->cpus is decremented under lock protection,
2528 // be sure sp->lock has been released before to proceed.
2529 lock_grab(&(sp->lock));
2530 lock_release(&(sp->lock));
2532 assert(threads[threadID].state == THREAD_AVAILABLE);
2534 threads[threadID].state = THREAD_SEARCHING;
2541 // init_threads() is called during startup. It launches all helper threads,
2542 // and initializes the split point stack and the global locks and condition
2545 void ThreadsManager::init_threads() {
2550 #if !defined(_MSC_VER)
2551 pthread_t pthread[1];
2554 // Initialize global locks
2555 lock_init(&MPLock, NULL);
2556 lock_init(&WaitLock, NULL);
2558 #if !defined(_MSC_VER)
2559 pthread_cond_init(&WaitCond, NULL);
2561 for (i = 0; i < MAX_THREADS; i++)
2562 SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0);
2565 // Initialize SplitPointStack locks
2566 for (i = 0; i < MAX_THREADS; i++)
2567 for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
2569 SplitPointStack[i][j].parent = NULL;
2570 lock_init(&(SplitPointStack[i][j].lock), NULL);
2573 // Will be set just before program exits to properly end the threads
2574 AllThreadsShouldExit = false;
2576 // Threads will be put to sleep as soon as created
2577 AllThreadsShouldSleep = true;
2579 // All threads except the main thread should be initialized to THREAD_AVAILABLE
2581 threads[0].state = THREAD_SEARCHING;
2582 for (i = 1; i < MAX_THREADS; i++)
2583 threads[i].state = THREAD_AVAILABLE;
2585 // Launch the helper threads
2586 for (i = 1; i < MAX_THREADS; i++)
2589 #if !defined(_MSC_VER)
2590 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&i)) == 0);
2592 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, NULL) != NULL);
2597 cout << "Failed to create thread number " << i << endl;
2598 Application::exit_with_failure();
2601 // Wait until the thread has finished launching and is gone to sleep
2602 while (threads[i].state != THREAD_SLEEPING) {}
2607 // exit_threads() is called when the program exits. It makes all the
2608 // helper threads exit cleanly.
2610 void ThreadsManager::exit_threads() {
2612 ActiveThreads = MAX_THREADS; // HACK
2613 AllThreadsShouldSleep = true; // HACK
2614 wake_sleeping_threads();
2616 // This makes the threads to exit idle_loop()
2617 AllThreadsShouldExit = true;
2619 // Wait for thread termination
2620 for (int i = 1; i < MAX_THREADS; i++)
2621 while (threads[i].state != THREAD_TERMINATED);
2623 // Now we can safely destroy the locks
2624 for (int i = 0; i < MAX_THREADS; i++)
2625 for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
2626 lock_destroy(&(SplitPointStack[i][j].lock));
2628 lock_destroy(&WaitLock);
2629 lock_destroy(&MPLock);
2633 // thread_should_stop() checks whether the thread should stop its search.
2634 // This can happen if a beta cutoff has occurred in the thread's currently
2635 // active split point, or in some ancestor of the current split point.
2637 bool ThreadsManager::thread_should_stop(int threadID) const {
2639 assert(threadID >= 0 && threadID < ActiveThreads);
2643 for (sp = threads[threadID].splitPoint; sp && !sp->stopRequest; sp = sp->parent) {}
2648 // thread_is_available() checks whether the thread with threadID "slave" is
2649 // available to help the thread with threadID "master" at a split point. An
2650 // obvious requirement is that "slave" must be idle. With more than two
2651 // threads, this is not by itself sufficient: If "slave" is the master of
2652 // some active split point, it is only available as a slave to the other
2653 // threads which are busy searching the split point at the top of "slave"'s
2654 // split point stack (the "helpful master concept" in YBWC terminology).
2656 bool ThreadsManager::thread_is_available(int slave, int master) const {
2658 assert(slave >= 0 && slave < ActiveThreads);
2659 assert(master >= 0 && master < ActiveThreads);
2660 assert(ActiveThreads > 1);
2662 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2665 // Make a local copy to be sure doesn't change under our feet
2666 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2668 if (localActiveSplitPoints == 0)
2669 // No active split points means that the thread is available as
2670 // a slave for any other thread.
2673 if (ActiveThreads == 2)
2676 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2677 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2678 // could have been set to 0 by another thread leading to an out of bound access.
2679 if (SplitPointStack[slave][localActiveSplitPoints - 1].slaves[master])
2686 // available_thread_exists() tries to find an idle thread which is available as
2687 // a slave for the thread with threadID "master".
2689 bool ThreadsManager::available_thread_exists(int master) const {
2691 assert(master >= 0 && master < ActiveThreads);
2692 assert(ActiveThreads > 1);
2694 for (int i = 0; i < ActiveThreads; i++)
2695 if (thread_is_available(i, master))
2702 // split() does the actual work of distributing the work at a node between
2703 // several threads at PV nodes. If it does not succeed in splitting the
2704 // node (because no idle threads are available, or because we have no unused
2705 // split point objects), the function immediately returns false. If
2706 // splitting is possible, a SplitPoint object is initialized with all the
2707 // data that must be copied to the helper threads (the current position and
2708 // search stack, alpha, beta, the search depth, etc.), and we tell our
2709 // helper threads that they have been assigned work. This will cause them
2710 // to instantly leave their idle loops and call sp_search_pv(). When all
2711 // threads have returned from sp_search_pv (or, equivalently, when
2712 // splitPoint->cpus becomes 0), split() returns true.
2714 template <bool Fake>
2715 bool ThreadsManager::split(const Position& p, SearchStack* sstck, int ply,
2716 Value* alpha, const Value beta, Value* bestValue,
2717 Depth depth, bool mateThreat, int* moves, MovePicker* mp, int master, bool pvNode) {
2720 assert(sstck != NULL);
2721 assert(ply >= 0 && ply < PLY_MAX);
2722 assert(*bestValue >= -VALUE_INFINITE);
2723 assert(*bestValue <= *alpha);
2724 assert(*alpha < beta);
2725 assert(beta <= VALUE_INFINITE);
2726 assert(depth > Depth(0));
2727 assert(master >= 0 && master < ActiveThreads);
2728 assert(Fake || ActiveThreads > 1);
2730 SplitPoint* splitPoint;
2734 // If no other thread is available to help us, or if we have too many
2735 // active split points, don't split.
2736 if ( (!Fake && !available_thread_exists(master))
2737 || threads[master].activeSplitPoints >= ACTIVE_SPLIT_POINTS_MAX)
2739 lock_release(&MPLock);
2743 // Pick the next available split point object from the split point stack
2744 splitPoint = &SplitPointStack[master][threads[master].activeSplitPoints];
2746 // Initialize the split point object
2747 splitPoint->parent = threads[master].splitPoint;
2748 splitPoint->stopRequest = false;
2749 splitPoint->ply = ply;
2750 splitPoint->depth = depth;
2751 splitPoint->mateThreat = mateThreat;
2752 splitPoint->alpha = *alpha;
2753 splitPoint->beta = beta;
2754 splitPoint->pvNode = pvNode;
2755 splitPoint->bestValue = *bestValue;
2756 splitPoint->master = master;
2757 splitPoint->mp = mp;
2758 splitPoint->moves = *moves;
2759 splitPoint->cpus = 1;
2760 splitPoint->pos = &p;
2761 splitPoint->parentSstack = sstck;
2762 for (int i = 0; i < ActiveThreads; i++)
2763 splitPoint->slaves[i] = 0;
2765 threads[master].splitPoint = splitPoint;
2766 threads[master].activeSplitPoints++;
2768 // If we are here it means we are not available
2769 assert(threads[master].state != THREAD_AVAILABLE);
2771 // Allocate available threads setting state to THREAD_BOOKED
2772 for (int i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint; i++)
2773 if (!Fake && thread_is_available(i, master))
2775 threads[i].state = THREAD_BOOKED;
2776 threads[i].splitPoint = splitPoint;
2777 splitPoint->slaves[i] = 1;
2781 assert(Fake || splitPoint->cpus > 1);
2783 // We can release the lock because slave threads are already booked and master is not available
2784 lock_release(&MPLock);
2786 // Tell the threads that they have work to do. This will make them leave
2787 // their idle loop. But before copy search stack tail for each thread.
2788 for (int i = 0; i < ActiveThreads; i++)
2789 if (i == master || splitPoint->slaves[i])
2791 memcpy(splitPoint->sstack[i] + ply - 1, sstck + ply - 1, 4 * sizeof(SearchStack));
2793 assert(i == master || threads[i].state == THREAD_BOOKED);
2795 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2798 // Everything is set up. The master thread enters the idle loop, from
2799 // which it will instantly launch a search, because its state is
2800 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2801 // idle loop, which means that the main thread will return from the idle
2802 // loop when all threads have finished their work at this split point
2803 // (i.e. when splitPoint->cpus == 0).
2804 idle_loop(master, splitPoint);
2806 // We have returned from the idle loop, which means that all threads are
2807 // finished. Update alpha and bestValue, and return.
2810 *alpha = splitPoint->alpha;
2811 *bestValue = splitPoint->bestValue;
2812 threads[master].activeSplitPoints--;
2813 threads[master].splitPoint = splitPoint->parent;
2815 lock_release(&MPLock);
2820 // wake_sleeping_threads() wakes up all sleeping threads when it is time
2821 // to start a new search from the root.
2823 void ThreadsManager::wake_sleeping_threads() {
2825 assert(AllThreadsShouldSleep);
2826 assert(ActiveThreads > 0);
2828 AllThreadsShouldSleep = false;
2830 if (ActiveThreads == 1)
2833 #if !defined(_MSC_VER)
2834 pthread_mutex_lock(&WaitLock);
2835 pthread_cond_broadcast(&WaitCond);
2836 pthread_mutex_unlock(&WaitLock);
2838 for (int i = 1; i < MAX_THREADS; i++)
2839 SetEvent(SitIdleEvent[i]);
2845 // put_threads_to_sleep() makes all the threads go to sleep just before
2846 // to leave think(), at the end of the search. Threads should have already
2847 // finished the job and should be idle.
2849 void ThreadsManager::put_threads_to_sleep() {
2851 assert(!AllThreadsShouldSleep);
2853 // This makes the threads to go to sleep
2854 AllThreadsShouldSleep = true;
2857 /// The RootMoveList class
2859 // RootMoveList c'tor
2861 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
2863 SearchStack ss[PLY_MAX_PLUS_2];
2864 MoveStack mlist[MaxRootMoves];
2866 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
2868 // Generate all legal moves
2869 MoveStack* last = generate_moves(pos, mlist);
2871 // Add each move to the moves[] array
2872 for (MoveStack* cur = mlist; cur != last; cur++)
2874 bool includeMove = includeAllMoves;
2876 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
2877 includeMove = (searchMoves[k] == cur->move);
2882 // Find a quick score for the move
2884 pos.do_move(cur->move, st);
2885 moves[count].move = cur->move;
2886 moves[count].score = -qsearch<PV>(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0);
2887 moves[count].pv[0] = cur->move;
2888 moves[count].pv[1] = MOVE_NONE;
2889 pos.undo_move(cur->move);
2896 // RootMoveList simple methods definitions
2898 void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
2900 moves[moveNum].nodes = nodes;
2901 moves[moveNum].cumulativeNodes += nodes;
2904 void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
2906 moves[moveNum].ourBeta = our;
2907 moves[moveNum].theirBeta = their;
2910 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
2914 for (j = 0; pv[j] != MOVE_NONE; j++)
2915 moves[moveNum].pv[j] = pv[j];
2917 moves[moveNum].pv[j] = MOVE_NONE;
2921 // RootMoveList::sort() sorts the root move list at the beginning of a new
2924 void RootMoveList::sort() {
2926 sort_multipv(count - 1); // Sort all items
2930 // RootMoveList::sort_multipv() sorts the first few moves in the root move
2931 // list by their scores and depths. It is used to order the different PVs
2932 // correctly in MultiPV mode.
2934 void RootMoveList::sort_multipv(int n) {
2938 for (i = 1; i <= n; i++)
2940 RootMove rm = moves[i];
2941 for (j = i; j > 0 && moves[j - 1] < rm; j--)
2942 moves[j] = moves[j - 1];