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;
129 void set_pv(const Move newPv[]);
132 Value pv_score, non_pv_score;
133 Move move, pv[PLY_MAX_PLUS_2];
136 RootMove::RootMove() : nodes(0) {
138 pv_score = non_pv_score = -VALUE_INFINITE;
139 move = pv[0] = MOVE_NONE;
142 RootMove& RootMove::operator=(const RootMove& rm) {
144 pv_score = rm.pv_score; non_pv_score = rm.non_pv_score;
145 nodes = rm.nodes; move = rm.move;
146 set_pv(rm.pv); // Skip costly full pv[] copy
150 void RootMove::set_pv(const Move newPv[]) {
154 while (*newPv != MOVE_NONE)
161 // RootMoveList struct is essentially a std::vector<> of RootMove objects,
162 // with an handful of methods above the standard ones.
164 struct RootMoveList : public std::vector<RootMove> {
166 typedef std::vector<RootMove> Base;
168 RootMoveList(Position& pos, Move searchMoves[]);
169 void set_non_pv_scores(const Position& pos);
171 void sort() { insertion_sort<RootMove, Base::iterator>(begin(), end()); }
172 void sort_multipv(int n) { insertion_sort<RootMove, Base::iterator>(begin(), begin() + n); }
176 // When formatting a move for std::cout we must know if we are in Chess960
177 // or not. To keep using the handy operator<<() on the move the trick is to
178 // embed this flag in the stream itself. Function-like named enum set960 is
179 // used as a custom manipulator and the stream internal general-purpose array,
180 // accessed through ios_base::iword(), is used to pass the flag to the move's
181 // operator<<() that will use it to properly format castling moves.
184 std::ostream& operator<< (std::ostream& os, const set960& m) {
186 os.iword(0) = int(m);
195 // Maximum depth for razoring
196 const Depth RazorDepth = 4 * ONE_PLY;
198 // Dynamic razoring margin based on depth
199 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
201 // Maximum depth for use of dynamic threat detection when null move fails low
202 const Depth ThreatDepth = 5 * ONE_PLY;
204 // Step 9. Internal iterative deepening
206 // Minimum depth for use of internal iterative deepening
207 const Depth IIDDepth[2] = { 8 * ONE_PLY /* non-PV */, 5 * ONE_PLY /* PV */};
209 // At Non-PV nodes we do an internal iterative deepening search
210 // when the static evaluation is bigger then beta - IIDMargin.
211 const Value IIDMargin = Value(0x100);
213 // Step 11. Decide the new search depth
215 // Extensions. Configurable UCI options
216 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
217 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
218 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
220 // Minimum depth for use of singular extension
221 const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */};
223 // If the TT move is at least SingularExtensionMargin better then the
224 // remaining ones we will extend it.
225 const Value SingularExtensionMargin = Value(0x20);
227 // Step 12. Futility pruning
229 // Futility margin for quiescence search
230 const Value FutilityMarginQS = Value(0x80);
232 // Futility lookup tables (initialized at startup) and their getter functions
233 Value FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
234 int FutilityMoveCountArray[32]; // [depth]
236 inline Value futility_margin(Depth d, int mn) { return d < 7 * ONE_PLY ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE; }
237 inline int futility_move_count(Depth d) { return d < 16 * ONE_PLY ? FutilityMoveCountArray[d] : 512; }
239 // Step 14. Reduced search
241 // Reduction lookup tables (initialized at startup) and their getter functions
242 int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
244 template <NodeType PV>
245 inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
247 // Common adjustments
249 // Search depth at iteration 1
250 const Depth InitialDepth = ONE_PLY;
252 // Easy move margin. An easy move candidate must be at least this much
253 // better than the second best move.
254 const Value EasyMoveMargin = Value(0x200);
257 /// Namespace variables
265 // Scores and number of times the best move changed for each iteration
266 Value ValueByIteration[PLY_MAX_PLUS_2];
267 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
269 // Search window management
275 // Time managment variables
276 int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
277 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
278 bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
283 std::ofstream LogFile;
285 // Multi-threads manager object
286 ThreadsManager ThreadsMgr;
288 // Node counters, used only by thread[0] but try to keep in different cache
289 // lines (64 bytes each) from the heavy multi-thread read accessed variables.
291 int NodesBetweenPolls = 30000;
298 Value id_loop(Position& pos, Move searchMoves[]);
299 Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
301 template <NodeType PvNode, bool SpNode>
302 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
304 template <NodeType PvNode>
305 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
307 template <NodeType PvNode>
308 inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
310 return depth < ONE_PLY ? qsearch<PvNode>(pos, ss, alpha, beta, DEPTH_ZERO, ply)
311 : search<PvNode, false>(pos, ss, alpha, beta, depth, ply);
314 template <NodeType PvNode>
315 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
317 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue);
318 bool connected_moves(const Position& pos, Move m1, Move m2);
319 bool value_is_mate(Value value);
320 Value value_to_tt(Value v, int ply);
321 Value value_from_tt(Value v, int ply);
322 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
323 bool connected_threat(const Position& pos, Move m, Move threat);
324 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
325 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
326 void update_killers(Move m, SearchStack* ss);
327 void update_gains(const Position& pos, Move move, Value before, Value after);
329 int current_search_time();
330 std::string value_to_uci(Value v);
331 int nps(const Position& pos);
332 void poll(const Position& pos);
334 void wait_for_stop_or_ponderhit();
335 void init_ss_array(SearchStack* ss, int size);
336 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value);
337 void insert_pv_in_tt(const Position& pos, Move pv[]);
338 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]);
340 #if !defined(_MSC_VER)
341 void* init_thread(void* threadID);
343 DWORD WINAPI init_thread(LPVOID threadID);
353 /// init_threads(), exit_threads() and nodes_searched() are helpers to
354 /// give accessibility to some TM methods from outside of current file.
356 void init_threads() { ThreadsMgr.init_threads(); }
357 void exit_threads() { ThreadsMgr.exit_threads(); }
360 /// init_search() is called during startup. It initializes various lookup tables
364 int d; // depth (ONE_PLY == 2)
365 int hd; // half depth (ONE_PLY == 1)
368 // Init reductions array
369 for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
371 double pvRed = log(double(hd)) * log(double(mc)) / 3.0;
372 double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
373 ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0);
374 ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0);
377 // Init futility margins array
378 for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
379 FutilityMarginsMatrix[d][mc] = Value(112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45);
381 // Init futility move count array
382 for (d = 0; d < 32; d++)
383 FutilityMoveCountArray[d] = int(3.001 + 0.25 * pow(d, 2.0));
387 /// perft() is our utility to verify move generation is bug free. All the legal
388 /// moves up to given depth are generated and counted and the sum returned.
390 int perft(Position& pos, Depth depth)
392 MoveStack mlist[MOVES_MAX];
397 // Generate all legal moves
398 MoveStack* last = generate_moves(pos, mlist);
400 // If we are at the last ply we don't need to do and undo
401 // the moves, just to count them.
402 if (depth <= ONE_PLY)
403 return int(last - mlist);
405 // Loop through all legal moves
407 for (MoveStack* cur = mlist; cur != last; cur++)
410 pos.do_move(m, st, ci, pos.move_is_check(m, ci));
411 sum += perft(pos, depth - ONE_PLY);
418 /// think() is the external interface to Stockfish's search, and is called when
419 /// the program receives the UCI 'go' command. It initializes various
420 /// search-related global variables, and calls root_search(). It returns false
421 /// when a quit command is received during the search.
423 bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[],
424 int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) {
426 // Initialize global search variables
427 StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
429 SearchStartTime = get_system_time();
430 ExactMaxTime = maxTime;
433 InfiniteSearch = infinite;
434 PonderSearch = ponder;
435 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
437 // Look for a book move, only during games, not tests
438 if (UseTimeManagement && Options["OwnBook"].value<bool>())
440 if (Options["Book File"].value<std::string>() != OpeningBook.file_name())
441 OpeningBook.open(Options["Book File"].value<std::string>());
443 Move bookMove = OpeningBook.get_move(pos, Options["Best Book Move"].value<bool>());
444 if (bookMove != MOVE_NONE)
447 wait_for_stop_or_ponderhit();
449 cout << "bestmove " << bookMove << endl;
454 // Read UCI option values
455 TT.set_size(Options["Hash"].value<int>());
456 if (Options["Clear Hash"].value<bool>())
458 Options["Clear Hash"].set_value("false");
462 CheckExtension[1] = Options["Check Extension (PV nodes)"].value<Depth>();
463 CheckExtension[0] = Options["Check Extension (non-PV nodes)"].value<Depth>();
464 SingleEvasionExtension[1] = Options["Single Evasion Extension (PV nodes)"].value<Depth>();
465 SingleEvasionExtension[0] = Options["Single Evasion Extension (non-PV nodes)"].value<Depth>();
466 PawnPushTo7thExtension[1] = Options["Pawn Push to 7th Extension (PV nodes)"].value<Depth>();
467 PawnPushTo7thExtension[0] = Options["Pawn Push to 7th Extension (non-PV nodes)"].value<Depth>();
468 PassedPawnExtension[1] = Options["Passed Pawn Extension (PV nodes)"].value<Depth>();
469 PassedPawnExtension[0] = Options["Passed Pawn Extension (non-PV nodes)"].value<Depth>();
470 PawnEndgameExtension[1] = Options["Pawn Endgame Extension (PV nodes)"].value<Depth>();
471 PawnEndgameExtension[0] = Options["Pawn Endgame Extension (non-PV nodes)"].value<Depth>();
472 MateThreatExtension[1] = Options["Mate Threat Extension (PV nodes)"].value<Depth>();
473 MateThreatExtension[0] = Options["Mate Threat Extension (non-PV nodes)"].value<Depth>();
474 MultiPV = Options["MultiPV"].value<int>();
475 UseLogFile = Options["Use Search Log"].value<bool>();
478 LogFile.open(Options["Search Log Filename"].value<std::string>().c_str(), std::ios::out | std::ios::app);
480 read_weights(pos.side_to_move());
482 // Set the number of active threads
483 ThreadsMgr.read_uci_options();
484 init_eval(ThreadsMgr.active_threads());
486 // Wake up needed threads
487 for (int i = 1; i < ThreadsMgr.active_threads(); i++)
488 ThreadsMgr.wake_sleeping_thread(i);
491 int myTime = time[pos.side_to_move()];
492 int myIncrement = increment[pos.side_to_move()];
493 if (UseTimeManagement)
494 TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter());
496 // Set best NodesBetweenPolls interval to avoid lagging under
497 // heavy time pressure.
499 NodesBetweenPolls = Min(MaxNodes, 30000);
500 else if (myTime && myTime < 1000)
501 NodesBetweenPolls = 1000;
502 else if (myTime && myTime < 5000)
503 NodesBetweenPolls = 5000;
505 NodesBetweenPolls = 30000;
507 // Write search information to log file
509 LogFile << "Searching: " << pos.to_fen() << endl
510 << "infinite: " << infinite
511 << " ponder: " << ponder
512 << " time: " << myTime
513 << " increment: " << myIncrement
514 << " moves to go: " << movesToGo << endl;
516 // We're ready to start thinking. Call the iterative deepening loop function
517 id_loop(pos, searchMoves);
522 // This makes all the threads to go to sleep
523 ThreadsMgr.set_active_threads(1);
531 // id_loop() is the main iterative deepening loop. It calls root_search
532 // repeatedly with increasing depth until the allocated thinking time has
533 // been consumed, the user stops the search, or the maximum search depth is
536 Value id_loop(Position& pos, Move searchMoves[]) {
538 SearchStack ss[PLY_MAX_PLUS_2];
539 Move pv[PLY_MAX_PLUS_2];
540 Move EasyMove = MOVE_NONE;
541 Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
543 // Moves to search are verified, copied, scored and sorted
544 RootMoveList rml(pos, searchMoves);
546 // Handle special case of searching on a mate/stale position
550 wait_for_stop_or_ponderhit();
552 return pos.is_check() ? -VALUE_MATE : VALUE_DRAW;
555 // Print RootMoveList startup scoring to the standard output,
556 // so to output information also for iteration 1.
557 cout << set960(pos.is_chess960()) // Is enough to set once at the beginning
558 << "info depth " << 1
559 << "\ninfo depth " << 1
560 << " score " << value_to_uci(rml[0].pv_score)
561 << " time " << current_search_time()
562 << " nodes " << pos.nodes_searched()
563 << " nps " << nps(pos)
564 << " pv " << rml[0].move << "\n";
569 init_ss_array(ss, PLY_MAX_PLUS_2);
570 pv[0] = pv[1] = MOVE_NONE;
571 ValueByIteration[1] = rml[0].pv_score;
574 // Is one move significantly better than others after initial scoring ?
576 || rml[0].pv_score > rml[1].pv_score + EasyMoveMargin)
577 EasyMove = rml[0].move;
579 // Iterative deepening loop
580 while (Iteration < PLY_MAX)
582 // Initialize iteration
584 BestMoveChangesByIteration[Iteration] = 0;
586 cout << "info depth " << Iteration << endl;
588 // Calculate dynamic aspiration window based on previous iterations
589 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
591 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
592 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
594 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
595 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
597 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
598 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
601 // Search to the current depth, rml is updated and sorted, alpha and beta could change
602 value = root_search(pos, ss, pv, rml, &alpha, &beta);
604 // Write PV to transposition table, in case the relevant entries have
605 // been overwritten during the search.
606 insert_pv_in_tt(pos, pv);
609 break; // Value cannot be trusted. Break out immediately!
611 //Save info about search result
612 ValueByIteration[Iteration] = value;
614 // Drop the easy move if differs from the new best move
615 if (pv[0] != EasyMove)
616 EasyMove = MOVE_NONE;
618 if (UseTimeManagement)
621 bool stopSearch = false;
623 // Stop search early if there is only a single legal move,
624 // we search up to Iteration 6 anyway to get a proper score.
625 if (Iteration >= 6 && rml.size() == 1)
628 // Stop search early when the last two iterations returned a mate score
630 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
631 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
634 // Stop search early if one move seems to be much better than the others
637 && ( ( rml[0].nodes > (pos.nodes_searched() * 85) / 100
638 && current_search_time() > TimeMgr.available_time() / 16)
639 ||( rml[0].nodes > (pos.nodes_searched() * 98) / 100
640 && current_search_time() > TimeMgr.available_time() / 32)))
643 // Add some extra time if the best move has changed during the last two iterations
644 if (Iteration > 5 && Iteration <= 50)
645 TimeMgr.pv_instability(BestMoveChangesByIteration[Iteration],
646 BestMoveChangesByIteration[Iteration-1]);
648 // Stop search if most of MaxSearchTime is consumed at the end of the
649 // iteration. We probably don't have enough time to search the first
650 // move at the next iteration anyway.
651 if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
657 StopOnPonderhit = true;
663 if (MaxDepth && Iteration >= MaxDepth)
667 // If we are pondering or in infinite search, we shouldn't print the
668 // best move before we are told to do so.
669 if (!AbortSearch && (PonderSearch || InfiniteSearch))
670 wait_for_stop_or_ponderhit();
672 // Print final search statistics
673 cout << "info nodes " << pos.nodes_searched()
674 << " nps " << nps(pos)
675 << " time " << current_search_time() << endl;
677 // Print the best move and the ponder move to the standard output
678 if (pv[0] == MOVE_NONE || MultiPV > 1)
684 assert(pv[0] != MOVE_NONE);
686 cout << "bestmove " << pv[0];
688 if (pv[1] != MOVE_NONE)
689 cout << " ponder " << pv[1];
696 dbg_print_mean(LogFile);
698 if (dbg_show_hit_rate)
699 dbg_print_hit_rate(LogFile);
701 LogFile << "\nNodes: " << pos.nodes_searched()
702 << "\nNodes/second: " << nps(pos)
703 << "\nBest move: " << move_to_san(pos, pv[0]);
706 pos.do_move(pv[0], st);
707 LogFile << "\nPonder move: "
708 << move_to_san(pos, pv[1]) // Works also with MOVE_NONE
711 return rml[0].pv_score;
715 // root_search() is the function which searches the root node. It is
716 // similar to search_pv except that it uses a different move ordering
717 // scheme, prints some information to the standard output and handles
718 // the fail low/high loops.
720 Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
726 Depth depth, ext, newDepth;
727 Value value, alpha, beta;
728 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
729 int researchCountFH, researchCountFL;
731 researchCountFH = researchCountFL = 0;
734 isCheck = pos.is_check();
735 depth = (Iteration - 2) * ONE_PLY + InitialDepth;
737 // Step 1. Initialize node (polling is omitted at root)
738 ss->currentMove = ss->bestMove = MOVE_NONE;
740 // Step 2. Check for aborted search (omitted at root)
741 // Step 3. Mate distance pruning (omitted at root)
742 // Step 4. Transposition table lookup (omitted at root)
744 // Step 5. Evaluate the position statically
745 // At root we do this only to get reference value for child nodes
746 ss->evalMargin = VALUE_NONE;
747 ss->eval = isCheck ? VALUE_NONE : evaluate(pos, ss->evalMargin);
749 // Step 6. Razoring (omitted at root)
750 // Step 7. Static null move pruning (omitted at root)
751 // Step 8. Null move search with verification search (omitted at root)
752 // Step 9. Internal iterative deepening (omitted at root)
754 // Step extra. Fail low loop
755 // We start with small aspiration window and in case of fail low, we research
756 // with bigger window until we are not failing low anymore.
759 // Sort the moves before to (re)search
760 rml.set_non_pv_scores(pos);
763 // Step 10. Loop through all moves in the root move list
764 for (int i = 0; i < (int)rml.size() && !AbortSearch; i++)
766 // This is used by time management
767 FirstRootMove = (i == 0);
769 // Save the current node count before the move is searched
770 nodes = pos.nodes_searched();
772 // Pick the next root move, and print the move and the move number to
773 // the standard output.
774 move = ss->currentMove = rml[i].move;
776 if (current_search_time() >= 1000)
777 cout << "info currmove " << move
778 << " currmovenumber " << i + 1 << endl;
780 moveIsCheck = pos.move_is_check(move);
781 captureOrPromotion = pos.move_is_capture_or_promotion(move);
783 // Step 11. Decide the new search depth
784 ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
785 newDepth = depth + ext;
787 // Step 12. Futility pruning (omitted at root)
789 // Step extra. Fail high loop
790 // If move fails high, we research with bigger window until we are not failing
792 value = -VALUE_INFINITE;
796 // Step 13. Make the move
797 pos.do_move(move, st, ci, moveIsCheck);
799 // Step extra. pv search
800 // We do pv search for first moves (i < MultiPV)
801 // and for fail high research (value > alpha)
802 if (i < MultiPV || value > alpha)
804 // Aspiration window is disabled in multi-pv case
806 alpha = -VALUE_INFINITE;
808 // Full depth PV search, done on first move or after a fail high
809 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
813 // Step 14. Reduced search
814 // if the move fails high will be re-searched at full depth
815 bool doFullDepthSearch = true;
817 if ( depth >= 3 * ONE_PLY
819 && !captureOrPromotion
820 && !move_is_castle(move))
822 ss->reduction = reduction<PV>(depth, i - MultiPV + 2);
825 assert(newDepth-ss->reduction >= ONE_PLY);
827 // Reduced depth non-pv search using alpha as upperbound
828 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
829 doFullDepthSearch = (value > alpha);
832 // The move failed high, but if reduction is very big we could
833 // face a false positive, retry with a less aggressive reduction,
834 // if the move fails high again then go with full depth search.
835 if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
837 assert(newDepth - ONE_PLY >= ONE_PLY);
839 ss->reduction = ONE_PLY;
840 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
841 doFullDepthSearch = (value > alpha);
843 ss->reduction = DEPTH_ZERO; // Restore original reduction
846 // Step 15. Full depth search
847 if (doFullDepthSearch)
849 // Full depth non-pv search using alpha as upperbound
850 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, 1);
852 // If we are above alpha then research at same depth but as PV
853 // to get a correct score or eventually a fail high above beta.
855 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
859 // Step 16. Undo move
862 // Can we exit fail high loop ?
863 if (AbortSearch || value < beta)
866 // We are failing high and going to do a research. It's important to update
867 // the score before research in case we run out of time while researching.
868 rml[i].pv_score = value;
870 extract_pv_from_tt(pos, move, pv);
873 // Print information to the standard output
874 print_pv_info(pos, pv, alpha, beta, value);
876 // Prepare for a research after a fail high, each time with a wider window
877 *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
880 } // End of fail high loop
882 // Finished searching the move. If AbortSearch is true, the search
883 // was aborted because the user interrupted the search or because we
884 // ran out of time. In this case, the return value of the search cannot
885 // be trusted, and we break out of the loop without updating the best
890 // Remember searched nodes counts for this move
891 rml[i].nodes += pos.nodes_searched() - nodes;
893 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
894 assert(value < beta);
896 // Step 17. Check for new best move
897 if (value <= alpha && i >= MultiPV)
898 rml[i].pv_score = -VALUE_INFINITE;
901 // PV move or new best move!
904 rml[i].pv_score = value;
906 extract_pv_from_tt(pos, move, pv);
911 // We record how often the best move has been changed in each
912 // iteration. This information is used for time managment: When
913 // the best move changes frequently, we allocate some more time.
915 BestMoveChangesByIteration[Iteration]++;
917 // Print information to the standard output
918 print_pv_info(pos, pv, alpha, beta, value);
920 // Raise alpha to setup proper non-pv search upper bound
927 for (int j = 0; j < Min(MultiPV, (int)rml.size()); j++)
929 cout << "info multipv " << j + 1
930 << " score " << value_to_uci(rml[j].pv_score)
931 << " depth " << (j <= i ? Iteration : Iteration - 1)
932 << " time " << current_search_time()
933 << " nodes " << pos.nodes_searched()
934 << " nps " << nps(pos)
937 for (int k = 0; rml[j].pv[k] != MOVE_NONE && k < PLY_MAX; k++)
938 cout << rml[j].pv[k] << " ";
942 alpha = rml[Min(i, MultiPV - 1)].pv_score;
944 } // PV move or new best move
946 assert(alpha >= *alphaPtr);
948 AspirationFailLow = (alpha == *alphaPtr);
950 if (AspirationFailLow && StopOnPonderhit)
951 StopOnPonderhit = false;
954 // Can we exit fail low loop ?
955 if (AbortSearch || !AspirationFailLow)
958 // Prepare for a research after a fail low, each time with a wider window
959 *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
964 // Sort the moves before to return
971 // search<>() is the main search function for both PV and non-PV nodes and for
972 // normal and SplitPoint nodes. When called just after a split point the search
973 // is simpler because we have already probed the hash table, done a null move
974 // search, and searched the first move before splitting, we don't have to repeat
975 // all this work again. We also don't need to store anything to the hash table
976 // here: This is taken care of after we return from the split point.
978 template <NodeType PvNode, bool SpNode>
979 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
981 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
982 assert(beta > alpha && beta <= VALUE_INFINITE);
983 assert(PvNode || alpha == beta - 1);
984 assert(ply > 0 && ply < PLY_MAX);
985 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
987 Move movesSearched[MOVES_MAX];
991 Move ttMove, move, excludedMove, threatMove;
994 Value bestValue, value, oldAlpha;
995 Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
996 bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
997 bool mateThreat = false;
999 int threadID = pos.thread();
1000 SplitPoint* sp = NULL;
1001 refinedValue = bestValue = value = -VALUE_INFINITE;
1003 isCheck = pos.is_check();
1009 ttMove = excludedMove = MOVE_NONE;
1010 threatMove = sp->threatMove;
1011 mateThreat = sp->mateThreat;
1012 goto split_point_start;
1014 else {} // Hack to fix icc's "statement is unreachable" warning
1016 // Step 1. Initialize node and poll. Polling can abort search
1017 ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
1018 (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
1020 if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
1026 // Step 2. Check for aborted search and immediate draw
1028 || ThreadsMgr.cutoff_at_splitpoint(threadID)
1030 || ply >= PLY_MAX - 1)
1033 // Step 3. Mate distance pruning
1034 alpha = Max(value_mated_in(ply), alpha);
1035 beta = Min(value_mate_in(ply+1), beta);
1039 // Step 4. Transposition table lookup
1041 // We don't want the score of a partial search to overwrite a previous full search
1042 // TT value, so we use a different position key in case of an excluded move exists.
1043 excludedMove = ss->excludedMove;
1044 posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1046 tte = TT.retrieve(posKey);
1047 ttMove = tte ? tte->move() : MOVE_NONE;
1049 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1050 // This is to avoid problems in the following areas:
1052 // * Repetition draw detection
1053 // * Fifty move rule detection
1054 // * Searching for a mate
1055 // * Printing of full PV line
1056 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1059 ss->bestMove = ttMove; // Can be MOVE_NONE
1060 return value_from_tt(tte->value(), ply);
1063 // Step 5. Evaluate the position statically and
1064 // update gain statistics of parent move.
1066 ss->eval = ss->evalMargin = VALUE_NONE;
1069 assert(tte->static_value() != VALUE_NONE);
1071 ss->eval = tte->static_value();
1072 ss->evalMargin = tte->static_value_margin();
1073 refinedValue = refine_eval(tte, ss->eval, ply);
1077 refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
1078 TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
1081 // Save gain for the parent non-capture move
1082 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1084 // Step 6. Razoring (is omitted in PV nodes)
1086 && depth < RazorDepth
1088 && refinedValue < beta - razor_margin(depth)
1089 && ttMove == MOVE_NONE
1090 && !value_is_mate(beta)
1091 && !pos.has_pawn_on_7th(pos.side_to_move()))
1093 Value rbeta = beta - razor_margin(depth);
1094 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply);
1096 // Logically we should return (v + razor_margin(depth)), but
1097 // surprisingly this did slightly weaker in tests.
1101 // Step 7. Static null move pruning (is omitted in PV nodes)
1102 // We're betting that the opponent doesn't have a move that will reduce
1103 // the score by more than futility_margin(depth) if we do a null move.
1105 && !ss->skipNullMove
1106 && depth < RazorDepth
1108 && refinedValue >= beta + futility_margin(depth, 0)
1109 && !value_is_mate(beta)
1110 && pos.non_pawn_material(pos.side_to_move()))
1111 return refinedValue - futility_margin(depth, 0);
1113 // Step 8. Null move search with verification search (is omitted in PV nodes)
1115 && !ss->skipNullMove
1118 && refinedValue >= beta
1119 && !value_is_mate(beta)
1120 && pos.non_pawn_material(pos.side_to_move()))
1122 ss->currentMove = MOVE_NULL;
1124 // Null move dynamic reduction based on depth
1125 int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
1127 // Null move dynamic reduction based on value
1128 if (refinedValue - beta > PawnValueMidgame)
1131 pos.do_null_move(st);
1132 (ss+1)->skipNullMove = true;
1133 nullValue = -search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1);
1134 (ss+1)->skipNullMove = false;
1135 pos.undo_null_move();
1137 if (nullValue >= beta)
1139 // Do not return unproven mate scores
1140 if (nullValue >= value_mate_in(PLY_MAX))
1143 if (depth < 6 * ONE_PLY)
1146 // Do verification search at high depths
1147 ss->skipNullMove = true;
1148 Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY, ply);
1149 ss->skipNullMove = false;
1156 // The null move failed low, which means that we may be faced with
1157 // some kind of threat. If the previous move was reduced, check if
1158 // the move that refuted the null move was somehow connected to the
1159 // move which was reduced. If a connection is found, return a fail
1160 // low score (which will cause the reduced move to fail high in the
1161 // parent node, which will trigger a re-search with full depth).
1162 if (nullValue == value_mated_in(ply + 2))
1165 threatMove = (ss+1)->bestMove;
1166 if ( depth < ThreatDepth
1167 && (ss-1)->reduction
1168 && threatMove != MOVE_NONE
1169 && connected_moves(pos, (ss-1)->currentMove, threatMove))
1174 // Step 9. Internal iterative deepening
1175 if ( depth >= IIDDepth[PvNode]
1176 && ttMove == MOVE_NONE
1177 && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
1179 Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
1181 ss->skipNullMove = true;
1182 search<PvNode>(pos, ss, alpha, beta, d, ply);
1183 ss->skipNullMove = false;
1185 ttMove = ss->bestMove;
1186 tte = TT.retrieve(posKey);
1189 // Expensive mate threat detection (only for PV nodes)
1191 mateThreat = pos.has_mate_threat();
1193 split_point_start: // At split points actual search starts from here
1195 // Initialize a MovePicker object for the current position
1196 // FIXME currently MovePicker() c'tor is needless called also in SplitPoint
1197 MovePicker mpBase(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
1198 MovePicker& mp = SpNode ? *sp->mp : mpBase;
1200 ss->bestMove = MOVE_NONE;
1201 singleEvasion = !SpNode && isCheck && mp.number_of_evasions() == 1;
1202 futilityBase = ss->eval + ss->evalMargin;
1203 singularExtensionNode = !SpNode
1204 && depth >= SingularExtensionDepth[PvNode]
1207 && !excludedMove // Do not allow recursive singular extension search
1208 && (tte->type() & VALUE_TYPE_LOWER)
1209 && tte->depth() >= depth - 3 * ONE_PLY;
1212 lock_grab(&(sp->lock));
1213 bestValue = sp->bestValue;
1216 // Step 10. Loop through moves
1217 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1218 while ( bestValue < beta
1219 && (move = mp.get_next_move()) != MOVE_NONE
1220 && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1222 assert(move_is_ok(move));
1226 moveCount = ++sp->moveCount;
1227 lock_release(&(sp->lock));
1229 else if (move == excludedMove)
1232 movesSearched[moveCount++] = move;
1234 moveIsCheck = pos.move_is_check(move, ci);
1235 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1237 // Step 11. Decide the new search depth
1238 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1240 // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s),
1241 // and just one fails high on (alpha, beta), then that move is singular and should be extended.
1242 // To verify this we do a reduced search on all the other moves but the ttMove, if result is
1243 // lower then ttValue minus a margin then we extend ttMove.
1244 if ( singularExtensionNode
1245 && move == tte->move()
1248 Value ttValue = value_from_tt(tte->value(), ply);
1250 if (abs(ttValue) < VALUE_KNOWN_WIN)
1252 Value b = ttValue - SingularExtensionMargin;
1253 ss->excludedMove = move;
1254 ss->skipNullMove = true;
1255 Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
1256 ss->skipNullMove = false;
1257 ss->excludedMove = MOVE_NONE;
1258 ss->bestMove = MOVE_NONE;
1264 // Update current move (this must be done after singular extension search)
1265 ss->currentMove = move;
1266 newDepth = depth - ONE_PLY + ext;
1268 // Step 12. Futility pruning (is omitted in PV nodes)
1270 && !captureOrPromotion
1274 && !move_is_castle(move))
1276 // Move count based pruning
1277 if ( moveCount >= futility_move_count(depth)
1278 && !(threatMove && connected_threat(pos, move, threatMove))
1279 && bestValue > value_mated_in(PLY_MAX)) // FIXME bestValue is racy
1282 lock_grab(&(sp->lock));
1287 // Value based pruning
1288 // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
1289 // but fixing this made program slightly weaker.
1290 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1291 futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount)
1292 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1294 if (futilityValueScaled < beta)
1298 lock_grab(&(sp->lock));
1299 if (futilityValueScaled > sp->bestValue)
1300 sp->bestValue = bestValue = futilityValueScaled;
1302 else if (futilityValueScaled > bestValue)
1303 bestValue = futilityValueScaled;
1308 // Prune moves with negative SEE at low depths
1309 if ( predictedDepth < 2 * ONE_PLY
1310 && bestValue > value_mated_in(PLY_MAX)
1311 && pos.see_sign(move) < 0)
1314 lock_grab(&(sp->lock));
1320 // Step 13. Make the move
1321 pos.do_move(move, st, ci, moveIsCheck);
1323 // Step extra. pv search (only in PV nodes)
1324 // The first move in list is the expected PV
1325 if (PvNode && moveCount == 1)
1326 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1329 // Step 14. Reduced depth search
1330 // If the move fails high will be re-searched at full depth.
1331 bool doFullDepthSearch = true;
1333 if ( depth >= 3 * ONE_PLY
1334 && !captureOrPromotion
1336 && !move_is_castle(move)
1337 && ss->killers[0] != move
1338 && ss->killers[1] != move)
1340 ss->reduction = reduction<PvNode>(depth, moveCount);
1344 alpha = SpNode ? sp->alpha : alpha;
1345 Depth d = newDepth - ss->reduction;
1346 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1348 doFullDepthSearch = (value > alpha);
1351 // The move failed high, but if reduction is very big we could
1352 // face a false positive, retry with a less aggressive reduction,
1353 // if the move fails high again then go with full depth search.
1354 if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
1356 assert(newDepth - ONE_PLY >= ONE_PLY);
1358 ss->reduction = ONE_PLY;
1359 alpha = SpNode ? sp->alpha : alpha;
1360 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, ply+1);
1361 doFullDepthSearch = (value > alpha);
1363 ss->reduction = DEPTH_ZERO; // Restore original reduction
1366 // Step 15. Full depth search
1367 if (doFullDepthSearch)
1369 alpha = SpNode ? sp->alpha : alpha;
1370 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1372 // Step extra. pv search (only in PV nodes)
1373 // Search only for possible new PV nodes, if instead value >= beta then
1374 // parent node fails low with value <= alpha and tries another move.
1375 if (PvNode && value > alpha && value < beta)
1376 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1380 // Step 16. Undo move
1381 pos.undo_move(move);
1383 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1385 // Step 17. Check for new best move
1388 lock_grab(&(sp->lock));
1389 bestValue = sp->bestValue;
1393 if (value > bestValue && !(SpNode && ThreadsMgr.cutoff_at_splitpoint(threadID)))
1398 sp->bestValue = value;
1402 if (PvNode && value < beta) // We want always alpha < beta
1410 sp->betaCutoff = true;
1412 if (value == value_mate_in(ply + 1))
1413 ss->mateKiller = move;
1415 ss->bestMove = move;
1418 sp->parentSstack->bestMove = move;
1422 // Step 18. Check for split
1424 && depth >= ThreadsMgr.min_split_depth()
1425 && ThreadsMgr.active_threads() > 1
1427 && ThreadsMgr.available_thread_exists(threadID)
1429 && !ThreadsMgr.cutoff_at_splitpoint(threadID)
1431 ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1432 threatMove, mateThreat, moveCount, &mp, PvNode);
1435 // Step 19. Check for mate and stalemate
1436 // All legal moves have been searched and if there are
1437 // no legal moves, it must be mate or stalemate.
1438 // If one move was excluded return fail low score.
1439 if (!SpNode && !moveCount)
1440 return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW;
1442 // Step 20. Update tables
1443 // If the search is not aborted, update the transposition table,
1444 // history counters, and killer moves.
1445 if (!SpNode && !AbortSearch && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1447 move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
1448 vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
1449 : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
1451 TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, ss->evalMargin);
1453 // Update killers and history only for non capture moves that fails high
1454 if ( bestValue >= beta
1455 && !pos.move_is_capture_or_promotion(move))
1457 update_history(pos, move, depth, movesSearched, moveCount);
1458 update_killers(move, ss);
1464 // Here we have the lock still grabbed
1465 sp->slaves[threadID] = 0;
1466 sp->nodes += pos.nodes_searched();
1467 lock_release(&(sp->lock));
1470 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1475 // qsearch() is the quiescence search function, which is called by the main
1476 // search function when the remaining depth is zero (or, to be more precise,
1477 // less than ONE_PLY).
1479 template <NodeType PvNode>
1480 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1482 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1483 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1484 assert(PvNode || alpha == beta - 1);
1486 assert(ply > 0 && ply < PLY_MAX);
1487 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1491 Value bestValue, value, evalMargin, futilityValue, futilityBase;
1492 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1495 Value oldAlpha = alpha;
1497 ss->bestMove = ss->currentMove = MOVE_NONE;
1499 // Check for an instant draw or maximum ply reached
1500 if (pos.is_draw() || ply >= PLY_MAX - 1)
1503 // Decide whether or not to include checks, this fixes also the type of
1504 // TT entry depth that we are going to use. Note that in qsearch we use
1505 // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
1506 isCheck = pos.is_check();
1507 ttDepth = (isCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS);
1509 // Transposition table lookup. At PV nodes, we don't use the TT for
1510 // pruning, but only for move ordering.
1511 tte = TT.retrieve(pos.get_key());
1512 ttMove = (tte ? tte->move() : MOVE_NONE);
1514 if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ply))
1516 ss->bestMove = ttMove; // Can be MOVE_NONE
1517 return value_from_tt(tte->value(), ply);
1520 // Evaluate the position statically
1523 bestValue = futilityBase = -VALUE_INFINITE;
1524 ss->eval = evalMargin = VALUE_NONE;
1525 enoughMaterial = false;
1531 assert(tte->static_value() != VALUE_NONE);
1533 evalMargin = tte->static_value_margin();
1534 ss->eval = bestValue = tte->static_value();
1537 ss->eval = bestValue = evaluate(pos, evalMargin);
1539 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1541 // Stand pat. Return immediately if static value is at least beta
1542 if (bestValue >= beta)
1545 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1550 if (PvNode && bestValue > alpha)
1553 // Futility pruning parameters, not needed when in check
1554 futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1555 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1558 // Initialize a MovePicker object for the current position, and prepare
1559 // to search the moves. Because the depth is <= 0 here, only captures,
1560 // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
1562 MovePicker mp(pos, ttMove, depth, H);
1565 // Loop through the moves until no moves remain or a beta cutoff occurs
1566 while ( alpha < beta
1567 && (move = mp.get_next_move()) != MOVE_NONE)
1569 assert(move_is_ok(move));
1571 moveIsCheck = pos.move_is_check(move, ci);
1579 && !move_is_promotion(move)
1580 && !pos.move_is_passed_pawn_push(move))
1582 futilityValue = futilityBase
1583 + pos.endgame_value_of_piece_on(move_to(move))
1584 + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1586 if (futilityValue < alpha)
1588 if (futilityValue > bestValue)
1589 bestValue = futilityValue;
1594 // Detect non-capture evasions that are candidate to be pruned
1595 evasionPrunable = isCheck
1596 && bestValue > value_mated_in(PLY_MAX)
1597 && !pos.move_is_capture(move)
1598 && !pos.can_castle(pos.side_to_move());
1600 // Don't search moves with negative SEE values
1602 && (!isCheck || evasionPrunable)
1604 && !move_is_promotion(move)
1605 && pos.see_sign(move) < 0)
1608 // Don't search useless checks
1613 && !pos.move_is_capture_or_promotion(move)
1614 && ss->eval + PawnValueMidgame / 4 < beta
1615 && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue))
1617 if (ss->eval + PawnValueMidgame / 4 > bestValue)
1618 bestValue = ss->eval + PawnValueMidgame / 4;
1623 // Update current move
1624 ss->currentMove = move;
1626 // Make and search the move
1627 pos.do_move(move, st, ci, moveIsCheck);
1628 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1);
1629 pos.undo_move(move);
1631 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1634 if (value > bestValue)
1640 ss->bestMove = move;
1645 // All legal moves have been searched. A special case: If we're in check
1646 // and no legal moves were found, it is checkmate.
1647 if (isCheck && bestValue == -VALUE_INFINITE)
1648 return value_mated_in(ply);
1650 // Update transposition table
1651 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1652 TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin);
1654 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1660 // check_is_dangerous() tests if a checking move can be pruned in qsearch().
1661 // bestValue is updated only when returning false because in that case move
1664 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bestValue)
1666 Bitboard b, occ, oldAtt, newAtt, kingAtt;
1667 Square from, to, ksq, victimSq;
1670 Value futilityValue, bv = *bestValue;
1672 from = move_from(move);
1674 them = opposite_color(pos.side_to_move());
1675 ksq = pos.king_square(them);
1676 kingAtt = pos.attacks_from<KING>(ksq);
1677 pc = pos.piece_on(from);
1679 occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL << ksq);
1680 oldAtt = pos.attacks_from(pc, from, occ);
1681 newAtt = pos.attacks_from(pc, to, occ);
1683 // Rule 1. Checks which give opponent's king at most one escape square are dangerous
1684 b = kingAtt & ~pos.pieces_of_color(them) & ~newAtt & ~(1ULL << to);
1686 if (!(b && (b & (b - 1))))
1689 // Rule 2. Queen contact check is very dangerous
1690 if ( type_of_piece(pc) == QUEEN
1691 && bit_is_set(kingAtt, to))
1694 // Rule 3. Creating new double threats with checks
1695 b = pos.pieces_of_color(them) & newAtt & ~oldAtt & ~(1ULL << ksq);
1699 victimSq = pop_1st_bit(&b);
1700 futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq);
1702 // Note that here we generate illegal "double move"!
1703 if ( futilityValue >= beta
1704 && pos.see_sign(make_move(from, victimSq)) >= 0)
1707 if (futilityValue > bv)
1711 // Update bestValue only if check is not dangerous (because we will prune the move)
1717 // connected_moves() tests whether two moves are 'connected' in the sense
1718 // that the first move somehow made the second move possible (for instance
1719 // if the moving piece is the same in both moves). The first move is assumed
1720 // to be the move that was made to reach the current position, while the
1721 // second move is assumed to be a move from the current position.
1723 bool connected_moves(const Position& pos, Move m1, Move m2) {
1725 Square f1, t1, f2, t2;
1728 assert(m1 && move_is_ok(m1));
1729 assert(m2 && move_is_ok(m2));
1731 // Case 1: The moving piece is the same in both moves
1737 // Case 2: The destination square for m2 was vacated by m1
1743 // Case 3: Moving through the vacated square
1744 if ( piece_is_slider(pos.piece_on(f2))
1745 && bit_is_set(squares_between(f2, t2), f1))
1748 // Case 4: The destination square for m2 is defended by the moving piece in m1
1749 p = pos.piece_on(t1);
1750 if (bit_is_set(pos.attacks_from(p, t1), t2))
1753 // Case 5: Discovered check, checking piece is the piece moved in m1
1754 if ( piece_is_slider(p)
1755 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1756 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1758 // discovered_check_candidates() works also if the Position's side to
1759 // move is the opposite of the checking piece.
1760 Color them = opposite_color(pos.side_to_move());
1761 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1763 if (bit_is_set(dcCandidates, f2))
1770 // value_is_mate() checks if the given value is a mate one eventually
1771 // compensated for the ply.
1773 bool value_is_mate(Value value) {
1775 assert(abs(value) <= VALUE_INFINITE);
1777 return value <= value_mated_in(PLY_MAX)
1778 || value >= value_mate_in(PLY_MAX);
1782 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1783 // "plies to mate from the current ply". Non-mate scores are unchanged.
1784 // The function is called before storing a value to the transposition table.
1786 Value value_to_tt(Value v, int ply) {
1788 if (v >= value_mate_in(PLY_MAX))
1791 if (v <= value_mated_in(PLY_MAX))
1798 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1799 // the transposition table to a mate score corrected for the current ply.
1801 Value value_from_tt(Value v, int ply) {
1803 if (v >= value_mate_in(PLY_MAX))
1806 if (v <= value_mated_in(PLY_MAX))
1813 // extension() decides whether a move should be searched with normal depth,
1814 // or with extended depth. Certain classes of moves (checking moves, in
1815 // particular) are searched with bigger depth than ordinary moves and in
1816 // any case are marked as 'dangerous'. Note that also if a move is not
1817 // extended, as example because the corresponding UCI option is set to zero,
1818 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1819 template <NodeType PvNode>
1820 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1821 bool singleEvasion, bool mateThreat, bool* dangerous) {
1823 assert(m != MOVE_NONE);
1825 Depth result = DEPTH_ZERO;
1826 *dangerous = moveIsCheck | singleEvasion | mateThreat;
1830 if (moveIsCheck && pos.see_sign(m) >= 0)
1831 result += CheckExtension[PvNode];
1834 result += SingleEvasionExtension[PvNode];
1837 result += MateThreatExtension[PvNode];
1840 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1842 Color c = pos.side_to_move();
1843 if (relative_rank(c, move_to(m)) == RANK_7)
1845 result += PawnPushTo7thExtension[PvNode];
1848 if (pos.pawn_is_passed(c, move_to(m)))
1850 result += PassedPawnExtension[PvNode];
1855 if ( captureOrPromotion
1856 && pos.type_of_piece_on(move_to(m)) != PAWN
1857 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1858 - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1859 && !move_is_promotion(m)
1862 result += PawnEndgameExtension[PvNode];
1867 && captureOrPromotion
1868 && pos.type_of_piece_on(move_to(m)) != PAWN
1869 && pos.see_sign(m) >= 0)
1871 result += ONE_PLY / 2;
1875 return Min(result, ONE_PLY);
1879 // connected_threat() tests whether it is safe to forward prune a move or if
1880 // is somehow coonected to the threat move returned by null search.
1882 bool connected_threat(const Position& pos, Move m, Move threat) {
1884 assert(move_is_ok(m));
1885 assert(threat && move_is_ok(threat));
1886 assert(!pos.move_is_check(m));
1887 assert(!pos.move_is_capture_or_promotion(m));
1888 assert(!pos.move_is_passed_pawn_push(m));
1890 Square mfrom, mto, tfrom, tto;
1892 mfrom = move_from(m);
1894 tfrom = move_from(threat);
1895 tto = move_to(threat);
1897 // Case 1: Don't prune moves which move the threatened piece
1901 // Case 2: If the threatened piece has value less than or equal to the
1902 // value of the threatening piece, don't prune move which defend it.
1903 if ( pos.move_is_capture(threat)
1904 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1905 || pos.type_of_piece_on(tfrom) == KING)
1906 && pos.move_attacks_square(m, tto))
1909 // Case 3: If the moving piece in the threatened move is a slider, don't
1910 // prune safe moves which block its ray.
1911 if ( piece_is_slider(pos.piece_on(tfrom))
1912 && bit_is_set(squares_between(tfrom, tto), mto)
1913 && pos.see_sign(m) >= 0)
1920 // ok_to_use_TT() returns true if a transposition table score
1921 // can be used at a given point in search.
1923 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1925 Value v = value_from_tt(tte->value(), ply);
1927 return ( tte->depth() >= depth
1928 || v >= Max(value_mate_in(PLY_MAX), beta)
1929 || v < Min(value_mated_in(PLY_MAX), beta))
1931 && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1932 || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1936 // refine_eval() returns the transposition table score if
1937 // possible otherwise falls back on static position evaluation.
1939 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1943 Value v = value_from_tt(tte->value(), ply);
1945 if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1946 || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1953 // update_history() registers a good move that produced a beta-cutoff
1954 // in history and marks as failures all the other moves of that ply.
1956 void update_history(const Position& pos, Move move, Depth depth,
1957 Move movesSearched[], int moveCount) {
1960 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
1962 for (int i = 0; i < moveCount - 1; i++)
1964 m = movesSearched[i];
1968 if (!pos.move_is_capture_or_promotion(m))
1969 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
1974 // update_killers() add a good move that produced a beta-cutoff
1975 // among the killer moves of that ply.
1977 void update_killers(Move m, SearchStack* ss) {
1979 if (m == ss->killers[0])
1982 ss->killers[1] = ss->killers[0];
1987 // update_gains() updates the gains table of a non-capture move given
1988 // the static position evaluation before and after the move.
1990 void update_gains(const Position& pos, Move m, Value before, Value after) {
1993 && before != VALUE_NONE
1994 && after != VALUE_NONE
1995 && pos.captured_piece_type() == PIECE_TYPE_NONE
1996 && !move_is_special(m))
1997 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
2001 // current_search_time() returns the number of milliseconds which have passed
2002 // since the beginning of the current search.
2004 int current_search_time() {
2006 return get_system_time() - SearchStartTime;
2010 // value_to_uci() converts a value to a string suitable for use with the UCI protocol
2012 std::string value_to_uci(Value v) {
2014 std::stringstream s;
2016 if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
2017 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100
2019 s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
2024 // nps() computes the current nodes/second count.
2026 int nps(const Position& pos) {
2028 int t = current_search_time();
2029 return (t > 0 ? int((pos.nodes_searched() * 1000) / t) : 0);
2033 // poll() performs two different functions: It polls for user input, and it
2034 // looks at the time consumed so far and decides if it's time to abort the
2037 void poll(const Position& pos) {
2039 static int lastInfoTime;
2040 int t = current_search_time();
2043 if (data_available())
2045 // We are line oriented, don't read single chars
2046 std::string command;
2048 if (!std::getline(std::cin, command))
2051 if (command == "quit")
2054 PonderSearch = false;
2058 else if (command == "stop")
2061 PonderSearch = false;
2063 else if (command == "ponderhit")
2067 // Print search information
2071 else if (lastInfoTime > t)
2072 // HACK: Must be a new search where we searched less than
2073 // NodesBetweenPolls nodes during the first second of search.
2076 else if (t - lastInfoTime >= 1000)
2083 if (dbg_show_hit_rate)
2084 dbg_print_hit_rate();
2086 cout << "info nodes " << pos.nodes_searched() << " nps " << nps(pos)
2087 << " time " << t << endl;
2090 // Should we stop the search?
2094 bool stillAtFirstMove = FirstRootMove
2095 && !AspirationFailLow
2096 && t > TimeMgr.available_time();
2098 bool noMoreTime = t > TimeMgr.maximum_time()
2099 || stillAtFirstMove;
2101 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2102 || (ExactMaxTime && t >= ExactMaxTime)
2103 || (Iteration >= 3 && MaxNodes && pos.nodes_searched() >= MaxNodes))
2108 // ponderhit() is called when the program is pondering (i.e. thinking while
2109 // it's the opponent's turn to move) in order to let the engine know that
2110 // it correctly predicted the opponent's move.
2114 int t = current_search_time();
2115 PonderSearch = false;
2117 bool stillAtFirstMove = FirstRootMove
2118 && !AspirationFailLow
2119 && t > TimeMgr.available_time();
2121 bool noMoreTime = t > TimeMgr.maximum_time()
2122 || stillAtFirstMove;
2124 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2129 // init_ss_array() does a fast reset of the first entries of a SearchStack
2130 // array and of all the excludedMove and skipNullMove entries.
2132 void init_ss_array(SearchStack* ss, int size) {
2134 for (int i = 0; i < size; i++, ss++)
2136 ss->excludedMove = MOVE_NONE;
2137 ss->skipNullMove = false;
2138 ss->reduction = DEPTH_ZERO;
2142 ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE;
2147 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2148 // while the program is pondering. The point is to work around a wrinkle in
2149 // the UCI protocol: When pondering, the engine is not allowed to give a
2150 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2151 // We simply wait here until one of these commands is sent, and return,
2152 // after which the bestmove and pondermove will be printed (in id_loop()).
2154 void wait_for_stop_or_ponderhit() {
2156 std::string command;
2160 if (!std::getline(std::cin, command))
2163 if (command == "quit")
2168 else if (command == "ponderhit" || command == "stop")
2174 // print_pv_info() prints to standard output and eventually to log file information on
2175 // the current PV line. It is called at each iteration or after a new pv is found.
2177 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) {
2179 cout << "info depth " << Iteration
2180 << " score " << value_to_uci(value)
2181 << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
2182 << " time " << current_search_time()
2183 << " nodes " << pos.nodes_searched()
2184 << " nps " << nps(pos)
2187 for (Move* m = pv; *m != MOVE_NONE; m++)
2194 ValueType t = value >= beta ? VALUE_TYPE_LOWER :
2195 value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
2197 LogFile << pretty_pv(pos, current_search_time(), Iteration, value, t, pv) << endl;
2202 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2203 // the PV back into the TT. This makes sure the old PV moves are searched
2204 // first, even if the old TT entries have been overwritten.
2206 void insert_pv_in_tt(const Position& pos, Move pv[]) {
2210 Position p(pos, pos.thread());
2211 Value v, m = VALUE_NONE;
2213 for (int i = 0; pv[i] != MOVE_NONE; i++)
2215 tte = TT.retrieve(p.get_key());
2216 if (!tte || tte->move() != pv[i])
2218 v = (p.is_check() ? VALUE_NONE : evaluate(p, m));
2219 TT.store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[i], v, m);
2221 p.do_move(pv[i], st);
2226 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2227 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2228 // allow to always have a ponder move even when we fail high at root and also a
2229 // long PV to print that is important for position analysis.
2231 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]) {
2235 Position p(pos, pos.thread());
2238 assert(bestMove != MOVE_NONE);
2241 p.do_move(pv[ply++], st);
2243 while ( (tte = TT.retrieve(p.get_key())) != NULL
2244 && tte->move() != MOVE_NONE
2245 && move_is_legal(p, tte->move())
2247 && (!p.is_draw() || ply < 2))
2249 pv[ply] = tte->move();
2250 p.do_move(pv[ply++], st);
2252 pv[ply] = MOVE_NONE;
2256 // init_thread() is the function which is called when a new thread is
2257 // launched. It simply calls the idle_loop() function with the supplied
2258 // threadID. There are two versions of this function; one for POSIX
2259 // threads and one for Windows threads.
2261 #if !defined(_MSC_VER)
2263 void* init_thread(void* threadID) {
2265 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2271 DWORD WINAPI init_thread(LPVOID threadID) {
2273 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2280 /// The ThreadsManager class
2283 // read_uci_options() updates number of active threads and other internal
2284 // parameters according to the UCI options values. It is called before
2285 // to start a new search.
2287 void ThreadsManager::read_uci_options() {
2289 maxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value<int>();
2290 minimumSplitDepth = Options["Minimum Split Depth"].value<int>() * ONE_PLY;
2291 useSleepingThreads = Options["Use Sleeping Threads"].value<bool>();
2292 activeThreads = Options["Threads"].value<int>();
2296 // idle_loop() is where the threads are parked when they have no work to do.
2297 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2298 // object for which the current thread is the master.
2300 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2302 assert(threadID >= 0 && threadID < MAX_THREADS);
2305 bool allFinished = false;
2309 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2310 // master should exit as last one.
2311 if (allThreadsShouldExit)
2314 threads[threadID].state = THREAD_TERMINATED;
2318 // If we are not thinking, wait for a condition to be signaled
2319 // instead of wasting CPU time polling for work.
2320 while ( threadID >= activeThreads || threads[threadID].state == THREAD_INITIALIZING
2321 || (useSleepingThreads && threads[threadID].state == THREAD_AVAILABLE))
2323 assert(!sp || useSleepingThreads);
2324 assert(threadID != 0 || useSleepingThreads);
2326 if (threads[threadID].state == THREAD_INITIALIZING)
2327 threads[threadID].state = THREAD_AVAILABLE;
2329 // Grab the lock to avoid races with wake_sleeping_thread()
2330 lock_grab(&sleepLock[threadID]);
2332 // If we are master and all slaves have finished do not go to sleep
2333 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2334 allFinished = (i == activeThreads);
2336 if (allFinished || allThreadsShouldExit)
2338 lock_release(&sleepLock[threadID]);
2342 // Do sleep here after retesting sleep conditions
2343 if (threadID >= activeThreads || threads[threadID].state == THREAD_AVAILABLE)
2344 cond_wait(&sleepCond[threadID], &sleepLock[threadID]);
2346 lock_release(&sleepLock[threadID]);
2349 // If this thread has been assigned work, launch a search
2350 if (threads[threadID].state == THREAD_WORKISWAITING)
2352 assert(!allThreadsShouldExit);
2354 threads[threadID].state = THREAD_SEARCHING;
2356 // Here we call search() with SplitPoint template parameter set to true
2357 SplitPoint* tsp = threads[threadID].splitPoint;
2358 Position pos(*tsp->pos, threadID);
2359 SearchStack* ss = tsp->sstack[threadID] + 1;
2363 search<PV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2365 search<NonPV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2367 assert(threads[threadID].state == THREAD_SEARCHING);
2369 threads[threadID].state = THREAD_AVAILABLE;
2371 // Wake up master thread so to allow it to return from the idle loop in
2372 // case we are the last slave of the split point.
2373 if (useSleepingThreads && threadID != tsp->master && threads[tsp->master].state == THREAD_AVAILABLE)
2374 wake_sleeping_thread(tsp->master);
2377 // If this thread is the master of a split point and all slaves have
2378 // finished their work at this split point, return from the idle loop.
2379 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2380 allFinished = (i == activeThreads);
2384 // Because sp->slaves[] is reset under lock protection,
2385 // be sure sp->lock has been released before to return.
2386 lock_grab(&(sp->lock));
2387 lock_release(&(sp->lock));
2389 // In helpful master concept a master can help only a sub-tree, and
2390 // because here is all finished is not possible master is booked.
2391 assert(threads[threadID].state == THREAD_AVAILABLE);
2393 threads[threadID].state = THREAD_SEARCHING;
2400 // init_threads() is called during startup. It launches all helper threads,
2401 // and initializes the split point stack and the global locks and condition
2404 void ThreadsManager::init_threads() {
2406 int i, arg[MAX_THREADS];
2409 // Initialize global locks
2412 for (i = 0; i < MAX_THREADS; i++)
2414 lock_init(&sleepLock[i]);
2415 cond_init(&sleepCond[i]);
2418 // Initialize splitPoints[] locks
2419 for (i = 0; i < MAX_THREADS; i++)
2420 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2421 lock_init(&(threads[i].splitPoints[j].lock));
2423 // Will be set just before program exits to properly end the threads
2424 allThreadsShouldExit = false;
2426 // Threads will be put all threads to sleep as soon as created
2429 // All threads except the main thread should be initialized to THREAD_INITIALIZING
2430 threads[0].state = THREAD_SEARCHING;
2431 for (i = 1; i < MAX_THREADS; i++)
2432 threads[i].state = THREAD_INITIALIZING;
2434 // Launch the helper threads
2435 for (i = 1; i < MAX_THREADS; i++)
2439 #if !defined(_MSC_VER)
2440 pthread_t pthread[1];
2441 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
2442 pthread_detach(pthread[0]);
2444 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
2448 cout << "Failed to create thread number " << i << endl;
2452 // Wait until the thread has finished launching and is gone to sleep
2453 while (threads[i].state == THREAD_INITIALIZING) {}
2458 // exit_threads() is called when the program exits. It makes all the
2459 // helper threads exit cleanly.
2461 void ThreadsManager::exit_threads() {
2463 allThreadsShouldExit = true; // Let the woken up threads to exit idle_loop()
2465 // Wake up all the threads and waits for termination
2466 for (int i = 1; i < MAX_THREADS; i++)
2468 wake_sleeping_thread(i);
2469 while (threads[i].state != THREAD_TERMINATED) {}
2472 // Now we can safely destroy the locks
2473 for (int i = 0; i < MAX_THREADS; i++)
2474 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2475 lock_destroy(&(threads[i].splitPoints[j].lock));
2477 lock_destroy(&mpLock);
2479 // Now we can safely destroy the wait conditions
2480 for (int i = 0; i < MAX_THREADS; i++)
2482 lock_destroy(&sleepLock[i]);
2483 cond_destroy(&sleepCond[i]);
2488 // cutoff_at_splitpoint() checks whether a beta cutoff has occurred in
2489 // the thread's currently active split point, or in some ancestor of
2490 // the current split point.
2492 bool ThreadsManager::cutoff_at_splitpoint(int threadID) const {
2494 assert(threadID >= 0 && threadID < activeThreads);
2496 SplitPoint* sp = threads[threadID].splitPoint;
2498 for ( ; sp && !sp->betaCutoff; sp = sp->parent) {}
2503 // thread_is_available() checks whether the thread with threadID "slave" is
2504 // available to help the thread with threadID "master" at a split point. An
2505 // obvious requirement is that "slave" must be idle. With more than two
2506 // threads, this is not by itself sufficient: If "slave" is the master of
2507 // some active split point, it is only available as a slave to the other
2508 // threads which are busy searching the split point at the top of "slave"'s
2509 // split point stack (the "helpful master concept" in YBWC terminology).
2511 bool ThreadsManager::thread_is_available(int slave, int master) const {
2513 assert(slave >= 0 && slave < activeThreads);
2514 assert(master >= 0 && master < activeThreads);
2515 assert(activeThreads > 1);
2517 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2520 // Make a local copy to be sure doesn't change under our feet
2521 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2523 // No active split points means that the thread is available as
2524 // a slave for any other thread.
2525 if (localActiveSplitPoints == 0 || activeThreads == 2)
2528 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2529 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2530 // could have been set to 0 by another thread leading to an out of bound access.
2531 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2538 // available_thread_exists() tries to find an idle thread which is available as
2539 // a slave for the thread with threadID "master".
2541 bool ThreadsManager::available_thread_exists(int master) const {
2543 assert(master >= 0 && master < activeThreads);
2544 assert(activeThreads > 1);
2546 for (int i = 0; i < activeThreads; i++)
2547 if (thread_is_available(i, master))
2554 // split() does the actual work of distributing the work at a node between
2555 // several available threads. If it does not succeed in splitting the
2556 // node (because no idle threads are available, or because we have no unused
2557 // split point objects), the function immediately returns. If splitting is
2558 // possible, a SplitPoint object is initialized with all the data that must be
2559 // copied to the helper threads and we tell our helper threads that they have
2560 // been assigned work. This will cause them to instantly leave their idle loops and
2561 // call search().When all threads have returned from search() then split() returns.
2563 template <bool Fake>
2564 void ThreadsManager::split(Position& pos, SearchStack* ss, int ply, Value* alpha,
2565 const Value beta, Value* bestValue, Depth depth, Move threatMove,
2566 bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) {
2567 assert(pos.is_ok());
2568 assert(ply > 0 && ply < PLY_MAX);
2569 assert(*bestValue >= -VALUE_INFINITE);
2570 assert(*bestValue <= *alpha);
2571 assert(*alpha < beta);
2572 assert(beta <= VALUE_INFINITE);
2573 assert(depth > DEPTH_ZERO);
2574 assert(pos.thread() >= 0 && pos.thread() < activeThreads);
2575 assert(activeThreads > 1);
2577 int i, master = pos.thread();
2578 Thread& masterThread = threads[master];
2582 // If no other thread is available to help us, or if we have too many
2583 // active split points, don't split.
2584 if ( !available_thread_exists(master)
2585 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2587 lock_release(&mpLock);
2591 // Pick the next available split point object from the split point stack
2592 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2594 // Initialize the split point object
2595 splitPoint.parent = masterThread.splitPoint;
2596 splitPoint.master = master;
2597 splitPoint.betaCutoff = false;
2598 splitPoint.ply = ply;
2599 splitPoint.depth = depth;
2600 splitPoint.threatMove = threatMove;
2601 splitPoint.mateThreat = mateThreat;
2602 splitPoint.alpha = *alpha;
2603 splitPoint.beta = beta;
2604 splitPoint.pvNode = pvNode;
2605 splitPoint.bestValue = *bestValue;
2607 splitPoint.moveCount = moveCount;
2608 splitPoint.pos = &pos;
2609 splitPoint.nodes = 0;
2610 splitPoint.parentSstack = ss;
2611 for (i = 0; i < activeThreads; i++)
2612 splitPoint.slaves[i] = 0;
2614 masterThread.splitPoint = &splitPoint;
2616 // If we are here it means we are not available
2617 assert(masterThread.state != THREAD_AVAILABLE);
2619 int workersCnt = 1; // At least the master is included
2621 // Allocate available threads setting state to THREAD_BOOKED
2622 for (i = 0; !Fake && i < activeThreads && workersCnt < maxThreadsPerSplitPoint; i++)
2623 if (thread_is_available(i, master))
2625 threads[i].state = THREAD_BOOKED;
2626 threads[i].splitPoint = &splitPoint;
2627 splitPoint.slaves[i] = 1;
2631 assert(Fake || workersCnt > 1);
2633 // We can release the lock because slave threads are already booked and master is not available
2634 lock_release(&mpLock);
2636 // Tell the threads that they have work to do. This will make them leave
2637 // their idle loop. But before copy search stack tail for each thread.
2638 for (i = 0; i < activeThreads; i++)
2639 if (i == master || splitPoint.slaves[i])
2641 memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
2643 assert(i == master || threads[i].state == THREAD_BOOKED);
2645 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2647 if (useSleepingThreads && i != master)
2648 wake_sleeping_thread(i);
2651 // Everything is set up. The master thread enters the idle loop, from
2652 // which it will instantly launch a search, because its state is
2653 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2654 // idle loop, which means that the main thread will return from the idle
2655 // loop when all threads have finished their work at this split point.
2656 idle_loop(master, &splitPoint);
2658 // We have returned from the idle loop, which means that all threads are
2659 // finished. Update alpha and bestValue, and return.
2662 *alpha = splitPoint.alpha;
2663 *bestValue = splitPoint.bestValue;
2664 masterThread.activeSplitPoints--;
2665 masterThread.splitPoint = splitPoint.parent;
2666 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
2668 lock_release(&mpLock);
2672 // wake_sleeping_thread() wakes up the thread with the given threadID
2673 // when it is time to start a new search.
2675 void ThreadsManager::wake_sleeping_thread(int threadID) {
2677 lock_grab(&sleepLock[threadID]);
2678 cond_signal(&sleepCond[threadID]);
2679 lock_release(&sleepLock[threadID]);
2683 /// The RootMoveList class
2685 // RootMoveList c'tor
2687 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) {
2689 SearchStack ss[PLY_MAX_PLUS_2];
2690 MoveStack mlist[MOVES_MAX];
2692 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
2694 // Initialize search stack
2695 init_ss_array(ss, PLY_MAX_PLUS_2);
2696 ss[0].eval = ss[0].evalMargin = VALUE_NONE;
2698 // Generate all legal moves
2699 MoveStack* last = generate_moves(pos, mlist);
2701 // Add each move to the moves[] array
2702 for (MoveStack* cur = mlist; cur != last; cur++)
2704 bool includeMove = includeAllMoves;
2706 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
2707 includeMove = (searchMoves[k] == cur->move);
2712 // Find a quick score for the move and add to the list
2714 rm.move = ss[0].currentMove = rm.pv[0] = cur->move;
2715 rm.pv[1] = MOVE_NONE;
2716 pos.do_move(cur->move, st);
2717 rm.pv_score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
2718 pos.undo_move(cur->move);
2724 // Score root moves using the standard way used in main search, the moves
2725 // are scored according to the order in which are returned by MovePicker.
2726 // This is the second order score that is used to compare the moves when
2727 // the first order pv scores of both moves are equal.
2729 void RootMoveList::set_non_pv_scores(const Position& pos)
2732 Value score = VALUE_ZERO;
2733 MovePicker mp(pos, MOVE_NONE, ONE_PLY, H);
2735 while ((move = mp.get_next_move()) != MOVE_NONE)
2736 for (Base::iterator it = begin(); it != end(); ++it)
2737 if (it->move == move)
2739 it->non_pv_score = score--;