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 // Step 9. Internal iterative deepening
176 const Depth IIDDepthAtPVNodes = 5 * OnePly;
177 const Depth IIDDepthAtNonPVNodes = 8 * OnePly;
179 // Internal iterative deepening margin. At Non-PV nodes
180 // we do an internal iterative deepening
181 // search when the static evaluation is at most IIDMargin below beta.
182 const Value IIDMargin = Value(0x100);
184 // Step 11. Decide the new search depth
186 // Extensions. Configurable UCI options.
187 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
188 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
189 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
191 const Depth SingularExtensionDepthAtPVNodes = 6 * OnePly;
192 const Depth SingularExtensionDepthAtNonPVNodes = 8 * OnePly;
194 // If the TT move is at least SingularExtensionMargin better then the
195 // remaining ones we will extend it.
196 const Value SingularExtensionMargin = Value(0x20);
200 // Search depth at iteration 1
201 const Depth InitialDepth = OnePly;
203 // Easy move margin. An easy move candidate must be at least this much
204 // better than the second best move.
205 const Value EasyMoveMargin = Value(0x200);
207 /// Lookup tables initialized at startup
209 // Reduction lookup tables and their getter functions
210 int8_t PVReductionMatrix[64][64]; // [depth][moveNumber]
211 int8_t NonPVReductionMatrix[64][64]; // [depth][moveNumber]
213 inline Depth pv_reduction(Depth d, int mn) { return (Depth) PVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; }
214 inline Depth nonpv_reduction(Depth d, int mn) { return (Depth) NonPVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; }
216 // Futility lookup tables and their getter functions
217 const Value FutilityMarginQS = Value(0x80);
218 int32_t FutilityMarginsMatrix[14][64]; // [depth][moveNumber]
219 int FutilityMoveCountArray[32]; // [depth]
221 inline Value futility_margin(Depth d, int mn) { return Value(d < 7*OnePly ? FutilityMarginsMatrix[Max(d, 0)][Min(mn, 63)] : 2 * VALUE_INFINITE); }
222 inline int futility_move_count(Depth d) { return d < 16*OnePly ? FutilityMoveCountArray[d] : 512; }
224 /// Variables initialized by UCI options
226 // Depth limit for use of dynamic threat detection
229 // Last seconds noise filtering (LSN)
230 const bool UseLSNFiltering = true;
231 const int LSNTime = 4000; // In milliseconds
232 const Value LSNValue = value_from_centipawns(200);
233 bool loseOnTime = false;
235 // Iteration counters
238 // Scores and number of times the best move changed for each iteration
239 Value ValueByIteration[PLY_MAX_PLUS_2];
240 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
242 // Search window management
248 // Time managment variables
251 int MaxNodes, MaxDepth;
252 int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
253 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
254 bool AbortSearch, Quit;
255 bool AspirationFailLow;
257 // Show current line?
258 bool ShowCurrentLine;
262 std::ofstream LogFile;
264 // MP related variables
265 Depth MinimumSplitDepth;
266 int MaxThreadsPerSplitPoint;
269 // Node counters, used only by thread[0] but try to keep in different
270 // cache lines (64 bytes each) from the heavy SMP read accessed variables.
272 int NodesBetweenPolls = 30000;
279 Value id_loop(const Position& pos, Move searchMoves[]);
280 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta);
281 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
282 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE);
283 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
284 void sp_search(SplitPoint* sp, int threadID);
285 void sp_search_pv(SplitPoint* sp, int threadID);
286 void init_node(SearchStack ss[], int ply, int threadID);
287 void update_pv(SearchStack ss[], int ply);
288 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply);
289 bool connected_moves(const Position& pos, Move m1, Move m2);
290 bool value_is_mate(Value value);
291 bool move_is_killer(Move m, const SearchStack& ss);
292 Depth extension(const Position&, Move, bool, bool, bool, bool, bool, bool*);
293 bool ok_to_do_nullmove(const Position& pos);
294 bool ok_to_prune(const Position& pos, Move m, Move threat);
295 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
296 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
297 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
298 void update_killers(Move m, SearchStack& ss);
299 void update_gains(const Position& pos, Move move, Value before, Value after);
301 int current_search_time();
303 void poll(SearchStack ss[], int ply);
305 void wait_for_stop_or_ponderhit();
306 void init_ss_array(SearchStack ss[]);
308 #if !defined(_MSC_VER)
309 void *init_thread(void *threadID);
311 DWORD WINAPI init_thread(LPVOID threadID);
321 /// init_threads(), exit_threads() and nodes_searched() are helpers to
322 /// give accessibility to some TM methods from outside of current file.
324 void init_threads() { TM.init_threads(); }
325 void exit_threads() { TM.exit_threads(); }
326 int64_t nodes_searched() { return TM.nodes_searched(); }
329 /// perft() is our utility to verify move generation is bug free. All the legal
330 /// moves up to given depth are generated and counted and the sum returned.
332 int perft(Position& pos, Depth depth)
336 MovePicker mp = MovePicker(pos, MOVE_NONE, depth, H);
338 // If we are at the last ply we don't need to do and undo
339 // the moves, just to count them.
340 if (depth <= OnePly) // Replace with '<' to test also qsearch
342 while (mp.get_next_move()) sum++;
346 // Loop through all legal moves
348 while ((move = mp.get_next_move()) != MOVE_NONE)
351 pos.do_move(move, st, ci, pos.move_is_check(move, ci));
352 sum += perft(pos, depth - OnePly);
359 /// think() is the external interface to Stockfish's search, and is called when
360 /// the program receives the UCI 'go' command. It initializes various
361 /// search-related global variables, and calls root_search(). It returns false
362 /// when a quit command is received during the search.
364 bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
365 int time[], int increment[], int movesToGo, int maxDepth,
366 int maxNodes, int maxTime, Move searchMoves[]) {
368 // Initialize global search variables
369 StopOnPonderhit = AbortSearch = Quit = false;
370 AspirationFailLow = false;
372 SearchStartTime = get_system_time();
373 ExactMaxTime = maxTime;
376 InfiniteSearch = infinite;
377 PonderSearch = ponder;
378 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
380 // Look for a book move, only during games, not tests
381 if (UseTimeManagement && get_option_value_bool("OwnBook"))
384 if (get_option_value_string("Book File") != OpeningBook.file_name())
385 OpeningBook.open(get_option_value_string("Book File"));
387 bookMove = OpeningBook.get_move(pos);
388 if (bookMove != MOVE_NONE)
391 wait_for_stop_or_ponderhit();
393 cout << "bestmove " << bookMove << endl;
398 TM.resetNodeCounters();
400 if (button_was_pressed("New Game"))
401 loseOnTime = false; // Reset at the beginning of a new game
403 // Read UCI option values
404 TT.set_size(get_option_value_int("Hash"));
405 if (button_was_pressed("Clear Hash"))
408 bool PonderingEnabled = get_option_value_bool("Ponder");
409 MultiPV = get_option_value_int("MultiPV");
411 CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)"));
412 CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)"));
414 SingleEvasionExtension[1] = Depth(get_option_value_int("Single Evasion Extension (PV nodes)"));
415 SingleEvasionExtension[0] = Depth(get_option_value_int("Single Evasion Extension (non-PV nodes)"));
417 PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)"));
418 PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
420 PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
421 PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
423 PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
424 PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)"));
426 MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
427 MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
429 ThreatDepth = get_option_value_int("Threat Depth") * OnePly;
431 Chess960 = get_option_value_bool("UCI_Chess960");
432 ShowCurrentLine = get_option_value_bool("UCI_ShowCurrLine");
433 UseLogFile = get_option_value_bool("Use Search Log");
435 LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app);
437 MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly;
438 MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point");
440 read_weights(pos.side_to_move());
442 // Set the number of active threads
443 int newActiveThreads = get_option_value_int("Threads");
444 if (newActiveThreads != TM.active_threads())
446 TM.set_active_threads(newActiveThreads);
447 init_eval(TM.active_threads());
448 // HACK: init_eval() destroys the static castleRightsMask[] array in the
449 // Position class. The below line repairs the damage.
450 Position p(pos.to_fen());
454 // Wake up sleeping threads
455 TM.wake_sleeping_threads();
458 int myTime = time[side_to_move];
459 int myIncrement = increment[side_to_move];
460 if (UseTimeManagement)
462 if (!movesToGo) // Sudden death time control
466 MaxSearchTime = myTime / 30 + myIncrement;
467 AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
469 else // Blitz game without increment
471 MaxSearchTime = myTime / 30;
472 AbsoluteMaxSearchTime = myTime / 8;
475 else // (x moves) / (y minutes)
479 MaxSearchTime = myTime / 2;
480 AbsoluteMaxSearchTime = (myTime > 3000)? (myTime - 500) : ((myTime * 3) / 4);
484 MaxSearchTime = myTime / Min(movesToGo, 20);
485 AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
489 if (PonderingEnabled)
491 MaxSearchTime += MaxSearchTime / 4;
492 MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime);
496 // Set best NodesBetweenPolls interval
498 NodesBetweenPolls = Min(MaxNodes, 30000);
499 else if (myTime && myTime < 1000)
500 NodesBetweenPolls = 1000;
501 else if (myTime && myTime < 5000)
502 NodesBetweenPolls = 5000;
504 NodesBetweenPolls = 30000;
506 // Write information to search log file
508 LogFile << "Searching: " << pos.to_fen() << endl
509 << "infinite: " << infinite
510 << " ponder: " << ponder
511 << " time: " << myTime
512 << " increment: " << myIncrement
513 << " moves to go: " << movesToGo << endl;
515 // LSN filtering. Used only for developing purpose. Disabled by default.
519 // Step 2. If after last move we decided to lose on time, do it now!
520 while (SearchStartTime + myTime + 1000 > get_system_time())
524 // We're ready to start thinking. Call the iterative deepening loop function
525 Value v = id_loop(pos, searchMoves);
529 // Step 1. If this is sudden death game and our position is hopeless,
530 // decide to lose on time.
531 if ( !loseOnTime // If we already lost on time, go to step 3.
541 // Step 3. Now after stepping over the time limit, reset flag for next match.
549 TM.put_threads_to_sleep();
555 /// init_search() is called during startup. It initializes various lookup tables
559 // Init our reduction lookup tables
560 for (int i = 1; i < 64; i++) // i == depth (OnePly = 1)
561 for (int j = 1; j < 64; j++) // j == moveNumber
563 double pvRed = 0.5 + log(double(i)) * log(double(j)) / 6.0;
564 double nonPVRed = 0.5 + log(double(i)) * log(double(j)) / 3.0;
565 PVReductionMatrix[i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0);
566 NonPVReductionMatrix[i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0);
569 // Init futility margins array
570 for (int i = 0; i < 14; i++) // i == depth (OnePly = 2)
571 for (int j = 0; j < 64; j++) // j == moveNumber
573 FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j; // FIXME: test using log instead of BSR
576 // Init futility move count array
577 for (int i = 0; i < 32; i++) // i == depth (OnePly = 2)
578 FutilityMoveCountArray[i] = 3 + (1 << (3 * i / 8));
582 // SearchStack::init() initializes a search stack. Used at the beginning of a
583 // new search from the root.
584 void SearchStack::init(int ply) {
586 pv[ply] = pv[ply + 1] = MOVE_NONE;
587 currentMove = threatMove = MOVE_NONE;
588 reduction = Depth(0);
592 void SearchStack::initKillers() {
594 mateKiller = MOVE_NONE;
595 for (int i = 0; i < KILLER_MAX; i++)
596 killers[i] = MOVE_NONE;
601 // id_loop() is the main iterative deepening loop. It calls root_search
602 // repeatedly with increasing depth until the allocated thinking time has
603 // been consumed, the user stops the search, or the maximum search depth is
606 Value id_loop(const Position& pos, Move searchMoves[]) {
609 SearchStack ss[PLY_MAX_PLUS_2];
611 // searchMoves are verified, copied, scored and sorted
612 RootMoveList rml(p, searchMoves);
614 // Handle special case of searching on a mate/stale position
615 if (rml.move_count() == 0)
618 wait_for_stop_or_ponderhit();
620 return pos.is_check()? -VALUE_MATE : VALUE_DRAW;
623 // Print RootMoveList c'tor startup scoring to the standard output,
624 // so that we print information also for iteration 1.
625 cout << "info depth " << 1 << "\ninfo depth " << 1
626 << " score " << value_to_string(rml.get_move_score(0))
627 << " time " << current_search_time()
628 << " nodes " << TM.nodes_searched()
630 << " pv " << rml.get_move(0) << "\n";
636 ValueByIteration[1] = rml.get_move_score(0);
639 // Is one move significantly better than others after initial scoring ?
640 Move EasyMove = MOVE_NONE;
641 if ( rml.move_count() == 1
642 || rml.get_move_score(0) > rml.get_move_score(1) + EasyMoveMargin)
643 EasyMove = rml.get_move(0);
645 // Iterative deepening loop
646 while (Iteration < PLY_MAX)
648 // Initialize iteration
651 BestMoveChangesByIteration[Iteration] = 0;
655 cout << "info depth " << Iteration << endl;
657 // Calculate dynamic search window based on previous iterations
660 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
662 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
663 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
665 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
666 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
668 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
669 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
673 alpha = - VALUE_INFINITE;
674 beta = VALUE_INFINITE;
677 // Search to the current depth
678 Value value = root_search(p, ss, rml, alpha, beta);
680 // Write PV to transposition table, in case the relevant entries have
681 // been overwritten during the search.
682 TT.insert_pv(p, ss[0].pv);
685 break; // Value cannot be trusted. Break out immediately!
687 //Save info about search result
688 ValueByIteration[Iteration] = value;
690 // Drop the easy move if it differs from the new best move
691 if (ss[0].pv[0] != EasyMove)
692 EasyMove = MOVE_NONE;
694 if (UseTimeManagement)
697 bool stopSearch = false;
699 // Stop search early if there is only a single legal move,
700 // we search up to Iteration 6 anyway to get a proper score.
701 if (Iteration >= 6 && rml.move_count() == 1)
704 // Stop search early when the last two iterations returned a mate score
706 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
707 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
710 // Stop search early if one move seems to be much better than the rest
711 int64_t nodes = TM.nodes_searched();
713 && EasyMove == ss[0].pv[0]
714 && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
715 && current_search_time() > MaxSearchTime / 16)
716 ||( rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100
717 && current_search_time() > MaxSearchTime / 32)))
720 // Add some extra time if the best move has changed during the last two iterations
721 if (Iteration > 5 && Iteration <= 50)
722 ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2)
723 + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3);
725 // Stop search if most of MaxSearchTime is consumed at the end of the
726 // iteration. We probably don't have enough time to search the first
727 // move at the next iteration anyway.
728 if (current_search_time() > ((MaxSearchTime + ExtraSearchTime) * 80) / 128)
736 StopOnPonderhit = true;
740 if (MaxDepth && Iteration >= MaxDepth)
746 // If we are pondering or in infinite search, we shouldn't print the
747 // best move before we are told to do so.
748 if (!AbortSearch && (PonderSearch || InfiniteSearch))
749 wait_for_stop_or_ponderhit();
751 // Print final search statistics
752 cout << "info nodes " << TM.nodes_searched()
754 << " time " << current_search_time()
755 << " hashfull " << TT.full() << endl;
757 // Print the best move and the ponder move to the standard output
758 if (ss[0].pv[0] == MOVE_NONE)
760 ss[0].pv[0] = rml.get_move(0);
761 ss[0].pv[1] = MOVE_NONE;
763 cout << "bestmove " << ss[0].pv[0];
764 if (ss[0].pv[1] != MOVE_NONE)
765 cout << " ponder " << ss[0].pv[1];
772 dbg_print_mean(LogFile);
774 if (dbg_show_hit_rate)
775 dbg_print_hit_rate(LogFile);
777 LogFile << "\nNodes: " << TM.nodes_searched()
778 << "\nNodes/second: " << nps()
779 << "\nBest move: " << move_to_san(p, ss[0].pv[0]);
782 p.do_move(ss[0].pv[0], st);
783 LogFile << "\nPonder move: " << move_to_san(p, ss[0].pv[1]) << endl;
785 return rml.get_move_score(0);
789 // root_search() is the function which searches the root node. It is
790 // similar to search_pv except that it uses a different move ordering
791 // scheme and prints some information to the standard output.
793 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta) {
798 Depth depth, ext, newDepth;
801 int researchCount = 0;
802 bool moveIsCheck, captureOrPromotion, dangerous;
803 Value alpha = oldAlpha;
804 bool isCheck = pos.is_check();
806 // Evaluate the position statically
808 ss[0].eval = !isCheck ? evaluate(pos, ei, 0) : VALUE_NONE;
810 while (1) // Fail low loop
813 // Loop through all the moves in the root move list
814 for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
818 // We failed high, invalidate and skip next moves, leave node-counters
819 // and beta-counters as they are and quickly return, we will try to do
820 // a research at the next iteration with a bigger aspiration window.
821 rml.set_move_score(i, -VALUE_INFINITE);
825 RootMoveNumber = i + 1;
827 // Save the current node count before the move is searched
828 nodes = TM.nodes_searched();
830 // Reset beta cut-off counters
831 TM.resetBetaCounters();
833 // Pick the next root move, and print the move and the move number to
834 // the standard output.
835 move = ss[0].currentMove = rml.get_move(i);
837 if (current_search_time() >= 1000)
838 cout << "info currmove " << move
839 << " currmovenumber " << RootMoveNumber << endl;
841 // Decide search depth for this move
842 moveIsCheck = pos.move_is_check(move);
843 captureOrPromotion = pos.move_is_capture_or_promotion(move);
844 depth = (Iteration - 2) * OnePly + InitialDepth;
845 ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
846 newDepth = depth + ext;
848 value = - VALUE_INFINITE;
850 while (1) // Fail high loop
853 // Make the move, and search it
854 pos.do_move(move, st, ci, moveIsCheck);
856 if (i < MultiPV || value > alpha)
858 // Aspiration window is disabled in multi-pv case
860 alpha = -VALUE_INFINITE;
862 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
866 // Try to reduce non-pv search depth by one ply if move seems not problematic,
867 // if the move fails high will be re-searched at full depth.
868 bool doFullDepthSearch = true;
870 if ( depth >= 3*OnePly // FIXME was newDepth
872 && !captureOrPromotion
873 && !move_is_castle(move))
875 ss[0].reduction = pv_reduction(depth, RootMoveNumber - MultiPV + 1);
878 value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0);
879 doFullDepthSearch = (value > alpha);
883 if (doFullDepthSearch)
885 ss[0].reduction = Depth(0);
886 value = -search(pos, ss, -alpha, newDepth, 1, true, 0);
889 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
895 // Can we exit fail high loop ?
896 if (AbortSearch || value < beta)
899 // We are failing high and going to do a research. It's important to update score
900 // before research in case we run out of time while researching.
901 rml.set_move_score(i, value);
903 TT.extract_pv(pos, ss[0].pv, PLY_MAX);
904 rml.set_move_pv(i, ss[0].pv);
906 // Print search information to the standard output
907 cout << "info depth " << Iteration
908 << " score " << value_to_string(value)
909 << ((value >= beta) ? " lowerbound" :
910 ((value <= alpha)? " upperbound" : ""))
911 << " time " << current_search_time()
912 << " nodes " << TM.nodes_searched()
916 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
917 cout << ss[0].pv[j] << " ";
923 ValueType type = (value >= beta ? VALUE_TYPE_LOWER
924 : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT));
926 LogFile << pretty_pv(pos, current_search_time(), Iteration,
927 TM.nodes_searched(), value, type, ss[0].pv) << endl;
930 // Prepare for a research after a fail high, each time with a wider window
932 beta = Min(beta + AspirationDelta * (1 << researchCount), VALUE_INFINITE);
934 } // End of fail high loop
936 // Finished searching the move. If AbortSearch is true, the search
937 // was aborted because the user interrupted the search or because we
938 // ran out of time. In this case, the return value of the search cannot
939 // be trusted, and we break out of the loop without updating the best
944 // Remember beta-cutoff and searched nodes counts for this move. The
945 // info is used to sort the root moves at the next iteration.
947 TM.get_beta_counters(pos.side_to_move(), our, their);
948 rml.set_beta_counters(i, our, their);
949 rml.set_move_nodes(i, TM.nodes_searched() - nodes);
951 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
953 if (value <= alpha && i >= MultiPV)
954 rml.set_move_score(i, -VALUE_INFINITE);
957 // PV move or new best move!
960 rml.set_move_score(i, value);
962 TT.extract_pv(pos, ss[0].pv, PLY_MAX);
963 rml.set_move_pv(i, ss[0].pv);
967 // We record how often the best move has been changed in each
968 // iteration. This information is used for time managment: When
969 // the best move changes frequently, we allocate some more time.
971 BestMoveChangesByIteration[Iteration]++;
973 // Print search information to the standard output
974 cout << "info depth " << Iteration
975 << " score " << value_to_string(value)
976 << ((value >= beta) ? " lowerbound" :
977 ((value <= alpha)? " upperbound" : ""))
978 << " time " << current_search_time()
979 << " nodes " << TM.nodes_searched()
983 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
984 cout << ss[0].pv[j] << " ";
990 ValueType type = (value >= beta ? VALUE_TYPE_LOWER
991 : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT));
993 LogFile << pretty_pv(pos, current_search_time(), Iteration,
994 TM.nodes_searched(), value, type, ss[0].pv) << endl;
1001 rml.sort_multipv(i);
1002 for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
1004 cout << "info multipv " << j + 1
1005 << " score " << value_to_string(rml.get_move_score(j))
1006 << " depth " << ((j <= i)? Iteration : Iteration - 1)
1007 << " time " << current_search_time()
1008 << " nodes " << TM.nodes_searched()
1012 for (int k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
1013 cout << rml.get_move_pv(j, k) << " ";
1017 alpha = rml.get_move_score(Min(i, MultiPV-1));
1019 } // PV move or new best move
1021 assert(alpha >= oldAlpha);
1023 AspirationFailLow = (alpha == oldAlpha);
1025 if (AspirationFailLow && StopOnPonderhit)
1026 StopOnPonderhit = false;
1029 // Can we exit fail low loop ?
1030 if (AbortSearch || alpha > oldAlpha)
1033 // Prepare for a research after a fail low, each time with a wider window
1035 alpha = Max(alpha - AspirationDelta * (1 << researchCount), -VALUE_INFINITE);
1044 // search_pv() is the main search function for PV nodes.
1046 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta,
1047 Depth depth, int ply, int threadID) {
1049 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1050 assert(beta > alpha && beta <= VALUE_INFINITE);
1051 assert(ply >= 0 && ply < PLY_MAX);
1052 assert(threadID >= 0 && threadID < TM.active_threads());
1054 Move movesSearched[256];
1059 Depth ext, newDepth;
1060 Value bestValue, value, oldAlpha;
1061 bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
1062 bool mateThreat = false;
1064 bestValue = value = -VALUE_INFINITE;
1067 return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID);
1069 // Step 1. Initialize node and poll
1070 // Polling can abort search.
1071 init_node(ss, ply, threadID);
1073 // Step 2. Check for aborted search and immediate draw
1074 if (AbortSearch || TM.thread_should_stop(threadID))
1077 if (pos.is_draw() || ply >= PLY_MAX - 1)
1080 // Step 3. Mate distance pruning
1082 alpha = Max(value_mated_in(ply), alpha);
1083 beta = Min(value_mate_in(ply+1), beta);
1087 // Step 4. Transposition table lookup
1088 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1089 // This is to avoid problems in the following areas:
1091 // * Repetition draw detection
1092 // * Fifty move rule detection
1093 // * Searching for a mate
1094 // * Printing of full PV line
1095 tte = TT.retrieve(pos.get_key());
1096 ttMove = (tte ? tte->move() : MOVE_NONE);
1098 // Step 5. Evaluate the position statically
1099 // At PV nodes we do this only to update gain statistics
1100 isCheck = pos.is_check();
1103 ss[ply].eval = evaluate(pos, ei, threadID);
1104 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1107 // Step 6. Razoring (is omitted in PV nodes)
1108 // Step 7. Static null move pruning (is omitted in PV nodes)
1109 // Step 8. Null move search with verification search (is omitted in PV nodes)
1111 // Step 9. Internal iterative deepening
1112 if ( depth >= IIDDepthAtPVNodes
1113 && ttMove == MOVE_NONE)
1115 search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID);
1116 ttMove = ss[ply].pv[ply];
1117 tte = TT.retrieve(pos.get_key());
1120 // Step 10. Loop through moves
1121 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1123 // Initialize a MovePicker object for the current position
1124 mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move()));
1125 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1128 while ( alpha < beta
1129 && (move = mp.get_next_move()) != MOVE_NONE
1130 && !TM.thread_should_stop(threadID))
1132 assert(move_is_ok(move));
1134 singleEvasion = (isCheck && mp.number_of_evasions() == 1);
1135 moveIsCheck = pos.move_is_check(move, ci);
1136 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1138 // Step 11. Decide the new search depth
1139 ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1141 // Singular extension search. We extend the TT move if its value is much better than
1142 // its siblings. To verify this we do a reduced search on all the other moves but the
1143 // ttMove, if result is lower then ttValue minus a margin then we extend ttMove.
1144 if ( depth >= SingularExtensionDepthAtPVNodes
1146 && move == tte->move()
1148 && is_lower_bound(tte->type())
1149 && tte->depth() >= depth - 3 * OnePly)
1151 Value ttValue = value_from_tt(tte->value(), ply);
1153 if (abs(ttValue) < VALUE_KNOWN_WIN)
1155 Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move);
1157 if (excValue < ttValue - SingularExtensionMargin)
1162 newDepth = depth - OnePly + ext;
1164 // Update current move (this must be done after singular extension search)
1165 movesSearched[moveCount++] = ss[ply].currentMove = move;
1167 // Step 12. Futility pruning (is omitted in PV nodes)
1169 // Step 13. Make the move
1170 pos.do_move(move, st, ci, moveIsCheck);
1172 // Step extra. pv search (only in PV nodes)
1173 // The first move in list is the expected PV
1175 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1178 // Step 14. Reduced search
1179 // if the move fails high will be re-searched at full depth.
1180 bool doFullDepthSearch = true;
1182 if ( depth >= 3*OnePly
1184 && !captureOrPromotion
1185 && !move_is_castle(move)
1186 && !move_is_killer(move, ss[ply]))
1188 ss[ply].reduction = pv_reduction(depth, moveCount);
1189 if (ss[ply].reduction)
1191 value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
1192 doFullDepthSearch = (value > alpha);
1196 // Step 15. Full depth search
1197 if (doFullDepthSearch)
1199 ss[ply].reduction = Depth(0);
1200 value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID);
1202 // Step extra. pv search (only in PV nodes)
1203 if (value > alpha && value < beta)
1204 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1208 // Step 16. Undo move
1209 pos.undo_move(move);
1211 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1213 // Step 17. Check for new best move
1214 if (value > bestValue)
1221 if (value == value_mate_in(ply + 1))
1222 ss[ply].mateKiller = move;
1226 // Step 18. Check for split
1227 if ( TM.active_threads() > 1
1229 && depth >= MinimumSplitDepth
1231 && TM.available_thread_exists(threadID)
1233 && !TM.thread_should_stop(threadID)
1234 && TM.split(pos, ss, ply, &alpha, beta, &bestValue,
1235 depth, &moveCount, &mp, threadID, true))
1239 // Step 19. Check for mate and stalemate
1240 // All legal moves have been searched and if there were
1241 // no legal moves, it must be mate or stalemate.
1243 return (isCheck ? value_mated_in(ply) : VALUE_DRAW);
1245 // Step 20. Update tables
1246 // If the search is not aborted, update the transposition table,
1247 // history counters, and killer moves.
1248 if (AbortSearch || TM.thread_should_stop(threadID))
1251 if (bestValue <= oldAlpha)
1252 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1254 else if (bestValue >= beta)
1256 TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
1257 move = ss[ply].pv[ply];
1258 if (!pos.move_is_capture_or_promotion(move))
1260 update_history(pos, move, depth, movesSearched, moveCount);
1261 update_killers(move, ss[ply]);
1263 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
1266 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
1272 // search() is the search function for zero-width nodes.
1274 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth,
1275 int ply, bool allowNullmove, int threadID, Move excludedMove) {
1277 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1278 assert(ply >= 0 && ply < PLY_MAX);
1279 assert(threadID >= 0 && threadID < TM.active_threads());
1281 Move movesSearched[256];
1286 Depth ext, newDepth;
1287 Value bestValue, refinedValue, nullValue, value, futilityValueScaled;
1288 bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
1289 bool mateThreat = false;
1291 refinedValue = bestValue = value = -VALUE_INFINITE;
1294 return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1296 // Step 1. Initialize node and poll
1297 // Polling can abort search.
1298 init_node(ss, ply, threadID);
1300 // Step 2. Check for aborted search and immediate draw
1301 if (AbortSearch || TM.thread_should_stop(threadID))
1304 if (pos.is_draw() || ply >= PLY_MAX - 1)
1307 // Step 3. Mate distance pruning
1308 if (value_mated_in(ply) >= beta)
1311 if (value_mate_in(ply + 1) < beta)
1314 // Step 4. Transposition table lookup
1316 // We don't want the score of a partial search to overwrite a previous full search
1317 // TT value, so we use a different position key in case of an excluded move exists.
1318 Key posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1320 tte = TT.retrieve(posKey);
1321 ttMove = (tte ? tte->move() : MOVE_NONE);
1323 if (tte && ok_to_use_TT(tte, depth, beta, ply))
1325 ss[ply].currentMove = ttMove; // Can be MOVE_NONE
1326 return value_from_tt(tte->value(), ply);
1329 // Step 5. Evaluate the position statically
1330 isCheck = pos.is_check();
1334 if (tte && (tte->type() & VALUE_TYPE_EVAL))
1335 ss[ply].eval = value_from_tt(tte->value(), ply);
1337 ss[ply].eval = evaluate(pos, ei, threadID);
1339 refinedValue = refine_eval(tte, ss[ply].eval, ply); // Enhance accuracy with TT value if possible
1340 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1344 if ( !value_is_mate(beta)
1346 && depth < RazorDepth
1347 && refinedValue < beta - razor_margin(depth)
1348 && ss[ply - 1].currentMove != MOVE_NULL
1349 && ttMove == MOVE_NONE
1350 && !pos.has_pawn_on_7th(pos.side_to_move()))
1352 Value rbeta = beta - razor_margin(depth);
1353 Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID);
1355 return v; //FIXME: Logically should be: return (v + razor_margin(depth));
1358 // Step 7. Static null move pruning
1359 // We're betting that the opponent doesn't have a move that will reduce
1360 // the score by more than fuility_margin(depth) if we do a null move.
1363 && depth < RazorDepth
1364 && refinedValue - futility_margin(depth, 0) >= beta)
1365 return refinedValue - futility_margin(depth, 0);
1367 // Step 8. Null move search with verification search
1368 // When we jump directly to qsearch() we do a null move only if static value is
1369 // at least beta. Otherwise we do a null move if static value is not more than
1370 // NullMoveMargin under beta.
1374 && !value_is_mate(beta)
1375 && ok_to_do_nullmove(pos)
1376 && refinedValue >= beta - (depth >= 4 * OnePly ? NullMoveMargin : 0))
1378 ss[ply].currentMove = MOVE_NULL;
1380 pos.do_null_move(st);
1382 // Null move dynamic reduction based on depth
1383 int R = 3 + (depth >= 5 * OnePly ? depth / 8 : 0);
1385 // Null move dynamic reduction based on value
1386 if (refinedValue - beta > PawnValueMidgame)
1389 nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);
1391 pos.undo_null_move();
1393 if (nullValue >= beta)
1395 if (depth < 6 * OnePly)
1398 // Do zugzwang verification search
1399 Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
1403 // The null move failed low, which means that we may be faced with
1404 // some kind of threat. If the previous move was reduced, check if
1405 // the move that refuted the null move was somehow connected to the
1406 // move which was reduced. If a connection is found, return a fail
1407 // low score (which will cause the reduced move to fail high in the
1408 // parent node, which will trigger a re-search with full depth).
1409 if (nullValue == value_mated_in(ply + 2))
1412 ss[ply].threatMove = ss[ply + 1].currentMove;
1413 if ( depth < ThreatDepth
1414 && ss[ply - 1].reduction
1415 && connected_moves(pos, ss[ply - 1].currentMove, ss[ply].threatMove))
1420 // Step 9. Internal iterative deepening
1421 if ( depth >= IIDDepthAtNonPVNodes
1422 && ttMove == MOVE_NONE
1424 && ss[ply].eval >= beta - IIDMargin)
1426 search(pos, ss, beta, depth/2, ply, false, threadID);
1427 ttMove = ss[ply].pv[ply];
1428 tte = TT.retrieve(posKey);
1431 // Step 10. Loop through moves
1432 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1434 // Initialize a MovePicker object for the current position
1435 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1438 while ( bestValue < beta
1439 && (move = mp.get_next_move()) != MOVE_NONE
1440 && !TM.thread_should_stop(threadID))
1442 assert(move_is_ok(move));
1444 if (move == excludedMove)
1447 moveIsCheck = pos.move_is_check(move, ci);
1448 singleEvasion = (isCheck && mp.number_of_evasions() == 1);
1449 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1451 // Step 11. Decide the new search depth
1452 ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1454 // Singular extension search. We extend the TT move if its value is much better than
1455 // its siblings. To verify this we do a reduced search on all the other moves but the
1456 // ttMove, if result is lower then ttValue minus a margin then we extend ttMove.
1457 if ( depth >= SingularExtensionDepthAtNonPVNodes
1459 && move == tte->move()
1460 && !excludedMove // Do not allow recursive single-reply search
1462 && is_lower_bound(tte->type())
1463 && tte->depth() >= depth - 3 * OnePly)
1465 Value ttValue = value_from_tt(tte->value(), ply);
1467 if (abs(ttValue) < VALUE_KNOWN_WIN)
1469 Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move);
1471 if (excValue < ttValue - SingularExtensionMargin)
1476 newDepth = depth - OnePly + ext;
1478 // Update current move (this must be done after singular extension search)
1479 movesSearched[moveCount++] = ss[ply].currentMove = move;
1481 // Step 12. Futility pruning
1484 && !captureOrPromotion
1485 && !move_is_castle(move)
1488 // Move count based pruning
1489 if ( moveCount >= futility_move_count(depth)
1490 && ok_to_prune(pos, move, ss[ply].threatMove)
1491 && bestValue > value_mated_in(PLY_MAX))
1494 // Value based pruning
1495 Depth predictedDepth = newDepth - nonpv_reduction(depth, moveCount); //FIXME: We are ignoring condition: depth >= 3*OnePly, BUG??
1496 futilityValueScaled = ss[ply].eval + futility_margin(predictedDepth, moveCount)
1497 + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45;
1499 if (futilityValueScaled < beta)
1501 if (futilityValueScaled > bestValue)
1502 bestValue = futilityValueScaled;
1507 // Step 13. Make the move
1508 pos.do_move(move, st, ci, moveIsCheck);
1510 // Step 14. Reduced search
1511 // if the move fails high will be re-searched at full depth.
1512 bool doFullDepthSearch = true;
1514 if ( depth >= 3*OnePly
1516 && !captureOrPromotion
1517 && !move_is_castle(move)
1518 && !move_is_killer(move, ss[ply]))
1520 ss[ply].reduction = nonpv_reduction(depth, moveCount);
1521 if (ss[ply].reduction)
1523 value = -search(pos, ss, -(beta-1), newDepth-ss[ply].reduction, ply+1, true, threadID);
1524 doFullDepthSearch = (value >= beta);
1528 // Step 15. Full depth search
1529 if (doFullDepthSearch)
1531 ss[ply].reduction = Depth(0);
1532 value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID);
1535 // Step 16. Undo move
1536 pos.undo_move(move);
1538 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1540 // Step 17. Check for new best move
1541 if (value > bestValue)
1547 if (value == value_mate_in(ply + 1))
1548 ss[ply].mateKiller = move;
1551 // Step 18. Check for split
1552 if ( TM.active_threads() > 1
1554 && depth >= MinimumSplitDepth
1556 && TM.available_thread_exists(threadID)
1558 && !TM.thread_should_stop(threadID)
1559 && TM.split(pos, ss, ply, NULL, beta, &bestValue,
1560 depth, &moveCount, &mp, threadID, false))
1564 // Step 19. Check for mate and stalemate
1565 // All legal moves have been searched and if there were
1566 // no legal moves, it must be mate or stalemate.
1567 // If one move was excluded return fail low.
1569 return excludedMove ? beta - 1 : (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW);
1571 // Step 20. Update tables
1572 // If the search is not aborted, update the transposition table,
1573 // history counters, and killer moves.
1574 if (AbortSearch || TM.thread_should_stop(threadID))
1577 if (bestValue < beta)
1578 TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1581 TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
1582 move = ss[ply].pv[ply];
1583 TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
1584 if (!pos.move_is_capture_or_promotion(move))
1586 update_history(pos, move, depth, movesSearched, moveCount);
1587 update_killers(move, ss[ply]);
1592 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1598 // qsearch() is the quiescence search function, which is called by the main
1599 // search function when the remaining depth is zero (or, to be more precise,
1600 // less than OnePly).
1602 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta,
1603 Depth depth, int ply, int threadID) {
1605 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1606 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1608 assert(ply >= 0 && ply < PLY_MAX);
1609 assert(threadID >= 0 && threadID < TM.active_threads());
1614 Value staticValue, bestValue, value, futilityBase, futilityValue;
1615 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1616 const TTEntry* tte = NULL;
1618 bool pvNode = (beta - alpha != 1);
1619 Value oldAlpha = alpha;
1621 // Initialize, and make an early exit in case of an aborted search,
1622 // an instant draw, maximum ply reached, etc.
1623 init_node(ss, ply, threadID);
1625 // After init_node() that calls poll()
1626 if (AbortSearch || TM.thread_should_stop(threadID))
1629 if (pos.is_draw() || ply >= PLY_MAX - 1)
1632 // Transposition table lookup. At PV nodes, we don't use the TT for
1633 // pruning, but only for move ordering.
1634 tte = TT.retrieve(pos.get_key());
1635 ttMove = (tte ? tte->move() : MOVE_NONE);
1637 if (!pvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1639 assert(tte->type() != VALUE_TYPE_EVAL);
1641 ss[ply].currentMove = ttMove; // Can be MOVE_NONE
1642 return value_from_tt(tte->value(), ply);
1645 isCheck = pos.is_check();
1647 // Evaluate the position statically
1649 staticValue = -VALUE_INFINITE;
1650 else if (tte && (tte->type() & VALUE_TYPE_EVAL))
1651 staticValue = value_from_tt(tte->value(), ply);
1653 staticValue = evaluate(pos, ei, threadID);
1657 ss[ply].eval = staticValue;
1658 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1661 // Initialize "stand pat score", and return it immediately if it is
1663 bestValue = staticValue;
1665 if (bestValue >= beta)
1667 // Store the score to avoid a future costly evaluation() call
1668 if (!isCheck && !tte && ei.futilityMargin[pos.side_to_move()] == 0)
1669 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EV_LO, Depth(-127*OnePly), MOVE_NONE);
1674 if (bestValue > alpha)
1677 // If we are near beta then try to get a cutoff pushing checks a bit further
1678 bool deepChecks = depth == -OnePly && staticValue >= beta - PawnValueMidgame / 8;
1680 // Initialize a MovePicker object for the current position, and prepare
1681 // to search the moves. Because the depth is <= 0 here, only captures,
1682 // queen promotions and checks (only if depth == 0 or depth == -OnePly
1683 // and we are near beta) will be generated.
1684 MovePicker mp = MovePicker(pos, ttMove, deepChecks ? Depth(0) : depth, H);
1686 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1687 futilityBase = staticValue + FutilityMarginQS + ei.futilityMargin[pos.side_to_move()];
1689 // Loop through the moves until no moves remain or a beta cutoff
1691 while ( alpha < beta
1692 && (move = mp.get_next_move()) != MOVE_NONE)
1694 assert(move_is_ok(move));
1696 moveIsCheck = pos.move_is_check(move, ci);
1698 // Update current move
1700 ss[ply].currentMove = move;
1708 && !move_is_promotion(move)
1709 && !pos.move_is_passed_pawn_push(move))
1711 futilityValue = futilityBase
1712 + pos.endgame_value_of_piece_on(move_to(move))
1713 + (move_is_ep(move) ? PawnValueEndgame : Value(0));
1715 if (futilityValue < alpha)
1717 if (futilityValue > bestValue)
1718 bestValue = futilityValue;
1723 // Detect blocking evasions that are candidate to be pruned
1724 evasionPrunable = isCheck
1725 && bestValue != -VALUE_INFINITE
1726 && !pos.move_is_capture(move)
1727 && pos.type_of_piece_on(move_from(move)) != KING
1728 && !pos.can_castle(pos.side_to_move());
1730 // Don't search moves with negative SEE values
1731 if ( (!isCheck || evasionPrunable)
1734 && !move_is_promotion(move)
1735 && pos.see_sign(move) < 0)
1738 // Make and search the move
1739 pos.do_move(move, st, ci, moveIsCheck);
1740 value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID);
1741 pos.undo_move(move);
1743 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1746 if (value > bestValue)
1757 // All legal moves have been searched. A special case: If we're in check
1758 // and no legal moves were found, it is checkmate.
1759 if (!moveCount && pos.is_check()) // Mate!
1760 return value_mated_in(ply);
1762 // Update transposition table
1763 Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
1764 if (bestValue <= oldAlpha)
1766 // If bestValue isn't changed it means it is still the static evaluation
1767 // of the node, so keep this info to avoid a future evaluation() call.
1768 ValueType type = (bestValue == staticValue && !ei.futilityMargin[pos.side_to_move()] ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER);
1769 TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE);
1771 else if (bestValue >= beta)
1773 move = ss[ply].pv[ply];
1774 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, move);
1776 // Update killers only for good checking moves
1777 if (!pos.move_is_capture_or_promotion(move))
1778 update_killers(move, ss[ply]);
1781 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, d, ss[ply].pv[ply]);
1783 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1789 // sp_search() is used to search from a split point. This function is called
1790 // by each thread working at the split point. It is similar to the normal
1791 // search() function, but simpler. Because we have already probed the hash
1792 // table, done a null move search, and searched the first move before
1793 // splitting, we don't have to repeat all this work in sp_search(). We
1794 // also don't need to store anything to the hash table here: This is taken
1795 // care of after we return from the split point.
1796 // FIXME: We are currently ignoring mateThreat flag here
1798 void sp_search(SplitPoint* sp, int threadID) {
1800 assert(threadID >= 0 && threadID < TM.active_threads());
1801 assert(TM.active_threads() > 1);
1805 Depth ext, newDepth;
1806 Value value, futilityValueScaled;
1807 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
1809 value = -VALUE_INFINITE;
1811 Position pos(*sp->pos);
1813 SearchStack* ss = sp->sstack[threadID];
1814 isCheck = pos.is_check();
1816 // Step 10. Loop through moves
1817 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1818 lock_grab(&(sp->lock));
1820 while ( sp->bestValue < sp->beta
1821 && !TM.thread_should_stop(threadID)
1822 && (move = sp->mp->get_next_move()) != MOVE_NONE)
1824 moveCount = ++sp->moves;
1825 lock_release(&(sp->lock));
1827 assert(move_is_ok(move));
1829 moveIsCheck = pos.move_is_check(move, ci);
1830 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1832 // Step 11. Decide the new search depth
1833 ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous);
1834 newDepth = sp->depth - OnePly + ext;
1836 // Update current move
1837 ss[sp->ply].currentMove = move;
1839 // Step 12. Futility pruning
1842 && !captureOrPromotion
1843 && !move_is_castle(move))
1845 // Move count based pruning
1846 if ( moveCount >= futility_move_count(sp->depth)
1847 && ok_to_prune(pos, move, ss[sp->ply].threatMove)
1848 && sp->bestValue > value_mated_in(PLY_MAX))
1850 lock_grab(&(sp->lock));
1854 // Value based pruning
1855 Depth predictedDepth = newDepth - nonpv_reduction(sp->depth, moveCount);
1856 futilityValueScaled = ss[sp->ply].eval + futility_margin(predictedDepth, moveCount)
1857 + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45;
1859 if (futilityValueScaled < sp->beta)
1861 lock_grab(&(sp->lock));
1863 if (futilityValueScaled > sp->bestValue)
1864 sp->bestValue = futilityValueScaled;
1869 // Step 13. Make the move
1870 pos.do_move(move, st, ci, moveIsCheck);
1872 // Step 14. Reduced search
1873 // if the move fails high will be re-searched at full depth.
1874 bool doFullDepthSearch = true;
1877 && !captureOrPromotion
1878 && !move_is_castle(move)
1879 && !move_is_killer(move, ss[sp->ply]))
1881 ss[sp->ply].reduction = nonpv_reduction(sp->depth, moveCount);
1882 if (ss[sp->ply].reduction)
1884 value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
1885 doFullDepthSearch = (value >= sp->beta && !TM.thread_should_stop(threadID));
1889 // Step 15. Full depth search
1890 if (doFullDepthSearch)
1892 ss[sp->ply].reduction = Depth(0);
1893 value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID);
1896 // Step 16. Undo move
1897 pos.undo_move(move);
1899 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1901 // Step 17. Check for new best move
1902 lock_grab(&(sp->lock));
1904 if (value > sp->bestValue && !TM.thread_should_stop(threadID))
1906 sp->bestValue = value;
1907 if (sp->bestValue >= sp->beta)
1909 sp->stopRequest = true;
1910 sp_update_pv(sp->parentSstack, ss, sp->ply);
1915 /* Here we have the lock still grabbed */
1917 sp->slaves[threadID] = 0;
1920 lock_release(&(sp->lock));
1924 // sp_search_pv() is used to search from a PV split point. This function
1925 // is called by each thread working at the split point. It is similar to
1926 // the normal search_pv() function, but simpler. Because we have already
1927 // probed the hash table and searched the first move before splitting, we
1928 // don't have to repeat all this work in sp_search_pv(). We also don't
1929 // need to store anything to the hash table here: This is taken care of
1930 // after we return from the split point.
1931 // FIXME: We are ignoring mateThreat flag!
1933 void sp_search_pv(SplitPoint* sp, int threadID) {
1935 assert(threadID >= 0 && threadID < TM.active_threads());
1936 assert(TM.active_threads() > 1);
1940 Depth ext, newDepth;
1942 bool moveIsCheck, captureOrPromotion, dangerous;
1944 value = -VALUE_INFINITE;
1946 Position pos(*sp->pos);
1948 SearchStack* ss = sp->sstack[threadID];
1950 // Step 10. Loop through moves
1951 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1952 lock_grab(&(sp->lock));
1954 while ( sp->alpha < sp->beta
1955 && !TM.thread_should_stop(threadID)
1956 && (move = sp->mp->get_next_move()) != MOVE_NONE)
1958 moveCount = ++sp->moves;
1959 lock_release(&(sp->lock));
1961 assert(move_is_ok(move));
1963 moveIsCheck = pos.move_is_check(move, ci);
1964 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1966 // Step 11. Decide the new search depth
1967 ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
1968 newDepth = sp->depth - OnePly + ext;
1970 // Update current move
1971 ss[sp->ply].currentMove = move;
1973 // Step 12. Futility pruning (is omitted in PV nodes)
1975 // Step 13. Make the move
1976 pos.do_move(move, st, ci, moveIsCheck);
1978 // Step 14. Reduced search
1979 // if the move fails high will be re-searched at full depth.
1980 bool doFullDepthSearch = true;
1983 && !captureOrPromotion
1984 && !move_is_castle(move)
1985 && !move_is_killer(move, ss[sp->ply]))
1987 ss[sp->ply].reduction = pv_reduction(sp->depth, moveCount);
1988 if (ss[sp->ply].reduction)
1990 Value localAlpha = sp->alpha;
1991 value = -search(pos, ss, -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
1992 doFullDepthSearch = (value > localAlpha && !TM.thread_should_stop(threadID));
1996 // Step 15. Full depth search
1997 if (doFullDepthSearch)
1999 Value localAlpha = sp->alpha;
2000 ss[sp->ply].reduction = Depth(0);
2001 value = -search(pos, ss, -localAlpha, newDepth, sp->ply+1, true, threadID);
2003 if (value > localAlpha && value < sp->beta && !TM.thread_should_stop(threadID))
2005 // If another thread has failed high then sp->alpha has been increased
2006 // to be higher or equal then beta, if so, avoid to start a PV search.
2007 localAlpha = sp->alpha;
2008 if (localAlpha < sp->beta)
2009 value = -search_pv(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, threadID);
2013 // Step 16. Undo move
2014 pos.undo_move(move);
2016 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
2018 // Step 17. Check for new best move
2019 lock_grab(&(sp->lock));
2021 if (value > sp->bestValue && !TM.thread_should_stop(threadID))
2023 sp->bestValue = value;
2024 if (value > sp->alpha)
2026 // Ask threads to stop before to modify sp->alpha
2027 if (value >= sp->beta)
2028 sp->stopRequest = true;
2032 sp_update_pv(sp->parentSstack, ss, sp->ply);
2033 if (value == value_mate_in(sp->ply + 1))
2034 ss[sp->ply].mateKiller = move;
2039 /* Here we have the lock still grabbed */
2041 sp->slaves[threadID] = 0;
2044 lock_release(&(sp->lock));
2048 // init_node() is called at the beginning of all the search functions
2049 // (search(), search_pv(), qsearch(), and so on) and initializes the
2050 // search stack object corresponding to the current node. Once every
2051 // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
2052 // for user input and checks whether it is time to stop the search.
2054 void init_node(SearchStack ss[], int ply, int threadID) {
2056 assert(ply >= 0 && ply < PLY_MAX);
2057 assert(threadID >= 0 && threadID < TM.active_threads());
2059 TM.incrementNodeCounter(threadID);
2064 if (NodesSincePoll >= NodesBetweenPolls)
2071 ss[ply + 2].initKillers();
2075 // update_pv() is called whenever a search returns a value > alpha.
2076 // It updates the PV in the SearchStack object corresponding to the
2079 void update_pv(SearchStack ss[], int ply) {
2081 assert(ply >= 0 && ply < PLY_MAX);
2085 ss[ply].pv[ply] = ss[ply].currentMove;
2087 for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
2088 ss[ply].pv[p] = ss[ply + 1].pv[p];
2090 ss[ply].pv[p] = MOVE_NONE;
2094 // sp_update_pv() is a variant of update_pv for use at split points. The
2095 // difference between the two functions is that sp_update_pv also updates
2096 // the PV at the parent node.
2098 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply) {
2100 assert(ply >= 0 && ply < PLY_MAX);
2104 ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
2106 for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
2107 ss[ply].pv[p] = pss[ply].pv[p] = ss[ply + 1].pv[p];
2109 ss[ply].pv[p] = pss[ply].pv[p] = MOVE_NONE;
2113 // connected_moves() tests whether two moves are 'connected' in the sense
2114 // that the first move somehow made the second move possible (for instance
2115 // if the moving piece is the same in both moves). The first move is assumed
2116 // to be the move that was made to reach the current position, while the
2117 // second move is assumed to be a move from the current position.
2119 bool connected_moves(const Position& pos, Move m1, Move m2) {
2121 Square f1, t1, f2, t2;
2124 assert(move_is_ok(m1));
2125 assert(move_is_ok(m2));
2127 if (m2 == MOVE_NONE)
2130 // Case 1: The moving piece is the same in both moves
2136 // Case 2: The destination square for m2 was vacated by m1
2142 // Case 3: Moving through the vacated square
2143 if ( piece_is_slider(pos.piece_on(f2))
2144 && bit_is_set(squares_between(f2, t2), f1))
2147 // Case 4: The destination square for m2 is defended by the moving piece in m1
2148 p = pos.piece_on(t1);
2149 if (bit_is_set(pos.attacks_from(p, t1), t2))
2152 // Case 5: Discovered check, checking piece is the piece moved in m1
2153 if ( piece_is_slider(p)
2154 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
2155 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
2157 // discovered_check_candidates() works also if the Position's side to
2158 // move is the opposite of the checking piece.
2159 Color them = opposite_color(pos.side_to_move());
2160 Bitboard dcCandidates = pos.discovered_check_candidates(them);
2162 if (bit_is_set(dcCandidates, f2))
2169 // value_is_mate() checks if the given value is a mate one
2170 // eventually compensated for the ply.
2172 bool value_is_mate(Value value) {
2174 assert(abs(value) <= VALUE_INFINITE);
2176 return value <= value_mated_in(PLY_MAX)
2177 || value >= value_mate_in(PLY_MAX);
2181 // move_is_killer() checks if the given move is among the
2182 // killer moves of that ply.
2184 bool move_is_killer(Move m, const SearchStack& ss) {
2186 const Move* k = ss.killers;
2187 for (int i = 0; i < KILLER_MAX; i++, k++)
2195 // extension() decides whether a move should be searched with normal depth,
2196 // or with extended depth. Certain classes of moves (checking moves, in
2197 // particular) are searched with bigger depth than ordinary moves and in
2198 // any case are marked as 'dangerous'. Note that also if a move is not
2199 // extended, as example because the corresponding UCI option is set to zero,
2200 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
2202 Depth extension(const Position& pos, Move m, bool pvNode, bool captureOrPromotion,
2203 bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous) {
2205 assert(m != MOVE_NONE);
2207 Depth result = Depth(0);
2208 *dangerous = moveIsCheck | singleEvasion | mateThreat;
2213 result += CheckExtension[pvNode];
2216 result += SingleEvasionExtension[pvNode];
2219 result += MateThreatExtension[pvNode];
2222 if (pos.type_of_piece_on(move_from(m)) == PAWN)
2224 Color c = pos.side_to_move();
2225 if (relative_rank(c, move_to(m)) == RANK_7)
2227 result += PawnPushTo7thExtension[pvNode];
2230 if (pos.pawn_is_passed(c, move_to(m)))
2232 result += PassedPawnExtension[pvNode];
2237 if ( captureOrPromotion
2238 && pos.type_of_piece_on(move_to(m)) != PAWN
2239 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
2240 - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))
2241 && !move_is_promotion(m)
2244 result += PawnEndgameExtension[pvNode];
2249 && captureOrPromotion
2250 && pos.type_of_piece_on(move_to(m)) != PAWN
2251 && pos.see_sign(m) >= 0)
2257 return Min(result, OnePly);
2261 // ok_to_do_nullmove() looks at the current position and decides whether
2262 // doing a 'null move' should be allowed. In order to avoid zugzwang
2263 // problems, null moves are not allowed when the side to move has very
2264 // little material left. Currently, the test is a bit too simple: Null
2265 // moves are avoided only when the side to move has only pawns left.
2266 // It's probably a good idea to avoid null moves in at least some more
2267 // complicated endgames, e.g. KQ vs KR. FIXME
2269 bool ok_to_do_nullmove(const Position& pos) {
2271 return pos.non_pawn_material(pos.side_to_move()) != Value(0);
2275 // ok_to_prune() tests whether it is safe to forward prune a move. Only
2276 // non-tactical moves late in the move list close to the leaves are
2277 // candidates for pruning.
2279 bool ok_to_prune(const Position& pos, Move m, Move threat) {
2281 assert(move_is_ok(m));
2282 assert(threat == MOVE_NONE || move_is_ok(threat));
2283 assert(!pos.move_is_check(m));
2284 assert(!pos.move_is_capture_or_promotion(m));
2285 assert(!pos.move_is_passed_pawn_push(m));
2287 Square mfrom, mto, tfrom, tto;
2289 // Prune if there isn't any threat move
2290 if (threat == MOVE_NONE)
2293 mfrom = move_from(m);
2295 tfrom = move_from(threat);
2296 tto = move_to(threat);
2298 // Case 1: Don't prune moves which move the threatened piece
2302 // Case 2: If the threatened piece has value less than or equal to the
2303 // value of the threatening piece, don't prune move which defend it.
2304 if ( pos.move_is_capture(threat)
2305 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
2306 || pos.type_of_piece_on(tfrom) == KING)
2307 && pos.move_attacks_square(m, tto))
2310 // Case 3: If the moving piece in the threatened move is a slider, don't
2311 // prune safe moves which block its ray.
2312 if ( piece_is_slider(pos.piece_on(tfrom))
2313 && bit_is_set(squares_between(tfrom, tto), mto)
2314 && pos.see_sign(m) >= 0)
2321 // ok_to_use_TT() returns true if a transposition table score
2322 // can be used at a given point in search.
2324 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
2326 Value v = value_from_tt(tte->value(), ply);
2328 return ( tte->depth() >= depth
2329 || v >= Max(value_mate_in(PLY_MAX), beta)
2330 || v < Min(value_mated_in(PLY_MAX), beta))
2332 && ( (is_lower_bound(tte->type()) && v >= beta)
2333 || (is_upper_bound(tte->type()) && v < beta));
2337 // refine_eval() returns the transposition table score if
2338 // possible otherwise falls back on static position evaluation.
2340 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
2345 Value v = value_from_tt(tte->value(), ply);
2347 if ( (is_lower_bound(tte->type()) && v >= defaultEval)
2348 || (is_upper_bound(tte->type()) && v < defaultEval))
2355 // update_history() registers a good move that produced a beta-cutoff
2356 // in history and marks as failures all the other moves of that ply.
2358 void update_history(const Position& pos, Move move, Depth depth,
2359 Move movesSearched[], int moveCount) {
2363 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
2365 for (int i = 0; i < moveCount - 1; i++)
2367 m = movesSearched[i];
2371 if (!pos.move_is_capture_or_promotion(m))
2372 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
2377 // update_killers() add a good move that produced a beta-cutoff
2378 // among the killer moves of that ply.
2380 void update_killers(Move m, SearchStack& ss) {
2382 if (m == ss.killers[0])
2385 for (int i = KILLER_MAX - 1; i > 0; i--)
2386 ss.killers[i] = ss.killers[i - 1];
2392 // update_gains() updates the gains table of a non-capture move given
2393 // the static position evaluation before and after the move.
2395 void update_gains(const Position& pos, Move m, Value before, Value after) {
2398 && before != VALUE_NONE
2399 && after != VALUE_NONE
2400 && pos.captured_piece() == NO_PIECE_TYPE
2401 && !move_is_castle(m)
2402 && !move_is_promotion(m))
2403 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
2407 // current_search_time() returns the number of milliseconds which have passed
2408 // since the beginning of the current search.
2410 int current_search_time() {
2412 return get_system_time() - SearchStartTime;
2416 // nps() computes the current nodes/second count.
2420 int t = current_search_time();
2421 return (t > 0 ? int((TM.nodes_searched() * 1000) / t) : 0);
2425 // poll() performs two different functions: It polls for user input, and it
2426 // looks at the time consumed so far and decides if it's time to abort the
2429 void poll(SearchStack ss[], int ply) {
2431 static int lastInfoTime;
2432 int t = current_search_time();
2437 // We are line oriented, don't read single chars
2438 std::string command;
2440 if (!std::getline(std::cin, command))
2443 if (command == "quit")
2446 PonderSearch = false;
2450 else if (command == "stop")
2453 PonderSearch = false;
2455 else if (command == "ponderhit")
2459 // Print search information
2463 else if (lastInfoTime > t)
2464 // HACK: Must be a new search where we searched less than
2465 // NodesBetweenPolls nodes during the first second of search.
2468 else if (t - lastInfoTime >= 1000)
2475 if (dbg_show_hit_rate)
2476 dbg_print_hit_rate();
2478 cout << "info nodes " << TM.nodes_searched() << " nps " << nps()
2479 << " time " << t << " hashfull " << TT.full() << endl;
2481 // We only support current line printing in single thread mode
2482 if (ShowCurrentLine && TM.active_threads() == 1)
2484 cout << "info currline";
2485 for (int p = 0; p < ply; p++)
2486 cout << " " << ss[p].currentMove;
2492 // Should we stop the search?
2496 bool stillAtFirstMove = RootMoveNumber == 1
2497 && !AspirationFailLow
2498 && t > MaxSearchTime + ExtraSearchTime;
2500 bool noMoreTime = t > AbsoluteMaxSearchTime
2501 || stillAtFirstMove;
2503 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2504 || (ExactMaxTime && t >= ExactMaxTime)
2505 || (Iteration >= 3 && MaxNodes && TM.nodes_searched() >= MaxNodes))
2510 // ponderhit() is called when the program is pondering (i.e. thinking while
2511 // it's the opponent's turn to move) in order to let the engine know that
2512 // it correctly predicted the opponent's move.
2516 int t = current_search_time();
2517 PonderSearch = false;
2519 bool stillAtFirstMove = RootMoveNumber == 1
2520 && !AspirationFailLow
2521 && t > MaxSearchTime + ExtraSearchTime;
2523 bool noMoreTime = t > AbsoluteMaxSearchTime
2524 || stillAtFirstMove;
2526 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2531 // init_ss_array() does a fast reset of the first entries of a SearchStack array
2533 void init_ss_array(SearchStack ss[]) {
2535 for (int i = 0; i < 3; i++)
2538 ss[i].initKillers();
2543 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2544 // while the program is pondering. The point is to work around a wrinkle in
2545 // the UCI protocol: When pondering, the engine is not allowed to give a
2546 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2547 // We simply wait here until one of these commands is sent, and return,
2548 // after which the bestmove and pondermove will be printed (in id_loop()).
2550 void wait_for_stop_or_ponderhit() {
2552 std::string command;
2556 if (!std::getline(std::cin, command))
2559 if (command == "quit")
2564 else if (command == "ponderhit" || command == "stop")
2570 // init_thread() is the function which is called when a new thread is
2571 // launched. It simply calls the idle_loop() function with the supplied
2572 // threadID. There are two versions of this function; one for POSIX
2573 // threads and one for Windows threads.
2575 #if !defined(_MSC_VER)
2577 void* init_thread(void *threadID) {
2579 TM.idle_loop(*(int*)threadID, NULL);
2585 DWORD WINAPI init_thread(LPVOID threadID) {
2587 TM.idle_loop(*(int*)threadID, NULL);
2594 /// The ThreadsManager class
2596 // resetNodeCounters(), resetBetaCounters(), searched_nodes() and
2597 // get_beta_counters() are getters/setters for the per thread
2598 // counters used to sort the moves at root.
2600 void ThreadsManager::resetNodeCounters() {
2602 for (int i = 0; i < MAX_THREADS; i++)
2603 threads[i].nodes = 0ULL;
2606 void ThreadsManager::resetBetaCounters() {
2608 for (int i = 0; i < MAX_THREADS; i++)
2609 threads[i].betaCutOffs[WHITE] = threads[i].betaCutOffs[BLACK] = 0ULL;
2612 int64_t ThreadsManager::nodes_searched() const {
2614 int64_t result = 0ULL;
2615 for (int i = 0; i < ActiveThreads; i++)
2616 result += threads[i].nodes;
2621 void ThreadsManager::get_beta_counters(Color us, int64_t& our, int64_t& their) const {
2624 for (int i = 0; i < MAX_THREADS; i++)
2626 our += threads[i].betaCutOffs[us];
2627 their += threads[i].betaCutOffs[opposite_color(us)];
2632 // idle_loop() is where the threads are parked when they have no work to do.
2633 // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint
2634 // object for which the current thread is the master.
2636 void ThreadsManager::idle_loop(int threadID, SplitPoint* waitSp) {
2638 assert(threadID >= 0 && threadID < MAX_THREADS);
2642 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2643 // master should exit as last one.
2644 if (AllThreadsShouldExit)
2647 threads[threadID].state = THREAD_TERMINATED;
2651 // If we are not thinking, wait for a condition to be signaled
2652 // instead of wasting CPU time polling for work.
2653 while (AllThreadsShouldSleep || threadID >= ActiveThreads)
2656 assert(threadID != 0);
2657 threads[threadID].state = THREAD_SLEEPING;
2659 #if !defined(_MSC_VER)
2660 pthread_mutex_lock(&WaitLock);
2661 if (AllThreadsShouldSleep || threadID >= ActiveThreads)
2662 pthread_cond_wait(&WaitCond, &WaitLock);
2663 pthread_mutex_unlock(&WaitLock);
2665 WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2669 // If thread has just woken up, mark it as available
2670 if (threads[threadID].state == THREAD_SLEEPING)
2671 threads[threadID].state = THREAD_AVAILABLE;
2673 // If this thread has been assigned work, launch a search
2674 if (threads[threadID].state == THREAD_WORKISWAITING)
2676 assert(!AllThreadsShouldExit && !AllThreadsShouldSleep);
2678 threads[threadID].state = THREAD_SEARCHING;
2680 if (threads[threadID].splitPoint->pvNode)
2681 sp_search_pv(threads[threadID].splitPoint, threadID);
2683 sp_search(threads[threadID].splitPoint, threadID);
2685 assert(threads[threadID].state == THREAD_SEARCHING);
2687 threads[threadID].state = THREAD_AVAILABLE;
2690 // If this thread is the master of a split point and all threads have
2691 // finished their work at this split point, return from the idle loop.
2692 if (waitSp != NULL && waitSp->cpus == 0)
2694 assert(threads[threadID].state == THREAD_AVAILABLE);
2696 threads[threadID].state = THREAD_SEARCHING;
2703 // init_threads() is called during startup. It launches all helper threads,
2704 // and initializes the split point stack and the global locks and condition
2707 void ThreadsManager::init_threads() {
2712 #if !defined(_MSC_VER)
2713 pthread_t pthread[1];
2716 // Initialize global locks
2717 lock_init(&MPLock, NULL);
2719 // Initialize SplitPointStack locks
2720 for (i = 0; i < MAX_THREADS; i++)
2721 for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
2723 SplitPointStack[i][j].parent = NULL;
2724 lock_init(&(SplitPointStack[i][j].lock), NULL);
2727 #if !defined(_MSC_VER)
2728 pthread_mutex_init(&WaitLock, NULL);
2729 pthread_cond_init(&WaitCond, NULL);
2731 for (i = 0; i < MAX_THREADS; i++)
2732 SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0);
2735 // Will be set just before program exits to properly end the threads
2736 AllThreadsShouldExit = false;
2738 // Threads will be put to sleep as soon as created
2739 AllThreadsShouldSleep = true;
2741 // All threads except the main thread should be initialized to THREAD_AVAILABLE
2743 threads[0].state = THREAD_SEARCHING;
2744 for (i = 1; i < MAX_THREADS; i++)
2745 threads[i].state = THREAD_AVAILABLE;
2747 // Launch the helper threads
2748 for (i = 1; i < MAX_THREADS; i++)
2751 #if !defined(_MSC_VER)
2752 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&i)) == 0);
2755 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID) != NULL);
2760 cout << "Failed to create thread number " << i << endl;
2761 Application::exit_with_failure();
2764 // Wait until the thread has finished launching and is gone to sleep
2765 while (threads[i].state != THREAD_SLEEPING);
2770 // exit_threads() is called when the program exits. It makes all the
2771 // helper threads exit cleanly.
2773 void ThreadsManager::exit_threads() {
2775 ActiveThreads = MAX_THREADS; // HACK
2776 AllThreadsShouldSleep = true; // HACK
2777 wake_sleeping_threads();
2779 // This makes the threads to exit idle_loop()
2780 AllThreadsShouldExit = true;
2782 // Wait for thread termination
2783 for (int i = 1; i < MAX_THREADS; i++)
2784 while (threads[i].state != THREAD_TERMINATED);
2786 // Now we can safely destroy the locks
2787 for (int i = 0; i < MAX_THREADS; i++)
2788 for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
2789 lock_destroy(&(SplitPointStack[i][j].lock));
2793 // thread_should_stop() checks whether the thread should stop its search.
2794 // This can happen if a beta cutoff has occurred in the thread's currently
2795 // active split point, or in some ancestor of the current split point.
2797 bool ThreadsManager::thread_should_stop(int threadID) const {
2799 assert(threadID >= 0 && threadID < ActiveThreads);
2803 for (sp = threads[threadID].splitPoint; sp && !sp->stopRequest; sp = sp->parent);
2808 // thread_is_available() checks whether the thread with threadID "slave" is
2809 // available to help the thread with threadID "master" at a split point. An
2810 // obvious requirement is that "slave" must be idle. With more than two
2811 // threads, this is not by itself sufficient: If "slave" is the master of
2812 // some active split point, it is only available as a slave to the other
2813 // threads which are busy searching the split point at the top of "slave"'s
2814 // split point stack (the "helpful master concept" in YBWC terminology).
2816 bool ThreadsManager::thread_is_available(int slave, int master) const {
2818 assert(slave >= 0 && slave < ActiveThreads);
2819 assert(master >= 0 && master < ActiveThreads);
2820 assert(ActiveThreads > 1);
2822 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2825 // Make a local copy to be sure doesn't change under our feet
2826 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2828 if (localActiveSplitPoints == 0)
2829 // No active split points means that the thread is available as
2830 // a slave for any other thread.
2833 if (ActiveThreads == 2)
2836 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2837 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2838 // could have been set to 0 by another thread leading to an out of bound access.
2839 if (SplitPointStack[slave][localActiveSplitPoints - 1].slaves[master])
2846 // available_thread_exists() tries to find an idle thread which is available as
2847 // a slave for the thread with threadID "master".
2849 bool ThreadsManager::available_thread_exists(int master) const {
2851 assert(master >= 0 && master < ActiveThreads);
2852 assert(ActiveThreads > 1);
2854 for (int i = 0; i < ActiveThreads; i++)
2855 if (thread_is_available(i, master))
2862 // split() does the actual work of distributing the work at a node between
2863 // several threads at PV nodes. If it does not succeed in splitting the
2864 // node (because no idle threads are available, or because we have no unused
2865 // split point objects), the function immediately returns false. If
2866 // splitting is possible, a SplitPoint object is initialized with all the
2867 // data that must be copied to the helper threads (the current position and
2868 // search stack, alpha, beta, the search depth, etc.), and we tell our
2869 // helper threads that they have been assigned work. This will cause them
2870 // to instantly leave their idle loops and call sp_search_pv(). When all
2871 // threads have returned from sp_search_pv (or, equivalently, when
2872 // splitPoint->cpus becomes 0), split() returns true.
2874 bool ThreadsManager::split(const Position& p, SearchStack* sstck, int ply,
2875 Value* alpha, const Value beta, Value* bestValue,
2876 Depth depth, int* moves, MovePicker* mp, int master, bool pvNode) {
2879 assert(sstck != NULL);
2880 assert(ply >= 0 && ply < PLY_MAX);
2881 assert(*bestValue >= -VALUE_INFINITE);
2882 assert( ( pvNode && *bestValue <= *alpha)
2883 || (!pvNode && *bestValue < beta ));
2884 assert(!pvNode || *alpha < beta);
2885 assert(beta <= VALUE_INFINITE);
2886 assert(depth > Depth(0));
2887 assert(master >= 0 && master < ActiveThreads);
2888 assert(ActiveThreads > 1);
2890 SplitPoint* splitPoint;
2894 // If no other thread is available to help us, or if we have too many
2895 // active split points, don't split.
2896 if ( !available_thread_exists(master)
2897 || threads[master].activeSplitPoints >= ACTIVE_SPLIT_POINTS_MAX)
2899 lock_release(&MPLock);
2903 // Pick the next available split point object from the split point stack
2904 splitPoint = &SplitPointStack[master][threads[master].activeSplitPoints];
2906 // Initialize the split point object
2907 splitPoint->parent = threads[master].splitPoint;
2908 splitPoint->stopRequest = false;
2909 splitPoint->ply = ply;
2910 splitPoint->depth = depth;
2911 splitPoint->alpha = pvNode ? *alpha : beta - 1;
2912 splitPoint->beta = beta;
2913 splitPoint->pvNode = pvNode;
2914 splitPoint->bestValue = *bestValue;
2915 splitPoint->master = master;
2916 splitPoint->mp = mp;
2917 splitPoint->moves = *moves;
2918 splitPoint->cpus = 1;
2919 splitPoint->pos = &p;
2920 splitPoint->parentSstack = sstck;
2921 for (int i = 0; i < ActiveThreads; i++)
2922 splitPoint->slaves[i] = 0;
2924 threads[master].splitPoint = splitPoint;
2925 threads[master].activeSplitPoints++;
2927 // If we are here it means we are not available
2928 assert(threads[master].state != THREAD_AVAILABLE);
2930 // Allocate available threads setting state to THREAD_BOOKED
2931 for (int i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint; i++)
2932 if (thread_is_available(i, master))
2934 threads[i].state = THREAD_BOOKED;
2935 threads[i].splitPoint = splitPoint;
2936 splitPoint->slaves[i] = 1;
2940 assert(splitPoint->cpus > 1);
2942 // We can release the lock because slave threads are already booked and master is not available
2943 lock_release(&MPLock);
2945 // Tell the threads that they have work to do. This will make them leave
2946 // their idle loop. But before copy search stack tail for each thread.
2947 for (int i = 0; i < ActiveThreads; i++)
2948 if (i == master || splitPoint->slaves[i])
2950 memcpy(splitPoint->sstack[i] + ply - 1, sstck + ply - 1, 4 * sizeof(SearchStack));
2952 assert(i == master || threads[i].state == THREAD_BOOKED);
2954 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2957 // Everything is set up. The master thread enters the idle loop, from
2958 // which it will instantly launch a search, because its state is
2959 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2960 // idle loop, which means that the main thread will return from the idle
2961 // loop when all threads have finished their work at this split point
2962 // (i.e. when splitPoint->cpus == 0).
2963 idle_loop(master, splitPoint);
2965 // We have returned from the idle loop, which means that all threads are
2966 // finished. Update alpha, beta and bestValue, and return.
2970 *alpha = splitPoint->alpha;
2972 *bestValue = splitPoint->bestValue;
2973 threads[master].activeSplitPoints--;
2974 threads[master].splitPoint = splitPoint->parent;
2976 lock_release(&MPLock);
2981 // wake_sleeping_threads() wakes up all sleeping threads when it is time
2982 // to start a new search from the root.
2984 void ThreadsManager::wake_sleeping_threads() {
2986 assert(AllThreadsShouldSleep);
2987 assert(ActiveThreads > 0);
2989 AllThreadsShouldSleep = false;
2991 if (ActiveThreads == 1)
2994 for (int i = 1; i < ActiveThreads; i++)
2995 assert(threads[i].state == THREAD_SLEEPING);
2997 #if !defined(_MSC_VER)
2998 pthread_mutex_lock(&WaitLock);
2999 pthread_cond_broadcast(&WaitCond);
3000 pthread_mutex_unlock(&WaitLock);
3002 for (int i = 1; i < MAX_THREADS; i++)
3003 SetEvent(SitIdleEvent[i]);
3009 // put_threads_to_sleep() makes all the threads go to sleep just before
3010 // to leave think(), at the end of the search. Threads should have already
3011 // finished the job and should be idle.
3013 void ThreadsManager::put_threads_to_sleep() {
3015 assert(!AllThreadsShouldSleep);
3017 // This makes the threads to go to sleep
3018 AllThreadsShouldSleep = true;
3021 /// The RootMoveList class
3023 // RootMoveList c'tor
3025 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
3027 SearchStack ss[PLY_MAX_PLUS_2];
3028 MoveStack mlist[MaxRootMoves];
3030 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
3032 // Generate all legal moves
3033 MoveStack* last = generate_moves(pos, mlist);
3035 // Add each move to the moves[] array
3036 for (MoveStack* cur = mlist; cur != last; cur++)
3038 bool includeMove = includeAllMoves;
3040 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
3041 includeMove = (searchMoves[k] == cur->move);
3046 // Find a quick score for the move
3048 pos.do_move(cur->move, st);
3049 moves[count].move = cur->move;
3050 moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0);
3051 moves[count].pv[0] = cur->move;
3052 moves[count].pv[1] = MOVE_NONE;
3053 pos.undo_move(cur->move);
3060 // RootMoveList simple methods definitions
3062 void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
3064 moves[moveNum].nodes = nodes;
3065 moves[moveNum].cumulativeNodes += nodes;
3068 void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
3070 moves[moveNum].ourBeta = our;
3071 moves[moveNum].theirBeta = their;
3074 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
3078 for (j = 0; pv[j] != MOVE_NONE; j++)
3079 moves[moveNum].pv[j] = pv[j];
3081 moves[moveNum].pv[j] = MOVE_NONE;
3085 // RootMoveList::sort() sorts the root move list at the beginning of a new
3088 void RootMoveList::sort() {
3090 sort_multipv(count - 1); // Sort all items
3094 // RootMoveList::sort_multipv() sorts the first few moves in the root move
3095 // list by their scores and depths. It is used to order the different PVs
3096 // correctly in MultiPV mode.
3098 void RootMoveList::sort_multipv(int n) {
3102 for (i = 1; i <= n; i++)
3104 RootMove rm = moves[i];
3105 for (j = i; j > 0 && moves[j - 1] < rm; j--)
3106 moves[j] = moves[j - 1];