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"
49 //// Local definitions
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* waitSp);
86 bool split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
87 Depth depth, int* moves, MovePicker* mp, int master, bool pvNode);
90 friend void poll(SearchStack ss[], int ply);
93 volatile bool AllThreadsShouldExit, AllThreadsShouldSleep;
94 Thread threads[MAX_THREADS];
95 SplitPoint SplitPointStack[MAX_THREADS][ACTIVE_SPLIT_POINTS_MAX];
99 #if !defined(_MSC_VER)
100 pthread_cond_t WaitCond;
101 pthread_mutex_t WaitLock;
103 HANDLE SitIdleEvent[MAX_THREADS];
109 // RootMove struct is used for moves at the root at the tree. For each
110 // root move, we store a score, a node count, and a PV (really a refutation
111 // in the case of moves which fail low).
115 RootMove() { nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL; }
117 // RootMove::operator<() is the comparison function used when
118 // sorting the moves. A move m1 is considered to be better
119 // than a move m2 if it has a higher score, or if the moves
120 // have equal score but m1 has the higher node count.
121 bool operator<(const RootMove& m) const {
123 return score != m.score ? score < m.score : theirBeta <= m.theirBeta;
128 int64_t nodes, cumulativeNodes, ourBeta, theirBeta;
129 Move pv[PLY_MAX_PLUS_2];
133 // The RootMoveList class is essentially an array of RootMove objects, with
134 // a handful of methods for accessing the data in the individual moves.
139 RootMoveList(Position& pos, Move searchMoves[]);
141 int move_count() const { return count; }
142 Move get_move(int moveNum) const { return moves[moveNum].move; }
143 Value get_move_score(int moveNum) const { return moves[moveNum].score; }
144 void set_move_score(int moveNum, Value score) { moves[moveNum].score = score; }
145 Move get_move_pv(int moveNum, int i) const { return moves[moveNum].pv[i]; }
146 int64_t get_move_cumulative_nodes(int moveNum) const { return moves[moveNum].cumulativeNodes; }
148 void set_move_nodes(int moveNum, int64_t nodes);
149 void set_beta_counters(int moveNum, int64_t our, int64_t their);
150 void set_move_pv(int moveNum, const Move pv[]);
152 void sort_multipv(int n);
155 static const int MaxRootMoves = 500;
156 RootMove moves[MaxRootMoves];
165 const Depth RazorDepth = 4 * OnePly;
166 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * d); }
168 // Step 8. Null move search with verification search
170 // Null move margin. A null move search will not be done if the static
171 // evaluation of the position is more than NullMoveMargin below beta.
172 const Value NullMoveMargin = Value(0x200);
174 // Depth limit for use of dynamic threat detection when null move fails low
175 const Depth ThreatDepth = 5 * OnePly;
177 // Step 9. Internal iterative deepening
179 const Depth IIDDepthAtPVNodes = 5 * OnePly;
180 const Depth IIDDepthAtNonPVNodes = 8 * OnePly;
182 // Internal iterative deepening margin. At Non-PV nodes
183 // we do an internal iterative deepening
184 // search when the static evaluation is at most IIDMargin below beta.
185 const Value IIDMargin = Value(0x100);
187 // Step 11. Decide the new search depth
189 // Extensions. Configurable UCI options.
190 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
191 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
192 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
194 const Depth SingularExtensionDepthAtPVNodes = 6 * OnePly;
195 const Depth SingularExtensionDepthAtNonPVNodes = 8 * OnePly;
197 // If the TT move is at least SingularExtensionMargin better then the
198 // remaining ones we will extend it.
199 const Value SingularExtensionMargin = Value(0x20);
201 // Step 12. Futility pruning
203 const Value FutilityMarginQS = Value(0x80);
205 // Futility lookup tables (initialized at startup) and their getter functions
206 int32_t FutilityMarginsMatrix[14][64]; // [depth][moveNumber]
207 int FutilityMoveCountArray[32]; // [depth]
209 inline Value futility_margin(Depth d, int mn) { return Value(d < 7*OnePly ? FutilityMarginsMatrix[Max(d, 0)][Min(mn, 63)] : 2 * VALUE_INFINITE); }
210 inline int futility_move_count(Depth d) { return d < 16*OnePly ? FutilityMoveCountArray[d] : 512; }
212 // Step 14. Reduced search
214 // Reduction lookup tables (initialized at startup) and their getter functions
215 int8_t PVReductionMatrix[64][64]; // [depth][moveNumber]
216 int8_t NonPVReductionMatrix[64][64]; // [depth][moveNumber]
218 inline Depth pv_reduction(Depth d, int mn) { return (Depth) PVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; }
219 inline Depth nonpv_reduction(Depth d, int mn) { return (Depth) NonPVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; }
223 // Search depth at iteration 1
224 const Depth InitialDepth = OnePly;
226 // Easy move margin. An easy move candidate must be at least this much
227 // better than the second best move.
228 const Value EasyMoveMargin = Value(0x200);
230 /// Variables initialized by UCI options
232 // Last seconds noise filtering (LSN)
233 const bool UseLSNFiltering = true;
234 const int LSNTime = 4000; // In milliseconds
235 const Value LSNValue = value_from_centipawns(200);
236 bool loseOnTime = false;
238 // Iteration counters
241 // Scores and number of times the best move changed for each iteration
242 Value ValueByIteration[PLY_MAX_PLUS_2];
243 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
245 // Search window management
251 // Time managment variables
254 int MaxNodes, MaxDepth;
255 int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
256 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
257 bool AbortSearch, Quit;
258 bool AspirationFailLow;
260 // Show current line?
261 bool ShowCurrentLine;
265 std::ofstream LogFile;
267 // MP related variables
268 Depth MinimumSplitDepth;
269 int MaxThreadsPerSplitPoint;
272 // Node counters, used only by thread[0] but try to keep in different
273 // cache lines (64 bytes each) from the heavy SMP read accessed variables.
275 int NodesBetweenPolls = 30000;
282 Value id_loop(const Position& pos, Move searchMoves[]);
283 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta);
284 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
285 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE);
286 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
287 void sp_search(SplitPoint* sp, int threadID);
288 void sp_search_pv(SplitPoint* sp, int threadID);
289 void init_node(SearchStack ss[], int ply, int threadID);
290 void update_pv(SearchStack ss[], int ply);
291 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply);
292 bool connected_moves(const Position& pos, Move m1, Move m2);
293 bool value_is_mate(Value value);
294 bool move_is_killer(Move m, const SearchStack& ss);
295 Depth extension(const Position&, Move, bool, bool, bool, bool, bool, bool*);
296 bool ok_to_do_nullmove(const Position& pos);
297 bool ok_to_prune(const Position& pos, Move m, Move threat);
298 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
299 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
300 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
301 void update_killers(Move m, SearchStack& ss);
302 void update_gains(const Position& pos, Move move, Value before, Value after);
304 int current_search_time();
306 void poll(SearchStack ss[], int ply);
308 void wait_for_stop_or_ponderhit();
309 void init_ss_array(SearchStack ss[]);
311 #if !defined(_MSC_VER)
312 void *init_thread(void *threadID);
314 DWORD WINAPI init_thread(LPVOID threadID);
324 /// init_threads(), exit_threads() and nodes_searched() are helpers to
325 /// give accessibility to some TM methods from outside of current file.
327 void init_threads() { TM.init_threads(); }
328 void exit_threads() { TM.exit_threads(); }
329 int64_t nodes_searched() { return TM.nodes_searched(); }
332 /// perft() is our utility to verify move generation is bug free. All the legal
333 /// moves up to given depth are generated and counted and the sum returned.
335 int perft(Position& pos, Depth depth)
339 MovePicker mp = MovePicker(pos, MOVE_NONE, depth, H);
341 // If we are at the last ply we don't need to do and undo
342 // the moves, just to count them.
343 if (depth <= OnePly) // Replace with '<' to test also qsearch
345 while (mp.get_next_move()) sum++;
349 // Loop through all legal moves
351 while ((move = mp.get_next_move()) != MOVE_NONE)
354 pos.do_move(move, st, ci, pos.move_is_check(move, ci));
355 sum += perft(pos, depth - OnePly);
362 /// think() is the external interface to Stockfish's search, and is called when
363 /// the program receives the UCI 'go' command. It initializes various
364 /// search-related global variables, and calls root_search(). It returns false
365 /// when a quit command is received during the search.
367 bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
368 int time[], int increment[], int movesToGo, int maxDepth,
369 int maxNodes, int maxTime, Move searchMoves[]) {
371 // Initialize global search variables
372 StopOnPonderhit = AbortSearch = Quit = false;
373 AspirationFailLow = false;
375 SearchStartTime = get_system_time();
376 ExactMaxTime = maxTime;
379 InfiniteSearch = infinite;
380 PonderSearch = ponder;
381 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
383 // Look for a book move, only during games, not tests
384 if (UseTimeManagement && get_option_value_bool("OwnBook"))
387 if (get_option_value_string("Book File") != OpeningBook.file_name())
388 OpeningBook.open(get_option_value_string("Book File"));
390 bookMove = OpeningBook.get_move(pos);
391 if (bookMove != MOVE_NONE)
394 wait_for_stop_or_ponderhit();
396 cout << "bestmove " << bookMove << endl;
401 TM.resetNodeCounters();
403 if (button_was_pressed("New Game"))
404 loseOnTime = false; // Reset at the beginning of a new game
406 // Read UCI option values
407 TT.set_size(get_option_value_int("Hash"));
408 if (button_was_pressed("Clear Hash"))
411 bool PonderingEnabled = get_option_value_bool("Ponder");
412 MultiPV = get_option_value_int("MultiPV");
414 CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)"));
415 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)"));
420 PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)"));
421 PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
423 PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
424 PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
426 PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
427 PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)"));
429 MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
430 MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
432 Chess960 = get_option_value_bool("UCI_Chess960");
433 ShowCurrentLine = get_option_value_bool("UCI_ShowCurrLine");
434 UseLogFile = get_option_value_bool("Use Search Log");
436 LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app);
438 MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly;
439 MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point");
441 read_weights(pos.side_to_move());
443 // Set the number of active threads
444 int newActiveThreads = get_option_value_int("Threads");
445 if (newActiveThreads != TM.active_threads())
447 TM.set_active_threads(newActiveThreads);
448 init_eval(TM.active_threads());
449 // HACK: init_eval() destroys the static castleRightsMask[] array in the
450 // Position class. The below line repairs the damage.
451 Position p(pos.to_fen());
455 // Wake up sleeping threads
456 TM.wake_sleeping_threads();
459 int myTime = time[side_to_move];
460 int myIncrement = increment[side_to_move];
461 if (UseTimeManagement)
463 if (!movesToGo) // Sudden death time control
467 MaxSearchTime = myTime / 30 + myIncrement;
468 AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
470 else // Blitz game without increment
472 MaxSearchTime = myTime / 30;
473 AbsoluteMaxSearchTime = myTime / 8;
476 else // (x moves) / (y minutes)
480 MaxSearchTime = myTime / 2;
481 AbsoluteMaxSearchTime = (myTime > 3000)? (myTime - 500) : ((myTime * 3) / 4);
485 MaxSearchTime = myTime / Min(movesToGo, 20);
486 AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
490 if (PonderingEnabled)
492 MaxSearchTime += MaxSearchTime / 4;
493 MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime);
497 // Set best NodesBetweenPolls interval
499 NodesBetweenPolls = Min(MaxNodes, 30000);
500 else if (myTime && myTime < 1000)
501 NodesBetweenPolls = 1000;
502 else if (myTime && myTime < 5000)
503 NodesBetweenPolls = 5000;
505 NodesBetweenPolls = 30000;
507 // Write information to search log file
509 LogFile << "Searching: " << pos.to_fen() << endl
510 << "infinite: " << infinite
511 << " ponder: " << ponder
512 << " time: " << myTime
513 << " increment: " << myIncrement
514 << " moves to go: " << movesToGo << endl;
516 // LSN filtering. Used only for developing purpose. Disabled by default.
520 // Step 2. If after last move we decided to lose on time, do it now!
521 while (SearchStartTime + myTime + 1000 > get_system_time())
525 // We're ready to start thinking. Call the iterative deepening loop function
526 Value v = id_loop(pos, searchMoves);
530 // Step 1. If this is sudden death game and our position is hopeless,
531 // decide to lose on time.
532 if ( !loseOnTime // If we already lost on time, go to step 3.
542 // Step 3. Now after stepping over the time limit, reset flag for next match.
550 TM.put_threads_to_sleep();
556 /// init_search() is called during startup. It initializes various lookup tables
560 // Init our reduction lookup tables
561 for (int i = 1; i < 64; i++) // i == depth (OnePly = 1)
562 for (int j = 1; j < 64; j++) // j == moveNumber
564 double pvRed = 0.5 + log(double(i)) * log(double(j)) / 6.0;
565 double nonPVRed = 0.5 + log(double(i)) * log(double(j)) / 3.0;
566 PVReductionMatrix[i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0);
567 NonPVReductionMatrix[i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0);
570 // Init futility margins array
571 for (int i = 0; i < 14; i++) // i == depth (OnePly = 2)
572 for (int j = 0; j < 64; j++) // j == moveNumber
574 FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j; // FIXME: test using log instead of BSR
577 // Init futility move count array
578 for (int i = 0; i < 32; i++) // i == depth (OnePly = 2)
579 FutilityMoveCountArray[i] = 3 + (1 << (3 * i / 8));
583 // SearchStack::init() initializes a search stack. Used at the beginning of a
584 // new search from the root.
585 void SearchStack::init(int ply) {
587 pv[ply] = pv[ply + 1] = MOVE_NONE;
588 currentMove = threatMove = MOVE_NONE;
589 reduction = Depth(0);
593 void SearchStack::initKillers() {
595 mateKiller = MOVE_NONE;
596 for (int i = 0; i < KILLER_MAX; i++)
597 killers[i] = MOVE_NONE;
602 // id_loop() is the main iterative deepening loop. It calls root_search
603 // repeatedly with increasing depth until the allocated thinking time has
604 // been consumed, the user stops the search, or the maximum search depth is
607 Value id_loop(const Position& pos, Move searchMoves[]) {
610 SearchStack ss[PLY_MAX_PLUS_2];
612 // searchMoves are verified, copied, scored and sorted
613 RootMoveList rml(p, searchMoves);
615 // Handle special case of searching on a mate/stale position
616 if (rml.move_count() == 0)
619 wait_for_stop_or_ponderhit();
621 return pos.is_check()? -VALUE_MATE : VALUE_DRAW;
624 // Print RootMoveList c'tor startup scoring to the standard output,
625 // so that we print information also for iteration 1.
626 cout << "info depth " << 1 << "\ninfo depth " << 1
627 << " score " << value_to_string(rml.get_move_score(0))
628 << " time " << current_search_time()
629 << " nodes " << TM.nodes_searched()
631 << " pv " << rml.get_move(0) << "\n";
637 ValueByIteration[1] = rml.get_move_score(0);
640 // Is one move significantly better than others after initial scoring ?
641 Move EasyMove = MOVE_NONE;
642 if ( rml.move_count() == 1
643 || rml.get_move_score(0) > rml.get_move_score(1) + EasyMoveMargin)
644 EasyMove = rml.get_move(0);
646 // Iterative deepening loop
647 while (Iteration < PLY_MAX)
649 // Initialize iteration
652 BestMoveChangesByIteration[Iteration] = 0;
656 cout << "info depth " << Iteration << endl;
658 // Calculate dynamic search window based on previous iterations
661 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
663 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
664 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
666 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
667 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
669 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
670 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
674 alpha = - VALUE_INFINITE;
675 beta = VALUE_INFINITE;
678 // Search to the current depth
679 Value value = root_search(p, ss, rml, alpha, beta);
681 // Write PV to transposition table, in case the relevant entries have
682 // been overwritten during the search.
683 TT.insert_pv(p, ss[0].pv);
686 break; // Value cannot be trusted. Break out immediately!
688 //Save info about search result
689 ValueByIteration[Iteration] = value;
691 // Drop the easy move if it differs from the new best move
692 if (ss[0].pv[0] != EasyMove)
693 EasyMove = MOVE_NONE;
695 if (UseTimeManagement)
698 bool stopSearch = false;
700 // Stop search early if there is only a single legal move,
701 // we search up to Iteration 6 anyway to get a proper score.
702 if (Iteration >= 6 && rml.move_count() == 1)
705 // Stop search early when the last two iterations returned a mate score
707 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
708 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
711 // Stop search early if one move seems to be much better than the rest
712 int64_t nodes = TM.nodes_searched();
714 && EasyMove == ss[0].pv[0]
715 && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
716 && current_search_time() > MaxSearchTime / 16)
717 ||( rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100
718 && current_search_time() > MaxSearchTime / 32)))
721 // Add some extra time if the best move has changed during the last two iterations
722 if (Iteration > 5 && Iteration <= 50)
723 ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2)
724 + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3);
726 // Stop search if most of MaxSearchTime is consumed at the end of the
727 // iteration. We probably don't have enough time to search the first
728 // move at the next iteration anyway.
729 if (current_search_time() > ((MaxSearchTime + ExtraSearchTime) * 80) / 128)
737 StopOnPonderhit = true;
741 if (MaxDepth && Iteration >= MaxDepth)
747 // If we are pondering or in infinite search, we shouldn't print the
748 // best move before we are told to do so.
749 if (!AbortSearch && (PonderSearch || InfiniteSearch))
750 wait_for_stop_or_ponderhit();
752 // Print final search statistics
753 cout << "info nodes " << TM.nodes_searched()
755 << " time " << current_search_time()
756 << " hashfull " << TT.full() << endl;
758 // Print the best move and the ponder move to the standard output
759 if (ss[0].pv[0] == MOVE_NONE)
761 ss[0].pv[0] = rml.get_move(0);
762 ss[0].pv[1] = MOVE_NONE;
764 cout << "bestmove " << ss[0].pv[0];
765 if (ss[0].pv[1] != MOVE_NONE)
766 cout << " ponder " << ss[0].pv[1];
773 dbg_print_mean(LogFile);
775 if (dbg_show_hit_rate)
776 dbg_print_hit_rate(LogFile);
778 LogFile << "\nNodes: " << TM.nodes_searched()
779 << "\nNodes/second: " << nps()
780 << "\nBest move: " << move_to_san(p, ss[0].pv[0]);
783 p.do_move(ss[0].pv[0], st);
784 LogFile << "\nPonder move: " << move_to_san(p, ss[0].pv[1]) << endl;
786 return rml.get_move_score(0);
790 // root_search() is the function which searches the root node. It is
791 // similar to search_pv except that it uses a different move ordering
792 // scheme and prints some information to the standard output.
794 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta) {
799 Depth depth, ext, newDepth;
802 int researchCount = 0;
803 bool moveIsCheck, captureOrPromotion, dangerous;
804 Value alpha = oldAlpha;
805 bool isCheck = pos.is_check();
807 // Evaluate the position statically
809 ss[0].eval = !isCheck ? evaluate(pos, ei, 0) : VALUE_NONE;
811 while (1) // Fail low loop
814 // Loop through all the moves in the root move list
815 for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
819 // We failed high, invalidate and skip next moves, leave node-counters
820 // and beta-counters as they are and quickly return, we will try to do
821 // a research at the next iteration with a bigger aspiration window.
822 rml.set_move_score(i, -VALUE_INFINITE);
826 RootMoveNumber = i + 1;
828 // Save the current node count before the move is searched
829 nodes = TM.nodes_searched();
831 // Reset beta cut-off counters
832 TM.resetBetaCounters();
834 // Pick the next root move, and print the move and the move number to
835 // the standard output.
836 move = ss[0].currentMove = rml.get_move(i);
838 if (current_search_time() >= 1000)
839 cout << "info currmove " << move
840 << " currmovenumber " << RootMoveNumber << endl;
842 // Decide search depth for this move
843 moveIsCheck = pos.move_is_check(move);
844 captureOrPromotion = pos.move_is_capture_or_promotion(move);
845 depth = (Iteration - 2) * OnePly + InitialDepth;
846 ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
847 newDepth = depth + ext;
849 value = - VALUE_INFINITE;
851 while (1) // Fail high loop
854 // Make the move, and search it
855 pos.do_move(move, st, ci, moveIsCheck);
857 if (i < MultiPV || value > alpha)
859 // Aspiration window is disabled in multi-pv case
861 alpha = -VALUE_INFINITE;
863 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
867 // Try to reduce non-pv search depth by one ply if move seems not problematic,
868 // if the move fails high will be re-searched at full depth.
869 bool doFullDepthSearch = true;
871 if ( depth >= 3*OnePly // FIXME was newDepth
873 && !captureOrPromotion
874 && !move_is_castle(move))
876 ss[0].reduction = pv_reduction(depth, RootMoveNumber - MultiPV + 1);
879 value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0);
880 doFullDepthSearch = (value > alpha);
884 if (doFullDepthSearch)
886 ss[0].reduction = Depth(0);
887 value = -search(pos, ss, -alpha, newDepth, 1, true, 0);
890 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
896 // Can we exit fail high loop ?
897 if (AbortSearch || value < beta)
900 // We are failing high and going to do a research. It's important to update score
901 // before research in case we run out of time while researching.
902 rml.set_move_score(i, value);
904 TT.extract_pv(pos, ss[0].pv, PLY_MAX);
905 rml.set_move_pv(i, ss[0].pv);
907 // Print search information to the standard output
908 cout << "info depth " << Iteration
909 << " score " << value_to_string(value)
910 << ((value >= beta) ? " lowerbound" :
911 ((value <= alpha)? " upperbound" : ""))
912 << " time " << current_search_time()
913 << " nodes " << TM.nodes_searched()
917 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
918 cout << ss[0].pv[j] << " ";
924 ValueType type = (value >= beta ? VALUE_TYPE_LOWER
925 : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT));
927 LogFile << pretty_pv(pos, current_search_time(), Iteration,
928 TM.nodes_searched(), value, type, ss[0].pv) << endl;
931 // Prepare for a research after a fail high, each time with a wider window
933 beta = Min(beta + AspirationDelta * (1 << researchCount), VALUE_INFINITE);
935 } // End of fail high loop
937 // Finished searching the move. If AbortSearch is true, the search
938 // was aborted because the user interrupted the search or because we
939 // ran out of time. In this case, the return value of the search cannot
940 // be trusted, and we break out of the loop without updating the best
945 // Remember beta-cutoff and searched nodes counts for this move. The
946 // info is used to sort the root moves at the next iteration.
948 TM.get_beta_counters(pos.side_to_move(), our, their);
949 rml.set_beta_counters(i, our, their);
950 rml.set_move_nodes(i, TM.nodes_searched() - nodes);
952 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
954 if (value <= alpha && i >= MultiPV)
955 rml.set_move_score(i, -VALUE_INFINITE);
958 // PV move or new best move!
961 rml.set_move_score(i, value);
963 TT.extract_pv(pos, ss[0].pv, PLY_MAX);
964 rml.set_move_pv(i, ss[0].pv);
968 // We record how often the best move has been changed in each
969 // iteration. This information is used for time managment: When
970 // the best move changes frequently, we allocate some more time.
972 BestMoveChangesByIteration[Iteration]++;
974 // Print search information to the standard output
975 cout << "info depth " << Iteration
976 << " score " << value_to_string(value)
977 << ((value >= beta) ? " lowerbound" :
978 ((value <= alpha)? " upperbound" : ""))
979 << " time " << current_search_time()
980 << " nodes " << TM.nodes_searched()
984 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
985 cout << ss[0].pv[j] << " ";
991 ValueType type = (value >= beta ? VALUE_TYPE_LOWER
992 : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT));
994 LogFile << pretty_pv(pos, current_search_time(), Iteration,
995 TM.nodes_searched(), value, type, ss[0].pv) << endl;
1002 rml.sort_multipv(i);
1003 for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
1005 cout << "info multipv " << j + 1
1006 << " score " << value_to_string(rml.get_move_score(j))
1007 << " depth " << ((j <= i)? Iteration : Iteration - 1)
1008 << " time " << current_search_time()
1009 << " nodes " << TM.nodes_searched()
1013 for (int k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
1014 cout << rml.get_move_pv(j, k) << " ";
1018 alpha = rml.get_move_score(Min(i, MultiPV-1));
1020 } // PV move or new best move
1022 assert(alpha >= oldAlpha);
1024 AspirationFailLow = (alpha == oldAlpha);
1026 if (AspirationFailLow && StopOnPonderhit)
1027 StopOnPonderhit = false;
1030 // Can we exit fail low loop ?
1031 if (AbortSearch || alpha > oldAlpha)
1034 // Prepare for a research after a fail low, each time with a wider window
1036 alpha = Max(alpha - AspirationDelta * (1 << researchCount), -VALUE_INFINITE);
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 < TM.active_threads());
1055 Move movesSearched[256];
1060 Depth ext, newDepth;
1061 Value bestValue, value, oldAlpha;
1062 bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
1063 bool mateThreat = false;
1065 bestValue = value = -VALUE_INFINITE;
1068 return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID);
1070 // Step 1. Initialize node and poll
1071 // Polling can abort search.
1072 init_node(ss, ply, threadID);
1074 // Step 2. Check for aborted search and immediate draw
1075 if (AbortSearch || TM.thread_should_stop(threadID))
1078 if (pos.is_draw() || ply >= PLY_MAX - 1)
1081 // Step 3. Mate distance pruning
1083 alpha = Max(value_mated_in(ply), alpha);
1084 beta = Min(value_mate_in(ply+1), beta);
1088 // Step 4. Transposition table lookup
1089 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1090 // This is to avoid problems in the following areas:
1092 // * Repetition draw detection
1093 // * Fifty move rule detection
1094 // * Searching for a mate
1095 // * Printing of full PV line
1096 tte = TT.retrieve(pos.get_key());
1097 ttMove = (tte ? tte->move() : MOVE_NONE);
1099 // Step 5. Evaluate the position statically
1100 // At PV nodes we do this only to update gain statistics
1101 isCheck = pos.is_check();
1104 ss[ply].eval = evaluate(pos, ei, threadID);
1105 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1108 // Step 6. Razoring (is omitted in PV nodes)
1109 // Step 7. Static null move pruning (is omitted in PV nodes)
1110 // Step 8. Null move search with verification search (is omitted in PV nodes)
1112 // Step 9. Internal iterative deepening
1113 if ( depth >= IIDDepthAtPVNodes
1114 && ttMove == MOVE_NONE)
1116 search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID);
1117 ttMove = ss[ply].pv[ply];
1118 tte = TT.retrieve(pos.get_key());
1121 // Step 10. Loop through moves
1122 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1124 // Initialize a MovePicker object for the current position
1125 mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move()));
1126 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1129 while ( alpha < beta
1130 && (move = mp.get_next_move()) != MOVE_NONE
1131 && !TM.thread_should_stop(threadID))
1133 assert(move_is_ok(move));
1135 singleEvasion = (isCheck && mp.number_of_evasions() == 1);
1136 moveIsCheck = pos.move_is_check(move, ci);
1137 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1139 // Step 11. Decide the new search depth
1140 ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1142 // Singular extension search. We extend the TT move if its value is much better than
1143 // its siblings. To verify this we do a reduced search on all the other moves but the
1144 // ttMove, if result is lower then ttValue minus a margin then we extend ttMove.
1145 if ( depth >= SingularExtensionDepthAtPVNodes
1147 && move == tte->move()
1149 && is_lower_bound(tte->type())
1150 && tte->depth() >= depth - 3 * OnePly)
1152 Value ttValue = value_from_tt(tte->value(), ply);
1154 if (abs(ttValue) < VALUE_KNOWN_WIN)
1156 Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move);
1158 if (excValue < ttValue - SingularExtensionMargin)
1163 newDepth = depth - OnePly + ext;
1165 // Update current move (this must be done after singular extension search)
1166 movesSearched[moveCount++] = ss[ply].currentMove = move;
1168 // Step 12. Futility pruning (is omitted in PV nodes)
1170 // Step 13. Make the move
1171 pos.do_move(move, st, ci, moveIsCheck);
1173 // Step extra. pv search (only in PV nodes)
1174 // The first move in list is the expected PV
1176 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1179 // Step 14. Reduced search
1180 // if the move fails high will be re-searched at full depth.
1181 bool doFullDepthSearch = true;
1183 if ( depth >= 3*OnePly
1185 && !captureOrPromotion
1186 && !move_is_castle(move)
1187 && !move_is_killer(move, ss[ply]))
1189 ss[ply].reduction = pv_reduction(depth, moveCount);
1190 if (ss[ply].reduction)
1192 value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
1193 doFullDepthSearch = (value > alpha);
1197 // Step 15. Full depth search
1198 if (doFullDepthSearch)
1200 ss[ply].reduction = Depth(0);
1201 value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID);
1203 // Step extra. pv search (only in PV nodes)
1204 if (value > alpha && value < beta)
1205 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1209 // Step 16. Undo move
1210 pos.undo_move(move);
1212 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1214 // Step 17. Check for new best move
1215 if (value > bestValue)
1222 if (value == value_mate_in(ply + 1))
1223 ss[ply].mateKiller = move;
1227 // Step 18. Check for split
1228 if ( TM.active_threads() > 1
1230 && depth >= MinimumSplitDepth
1232 && TM.available_thread_exists(threadID)
1234 && !TM.thread_should_stop(threadID)
1235 && TM.split(pos, ss, ply, &alpha, beta, &bestValue,
1236 depth, &moveCount, &mp, threadID, true))
1240 // Step 19. Check for mate and stalemate
1241 // All legal moves have been searched and if there were
1242 // no legal moves, it must be mate or stalemate.
1244 return (isCheck ? value_mated_in(ply) : VALUE_DRAW);
1246 // Step 20. Update tables
1247 // If the search is not aborted, update the transposition table,
1248 // history counters, and killer moves.
1249 if (AbortSearch || TM.thread_should_stop(threadID))
1252 if (bestValue <= oldAlpha)
1253 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1255 else if (bestValue >= beta)
1257 TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
1258 move = ss[ply].pv[ply];
1259 if (!pos.move_is_capture_or_promotion(move))
1261 update_history(pos, move, depth, movesSearched, moveCount);
1262 update_killers(move, ss[ply]);
1264 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
1267 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
1273 // search() is the search function for zero-width nodes.
1275 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth,
1276 int ply, bool allowNullmove, int threadID, Move excludedMove) {
1278 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1279 assert(ply >= 0 && ply < PLY_MAX);
1280 assert(threadID >= 0 && threadID < TM.active_threads());
1282 Move movesSearched[256];
1287 Depth ext, newDepth;
1288 Value bestValue, refinedValue, nullValue, value, futilityValueScaled;
1289 bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
1290 bool mateThreat = false;
1292 refinedValue = bestValue = value = -VALUE_INFINITE;
1295 return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1297 // Step 1. Initialize node and poll
1298 // Polling can abort search.
1299 init_node(ss, ply, threadID);
1301 // Step 2. Check for aborted search and immediate draw
1302 if (AbortSearch || TM.thread_should_stop(threadID))
1305 if (pos.is_draw() || ply >= PLY_MAX - 1)
1308 // Step 3. Mate distance pruning
1309 if (value_mated_in(ply) >= beta)
1312 if (value_mate_in(ply + 1) < beta)
1315 // Step 4. Transposition table lookup
1317 // We don't want the score of a partial search to overwrite a previous full search
1318 // TT value, so we use a different position key in case of an excluded move exists.
1319 Key posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1321 tte = TT.retrieve(posKey);
1322 ttMove = (tte ? tte->move() : MOVE_NONE);
1324 if (tte && ok_to_use_TT(tte, depth, beta, ply))
1326 ss[ply].currentMove = ttMove; // Can be MOVE_NONE
1327 return value_from_tt(tte->value(), ply);
1330 // Step 5. Evaluate the position statically
1331 isCheck = pos.is_check();
1335 if (tte && (tte->type() & VALUE_TYPE_EVAL))
1336 ss[ply].eval = value_from_tt(tte->value(), ply);
1338 ss[ply].eval = evaluate(pos, ei, threadID);
1340 refinedValue = refine_eval(tte, ss[ply].eval, ply); // Enhance accuracy with TT value if possible
1341 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1345 if ( !value_is_mate(beta)
1347 && depth < RazorDepth
1348 && refinedValue < beta - razor_margin(depth)
1349 && ss[ply - 1].currentMove != MOVE_NULL
1350 && ttMove == MOVE_NONE
1351 && !pos.has_pawn_on_7th(pos.side_to_move()))
1353 Value rbeta = beta - razor_margin(depth);
1354 Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID);
1356 return v; //FIXME: Logically should be: return (v + razor_margin(depth));
1359 // Step 7. Static null move pruning
1360 // We're betting that the opponent doesn't have a move that will reduce
1361 // the score by more than fuility_margin(depth) if we do a null move.
1364 && depth < RazorDepth
1365 && refinedValue - futility_margin(depth, 0) >= beta)
1366 return refinedValue - futility_margin(depth, 0);
1368 // Step 8. Null move search with verification search
1369 // When we jump directly to qsearch() we do a null move only if static value is
1370 // at least beta. Otherwise we do a null move if static value is not more than
1371 // NullMoveMargin under beta.
1375 && !value_is_mate(beta)
1376 && ok_to_do_nullmove(pos)
1377 && refinedValue >= beta - (depth >= 4 * OnePly ? NullMoveMargin : 0))
1379 ss[ply].currentMove = MOVE_NULL;
1381 pos.do_null_move(st);
1383 // Null move dynamic reduction based on depth
1384 int R = 3 + (depth >= 5 * OnePly ? depth / 8 : 0);
1386 // Null move dynamic reduction based on value
1387 if (refinedValue - beta > PawnValueMidgame)
1390 nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);
1392 pos.undo_null_move();
1394 if (nullValue >= beta)
1396 if (depth < 6 * OnePly)
1399 // Do zugzwang verification search
1400 Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
1404 // The null move failed low, which means that we may be faced with
1405 // some kind of threat. If the previous move was reduced, check if
1406 // the move that refuted the null move was somehow connected to the
1407 // move which was reduced. If a connection is found, return a fail
1408 // low score (which will cause the reduced move to fail high in the
1409 // parent node, which will trigger a re-search with full depth).
1410 if (nullValue == value_mated_in(ply + 2))
1413 ss[ply].threatMove = ss[ply + 1].currentMove;
1414 if ( depth < ThreatDepth
1415 && ss[ply - 1].reduction
1416 && connected_moves(pos, ss[ply - 1].currentMove, ss[ply].threatMove))
1421 // Step 9. Internal iterative deepening
1422 if ( depth >= IIDDepthAtNonPVNodes
1423 && ttMove == MOVE_NONE
1425 && ss[ply].eval >= beta - IIDMargin)
1427 search(pos, ss, beta, depth/2, ply, false, threadID);
1428 ttMove = ss[ply].pv[ply];
1429 tte = TT.retrieve(posKey);
1432 // Step 10. Loop through moves
1433 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1435 // Initialize a MovePicker object for the current position
1436 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1439 while ( bestValue < beta
1440 && (move = mp.get_next_move()) != MOVE_NONE
1441 && !TM.thread_should_stop(threadID))
1443 assert(move_is_ok(move));
1445 if (move == excludedMove)
1448 moveIsCheck = pos.move_is_check(move, ci);
1449 singleEvasion = (isCheck && mp.number_of_evasions() == 1);
1450 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1452 // Step 11. Decide the new search depth
1453 ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1455 // Singular extension search. We extend the TT move if its value is much better than
1456 // its siblings. To verify this we do a reduced search on all the other moves but the
1457 // ttMove, if result is lower then ttValue minus a margin then we extend ttMove.
1458 if ( depth >= SingularExtensionDepthAtNonPVNodes
1460 && move == tte->move()
1461 && !excludedMove // Do not allow recursive single-reply search
1463 && is_lower_bound(tte->type())
1464 && tte->depth() >= depth - 3 * OnePly)
1466 Value ttValue = value_from_tt(tte->value(), ply);
1468 if (abs(ttValue) < VALUE_KNOWN_WIN)
1470 Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move);
1472 if (excValue < ttValue - SingularExtensionMargin)
1477 newDepth = depth - OnePly + ext;
1479 // Update current move (this must be done after singular extension search)
1480 movesSearched[moveCount++] = ss[ply].currentMove = move;
1482 // Step 12. Futility pruning
1485 && !captureOrPromotion
1486 && !move_is_castle(move)
1489 // Move count based pruning
1490 if ( moveCount >= futility_move_count(depth)
1491 && ok_to_prune(pos, move, ss[ply].threatMove)
1492 && bestValue > value_mated_in(PLY_MAX))
1495 // Value based pruning
1496 Depth predictedDepth = newDepth - nonpv_reduction(depth, moveCount); // We illogically ignore reduction condition depth >= 3*OnePly
1497 futilityValueScaled = ss[ply].eval + futility_margin(predictedDepth, moveCount)
1498 + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45;
1500 if (futilityValueScaled < beta)
1502 if (futilityValueScaled > bestValue)
1503 bestValue = futilityValueScaled;
1508 // Step 13. Make the move
1509 pos.do_move(move, st, ci, moveIsCheck);
1511 // Step 14. Reduced search
1512 // if the move fails high will be re-searched at full depth.
1513 bool doFullDepthSearch = true;
1515 if ( depth >= 3*OnePly
1517 && !captureOrPromotion
1518 && !move_is_castle(move)
1519 && !move_is_killer(move, ss[ply]))
1521 ss[ply].reduction = nonpv_reduction(depth, moveCount);
1522 if (ss[ply].reduction)
1524 value = -search(pos, ss, -(beta-1), newDepth-ss[ply].reduction, ply+1, true, threadID);
1525 doFullDepthSearch = (value >= beta);
1529 // Step 15. Full depth search
1530 if (doFullDepthSearch)
1532 ss[ply].reduction = Depth(0);
1533 value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID);
1536 // Step 16. Undo move
1537 pos.undo_move(move);
1539 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1541 // Step 17. Check for new best move
1542 if (value > bestValue)
1548 if (value == value_mate_in(ply + 1))
1549 ss[ply].mateKiller = move;
1552 // Step 18. Check for split
1553 if ( TM.active_threads() > 1
1555 && depth >= MinimumSplitDepth
1557 && TM.available_thread_exists(threadID)
1559 && !TM.thread_should_stop(threadID)
1560 && TM.split(pos, ss, ply, NULL, beta, &bestValue,
1561 depth, &moveCount, &mp, threadID, false))
1565 // Step 19. Check for mate and stalemate
1566 // All legal moves have been searched and if there were
1567 // no legal moves, it must be mate or stalemate.
1568 // If one move was excluded return fail low.
1570 return excludedMove ? beta - 1 : (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW);
1572 // Step 20. Update tables
1573 // If the search is not aborted, update the transposition table,
1574 // history counters, and killer moves.
1575 if (AbortSearch || TM.thread_should_stop(threadID))
1578 if (bestValue < beta)
1579 TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1582 TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
1583 move = ss[ply].pv[ply];
1584 TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
1585 if (!pos.move_is_capture_or_promotion(move))
1587 update_history(pos, move, depth, movesSearched, moveCount);
1588 update_killers(move, ss[ply]);
1593 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1599 // qsearch() is the quiescence search function, which is called by the main
1600 // search function when the remaining depth is zero (or, to be more precise,
1601 // less than OnePly).
1603 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta,
1604 Depth depth, int ply, int threadID) {
1606 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1607 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1609 assert(ply >= 0 && ply < PLY_MAX);
1610 assert(threadID >= 0 && threadID < TM.active_threads());
1615 Value staticValue, bestValue, value, futilityBase, futilityValue;
1616 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1617 const TTEntry* tte = NULL;
1619 bool pvNode = (beta - alpha != 1);
1620 Value oldAlpha = alpha;
1622 // Initialize, and make an early exit in case of an aborted search,
1623 // an instant draw, maximum ply reached, etc.
1624 init_node(ss, ply, threadID);
1626 // After init_node() that calls poll()
1627 if (AbortSearch || TM.thread_should_stop(threadID))
1630 if (pos.is_draw() || ply >= PLY_MAX - 1)
1633 // Transposition table lookup. At PV nodes, we don't use the TT for
1634 // pruning, but only for move ordering.
1635 tte = TT.retrieve(pos.get_key());
1636 ttMove = (tte ? tte->move() : MOVE_NONE);
1638 if (!pvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1640 assert(tte->type() != VALUE_TYPE_EVAL);
1642 ss[ply].currentMove = ttMove; // Can be MOVE_NONE
1643 return value_from_tt(tte->value(), ply);
1646 isCheck = pos.is_check();
1648 // Evaluate the position statically
1650 staticValue = -VALUE_INFINITE;
1651 else if (tte && (tte->type() & VALUE_TYPE_EVAL))
1652 staticValue = value_from_tt(tte->value(), ply);
1654 staticValue = evaluate(pos, ei, threadID);
1658 ss[ply].eval = staticValue;
1659 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1662 // Initialize "stand pat score", and return it immediately if it is
1664 bestValue = staticValue;
1666 if (bestValue >= beta)
1668 // Store the score to avoid a future costly evaluation() call
1669 if (!isCheck && !tte && ei.futilityMargin[pos.side_to_move()] == 0)
1670 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EV_LO, Depth(-127*OnePly), MOVE_NONE);
1675 if (bestValue > alpha)
1678 // If we are near beta then try to get a cutoff pushing checks a bit further
1679 bool deepChecks = depth == -OnePly && staticValue >= beta - PawnValueMidgame / 8;
1681 // Initialize a MovePicker object for the current position, and prepare
1682 // to search the moves. Because the depth is <= 0 here, only captures,
1683 // queen promotions and checks (only if depth == 0 or depth == -OnePly
1684 // and we are near beta) will be generated.
1685 MovePicker mp = MovePicker(pos, ttMove, deepChecks ? Depth(0) : depth, H);
1687 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1688 futilityBase = staticValue + FutilityMarginQS + ei.futilityMargin[pos.side_to_move()];
1690 // Loop through the moves until no moves remain or a beta cutoff
1692 while ( alpha < beta
1693 && (move = mp.get_next_move()) != MOVE_NONE)
1695 assert(move_is_ok(move));
1697 moveIsCheck = pos.move_is_check(move, ci);
1699 // Update current move
1701 ss[ply].currentMove = move;
1709 && !move_is_promotion(move)
1710 && !pos.move_is_passed_pawn_push(move))
1712 futilityValue = futilityBase
1713 + pos.endgame_value_of_piece_on(move_to(move))
1714 + (move_is_ep(move) ? PawnValueEndgame : Value(0));
1716 if (futilityValue < alpha)
1718 if (futilityValue > bestValue)
1719 bestValue = futilityValue;
1724 // Detect blocking evasions that are candidate to be pruned
1725 evasionPrunable = isCheck
1726 && bestValue != -VALUE_INFINITE
1727 && !pos.move_is_capture(move)
1728 && pos.type_of_piece_on(move_from(move)) != KING
1729 && !pos.can_castle(pos.side_to_move());
1731 // Don't search moves with negative SEE values
1732 if ( (!isCheck || evasionPrunable)
1735 && !move_is_promotion(move)
1736 && pos.see_sign(move) < 0)
1739 // Make and search the move
1740 pos.do_move(move, st, ci, moveIsCheck);
1741 value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID);
1742 pos.undo_move(move);
1744 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1747 if (value > bestValue)
1758 // All legal moves have been searched. A special case: If we're in check
1759 // and no legal moves were found, it is checkmate.
1760 if (!moveCount && pos.is_check()) // Mate!
1761 return value_mated_in(ply);
1763 // Update transposition table
1764 Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
1765 if (bestValue <= oldAlpha)
1767 // If bestValue isn't changed it means it is still the static evaluation
1768 // of the node, so keep this info to avoid a future evaluation() call.
1769 ValueType type = (bestValue == staticValue && !ei.futilityMargin[pos.side_to_move()] ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER);
1770 TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE);
1772 else if (bestValue >= beta)
1774 move = ss[ply].pv[ply];
1775 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, move);
1777 // Update killers only for good checking moves
1778 if (!pos.move_is_capture_or_promotion(move))
1779 update_killers(move, ss[ply]);
1782 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, d, ss[ply].pv[ply]);
1784 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1790 // sp_search() is used to search from a split point. This function is called
1791 // by each thread working at the split point. It is similar to the normal
1792 // search() function, but simpler. Because we have already probed the hash
1793 // table, done a null move search, and searched the first move before
1794 // splitting, we don't have to repeat all this work in sp_search(). We
1795 // also don't need to store anything to the hash table here: This is taken
1796 // care of after we return from the split point.
1797 // FIXME: We are currently ignoring mateThreat flag here
1799 void sp_search(SplitPoint* sp, int threadID) {
1801 assert(threadID >= 0 && threadID < TM.active_threads());
1802 assert(TM.active_threads() > 1);
1806 Depth ext, newDepth;
1807 Value value, futilityValueScaled;
1808 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
1810 value = -VALUE_INFINITE;
1812 Position pos(*sp->pos);
1814 SearchStack* ss = sp->sstack[threadID];
1815 isCheck = pos.is_check();
1817 // Step 10. Loop through moves
1818 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1819 lock_grab(&(sp->lock));
1821 while ( sp->bestValue < sp->beta
1822 && !TM.thread_should_stop(threadID)
1823 && (move = sp->mp->get_next_move()) != MOVE_NONE)
1825 moveCount = ++sp->moves;
1826 lock_release(&(sp->lock));
1828 assert(move_is_ok(move));
1830 moveIsCheck = pos.move_is_check(move, ci);
1831 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1833 // Step 11. Decide the new search depth
1834 ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous);
1835 newDepth = sp->depth - OnePly + ext;
1837 // Update current move
1838 ss[sp->ply].currentMove = move;
1840 // Step 12. Futility pruning
1843 && !captureOrPromotion
1844 && !move_is_castle(move))
1846 // Move count based pruning
1847 if ( moveCount >= futility_move_count(sp->depth)
1848 && ok_to_prune(pos, move, ss[sp->ply].threatMove)
1849 && sp->bestValue > value_mated_in(PLY_MAX))
1851 lock_grab(&(sp->lock));
1855 // Value based pruning
1856 Depth predictedDepth = newDepth - nonpv_reduction(sp->depth, moveCount);
1857 futilityValueScaled = ss[sp->ply].eval + futility_margin(predictedDepth, moveCount)
1858 + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45;
1860 if (futilityValueScaled < sp->beta)
1862 lock_grab(&(sp->lock));
1864 if (futilityValueScaled > sp->bestValue)
1865 sp->bestValue = futilityValueScaled;
1870 // Step 13. Make the move
1871 pos.do_move(move, st, ci, moveIsCheck);
1873 // Step 14. Reduced search
1874 // if the move fails high will be re-searched at full depth.
1875 bool doFullDepthSearch = true;
1878 && !captureOrPromotion
1879 && !move_is_castle(move)
1880 && !move_is_killer(move, ss[sp->ply]))
1882 ss[sp->ply].reduction = nonpv_reduction(sp->depth, moveCount);
1883 if (ss[sp->ply].reduction)
1885 value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
1886 doFullDepthSearch = (value >= sp->beta && !TM.thread_should_stop(threadID));
1890 // Step 15. Full depth search
1891 if (doFullDepthSearch)
1893 ss[sp->ply].reduction = Depth(0);
1894 value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID);
1897 // Step 16. Undo move
1898 pos.undo_move(move);
1900 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1902 // Step 17. Check for new best move
1903 lock_grab(&(sp->lock));
1905 if (value > sp->bestValue && !TM.thread_should_stop(threadID))
1907 sp->bestValue = value;
1908 if (sp->bestValue >= sp->beta)
1910 sp->stopRequest = true;
1911 sp_update_pv(sp->parentSstack, ss, sp->ply);
1916 /* Here we have the lock still grabbed */
1918 sp->slaves[threadID] = 0;
1921 lock_release(&(sp->lock));
1925 // sp_search_pv() is used to search from a PV split point. This function
1926 // is called by each thread working at the split point. It is similar to
1927 // the normal search_pv() function, but simpler. Because we have already
1928 // probed the hash table and searched the first move before splitting, we
1929 // don't have to repeat all this work in sp_search_pv(). We also don't
1930 // need to store anything to the hash table here: This is taken care of
1931 // after we return from the split point.
1932 // FIXME: We are ignoring mateThreat flag!
1934 void sp_search_pv(SplitPoint* sp, int threadID) {
1936 assert(threadID >= 0 && threadID < TM.active_threads());
1937 assert(TM.active_threads() > 1);
1941 Depth ext, newDepth;
1943 bool moveIsCheck, captureOrPromotion, dangerous;
1945 value = -VALUE_INFINITE;
1947 Position pos(*sp->pos);
1949 SearchStack* ss = sp->sstack[threadID];
1951 // Step 10. Loop through moves
1952 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1953 lock_grab(&(sp->lock));
1955 while ( sp->alpha < sp->beta
1956 && !TM.thread_should_stop(threadID)
1957 && (move = sp->mp->get_next_move()) != MOVE_NONE)
1959 moveCount = ++sp->moves;
1960 lock_release(&(sp->lock));
1962 assert(move_is_ok(move));
1964 moveIsCheck = pos.move_is_check(move, ci);
1965 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1967 // Step 11. Decide the new search depth
1968 ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
1969 newDepth = sp->depth - OnePly + ext;
1971 // Update current move
1972 ss[sp->ply].currentMove = move;
1974 // Step 12. Futility pruning (is omitted in PV nodes)
1976 // Step 13. Make the move
1977 pos.do_move(move, st, ci, moveIsCheck);
1979 // Step 14. Reduced search
1980 // if the move fails high will be re-searched at full depth.
1981 bool doFullDepthSearch = true;
1984 && !captureOrPromotion
1985 && !move_is_castle(move)
1986 && !move_is_killer(move, ss[sp->ply]))
1988 ss[sp->ply].reduction = pv_reduction(sp->depth, moveCount);
1989 if (ss[sp->ply].reduction)
1991 Value localAlpha = sp->alpha;
1992 value = -search(pos, ss, -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
1993 doFullDepthSearch = (value > localAlpha && !TM.thread_should_stop(threadID));
1997 // Step 15. Full depth search
1998 if (doFullDepthSearch)
2000 Value localAlpha = sp->alpha;
2001 ss[sp->ply].reduction = Depth(0);
2002 value = -search(pos, ss, -localAlpha, newDepth, sp->ply+1, true, threadID);
2004 if (value > localAlpha && value < sp->beta && !TM.thread_should_stop(threadID))
2006 // If another thread has failed high then sp->alpha has been increased
2007 // to be higher or equal then beta, if so, avoid to start a PV search.
2008 localAlpha = sp->alpha;
2009 if (localAlpha < sp->beta)
2010 value = -search_pv(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, threadID);
2014 // Step 16. Undo move
2015 pos.undo_move(move);
2017 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
2019 // Step 17. Check for new best move
2020 lock_grab(&(sp->lock));
2022 if (value > sp->bestValue && !TM.thread_should_stop(threadID))
2024 sp->bestValue = value;
2025 if (value > sp->alpha)
2027 // Ask threads to stop before to modify sp->alpha
2028 if (value >= sp->beta)
2029 sp->stopRequest = true;
2033 sp_update_pv(sp->parentSstack, ss, sp->ply);
2034 if (value == value_mate_in(sp->ply + 1))
2035 ss[sp->ply].mateKiller = move;
2040 /* Here we have the lock still grabbed */
2042 sp->slaves[threadID] = 0;
2045 lock_release(&(sp->lock));
2049 // init_node() is called at the beginning of all the search functions
2050 // (search(), search_pv(), qsearch(), and so on) and initializes the
2051 // search stack object corresponding to the current node. Once every
2052 // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
2053 // for user input and checks whether it is time to stop the search.
2055 void init_node(SearchStack ss[], int ply, int threadID) {
2057 assert(ply >= 0 && ply < PLY_MAX);
2058 assert(threadID >= 0 && threadID < TM.active_threads());
2060 TM.incrementNodeCounter(threadID);
2065 if (NodesSincePoll >= NodesBetweenPolls)
2072 ss[ply + 2].initKillers();
2076 // update_pv() is called whenever a search returns a value > alpha.
2077 // It updates the PV in the SearchStack object corresponding to the
2080 void update_pv(SearchStack ss[], int ply) {
2082 assert(ply >= 0 && ply < PLY_MAX);
2086 ss[ply].pv[ply] = ss[ply].currentMove;
2088 for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
2089 ss[ply].pv[p] = ss[ply + 1].pv[p];
2091 ss[ply].pv[p] = MOVE_NONE;
2095 // sp_update_pv() is a variant of update_pv for use at split points. The
2096 // difference between the two functions is that sp_update_pv also updates
2097 // the PV at the parent node.
2099 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply) {
2101 assert(ply >= 0 && ply < PLY_MAX);
2105 ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
2107 for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
2108 ss[ply].pv[p] = pss[ply].pv[p] = ss[ply + 1].pv[p];
2110 ss[ply].pv[p] = pss[ply].pv[p] = MOVE_NONE;
2114 // connected_moves() tests whether two moves are 'connected' in the sense
2115 // that the first move somehow made the second move possible (for instance
2116 // if the moving piece is the same in both moves). The first move is assumed
2117 // to be the move that was made to reach the current position, while the
2118 // second move is assumed to be a move from the current position.
2120 bool connected_moves(const Position& pos, Move m1, Move m2) {
2122 Square f1, t1, f2, t2;
2125 assert(move_is_ok(m1));
2126 assert(move_is_ok(m2));
2128 if (m2 == MOVE_NONE)
2131 // Case 1: The moving piece is the same in both moves
2137 // Case 2: The destination square for m2 was vacated by m1
2143 // Case 3: Moving through the vacated square
2144 if ( piece_is_slider(pos.piece_on(f2))
2145 && bit_is_set(squares_between(f2, t2), f1))
2148 // Case 4: The destination square for m2 is defended by the moving piece in m1
2149 p = pos.piece_on(t1);
2150 if (bit_is_set(pos.attacks_from(p, t1), t2))
2153 // Case 5: Discovered check, checking piece is the piece moved in m1
2154 if ( piece_is_slider(p)
2155 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
2156 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
2158 // discovered_check_candidates() works also if the Position's side to
2159 // move is the opposite of the checking piece.
2160 Color them = opposite_color(pos.side_to_move());
2161 Bitboard dcCandidates = pos.discovered_check_candidates(them);
2163 if (bit_is_set(dcCandidates, f2))
2170 // value_is_mate() checks if the given value is a mate one
2171 // eventually compensated for the ply.
2173 bool value_is_mate(Value value) {
2175 assert(abs(value) <= VALUE_INFINITE);
2177 return value <= value_mated_in(PLY_MAX)
2178 || value >= value_mate_in(PLY_MAX);
2182 // move_is_killer() checks if the given move is among the
2183 // killer moves of that ply.
2185 bool move_is_killer(Move m, const SearchStack& ss) {
2187 const Move* k = ss.killers;
2188 for (int i = 0; i < KILLER_MAX; i++, k++)
2196 // extension() decides whether a move should be searched with normal depth,
2197 // or with extended depth. Certain classes of moves (checking moves, in
2198 // particular) are searched with bigger depth than ordinary moves and in
2199 // any case are marked as 'dangerous'. Note that also if a move is not
2200 // extended, as example because the corresponding UCI option is set to zero,
2201 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
2203 Depth extension(const Position& pos, Move m, bool pvNode, bool captureOrPromotion,
2204 bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous) {
2206 assert(m != MOVE_NONE);
2208 Depth result = Depth(0);
2209 *dangerous = moveIsCheck | singleEvasion | mateThreat;
2214 result += CheckExtension[pvNode];
2217 result += SingleEvasionExtension[pvNode];
2220 result += MateThreatExtension[pvNode];
2223 if (pos.type_of_piece_on(move_from(m)) == PAWN)
2225 Color c = pos.side_to_move();
2226 if (relative_rank(c, move_to(m)) == RANK_7)
2228 result += PawnPushTo7thExtension[pvNode];
2231 if (pos.pawn_is_passed(c, move_to(m)))
2233 result += PassedPawnExtension[pvNode];
2238 if ( captureOrPromotion
2239 && pos.type_of_piece_on(move_to(m)) != PAWN
2240 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
2241 - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))
2242 && !move_is_promotion(m)
2245 result += PawnEndgameExtension[pvNode];
2250 && captureOrPromotion
2251 && pos.type_of_piece_on(move_to(m)) != PAWN
2252 && pos.see_sign(m) >= 0)
2258 return Min(result, OnePly);
2262 // ok_to_do_nullmove() looks at the current position and decides whether
2263 // doing a 'null move' should be allowed. In order to avoid zugzwang
2264 // problems, null moves are not allowed when the side to move has very
2265 // little material left. Currently, the test is a bit too simple: Null
2266 // moves are avoided only when the side to move has only pawns left.
2267 // It's probably a good idea to avoid null moves in at least some more
2268 // complicated endgames, e.g. KQ vs KR. FIXME
2270 bool ok_to_do_nullmove(const Position& pos) {
2272 return pos.non_pawn_material(pos.side_to_move()) != Value(0);
2276 // ok_to_prune() tests whether it is safe to forward prune a move. Only
2277 // non-tactical moves late in the move list close to the leaves are
2278 // candidates for pruning.
2280 bool ok_to_prune(const Position& pos, Move m, Move threat) {
2282 assert(move_is_ok(m));
2283 assert(threat == MOVE_NONE || move_is_ok(threat));
2284 assert(!pos.move_is_check(m));
2285 assert(!pos.move_is_capture_or_promotion(m));
2286 assert(!pos.move_is_passed_pawn_push(m));
2288 Square mfrom, mto, tfrom, tto;
2290 // Prune if there isn't any threat move
2291 if (threat == MOVE_NONE)
2294 mfrom = move_from(m);
2296 tfrom = move_from(threat);
2297 tto = move_to(threat);
2299 // Case 1: Don't prune moves which move the threatened piece
2303 // Case 2: If the threatened piece has value less than or equal to the
2304 // value of the threatening piece, don't prune move which defend it.
2305 if ( pos.move_is_capture(threat)
2306 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
2307 || pos.type_of_piece_on(tfrom) == KING)
2308 && pos.move_attacks_square(m, tto))
2311 // Case 3: If the moving piece in the threatened move is a slider, don't
2312 // prune safe moves which block its ray.
2313 if ( piece_is_slider(pos.piece_on(tfrom))
2314 && bit_is_set(squares_between(tfrom, tto), mto)
2315 && pos.see_sign(m) >= 0)
2322 // ok_to_use_TT() returns true if a transposition table score
2323 // can be used at a given point in search.
2325 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
2327 Value v = value_from_tt(tte->value(), ply);
2329 return ( tte->depth() >= depth
2330 || v >= Max(value_mate_in(PLY_MAX), beta)
2331 || v < Min(value_mated_in(PLY_MAX), beta))
2333 && ( (is_lower_bound(tte->type()) && v >= beta)
2334 || (is_upper_bound(tte->type()) && v < beta));
2338 // refine_eval() returns the transposition table score if
2339 // possible otherwise falls back on static position evaluation.
2341 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
2346 Value v = value_from_tt(tte->value(), ply);
2348 if ( (is_lower_bound(tte->type()) && v >= defaultEval)
2349 || (is_upper_bound(tte->type()) && v < defaultEval))
2356 // update_history() registers a good move that produced a beta-cutoff
2357 // in history and marks as failures all the other moves of that ply.
2359 void update_history(const Position& pos, Move move, Depth depth,
2360 Move movesSearched[], int moveCount) {
2364 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
2366 for (int i = 0; i < moveCount - 1; i++)
2368 m = movesSearched[i];
2372 if (!pos.move_is_capture_or_promotion(m))
2373 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
2378 // update_killers() add a good move that produced a beta-cutoff
2379 // among the killer moves of that ply.
2381 void update_killers(Move m, SearchStack& ss) {
2383 if (m == ss.killers[0])
2386 for (int i = KILLER_MAX - 1; i > 0; i--)
2387 ss.killers[i] = ss.killers[i - 1];
2393 // update_gains() updates the gains table of a non-capture move given
2394 // the static position evaluation before and after the move.
2396 void update_gains(const Position& pos, Move m, Value before, Value after) {
2399 && before != VALUE_NONE
2400 && after != VALUE_NONE
2401 && pos.captured_piece() == NO_PIECE_TYPE
2402 && !move_is_castle(m)
2403 && !move_is_promotion(m))
2404 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
2408 // current_search_time() returns the number of milliseconds which have passed
2409 // since the beginning of the current search.
2411 int current_search_time() {
2413 return get_system_time() - SearchStartTime;
2417 // nps() computes the current nodes/second count.
2421 int t = current_search_time();
2422 return (t > 0 ? int((TM.nodes_searched() * 1000) / t) : 0);
2426 // poll() performs two different functions: It polls for user input, and it
2427 // looks at the time consumed so far and decides if it's time to abort the
2430 void poll(SearchStack ss[], int ply) {
2432 static int lastInfoTime;
2433 int t = current_search_time();
2438 // We are line oriented, don't read single chars
2439 std::string command;
2441 if (!std::getline(std::cin, command))
2444 if (command == "quit")
2447 PonderSearch = false;
2451 else if (command == "stop")
2454 PonderSearch = false;
2456 else if (command == "ponderhit")
2460 // Print search information
2464 else if (lastInfoTime > t)
2465 // HACK: Must be a new search where we searched less than
2466 // NodesBetweenPolls nodes during the first second of search.
2469 else if (t - lastInfoTime >= 1000)
2476 if (dbg_show_hit_rate)
2477 dbg_print_hit_rate();
2479 cout << "info nodes " << TM.nodes_searched() << " nps " << nps()
2480 << " time " << t << " hashfull " << TT.full() << endl;
2482 // We only support current line printing in single thread mode
2483 if (ShowCurrentLine && TM.active_threads() == 1)
2485 cout << "info currline";
2486 for (int p = 0; p < ply; p++)
2487 cout << " " << ss[p].currentMove;
2493 // Should we stop the search?
2497 bool stillAtFirstMove = RootMoveNumber == 1
2498 && !AspirationFailLow
2499 && t > MaxSearchTime + ExtraSearchTime;
2501 bool noMoreTime = t > AbsoluteMaxSearchTime
2502 || stillAtFirstMove;
2504 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2505 || (ExactMaxTime && t >= ExactMaxTime)
2506 || (Iteration >= 3 && MaxNodes && TM.nodes_searched() >= MaxNodes))
2511 // ponderhit() is called when the program is pondering (i.e. thinking while
2512 // it's the opponent's turn to move) in order to let the engine know that
2513 // it correctly predicted the opponent's move.
2517 int t = current_search_time();
2518 PonderSearch = false;
2520 bool stillAtFirstMove = RootMoveNumber == 1
2521 && !AspirationFailLow
2522 && t > MaxSearchTime + ExtraSearchTime;
2524 bool noMoreTime = t > AbsoluteMaxSearchTime
2525 || stillAtFirstMove;
2527 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2532 // init_ss_array() does a fast reset of the first entries of a SearchStack array
2534 void init_ss_array(SearchStack ss[]) {
2536 for (int i = 0; i < 3; i++)
2539 ss[i].initKillers();
2544 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2545 // while the program is pondering. The point is to work around a wrinkle in
2546 // the UCI protocol: When pondering, the engine is not allowed to give a
2547 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2548 // We simply wait here until one of these commands is sent, and return,
2549 // after which the bestmove and pondermove will be printed (in id_loop()).
2551 void wait_for_stop_or_ponderhit() {
2553 std::string command;
2557 if (!std::getline(std::cin, command))
2560 if (command == "quit")
2565 else if (command == "ponderhit" || command == "stop")
2571 // init_thread() is the function which is called when a new thread is
2572 // launched. It simply calls the idle_loop() function with the supplied
2573 // threadID. There are two versions of this function; one for POSIX
2574 // threads and one for Windows threads.
2576 #if !defined(_MSC_VER)
2578 void* init_thread(void *threadID) {
2580 TM.idle_loop(*(int*)threadID, NULL);
2586 DWORD WINAPI init_thread(LPVOID threadID) {
2588 TM.idle_loop(*(int*)threadID, NULL);
2595 /// The ThreadsManager class
2597 // resetNodeCounters(), resetBetaCounters(), searched_nodes() and
2598 // get_beta_counters() are getters/setters for the per thread
2599 // counters used to sort the moves at root.
2601 void ThreadsManager::resetNodeCounters() {
2603 for (int i = 0; i < MAX_THREADS; i++)
2604 threads[i].nodes = 0ULL;
2607 void ThreadsManager::resetBetaCounters() {
2609 for (int i = 0; i < MAX_THREADS; i++)
2610 threads[i].betaCutOffs[WHITE] = threads[i].betaCutOffs[BLACK] = 0ULL;
2613 int64_t ThreadsManager::nodes_searched() const {
2615 int64_t result = 0ULL;
2616 for (int i = 0; i < ActiveThreads; i++)
2617 result += threads[i].nodes;
2622 void ThreadsManager::get_beta_counters(Color us, int64_t& our, int64_t& their) const {
2625 for (int i = 0; i < MAX_THREADS; i++)
2627 our += threads[i].betaCutOffs[us];
2628 their += threads[i].betaCutOffs[opposite_color(us)];
2633 // idle_loop() is where the threads are parked when they have no work to do.
2634 // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint
2635 // object for which the current thread is the master.
2637 void ThreadsManager::idle_loop(int threadID, SplitPoint* waitSp) {
2639 assert(threadID >= 0 && threadID < MAX_THREADS);
2643 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2644 // master should exit as last one.
2645 if (AllThreadsShouldExit)
2648 threads[threadID].state = THREAD_TERMINATED;
2652 // If we are not thinking, wait for a condition to be signaled
2653 // instead of wasting CPU time polling for work.
2654 while (AllThreadsShouldSleep || threadID >= ActiveThreads)
2657 assert(threadID != 0);
2658 threads[threadID].state = THREAD_SLEEPING;
2660 #if !defined(_MSC_VER)
2661 pthread_mutex_lock(&WaitLock);
2662 if (AllThreadsShouldSleep || threadID >= ActiveThreads)
2663 pthread_cond_wait(&WaitCond, &WaitLock);
2664 pthread_mutex_unlock(&WaitLock);
2666 WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2670 // If thread has just woken up, mark it as available
2671 if (threads[threadID].state == THREAD_SLEEPING)
2672 threads[threadID].state = THREAD_AVAILABLE;
2674 // If this thread has been assigned work, launch a search
2675 if (threads[threadID].state == THREAD_WORKISWAITING)
2677 assert(!AllThreadsShouldExit && !AllThreadsShouldSleep);
2679 threads[threadID].state = THREAD_SEARCHING;
2681 if (threads[threadID].splitPoint->pvNode)
2682 sp_search_pv(threads[threadID].splitPoint, threadID);
2684 sp_search(threads[threadID].splitPoint, threadID);
2686 assert(threads[threadID].state == THREAD_SEARCHING);
2688 threads[threadID].state = THREAD_AVAILABLE;
2691 // If this thread is the master of a split point and all threads have
2692 // finished their work at this split point, return from the idle loop.
2693 if (waitSp != NULL && waitSp->cpus == 0)
2695 assert(threads[threadID].state == THREAD_AVAILABLE);
2697 threads[threadID].state = THREAD_SEARCHING;
2704 // init_threads() is called during startup. It launches all helper threads,
2705 // and initializes the split point stack and the global locks and condition
2708 void ThreadsManager::init_threads() {
2713 #if !defined(_MSC_VER)
2714 pthread_t pthread[1];
2717 // Initialize global locks
2718 lock_init(&MPLock, NULL);
2720 // Initialize SplitPointStack locks
2721 for (i = 0; i < MAX_THREADS; i++)
2722 for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
2724 SplitPointStack[i][j].parent = NULL;
2725 lock_init(&(SplitPointStack[i][j].lock), NULL);
2728 #if !defined(_MSC_VER)
2729 pthread_mutex_init(&WaitLock, NULL);
2730 pthread_cond_init(&WaitCond, NULL);
2732 for (i = 0; i < MAX_THREADS; i++)
2733 SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0);
2736 // Will be set just before program exits to properly end the threads
2737 AllThreadsShouldExit = false;
2739 // Threads will be put to sleep as soon as created
2740 AllThreadsShouldSleep = true;
2742 // All threads except the main thread should be initialized to THREAD_AVAILABLE
2744 threads[0].state = THREAD_SEARCHING;
2745 for (i = 1; i < MAX_THREADS; i++)
2746 threads[i].state = THREAD_AVAILABLE;
2748 // Launch the helper threads
2749 for (i = 1; i < MAX_THREADS; i++)
2752 #if !defined(_MSC_VER)
2753 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&i)) == 0);
2756 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID) != NULL);
2761 cout << "Failed to create thread number " << i << endl;
2762 Application::exit_with_failure();
2765 // Wait until the thread has finished launching and is gone to sleep
2766 while (threads[i].state != THREAD_SLEEPING);
2771 // exit_threads() is called when the program exits. It makes all the
2772 // helper threads exit cleanly.
2774 void ThreadsManager::exit_threads() {
2776 ActiveThreads = MAX_THREADS; // HACK
2777 AllThreadsShouldSleep = true; // HACK
2778 wake_sleeping_threads();
2780 // This makes the threads to exit idle_loop()
2781 AllThreadsShouldExit = true;
2783 // Wait for thread termination
2784 for (int i = 1; i < MAX_THREADS; i++)
2785 while (threads[i].state != THREAD_TERMINATED);
2787 // Now we can safely destroy the locks
2788 for (int i = 0; i < MAX_THREADS; i++)
2789 for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
2790 lock_destroy(&(SplitPointStack[i][j].lock));
2794 // thread_should_stop() checks whether the thread should stop its search.
2795 // This can happen if a beta cutoff has occurred in the thread's currently
2796 // active split point, or in some ancestor of the current split point.
2798 bool ThreadsManager::thread_should_stop(int threadID) const {
2800 assert(threadID >= 0 && threadID < ActiveThreads);
2804 for (sp = threads[threadID].splitPoint; sp && !sp->stopRequest; sp = sp->parent);
2809 // thread_is_available() checks whether the thread with threadID "slave" is
2810 // available to help the thread with threadID "master" at a split point. An
2811 // obvious requirement is that "slave" must be idle. With more than two
2812 // threads, this is not by itself sufficient: If "slave" is the master of
2813 // some active split point, it is only available as a slave to the other
2814 // threads which are busy searching the split point at the top of "slave"'s
2815 // split point stack (the "helpful master concept" in YBWC terminology).
2817 bool ThreadsManager::thread_is_available(int slave, int master) const {
2819 assert(slave >= 0 && slave < ActiveThreads);
2820 assert(master >= 0 && master < ActiveThreads);
2821 assert(ActiveThreads > 1);
2823 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2826 // Make a local copy to be sure doesn't change under our feet
2827 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2829 if (localActiveSplitPoints == 0)
2830 // No active split points means that the thread is available as
2831 // a slave for any other thread.
2834 if (ActiveThreads == 2)
2837 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2838 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2839 // could have been set to 0 by another thread leading to an out of bound access.
2840 if (SplitPointStack[slave][localActiveSplitPoints - 1].slaves[master])
2847 // available_thread_exists() tries to find an idle thread which is available as
2848 // a slave for the thread with threadID "master".
2850 bool ThreadsManager::available_thread_exists(int master) const {
2852 assert(master >= 0 && master < ActiveThreads);
2853 assert(ActiveThreads > 1);
2855 for (int i = 0; i < ActiveThreads; i++)
2856 if (thread_is_available(i, master))
2863 // split() does the actual work of distributing the work at a node between
2864 // several threads at PV nodes. If it does not succeed in splitting the
2865 // node (because no idle threads are available, or because we have no unused
2866 // split point objects), the function immediately returns false. If
2867 // splitting is possible, a SplitPoint object is initialized with all the
2868 // data that must be copied to the helper threads (the current position and
2869 // search stack, alpha, beta, the search depth, etc.), and we tell our
2870 // helper threads that they have been assigned work. This will cause them
2871 // to instantly leave their idle loops and call sp_search_pv(). When all
2872 // threads have returned from sp_search_pv (or, equivalently, when
2873 // splitPoint->cpus becomes 0), split() returns true.
2875 bool ThreadsManager::split(const Position& p, SearchStack* sstck, int ply,
2876 Value* alpha, const Value beta, Value* bestValue,
2877 Depth depth, int* moves, MovePicker* mp, int master, bool pvNode) {
2880 assert(sstck != NULL);
2881 assert(ply >= 0 && ply < PLY_MAX);
2882 assert(*bestValue >= -VALUE_INFINITE);
2883 assert( ( pvNode && *bestValue <= *alpha)
2884 || (!pvNode && *bestValue < beta ));
2885 assert(!pvNode || *alpha < beta);
2886 assert(beta <= VALUE_INFINITE);
2887 assert(depth > Depth(0));
2888 assert(master >= 0 && master < ActiveThreads);
2889 assert(ActiveThreads > 1);
2891 SplitPoint* splitPoint;
2895 // If no other thread is available to help us, or if we have too many
2896 // active split points, don't split.
2897 if ( !available_thread_exists(master)
2898 || threads[master].activeSplitPoints >= ACTIVE_SPLIT_POINTS_MAX)
2900 lock_release(&MPLock);
2904 // Pick the next available split point object from the split point stack
2905 splitPoint = &SplitPointStack[master][threads[master].activeSplitPoints];
2907 // Initialize the split point object
2908 splitPoint->parent = threads[master].splitPoint;
2909 splitPoint->stopRequest = false;
2910 splitPoint->ply = ply;
2911 splitPoint->depth = depth;
2912 splitPoint->alpha = pvNode ? *alpha : beta - 1;
2913 splitPoint->beta = beta;
2914 splitPoint->pvNode = pvNode;
2915 splitPoint->bestValue = *bestValue;
2916 splitPoint->master = master;
2917 splitPoint->mp = mp;
2918 splitPoint->moves = *moves;
2919 splitPoint->cpus = 1;
2920 splitPoint->pos = &p;
2921 splitPoint->parentSstack = sstck;
2922 for (int i = 0; i < ActiveThreads; i++)
2923 splitPoint->slaves[i] = 0;
2925 threads[master].splitPoint = splitPoint;
2926 threads[master].activeSplitPoints++;
2928 // If we are here it means we are not available
2929 assert(threads[master].state != THREAD_AVAILABLE);
2931 // Allocate available threads setting state to THREAD_BOOKED
2932 for (int i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint; i++)
2933 if (thread_is_available(i, master))
2935 threads[i].state = THREAD_BOOKED;
2936 threads[i].splitPoint = splitPoint;
2937 splitPoint->slaves[i] = 1;
2941 assert(splitPoint->cpus > 1);
2943 // We can release the lock because slave threads are already booked and master is not available
2944 lock_release(&MPLock);
2946 // Tell the threads that they have work to do. This will make them leave
2947 // their idle loop. But before copy search stack tail for each thread.
2948 for (int i = 0; i < ActiveThreads; i++)
2949 if (i == master || splitPoint->slaves[i])
2951 memcpy(splitPoint->sstack[i] + ply - 1, sstck + ply - 1, 4 * sizeof(SearchStack));
2953 assert(i == master || threads[i].state == THREAD_BOOKED);
2955 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2958 // Everything is set up. The master thread enters the idle loop, from
2959 // which it will instantly launch a search, because its state is
2960 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2961 // idle loop, which means that the main thread will return from the idle
2962 // loop when all threads have finished their work at this split point
2963 // (i.e. when splitPoint->cpus == 0).
2964 idle_loop(master, splitPoint);
2966 // We have returned from the idle loop, which means that all threads are
2967 // finished. Update alpha, beta and bestValue, and return.
2971 *alpha = splitPoint->alpha;
2973 *bestValue = splitPoint->bestValue;
2974 threads[master].activeSplitPoints--;
2975 threads[master].splitPoint = splitPoint->parent;
2977 lock_release(&MPLock);
2982 // wake_sleeping_threads() wakes up all sleeping threads when it is time
2983 // to start a new search from the root.
2985 void ThreadsManager::wake_sleeping_threads() {
2987 assert(AllThreadsShouldSleep);
2988 assert(ActiveThreads > 0);
2990 AllThreadsShouldSleep = false;
2992 if (ActiveThreads == 1)
2995 for (int i = 1; i < ActiveThreads; i++)
2996 assert(threads[i].state == THREAD_SLEEPING);
2998 #if !defined(_MSC_VER)
2999 pthread_mutex_lock(&WaitLock);
3000 pthread_cond_broadcast(&WaitCond);
3001 pthread_mutex_unlock(&WaitLock);
3003 for (int i = 1; i < MAX_THREADS; i++)
3004 SetEvent(SitIdleEvent[i]);
3010 // put_threads_to_sleep() makes all the threads go to sleep just before
3011 // to leave think(), at the end of the search. Threads should have already
3012 // finished the job and should be idle.
3014 void ThreadsManager::put_threads_to_sleep() {
3016 assert(!AllThreadsShouldSleep);
3018 // This makes the threads to go to sleep
3019 AllThreadsShouldSleep = true;
3022 /// The RootMoveList class
3024 // RootMoveList c'tor
3026 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
3028 SearchStack ss[PLY_MAX_PLUS_2];
3029 MoveStack mlist[MaxRootMoves];
3031 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
3033 // Generate all legal moves
3034 MoveStack* last = generate_moves(pos, mlist);
3036 // Add each move to the moves[] array
3037 for (MoveStack* cur = mlist; cur != last; cur++)
3039 bool includeMove = includeAllMoves;
3041 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
3042 includeMove = (searchMoves[k] == cur->move);
3047 // Find a quick score for the move
3049 pos.do_move(cur->move, st);
3050 moves[count].move = cur->move;
3051 moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0);
3052 moves[count].pv[0] = cur->move;
3053 moves[count].pv[1] = MOVE_NONE;
3054 pos.undo_move(cur->move);
3061 // RootMoveList simple methods definitions
3063 void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
3065 moves[moveNum].nodes = nodes;
3066 moves[moveNum].cumulativeNodes += nodes;
3069 void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
3071 moves[moveNum].ourBeta = our;
3072 moves[moveNum].theirBeta = their;
3075 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
3079 for (j = 0; pv[j] != MOVE_NONE; j++)
3080 moves[moveNum].pv[j] = pv[j];
3082 moves[moveNum].pv[j] = MOVE_NONE;
3086 // RootMoveList::sort() sorts the root move list at the beginning of a new
3089 void RootMoveList::sort() {
3091 sort_multipv(count - 1); // Sort all items
3095 // RootMoveList::sort_multipv() sorts the first few moves in the root move
3096 // list by their scores and depths. It is used to order the different PVs
3097 // correctly in MultiPV mode.
3099 void RootMoveList::sort_multipv(int n) {
3103 for (i = 1; i <= n; i++)
3105 RootMove rm = moves[i];
3106 for (j = i; j > 0 && moves[j - 1] < rm; j--)
3107 moves[j] = moves[j - 1];