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, Move ttm, SearchStack* ss);
151 void sort() { insertion_sort<RootMove, Base::iterator>(begin(), end()); }
152 void sort_multipv(int n) { insertion_sort<RootMove, Base::iterator>(begin(), begin() + n); }
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& f) {
166 os.iword(0) = int(f);
171 // Overload operator << for moves to make it easier to print moves in
172 // coordinate notation compatible with UCI protocol.
173 std::ostream& operator<<(std::ostream& os, Move m) {
175 bool chess960 = (os.iword(0) != 0); // See set960()
176 return os << move_to_uci(m, chess960);
184 // Maximum depth for razoring
185 const Depth RazorDepth = 4 * ONE_PLY;
187 // Dynamic razoring margin based on depth
188 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
190 // Maximum depth for use of dynamic threat detection when null move fails low
191 const Depth ThreatDepth = 5 * ONE_PLY;
193 // Step 9. Internal iterative deepening
195 // Minimum depth for use of internal iterative deepening
196 const Depth IIDDepth[2] = { 8 * ONE_PLY /* non-PV */, 5 * ONE_PLY /* PV */};
198 // At Non-PV nodes we do an internal iterative deepening search
199 // when the static evaluation is bigger then beta - IIDMargin.
200 const Value IIDMargin = Value(0x100);
202 // Step 11. Decide the new search depth
204 // Extensions. Configurable UCI options
205 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
206 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
207 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
209 // Minimum depth for use of singular extension
210 const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */};
212 // If the TT move is at least SingularExtensionMargin better then the
213 // remaining ones we will extend it.
214 const Value SingularExtensionMargin = Value(0x20);
216 // Step 12. Futility pruning
218 // Futility margin for quiescence search
219 const Value FutilityMarginQS = Value(0x80);
221 // Futility lookup tables (initialized at startup) and their getter functions
222 Value FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
223 int FutilityMoveCountArray[32]; // [depth]
225 inline Value futility_margin(Depth d, int mn) { return d < 7 * ONE_PLY ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE; }
226 inline int futility_move_count(Depth d) { return d < 16 * ONE_PLY ? FutilityMoveCountArray[d] : 512; }
228 // Step 14. Reduced search
230 // Reduction lookup tables (initialized at startup) and their getter functions
231 int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
233 template <NodeType PV>
234 inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
236 // Common adjustments
238 // Search depth at iteration 1
239 const Depth InitialDepth = ONE_PLY;
241 // Easy move margin. An easy move candidate must be at least this much
242 // better than the second best move.
243 const Value EasyMoveMargin = Value(0x200);
246 /// Namespace variables
254 // Scores and number of times the best move changed for each iteration
255 Value ValueByIteration[PLY_MAX_PLUS_2];
256 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
258 // Search window management
264 // Time managment variables
265 int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
266 bool UseTimeManagement, InfiniteSearch, Pondering, StopOnPonderhit;
267 bool FirstRootMove, StopRequest, QuitRequest, AspirationFailLow;
272 std::ofstream LogFile;
274 // Multi-threads manager object
275 ThreadsManager ThreadsMgr;
277 // Node counters, used only by thread[0] but try to keep in different cache
278 // lines (64 bytes each) from the heavy multi-thread read accessed variables.
279 bool SendSearchedNodes;
281 int NodesBetweenPolls = 30000;
288 Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove);
289 Value root_search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, RootMoveList& rml);
291 template <NodeType PvNode, bool SpNode>
292 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
294 template <NodeType PvNode>
295 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
297 template <NodeType PvNode>
298 inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
300 return depth < ONE_PLY ? qsearch<PvNode>(pos, ss, alpha, beta, DEPTH_ZERO, ply)
301 : search<PvNode, false>(pos, ss, alpha, beta, depth, ply);
304 template <NodeType PvNode>
305 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
307 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue);
308 bool connected_moves(const Position& pos, Move m1, Move m2);
309 bool value_is_mate(Value value);
310 Value value_to_tt(Value v, int ply);
311 Value value_from_tt(Value v, int ply);
312 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
313 bool connected_threat(const Position& pos, Move m, Move threat);
314 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
315 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
316 void update_killers(Move m, Move killers[]);
317 void update_gains(const Position& pos, Move move, Value before, Value after);
319 int current_search_time();
320 std::string value_to_uci(Value v);
321 int nps(const Position& pos);
322 void poll(const Position& pos);
323 void wait_for_stop_or_ponderhit();
324 void init_ss_array(SearchStack* ss, int size);
326 #if !defined(_MSC_VER)
327 void* init_thread(void* threadID);
329 DWORD WINAPI init_thread(LPVOID threadID);
339 /// init_threads(), exit_threads() and nodes_searched() are helpers to
340 /// give accessibility to some TM methods from outside of current file.
342 void init_threads() { ThreadsMgr.init_threads(); }
343 void exit_threads() { ThreadsMgr.exit_threads(); }
346 /// init_search() is called during startup. It initializes various lookup tables
350 int d; // depth (ONE_PLY == 2)
351 int hd; // half depth (ONE_PLY == 1)
354 // Init reductions array
355 for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
357 double pvRed = log(double(hd)) * log(double(mc)) / 3.0;
358 double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
359 ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0);
360 ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0);
363 // Init futility margins array
364 for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
365 FutilityMarginsMatrix[d][mc] = Value(112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45);
367 // Init futility move count array
368 for (d = 0; d < 32; d++)
369 FutilityMoveCountArray[d] = int(3.001 + 0.25 * pow(d, 2.0));
373 /// perft() is our utility to verify move generation is bug free. All the legal
374 /// moves up to given depth are generated and counted and the sum returned.
376 int64_t perft(Position& pos, Depth depth)
378 MoveStack mlist[MOVES_MAX];
383 // Generate all legal moves
384 MoveStack* last = generate<MV_LEGAL>(pos, mlist);
386 // If we are at the last ply we don't need to do and undo
387 // the moves, just to count them.
388 if (depth <= ONE_PLY)
389 return int(last - mlist);
391 // Loop through all legal moves
393 for (MoveStack* cur = mlist; cur != last; cur++)
396 pos.do_move(m, st, ci, pos.move_is_check(m, ci));
397 sum += perft(pos, depth - ONE_PLY);
404 /// think() is the external interface to Stockfish's search, and is called when
405 /// the program receives the UCI 'go' command. It initializes various
406 /// search-related global variables, and calls root_search(). It returns false
407 /// when a quit command is received during the search.
409 bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[],
410 int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) {
412 // Initialize global search variables
413 StopOnPonderhit = StopRequest = QuitRequest = AspirationFailLow = SendSearchedNodes = false;
415 SearchStartTime = get_system_time();
416 ExactMaxTime = maxTime;
419 InfiniteSearch = infinite;
421 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
423 // Look for a book move, only during games, not tests
424 if (UseTimeManagement && Options["OwnBook"].value<bool>())
426 if (Options["Book File"].value<std::string>() != OpeningBook.file_name())
427 OpeningBook.open(Options["Book File"].value<std::string>());
429 Move bookMove = OpeningBook.get_move(pos, Options["Best Book Move"].value<bool>());
430 if (bookMove != MOVE_NONE)
433 wait_for_stop_or_ponderhit();
435 cout << "bestmove " << bookMove << endl;
440 // Read UCI option values
441 TT.set_size(Options["Hash"].value<int>());
442 if (Options["Clear Hash"].value<bool>())
444 Options["Clear Hash"].set_value("false");
448 CheckExtension[1] = Options["Check Extension (PV nodes)"].value<Depth>();
449 CheckExtension[0] = Options["Check Extension (non-PV nodes)"].value<Depth>();
450 SingleEvasionExtension[1] = Options["Single Evasion Extension (PV nodes)"].value<Depth>();
451 SingleEvasionExtension[0] = Options["Single Evasion Extension (non-PV nodes)"].value<Depth>();
452 PawnPushTo7thExtension[1] = Options["Pawn Push to 7th Extension (PV nodes)"].value<Depth>();
453 PawnPushTo7thExtension[0] = Options["Pawn Push to 7th Extension (non-PV nodes)"].value<Depth>();
454 PassedPawnExtension[1] = Options["Passed Pawn Extension (PV nodes)"].value<Depth>();
455 PassedPawnExtension[0] = Options["Passed Pawn Extension (non-PV nodes)"].value<Depth>();
456 PawnEndgameExtension[1] = Options["Pawn Endgame Extension (PV nodes)"].value<Depth>();
457 PawnEndgameExtension[0] = Options["Pawn Endgame Extension (non-PV nodes)"].value<Depth>();
458 MateThreatExtension[1] = Options["Mate Threat Extension (PV nodes)"].value<Depth>();
459 MateThreatExtension[0] = Options["Mate Threat Extension (non-PV nodes)"].value<Depth>();
460 MultiPV = Options["MultiPV"].value<int>();
461 UseLogFile = Options["Use Search Log"].value<bool>();
463 read_evaluation_uci_options(pos.side_to_move());
465 // Set the number of active threads
466 ThreadsMgr.read_uci_options();
467 init_eval(ThreadsMgr.active_threads());
469 // Wake up needed threads
470 for (int i = 1; i < ThreadsMgr.active_threads(); i++)
471 ThreadsMgr.wake_sleeping_thread(i);
474 int myTime = time[pos.side_to_move()];
475 int myIncrement = increment[pos.side_to_move()];
476 if (UseTimeManagement)
477 TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter());
479 // Set best NodesBetweenPolls interval to avoid lagging under
480 // heavy time pressure.
482 NodesBetweenPolls = Min(MaxNodes, 30000);
483 else if (myTime && myTime < 1000)
484 NodesBetweenPolls = 1000;
485 else if (myTime && myTime < 5000)
486 NodesBetweenPolls = 5000;
488 NodesBetweenPolls = 30000;
490 // Write search information to log file
493 std::string name = Options["Search Log Filename"].value<std::string>();
494 LogFile.open(name.c_str(), std::ios::out | std::ios::app);
496 LogFile << "Searching: " << pos.to_fen()
497 << "\ninfinite: " << infinite
498 << " ponder: " << ponder
499 << " time: " << myTime
500 << " increment: " << myIncrement
501 << " moves to go: " << movesToGo << endl;
504 // We're ready to start thinking. Call the iterative deepening loop function
505 Move ponderMove = MOVE_NONE;
506 Move bestMove = id_loop(pos, searchMoves, &ponderMove);
508 // Print final search statistics
509 cout << "info nodes " << pos.nodes_searched()
510 << " nps " << nps(pos)
511 << " time " << current_search_time() << endl;
515 LogFile << "\nNodes: " << pos.nodes_searched()
516 << "\nNodes/second: " << nps(pos)
517 << "\nBest move: " << move_to_san(pos, bestMove);
520 pos.do_move(bestMove, st);
521 LogFile << "\nPonder move: "
522 << move_to_san(pos, ponderMove) // Works also with MOVE_NONE
525 // Return from think() with unchanged position
526 pos.undo_move(bestMove);
531 // This makes all the threads to go to sleep
532 ThreadsMgr.set_active_threads(1);
534 // If we are pondering or in infinite search, we shouldn't print the
535 // best move before we are told to do so.
536 if (!StopRequest && (Pondering || InfiniteSearch))
537 wait_for_stop_or_ponderhit();
539 // Could be both MOVE_NONE when searching on a stalemate position
540 cout << "bestmove " << bestMove << " ponder " << ponderMove << endl;
548 // id_loop() is the main iterative deepening loop. It calls root_search
549 // repeatedly with increasing depth until the allocated thinking time has
550 // been consumed, the user stops the search, or the maximum search depth is
553 Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove) {
555 SearchStack ss[PLY_MAX_PLUS_2];
557 Move EasyMove = MOVE_NONE;
558 Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
560 // Moves to search are verified, scored and sorted
561 RootMoveList rml(pos, searchMoves);
563 // Handle special case of searching on a mate/stale position
566 Value s = (pos.is_check() ? -VALUE_MATE : VALUE_DRAW);
568 cout << "info depth " << 1
569 << " score " << value_to_uci(s) << endl;
577 init_ss_array(ss, PLY_MAX_PLUS_2);
578 ValueByIteration[1] = rml[0].pv_score;
581 // Send initial RootMoveList scoring (iteration 1)
582 cout << set960(pos.is_chess960()) // Is enough to set once at the beginning
583 << "info depth " << Iteration
584 << "\n" << rml[0].pv_info_to_uci(pos, alpha, beta) << endl;
586 // Is one move significantly better than others after initial scoring ?
588 || rml[0].pv_score > rml[1].pv_score + EasyMoveMargin)
589 EasyMove = rml[0].pv[0];
591 // Iterative deepening loop
592 while (Iteration < PLY_MAX)
594 // Initialize iteration
596 BestMoveChangesByIteration[Iteration] = 0;
598 cout << "info depth " << Iteration << endl;
600 // Calculate dynamic aspiration window based on previous iterations
601 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
603 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
604 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
606 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
607 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
609 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
610 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
613 depth = (Iteration - 2) * ONE_PLY + InitialDepth;
615 // Search to the current depth, rml is updated and sorted
616 value = root_search(pos, ss, alpha, beta, depth, rml);
619 break; // Value cannot be trusted. Break out immediately!
621 //Save info about search result
622 ValueByIteration[Iteration] = value;
624 // Drop the easy move if differs from the new best move
625 if (rml[0].pv[0] != EasyMove)
626 EasyMove = MOVE_NONE;
628 if (UseTimeManagement)
631 bool stopSearch = false;
633 // Stop search early if there is only a single legal move,
634 // we search up to Iteration 6 anyway to get a proper score.
635 if (Iteration >= 6 && rml.size() == 1)
638 // Stop search early when the last two iterations returned a mate score
640 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
641 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
644 // Stop search early if one move seems to be much better than the others
646 && EasyMove == rml[0].pv[0]
647 && ( ( rml[0].nodes > (pos.nodes_searched() * 85) / 100
648 && current_search_time() > TimeMgr.available_time() / 16)
649 ||( rml[0].nodes > (pos.nodes_searched() * 98) / 100
650 && current_search_time() > TimeMgr.available_time() / 32)))
653 // Add some extra time if the best move has changed during the last two iterations
654 if (Iteration > 5 && Iteration <= 50)
655 TimeMgr.pv_instability(BestMoveChangesByIteration[Iteration],
656 BestMoveChangesByIteration[Iteration-1]);
658 // Stop search if most of MaxSearchTime is consumed at the end of the
659 // iteration. We probably don't have enough time to search the first
660 // move at the next iteration anyway.
661 if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
667 StopOnPonderhit = true;
673 if (MaxDepth && Iteration >= MaxDepth)
677 *ponderMove = rml[0].pv[1];
682 // root_search() is the function which searches the root node. It is
683 // similar to search_pv except that it prints some information to the
684 // standard output and handles the fail low/high loops.
686 Value root_search(Position& pos, SearchStack* ss, Value alpha,
687 Value beta, Depth depth, RootMoveList& rml) {
689 Move movesSearched[MOVES_MAX];
694 Value value, oldAlpha;
695 RootMoveList::iterator rm;
696 bool isCheck, moveIsCheck, captureOrPromotion, dangerous, isPvMove;
697 int moveCount, researchCountFH, researchCountFL;
699 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, rml[0].pv[0], ss);
730 // Step 10. Loop through all moves in the root move list
731 for (rm = rml.begin(); rm != rml.end() && !StopRequest; ++rm)
733 // This is used by time management
734 FirstRootMove = (rm == rml.begin());
736 // Save the current node count before the move is searched
737 nodes = pos.nodes_searched();
739 // If it's time to send nodes info, do it here where we have the
740 // correct accumulated node counts searched by each thread.
741 if (SendSearchedNodes)
743 SendSearchedNodes = false;
744 cout << "info nodes " << nodes
745 << " nps " << nps(pos)
746 << " time " << current_search_time() << endl;
749 // Pick the next root move, and print the move and the move number to
750 // the standard output.
751 move = ss->currentMove = rm->pv[0];
752 movesSearched[moveCount++] = move;
753 isPvMove = (moveCount <= MultiPV);
755 if (current_search_time() >= 1000)
756 cout << "info currmove " << move
757 << " currmovenumber " << moveCount << endl;
759 moveIsCheck = pos.move_is_check(move);
760 captureOrPromotion = pos.move_is_capture_or_promotion(move);
762 // Step 11. Decide the new search depth
763 ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
764 newDepth = depth + ext;
766 // Step 12. Futility pruning (omitted at root)
768 // Step extra. Fail high loop
769 // If move fails high, we research with bigger window until we are not failing
771 value = -VALUE_INFINITE;
775 // Step 13. Make the move
776 pos.do_move(move, st, ci, moveIsCheck);
778 // Step extra. pv search
779 // We do pv search for PV moves and when failing high
780 if (isPvMove || value > alpha)
782 // Aspiration window is disabled in multi-pv case
784 alpha = -VALUE_INFINITE;
786 // Full depth PV search, done on first move or after a fail high
787 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
791 // Step 14. Reduced search
792 // if the move fails high will be re-searched at full depth
793 bool doFullDepthSearch = true;
795 if ( depth >= 3 * ONE_PLY
797 && !captureOrPromotion
798 && !move_is_castle(move))
800 ss->reduction = reduction<PV>(depth, moveCount - MultiPV + 1);
803 assert(newDepth-ss->reduction >= ONE_PLY);
805 // Reduced depth non-pv search using alpha as upperbound
806 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
807 doFullDepthSearch = (value > alpha);
809 ss->reduction = DEPTH_ZERO; // Restore original reduction
812 // Step 15. Full depth search
813 if (doFullDepthSearch)
815 // Full depth non-pv search using alpha as upperbound
816 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, 1);
818 // If we are above alpha then research at same depth but as PV
819 // to get a correct score or eventually a fail high above beta.
821 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
825 // Step 16. Undo move
828 // Can we exit fail high loop ?
829 if (StopRequest || value < beta)
832 // We are failing high and going to do a research. It's important to update
833 // the score before research in case we run out of time while researching.
835 rm->pv_score = value;
836 rm->extract_pv_from_tt(pos);
838 // Update killers and history only for non capture moves that fails high
839 if (!pos.move_is_capture_or_promotion(move))
841 update_history(pos, move, depth, movesSearched, moveCount);
842 update_killers(move, ss->killers);
845 // Inform GUI that PV has changed
846 cout << rm->pv_info_to_uci(pos, alpha, beta) << endl;
848 // Prepare for a research after a fail high, each time with a wider window
849 beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
852 } // End of fail high loop
854 // Finished searching the move. If AbortSearch is true, the search
855 // was aborted because the user interrupted the search or because we
856 // ran out of time. In this case, the return value of the search cannot
857 // be trusted, and we break out of the loop without updating the best
862 // Remember searched nodes counts for this move
863 rm->nodes += pos.nodes_searched() - nodes;
865 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
866 assert(value < beta);
868 // Step 17. Check for new best move
869 if (!isPvMove && value <= alpha)
870 rm->pv_score = -VALUE_INFINITE;
873 // PV move or new best move!
877 rm->pv_score = value;
878 rm->extract_pv_from_tt(pos);
880 // We record how often the best move has been changed in each
881 // iteration. This information is used for time managment: When
882 // the best move changes frequently, we allocate some more time.
883 if (!isPvMove && MultiPV == 1)
884 BestMoveChangesByIteration[Iteration]++;
886 // Inform GUI that PV has changed, in case of multi-pv UCI protocol
887 // requires we send all the PV lines properly sorted.
888 rml.sort_multipv(moveCount);
890 for (int j = 0; j < Min(MultiPV, (int)rml.size()); j++)
891 cout << rml[j].pv_info_to_uci(pos, alpha, beta, j) << endl;
893 // Update alpha. In multi-pv we don't use aspiration window
896 // Raise alpha to setup proper non-pv search upper bound
900 else // Set alpha equal to minimum score among the PV lines
901 alpha = rml[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount?
903 } // PV move or new best move
905 assert(alpha >= oldAlpha);
907 AspirationFailLow = (alpha == oldAlpha);
909 if (AspirationFailLow && StopOnPonderhit)
910 StopOnPonderhit = false;
914 // Can we exit fail low loop ?
915 if (StopRequest || !AspirationFailLow)
918 // Prepare for a research after a fail low, each time with a wider window
919 oldAlpha = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
924 // Sort the moves before to return
927 // Write PV lines to transposition table, in case the relevant entries
928 // have been overwritten during the search.
929 for (int i = 0; i < Min(MultiPV, (int)rml.size()); i++)
930 rml[i].insert_pv_in_tt(pos);
936 // search<>() is the main search function for both PV and non-PV nodes and for
937 // normal and SplitPoint nodes. When called just after a split point the search
938 // is simpler because we have already probed the hash table, done a null move
939 // search, and searched the first move before splitting, we don't have to repeat
940 // all this work again. We also don't need to store anything to the hash table
941 // here: This is taken care of after we return from the split point.
943 template <NodeType PvNode, bool SpNode>
944 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
946 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
947 assert(beta > alpha && beta <= VALUE_INFINITE);
948 assert(PvNode || alpha == beta - 1);
949 assert(ply > 0 && ply < PLY_MAX);
950 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
952 Move movesSearched[MOVES_MAX];
956 Move ttMove, move, excludedMove, threatMove;
959 Value bestValue, value, oldAlpha;
960 Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
961 bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
962 bool mateThreat = false;
964 int threadID = pos.thread();
965 SplitPoint* sp = NULL;
966 refinedValue = bestValue = value = -VALUE_INFINITE;
968 isCheck = pos.is_check();
974 ttMove = excludedMove = MOVE_NONE;
975 threatMove = sp->threatMove;
976 mateThreat = sp->mateThreat;
977 goto split_point_start;
979 else {} // Hack to fix icc's "statement is unreachable" warning
981 // Step 1. Initialize node and poll. Polling can abort search
982 ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
983 (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
985 if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
991 // Step 2. Check for aborted search and immediate draw
993 || ThreadsMgr.cutoff_at_splitpoint(threadID)
995 || ply >= PLY_MAX - 1)
998 // Step 3. Mate distance pruning
999 alpha = Max(value_mated_in(ply), alpha);
1000 beta = Min(value_mate_in(ply+1), beta);
1004 // Step 4. Transposition table lookup
1006 // We don't want the score of a partial search to overwrite a previous full search
1007 // TT value, so we use a different position key in case of an excluded move exists.
1008 excludedMove = ss->excludedMove;
1009 posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1011 tte = TT.retrieve(posKey);
1012 ttMove = tte ? tte->move() : MOVE_NONE;
1014 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1015 // This is to avoid problems in the following areas:
1017 // * Repetition draw detection
1018 // * Fifty move rule detection
1019 // * Searching for a mate
1020 // * Printing of full PV line
1021 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1024 ss->bestMove = ttMove; // Can be MOVE_NONE
1025 return value_from_tt(tte->value(), ply);
1028 // Step 5. Evaluate the position statically and
1029 // update gain statistics of parent move.
1031 ss->eval = ss->evalMargin = VALUE_NONE;
1034 assert(tte->static_value() != VALUE_NONE);
1036 ss->eval = tte->static_value();
1037 ss->evalMargin = tte->static_value_margin();
1038 refinedValue = refine_eval(tte, ss->eval, ply);
1042 refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
1043 TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
1046 // Save gain for the parent non-capture move
1047 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1049 // Step 6. Razoring (is omitted in PV nodes)
1051 && depth < RazorDepth
1053 && refinedValue < beta - razor_margin(depth)
1054 && ttMove == MOVE_NONE
1055 && !value_is_mate(beta)
1056 && !pos.has_pawn_on_7th(pos.side_to_move()))
1058 Value rbeta = beta - razor_margin(depth);
1059 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply);
1061 // Logically we should return (v + razor_margin(depth)), but
1062 // surprisingly this did slightly weaker in tests.
1066 // Step 7. Static null move pruning (is omitted in PV nodes)
1067 // We're betting that the opponent doesn't have a move that will reduce
1068 // the score by more than futility_margin(depth) if we do a null move.
1070 && !ss->skipNullMove
1071 && depth < RazorDepth
1073 && refinedValue >= beta + futility_margin(depth, 0)
1074 && !value_is_mate(beta)
1075 && pos.non_pawn_material(pos.side_to_move()))
1076 return refinedValue - futility_margin(depth, 0);
1078 // Step 8. Null move search with verification search (is omitted in PV nodes)
1080 && !ss->skipNullMove
1083 && refinedValue >= beta
1084 && !value_is_mate(beta)
1085 && pos.non_pawn_material(pos.side_to_move()))
1087 ss->currentMove = MOVE_NULL;
1089 // Null move dynamic reduction based on depth
1090 int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
1092 // Null move dynamic reduction based on value
1093 if (refinedValue - beta > PawnValueMidgame)
1096 pos.do_null_move(st);
1097 (ss+1)->skipNullMove = true;
1098 nullValue = -search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1);
1099 (ss+1)->skipNullMove = false;
1100 pos.undo_null_move();
1102 if (nullValue >= beta)
1104 // Do not return unproven mate scores
1105 if (nullValue >= value_mate_in(PLY_MAX))
1108 if (depth < 6 * ONE_PLY)
1111 // Do verification search at high depths
1112 ss->skipNullMove = true;
1113 Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY, ply);
1114 ss->skipNullMove = false;
1121 // The null move failed low, which means that we may be faced with
1122 // some kind of threat. If the previous move was reduced, check if
1123 // the move that refuted the null move was somehow connected to the
1124 // move which was reduced. If a connection is found, return a fail
1125 // low score (which will cause the reduced move to fail high in the
1126 // parent node, which will trigger a re-search with full depth).
1127 if (nullValue == value_mated_in(ply + 2))
1130 threatMove = (ss+1)->bestMove;
1131 if ( depth < ThreatDepth
1132 && (ss-1)->reduction
1133 && threatMove != MOVE_NONE
1134 && connected_moves(pos, (ss-1)->currentMove, threatMove))
1139 // Step 9. Internal iterative deepening
1140 if ( depth >= IIDDepth[PvNode]
1141 && ttMove == MOVE_NONE
1142 && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
1144 Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
1146 ss->skipNullMove = true;
1147 search<PvNode>(pos, ss, alpha, beta, d, ply);
1148 ss->skipNullMove = false;
1150 ttMove = ss->bestMove;
1151 tte = TT.retrieve(posKey);
1154 // Expensive mate threat detection (only for PV nodes)
1156 mateThreat = pos.has_mate_threat();
1158 split_point_start: // At split points actual search starts from here
1160 // Initialize a MovePicker object for the current position
1161 // FIXME currently MovePicker() c'tor is needless called also in SplitPoint
1162 MovePicker mpBase(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
1163 MovePicker& mp = SpNode ? *sp->mp : mpBase;
1165 ss->bestMove = MOVE_NONE;
1166 singleEvasion = !SpNode && isCheck && mp.number_of_evasions() == 1;
1167 futilityBase = ss->eval + ss->evalMargin;
1168 singularExtensionNode = !SpNode
1169 && depth >= SingularExtensionDepth[PvNode]
1172 && !excludedMove // Do not allow recursive singular extension search
1173 && (tte->type() & VALUE_TYPE_LOWER)
1174 && tte->depth() >= depth - 3 * ONE_PLY;
1177 lock_grab(&(sp->lock));
1178 bestValue = sp->bestValue;
1181 // Step 10. Loop through moves
1182 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1183 while ( bestValue < beta
1184 && (move = mp.get_next_move()) != MOVE_NONE
1185 && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1187 assert(move_is_ok(move));
1191 moveCount = ++sp->moveCount;
1192 lock_release(&(sp->lock));
1194 else if (move == excludedMove)
1197 movesSearched[moveCount++] = move;
1199 moveIsCheck = pos.move_is_check(move, ci);
1200 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1202 // Step 11. Decide the new search depth
1203 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1205 // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s),
1206 // and just one fails high on (alpha, beta), then that move is singular and should be extended.
1207 // To verify this we do a reduced search on all the other moves but the ttMove, if result is
1208 // lower then ttValue minus a margin then we extend ttMove.
1209 if ( singularExtensionNode
1210 && move == tte->move()
1213 Value ttValue = value_from_tt(tte->value(), ply);
1215 if (abs(ttValue) < VALUE_KNOWN_WIN)
1217 Value b = ttValue - SingularExtensionMargin;
1218 ss->excludedMove = move;
1219 ss->skipNullMove = true;
1220 Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
1221 ss->skipNullMove = false;
1222 ss->excludedMove = MOVE_NONE;
1223 ss->bestMove = MOVE_NONE;
1229 // Update current move (this must be done after singular extension search)
1230 ss->currentMove = move;
1231 newDepth = depth - ONE_PLY + ext;
1233 // Step 12. Futility pruning (is omitted in PV nodes)
1235 && !captureOrPromotion
1239 && !move_is_castle(move))
1241 // Move count based pruning
1242 if ( moveCount >= futility_move_count(depth)
1243 && !(threatMove && connected_threat(pos, move, threatMove))
1244 && bestValue > value_mated_in(PLY_MAX)) // FIXME bestValue is racy
1247 lock_grab(&(sp->lock));
1252 // Value based pruning
1253 // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
1254 // but fixing this made program slightly weaker.
1255 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1256 futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount)
1257 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1259 if (futilityValueScaled < beta)
1263 lock_grab(&(sp->lock));
1264 if (futilityValueScaled > sp->bestValue)
1265 sp->bestValue = bestValue = futilityValueScaled;
1267 else if (futilityValueScaled > bestValue)
1268 bestValue = futilityValueScaled;
1273 // Prune moves with negative SEE at low depths
1274 if ( predictedDepth < 2 * ONE_PLY
1275 && bestValue > value_mated_in(PLY_MAX)
1276 && pos.see_sign(move) < 0)
1279 lock_grab(&(sp->lock));
1285 // Step 13. Make the move
1286 pos.do_move(move, st, ci, moveIsCheck);
1288 // Step extra. pv search (only in PV nodes)
1289 // The first move in list is the expected PV
1290 if (PvNode && moveCount == 1)
1291 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1294 // Step 14. Reduced depth search
1295 // If the move fails high will be re-searched at full depth.
1296 bool doFullDepthSearch = true;
1298 if ( depth >= 3 * ONE_PLY
1299 && !captureOrPromotion
1301 && !move_is_castle(move)
1302 && ss->killers[0] != move
1303 && ss->killers[1] != move)
1305 ss->reduction = reduction<PvNode>(depth, moveCount);
1309 alpha = SpNode ? sp->alpha : alpha;
1310 Depth d = newDepth - ss->reduction;
1311 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1313 doFullDepthSearch = (value > alpha);
1315 ss->reduction = DEPTH_ZERO; // Restore original reduction
1318 // Step 15. Full depth search
1319 if (doFullDepthSearch)
1321 alpha = SpNode ? sp->alpha : alpha;
1322 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1324 // Step extra. pv search (only in PV nodes)
1325 // Search only for possible new PV nodes, if instead value >= beta then
1326 // parent node fails low with value <= alpha and tries another move.
1327 if (PvNode && value > alpha && value < beta)
1328 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1332 // Step 16. Undo move
1333 pos.undo_move(move);
1335 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1337 // Step 17. Check for new best move
1340 lock_grab(&(sp->lock));
1341 bestValue = sp->bestValue;
1345 if (value > bestValue && !(SpNode && ThreadsMgr.cutoff_at_splitpoint(threadID)))
1350 sp->bestValue = value;
1354 if (PvNode && value < beta) // We want always alpha < beta
1362 sp->betaCutoff = true;
1364 if (value == value_mate_in(ply + 1))
1365 ss->mateKiller = move;
1367 ss->bestMove = move;
1370 sp->parentSstack->bestMove = move;
1374 // Step 18. Check for split
1376 && depth >= ThreadsMgr.min_split_depth()
1377 && ThreadsMgr.active_threads() > 1
1379 && ThreadsMgr.available_thread_exists(threadID)
1381 && !ThreadsMgr.cutoff_at_splitpoint(threadID)
1383 ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1384 threatMove, mateThreat, moveCount, &mp, PvNode);
1387 // Step 19. Check for mate and stalemate
1388 // All legal moves have been searched and if there are
1389 // no legal moves, it must be mate or stalemate.
1390 // If one move was excluded return fail low score.
1391 if (!SpNode && !moveCount)
1392 return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW;
1394 // Step 20. Update tables
1395 // If the search is not aborted, update the transposition table,
1396 // history counters, and killer moves.
1397 if (!SpNode && !StopRequest && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1399 move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
1400 vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
1401 : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
1403 TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, ss->evalMargin);
1405 // Update killers and history only for non capture moves that fails high
1406 if ( bestValue >= beta
1407 && !pos.move_is_capture_or_promotion(move))
1409 update_history(pos, move, depth, movesSearched, moveCount);
1410 update_killers(move, ss->killers);
1416 // Here we have the lock still grabbed
1417 sp->slaves[threadID] = 0;
1418 sp->nodes += pos.nodes_searched();
1419 lock_release(&(sp->lock));
1422 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1427 // qsearch() is the quiescence search function, which is called by the main
1428 // search function when the remaining depth is zero (or, to be more precise,
1429 // less than ONE_PLY).
1431 template <NodeType PvNode>
1432 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1434 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1435 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1436 assert(PvNode || alpha == beta - 1);
1438 assert(ply > 0 && ply < PLY_MAX);
1439 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1443 Value bestValue, value, evalMargin, futilityValue, futilityBase;
1444 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1447 Value oldAlpha = alpha;
1449 ss->bestMove = ss->currentMove = MOVE_NONE;
1451 // Check for an instant draw or maximum ply reached
1452 if (pos.is_draw() || ply >= PLY_MAX - 1)
1455 // Decide whether or not to include checks, this fixes also the type of
1456 // TT entry depth that we are going to use. Note that in qsearch we use
1457 // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
1458 isCheck = pos.is_check();
1459 ttDepth = (isCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS);
1461 // Transposition table lookup. At PV nodes, we don't use the TT for
1462 // pruning, but only for move ordering.
1463 tte = TT.retrieve(pos.get_key());
1464 ttMove = (tte ? tte->move() : MOVE_NONE);
1466 if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ply))
1468 ss->bestMove = ttMove; // Can be MOVE_NONE
1469 return value_from_tt(tte->value(), ply);
1472 // Evaluate the position statically
1475 bestValue = futilityBase = -VALUE_INFINITE;
1476 ss->eval = evalMargin = VALUE_NONE;
1477 enoughMaterial = false;
1483 assert(tte->static_value() != VALUE_NONE);
1485 evalMargin = tte->static_value_margin();
1486 ss->eval = bestValue = tte->static_value();
1489 ss->eval = bestValue = evaluate(pos, evalMargin);
1491 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1493 // Stand pat. Return immediately if static value is at least beta
1494 if (bestValue >= beta)
1497 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1502 if (PvNode && bestValue > alpha)
1505 // Futility pruning parameters, not needed when in check
1506 futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1507 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1510 // Initialize a MovePicker object for the current position, and prepare
1511 // to search the moves. Because the depth is <= 0 here, only captures,
1512 // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
1514 MovePicker mp(pos, ttMove, depth, H);
1517 // Loop through the moves until no moves remain or a beta cutoff occurs
1518 while ( alpha < beta
1519 && (move = mp.get_next_move()) != MOVE_NONE)
1521 assert(move_is_ok(move));
1523 moveIsCheck = pos.move_is_check(move, ci);
1531 && !move_is_promotion(move)
1532 && !pos.move_is_passed_pawn_push(move))
1534 futilityValue = futilityBase
1535 + pos.endgame_value_of_piece_on(move_to(move))
1536 + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1538 if (futilityValue < alpha)
1540 if (futilityValue > bestValue)
1541 bestValue = futilityValue;
1546 // Detect non-capture evasions that are candidate to be pruned
1547 evasionPrunable = isCheck
1548 && bestValue > value_mated_in(PLY_MAX)
1549 && !pos.move_is_capture(move)
1550 && !pos.can_castle(pos.side_to_move());
1552 // Don't search moves with negative SEE values
1554 && (!isCheck || evasionPrunable)
1556 && !move_is_promotion(move)
1557 && pos.see_sign(move) < 0)
1560 // Don't search useless checks
1565 && !pos.move_is_capture_or_promotion(move)
1566 && ss->eval + PawnValueMidgame / 4 < beta
1567 && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue))
1569 if (ss->eval + PawnValueMidgame / 4 > bestValue)
1570 bestValue = ss->eval + PawnValueMidgame / 4;
1575 // Update current move
1576 ss->currentMove = move;
1578 // Make and search the move
1579 pos.do_move(move, st, ci, moveIsCheck);
1580 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1);
1581 pos.undo_move(move);
1583 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1586 if (value > bestValue)
1592 ss->bestMove = move;
1597 // All legal moves have been searched. A special case: If we're in check
1598 // and no legal moves were found, it is checkmate.
1599 if (isCheck && bestValue == -VALUE_INFINITE)
1600 return value_mated_in(ply);
1602 // Update transposition table
1603 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1604 TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin);
1606 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1612 // check_is_dangerous() tests if a checking move can be pruned in qsearch().
1613 // bestValue is updated only when returning false because in that case move
1616 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bestValue)
1618 Bitboard b, occ, oldAtt, newAtt, kingAtt;
1619 Square from, to, ksq, victimSq;
1622 Value futilityValue, bv = *bestValue;
1624 from = move_from(move);
1626 them = opposite_color(pos.side_to_move());
1627 ksq = pos.king_square(them);
1628 kingAtt = pos.attacks_from<KING>(ksq);
1629 pc = pos.piece_on(from);
1631 occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL << ksq);
1632 oldAtt = pos.attacks_from(pc, from, occ);
1633 newAtt = pos.attacks_from(pc, to, occ);
1635 // Rule 1. Checks which give opponent's king at most one escape square are dangerous
1636 b = kingAtt & ~pos.pieces_of_color(them) & ~newAtt & ~(1ULL << to);
1638 if (!(b && (b & (b - 1))))
1641 // Rule 2. Queen contact check is very dangerous
1642 if ( type_of_piece(pc) == QUEEN
1643 && bit_is_set(kingAtt, to))
1646 // Rule 3. Creating new double threats with checks
1647 b = pos.pieces_of_color(them) & newAtt & ~oldAtt & ~(1ULL << ksq);
1651 victimSq = pop_1st_bit(&b);
1652 futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq);
1654 // Note that here we generate illegal "double move"!
1655 if ( futilityValue >= beta
1656 && pos.see_sign(make_move(from, victimSq)) >= 0)
1659 if (futilityValue > bv)
1663 // Update bestValue only if check is not dangerous (because we will prune the move)
1669 // connected_moves() tests whether two moves are 'connected' in the sense
1670 // that the first move somehow made the second move possible (for instance
1671 // if the moving piece is the same in both moves). The first move is assumed
1672 // to be the move that was made to reach the current position, while the
1673 // second move is assumed to be a move from the current position.
1675 bool connected_moves(const Position& pos, Move m1, Move m2) {
1677 Square f1, t1, f2, t2;
1680 assert(m1 && move_is_ok(m1));
1681 assert(m2 && move_is_ok(m2));
1683 // Case 1: The moving piece is the same in both moves
1689 // Case 2: The destination square for m2 was vacated by m1
1695 // Case 3: Moving through the vacated square
1696 if ( piece_is_slider(pos.piece_on(f2))
1697 && bit_is_set(squares_between(f2, t2), f1))
1700 // Case 4: The destination square for m2 is defended by the moving piece in m1
1701 p = pos.piece_on(t1);
1702 if (bit_is_set(pos.attacks_from(p, t1), t2))
1705 // Case 5: Discovered check, checking piece is the piece moved in m1
1706 if ( piece_is_slider(p)
1707 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1708 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1710 // discovered_check_candidates() works also if the Position's side to
1711 // move is the opposite of the checking piece.
1712 Color them = opposite_color(pos.side_to_move());
1713 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1715 if (bit_is_set(dcCandidates, f2))
1722 // value_is_mate() checks if the given value is a mate one eventually
1723 // compensated for the ply.
1725 bool value_is_mate(Value value) {
1727 assert(abs(value) <= VALUE_INFINITE);
1729 return value <= value_mated_in(PLY_MAX)
1730 || value >= value_mate_in(PLY_MAX);
1734 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1735 // "plies to mate from the current ply". Non-mate scores are unchanged.
1736 // The function is called before storing a value to the transposition table.
1738 Value value_to_tt(Value v, int ply) {
1740 if (v >= value_mate_in(PLY_MAX))
1743 if (v <= value_mated_in(PLY_MAX))
1750 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1751 // the transposition table to a mate score corrected for the current ply.
1753 Value value_from_tt(Value v, int ply) {
1755 if (v >= value_mate_in(PLY_MAX))
1758 if (v <= value_mated_in(PLY_MAX))
1765 // extension() decides whether a move should be searched with normal depth,
1766 // or with extended depth. Certain classes of moves (checking moves, in
1767 // particular) are searched with bigger depth than ordinary moves and in
1768 // any case are marked as 'dangerous'. Note that also if a move is not
1769 // extended, as example because the corresponding UCI option is set to zero,
1770 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1771 template <NodeType PvNode>
1772 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1773 bool singleEvasion, bool mateThreat, bool* dangerous) {
1775 assert(m != MOVE_NONE);
1777 Depth result = DEPTH_ZERO;
1778 *dangerous = moveIsCheck | singleEvasion | mateThreat;
1782 if (moveIsCheck && pos.see_sign(m) >= 0)
1783 result += CheckExtension[PvNode];
1786 result += SingleEvasionExtension[PvNode];
1789 result += MateThreatExtension[PvNode];
1792 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1794 Color c = pos.side_to_move();
1795 if (relative_rank(c, move_to(m)) == RANK_7)
1797 result += PawnPushTo7thExtension[PvNode];
1800 if (pos.pawn_is_passed(c, move_to(m)))
1802 result += PassedPawnExtension[PvNode];
1807 if ( captureOrPromotion
1808 && pos.type_of_piece_on(move_to(m)) != PAWN
1809 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1810 - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1811 && !move_is_promotion(m)
1814 result += PawnEndgameExtension[PvNode];
1819 && captureOrPromotion
1820 && pos.type_of_piece_on(move_to(m)) != PAWN
1821 && pos.see_sign(m) >= 0)
1823 result += ONE_PLY / 2;
1827 return Min(result, ONE_PLY);
1831 // connected_threat() tests whether it is safe to forward prune a move or if
1832 // is somehow coonected to the threat move returned by null search.
1834 bool connected_threat(const Position& pos, Move m, Move threat) {
1836 assert(move_is_ok(m));
1837 assert(threat && move_is_ok(threat));
1838 assert(!pos.move_is_check(m));
1839 assert(!pos.move_is_capture_or_promotion(m));
1840 assert(!pos.move_is_passed_pawn_push(m));
1842 Square mfrom, mto, tfrom, tto;
1844 mfrom = move_from(m);
1846 tfrom = move_from(threat);
1847 tto = move_to(threat);
1849 // Case 1: Don't prune moves which move the threatened piece
1853 // Case 2: If the threatened piece has value less than or equal to the
1854 // value of the threatening piece, don't prune move which defend it.
1855 if ( pos.move_is_capture(threat)
1856 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1857 || pos.type_of_piece_on(tfrom) == KING)
1858 && pos.move_attacks_square(m, tto))
1861 // Case 3: If the moving piece in the threatened move is a slider, don't
1862 // prune safe moves which block its ray.
1863 if ( piece_is_slider(pos.piece_on(tfrom))
1864 && bit_is_set(squares_between(tfrom, tto), mto)
1865 && pos.see_sign(m) >= 0)
1872 // ok_to_use_TT() returns true if a transposition table score
1873 // can be used at a given point in search.
1875 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1877 Value v = value_from_tt(tte->value(), ply);
1879 return ( tte->depth() >= depth
1880 || v >= Max(value_mate_in(PLY_MAX), beta)
1881 || v < Min(value_mated_in(PLY_MAX), beta))
1883 && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1884 || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1888 // refine_eval() returns the transposition table score if
1889 // possible otherwise falls back on static position evaluation.
1891 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1895 Value v = value_from_tt(tte->value(), ply);
1897 if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1898 || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1905 // update_history() registers a good move that produced a beta-cutoff
1906 // in history and marks as failures all the other moves of that ply.
1908 void update_history(const Position& pos, Move move, Depth depth,
1909 Move movesSearched[], int moveCount) {
1912 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
1914 for (int i = 0; i < moveCount - 1; i++)
1916 m = movesSearched[i];
1920 if (!pos.move_is_capture_or_promotion(m))
1921 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
1926 // update_killers() add a good move that produced a beta-cutoff
1927 // among the killer moves of that ply.
1929 void update_killers(Move m, Move killers[]) {
1931 if (m == killers[0])
1934 killers[1] = killers[0];
1939 // update_gains() updates the gains table of a non-capture move given
1940 // the static position evaluation before and after the move.
1942 void update_gains(const Position& pos, Move m, Value before, Value after) {
1945 && before != VALUE_NONE
1946 && after != VALUE_NONE
1947 && pos.captured_piece_type() == PIECE_TYPE_NONE
1948 && !move_is_special(m))
1949 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
1953 // init_ss_array() does a fast reset of the first entries of a SearchStack
1954 // array and of all the excludedMove and skipNullMove entries.
1956 void init_ss_array(SearchStack* ss, int size) {
1958 for (int i = 0; i < size; i++, ss++)
1960 ss->excludedMove = MOVE_NONE;
1961 ss->skipNullMove = false;
1962 ss->reduction = DEPTH_ZERO;
1966 ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE;
1971 // value_to_uci() converts a value to a string suitable for use with the UCI
1972 // protocol specifications:
1974 // cp <x> The score from the engine's point of view in centipawns.
1975 // mate <y> Mate in y moves, not plies. If the engine is getting mated
1976 // use negative values for y.
1978 std::string value_to_uci(Value v) {
1980 std::stringstream s;
1982 if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
1983 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to centipawns
1985 s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
1991 // current_search_time() returns the number of milliseconds which have passed
1992 // since the beginning of the current search.
1994 int current_search_time() {
1996 return get_system_time() - SearchStartTime;
2000 // nps() computes the current nodes/second count
2002 int nps(const Position& pos) {
2004 int t = current_search_time();
2005 return (t > 0 ? int((pos.nodes_searched() * 1000) / t) : 0);
2009 // poll() performs two different functions: It polls for user input, and it
2010 // looks at the time consumed so far and decides if it's time to abort the
2013 void poll(const Position& pos) {
2015 static int lastInfoTime;
2016 int t = current_search_time();
2019 if (input_available())
2021 // We are line oriented, don't read single chars
2022 std::string command;
2024 if (!std::getline(std::cin, command))
2027 if (command == "quit")
2029 // Quit the program as soon as possible
2031 QuitRequest = StopRequest = true;
2034 else if (command == "stop")
2036 // Stop calculating as soon as possible, but still send the "bestmove"
2037 // and possibly the "ponder" token when finishing the search.
2041 else if (command == "ponderhit")
2043 // The opponent has played the expected move. GUI sends "ponderhit" if
2044 // we were told to ponder on the same move the opponent has played. We
2045 // should continue searching but switching from pondering to normal search.
2048 if (StopOnPonderhit)
2053 // Print search information
2057 else if (lastInfoTime > t)
2058 // HACK: Must be a new search where we searched less than
2059 // NodesBetweenPolls nodes during the first second of search.
2062 else if (t - lastInfoTime >= 1000)
2069 if (dbg_show_hit_rate)
2070 dbg_print_hit_rate();
2072 // Send info on searched nodes as soon as we return to root
2073 SendSearchedNodes = true;
2076 // Should we stop the search?
2080 bool stillAtFirstMove = FirstRootMove
2081 && !AspirationFailLow
2082 && t > TimeMgr.available_time();
2084 bool noMoreTime = t > TimeMgr.maximum_time()
2085 || stillAtFirstMove;
2087 if ( (UseTimeManagement && noMoreTime)
2088 || (ExactMaxTime && t >= ExactMaxTime)
2089 || (MaxNodes && pos.nodes_searched() >= MaxNodes)) // FIXME
2094 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2095 // while the program is pondering. The point is to work around a wrinkle in
2096 // the UCI protocol: When pondering, the engine is not allowed to give a
2097 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2098 // We simply wait here until one of these commands is sent, and return,
2099 // after which the bestmove and pondermove will be printed.
2101 void wait_for_stop_or_ponderhit() {
2103 std::string command;
2107 // Wait for a command from stdin
2108 if (!std::getline(std::cin, command))
2111 if (command == "quit")
2116 else if (command == "ponderhit" || command == "stop")
2122 // init_thread() is the function which is called when a new thread is
2123 // launched. It simply calls the idle_loop() function with the supplied
2124 // threadID. There are two versions of this function; one for POSIX
2125 // threads and one for Windows threads.
2127 #if !defined(_MSC_VER)
2129 void* init_thread(void* threadID) {
2131 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2137 DWORD WINAPI init_thread(LPVOID threadID) {
2139 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2146 /// The ThreadsManager class
2149 // read_uci_options() updates number of active threads and other internal
2150 // parameters according to the UCI options values. It is called before
2151 // to start a new search.
2153 void ThreadsManager::read_uci_options() {
2155 maxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value<int>();
2156 minimumSplitDepth = Options["Minimum Split Depth"].value<int>() * ONE_PLY;
2157 useSleepingThreads = Options["Use Sleeping Threads"].value<bool>();
2158 activeThreads = Options["Threads"].value<int>();
2162 // idle_loop() is where the threads are parked when they have no work to do.
2163 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2164 // object for which the current thread is the master.
2166 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2168 assert(threadID >= 0 && threadID < MAX_THREADS);
2171 bool allFinished = false;
2175 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2176 // master should exit as last one.
2177 if (allThreadsShouldExit)
2180 threads[threadID].state = THREAD_TERMINATED;
2184 // If we are not thinking, wait for a condition to be signaled
2185 // instead of wasting CPU time polling for work.
2186 while ( threadID >= activeThreads || threads[threadID].state == THREAD_INITIALIZING
2187 || (useSleepingThreads && threads[threadID].state == THREAD_AVAILABLE))
2189 assert(!sp || useSleepingThreads);
2190 assert(threadID != 0 || useSleepingThreads);
2192 if (threads[threadID].state == THREAD_INITIALIZING)
2193 threads[threadID].state = THREAD_AVAILABLE;
2195 // Grab the lock to avoid races with wake_sleeping_thread()
2196 lock_grab(&sleepLock[threadID]);
2198 // If we are master and all slaves have finished do not go to sleep
2199 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2200 allFinished = (i == activeThreads);
2202 if (allFinished || allThreadsShouldExit)
2204 lock_release(&sleepLock[threadID]);
2208 // Do sleep here after retesting sleep conditions
2209 if (threadID >= activeThreads || threads[threadID].state == THREAD_AVAILABLE)
2210 cond_wait(&sleepCond[threadID], &sleepLock[threadID]);
2212 lock_release(&sleepLock[threadID]);
2215 // If this thread has been assigned work, launch a search
2216 if (threads[threadID].state == THREAD_WORKISWAITING)
2218 assert(!allThreadsShouldExit);
2220 threads[threadID].state = THREAD_SEARCHING;
2222 // Here we call search() with SplitPoint template parameter set to true
2223 SplitPoint* tsp = threads[threadID].splitPoint;
2224 Position pos(*tsp->pos, threadID);
2225 SearchStack* ss = tsp->sstack[threadID] + 1;
2229 search<PV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2231 search<NonPV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2233 assert(threads[threadID].state == THREAD_SEARCHING);
2235 threads[threadID].state = THREAD_AVAILABLE;
2237 // Wake up master thread so to allow it to return from the idle loop in
2238 // case we are the last slave of the split point.
2239 if (useSleepingThreads && threadID != tsp->master && threads[tsp->master].state == THREAD_AVAILABLE)
2240 wake_sleeping_thread(tsp->master);
2243 // If this thread is the master of a split point and all slaves have
2244 // finished their work at this split point, return from the idle loop.
2245 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2246 allFinished = (i == activeThreads);
2250 // Because sp->slaves[] is reset under lock protection,
2251 // be sure sp->lock has been released before to return.
2252 lock_grab(&(sp->lock));
2253 lock_release(&(sp->lock));
2255 // In helpful master concept a master can help only a sub-tree, and
2256 // because here is all finished is not possible master is booked.
2257 assert(threads[threadID].state == THREAD_AVAILABLE);
2259 threads[threadID].state = THREAD_SEARCHING;
2266 // init_threads() is called during startup. It launches all helper threads,
2267 // and initializes the split point stack and the global locks and condition
2270 void ThreadsManager::init_threads() {
2272 int i, arg[MAX_THREADS];
2275 // Initialize global locks
2278 for (i = 0; i < MAX_THREADS; i++)
2280 lock_init(&sleepLock[i]);
2281 cond_init(&sleepCond[i]);
2284 // Initialize splitPoints[] locks
2285 for (i = 0; i < MAX_THREADS; i++)
2286 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2287 lock_init(&(threads[i].splitPoints[j].lock));
2289 // Will be set just before program exits to properly end the threads
2290 allThreadsShouldExit = false;
2292 // Threads will be put all threads to sleep as soon as created
2295 // All threads except the main thread should be initialized to THREAD_INITIALIZING
2296 threads[0].state = THREAD_SEARCHING;
2297 for (i = 1; i < MAX_THREADS; i++)
2298 threads[i].state = THREAD_INITIALIZING;
2300 // Launch the helper threads
2301 for (i = 1; i < MAX_THREADS; i++)
2305 #if !defined(_MSC_VER)
2306 pthread_t pthread[1];
2307 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
2308 pthread_detach(pthread[0]);
2310 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
2314 cout << "Failed to create thread number " << i << endl;
2318 // Wait until the thread has finished launching and is gone to sleep
2319 while (threads[i].state == THREAD_INITIALIZING) {}
2324 // exit_threads() is called when the program exits. It makes all the
2325 // helper threads exit cleanly.
2327 void ThreadsManager::exit_threads() {
2329 allThreadsShouldExit = true; // Let the woken up threads to exit idle_loop()
2331 // Wake up all the threads and waits for termination
2332 for (int i = 1; i < MAX_THREADS; i++)
2334 wake_sleeping_thread(i);
2335 while (threads[i].state != THREAD_TERMINATED) {}
2338 // Now we can safely destroy the locks
2339 for (int i = 0; i < MAX_THREADS; i++)
2340 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2341 lock_destroy(&(threads[i].splitPoints[j].lock));
2343 lock_destroy(&mpLock);
2345 // Now we can safely destroy the wait conditions
2346 for (int i = 0; i < MAX_THREADS; i++)
2348 lock_destroy(&sleepLock[i]);
2349 cond_destroy(&sleepCond[i]);
2354 // cutoff_at_splitpoint() checks whether a beta cutoff has occurred in
2355 // the thread's currently active split point, or in some ancestor of
2356 // the current split point.
2358 bool ThreadsManager::cutoff_at_splitpoint(int threadID) const {
2360 assert(threadID >= 0 && threadID < activeThreads);
2362 SplitPoint* sp = threads[threadID].splitPoint;
2364 for ( ; sp && !sp->betaCutoff; sp = sp->parent) {}
2369 // thread_is_available() checks whether the thread with threadID "slave" is
2370 // available to help the thread with threadID "master" at a split point. An
2371 // obvious requirement is that "slave" must be idle. With more than two
2372 // threads, this is not by itself sufficient: If "slave" is the master of
2373 // some active split point, it is only available as a slave to the other
2374 // threads which are busy searching the split point at the top of "slave"'s
2375 // split point stack (the "helpful master concept" in YBWC terminology).
2377 bool ThreadsManager::thread_is_available(int slave, int master) const {
2379 assert(slave >= 0 && slave < activeThreads);
2380 assert(master >= 0 && master < activeThreads);
2381 assert(activeThreads > 1);
2383 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2386 // Make a local copy to be sure doesn't change under our feet
2387 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2389 // No active split points means that the thread is available as
2390 // a slave for any other thread.
2391 if (localActiveSplitPoints == 0 || activeThreads == 2)
2394 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2395 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2396 // could have been set to 0 by another thread leading to an out of bound access.
2397 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2404 // available_thread_exists() tries to find an idle thread which is available as
2405 // a slave for the thread with threadID "master".
2407 bool ThreadsManager::available_thread_exists(int master) const {
2409 assert(master >= 0 && master < activeThreads);
2410 assert(activeThreads > 1);
2412 for (int i = 0; i < activeThreads; i++)
2413 if (thread_is_available(i, master))
2420 // split() does the actual work of distributing the work at a node between
2421 // several available threads. If it does not succeed in splitting the
2422 // node (because no idle threads are available, or because we have no unused
2423 // split point objects), the function immediately returns. If splitting is
2424 // possible, a SplitPoint object is initialized with all the data that must be
2425 // copied to the helper threads and we tell our helper threads that they have
2426 // been assigned work. This will cause them to instantly leave their idle loops and
2427 // call search().When all threads have returned from search() then split() returns.
2429 template <bool Fake>
2430 void ThreadsManager::split(Position& pos, SearchStack* ss, int ply, Value* alpha,
2431 const Value beta, Value* bestValue, Depth depth, Move threatMove,
2432 bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) {
2433 assert(pos.is_ok());
2434 assert(ply > 0 && ply < PLY_MAX);
2435 assert(*bestValue >= -VALUE_INFINITE);
2436 assert(*bestValue <= *alpha);
2437 assert(*alpha < beta);
2438 assert(beta <= VALUE_INFINITE);
2439 assert(depth > DEPTH_ZERO);
2440 assert(pos.thread() >= 0 && pos.thread() < activeThreads);
2441 assert(activeThreads > 1);
2443 int i, master = pos.thread();
2444 Thread& masterThread = threads[master];
2448 // If no other thread is available to help us, or if we have too many
2449 // active split points, don't split.
2450 if ( !available_thread_exists(master)
2451 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2453 lock_release(&mpLock);
2457 // Pick the next available split point object from the split point stack
2458 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2460 // Initialize the split point object
2461 splitPoint.parent = masterThread.splitPoint;
2462 splitPoint.master = master;
2463 splitPoint.betaCutoff = false;
2464 splitPoint.ply = ply;
2465 splitPoint.depth = depth;
2466 splitPoint.threatMove = threatMove;
2467 splitPoint.mateThreat = mateThreat;
2468 splitPoint.alpha = *alpha;
2469 splitPoint.beta = beta;
2470 splitPoint.pvNode = pvNode;
2471 splitPoint.bestValue = *bestValue;
2473 splitPoint.moveCount = moveCount;
2474 splitPoint.pos = &pos;
2475 splitPoint.nodes = 0;
2476 splitPoint.parentSstack = ss;
2477 for (i = 0; i < activeThreads; i++)
2478 splitPoint.slaves[i] = 0;
2480 masterThread.splitPoint = &splitPoint;
2482 // If we are here it means we are not available
2483 assert(masterThread.state != THREAD_AVAILABLE);
2485 int workersCnt = 1; // At least the master is included
2487 // Allocate available threads setting state to THREAD_BOOKED
2488 for (i = 0; !Fake && i < activeThreads && workersCnt < maxThreadsPerSplitPoint; i++)
2489 if (thread_is_available(i, master))
2491 threads[i].state = THREAD_BOOKED;
2492 threads[i].splitPoint = &splitPoint;
2493 splitPoint.slaves[i] = 1;
2497 assert(Fake || workersCnt > 1);
2499 // We can release the lock because slave threads are already booked and master is not available
2500 lock_release(&mpLock);
2502 // Tell the threads that they have work to do. This will make them leave
2503 // their idle loop. But before copy search stack tail for each thread.
2504 for (i = 0; i < activeThreads; i++)
2505 if (i == master || splitPoint.slaves[i])
2507 memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
2509 assert(i == master || threads[i].state == THREAD_BOOKED);
2511 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2513 if (useSleepingThreads && i != master)
2514 wake_sleeping_thread(i);
2517 // Everything is set up. The master thread enters the idle loop, from
2518 // which it will instantly launch a search, because its state is
2519 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2520 // idle loop, which means that the main thread will return from the idle
2521 // loop when all threads have finished their work at this split point.
2522 idle_loop(master, &splitPoint);
2524 // We have returned from the idle loop, which means that all threads are
2525 // finished. Update alpha and bestValue, and return.
2528 *alpha = splitPoint.alpha;
2529 *bestValue = splitPoint.bestValue;
2530 masterThread.activeSplitPoints--;
2531 masterThread.splitPoint = splitPoint.parent;
2532 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
2534 lock_release(&mpLock);
2538 // wake_sleeping_thread() wakes up the thread with the given threadID
2539 // when it is time to start a new search.
2541 void ThreadsManager::wake_sleeping_thread(int threadID) {
2543 lock_grab(&sleepLock[threadID]);
2544 cond_signal(&sleepCond[threadID]);
2545 lock_release(&sleepLock[threadID]);
2549 /// RootMove and RootMoveList method's definitions
2551 RootMove::RootMove() {
2554 pv_score = non_pv_score = -VALUE_INFINITE;
2558 RootMove& RootMove::operator=(const RootMove& rm) {
2560 const Move* src = rm.pv;
2563 // Avoid a costly full rm.pv[] copy
2564 do *dst++ = *src; while (*src++ != MOVE_NONE);
2567 pv_score = rm.pv_score;
2568 non_pv_score = rm.non_pv_score;
2572 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2573 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2574 // allow to always have a ponder move even when we fail high at root and also a
2575 // long PV to print that is important for position analysis.
2577 void RootMove::extract_pv_from_tt(Position& pos) {
2579 StateInfo state[PLY_MAX_PLUS_2], *st = state;
2583 assert(pv[0] != MOVE_NONE && move_is_legal(pos, pv[0]));
2585 pos.do_move(pv[0], *st++);
2587 while ( (tte = TT.retrieve(pos.get_key())) != NULL
2588 && tte->move() != MOVE_NONE
2589 && move_is_legal(pos, tte->move())
2591 && (!pos.is_draw() || ply < 2))
2593 pv[ply] = tte->move();
2594 pos.do_move(pv[ply++], *st++);
2596 pv[ply] = MOVE_NONE;
2598 do pos.undo_move(pv[--ply]); while (ply);
2601 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2602 // the PV back into the TT. This makes sure the old PV moves are searched
2603 // first, even if the old TT entries have been overwritten.
2605 void RootMove::insert_pv_in_tt(Position& pos) {
2607 StateInfo state[PLY_MAX_PLUS_2], *st = state;
2610 Value v, m = VALUE_NONE;
2613 assert(pv[0] != MOVE_NONE && move_is_legal(pos, pv[0]));
2617 tte = TT.retrieve(k);
2619 // Don't overwrite exsisting correct entries
2620 if (!tte || tte->move() != pv[ply])
2622 v = (pos.is_check() ? VALUE_NONE : evaluate(pos, m));
2623 TT.store(k, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[ply], v, m);
2625 pos.do_move(pv[ply], *st++);
2627 } while (pv[++ply] != MOVE_NONE);
2629 do pos.undo_move(pv[--ply]); while (ply);
2632 // pv_info_to_uci() returns a string with information on the current PV line
2633 // formatted according to UCI specification and eventually writes the info
2634 // to a log file. It is called at each iteration or after a new pv is found.
2636 std::string RootMove::pv_info_to_uci(const Position& pos, Value alpha, Value beta, int pvLine) {
2638 std::stringstream s, l;
2641 while (*m != MOVE_NONE)
2644 s << "info depth " << Iteration // FIXME
2645 << " seldepth " << int(m - pv)
2646 << " multipv " << pvLine + 1
2647 << " score " << value_to_uci(pv_score)
2648 << (pv_score >= beta ? " lowerbound" : pv_score <= alpha ? " upperbound" : "")
2649 << " time " << current_search_time()
2650 << " nodes " << pos.nodes_searched()
2651 << " nps " << nps(pos)
2652 << " pv " << l.str();
2654 if (UseLogFile && pvLine == 0)
2656 ValueType t = pv_score >= beta ? VALUE_TYPE_LOWER :
2657 pv_score <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
2659 LogFile << pretty_pv(pos, current_search_time(), Iteration, pv_score, t, pv) << endl;
2665 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) {
2667 SearchStack ss[PLY_MAX_PLUS_2];
2668 MoveStack mlist[MOVES_MAX];
2672 // Initialize search stack
2673 init_ss_array(ss, PLY_MAX_PLUS_2);
2674 ss[0].eval = ss[0].evalMargin = VALUE_NONE;
2676 // Generate all legal moves
2677 MoveStack* last = generate<MV_LEGAL>(pos, mlist);
2679 // Add each move to the RootMoveList's vector
2680 for (MoveStack* cur = mlist; cur != last; cur++)
2682 // If we have a searchMoves[] list then verify cur->move
2683 // is in the list before to add it.
2684 for (sm = searchMoves; *sm && *sm != cur->move; sm++) {}
2686 if (searchMoves[0] && *sm != cur->move)
2689 // Find a quick score for the move and add to the list
2690 pos.do_move(cur->move, st);
2693 rm.pv[0] = ss[0].currentMove = cur->move;
2694 rm.pv[1] = MOVE_NONE;
2695 rm.pv_score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
2698 pos.undo_move(cur->move);
2703 // Score root moves using the standard way used in main search, the moves
2704 // are scored according to the order in which are returned by MovePicker.
2705 // This is the second order score that is used to compare the moves when
2706 // the first order pv scores of both moves are equal.
2708 void RootMoveList::set_non_pv_scores(const Position& pos, Move ttm, SearchStack* ss)
2711 Value score = VALUE_ZERO;
2712 MovePicker mp(pos, ttm, ONE_PLY, H, ss);
2714 while ((move = mp.get_next_move()) != MOVE_NONE)
2715 for (Base::iterator it = begin(); it != end(); ++it)
2716 if (it->pv[0] == move)
2718 it->non_pv_score = score--;