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];
97 Lock MPLock, WaitLock;
99 #if !defined(_MSC_VER)
100 pthread_cond_t WaitCond;
102 HANDLE SitIdleEvent[MAX_THREADS];
108 // RootMove struct is used for moves at the root at the tree. For each
109 // root move, we store a score, a node count, and a PV (really a refutation
110 // in the case of moves which fail low).
114 RootMove() { nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL; }
116 // RootMove::operator<() is the comparison function used when
117 // sorting the moves. A move m1 is considered to be better
118 // than a move m2 if it has a higher score, or if the moves
119 // have equal score but m1 has the higher node count.
120 bool operator<(const RootMove& m) const {
122 return score != m.score ? score < m.score : theirBeta <= m.theirBeta;
127 int64_t nodes, cumulativeNodes, ourBeta, theirBeta;
128 Move pv[PLY_MAX_PLUS_2];
132 // The RootMoveList class is essentially an array of RootMove objects, with
133 // a handful of methods for accessing the data in the individual moves.
138 RootMoveList(Position& pos, Move searchMoves[]);
140 int move_count() const { return count; }
141 Move get_move(int moveNum) const { return moves[moveNum].move; }
142 Value get_move_score(int moveNum) const { return moves[moveNum].score; }
143 void set_move_score(int moveNum, Value score) { moves[moveNum].score = score; }
144 Move get_move_pv(int moveNum, int i) const { return moves[moveNum].pv[i]; }
145 int64_t get_move_cumulative_nodes(int moveNum) const { return moves[moveNum].cumulativeNodes; }
147 void set_move_nodes(int moveNum, int64_t nodes);
148 void set_beta_counters(int moveNum, int64_t our, int64_t their);
149 void set_move_pv(int moveNum, const Move pv[]);
151 void sort_multipv(int n);
154 static const int MaxRootMoves = 500;
155 RootMove moves[MaxRootMoves];
164 // Maximum depth for razoring
165 const Depth RazorDepth = 4 * OnePly;
167 // Dynamic razoring margin based on depth
168 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * d); }
170 // Step 8. Null move search with verification search
172 // Null move margin. A null move search will not be done if the static
173 // evaluation of the position is more than NullMoveMargin below beta.
174 const Value NullMoveMargin = Value(0x200);
176 // Maximum depth for use of dynamic threat detection when null move fails low
177 const Depth ThreatDepth = 5 * OnePly;
179 // Step 9. Internal iterative deepening
181 // Minimum depth for use of internal iterative deepening
182 const Depth IIDDepthAtPVNodes = 5 * OnePly;
183 const Depth IIDDepthAtNonPVNodes = 8 * OnePly;
185 // Internal iterative deepening margin. At Non-PV nodes
186 // we do an internal iterative deepening
187 // search 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 SingularExtensionDepthAtPVNodes = 6 * OnePly;
199 const Depth SingularExtensionDepthAtNonPVNodes = 8 * OnePly;
201 // If the TT move is at least SingularExtensionMargin better then the
202 // remaining ones we will extend it.
203 const Value SingularExtensionMargin = Value(0x20);
205 // Step 12. Futility pruning
207 // Futility margin for quiescence search
208 const Value FutilityMarginQS = Value(0x80);
210 // Futility lookup tables (initialized at startup) and their getter functions
211 int32_t FutilityMarginsMatrix[14][64]; // [depth][moveNumber]
212 int FutilityMoveCountArray[32]; // [depth]
214 inline Value futility_margin(Depth d, int mn) { return Value(d < 7*OnePly ? FutilityMarginsMatrix[Max(d, 0)][Min(mn, 63)] : 2 * VALUE_INFINITE); }
215 inline int futility_move_count(Depth d) { return d < 16*OnePly ? FutilityMoveCountArray[d] : 512; }
217 // Step 14. Reduced search
219 // Reduction lookup tables (initialized at startup) and their getter functions
220 int8_t PVReductionMatrix[64][64]; // [depth][moveNumber]
221 int8_t NonPVReductionMatrix[64][64]; // [depth][moveNumber]
223 inline Depth pv_reduction(Depth d, int mn) { return (Depth) PVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; }
224 inline Depth nonpv_reduction(Depth d, int mn) { return (Depth) NonPVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; }
226 // Step. Common adjustments
228 // Search depth at iteration 1
229 const Depth InitialDepth = OnePly;
231 // Easy move margin. An easy move candidate must be at least this much
232 // better than the second best move.
233 const Value EasyMoveMargin = Value(0x200);
235 // Last seconds noise filtering (LSN)
236 const bool UseLSNFiltering = true;
237 const int LSNTime = 4000; // In milliseconds
238 const Value LSNValue = value_from_centipawns(200);
239 bool loseOnTime = false;
244 // Iteration counters
247 // Scores and number of times the best move changed for each iteration
248 Value ValueByIteration[PLY_MAX_PLUS_2];
249 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
251 // Search window management
257 // Time managment variables
260 int MaxNodes, MaxDepth;
261 int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
262 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
263 bool AbortSearch, Quit;
264 bool AspirationFailLow;
266 // Show current line?
267 bool ShowCurrentLine;
271 std::ofstream LogFile;
273 // MP related variables
274 Depth MinimumSplitDepth;
275 int MaxThreadsPerSplitPoint;
278 // Node counters, used only by thread[0] but try to keep in different
279 // cache lines (64 bytes each) from the heavy SMP read accessed variables.
281 int NodesBetweenPolls = 30000;
288 Value id_loop(const Position& pos, Move searchMoves[]);
289 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta);
290 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
291 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE);
292 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
293 void sp_search(SplitPoint* sp, int threadID);
294 void sp_search_pv(SplitPoint* sp, int threadID);
295 void init_node(SearchStack ss[], int ply, int threadID);
296 void update_pv(SearchStack ss[], int ply);
297 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply);
298 bool connected_moves(const Position& pos, Move m1, Move m2);
299 bool value_is_mate(Value value);
300 bool move_is_killer(Move m, const SearchStack& ss);
301 Depth extension(const Position&, Move, bool, bool, bool, bool, bool, bool*);
302 bool ok_to_do_nullmove(const Position& pos);
303 bool ok_to_prune(const Position& pos, Move m, Move threat);
304 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
305 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
306 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
307 void update_killers(Move m, SearchStack& ss);
308 void update_gains(const Position& pos, Move move, Value before, Value after);
310 int current_search_time();
312 void poll(SearchStack ss[], int ply);
314 void wait_for_stop_or_ponderhit();
315 void init_ss_array(SearchStack ss[]);
317 #if !defined(_MSC_VER)
318 void *init_thread(void *threadID);
320 DWORD WINAPI init_thread(LPVOID threadID);
330 /// init_threads(), exit_threads() and nodes_searched() are helpers to
331 /// give accessibility to some TM methods from outside of current file.
333 void init_threads() { TM.init_threads(); }
334 void exit_threads() { TM.exit_threads(); }
335 int64_t nodes_searched() { return TM.nodes_searched(); }
338 /// perft() is our utility to verify move generation is bug free. All the legal
339 /// moves up to given depth are generated and counted and the sum returned.
341 int perft(Position& pos, Depth depth)
345 MovePicker mp = MovePicker(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)
360 pos.do_move(move, st, ci, pos.move_is_check(move, ci));
361 sum += perft(pos, depth - OnePly);
368 /// think() is the external interface to Stockfish's search, and is called when
369 /// the program receives the UCI 'go' command. It initializes various
370 /// search-related global variables, and calls root_search(). It returns false
371 /// when a quit command is received during the search.
373 bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
374 int time[], int increment[], int movesToGo, int maxDepth,
375 int maxNodes, int maxTime, Move searchMoves[]) {
377 // Initialize global search variables
378 StopOnPonderhit = AbortSearch = Quit = false;
379 AspirationFailLow = false;
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"))
393 if (get_option_value_string("Book File") != OpeningBook.file_name())
394 OpeningBook.open(get_option_value_string("Book File"));
396 bookMove = OpeningBook.get_move(pos);
397 if (bookMove != MOVE_NONE)
400 wait_for_stop_or_ponderhit();
402 cout << "bestmove " << bookMove << endl;
407 TM.resetNodeCounters();
409 if (button_was_pressed("New Game"))
410 loseOnTime = false; // Reset at the beginning of a new game
412 // Read UCI option values
413 TT.set_size(get_option_value_int("Hash"));
414 if (button_was_pressed("Clear Hash"))
417 bool PonderingEnabled = get_option_value_bool("Ponder");
418 MultiPV = get_option_value_int("MultiPV");
420 CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)"));
421 CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)"));
423 SingleEvasionExtension[1] = Depth(get_option_value_int("Single Evasion Extension (PV nodes)"));
424 SingleEvasionExtension[0] = Depth(get_option_value_int("Single Evasion Extension (non-PV nodes)"));
426 PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)"));
427 PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
429 PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
430 PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
432 PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
433 PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)"));
435 MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
436 MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
438 Chess960 = get_option_value_bool("UCI_Chess960");
439 ShowCurrentLine = get_option_value_bool("UCI_ShowCurrLine");
440 UseLogFile = get_option_value_bool("Use Search Log");
442 LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app);
444 MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly;
445 MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point");
447 read_weights(pos.side_to_move());
449 // Set the number of active threads
450 int newActiveThreads = get_option_value_int("Threads");
451 if (newActiveThreads != TM.active_threads())
453 TM.set_active_threads(newActiveThreads);
454 init_eval(TM.active_threads());
455 // HACK: init_eval() destroys the static castleRightsMask[] array in the
456 // Position class. The below line repairs the damage.
457 Position p(pos.to_fen());
461 // Wake up sleeping threads
462 TM.wake_sleeping_threads();
465 int myTime = time[side_to_move];
466 int myIncrement = increment[side_to_move];
467 if (UseTimeManagement)
469 if (!movesToGo) // Sudden death time control
473 MaxSearchTime = myTime / 30 + myIncrement;
474 AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
476 else // Blitz game without increment
478 MaxSearchTime = myTime / 30;
479 AbsoluteMaxSearchTime = myTime / 8;
482 else // (x moves) / (y minutes)
486 MaxSearchTime = myTime / 2;
487 AbsoluteMaxSearchTime = (myTime > 3000)? (myTime - 500) : ((myTime * 3) / 4);
491 MaxSearchTime = myTime / Min(movesToGo, 20);
492 AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
496 if (PonderingEnabled)
498 MaxSearchTime += MaxSearchTime / 4;
499 MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime);
503 // Set best NodesBetweenPolls interval
505 NodesBetweenPolls = Min(MaxNodes, 30000);
506 else if (myTime && myTime < 1000)
507 NodesBetweenPolls = 1000;
508 else if (myTime && myTime < 5000)
509 NodesBetweenPolls = 5000;
511 NodesBetweenPolls = 30000;
513 // Write information to search log file
515 LogFile << "Searching: " << pos.to_fen() << endl
516 << "infinite: " << infinite
517 << " ponder: " << ponder
518 << " time: " << myTime
519 << " increment: " << myIncrement
520 << " moves to go: " << movesToGo << endl;
522 // LSN filtering. Used only for developing purpose. Disabled by default.
526 // Step 2. If after last move we decided to lose on time, do it now!
527 while (SearchStartTime + myTime + 1000 > get_system_time())
531 // We're ready to start thinking. Call the iterative deepening loop function
532 Value v = id_loop(pos, searchMoves);
536 // Step 1. If this is sudden death game and our position is hopeless,
537 // decide to lose on time.
538 if ( !loseOnTime // If we already lost on time, go to step 3.
548 // Step 3. Now after stepping over the time limit, reset flag for next match.
556 TM.put_threads_to_sleep();
562 /// init_search() is called during startup. It initializes various lookup tables
566 // Init our reduction lookup tables
567 for (int i = 1; i < 64; i++) // i == depth (OnePly = 1)
568 for (int j = 1; j < 64; j++) // j == moveNumber
570 double pvRed = 0.5 + log(double(i)) * log(double(j)) / 6.0;
571 double nonPVRed = 0.5 + log(double(i)) * log(double(j)) / 3.0;
572 PVReductionMatrix[i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0);
573 NonPVReductionMatrix[i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0);
576 // Init futility margins array
577 for (int i = 0; i < 14; i++) // i == depth (OnePly = 2)
578 for (int j = 0; j < 64; j++) // j == moveNumber
580 FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j; // FIXME: test using log instead of BSR
583 // Init futility move count array
584 for (int i = 0; i < 32; i++) // i == depth (OnePly = 2)
585 FutilityMoveCountArray[i] = 3 + (1 << (3 * i / 8));
589 // SearchStack::init() initializes a search stack. Used at the beginning of a
590 // new search from the root.
591 void SearchStack::init(int ply) {
593 pv[ply] = pv[ply + 1] = MOVE_NONE;
594 currentMove = threatMove = MOVE_NONE;
595 reduction = Depth(0);
599 void SearchStack::initKillers() {
601 mateKiller = MOVE_NONE;
602 for (int i = 0; i < KILLER_MAX; i++)
603 killers[i] = MOVE_NONE;
608 // id_loop() is the main iterative deepening loop. It calls root_search
609 // repeatedly with increasing depth until the allocated thinking time has
610 // been consumed, the user stops the search, or the maximum search depth is
613 Value id_loop(const Position& pos, Move searchMoves[]) {
616 SearchStack ss[PLY_MAX_PLUS_2];
618 // searchMoves are verified, copied, scored and sorted
619 RootMoveList rml(p, searchMoves);
621 // Handle special case of searching on a mate/stale position
622 if (rml.move_count() == 0)
625 wait_for_stop_or_ponderhit();
627 return pos.is_check()? -VALUE_MATE : VALUE_DRAW;
630 // Print RootMoveList c'tor startup scoring to the standard output,
631 // so that we print information also for iteration 1.
632 cout << "info depth " << 1 << "\ninfo depth " << 1
633 << " score " << value_to_string(rml.get_move_score(0))
634 << " time " << current_search_time()
635 << " nodes " << TM.nodes_searched()
637 << " pv " << rml.get_move(0) << "\n";
643 ValueByIteration[1] = rml.get_move_score(0);
646 // Is one move significantly better than others after initial scoring ?
647 Move EasyMove = MOVE_NONE;
648 if ( rml.move_count() == 1
649 || rml.get_move_score(0) > rml.get_move_score(1) + EasyMoveMargin)
650 EasyMove = rml.get_move(0);
652 // Iterative deepening loop
653 while (Iteration < PLY_MAX)
655 // Initialize iteration
658 BestMoveChangesByIteration[Iteration] = 0;
662 cout << "info depth " << Iteration << endl;
664 // Calculate dynamic search window based on previous iterations
667 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
669 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
670 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
672 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
673 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
675 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
676 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
680 alpha = - VALUE_INFINITE;
681 beta = VALUE_INFINITE;
684 // Search to the current depth
685 Value value = root_search(p, ss, rml, alpha, beta);
687 // Write PV to transposition table, in case the relevant entries have
688 // been overwritten during the search.
689 TT.insert_pv(p, ss[0].pv);
692 break; // Value cannot be trusted. Break out immediately!
694 //Save info about search result
695 ValueByIteration[Iteration] = value;
697 // Drop the easy move if it differs from the new best move
698 if (ss[0].pv[0] != EasyMove)
699 EasyMove = MOVE_NONE;
701 if (UseTimeManagement)
704 bool stopSearch = false;
706 // Stop search early if there is only a single legal move,
707 // we search up to Iteration 6 anyway to get a proper score.
708 if (Iteration >= 6 && rml.move_count() == 1)
711 // Stop search early when the last two iterations returned a mate score
713 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
714 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
717 // Stop search early if one move seems to be much better than the rest
718 int64_t nodes = TM.nodes_searched();
720 && EasyMove == ss[0].pv[0]
721 && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
722 && current_search_time() > MaxSearchTime / 16)
723 ||( rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100
724 && current_search_time() > MaxSearchTime / 32)))
727 // Add some extra time if the best move has changed during the last two iterations
728 if (Iteration > 5 && Iteration <= 50)
729 ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2)
730 + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3);
732 // Stop search if most of MaxSearchTime is consumed at the end of the
733 // iteration. We probably don't have enough time to search the first
734 // move at the next iteration anyway.
735 if (current_search_time() > ((MaxSearchTime + ExtraSearchTime) * 80) / 128)
743 StopOnPonderhit = true;
747 if (MaxDepth && Iteration >= MaxDepth)
753 // If we are pondering or in infinite search, we shouldn't print the
754 // best move before we are told to do so.
755 if (!AbortSearch && (PonderSearch || InfiniteSearch))
756 wait_for_stop_or_ponderhit();
758 // Print final search statistics
759 cout << "info nodes " << TM.nodes_searched()
761 << " time " << current_search_time()
762 << " hashfull " << TT.full() << endl;
764 // Print the best move and the ponder move to the standard output
765 if (ss[0].pv[0] == MOVE_NONE)
767 ss[0].pv[0] = rml.get_move(0);
768 ss[0].pv[1] = MOVE_NONE;
770 cout << "bestmove " << ss[0].pv[0];
771 if (ss[0].pv[1] != MOVE_NONE)
772 cout << " ponder " << ss[0].pv[1];
779 dbg_print_mean(LogFile);
781 if (dbg_show_hit_rate)
782 dbg_print_hit_rate(LogFile);
784 LogFile << "\nNodes: " << TM.nodes_searched()
785 << "\nNodes/second: " << nps()
786 << "\nBest move: " << move_to_san(p, ss[0].pv[0]);
789 p.do_move(ss[0].pv[0], st);
790 LogFile << "\nPonder move: " << move_to_san(p, ss[0].pv[1]) << endl;
792 return rml.get_move_score(0);
796 // root_search() is the function which searches the root node. It is
797 // similar to search_pv except that it uses a different move ordering
798 // scheme and prints some information to the standard output.
800 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta) {
805 Depth depth, ext, newDepth;
808 int researchCount = 0;
809 bool moveIsCheck, captureOrPromotion, dangerous;
810 Value alpha = oldAlpha;
811 bool isCheck = pos.is_check();
813 // Evaluate the position statically
815 ss[0].eval = !isCheck ? evaluate(pos, ei, 0) : VALUE_NONE;
817 while (1) // Fail low loop
820 // Loop through all the moves in the root move list
821 for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
825 // We failed high, invalidate and skip next moves, leave node-counters
826 // and beta-counters as they are and quickly return, we will try to do
827 // a research at the next iteration with a bigger aspiration window.
828 rml.set_move_score(i, -VALUE_INFINITE);
832 RootMoveNumber = i + 1;
834 // Save the current node count before the move is searched
835 nodes = TM.nodes_searched();
837 // Reset beta cut-off counters
838 TM.resetBetaCounters();
840 // Pick the next root move, and print the move and the move number to
841 // the standard output.
842 move = ss[0].currentMove = rml.get_move(i);
844 if (current_search_time() >= 1000)
845 cout << "info currmove " << move
846 << " currmovenumber " << RootMoveNumber << endl;
848 // Decide search depth for this move
849 moveIsCheck = pos.move_is_check(move);
850 captureOrPromotion = pos.move_is_capture_or_promotion(move);
851 depth = (Iteration - 2) * OnePly + InitialDepth;
852 ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
853 newDepth = depth + ext;
855 value = - VALUE_INFINITE;
857 while (1) // Fail high loop
860 // Make the move, and search it
861 pos.do_move(move, st, ci, moveIsCheck);
863 if (i < MultiPV || value > alpha)
865 // Aspiration window is disabled in multi-pv case
867 alpha = -VALUE_INFINITE;
869 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
873 // Try to reduce non-pv search depth by one ply if move seems not problematic,
874 // if the move fails high will be re-searched at full depth.
875 bool doFullDepthSearch = true;
877 if ( depth >= 3*OnePly // FIXME was newDepth
879 && !captureOrPromotion
880 && !move_is_castle(move))
882 ss[0].reduction = pv_reduction(depth, RootMoveNumber - MultiPV + 1);
885 value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0);
886 doFullDepthSearch = (value > alpha);
890 if (doFullDepthSearch)
892 ss[0].reduction = Depth(0);
893 value = -search(pos, ss, -alpha, newDepth, 1, true, 0);
896 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
902 // Can we exit fail high loop ?
903 if (AbortSearch || value < beta)
906 // We are failing high and going to do a research. It's important to update score
907 // before research in case we run out of time while researching.
908 rml.set_move_score(i, value);
910 TT.extract_pv(pos, ss[0].pv, PLY_MAX);
911 rml.set_move_pv(i, ss[0].pv);
913 // Print search information to the standard output
914 cout << "info depth " << Iteration
915 << " score " << value_to_string(value)
916 << ((value >= beta) ? " lowerbound" :
917 ((value <= alpha)? " upperbound" : ""))
918 << " time " << current_search_time()
919 << " nodes " << TM.nodes_searched()
923 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
924 cout << ss[0].pv[j] << " ";
930 ValueType type = (value >= beta ? VALUE_TYPE_LOWER
931 : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT));
933 LogFile << pretty_pv(pos, current_search_time(), Iteration,
934 TM.nodes_searched(), value, type, ss[0].pv) << endl;
937 // Prepare for a research after a fail high, each time with a wider window
939 beta = Min(beta + AspirationDelta * (1 << researchCount), VALUE_INFINITE);
941 } // End of fail high loop
943 // Finished searching the move. If AbortSearch is true, the search
944 // was aborted because the user interrupted the search or because we
945 // ran out of time. In this case, the return value of the search cannot
946 // be trusted, and we break out of the loop without updating the best
951 // Remember beta-cutoff and searched nodes counts for this move. The
952 // info is used to sort the root moves at the next iteration.
954 TM.get_beta_counters(pos.side_to_move(), our, their);
955 rml.set_beta_counters(i, our, their);
956 rml.set_move_nodes(i, TM.nodes_searched() - nodes);
958 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
960 if (value <= alpha && i >= MultiPV)
961 rml.set_move_score(i, -VALUE_INFINITE);
964 // PV move or new best move!
967 rml.set_move_score(i, value);
969 TT.extract_pv(pos, ss[0].pv, PLY_MAX);
970 rml.set_move_pv(i, ss[0].pv);
974 // We record how often the best move has been changed in each
975 // iteration. This information is used for time managment: When
976 // the best move changes frequently, we allocate some more time.
978 BestMoveChangesByIteration[Iteration]++;
980 // Print search information to the standard output
981 cout << "info depth " << Iteration
982 << " score " << value_to_string(value)
983 << ((value >= beta) ? " lowerbound" :
984 ((value <= alpha)? " upperbound" : ""))
985 << " time " << current_search_time()
986 << " nodes " << TM.nodes_searched()
990 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
991 cout << ss[0].pv[j] << " ";
997 ValueType type = (value >= beta ? VALUE_TYPE_LOWER
998 : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT));
1000 LogFile << pretty_pv(pos, current_search_time(), Iteration,
1001 TM.nodes_searched(), value, type, ss[0].pv) << endl;
1008 rml.sort_multipv(i);
1009 for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
1011 cout << "info multipv " << j + 1
1012 << " score " << value_to_string(rml.get_move_score(j))
1013 << " depth " << ((j <= i)? Iteration : Iteration - 1)
1014 << " time " << current_search_time()
1015 << " nodes " << TM.nodes_searched()
1019 for (int k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
1020 cout << rml.get_move_pv(j, k) << " ";
1024 alpha = rml.get_move_score(Min(i, MultiPV-1));
1026 } // PV move or new best move
1028 assert(alpha >= oldAlpha);
1030 AspirationFailLow = (alpha == oldAlpha);
1032 if (AspirationFailLow && StopOnPonderhit)
1033 StopOnPonderhit = false;
1036 // Can we exit fail low loop ?
1037 if (AbortSearch || alpha > oldAlpha)
1040 // Prepare for a research after a fail low, each time with a wider window
1042 alpha = Max(alpha - AspirationDelta * (1 << researchCount), -VALUE_INFINITE);
1051 // search_pv() is the main search function for PV nodes.
1053 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta,
1054 Depth depth, int ply, int threadID) {
1056 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1057 assert(beta > alpha && beta <= VALUE_INFINITE);
1058 assert(ply >= 0 && ply < PLY_MAX);
1059 assert(threadID >= 0 && threadID < TM.active_threads());
1061 Move movesSearched[256];
1066 Depth ext, newDepth;
1067 Value bestValue, value, oldAlpha;
1068 bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
1069 bool mateThreat = false;
1071 bestValue = value = -VALUE_INFINITE;
1074 return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID);
1076 // Step 1. Initialize node and poll
1077 // Polling can abort search.
1078 init_node(ss, ply, threadID);
1080 // Step 2. Check for aborted search and immediate draw
1081 if (AbortSearch || TM.thread_should_stop(threadID))
1084 if (pos.is_draw() || ply >= PLY_MAX - 1)
1087 // Step 3. Mate distance pruning
1089 alpha = Max(value_mated_in(ply), alpha);
1090 beta = Min(value_mate_in(ply+1), beta);
1094 // Step 4. Transposition table lookup
1095 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1096 // This is to avoid problems in the following areas:
1098 // * Repetition draw detection
1099 // * Fifty move rule detection
1100 // * Searching for a mate
1101 // * Printing of full PV line
1102 tte = TT.retrieve(pos.get_key());
1103 ttMove = (tte ? tte->move() : MOVE_NONE);
1105 // Step 5. Evaluate the position statically
1106 // At PV nodes we do this only to update gain statistics
1107 isCheck = pos.is_check();
1110 ss[ply].eval = evaluate(pos, ei, threadID);
1111 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1114 // Step 6. Razoring (is omitted in PV nodes)
1115 // Step 7. Static null move pruning (is omitted in PV nodes)
1116 // Step 8. Null move search with verification search (is omitted in PV nodes)
1118 // Step 9. Internal iterative deepening
1119 if ( depth >= IIDDepthAtPVNodes
1120 && ttMove == MOVE_NONE)
1122 search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID);
1123 ttMove = ss[ply].pv[ply];
1124 tte = TT.retrieve(pos.get_key());
1127 // Step 10. Loop through moves
1128 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1130 // Initialize a MovePicker object for the current position
1131 mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move()));
1132 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1135 while ( alpha < beta
1136 && (move = mp.get_next_move()) != MOVE_NONE
1137 && !TM.thread_should_stop(threadID))
1139 assert(move_is_ok(move));
1141 singleEvasion = (isCheck && mp.number_of_evasions() == 1);
1142 moveIsCheck = pos.move_is_check(move, ci);
1143 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1145 // Step 11. Decide the new search depth
1146 ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1148 // Singular extension search. We extend the TT move if its value is much better than
1149 // its siblings. To verify this we do a reduced search on all the other moves but the
1150 // ttMove, if result is lower then ttValue minus a margin then we extend ttMove.
1151 if ( depth >= SingularExtensionDepthAtPVNodes
1153 && move == tte->move()
1155 && is_lower_bound(tte->type())
1156 && tte->depth() >= depth - 3 * OnePly)
1158 Value ttValue = value_from_tt(tte->value(), ply);
1160 if (abs(ttValue) < VALUE_KNOWN_WIN)
1162 Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move);
1164 if (excValue < ttValue - SingularExtensionMargin)
1169 newDepth = depth - OnePly + ext;
1171 // Update current move (this must be done after singular extension search)
1172 movesSearched[moveCount++] = ss[ply].currentMove = move;
1174 // Step 12. Futility pruning (is omitted in PV nodes)
1176 // Step 13. Make the move
1177 pos.do_move(move, st, ci, moveIsCheck);
1179 // Step extra. pv search (only in PV nodes)
1180 // The first move in list is the expected PV
1182 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1185 // Step 14. Reduced search
1186 // if the move fails high will be re-searched at full depth.
1187 bool doFullDepthSearch = true;
1189 if ( depth >= 3*OnePly
1191 && !captureOrPromotion
1192 && !move_is_castle(move)
1193 && !move_is_killer(move, ss[ply]))
1195 ss[ply].reduction = pv_reduction(depth, moveCount);
1196 if (ss[ply].reduction)
1198 value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
1199 doFullDepthSearch = (value > alpha);
1203 // Step 15. Full depth search
1204 if (doFullDepthSearch)
1206 ss[ply].reduction = Depth(0);
1207 value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID);
1209 // Step extra. pv search (only in PV nodes)
1210 if (value > alpha && value < beta)
1211 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1215 // Step 16. Undo move
1216 pos.undo_move(move);
1218 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1220 // Step 17. Check for new best move
1221 if (value > bestValue)
1228 if (value == value_mate_in(ply + 1))
1229 ss[ply].mateKiller = move;
1233 // Step 18. Check for split
1234 if ( TM.active_threads() > 1
1236 && depth >= MinimumSplitDepth
1238 && TM.available_thread_exists(threadID)
1240 && !TM.thread_should_stop(threadID)
1241 && TM.split(pos, ss, ply, &alpha, beta, &bestValue,
1242 depth, &moveCount, &mp, threadID, true))
1246 // Step 19. Check for mate and stalemate
1247 // All legal moves have been searched and if there were
1248 // no legal moves, it must be mate or stalemate.
1250 return (isCheck ? value_mated_in(ply) : VALUE_DRAW);
1252 // Step 20. Update tables
1253 // If the search is not aborted, update the transposition table,
1254 // history counters, and killer moves.
1255 if (AbortSearch || TM.thread_should_stop(threadID))
1258 if (bestValue <= oldAlpha)
1259 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1261 else if (bestValue >= beta)
1263 TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
1264 move = ss[ply].pv[ply];
1265 if (!pos.move_is_capture_or_promotion(move))
1267 update_history(pos, move, depth, movesSearched, moveCount);
1268 update_killers(move, ss[ply]);
1270 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
1273 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
1279 // search() is the search function for zero-width nodes.
1281 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth,
1282 int ply, bool allowNullmove, int threadID, Move excludedMove) {
1284 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1285 assert(ply >= 0 && ply < PLY_MAX);
1286 assert(threadID >= 0 && threadID < TM.active_threads());
1288 Move movesSearched[256];
1293 Depth ext, newDepth;
1294 Value bestValue, refinedValue, nullValue, value, futilityValueScaled;
1295 bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
1296 bool mateThreat = false;
1298 refinedValue = bestValue = value = -VALUE_INFINITE;
1301 return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1303 // Step 1. Initialize node and poll
1304 // Polling can abort search.
1305 init_node(ss, ply, threadID);
1307 // Step 2. Check for aborted search and immediate draw
1308 if (AbortSearch || TM.thread_should_stop(threadID))
1311 if (pos.is_draw() || ply >= PLY_MAX - 1)
1314 // Step 3. Mate distance pruning
1315 if (value_mated_in(ply) >= beta)
1318 if (value_mate_in(ply + 1) < beta)
1321 // Step 4. Transposition table lookup
1323 // We don't want the score of a partial search to overwrite a previous full search
1324 // TT value, so we use a different position key in case of an excluded move exists.
1325 Key posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1327 tte = TT.retrieve(posKey);
1328 ttMove = (tte ? tte->move() : MOVE_NONE);
1330 if (tte && ok_to_use_TT(tte, depth, beta, ply))
1332 ss[ply].currentMove = ttMove; // Can be MOVE_NONE
1333 return value_from_tt(tte->value(), ply);
1336 // Step 5. Evaluate the position statically
1337 isCheck = pos.is_check();
1341 if (tte && (tte->type() & VALUE_TYPE_EVAL))
1342 ss[ply].eval = value_from_tt(tte->value(), ply);
1344 ss[ply].eval = evaluate(pos, ei, threadID);
1346 refinedValue = refine_eval(tte, ss[ply].eval, ply); // Enhance accuracy with TT value if possible
1347 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1351 if ( !value_is_mate(beta)
1353 && depth < RazorDepth
1354 && refinedValue < beta - razor_margin(depth)
1355 && ss[ply - 1].currentMove != MOVE_NULL
1356 && ttMove == MOVE_NONE
1357 && !pos.has_pawn_on_7th(pos.side_to_move()))
1359 Value rbeta = beta - razor_margin(depth);
1360 Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID);
1362 return v; //FIXME: Logically should be: return (v + razor_margin(depth));
1365 // Step 7. Static null move pruning
1366 // We're betting that the opponent doesn't have a move that will reduce
1367 // the score by more than fuility_margin(depth) if we do a null move.
1370 && depth < RazorDepth
1371 && refinedValue - futility_margin(depth, 0) >= beta)
1372 return refinedValue - futility_margin(depth, 0);
1374 // Step 8. Null move search with verification search
1375 // When we jump directly to qsearch() we do a null move only if static value is
1376 // at least beta. Otherwise we do a null move if static value is not more than
1377 // NullMoveMargin under beta.
1381 && !value_is_mate(beta)
1382 && ok_to_do_nullmove(pos)
1383 && refinedValue >= beta - (depth >= 4 * OnePly ? NullMoveMargin : 0))
1385 ss[ply].currentMove = MOVE_NULL;
1387 pos.do_null_move(st);
1389 // Null move dynamic reduction based on depth
1390 int R = 3 + (depth >= 5 * OnePly ? depth / 8 : 0);
1392 // Null move dynamic reduction based on value
1393 if (refinedValue - beta > PawnValueMidgame)
1396 nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);
1398 pos.undo_null_move();
1400 if (nullValue >= beta)
1402 if (depth < 6 * OnePly)
1405 // Do zugzwang verification search
1406 Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
1410 // The null move failed low, which means that we may be faced with
1411 // some kind of threat. If the previous move was reduced, check if
1412 // the move that refuted the null move was somehow connected to the
1413 // move which was reduced. If a connection is found, return a fail
1414 // low score (which will cause the reduced move to fail high in the
1415 // parent node, which will trigger a re-search with full depth).
1416 if (nullValue == value_mated_in(ply + 2))
1419 ss[ply].threatMove = ss[ply + 1].currentMove;
1420 if ( depth < ThreatDepth
1421 && ss[ply - 1].reduction
1422 && connected_moves(pos, ss[ply - 1].currentMove, ss[ply].threatMove))
1427 // Step 9. Internal iterative deepening
1428 if ( depth >= IIDDepthAtNonPVNodes
1429 && ttMove == MOVE_NONE
1431 && ss[ply].eval >= beta - IIDMargin)
1433 search(pos, ss, beta, depth/2, ply, false, threadID);
1434 ttMove = ss[ply].pv[ply];
1435 tte = TT.retrieve(posKey);
1438 // Step 10. Loop through moves
1439 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1441 // Initialize a MovePicker object for the current position
1442 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply], beta);
1445 while ( bestValue < beta
1446 && (move = mp.get_next_move()) != MOVE_NONE
1447 && !TM.thread_should_stop(threadID))
1449 assert(move_is_ok(move));
1451 if (move == excludedMove)
1454 moveIsCheck = pos.move_is_check(move, ci);
1455 singleEvasion = (isCheck && mp.number_of_evasions() == 1);
1456 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1458 // Step 11. Decide the new search depth
1459 ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1461 // Singular extension search. We extend the TT move if its value is much better than
1462 // its siblings. To verify this we do a reduced search on all the other moves but the
1463 // ttMove, if result is lower then ttValue minus a margin then we extend ttMove.
1464 if ( depth >= SingularExtensionDepthAtNonPVNodes
1466 && move == tte->move()
1467 && !excludedMove // Do not allow recursive single-reply search
1469 && is_lower_bound(tte->type())
1470 && tte->depth() >= depth - 3 * OnePly)
1472 Value ttValue = value_from_tt(tte->value(), ply);
1474 if (abs(ttValue) < VALUE_KNOWN_WIN)
1476 Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move);
1478 if (excValue < ttValue - SingularExtensionMargin)
1483 newDepth = depth - OnePly + ext;
1485 // Update current move (this must be done after singular extension search)
1486 movesSearched[moveCount++] = ss[ply].currentMove = move;
1488 // Step 12. Futility pruning
1491 && !captureOrPromotion
1492 && !move_is_castle(move)
1495 // Move count based pruning
1496 if ( moveCount >= futility_move_count(depth)
1497 && ok_to_prune(pos, move, ss[ply].threatMove)
1498 && bestValue > value_mated_in(PLY_MAX))
1501 // Value based pruning
1502 Depth predictedDepth = newDepth - nonpv_reduction(depth, moveCount); // We illogically ignore reduction condition depth >= 3*OnePly
1503 futilityValueScaled = ss[ply].eval + futility_margin(predictedDepth, moveCount)
1504 + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45;
1506 if (futilityValueScaled < beta)
1508 if (futilityValueScaled > bestValue)
1509 bestValue = futilityValueScaled;
1514 // Step 13. Make the move
1515 pos.do_move(move, st, ci, moveIsCheck);
1517 // Step 14. Reduced search
1518 // if the move fails high will be re-searched at full depth.
1519 bool doFullDepthSearch = true;
1521 if ( depth >= 3*OnePly
1523 && !captureOrPromotion
1524 && !move_is_castle(move)
1525 && !move_is_killer(move, ss[ply]))
1527 ss[ply].reduction = nonpv_reduction(depth, moveCount);
1528 if (ss[ply].reduction)
1530 value = -search(pos, ss, -(beta-1), newDepth-ss[ply].reduction, ply+1, true, threadID);
1531 doFullDepthSearch = (value >= beta);
1535 // Step 15. Full depth search
1536 if (doFullDepthSearch)
1538 ss[ply].reduction = Depth(0);
1539 value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID);
1542 // Step 16. Undo move
1543 pos.undo_move(move);
1545 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1547 // Step 17. Check for new best move
1548 if (value > bestValue)
1554 if (value == value_mate_in(ply + 1))
1555 ss[ply].mateKiller = move;
1558 // Step 18. Check for split
1559 if ( TM.active_threads() > 1
1561 && depth >= MinimumSplitDepth
1563 && TM.available_thread_exists(threadID)
1565 && !TM.thread_should_stop(threadID)
1566 && TM.split(pos, ss, ply, NULL, beta, &bestValue,
1567 depth, &moveCount, &mp, threadID, false))
1571 // Step 19. Check for mate and stalemate
1572 // All legal moves have been searched and if there were
1573 // no legal moves, it must be mate or stalemate.
1574 // If one move was excluded return fail low.
1576 return excludedMove ? beta - 1 : (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW);
1578 // Step 20. Update tables
1579 // If the search is not aborted, update the transposition table,
1580 // history counters, and killer moves.
1581 if (AbortSearch || TM.thread_should_stop(threadID))
1584 if (bestValue < beta)
1585 TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1588 TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
1589 move = ss[ply].pv[ply];
1590 TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
1591 if (!pos.move_is_capture_or_promotion(move))
1593 update_history(pos, move, depth, movesSearched, moveCount);
1594 update_killers(move, ss[ply]);
1599 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1605 // qsearch() is the quiescence search function, which is called by the main
1606 // search function when the remaining depth is zero (or, to be more precise,
1607 // less than OnePly).
1609 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta,
1610 Depth depth, int ply, int threadID) {
1612 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1613 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1615 assert(ply >= 0 && ply < PLY_MAX);
1616 assert(threadID >= 0 && threadID < TM.active_threads());
1621 Value staticValue, bestValue, value, futilityBase, futilityValue;
1622 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1623 const TTEntry* tte = NULL;
1625 bool pvNode = (beta - alpha != 1);
1626 Value oldAlpha = alpha;
1628 // Initialize, and make an early exit in case of an aborted search,
1629 // an instant draw, maximum ply reached, etc.
1630 init_node(ss, ply, threadID);
1632 // After init_node() that calls poll()
1633 if (AbortSearch || TM.thread_should_stop(threadID))
1636 if (pos.is_draw() || ply >= PLY_MAX - 1)
1639 // Transposition table lookup. At PV nodes, we don't use the TT for
1640 // pruning, but only for move ordering.
1641 tte = TT.retrieve(pos.get_key());
1642 ttMove = (tte ? tte->move() : MOVE_NONE);
1644 if (!pvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1646 assert(tte->type() != VALUE_TYPE_EVAL);
1648 ss[ply].currentMove = ttMove; // Can be MOVE_NONE
1649 return value_from_tt(tte->value(), ply);
1652 isCheck = pos.is_check();
1654 // Evaluate the position statically
1656 staticValue = -VALUE_INFINITE;
1657 else if (tte && (tte->type() & VALUE_TYPE_EVAL))
1658 staticValue = value_from_tt(tte->value(), ply);
1660 staticValue = evaluate(pos, ei, threadID);
1664 ss[ply].eval = staticValue;
1665 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1668 // Initialize "stand pat score", and return it immediately if it is
1670 bestValue = staticValue;
1672 if (bestValue >= beta)
1674 // Store the score to avoid a future costly evaluation() call
1675 if (!isCheck && !tte && ei.futilityMargin[pos.side_to_move()] == 0)
1676 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EV_LO, Depth(-127*OnePly), MOVE_NONE);
1681 if (bestValue > alpha)
1684 // If we are near beta then try to get a cutoff pushing checks a bit further
1685 bool deepChecks = depth == -OnePly && staticValue >= beta - PawnValueMidgame / 8;
1687 // Initialize a MovePicker object for the current position, and prepare
1688 // to search the moves. Because the depth is <= 0 here, only captures,
1689 // queen promotions and checks (only if depth == 0 or depth == -OnePly
1690 // and we are near beta) will be generated.
1691 MovePicker mp = MovePicker(pos, ttMove, deepChecks ? Depth(0) : depth, H);
1693 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1694 futilityBase = staticValue + FutilityMarginQS + ei.futilityMargin[pos.side_to_move()];
1696 // Loop through the moves until no moves remain or a beta cutoff
1698 while ( alpha < beta
1699 && (move = mp.get_next_move()) != MOVE_NONE)
1701 assert(move_is_ok(move));
1703 moveIsCheck = pos.move_is_check(move, ci);
1705 // Update current move
1707 ss[ply].currentMove = move;
1715 && !move_is_promotion(move)
1716 && !pos.move_is_passed_pawn_push(move))
1718 futilityValue = futilityBase
1719 + pos.endgame_value_of_piece_on(move_to(move))
1720 + (move_is_ep(move) ? PawnValueEndgame : Value(0));
1722 if (futilityValue < alpha)
1724 if (futilityValue > bestValue)
1725 bestValue = futilityValue;
1730 // Detect blocking evasions that are candidate to be pruned
1731 evasionPrunable = isCheck
1732 && bestValue != -VALUE_INFINITE
1733 && !pos.move_is_capture(move)
1734 && pos.type_of_piece_on(move_from(move)) != KING
1735 && !pos.can_castle(pos.side_to_move());
1737 // Don't search moves with negative SEE values
1738 if ( (!isCheck || evasionPrunable)
1741 && !move_is_promotion(move)
1742 && pos.see_sign(move) < 0)
1745 // Make and search the move
1746 pos.do_move(move, st, ci, moveIsCheck);
1747 value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID);
1748 pos.undo_move(move);
1750 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1753 if (value > bestValue)
1764 // All legal moves have been searched. A special case: If we're in check
1765 // and no legal moves were found, it is checkmate.
1766 if (!moveCount && pos.is_check()) // Mate!
1767 return value_mated_in(ply);
1769 // Update transposition table
1770 Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
1771 if (bestValue <= oldAlpha)
1773 // If bestValue isn't changed it means it is still the static evaluation
1774 // of the node, so keep this info to avoid a future evaluation() call.
1775 ValueType type = (bestValue == staticValue && !ei.futilityMargin[pos.side_to_move()] ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER);
1776 TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE);
1778 else if (bestValue >= beta)
1780 move = ss[ply].pv[ply];
1781 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, move);
1783 // Update killers only for good checking moves
1784 if (!pos.move_is_capture_or_promotion(move))
1785 update_killers(move, ss[ply]);
1788 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, d, ss[ply].pv[ply]);
1790 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1796 // sp_search() is used to search from a split point. This function is called
1797 // by each thread working at the split point. It is similar to the normal
1798 // search() function, but simpler. Because we have already probed the hash
1799 // table, done a null move search, and searched the first move before
1800 // splitting, we don't have to repeat all this work in sp_search(). We
1801 // also don't need to store anything to the hash table here: This is taken
1802 // care of after we return from the split point.
1803 // FIXME: We are currently ignoring mateThreat flag here
1805 void sp_search(SplitPoint* sp, int threadID) {
1807 assert(threadID >= 0 && threadID < TM.active_threads());
1808 assert(TM.active_threads() > 1);
1812 Depth ext, newDepth;
1813 Value value, futilityValueScaled;
1814 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
1816 value = -VALUE_INFINITE;
1818 Position pos(*sp->pos);
1820 SearchStack* ss = sp->sstack[threadID];
1821 isCheck = pos.is_check();
1823 // Step 10. Loop through moves
1824 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1825 lock_grab(&(sp->lock));
1827 while ( sp->bestValue < sp->beta
1828 && !TM.thread_should_stop(threadID)
1829 && (move = sp->mp->get_next_move()) != MOVE_NONE)
1831 moveCount = ++sp->moves;
1832 lock_release(&(sp->lock));
1834 assert(move_is_ok(move));
1836 moveIsCheck = pos.move_is_check(move, ci);
1837 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1839 // Step 11. Decide the new search depth
1840 ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous);
1841 newDepth = sp->depth - OnePly + ext;
1843 // Update current move
1844 ss[sp->ply].currentMove = move;
1846 // Step 12. Futility pruning
1849 && !captureOrPromotion
1850 && !move_is_castle(move))
1852 // Move count based pruning
1853 if ( moveCount >= futility_move_count(sp->depth)
1854 && ok_to_prune(pos, move, ss[sp->ply].threatMove)
1855 && sp->bestValue > value_mated_in(PLY_MAX))
1857 lock_grab(&(sp->lock));
1861 // Value based pruning
1862 Depth predictedDepth = newDepth - nonpv_reduction(sp->depth, moveCount);
1863 futilityValueScaled = ss[sp->ply].eval + futility_margin(predictedDepth, moveCount)
1864 + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45;
1866 if (futilityValueScaled < sp->beta)
1868 lock_grab(&(sp->lock));
1870 if (futilityValueScaled > sp->bestValue)
1871 sp->bestValue = futilityValueScaled;
1876 // Step 13. Make the move
1877 pos.do_move(move, st, ci, moveIsCheck);
1879 // Step 14. Reduced search
1880 // if the move fails high will be re-searched at full depth.
1881 bool doFullDepthSearch = true;
1884 && !captureOrPromotion
1885 && !move_is_castle(move)
1886 && !move_is_killer(move, ss[sp->ply]))
1888 ss[sp->ply].reduction = nonpv_reduction(sp->depth, moveCount);
1889 if (ss[sp->ply].reduction)
1891 value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
1892 doFullDepthSearch = (value >= sp->beta && !TM.thread_should_stop(threadID));
1896 // Step 15. Full depth search
1897 if (doFullDepthSearch)
1899 ss[sp->ply].reduction = Depth(0);
1900 value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID);
1903 // Step 16. Undo move
1904 pos.undo_move(move);
1906 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1908 // Step 17. Check for new best move
1909 lock_grab(&(sp->lock));
1911 if (value > sp->bestValue && !TM.thread_should_stop(threadID))
1913 sp->bestValue = value;
1914 if (sp->bestValue >= sp->beta)
1916 sp->stopRequest = true;
1917 sp_update_pv(sp->parentSstack, ss, sp->ply);
1922 /* Here we have the lock still grabbed */
1924 sp->slaves[threadID] = 0;
1927 lock_release(&(sp->lock));
1931 // sp_search_pv() is used to search from a PV split point. This function
1932 // is called by each thread working at the split point. It is similar to
1933 // the normal search_pv() function, but simpler. Because we have already
1934 // probed the hash table and searched the first move before splitting, we
1935 // don't have to repeat all this work in sp_search_pv(). We also don't
1936 // need to store anything to the hash table here: This is taken care of
1937 // after we return from the split point.
1938 // FIXME: We are ignoring mateThreat flag!
1940 void sp_search_pv(SplitPoint* sp, int threadID) {
1942 assert(threadID >= 0 && threadID < TM.active_threads());
1943 assert(TM.active_threads() > 1);
1947 Depth ext, newDepth;
1949 bool moveIsCheck, captureOrPromotion, dangerous;
1951 value = -VALUE_INFINITE;
1953 Position pos(*sp->pos);
1955 SearchStack* ss = sp->sstack[threadID];
1957 // Step 10. Loop through moves
1958 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1959 lock_grab(&(sp->lock));
1961 while ( sp->alpha < sp->beta
1962 && !TM.thread_should_stop(threadID)
1963 && (move = sp->mp->get_next_move()) != MOVE_NONE)
1965 moveCount = ++sp->moves;
1966 lock_release(&(sp->lock));
1968 assert(move_is_ok(move));
1970 moveIsCheck = pos.move_is_check(move, ci);
1971 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1973 // Step 11. Decide the new search depth
1974 ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
1975 newDepth = sp->depth - OnePly + ext;
1977 // Update current move
1978 ss[sp->ply].currentMove = move;
1980 // Step 12. Futility pruning (is omitted in PV nodes)
1982 // Step 13. Make the move
1983 pos.do_move(move, st, ci, moveIsCheck);
1985 // Step 14. Reduced search
1986 // if the move fails high will be re-searched at full depth.
1987 bool doFullDepthSearch = true;
1990 && !captureOrPromotion
1991 && !move_is_castle(move)
1992 && !move_is_killer(move, ss[sp->ply]))
1994 ss[sp->ply].reduction = pv_reduction(sp->depth, moveCount);
1995 if (ss[sp->ply].reduction)
1997 Value localAlpha = sp->alpha;
1998 value = -search(pos, ss, -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
1999 doFullDepthSearch = (value > localAlpha && !TM.thread_should_stop(threadID));
2003 // Step 15. Full depth search
2004 if (doFullDepthSearch)
2006 Value localAlpha = sp->alpha;
2007 ss[sp->ply].reduction = Depth(0);
2008 value = -search(pos, ss, -localAlpha, newDepth, sp->ply+1, true, threadID);
2010 if (value > localAlpha && value < sp->beta && !TM.thread_should_stop(threadID))
2012 // If another thread has failed high then sp->alpha has been increased
2013 // to be higher or equal then beta, if so, avoid to start a PV search.
2014 localAlpha = sp->alpha;
2015 if (localAlpha < sp->beta)
2016 value = -search_pv(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, threadID);
2020 // Step 16. Undo move
2021 pos.undo_move(move);
2023 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
2025 // Step 17. Check for new best move
2026 lock_grab(&(sp->lock));
2028 if (value > sp->bestValue && !TM.thread_should_stop(threadID))
2030 sp->bestValue = value;
2031 if (value > sp->alpha)
2033 // Ask threads to stop before to modify sp->alpha
2034 if (value >= sp->beta)
2035 sp->stopRequest = true;
2039 sp_update_pv(sp->parentSstack, ss, sp->ply);
2040 if (value == value_mate_in(sp->ply + 1))
2041 ss[sp->ply].mateKiller = move;
2046 /* Here we have the lock still grabbed */
2048 sp->slaves[threadID] = 0;
2051 lock_release(&(sp->lock));
2055 // init_node() is called at the beginning of all the search functions
2056 // (search(), search_pv(), qsearch(), and so on) and initializes the
2057 // search stack object corresponding to the current node. Once every
2058 // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
2059 // for user input and checks whether it is time to stop the search.
2061 void init_node(SearchStack ss[], int ply, int threadID) {
2063 assert(ply >= 0 && ply < PLY_MAX);
2064 assert(threadID >= 0 && threadID < TM.active_threads());
2066 TM.incrementNodeCounter(threadID);
2071 if (NodesSincePoll >= NodesBetweenPolls)
2078 ss[ply + 2].initKillers();
2082 // update_pv() is called whenever a search returns a value > alpha.
2083 // It updates the PV in the SearchStack object corresponding to the
2086 void update_pv(SearchStack ss[], int ply) {
2088 assert(ply >= 0 && ply < PLY_MAX);
2092 ss[ply].pv[ply] = ss[ply].currentMove;
2094 for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
2095 ss[ply].pv[p] = ss[ply + 1].pv[p];
2097 ss[ply].pv[p] = MOVE_NONE;
2101 // sp_update_pv() is a variant of update_pv for use at split points. The
2102 // difference between the two functions is that sp_update_pv also updates
2103 // the PV at the parent node.
2105 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply) {
2107 assert(ply >= 0 && ply < PLY_MAX);
2111 ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
2113 for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
2114 ss[ply].pv[p] = pss[ply].pv[p] = ss[ply + 1].pv[p];
2116 ss[ply].pv[p] = pss[ply].pv[p] = MOVE_NONE;
2120 // connected_moves() tests whether two moves are 'connected' in the sense
2121 // that the first move somehow made the second move possible (for instance
2122 // if the moving piece is the same in both moves). The first move is assumed
2123 // to be the move that was made to reach the current position, while the
2124 // second move is assumed to be a move from the current position.
2126 bool connected_moves(const Position& pos, Move m1, Move m2) {
2128 Square f1, t1, f2, t2;
2131 assert(move_is_ok(m1));
2132 assert(move_is_ok(m2));
2134 if (m2 == MOVE_NONE)
2137 // Case 1: The moving piece is the same in both moves
2143 // Case 2: The destination square for m2 was vacated by m1
2149 // Case 3: Moving through the vacated square
2150 if ( piece_is_slider(pos.piece_on(f2))
2151 && bit_is_set(squares_between(f2, t2), f1))
2154 // Case 4: The destination square for m2 is defended by the moving piece in m1
2155 p = pos.piece_on(t1);
2156 if (bit_is_set(pos.attacks_from(p, t1), t2))
2159 // Case 5: Discovered check, checking piece is the piece moved in m1
2160 if ( piece_is_slider(p)
2161 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
2162 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
2164 // discovered_check_candidates() works also if the Position's side to
2165 // move is the opposite of the checking piece.
2166 Color them = opposite_color(pos.side_to_move());
2167 Bitboard dcCandidates = pos.discovered_check_candidates(them);
2169 if (bit_is_set(dcCandidates, f2))
2176 // value_is_mate() checks if the given value is a mate one
2177 // eventually compensated for the ply.
2179 bool value_is_mate(Value value) {
2181 assert(abs(value) <= VALUE_INFINITE);
2183 return value <= value_mated_in(PLY_MAX)
2184 || value >= value_mate_in(PLY_MAX);
2188 // move_is_killer() checks if the given move is among the
2189 // killer moves of that ply.
2191 bool move_is_killer(Move m, const SearchStack& ss) {
2193 const Move* k = ss.killers;
2194 for (int i = 0; i < KILLER_MAX; i++, k++)
2202 // extension() decides whether a move should be searched with normal depth,
2203 // or with extended depth. Certain classes of moves (checking moves, in
2204 // particular) are searched with bigger depth than ordinary moves and in
2205 // any case are marked as 'dangerous'. Note that also if a move is not
2206 // extended, as example because the corresponding UCI option is set to zero,
2207 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
2209 Depth extension(const Position& pos, Move m, bool pvNode, bool captureOrPromotion,
2210 bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous) {
2212 assert(m != MOVE_NONE);
2214 Depth result = Depth(0);
2215 *dangerous = moveIsCheck | singleEvasion | mateThreat;
2220 result += CheckExtension[pvNode];
2223 result += SingleEvasionExtension[pvNode];
2226 result += MateThreatExtension[pvNode];
2229 if (pos.type_of_piece_on(move_from(m)) == PAWN)
2231 Color c = pos.side_to_move();
2232 if (relative_rank(c, move_to(m)) == RANK_7)
2234 result += PawnPushTo7thExtension[pvNode];
2237 if (pos.pawn_is_passed(c, move_to(m)))
2239 result += PassedPawnExtension[pvNode];
2244 if ( captureOrPromotion
2245 && pos.type_of_piece_on(move_to(m)) != PAWN
2246 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
2247 - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))
2248 && !move_is_promotion(m)
2251 result += PawnEndgameExtension[pvNode];
2256 && captureOrPromotion
2257 && pos.type_of_piece_on(move_to(m)) != PAWN
2258 && pos.see_sign(m) >= 0)
2264 return Min(result, OnePly);
2268 // ok_to_do_nullmove() looks at the current position and decides whether
2269 // doing a 'null move' should be allowed. In order to avoid zugzwang
2270 // problems, null moves are not allowed when the side to move has very
2271 // little material left. Currently, the test is a bit too simple: Null
2272 // moves are avoided only when the side to move has only pawns left.
2273 // It's probably a good idea to avoid null moves in at least some more
2274 // complicated endgames, e.g. KQ vs KR. FIXME
2276 bool ok_to_do_nullmove(const Position& pos) {
2278 return pos.non_pawn_material(pos.side_to_move()) != Value(0);
2282 // ok_to_prune() tests whether it is safe to forward prune a move. Only
2283 // non-tactical moves late in the move list close to the leaves are
2284 // candidates for pruning.
2286 bool ok_to_prune(const Position& pos, Move m, Move threat) {
2288 assert(move_is_ok(m));
2289 assert(threat == MOVE_NONE || move_is_ok(threat));
2290 assert(!pos.move_is_check(m));
2291 assert(!pos.move_is_capture_or_promotion(m));
2292 assert(!pos.move_is_passed_pawn_push(m));
2294 Square mfrom, mto, tfrom, tto;
2296 // Prune if there isn't any threat move
2297 if (threat == MOVE_NONE)
2300 mfrom = move_from(m);
2302 tfrom = move_from(threat);
2303 tto = move_to(threat);
2305 // Case 1: Don't prune moves which move the threatened piece
2309 // Case 2: If the threatened piece has value less than or equal to the
2310 // value of the threatening piece, don't prune move which defend it.
2311 if ( pos.move_is_capture(threat)
2312 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
2313 || pos.type_of_piece_on(tfrom) == KING)
2314 && pos.move_attacks_square(m, tto))
2317 // Case 3: If the moving piece in the threatened move is a slider, don't
2318 // prune safe moves which block its ray.
2319 if ( piece_is_slider(pos.piece_on(tfrom))
2320 && bit_is_set(squares_between(tfrom, tto), mto)
2321 && pos.see_sign(m) >= 0)
2328 // ok_to_use_TT() returns true if a transposition table score
2329 // can be used at a given point in search.
2331 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
2333 Value v = value_from_tt(tte->value(), ply);
2335 return ( tte->depth() >= depth
2336 || v >= Max(value_mate_in(PLY_MAX), beta)
2337 || v < Min(value_mated_in(PLY_MAX), beta))
2339 && ( (is_lower_bound(tte->type()) && v >= beta)
2340 || (is_upper_bound(tte->type()) && v < beta));
2344 // refine_eval() returns the transposition table score if
2345 // possible otherwise falls back on static position evaluation.
2347 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
2352 Value v = value_from_tt(tte->value(), ply);
2354 if ( (is_lower_bound(tte->type()) && v >= defaultEval)
2355 || (is_upper_bound(tte->type()) && v < defaultEval))
2362 // update_history() registers a good move that produced a beta-cutoff
2363 // in history and marks as failures all the other moves of that ply.
2365 void update_history(const Position& pos, Move move, Depth depth,
2366 Move movesSearched[], int moveCount) {
2370 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
2372 for (int i = 0; i < moveCount - 1; i++)
2374 m = movesSearched[i];
2378 if (!pos.move_is_capture_or_promotion(m))
2379 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
2384 // update_killers() add a good move that produced a beta-cutoff
2385 // among the killer moves of that ply.
2387 void update_killers(Move m, SearchStack& ss) {
2389 if (m == ss.killers[0])
2392 for (int i = KILLER_MAX - 1; i > 0; i--)
2393 ss.killers[i] = ss.killers[i - 1];
2399 // update_gains() updates the gains table of a non-capture move given
2400 // the static position evaluation before and after the move.
2402 void update_gains(const Position& pos, Move m, Value before, Value after) {
2405 && before != VALUE_NONE
2406 && after != VALUE_NONE
2407 && pos.captured_piece() == NO_PIECE_TYPE
2408 && !move_is_castle(m)
2409 && !move_is_promotion(m))
2410 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
2414 // current_search_time() returns the number of milliseconds which have passed
2415 // since the beginning of the current search.
2417 int current_search_time() {
2419 return get_system_time() - SearchStartTime;
2423 // nps() computes the current nodes/second count.
2427 int t = current_search_time();
2428 return (t > 0 ? int((TM.nodes_searched() * 1000) / t) : 0);
2432 // poll() performs two different functions: It polls for user input, and it
2433 // looks at the time consumed so far and decides if it's time to abort the
2436 void poll(SearchStack ss[], int ply) {
2438 static int lastInfoTime;
2439 int t = current_search_time();
2444 // We are line oriented, don't read single chars
2445 std::string command;
2447 if (!std::getline(std::cin, command))
2450 if (command == "quit")
2453 PonderSearch = false;
2457 else if (command == "stop")
2460 PonderSearch = false;
2462 else if (command == "ponderhit")
2466 // Print search information
2470 else if (lastInfoTime > t)
2471 // HACK: Must be a new search where we searched less than
2472 // NodesBetweenPolls nodes during the first second of search.
2475 else if (t - lastInfoTime >= 1000)
2482 if (dbg_show_hit_rate)
2483 dbg_print_hit_rate();
2485 cout << "info nodes " << TM.nodes_searched() << " nps " << nps()
2486 << " time " << t << " hashfull " << TT.full() << endl;
2488 // We only support current line printing in single thread mode
2489 if (ShowCurrentLine && TM.active_threads() == 1)
2491 cout << "info currline";
2492 for (int p = 0; p < ply; p++)
2493 cout << " " << ss[p].currentMove;
2499 // Should we stop the search?
2503 bool stillAtFirstMove = RootMoveNumber == 1
2504 && !AspirationFailLow
2505 && t > MaxSearchTime + ExtraSearchTime;
2507 bool noMoreTime = t > AbsoluteMaxSearchTime
2508 || stillAtFirstMove;
2510 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2511 || (ExactMaxTime && t >= ExactMaxTime)
2512 || (Iteration >= 3 && MaxNodes && TM.nodes_searched() >= MaxNodes))
2517 // ponderhit() is called when the program is pondering (i.e. thinking while
2518 // it's the opponent's turn to move) in order to let the engine know that
2519 // it correctly predicted the opponent's move.
2523 int t = current_search_time();
2524 PonderSearch = false;
2526 bool stillAtFirstMove = RootMoveNumber == 1
2527 && !AspirationFailLow
2528 && t > MaxSearchTime + ExtraSearchTime;
2530 bool noMoreTime = t > AbsoluteMaxSearchTime
2531 || stillAtFirstMove;
2533 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2538 // init_ss_array() does a fast reset of the first entries of a SearchStack array
2540 void init_ss_array(SearchStack ss[]) {
2542 for (int i = 0; i < 3; i++)
2545 ss[i].initKillers();
2550 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2551 // while the program is pondering. The point is to work around a wrinkle in
2552 // the UCI protocol: When pondering, the engine is not allowed to give a
2553 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2554 // We simply wait here until one of these commands is sent, and return,
2555 // after which the bestmove and pondermove will be printed (in id_loop()).
2557 void wait_for_stop_or_ponderhit() {
2559 std::string command;
2563 if (!std::getline(std::cin, command))
2566 if (command == "quit")
2571 else if (command == "ponderhit" || command == "stop")
2577 // init_thread() is the function which is called when a new thread is
2578 // launched. It simply calls the idle_loop() function with the supplied
2579 // threadID. There are two versions of this function; one for POSIX
2580 // threads and one for Windows threads.
2582 #if !defined(_MSC_VER)
2584 void* init_thread(void *threadID) {
2586 TM.idle_loop(*(int*)threadID, NULL);
2592 DWORD WINAPI init_thread(LPVOID threadID) {
2594 TM.idle_loop(*(int*)threadID, NULL);
2601 /// The ThreadsManager class
2603 // resetNodeCounters(), resetBetaCounters(), searched_nodes() and
2604 // get_beta_counters() are getters/setters for the per thread
2605 // counters used to sort the moves at root.
2607 void ThreadsManager::resetNodeCounters() {
2609 for (int i = 0; i < MAX_THREADS; i++)
2610 threads[i].nodes = 0ULL;
2613 void ThreadsManager::resetBetaCounters() {
2615 for (int i = 0; i < MAX_THREADS; i++)
2616 threads[i].betaCutOffs[WHITE] = threads[i].betaCutOffs[BLACK] = 0ULL;
2619 int64_t ThreadsManager::nodes_searched() const {
2621 int64_t result = 0ULL;
2622 for (int i = 0; i < ActiveThreads; i++)
2623 result += threads[i].nodes;
2628 void ThreadsManager::get_beta_counters(Color us, int64_t& our, int64_t& their) const {
2631 for (int i = 0; i < MAX_THREADS; i++)
2633 our += threads[i].betaCutOffs[us];
2634 their += threads[i].betaCutOffs[opposite_color(us)];
2639 // idle_loop() is where the threads are parked when they have no work to do.
2640 // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint
2641 // object for which the current thread is the master.
2643 void ThreadsManager::idle_loop(int threadID, SplitPoint* waitSp) {
2645 assert(threadID >= 0 && threadID < MAX_THREADS);
2649 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2650 // master should exit as last one.
2651 if (AllThreadsShouldExit)
2654 threads[threadID].state = THREAD_TERMINATED;
2658 // If we are not thinking, wait for a condition to be signaled
2659 // instead of wasting CPU time polling for work.
2660 while (AllThreadsShouldSleep || threadID >= ActiveThreads)
2663 assert(threadID != 0);
2664 threads[threadID].state = THREAD_SLEEPING;
2666 #if !defined(_MSC_VER)
2667 lock_grab(&WaitLock);
2668 if (AllThreadsShouldSleep || threadID >= ActiveThreads)
2669 pthread_cond_wait(&WaitCond, &WaitLock);
2670 lock_release(&WaitLock);
2672 WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2676 // If thread has just woken up, mark it as available
2677 if (threads[threadID].state == THREAD_SLEEPING)
2678 threads[threadID].state = THREAD_AVAILABLE;
2680 // If this thread has been assigned work, launch a search
2681 if (threads[threadID].state == THREAD_WORKISWAITING)
2683 assert(!AllThreadsShouldExit && !AllThreadsShouldSleep);
2685 threads[threadID].state = THREAD_SEARCHING;
2687 if (threads[threadID].splitPoint->pvNode)
2688 sp_search_pv(threads[threadID].splitPoint, threadID);
2690 sp_search(threads[threadID].splitPoint, threadID);
2692 assert(threads[threadID].state == THREAD_SEARCHING);
2694 threads[threadID].state = THREAD_AVAILABLE;
2697 // If this thread is the master of a split point and all threads have
2698 // finished their work at this split point, return from the idle loop.
2699 if (waitSp != NULL && waitSp->cpus == 0)
2701 assert(threads[threadID].state == THREAD_AVAILABLE);
2703 threads[threadID].state = THREAD_SEARCHING;
2710 // init_threads() is called during startup. It launches all helper threads,
2711 // and initializes the split point stack and the global locks and condition
2714 void ThreadsManager::init_threads() {
2719 #if !defined(_MSC_VER)
2720 pthread_t pthread[1];
2723 // Initialize global locks
2724 lock_init(&MPLock, NULL);
2725 lock_init(&WaitLock, NULL);
2727 #if !defined(_MSC_VER)
2728 pthread_cond_init(&WaitCond, NULL);
2730 for (i = 0; i < MAX_THREADS; i++)
2731 SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0);
2734 // Initialize SplitPointStack locks
2735 for (i = 0; i < MAX_THREADS; i++)
2736 for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
2738 SplitPointStack[i][j].parent = NULL;
2739 lock_init(&(SplitPointStack[i][j].lock), NULL);
2742 // Will be set just before program exits to properly end the threads
2743 AllThreadsShouldExit = false;
2745 // Threads will be put to sleep as soon as created
2746 AllThreadsShouldSleep = true;
2748 // All threads except the main thread should be initialized to THREAD_AVAILABLE
2750 threads[0].state = THREAD_SEARCHING;
2751 for (i = 1; i < MAX_THREADS; i++)
2752 threads[i].state = THREAD_AVAILABLE;
2754 // Launch the helper threads
2755 for (i = 1; i < MAX_THREADS; i++)
2758 #if !defined(_MSC_VER)
2759 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&i)) == 0);
2761 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, NULL) != NULL);
2766 cout << "Failed to create thread number " << i << endl;
2767 Application::exit_with_failure();
2770 // Wait until the thread has finished launching and is gone to sleep
2771 while (threads[i].state != THREAD_SLEEPING);
2776 // exit_threads() is called when the program exits. It makes all the
2777 // helper threads exit cleanly.
2779 void ThreadsManager::exit_threads() {
2781 ActiveThreads = MAX_THREADS; // HACK
2782 AllThreadsShouldSleep = true; // HACK
2783 wake_sleeping_threads();
2785 // This makes the threads to exit idle_loop()
2786 AllThreadsShouldExit = true;
2788 // Wait for thread termination
2789 for (int i = 1; i < MAX_THREADS; i++)
2790 while (threads[i].state != THREAD_TERMINATED);
2792 // Now we can safely destroy the locks
2793 for (int i = 0; i < MAX_THREADS; i++)
2794 for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
2795 lock_destroy(&(SplitPointStack[i][j].lock));
2797 lock_destroy(&WaitLock);
2798 lock_destroy(&MPLock);
2802 // thread_should_stop() checks whether the thread should stop its search.
2803 // This can happen if a beta cutoff has occurred in the thread's currently
2804 // active split point, or in some ancestor of the current split point.
2806 bool ThreadsManager::thread_should_stop(int threadID) const {
2808 assert(threadID >= 0 && threadID < ActiveThreads);
2812 for (sp = threads[threadID].splitPoint; sp && !sp->stopRequest; sp = sp->parent);
2817 // thread_is_available() checks whether the thread with threadID "slave" is
2818 // available to help the thread with threadID "master" at a split point. An
2819 // obvious requirement is that "slave" must be idle. With more than two
2820 // threads, this is not by itself sufficient: If "slave" is the master of
2821 // some active split point, it is only available as a slave to the other
2822 // threads which are busy searching the split point at the top of "slave"'s
2823 // split point stack (the "helpful master concept" in YBWC terminology).
2825 bool ThreadsManager::thread_is_available(int slave, int master) const {
2827 assert(slave >= 0 && slave < ActiveThreads);
2828 assert(master >= 0 && master < ActiveThreads);
2829 assert(ActiveThreads > 1);
2831 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2834 // Make a local copy to be sure doesn't change under our feet
2835 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2837 if (localActiveSplitPoints == 0)
2838 // No active split points means that the thread is available as
2839 // a slave for any other thread.
2842 if (ActiveThreads == 2)
2845 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2846 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2847 // could have been set to 0 by another thread leading to an out of bound access.
2848 if (SplitPointStack[slave][localActiveSplitPoints - 1].slaves[master])
2855 // available_thread_exists() tries to find an idle thread which is available as
2856 // a slave for the thread with threadID "master".
2858 bool ThreadsManager::available_thread_exists(int master) const {
2860 assert(master >= 0 && master < ActiveThreads);
2861 assert(ActiveThreads > 1);
2863 for (int i = 0; i < ActiveThreads; i++)
2864 if (thread_is_available(i, master))
2871 // split() does the actual work of distributing the work at a node between
2872 // several threads at PV nodes. If it does not succeed in splitting the
2873 // node (because no idle threads are available, or because we have no unused
2874 // split point objects), the function immediately returns false. If
2875 // splitting is possible, a SplitPoint object is initialized with all the
2876 // data that must be copied to the helper threads (the current position and
2877 // search stack, alpha, beta, the search depth, etc.), and we tell our
2878 // helper threads that they have been assigned work. This will cause them
2879 // to instantly leave their idle loops and call sp_search_pv(). When all
2880 // threads have returned from sp_search_pv (or, equivalently, when
2881 // splitPoint->cpus becomes 0), split() returns true.
2883 bool ThreadsManager::split(const Position& p, SearchStack* sstck, int ply,
2884 Value* alpha, const Value beta, Value* bestValue,
2885 Depth depth, int* moves, MovePicker* mp, int master, bool pvNode) {
2888 assert(sstck != NULL);
2889 assert(ply >= 0 && ply < PLY_MAX);
2890 assert(*bestValue >= -VALUE_INFINITE);
2891 assert( ( pvNode && *bestValue <= *alpha)
2892 || (!pvNode && *bestValue < beta ));
2893 assert(!pvNode || *alpha < beta);
2894 assert(beta <= VALUE_INFINITE);
2895 assert(depth > Depth(0));
2896 assert(master >= 0 && master < ActiveThreads);
2897 assert(ActiveThreads > 1);
2899 SplitPoint* splitPoint;
2903 // If no other thread is available to help us, or if we have too many
2904 // active split points, don't split.
2905 if ( !available_thread_exists(master)
2906 || threads[master].activeSplitPoints >= ACTIVE_SPLIT_POINTS_MAX)
2908 lock_release(&MPLock);
2912 // Pick the next available split point object from the split point stack
2913 splitPoint = &SplitPointStack[master][threads[master].activeSplitPoints];
2915 // Initialize the split point object
2916 splitPoint->parent = threads[master].splitPoint;
2917 splitPoint->stopRequest = false;
2918 splitPoint->ply = ply;
2919 splitPoint->depth = depth;
2920 splitPoint->alpha = pvNode ? *alpha : beta - 1;
2921 splitPoint->beta = beta;
2922 splitPoint->pvNode = pvNode;
2923 splitPoint->bestValue = *bestValue;
2924 splitPoint->master = master;
2925 splitPoint->mp = mp;
2926 splitPoint->moves = *moves;
2927 splitPoint->cpus = 1;
2928 splitPoint->pos = &p;
2929 splitPoint->parentSstack = sstck;
2930 for (int i = 0; i < ActiveThreads; i++)
2931 splitPoint->slaves[i] = 0;
2933 threads[master].splitPoint = splitPoint;
2934 threads[master].activeSplitPoints++;
2936 // If we are here it means we are not available
2937 assert(threads[master].state != THREAD_AVAILABLE);
2939 // Allocate available threads setting state to THREAD_BOOKED
2940 for (int i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint; i++)
2941 if (thread_is_available(i, master))
2943 threads[i].state = THREAD_BOOKED;
2944 threads[i].splitPoint = splitPoint;
2945 splitPoint->slaves[i] = 1;
2949 assert(splitPoint->cpus > 1);
2951 // We can release the lock because slave threads are already booked and master is not available
2952 lock_release(&MPLock);
2954 // Tell the threads that they have work to do. This will make them leave
2955 // their idle loop. But before copy search stack tail for each thread.
2956 for (int i = 0; i < ActiveThreads; i++)
2957 if (i == master || splitPoint->slaves[i])
2959 memcpy(splitPoint->sstack[i] + ply - 1, sstck + ply - 1, 4 * sizeof(SearchStack));
2961 assert(i == master || threads[i].state == THREAD_BOOKED);
2963 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2966 // Everything is set up. The master thread enters the idle loop, from
2967 // which it will instantly launch a search, because its state is
2968 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2969 // idle loop, which means that the main thread will return from the idle
2970 // loop when all threads have finished their work at this split point
2971 // (i.e. when splitPoint->cpus == 0).
2972 idle_loop(master, splitPoint);
2974 // We have returned from the idle loop, which means that all threads are
2975 // finished. Update alpha, beta and bestValue, and return.
2979 *alpha = splitPoint->alpha;
2981 *bestValue = splitPoint->bestValue;
2982 threads[master].activeSplitPoints--;
2983 threads[master].splitPoint = splitPoint->parent;
2985 lock_release(&MPLock);
2990 // wake_sleeping_threads() wakes up all sleeping threads when it is time
2991 // to start a new search from the root.
2993 void ThreadsManager::wake_sleeping_threads() {
2995 assert(AllThreadsShouldSleep);
2996 assert(ActiveThreads > 0);
2998 AllThreadsShouldSleep = false;
3000 if (ActiveThreads == 1)
3003 #if !defined(_MSC_VER)
3004 pthread_mutex_lock(&WaitLock);
3005 pthread_cond_broadcast(&WaitCond);
3006 pthread_mutex_unlock(&WaitLock);
3008 for (int i = 1; i < MAX_THREADS; i++)
3009 SetEvent(SitIdleEvent[i]);
3015 // put_threads_to_sleep() makes all the threads go to sleep just before
3016 // to leave think(), at the end of the search. Threads should have already
3017 // finished the job and should be idle.
3019 void ThreadsManager::put_threads_to_sleep() {
3021 assert(!AllThreadsShouldSleep);
3023 // This makes the threads to go to sleep
3024 AllThreadsShouldSleep = true;
3027 /// The RootMoveList class
3029 // RootMoveList c'tor
3031 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
3033 SearchStack ss[PLY_MAX_PLUS_2];
3034 MoveStack mlist[MaxRootMoves];
3036 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
3038 // Generate all legal moves
3039 MoveStack* last = generate_moves(pos, mlist);
3041 // Add each move to the moves[] array
3042 for (MoveStack* cur = mlist; cur != last; cur++)
3044 bool includeMove = includeAllMoves;
3046 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
3047 includeMove = (searchMoves[k] == cur->move);
3052 // Find a quick score for the move
3054 pos.do_move(cur->move, st);
3055 moves[count].move = cur->move;
3056 moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0);
3057 moves[count].pv[0] = cur->move;
3058 moves[count].pv[1] = MOVE_NONE;
3059 pos.undo_move(cur->move);
3066 // RootMoveList simple methods definitions
3068 void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
3070 moves[moveNum].nodes = nodes;
3071 moves[moveNum].cumulativeNodes += nodes;
3074 void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
3076 moves[moveNum].ourBeta = our;
3077 moves[moveNum].theirBeta = their;
3080 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
3084 for (j = 0; pv[j] != MOVE_NONE; j++)
3085 moves[moveNum].pv[j] = pv[j];
3087 moves[moveNum].pv[j] = MOVE_NONE;
3091 // RootMoveList::sort() sorts the root move list at the beginning of a new
3094 void RootMoveList::sort() {
3096 sort_multipv(count - 1); // Sort all items
3100 // RootMoveList::sort_multipv() sorts the first few moves in the root move
3101 // list by their scores and depths. It is used to order the different PVs
3102 // correctly in MultiPV mode.
3104 void RootMoveList::sort_multipv(int n) {
3108 for (i = 1; i <= n; i++)
3110 RootMove rm = moves[i];
3111 for (j = i; j > 0 && moves[j - 1] < rm; j--)
3112 moves[j] = moves[j - 1];