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);
132 std::string pv_info_to_uci(const Position& pos, Value alpha, Value beta, int pvLine = 0);
137 Move pv[PLY_MAX_PLUS_2];
141 // RootMoveList struct is essentially a std::vector<> of RootMove objects,
142 // with an handful of methods above the standard ones.
144 struct RootMoveList : public std::vector<RootMove> {
146 typedef std::vector<RootMove> Base;
148 RootMoveList(Position& pos, Move searchMoves[]);
149 void set_non_pv_scores(const Position& pos);
151 void sort() { insertion_sort<RootMove, Base::iterator>(begin(), end()); }
152 void sort_multipv(int n) { insertion_sort<RootMove, Base::iterator>(begin(), begin() + n + 1); }
156 // When formatting a move for std::cout we must know if we are in Chess960
157 // or not. To keep using the handy operator<<() on the move the trick is to
158 // embed this flag in the stream itself. Function-like named enum set960 is
159 // used as a custom manipulator and the stream internal general-purpose array,
160 // accessed through ios_base::iword(), is used to pass the flag to the move's
161 // operator<<() that will use it to properly format castling moves.
164 std::ostream& operator<< (std::ostream& os, const set960& m) {
166 os.iword(0) = int(m);
175 // Maximum depth for razoring
176 const Depth RazorDepth = 4 * ONE_PLY;
178 // Dynamic razoring margin based on depth
179 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
181 // Maximum depth for use of dynamic threat detection when null move fails low
182 const Depth ThreatDepth = 5 * ONE_PLY;
184 // Step 9. Internal iterative deepening
186 // Minimum depth for use of internal iterative deepening
187 const Depth IIDDepth[2] = { 8 * ONE_PLY /* non-PV */, 5 * ONE_PLY /* PV */};
189 // At Non-PV nodes we do an internal iterative deepening search
190 // when the static evaluation is bigger then beta - IIDMargin.
191 const Value IIDMargin = Value(0x100);
193 // Step 11. Decide the new search depth
195 // Extensions. Configurable UCI options
196 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
197 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
198 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
200 // Minimum depth for use of singular extension
201 const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */};
203 // If the TT move is at least SingularExtensionMargin better then the
204 // remaining ones we will extend it.
205 const Value SingularExtensionMargin = Value(0x20);
207 // Step 12. Futility pruning
209 // Futility margin for quiescence search
210 const Value FutilityMarginQS = Value(0x80);
212 // Futility lookup tables (initialized at startup) and their getter functions
213 Value FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
214 int FutilityMoveCountArray[32]; // [depth]
216 inline Value futility_margin(Depth d, int mn) { return d < 7 * ONE_PLY ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE; }
217 inline int futility_move_count(Depth d) { return d < 16 * ONE_PLY ? FutilityMoveCountArray[d] : 512; }
219 // Step 14. Reduced search
221 // Reduction lookup tables (initialized at startup) and their getter functions
222 int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
224 template <NodeType PV>
225 inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
227 // Common adjustments
229 // Search depth at iteration 1
230 const Depth InitialDepth = ONE_PLY;
232 // Easy move margin. An easy move candidate must be at least this much
233 // better than the second best move.
234 const Value EasyMoveMargin = Value(0x200);
237 /// Namespace variables
245 // Scores and number of times the best move changed for each iteration
246 Value ValueByIteration[PLY_MAX_PLUS_2];
247 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
249 // Search window management
255 // Time managment variables
256 int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
257 bool UseTimeManagement, InfiniteSearch, Pondering, StopOnPonderhit;
258 bool FirstRootMove, StopRequest, QuitRequest, AspirationFailLow;
263 std::ofstream LogFile;
265 // Multi-threads manager object
266 ThreadsManager ThreadsMgr;
268 // Node counters, used only by thread[0] but try to keep in different cache
269 // lines (64 bytes each) from the heavy multi-thread read accessed variables.
270 bool SendSearchedNodes;
272 int NodesBetweenPolls = 30000;
279 Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove);
280 Value root_search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, RootMoveList& rml);
282 template <NodeType PvNode, bool SpNode>
283 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
285 template <NodeType PvNode>
286 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
288 template <NodeType PvNode>
289 inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
291 return depth < ONE_PLY ? qsearch<PvNode>(pos, ss, alpha, beta, DEPTH_ZERO, ply)
292 : search<PvNode, false>(pos, ss, alpha, beta, depth, ply);
295 template <NodeType PvNode>
296 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
298 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue);
299 bool connected_moves(const Position& pos, Move m1, Move m2);
300 bool value_is_mate(Value value);
301 Value value_to_tt(Value v, int ply);
302 Value value_from_tt(Value v, int ply);
303 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
304 bool connected_threat(const Position& pos, Move m, Move threat);
305 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
306 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
307 void update_killers(Move m, SearchStack* ss);
308 void update_gains(const Position& pos, Move move, Value before, Value after);
310 int current_search_time();
311 std::string value_to_uci(Value v);
312 int nps(const Position& pos);
313 void poll(const Position& pos);
314 void wait_for_stop_or_ponderhit();
315 void init_ss_array(SearchStack* ss, int size);
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 = StopRequest = QuitRequest = AspirationFailLow = SendSearchedNodes = false;
406 SearchStartTime = get_system_time();
407 ExactMaxTime = maxTime;
410 InfiniteSearch = infinite;
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>();
454 read_evaluation_uci_options(pos.side_to_move());
456 // Set the number of active threads
457 ThreadsMgr.read_uci_options();
458 init_eval(ThreadsMgr.active_threads());
460 // Wake up needed threads
461 for (int i = 1; i < ThreadsMgr.active_threads(); i++)
462 ThreadsMgr.wake_sleeping_thread(i);
465 int myTime = time[pos.side_to_move()];
466 int myIncrement = increment[pos.side_to_move()];
467 if (UseTimeManagement)
468 TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter());
470 // Set best NodesBetweenPolls interval to avoid lagging under
471 // heavy time pressure.
473 NodesBetweenPolls = Min(MaxNodes, 30000);
474 else if (myTime && myTime < 1000)
475 NodesBetweenPolls = 1000;
476 else if (myTime && myTime < 5000)
477 NodesBetweenPolls = 5000;
479 NodesBetweenPolls = 30000;
481 // Write search information to log file
484 std::string name = Options["Search Log Filename"].value<std::string>();
485 LogFile.open(name.c_str(), std::ios::out | std::ios::app);
487 LogFile << "Searching: " << pos.to_fen(Options["UCI_Chess960"].value<bool>())
488 << "\ninfinite: " << infinite
489 << " ponder: " << ponder
490 << " time: " << myTime
491 << " increment: " << myIncrement
492 << " moves to go: " << movesToGo << endl;
495 // We're ready to start thinking. Call the iterative deepening loop function
496 Move ponderMove = MOVE_NONE;
497 Move bestMove = id_loop(pos, searchMoves, &ponderMove);
499 // Print final search statistics
500 cout << "info nodes " << pos.nodes_searched()
501 << " nps " << nps(pos)
502 << " time " << current_search_time() << endl;
506 LogFile << "\nNodes: " << pos.nodes_searched()
507 << "\nNodes/second: " << nps(pos)
508 << "\nBest move: " << move_to_san(pos, bestMove);
511 pos.do_move(bestMove, st);
512 LogFile << "\nPonder move: "
513 << move_to_san(pos, ponderMove) // Works also with MOVE_NONE
516 // Return from think() with unchanged position
517 pos.undo_move(bestMove);
522 // This makes all the threads to go to sleep
523 ThreadsMgr.set_active_threads(1);
525 // If we are pondering or in infinite search, we shouldn't print the
526 // best move before we are told to do so.
527 if (!StopRequest && (Pondering || InfiniteSearch))
528 wait_for_stop_or_ponderhit();
530 // Could be both MOVE_NONE when searching on a stalemate position
531 cout << "bestmove " << bestMove << " ponder " << ponderMove << endl;
539 // id_loop() is the main iterative deepening loop. It calls root_search
540 // repeatedly with increasing depth until the allocated thinking time has
541 // been consumed, the user stops the search, or the maximum search depth is
544 Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove) {
546 SearchStack ss[PLY_MAX_PLUS_2];
548 Move EasyMove = MOVE_NONE;
549 Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
551 // Moves to search are verified, scored and sorted
552 RootMoveList rml(pos, searchMoves);
554 // Handle special case of searching on a mate/stale position
557 Value s = (pos.is_check() ? -VALUE_MATE : VALUE_DRAW);
559 cout << "info depth " << 1
560 << " score " << value_to_uci(s) << endl;
568 init_ss_array(ss, PLY_MAX_PLUS_2);
569 ValueByIteration[1] = rml[0].pv_score;
572 // Send initial RootMoveList scoring (iteration 1)
573 cout << set960(Options["UCI_Chess960"].value<bool>()) // Is enough to set once at the beginning
574 << "info depth " << Iteration
575 << "\n" << rml[0].pv_info_to_uci(pos, alpha, beta) << endl;
577 // Is one move significantly better than others after initial scoring ?
579 || rml[0].pv_score > rml[1].pv_score + EasyMoveMargin)
580 EasyMove = rml[0].pv[0];
582 // Iterative deepening loop
583 while (Iteration < PLY_MAX)
585 // Initialize iteration
587 BestMoveChangesByIteration[Iteration] = 0;
589 cout << "info depth " << Iteration << endl;
591 // Calculate dynamic aspiration window based on previous iterations
592 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
594 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
595 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
597 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
598 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
600 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
601 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
604 depth = (Iteration - 2) * ONE_PLY + InitialDepth;
606 // Search to the current depth, rml is updated and sorted
607 value = root_search(pos, ss, alpha, beta, depth, rml);
610 break; // Value cannot be trusted. Break out immediately!
612 //Save info about search result
613 ValueByIteration[Iteration] = value;
615 // Drop the easy move if differs from the new best move
616 if (rml[0].pv[0] != EasyMove)
617 EasyMove = MOVE_NONE;
619 if (UseTimeManagement)
622 bool stopSearch = false;
624 // Stop search early if there is only a single legal move,
625 // we search up to Iteration 6 anyway to get a proper score.
626 if (Iteration >= 6 && rml.size() == 1)
629 // Stop search early when the last two iterations returned a mate score
631 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
632 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
635 // Stop search early if one move seems to be much better than the others
637 && EasyMove == rml[0].pv[0]
638 && ( ( rml[0].nodes > (pos.nodes_searched() * 85) / 100
639 && current_search_time() > TimeMgr.available_time() / 16)
640 ||( rml[0].nodes > (pos.nodes_searched() * 98) / 100
641 && current_search_time() > TimeMgr.available_time() / 32)))
644 // Add some extra time if the best move has changed during the last two iterations
645 if (Iteration > 5 && Iteration <= 50)
646 TimeMgr.pv_instability(BestMoveChangesByIteration[Iteration],
647 BestMoveChangesByIteration[Iteration-1]);
649 // Stop search if most of MaxSearchTime is consumed at the end of the
650 // iteration. We probably don't have enough time to search the first
651 // move at the next iteration anyway.
652 if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
658 StopOnPonderhit = true;
664 if (MaxDepth && Iteration >= MaxDepth)
668 *ponderMove = rml[0].pv[1];
673 // root_search() is the function which searches the root node. It is
674 // similar to search_pv except that it prints some information to the
675 // standard output and handles the fail low/high loops.
677 Value root_search(Position& pos, SearchStack* ss, Value alpha,
678 Value beta, Depth depth, RootMoveList& rml) {
684 Value value, oldAlpha;
685 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
686 int researchCountFH, researchCountFL;
688 researchCountFH = researchCountFL = 0;
690 isCheck = pos.is_check();
692 // Step 1. Initialize node (polling is omitted at root)
693 ss->currentMove = ss->bestMove = MOVE_NONE;
695 // Step 2. Check for aborted search (omitted at root)
696 // Step 3. Mate distance pruning (omitted at root)
697 // Step 4. Transposition table lookup (omitted at root)
699 // Step 5. Evaluate the position statically
700 // At root we do this only to get reference value for child nodes
701 ss->evalMargin = VALUE_NONE;
702 ss->eval = isCheck ? VALUE_NONE : evaluate(pos, ss->evalMargin);
704 // Step 6. Razoring (omitted at root)
705 // Step 7. Static null move pruning (omitted at root)
706 // Step 8. Null move search with verification search (omitted at root)
707 // Step 9. Internal iterative deepening (omitted at root)
709 // Step extra. Fail low loop
710 // We start with small aspiration window and in case of fail low, we research
711 // with bigger window until we are not failing low anymore.
714 // Sort the moves before to (re)search
715 rml.set_non_pv_scores(pos);
718 // Step 10. Loop through all moves in the root move list
719 for (int i = 0; i < (int)rml.size() && !StopRequest; i++)
721 // This is used by time management
722 FirstRootMove = (i == 0);
724 // Save the current node count before the move is searched
725 nodes = pos.nodes_searched();
727 // If it's time to send nodes info, do it here where we have the
728 // correct accumulated node counts searched by each thread.
729 if (SendSearchedNodes)
731 SendSearchedNodes = false;
732 cout << "info nodes " << nodes
733 << " nps " << nps(pos)
734 << " time " << current_search_time() << endl;
737 // Pick the next root move, and print the move and the move number to
738 // the standard output.
739 move = ss->currentMove = rml[i].pv[0];
741 if (current_search_time() >= 1000)
742 cout << "info currmove " << move
743 << " currmovenumber " << i + 1 << endl;
745 moveIsCheck = pos.move_is_check(move);
746 captureOrPromotion = pos.move_is_capture_or_promotion(move);
748 // Step 11. Decide the new search depth
749 ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
750 newDepth = depth + ext;
752 // Step 12. Futility pruning (omitted at root)
754 // Step extra. Fail high loop
755 // If move fails high, we research with bigger window until we are not failing
757 value = -VALUE_INFINITE;
761 // Step 13. Make the move
762 pos.do_move(move, st, ci, moveIsCheck);
764 // Step extra. pv search
765 // We do pv search for first moves (i < MultiPV)
766 // and for fail high research (value > alpha)
767 if (i < MultiPV || value > alpha)
769 // Aspiration window is disabled in multi-pv case
771 alpha = -VALUE_INFINITE;
773 // Full depth PV search, done on first move or after a fail high
774 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
778 // Step 14. Reduced search
779 // if the move fails high will be re-searched at full depth
780 bool doFullDepthSearch = true;
782 if ( depth >= 3 * ONE_PLY
784 && !captureOrPromotion
785 && !move_is_castle(move))
787 ss->reduction = reduction<PV>(depth, i - MultiPV + 2);
790 assert(newDepth-ss->reduction >= ONE_PLY);
792 // Reduced depth non-pv search using alpha as upperbound
793 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
794 doFullDepthSearch = (value > alpha);
796 ss->reduction = DEPTH_ZERO; // Restore original reduction
799 // Step 15. Full depth search
800 if (doFullDepthSearch)
802 // Full depth non-pv search using alpha as upperbound
803 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, 1);
805 // If we are above alpha then research at same depth but as PV
806 // to get a correct score or eventually a fail high above beta.
808 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
812 // Step 16. Undo move
815 // Can we exit fail high loop ?
816 if (StopRequest || value < beta)
819 // We are failing high and going to do a research. It's important to update
820 // the score before research in case we run out of time while researching.
822 rml[i].pv_score = value;
823 rml[i].extract_pv_from_tt(pos);
825 // Inform GUI that PV has changed
826 cout << rml[i].pv_info_to_uci(pos, alpha, beta) << endl;
828 // Prepare for a research after a fail high, each time with a wider window
829 beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
832 } // End of fail high loop
834 // Finished searching the move. If AbortSearch is true, the search
835 // was aborted because the user interrupted the search or because we
836 // ran out of time. In this case, the return value of the search cannot
837 // be trusted, and we break out of the loop without updating the best
842 // Remember searched nodes counts for this move
843 rml[i].nodes += pos.nodes_searched() - nodes;
845 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
846 assert(value < beta);
848 // Step 17. Check for new best move
849 if (value <= alpha && i >= MultiPV)
850 rml[i].pv_score = -VALUE_INFINITE;
853 // PV move or new best move!
857 rml[i].pv_score = value;
858 rml[i].extract_pv_from_tt(pos);
860 // We record how often the best move has been changed in each
861 // iteration. This information is used for time managment: When
862 // the best move changes frequently, we allocate some more time.
863 if (MultiPV == 1 && i > 0)
864 BestMoveChangesByIteration[Iteration]++;
866 // Inform GUI that PV has changed, in case of multi-pv UCI protocol
867 // requires we send all the PV lines properly sorted.
870 for (int j = 0; j < Min(MultiPV, (int)rml.size()); j++)
871 cout << rml[j].pv_info_to_uci(pos, alpha, beta, j) << endl;
873 // Update alpha. In multi-pv we don't use aspiration window
876 // Raise alpha to setup proper non-pv search upper bound
880 else // Set alpha equal to minimum score among the PV lines
881 alpha = rml[Min(i, MultiPV - 1)].pv_score;
883 } // PV move or new best move
885 assert(alpha >= oldAlpha);
887 AspirationFailLow = (alpha == oldAlpha);
889 if (AspirationFailLow && StopOnPonderhit)
890 StopOnPonderhit = false;
894 // Can we exit fail low loop ?
895 if (StopRequest || !AspirationFailLow)
898 // Prepare for a research after a fail low, each time with a wider window
899 oldAlpha = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
904 // Sort the moves before to return
907 // Write PV lines to transposition table, in case the relevant entries
908 // have been overwritten during the search.
909 for (int i = 0; i < Min(MultiPV, (int)rml.size()); i++)
910 rml[i].insert_pv_in_tt(pos);
916 // search<>() is the main search function for both PV and non-PV nodes and for
917 // normal and SplitPoint nodes. When called just after a split point the search
918 // is simpler because we have already probed the hash table, done a null move
919 // search, and searched the first move before splitting, we don't have to repeat
920 // all this work again. We also don't need to store anything to the hash table
921 // here: This is taken care of after we return from the split point.
923 template <NodeType PvNode, bool SpNode>
924 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
926 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
927 assert(beta > alpha && beta <= VALUE_INFINITE);
928 assert(PvNode || alpha == beta - 1);
929 assert(ply > 0 && ply < PLY_MAX);
930 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
932 Move movesSearched[MOVES_MAX];
936 Move ttMove, move, excludedMove, threatMove;
939 Value bestValue, value, oldAlpha;
940 Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
941 bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
942 bool mateThreat = false;
944 int threadID = pos.thread();
945 SplitPoint* sp = NULL;
946 refinedValue = bestValue = value = -VALUE_INFINITE;
948 isCheck = pos.is_check();
954 ttMove = excludedMove = MOVE_NONE;
955 threatMove = sp->threatMove;
956 mateThreat = sp->mateThreat;
957 goto split_point_start;
959 else {} // Hack to fix icc's "statement is unreachable" warning
961 // Step 1. Initialize node and poll. Polling can abort search
962 ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
963 (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
965 if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
971 // Step 2. Check for aborted search and immediate draw
973 || ThreadsMgr.cutoff_at_splitpoint(threadID)
975 || ply >= PLY_MAX - 1)
978 // Step 3. Mate distance pruning
979 alpha = Max(value_mated_in(ply), alpha);
980 beta = Min(value_mate_in(ply+1), beta);
984 // Step 4. Transposition table lookup
986 // We don't want the score of a partial search to overwrite a previous full search
987 // TT value, so we use a different position key in case of an excluded move exists.
988 excludedMove = ss->excludedMove;
989 posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
991 tte = TT.retrieve(posKey);
992 ttMove = tte ? tte->move() : MOVE_NONE;
994 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
995 // This is to avoid problems in the following areas:
997 // * Repetition draw detection
998 // * Fifty move rule detection
999 // * Searching for a mate
1000 // * Printing of full PV line
1001 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1004 ss->bestMove = ttMove; // Can be MOVE_NONE
1005 return value_from_tt(tte->value(), ply);
1008 // Step 5. Evaluate the position statically and
1009 // update gain statistics of parent move.
1011 ss->eval = ss->evalMargin = VALUE_NONE;
1014 assert(tte->static_value() != VALUE_NONE);
1016 ss->eval = tte->static_value();
1017 ss->evalMargin = tte->static_value_margin();
1018 refinedValue = refine_eval(tte, ss->eval, ply);
1022 refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
1023 TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
1026 // Save gain for the parent non-capture move
1027 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1029 // Step 6. Razoring (is omitted in PV nodes)
1031 && depth < RazorDepth
1033 && refinedValue < beta - razor_margin(depth)
1034 && ttMove == MOVE_NONE
1035 && !value_is_mate(beta)
1036 && !pos.has_pawn_on_7th(pos.side_to_move()))
1038 Value rbeta = beta - razor_margin(depth);
1039 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply);
1041 // Logically we should return (v + razor_margin(depth)), but
1042 // surprisingly this did slightly weaker in tests.
1046 // Step 7. Static null move pruning (is omitted in PV nodes)
1047 // We're betting that the opponent doesn't have a move that will reduce
1048 // the score by more than futility_margin(depth) if we do a null move.
1050 && !ss->skipNullMove
1051 && depth < RazorDepth
1053 && refinedValue >= beta + futility_margin(depth, 0)
1054 && !value_is_mate(beta)
1055 && pos.non_pawn_material(pos.side_to_move()))
1056 return refinedValue - futility_margin(depth, 0);
1058 // Step 8. Null move search with verification search (is omitted in PV nodes)
1060 && !ss->skipNullMove
1063 && refinedValue >= beta
1064 && !value_is_mate(beta)
1065 && pos.non_pawn_material(pos.side_to_move()))
1067 ss->currentMove = MOVE_NULL;
1069 // Null move dynamic reduction based on depth
1070 int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
1072 // Null move dynamic reduction based on value
1073 if (refinedValue - beta > PawnValueMidgame)
1076 pos.do_null_move(st);
1077 (ss+1)->skipNullMove = true;
1078 nullValue = -search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1);
1079 (ss+1)->skipNullMove = false;
1080 pos.undo_null_move();
1082 if (nullValue >= beta)
1084 // Do not return unproven mate scores
1085 if (nullValue >= value_mate_in(PLY_MAX))
1088 if (depth < 6 * ONE_PLY)
1091 // Do verification search at high depths
1092 ss->skipNullMove = true;
1093 Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY, ply);
1094 ss->skipNullMove = false;
1101 // The null move failed low, which means that we may be faced with
1102 // some kind of threat. If the previous move was reduced, check if
1103 // the move that refuted the null move was somehow connected to the
1104 // move which was reduced. If a connection is found, return a fail
1105 // low score (which will cause the reduced move to fail high in the
1106 // parent node, which will trigger a re-search with full depth).
1107 if (nullValue == value_mated_in(ply + 2))
1110 threatMove = (ss+1)->bestMove;
1111 if ( depth < ThreatDepth
1112 && (ss-1)->reduction
1113 && threatMove != MOVE_NONE
1114 && connected_moves(pos, (ss-1)->currentMove, threatMove))
1119 // Step 9. Internal iterative deepening
1120 if ( depth >= IIDDepth[PvNode]
1121 && ttMove == MOVE_NONE
1122 && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
1124 Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
1126 ss->skipNullMove = true;
1127 search<PvNode>(pos, ss, alpha, beta, d, ply);
1128 ss->skipNullMove = false;
1130 ttMove = ss->bestMove;
1131 tte = TT.retrieve(posKey);
1134 // Expensive mate threat detection (only for PV nodes)
1136 mateThreat = pos.has_mate_threat();
1138 split_point_start: // At split points actual search starts from here
1140 // Initialize a MovePicker object for the current position
1141 // FIXME currently MovePicker() c'tor is needless called also in SplitPoint
1142 MovePicker mpBase(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
1143 MovePicker& mp = SpNode ? *sp->mp : mpBase;
1145 ss->bestMove = MOVE_NONE;
1146 singleEvasion = !SpNode && isCheck && mp.number_of_evasions() == 1;
1147 futilityBase = ss->eval + ss->evalMargin;
1148 singularExtensionNode = !SpNode
1149 && depth >= SingularExtensionDepth[PvNode]
1152 && !excludedMove // Do not allow recursive singular extension search
1153 && (tte->type() & VALUE_TYPE_LOWER)
1154 && tte->depth() >= depth - 3 * ONE_PLY;
1157 lock_grab(&(sp->lock));
1158 bestValue = sp->bestValue;
1161 // Step 10. Loop through moves
1162 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1163 while ( bestValue < beta
1164 && (move = mp.get_next_move()) != MOVE_NONE
1165 && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1167 assert(move_is_ok(move));
1171 moveCount = ++sp->moveCount;
1172 lock_release(&(sp->lock));
1174 else if (move == excludedMove)
1177 movesSearched[moveCount++] = move;
1179 moveIsCheck = pos.move_is_check(move, ci);
1180 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1182 // Step 11. Decide the new search depth
1183 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1185 // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s),
1186 // and just one fails high on (alpha, beta), then that move is singular and should be extended.
1187 // To verify this we do a reduced search on all the other moves but the ttMove, if result is
1188 // lower then ttValue minus a margin then we extend ttMove.
1189 if ( singularExtensionNode
1190 && move == tte->move()
1193 Value ttValue = value_from_tt(tte->value(), ply);
1195 if (abs(ttValue) < VALUE_KNOWN_WIN)
1197 Value b = ttValue - SingularExtensionMargin;
1198 ss->excludedMove = move;
1199 ss->skipNullMove = true;
1200 Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
1201 ss->skipNullMove = false;
1202 ss->excludedMove = MOVE_NONE;
1203 ss->bestMove = MOVE_NONE;
1209 // Update current move (this must be done after singular extension search)
1210 ss->currentMove = move;
1211 newDepth = depth - ONE_PLY + ext;
1213 // Step 12. Futility pruning (is omitted in PV nodes)
1215 && !captureOrPromotion
1219 && !move_is_castle(move))
1221 // Move count based pruning
1222 if ( moveCount >= futility_move_count(depth)
1223 && !(threatMove && connected_threat(pos, move, threatMove))
1224 && bestValue > value_mated_in(PLY_MAX)) // FIXME bestValue is racy
1227 lock_grab(&(sp->lock));
1232 // Value based pruning
1233 // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
1234 // but fixing this made program slightly weaker.
1235 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1236 futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount)
1237 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1239 if (futilityValueScaled < beta)
1243 lock_grab(&(sp->lock));
1244 if (futilityValueScaled > sp->bestValue)
1245 sp->bestValue = bestValue = futilityValueScaled;
1247 else if (futilityValueScaled > bestValue)
1248 bestValue = futilityValueScaled;
1253 // Prune moves with negative SEE at low depths
1254 if ( predictedDepth < 2 * ONE_PLY
1255 && bestValue > value_mated_in(PLY_MAX)
1256 && pos.see_sign(move) < 0)
1259 lock_grab(&(sp->lock));
1265 // Step 13. Make the move
1266 pos.do_move(move, st, ci, moveIsCheck);
1268 // Step extra. pv search (only in PV nodes)
1269 // The first move in list is the expected PV
1270 if (PvNode && moveCount == 1)
1271 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1274 // Step 14. Reduced depth search
1275 // If the move fails high will be re-searched at full depth.
1276 bool doFullDepthSearch = true;
1278 if ( depth >= 3 * ONE_PLY
1279 && !captureOrPromotion
1281 && !move_is_castle(move)
1282 && ss->killers[0] != move
1283 && ss->killers[1] != move)
1285 ss->reduction = reduction<PvNode>(depth, moveCount);
1289 alpha = SpNode ? sp->alpha : alpha;
1290 Depth d = newDepth - ss->reduction;
1291 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1293 doFullDepthSearch = (value > alpha);
1295 ss->reduction = DEPTH_ZERO; // Restore original reduction
1298 // Step 15. Full depth search
1299 if (doFullDepthSearch)
1301 alpha = SpNode ? sp->alpha : alpha;
1302 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1304 // Step extra. pv search (only in PV nodes)
1305 // Search only for possible new PV nodes, if instead value >= beta then
1306 // parent node fails low with value <= alpha and tries another move.
1307 if (PvNode && value > alpha && value < beta)
1308 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1312 // Step 16. Undo move
1313 pos.undo_move(move);
1315 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1317 // Step 17. Check for new best move
1320 lock_grab(&(sp->lock));
1321 bestValue = sp->bestValue;
1325 if (value > bestValue && !(SpNode && ThreadsMgr.cutoff_at_splitpoint(threadID)))
1330 sp->bestValue = value;
1334 if (PvNode && value < beta) // We want always alpha < beta
1342 sp->betaCutoff = true;
1344 if (value == value_mate_in(ply + 1))
1345 ss->mateKiller = move;
1347 ss->bestMove = move;
1350 sp->parentSstack->bestMove = move;
1354 // Step 18. Check for split
1356 && depth >= ThreadsMgr.min_split_depth()
1357 && ThreadsMgr.active_threads() > 1
1359 && ThreadsMgr.available_thread_exists(threadID)
1361 && !ThreadsMgr.cutoff_at_splitpoint(threadID)
1363 ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1364 threatMove, mateThreat, moveCount, &mp, PvNode);
1367 // Step 19. Check for mate and stalemate
1368 // All legal moves have been searched and if there are
1369 // no legal moves, it must be mate or stalemate.
1370 // If one move was excluded return fail low score.
1371 if (!SpNode && !moveCount)
1372 return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW;
1374 // Step 20. Update tables
1375 // If the search is not aborted, update the transposition table,
1376 // history counters, and killer moves.
1377 if (!SpNode && !StopRequest && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1379 move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
1380 vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
1381 : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
1383 TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, ss->evalMargin);
1385 // Update killers and history only for non capture moves that fails high
1386 if ( bestValue >= beta
1387 && !pos.move_is_capture_or_promotion(move))
1389 update_history(pos, move, depth, movesSearched, moveCount);
1390 update_killers(move, ss);
1396 // Here we have the lock still grabbed
1397 sp->slaves[threadID] = 0;
1398 sp->nodes += pos.nodes_searched();
1399 lock_release(&(sp->lock));
1402 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1407 // qsearch() is the quiescence search function, which is called by the main
1408 // search function when the remaining depth is zero (or, to be more precise,
1409 // less than ONE_PLY).
1411 template <NodeType PvNode>
1412 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1414 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1415 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1416 assert(PvNode || alpha == beta - 1);
1418 assert(ply > 0 && ply < PLY_MAX);
1419 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1423 Value bestValue, value, evalMargin, futilityValue, futilityBase;
1424 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1427 Value oldAlpha = alpha;
1429 ss->bestMove = ss->currentMove = MOVE_NONE;
1431 // Check for an instant draw or maximum ply reached
1432 if (pos.is_draw() || ply >= PLY_MAX - 1)
1435 // Decide whether or not to include checks, this fixes also the type of
1436 // TT entry depth that we are going to use. Note that in qsearch we use
1437 // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
1438 isCheck = pos.is_check();
1439 ttDepth = (isCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS);
1441 // Transposition table lookup. At PV nodes, we don't use the TT for
1442 // pruning, but only for move ordering.
1443 tte = TT.retrieve(pos.get_key());
1444 ttMove = (tte ? tte->move() : MOVE_NONE);
1446 if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ply))
1448 ss->bestMove = ttMove; // Can be MOVE_NONE
1449 return value_from_tt(tte->value(), ply);
1452 // Evaluate the position statically
1455 bestValue = futilityBase = -VALUE_INFINITE;
1456 ss->eval = evalMargin = VALUE_NONE;
1457 enoughMaterial = false;
1463 assert(tte->static_value() != VALUE_NONE);
1465 evalMargin = tte->static_value_margin();
1466 ss->eval = bestValue = tte->static_value();
1469 ss->eval = bestValue = evaluate(pos, evalMargin);
1471 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1473 // Stand pat. Return immediately if static value is at least beta
1474 if (bestValue >= beta)
1477 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1482 if (PvNode && bestValue > alpha)
1485 // Futility pruning parameters, not needed when in check
1486 futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1487 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1490 // Initialize a MovePicker object for the current position, and prepare
1491 // to search the moves. Because the depth is <= 0 here, only captures,
1492 // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
1494 MovePicker mp(pos, ttMove, depth, H);
1497 // Loop through the moves until no moves remain or a beta cutoff occurs
1498 while ( alpha < beta
1499 && (move = mp.get_next_move()) != MOVE_NONE)
1501 assert(move_is_ok(move));
1503 moveIsCheck = pos.move_is_check(move, ci);
1511 && !move_is_promotion(move)
1512 && !pos.move_is_passed_pawn_push(move))
1514 futilityValue = futilityBase
1515 + pos.endgame_value_of_piece_on(move_to(move))
1516 + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1518 if (futilityValue < alpha)
1520 if (futilityValue > bestValue)
1521 bestValue = futilityValue;
1526 // Detect non-capture evasions that are candidate to be pruned
1527 evasionPrunable = isCheck
1528 && bestValue > value_mated_in(PLY_MAX)
1529 && !pos.move_is_capture(move)
1530 && !pos.can_castle(pos.side_to_move());
1532 // Don't search moves with negative SEE values
1534 && (!isCheck || evasionPrunable)
1536 && !move_is_promotion(move)
1537 && pos.see_sign(move) < 0)
1540 // Don't search useless checks
1545 && !pos.move_is_capture_or_promotion(move)
1546 && ss->eval + PawnValueMidgame / 4 < beta
1547 && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue))
1549 if (ss->eval + PawnValueMidgame / 4 > bestValue)
1550 bestValue = ss->eval + PawnValueMidgame / 4;
1555 // Update current move
1556 ss->currentMove = move;
1558 // Make and search the move
1559 pos.do_move(move, st, ci, moveIsCheck);
1560 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1);
1561 pos.undo_move(move);
1563 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1566 if (value > bestValue)
1572 ss->bestMove = move;
1577 // All legal moves have been searched. A special case: If we're in check
1578 // and no legal moves were found, it is checkmate.
1579 if (isCheck && bestValue == -VALUE_INFINITE)
1580 return value_mated_in(ply);
1582 // Update transposition table
1583 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1584 TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin);
1586 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1592 // check_is_dangerous() tests if a checking move can be pruned in qsearch().
1593 // bestValue is updated only when returning false because in that case move
1596 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bestValue)
1598 Bitboard b, occ, oldAtt, newAtt, kingAtt;
1599 Square from, to, ksq, victimSq;
1602 Value futilityValue, bv = *bestValue;
1604 from = move_from(move);
1606 them = opposite_color(pos.side_to_move());
1607 ksq = pos.king_square(them);
1608 kingAtt = pos.attacks_from<KING>(ksq);
1609 pc = pos.piece_on(from);
1611 occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL << ksq);
1612 oldAtt = pos.attacks_from(pc, from, occ);
1613 newAtt = pos.attacks_from(pc, to, occ);
1615 // Rule 1. Checks which give opponent's king at most one escape square are dangerous
1616 b = kingAtt & ~pos.pieces_of_color(them) & ~newAtt & ~(1ULL << to);
1618 if (!(b && (b & (b - 1))))
1621 // Rule 2. Queen contact check is very dangerous
1622 if ( type_of_piece(pc) == QUEEN
1623 && bit_is_set(kingAtt, to))
1626 // Rule 3. Creating new double threats with checks
1627 b = pos.pieces_of_color(them) & newAtt & ~oldAtt & ~(1ULL << ksq);
1631 victimSq = pop_1st_bit(&b);
1632 futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq);
1634 // Note that here we generate illegal "double move"!
1635 if ( futilityValue >= beta
1636 && pos.see_sign(make_move(from, victimSq)) >= 0)
1639 if (futilityValue > bv)
1643 // Update bestValue only if check is not dangerous (because we will prune the move)
1649 // connected_moves() tests whether two moves are 'connected' in the sense
1650 // that the first move somehow made the second move possible (for instance
1651 // if the moving piece is the same in both moves). The first move is assumed
1652 // to be the move that was made to reach the current position, while the
1653 // second move is assumed to be a move from the current position.
1655 bool connected_moves(const Position& pos, Move m1, Move m2) {
1657 Square f1, t1, f2, t2;
1660 assert(m1 && move_is_ok(m1));
1661 assert(m2 && move_is_ok(m2));
1663 // Case 1: The moving piece is the same in both moves
1669 // Case 2: The destination square for m2 was vacated by m1
1675 // Case 3: Moving through the vacated square
1676 if ( piece_is_slider(pos.piece_on(f2))
1677 && bit_is_set(squares_between(f2, t2), f1))
1680 // Case 4: The destination square for m2 is defended by the moving piece in m1
1681 p = pos.piece_on(t1);
1682 if (bit_is_set(pos.attacks_from(p, t1), t2))
1685 // Case 5: Discovered check, checking piece is the piece moved in m1
1686 if ( piece_is_slider(p)
1687 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1688 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1690 // discovered_check_candidates() works also if the Position's side to
1691 // move is the opposite of the checking piece.
1692 Color them = opposite_color(pos.side_to_move());
1693 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1695 if (bit_is_set(dcCandidates, f2))
1702 // value_is_mate() checks if the given value is a mate one eventually
1703 // compensated for the ply.
1705 bool value_is_mate(Value value) {
1707 assert(abs(value) <= VALUE_INFINITE);
1709 return value <= value_mated_in(PLY_MAX)
1710 || value >= value_mate_in(PLY_MAX);
1714 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1715 // "plies to mate from the current ply". Non-mate scores are unchanged.
1716 // The function is called before storing a value to the transposition table.
1718 Value value_to_tt(Value v, int ply) {
1720 if (v >= value_mate_in(PLY_MAX))
1723 if (v <= value_mated_in(PLY_MAX))
1730 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1731 // the transposition table to a mate score corrected for the current ply.
1733 Value value_from_tt(Value v, int ply) {
1735 if (v >= value_mate_in(PLY_MAX))
1738 if (v <= value_mated_in(PLY_MAX))
1745 // extension() decides whether a move should be searched with normal depth,
1746 // or with extended depth. Certain classes of moves (checking moves, in
1747 // particular) are searched with bigger depth than ordinary moves and in
1748 // any case are marked as 'dangerous'. Note that also if a move is not
1749 // extended, as example because the corresponding UCI option is set to zero,
1750 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1751 template <NodeType PvNode>
1752 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1753 bool singleEvasion, bool mateThreat, bool* dangerous) {
1755 assert(m != MOVE_NONE);
1757 Depth result = DEPTH_ZERO;
1758 *dangerous = moveIsCheck | singleEvasion | mateThreat;
1762 if (moveIsCheck && pos.see_sign(m) >= 0)
1763 result += CheckExtension[PvNode];
1766 result += SingleEvasionExtension[PvNode];
1769 result += MateThreatExtension[PvNode];
1772 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1774 Color c = pos.side_to_move();
1775 if (relative_rank(c, move_to(m)) == RANK_7)
1777 result += PawnPushTo7thExtension[PvNode];
1780 if (pos.pawn_is_passed(c, move_to(m)))
1782 result += PassedPawnExtension[PvNode];
1787 if ( captureOrPromotion
1788 && pos.type_of_piece_on(move_to(m)) != PAWN
1789 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1790 - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1791 && !move_is_promotion(m)
1794 result += PawnEndgameExtension[PvNode];
1799 && captureOrPromotion
1800 && pos.type_of_piece_on(move_to(m)) != PAWN
1801 && pos.see_sign(m) >= 0)
1803 result += ONE_PLY / 2;
1807 return Min(result, ONE_PLY);
1811 // connected_threat() tests whether it is safe to forward prune a move or if
1812 // is somehow coonected to the threat move returned by null search.
1814 bool connected_threat(const Position& pos, Move m, Move threat) {
1816 assert(move_is_ok(m));
1817 assert(threat && move_is_ok(threat));
1818 assert(!pos.move_is_check(m));
1819 assert(!pos.move_is_capture_or_promotion(m));
1820 assert(!pos.move_is_passed_pawn_push(m));
1822 Square mfrom, mto, tfrom, tto;
1824 mfrom = move_from(m);
1826 tfrom = move_from(threat);
1827 tto = move_to(threat);
1829 // Case 1: Don't prune moves which move the threatened piece
1833 // Case 2: If the threatened piece has value less than or equal to the
1834 // value of the threatening piece, don't prune move which defend it.
1835 if ( pos.move_is_capture(threat)
1836 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1837 || pos.type_of_piece_on(tfrom) == KING)
1838 && pos.move_attacks_square(m, tto))
1841 // Case 3: If the moving piece in the threatened move is a slider, don't
1842 // prune safe moves which block its ray.
1843 if ( piece_is_slider(pos.piece_on(tfrom))
1844 && bit_is_set(squares_between(tfrom, tto), mto)
1845 && pos.see_sign(m) >= 0)
1852 // ok_to_use_TT() returns true if a transposition table score
1853 // can be used at a given point in search.
1855 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1857 Value v = value_from_tt(tte->value(), ply);
1859 return ( tte->depth() >= depth
1860 || v >= Max(value_mate_in(PLY_MAX), beta)
1861 || v < Min(value_mated_in(PLY_MAX), beta))
1863 && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1864 || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1868 // refine_eval() returns the transposition table score if
1869 // possible otherwise falls back on static position evaluation.
1871 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1875 Value v = value_from_tt(tte->value(), ply);
1877 if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1878 || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1885 // update_history() registers a good move that produced a beta-cutoff
1886 // in history and marks as failures all the other moves of that ply.
1888 void update_history(const Position& pos, Move move, Depth depth,
1889 Move movesSearched[], int moveCount) {
1892 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
1894 for (int i = 0; i < moveCount - 1; i++)
1896 m = movesSearched[i];
1900 if (!pos.move_is_capture_or_promotion(m))
1901 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
1906 // update_killers() add a good move that produced a beta-cutoff
1907 // among the killer moves of that ply.
1909 void update_killers(Move m, SearchStack* ss) {
1911 if (m == ss->killers[0])
1914 ss->killers[1] = ss->killers[0];
1919 // update_gains() updates the gains table of a non-capture move given
1920 // the static position evaluation before and after the move.
1922 void update_gains(const Position& pos, Move m, Value before, Value after) {
1925 && before != VALUE_NONE
1926 && after != VALUE_NONE
1927 && pos.captured_piece_type() == PIECE_TYPE_NONE
1928 && !move_is_special(m))
1929 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
1933 // init_ss_array() does a fast reset of the first entries of a SearchStack
1934 // array and of all the excludedMove and skipNullMove entries.
1936 void init_ss_array(SearchStack* ss, int size) {
1938 for (int i = 0; i < size; i++, ss++)
1940 ss->excludedMove = MOVE_NONE;
1941 ss->skipNullMove = false;
1942 ss->reduction = DEPTH_ZERO;
1946 ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE;
1951 // value_to_uci() converts a value to a string suitable for use with the UCI
1952 // protocol specifications:
1954 // cp <x> The score from the engine's point of view in centipawns.
1955 // mate <y> Mate in y moves, not plies. If the engine is getting mated
1956 // use negative values for y.
1958 std::string value_to_uci(Value v) {
1960 std::stringstream s;
1962 if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
1963 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to centipawns
1965 s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
1971 // current_search_time() returns the number of milliseconds which have passed
1972 // since the beginning of the current search.
1974 int current_search_time() {
1976 return get_system_time() - SearchStartTime;
1980 // nps() computes the current nodes/second count
1982 int nps(const Position& pos) {
1984 int t = current_search_time();
1985 return (t > 0 ? int((pos.nodes_searched() * 1000) / t) : 0);
1989 // poll() performs two different functions: It polls for user input, and it
1990 // looks at the time consumed so far and decides if it's time to abort the
1993 void poll(const Position& pos) {
1995 static int lastInfoTime;
1996 int t = current_search_time();
1999 if (data_available())
2001 // We are line oriented, don't read single chars
2002 std::string command;
2004 if (!std::getline(std::cin, command))
2007 if (command == "quit")
2009 // Quit the program as soon as possible
2011 QuitRequest = StopRequest = true;
2014 else if (command == "stop")
2016 // Stop calculating as soon as possible, but still send the "bestmove"
2017 // and possibly the "ponder" token when finishing the search.
2021 else if (command == "ponderhit")
2023 // The opponent has played the expected move. GUI sends "ponderhit" if
2024 // we were told to ponder on the same move the opponent has played. We
2025 // should continue searching but switching from pondering to normal search.
2028 if (StopOnPonderhit)
2033 // Print search information
2037 else if (lastInfoTime > t)
2038 // HACK: Must be a new search where we searched less than
2039 // NodesBetweenPolls nodes during the first second of search.
2042 else if (t - lastInfoTime >= 1000)
2049 if (dbg_show_hit_rate)
2050 dbg_print_hit_rate();
2052 // Send info on searched nodes as soon as we return to root
2053 SendSearchedNodes = true;
2056 // Should we stop the search?
2060 bool stillAtFirstMove = FirstRootMove
2061 && !AspirationFailLow
2062 && t > TimeMgr.available_time();
2064 bool noMoreTime = t > TimeMgr.maximum_time()
2065 || stillAtFirstMove;
2067 if ( (UseTimeManagement && noMoreTime)
2068 || (ExactMaxTime && t >= ExactMaxTime)
2069 || (MaxNodes && pos.nodes_searched() >= MaxNodes)) // FIXME
2074 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2075 // while the program is pondering. The point is to work around a wrinkle in
2076 // the UCI protocol: When pondering, the engine is not allowed to give a
2077 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2078 // We simply wait here until one of these commands is sent, and return,
2079 // after which the bestmove and pondermove will be printed.
2081 void wait_for_stop_or_ponderhit() {
2083 std::string command;
2087 // Wait for a command from stdin
2088 if (!std::getline(std::cin, command))
2091 if (command == "quit")
2096 else if (command == "ponderhit" || command == "stop")
2102 // init_thread() is the function which is called when a new thread is
2103 // launched. It simply calls the idle_loop() function with the supplied
2104 // threadID. There are two versions of this function; one for POSIX
2105 // threads and one for Windows threads.
2107 #if !defined(_MSC_VER)
2109 void* init_thread(void* threadID) {
2111 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2117 DWORD WINAPI init_thread(LPVOID threadID) {
2119 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2126 /// The ThreadsManager class
2129 // read_uci_options() updates number of active threads and other internal
2130 // parameters according to the UCI options values. It is called before
2131 // to start a new search.
2133 void ThreadsManager::read_uci_options() {
2135 maxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value<int>();
2136 minimumSplitDepth = Options["Minimum Split Depth"].value<int>() * ONE_PLY;
2137 useSleepingThreads = Options["Use Sleeping Threads"].value<bool>();
2138 activeThreads = Options["Threads"].value<int>();
2142 // idle_loop() is where the threads are parked when they have no work to do.
2143 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2144 // object for which the current thread is the master.
2146 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2148 assert(threadID >= 0 && threadID < MAX_THREADS);
2151 bool allFinished = false;
2155 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2156 // master should exit as last one.
2157 if (allThreadsShouldExit)
2160 threads[threadID].state = THREAD_TERMINATED;
2164 // If we are not thinking, wait for a condition to be signaled
2165 // instead of wasting CPU time polling for work.
2166 while ( threadID >= activeThreads || threads[threadID].state == THREAD_INITIALIZING
2167 || (useSleepingThreads && threads[threadID].state == THREAD_AVAILABLE))
2169 assert(!sp || useSleepingThreads);
2170 assert(threadID != 0 || useSleepingThreads);
2172 if (threads[threadID].state == THREAD_INITIALIZING)
2173 threads[threadID].state = THREAD_AVAILABLE;
2175 // Grab the lock to avoid races with wake_sleeping_thread()
2176 lock_grab(&sleepLock[threadID]);
2178 // If we are master and all slaves have finished do not go to sleep
2179 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2180 allFinished = (i == activeThreads);
2182 if (allFinished || allThreadsShouldExit)
2184 lock_release(&sleepLock[threadID]);
2188 // Do sleep here after retesting sleep conditions
2189 if (threadID >= activeThreads || threads[threadID].state == THREAD_AVAILABLE)
2190 cond_wait(&sleepCond[threadID], &sleepLock[threadID]);
2192 lock_release(&sleepLock[threadID]);
2195 // If this thread has been assigned work, launch a search
2196 if (threads[threadID].state == THREAD_WORKISWAITING)
2198 assert(!allThreadsShouldExit);
2200 threads[threadID].state = THREAD_SEARCHING;
2202 // Here we call search() with SplitPoint template parameter set to true
2203 SplitPoint* tsp = threads[threadID].splitPoint;
2204 Position pos(*tsp->pos, threadID);
2205 SearchStack* ss = tsp->sstack[threadID] + 1;
2209 search<PV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2211 search<NonPV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2213 assert(threads[threadID].state == THREAD_SEARCHING);
2215 threads[threadID].state = THREAD_AVAILABLE;
2217 // Wake up master thread so to allow it to return from the idle loop in
2218 // case we are the last slave of the split point.
2219 if (useSleepingThreads && threadID != tsp->master && threads[tsp->master].state == THREAD_AVAILABLE)
2220 wake_sleeping_thread(tsp->master);
2223 // If this thread is the master of a split point and all slaves have
2224 // finished their work at this split point, return from the idle loop.
2225 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2226 allFinished = (i == activeThreads);
2230 // Because sp->slaves[] is reset under lock protection,
2231 // be sure sp->lock has been released before to return.
2232 lock_grab(&(sp->lock));
2233 lock_release(&(sp->lock));
2235 // In helpful master concept a master can help only a sub-tree, and
2236 // because here is all finished is not possible master is booked.
2237 assert(threads[threadID].state == THREAD_AVAILABLE);
2239 threads[threadID].state = THREAD_SEARCHING;
2246 // init_threads() is called during startup. It launches all helper threads,
2247 // and initializes the split point stack and the global locks and condition
2250 void ThreadsManager::init_threads() {
2252 int i, arg[MAX_THREADS];
2255 // Initialize global locks
2258 for (i = 0; i < MAX_THREADS; i++)
2260 lock_init(&sleepLock[i]);
2261 cond_init(&sleepCond[i]);
2264 // Initialize splitPoints[] locks
2265 for (i = 0; i < MAX_THREADS; i++)
2266 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2267 lock_init(&(threads[i].splitPoints[j].lock));
2269 // Will be set just before program exits to properly end the threads
2270 allThreadsShouldExit = false;
2272 // Threads will be put all threads to sleep as soon as created
2275 // All threads except the main thread should be initialized to THREAD_INITIALIZING
2276 threads[0].state = THREAD_SEARCHING;
2277 for (i = 1; i < MAX_THREADS; i++)
2278 threads[i].state = THREAD_INITIALIZING;
2280 // Launch the helper threads
2281 for (i = 1; i < MAX_THREADS; i++)
2285 #if !defined(_MSC_VER)
2286 pthread_t pthread[1];
2287 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
2288 pthread_detach(pthread[0]);
2290 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
2294 cout << "Failed to create thread number " << i << endl;
2298 // Wait until the thread has finished launching and is gone to sleep
2299 while (threads[i].state == THREAD_INITIALIZING) {}
2304 // exit_threads() is called when the program exits. It makes all the
2305 // helper threads exit cleanly.
2307 void ThreadsManager::exit_threads() {
2309 allThreadsShouldExit = true; // Let the woken up threads to exit idle_loop()
2311 // Wake up all the threads and waits for termination
2312 for (int i = 1; i < MAX_THREADS; i++)
2314 wake_sleeping_thread(i);
2315 while (threads[i].state != THREAD_TERMINATED) {}
2318 // Now we can safely destroy the locks
2319 for (int i = 0; i < MAX_THREADS; i++)
2320 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2321 lock_destroy(&(threads[i].splitPoints[j].lock));
2323 lock_destroy(&mpLock);
2325 // Now we can safely destroy the wait conditions
2326 for (int i = 0; i < MAX_THREADS; i++)
2328 lock_destroy(&sleepLock[i]);
2329 cond_destroy(&sleepCond[i]);
2334 // cutoff_at_splitpoint() checks whether a beta cutoff has occurred in
2335 // the thread's currently active split point, or in some ancestor of
2336 // the current split point.
2338 bool ThreadsManager::cutoff_at_splitpoint(int threadID) const {
2340 assert(threadID >= 0 && threadID < activeThreads);
2342 SplitPoint* sp = threads[threadID].splitPoint;
2344 for ( ; sp && !sp->betaCutoff; sp = sp->parent) {}
2349 // thread_is_available() checks whether the thread with threadID "slave" is
2350 // available to help the thread with threadID "master" at a split point. An
2351 // obvious requirement is that "slave" must be idle. With more than two
2352 // threads, this is not by itself sufficient: If "slave" is the master of
2353 // some active split point, it is only available as a slave to the other
2354 // threads which are busy searching the split point at the top of "slave"'s
2355 // split point stack (the "helpful master concept" in YBWC terminology).
2357 bool ThreadsManager::thread_is_available(int slave, int master) const {
2359 assert(slave >= 0 && slave < activeThreads);
2360 assert(master >= 0 && master < activeThreads);
2361 assert(activeThreads > 1);
2363 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2366 // Make a local copy to be sure doesn't change under our feet
2367 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2369 // No active split points means that the thread is available as
2370 // a slave for any other thread.
2371 if (localActiveSplitPoints == 0 || activeThreads == 2)
2374 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2375 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2376 // could have been set to 0 by another thread leading to an out of bound access.
2377 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2384 // available_thread_exists() tries to find an idle thread which is available as
2385 // a slave for the thread with threadID "master".
2387 bool ThreadsManager::available_thread_exists(int master) const {
2389 assert(master >= 0 && master < activeThreads);
2390 assert(activeThreads > 1);
2392 for (int i = 0; i < activeThreads; i++)
2393 if (thread_is_available(i, master))
2400 // split() does the actual work of distributing the work at a node between
2401 // several available threads. If it does not succeed in splitting the
2402 // node (because no idle threads are available, or because we have no unused
2403 // split point objects), the function immediately returns. If splitting is
2404 // possible, a SplitPoint object is initialized with all the data that must be
2405 // copied to the helper threads and we tell our helper threads that they have
2406 // been assigned work. This will cause them to instantly leave their idle loops and
2407 // call search().When all threads have returned from search() then split() returns.
2409 template <bool Fake>
2410 void ThreadsManager::split(Position& pos, SearchStack* ss, int ply, Value* alpha,
2411 const Value beta, Value* bestValue, Depth depth, Move threatMove,
2412 bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) {
2413 assert(pos.is_ok());
2414 assert(ply > 0 && ply < PLY_MAX);
2415 assert(*bestValue >= -VALUE_INFINITE);
2416 assert(*bestValue <= *alpha);
2417 assert(*alpha < beta);
2418 assert(beta <= VALUE_INFINITE);
2419 assert(depth > DEPTH_ZERO);
2420 assert(pos.thread() >= 0 && pos.thread() < activeThreads);
2421 assert(activeThreads > 1);
2423 int i, master = pos.thread();
2424 Thread& masterThread = threads[master];
2428 // If no other thread is available to help us, or if we have too many
2429 // active split points, don't split.
2430 if ( !available_thread_exists(master)
2431 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2433 lock_release(&mpLock);
2437 // Pick the next available split point object from the split point stack
2438 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2440 // Initialize the split point object
2441 splitPoint.parent = masterThread.splitPoint;
2442 splitPoint.master = master;
2443 splitPoint.betaCutoff = false;
2444 splitPoint.ply = ply;
2445 splitPoint.depth = depth;
2446 splitPoint.threatMove = threatMove;
2447 splitPoint.mateThreat = mateThreat;
2448 splitPoint.alpha = *alpha;
2449 splitPoint.beta = beta;
2450 splitPoint.pvNode = pvNode;
2451 splitPoint.bestValue = *bestValue;
2453 splitPoint.moveCount = moveCount;
2454 splitPoint.pos = &pos;
2455 splitPoint.nodes = 0;
2456 splitPoint.parentSstack = ss;
2457 for (i = 0; i < activeThreads; i++)
2458 splitPoint.slaves[i] = 0;
2460 masterThread.splitPoint = &splitPoint;
2462 // If we are here it means we are not available
2463 assert(masterThread.state != THREAD_AVAILABLE);
2465 int workersCnt = 1; // At least the master is included
2467 // Allocate available threads setting state to THREAD_BOOKED
2468 for (i = 0; !Fake && i < activeThreads && workersCnt < maxThreadsPerSplitPoint; i++)
2469 if (thread_is_available(i, master))
2471 threads[i].state = THREAD_BOOKED;
2472 threads[i].splitPoint = &splitPoint;
2473 splitPoint.slaves[i] = 1;
2477 assert(Fake || workersCnt > 1);
2479 // We can release the lock because slave threads are already booked and master is not available
2480 lock_release(&mpLock);
2482 // Tell the threads that they have work to do. This will make them leave
2483 // their idle loop. But before copy search stack tail for each thread.
2484 for (i = 0; i < activeThreads; i++)
2485 if (i == master || splitPoint.slaves[i])
2487 memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
2489 assert(i == master || threads[i].state == THREAD_BOOKED);
2491 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2493 if (useSleepingThreads && i != master)
2494 wake_sleeping_thread(i);
2497 // Everything is set up. The master thread enters the idle loop, from
2498 // which it will instantly launch a search, because its state is
2499 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2500 // idle loop, which means that the main thread will return from the idle
2501 // loop when all threads have finished their work at this split point.
2502 idle_loop(master, &splitPoint);
2504 // We have returned from the idle loop, which means that all threads are
2505 // finished. Update alpha and bestValue, and return.
2508 *alpha = splitPoint.alpha;
2509 *bestValue = splitPoint.bestValue;
2510 masterThread.activeSplitPoints--;
2511 masterThread.splitPoint = splitPoint.parent;
2512 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
2514 lock_release(&mpLock);
2518 // wake_sleeping_thread() wakes up the thread with the given threadID
2519 // when it is time to start a new search.
2521 void ThreadsManager::wake_sleeping_thread(int threadID) {
2523 lock_grab(&sleepLock[threadID]);
2524 cond_signal(&sleepCond[threadID]);
2525 lock_release(&sleepLock[threadID]);
2529 /// RootMove and RootMoveList method's definitions
2531 RootMove::RootMove() {
2534 pv_score = non_pv_score = -VALUE_INFINITE;
2538 RootMove& RootMove::operator=(const RootMove& rm) {
2540 const Move* src = rm.pv;
2543 // Avoid a costly full rm.pv[] copy
2544 do *dst++ = *src; while (*src++ != MOVE_NONE);
2547 pv_score = rm.pv_score;
2548 non_pv_score = rm.non_pv_score;
2552 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2553 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2554 // allow to always have a ponder move even when we fail high at root and also a
2555 // long PV to print that is important for position analysis.
2557 void RootMove::extract_pv_from_tt(Position& pos) {
2559 StateInfo state[PLY_MAX_PLUS_2], *st = state;
2563 assert(pv[0] != MOVE_NONE && move_is_legal(pos, pv[0]));
2565 pos.do_move(pv[0], *st++);
2567 while ( (tte = TT.retrieve(pos.get_key())) != NULL
2568 && tte->move() != MOVE_NONE
2569 && move_is_legal(pos, tte->move())
2571 && (!pos.is_draw() || ply < 2))
2573 pv[ply] = tte->move();
2574 pos.do_move(pv[ply++], *st++);
2576 pv[ply] = MOVE_NONE;
2578 do pos.undo_move(pv[--ply]); while (ply);
2581 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2582 // the PV back into the TT. This makes sure the old PV moves are searched
2583 // first, even if the old TT entries have been overwritten.
2585 void RootMove::insert_pv_in_tt(Position& pos) {
2587 StateInfo state[PLY_MAX_PLUS_2], *st = state;
2590 Value v, m = VALUE_NONE;
2593 assert(pv[0] != MOVE_NONE && move_is_legal(pos, pv[0]));
2597 tte = TT.retrieve(k);
2599 // Don't overwrite exsisting correct entries
2600 if (!tte || tte->move() != pv[ply])
2602 v = (pos.is_check() ? VALUE_NONE : evaluate(pos, m));
2603 TT.store(k, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[ply], v, m);
2605 pos.do_move(pv[ply], *st++);
2607 } while (pv[++ply] != MOVE_NONE);
2609 do pos.undo_move(pv[--ply]); while (ply);
2612 // pv_info_to_uci() returns a string with information on the current PV line
2613 // formatted according to UCI specification and eventually writes the info
2614 // to a log file. It is called at each iteration or after a new pv is found.
2616 std::string RootMove::pv_info_to_uci(const Position& pos, Value alpha, Value beta, int pvLine) {
2618 std::stringstream s, l;
2621 while (*m != MOVE_NONE)
2624 s << "info depth " << Iteration // FIXME
2625 << " seldepth " << int(m - pv)
2626 << " multipv " << pvLine + 1
2627 << " score " << value_to_uci(pv_score)
2628 << (pv_score >= beta ? " lowerbound" : pv_score <= alpha ? " upperbound" : "")
2629 << " time " << current_search_time()
2630 << " nodes " << pos.nodes_searched()
2631 << " nps " << nps(pos)
2632 << " pv " << l.str();
2634 if (UseLogFile && pvLine == 0)
2636 ValueType t = pv_score >= beta ? VALUE_TYPE_LOWER :
2637 pv_score <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
2639 LogFile << pretty_pv(pos, current_search_time(), Iteration, pv_score, t, pv) << endl;
2645 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) {
2647 SearchStack ss[PLY_MAX_PLUS_2];
2648 MoveStack mlist[MOVES_MAX];
2652 // Initialize search stack
2653 init_ss_array(ss, PLY_MAX_PLUS_2);
2654 ss[0].eval = ss[0].evalMargin = VALUE_NONE;
2656 // Generate all legal moves
2657 MoveStack* last = generate_moves(pos, mlist);
2659 // Add each move to the RootMoveList's vector
2660 for (MoveStack* cur = mlist; cur != last; cur++)
2662 // If we have a searchMoves[] list then verify cur->move
2663 // is in the list before to add it.
2664 for (sm = searchMoves; *sm && *sm != cur->move; sm++) {}
2666 if (searchMoves[0] && *sm != cur->move)
2669 // Find a quick score for the move and add to the list
2670 pos.do_move(cur->move, st);
2673 rm.pv[0] = ss[0].currentMove = cur->move;
2674 rm.pv[1] = MOVE_NONE;
2675 rm.pv_score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
2678 pos.undo_move(cur->move);
2683 // Score root moves using the standard way used in main search, the moves
2684 // are scored according to the order in which are returned by MovePicker.
2685 // This is the second order score that is used to compare the moves when
2686 // the first order pv scores of both moves are equal.
2688 void RootMoveList::set_non_pv_scores(const Position& pos)
2691 Value score = VALUE_ZERO;
2692 MovePicker mp(pos, MOVE_NONE, ONE_PLY, H);
2694 while ((move = mp.get_next_move()) != MOVE_NONE)
2695 for (Base::iterator it = begin(); it != end(); ++it)
2696 if (it->pv[0] == move)
2698 it->non_pv_score = score--;