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/>.
45 #include "ucioption.h"
51 //// Local definitions
57 enum NodeType { NonPV, PV };
59 // Set to true to force running with one thread.
60 // Used for debugging SMP code.
61 const bool FakeSplit = false;
63 // Fast lookup table of sliding pieces indexed by Piece
64 const bool Slidings[18] = { 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1 };
65 inline bool piece_is_slider(Piece p) { return Slidings[p]; }
67 // ThreadsManager class is used to handle all the threads related stuff in search,
68 // init, starting, parking and, the most important, launching a slave thread at a
69 // split point are what this class does. All the access to shared thread data is
70 // done through this class, so that we avoid using global variables instead.
72 class ThreadsManager {
73 /* As long as the single ThreadsManager object is defined as a global we don't
74 need to explicitly initialize to zero its data members because variables with
75 static storage duration are automatically set to zero before enter main()
81 int min_split_depth() const { return minimumSplitDepth; }
82 int active_threads() const { return activeThreads; }
83 void set_active_threads(int cnt) { activeThreads = cnt; }
85 void read_uci_options();
86 bool available_thread_exists(int master) const;
87 bool thread_is_available(int slave, int master) const;
88 bool cutoff_at_splitpoint(int threadID) const;
89 void wake_sleeping_thread(int threadID);
90 void idle_loop(int threadID, SplitPoint* sp);
93 void split(Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
94 Depth depth, Move threatMove, bool mateThreat, int moveCount, MovePicker* mp, bool pvNode);
97 Depth minimumSplitDepth;
98 int maxThreadsPerSplitPoint;
99 bool useSleepingThreads;
101 volatile bool allThreadsShouldExit;
102 Thread threads[MAX_THREADS];
103 Lock mpLock, sleepLock[MAX_THREADS];
104 WaitCondition sleepCond[MAX_THREADS];
108 // RootMove struct is used for moves at the root at the tree. For each root
109 // move, we store two scores, a node count, and a PV (really a refutation
110 // in the case of moves which fail low). Value pv_score is normally set at
111 // -VALUE_INFINITE for all non-pv moves, while non_pv_score is computed
112 // according to the order in which moves are returned by MovePicker.
117 RootMove(const RootMove& rm) { *this = rm; }
118 RootMove& operator=(const RootMove& rm);
120 // RootMove::operator<() is the comparison function used when
121 // sorting the moves. A move m1 is considered to be better
122 // than a move m2 if it has an higher pv_score, or if it has
123 // equal pv_score but m1 has the higher non_pv_score. In this
124 // way we are guaranteed that PV moves are always sorted as first.
125 bool operator<(const RootMove& m) const {
126 return pv_score != m.pv_score ? pv_score < m.pv_score
127 : non_pv_score < m.non_pv_score;
130 void extract_pv_from_tt(Position& pos);
131 void insert_pv_in_tt(Position& pos);
136 Move pv[PLY_MAX_PLUS_2];
140 // RootMoveList struct is essentially a std::vector<> of RootMove objects,
141 // with an handful of methods above the standard ones.
143 struct RootMoveList : public std::vector<RootMove> {
145 typedef std::vector<RootMove> Base;
147 RootMoveList(Position& pos, Move searchMoves[]);
148 void set_non_pv_scores(const Position& pos);
150 void sort() { insertion_sort<RootMove, Base::iterator>(begin(), end()); }
151 void sort_multipv(int n) { insertion_sort<RootMove, Base::iterator>(begin(), begin() + n); }
155 // When formatting a move for std::cout we must know if we are in Chess960
156 // or not. To keep using the handy operator<<() on the move the trick is to
157 // embed this flag in the stream itself. Function-like named enum set960 is
158 // used as a custom manipulator and the stream internal general-purpose array,
159 // accessed through ios_base::iword(), is used to pass the flag to the move's
160 // operator<<() that will use it to properly format castling moves.
163 std::ostream& operator<< (std::ostream& os, const set960& m) {
165 os.iword(0) = int(m);
174 // Maximum depth for razoring
175 const Depth RazorDepth = 4 * ONE_PLY;
177 // Dynamic razoring margin based on depth
178 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
180 // Maximum depth for use of dynamic threat detection when null move fails low
181 const Depth ThreatDepth = 5 * ONE_PLY;
183 // Step 9. Internal iterative deepening
185 // Minimum depth for use of internal iterative deepening
186 const Depth IIDDepth[2] = { 8 * ONE_PLY /* non-PV */, 5 * ONE_PLY /* PV */};
188 // At Non-PV nodes we do an internal iterative deepening search
189 // when the static evaluation is bigger then beta - IIDMargin.
190 const Value IIDMargin = Value(0x100);
192 // Step 11. Decide the new search depth
194 // Extensions. Configurable UCI options
195 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
196 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
197 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
199 // Minimum depth for use of singular extension
200 const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */};
202 // If the TT move is at least SingularExtensionMargin better then the
203 // remaining ones we will extend it.
204 const Value SingularExtensionMargin = Value(0x20);
206 // Step 12. Futility pruning
208 // Futility margin for quiescence search
209 const Value FutilityMarginQS = Value(0x80);
211 // Futility lookup tables (initialized at startup) and their getter functions
212 Value FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
213 int FutilityMoveCountArray[32]; // [depth]
215 inline Value futility_margin(Depth d, int mn) { return d < 7 * ONE_PLY ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE; }
216 inline int futility_move_count(Depth d) { return d < 16 * ONE_PLY ? FutilityMoveCountArray[d] : 512; }
218 // Step 14. Reduced search
220 // Reduction lookup tables (initialized at startup) and their getter functions
221 int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
223 template <NodeType PV>
224 inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
226 // Common adjustments
228 // Search depth at iteration 1
229 const Depth InitialDepth = ONE_PLY;
231 // Easy move margin. An easy move candidate must be at least this much
232 // better than the second best move.
233 const Value EasyMoveMargin = Value(0x200);
236 /// Namespace variables
244 // Scores and number of times the best move changed for each iteration
245 Value ValueByIteration[PLY_MAX_PLUS_2];
246 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
248 // Search window management
254 // Time managment variables
255 int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
256 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
257 bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
262 std::ofstream LogFile;
264 // Multi-threads manager object
265 ThreadsManager ThreadsMgr;
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(Position& pos, Move searchMoves[]);
278 Value root_search(Position& pos, SearchStack* ss, Value* alphaPtr, Value* betaPtr, Depth depth, RootMoveList& rml);
280 template <NodeType PvNode, bool SpNode>
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 inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
289 return depth < ONE_PLY ? qsearch<PvNode>(pos, ss, alpha, beta, DEPTH_ZERO, ply)
290 : search<PvNode, false>(pos, ss, alpha, beta, depth, ply);
293 template <NodeType PvNode>
294 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
296 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue);
297 bool connected_moves(const Position& pos, Move m1, Move m2);
298 bool value_is_mate(Value value);
299 Value value_to_tt(Value v, int ply);
300 Value value_from_tt(Value v, int ply);
301 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
302 bool connected_threat(const Position& pos, Move m, Move threat);
303 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
304 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
305 void update_killers(Move m, SearchStack* ss);
306 void update_gains(const Position& pos, Move move, Value before, Value after);
308 int current_search_time();
309 std::string value_to_uci(Value v);
310 int nps(const Position& pos);
311 void poll(const Position& pos);
313 void wait_for_stop_or_ponderhit();
314 void init_ss_array(SearchStack* ss, int size);
315 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value);
317 #if !defined(_MSC_VER)
318 void* init_thread(void* threadID);
320 DWORD WINAPI init_thread(LPVOID threadID);
330 /// init_threads(), exit_threads() and nodes_searched() are helpers to
331 /// give accessibility to some TM methods from outside of current file.
333 void init_threads() { ThreadsMgr.init_threads(); }
334 void exit_threads() { ThreadsMgr.exit_threads(); }
337 /// init_search() is called during startup. It initializes various lookup tables
341 int d; // depth (ONE_PLY == 2)
342 int hd; // half depth (ONE_PLY == 1)
345 // Init reductions array
346 for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
348 double pvRed = log(double(hd)) * log(double(mc)) / 3.0;
349 double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
350 ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0);
351 ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0);
354 // Init futility margins array
355 for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
356 FutilityMarginsMatrix[d][mc] = Value(112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45);
358 // Init futility move count array
359 for (d = 0; d < 32; d++)
360 FutilityMoveCountArray[d] = int(3.001 + 0.25 * pow(d, 2.0));
364 /// perft() is our utility to verify move generation is bug free. All the legal
365 /// moves up to given depth are generated and counted and the sum returned.
367 int perft(Position& pos, Depth depth)
369 MoveStack mlist[MOVES_MAX];
374 // Generate all legal moves
375 MoveStack* last = generate_moves(pos, mlist);
377 // If we are at the last ply we don't need to do and undo
378 // the moves, just to count them.
379 if (depth <= ONE_PLY)
380 return int(last - mlist);
382 // Loop through all legal moves
384 for (MoveStack* cur = mlist; cur != last; cur++)
387 pos.do_move(m, st, ci, pos.move_is_check(m, ci));
388 sum += perft(pos, depth - ONE_PLY);
395 /// think() is the external interface to Stockfish's search, and is called when
396 /// the program receives the UCI 'go' command. It initializes various
397 /// search-related global variables, and calls root_search(). It returns false
398 /// when a quit command is received during the search.
400 bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[],
401 int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) {
403 // Initialize global search variables
404 StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
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 && Options["OwnBook"].value<bool>())
417 if (Options["Book File"].value<std::string>() != OpeningBook.file_name())
418 OpeningBook.open(Options["Book File"].value<std::string>());
420 Move bookMove = OpeningBook.get_move(pos, Options["Best Book Move"].value<bool>());
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(Options["Hash"].value<int>());
433 if (Options["Clear Hash"].value<bool>())
435 Options["Clear Hash"].set_value("false");
439 CheckExtension[1] = Options["Check Extension (PV nodes)"].value<Depth>();
440 CheckExtension[0] = Options["Check Extension (non-PV nodes)"].value<Depth>();
441 SingleEvasionExtension[1] = Options["Single Evasion Extension (PV nodes)"].value<Depth>();
442 SingleEvasionExtension[0] = Options["Single Evasion Extension (non-PV nodes)"].value<Depth>();
443 PawnPushTo7thExtension[1] = Options["Pawn Push to 7th Extension (PV nodes)"].value<Depth>();
444 PawnPushTo7thExtension[0] = Options["Pawn Push to 7th Extension (non-PV nodes)"].value<Depth>();
445 PassedPawnExtension[1] = Options["Passed Pawn Extension (PV nodes)"].value<Depth>();
446 PassedPawnExtension[0] = Options["Passed Pawn Extension (non-PV nodes)"].value<Depth>();
447 PawnEndgameExtension[1] = Options["Pawn Endgame Extension (PV nodes)"].value<Depth>();
448 PawnEndgameExtension[0] = Options["Pawn Endgame Extension (non-PV nodes)"].value<Depth>();
449 MateThreatExtension[1] = Options["Mate Threat Extension (PV nodes)"].value<Depth>();
450 MateThreatExtension[0] = Options["Mate Threat Extension (non-PV nodes)"].value<Depth>();
451 MultiPV = Options["MultiPV"].value<int>();
452 UseLogFile = Options["Use Search Log"].value<bool>();
455 LogFile.open(Options["Search Log Filename"].value<std::string>().c_str(), std::ios::out | std::ios::app);
457 read_weights(pos.side_to_move());
459 // Set the number of active threads
460 ThreadsMgr.read_uci_options();
461 init_eval(ThreadsMgr.active_threads());
463 // Wake up needed threads
464 for (int i = 1; i < ThreadsMgr.active_threads(); i++)
465 ThreadsMgr.wake_sleeping_thread(i);
468 int myTime = time[pos.side_to_move()];
469 int myIncrement = increment[pos.side_to_move()];
470 if (UseTimeManagement)
471 TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter());
473 // Set best NodesBetweenPolls interval to avoid lagging under
474 // heavy time pressure.
476 NodesBetweenPolls = Min(MaxNodes, 30000);
477 else if (myTime && myTime < 1000)
478 NodesBetweenPolls = 1000;
479 else if (myTime && myTime < 5000)
480 NodesBetweenPolls = 5000;
482 NodesBetweenPolls = 30000;
484 // Write search information to log file
486 LogFile << "Searching: " << pos.to_fen() << endl
487 << "infinite: " << infinite
488 << " ponder: " << ponder
489 << " time: " << myTime
490 << " increment: " << myIncrement
491 << " moves to go: " << movesToGo << endl;
493 // We're ready to start thinking. Call the iterative deepening loop function
494 id_loop(pos, searchMoves);
499 // This makes all the threads to go to sleep
500 ThreadsMgr.set_active_threads(1);
508 // id_loop() is the main iterative deepening loop. It calls root_search
509 // repeatedly with increasing depth until the allocated thinking time has
510 // been consumed, the user stops the search, or the maximum search depth is
513 Value id_loop(Position& pos, Move searchMoves[]) {
515 SearchStack ss[PLY_MAX_PLUS_2];
517 Move EasyMove = MOVE_NONE;
518 Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
520 // Moves to search are verified, copied, scored and sorted
521 RootMoveList rml(pos, searchMoves);
523 // Handle special case of searching on a mate/stale position
527 wait_for_stop_or_ponderhit();
529 return pos.is_check() ? -VALUE_MATE : VALUE_DRAW;
532 // Print RootMoveList startup scoring to the standard output,
533 // so to output information also for iteration 1.
534 cout << set960(pos.is_chess960()) // Is enough to set once at the beginning
535 << "info depth " << 1
536 << "\ninfo depth " << 1
537 << " score " << value_to_uci(rml[0].pv_score)
538 << " time " << current_search_time()
539 << " nodes " << pos.nodes_searched()
540 << " nps " << nps(pos)
541 << " pv " << rml[0].pv[0] << "\n";
546 init_ss_array(ss, PLY_MAX_PLUS_2);
547 ValueByIteration[1] = rml[0].pv_score;
550 // Is one move significantly better than others after initial scoring ?
552 || rml[0].pv_score > rml[1].pv_score + EasyMoveMargin)
553 EasyMove = rml[0].pv[0];
555 // Iterative deepening loop
556 while (Iteration < PLY_MAX)
558 // Initialize iteration
560 BestMoveChangesByIteration[Iteration] = 0;
562 cout << "info depth " << Iteration << endl;
564 // Calculate dynamic aspiration window based on previous iterations
565 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
567 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
568 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
570 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
571 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
573 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
574 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
577 // Search to the current depth, rml is updated and sorted,
578 // alpha and beta could change.
579 depth = (Iteration - 2) * ONE_PLY + InitialDepth;
581 value = root_search(pos, ss, &alpha, &beta, depth, rml);
584 break; // Value cannot be trusted. Break out immediately!
586 //Save info about search result
587 ValueByIteration[Iteration] = value;
589 // Drop the easy move if differs from the new best move
590 if (rml[0].pv[0] != EasyMove)
591 EasyMove = MOVE_NONE;
593 if (UseTimeManagement)
596 bool stopSearch = false;
598 // Stop search early if there is only a single legal move,
599 // we search up to Iteration 6 anyway to get a proper score.
600 if (Iteration >= 6 && rml.size() == 1)
603 // Stop search early when the last two iterations returned a mate score
605 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
606 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
609 // Stop search early if one move seems to be much better than the others
611 && EasyMove == rml[0].pv[0]
612 && ( ( rml[0].nodes > (pos.nodes_searched() * 85) / 100
613 && current_search_time() > TimeMgr.available_time() / 16)
614 ||( rml[0].nodes > (pos.nodes_searched() * 98) / 100
615 && current_search_time() > TimeMgr.available_time() / 32)))
618 // Add some extra time if the best move has changed during the last two iterations
619 if (Iteration > 5 && Iteration <= 50)
620 TimeMgr.pv_instability(BestMoveChangesByIteration[Iteration],
621 BestMoveChangesByIteration[Iteration-1]);
623 // Stop search if most of MaxSearchTime is consumed at the end of the
624 // iteration. We probably don't have enough time to search the first
625 // move at the next iteration anyway.
626 if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
632 StopOnPonderhit = true;
638 if (MaxDepth && Iteration >= MaxDepth)
642 // If we are pondering or in infinite search, we shouldn't print the
643 // best move before we are told to do so.
644 if (!AbortSearch && (PonderSearch || InfiniteSearch))
645 wait_for_stop_or_ponderhit();
647 // Print final search statistics
648 cout << "info nodes " << pos.nodes_searched()
649 << " nps " << nps(pos)
650 << " time " << current_search_time() << endl;
652 // Print the best move and the ponder move to the standard output
653 cout << "bestmove " << rml[0].pv[0];
655 if (rml[0].pv[1] != MOVE_NONE)
656 cout << " ponder " << rml[0].pv[1];
663 dbg_print_mean(LogFile);
665 if (dbg_show_hit_rate)
666 dbg_print_hit_rate(LogFile);
668 LogFile << "\nNodes: " << pos.nodes_searched()
669 << "\nNodes/second: " << nps(pos)
670 << "\nBest move: " << move_to_san(pos, rml[0].pv[0]);
673 pos.do_move(rml[0].pv[0], st);
674 LogFile << "\nPonder move: "
675 << move_to_san(pos, rml[0].pv[1]) // Works also with MOVE_NONE
678 return rml[0].pv_score;
682 // root_search() is the function which searches the root node. It is
683 // similar to search_pv except that it uses a different move ordering
684 // scheme, prints some information to the standard output and handles
685 // the fail low/high loops.
687 Value root_search(Position& pos, SearchStack* ss, Value* alphaPtr,
688 Value* betaPtr, Depth depth, RootMoveList& rml) {
694 Value value, alpha, beta;
695 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
696 int researchCountFH, researchCountFL;
698 researchCountFH = researchCountFL = 0;
701 isCheck = pos.is_check();
703 // Step 1. Initialize node (polling is omitted at root)
704 ss->currentMove = ss->bestMove = MOVE_NONE;
706 // Step 2. Check for aborted search (omitted at root)
707 // Step 3. Mate distance pruning (omitted at root)
708 // Step 4. Transposition table lookup (omitted at root)
710 // Step 5. Evaluate the position statically
711 // At root we do this only to get reference value for child nodes
712 ss->evalMargin = VALUE_NONE;
713 ss->eval = isCheck ? VALUE_NONE : evaluate(pos, ss->evalMargin);
715 // Step 6. Razoring (omitted at root)
716 // Step 7. Static null move pruning (omitted at root)
717 // Step 8. Null move search with verification search (omitted at root)
718 // Step 9. Internal iterative deepening (omitted at root)
720 // Step extra. Fail low loop
721 // We start with small aspiration window and in case of fail low, we research
722 // with bigger window until we are not failing low anymore.
725 // Sort the moves before to (re)search
726 rml.set_non_pv_scores(pos);
729 // Step 10. Loop through all moves in the root move list
730 for (int i = 0; i < (int)rml.size() && !AbortSearch; i++)
732 // This is used by time management
733 FirstRootMove = (i == 0);
735 // Save the current node count before the move is searched
736 nodes = pos.nodes_searched();
738 // Pick the next root move, and print the move and the move number to
739 // the standard output.
740 move = ss->currentMove = rml[i].pv[0];
742 if (current_search_time() >= 1000)
743 cout << "info currmove " << move
744 << " currmovenumber " << i + 1 << endl;
746 moveIsCheck = pos.move_is_check(move);
747 captureOrPromotion = pos.move_is_capture_or_promotion(move);
749 // Step 11. Decide the new search depth
750 ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
751 newDepth = depth + ext;
753 // Step 12. Futility pruning (omitted at root)
755 // Step extra. Fail high loop
756 // If move fails high, we research with bigger window until we are not failing
758 value = -VALUE_INFINITE;
762 // Step 13. Make the move
763 pos.do_move(move, st, ci, moveIsCheck);
765 // Step extra. pv search
766 // We do pv search for first moves (i < MultiPV)
767 // and for fail high research (value > alpha)
768 if (i < MultiPV || value > alpha)
770 // Aspiration window is disabled in multi-pv case
772 alpha = -VALUE_INFINITE;
774 // Full depth PV search, done on first move or after a fail high
775 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
779 // Step 14. Reduced search
780 // if the move fails high will be re-searched at full depth
781 bool doFullDepthSearch = true;
783 if ( depth >= 3 * ONE_PLY
785 && !captureOrPromotion
786 && !move_is_castle(move))
788 ss->reduction = reduction<PV>(depth, i - MultiPV + 2);
791 assert(newDepth-ss->reduction >= ONE_PLY);
793 // Reduced depth non-pv search using alpha as upperbound
794 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
795 doFullDepthSearch = (value > alpha);
797 ss->reduction = DEPTH_ZERO; // Restore original reduction
800 // Step 15. Full depth search
801 if (doFullDepthSearch)
803 // Full depth non-pv search using alpha as upperbound
804 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, 1);
806 // If we are above alpha then research at same depth but as PV
807 // to get a correct score or eventually a fail high above beta.
809 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
813 // Step 16. Undo move
816 // Can we exit fail high loop ?
817 if (AbortSearch || value < beta)
820 // We are failing high and going to do a research. It's important to update
821 // the score before research in case we run out of time while researching.
823 rml[i].pv_score = value;
824 rml[i].extract_pv_from_tt(pos);
826 // Print information to the standard output
827 print_pv_info(pos, rml[i].pv, alpha, beta, value);
829 // Prepare for a research after a fail high, each time with a wider window
830 *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
833 } // End of fail high loop
835 // Finished searching the move. If AbortSearch is true, the search
836 // was aborted because the user interrupted the search or because we
837 // ran out of time. In this case, the return value of the search cannot
838 // be trusted, and we break out of the loop without updating the best
843 // Remember searched nodes counts for this move
844 rml[i].nodes += pos.nodes_searched() - nodes;
846 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
847 assert(value < beta);
849 // Step 17. Check for new best move
850 if (value <= alpha && i >= MultiPV)
851 rml[i].pv_score = -VALUE_INFINITE;
854 // PV move or new best move!
858 rml[i].pv_score = value;
859 rml[i].extract_pv_from_tt(pos);
863 // We record how often the best move has been changed in each
864 // iteration. This information is used for time managment: When
865 // the best move changes frequently, we allocate some more time.
867 BestMoveChangesByIteration[Iteration]++;
869 // Print information to the standard output
870 print_pv_info(pos, rml[i].pv, alpha, beta, value);
872 // Raise alpha to setup proper non-pv search upper bound
879 for (int j = 0; j < Min(MultiPV, (int)rml.size()); j++)
881 cout << "info multipv " << j + 1
882 << " score " << value_to_uci(rml[j].pv_score)
883 << " depth " << (j <= i ? Iteration : Iteration - 1)
884 << " time " << current_search_time()
885 << " nodes " << pos.nodes_searched()
886 << " nps " << nps(pos)
889 for (int k = 0; rml[j].pv[k] != MOVE_NONE && k < PLY_MAX; k++)
890 cout << rml[j].pv[k] << " ";
894 alpha = rml[Min(i, MultiPV - 1)].pv_score;
896 } // PV move or new best move
898 assert(alpha >= *alphaPtr);
900 AspirationFailLow = (alpha == *alphaPtr);
902 if (AspirationFailLow && StopOnPonderhit)
903 StopOnPonderhit = false;
906 // Can we exit fail low loop ?
907 if (AbortSearch || !AspirationFailLow)
910 // Prepare for a research after a fail low, each time with a wider window
911 *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
916 // Sort the moves before to return
919 // Write PV lines to transposition table, in case the relevant entries
920 // have been overwritten during the search.
921 for (int i = 0; i < MultiPV; i++)
922 rml[i].insert_pv_in_tt(pos);
928 // search<>() is the main search function for both PV and non-PV nodes and for
929 // normal and SplitPoint nodes. When called just after a split point the search
930 // is simpler because we have already probed the hash table, done a null move
931 // search, and searched the first move before splitting, we don't have to repeat
932 // all this work again. We also don't need to store anything to the hash table
933 // here: This is taken care of after we return from the split point.
935 template <NodeType PvNode, bool SpNode>
936 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
938 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
939 assert(beta > alpha && beta <= VALUE_INFINITE);
940 assert(PvNode || alpha == beta - 1);
941 assert(ply > 0 && ply < PLY_MAX);
942 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
944 Move movesSearched[MOVES_MAX];
948 Move ttMove, move, excludedMove, threatMove;
951 Value bestValue, value, oldAlpha;
952 Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
953 bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
954 bool mateThreat = false;
956 int threadID = pos.thread();
957 SplitPoint* sp = NULL;
958 refinedValue = bestValue = value = -VALUE_INFINITE;
960 isCheck = pos.is_check();
966 ttMove = excludedMove = MOVE_NONE;
967 threatMove = sp->threatMove;
968 mateThreat = sp->mateThreat;
969 goto split_point_start;
971 else {} // Hack to fix icc's "statement is unreachable" warning
973 // Step 1. Initialize node and poll. Polling can abort search
974 ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
975 (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
977 if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
983 // Step 2. Check for aborted search and immediate draw
985 || ThreadsMgr.cutoff_at_splitpoint(threadID)
987 || ply >= PLY_MAX - 1)
990 // Step 3. Mate distance pruning
991 alpha = Max(value_mated_in(ply), alpha);
992 beta = Min(value_mate_in(ply+1), beta);
996 // Step 4. Transposition table lookup
998 // We don't want the score of a partial search to overwrite a previous full search
999 // TT value, so we use a different position key in case of an excluded move exists.
1000 excludedMove = ss->excludedMove;
1001 posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1003 tte = TT.retrieve(posKey);
1004 ttMove = tte ? tte->move() : MOVE_NONE;
1006 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1007 // This is to avoid problems in the following areas:
1009 // * Repetition draw detection
1010 // * Fifty move rule detection
1011 // * Searching for a mate
1012 // * Printing of full PV line
1013 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1016 ss->bestMove = ttMove; // Can be MOVE_NONE
1017 return value_from_tt(tte->value(), ply);
1020 // Step 5. Evaluate the position statically and
1021 // update gain statistics of parent move.
1023 ss->eval = ss->evalMargin = VALUE_NONE;
1026 assert(tte->static_value() != VALUE_NONE);
1028 ss->eval = tte->static_value();
1029 ss->evalMargin = tte->static_value_margin();
1030 refinedValue = refine_eval(tte, ss->eval, ply);
1034 refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
1035 TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
1038 // Save gain for the parent non-capture move
1039 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1041 // Step 6. Razoring (is omitted in PV nodes)
1043 && depth < RazorDepth
1045 && refinedValue < beta - razor_margin(depth)
1046 && ttMove == MOVE_NONE
1047 && !value_is_mate(beta)
1048 && !pos.has_pawn_on_7th(pos.side_to_move()))
1050 Value rbeta = beta - razor_margin(depth);
1051 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply);
1053 // Logically we should return (v + razor_margin(depth)), but
1054 // surprisingly this did slightly weaker in tests.
1058 // Step 7. Static null move pruning (is omitted in PV nodes)
1059 // We're betting that the opponent doesn't have a move that will reduce
1060 // the score by more than futility_margin(depth) if we do a null move.
1062 && !ss->skipNullMove
1063 && depth < RazorDepth
1065 && refinedValue >= beta + futility_margin(depth, 0)
1066 && !value_is_mate(beta)
1067 && pos.non_pawn_material(pos.side_to_move()))
1068 return refinedValue - futility_margin(depth, 0);
1070 // Step 8. Null move search with verification search (is omitted in PV nodes)
1072 && !ss->skipNullMove
1075 && refinedValue >= beta
1076 && !value_is_mate(beta)
1077 && pos.non_pawn_material(pos.side_to_move()))
1079 ss->currentMove = MOVE_NULL;
1081 // Null move dynamic reduction based on depth
1082 int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
1084 // Null move dynamic reduction based on value
1085 if (refinedValue - beta > PawnValueMidgame)
1088 pos.do_null_move(st);
1089 (ss+1)->skipNullMove = true;
1090 nullValue = -search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1);
1091 (ss+1)->skipNullMove = false;
1092 pos.undo_null_move();
1094 if (nullValue >= beta)
1096 // Do not return unproven mate scores
1097 if (nullValue >= value_mate_in(PLY_MAX))
1100 if (depth < 6 * ONE_PLY)
1103 // Do verification search at high depths
1104 ss->skipNullMove = true;
1105 Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY, ply);
1106 ss->skipNullMove = false;
1113 // The null move failed low, which means that we may be faced with
1114 // some kind of threat. If the previous move was reduced, check if
1115 // the move that refuted the null move was somehow connected to the
1116 // move which was reduced. If a connection is found, return a fail
1117 // low score (which will cause the reduced move to fail high in the
1118 // parent node, which will trigger a re-search with full depth).
1119 if (nullValue == value_mated_in(ply + 2))
1122 threatMove = (ss+1)->bestMove;
1123 if ( depth < ThreatDepth
1124 && (ss-1)->reduction
1125 && threatMove != MOVE_NONE
1126 && connected_moves(pos, (ss-1)->currentMove, threatMove))
1131 // Step 9. Internal iterative deepening
1132 if ( depth >= IIDDepth[PvNode]
1133 && ttMove == MOVE_NONE
1134 && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
1136 Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
1138 ss->skipNullMove = true;
1139 search<PvNode>(pos, ss, alpha, beta, d, ply);
1140 ss->skipNullMove = false;
1142 ttMove = ss->bestMove;
1143 tte = TT.retrieve(posKey);
1146 // Expensive mate threat detection (only for PV nodes)
1148 mateThreat = pos.has_mate_threat();
1150 split_point_start: // At split points actual search starts from here
1152 // Initialize a MovePicker object for the current position
1153 // FIXME currently MovePicker() c'tor is needless called also in SplitPoint
1154 MovePicker mpBase(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
1155 MovePicker& mp = SpNode ? *sp->mp : mpBase;
1157 ss->bestMove = MOVE_NONE;
1158 singleEvasion = !SpNode && isCheck && mp.number_of_evasions() == 1;
1159 futilityBase = ss->eval + ss->evalMargin;
1160 singularExtensionNode = !SpNode
1161 && depth >= SingularExtensionDepth[PvNode]
1164 && !excludedMove // Do not allow recursive singular extension search
1165 && (tte->type() & VALUE_TYPE_LOWER)
1166 && tte->depth() >= depth - 3 * ONE_PLY;
1169 lock_grab(&(sp->lock));
1170 bestValue = sp->bestValue;
1173 // Step 10. Loop through moves
1174 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1175 while ( bestValue < beta
1176 && (move = mp.get_next_move()) != MOVE_NONE
1177 && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1179 assert(move_is_ok(move));
1183 moveCount = ++sp->moveCount;
1184 lock_release(&(sp->lock));
1186 else if (move == excludedMove)
1189 movesSearched[moveCount++] = move;
1191 moveIsCheck = pos.move_is_check(move, ci);
1192 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1194 // Step 11. Decide the new search depth
1195 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1197 // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s),
1198 // and just one fails high on (alpha, beta), then that move is singular and should be extended.
1199 // To verify this we do a reduced search on all the other moves but the ttMove, if result is
1200 // lower then ttValue minus a margin then we extend ttMove.
1201 if ( singularExtensionNode
1202 && move == tte->move()
1205 Value ttValue = value_from_tt(tte->value(), ply);
1207 if (abs(ttValue) < VALUE_KNOWN_WIN)
1209 Value b = ttValue - SingularExtensionMargin;
1210 ss->excludedMove = move;
1211 ss->skipNullMove = true;
1212 Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
1213 ss->skipNullMove = false;
1214 ss->excludedMove = MOVE_NONE;
1215 ss->bestMove = MOVE_NONE;
1221 // Update current move (this must be done after singular extension search)
1222 ss->currentMove = move;
1223 newDepth = depth - ONE_PLY + ext;
1225 // Step 12. Futility pruning (is omitted in PV nodes)
1227 && !captureOrPromotion
1231 && !move_is_castle(move))
1233 // Move count based pruning
1234 if ( moveCount >= futility_move_count(depth)
1235 && !(threatMove && connected_threat(pos, move, threatMove))
1236 && bestValue > value_mated_in(PLY_MAX)) // FIXME bestValue is racy
1239 lock_grab(&(sp->lock));
1244 // Value based pruning
1245 // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
1246 // but fixing this made program slightly weaker.
1247 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1248 futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount)
1249 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1251 if (futilityValueScaled < beta)
1255 lock_grab(&(sp->lock));
1256 if (futilityValueScaled > sp->bestValue)
1257 sp->bestValue = bestValue = futilityValueScaled;
1259 else if (futilityValueScaled > bestValue)
1260 bestValue = futilityValueScaled;
1265 // Prune moves with negative SEE at low depths
1266 if ( predictedDepth < 2 * ONE_PLY
1267 && bestValue > value_mated_in(PLY_MAX)
1268 && pos.see_sign(move) < 0)
1271 lock_grab(&(sp->lock));
1277 // Step 13. Make the move
1278 pos.do_move(move, st, ci, moveIsCheck);
1280 // Step extra. pv search (only in PV nodes)
1281 // The first move in list is the expected PV
1282 if (PvNode && moveCount == 1)
1283 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1286 // Step 14. Reduced depth search
1287 // If the move fails high will be re-searched at full depth.
1288 bool doFullDepthSearch = true;
1290 if ( depth >= 3 * ONE_PLY
1291 && !captureOrPromotion
1293 && !move_is_castle(move)
1294 && ss->killers[0] != move
1295 && ss->killers[1] != move)
1297 ss->reduction = reduction<PvNode>(depth, moveCount);
1301 alpha = SpNode ? sp->alpha : alpha;
1302 Depth d = newDepth - ss->reduction;
1303 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1305 doFullDepthSearch = (value > alpha);
1307 ss->reduction = DEPTH_ZERO; // Restore original reduction
1310 // Step 15. Full depth search
1311 if (doFullDepthSearch)
1313 alpha = SpNode ? sp->alpha : alpha;
1314 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1316 // Step extra. pv search (only in PV nodes)
1317 // Search only for possible new PV nodes, if instead value >= beta then
1318 // parent node fails low with value <= alpha and tries another move.
1319 if (PvNode && value > alpha && value < beta)
1320 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1324 // Step 16. Undo move
1325 pos.undo_move(move);
1327 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1329 // Step 17. Check for new best move
1332 lock_grab(&(sp->lock));
1333 bestValue = sp->bestValue;
1337 if (value > bestValue && !(SpNode && ThreadsMgr.cutoff_at_splitpoint(threadID)))
1342 sp->bestValue = value;
1346 if (PvNode && value < beta) // We want always alpha < beta
1354 sp->betaCutoff = true;
1356 if (value == value_mate_in(ply + 1))
1357 ss->mateKiller = move;
1359 ss->bestMove = move;
1362 sp->parentSstack->bestMove = move;
1366 // Step 18. Check for split
1368 && depth >= ThreadsMgr.min_split_depth()
1369 && ThreadsMgr.active_threads() > 1
1371 && ThreadsMgr.available_thread_exists(threadID)
1373 && !ThreadsMgr.cutoff_at_splitpoint(threadID)
1375 ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1376 threatMove, mateThreat, moveCount, &mp, PvNode);
1379 // Step 19. Check for mate and stalemate
1380 // All legal moves have been searched and if there are
1381 // no legal moves, it must be mate or stalemate.
1382 // If one move was excluded return fail low score.
1383 if (!SpNode && !moveCount)
1384 return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW;
1386 // Step 20. Update tables
1387 // If the search is not aborted, update the transposition table,
1388 // history counters, and killer moves.
1389 if (!SpNode && !AbortSearch && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1391 move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
1392 vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
1393 : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
1395 TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, ss->evalMargin);
1397 // Update killers and history only for non capture moves that fails high
1398 if ( bestValue >= beta
1399 && !pos.move_is_capture_or_promotion(move))
1401 update_history(pos, move, depth, movesSearched, moveCount);
1402 update_killers(move, ss);
1408 // Here we have the lock still grabbed
1409 sp->slaves[threadID] = 0;
1410 sp->nodes += pos.nodes_searched();
1411 lock_release(&(sp->lock));
1414 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1419 // qsearch() is the quiescence search function, which is called by the main
1420 // search function when the remaining depth is zero (or, to be more precise,
1421 // less than ONE_PLY).
1423 template <NodeType PvNode>
1424 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1426 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1427 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1428 assert(PvNode || alpha == beta - 1);
1430 assert(ply > 0 && ply < PLY_MAX);
1431 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1435 Value bestValue, value, evalMargin, futilityValue, futilityBase;
1436 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1439 Value oldAlpha = alpha;
1441 ss->bestMove = ss->currentMove = MOVE_NONE;
1443 // Check for an instant draw or maximum ply reached
1444 if (pos.is_draw() || ply >= PLY_MAX - 1)
1447 // Decide whether or not to include checks, this fixes also the type of
1448 // TT entry depth that we are going to use. Note that in qsearch we use
1449 // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
1450 isCheck = pos.is_check();
1451 ttDepth = (isCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS);
1453 // Transposition table lookup. At PV nodes, we don't use the TT for
1454 // pruning, but only for move ordering.
1455 tte = TT.retrieve(pos.get_key());
1456 ttMove = (tte ? tte->move() : MOVE_NONE);
1458 if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ply))
1460 ss->bestMove = ttMove; // Can be MOVE_NONE
1461 return value_from_tt(tte->value(), ply);
1464 // Evaluate the position statically
1467 bestValue = futilityBase = -VALUE_INFINITE;
1468 ss->eval = evalMargin = VALUE_NONE;
1469 enoughMaterial = false;
1475 assert(tte->static_value() != VALUE_NONE);
1477 evalMargin = tte->static_value_margin();
1478 ss->eval = bestValue = tte->static_value();
1481 ss->eval = bestValue = evaluate(pos, evalMargin);
1483 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1485 // Stand pat. Return immediately if static value is at least beta
1486 if (bestValue >= beta)
1489 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1494 if (PvNode && bestValue > alpha)
1497 // Futility pruning parameters, not needed when in check
1498 futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1499 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1502 // Initialize a MovePicker object for the current position, and prepare
1503 // to search the moves. Because the depth is <= 0 here, only captures,
1504 // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
1506 MovePicker mp(pos, ttMove, depth, H);
1509 // Loop through the moves until no moves remain or a beta cutoff occurs
1510 while ( alpha < beta
1511 && (move = mp.get_next_move()) != MOVE_NONE)
1513 assert(move_is_ok(move));
1515 moveIsCheck = pos.move_is_check(move, ci);
1523 && !move_is_promotion(move)
1524 && !pos.move_is_passed_pawn_push(move))
1526 futilityValue = futilityBase
1527 + pos.endgame_value_of_piece_on(move_to(move))
1528 + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1530 if (futilityValue < alpha)
1532 if (futilityValue > bestValue)
1533 bestValue = futilityValue;
1538 // Detect non-capture evasions that are candidate to be pruned
1539 evasionPrunable = isCheck
1540 && bestValue > value_mated_in(PLY_MAX)
1541 && !pos.move_is_capture(move)
1542 && !pos.can_castle(pos.side_to_move());
1544 // Don't search moves with negative SEE values
1546 && (!isCheck || evasionPrunable)
1548 && !move_is_promotion(move)
1549 && pos.see_sign(move) < 0)
1552 // Don't search useless checks
1557 && !pos.move_is_capture_or_promotion(move)
1558 && ss->eval + PawnValueMidgame / 4 < beta
1559 && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue))
1561 if (ss->eval + PawnValueMidgame / 4 > bestValue)
1562 bestValue = ss->eval + PawnValueMidgame / 4;
1567 // Update current move
1568 ss->currentMove = move;
1570 // Make and search the move
1571 pos.do_move(move, st, ci, moveIsCheck);
1572 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1);
1573 pos.undo_move(move);
1575 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1578 if (value > bestValue)
1584 ss->bestMove = move;
1589 // All legal moves have been searched. A special case: If we're in check
1590 // and no legal moves were found, it is checkmate.
1591 if (isCheck && bestValue == -VALUE_INFINITE)
1592 return value_mated_in(ply);
1594 // Update transposition table
1595 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1596 TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin);
1598 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1604 // check_is_dangerous() tests if a checking move can be pruned in qsearch().
1605 // bestValue is updated only when returning false because in that case move
1608 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bestValue)
1610 Bitboard b, occ, oldAtt, newAtt, kingAtt;
1611 Square from, to, ksq, victimSq;
1614 Value futilityValue, bv = *bestValue;
1616 from = move_from(move);
1618 them = opposite_color(pos.side_to_move());
1619 ksq = pos.king_square(them);
1620 kingAtt = pos.attacks_from<KING>(ksq);
1621 pc = pos.piece_on(from);
1623 occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL << ksq);
1624 oldAtt = pos.attacks_from(pc, from, occ);
1625 newAtt = pos.attacks_from(pc, to, occ);
1627 // Rule 1. Checks which give opponent's king at most one escape square are dangerous
1628 b = kingAtt & ~pos.pieces_of_color(them) & ~newAtt & ~(1ULL << to);
1630 if (!(b && (b & (b - 1))))
1633 // Rule 2. Queen contact check is very dangerous
1634 if ( type_of_piece(pc) == QUEEN
1635 && bit_is_set(kingAtt, to))
1638 // Rule 3. Creating new double threats with checks
1639 b = pos.pieces_of_color(them) & newAtt & ~oldAtt & ~(1ULL << ksq);
1643 victimSq = pop_1st_bit(&b);
1644 futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq);
1646 // Note that here we generate illegal "double move"!
1647 if ( futilityValue >= beta
1648 && pos.see_sign(make_move(from, victimSq)) >= 0)
1651 if (futilityValue > bv)
1655 // Update bestValue only if check is not dangerous (because we will prune the move)
1661 // connected_moves() tests whether two moves are 'connected' in the sense
1662 // that the first move somehow made the second move possible (for instance
1663 // if the moving piece is the same in both moves). The first move is assumed
1664 // to be the move that was made to reach the current position, while the
1665 // second move is assumed to be a move from the current position.
1667 bool connected_moves(const Position& pos, Move m1, Move m2) {
1669 Square f1, t1, f2, t2;
1672 assert(m1 && move_is_ok(m1));
1673 assert(m2 && move_is_ok(m2));
1675 // Case 1: The moving piece is the same in both moves
1681 // Case 2: The destination square for m2 was vacated by m1
1687 // Case 3: Moving through the vacated square
1688 if ( piece_is_slider(pos.piece_on(f2))
1689 && bit_is_set(squares_between(f2, t2), f1))
1692 // Case 4: The destination square for m2 is defended by the moving piece in m1
1693 p = pos.piece_on(t1);
1694 if (bit_is_set(pos.attacks_from(p, t1), t2))
1697 // Case 5: Discovered check, checking piece is the piece moved in m1
1698 if ( piece_is_slider(p)
1699 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1700 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1702 // discovered_check_candidates() works also if the Position's side to
1703 // move is the opposite of the checking piece.
1704 Color them = opposite_color(pos.side_to_move());
1705 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1707 if (bit_is_set(dcCandidates, f2))
1714 // value_is_mate() checks if the given value is a mate one eventually
1715 // compensated for the ply.
1717 bool value_is_mate(Value value) {
1719 assert(abs(value) <= VALUE_INFINITE);
1721 return value <= value_mated_in(PLY_MAX)
1722 || value >= value_mate_in(PLY_MAX);
1726 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1727 // "plies to mate from the current ply". Non-mate scores are unchanged.
1728 // The function is called before storing a value to the transposition table.
1730 Value value_to_tt(Value v, int ply) {
1732 if (v >= value_mate_in(PLY_MAX))
1735 if (v <= value_mated_in(PLY_MAX))
1742 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1743 // the transposition table to a mate score corrected for the current ply.
1745 Value value_from_tt(Value v, int ply) {
1747 if (v >= value_mate_in(PLY_MAX))
1750 if (v <= value_mated_in(PLY_MAX))
1757 // extension() decides whether a move should be searched with normal depth,
1758 // or with extended depth. Certain classes of moves (checking moves, in
1759 // particular) are searched with bigger depth than ordinary moves and in
1760 // any case are marked as 'dangerous'. Note that also if a move is not
1761 // extended, as example because the corresponding UCI option is set to zero,
1762 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1763 template <NodeType PvNode>
1764 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1765 bool singleEvasion, bool mateThreat, bool* dangerous) {
1767 assert(m != MOVE_NONE);
1769 Depth result = DEPTH_ZERO;
1770 *dangerous = moveIsCheck | singleEvasion | mateThreat;
1774 if (moveIsCheck && pos.see_sign(m) >= 0)
1775 result += CheckExtension[PvNode];
1778 result += SingleEvasionExtension[PvNode];
1781 result += MateThreatExtension[PvNode];
1784 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1786 Color c = pos.side_to_move();
1787 if (relative_rank(c, move_to(m)) == RANK_7)
1789 result += PawnPushTo7thExtension[PvNode];
1792 if (pos.pawn_is_passed(c, move_to(m)))
1794 result += PassedPawnExtension[PvNode];
1799 if ( captureOrPromotion
1800 && pos.type_of_piece_on(move_to(m)) != PAWN
1801 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1802 - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1803 && !move_is_promotion(m)
1806 result += PawnEndgameExtension[PvNode];
1811 && captureOrPromotion
1812 && pos.type_of_piece_on(move_to(m)) != PAWN
1813 && pos.see_sign(m) >= 0)
1815 result += ONE_PLY / 2;
1819 return Min(result, ONE_PLY);
1823 // connected_threat() tests whether it is safe to forward prune a move or if
1824 // is somehow coonected to the threat move returned by null search.
1826 bool connected_threat(const Position& pos, Move m, Move threat) {
1828 assert(move_is_ok(m));
1829 assert(threat && move_is_ok(threat));
1830 assert(!pos.move_is_check(m));
1831 assert(!pos.move_is_capture_or_promotion(m));
1832 assert(!pos.move_is_passed_pawn_push(m));
1834 Square mfrom, mto, tfrom, tto;
1836 mfrom = move_from(m);
1838 tfrom = move_from(threat);
1839 tto = move_to(threat);
1841 // Case 1: Don't prune moves which move the threatened piece
1845 // Case 2: If the threatened piece has value less than or equal to the
1846 // value of the threatening piece, don't prune move which defend it.
1847 if ( pos.move_is_capture(threat)
1848 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1849 || pos.type_of_piece_on(tfrom) == KING)
1850 && pos.move_attacks_square(m, tto))
1853 // Case 3: If the moving piece in the threatened move is a slider, don't
1854 // prune safe moves which block its ray.
1855 if ( piece_is_slider(pos.piece_on(tfrom))
1856 && bit_is_set(squares_between(tfrom, tto), mto)
1857 && pos.see_sign(m) >= 0)
1864 // ok_to_use_TT() returns true if a transposition table score
1865 // can be used at a given point in search.
1867 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1869 Value v = value_from_tt(tte->value(), ply);
1871 return ( tte->depth() >= depth
1872 || v >= Max(value_mate_in(PLY_MAX), beta)
1873 || v < Min(value_mated_in(PLY_MAX), beta))
1875 && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1876 || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1880 // refine_eval() returns the transposition table score if
1881 // possible otherwise falls back on static position evaluation.
1883 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1887 Value v = value_from_tt(tte->value(), ply);
1889 if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1890 || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1897 // update_history() registers a good move that produced a beta-cutoff
1898 // in history and marks as failures all the other moves of that ply.
1900 void update_history(const Position& pos, Move move, Depth depth,
1901 Move movesSearched[], int moveCount) {
1904 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
1906 for (int i = 0; i < moveCount - 1; i++)
1908 m = movesSearched[i];
1912 if (!pos.move_is_capture_or_promotion(m))
1913 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
1918 // update_killers() add a good move that produced a beta-cutoff
1919 // among the killer moves of that ply.
1921 void update_killers(Move m, SearchStack* ss) {
1923 if (m == ss->killers[0])
1926 ss->killers[1] = ss->killers[0];
1931 // update_gains() updates the gains table of a non-capture move given
1932 // the static position evaluation before and after the move.
1934 void update_gains(const Position& pos, Move m, Value before, Value after) {
1937 && before != VALUE_NONE
1938 && after != VALUE_NONE
1939 && pos.captured_piece_type() == PIECE_TYPE_NONE
1940 && !move_is_special(m))
1941 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
1945 // current_search_time() returns the number of milliseconds which have passed
1946 // since the beginning of the current search.
1948 int current_search_time() {
1950 return get_system_time() - SearchStartTime;
1954 // value_to_uci() converts a value to a string suitable for use with the UCI protocol
1956 std::string value_to_uci(Value v) {
1958 std::stringstream s;
1960 if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
1961 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100
1963 s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
1968 // nps() computes the current nodes/second count.
1970 int nps(const Position& pos) {
1972 int t = current_search_time();
1973 return (t > 0 ? int((pos.nodes_searched() * 1000) / t) : 0);
1977 // poll() performs two different functions: It polls for user input, and it
1978 // looks at the time consumed so far and decides if it's time to abort the
1981 void poll(const Position& pos) {
1983 static int lastInfoTime;
1984 int t = current_search_time();
1987 if (data_available())
1989 // We are line oriented, don't read single chars
1990 std::string command;
1992 if (!std::getline(std::cin, command))
1995 if (command == "quit")
1998 PonderSearch = false;
2002 else if (command == "stop")
2005 PonderSearch = false;
2007 else if (command == "ponderhit")
2011 // Print search information
2015 else if (lastInfoTime > t)
2016 // HACK: Must be a new search where we searched less than
2017 // NodesBetweenPolls nodes during the first second of search.
2020 else if (t - lastInfoTime >= 1000)
2027 if (dbg_show_hit_rate)
2028 dbg_print_hit_rate();
2030 cout << "info nodes " << pos.nodes_searched() << " nps " << nps(pos)
2031 << " time " << t << endl;
2034 // Should we stop the search?
2038 bool stillAtFirstMove = FirstRootMove
2039 && !AspirationFailLow
2040 && t > TimeMgr.available_time();
2042 bool noMoreTime = t > TimeMgr.maximum_time()
2043 || stillAtFirstMove;
2045 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2046 || (ExactMaxTime && t >= ExactMaxTime)
2047 || (Iteration >= 3 && MaxNodes && pos.nodes_searched() >= MaxNodes))
2052 // ponderhit() is called when the program is pondering (i.e. thinking while
2053 // it's the opponent's turn to move) in order to let the engine know that
2054 // it correctly predicted the opponent's move.
2058 int t = current_search_time();
2059 PonderSearch = false;
2061 bool stillAtFirstMove = FirstRootMove
2062 && !AspirationFailLow
2063 && t > TimeMgr.available_time();
2065 bool noMoreTime = t > TimeMgr.maximum_time()
2066 || stillAtFirstMove;
2068 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2073 // init_ss_array() does a fast reset of the first entries of a SearchStack
2074 // array and of all the excludedMove and skipNullMove entries.
2076 void init_ss_array(SearchStack* ss, int size) {
2078 for (int i = 0; i < size; i++, ss++)
2080 ss->excludedMove = MOVE_NONE;
2081 ss->skipNullMove = false;
2082 ss->reduction = DEPTH_ZERO;
2086 ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE;
2091 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2092 // while the program is pondering. The point is to work around a wrinkle in
2093 // the UCI protocol: When pondering, the engine is not allowed to give a
2094 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2095 // We simply wait here until one of these commands is sent, and return,
2096 // after which the bestmove and pondermove will be printed (in id_loop()).
2098 void wait_for_stop_or_ponderhit() {
2100 std::string command;
2104 if (!std::getline(std::cin, command))
2107 if (command == "quit")
2112 else if (command == "ponderhit" || command == "stop")
2118 // print_pv_info() prints to standard output and eventually to log file information on
2119 // the current PV line. It is called at each iteration or after a new pv is found.
2121 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) {
2123 cout << "info depth " << Iteration
2124 << " score " << value_to_uci(value)
2125 << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
2126 << " time " << current_search_time()
2127 << " nodes " << pos.nodes_searched()
2128 << " nps " << nps(pos)
2131 for (Move* m = pv; *m != MOVE_NONE; m++)
2138 ValueType t = value >= beta ? VALUE_TYPE_LOWER :
2139 value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
2141 LogFile << pretty_pv(pos, current_search_time(), Iteration, value, t, pv) << endl;
2146 // init_thread() is the function which is called when a new thread is
2147 // launched. It simply calls the idle_loop() function with the supplied
2148 // threadID. There are two versions of this function; one for POSIX
2149 // threads and one for Windows threads.
2151 #if !defined(_MSC_VER)
2153 void* init_thread(void* threadID) {
2155 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2161 DWORD WINAPI init_thread(LPVOID threadID) {
2163 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2170 /// The ThreadsManager class
2173 // read_uci_options() updates number of active threads and other internal
2174 // parameters according to the UCI options values. It is called before
2175 // to start a new search.
2177 void ThreadsManager::read_uci_options() {
2179 maxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value<int>();
2180 minimumSplitDepth = Options["Minimum Split Depth"].value<int>() * ONE_PLY;
2181 useSleepingThreads = Options["Use Sleeping Threads"].value<bool>();
2182 activeThreads = Options["Threads"].value<int>();
2186 // idle_loop() is where the threads are parked when they have no work to do.
2187 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2188 // object for which the current thread is the master.
2190 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2192 assert(threadID >= 0 && threadID < MAX_THREADS);
2195 bool allFinished = false;
2199 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2200 // master should exit as last one.
2201 if (allThreadsShouldExit)
2204 threads[threadID].state = THREAD_TERMINATED;
2208 // If we are not thinking, wait for a condition to be signaled
2209 // instead of wasting CPU time polling for work.
2210 while ( threadID >= activeThreads || threads[threadID].state == THREAD_INITIALIZING
2211 || (useSleepingThreads && threads[threadID].state == THREAD_AVAILABLE))
2213 assert(!sp || useSleepingThreads);
2214 assert(threadID != 0 || useSleepingThreads);
2216 if (threads[threadID].state == THREAD_INITIALIZING)
2217 threads[threadID].state = THREAD_AVAILABLE;
2219 // Grab the lock to avoid races with wake_sleeping_thread()
2220 lock_grab(&sleepLock[threadID]);
2222 // If we are master and all slaves have finished do not go to sleep
2223 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2224 allFinished = (i == activeThreads);
2226 if (allFinished || allThreadsShouldExit)
2228 lock_release(&sleepLock[threadID]);
2232 // Do sleep here after retesting sleep conditions
2233 if (threadID >= activeThreads || threads[threadID].state == THREAD_AVAILABLE)
2234 cond_wait(&sleepCond[threadID], &sleepLock[threadID]);
2236 lock_release(&sleepLock[threadID]);
2239 // If this thread has been assigned work, launch a search
2240 if (threads[threadID].state == THREAD_WORKISWAITING)
2242 assert(!allThreadsShouldExit);
2244 threads[threadID].state = THREAD_SEARCHING;
2246 // Here we call search() with SplitPoint template parameter set to true
2247 SplitPoint* tsp = threads[threadID].splitPoint;
2248 Position pos(*tsp->pos, threadID);
2249 SearchStack* ss = tsp->sstack[threadID] + 1;
2253 search<PV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2255 search<NonPV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2257 assert(threads[threadID].state == THREAD_SEARCHING);
2259 threads[threadID].state = THREAD_AVAILABLE;
2261 // Wake up master thread so to allow it to return from the idle loop in
2262 // case we are the last slave of the split point.
2263 if (useSleepingThreads && threadID != tsp->master && threads[tsp->master].state == THREAD_AVAILABLE)
2264 wake_sleeping_thread(tsp->master);
2267 // If this thread is the master of a split point and all slaves have
2268 // finished their work at this split point, return from the idle loop.
2269 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2270 allFinished = (i == activeThreads);
2274 // Because sp->slaves[] is reset under lock protection,
2275 // be sure sp->lock has been released before to return.
2276 lock_grab(&(sp->lock));
2277 lock_release(&(sp->lock));
2279 // In helpful master concept a master can help only a sub-tree, and
2280 // because here is all finished is not possible master is booked.
2281 assert(threads[threadID].state == THREAD_AVAILABLE);
2283 threads[threadID].state = THREAD_SEARCHING;
2290 // init_threads() is called during startup. It launches all helper threads,
2291 // and initializes the split point stack and the global locks and condition
2294 void ThreadsManager::init_threads() {
2296 int i, arg[MAX_THREADS];
2299 // Initialize global locks
2302 for (i = 0; i < MAX_THREADS; i++)
2304 lock_init(&sleepLock[i]);
2305 cond_init(&sleepCond[i]);
2308 // Initialize splitPoints[] locks
2309 for (i = 0; i < MAX_THREADS; i++)
2310 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2311 lock_init(&(threads[i].splitPoints[j].lock));
2313 // Will be set just before program exits to properly end the threads
2314 allThreadsShouldExit = false;
2316 // Threads will be put all threads to sleep as soon as created
2319 // All threads except the main thread should be initialized to THREAD_INITIALIZING
2320 threads[0].state = THREAD_SEARCHING;
2321 for (i = 1; i < MAX_THREADS; i++)
2322 threads[i].state = THREAD_INITIALIZING;
2324 // Launch the helper threads
2325 for (i = 1; i < MAX_THREADS; i++)
2329 #if !defined(_MSC_VER)
2330 pthread_t pthread[1];
2331 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
2332 pthread_detach(pthread[0]);
2334 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
2338 cout << "Failed to create thread number " << i << endl;
2342 // Wait until the thread has finished launching and is gone to sleep
2343 while (threads[i].state == THREAD_INITIALIZING) {}
2348 // exit_threads() is called when the program exits. It makes all the
2349 // helper threads exit cleanly.
2351 void ThreadsManager::exit_threads() {
2353 allThreadsShouldExit = true; // Let the woken up threads to exit idle_loop()
2355 // Wake up all the threads and waits for termination
2356 for (int i = 1; i < MAX_THREADS; i++)
2358 wake_sleeping_thread(i);
2359 while (threads[i].state != THREAD_TERMINATED) {}
2362 // Now we can safely destroy the locks
2363 for (int i = 0; i < MAX_THREADS; i++)
2364 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2365 lock_destroy(&(threads[i].splitPoints[j].lock));
2367 lock_destroy(&mpLock);
2369 // Now we can safely destroy the wait conditions
2370 for (int i = 0; i < MAX_THREADS; i++)
2372 lock_destroy(&sleepLock[i]);
2373 cond_destroy(&sleepCond[i]);
2378 // cutoff_at_splitpoint() checks whether a beta cutoff has occurred in
2379 // the thread's currently active split point, or in some ancestor of
2380 // the current split point.
2382 bool ThreadsManager::cutoff_at_splitpoint(int threadID) const {
2384 assert(threadID >= 0 && threadID < activeThreads);
2386 SplitPoint* sp = threads[threadID].splitPoint;
2388 for ( ; sp && !sp->betaCutoff; sp = sp->parent) {}
2393 // thread_is_available() checks whether the thread with threadID "slave" is
2394 // available to help the thread with threadID "master" at a split point. An
2395 // obvious requirement is that "slave" must be idle. With more than two
2396 // threads, this is not by itself sufficient: If "slave" is the master of
2397 // some active split point, it is only available as a slave to the other
2398 // threads which are busy searching the split point at the top of "slave"'s
2399 // split point stack (the "helpful master concept" in YBWC terminology).
2401 bool ThreadsManager::thread_is_available(int slave, int master) const {
2403 assert(slave >= 0 && slave < activeThreads);
2404 assert(master >= 0 && master < activeThreads);
2405 assert(activeThreads > 1);
2407 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2410 // Make a local copy to be sure doesn't change under our feet
2411 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2413 // No active split points means that the thread is available as
2414 // a slave for any other thread.
2415 if (localActiveSplitPoints == 0 || activeThreads == 2)
2418 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2419 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2420 // could have been set to 0 by another thread leading to an out of bound access.
2421 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2428 // available_thread_exists() tries to find an idle thread which is available as
2429 // a slave for the thread with threadID "master".
2431 bool ThreadsManager::available_thread_exists(int master) const {
2433 assert(master >= 0 && master < activeThreads);
2434 assert(activeThreads > 1);
2436 for (int i = 0; i < activeThreads; i++)
2437 if (thread_is_available(i, master))
2444 // split() does the actual work of distributing the work at a node between
2445 // several available threads. If it does not succeed in splitting the
2446 // node (because no idle threads are available, or because we have no unused
2447 // split point objects), the function immediately returns. If splitting is
2448 // possible, a SplitPoint object is initialized with all the data that must be
2449 // copied to the helper threads and we tell our helper threads that they have
2450 // been assigned work. This will cause them to instantly leave their idle loops and
2451 // call search().When all threads have returned from search() then split() returns.
2453 template <bool Fake>
2454 void ThreadsManager::split(Position& pos, SearchStack* ss, int ply, Value* alpha,
2455 const Value beta, Value* bestValue, Depth depth, Move threatMove,
2456 bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) {
2457 assert(pos.is_ok());
2458 assert(ply > 0 && ply < PLY_MAX);
2459 assert(*bestValue >= -VALUE_INFINITE);
2460 assert(*bestValue <= *alpha);
2461 assert(*alpha < beta);
2462 assert(beta <= VALUE_INFINITE);
2463 assert(depth > DEPTH_ZERO);
2464 assert(pos.thread() >= 0 && pos.thread() < activeThreads);
2465 assert(activeThreads > 1);
2467 int i, master = pos.thread();
2468 Thread& masterThread = threads[master];
2472 // If no other thread is available to help us, or if we have too many
2473 // active split points, don't split.
2474 if ( !available_thread_exists(master)
2475 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2477 lock_release(&mpLock);
2481 // Pick the next available split point object from the split point stack
2482 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2484 // Initialize the split point object
2485 splitPoint.parent = masterThread.splitPoint;
2486 splitPoint.master = master;
2487 splitPoint.betaCutoff = false;
2488 splitPoint.ply = ply;
2489 splitPoint.depth = depth;
2490 splitPoint.threatMove = threatMove;
2491 splitPoint.mateThreat = mateThreat;
2492 splitPoint.alpha = *alpha;
2493 splitPoint.beta = beta;
2494 splitPoint.pvNode = pvNode;
2495 splitPoint.bestValue = *bestValue;
2497 splitPoint.moveCount = moveCount;
2498 splitPoint.pos = &pos;
2499 splitPoint.nodes = 0;
2500 splitPoint.parentSstack = ss;
2501 for (i = 0; i < activeThreads; i++)
2502 splitPoint.slaves[i] = 0;
2504 masterThread.splitPoint = &splitPoint;
2506 // If we are here it means we are not available
2507 assert(masterThread.state != THREAD_AVAILABLE);
2509 int workersCnt = 1; // At least the master is included
2511 // Allocate available threads setting state to THREAD_BOOKED
2512 for (i = 0; !Fake && i < activeThreads && workersCnt < maxThreadsPerSplitPoint; i++)
2513 if (thread_is_available(i, master))
2515 threads[i].state = THREAD_BOOKED;
2516 threads[i].splitPoint = &splitPoint;
2517 splitPoint.slaves[i] = 1;
2521 assert(Fake || workersCnt > 1);
2523 // We can release the lock because slave threads are already booked and master is not available
2524 lock_release(&mpLock);
2526 // Tell the threads that they have work to do. This will make them leave
2527 // their idle loop. But before copy search stack tail for each thread.
2528 for (i = 0; i < activeThreads; i++)
2529 if (i == master || splitPoint.slaves[i])
2531 memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
2533 assert(i == master || threads[i].state == THREAD_BOOKED);
2535 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2537 if (useSleepingThreads && i != master)
2538 wake_sleeping_thread(i);
2541 // Everything is set up. The master thread enters the idle loop, from
2542 // which it will instantly launch a search, because its state is
2543 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2544 // idle loop, which means that the main thread will return from the idle
2545 // loop when all threads have finished their work at this split point.
2546 idle_loop(master, &splitPoint);
2548 // We have returned from the idle loop, which means that all threads are
2549 // finished. Update alpha and bestValue, and return.
2552 *alpha = splitPoint.alpha;
2553 *bestValue = splitPoint.bestValue;
2554 masterThread.activeSplitPoints--;
2555 masterThread.splitPoint = splitPoint.parent;
2556 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
2558 lock_release(&mpLock);
2562 // wake_sleeping_thread() wakes up the thread with the given threadID
2563 // when it is time to start a new search.
2565 void ThreadsManager::wake_sleeping_thread(int threadID) {
2567 lock_grab(&sleepLock[threadID]);
2568 cond_signal(&sleepCond[threadID]);
2569 lock_release(&sleepLock[threadID]);
2573 /// RootMove and RootMoveList method's definitions
2575 RootMove::RootMove() {
2578 pv_score = non_pv_score = -VALUE_INFINITE;
2582 RootMove& RootMove::operator=(const RootMove& rm) {
2584 const Move* src = rm.pv;
2587 // Avoid a costly full rm.pv[] copy
2588 do *dst++ = *src; while (*src++ != MOVE_NONE);
2591 pv_score = rm.pv_score;
2592 non_pv_score = rm.non_pv_score;
2596 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2597 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2598 // allow to always have a ponder move even when we fail high at root and also a
2599 // long PV to print that is important for position analysis.
2601 void RootMove::extract_pv_from_tt(Position& pos) {
2603 StateInfo state[PLY_MAX_PLUS_2], *st = state;
2607 assert(pv[0] != MOVE_NONE && move_is_legal(pos, pv[0]));
2609 pos.do_move(pv[0], *st++);
2611 while ( (tte = TT.retrieve(pos.get_key())) != NULL
2612 && tte->move() != MOVE_NONE
2613 && move_is_legal(pos, tte->move())
2615 && (!pos.is_draw() || ply < 2))
2617 pv[ply] = tte->move();
2618 pos.do_move(pv[ply++], *st++);
2620 pv[ply] = MOVE_NONE;
2622 do pos.undo_move(pv[--ply]); while (ply);
2625 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2626 // the PV back into the TT. This makes sure the old PV moves are searched
2627 // first, even if the old TT entries have been overwritten.
2629 void RootMove::insert_pv_in_tt(Position& pos) {
2631 StateInfo state[PLY_MAX_PLUS_2], *st = state;
2634 Value v, m = VALUE_NONE;
2637 assert(pv[0] != MOVE_NONE && move_is_legal(pos, pv[0]));
2641 tte = TT.retrieve(k);
2643 // Don't overwrite exsisting correct entries
2644 if (!tte || tte->move() != pv[ply])
2646 v = (pos.is_check() ? VALUE_NONE : evaluate(pos, m));
2647 TT.store(k, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[ply], v, m);
2649 pos.do_move(pv[ply], *st++);
2651 } while (pv[++ply] != MOVE_NONE);
2653 do pos.undo_move(pv[--ply]); while (ply);
2657 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) {
2659 SearchStack ss[PLY_MAX_PLUS_2];
2660 MoveStack mlist[MOVES_MAX];
2664 // Initialize search stack
2665 init_ss_array(ss, PLY_MAX_PLUS_2);
2666 ss[0].eval = ss[0].evalMargin = VALUE_NONE;
2668 // Generate all legal moves
2669 MoveStack* last = generate_moves(pos, mlist);
2671 // Add each move to the RootMoveList's vector
2672 for (MoveStack* cur = mlist; cur != last; cur++)
2674 // If we have a searchMoves[] list then verify cur->move
2675 // is in the list before to add it.
2676 for (sm = searchMoves; *sm && *sm != cur->move; sm++) {}
2678 if (searchMoves[0] && *sm != cur->move)
2681 // Find a quick score for the move and add to the list
2682 pos.do_move(cur->move, st);
2685 rm.pv[0] = ss[0].currentMove = cur->move;
2686 rm.pv[1] = MOVE_NONE;
2687 rm.pv_score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
2690 pos.undo_move(cur->move);
2695 // Score root moves using the standard way used in main search, the moves
2696 // are scored according to the order in which are returned by MovePicker.
2697 // This is the second order score that is used to compare the moves when
2698 // the first order pv scores of both moves are equal.
2700 void RootMoveList::set_non_pv_scores(const Position& pos)
2703 Value score = VALUE_ZERO;
2704 MovePicker mp(pos, MOVE_NONE, ONE_PLY, H);
2706 while ((move = mp.get_next_move()) != MOVE_NONE)
2707 for (Base::iterator it = begin(); it != end(); ++it)
2708 if (it->pv[0] == move)
2710 it->non_pv_score = score--;