2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad
6 Stockfish is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 Stockfish is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
43 #include "ucioption.h"
49 //// Local definitions
55 enum NodeType { NonPV, PV };
57 // Set to true to force running with one thread.
58 // Used for debugging SMP code.
59 const bool FakeSplit = false;
61 // ThreadsManager class is used to handle all the threads related stuff in search,
62 // init, starting, parking and, the most important, launching a slave thread at a
63 // split point are what this class does. All the access to shared thread data is
64 // done through this class, so that we avoid using global variables instead.
66 class ThreadsManager {
67 /* As long as the single ThreadsManager object is defined as a global we don't
68 need to explicitly initialize to zero its data members because variables with
69 static storage duration are automatically set to zero before enter main()
75 int active_threads() const { return ActiveThreads; }
76 void set_active_threads(int newActiveThreads) { ActiveThreads = newActiveThreads; }
77 void incrementNodeCounter(int threadID) { threads[threadID].nodes++; }
78 void incrementBetaCounter(Color us, Depth d, int threadID) { threads[threadID].betaCutOffs[us] += unsigned(d); }
80 void resetNodeCounters();
81 void resetBetaCounters();
82 int64_t nodes_searched() const;
83 void get_beta_counters(Color us, int64_t& our, int64_t& their) const;
84 bool available_thread_exists(int master) const;
85 bool thread_is_available(int slave, int master) const;
86 bool thread_should_stop(int threadID) const;
87 void wake_sleeping_threads();
88 void put_threads_to_sleep();
89 void idle_loop(int threadID, SplitPoint* sp);
92 void split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
93 Depth depth, Move threatMove, bool mateThreat, int* moveCount, MovePicker* mp, bool pvNode);
99 volatile bool AllThreadsShouldExit, AllThreadsShouldSleep;
100 Thread threads[MAX_THREADS];
102 Lock MPLock, WaitLock;
104 #if !defined(_MSC_VER)
105 pthread_cond_t WaitCond;
107 HANDLE SitIdleEvent[MAX_THREADS];
113 // RootMove struct is used for moves at the root at the tree. For each
114 // root move, we store a score, a node count, and a PV (really a refutation
115 // in the case of moves which fail low).
119 RootMove() { nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL; }
121 // RootMove::operator<() is the comparison function used when
122 // sorting the moves. A move m1 is considered to be better
123 // than a move m2 if it has a higher score, or if the moves
124 // have equal score but m1 has the higher beta cut-off count.
125 bool operator<(const RootMove& m) const {
127 return score != m.score ? score < m.score : theirBeta <= m.theirBeta;
132 int64_t nodes, cumulativeNodes, ourBeta, theirBeta;
133 Move pv[PLY_MAX_PLUS_2];
137 // The RootMoveList class is essentially an array of RootMove objects, with
138 // a handful of methods for accessing the data in the individual moves.
143 RootMoveList(Position& pos, Move searchMoves[]);
145 int move_count() const { return count; }
146 Move get_move(int moveNum) const { return moves[moveNum].move; }
147 Value get_move_score(int moveNum) const { return moves[moveNum].score; }
148 void set_move_score(int moveNum, Value score) { moves[moveNum].score = score; }
149 Move get_move_pv(int moveNum, int i) const { return moves[moveNum].pv[i]; }
150 int64_t get_move_cumulative_nodes(int moveNum) const { return moves[moveNum].cumulativeNodes; }
152 void set_move_nodes(int moveNum, int64_t nodes);
153 void set_beta_counters(int moveNum, int64_t our, int64_t their);
154 void set_move_pv(int moveNum, const Move pv[]);
156 void sort_multipv(int n);
159 static const int MaxRootMoves = 500;
160 RootMove moves[MaxRootMoves];
169 // Maximum depth for razoring
170 const Depth RazorDepth = 4 * OnePly;
172 // Dynamic razoring margin based on depth
173 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
175 // Step 8. Null move search with verification search
177 // Null move margin. A null move search will not be done if the static
178 // evaluation of the position is more than NullMoveMargin below beta.
179 const Value NullMoveMargin = Value(0x200);
181 // Maximum depth for use of dynamic threat detection when null move fails low
182 const Depth ThreatDepth = 5 * OnePly;
184 // Step 9. Internal iterative deepening
186 // Minimum depth for use of internal iterative deepening
187 const Depth IIDDepth[2] = { 8 * OnePly /* non-PV */, 5 * OnePly /* PV */};
189 // At Non-PV nodes we do an internal iterative deepening search
190 // when the static evaluation is bigger then beta - IIDMargin.
191 const Value IIDMargin = Value(0x100);
193 // Step 11. Decide the new search depth
195 // Extensions. Configurable UCI options
196 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
197 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
198 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
200 // Minimum depth for use of singular extension
201 const Depth SingularExtensionDepth[2] = { 7 * OnePly /* non-PV */, 6 * OnePly /* PV */};
203 // If the TT move is at least SingularExtensionMargin better then the
204 // remaining ones we will extend it.
205 const Value SingularExtensionMargin = Value(0x20);
207 // Step 12. Futility pruning
209 // Futility margin for quiescence search
210 const Value FutilityMarginQS = Value(0x80);
212 // Futility lookup tables (initialized at startup) and their getter functions
213 int32_t FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
214 int FutilityMoveCountArray[32]; // [depth]
216 inline Value futility_margin(Depth d, int mn) { return Value(d < 7 * OnePly ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE); }
217 inline int futility_move_count(Depth d) { return d < 16 * OnePly ? FutilityMoveCountArray[d] : 512; }
219 // Step 14. Reduced search
221 // Reduction lookup tables (initialized at startup) and their getter functions
222 int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
224 template <NodeType PV>
225 inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
227 // Common adjustments
229 // Search depth at iteration 1
230 const Depth InitialDepth = OnePly;
232 // Easy move margin. An easy move candidate must be at least this much
233 // better than the second best move.
234 const Value EasyMoveMargin = Value(0x200);
242 // Scores and number of times the best move changed for each iteration
243 Value ValueByIteration[PLY_MAX_PLUS_2];
244 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
246 // Search window management
252 // Time managment variables
253 int SearchStartTime, MaxNodes, MaxDepth, MaxSearchTime;
254 int AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
255 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
256 bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
260 std::ofstream LogFile;
262 // Multi-threads related variables
263 Depth MinimumSplitDepth;
264 int MaxThreadsPerSplitPoint;
267 // Node counters, used only by thread[0] but try to keep in different cache
268 // lines (64 bytes each) from the heavy multi-thread read accessed variables.
270 int NodesBetweenPolls = 30000;
277 Value id_loop(const Position& pos, Move searchMoves[]);
278 Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
280 template <NodeType PvNode>
281 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
283 template <NodeType PvNode>
284 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
286 template <NodeType PvNode>
287 void sp_search(SplitPoint* sp, int threadID);
289 template <NodeType PvNode>
290 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
292 bool connected_moves(const Position& pos, Move m1, Move m2);
293 bool value_is_mate(Value value);
294 Value value_to_tt(Value v, int ply);
295 Value value_from_tt(Value v, int ply);
296 bool move_is_killer(Move m, SearchStack* ss);
297 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
298 bool connected_threat(const Position& pos, Move m, Move threat);
299 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
300 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
301 void update_killers(Move m, SearchStack* ss);
302 void update_gains(const Position& pos, Move move, Value before, Value after);
304 int current_search_time();
305 std::string value_to_uci(Value v);
309 void wait_for_stop_or_ponderhit();
310 void init_ss_array(SearchStack* ss, int size);
311 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value);
312 void insert_pv_in_tt(const Position& pos, Move pv[]);
313 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]);
315 #if !defined(_MSC_VER)
316 void *init_thread(void *threadID);
318 DWORD WINAPI init_thread(LPVOID threadID);
328 /// init_threads(), exit_threads() and nodes_searched() are helpers to
329 /// give accessibility to some TM methods from outside of current file.
331 void init_threads() { TM.init_threads(); }
332 void exit_threads() { TM.exit_threads(); }
333 int64_t nodes_searched() { return TM.nodes_searched(); }
336 /// init_search() is called during startup. It initializes various lookup tables
340 int d; // depth (OnePly == 2)
341 int hd; // half depth (OnePly == 1)
344 // Init reductions array
345 for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
347 double pvRed = 0.33 + log(double(hd)) * log(double(mc)) / 4.5;
348 double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
349 ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0);
350 ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0);
353 // Init futility margins array
354 for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
355 FutilityMarginsMatrix[d][mc] = 112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45;
357 // Init futility move count array
358 for (d = 0; d < 32; d++)
359 FutilityMoveCountArray[d] = 3 + (1 << (3 * d / 8));
363 /// perft() is our utility to verify move generation is bug free. All the legal
364 /// moves up to given depth are generated and counted and the sum returned.
366 int perft(Position& pos, Depth depth)
371 MovePicker mp(pos, MOVE_NONE, depth, H);
373 // If we are at the last ply we don't need to do and undo
374 // the moves, just to count them.
375 if (depth <= OnePly) // Replace with '<' to test also qsearch
377 while (mp.get_next_move()) sum++;
381 // Loop through all legal moves
383 while ((move = mp.get_next_move()) != MOVE_NONE)
385 pos.do_move(move, st, ci, pos.move_is_check(move, ci));
386 sum += perft(pos, depth - OnePly);
393 /// think() is the external interface to Stockfish's search, and is called when
394 /// the program receives the UCI 'go' command. It initializes various
395 /// search-related global variables, and calls root_search(). It returns false
396 /// when a quit command is received during the search.
398 bool think(const Position& pos, bool infinite, bool ponder, int time[], int increment[],
399 int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) {
401 // Initialize global search variables
402 StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
403 MaxSearchTime = AbsoluteMaxSearchTime = ExtraSearchTime = 0;
405 TM.resetNodeCounters();
406 SearchStartTime = get_system_time();
407 ExactMaxTime = maxTime;
410 InfiniteSearch = infinite;
411 PonderSearch = ponder;
412 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
414 // Look for a book move, only during games, not tests
415 if (UseTimeManagement && get_option_value_bool("OwnBook"))
417 if (get_option_value_string("Book File") != OpeningBook.file_name())
418 OpeningBook.open(get_option_value_string("Book File"));
420 Move bookMove = OpeningBook.get_move(pos, get_option_value_bool("Best Book Move"));
421 if (bookMove != MOVE_NONE)
424 wait_for_stop_or_ponderhit();
426 cout << "bestmove " << bookMove << endl;
431 // Read UCI option values
432 TT.set_size(get_option_value_int("Hash"));
433 if (button_was_pressed("Clear Hash"))
436 CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)"));
437 CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)"));
438 SingleEvasionExtension[1] = Depth(get_option_value_int("Single Evasion Extension (PV nodes)"));
439 SingleEvasionExtension[0] = Depth(get_option_value_int("Single Evasion Extension (non-PV nodes)"));
440 PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)"));
441 PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
442 PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
443 PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
444 PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
445 PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)"));
446 MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
447 MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
449 MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly;
450 MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point");
451 MultiPV = get_option_value_int("MultiPV");
452 Chess960 = get_option_value_bool("UCI_Chess960");
453 UseLogFile = get_option_value_bool("Use Search Log");
456 LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app);
458 read_weights(pos.side_to_move());
460 // Set the number of active threads
461 int newActiveThreads = get_option_value_int("Threads");
462 if (newActiveThreads != TM.active_threads())
464 TM.set_active_threads(newActiveThreads);
465 init_eval(TM.active_threads());
468 // Wake up sleeping threads
469 TM.wake_sleeping_threads();
472 int myTime = time[pos.side_to_move()];
473 int myIncrement = increment[pos.side_to_move()];
474 if (UseTimeManagement)
476 if (!movesToGo) // Sudden death time control
480 MaxSearchTime = myTime / 30 + myIncrement;
481 AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
483 else // Blitz game without increment
485 MaxSearchTime = myTime / 30;
486 AbsoluteMaxSearchTime = myTime / 8;
489 else // (x moves) / (y minutes)
493 MaxSearchTime = myTime / 2;
494 AbsoluteMaxSearchTime = (myTime > 3000)? (myTime - 500) : ((myTime * 3) / 4);
498 MaxSearchTime = myTime / Min(movesToGo, 20);
499 AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
503 if (get_option_value_bool("Ponder"))
505 MaxSearchTime += MaxSearchTime / 4;
506 MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime);
510 // Set best NodesBetweenPolls interval to avoid lagging under
511 // heavy time pressure.
513 NodesBetweenPolls = Min(MaxNodes, 30000);
514 else if (myTime && myTime < 1000)
515 NodesBetweenPolls = 1000;
516 else if (myTime && myTime < 5000)
517 NodesBetweenPolls = 5000;
519 NodesBetweenPolls = 30000;
521 // Write search information to log file
523 LogFile << "Searching: " << pos.to_fen() << endl
524 << "infinite: " << infinite
525 << " ponder: " << ponder
526 << " time: " << myTime
527 << " increment: " << myIncrement
528 << " moves to go: " << movesToGo << endl;
530 // We're ready to start thinking. Call the iterative deepening loop function
531 id_loop(pos, searchMoves);
536 TM.put_threads_to_sleep();
544 // id_loop() is the main iterative deepening loop. It calls root_search
545 // repeatedly with increasing depth until the allocated thinking time has
546 // been consumed, the user stops the search, or the maximum search depth is
549 Value id_loop(const Position& pos, Move searchMoves[]) {
551 Position p(pos, pos.thread());
552 SearchStack ss[PLY_MAX_PLUS_2];
553 Move pv[PLY_MAX_PLUS_2];
554 Move EasyMove = MOVE_NONE;
555 Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
557 // Moves to search are verified, copied, scored and sorted
558 RootMoveList rml(p, searchMoves);
560 // Handle special case of searching on a mate/stale position
561 if (rml.move_count() == 0)
564 wait_for_stop_or_ponderhit();
566 return pos.is_check() ? -VALUE_MATE : VALUE_DRAW;
569 // Print RootMoveList startup scoring to the standard output,
570 // so to output information also for iteration 1.
571 cout << "info depth " << 1
572 << "\ninfo depth " << 1
573 << " score " << value_to_uci(rml.get_move_score(0))
574 << " time " << current_search_time()
575 << " nodes " << TM.nodes_searched()
577 << " pv " << rml.get_move(0) << "\n";
582 init_ss_array(ss, PLY_MAX_PLUS_2);
583 pv[0] = pv[1] = MOVE_NONE;
584 ValueByIteration[1] = rml.get_move_score(0);
587 // Is one move significantly better than others after initial scoring ?
588 if ( rml.move_count() == 1
589 || rml.get_move_score(0) > rml.get_move_score(1) + EasyMoveMargin)
590 EasyMove = rml.get_move(0);
592 // Iterative deepening loop
593 while (Iteration < PLY_MAX)
595 // Initialize iteration
597 BestMoveChangesByIteration[Iteration] = 0;
599 cout << "info depth " << Iteration << endl;
601 // Calculate dynamic aspiration window based on previous iterations
602 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
604 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
605 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
607 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
608 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
610 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
611 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
614 // Search to the current depth, rml is updated and sorted, alpha and beta could change
615 value = root_search(p, ss, pv, rml, &alpha, &beta);
617 // Write PV to transposition table, in case the relevant entries have
618 // been overwritten during the search.
619 insert_pv_in_tt(p, pv);
622 break; // Value cannot be trusted. Break out immediately!
624 //Save info about search result
625 ValueByIteration[Iteration] = value;
627 // Drop the easy move if differs from the new best move
628 if (pv[0] != EasyMove)
629 EasyMove = MOVE_NONE;
631 if (UseTimeManagement)
634 bool stopSearch = false;
636 // Stop search early if there is only a single legal move,
637 // we search up to Iteration 6 anyway to get a proper score.
638 if (Iteration >= 6 && rml.move_count() == 1)
641 // Stop search early when the last two iterations returned a mate score
643 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
644 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
647 // Stop search early if one move seems to be much better than the others
648 int64_t nodes = TM.nodes_searched();
651 && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
652 && current_search_time() > MaxSearchTime / 16)
653 ||( rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100
654 && current_search_time() > MaxSearchTime / 32)))
657 // Add some extra time if the best move has changed during the last two iterations
658 if (Iteration > 5 && Iteration <= 50)
659 ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2)
660 + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3);
662 // Stop search if most of MaxSearchTime is consumed at the end of the
663 // iteration. We probably don't have enough time to search the first
664 // move at the next iteration anyway.
665 if (current_search_time() > ((MaxSearchTime + ExtraSearchTime) * 80) / 128)
671 StopOnPonderhit = true;
677 if (MaxDepth && Iteration >= MaxDepth)
681 // If we are pondering or in infinite search, we shouldn't print the
682 // best move before we are told to do so.
683 if (!AbortSearch && (PonderSearch || InfiniteSearch))
684 wait_for_stop_or_ponderhit();
686 // Print final search statistics
687 cout << "info nodes " << TM.nodes_searched()
689 << " time " << current_search_time() << endl;
691 // Print the best move and the ponder move to the standard output
692 if (pv[0] == MOVE_NONE)
694 pv[0] = rml.get_move(0);
698 assert(pv[0] != MOVE_NONE);
700 cout << "bestmove " << pv[0];
702 if (pv[1] != MOVE_NONE)
703 cout << " ponder " << pv[1];
710 dbg_print_mean(LogFile);
712 if (dbg_show_hit_rate)
713 dbg_print_hit_rate(LogFile);
715 LogFile << "\nNodes: " << TM.nodes_searched()
716 << "\nNodes/second: " << nps()
717 << "\nBest move: " << move_to_san(p, pv[0]);
720 p.do_move(pv[0], st);
721 LogFile << "\nPonder move: "
722 << move_to_san(p, pv[1]) // Works also with MOVE_NONE
725 return rml.get_move_score(0);
729 // root_search() is the function which searches the root node. It is
730 // similar to search_pv except that it uses a different move ordering
731 // scheme, prints some information to the standard output and handles
732 // the fail low/high loops.
734 Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
741 Depth depth, ext, newDepth;
742 Value value, alpha, beta;
743 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
744 int researchCountFH, researchCountFL;
746 researchCountFH = researchCountFL = 0;
749 isCheck = pos.is_check();
751 // Step 1. Initialize node (polling is omitted at root)
752 ss->currentMove = ss->bestMove = MOVE_NONE;
754 // Step 2. Check for aborted search (omitted at root)
755 // Step 3. Mate distance pruning (omitted at root)
756 // Step 4. Transposition table lookup (omitted at root)
758 // Step 5. Evaluate the position statically
759 // At root we do this only to get reference value for child nodes
760 ss->eval = isCheck ? VALUE_NONE : evaluate(pos, ei);
762 // Step 6. Razoring (omitted at root)
763 // Step 7. Static null move pruning (omitted at root)
764 // Step 8. Null move search with verification search (omitted at root)
765 // Step 9. Internal iterative deepening (omitted at root)
767 // Step extra. Fail low loop
768 // We start with small aspiration window and in case of fail low, we research
769 // with bigger window until we are not failing low anymore.
772 // Sort the moves before to (re)search
775 // Step 10. Loop through all moves in the root move list
776 for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
778 // This is used by time management
779 FirstRootMove = (i == 0);
781 // Save the current node count before the move is searched
782 nodes = TM.nodes_searched();
784 // Reset beta cut-off counters
785 TM.resetBetaCounters();
787 // Pick the next root move, and print the move and the move number to
788 // the standard output.
789 move = ss->currentMove = rml.get_move(i);
791 if (current_search_time() >= 1000)
792 cout << "info currmove " << move
793 << " currmovenumber " << i + 1 << endl;
795 moveIsCheck = pos.move_is_check(move);
796 captureOrPromotion = pos.move_is_capture_or_promotion(move);
798 // Step 11. Decide the new search depth
799 depth = (Iteration - 2) * OnePly + InitialDepth;
800 ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
801 newDepth = depth + ext;
803 // Step 12. Futility pruning (omitted at root)
805 // Step extra. Fail high loop
806 // If move fails high, we research with bigger window until we are not failing
808 value = - VALUE_INFINITE;
812 // Step 13. Make the move
813 pos.do_move(move, st, ci, moveIsCheck);
815 // Step extra. pv search
816 // We do pv search for first moves (i < MultiPV)
817 // and for fail high research (value > alpha)
818 if (i < MultiPV || value > alpha)
820 // Aspiration window is disabled in multi-pv case
822 alpha = -VALUE_INFINITE;
824 // Full depth PV search, done on first move or after a fail high
825 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
829 // Step 14. Reduced search
830 // if the move fails high will be re-searched at full depth
831 bool doFullDepthSearch = true;
833 if ( depth >= 3 * OnePly
835 && !captureOrPromotion
836 && !move_is_castle(move))
838 ss->reduction = reduction<PV>(depth, i - MultiPV + 2);
841 assert(newDepth-ss->reduction >= OnePly);
843 // Reduced depth non-pv search using alpha as upperbound
844 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
845 doFullDepthSearch = (value > alpha);
848 // The move failed high, but if reduction is very big we could
849 // face a false positive, retry with a less aggressive reduction,
850 // if the move fails high again then go with full depth search.
851 if (doFullDepthSearch && ss->reduction > 2 * OnePly)
853 assert(newDepth - OnePly >= OnePly);
855 ss->reduction = OnePly;
856 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
857 doFullDepthSearch = (value > alpha);
859 ss->reduction = Depth(0); // Restore original reduction
862 // Step 15. Full depth search
863 if (doFullDepthSearch)
865 // Full depth non-pv search using alpha as upperbound
866 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, 1);
868 // If we are above alpha then research at same depth but as PV
869 // to get a correct score or eventually a fail high above beta.
871 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
875 // Step 16. Undo move
878 // Can we exit fail high loop ?
879 if (AbortSearch || value < beta)
882 // We are failing high and going to do a research. It's important to update
883 // the score before research in case we run out of time while researching.
884 rml.set_move_score(i, value);
886 extract_pv_from_tt(pos, move, pv);
887 rml.set_move_pv(i, pv);
889 // Print information to the standard output
890 print_pv_info(pos, pv, alpha, beta, value);
892 // Prepare for a research after a fail high, each time with a wider window
893 *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
896 } // End of fail high loop
898 // Finished searching the move. If AbortSearch is true, the search
899 // was aborted because the user interrupted the search or because we
900 // ran out of time. In this case, the return value of the search cannot
901 // be trusted, and we break out of the loop without updating the best
906 // Remember beta-cutoff and searched nodes counts for this move. The
907 // info is used to sort the root moves for the next iteration.
909 TM.get_beta_counters(pos.side_to_move(), our, their);
910 rml.set_beta_counters(i, our, their);
911 rml.set_move_nodes(i, TM.nodes_searched() - nodes);
913 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
914 assert(value < beta);
916 // Step 17. Check for new best move
917 if (value <= alpha && i >= MultiPV)
918 rml.set_move_score(i, -VALUE_INFINITE);
921 // PV move or new best move!
924 rml.set_move_score(i, value);
926 extract_pv_from_tt(pos, move, pv);
927 rml.set_move_pv(i, pv);
931 // We record how often the best move has been changed in each
932 // iteration. This information is used for time managment: When
933 // the best move changes frequently, we allocate some more time.
935 BestMoveChangesByIteration[Iteration]++;
937 // Print information to the standard output
938 print_pv_info(pos, pv, alpha, beta, value);
940 // Raise alpha to setup proper non-pv search upper bound
947 for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
949 cout << "info multipv " << j + 1
950 << " score " << value_to_uci(rml.get_move_score(j))
951 << " depth " << (j <= i ? Iteration : Iteration - 1)
952 << " time " << current_search_time()
953 << " nodes " << TM.nodes_searched()
957 for (int k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
958 cout << rml.get_move_pv(j, k) << " ";
962 alpha = rml.get_move_score(Min(i, MultiPV - 1));
964 } // PV move or new best move
966 assert(alpha >= *alphaPtr);
968 AspirationFailLow = (alpha == *alphaPtr);
970 if (AspirationFailLow && StopOnPonderhit)
971 StopOnPonderhit = false;
974 // Can we exit fail low loop ?
975 if (AbortSearch || !AspirationFailLow)
978 // Prepare for a research after a fail low, each time with a wider window
979 *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
984 // Sort the moves before to return
991 // search<>() is the main search function for both PV and non-PV nodes
993 template <NodeType PvNode>
994 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
996 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
997 assert(beta > alpha && beta <= VALUE_INFINITE);
998 assert(PvNode || alpha == beta - 1);
999 assert(ply > 0 && ply < PLY_MAX);
1000 assert(pos.thread() >= 0 && pos.thread() < TM.active_threads());
1002 Move movesSearched[256];
1007 Move ttMove, move, excludedMove, threatMove;
1008 Depth ext, newDepth;
1009 Value bestValue, value, oldAlpha;
1010 Value refinedValue, nullValue, futilityValueScaled; // Non-PV specific
1011 bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
1012 bool mateThreat = false;
1014 int threadID = pos.thread();
1015 refinedValue = bestValue = value = -VALUE_INFINITE;
1018 // Step 1. Initialize node and poll. Polling can abort search
1019 TM.incrementNodeCounter(threadID);
1020 ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
1021 (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
1023 if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
1029 // Step 2. Check for aborted search and immediate draw
1030 if (AbortSearch || TM.thread_should_stop(threadID))
1033 if (pos.is_draw() || ply >= PLY_MAX - 1)
1036 // Step 3. Mate distance pruning
1037 alpha = Max(value_mated_in(ply), alpha);
1038 beta = Min(value_mate_in(ply+1), beta);
1042 // Step 4. Transposition table lookup
1044 // We don't want the score of a partial search to overwrite a previous full search
1045 // TT value, so we use a different position key in case of an excluded move exists.
1046 excludedMove = ss->excludedMove;
1047 posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1049 tte = TT.retrieve(posKey);
1050 ttMove = (tte ? tte->move() : MOVE_NONE);
1052 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1053 // This is to avoid problems in the following areas:
1055 // * Repetition draw detection
1056 // * Fifty move rule detection
1057 // * Searching for a mate
1058 // * Printing of full PV line
1060 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1062 // Refresh tte entry to avoid aging
1063 TT.store(posKey, tte->value(), tte->type(), tte->depth(), ttMove, tte->static_value(), tte->king_danger());
1065 ss->currentMove = ttMove; // Can be MOVE_NONE
1066 return value_from_tt(tte->value(), ply);
1069 // Step 5. Evaluate the position statically
1070 // At PV nodes we do this only to update gain statistics
1071 isCheck = pos.is_check();
1076 assert(tte->static_value() != VALUE_NONE);
1077 ss->eval = tte->static_value();
1078 ei.kingDanger[pos.side_to_move()] = tte->king_danger();
1082 ss->eval = evaluate(pos, ei);
1083 TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]);
1086 refinedValue = refine_eval(tte, ss->eval, ply); // Enhance accuracy with TT value if possible
1087 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1090 ss->eval = VALUE_NONE;
1092 // Step 6. Razoring (is omitted in PV nodes)
1094 && depth < RazorDepth
1096 && refinedValue < beta - razor_margin(depth)
1097 && ttMove == MOVE_NONE
1098 && (ss-1)->currentMove != MOVE_NULL
1099 && !value_is_mate(beta)
1100 && !pos.has_pawn_on_7th(pos.side_to_move()))
1102 Value rbeta = beta - razor_margin(depth);
1103 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, Depth(0), ply);
1105 // Logically we should return (v + razor_margin(depth)), but
1106 // surprisingly this did slightly weaker in tests.
1110 // Step 7. Static null move pruning (is omitted in PV nodes)
1111 // We're betting that the opponent doesn't have a move that will reduce
1112 // the score by more than futility_margin(depth) if we do a null move.
1114 && !ss->skipNullMove
1115 && depth < RazorDepth
1116 && refinedValue >= beta + futility_margin(depth, 0)
1118 && !value_is_mate(beta)
1119 && pos.non_pawn_material(pos.side_to_move()))
1120 return refinedValue - futility_margin(depth, 0);
1122 // Step 8. Null move search with verification search (is omitted in PV nodes)
1123 // When we jump directly to qsearch() we do a null move only if static value is
1124 // at least beta. Otherwise we do a null move if static value is not more than
1125 // NullMoveMargin under beta.
1127 && !ss->skipNullMove
1129 && refinedValue >= beta - (depth >= 4 * OnePly ? NullMoveMargin : 0)
1131 && !value_is_mate(beta)
1132 && pos.non_pawn_material(pos.side_to_move()))
1134 ss->currentMove = MOVE_NULL;
1136 // Null move dynamic reduction based on depth
1137 int R = 3 + (depth >= 5 * OnePly ? depth / 8 : 0);
1139 // Null move dynamic reduction based on value
1140 if (refinedValue - beta > PawnValueMidgame)
1143 pos.do_null_move(st);
1144 (ss+1)->skipNullMove = true;
1146 nullValue = depth-R*OnePly < OnePly ? -qsearch<NonPV>(pos, ss+1, -beta, -alpha, Depth(0), ply+1)
1147 : - search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*OnePly, ply+1);
1148 (ss+1)->skipNullMove = false;
1149 pos.undo_null_move();
1151 if (nullValue >= beta)
1153 // Do not return unproven mate scores
1154 if (nullValue >= value_mate_in(PLY_MAX))
1157 if (depth < 6 * OnePly)
1160 // Do verification search at high depths
1161 ss->skipNullMove = true;
1162 Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*OnePly, ply);
1163 ss->skipNullMove = false;
1170 // The null move failed low, which means that we may be faced with
1171 // some kind of threat. If the previous move was reduced, check if
1172 // the move that refuted the null move was somehow connected to the
1173 // move which was reduced. If a connection is found, return a fail
1174 // low score (which will cause the reduced move to fail high in the
1175 // parent node, which will trigger a re-search with full depth).
1176 if (nullValue == value_mated_in(ply + 2))
1179 threatMove = (ss+1)->currentMove;
1180 if ( depth < ThreatDepth
1181 && (ss-1)->reduction
1182 && connected_moves(pos, (ss-1)->currentMove, threatMove))
1187 // Step 9. Internal iterative deepening
1188 if ( depth >= IIDDepth[PvNode]
1189 && ttMove == MOVE_NONE
1190 && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
1192 Depth d = (PvNode ? depth - 2 * OnePly : depth / 2);
1194 ss->skipNullMove = true;
1195 search<PvNode>(pos, ss, alpha, beta, d, ply);
1196 ss->skipNullMove = false;
1198 ttMove = ss->bestMove;
1199 tte = TT.retrieve(posKey);
1202 // Expensive mate threat detection (only for PV nodes)
1204 mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move()));
1206 // Initialize a MovePicker object for the current position
1207 MovePicker mp = MovePicker(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
1209 singleEvasion = isCheck && mp.number_of_evasions() == 1;
1210 singularExtensionNode = depth >= SingularExtensionDepth[PvNode]
1211 && tte && tte->move()
1212 && !excludedMove // Do not allow recursive singular extension search
1213 && is_lower_bound(tte->type())
1214 && tte->depth() >= depth - 3 * OnePly;
1216 // Avoid to do an expensive singular extension search on nodes where
1217 // such search had already failed in the past.
1219 && singularExtensionNode
1220 && depth < SingularExtensionDepth[PvNode] + 5 * OnePly)
1222 TTEntry* ttx = TT.retrieve(pos.get_exclusion_key());
1223 if (ttx && is_lower_bound(ttx->type()))
1224 singularExtensionNode = false;
1227 // Step 10. Loop through moves
1228 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1229 while ( bestValue < beta
1230 && (move = mp.get_next_move()) != MOVE_NONE
1231 && !TM.thread_should_stop(threadID))
1233 assert(move_is_ok(move));
1235 if (move == excludedMove)
1238 moveIsCheck = pos.move_is_check(move, ci);
1239 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1241 // Step 11. Decide the new search depth
1242 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1244 // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s),
1245 // and just one fails high on (alpha, beta), then that move is singular and should be extended.
1246 // To verify this we do a reduced search on all the other moves but the ttMove, if result is
1247 // lower then ttValue minus a margin then we extend ttMove.
1248 if ( singularExtensionNode
1249 && move == tte->move()
1252 Value ttValue = value_from_tt(tte->value(), ply);
1254 if (abs(ttValue) < VALUE_KNOWN_WIN)
1256 Value b = ttValue - SingularExtensionMargin;
1257 ss->excludedMove = move;
1258 ss->skipNullMove = true;
1259 Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
1260 ss->skipNullMove = false;
1261 ss->excludedMove = MOVE_NONE;
1267 newDepth = depth - OnePly + ext;
1269 // Update current move (this must be done after singular extension search)
1270 movesSearched[moveCount++] = ss->currentMove = move;
1272 // Step 12. Futility pruning (is omitted in PV nodes)
1274 && !captureOrPromotion
1278 && !move_is_castle(move))
1280 // Move count based pruning
1281 if ( moveCount >= futility_move_count(depth)
1282 && !(threatMove && connected_threat(pos, move, threatMove))
1283 && bestValue > value_mated_in(PLY_MAX))
1286 // Value based pruning
1287 // We illogically ignore reduction condition depth >= 3*OnePly for predicted depth,
1288 // but fixing this made program slightly weaker.
1289 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1290 futilityValueScaled = ss->eval + futility_margin(predictedDepth, moveCount)
1291 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1293 if (futilityValueScaled < beta)
1295 if (futilityValueScaled > bestValue)
1296 bestValue = futilityValueScaled;
1301 // Step 13. Make the move
1302 pos.do_move(move, st, ci, moveIsCheck);
1304 // Step extra. pv search (only in PV nodes)
1305 // The first move in list is the expected PV
1306 if (PvNode && moveCount == 1)
1307 value = newDepth < OnePly ? -qsearch<PV>(pos, ss+1, -beta, -alpha, Depth(0), ply+1)
1308 : - search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1311 // Step 14. Reduced depth search
1312 // If the move fails high will be re-searched at full depth.
1313 bool doFullDepthSearch = true;
1315 if ( depth >= 3 * OnePly
1316 && !captureOrPromotion
1318 && !move_is_castle(move)
1319 && !move_is_killer(move, ss))
1321 ss->reduction = reduction<PvNode>(depth, moveCount);
1324 Depth d = newDepth - ss->reduction;
1325 value = d < OnePly ? -qsearch<NonPV>(pos, ss+1, -(alpha+1), -alpha, Depth(0), ply+1)
1326 : - search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1328 doFullDepthSearch = (value > alpha);
1331 // The move failed high, but if reduction is very big we could
1332 // face a false positive, retry with a less aggressive reduction,
1333 // if the move fails high again then go with full depth search.
1334 if (doFullDepthSearch && ss->reduction > 2 * OnePly)
1336 assert(newDepth - OnePly >= OnePly);
1338 ss->reduction = OnePly;
1339 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, ply+1);
1340 doFullDepthSearch = (value > alpha);
1342 ss->reduction = Depth(0); // Restore original reduction
1345 // Step 15. Full depth search
1346 if (doFullDepthSearch)
1348 value = newDepth < OnePly ? -qsearch<NonPV>(pos, ss+1, -(alpha+1), -alpha, Depth(0), ply+1)
1349 : - search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1351 // Step extra. pv search (only in PV nodes)
1352 // Search only for possible new PV nodes, if instead value >= beta then
1353 // parent node fails low with value <= alpha and tries another move.
1354 if (PvNode && value > alpha && value < beta)
1355 value = newDepth < OnePly ? -qsearch<PV>(pos, ss+1, -beta, -alpha, Depth(0), ply+1)
1356 : - search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1360 // Step 16. Undo move
1361 pos.undo_move(move);
1363 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1365 // Step 17. Check for new best move
1366 if (value > bestValue)
1371 if (PvNode && value < beta) // This guarantees that always: alpha < beta
1374 if (value == value_mate_in(ply + 1))
1375 ss->mateKiller = move;
1377 ss->bestMove = move;
1381 // Step 18. Check for split
1382 if ( depth >= MinimumSplitDepth
1383 && TM.active_threads() > 1
1385 && TM.available_thread_exists(threadID)
1387 && !TM.thread_should_stop(threadID)
1389 TM.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1390 threatMove, mateThreat, &moveCount, &mp, PvNode);
1393 // Step 19. Check for mate and stalemate
1394 // All legal moves have been searched and if there are
1395 // no legal moves, it must be mate or stalemate.
1396 // If one move was excluded return fail low score.
1398 return excludedMove ? oldAlpha : (isCheck ? value_mated_in(ply) : VALUE_DRAW);
1400 // Step 20. Update tables
1401 // If the search is not aborted, update the transposition table,
1402 // history counters, and killer moves.
1403 if (AbortSearch || TM.thread_should_stop(threadID))
1406 ValueType f = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1407 move = (bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove);
1408 TT.store(posKey, value_to_tt(bestValue, ply), f, depth, move, ss->eval, ei.kingDanger[pos.side_to_move()]);
1410 // Update killers and history only for non capture moves that fails high
1411 if (bestValue >= beta)
1413 TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
1414 if (!pos.move_is_capture_or_promotion(move))
1416 update_history(pos, move, depth, movesSearched, moveCount);
1417 update_killers(move, ss);
1421 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1427 // qsearch() is the quiescence search function, which is called by the main
1428 // search function when the remaining depth is zero (or, to be more precise,
1429 // less than OnePly).
1431 template <NodeType PvNode>
1432 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1434 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1435 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1436 assert(PvNode || alpha == beta - 1);
1438 assert(ply > 0 && ply < PLY_MAX);
1439 assert(pos.thread() >= 0 && pos.thread() < TM.active_threads());
1444 Value bestValue, value, futilityValue, futilityBase;
1445 bool isCheck, deepChecks, enoughMaterial, moveIsCheck, evasionPrunable;
1447 Value oldAlpha = alpha;
1449 TM.incrementNodeCounter(pos.thread());
1450 ss->bestMove = ss->currentMove = MOVE_NONE;
1452 // Check for an instant draw or maximum ply reached
1453 if (pos.is_draw() || ply >= PLY_MAX - 1)
1456 // Transposition table lookup. At PV nodes, we don't use the TT for
1457 // pruning, but only for move ordering.
1458 tte = TT.retrieve(pos.get_key());
1459 ttMove = (tte ? tte->move() : MOVE_NONE);
1461 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1463 ss->currentMove = ttMove; // Can be MOVE_NONE
1464 return value_from_tt(tte->value(), ply);
1467 isCheck = pos.is_check();
1469 // Evaluate the position statically
1472 bestValue = futilityBase = -VALUE_INFINITE;
1473 ss->eval = VALUE_NONE;
1474 deepChecks = enoughMaterial = false;
1480 assert(tte->static_value() != VALUE_NONE);
1481 ei.kingDanger[pos.side_to_move()] = tte->king_danger();
1482 bestValue = tte->static_value();
1485 bestValue = evaluate(pos, ei);
1487 ss->eval = bestValue;
1488 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1490 // Stand pat. Return immediately if static value is at least beta
1491 if (bestValue >= beta)
1494 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]);
1499 if (PvNode && bestValue > alpha)
1502 // If we are near beta then try to get a cutoff pushing checks a bit further
1503 deepChecks = (depth == -OnePly && bestValue >= beta - PawnValueMidgame / 8);
1505 // Futility pruning parameters, not needed when in check
1506 futilityBase = bestValue + FutilityMarginQS + ei.kingDanger[pos.side_to_move()];
1507 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1510 // Initialize a MovePicker object for the current position, and prepare
1511 // to search the moves. Because the depth is <= 0 here, only captures,
1512 // queen promotions and checks (only if depth == 0 or depth == -OnePly
1513 // and we are near beta) will be generated.
1514 MovePicker mp = MovePicker(pos, ttMove, deepChecks ? Depth(0) : depth, H);
1517 // Loop through the moves until no moves remain or a beta cutoff occurs
1518 while ( alpha < beta
1519 && (move = mp.get_next_move()) != MOVE_NONE)
1521 assert(move_is_ok(move));
1523 moveIsCheck = pos.move_is_check(move, ci);
1531 && !move_is_promotion(move)
1532 && !pos.move_is_passed_pawn_push(move))
1534 futilityValue = futilityBase
1535 + pos.endgame_value_of_piece_on(move_to(move))
1536 + (move_is_ep(move) ? PawnValueEndgame : Value(0));
1538 if (futilityValue < alpha)
1540 if (futilityValue > bestValue)
1541 bestValue = futilityValue;
1546 // Detect blocking evasions that are candidate to be pruned
1547 evasionPrunable = isCheck
1548 && bestValue > value_mated_in(PLY_MAX)
1549 && !pos.move_is_capture(move)
1550 && pos.type_of_piece_on(move_from(move)) != KING
1551 && !pos.can_castle(pos.side_to_move());
1553 // Don't search moves with negative SEE values
1555 && (!isCheck || evasionPrunable)
1557 && !move_is_promotion(move)
1558 && pos.see_sign(move) < 0)
1561 // Update current move
1562 ss->currentMove = move;
1564 // Make and search the move
1565 pos.do_move(move, st, ci, moveIsCheck);
1566 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-OnePly, ply+1);
1567 pos.undo_move(move);
1569 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1572 if (value > bestValue)
1578 ss->bestMove = move;
1583 // All legal moves have been searched. A special case: If we're in check
1584 // and no legal moves were found, it is checkmate.
1585 if (isCheck && bestValue == -VALUE_INFINITE)
1586 return value_mated_in(ply);
1588 // Update transposition table
1589 Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
1590 ValueType f = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1591 TT.store(pos.get_key(), value_to_tt(bestValue, ply), f, d, ss->bestMove, ss->eval, ei.kingDanger[pos.side_to_move()]);
1593 // Update killers only for checking moves that fails high
1594 if ( bestValue >= beta
1595 && !pos.move_is_capture_or_promotion(ss->bestMove))
1596 update_killers(ss->bestMove, ss);
1598 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1604 // sp_search() is used to search from a split point. This function is called
1605 // by each thread working at the split point. It is similar to the normal
1606 // search() function, but simpler. Because we have already probed the hash
1607 // table, done a null move search, and searched the first move before
1608 // splitting, we don't have to repeat all this work in sp_search(). We
1609 // also don't need to store anything to the hash table here: This is taken
1610 // care of after we return from the split point.
1612 template <NodeType PvNode>
1613 void sp_search(SplitPoint* sp, int threadID) {
1615 assert(threadID >= 0 && threadID < TM.active_threads());
1616 assert(TM.active_threads() > 1);
1620 Depth ext, newDepth;
1622 Value futilityValueScaled; // NonPV specific
1623 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
1625 value = -VALUE_INFINITE;
1627 Position pos(*sp->pos, threadID);
1629 SearchStack* ss = sp->sstack[threadID] + 1;
1630 isCheck = pos.is_check();
1632 // Step 10. Loop through moves
1633 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1634 lock_grab(&(sp->lock));
1636 while ( sp->bestValue < sp->beta
1637 && (move = sp->mp->get_next_move()) != MOVE_NONE
1638 && !TM.thread_should_stop(threadID))
1640 moveCount = ++sp->moveCount;
1641 lock_release(&(sp->lock));
1643 assert(move_is_ok(move));
1645 moveIsCheck = pos.move_is_check(move, ci);
1646 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1648 // Step 11. Decide the new search depth
1649 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous);
1650 newDepth = sp->depth - OnePly + ext;
1652 // Update current move
1653 ss->currentMove = move;
1655 // Step 12. Futility pruning (is omitted in PV nodes)
1657 && !captureOrPromotion
1660 && !move_is_castle(move))
1662 // Move count based pruning
1663 if ( moveCount >= futility_move_count(sp->depth)
1664 && !(sp->threatMove && connected_threat(pos, move, sp->threatMove))
1665 && sp->bestValue > value_mated_in(PLY_MAX))
1667 lock_grab(&(sp->lock));
1671 // Value based pruning
1672 Depth predictedDepth = newDepth - reduction<NonPV>(sp->depth, moveCount);
1673 futilityValueScaled = ss->eval + futility_margin(predictedDepth, moveCount)
1674 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1676 if (futilityValueScaled < sp->beta)
1678 lock_grab(&(sp->lock));
1680 if (futilityValueScaled > sp->bestValue)
1681 sp->bestValue = futilityValueScaled;
1686 // Step 13. Make the move
1687 pos.do_move(move, st, ci, moveIsCheck);
1689 // Step 14. Reduced search
1690 // If the move fails high will be re-searched at full depth.
1691 bool doFullDepthSearch = true;
1693 if ( !captureOrPromotion
1695 && !move_is_castle(move)
1696 && !move_is_killer(move, ss))
1698 ss->reduction = reduction<PvNode>(sp->depth, moveCount);
1701 Value localAlpha = sp->alpha;
1702 Depth d = newDepth - ss->reduction;
1703 value = d < OnePly ? -qsearch<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, Depth(0), sp->ply+1)
1704 : - search<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, d, sp->ply+1);
1706 doFullDepthSearch = (value > localAlpha);
1709 // The move failed high, but if reduction is very big we could
1710 // face a false positive, retry with a less aggressive reduction,
1711 // if the move fails high again then go with full depth search.
1712 if (doFullDepthSearch && ss->reduction > 2 * OnePly)
1714 assert(newDepth - OnePly >= OnePly);
1716 ss->reduction = OnePly;
1717 Value localAlpha = sp->alpha;
1718 value = -search<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, newDepth-ss->reduction, sp->ply+1);
1719 doFullDepthSearch = (value > localAlpha);
1721 ss->reduction = Depth(0); // Restore original reduction
1724 // Step 15. Full depth search
1725 if (doFullDepthSearch)
1727 Value localAlpha = sp->alpha;
1728 value = newDepth < OnePly ? -qsearch<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, Depth(0), sp->ply+1)
1729 : - search<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, newDepth, sp->ply+1);
1731 // Step extra. pv search (only in PV nodes)
1732 // Search only for possible new PV nodes, if instead value >= beta then
1733 // parent node fails low with value <= alpha and tries another move.
1734 if (PvNode && value > localAlpha && value < sp->beta)
1735 value = newDepth < OnePly ? -qsearch<PV>(pos, ss+1, -sp->beta, -sp->alpha, Depth(0), sp->ply+1)
1736 : - search<PV>(pos, ss+1, -sp->beta, -sp->alpha, newDepth, sp->ply+1);
1739 // Step 16. Undo move
1740 pos.undo_move(move);
1742 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1744 // Step 17. Check for new best move
1745 lock_grab(&(sp->lock));
1747 if (value > sp->bestValue && !TM.thread_should_stop(threadID))
1749 sp->bestValue = value;
1751 if (sp->bestValue > sp->alpha)
1753 if (!PvNode || value >= sp->beta)
1754 sp->stopRequest = true;
1756 if (PvNode && value < sp->beta) // This guarantees that always: sp->alpha < sp->beta
1759 sp->parentSstack->bestMove = ss->bestMove = move;
1764 /* Here we have the lock still grabbed */
1766 sp->slaves[threadID] = 0;
1768 lock_release(&(sp->lock));
1772 // connected_moves() tests whether two moves are 'connected' in the sense
1773 // that the first move somehow made the second move possible (for instance
1774 // if the moving piece is the same in both moves). The first move is assumed
1775 // to be the move that was made to reach the current position, while the
1776 // second move is assumed to be a move from the current position.
1778 bool connected_moves(const Position& pos, Move m1, Move m2) {
1780 Square f1, t1, f2, t2;
1783 assert(move_is_ok(m1));
1784 assert(move_is_ok(m2));
1786 if (m2 == MOVE_NONE)
1789 // Case 1: The moving piece is the same in both moves
1795 // Case 2: The destination square for m2 was vacated by m1
1801 // Case 3: Moving through the vacated square
1802 if ( piece_is_slider(pos.piece_on(f2))
1803 && bit_is_set(squares_between(f2, t2), f1))
1806 // Case 4: The destination square for m2 is defended by the moving piece in m1
1807 p = pos.piece_on(t1);
1808 if (bit_is_set(pos.attacks_from(p, t1), t2))
1811 // Case 5: Discovered check, checking piece is the piece moved in m1
1812 if ( piece_is_slider(p)
1813 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1814 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1816 // discovered_check_candidates() works also if the Position's side to
1817 // move is the opposite of the checking piece.
1818 Color them = opposite_color(pos.side_to_move());
1819 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1821 if (bit_is_set(dcCandidates, f2))
1828 // value_is_mate() checks if the given value is a mate one eventually
1829 // compensated for the ply.
1831 bool value_is_mate(Value value) {
1833 assert(abs(value) <= VALUE_INFINITE);
1835 return value <= value_mated_in(PLY_MAX)
1836 || value >= value_mate_in(PLY_MAX);
1840 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1841 // "plies to mate from the current ply". Non-mate scores are unchanged.
1842 // The function is called before storing a value to the transposition table.
1844 Value value_to_tt(Value v, int ply) {
1846 if (v >= value_mate_in(PLY_MAX))
1849 if (v <= value_mated_in(PLY_MAX))
1856 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1857 // the transposition table to a mate score corrected for the current ply.
1859 Value value_from_tt(Value v, int ply) {
1861 if (v >= value_mate_in(PLY_MAX))
1864 if (v <= value_mated_in(PLY_MAX))
1871 // move_is_killer() checks if the given move is among the killer moves
1873 bool move_is_killer(Move m, SearchStack* ss) {
1875 if (ss->killers[0] == m || ss->killers[1] == m)
1882 // extension() decides whether a move should be searched with normal depth,
1883 // or with extended depth. Certain classes of moves (checking moves, in
1884 // particular) are searched with bigger depth than ordinary moves and in
1885 // any case are marked as 'dangerous'. Note that also if a move is not
1886 // extended, as example because the corresponding UCI option is set to zero,
1887 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1888 template <NodeType PvNode>
1889 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1890 bool singleEvasion, bool mateThreat, bool* dangerous) {
1892 assert(m != MOVE_NONE);
1894 Depth result = Depth(0);
1895 *dangerous = moveIsCheck | singleEvasion | mateThreat;
1899 if (moveIsCheck && pos.see_sign(m) >= 0)
1900 result += CheckExtension[PvNode];
1903 result += SingleEvasionExtension[PvNode];
1906 result += MateThreatExtension[PvNode];
1909 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1911 Color c = pos.side_to_move();
1912 if (relative_rank(c, move_to(m)) == RANK_7)
1914 result += PawnPushTo7thExtension[PvNode];
1917 if (pos.pawn_is_passed(c, move_to(m)))
1919 result += PassedPawnExtension[PvNode];
1924 if ( captureOrPromotion
1925 && pos.type_of_piece_on(move_to(m)) != PAWN
1926 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1927 - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))
1928 && !move_is_promotion(m)
1931 result += PawnEndgameExtension[PvNode];
1936 && captureOrPromotion
1937 && pos.type_of_piece_on(move_to(m)) != PAWN
1938 && pos.see_sign(m) >= 0)
1944 return Min(result, OnePly);
1948 // connected_threat() tests whether it is safe to forward prune a move or if
1949 // is somehow coonected to the threat move returned by null search.
1951 bool connected_threat(const Position& pos, Move m, Move threat) {
1953 assert(move_is_ok(m));
1954 assert(threat && move_is_ok(threat));
1955 assert(!pos.move_is_check(m));
1956 assert(!pos.move_is_capture_or_promotion(m));
1957 assert(!pos.move_is_passed_pawn_push(m));
1959 Square mfrom, mto, tfrom, tto;
1961 mfrom = move_from(m);
1963 tfrom = move_from(threat);
1964 tto = move_to(threat);
1966 // Case 1: Don't prune moves which move the threatened piece
1970 // Case 2: If the threatened piece has value less than or equal to the
1971 // value of the threatening piece, don't prune move which defend it.
1972 if ( pos.move_is_capture(threat)
1973 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1974 || pos.type_of_piece_on(tfrom) == KING)
1975 && pos.move_attacks_square(m, tto))
1978 // Case 3: If the moving piece in the threatened move is a slider, don't
1979 // prune safe moves which block its ray.
1980 if ( piece_is_slider(pos.piece_on(tfrom))
1981 && bit_is_set(squares_between(tfrom, tto), mto)
1982 && pos.see_sign(m) >= 0)
1989 // ok_to_use_TT() returns true if a transposition table score
1990 // can be used at a given point in search.
1992 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1994 Value v = value_from_tt(tte->value(), ply);
1996 return ( tte->depth() >= depth
1997 || v >= Max(value_mate_in(PLY_MAX), beta)
1998 || v < Min(value_mated_in(PLY_MAX), beta))
2000 && ( (is_lower_bound(tte->type()) && v >= beta)
2001 || (is_upper_bound(tte->type()) && v < beta));
2005 // refine_eval() returns the transposition table score if
2006 // possible otherwise falls back on static position evaluation.
2008 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
2013 Value v = value_from_tt(tte->value(), ply);
2015 if ( (is_lower_bound(tte->type()) && v >= defaultEval)
2016 || (is_upper_bound(tte->type()) && v < defaultEval))
2023 // update_history() registers a good move that produced a beta-cutoff
2024 // in history and marks as failures all the other moves of that ply.
2026 void update_history(const Position& pos, Move move, Depth depth,
2027 Move movesSearched[], int moveCount) {
2031 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
2033 for (int i = 0; i < moveCount - 1; i++)
2035 m = movesSearched[i];
2039 if (!pos.move_is_capture_or_promotion(m))
2040 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
2045 // update_killers() add a good move that produced a beta-cutoff
2046 // among the killer moves of that ply.
2048 void update_killers(Move m, SearchStack* ss) {
2050 if (m == ss->killers[0])
2053 ss->killers[1] = ss->killers[0];
2058 // update_gains() updates the gains table of a non-capture move given
2059 // the static position evaluation before and after the move.
2061 void update_gains(const Position& pos, Move m, Value before, Value after) {
2064 && before != VALUE_NONE
2065 && after != VALUE_NONE
2066 && pos.captured_piece() == NO_PIECE_TYPE
2067 && !move_is_castle(m)
2068 && !move_is_promotion(m))
2069 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
2073 // current_search_time() returns the number of milliseconds which have passed
2074 // since the beginning of the current search.
2076 int current_search_time() {
2078 return get_system_time() - SearchStartTime;
2082 // value_to_uci() converts a value to a string suitable for use with the UCI protocol
2084 std::string value_to_uci(Value v) {
2086 std::stringstream s;
2088 if (abs(v) < VALUE_MATE - PLY_MAX * OnePly)
2089 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100
2091 s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
2096 // nps() computes the current nodes/second count.
2100 int t = current_search_time();
2101 return (t > 0 ? int((TM.nodes_searched() * 1000) / t) : 0);
2105 // poll() performs two different functions: It polls for user input, and it
2106 // looks at the time consumed so far and decides if it's time to abort the
2111 static int lastInfoTime;
2112 int t = current_search_time();
2117 // We are line oriented, don't read single chars
2118 std::string command;
2120 if (!std::getline(std::cin, command))
2123 if (command == "quit")
2126 PonderSearch = false;
2130 else if (command == "stop")
2133 PonderSearch = false;
2135 else if (command == "ponderhit")
2139 // Print search information
2143 else if (lastInfoTime > t)
2144 // HACK: Must be a new search where we searched less than
2145 // NodesBetweenPolls nodes during the first second of search.
2148 else if (t - lastInfoTime >= 1000)
2155 if (dbg_show_hit_rate)
2156 dbg_print_hit_rate();
2158 cout << "info nodes " << TM.nodes_searched() << " nps " << nps()
2159 << " time " << t << endl;
2162 // Should we stop the search?
2166 bool stillAtFirstMove = FirstRootMove
2167 && !AspirationFailLow
2168 && t > MaxSearchTime + ExtraSearchTime;
2170 bool noMoreTime = t > AbsoluteMaxSearchTime
2171 || stillAtFirstMove;
2173 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2174 || (ExactMaxTime && t >= ExactMaxTime)
2175 || (Iteration >= 3 && MaxNodes && TM.nodes_searched() >= MaxNodes))
2180 // ponderhit() is called when the program is pondering (i.e. thinking while
2181 // it's the opponent's turn to move) in order to let the engine know that
2182 // it correctly predicted the opponent's move.
2186 int t = current_search_time();
2187 PonderSearch = false;
2189 bool stillAtFirstMove = FirstRootMove
2190 && !AspirationFailLow
2191 && t > MaxSearchTime + ExtraSearchTime;
2193 bool noMoreTime = t > AbsoluteMaxSearchTime
2194 || stillAtFirstMove;
2196 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2201 // init_ss_array() does a fast reset of the first entries of a SearchStack
2202 // array and of all the excludedMove and skipNullMove entries.
2204 void init_ss_array(SearchStack* ss, int size) {
2206 for (int i = 0; i < size; i++, ss++)
2208 ss->excludedMove = MOVE_NONE;
2209 ss->skipNullMove = false;
2210 ss->reduction = Depth(0);
2213 ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE;
2218 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2219 // while the program is pondering. The point is to work around a wrinkle in
2220 // the UCI protocol: When pondering, the engine is not allowed to give a
2221 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2222 // We simply wait here until one of these commands is sent, and return,
2223 // after which the bestmove and pondermove will be printed (in id_loop()).
2225 void wait_for_stop_or_ponderhit() {
2227 std::string command;
2231 if (!std::getline(std::cin, command))
2234 if (command == "quit")
2239 else if (command == "ponderhit" || command == "stop")
2245 // print_pv_info() prints to standard output and eventually to log file information on
2246 // the current PV line. It is called at each iteration or after a new pv is found.
2248 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) {
2250 cout << "info depth " << Iteration
2251 << " score " << value_to_uci(value)
2252 << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
2253 << " time " << current_search_time()
2254 << " nodes " << TM.nodes_searched()
2258 for (Move* m = pv; *m != MOVE_NONE; m++)
2265 ValueType t = value >= beta ? VALUE_TYPE_LOWER :
2266 value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
2268 LogFile << pretty_pv(pos, current_search_time(), Iteration,
2269 TM.nodes_searched(), value, t, pv) << endl;
2274 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2275 // the PV back into the TT. This makes sure the old PV moves are searched
2276 // first, even if the old TT entries have been overwritten.
2278 void insert_pv_in_tt(const Position& pos, Move pv[]) {
2282 Position p(pos, pos.thread());
2286 for (int i = 0; pv[i] != MOVE_NONE; i++)
2288 tte = TT.retrieve(p.get_key());
2289 if (!tte || tte->move() != pv[i])
2291 v = (p.is_check() ? VALUE_NONE : evaluate(p, ei));
2292 TT.store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[i], v, ei.kingDanger[pos.side_to_move()]);
2294 p.do_move(pv[i], st);
2299 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2300 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2301 // allow to always have a ponder move even when we fail high at root and also a
2302 // long PV to print that is important for position analysis.
2304 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]) {
2308 Position p(pos, pos.thread());
2311 assert(bestMove != MOVE_NONE);
2314 p.do_move(pv[ply++], st);
2316 while ( (tte = TT.retrieve(p.get_key())) != NULL
2317 && tte->move() != MOVE_NONE
2318 && move_is_legal(p, tte->move())
2320 && (!p.is_draw() || ply < 2))
2322 pv[ply] = tte->move();
2323 p.do_move(pv[ply++], st);
2325 pv[ply] = MOVE_NONE;
2329 // init_thread() is the function which is called when a new thread is
2330 // launched. It simply calls the idle_loop() function with the supplied
2331 // threadID. There are two versions of this function; one for POSIX
2332 // threads and one for Windows threads.
2334 #if !defined(_MSC_VER)
2336 void* init_thread(void *threadID) {
2338 TM.idle_loop(*(int*)threadID, NULL);
2344 DWORD WINAPI init_thread(LPVOID threadID) {
2346 TM.idle_loop(*(int*)threadID, NULL);
2353 /// The ThreadsManager class
2355 // resetNodeCounters(), resetBetaCounters(), searched_nodes() and
2356 // get_beta_counters() are getters/setters for the per thread
2357 // counters used to sort the moves at root.
2359 void ThreadsManager::resetNodeCounters() {
2361 for (int i = 0; i < MAX_THREADS; i++)
2362 threads[i].nodes = 0ULL;
2365 void ThreadsManager::resetBetaCounters() {
2367 for (int i = 0; i < MAX_THREADS; i++)
2368 threads[i].betaCutOffs[WHITE] = threads[i].betaCutOffs[BLACK] = 0ULL;
2371 int64_t ThreadsManager::nodes_searched() const {
2373 int64_t result = 0ULL;
2374 for (int i = 0; i < ActiveThreads; i++)
2375 result += threads[i].nodes;
2380 void ThreadsManager::get_beta_counters(Color us, int64_t& our, int64_t& their) const {
2383 for (int i = 0; i < MAX_THREADS; i++)
2385 our += threads[i].betaCutOffs[us];
2386 their += threads[i].betaCutOffs[opposite_color(us)];
2391 // idle_loop() is where the threads are parked when they have no work to do.
2392 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2393 // object for which the current thread is the master.
2395 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2397 assert(threadID >= 0 && threadID < MAX_THREADS);
2401 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2402 // master should exit as last one.
2403 if (AllThreadsShouldExit)
2406 threads[threadID].state = THREAD_TERMINATED;
2410 // If we are not thinking, wait for a condition to be signaled
2411 // instead of wasting CPU time polling for work.
2412 while (AllThreadsShouldSleep || threadID >= ActiveThreads)
2415 assert(threadID != 0);
2416 threads[threadID].state = THREAD_SLEEPING;
2418 #if !defined(_MSC_VER)
2419 lock_grab(&WaitLock);
2420 if (AllThreadsShouldSleep || threadID >= ActiveThreads)
2421 pthread_cond_wait(&WaitCond, &WaitLock);
2422 lock_release(&WaitLock);
2424 WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2428 // If thread has just woken up, mark it as available
2429 if (threads[threadID].state == THREAD_SLEEPING)
2430 threads[threadID].state = THREAD_AVAILABLE;
2432 // If this thread has been assigned work, launch a search
2433 if (threads[threadID].state == THREAD_WORKISWAITING)
2435 assert(!AllThreadsShouldExit && !AllThreadsShouldSleep);
2437 threads[threadID].state = THREAD_SEARCHING;
2439 if (threads[threadID].splitPoint->pvNode)
2440 sp_search<PV>(threads[threadID].splitPoint, threadID);
2442 sp_search<NonPV>(threads[threadID].splitPoint, threadID);
2444 assert(threads[threadID].state == THREAD_SEARCHING);
2446 threads[threadID].state = THREAD_AVAILABLE;
2449 // If this thread is the master of a split point and all slaves have
2450 // finished their work at this split point, return from the idle loop.
2452 for ( ; sp && i < ActiveThreads && !sp->slaves[i]; i++) {}
2454 if (i == ActiveThreads)
2456 // Because sp->slaves[] is reset under lock protection,
2457 // be sure sp->lock has been released before to return.
2458 lock_grab(&(sp->lock));
2459 lock_release(&(sp->lock));
2461 assert(threads[threadID].state == THREAD_AVAILABLE);
2463 threads[threadID].state = THREAD_SEARCHING;
2470 // init_threads() is called during startup. It launches all helper threads,
2471 // and initializes the split point stack and the global locks and condition
2474 void ThreadsManager::init_threads() {
2479 #if !defined(_MSC_VER)
2480 pthread_t pthread[1];
2483 // Initialize global locks
2485 lock_init(&WaitLock);
2487 #if !defined(_MSC_VER)
2488 pthread_cond_init(&WaitCond, NULL);
2490 for (i = 0; i < MAX_THREADS; i++)
2491 SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0);
2494 // Initialize splitPoints[] locks
2495 for (i = 0; i < MAX_THREADS; i++)
2496 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2497 lock_init(&(threads[i].splitPoints[j].lock));
2499 // Will be set just before program exits to properly end the threads
2500 AllThreadsShouldExit = false;
2502 // Threads will be put to sleep as soon as created
2503 AllThreadsShouldSleep = true;
2505 // All threads except the main thread should be initialized to THREAD_AVAILABLE
2507 threads[0].state = THREAD_SEARCHING;
2508 for (i = 1; i < MAX_THREADS; i++)
2509 threads[i].state = THREAD_AVAILABLE;
2511 // Launch the helper threads
2512 for (i = 1; i < MAX_THREADS; i++)
2515 #if !defined(_MSC_VER)
2516 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&i)) == 0);
2518 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, NULL) != NULL);
2523 cout << "Failed to create thread number " << i << endl;
2524 Application::exit_with_failure();
2527 // Wait until the thread has finished launching and is gone to sleep
2528 while (threads[i].state != THREAD_SLEEPING) {}
2533 // exit_threads() is called when the program exits. It makes all the
2534 // helper threads exit cleanly.
2536 void ThreadsManager::exit_threads() {
2538 ActiveThreads = MAX_THREADS; // HACK
2539 AllThreadsShouldSleep = true; // HACK
2540 wake_sleeping_threads();
2542 // This makes the threads to exit idle_loop()
2543 AllThreadsShouldExit = true;
2545 // Wait for thread termination
2546 for (int i = 1; i < MAX_THREADS; i++)
2547 while (threads[i].state != THREAD_TERMINATED) {}
2549 // Now we can safely destroy the locks
2550 for (int i = 0; i < MAX_THREADS; i++)
2551 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2552 lock_destroy(&(threads[i].splitPoints[j].lock));
2554 lock_destroy(&WaitLock);
2555 lock_destroy(&MPLock);
2559 // thread_should_stop() checks whether the thread should stop its search.
2560 // This can happen if a beta cutoff has occurred in the thread's currently
2561 // active split point, or in some ancestor of the current split point.
2563 bool ThreadsManager::thread_should_stop(int threadID) const {
2565 assert(threadID >= 0 && threadID < ActiveThreads);
2569 for (sp = threads[threadID].splitPoint; sp && !sp->stopRequest; sp = sp->parent) {}
2574 // thread_is_available() checks whether the thread with threadID "slave" is
2575 // available to help the thread with threadID "master" at a split point. An
2576 // obvious requirement is that "slave" must be idle. With more than two
2577 // threads, this is not by itself sufficient: If "slave" is the master of
2578 // some active split point, it is only available as a slave to the other
2579 // threads which are busy searching the split point at the top of "slave"'s
2580 // split point stack (the "helpful master concept" in YBWC terminology).
2582 bool ThreadsManager::thread_is_available(int slave, int master) const {
2584 assert(slave >= 0 && slave < ActiveThreads);
2585 assert(master >= 0 && master < ActiveThreads);
2586 assert(ActiveThreads > 1);
2588 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2591 // Make a local copy to be sure doesn't change under our feet
2592 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2594 if (localActiveSplitPoints == 0)
2595 // No active split points means that the thread is available as
2596 // a slave for any other thread.
2599 if (ActiveThreads == 2)
2602 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2603 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2604 // could have been set to 0 by another thread leading to an out of bound access.
2605 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2612 // available_thread_exists() tries to find an idle thread which is available as
2613 // a slave for the thread with threadID "master".
2615 bool ThreadsManager::available_thread_exists(int master) const {
2617 assert(master >= 0 && master < ActiveThreads);
2618 assert(ActiveThreads > 1);
2620 for (int i = 0; i < ActiveThreads; i++)
2621 if (thread_is_available(i, master))
2628 // split() does the actual work of distributing the work at a node between
2629 // several available threads. If it does not succeed in splitting the
2630 // node (because no idle threads are available, or because we have no unused
2631 // split point objects), the function immediately returns. If splitting is
2632 // possible, a SplitPoint object is initialized with all the data that must be
2633 // copied to the helper threads and we tell our helper threads that they have
2634 // been assigned work. This will cause them to instantly leave their idle loops
2635 // and call sp_search(). When all threads have returned from sp_search() then
2638 template <bool Fake>
2639 void ThreadsManager::split(const Position& p, SearchStack* ss, int ply, Value* alpha,
2640 const Value beta, Value* bestValue, Depth depth, Move threatMove,
2641 bool mateThreat, int* moveCount, MovePicker* mp, bool pvNode) {
2643 assert(ply > 0 && ply < PLY_MAX);
2644 assert(*bestValue >= -VALUE_INFINITE);
2645 assert(*bestValue <= *alpha);
2646 assert(*alpha < beta);
2647 assert(beta <= VALUE_INFINITE);
2648 assert(depth > Depth(0));
2649 assert(p.thread() >= 0 && p.thread() < ActiveThreads);
2650 assert(ActiveThreads > 1);
2652 int i, master = p.thread();
2653 Thread& masterThread = threads[master];
2657 // If no other thread is available to help us, or if we have too many
2658 // active split points, don't split.
2659 if ( !available_thread_exists(master)
2660 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2662 lock_release(&MPLock);
2666 // Pick the next available split point object from the split point stack
2667 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2669 // Initialize the split point object
2670 splitPoint.parent = masterThread.splitPoint;
2671 splitPoint.stopRequest = false;
2672 splitPoint.ply = ply;
2673 splitPoint.depth = depth;
2674 splitPoint.threatMove = threatMove;
2675 splitPoint.mateThreat = mateThreat;
2676 splitPoint.alpha = *alpha;
2677 splitPoint.beta = beta;
2678 splitPoint.pvNode = pvNode;
2679 splitPoint.bestValue = *bestValue;
2681 splitPoint.moveCount = *moveCount;
2682 splitPoint.pos = &p;
2683 splitPoint.parentSstack = ss;
2684 for (i = 0; i < ActiveThreads; i++)
2685 splitPoint.slaves[i] = 0;
2687 masterThread.splitPoint = &splitPoint;
2689 // If we are here it means we are not available
2690 assert(masterThread.state != THREAD_AVAILABLE);
2692 int workersCnt = 1; // At least the master is included
2694 // Allocate available threads setting state to THREAD_BOOKED
2695 for (i = 0; !Fake && i < ActiveThreads && workersCnt < MaxThreadsPerSplitPoint; i++)
2696 if (thread_is_available(i, master))
2698 threads[i].state = THREAD_BOOKED;
2699 threads[i].splitPoint = &splitPoint;
2700 splitPoint.slaves[i] = 1;
2704 assert(Fake || workersCnt > 1);
2706 // We can release the lock because slave threads are already booked and master is not available
2707 lock_release(&MPLock);
2709 // Tell the threads that they have work to do. This will make them leave
2710 // their idle loop. But before copy search stack tail for each thread.
2711 for (i = 0; i < ActiveThreads; i++)
2712 if (i == master || splitPoint.slaves[i])
2714 memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
2716 assert(i == master || threads[i].state == THREAD_BOOKED);
2718 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2721 // Everything is set up. The master thread enters the idle loop, from
2722 // which it will instantly launch a search, because its state is
2723 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2724 // idle loop, which means that the main thread will return from the idle
2725 // loop when all threads have finished their work at this split point.
2726 idle_loop(master, &splitPoint);
2728 // We have returned from the idle loop, which means that all threads are
2729 // finished. Update alpha and bestValue, and return.
2732 *alpha = splitPoint.alpha;
2733 *bestValue = splitPoint.bestValue;
2734 masterThread.activeSplitPoints--;
2735 masterThread.splitPoint = splitPoint.parent;
2737 lock_release(&MPLock);
2741 // wake_sleeping_threads() wakes up all sleeping threads when it is time
2742 // to start a new search from the root.
2744 void ThreadsManager::wake_sleeping_threads() {
2746 assert(AllThreadsShouldSleep);
2747 assert(ActiveThreads > 0);
2749 AllThreadsShouldSleep = false;
2751 if (ActiveThreads == 1)
2754 #if !defined(_MSC_VER)
2755 pthread_mutex_lock(&WaitLock);
2756 pthread_cond_broadcast(&WaitCond);
2757 pthread_mutex_unlock(&WaitLock);
2759 for (int i = 1; i < MAX_THREADS; i++)
2760 SetEvent(SitIdleEvent[i]);
2766 // put_threads_to_sleep() makes all the threads go to sleep just before
2767 // to leave think(), at the end of the search. Threads should have already
2768 // finished the job and should be idle.
2770 void ThreadsManager::put_threads_to_sleep() {
2772 assert(!AllThreadsShouldSleep);
2774 // This makes the threads to go to sleep
2775 AllThreadsShouldSleep = true;
2778 /// The RootMoveList class
2780 // RootMoveList c'tor
2782 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
2784 SearchStack ss[PLY_MAX_PLUS_2];
2785 MoveStack mlist[MaxRootMoves];
2787 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
2789 // Initialize search stack
2790 init_ss_array(ss, PLY_MAX_PLUS_2);
2791 ss[0].currentMove = ss[0].bestMove = MOVE_NONE;
2792 ss[0].eval = VALUE_NONE;
2794 // Generate all legal moves
2795 MoveStack* last = generate_moves(pos, mlist);
2797 // Add each move to the moves[] array
2798 for (MoveStack* cur = mlist; cur != last; cur++)
2800 bool includeMove = includeAllMoves;
2802 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
2803 includeMove = (searchMoves[k] == cur->move);
2808 // Find a quick score for the move
2809 pos.do_move(cur->move, st);
2810 ss[0].currentMove = cur->move;
2811 moves[count].move = cur->move;
2812 moves[count].score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1);
2813 moves[count].pv[0] = cur->move;
2814 moves[count].pv[1] = MOVE_NONE;
2815 pos.undo_move(cur->move);
2822 // RootMoveList simple methods definitions
2824 void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
2826 moves[moveNum].nodes = nodes;
2827 moves[moveNum].cumulativeNodes += nodes;
2830 void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
2832 moves[moveNum].ourBeta = our;
2833 moves[moveNum].theirBeta = their;
2836 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
2840 for (j = 0; pv[j] != MOVE_NONE; j++)
2841 moves[moveNum].pv[j] = pv[j];
2843 moves[moveNum].pv[j] = MOVE_NONE;
2847 // RootMoveList::sort() sorts the root move list at the beginning of a new
2850 void RootMoveList::sort() {
2852 sort_multipv(count - 1); // Sort all items
2856 // RootMoveList::sort_multipv() sorts the first few moves in the root move
2857 // list by their scores and depths. It is used to order the different PVs
2858 // correctly in MultiPV mode.
2860 void RootMoveList::sort_multipv(int n) {
2864 for (i = 1; i <= n; i++)
2866 RootMove rm = moves[i];
2867 for (j = i; j > 0 && moves[j - 1] < rm; j--)
2868 moves[j] = moves[j - 1];