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/>.
44 #include "ucioption.h"
50 //// Local definitions
56 enum NodeType { NonPV, PV };
58 // Set to true to force running with one thread.
59 // Used for debugging SMP code.
60 const bool FakeSplit = false;
62 // ThreadsManager class is used to handle all the threads related stuff in search,
63 // init, starting, parking and, the most important, launching a slave thread at a
64 // split point are what this class does. All the access to shared thread data is
65 // done through this class, so that we avoid using global variables instead.
67 class ThreadsManager {
68 /* As long as the single ThreadsManager object is defined as a global we don't
69 need to explicitly initialize to zero its data members because variables with
70 static storage duration are automatically set to zero before enter main()
76 int active_threads() const { return ActiveThreads; }
77 void set_active_threads(int newActiveThreads) { ActiveThreads = newActiveThreads; }
78 void incrementNodeCounter(int threadID) { threads[threadID].nodes++; }
80 void resetNodeCounters();
81 int64_t nodes_searched() const;
82 bool available_thread_exists(int master) const;
83 bool thread_is_available(int slave, int master) const;
84 bool thread_should_stop(int threadID) const;
85 void wake_sleeping_threads();
86 void put_threads_to_sleep();
87 void idle_loop(int threadID, SplitPoint* sp);
90 void split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
91 Depth depth, Move threatMove, bool mateThreat, int moveCount, MovePicker* mp, bool pvNode);
97 volatile bool AllThreadsShouldExit, AllThreadsShouldSleep;
98 Thread threads[MAX_THREADS];
100 Lock MPLock, WaitLock;
102 #if !defined(_MSC_VER)
103 pthread_cond_t WaitCond;
105 HANDLE SitIdleEvent[MAX_THREADS];
111 // RootMove struct is used for moves at the root at the tree. For each
112 // root move, we store a score, a node count, and a PV (really a refutation
113 // in the case of moves which fail low).
117 RootMove() : mp_score(0), nodes(0) {}
119 // RootMove::operator<() is the comparison function used when
120 // sorting the moves. A move m1 is considered to be better
121 // than a move m2 if it has a higher score, or if the moves
122 // have equal score but m1 has the higher beta cut-off count.
123 bool operator<(const RootMove& m) const {
125 return score != m.score ? score < m.score : mp_score <= m.mp_score;
132 Move pv[PLY_MAX_PLUS_2];
136 // The RootMoveList class is essentially an array of RootMove objects, with
137 // a handful of methods for accessing the data in the individual moves.
142 RootMoveList(Position& pos, Move searchMoves[]);
144 Move move(int moveNum) const { return moves[moveNum].move; }
145 Move move_pv(int moveNum, int i) const { return moves[moveNum].pv[i]; }
146 int move_count() const { return count; }
147 Value move_score(int moveNum) const { return moves[moveNum].score; }
148 int64_t move_nodes(int moveNum) const { return moves[moveNum].nodes; }
149 void add_move_nodes(int moveNum, int64_t nodes) { moves[moveNum].nodes += nodes; }
150 void set_move_score(int moveNum, Value score) { moves[moveNum].score = score; }
152 void set_move_pv(int moveNum, const Move pv[]);
153 void score_moves(const Position& pos);
155 void sort_multipv(int n);
158 RootMove moves[MOVES_MAX];
163 // When formatting a move for std::cout we must know if we are in Chess960
164 // or not. To keep using the handy operator<<() on the move the trick is to
165 // embed this flag in the stream itself. Function-like named enum set960 is
166 // used as a custom manipulator and the stream internal general-purpose array,
167 // accessed through ios_base::iword(), is used to pass the flag to the move's
168 // operator<<() that will use it to properly format castling moves.
171 std::ostream& operator<< (std::ostream& os, const set960& m) {
173 os.iword(0) = int(m);
182 // Maximum depth for razoring
183 const Depth RazorDepth = 4 * ONE_PLY;
185 // Dynamic razoring margin based on depth
186 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
188 // Maximum depth for use of dynamic threat detection when null move fails low
189 const Depth ThreatDepth = 5 * ONE_PLY;
191 // Step 9. Internal iterative deepening
193 // Minimum depth for use of internal iterative deepening
194 const Depth IIDDepth[2] = { 8 * ONE_PLY /* non-PV */, 5 * ONE_PLY /* PV */};
196 // At Non-PV nodes we do an internal iterative deepening search
197 // when the static evaluation is bigger then beta - IIDMargin.
198 const Value IIDMargin = Value(0x100);
200 // Step 11. Decide the new search depth
202 // Extensions. Configurable UCI options
203 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
204 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
205 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
207 // Minimum depth for use of singular extension
208 const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */};
210 // If the TT move is at least SingularExtensionMargin better then the
211 // remaining ones we will extend it.
212 const Value SingularExtensionMargin = Value(0x20);
214 // Step 12. Futility pruning
216 // Futility margin for quiescence search
217 const Value FutilityMarginQS = Value(0x80);
219 // Futility lookup tables (initialized at startup) and their getter functions
220 Value FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
221 int FutilityMoveCountArray[32]; // [depth]
223 inline Value futility_margin(Depth d, int mn) { return d < 7 * ONE_PLY ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE; }
224 inline int futility_move_count(Depth d) { return d < 16 * ONE_PLY ? FutilityMoveCountArray[d] : 512; }
226 // Step 14. Reduced search
228 // Reduction lookup tables (initialized at startup) and their getter functions
229 int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
231 template <NodeType PV>
232 inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
234 // Common adjustments
236 // Search depth at iteration 1
237 const Depth InitialDepth = ONE_PLY;
239 // Easy move margin. An easy move candidate must be at least this much
240 // better than the second best move.
241 const Value EasyMoveMargin = Value(0x200);
249 // Scores and number of times the best move changed for each iteration
250 Value ValueByIteration[PLY_MAX_PLUS_2];
251 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
253 // Search window management
259 // Time managment variables
260 int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
261 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
262 bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
267 std::ofstream LogFile;
269 // Multi-threads related variables
270 Depth MinimumSplitDepth;
271 int MaxThreadsPerSplitPoint;
272 ThreadsManager ThreadsMgr;
274 // Node counters, used only by thread[0] but try to keep in different cache
275 // lines (64 bytes each) from the heavy multi-thread read accessed variables.
277 int NodesBetweenPolls = 30000;
284 Value id_loop(const Position& pos, Move searchMoves[]);
285 Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
287 template <NodeType PvNode, bool SplitPoint>
288 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
290 template <NodeType PvNode>
291 inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
292 return search<PvNode, false>(pos, ss, alpha, beta, depth, ply);
295 template <NodeType PvNode>
296 void sp_search(Position& pos, SearchStack* ss, Value dumy, Value beta, Depth depth, int ply);
298 template <NodeType PvNode>
299 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
301 template <NodeType PvNode>
302 void do_sp_search(SplitPoint* sp, int threadID);
304 template <NodeType PvNode>
305 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
307 bool connected_moves(const Position& pos, Move m1, Move m2);
308 bool value_is_mate(Value value);
309 Value value_to_tt(Value v, int ply);
310 Value value_from_tt(Value v, int ply);
311 bool move_is_killer(Move m, SearchStack* ss);
312 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
313 bool connected_threat(const Position& pos, Move m, Move threat);
314 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
315 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
316 void update_killers(Move m, SearchStack* ss);
317 void update_gains(const Position& pos, Move move, Value before, Value after);
319 int current_search_time();
320 std::string value_to_uci(Value v);
324 void wait_for_stop_or_ponderhit();
325 void init_ss_array(SearchStack* ss, int size);
326 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value);
327 void insert_pv_in_tt(const Position& pos, Move pv[]);
328 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]);
330 #if !defined(_MSC_VER)
331 void *init_thread(void *threadID);
333 DWORD WINAPI init_thread(LPVOID threadID);
343 /// init_threads(), exit_threads() and nodes_searched() are helpers to
344 /// give accessibility to some TM methods from outside of current file.
346 void init_threads() { ThreadsMgr.init_threads(); }
347 void exit_threads() { ThreadsMgr.exit_threads(); }
348 int64_t nodes_searched() { return ThreadsMgr.nodes_searched(); }
351 /// init_search() is called during startup. It initializes various lookup tables
355 int d; // depth (ONE_PLY == 2)
356 int hd; // half depth (ONE_PLY == 1)
359 // Init reductions array
360 for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
362 double pvRed = 0.33 + log(double(hd)) * log(double(mc)) / 4.5;
363 double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
364 ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0);
365 ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0);
368 // Init futility margins array
369 for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
370 FutilityMarginsMatrix[d][mc] = Value(112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45);
372 // Init futility move count array
373 for (d = 0; d < 32; d++)
374 FutilityMoveCountArray[d] = int(3.001 + 0.25 * pow(d, 2.0));
378 /// perft() is our utility to verify move generation is bug free. All the legal
379 /// moves up to given depth are generated and counted and the sum returned.
381 int perft(Position& pos, Depth depth)
383 MoveStack mlist[MOVES_MAX];
388 // Generate all legal moves
389 MoveStack* last = generate_moves(pos, mlist);
391 // If we are at the last ply we don't need to do and undo
392 // the moves, just to count them.
393 if (depth <= ONE_PLY)
394 return int(last - mlist);
396 // Loop through all legal moves
398 for (MoveStack* cur = mlist; cur != last; cur++)
401 pos.do_move(m, st, ci, pos.move_is_check(m, ci));
402 sum += perft(pos, depth - ONE_PLY);
409 /// think() is the external interface to Stockfish's search, and is called when
410 /// the program receives the UCI 'go' command. It initializes various
411 /// search-related global variables, and calls root_search(). It returns false
412 /// when a quit command is received during the search.
414 bool think(const Position& pos, bool infinite, bool ponder, int time[], int increment[],
415 int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) {
417 // Initialize global search variables
418 StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
420 ThreadsMgr.resetNodeCounters();
421 SearchStartTime = get_system_time();
422 ExactMaxTime = maxTime;
425 InfiniteSearch = infinite;
426 PonderSearch = ponder;
427 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
429 // Look for a book move, only during games, not tests
430 if (UseTimeManagement && get_option_value_bool("OwnBook"))
432 if (get_option_value_string("Book File") != OpeningBook.file_name())
433 OpeningBook.open(get_option_value_string("Book File"));
435 Move bookMove = OpeningBook.get_move(pos, get_option_value_bool("Best Book Move"));
436 if (bookMove != MOVE_NONE)
439 wait_for_stop_or_ponderhit();
441 cout << "bestmove " << bookMove << endl;
446 // Read UCI option values
447 TT.set_size(get_option_value_int("Hash"));
448 if (button_was_pressed("Clear Hash"))
451 CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)"));
452 CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)"));
453 SingleEvasionExtension[1] = Depth(get_option_value_int("Single Evasion Extension (PV nodes)"));
454 SingleEvasionExtension[0] = Depth(get_option_value_int("Single Evasion Extension (non-PV nodes)"));
455 PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)"));
456 PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
457 PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
458 PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
459 PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
460 PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)"));
461 MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
462 MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
464 MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * ONE_PLY;
465 MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point");
466 MultiPV = get_option_value_int("MultiPV");
467 UseLogFile = get_option_value_bool("Use Search Log");
470 LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app);
472 read_weights(pos.side_to_move());
474 // Set the number of active threads
475 int newActiveThreads = get_option_value_int("Threads");
476 if (newActiveThreads != ThreadsMgr.active_threads())
478 ThreadsMgr.set_active_threads(newActiveThreads);
479 init_eval(ThreadsMgr.active_threads());
482 // Wake up sleeping threads
483 ThreadsMgr.wake_sleeping_threads();
486 int myTime = time[pos.side_to_move()];
487 int myIncrement = increment[pos.side_to_move()];
488 if (UseTimeManagement)
489 TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter());
491 // Set best NodesBetweenPolls interval to avoid lagging under
492 // heavy time pressure.
494 NodesBetweenPolls = Min(MaxNodes, 30000);
495 else if (myTime && myTime < 1000)
496 NodesBetweenPolls = 1000;
497 else if (myTime && myTime < 5000)
498 NodesBetweenPolls = 5000;
500 NodesBetweenPolls = 30000;
502 // Write search information to log file
504 LogFile << "Searching: " << pos.to_fen() << endl
505 << "infinite: " << infinite
506 << " ponder: " << ponder
507 << " time: " << myTime
508 << " increment: " << myIncrement
509 << " moves to go: " << movesToGo << endl;
511 // We're ready to start thinking. Call the iterative deepening loop function
512 id_loop(pos, searchMoves);
517 ThreadsMgr.put_threads_to_sleep();
525 // id_loop() is the main iterative deepening loop. It calls root_search
526 // repeatedly with increasing depth until the allocated thinking time has
527 // been consumed, the user stops the search, or the maximum search depth is
530 Value id_loop(const Position& pos, Move searchMoves[]) {
532 Position p(pos, pos.thread());
533 SearchStack ss[PLY_MAX_PLUS_2];
534 Move pv[PLY_MAX_PLUS_2];
535 Move EasyMove = MOVE_NONE;
536 Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
538 // Moves to search are verified, copied, scored and sorted
539 RootMoveList rml(p, searchMoves);
541 // Handle special case of searching on a mate/stale position
542 if (rml.move_count() == 0)
545 wait_for_stop_or_ponderhit();
547 return pos.is_check() ? -VALUE_MATE : VALUE_DRAW;
550 // Print RootMoveList startup scoring to the standard output,
551 // so to output information also for iteration 1.
552 cout << set960(p.is_chess960()) // Is enough to set once at the beginning
553 << "info depth " << 1
554 << "\ninfo depth " << 1
555 << " score " << value_to_uci(rml.move_score(0))
556 << " time " << current_search_time()
557 << " nodes " << ThreadsMgr.nodes_searched()
559 << " pv " << rml.move(0) << "\n";
564 init_ss_array(ss, PLY_MAX_PLUS_2);
565 pv[0] = pv[1] = MOVE_NONE;
566 ValueByIteration[1] = rml.move_score(0);
569 // Is one move significantly better than others after initial scoring ?
570 if ( rml.move_count() == 1
571 || rml.move_score(0) > rml.move_score(1) + EasyMoveMargin)
572 EasyMove = rml.move(0);
574 // Iterative deepening loop
575 while (Iteration < PLY_MAX)
577 // Initialize iteration
579 BestMoveChangesByIteration[Iteration] = 0;
581 cout << "info depth " << Iteration << endl;
583 // Calculate dynamic aspiration window based on previous iterations
584 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
586 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
587 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
589 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
590 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
592 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
593 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
596 // Search to the current depth, rml is updated and sorted, alpha and beta could change
597 value = root_search(p, ss, pv, rml, &alpha, &beta);
599 // Write PV to transposition table, in case the relevant entries have
600 // been overwritten during the search.
601 insert_pv_in_tt(p, pv);
604 break; // Value cannot be trusted. Break out immediately!
606 //Save info about search result
607 ValueByIteration[Iteration] = value;
609 // Drop the easy move if differs from the new best move
610 if (pv[0] != EasyMove)
611 EasyMove = MOVE_NONE;
613 if (UseTimeManagement)
616 bool stopSearch = false;
618 // Stop search early if there is only a single legal move,
619 // we search up to Iteration 6 anyway to get a proper score.
620 if (Iteration >= 6 && rml.move_count() == 1)
623 // Stop search early when the last two iterations returned a mate score
625 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
626 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
629 // Stop search early if one move seems to be much better than the others
630 int64_t nodes = ThreadsMgr.nodes_searched();
633 && ( ( rml.move_nodes(0) > (nodes * 85) / 100
634 && current_search_time() > TimeMgr.available_time() / 16)
635 ||( rml.move_nodes(0) > (nodes * 98) / 100
636 && current_search_time() > TimeMgr.available_time() / 32)))
639 // Add some extra time if the best move has changed during the last two iterations
640 if (Iteration > 5 && Iteration <= 50)
641 TimeMgr.pv_instability(BestMoveChangesByIteration[Iteration],
642 BestMoveChangesByIteration[Iteration-1]);
644 // Stop search if most of MaxSearchTime is consumed at the end of the
645 // iteration. We probably don't have enough time to search the first
646 // move at the next iteration anyway.
647 if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
653 StopOnPonderhit = true;
659 if (MaxDepth && Iteration >= MaxDepth)
663 // If we are pondering or in infinite search, we shouldn't print the
664 // best move before we are told to do so.
665 if (!AbortSearch && (PonderSearch || InfiniteSearch))
666 wait_for_stop_or_ponderhit();
668 // Print final search statistics
669 cout << "info nodes " << ThreadsMgr.nodes_searched()
671 << " time " << current_search_time() << endl;
673 // Print the best move and the ponder move to the standard output
674 if (pv[0] == MOVE_NONE)
680 assert(pv[0] != MOVE_NONE);
682 cout << "bestmove " << pv[0];
684 if (pv[1] != MOVE_NONE)
685 cout << " ponder " << pv[1];
692 dbg_print_mean(LogFile);
694 if (dbg_show_hit_rate)
695 dbg_print_hit_rate(LogFile);
697 LogFile << "\nNodes: " << ThreadsMgr.nodes_searched()
698 << "\nNodes/second: " << nps()
699 << "\nBest move: " << move_to_san(p, pv[0]);
702 p.do_move(pv[0], st);
703 LogFile << "\nPonder move: "
704 << move_to_san(p, pv[1]) // Works also with MOVE_NONE
707 return rml.move_score(0);
711 // root_search() is the function which searches the root node. It is
712 // similar to search_pv except that it uses a different move ordering
713 // scheme, prints some information to the standard output and handles
714 // the fail low/high loops.
716 Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
722 Depth depth, ext, newDepth;
723 Value value, evalMargin, alpha, beta;
724 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
725 int researchCountFH, researchCountFL;
727 researchCountFH = researchCountFL = 0;
730 isCheck = pos.is_check();
731 depth = (Iteration - 2) * ONE_PLY + InitialDepth;
733 // Step 1. Initialize node (polling is omitted at root)
734 ss->currentMove = ss->bestMove = MOVE_NONE;
736 // Step 2. Check for aborted search (omitted at root)
737 // Step 3. Mate distance pruning (omitted at root)
738 // Step 4. Transposition table lookup (omitted at root)
740 // Step 5. Evaluate the position statically
741 // At root we do this only to get reference value for child nodes
742 ss->eval = isCheck ? VALUE_NONE : evaluate(pos, evalMargin);
744 // Step 6. Razoring (omitted at root)
745 // Step 7. Static null move pruning (omitted at root)
746 // Step 8. Null move search with verification search (omitted at root)
747 // Step 9. Internal iterative deepening (omitted at root)
749 // Step extra. Fail low loop
750 // We start with small aspiration window and in case of fail low, we research
751 // with bigger window until we are not failing low anymore.
754 // Sort the moves before to (re)search
755 rml.score_moves(pos);
758 // Step 10. Loop through all moves in the root move list
759 for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
761 // This is used by time management
762 FirstRootMove = (i == 0);
764 // Save the current node count before the move is searched
765 nodes = ThreadsMgr.nodes_searched();
767 // Pick the next root move, and print the move and the move number to
768 // the standard output.
769 move = ss->currentMove = rml.move(i);
771 if (current_search_time() >= 1000)
772 cout << "info currmove " << move
773 << " currmovenumber " << i + 1 << endl;
775 moveIsCheck = pos.move_is_check(move);
776 captureOrPromotion = pos.move_is_capture_or_promotion(move);
778 // Step 11. Decide the new search depth
779 ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
780 newDepth = depth + ext;
782 // Step 12. Futility pruning (omitted at root)
784 // Step extra. Fail high loop
785 // If move fails high, we research with bigger window until we are not failing
787 value = - VALUE_INFINITE;
791 // Step 13. Make the move
792 pos.do_move(move, st, ci, moveIsCheck);
794 // Step extra. pv search
795 // We do pv search for first moves (i < MultiPV)
796 // and for fail high research (value > alpha)
797 if (i < MultiPV || value > alpha)
799 // Aspiration window is disabled in multi-pv case
801 alpha = -VALUE_INFINITE;
803 // Full depth PV search, done on first move or after a fail high
804 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
808 // Step 14. Reduced search
809 // if the move fails high will be re-searched at full depth
810 bool doFullDepthSearch = true;
812 if ( depth >= 3 * ONE_PLY
814 && !captureOrPromotion
815 && !move_is_castle(move))
817 ss->reduction = reduction<PV>(depth, i - MultiPV + 2);
820 assert(newDepth-ss->reduction >= ONE_PLY);
822 // Reduced depth non-pv search using alpha as upperbound
823 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
824 doFullDepthSearch = (value > alpha);
827 // The move failed high, but if reduction is very big we could
828 // face a false positive, retry with a less aggressive reduction,
829 // if the move fails high again then go with full depth search.
830 if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
832 assert(newDepth - ONE_PLY >= ONE_PLY);
834 ss->reduction = ONE_PLY;
835 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
836 doFullDepthSearch = (value > alpha);
838 ss->reduction = DEPTH_ZERO; // Restore original reduction
841 // Step 15. Full depth search
842 if (doFullDepthSearch)
844 // Full depth non-pv search using alpha as upperbound
845 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, 1);
847 // If we are above alpha then research at same depth but as PV
848 // to get a correct score or eventually a fail high above beta.
850 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
854 // Step 16. Undo move
857 // Can we exit fail high loop ?
858 if (AbortSearch || value < beta)
861 // We are failing high and going to do a research. It's important to update
862 // the score before research in case we run out of time while researching.
863 rml.set_move_score(i, value);
865 extract_pv_from_tt(pos, move, pv);
866 rml.set_move_pv(i, pv);
868 // Print information to the standard output
869 print_pv_info(pos, pv, alpha, beta, value);
871 // Prepare for a research after a fail high, each time with a wider window
872 *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
875 } // End of fail high loop
877 // Finished searching the move. If AbortSearch is true, the search
878 // was aborted because the user interrupted the search or because we
879 // ran out of time. In this case, the return value of the search cannot
880 // be trusted, and we break out of the loop without updating the best
885 // Remember searched nodes counts for this move
886 rml.add_move_nodes(i, ThreadsMgr.nodes_searched() - nodes);
888 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
889 assert(value < beta);
891 // Step 17. Check for new best move
892 if (value <= alpha && i >= MultiPV)
893 rml.set_move_score(i, -VALUE_INFINITE);
896 // PV move or new best move!
899 rml.set_move_score(i, value);
901 extract_pv_from_tt(pos, move, pv);
902 rml.set_move_pv(i, pv);
906 // We record how often the best move has been changed in each
907 // iteration. This information is used for time managment: When
908 // the best move changes frequently, we allocate some more time.
910 BestMoveChangesByIteration[Iteration]++;
912 // Print information to the standard output
913 print_pv_info(pos, pv, alpha, beta, value);
915 // Raise alpha to setup proper non-pv search upper bound
922 for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
924 cout << "info multipv " << j + 1
925 << " score " << value_to_uci(rml.move_score(j))
926 << " depth " << (j <= i ? Iteration : Iteration - 1)
927 << " time " << current_search_time()
928 << " nodes " << ThreadsMgr.nodes_searched()
932 for (int k = 0; rml.move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
933 cout << rml.move_pv(j, k) << " ";
937 alpha = rml.move_score(Min(i, MultiPV - 1));
939 } // PV move or new best move
941 assert(alpha >= *alphaPtr);
943 AspirationFailLow = (alpha == *alphaPtr);
945 if (AspirationFailLow && StopOnPonderhit)
946 StopOnPonderhit = false;
949 // Can we exit fail low loop ?
950 if (AbortSearch || !AspirationFailLow)
953 // Prepare for a research after a fail low, each time with a wider window
954 *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
959 // Sort the moves before to return
966 // search<>() is the main search function for both PV and non-PV nodes
968 template <NodeType PvNode, bool SplitPoint>
969 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
971 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
972 assert(beta > alpha && beta <= VALUE_INFINITE);
973 assert(PvNode || alpha == beta - 1);
974 assert(ply > 0 && ply < PLY_MAX);
975 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
977 Move movesSearched[MOVES_MAX];
981 Move ttMove, move, excludedMove, threatMove;
983 Value bestValue, value, evalMargin, oldAlpha;
984 Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
985 bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
986 bool mateThreat = false;
988 int threadID = pos.thread();
989 refinedValue = bestValue = value = -VALUE_INFINITE;
991 isCheck = pos.is_check();
996 ttMove = excludedMove = MOVE_NONE;
997 threatMove = ss->sp->threatMove;
998 mateThreat = ss->sp->mateThreat;
1002 // Step 1. Initialize node and poll. Polling can abort search
1003 ThreadsMgr.incrementNodeCounter(threadID);
1004 ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
1005 (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
1007 if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
1013 // Step 2. Check for aborted search and immediate draw
1014 if (AbortSearch || ThreadsMgr.thread_should_stop(threadID))
1017 if (pos.is_draw() || ply >= PLY_MAX - 1)
1020 // Step 3. Mate distance pruning
1021 alpha = Max(value_mated_in(ply), alpha);
1022 beta = Min(value_mate_in(ply+1), beta);
1026 // Step 4. Transposition table lookup
1028 // We don't want the score of a partial search to overwrite a previous full search
1029 // TT value, so we use a different position key in case of an excluded move exists.
1030 excludedMove = ss->excludedMove;
1031 posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1033 tte = TT.retrieve(posKey);
1034 ttMove = (tte ? tte->move() : MOVE_NONE);
1036 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1037 // This is to avoid problems in the following areas:
1039 // * Repetition draw detection
1040 // * Fifty move rule detection
1041 // * Searching for a mate
1042 // * Printing of full PV line
1044 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1046 // Refresh tte entry to avoid aging
1047 TT.store(posKey, tte->value(), tte->type(), tte->depth(), ttMove, tte->static_value(), tte->static_value_margin());
1049 ss->bestMove = ttMove; // Can be MOVE_NONE
1050 return value_from_tt(tte->value(), ply);
1053 // Step 5. Evaluate the position statically and
1054 // update gain statistics of parent move.
1056 ss->eval = evalMargin = VALUE_NONE;
1059 assert(tte->static_value() != VALUE_NONE);
1061 ss->eval = tte->static_value();
1062 evalMargin = tte->static_value_margin();
1063 refinedValue = refine_eval(tte, ss->eval, ply);
1067 refinedValue = ss->eval = evaluate(pos, evalMargin);
1068 TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1071 // Save gain for the parent non-capture move
1072 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1074 // Step 6. Razoring (is omitted in PV nodes)
1076 && depth < RazorDepth
1078 && refinedValue < beta - razor_margin(depth)
1079 && ttMove == MOVE_NONE
1080 && (ss-1)->currentMove != MOVE_NULL
1081 && !value_is_mate(beta)
1082 && !pos.has_pawn_on_7th(pos.side_to_move()))
1084 Value rbeta = beta - razor_margin(depth);
1085 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply);
1087 // Logically we should return (v + razor_margin(depth)), but
1088 // surprisingly this did slightly weaker in tests.
1092 // Step 7. Static null move pruning (is omitted in PV nodes)
1093 // We're betting that the opponent doesn't have a move that will reduce
1094 // the score by more than futility_margin(depth) if we do a null move.
1096 && !ss->skipNullMove
1097 && depth < RazorDepth
1099 && refinedValue >= beta + futility_margin(depth, 0)
1100 && !value_is_mate(beta)
1101 && pos.non_pawn_material(pos.side_to_move()))
1102 return refinedValue - futility_margin(depth, 0);
1104 // Step 8. Null move search with verification search (is omitted in PV nodes)
1106 && !ss->skipNullMove
1109 && refinedValue >= beta
1110 && !value_is_mate(beta)
1111 && pos.non_pawn_material(pos.side_to_move()))
1113 ss->currentMove = MOVE_NULL;
1115 // Null move dynamic reduction based on depth
1116 int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
1118 // Null move dynamic reduction based on value
1119 if (refinedValue - beta > PawnValueMidgame)
1122 pos.do_null_move(st);
1123 (ss+1)->skipNullMove = true;
1125 nullValue = depth-R*ONE_PLY < ONE_PLY ? -qsearch<NonPV>(pos, ss+1, -beta, -alpha, DEPTH_ZERO, ply+1)
1126 : - search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1);
1127 (ss+1)->skipNullMove = false;
1128 pos.undo_null_move();
1130 if (nullValue >= beta)
1132 // Do not return unproven mate scores
1133 if (nullValue >= value_mate_in(PLY_MAX))
1136 if (depth < 6 * ONE_PLY)
1139 // Do verification search at high depths
1140 ss->skipNullMove = true;
1141 Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY, ply);
1142 ss->skipNullMove = false;
1149 // The null move failed low, which means that we may be faced with
1150 // some kind of threat. If the previous move was reduced, check if
1151 // the move that refuted the null move was somehow connected to the
1152 // move which was reduced. If a connection is found, return a fail
1153 // low score (which will cause the reduced move to fail high in the
1154 // parent node, which will trigger a re-search with full depth).
1155 if (nullValue == value_mated_in(ply + 2))
1158 threatMove = (ss+1)->bestMove;
1159 if ( depth < ThreatDepth
1160 && (ss-1)->reduction
1161 && connected_moves(pos, (ss-1)->currentMove, threatMove))
1166 // Step 9. Internal iterative deepening
1167 if ( depth >= IIDDepth[PvNode]
1168 && ttMove == MOVE_NONE
1169 && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
1171 Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
1173 ss->skipNullMove = true;
1174 search<PvNode>(pos, ss, alpha, beta, d, ply);
1175 ss->skipNullMove = false;
1177 ttMove = ss->bestMove;
1178 tte = TT.retrieve(posKey);
1181 // Expensive mate threat detection (only for PV nodes)
1183 mateThreat = pos.has_mate_threat();
1187 // Initialize a MovePicker object for the current position
1188 MovePicker mpBase = MovePicker(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
1189 MovePicker& mp = SplitPoint ? *ss->sp->mp : mpBase;
1191 ss->bestMove = MOVE_NONE;
1192 singleEvasion = SplitPoint ? false : isCheck && mp.number_of_evasions() == 1;
1193 futilityBase = SplitPoint ? ss->eval : ss->eval + evalMargin;
1194 singularExtensionNode = !SplitPoint
1195 && depth >= SingularExtensionDepth[PvNode]
1198 && !excludedMove // Do not allow recursive singular extension search
1199 && (tte->type() & VALUE_TYPE_LOWER)
1200 && tte->depth() >= depth - 3 * ONE_PLY;
1202 // Step 10. Loop through moves
1203 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1206 lock_grab(&(ss->sp->lock));
1207 bestValue = ss->sp->bestValue;
1210 while ( bestValue < beta
1211 && (move = mp.get_next_move()) != MOVE_NONE
1212 && !ThreadsMgr.thread_should_stop(threadID))
1216 moveCount = ++ss->sp->moveCount;
1217 lock_release(&(ss->sp->lock));
1220 assert(move_is_ok(move));
1222 if (move == excludedMove)
1225 moveIsCheck = pos.move_is_check(move, ci);
1226 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1228 // Step 11. Decide the new search depth
1229 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1231 // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s),
1232 // and just one fails high on (alpha, beta), then that move is singular and should be extended.
1233 // To verify this we do a reduced search on all the other moves but the ttMove, if result is
1234 // lower then ttValue minus a margin then we extend ttMove.
1235 if ( singularExtensionNode
1236 && move == tte->move()
1239 Value ttValue = value_from_tt(tte->value(), ply);
1241 if (abs(ttValue) < VALUE_KNOWN_WIN)
1243 Value b = ttValue - SingularExtensionMargin;
1244 ss->excludedMove = move;
1245 ss->skipNullMove = true;
1246 Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
1247 ss->skipNullMove = false;
1248 ss->excludedMove = MOVE_NONE;
1249 ss->bestMove = MOVE_NONE;
1255 newDepth = depth - ONE_PLY + ext;
1257 // Update current move (this must be done after singular extension search)
1258 movesSearched[moveCount++] = ss->currentMove = move;
1260 // Step 12. Futility pruning (is omitted in PV nodes)
1262 && !captureOrPromotion
1266 && !move_is_castle(move))
1268 // Move count based pruning
1269 if ( moveCount >= futility_move_count(depth)
1270 && !(threatMove && connected_threat(pos, move, threatMove))
1271 && bestValue > value_mated_in(PLY_MAX)) // FIXME bestValue is racy
1274 lock_grab(&(ss->sp->lock));
1278 // Value based pruning
1279 // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
1280 // but fixing this made program slightly weaker.
1281 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1282 futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount)
1283 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1285 if (futilityValueScaled < beta)
1289 lock_grab(&(ss->sp->lock));
1290 if (futilityValueScaled > ss->sp->bestValue)
1291 ss->sp->bestValue = futilityValueScaled;
1293 else if (futilityValueScaled > bestValue)
1294 bestValue = futilityValueScaled;
1299 // Step 13. Make the move
1300 pos.do_move(move, st, ci, moveIsCheck);
1302 // Step extra. pv search (only in PV nodes)
1303 // The first move in list is the expected PV
1304 if (!SplitPoint && PvNode && moveCount == 1)
1305 value = newDepth < ONE_PLY ? -qsearch<PV>(pos, ss+1, -beta, -alpha, DEPTH_ZERO, ply+1)
1306 : - search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1309 // Step 14. Reduced depth search
1310 // If the move fails high will be re-searched at full depth.
1311 bool doFullDepthSearch = true;
1313 if ( depth >= 3 * ONE_PLY
1314 && !captureOrPromotion
1316 && !move_is_castle(move)
1317 && !move_is_killer(move, ss))
1319 ss->reduction = reduction<PvNode>(depth, moveCount);
1322 alpha = SplitPoint ? ss->sp->alpha : alpha;
1323 Depth d = newDepth - ss->reduction;
1324 value = d < ONE_PLY ? -qsearch<NonPV>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO, ply+1)
1325 : - search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1327 doFullDepthSearch = (value > alpha);
1330 // The move failed high, but if reduction is very big we could
1331 // face a false positive, retry with a less aggressive reduction,
1332 // if the move fails high again then go with full depth search.
1333 if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
1335 assert(newDepth - ONE_PLY >= ONE_PLY);
1337 ss->reduction = ONE_PLY;
1338 alpha = SplitPoint ? ss->sp->alpha : alpha;
1339 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, ply+1);
1340 doFullDepthSearch = (value > alpha);
1342 ss->reduction = DEPTH_ZERO; // Restore original reduction
1345 // Step 15. Full depth search
1346 if (doFullDepthSearch)
1348 alpha = SplitPoint ? ss->sp->alpha : alpha;
1349 value = newDepth < ONE_PLY ? -qsearch<NonPV>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO, ply+1)
1350 : - search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1352 // Step extra. pv search (only in PV nodes)
1353 // Search only for possible new PV nodes, if instead value >= beta then
1354 // parent node fails low with value <= alpha and tries another move.
1355 if (PvNode && value > alpha && value < beta)
1356 value = newDepth < ONE_PLY ? -qsearch<PV>(pos, ss+1, -beta, -alpha, DEPTH_ZERO, ply+1)
1357 : - search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1361 // Step 16. Undo move
1362 pos.undo_move(move);
1364 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1366 // Step 17. Check for new best move
1369 lock_grab(&(ss->sp->lock));
1370 bestValue = ss->sp->bestValue;
1371 alpha = ss->sp->alpha;
1374 if (value > bestValue && !(SplitPoint && ThreadsMgr.thread_should_stop(threadID)))
1379 if (SplitPoint && (!PvNode || value >= beta))
1380 ss->sp->stopRequest = true;
1382 if (PvNode && value < beta) // We want always alpha < beta
1385 if (value == value_mate_in(ply + 1))
1386 ss->mateKiller = move;
1388 ss->bestMove = move;
1392 ss->sp->bestValue = bestValue;
1393 ss->sp->alpha = alpha;
1394 ss->sp->parentSstack->bestMove = ss->bestMove;
1398 // Step 18. Check for split
1400 && depth >= MinimumSplitDepth
1401 && ThreadsMgr.active_threads() > 1
1403 && ThreadsMgr.available_thread_exists(threadID)
1405 && !ThreadsMgr.thread_should_stop(threadID)
1407 ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1408 threatMove, mateThreat, moveCount, &mp, PvNode);
1413 /* Here we have the lock still grabbed */
1414 ss->sp->slaves[threadID] = 0;
1415 lock_release(&(ss->sp->lock));
1419 // Step 19. Check for mate and stalemate
1420 // All legal moves have been searched and if there are
1421 // no legal moves, it must be mate or stalemate.
1422 // If one move was excluded return fail low score.
1424 return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW;
1426 // Step 20. Update tables
1427 // If the search is not aborted, update the transposition table,
1428 // history counters, and killer moves.
1429 if (AbortSearch || ThreadsMgr.thread_should_stop(threadID))
1432 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1433 move = (bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove);
1434 TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, evalMargin);
1436 // Update killers and history only for non capture moves that fails high
1437 if ( bestValue >= beta
1438 && !pos.move_is_capture_or_promotion(move))
1440 update_history(pos, move, depth, movesSearched, moveCount);
1441 update_killers(move, ss);
1444 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1450 // qsearch() is the quiescence search function, which is called by the main
1451 // search function when the remaining depth is zero (or, to be more precise,
1452 // less than ONE_PLY).
1454 template <NodeType PvNode>
1455 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1457 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1458 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1459 assert(PvNode || alpha == beta - 1);
1461 assert(ply > 0 && ply < PLY_MAX);
1462 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1466 Value bestValue, value, evalMargin, futilityValue, futilityBase;
1467 bool isCheck, deepChecks, enoughMaterial, moveIsCheck, evasionPrunable;
1469 Value oldAlpha = alpha;
1471 ThreadsMgr.incrementNodeCounter(pos.thread());
1472 ss->bestMove = ss->currentMove = MOVE_NONE;
1474 // Check for an instant draw or maximum ply reached
1475 if (pos.is_draw() || ply >= PLY_MAX - 1)
1478 // Transposition table lookup. At PV nodes, we don't use the TT for
1479 // pruning, but only for move ordering.
1480 tte = TT.retrieve(pos.get_key());
1481 ttMove = (tte ? tte->move() : MOVE_NONE);
1483 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1485 ss->bestMove = ttMove; // Can be MOVE_NONE
1486 return value_from_tt(tte->value(), ply);
1489 isCheck = pos.is_check();
1491 // Evaluate the position statically
1494 bestValue = futilityBase = -VALUE_INFINITE;
1495 ss->eval = evalMargin = VALUE_NONE;
1496 deepChecks = enoughMaterial = false;
1502 assert(tte->static_value() != VALUE_NONE);
1504 evalMargin = tte->static_value_margin();
1505 ss->eval = bestValue = tte->static_value();
1508 ss->eval = bestValue = evaluate(pos, evalMargin);
1510 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1512 // Stand pat. Return immediately if static value is at least beta
1513 if (bestValue >= beta)
1516 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1521 if (PvNode && bestValue > alpha)
1524 // If we are near beta then try to get a cutoff pushing checks a bit further
1525 deepChecks = (depth == -ONE_PLY && bestValue >= beta - PawnValueMidgame / 8);
1527 // Futility pruning parameters, not needed when in check
1528 futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1529 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1532 // Initialize a MovePicker object for the current position, and prepare
1533 // to search the moves. Because the depth is <= 0 here, only captures,
1534 // queen promotions and checks (only if depth == 0 or depth == -ONE_PLY
1535 // and we are near beta) will be generated.
1536 MovePicker mp = MovePicker(pos, ttMove, deepChecks ? DEPTH_ZERO : depth, H);
1539 // Loop through the moves until no moves remain or a beta cutoff occurs
1540 while ( alpha < beta
1541 && (move = mp.get_next_move()) != MOVE_NONE)
1543 assert(move_is_ok(move));
1545 moveIsCheck = pos.move_is_check(move, ci);
1553 && !move_is_promotion(move)
1554 && !pos.move_is_passed_pawn_push(move))
1556 futilityValue = futilityBase
1557 + pos.endgame_value_of_piece_on(move_to(move))
1558 + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1560 if (futilityValue < alpha)
1562 if (futilityValue > bestValue)
1563 bestValue = futilityValue;
1568 // Detect non-capture evasions that are candidate to be pruned
1569 evasionPrunable = isCheck
1570 && bestValue > value_mated_in(PLY_MAX)
1571 && !pos.move_is_capture(move)
1572 && !pos.can_castle(pos.side_to_move());
1574 // Don't search moves with negative SEE values
1576 && (!isCheck || evasionPrunable)
1578 && !move_is_promotion(move)
1579 && pos.see_sign(move) < 0)
1582 // Update current move
1583 ss->currentMove = move;
1585 // Make and search the move
1586 pos.do_move(move, st, ci, moveIsCheck);
1587 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1);
1588 pos.undo_move(move);
1590 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1593 if (value > bestValue)
1599 ss->bestMove = move;
1604 // All legal moves have been searched. A special case: If we're in check
1605 // and no legal moves were found, it is checkmate.
1606 if (isCheck && bestValue == -VALUE_INFINITE)
1607 return value_mated_in(ply);
1609 // Update transposition table
1610 Depth d = (depth == DEPTH_ZERO ? DEPTH_ZERO : DEPTH_ZERO - ONE_PLY);
1611 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1612 TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, d, ss->bestMove, ss->eval, evalMargin);
1614 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1620 // sp_search() is used to search from a split point. This function is called
1621 // by each thread working at the split point. It is similar to the normal
1622 // search() function, but simpler. Because we have already probed the hash
1623 // table, done a null move search, and searched the first move before
1624 // splitting, we don't have to repeat all this work in sp_search(). We
1625 // also don't need to store anything to the hash table here: This is taken
1626 // care of after we return from the split point.
1628 template <NodeType PvNode>
1629 void do_sp_search(SplitPoint* sp, int threadID) {
1631 assert(threadID >= 0 && threadID < ThreadsMgr.active_threads());
1632 assert(ThreadsMgr.active_threads() > 1);
1634 Position pos(*sp->pos, threadID);
1635 SearchStack* ss = sp->sstack[threadID] + 1;
1638 search<PvNode, true>(pos, ss, sp->alpha, sp->beta, sp->depth, sp->ply);
1641 template <NodeType PvNode>
1642 void sp_search(Position& pos, SearchStack* ss, Value, Value beta, Depth depth, int ply) {
1646 Depth ext, newDepth;
1648 Value futilityValueScaled; // NonPV specific
1649 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
1651 value = -VALUE_INFINITE;
1652 SplitPoint* sp = ss->sp;
1653 Move threatMove = sp->threatMove;
1654 MovePicker& mp = *sp->mp;
1655 int threadID = pos.thread();
1658 isCheck = pos.is_check();
1660 // Step 10. Loop through moves
1661 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1662 lock_grab(&(sp->lock));
1664 while ( sp->bestValue < beta
1665 && (move = mp.get_next_move()) != MOVE_NONE
1666 && !ThreadsMgr.thread_should_stop(threadID))
1668 moveCount = ++sp->moveCount;
1669 lock_release(&(sp->lock));
1671 assert(move_is_ok(move));
1673 moveIsCheck = pos.move_is_check(move, ci);
1674 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1676 // Step 11. Decide the new search depth
1677 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous);
1678 newDepth = depth - ONE_PLY + ext;
1680 // Update current move
1681 ss->currentMove = move;
1683 // Step 12. Futility pruning (is omitted in PV nodes)
1685 && !captureOrPromotion
1688 && !move_is_castle(move))
1690 // Move count based pruning
1691 if ( moveCount >= futility_move_count(depth)
1692 && !(threatMove && connected_threat(pos, move, threatMove))
1693 && sp->bestValue > value_mated_in(PLY_MAX))
1695 lock_grab(&(sp->lock));
1699 // Value based pruning
1700 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1701 futilityValueScaled = ss->eval + futility_margin(predictedDepth, moveCount)
1702 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1704 if (futilityValueScaled < beta)
1706 lock_grab(&(sp->lock));
1708 if (futilityValueScaled > sp->bestValue)
1709 sp->bestValue = futilityValueScaled;
1714 // Step 13. Make the move
1715 pos.do_move(move, st, ci, moveIsCheck);
1717 // Step 14. Reduced search
1718 // If the move fails high will be re-searched at full depth.
1719 bool doFullDepthSearch = true;
1721 if ( !captureOrPromotion
1723 && !move_is_castle(move)
1724 && !move_is_killer(move, ss))
1726 ss->reduction = reduction<PvNode>(depth, moveCount);
1729 Value localAlpha = sp->alpha;
1730 Depth d = newDepth - ss->reduction;
1731 value = d < ONE_PLY ? -qsearch<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, DEPTH_ZERO, ply+1)
1732 : - search<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, d, ply+1);
1734 doFullDepthSearch = (value > localAlpha);
1737 // The move failed high, but if reduction is very big we could
1738 // face a false positive, retry with a less aggressive reduction,
1739 // if the move fails high again then go with full depth search.
1740 if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
1742 assert(newDepth - ONE_PLY >= ONE_PLY);
1744 ss->reduction = ONE_PLY;
1745 Value localAlpha = sp->alpha;
1746 value = -search<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, newDepth-ss->reduction, ply+1);
1747 doFullDepthSearch = (value > localAlpha);
1749 ss->reduction = DEPTH_ZERO; // Restore original reduction
1752 // Step 15. Full depth search
1753 if (doFullDepthSearch)
1755 Value localAlpha = sp->alpha;
1756 value = newDepth < ONE_PLY ? -qsearch<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, DEPTH_ZERO, ply+1)
1757 : - search<NonPV>(pos, ss+1, -(localAlpha+1), -localAlpha, newDepth, ply+1);
1759 // Step extra. pv search (only in PV nodes)
1760 // Search only for possible new PV nodes, if instead value >= beta then
1761 // parent node fails low with value <= alpha and tries another move.
1762 if (PvNode && value > localAlpha && value < beta)
1763 value = newDepth < ONE_PLY ? -qsearch<PV>(pos, ss+1, -beta, -sp->alpha, DEPTH_ZERO, ply+1)
1764 : - search<PV>(pos, ss+1, -beta, -sp->alpha, newDepth, ply+1);
1767 // Step 16. Undo move
1768 pos.undo_move(move);
1770 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1772 // Step 17. Check for new best move
1773 lock_grab(&(sp->lock));
1775 if (value > sp->bestValue && !ThreadsMgr.thread_should_stop(threadID))
1777 sp->bestValue = value;
1778 if (value > sp->alpha)
1780 if (!PvNode || value >= beta)
1781 sp->stopRequest = true;
1783 if (PvNode && value < beta) // We want always sp->alpha < beta
1786 sp->parentSstack->bestMove = ss->bestMove = move;
1791 /* Here we have the lock still grabbed */
1793 sp->slaves[threadID] = 0;
1795 lock_release(&(sp->lock));
1799 // connected_moves() tests whether two moves are 'connected' in the sense
1800 // that the first move somehow made the second move possible (for instance
1801 // if the moving piece is the same in both moves). The first move is assumed
1802 // to be the move that was made to reach the current position, while the
1803 // second move is assumed to be a move from the current position.
1805 bool connected_moves(const Position& pos, Move m1, Move m2) {
1807 Square f1, t1, f2, t2;
1810 assert(move_is_ok(m1));
1811 assert(move_is_ok(m2));
1813 if (m2 == MOVE_NONE)
1816 // Case 1: The moving piece is the same in both moves
1822 // Case 2: The destination square for m2 was vacated by m1
1828 // Case 3: Moving through the vacated square
1829 if ( piece_is_slider(pos.piece_on(f2))
1830 && bit_is_set(squares_between(f2, t2), f1))
1833 // Case 4: The destination square for m2 is defended by the moving piece in m1
1834 p = pos.piece_on(t1);
1835 if (bit_is_set(pos.attacks_from(p, t1), t2))
1838 // Case 5: Discovered check, checking piece is the piece moved in m1
1839 if ( piece_is_slider(p)
1840 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1841 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1843 // discovered_check_candidates() works also if the Position's side to
1844 // move is the opposite of the checking piece.
1845 Color them = opposite_color(pos.side_to_move());
1846 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1848 if (bit_is_set(dcCandidates, f2))
1855 // value_is_mate() checks if the given value is a mate one eventually
1856 // compensated for the ply.
1858 bool value_is_mate(Value value) {
1860 assert(abs(value) <= VALUE_INFINITE);
1862 return value <= value_mated_in(PLY_MAX)
1863 || value >= value_mate_in(PLY_MAX);
1867 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1868 // "plies to mate from the current ply". Non-mate scores are unchanged.
1869 // The function is called before storing a value to the transposition table.
1871 Value value_to_tt(Value v, int ply) {
1873 if (v >= value_mate_in(PLY_MAX))
1876 if (v <= value_mated_in(PLY_MAX))
1883 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1884 // the transposition table to a mate score corrected for the current ply.
1886 Value value_from_tt(Value v, int ply) {
1888 if (v >= value_mate_in(PLY_MAX))
1891 if (v <= value_mated_in(PLY_MAX))
1898 // move_is_killer() checks if the given move is among the killer moves
1900 bool move_is_killer(Move m, SearchStack* ss) {
1902 if (ss->killers[0] == m || ss->killers[1] == m)
1909 // extension() decides whether a move should be searched with normal depth,
1910 // or with extended depth. Certain classes of moves (checking moves, in
1911 // particular) are searched with bigger depth than ordinary moves and in
1912 // any case are marked as 'dangerous'. Note that also if a move is not
1913 // extended, as example because the corresponding UCI option is set to zero,
1914 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1915 template <NodeType PvNode>
1916 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1917 bool singleEvasion, bool mateThreat, bool* dangerous) {
1919 assert(m != MOVE_NONE);
1921 Depth result = DEPTH_ZERO;
1922 *dangerous = moveIsCheck | singleEvasion | mateThreat;
1926 if (moveIsCheck && pos.see_sign(m) >= 0)
1927 result += CheckExtension[PvNode];
1930 result += SingleEvasionExtension[PvNode];
1933 result += MateThreatExtension[PvNode];
1936 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1938 Color c = pos.side_to_move();
1939 if (relative_rank(c, move_to(m)) == RANK_7)
1941 result += PawnPushTo7thExtension[PvNode];
1944 if (pos.pawn_is_passed(c, move_to(m)))
1946 result += PassedPawnExtension[PvNode];
1951 if ( captureOrPromotion
1952 && pos.type_of_piece_on(move_to(m)) != PAWN
1953 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1954 - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1955 && !move_is_promotion(m)
1958 result += PawnEndgameExtension[PvNode];
1963 && captureOrPromotion
1964 && pos.type_of_piece_on(move_to(m)) != PAWN
1965 && pos.see_sign(m) >= 0)
1967 result += ONE_PLY / 2;
1971 return Min(result, ONE_PLY);
1975 // connected_threat() tests whether it is safe to forward prune a move or if
1976 // is somehow coonected to the threat move returned by null search.
1978 bool connected_threat(const Position& pos, Move m, Move threat) {
1980 assert(move_is_ok(m));
1981 assert(threat && move_is_ok(threat));
1982 assert(!pos.move_is_check(m));
1983 assert(!pos.move_is_capture_or_promotion(m));
1984 assert(!pos.move_is_passed_pawn_push(m));
1986 Square mfrom, mto, tfrom, tto;
1988 mfrom = move_from(m);
1990 tfrom = move_from(threat);
1991 tto = move_to(threat);
1993 // Case 1: Don't prune moves which move the threatened piece
1997 // Case 2: If the threatened piece has value less than or equal to the
1998 // value of the threatening piece, don't prune move which defend it.
1999 if ( pos.move_is_capture(threat)
2000 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
2001 || pos.type_of_piece_on(tfrom) == KING)
2002 && pos.move_attacks_square(m, tto))
2005 // Case 3: If the moving piece in the threatened move is a slider, don't
2006 // prune safe moves which block its ray.
2007 if ( piece_is_slider(pos.piece_on(tfrom))
2008 && bit_is_set(squares_between(tfrom, tto), mto)
2009 && pos.see_sign(m) >= 0)
2016 // ok_to_use_TT() returns true if a transposition table score
2017 // can be used at a given point in search.
2019 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
2021 Value v = value_from_tt(tte->value(), ply);
2023 return ( tte->depth() >= depth
2024 || v >= Max(value_mate_in(PLY_MAX), beta)
2025 || v < Min(value_mated_in(PLY_MAX), beta))
2027 && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
2028 || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
2032 // refine_eval() returns the transposition table score if
2033 // possible otherwise falls back on static position evaluation.
2035 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
2039 Value v = value_from_tt(tte->value(), ply);
2041 if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
2042 || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
2049 // update_history() registers a good move that produced a beta-cutoff
2050 // in history and marks as failures all the other moves of that ply.
2052 void update_history(const Position& pos, Move move, Depth depth,
2053 Move movesSearched[], int moveCount) {
2057 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
2059 for (int i = 0; i < moveCount - 1; i++)
2061 m = movesSearched[i];
2065 if (!pos.move_is_capture_or_promotion(m))
2066 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
2071 // update_killers() add a good move that produced a beta-cutoff
2072 // among the killer moves of that ply.
2074 void update_killers(Move m, SearchStack* ss) {
2076 if (m == ss->killers[0])
2079 ss->killers[1] = ss->killers[0];
2084 // update_gains() updates the gains table of a non-capture move given
2085 // the static position evaluation before and after the move.
2087 void update_gains(const Position& pos, Move m, Value before, Value after) {
2090 && before != VALUE_NONE
2091 && after != VALUE_NONE
2092 && pos.captured_piece_type() == PIECE_TYPE_NONE
2093 && !move_is_special(m))
2094 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
2098 // current_search_time() returns the number of milliseconds which have passed
2099 // since the beginning of the current search.
2101 int current_search_time() {
2103 return get_system_time() - SearchStartTime;
2107 // value_to_uci() converts a value to a string suitable for use with the UCI protocol
2109 std::string value_to_uci(Value v) {
2111 std::stringstream s;
2113 if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
2114 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100
2116 s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
2121 // nps() computes the current nodes/second count.
2125 int t = current_search_time();
2126 return (t > 0 ? int((ThreadsMgr.nodes_searched() * 1000) / t) : 0);
2130 // poll() performs two different functions: It polls for user input, and it
2131 // looks at the time consumed so far and decides if it's time to abort the
2136 static int lastInfoTime;
2137 int t = current_search_time();
2142 // We are line oriented, don't read single chars
2143 std::string command;
2145 if (!std::getline(std::cin, command))
2148 if (command == "quit")
2151 PonderSearch = false;
2155 else if (command == "stop")
2158 PonderSearch = false;
2160 else if (command == "ponderhit")
2164 // Print search information
2168 else if (lastInfoTime > t)
2169 // HACK: Must be a new search where we searched less than
2170 // NodesBetweenPolls nodes during the first second of search.
2173 else if (t - lastInfoTime >= 1000)
2180 if (dbg_show_hit_rate)
2181 dbg_print_hit_rate();
2183 cout << "info nodes " << ThreadsMgr.nodes_searched() << " nps " << nps()
2184 << " time " << t << endl;
2187 // Should we stop the search?
2191 bool stillAtFirstMove = FirstRootMove
2192 && !AspirationFailLow
2193 && t > TimeMgr.available_time();
2195 bool noMoreTime = t > TimeMgr.maximum_time()
2196 || stillAtFirstMove;
2198 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2199 || (ExactMaxTime && t >= ExactMaxTime)
2200 || (Iteration >= 3 && MaxNodes && ThreadsMgr.nodes_searched() >= MaxNodes))
2205 // ponderhit() is called when the program is pondering (i.e. thinking while
2206 // it's the opponent's turn to move) in order to let the engine know that
2207 // it correctly predicted the opponent's move.
2211 int t = current_search_time();
2212 PonderSearch = false;
2214 bool stillAtFirstMove = FirstRootMove
2215 && !AspirationFailLow
2216 && t > TimeMgr.available_time();
2218 bool noMoreTime = t > TimeMgr.maximum_time()
2219 || stillAtFirstMove;
2221 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2226 // init_ss_array() does a fast reset of the first entries of a SearchStack
2227 // array and of all the excludedMove and skipNullMove entries.
2229 void init_ss_array(SearchStack* ss, int size) {
2231 for (int i = 0; i < size; i++, ss++)
2233 ss->excludedMove = MOVE_NONE;
2234 ss->skipNullMove = false;
2235 ss->reduction = DEPTH_ZERO;
2239 ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE;
2244 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2245 // while the program is pondering. The point is to work around a wrinkle in
2246 // the UCI protocol: When pondering, the engine is not allowed to give a
2247 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2248 // We simply wait here until one of these commands is sent, and return,
2249 // after which the bestmove and pondermove will be printed (in id_loop()).
2251 void wait_for_stop_or_ponderhit() {
2253 std::string command;
2257 if (!std::getline(std::cin, command))
2260 if (command == "quit")
2265 else if (command == "ponderhit" || command == "stop")
2271 // print_pv_info() prints to standard output and eventually to log file information on
2272 // the current PV line. It is called at each iteration or after a new pv is found.
2274 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) {
2276 cout << "info depth " << Iteration
2277 << " score " << value_to_uci(value)
2278 << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
2279 << " time " << current_search_time()
2280 << " nodes " << ThreadsMgr.nodes_searched()
2284 for (Move* m = pv; *m != MOVE_NONE; m++)
2291 ValueType t = value >= beta ? VALUE_TYPE_LOWER :
2292 value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
2294 LogFile << pretty_pv(pos, current_search_time(), Iteration,
2295 ThreadsMgr.nodes_searched(), value, t, pv) << endl;
2300 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2301 // the PV back into the TT. This makes sure the old PV moves are searched
2302 // first, even if the old TT entries have been overwritten.
2304 void insert_pv_in_tt(const Position& pos, Move pv[]) {
2308 Position p(pos, pos.thread());
2309 Value v, m = VALUE_NONE;
2311 for (int i = 0; pv[i] != MOVE_NONE; i++)
2313 tte = TT.retrieve(p.get_key());
2314 if (!tte || tte->move() != pv[i])
2316 v = (p.is_check() ? VALUE_NONE : evaluate(p, m));
2317 TT.store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[i], v, m);
2319 p.do_move(pv[i], st);
2324 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2325 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2326 // allow to always have a ponder move even when we fail high at root and also a
2327 // long PV to print that is important for position analysis.
2329 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]) {
2333 Position p(pos, pos.thread());
2336 assert(bestMove != MOVE_NONE);
2339 p.do_move(pv[ply++], st);
2341 while ( (tte = TT.retrieve(p.get_key())) != NULL
2342 && tte->move() != MOVE_NONE
2343 && move_is_legal(p, tte->move())
2345 && (!p.is_draw() || ply < 2))
2347 pv[ply] = tte->move();
2348 p.do_move(pv[ply++], st);
2350 pv[ply] = MOVE_NONE;
2354 // init_thread() is the function which is called when a new thread is
2355 // launched. It simply calls the idle_loop() function with the supplied
2356 // threadID. There are two versions of this function; one for POSIX
2357 // threads and one for Windows threads.
2359 #if !defined(_MSC_VER)
2361 void* init_thread(void *threadID) {
2363 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2369 DWORD WINAPI init_thread(LPVOID threadID) {
2371 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2378 /// The ThreadsManager class
2380 // resetNodeCounters(), resetBetaCounters(), searched_nodes() and
2381 // get_beta_counters() are getters/setters for the per thread
2382 // counters used to sort the moves at root.
2384 void ThreadsManager::resetNodeCounters() {
2386 for (int i = 0; i < MAX_THREADS; i++)
2387 threads[i].nodes = 0ULL;
2390 int64_t ThreadsManager::nodes_searched() const {
2392 int64_t result = 0ULL;
2393 for (int i = 0; i < ActiveThreads; i++)
2394 result += threads[i].nodes;
2400 // idle_loop() is where the threads are parked when they have no work to do.
2401 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2402 // object for which the current thread is the master.
2404 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2406 assert(threadID >= 0 && threadID < MAX_THREADS);
2410 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2411 // master should exit as last one.
2412 if (AllThreadsShouldExit)
2415 threads[threadID].state = THREAD_TERMINATED;
2419 // If we are not thinking, wait for a condition to be signaled
2420 // instead of wasting CPU time polling for work.
2421 while (AllThreadsShouldSleep || threadID >= ActiveThreads)
2424 assert(threadID != 0);
2425 threads[threadID].state = THREAD_SLEEPING;
2427 #if !defined(_MSC_VER)
2428 lock_grab(&WaitLock);
2429 if (AllThreadsShouldSleep || threadID >= ActiveThreads)
2430 pthread_cond_wait(&WaitCond, &WaitLock);
2431 lock_release(&WaitLock);
2433 WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2437 // If thread has just woken up, mark it as available
2438 if (threads[threadID].state == THREAD_SLEEPING)
2439 threads[threadID].state = THREAD_AVAILABLE;
2441 // If this thread has been assigned work, launch a search
2442 if (threads[threadID].state == THREAD_WORKISWAITING)
2444 assert(!AllThreadsShouldExit && !AllThreadsShouldSleep);
2446 threads[threadID].state = THREAD_SEARCHING;
2448 if (threads[threadID].splitPoint->pvNode)
2449 do_sp_search<PV>(threads[threadID].splitPoint, threadID);
2451 do_sp_search<NonPV>(threads[threadID].splitPoint, threadID);
2453 assert(threads[threadID].state == THREAD_SEARCHING);
2455 threads[threadID].state = THREAD_AVAILABLE;
2458 // If this thread is the master of a split point and all slaves have
2459 // finished their work at this split point, return from the idle loop.
2461 for ( ; sp && i < ActiveThreads && !sp->slaves[i]; i++) {}
2463 if (i == ActiveThreads)
2465 // Because sp->slaves[] is reset under lock protection,
2466 // be sure sp->lock has been released before to return.
2467 lock_grab(&(sp->lock));
2468 lock_release(&(sp->lock));
2470 // In helpful master concept a master can help only a sub-tree, and
2471 // because here is all finished is not possible master is booked.
2472 assert(threads[threadID].state == THREAD_AVAILABLE);
2474 threads[threadID].state = THREAD_SEARCHING;
2481 // init_threads() is called during startup. It launches all helper threads,
2482 // and initializes the split point stack and the global locks and condition
2485 void ThreadsManager::init_threads() {
2490 #if !defined(_MSC_VER)
2491 pthread_t pthread[1];
2494 // Initialize global locks
2496 lock_init(&WaitLock);
2498 #if !defined(_MSC_VER)
2499 pthread_cond_init(&WaitCond, NULL);
2501 for (i = 0; i < MAX_THREADS; i++)
2502 SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0);
2505 // Initialize splitPoints[] locks
2506 for (i = 0; i < MAX_THREADS; i++)
2507 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2508 lock_init(&(threads[i].splitPoints[j].lock));
2510 // Will be set just before program exits to properly end the threads
2511 AllThreadsShouldExit = false;
2513 // Threads will be put to sleep as soon as created
2514 AllThreadsShouldSleep = true;
2516 // All threads except the main thread should be initialized to THREAD_AVAILABLE
2518 threads[0].state = THREAD_SEARCHING;
2519 for (i = 1; i < MAX_THREADS; i++)
2520 threads[i].state = THREAD_AVAILABLE;
2522 // Launch the helper threads
2523 for (i = 1; i < MAX_THREADS; i++)
2526 #if !defined(_MSC_VER)
2527 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&i)) == 0);
2529 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, NULL) != NULL);
2534 cout << "Failed to create thread number " << i << endl;
2535 Application::exit_with_failure();
2538 // Wait until the thread has finished launching and is gone to sleep
2539 while (threads[i].state != THREAD_SLEEPING) {}
2544 // exit_threads() is called when the program exits. It makes all the
2545 // helper threads exit cleanly.
2547 void ThreadsManager::exit_threads() {
2549 ActiveThreads = MAX_THREADS; // Wake up all the threads
2550 AllThreadsShouldExit = true; // Let the woken up threads to exit idle_loop()
2551 AllThreadsShouldSleep = true; // Avoid an assert in wake_sleeping_threads()
2552 wake_sleeping_threads();
2554 // Wait for thread termination
2555 for (int i = 1; i < MAX_THREADS; i++)
2556 while (threads[i].state != THREAD_TERMINATED) {}
2558 // Now we can safely destroy the locks
2559 for (int i = 0; i < MAX_THREADS; i++)
2560 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2561 lock_destroy(&(threads[i].splitPoints[j].lock));
2563 lock_destroy(&WaitLock);
2564 lock_destroy(&MPLock);
2568 // thread_should_stop() checks whether the thread should stop its search.
2569 // This can happen if a beta cutoff has occurred in the thread's currently
2570 // active split point, or in some ancestor of the current split point.
2572 bool ThreadsManager::thread_should_stop(int threadID) const {
2574 assert(threadID >= 0 && threadID < ActiveThreads);
2576 SplitPoint* sp = threads[threadID].splitPoint;
2578 for ( ; sp && !sp->stopRequest; sp = sp->parent) {}
2583 // thread_is_available() checks whether the thread with threadID "slave" is
2584 // available to help the thread with threadID "master" at a split point. An
2585 // obvious requirement is that "slave" must be idle. With more than two
2586 // threads, this is not by itself sufficient: If "slave" is the master of
2587 // some active split point, it is only available as a slave to the other
2588 // threads which are busy searching the split point at the top of "slave"'s
2589 // split point stack (the "helpful master concept" in YBWC terminology).
2591 bool ThreadsManager::thread_is_available(int slave, int master) const {
2593 assert(slave >= 0 && slave < ActiveThreads);
2594 assert(master >= 0 && master < ActiveThreads);
2595 assert(ActiveThreads > 1);
2597 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2600 // Make a local copy to be sure doesn't change under our feet
2601 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2603 // No active split points means that the thread is available as
2604 // a slave for any other thread.
2605 if (localActiveSplitPoints == 0 || ActiveThreads == 2)
2608 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2609 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2610 // could have been set to 0 by another thread leading to an out of bound access.
2611 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2618 // available_thread_exists() tries to find an idle thread which is available as
2619 // a slave for the thread with threadID "master".
2621 bool ThreadsManager::available_thread_exists(int master) const {
2623 assert(master >= 0 && master < ActiveThreads);
2624 assert(ActiveThreads > 1);
2626 for (int i = 0; i < ActiveThreads; i++)
2627 if (thread_is_available(i, master))
2634 // split() does the actual work of distributing the work at a node between
2635 // several available threads. If it does not succeed in splitting the
2636 // node (because no idle threads are available, or because we have no unused
2637 // split point objects), the function immediately returns. If splitting is
2638 // possible, a SplitPoint object is initialized with all the data that must be
2639 // copied to the helper threads and we tell our helper threads that they have
2640 // been assigned work. This will cause them to instantly leave their idle loops
2641 // and call sp_search(). When all threads have returned from sp_search() then
2644 template <bool Fake>
2645 void ThreadsManager::split(const Position& p, SearchStack* ss, int ply, Value* alpha,
2646 const Value beta, Value* bestValue, Depth depth, Move threatMove,
2647 bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) {
2649 assert(ply > 0 && ply < PLY_MAX);
2650 assert(*bestValue >= -VALUE_INFINITE);
2651 assert(*bestValue <= *alpha);
2652 assert(*alpha < beta);
2653 assert(beta <= VALUE_INFINITE);
2654 assert(depth > DEPTH_ZERO);
2655 assert(p.thread() >= 0 && p.thread() < ActiveThreads);
2656 assert(ActiveThreads > 1);
2658 int i, master = p.thread();
2659 Thread& masterThread = threads[master];
2663 // If no other thread is available to help us, or if we have too many
2664 // active split points, don't split.
2665 if ( !available_thread_exists(master)
2666 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2668 lock_release(&MPLock);
2672 // Pick the next available split point object from the split point stack
2673 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2675 // Initialize the split point object
2676 splitPoint.parent = masterThread.splitPoint;
2677 splitPoint.stopRequest = false;
2678 splitPoint.ply = ply;
2679 splitPoint.depth = depth;
2680 splitPoint.threatMove = threatMove;
2681 splitPoint.mateThreat = mateThreat;
2682 splitPoint.alpha = *alpha;
2683 splitPoint.beta = beta;
2684 splitPoint.pvNode = pvNode;
2685 splitPoint.bestValue = *bestValue;
2687 splitPoint.moveCount = moveCount;
2688 splitPoint.pos = &p;
2689 splitPoint.parentSstack = ss;
2690 for (i = 0; i < ActiveThreads; i++)
2691 splitPoint.slaves[i] = 0;
2693 masterThread.splitPoint = &splitPoint;
2695 // If we are here it means we are not available
2696 assert(masterThread.state != THREAD_AVAILABLE);
2698 int workersCnt = 1; // At least the master is included
2700 // Allocate available threads setting state to THREAD_BOOKED
2701 for (i = 0; !Fake && i < ActiveThreads && workersCnt < MaxThreadsPerSplitPoint; i++)
2702 if (thread_is_available(i, master))
2704 threads[i].state = THREAD_BOOKED;
2705 threads[i].splitPoint = &splitPoint;
2706 splitPoint.slaves[i] = 1;
2710 assert(Fake || workersCnt > 1);
2712 // We can release the lock because slave threads are already booked and master is not available
2713 lock_release(&MPLock);
2715 // Tell the threads that they have work to do. This will make them leave
2716 // their idle loop. But before copy search stack tail for each thread.
2717 for (i = 0; i < ActiveThreads; i++)
2718 if (i == master || splitPoint.slaves[i])
2720 memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
2722 assert(i == master || threads[i].state == THREAD_BOOKED);
2724 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2727 // Everything is set up. The master thread enters the idle loop, from
2728 // which it will instantly launch a search, because its state is
2729 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2730 // idle loop, which means that the main thread will return from the idle
2731 // loop when all threads have finished their work at this split point.
2732 idle_loop(master, &splitPoint);
2734 // We have returned from the idle loop, which means that all threads are
2735 // finished. Update alpha and bestValue, and return.
2738 *alpha = splitPoint.alpha;
2739 *bestValue = splitPoint.bestValue;
2740 masterThread.activeSplitPoints--;
2741 masterThread.splitPoint = splitPoint.parent;
2743 lock_release(&MPLock);
2747 // wake_sleeping_threads() wakes up all sleeping threads when it is time
2748 // to start a new search from the root.
2750 void ThreadsManager::wake_sleeping_threads() {
2752 assert(AllThreadsShouldSleep);
2753 assert(ActiveThreads > 0);
2755 AllThreadsShouldSleep = false;
2757 if (ActiveThreads == 1)
2760 #if !defined(_MSC_VER)
2761 pthread_mutex_lock(&WaitLock);
2762 pthread_cond_broadcast(&WaitCond);
2763 pthread_mutex_unlock(&WaitLock);
2765 for (int i = 1; i < MAX_THREADS; i++)
2766 SetEvent(SitIdleEvent[i]);
2772 // put_threads_to_sleep() makes all the threads go to sleep just before
2773 // to leave think(), at the end of the search. Threads should have already
2774 // finished the job and should be idle.
2776 void ThreadsManager::put_threads_to_sleep() {
2778 assert(!AllThreadsShouldSleep);
2780 // This makes the threads to go to sleep
2781 AllThreadsShouldSleep = true;
2784 /// The RootMoveList class
2786 // RootMoveList c'tor
2788 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) {
2790 SearchStack ss[PLY_MAX_PLUS_2];
2791 MoveStack mlist[MOVES_MAX];
2793 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
2795 // Initialize search stack
2796 init_ss_array(ss, PLY_MAX_PLUS_2);
2797 ss[0].eval = VALUE_NONE;
2800 // Generate all legal moves
2801 MoveStack* last = generate_moves(pos, mlist);
2803 // Add each move to the moves[] array
2804 for (MoveStack* cur = mlist; cur != last; cur++)
2806 bool includeMove = includeAllMoves;
2808 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
2809 includeMove = (searchMoves[k] == cur->move);
2814 // Find a quick score for the move
2815 moves[count].move = ss[0].currentMove = moves[count].pv[0] = cur->move;
2816 moves[count].pv[1] = MOVE_NONE;
2817 pos.do_move(cur->move, st);
2818 moves[count].score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
2819 pos.undo_move(cur->move);
2825 // Score root moves using the standard way used in main search, the moves
2826 // are scored according to the order in which are returned by MovePicker.
2828 void RootMoveList::score_moves(const Position& pos)
2832 MovePicker mp = MovePicker(pos, MOVE_NONE, ONE_PLY, H);
2834 while ((move = mp.get_next_move()) != MOVE_NONE)
2835 for (int i = 0; i < count; i++)
2836 if (moves[i].move == move)
2838 moves[i].mp_score = score--;
2843 // RootMoveList simple methods definitions
2845 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
2849 for (j = 0; pv[j] != MOVE_NONE; j++)
2850 moves[moveNum].pv[j] = pv[j];
2852 moves[moveNum].pv[j] = MOVE_NONE;
2856 // RootMoveList::sort() sorts the root move list at the beginning of a new
2859 void RootMoveList::sort() {
2861 sort_multipv(count - 1); // Sort all items
2865 // RootMoveList::sort_multipv() sorts the first few moves in the root move
2866 // list by their scores and depths. It is used to order the different PVs
2867 // correctly in MultiPV mode.
2869 void RootMoveList::sort_multipv(int n) {
2873 for (i = 1; i <= n; i++)
2875 RootMove rm = moves[i];
2876 for (j = i; j > 0 && moves[j - 1] < rm; j--)
2877 moves[j] = moves[j - 1];