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;
133 Move pv[PLY_MAX_PLUS_2];
136 RootMove::RootMove() {
139 pv_score = non_pv_score = -VALUE_INFINITE;
143 RootMove& RootMove::operator=(const RootMove& rm) {
145 const Move* src = rm.pv;
148 // Avoid a costly full rm.pv[] copy
149 do *dst++ = *src; while (*src++ != MOVE_NONE);
152 pv_score = rm.pv_score;
153 non_pv_score = rm.non_pv_score;
158 // RootMoveList struct is essentially a std::vector<> of RootMove objects,
159 // with an handful of methods above the standard ones.
161 struct RootMoveList : public std::vector<RootMove> {
163 typedef std::vector<RootMove> Base;
165 RootMoveList(Position& pos, Move searchMoves[]);
166 void set_non_pv_scores(const Position& pos);
168 void sort() { insertion_sort<RootMove, Base::iterator>(begin(), end()); }
169 void sort_multipv(int n) { insertion_sort<RootMove, Base::iterator>(begin(), begin() + n); }
173 // When formatting a move for std::cout we must know if we are in Chess960
174 // or not. To keep using the handy operator<<() on the move the trick is to
175 // embed this flag in the stream itself. Function-like named enum set960 is
176 // used as a custom manipulator and the stream internal general-purpose array,
177 // accessed through ios_base::iword(), is used to pass the flag to the move's
178 // operator<<() that will use it to properly format castling moves.
181 std::ostream& operator<< (std::ostream& os, const set960& m) {
183 os.iword(0) = int(m);
192 // Maximum depth for razoring
193 const Depth RazorDepth = 4 * ONE_PLY;
195 // Dynamic razoring margin based on depth
196 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
198 // Maximum depth for use of dynamic threat detection when null move fails low
199 const Depth ThreatDepth = 5 * ONE_PLY;
201 // Step 9. Internal iterative deepening
203 // Minimum depth for use of internal iterative deepening
204 const Depth IIDDepth[2] = { 8 * ONE_PLY /* non-PV */, 5 * ONE_PLY /* PV */};
206 // At Non-PV nodes we do an internal iterative deepening search
207 // when the static evaluation is bigger then beta - IIDMargin.
208 const Value IIDMargin = Value(0x100);
210 // Step 11. Decide the new search depth
212 // Extensions. Configurable UCI options
213 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
214 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
215 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
217 // Minimum depth for use of singular extension
218 const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */};
220 // If the TT move is at least SingularExtensionMargin better then the
221 // remaining ones we will extend it.
222 const Value SingularExtensionMargin = Value(0x20);
224 // Step 12. Futility pruning
226 // Futility margin for quiescence search
227 const Value FutilityMarginQS = Value(0x80);
229 // Futility lookup tables (initialized at startup) and their getter functions
230 Value FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
231 int FutilityMoveCountArray[32]; // [depth]
233 inline Value futility_margin(Depth d, int mn) { return d < 7 * ONE_PLY ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE; }
234 inline int futility_move_count(Depth d) { return d < 16 * ONE_PLY ? FutilityMoveCountArray[d] : 512; }
236 // Step 14. Reduced search
238 // Reduction lookup tables (initialized at startup) and their getter functions
239 int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
241 template <NodeType PV>
242 inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
244 // Common adjustments
246 // Search depth at iteration 1
247 const Depth InitialDepth = ONE_PLY;
249 // Easy move margin. An easy move candidate must be at least this much
250 // better than the second best move.
251 const Value EasyMoveMargin = Value(0x200);
254 /// Namespace variables
262 // Scores and number of times the best move changed for each iteration
263 Value ValueByIteration[PLY_MAX_PLUS_2];
264 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
266 // Search window management
272 // Time managment variables
273 int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
274 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
275 bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
280 std::ofstream LogFile;
282 // Multi-threads manager object
283 ThreadsManager ThreadsMgr;
285 // Node counters, used only by thread[0] but try to keep in different cache
286 // lines (64 bytes each) from the heavy multi-thread read accessed variables.
288 int NodesBetweenPolls = 30000;
295 Value id_loop(Position& pos, Move searchMoves[]);
296 Value root_search(Position& pos, SearchStack* ss, RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
298 template <NodeType PvNode, bool SpNode>
299 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
301 template <NodeType PvNode>
302 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
304 template <NodeType PvNode>
305 inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
307 return depth < ONE_PLY ? qsearch<PvNode>(pos, ss, alpha, beta, DEPTH_ZERO, ply)
308 : search<PvNode, false>(pos, ss, alpha, beta, depth, ply);
311 template <NodeType PvNode>
312 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
314 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue);
315 bool connected_moves(const Position& pos, Move m1, Move m2);
316 bool value_is_mate(Value value);
317 Value value_to_tt(Value v, int ply);
318 Value value_from_tt(Value v, int ply);
319 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
320 bool connected_threat(const Position& pos, Move m, Move threat);
321 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
322 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
323 void update_killers(Move m, SearchStack* ss);
324 void update_gains(const Position& pos, Move move, Value before, Value after);
326 int current_search_time();
327 std::string value_to_uci(Value v);
328 int nps(const Position& pos);
329 void poll(const Position& pos);
331 void wait_for_stop_or_ponderhit();
332 void init_ss_array(SearchStack* ss, int size);
333 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value);
334 void insert_pv_in_tt(const Position& pos, Move pv[]);
335 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]);
337 #if !defined(_MSC_VER)
338 void* init_thread(void* threadID);
340 DWORD WINAPI init_thread(LPVOID threadID);
350 /// init_threads(), exit_threads() and nodes_searched() are helpers to
351 /// give accessibility to some TM methods from outside of current file.
353 void init_threads() { ThreadsMgr.init_threads(); }
354 void exit_threads() { ThreadsMgr.exit_threads(); }
357 /// init_search() is called during startup. It initializes various lookup tables
361 int d; // depth (ONE_PLY == 2)
362 int hd; // half depth (ONE_PLY == 1)
365 // Init reductions array
366 for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
368 double pvRed = log(double(hd)) * log(double(mc)) / 3.0;
369 double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
370 ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0);
371 ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0);
374 // Init futility margins array
375 for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
376 FutilityMarginsMatrix[d][mc] = Value(112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45);
378 // Init futility move count array
379 for (d = 0; d < 32; d++)
380 FutilityMoveCountArray[d] = int(3.001 + 0.25 * pow(d, 2.0));
384 /// perft() is our utility to verify move generation is bug free. All the legal
385 /// moves up to given depth are generated and counted and the sum returned.
387 int perft(Position& pos, Depth depth)
389 MoveStack mlist[MOVES_MAX];
394 // Generate all legal moves
395 MoveStack* last = generate_moves(pos, mlist);
397 // If we are at the last ply we don't need to do and undo
398 // the moves, just to count them.
399 if (depth <= ONE_PLY)
400 return int(last - mlist);
402 // Loop through all legal moves
404 for (MoveStack* cur = mlist; cur != last; cur++)
407 pos.do_move(m, st, ci, pos.move_is_check(m, ci));
408 sum += perft(pos, depth - ONE_PLY);
415 /// think() is the external interface to Stockfish's search, and is called when
416 /// the program receives the UCI 'go' command. It initializes various
417 /// search-related global variables, and calls root_search(). It returns false
418 /// when a quit command is received during the search.
420 bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[],
421 int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) {
423 // Initialize global search variables
424 StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
426 SearchStartTime = get_system_time();
427 ExactMaxTime = maxTime;
430 InfiniteSearch = infinite;
431 PonderSearch = ponder;
432 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
434 // Look for a book move, only during games, not tests
435 if (UseTimeManagement && Options["OwnBook"].value<bool>())
437 if (Options["Book File"].value<std::string>() != OpeningBook.file_name())
438 OpeningBook.open(Options["Book File"].value<std::string>());
440 Move bookMove = OpeningBook.get_move(pos, Options["Best Book Move"].value<bool>());
441 if (bookMove != MOVE_NONE)
444 wait_for_stop_or_ponderhit();
446 cout << "bestmove " << bookMove << endl;
451 // Read UCI option values
452 TT.set_size(Options["Hash"].value<int>());
453 if (Options["Clear Hash"].value<bool>())
455 Options["Clear Hash"].set_value("false");
459 CheckExtension[1] = Options["Check Extension (PV nodes)"].value<Depth>();
460 CheckExtension[0] = Options["Check Extension (non-PV nodes)"].value<Depth>();
461 SingleEvasionExtension[1] = Options["Single Evasion Extension (PV nodes)"].value<Depth>();
462 SingleEvasionExtension[0] = Options["Single Evasion Extension (non-PV nodes)"].value<Depth>();
463 PawnPushTo7thExtension[1] = Options["Pawn Push to 7th Extension (PV nodes)"].value<Depth>();
464 PawnPushTo7thExtension[0] = Options["Pawn Push to 7th Extension (non-PV nodes)"].value<Depth>();
465 PassedPawnExtension[1] = Options["Passed Pawn Extension (PV nodes)"].value<Depth>();
466 PassedPawnExtension[0] = Options["Passed Pawn Extension (non-PV nodes)"].value<Depth>();
467 PawnEndgameExtension[1] = Options["Pawn Endgame Extension (PV nodes)"].value<Depth>();
468 PawnEndgameExtension[0] = Options["Pawn Endgame Extension (non-PV nodes)"].value<Depth>();
469 MateThreatExtension[1] = Options["Mate Threat Extension (PV nodes)"].value<Depth>();
470 MateThreatExtension[0] = Options["Mate Threat Extension (non-PV nodes)"].value<Depth>();
471 MultiPV = Options["MultiPV"].value<int>();
472 UseLogFile = Options["Use Search Log"].value<bool>();
475 LogFile.open(Options["Search Log Filename"].value<std::string>().c_str(), std::ios::out | std::ios::app);
477 read_weights(pos.side_to_move());
479 // Set the number of active threads
480 ThreadsMgr.read_uci_options();
481 init_eval(ThreadsMgr.active_threads());
483 // Wake up needed threads
484 for (int i = 1; i < ThreadsMgr.active_threads(); i++)
485 ThreadsMgr.wake_sleeping_thread(i);
488 int myTime = time[pos.side_to_move()];
489 int myIncrement = increment[pos.side_to_move()];
490 if (UseTimeManagement)
491 TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter());
493 // Set best NodesBetweenPolls interval to avoid lagging under
494 // heavy time pressure.
496 NodesBetweenPolls = Min(MaxNodes, 30000);
497 else if (myTime && myTime < 1000)
498 NodesBetweenPolls = 1000;
499 else if (myTime && myTime < 5000)
500 NodesBetweenPolls = 5000;
502 NodesBetweenPolls = 30000;
504 // Write search information to log file
506 LogFile << "Searching: " << pos.to_fen() << endl
507 << "infinite: " << infinite
508 << " ponder: " << ponder
509 << " time: " << myTime
510 << " increment: " << myIncrement
511 << " moves to go: " << movesToGo << endl;
513 // We're ready to start thinking. Call the iterative deepening loop function
514 id_loop(pos, searchMoves);
519 // This makes all the threads to go to sleep
520 ThreadsMgr.set_active_threads(1);
528 // id_loop() is the main iterative deepening loop. It calls root_search
529 // repeatedly with increasing depth until the allocated thinking time has
530 // been consumed, the user stops the search, or the maximum search depth is
533 Value id_loop(Position& pos, Move searchMoves[]) {
535 SearchStack ss[PLY_MAX_PLUS_2];
536 Move EasyMove = MOVE_NONE;
537 Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
539 // Moves to search are verified, copied, scored and sorted
540 RootMoveList rml(pos, searchMoves);
542 // Handle special case of searching on a mate/stale position
546 wait_for_stop_or_ponderhit();
548 return pos.is_check() ? -VALUE_MATE : VALUE_DRAW;
551 // Print RootMoveList startup scoring to the standard output,
552 // so to output information also for iteration 1.
553 cout << set960(pos.is_chess960()) // Is enough to set once at the beginning
554 << "info depth " << 1
555 << "\ninfo depth " << 1
556 << " score " << value_to_uci(rml[0].pv_score)
557 << " time " << current_search_time()
558 << " nodes " << pos.nodes_searched()
559 << " nps " << nps(pos)
560 << " pv " << rml[0].pv[0] << "\n";
565 init_ss_array(ss, PLY_MAX_PLUS_2);
566 ValueByIteration[1] = rml[0].pv_score;
569 // Is one move significantly better than others after initial scoring ?
571 || rml[0].pv_score > rml[1].pv_score + EasyMoveMargin)
572 EasyMove = rml[0].pv[0];
574 // Iterative deepening loop
575 while (Iteration < PLY_MAX)
577 // Initialize iteration
579 BestMoveChangesByIteration[Iteration] = 0;
581 cout << "info depth " << Iteration << endl;
583 // Calculate dynamic aspiration window based on previous iterations
584 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
586 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
587 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
589 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
590 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
592 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
593 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
596 // Search to the current depth, rml is updated and sorted, alpha and beta could change
597 value = root_search(pos, ss, rml, &alpha, &beta);
600 break; // Value cannot be trusted. Break out immediately!
602 //Save info about search result
603 ValueByIteration[Iteration] = value;
605 // Drop the easy move if differs from the new best move
606 if (rml[0].pv[0] != EasyMove)
607 EasyMove = MOVE_NONE;
609 if (UseTimeManagement)
612 bool stopSearch = false;
614 // Stop search early if there is only a single legal move,
615 // we search up to Iteration 6 anyway to get a proper score.
616 if (Iteration >= 6 && rml.size() == 1)
619 // Stop search early when the last two iterations returned a mate score
621 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
622 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
625 // Stop search early if one move seems to be much better than the others
627 && EasyMove == rml[0].pv[0]
628 && ( ( rml[0].nodes > (pos.nodes_searched() * 85) / 100
629 && current_search_time() > TimeMgr.available_time() / 16)
630 ||( rml[0].nodes > (pos.nodes_searched() * 98) / 100
631 && current_search_time() > TimeMgr.available_time() / 32)))
634 // Add some extra time if the best move has changed during the last two iterations
635 if (Iteration > 5 && Iteration <= 50)
636 TimeMgr.pv_instability(BestMoveChangesByIteration[Iteration],
637 BestMoveChangesByIteration[Iteration-1]);
639 // Stop search if most of MaxSearchTime is consumed at the end of the
640 // iteration. We probably don't have enough time to search the first
641 // move at the next iteration anyway.
642 if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
648 StopOnPonderhit = true;
654 if (MaxDepth && Iteration >= MaxDepth)
658 // If we are pondering or in infinite search, we shouldn't print the
659 // best move before we are told to do so.
660 if (!AbortSearch && (PonderSearch || InfiniteSearch))
661 wait_for_stop_or_ponderhit();
663 // Print final search statistics
664 cout << "info nodes " << pos.nodes_searched()
665 << " nps " << nps(pos)
666 << " time " << current_search_time() << endl;
668 // Print the best move and the ponder move to the standard output
669 cout << "bestmove " << rml[0].pv[0];
671 if (rml[0].pv[1] != MOVE_NONE)
672 cout << " ponder " << rml[0].pv[1];
679 dbg_print_mean(LogFile);
681 if (dbg_show_hit_rate)
682 dbg_print_hit_rate(LogFile);
684 LogFile << "\nNodes: " << pos.nodes_searched()
685 << "\nNodes/second: " << nps(pos)
686 << "\nBest move: " << move_to_san(pos, rml[0].pv[0]);
689 pos.do_move(rml[0].pv[0], st);
690 LogFile << "\nPonder move: "
691 << move_to_san(pos, rml[0].pv[1]) // Works also with MOVE_NONE
694 return rml[0].pv_score;
698 // root_search() is the function which searches the root node. It is
699 // similar to search_pv except that it uses a different move ordering
700 // scheme, prints some information to the standard output and handles
701 // the fail low/high loops.
703 Value root_search(Position& pos, SearchStack* ss, RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
709 Depth depth, ext, newDepth;
710 Value value, alpha, beta;
711 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
712 int researchCountFH, researchCountFL;
714 researchCountFH = researchCountFL = 0;
717 isCheck = pos.is_check();
718 depth = (Iteration - 2) * ONE_PLY + InitialDepth;
720 // Step 1. Initialize node (polling is omitted at root)
721 ss->currentMove = ss->bestMove = MOVE_NONE;
723 // Step 2. Check for aborted search (omitted at root)
724 // Step 3. Mate distance pruning (omitted at root)
725 // Step 4. Transposition table lookup (omitted at root)
727 // Step 5. Evaluate the position statically
728 // At root we do this only to get reference value for child nodes
729 ss->evalMargin = VALUE_NONE;
730 ss->eval = isCheck ? VALUE_NONE : evaluate(pos, ss->evalMargin);
732 // Step 6. Razoring (omitted at root)
733 // Step 7. Static null move pruning (omitted at root)
734 // Step 8. Null move search with verification search (omitted at root)
735 // Step 9. Internal iterative deepening (omitted at root)
737 // Step extra. Fail low loop
738 // We start with small aspiration window and in case of fail low, we research
739 // with bigger window until we are not failing low anymore.
742 // Sort the moves before to (re)search
743 rml.set_non_pv_scores(pos);
746 // Step 10. Loop through all moves in the root move list
747 for (int i = 0; i < (int)rml.size() && !AbortSearch; i++)
749 // This is used by time management
750 FirstRootMove = (i == 0);
752 // Save the current node count before the move is searched
753 nodes = pos.nodes_searched();
755 // Pick the next root move, and print the move and the move number to
756 // the standard output.
757 move = ss->currentMove = rml[i].pv[0];
759 if (current_search_time() >= 1000)
760 cout << "info currmove " << move
761 << " currmovenumber " << i + 1 << endl;
763 moveIsCheck = pos.move_is_check(move);
764 captureOrPromotion = pos.move_is_capture_or_promotion(move);
766 // Step 11. Decide the new search depth
767 ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
768 newDepth = depth + ext;
770 // Step 12. Futility pruning (omitted at root)
772 // Step extra. Fail high loop
773 // If move fails high, we research with bigger window until we are not failing
775 value = -VALUE_INFINITE;
779 // Step 13. Make the move
780 pos.do_move(move, st, ci, moveIsCheck);
782 // Step extra. pv search
783 // We do pv search for first moves (i < MultiPV)
784 // and for fail high research (value > alpha)
785 if (i < MultiPV || value > alpha)
787 // Aspiration window is disabled in multi-pv case
789 alpha = -VALUE_INFINITE;
791 // Full depth PV search, done on first move or after a fail high
792 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
796 // Step 14. Reduced search
797 // if the move fails high will be re-searched at full depth
798 bool doFullDepthSearch = true;
800 if ( depth >= 3 * ONE_PLY
802 && !captureOrPromotion
803 && !move_is_castle(move))
805 ss->reduction = reduction<PV>(depth, i - MultiPV + 2);
808 assert(newDepth-ss->reduction >= ONE_PLY);
810 // Reduced depth non-pv search using alpha as upperbound
811 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
812 doFullDepthSearch = (value > alpha);
814 ss->reduction = DEPTH_ZERO; // Restore original reduction
817 // Step 15. Full depth search
818 if (doFullDepthSearch)
820 // Full depth non-pv search using alpha as upperbound
821 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, 1);
823 // If we are above alpha then research at same depth but as PV
824 // to get a correct score or eventually a fail high above beta.
826 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
830 // Step 16. Undo move
833 // Can we exit fail high loop ?
834 if (AbortSearch || value < beta)
837 // We are failing high and going to do a research. It's important to update
838 // the score before research in case we run out of time while researching.
839 rml[i].pv_score = value;
841 extract_pv_from_tt(pos, move, rml[i].pv);
843 // Print information to the standard output
844 print_pv_info(pos, rml[i].pv, alpha, beta, value);
846 // Prepare for a research after a fail high, each time with a wider window
847 *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
850 } // End of fail high loop
852 // Finished searching the move. If AbortSearch is true, the search
853 // was aborted because the user interrupted the search or because we
854 // ran out of time. In this case, the return value of the search cannot
855 // be trusted, and we break out of the loop without updating the best
860 // Remember searched nodes counts for this move
861 rml[i].nodes += pos.nodes_searched() - nodes;
863 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
864 assert(value < beta);
866 // Step 17. Check for new best move
867 if (value <= alpha && i >= MultiPV)
868 rml[i].pv_score = -VALUE_INFINITE;
871 // PV move or new best move!
874 rml[i].pv_score = value;
876 extract_pv_from_tt(pos, move, rml[i].pv);
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.
884 BestMoveChangesByIteration[Iteration]++;
886 // Print information to the standard output
887 print_pv_info(pos, rml[i].pv, alpha, beta, value);
889 // Raise alpha to setup proper non-pv search upper bound
896 for (int j = 0; j < Min(MultiPV, (int)rml.size()); j++)
898 cout << "info multipv " << j + 1
899 << " score " << value_to_uci(rml[j].pv_score)
900 << " depth " << (j <= i ? Iteration : Iteration - 1)
901 << " time " << current_search_time()
902 << " nodes " << pos.nodes_searched()
903 << " nps " << nps(pos)
906 for (int k = 0; rml[j].pv[k] != MOVE_NONE && k < PLY_MAX; k++)
907 cout << rml[j].pv[k] << " ";
911 alpha = rml[Min(i, MultiPV - 1)].pv_score;
913 } // PV move or new best move
915 assert(alpha >= *alphaPtr);
917 AspirationFailLow = (alpha == *alphaPtr);
919 if (AspirationFailLow && StopOnPonderhit)
920 StopOnPonderhit = false;
923 // Can we exit fail low loop ?
924 if (AbortSearch || !AspirationFailLow)
927 // Prepare for a research after a fail low, each time with a wider window
928 *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
933 // Sort the moves before to return
936 // Write PV to transposition table, in case the relevant entries have
937 // been overwritten during the search.
938 insert_pv_in_tt(pos, rml[0].pv);
944 // search<>() is the main search function for both PV and non-PV nodes and for
945 // normal and SplitPoint nodes. When called just after a split point the search
946 // is simpler because we have already probed the hash table, done a null move
947 // search, and searched the first move before splitting, we don't have to repeat
948 // all this work again. We also don't need to store anything to the hash table
949 // here: This is taken care of after we return from the split point.
951 template <NodeType PvNode, bool SpNode>
952 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
954 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
955 assert(beta > alpha && beta <= VALUE_INFINITE);
956 assert(PvNode || alpha == beta - 1);
957 assert(ply > 0 && ply < PLY_MAX);
958 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
960 Move movesSearched[MOVES_MAX];
964 Move ttMove, move, excludedMove, threatMove;
967 Value bestValue, value, oldAlpha;
968 Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
969 bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
970 bool mateThreat = false;
972 int threadID = pos.thread();
973 SplitPoint* sp = NULL;
974 refinedValue = bestValue = value = -VALUE_INFINITE;
976 isCheck = pos.is_check();
982 ttMove = excludedMove = MOVE_NONE;
983 threatMove = sp->threatMove;
984 mateThreat = sp->mateThreat;
985 goto split_point_start;
987 else {} // Hack to fix icc's "statement is unreachable" warning
989 // Step 1. Initialize node and poll. Polling can abort search
990 ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
991 (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
993 if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
999 // Step 2. Check for aborted search and immediate draw
1001 || ThreadsMgr.cutoff_at_splitpoint(threadID)
1003 || ply >= PLY_MAX - 1)
1006 // Step 3. Mate distance pruning
1007 alpha = Max(value_mated_in(ply), alpha);
1008 beta = Min(value_mate_in(ply+1), beta);
1012 // Step 4. Transposition table lookup
1014 // We don't want the score of a partial search to overwrite a previous full search
1015 // TT value, so we use a different position key in case of an excluded move exists.
1016 excludedMove = ss->excludedMove;
1017 posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1019 tte = TT.retrieve(posKey);
1020 ttMove = tte ? tte->move() : MOVE_NONE;
1022 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1023 // This is to avoid problems in the following areas:
1025 // * Repetition draw detection
1026 // * Fifty move rule detection
1027 // * Searching for a mate
1028 // * Printing of full PV line
1029 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1032 ss->bestMove = ttMove; // Can be MOVE_NONE
1033 return value_from_tt(tte->value(), ply);
1036 // Step 5. Evaluate the position statically and
1037 // update gain statistics of parent move.
1039 ss->eval = ss->evalMargin = VALUE_NONE;
1042 assert(tte->static_value() != VALUE_NONE);
1044 ss->eval = tte->static_value();
1045 ss->evalMargin = tte->static_value_margin();
1046 refinedValue = refine_eval(tte, ss->eval, ply);
1050 refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
1051 TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
1054 // Save gain for the parent non-capture move
1055 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1057 // Step 6. Razoring (is omitted in PV nodes)
1059 && depth < RazorDepth
1061 && refinedValue < beta - razor_margin(depth)
1062 && ttMove == MOVE_NONE
1063 && !value_is_mate(beta)
1064 && !pos.has_pawn_on_7th(pos.side_to_move()))
1066 Value rbeta = beta - razor_margin(depth);
1067 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply);
1069 // Logically we should return (v + razor_margin(depth)), but
1070 // surprisingly this did slightly weaker in tests.
1074 // Step 7. Static null move pruning (is omitted in PV nodes)
1075 // We're betting that the opponent doesn't have a move that will reduce
1076 // the score by more than futility_margin(depth) if we do a null move.
1078 && !ss->skipNullMove
1079 && depth < RazorDepth
1081 && refinedValue >= beta + futility_margin(depth, 0)
1082 && !value_is_mate(beta)
1083 && pos.non_pawn_material(pos.side_to_move()))
1084 return refinedValue - futility_margin(depth, 0);
1086 // Step 8. Null move search with verification search (is omitted in PV nodes)
1088 && !ss->skipNullMove
1091 && refinedValue >= beta
1092 && !value_is_mate(beta)
1093 && pos.non_pawn_material(pos.side_to_move()))
1095 ss->currentMove = MOVE_NULL;
1097 // Null move dynamic reduction based on depth
1098 int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
1100 // Null move dynamic reduction based on value
1101 if (refinedValue - beta > PawnValueMidgame)
1104 pos.do_null_move(st);
1105 (ss+1)->skipNullMove = true;
1106 nullValue = -search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1);
1107 (ss+1)->skipNullMove = false;
1108 pos.undo_null_move();
1110 if (nullValue >= beta)
1112 // Do not return unproven mate scores
1113 if (nullValue >= value_mate_in(PLY_MAX))
1116 if (depth < 6 * ONE_PLY)
1119 // Do verification search at high depths
1120 ss->skipNullMove = true;
1121 Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY, ply);
1122 ss->skipNullMove = false;
1129 // The null move failed low, which means that we may be faced with
1130 // some kind of threat. If the previous move was reduced, check if
1131 // the move that refuted the null move was somehow connected to the
1132 // move which was reduced. If a connection is found, return a fail
1133 // low score (which will cause the reduced move to fail high in the
1134 // parent node, which will trigger a re-search with full depth).
1135 if (nullValue == value_mated_in(ply + 2))
1138 threatMove = (ss+1)->bestMove;
1139 if ( depth < ThreatDepth
1140 && (ss-1)->reduction
1141 && threatMove != MOVE_NONE
1142 && connected_moves(pos, (ss-1)->currentMove, threatMove))
1147 // Step 9. Internal iterative deepening
1148 if ( depth >= IIDDepth[PvNode]
1149 && ttMove == MOVE_NONE
1150 && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
1152 Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
1154 ss->skipNullMove = true;
1155 search<PvNode>(pos, ss, alpha, beta, d, ply);
1156 ss->skipNullMove = false;
1158 ttMove = ss->bestMove;
1159 tte = TT.retrieve(posKey);
1162 // Expensive mate threat detection (only for PV nodes)
1164 mateThreat = pos.has_mate_threat();
1166 split_point_start: // At split points actual search starts from here
1168 // Initialize a MovePicker object for the current position
1169 // FIXME currently MovePicker() c'tor is needless called also in SplitPoint
1170 MovePicker mpBase(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
1171 MovePicker& mp = SpNode ? *sp->mp : mpBase;
1173 ss->bestMove = MOVE_NONE;
1174 singleEvasion = !SpNode && isCheck && mp.number_of_evasions() == 1;
1175 futilityBase = ss->eval + ss->evalMargin;
1176 singularExtensionNode = !SpNode
1177 && depth >= SingularExtensionDepth[PvNode]
1180 && !excludedMove // Do not allow recursive singular extension search
1181 && (tte->type() & VALUE_TYPE_LOWER)
1182 && tte->depth() >= depth - 3 * ONE_PLY;
1185 lock_grab(&(sp->lock));
1186 bestValue = sp->bestValue;
1189 // Step 10. Loop through moves
1190 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1191 while ( bestValue < beta
1192 && (move = mp.get_next_move()) != MOVE_NONE
1193 && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1195 assert(move_is_ok(move));
1199 moveCount = ++sp->moveCount;
1200 lock_release(&(sp->lock));
1202 else if (move == excludedMove)
1205 movesSearched[moveCount++] = move;
1207 moveIsCheck = pos.move_is_check(move, ci);
1208 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1210 // Step 11. Decide the new search depth
1211 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1213 // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s),
1214 // and just one fails high on (alpha, beta), then that move is singular and should be extended.
1215 // To verify this we do a reduced search on all the other moves but the ttMove, if result is
1216 // lower then ttValue minus a margin then we extend ttMove.
1217 if ( singularExtensionNode
1218 && move == tte->move()
1221 Value ttValue = value_from_tt(tte->value(), ply);
1223 if (abs(ttValue) < VALUE_KNOWN_WIN)
1225 Value b = ttValue - SingularExtensionMargin;
1226 ss->excludedMove = move;
1227 ss->skipNullMove = true;
1228 Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
1229 ss->skipNullMove = false;
1230 ss->excludedMove = MOVE_NONE;
1231 ss->bestMove = MOVE_NONE;
1237 // Update current move (this must be done after singular extension search)
1238 ss->currentMove = move;
1239 newDepth = depth - ONE_PLY + ext;
1241 // Step 12. Futility pruning (is omitted in PV nodes)
1243 && !captureOrPromotion
1247 && !move_is_castle(move))
1249 // Move count based pruning
1250 if ( moveCount >= futility_move_count(depth)
1251 && !(threatMove && connected_threat(pos, move, threatMove))
1252 && bestValue > value_mated_in(PLY_MAX)) // FIXME bestValue is racy
1255 lock_grab(&(sp->lock));
1260 // Value based pruning
1261 // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
1262 // but fixing this made program slightly weaker.
1263 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1264 futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount)
1265 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1267 if (futilityValueScaled < beta)
1271 lock_grab(&(sp->lock));
1272 if (futilityValueScaled > sp->bestValue)
1273 sp->bestValue = bestValue = futilityValueScaled;
1275 else if (futilityValueScaled > bestValue)
1276 bestValue = futilityValueScaled;
1281 // Prune moves with negative SEE at low depths
1282 if ( predictedDepth < 2 * ONE_PLY
1283 && bestValue > value_mated_in(PLY_MAX)
1284 && pos.see_sign(move) < 0)
1287 lock_grab(&(sp->lock));
1293 // Step 13. Make the move
1294 pos.do_move(move, st, ci, moveIsCheck);
1296 // Step extra. pv search (only in PV nodes)
1297 // The first move in list is the expected PV
1298 if (PvNode && moveCount == 1)
1299 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1302 // Step 14. Reduced depth search
1303 // If the move fails high will be re-searched at full depth.
1304 bool doFullDepthSearch = true;
1306 if ( depth >= 3 * ONE_PLY
1307 && !captureOrPromotion
1309 && !move_is_castle(move)
1310 && ss->killers[0] != move
1311 && ss->killers[1] != move)
1313 ss->reduction = reduction<PvNode>(depth, moveCount);
1317 alpha = SpNode ? sp->alpha : alpha;
1318 Depth d = newDepth - ss->reduction;
1319 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1321 doFullDepthSearch = (value > alpha);
1323 ss->reduction = DEPTH_ZERO; // Restore original reduction
1326 // Step 15. Full depth search
1327 if (doFullDepthSearch)
1329 alpha = SpNode ? sp->alpha : alpha;
1330 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1332 // Step extra. pv search (only in PV nodes)
1333 // Search only for possible new PV nodes, if instead value >= beta then
1334 // parent node fails low with value <= alpha and tries another move.
1335 if (PvNode && value > alpha && value < beta)
1336 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1340 // Step 16. Undo move
1341 pos.undo_move(move);
1343 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1345 // Step 17. Check for new best move
1348 lock_grab(&(sp->lock));
1349 bestValue = sp->bestValue;
1353 if (value > bestValue && !(SpNode && ThreadsMgr.cutoff_at_splitpoint(threadID)))
1358 sp->bestValue = value;
1362 if (PvNode && value < beta) // We want always alpha < beta
1370 sp->betaCutoff = true;
1372 if (value == value_mate_in(ply + 1))
1373 ss->mateKiller = move;
1375 ss->bestMove = move;
1378 sp->parentSstack->bestMove = move;
1382 // Step 18. Check for split
1384 && depth >= ThreadsMgr.min_split_depth()
1385 && ThreadsMgr.active_threads() > 1
1387 && ThreadsMgr.available_thread_exists(threadID)
1389 && !ThreadsMgr.cutoff_at_splitpoint(threadID)
1391 ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1392 threatMove, mateThreat, moveCount, &mp, PvNode);
1395 // Step 19. Check for mate and stalemate
1396 // All legal moves have been searched and if there are
1397 // no legal moves, it must be mate or stalemate.
1398 // If one move was excluded return fail low score.
1399 if (!SpNode && !moveCount)
1400 return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW;
1402 // Step 20. Update tables
1403 // If the search is not aborted, update the transposition table,
1404 // history counters, and killer moves.
1405 if (!SpNode && !AbortSearch && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1407 move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
1408 vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
1409 : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
1411 TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, ss->evalMargin);
1413 // Update killers and history only for non capture moves that fails high
1414 if ( bestValue >= beta
1415 && !pos.move_is_capture_or_promotion(move))
1417 update_history(pos, move, depth, movesSearched, moveCount);
1418 update_killers(move, ss);
1424 // Here we have the lock still grabbed
1425 sp->slaves[threadID] = 0;
1426 sp->nodes += pos.nodes_searched();
1427 lock_release(&(sp->lock));
1430 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1435 // qsearch() is the quiescence search function, which is called by the main
1436 // search function when the remaining depth is zero (or, to be more precise,
1437 // less than ONE_PLY).
1439 template <NodeType PvNode>
1440 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1442 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1443 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1444 assert(PvNode || alpha == beta - 1);
1446 assert(ply > 0 && ply < PLY_MAX);
1447 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1451 Value bestValue, value, evalMargin, futilityValue, futilityBase;
1452 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1455 Value oldAlpha = alpha;
1457 ss->bestMove = ss->currentMove = MOVE_NONE;
1459 // Check for an instant draw or maximum ply reached
1460 if (pos.is_draw() || ply >= PLY_MAX - 1)
1463 // Decide whether or not to include checks, this fixes also the type of
1464 // TT entry depth that we are going to use. Note that in qsearch we use
1465 // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
1466 isCheck = pos.is_check();
1467 ttDepth = (isCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS);
1469 // Transposition table lookup. At PV nodes, we don't use the TT for
1470 // pruning, but only for move ordering.
1471 tte = TT.retrieve(pos.get_key());
1472 ttMove = (tte ? tte->move() : MOVE_NONE);
1474 if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ply))
1476 ss->bestMove = ttMove; // Can be MOVE_NONE
1477 return value_from_tt(tte->value(), ply);
1480 // Evaluate the position statically
1483 bestValue = futilityBase = -VALUE_INFINITE;
1484 ss->eval = evalMargin = VALUE_NONE;
1485 enoughMaterial = false;
1491 assert(tte->static_value() != VALUE_NONE);
1493 evalMargin = tte->static_value_margin();
1494 ss->eval = bestValue = tte->static_value();
1497 ss->eval = bestValue = evaluate(pos, evalMargin);
1499 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1501 // Stand pat. Return immediately if static value is at least beta
1502 if (bestValue >= beta)
1505 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1510 if (PvNode && bestValue > alpha)
1513 // Futility pruning parameters, not needed when in check
1514 futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1515 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1518 // Initialize a MovePicker object for the current position, and prepare
1519 // to search the moves. Because the depth is <= 0 here, only captures,
1520 // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
1522 MovePicker mp(pos, ttMove, depth, H);
1525 // Loop through the moves until no moves remain or a beta cutoff occurs
1526 while ( alpha < beta
1527 && (move = mp.get_next_move()) != MOVE_NONE)
1529 assert(move_is_ok(move));
1531 moveIsCheck = pos.move_is_check(move, ci);
1539 && !move_is_promotion(move)
1540 && !pos.move_is_passed_pawn_push(move))
1542 futilityValue = futilityBase
1543 + pos.endgame_value_of_piece_on(move_to(move))
1544 + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1546 if (futilityValue < alpha)
1548 if (futilityValue > bestValue)
1549 bestValue = futilityValue;
1554 // Detect non-capture evasions that are candidate to be pruned
1555 evasionPrunable = isCheck
1556 && bestValue > value_mated_in(PLY_MAX)
1557 && !pos.move_is_capture(move)
1558 && !pos.can_castle(pos.side_to_move());
1560 // Don't search moves with negative SEE values
1562 && (!isCheck || evasionPrunable)
1564 && !move_is_promotion(move)
1565 && pos.see_sign(move) < 0)
1568 // Don't search useless checks
1573 && !pos.move_is_capture_or_promotion(move)
1574 && ss->eval + PawnValueMidgame / 4 < beta
1575 && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue))
1577 if (ss->eval + PawnValueMidgame / 4 > bestValue)
1578 bestValue = ss->eval + PawnValueMidgame / 4;
1583 // Update current move
1584 ss->currentMove = move;
1586 // Make and search the move
1587 pos.do_move(move, st, ci, moveIsCheck);
1588 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1);
1589 pos.undo_move(move);
1591 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1594 if (value > bestValue)
1600 ss->bestMove = move;
1605 // All legal moves have been searched. A special case: If we're in check
1606 // and no legal moves were found, it is checkmate.
1607 if (isCheck && bestValue == -VALUE_INFINITE)
1608 return value_mated_in(ply);
1610 // Update transposition table
1611 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1612 TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin);
1614 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1620 // check_is_dangerous() tests if a checking move can be pruned in qsearch().
1621 // bestValue is updated only when returning false because in that case move
1624 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bestValue)
1626 Bitboard b, occ, oldAtt, newAtt, kingAtt;
1627 Square from, to, ksq, victimSq;
1630 Value futilityValue, bv = *bestValue;
1632 from = move_from(move);
1634 them = opposite_color(pos.side_to_move());
1635 ksq = pos.king_square(them);
1636 kingAtt = pos.attacks_from<KING>(ksq);
1637 pc = pos.piece_on(from);
1639 occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL << ksq);
1640 oldAtt = pos.attacks_from(pc, from, occ);
1641 newAtt = pos.attacks_from(pc, to, occ);
1643 // Rule 1. Checks which give opponent's king at most one escape square are dangerous
1644 b = kingAtt & ~pos.pieces_of_color(them) & ~newAtt & ~(1ULL << to);
1646 if (!(b && (b & (b - 1))))
1649 // Rule 2. Queen contact check is very dangerous
1650 if ( type_of_piece(pc) == QUEEN
1651 && bit_is_set(kingAtt, to))
1654 // Rule 3. Creating new double threats with checks
1655 b = pos.pieces_of_color(them) & newAtt & ~oldAtt & ~(1ULL << ksq);
1659 victimSq = pop_1st_bit(&b);
1660 futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq);
1662 // Note that here we generate illegal "double move"!
1663 if ( futilityValue >= beta
1664 && pos.see_sign(make_move(from, victimSq)) >= 0)
1667 if (futilityValue > bv)
1671 // Update bestValue only if check is not dangerous (because we will prune the move)
1677 // connected_moves() tests whether two moves are 'connected' in the sense
1678 // that the first move somehow made the second move possible (for instance
1679 // if the moving piece is the same in both moves). The first move is assumed
1680 // to be the move that was made to reach the current position, while the
1681 // second move is assumed to be a move from the current position.
1683 bool connected_moves(const Position& pos, Move m1, Move m2) {
1685 Square f1, t1, f2, t2;
1688 assert(m1 && move_is_ok(m1));
1689 assert(m2 && move_is_ok(m2));
1691 // Case 1: The moving piece is the same in both moves
1697 // Case 2: The destination square for m2 was vacated by m1
1703 // Case 3: Moving through the vacated square
1704 if ( piece_is_slider(pos.piece_on(f2))
1705 && bit_is_set(squares_between(f2, t2), f1))
1708 // Case 4: The destination square for m2 is defended by the moving piece in m1
1709 p = pos.piece_on(t1);
1710 if (bit_is_set(pos.attacks_from(p, t1), t2))
1713 // Case 5: Discovered check, checking piece is the piece moved in m1
1714 if ( piece_is_slider(p)
1715 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1716 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1718 // discovered_check_candidates() works also if the Position's side to
1719 // move is the opposite of the checking piece.
1720 Color them = opposite_color(pos.side_to_move());
1721 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1723 if (bit_is_set(dcCandidates, f2))
1730 // value_is_mate() checks if the given value is a mate one eventually
1731 // compensated for the ply.
1733 bool value_is_mate(Value value) {
1735 assert(abs(value) <= VALUE_INFINITE);
1737 return value <= value_mated_in(PLY_MAX)
1738 || value >= value_mate_in(PLY_MAX);
1742 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1743 // "plies to mate from the current ply". Non-mate scores are unchanged.
1744 // The function is called before storing a value to the transposition table.
1746 Value value_to_tt(Value v, int ply) {
1748 if (v >= value_mate_in(PLY_MAX))
1751 if (v <= value_mated_in(PLY_MAX))
1758 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1759 // the transposition table to a mate score corrected for the current ply.
1761 Value value_from_tt(Value v, int ply) {
1763 if (v >= value_mate_in(PLY_MAX))
1766 if (v <= value_mated_in(PLY_MAX))
1773 // extension() decides whether a move should be searched with normal depth,
1774 // or with extended depth. Certain classes of moves (checking moves, in
1775 // particular) are searched with bigger depth than ordinary moves and in
1776 // any case are marked as 'dangerous'. Note that also if a move is not
1777 // extended, as example because the corresponding UCI option is set to zero,
1778 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1779 template <NodeType PvNode>
1780 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1781 bool singleEvasion, bool mateThreat, bool* dangerous) {
1783 assert(m != MOVE_NONE);
1785 Depth result = DEPTH_ZERO;
1786 *dangerous = moveIsCheck | singleEvasion | mateThreat;
1790 if (moveIsCheck && pos.see_sign(m) >= 0)
1791 result += CheckExtension[PvNode];
1794 result += SingleEvasionExtension[PvNode];
1797 result += MateThreatExtension[PvNode];
1800 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1802 Color c = pos.side_to_move();
1803 if (relative_rank(c, move_to(m)) == RANK_7)
1805 result += PawnPushTo7thExtension[PvNode];
1808 if (pos.pawn_is_passed(c, move_to(m)))
1810 result += PassedPawnExtension[PvNode];
1815 if ( captureOrPromotion
1816 && pos.type_of_piece_on(move_to(m)) != PAWN
1817 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1818 - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1819 && !move_is_promotion(m)
1822 result += PawnEndgameExtension[PvNode];
1827 && captureOrPromotion
1828 && pos.type_of_piece_on(move_to(m)) != PAWN
1829 && pos.see_sign(m) >= 0)
1831 result += ONE_PLY / 2;
1835 return Min(result, ONE_PLY);
1839 // connected_threat() tests whether it is safe to forward prune a move or if
1840 // is somehow coonected to the threat move returned by null search.
1842 bool connected_threat(const Position& pos, Move m, Move threat) {
1844 assert(move_is_ok(m));
1845 assert(threat && move_is_ok(threat));
1846 assert(!pos.move_is_check(m));
1847 assert(!pos.move_is_capture_or_promotion(m));
1848 assert(!pos.move_is_passed_pawn_push(m));
1850 Square mfrom, mto, tfrom, tto;
1852 mfrom = move_from(m);
1854 tfrom = move_from(threat);
1855 tto = move_to(threat);
1857 // Case 1: Don't prune moves which move the threatened piece
1861 // Case 2: If the threatened piece has value less than or equal to the
1862 // value of the threatening piece, don't prune move which defend it.
1863 if ( pos.move_is_capture(threat)
1864 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1865 || pos.type_of_piece_on(tfrom) == KING)
1866 && pos.move_attacks_square(m, tto))
1869 // Case 3: If the moving piece in the threatened move is a slider, don't
1870 // prune safe moves which block its ray.
1871 if ( piece_is_slider(pos.piece_on(tfrom))
1872 && bit_is_set(squares_between(tfrom, tto), mto)
1873 && pos.see_sign(m) >= 0)
1880 // ok_to_use_TT() returns true if a transposition table score
1881 // can be used at a given point in search.
1883 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1885 Value v = value_from_tt(tte->value(), ply);
1887 return ( tte->depth() >= depth
1888 || v >= Max(value_mate_in(PLY_MAX), beta)
1889 || v < Min(value_mated_in(PLY_MAX), beta))
1891 && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1892 || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1896 // refine_eval() returns the transposition table score if
1897 // possible otherwise falls back on static position evaluation.
1899 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1903 Value v = value_from_tt(tte->value(), ply);
1905 if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1906 || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1913 // update_history() registers a good move that produced a beta-cutoff
1914 // in history and marks as failures all the other moves of that ply.
1916 void update_history(const Position& pos, Move move, Depth depth,
1917 Move movesSearched[], int moveCount) {
1920 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
1922 for (int i = 0; i < moveCount - 1; i++)
1924 m = movesSearched[i];
1928 if (!pos.move_is_capture_or_promotion(m))
1929 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
1934 // update_killers() add a good move that produced a beta-cutoff
1935 // among the killer moves of that ply.
1937 void update_killers(Move m, SearchStack* ss) {
1939 if (m == ss->killers[0])
1942 ss->killers[1] = ss->killers[0];
1947 // update_gains() updates the gains table of a non-capture move given
1948 // the static position evaluation before and after the move.
1950 void update_gains(const Position& pos, Move m, Value before, Value after) {
1953 && before != VALUE_NONE
1954 && after != VALUE_NONE
1955 && pos.captured_piece_type() == PIECE_TYPE_NONE
1956 && !move_is_special(m))
1957 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
1961 // current_search_time() returns the number of milliseconds which have passed
1962 // since the beginning of the current search.
1964 int current_search_time() {
1966 return get_system_time() - SearchStartTime;
1970 // value_to_uci() converts a value to a string suitable for use with the UCI protocol
1972 std::string value_to_uci(Value v) {
1974 std::stringstream s;
1976 if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
1977 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100
1979 s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
1984 // nps() computes the current nodes/second count.
1986 int nps(const Position& pos) {
1988 int t = current_search_time();
1989 return (t > 0 ? int((pos.nodes_searched() * 1000) / t) : 0);
1993 // poll() performs two different functions: It polls for user input, and it
1994 // looks at the time consumed so far and decides if it's time to abort the
1997 void poll(const Position& pos) {
1999 static int lastInfoTime;
2000 int t = current_search_time();
2003 if (data_available())
2005 // We are line oriented, don't read single chars
2006 std::string command;
2008 if (!std::getline(std::cin, command))
2011 if (command == "quit")
2014 PonderSearch = false;
2018 else if (command == "stop")
2021 PonderSearch = false;
2023 else if (command == "ponderhit")
2027 // Print search information
2031 else if (lastInfoTime > t)
2032 // HACK: Must be a new search where we searched less than
2033 // NodesBetweenPolls nodes during the first second of search.
2036 else if (t - lastInfoTime >= 1000)
2043 if (dbg_show_hit_rate)
2044 dbg_print_hit_rate();
2046 cout << "info nodes " << pos.nodes_searched() << " nps " << nps(pos)
2047 << " time " << t << endl;
2050 // Should we stop the search?
2054 bool stillAtFirstMove = FirstRootMove
2055 && !AspirationFailLow
2056 && t > TimeMgr.available_time();
2058 bool noMoreTime = t > TimeMgr.maximum_time()
2059 || stillAtFirstMove;
2061 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2062 || (ExactMaxTime && t >= ExactMaxTime)
2063 || (Iteration >= 3 && MaxNodes && pos.nodes_searched() >= MaxNodes))
2068 // ponderhit() is called when the program is pondering (i.e. thinking while
2069 // it's the opponent's turn to move) in order to let the engine know that
2070 // it correctly predicted the opponent's move.
2074 int t = current_search_time();
2075 PonderSearch = false;
2077 bool stillAtFirstMove = FirstRootMove
2078 && !AspirationFailLow
2079 && t > TimeMgr.available_time();
2081 bool noMoreTime = t > TimeMgr.maximum_time()
2082 || stillAtFirstMove;
2084 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2089 // init_ss_array() does a fast reset of the first entries of a SearchStack
2090 // array and of all the excludedMove and skipNullMove entries.
2092 void init_ss_array(SearchStack* ss, int size) {
2094 for (int i = 0; i < size; i++, ss++)
2096 ss->excludedMove = MOVE_NONE;
2097 ss->skipNullMove = false;
2098 ss->reduction = DEPTH_ZERO;
2102 ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE;
2107 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2108 // while the program is pondering. The point is to work around a wrinkle in
2109 // the UCI protocol: When pondering, the engine is not allowed to give a
2110 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2111 // We simply wait here until one of these commands is sent, and return,
2112 // after which the bestmove and pondermove will be printed (in id_loop()).
2114 void wait_for_stop_or_ponderhit() {
2116 std::string command;
2120 if (!std::getline(std::cin, command))
2123 if (command == "quit")
2128 else if (command == "ponderhit" || command == "stop")
2134 // print_pv_info() prints to standard output and eventually to log file information on
2135 // the current PV line. It is called at each iteration or after a new pv is found.
2137 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) {
2139 cout << "info depth " << Iteration
2140 << " score " << value_to_uci(value)
2141 << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
2142 << " time " << current_search_time()
2143 << " nodes " << pos.nodes_searched()
2144 << " nps " << nps(pos)
2147 for (Move* m = pv; *m != MOVE_NONE; m++)
2154 ValueType t = value >= beta ? VALUE_TYPE_LOWER :
2155 value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
2157 LogFile << pretty_pv(pos, current_search_time(), Iteration, value, t, pv) << endl;
2162 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2163 // the PV back into the TT. This makes sure the old PV moves are searched
2164 // first, even if the old TT entries have been overwritten.
2166 void insert_pv_in_tt(const Position& pos, Move pv[]) {
2170 Position p(pos, pos.thread());
2171 Value v, m = VALUE_NONE;
2173 for (int i = 0; pv[i] != MOVE_NONE; i++)
2175 tte = TT.retrieve(p.get_key());
2176 if (!tte || tte->move() != pv[i])
2178 v = (p.is_check() ? VALUE_NONE : evaluate(p, m));
2179 TT.store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[i], v, m);
2181 p.do_move(pv[i], st);
2186 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2187 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2188 // allow to always have a ponder move even when we fail high at root and also a
2189 // long PV to print that is important for position analysis.
2191 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]) {
2195 Position p(pos, pos.thread());
2198 assert(bestMove != MOVE_NONE);
2201 p.do_move(pv[ply++], st);
2203 while ( (tte = TT.retrieve(p.get_key())) != NULL
2204 && tte->move() != MOVE_NONE
2205 && move_is_legal(p, tte->move())
2207 && (!p.is_draw() || ply < 2))
2209 pv[ply] = tte->move();
2210 p.do_move(pv[ply++], st);
2212 pv[ply] = MOVE_NONE;
2216 // init_thread() is the function which is called when a new thread is
2217 // launched. It simply calls the idle_loop() function with the supplied
2218 // threadID. There are two versions of this function; one for POSIX
2219 // threads and one for Windows threads.
2221 #if !defined(_MSC_VER)
2223 void* init_thread(void* threadID) {
2225 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2231 DWORD WINAPI init_thread(LPVOID threadID) {
2233 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2240 /// The ThreadsManager class
2243 // read_uci_options() updates number of active threads and other internal
2244 // parameters according to the UCI options values. It is called before
2245 // to start a new search.
2247 void ThreadsManager::read_uci_options() {
2249 maxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value<int>();
2250 minimumSplitDepth = Options["Minimum Split Depth"].value<int>() * ONE_PLY;
2251 useSleepingThreads = Options["Use Sleeping Threads"].value<bool>();
2252 activeThreads = Options["Threads"].value<int>();
2256 // idle_loop() is where the threads are parked when they have no work to do.
2257 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2258 // object for which the current thread is the master.
2260 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2262 assert(threadID >= 0 && threadID < MAX_THREADS);
2265 bool allFinished = false;
2269 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2270 // master should exit as last one.
2271 if (allThreadsShouldExit)
2274 threads[threadID].state = THREAD_TERMINATED;
2278 // If we are not thinking, wait for a condition to be signaled
2279 // instead of wasting CPU time polling for work.
2280 while ( threadID >= activeThreads || threads[threadID].state == THREAD_INITIALIZING
2281 || (useSleepingThreads && threads[threadID].state == THREAD_AVAILABLE))
2283 assert(!sp || useSleepingThreads);
2284 assert(threadID != 0 || useSleepingThreads);
2286 if (threads[threadID].state == THREAD_INITIALIZING)
2287 threads[threadID].state = THREAD_AVAILABLE;
2289 // Grab the lock to avoid races with wake_sleeping_thread()
2290 lock_grab(&sleepLock[threadID]);
2292 // If we are master and all slaves have finished do not go to sleep
2293 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2294 allFinished = (i == activeThreads);
2296 if (allFinished || allThreadsShouldExit)
2298 lock_release(&sleepLock[threadID]);
2302 // Do sleep here after retesting sleep conditions
2303 if (threadID >= activeThreads || threads[threadID].state == THREAD_AVAILABLE)
2304 cond_wait(&sleepCond[threadID], &sleepLock[threadID]);
2306 lock_release(&sleepLock[threadID]);
2309 // If this thread has been assigned work, launch a search
2310 if (threads[threadID].state == THREAD_WORKISWAITING)
2312 assert(!allThreadsShouldExit);
2314 threads[threadID].state = THREAD_SEARCHING;
2316 // Here we call search() with SplitPoint template parameter set to true
2317 SplitPoint* tsp = threads[threadID].splitPoint;
2318 Position pos(*tsp->pos, threadID);
2319 SearchStack* ss = tsp->sstack[threadID] + 1;
2323 search<PV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2325 search<NonPV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2327 assert(threads[threadID].state == THREAD_SEARCHING);
2329 threads[threadID].state = THREAD_AVAILABLE;
2331 // Wake up master thread so to allow it to return from the idle loop in
2332 // case we are the last slave of the split point.
2333 if (useSleepingThreads && threadID != tsp->master && threads[tsp->master].state == THREAD_AVAILABLE)
2334 wake_sleeping_thread(tsp->master);
2337 // If this thread is the master of a split point and all slaves have
2338 // finished their work at this split point, return from the idle loop.
2339 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2340 allFinished = (i == activeThreads);
2344 // Because sp->slaves[] is reset under lock protection,
2345 // be sure sp->lock has been released before to return.
2346 lock_grab(&(sp->lock));
2347 lock_release(&(sp->lock));
2349 // In helpful master concept a master can help only a sub-tree, and
2350 // because here is all finished is not possible master is booked.
2351 assert(threads[threadID].state == THREAD_AVAILABLE);
2353 threads[threadID].state = THREAD_SEARCHING;
2360 // init_threads() is called during startup. It launches all helper threads,
2361 // and initializes the split point stack and the global locks and condition
2364 void ThreadsManager::init_threads() {
2366 int i, arg[MAX_THREADS];
2369 // Initialize global locks
2372 for (i = 0; i < MAX_THREADS; i++)
2374 lock_init(&sleepLock[i]);
2375 cond_init(&sleepCond[i]);
2378 // Initialize splitPoints[] locks
2379 for (i = 0; i < MAX_THREADS; i++)
2380 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2381 lock_init(&(threads[i].splitPoints[j].lock));
2383 // Will be set just before program exits to properly end the threads
2384 allThreadsShouldExit = false;
2386 // Threads will be put all threads to sleep as soon as created
2389 // All threads except the main thread should be initialized to THREAD_INITIALIZING
2390 threads[0].state = THREAD_SEARCHING;
2391 for (i = 1; i < MAX_THREADS; i++)
2392 threads[i].state = THREAD_INITIALIZING;
2394 // Launch the helper threads
2395 for (i = 1; i < MAX_THREADS; i++)
2399 #if !defined(_MSC_VER)
2400 pthread_t pthread[1];
2401 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
2402 pthread_detach(pthread[0]);
2404 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
2408 cout << "Failed to create thread number " << i << endl;
2412 // Wait until the thread has finished launching and is gone to sleep
2413 while (threads[i].state == THREAD_INITIALIZING) {}
2418 // exit_threads() is called when the program exits. It makes all the
2419 // helper threads exit cleanly.
2421 void ThreadsManager::exit_threads() {
2423 allThreadsShouldExit = true; // Let the woken up threads to exit idle_loop()
2425 // Wake up all the threads and waits for termination
2426 for (int i = 1; i < MAX_THREADS; i++)
2428 wake_sleeping_thread(i);
2429 while (threads[i].state != THREAD_TERMINATED) {}
2432 // Now we can safely destroy the locks
2433 for (int i = 0; i < MAX_THREADS; i++)
2434 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2435 lock_destroy(&(threads[i].splitPoints[j].lock));
2437 lock_destroy(&mpLock);
2439 // Now we can safely destroy the wait conditions
2440 for (int i = 0; i < MAX_THREADS; i++)
2442 lock_destroy(&sleepLock[i]);
2443 cond_destroy(&sleepCond[i]);
2448 // cutoff_at_splitpoint() checks whether a beta cutoff has occurred in
2449 // the thread's currently active split point, or in some ancestor of
2450 // the current split point.
2452 bool ThreadsManager::cutoff_at_splitpoint(int threadID) const {
2454 assert(threadID >= 0 && threadID < activeThreads);
2456 SplitPoint* sp = threads[threadID].splitPoint;
2458 for ( ; sp && !sp->betaCutoff; sp = sp->parent) {}
2463 // thread_is_available() checks whether the thread with threadID "slave" is
2464 // available to help the thread with threadID "master" at a split point. An
2465 // obvious requirement is that "slave" must be idle. With more than two
2466 // threads, this is not by itself sufficient: If "slave" is the master of
2467 // some active split point, it is only available as a slave to the other
2468 // threads which are busy searching the split point at the top of "slave"'s
2469 // split point stack (the "helpful master concept" in YBWC terminology).
2471 bool ThreadsManager::thread_is_available(int slave, int master) const {
2473 assert(slave >= 0 && slave < activeThreads);
2474 assert(master >= 0 && master < activeThreads);
2475 assert(activeThreads > 1);
2477 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2480 // Make a local copy to be sure doesn't change under our feet
2481 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2483 // No active split points means that the thread is available as
2484 // a slave for any other thread.
2485 if (localActiveSplitPoints == 0 || activeThreads == 2)
2488 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2489 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2490 // could have been set to 0 by another thread leading to an out of bound access.
2491 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2498 // available_thread_exists() tries to find an idle thread which is available as
2499 // a slave for the thread with threadID "master".
2501 bool ThreadsManager::available_thread_exists(int master) const {
2503 assert(master >= 0 && master < activeThreads);
2504 assert(activeThreads > 1);
2506 for (int i = 0; i < activeThreads; i++)
2507 if (thread_is_available(i, master))
2514 // split() does the actual work of distributing the work at a node between
2515 // several available threads. If it does not succeed in splitting the
2516 // node (because no idle threads are available, or because we have no unused
2517 // split point objects), the function immediately returns. If splitting is
2518 // possible, a SplitPoint object is initialized with all the data that must be
2519 // copied to the helper threads and we tell our helper threads that they have
2520 // been assigned work. This will cause them to instantly leave their idle loops and
2521 // call search().When all threads have returned from search() then split() returns.
2523 template <bool Fake>
2524 void ThreadsManager::split(Position& pos, SearchStack* ss, int ply, Value* alpha,
2525 const Value beta, Value* bestValue, Depth depth, Move threatMove,
2526 bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) {
2527 assert(pos.is_ok());
2528 assert(ply > 0 && ply < PLY_MAX);
2529 assert(*bestValue >= -VALUE_INFINITE);
2530 assert(*bestValue <= *alpha);
2531 assert(*alpha < beta);
2532 assert(beta <= VALUE_INFINITE);
2533 assert(depth > DEPTH_ZERO);
2534 assert(pos.thread() >= 0 && pos.thread() < activeThreads);
2535 assert(activeThreads > 1);
2537 int i, master = pos.thread();
2538 Thread& masterThread = threads[master];
2542 // If no other thread is available to help us, or if we have too many
2543 // active split points, don't split.
2544 if ( !available_thread_exists(master)
2545 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2547 lock_release(&mpLock);
2551 // Pick the next available split point object from the split point stack
2552 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2554 // Initialize the split point object
2555 splitPoint.parent = masterThread.splitPoint;
2556 splitPoint.master = master;
2557 splitPoint.betaCutoff = false;
2558 splitPoint.ply = ply;
2559 splitPoint.depth = depth;
2560 splitPoint.threatMove = threatMove;
2561 splitPoint.mateThreat = mateThreat;
2562 splitPoint.alpha = *alpha;
2563 splitPoint.beta = beta;
2564 splitPoint.pvNode = pvNode;
2565 splitPoint.bestValue = *bestValue;
2567 splitPoint.moveCount = moveCount;
2568 splitPoint.pos = &pos;
2569 splitPoint.nodes = 0;
2570 splitPoint.parentSstack = ss;
2571 for (i = 0; i < activeThreads; i++)
2572 splitPoint.slaves[i] = 0;
2574 masterThread.splitPoint = &splitPoint;
2576 // If we are here it means we are not available
2577 assert(masterThread.state != THREAD_AVAILABLE);
2579 int workersCnt = 1; // At least the master is included
2581 // Allocate available threads setting state to THREAD_BOOKED
2582 for (i = 0; !Fake && i < activeThreads && workersCnt < maxThreadsPerSplitPoint; i++)
2583 if (thread_is_available(i, master))
2585 threads[i].state = THREAD_BOOKED;
2586 threads[i].splitPoint = &splitPoint;
2587 splitPoint.slaves[i] = 1;
2591 assert(Fake || workersCnt > 1);
2593 // We can release the lock because slave threads are already booked and master is not available
2594 lock_release(&mpLock);
2596 // Tell the threads that they have work to do. This will make them leave
2597 // their idle loop. But before copy search stack tail for each thread.
2598 for (i = 0; i < activeThreads; i++)
2599 if (i == master || splitPoint.slaves[i])
2601 memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
2603 assert(i == master || threads[i].state == THREAD_BOOKED);
2605 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2607 if (useSleepingThreads && i != master)
2608 wake_sleeping_thread(i);
2611 // Everything is set up. The master thread enters the idle loop, from
2612 // which it will instantly launch a search, because its state is
2613 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2614 // idle loop, which means that the main thread will return from the idle
2615 // loop when all threads have finished their work at this split point.
2616 idle_loop(master, &splitPoint);
2618 // We have returned from the idle loop, which means that all threads are
2619 // finished. Update alpha and bestValue, and return.
2622 *alpha = splitPoint.alpha;
2623 *bestValue = splitPoint.bestValue;
2624 masterThread.activeSplitPoints--;
2625 masterThread.splitPoint = splitPoint.parent;
2626 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
2628 lock_release(&mpLock);
2632 // wake_sleeping_thread() wakes up the thread with the given threadID
2633 // when it is time to start a new search.
2635 void ThreadsManager::wake_sleeping_thread(int threadID) {
2637 lock_grab(&sleepLock[threadID]);
2638 cond_signal(&sleepCond[threadID]);
2639 lock_release(&sleepLock[threadID]);
2643 /// The RootMoveList class
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--;