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 pvScore is normally set at
111 // -VALUE_INFINITE for all non-pv moves, while nonPvScore is computed
112 // according to the order in which moves are returned by MovePicker.
116 RootMove() : nodes(0) { pv_score = non_pv_score = -VALUE_INFINITE; }
118 // RootMove::operator<() is the comparison function used when
119 // sorting the moves. A move m1 is considered to be better
120 // than a move m2 if it has an higher pvScore, or if it has
121 // equal pvScore but m1 has the higher nonPvScore. In this way
122 // we are guaranteed that PV moves are always sorted as first.
123 bool operator<(const RootMove& m) const {
124 return pv_score != m.pv_score ? pv_score < m.pv_score : non_pv_score <= m.non_pv_score;
126 void set_pv(const Move newPv[]);
132 Move pv[PLY_MAX_PLUS_2];
135 void RootMove::set_pv(const Move newPv[]) {
139 while (newPv[++i] != MOVE_NONE)
146 // The RootMoveList struct is essentially a std::vector<> of RootMove objects,
147 // with an handful of methods above the standard ones.
149 struct RootMoveList : public std::vector<RootMove> {
151 typedef std::vector<RootMove> Base;
153 RootMoveList(Position& pos, Move searchMoves[]);
154 void sort() { sort_multipv((int)size() - 1); } // Sort all items
156 void set_non_pv_scores(const Position& pos);
157 void sort_multipv(int n);
161 // When formatting a move for std::cout we must know if we are in Chess960
162 // or not. To keep using the handy operator<<() on the move the trick is to
163 // embed this flag in the stream itself. Function-like named enum set960 is
164 // used as a custom manipulator and the stream internal general-purpose array,
165 // accessed through ios_base::iword(), is used to pass the flag to the move's
166 // operator<<() that will use it to properly format castling moves.
169 std::ostream& operator<< (std::ostream& os, const set960& m) {
171 os.iword(0) = int(m);
180 // Maximum depth for razoring
181 const Depth RazorDepth = 4 * ONE_PLY;
183 // Dynamic razoring margin based on depth
184 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
186 // Maximum depth for use of dynamic threat detection when null move fails low
187 const Depth ThreatDepth = 5 * ONE_PLY;
189 // Step 9. Internal iterative deepening
191 // Minimum depth for use of internal iterative deepening
192 const Depth IIDDepth[2] = { 8 * ONE_PLY /* non-PV */, 5 * ONE_PLY /* PV */};
194 // At Non-PV nodes we do an internal iterative deepening search
195 // when the static evaluation is bigger then beta - IIDMargin.
196 const Value IIDMargin = Value(0x100);
198 // Step 11. Decide the new search depth
200 // Extensions. Configurable UCI options
201 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
202 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
203 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
205 // Minimum depth for use of singular extension
206 const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */};
208 // If the TT move is at least SingularExtensionMargin better then the
209 // remaining ones we will extend it.
210 const Value SingularExtensionMargin = Value(0x20);
212 // Step 12. Futility pruning
214 // Futility margin for quiescence search
215 const Value FutilityMarginQS = Value(0x80);
217 // Futility lookup tables (initialized at startup) and their getter functions
218 Value FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
219 int FutilityMoveCountArray[32]; // [depth]
221 inline Value futility_margin(Depth d, int mn) { return d < 7 * ONE_PLY ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE; }
222 inline int futility_move_count(Depth d) { return d < 16 * ONE_PLY ? FutilityMoveCountArray[d] : 512; }
224 // Step 14. Reduced search
226 // Reduction lookup tables (initialized at startup) and their getter functions
227 int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
229 template <NodeType PV>
230 inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
232 // Common adjustments
234 // Search depth at iteration 1
235 const Depth InitialDepth = ONE_PLY;
237 // Easy move margin. An easy move candidate must be at least this much
238 // better than the second best move.
239 const Value EasyMoveMargin = Value(0x200);
242 /// Namespace variables
250 // Scores and number of times the best move changed for each iteration
251 Value ValueByIteration[PLY_MAX_PLUS_2];
252 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
254 // Search window management
260 // Time managment variables
261 int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
262 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
263 bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
268 std::ofstream LogFile;
270 // Multi-threads manager object
271 ThreadsManager ThreadsMgr;
273 // Node counters, used only by thread[0] but try to keep in different cache
274 // lines (64 bytes each) from the heavy multi-thread read accessed variables.
276 int NodesBetweenPolls = 30000;
283 Value id_loop(Position& pos, Move searchMoves[]);
284 Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
286 template <NodeType PvNode, bool SpNode>
287 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
289 template <NodeType PvNode>
290 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
292 template <NodeType PvNode>
293 inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
295 return depth < ONE_PLY ? qsearch<PvNode>(pos, ss, alpha, beta, DEPTH_ZERO, ply)
296 : search<PvNode, false>(pos, ss, alpha, beta, depth, ply);
299 template <NodeType PvNode>
300 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
302 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue);
303 bool connected_moves(const Position& pos, Move m1, Move m2);
304 bool value_is_mate(Value value);
305 Value value_to_tt(Value v, int ply);
306 Value value_from_tt(Value v, int ply);
307 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
308 bool connected_threat(const Position& pos, Move m, Move threat);
309 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
310 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
311 void update_killers(Move m, SearchStack* ss);
312 void update_gains(const Position& pos, Move move, Value before, Value after);
314 int current_search_time();
315 std::string value_to_uci(Value v);
316 int nps(const Position& pos);
317 void poll(const Position& pos);
319 void wait_for_stop_or_ponderhit();
320 void init_ss_array(SearchStack* ss, int size);
321 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value);
322 void insert_pv_in_tt(const Position& pos, Move pv[]);
323 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]);
325 #if !defined(_MSC_VER)
326 void* init_thread(void* threadID);
328 DWORD WINAPI init_thread(LPVOID threadID);
338 /// init_threads(), exit_threads() and nodes_searched() are helpers to
339 /// give accessibility to some TM methods from outside of current file.
341 void init_threads() { ThreadsMgr.init_threads(); }
342 void exit_threads() { ThreadsMgr.exit_threads(); }
345 /// init_search() is called during startup. It initializes various lookup tables
349 int d; // depth (ONE_PLY == 2)
350 int hd; // half depth (ONE_PLY == 1)
353 // Init reductions array
354 for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
356 double pvRed = log(double(hd)) * log(double(mc)) / 3.0;
357 double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
358 ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0);
359 ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0);
362 // Init futility margins array
363 for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
364 FutilityMarginsMatrix[d][mc] = Value(112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45);
366 // Init futility move count array
367 for (d = 0; d < 32; d++)
368 FutilityMoveCountArray[d] = int(3.001 + 0.25 * pow(d, 2.0));
372 /// perft() is our utility to verify move generation is bug free. All the legal
373 /// moves up to given depth are generated and counted and the sum returned.
375 int perft(Position& pos, Depth depth)
377 MoveStack mlist[MOVES_MAX];
382 // Generate all legal moves
383 MoveStack* last = generate_moves(pos, mlist);
385 // If we are at the last ply we don't need to do and undo
386 // the moves, just to count them.
387 if (depth <= ONE_PLY)
388 return int(last - mlist);
390 // Loop through all legal moves
392 for (MoveStack* cur = mlist; cur != last; cur++)
395 pos.do_move(m, st, ci, pos.move_is_check(m, ci));
396 sum += perft(pos, depth - ONE_PLY);
403 /// think() is the external interface to Stockfish's search, and is called when
404 /// the program receives the UCI 'go' command. It initializes various
405 /// search-related global variables, and calls root_search(). It returns false
406 /// when a quit command is received during the search.
408 bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[],
409 int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) {
411 // Initialize global search variables
412 StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
414 SearchStartTime = get_system_time();
415 ExactMaxTime = maxTime;
418 InfiniteSearch = infinite;
419 PonderSearch = ponder;
420 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
422 // Look for a book move, only during games, not tests
423 if (UseTimeManagement && Options["OwnBook"].value<bool>())
425 if (Options["Book File"].value<std::string>() != OpeningBook.file_name())
426 OpeningBook.open(Options["Book File"].value<std::string>());
428 Move bookMove = OpeningBook.get_move(pos, Options["Best Book Move"].value<bool>());
429 if (bookMove != MOVE_NONE)
432 wait_for_stop_or_ponderhit();
434 cout << "bestmove " << bookMove << endl;
439 // Read UCI option values
440 TT.set_size(Options["Hash"].value<int>());
441 if (Options["Clear Hash"].value<bool>())
443 Options["Clear Hash"].set_value("false");
447 CheckExtension[1] = Options["Check Extension (PV nodes)"].value<Depth>();
448 CheckExtension[0] = Options["Check Extension (non-PV nodes)"].value<Depth>();
449 SingleEvasionExtension[1] = Options["Single Evasion Extension (PV nodes)"].value<Depth>();
450 SingleEvasionExtension[0] = Options["Single Evasion Extension (non-PV nodes)"].value<Depth>();
451 PawnPushTo7thExtension[1] = Options["Pawn Push to 7th Extension (PV nodes)"].value<Depth>();
452 PawnPushTo7thExtension[0] = Options["Pawn Push to 7th Extension (non-PV nodes)"].value<Depth>();
453 PassedPawnExtension[1] = Options["Passed Pawn Extension (PV nodes)"].value<Depth>();
454 PassedPawnExtension[0] = Options["Passed Pawn Extension (non-PV nodes)"].value<Depth>();
455 PawnEndgameExtension[1] = Options["Pawn Endgame Extension (PV nodes)"].value<Depth>();
456 PawnEndgameExtension[0] = Options["Pawn Endgame Extension (non-PV nodes)"].value<Depth>();
457 MateThreatExtension[1] = Options["Mate Threat Extension (PV nodes)"].value<Depth>();
458 MateThreatExtension[0] = Options["Mate Threat Extension (non-PV nodes)"].value<Depth>();
459 MultiPV = Options["MultiPV"].value<int>();
460 UseLogFile = Options["Use Search Log"].value<bool>();
463 LogFile.open(Options["Search Log Filename"].value<std::string>().c_str(), std::ios::out | std::ios::app);
465 read_weights(pos.side_to_move());
467 // Set the number of active threads
468 ThreadsMgr.read_uci_options();
469 init_eval(ThreadsMgr.active_threads());
471 // Wake up needed threads
472 for (int i = 1; i < ThreadsMgr.active_threads(); i++)
473 ThreadsMgr.wake_sleeping_thread(i);
476 int myTime = time[pos.side_to_move()];
477 int myIncrement = increment[pos.side_to_move()];
478 if (UseTimeManagement)
479 TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter());
481 // Set best NodesBetweenPolls interval to avoid lagging under
482 // heavy time pressure.
484 NodesBetweenPolls = Min(MaxNodes, 30000);
485 else if (myTime && myTime < 1000)
486 NodesBetweenPolls = 1000;
487 else if (myTime && myTime < 5000)
488 NodesBetweenPolls = 5000;
490 NodesBetweenPolls = 30000;
492 // Write search information to log file
494 LogFile << "Searching: " << pos.to_fen() << endl
495 << "infinite: " << infinite
496 << " ponder: " << ponder
497 << " time: " << myTime
498 << " increment: " << myIncrement
499 << " moves to go: " << movesToGo << endl;
501 // We're ready to start thinking. Call the iterative deepening loop function
502 id_loop(pos, searchMoves);
507 // This makes all the threads to go to sleep
508 ThreadsMgr.set_active_threads(1);
516 // id_loop() is the main iterative deepening loop. It calls root_search
517 // repeatedly with increasing depth until the allocated thinking time has
518 // been consumed, the user stops the search, or the maximum search depth is
521 Value id_loop(Position& pos, Move searchMoves[]) {
523 SearchStack ss[PLY_MAX_PLUS_2];
524 Move pv[PLY_MAX_PLUS_2];
525 Move EasyMove = MOVE_NONE;
526 Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
528 // Moves to search are verified, copied, scored and sorted
529 RootMoveList rml(pos, searchMoves);
531 // Handle special case of searching on a mate/stale position
535 wait_for_stop_or_ponderhit();
537 return pos.is_check() ? -VALUE_MATE : VALUE_DRAW;
540 // Print RootMoveList startup scoring to the standard output,
541 // so to output information also for iteration 1.
542 cout << set960(pos.is_chess960()) // Is enough to set once at the beginning
543 << "info depth " << 1
544 << "\ninfo depth " << 1
545 << " score " << value_to_uci(rml[0].pv_score)
546 << " time " << current_search_time()
547 << " nodes " << pos.nodes_searched()
548 << " nps " << nps(pos)
549 << " pv " << rml[0].move << "\n";
554 init_ss_array(ss, PLY_MAX_PLUS_2);
555 pv[0] = pv[1] = MOVE_NONE;
556 ValueByIteration[1] = rml[0].pv_score;
559 // Is one move significantly better than others after initial scoring ?
561 || rml[0].pv_score > rml[1].pv_score + EasyMoveMargin)
562 EasyMove = rml[0].move;
564 // Iterative deepening loop
565 while (Iteration < PLY_MAX)
567 // Initialize iteration
569 BestMoveChangesByIteration[Iteration] = 0;
571 cout << "info depth " << Iteration << endl;
573 // Calculate dynamic aspiration window based on previous iterations
574 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
576 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
577 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
579 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
580 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
582 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
583 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
586 // Search to the current depth, rml is updated and sorted, alpha and beta could change
587 value = root_search(pos, ss, pv, rml, &alpha, &beta);
589 // Write PV to transposition table, in case the relevant entries have
590 // been overwritten during the search.
591 insert_pv_in_tt(pos, pv);
594 break; // Value cannot be trusted. Break out immediately!
596 //Save info about search result
597 ValueByIteration[Iteration] = value;
599 // Drop the easy move if differs from the new best move
600 if (pv[0] != EasyMove)
601 EasyMove = MOVE_NONE;
603 if (UseTimeManagement)
606 bool stopSearch = false;
608 // Stop search early if there is only a single legal move,
609 // we search up to Iteration 6 anyway to get a proper score.
610 if (Iteration >= 6 && rml.size() == 1)
613 // Stop search early when the last two iterations returned a mate score
615 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
616 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
619 // Stop search early if one move seems to be much better than the others
622 && ( ( rml[0].nodes > (pos.nodes_searched() * 85) / 100
623 && current_search_time() > TimeMgr.available_time() / 16)
624 ||( rml[0].nodes > (pos.nodes_searched() * 98) / 100
625 && current_search_time() > TimeMgr.available_time() / 32)))
628 // Add some extra time if the best move has changed during the last two iterations
629 if (Iteration > 5 && Iteration <= 50)
630 TimeMgr.pv_instability(BestMoveChangesByIteration[Iteration],
631 BestMoveChangesByIteration[Iteration-1]);
633 // Stop search if most of MaxSearchTime is consumed at the end of the
634 // iteration. We probably don't have enough time to search the first
635 // move at the next iteration anyway.
636 if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
642 StopOnPonderhit = true;
648 if (MaxDepth && Iteration >= MaxDepth)
652 // If we are pondering or in infinite search, we shouldn't print the
653 // best move before we are told to do so.
654 if (!AbortSearch && (PonderSearch || InfiniteSearch))
655 wait_for_stop_or_ponderhit();
657 // Print final search statistics
658 cout << "info nodes " << pos.nodes_searched()
659 << " nps " << nps(pos)
660 << " time " << current_search_time() << endl;
662 // Print the best move and the ponder move to the standard output
663 if (pv[0] == MOVE_NONE || MultiPV > 1)
669 assert(pv[0] != MOVE_NONE);
671 cout << "bestmove " << pv[0];
673 if (pv[1] != MOVE_NONE)
674 cout << " ponder " << pv[1];
681 dbg_print_mean(LogFile);
683 if (dbg_show_hit_rate)
684 dbg_print_hit_rate(LogFile);
686 LogFile << "\nNodes: " << pos.nodes_searched()
687 << "\nNodes/second: " << nps(pos)
688 << "\nBest move: " << move_to_san(pos, pv[0]);
691 pos.do_move(pv[0], st);
692 LogFile << "\nPonder move: "
693 << move_to_san(pos, pv[1]) // Works also with MOVE_NONE
696 return rml[0].pv_score;
700 // root_search() is the function which searches the root node. It is
701 // similar to search_pv except that it uses a different move ordering
702 // scheme, prints some information to the standard output and handles
703 // the fail low/high loops.
705 Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
711 Depth depth, ext, newDepth;
712 Value value, alpha, beta;
713 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
714 int researchCountFH, researchCountFL;
716 researchCountFH = researchCountFL = 0;
719 isCheck = pos.is_check();
720 depth = (Iteration - 2) * ONE_PLY + InitialDepth;
722 // Step 1. Initialize node (polling is omitted at root)
723 ss->currentMove = ss->bestMove = MOVE_NONE;
725 // Step 2. Check for aborted search (omitted at root)
726 // Step 3. Mate distance pruning (omitted at root)
727 // Step 4. Transposition table lookup (omitted at root)
729 // Step 5. Evaluate the position statically
730 // At root we do this only to get reference value for child nodes
731 ss->evalMargin = VALUE_NONE;
732 ss->eval = isCheck ? VALUE_NONE : evaluate(pos, ss->evalMargin);
734 // Step 6. Razoring (omitted at root)
735 // Step 7. Static null move pruning (omitted at root)
736 // Step 8. Null move search with verification search (omitted at root)
737 // Step 9. Internal iterative deepening (omitted at root)
739 // Step extra. Fail low loop
740 // We start with small aspiration window and in case of fail low, we research
741 // with bigger window until we are not failing low anymore.
744 // Sort the moves before to (re)search
745 rml.set_non_pv_scores(pos);
748 // Step 10. Loop through all moves in the root move list
749 for (int i = 0; i < (int)rml.size() && !AbortSearch; i++)
751 // This is used by time management
752 FirstRootMove = (i == 0);
754 // Save the current node count before the move is searched
755 nodes = pos.nodes_searched();
757 // Pick the next root move, and print the move and the move number to
758 // the standard output.
759 move = ss->currentMove = rml[i].move;
761 if (current_search_time() >= 1000)
762 cout << "info currmove " << move
763 << " currmovenumber " << i + 1 << endl;
765 moveIsCheck = pos.move_is_check(move);
766 captureOrPromotion = pos.move_is_capture_or_promotion(move);
768 // Step 11. Decide the new search depth
769 ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
770 newDepth = depth + ext;
772 // Step 12. Futility pruning (omitted at root)
774 // Step extra. Fail high loop
775 // If move fails high, we research with bigger window until we are not failing
777 value = -VALUE_INFINITE;
781 // Step 13. Make the move
782 pos.do_move(move, st, ci, moveIsCheck);
784 // Step extra. pv search
785 // We do pv search for first moves (i < MultiPV)
786 // and for fail high research (value > alpha)
787 if (i < MultiPV || value > alpha)
789 // Aspiration window is disabled in multi-pv case
791 alpha = -VALUE_INFINITE;
793 // Full depth PV search, done on first move or after a fail high
794 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
798 // Step 14. Reduced search
799 // if the move fails high will be re-searched at full depth
800 bool doFullDepthSearch = true;
802 if ( depth >= 3 * ONE_PLY
804 && !captureOrPromotion
805 && !move_is_castle(move))
807 ss->reduction = reduction<PV>(depth, i - MultiPV + 2);
810 assert(newDepth-ss->reduction >= ONE_PLY);
812 // Reduced depth non-pv search using alpha as upperbound
813 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
814 doFullDepthSearch = (value > alpha);
817 // The move failed high, but if reduction is very big we could
818 // face a false positive, retry with a less aggressive reduction,
819 // if the move fails high again then go with full depth search.
820 if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
822 assert(newDepth - ONE_PLY >= ONE_PLY);
824 ss->reduction = ONE_PLY;
825 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
826 doFullDepthSearch = (value > alpha);
828 ss->reduction = DEPTH_ZERO; // Restore original reduction
831 // Step 15. Full depth search
832 if (doFullDepthSearch)
834 // Full depth non-pv search using alpha as upperbound
835 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, 1);
837 // If we are above alpha then research at same depth but as PV
838 // to get a correct score or eventually a fail high above beta.
840 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
844 // Step 16. Undo move
847 // Can we exit fail high loop ?
848 if (AbortSearch || value < beta)
851 // We are failing high and going to do a research. It's important to update
852 // the score before research in case we run out of time while researching.
853 rml[i].pv_score = value;
855 extract_pv_from_tt(pos, move, pv);
858 // Print information to the standard output
859 print_pv_info(pos, pv, alpha, beta, value);
861 // Prepare for a research after a fail high, each time with a wider window
862 *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
865 } // End of fail high loop
867 // Finished searching the move. If AbortSearch is true, the search
868 // was aborted because the user interrupted the search or because we
869 // ran out of time. In this case, the return value of the search cannot
870 // be trusted, and we break out of the loop without updating the best
875 // Remember searched nodes counts for this move
876 rml[i].nodes += pos.nodes_searched() - nodes;
878 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
879 assert(value < beta);
881 // Step 17. Check for new best move
882 if (value <= alpha && i >= MultiPV)
883 rml[i].pv_score = -VALUE_INFINITE;
886 // PV move or new best move!
889 rml[i].pv_score = value;
891 extract_pv_from_tt(pos, move, pv);
896 // We record how often the best move has been changed in each
897 // iteration. This information is used for time managment: When
898 // the best move changes frequently, we allocate some more time.
900 BestMoveChangesByIteration[Iteration]++;
902 // Print information to the standard output
903 print_pv_info(pos, pv, alpha, beta, value);
905 // Raise alpha to setup proper non-pv search upper bound
912 for (int j = 0; j < Min(MultiPV, (int)rml.size()); j++)
914 cout << "info multipv " << j + 1
915 << " score " << value_to_uci(rml[j].pv_score)
916 << " depth " << (j <= i ? Iteration : Iteration - 1)
917 << " time " << current_search_time()
918 << " nodes " << pos.nodes_searched()
919 << " nps " << nps(pos)
922 for (int k = 0; rml[j].pv[k] != MOVE_NONE && k < PLY_MAX; k++)
923 cout << rml[j].pv[k] << " ";
927 alpha = rml[Min(i, MultiPV - 1)].pv_score;
929 } // PV move or new best move
931 assert(alpha >= *alphaPtr);
933 AspirationFailLow = (alpha == *alphaPtr);
935 if (AspirationFailLow && StopOnPonderhit)
936 StopOnPonderhit = false;
939 // Can we exit fail low loop ?
940 if (AbortSearch || !AspirationFailLow)
943 // Prepare for a research after a fail low, each time with a wider window
944 *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
949 // Sort the moves before to return
956 // search<>() is the main search function for both PV and non-PV nodes and for
957 // normal and SplitPoint nodes. When called just after a split point the search
958 // is simpler because we have already probed the hash table, done a null move
959 // search, and searched the first move before splitting, we don't have to repeat
960 // all this work again. We also don't need to store anything to the hash table
961 // here: This is taken care of after we return from the split point.
963 template <NodeType PvNode, bool SpNode>
964 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
966 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
967 assert(beta > alpha && beta <= VALUE_INFINITE);
968 assert(PvNode || alpha == beta - 1);
969 assert(ply > 0 && ply < PLY_MAX);
970 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
972 Move movesSearched[MOVES_MAX];
976 Move ttMove, move, excludedMove, threatMove;
979 Value bestValue, value, oldAlpha;
980 Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
981 bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
982 bool mateThreat = false;
984 int threadID = pos.thread();
985 SplitPoint* sp = NULL;
986 refinedValue = bestValue = value = -VALUE_INFINITE;
988 isCheck = pos.is_check();
994 ttMove = excludedMove = MOVE_NONE;
995 threatMove = sp->threatMove;
996 mateThreat = sp->mateThreat;
997 goto split_point_start;
999 else {} // Hack to fix icc's "statement is unreachable" warning
1001 // Step 1. Initialize node and poll. Polling can abort search
1002 ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
1003 (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
1005 if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
1011 // Step 2. Check for aborted search and immediate draw
1013 || ThreadsMgr.cutoff_at_splitpoint(threadID)
1015 || ply >= PLY_MAX - 1)
1018 // Step 3. Mate distance pruning
1019 alpha = Max(value_mated_in(ply), alpha);
1020 beta = Min(value_mate_in(ply+1), beta);
1024 // Step 4. Transposition table lookup
1026 // We don't want the score of a partial search to overwrite a previous full search
1027 // TT value, so we use a different position key in case of an excluded move exists.
1028 excludedMove = ss->excludedMove;
1029 posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1031 tte = TT.retrieve(posKey);
1032 ttMove = tte ? tte->move() : MOVE_NONE;
1034 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1035 // This is to avoid problems in the following areas:
1037 // * Repetition draw detection
1038 // * Fifty move rule detection
1039 // * Searching for a mate
1040 // * Printing of full PV line
1041 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1044 ss->bestMove = ttMove; // Can be MOVE_NONE
1045 return value_from_tt(tte->value(), ply);
1048 // Step 5. Evaluate the position statically and
1049 // update gain statistics of parent move.
1051 ss->eval = ss->evalMargin = VALUE_NONE;
1054 assert(tte->static_value() != VALUE_NONE);
1056 ss->eval = tte->static_value();
1057 ss->evalMargin = tte->static_value_margin();
1058 refinedValue = refine_eval(tte, ss->eval, ply);
1062 refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
1063 TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
1066 // Save gain for the parent non-capture move
1067 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1069 // Step 6. Razoring (is omitted in PV nodes)
1071 && depth < RazorDepth
1073 && refinedValue < beta - razor_margin(depth)
1074 && ttMove == MOVE_NONE
1075 && !value_is_mate(beta)
1076 && !pos.has_pawn_on_7th(pos.side_to_move()))
1078 Value rbeta = beta - razor_margin(depth);
1079 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply);
1081 // Logically we should return (v + razor_margin(depth)), but
1082 // surprisingly this did slightly weaker in tests.
1086 // Step 7. Static null move pruning (is omitted in PV nodes)
1087 // We're betting that the opponent doesn't have a move that will reduce
1088 // the score by more than futility_margin(depth) if we do a null move.
1090 && !ss->skipNullMove
1091 && depth < RazorDepth
1093 && refinedValue >= beta + futility_margin(depth, 0)
1094 && !value_is_mate(beta)
1095 && pos.non_pawn_material(pos.side_to_move()))
1096 return refinedValue - futility_margin(depth, 0);
1098 // Step 8. Null move search with verification search (is omitted in PV nodes)
1100 && !ss->skipNullMove
1103 && refinedValue >= beta
1104 && !value_is_mate(beta)
1105 && pos.non_pawn_material(pos.side_to_move()))
1107 ss->currentMove = MOVE_NULL;
1109 // Null move dynamic reduction based on depth
1110 int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
1112 // Null move dynamic reduction based on value
1113 if (refinedValue - beta > PawnValueMidgame)
1116 pos.do_null_move(st);
1117 (ss+1)->skipNullMove = true;
1118 nullValue = -search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1);
1119 (ss+1)->skipNullMove = false;
1120 pos.undo_null_move();
1122 if (nullValue >= beta)
1124 // Do not return unproven mate scores
1125 if (nullValue >= value_mate_in(PLY_MAX))
1128 if (depth < 6 * ONE_PLY)
1131 // Do verification search at high depths
1132 ss->skipNullMove = true;
1133 Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY, ply);
1134 ss->skipNullMove = false;
1141 // The null move failed low, which means that we may be faced with
1142 // some kind of threat. If the previous move was reduced, check if
1143 // the move that refuted the null move was somehow connected to the
1144 // move which was reduced. If a connection is found, return a fail
1145 // low score (which will cause the reduced move to fail high in the
1146 // parent node, which will trigger a re-search with full depth).
1147 if (nullValue == value_mated_in(ply + 2))
1150 threatMove = (ss+1)->bestMove;
1151 if ( depth < ThreatDepth
1152 && (ss-1)->reduction
1153 && threatMove != MOVE_NONE
1154 && connected_moves(pos, (ss-1)->currentMove, threatMove))
1159 // Step 9. Internal iterative deepening
1160 if ( depth >= IIDDepth[PvNode]
1161 && ttMove == MOVE_NONE
1162 && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
1164 Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
1166 ss->skipNullMove = true;
1167 search<PvNode>(pos, ss, alpha, beta, d, ply);
1168 ss->skipNullMove = false;
1170 ttMove = ss->bestMove;
1171 tte = TT.retrieve(posKey);
1174 // Expensive mate threat detection (only for PV nodes)
1176 mateThreat = pos.has_mate_threat();
1178 split_point_start: // At split points actual search starts from here
1180 // Initialize a MovePicker object for the current position
1181 // FIXME currently MovePicker() c'tor is needless called also in SplitPoint
1182 MovePicker mpBase(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
1183 MovePicker& mp = SpNode ? *sp->mp : mpBase;
1185 ss->bestMove = MOVE_NONE;
1186 singleEvasion = !SpNode && isCheck && mp.number_of_evasions() == 1;
1187 futilityBase = ss->eval + ss->evalMargin;
1188 singularExtensionNode = !SpNode
1189 && depth >= SingularExtensionDepth[PvNode]
1192 && !excludedMove // Do not allow recursive singular extension search
1193 && (tte->type() & VALUE_TYPE_LOWER)
1194 && tte->depth() >= depth - 3 * ONE_PLY;
1197 lock_grab(&(sp->lock));
1198 bestValue = sp->bestValue;
1201 // Step 10. Loop through moves
1202 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1203 while ( bestValue < beta
1204 && (move = mp.get_next_move()) != MOVE_NONE
1205 && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1207 assert(move_is_ok(move));
1211 moveCount = ++sp->moveCount;
1212 lock_release(&(sp->lock));
1214 else if (move == excludedMove)
1217 movesSearched[moveCount++] = move;
1219 moveIsCheck = pos.move_is_check(move, ci);
1220 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1222 // Step 11. Decide the new search depth
1223 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1225 // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s),
1226 // and just one fails high on (alpha, beta), then that move is singular and should be extended.
1227 // To verify this we do a reduced search on all the other moves but the ttMove, if result is
1228 // lower then ttValue minus a margin then we extend ttMove.
1229 if ( singularExtensionNode
1230 && move == tte->move()
1233 Value ttValue = value_from_tt(tte->value(), ply);
1235 if (abs(ttValue) < VALUE_KNOWN_WIN)
1237 Value b = ttValue - SingularExtensionMargin;
1238 ss->excludedMove = move;
1239 ss->skipNullMove = true;
1240 Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
1241 ss->skipNullMove = false;
1242 ss->excludedMove = MOVE_NONE;
1243 ss->bestMove = MOVE_NONE;
1249 // Update current move (this must be done after singular extension search)
1250 ss->currentMove = move;
1251 newDepth = depth - ONE_PLY + ext;
1253 // Step 12. Futility pruning (is omitted in PV nodes)
1255 && !captureOrPromotion
1259 && !move_is_castle(move))
1261 // Move count based pruning
1262 if ( moveCount >= futility_move_count(depth)
1263 && !(threatMove && connected_threat(pos, move, threatMove))
1264 && bestValue > value_mated_in(PLY_MAX)) // FIXME bestValue is racy
1267 lock_grab(&(sp->lock));
1272 // Value based pruning
1273 // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
1274 // but fixing this made program slightly weaker.
1275 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1276 futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount)
1277 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1279 if (futilityValueScaled < beta)
1283 lock_grab(&(sp->lock));
1284 if (futilityValueScaled > sp->bestValue)
1285 sp->bestValue = bestValue = futilityValueScaled;
1287 else if (futilityValueScaled > bestValue)
1288 bestValue = futilityValueScaled;
1293 // Prune moves with negative SEE at low depths
1294 if ( predictedDepth < 2 * ONE_PLY
1295 && bestValue > value_mated_in(PLY_MAX)
1296 && pos.see_sign(move) < 0)
1299 lock_grab(&(sp->lock));
1305 // Step 13. Make the move
1306 pos.do_move(move, st, ci, moveIsCheck);
1308 // Step extra. pv search (only in PV nodes)
1309 // The first move in list is the expected PV
1310 if (PvNode && moveCount == 1)
1311 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1314 // Step 14. Reduced depth search
1315 // If the move fails high will be re-searched at full depth.
1316 bool doFullDepthSearch = true;
1318 if ( depth >= 3 * ONE_PLY
1319 && !captureOrPromotion
1321 && !move_is_castle(move)
1322 && ss->killers[0] != move
1323 && ss->killers[1] != move)
1325 ss->reduction = reduction<PvNode>(depth, moveCount);
1329 alpha = SpNode ? sp->alpha : alpha;
1330 Depth d = newDepth - ss->reduction;
1331 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1333 doFullDepthSearch = (value > alpha);
1336 // The move failed high, but if reduction is very big we could
1337 // face a false positive, retry with a less aggressive reduction,
1338 // if the move fails high again then go with full depth search.
1339 if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
1341 assert(newDepth - ONE_PLY >= ONE_PLY);
1343 ss->reduction = ONE_PLY;
1344 alpha = SpNode ? sp->alpha : alpha;
1345 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, ply+1);
1346 doFullDepthSearch = (value > alpha);
1348 ss->reduction = DEPTH_ZERO; // Restore original reduction
1351 // Step 15. Full depth search
1352 if (doFullDepthSearch)
1354 alpha = SpNode ? sp->alpha : alpha;
1355 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1357 // Step extra. pv search (only in PV nodes)
1358 // Search only for possible new PV nodes, if instead value >= beta then
1359 // parent node fails low with value <= alpha and tries another move.
1360 if (PvNode && value > alpha && value < beta)
1361 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1365 // Step 16. Undo move
1366 pos.undo_move(move);
1368 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1370 // Step 17. Check for new best move
1373 lock_grab(&(sp->lock));
1374 bestValue = sp->bestValue;
1378 if (value > bestValue && !(SpNode && ThreadsMgr.cutoff_at_splitpoint(threadID)))
1383 sp->bestValue = value;
1387 if (PvNode && value < beta) // We want always alpha < beta
1395 sp->betaCutoff = true;
1397 if (value == value_mate_in(ply + 1))
1398 ss->mateKiller = move;
1400 ss->bestMove = move;
1403 sp->parentSstack->bestMove = move;
1407 // Step 18. Check for split
1409 && depth >= ThreadsMgr.min_split_depth()
1410 && ThreadsMgr.active_threads() > 1
1412 && ThreadsMgr.available_thread_exists(threadID)
1414 && !ThreadsMgr.cutoff_at_splitpoint(threadID)
1416 ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1417 threatMove, mateThreat, moveCount, &mp, PvNode);
1420 // Step 19. Check for mate and stalemate
1421 // All legal moves have been searched and if there are
1422 // no legal moves, it must be mate or stalemate.
1423 // If one move was excluded return fail low score.
1424 if (!SpNode && !moveCount)
1425 return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW;
1427 // Step 20. Update tables
1428 // If the search is not aborted, update the transposition table,
1429 // history counters, and killer moves.
1430 if (!SpNode && !AbortSearch && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1432 move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
1433 vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
1434 : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
1436 TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, ss->evalMargin);
1438 // Update killers and history only for non capture moves that fails high
1439 if ( bestValue >= beta
1440 && !pos.move_is_capture_or_promotion(move))
1442 update_history(pos, move, depth, movesSearched, moveCount);
1443 update_killers(move, ss);
1449 // Here we have the lock still grabbed
1450 sp->slaves[threadID] = 0;
1451 sp->nodes += pos.nodes_searched();
1452 lock_release(&(sp->lock));
1455 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1460 // qsearch() is the quiescence search function, which is called by the main
1461 // search function when the remaining depth is zero (or, to be more precise,
1462 // less than ONE_PLY).
1464 template <NodeType PvNode>
1465 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1467 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1468 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1469 assert(PvNode || alpha == beta - 1);
1471 assert(ply > 0 && ply < PLY_MAX);
1472 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1476 Value bestValue, value, evalMargin, futilityValue, futilityBase;
1477 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1480 Value oldAlpha = alpha;
1482 ss->bestMove = ss->currentMove = MOVE_NONE;
1484 // Check for an instant draw or maximum ply reached
1485 if (pos.is_draw() || ply >= PLY_MAX - 1)
1488 // Decide whether or not to include checks, this fixes also the type of
1489 // TT entry depth that we are going to use. Note that in qsearch we use
1490 // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
1491 isCheck = pos.is_check();
1492 ttDepth = (isCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS);
1494 // Transposition table lookup. At PV nodes, we don't use the TT for
1495 // pruning, but only for move ordering.
1496 tte = TT.retrieve(pos.get_key());
1497 ttMove = (tte ? tte->move() : MOVE_NONE);
1499 if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ply))
1501 ss->bestMove = ttMove; // Can be MOVE_NONE
1502 return value_from_tt(tte->value(), ply);
1505 // Evaluate the position statically
1508 bestValue = futilityBase = -VALUE_INFINITE;
1509 ss->eval = evalMargin = VALUE_NONE;
1510 enoughMaterial = false;
1516 assert(tte->static_value() != VALUE_NONE);
1518 evalMargin = tte->static_value_margin();
1519 ss->eval = bestValue = tte->static_value();
1522 ss->eval = bestValue = evaluate(pos, evalMargin);
1524 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1526 // Stand pat. Return immediately if static value is at least beta
1527 if (bestValue >= beta)
1530 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1535 if (PvNode && bestValue > alpha)
1538 // Futility pruning parameters, not needed when in check
1539 futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1540 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1543 // Initialize a MovePicker object for the current position, and prepare
1544 // to search the moves. Because the depth is <= 0 here, only captures,
1545 // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
1547 MovePicker mp(pos, ttMove, depth, H);
1550 // Loop through the moves until no moves remain or a beta cutoff occurs
1551 while ( alpha < beta
1552 && (move = mp.get_next_move()) != MOVE_NONE)
1554 assert(move_is_ok(move));
1556 moveIsCheck = pos.move_is_check(move, ci);
1564 && !move_is_promotion(move)
1565 && !pos.move_is_passed_pawn_push(move))
1567 futilityValue = futilityBase
1568 + pos.endgame_value_of_piece_on(move_to(move))
1569 + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1571 if (futilityValue < alpha)
1573 if (futilityValue > bestValue)
1574 bestValue = futilityValue;
1579 // Detect non-capture evasions that are candidate to be pruned
1580 evasionPrunable = isCheck
1581 && bestValue > value_mated_in(PLY_MAX)
1582 && !pos.move_is_capture(move)
1583 && !pos.can_castle(pos.side_to_move());
1585 // Don't search moves with negative SEE values
1587 && (!isCheck || evasionPrunable)
1589 && !move_is_promotion(move)
1590 && pos.see_sign(move) < 0)
1593 // Don't search useless checks
1598 && !pos.move_is_capture_or_promotion(move)
1599 && ss->eval + PawnValueMidgame / 4 < beta
1600 && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue))
1602 if (ss->eval + PawnValueMidgame / 4 > bestValue)
1603 bestValue = ss->eval + PawnValueMidgame / 4;
1608 // Update current move
1609 ss->currentMove = move;
1611 // Make and search the move
1612 pos.do_move(move, st, ci, moveIsCheck);
1613 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1);
1614 pos.undo_move(move);
1616 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1619 if (value > bestValue)
1625 ss->bestMove = move;
1630 // All legal moves have been searched. A special case: If we're in check
1631 // and no legal moves were found, it is checkmate.
1632 if (isCheck && bestValue == -VALUE_INFINITE)
1633 return value_mated_in(ply);
1635 // Update transposition table
1636 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1637 TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin);
1639 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1645 // check_is_dangerous() tests if a checking move can be pruned in qsearch().
1646 // bestValue is updated only when returning false because in that case move
1649 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bestValue)
1651 Bitboard b, occ, oldAtt, newAtt, kingAtt;
1652 Square from, to, ksq, victimSq;
1655 Value futilityValue, bv = *bestValue;
1657 from = move_from(move);
1659 them = opposite_color(pos.side_to_move());
1660 ksq = pos.king_square(them);
1661 kingAtt = pos.attacks_from<KING>(ksq);
1662 pc = pos.piece_on(from);
1664 occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL << ksq);
1665 oldAtt = pos.attacks_from(pc, from, occ);
1666 newAtt = pos.attacks_from(pc, to, occ);
1668 // Rule 1. Checks which give opponent's king at most one escape square are dangerous
1669 b = kingAtt & ~pos.pieces_of_color(them) & ~newAtt & ~(1ULL << to);
1671 if (!(b && (b & (b - 1))))
1674 // Rule 2. Queen contact check is very dangerous
1675 if ( type_of_piece(pc) == QUEEN
1676 && bit_is_set(kingAtt, to))
1679 // Rule 3. Creating new double threats with checks
1680 b = pos.pieces_of_color(them) & newAtt & ~oldAtt & ~(1ULL << ksq);
1684 victimSq = pop_1st_bit(&b);
1685 futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq);
1687 // Note that here we generate illegal "double move"!
1688 if ( futilityValue >= beta
1689 && pos.see_sign(make_move(from, victimSq)) >= 0)
1692 if (futilityValue > bv)
1696 // Update bestValue only if check is not dangerous (because we will prune the move)
1702 // connected_moves() tests whether two moves are 'connected' in the sense
1703 // that the first move somehow made the second move possible (for instance
1704 // if the moving piece is the same in both moves). The first move is assumed
1705 // to be the move that was made to reach the current position, while the
1706 // second move is assumed to be a move from the current position.
1708 bool connected_moves(const Position& pos, Move m1, Move m2) {
1710 Square f1, t1, f2, t2;
1713 assert(m1 && move_is_ok(m1));
1714 assert(m2 && move_is_ok(m2));
1716 // Case 1: The moving piece is the same in both moves
1722 // Case 2: The destination square for m2 was vacated by m1
1728 // Case 3: Moving through the vacated square
1729 if ( piece_is_slider(pos.piece_on(f2))
1730 && bit_is_set(squares_between(f2, t2), f1))
1733 // Case 4: The destination square for m2 is defended by the moving piece in m1
1734 p = pos.piece_on(t1);
1735 if (bit_is_set(pos.attacks_from(p, t1), t2))
1738 // Case 5: Discovered check, checking piece is the piece moved in m1
1739 if ( piece_is_slider(p)
1740 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1741 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1743 // discovered_check_candidates() works also if the Position's side to
1744 // move is the opposite of the checking piece.
1745 Color them = opposite_color(pos.side_to_move());
1746 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1748 if (bit_is_set(dcCandidates, f2))
1755 // value_is_mate() checks if the given value is a mate one eventually
1756 // compensated for the ply.
1758 bool value_is_mate(Value value) {
1760 assert(abs(value) <= VALUE_INFINITE);
1762 return value <= value_mated_in(PLY_MAX)
1763 || value >= value_mate_in(PLY_MAX);
1767 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1768 // "plies to mate from the current ply". Non-mate scores are unchanged.
1769 // The function is called before storing a value to the transposition table.
1771 Value value_to_tt(Value v, int ply) {
1773 if (v >= value_mate_in(PLY_MAX))
1776 if (v <= value_mated_in(PLY_MAX))
1783 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1784 // the transposition table to a mate score corrected for the current ply.
1786 Value value_from_tt(Value v, int ply) {
1788 if (v >= value_mate_in(PLY_MAX))
1791 if (v <= value_mated_in(PLY_MAX))
1798 // extension() decides whether a move should be searched with normal depth,
1799 // or with extended depth. Certain classes of moves (checking moves, in
1800 // particular) are searched with bigger depth than ordinary moves and in
1801 // any case are marked as 'dangerous'. Note that also if a move is not
1802 // extended, as example because the corresponding UCI option is set to zero,
1803 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1804 template <NodeType PvNode>
1805 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1806 bool singleEvasion, bool mateThreat, bool* dangerous) {
1808 assert(m != MOVE_NONE);
1810 Depth result = DEPTH_ZERO;
1811 *dangerous = moveIsCheck | singleEvasion | mateThreat;
1815 if (moveIsCheck && pos.see_sign(m) >= 0)
1816 result += CheckExtension[PvNode];
1819 result += SingleEvasionExtension[PvNode];
1822 result += MateThreatExtension[PvNode];
1825 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1827 Color c = pos.side_to_move();
1828 if (relative_rank(c, move_to(m)) == RANK_7)
1830 result += PawnPushTo7thExtension[PvNode];
1833 if (pos.pawn_is_passed(c, move_to(m)))
1835 result += PassedPawnExtension[PvNode];
1840 if ( captureOrPromotion
1841 && pos.type_of_piece_on(move_to(m)) != PAWN
1842 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1843 - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1844 && !move_is_promotion(m)
1847 result += PawnEndgameExtension[PvNode];
1852 && captureOrPromotion
1853 && pos.type_of_piece_on(move_to(m)) != PAWN
1854 && pos.see_sign(m) >= 0)
1856 result += ONE_PLY / 2;
1860 return Min(result, ONE_PLY);
1864 // connected_threat() tests whether it is safe to forward prune a move or if
1865 // is somehow coonected to the threat move returned by null search.
1867 bool connected_threat(const Position& pos, Move m, Move threat) {
1869 assert(move_is_ok(m));
1870 assert(threat && move_is_ok(threat));
1871 assert(!pos.move_is_check(m));
1872 assert(!pos.move_is_capture_or_promotion(m));
1873 assert(!pos.move_is_passed_pawn_push(m));
1875 Square mfrom, mto, tfrom, tto;
1877 mfrom = move_from(m);
1879 tfrom = move_from(threat);
1880 tto = move_to(threat);
1882 // Case 1: Don't prune moves which move the threatened piece
1886 // Case 2: If the threatened piece has value less than or equal to the
1887 // value of the threatening piece, don't prune move which defend it.
1888 if ( pos.move_is_capture(threat)
1889 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1890 || pos.type_of_piece_on(tfrom) == KING)
1891 && pos.move_attacks_square(m, tto))
1894 // Case 3: If the moving piece in the threatened move is a slider, don't
1895 // prune safe moves which block its ray.
1896 if ( piece_is_slider(pos.piece_on(tfrom))
1897 && bit_is_set(squares_between(tfrom, tto), mto)
1898 && pos.see_sign(m) >= 0)
1905 // ok_to_use_TT() returns true if a transposition table score
1906 // can be used at a given point in search.
1908 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1910 Value v = value_from_tt(tte->value(), ply);
1912 return ( tte->depth() >= depth
1913 || v >= Max(value_mate_in(PLY_MAX), beta)
1914 || v < Min(value_mated_in(PLY_MAX), beta))
1916 && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1917 || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1921 // refine_eval() returns the transposition table score if
1922 // possible otherwise falls back on static position evaluation.
1924 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1928 Value v = value_from_tt(tte->value(), ply);
1930 if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1931 || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1938 // update_history() registers a good move that produced a beta-cutoff
1939 // in history and marks as failures all the other moves of that ply.
1941 void update_history(const Position& pos, Move move, Depth depth,
1942 Move movesSearched[], int moveCount) {
1945 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
1947 for (int i = 0; i < moveCount - 1; i++)
1949 m = movesSearched[i];
1953 if (!pos.move_is_capture_or_promotion(m))
1954 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
1959 // update_killers() add a good move that produced a beta-cutoff
1960 // among the killer moves of that ply.
1962 void update_killers(Move m, SearchStack* ss) {
1964 if (m == ss->killers[0])
1967 ss->killers[1] = ss->killers[0];
1972 // update_gains() updates the gains table of a non-capture move given
1973 // the static position evaluation before and after the move.
1975 void update_gains(const Position& pos, Move m, Value before, Value after) {
1978 && before != VALUE_NONE
1979 && after != VALUE_NONE
1980 && pos.captured_piece_type() == PIECE_TYPE_NONE
1981 && !move_is_special(m))
1982 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
1986 // current_search_time() returns the number of milliseconds which have passed
1987 // since the beginning of the current search.
1989 int current_search_time() {
1991 return get_system_time() - SearchStartTime;
1995 // value_to_uci() converts a value to a string suitable for use with the UCI protocol
1997 std::string value_to_uci(Value v) {
1999 std::stringstream s;
2001 if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
2002 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100
2004 s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
2009 // nps() computes the current nodes/second count.
2011 int nps(const Position& pos) {
2013 int t = current_search_time();
2014 return (t > 0 ? int((pos.nodes_searched() * 1000) / t) : 0);
2018 // poll() performs two different functions: It polls for user input, and it
2019 // looks at the time consumed so far and decides if it's time to abort the
2022 void poll(const Position& pos) {
2024 static int lastInfoTime;
2025 int t = current_search_time();
2028 if (data_available())
2030 // We are line oriented, don't read single chars
2031 std::string command;
2033 if (!std::getline(std::cin, command))
2036 if (command == "quit")
2039 PonderSearch = false;
2043 else if (command == "stop")
2046 PonderSearch = false;
2048 else if (command == "ponderhit")
2052 // Print search information
2056 else if (lastInfoTime > t)
2057 // HACK: Must be a new search where we searched less than
2058 // NodesBetweenPolls nodes during the first second of search.
2061 else if (t - lastInfoTime >= 1000)
2068 if (dbg_show_hit_rate)
2069 dbg_print_hit_rate();
2071 cout << "info nodes " << pos.nodes_searched() << " nps " << nps(pos)
2072 << " time " << t << endl;
2075 // Should we stop the search?
2079 bool stillAtFirstMove = FirstRootMove
2080 && !AspirationFailLow
2081 && t > TimeMgr.available_time();
2083 bool noMoreTime = t > TimeMgr.maximum_time()
2084 || stillAtFirstMove;
2086 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2087 || (ExactMaxTime && t >= ExactMaxTime)
2088 || (Iteration >= 3 && MaxNodes && pos.nodes_searched() >= MaxNodes))
2093 // ponderhit() is called when the program is pondering (i.e. thinking while
2094 // it's the opponent's turn to move) in order to let the engine know that
2095 // it correctly predicted the opponent's move.
2099 int t = current_search_time();
2100 PonderSearch = false;
2102 bool stillAtFirstMove = FirstRootMove
2103 && !AspirationFailLow
2104 && t > TimeMgr.available_time();
2106 bool noMoreTime = t > TimeMgr.maximum_time()
2107 || stillAtFirstMove;
2109 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2114 // init_ss_array() does a fast reset of the first entries of a SearchStack
2115 // array and of all the excludedMove and skipNullMove entries.
2117 void init_ss_array(SearchStack* ss, int size) {
2119 for (int i = 0; i < size; i++, ss++)
2121 ss->excludedMove = MOVE_NONE;
2122 ss->skipNullMove = false;
2123 ss->reduction = DEPTH_ZERO;
2127 ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE;
2132 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2133 // while the program is pondering. The point is to work around a wrinkle in
2134 // the UCI protocol: When pondering, the engine is not allowed to give a
2135 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2136 // We simply wait here until one of these commands is sent, and return,
2137 // after which the bestmove and pondermove will be printed (in id_loop()).
2139 void wait_for_stop_or_ponderhit() {
2141 std::string command;
2145 if (!std::getline(std::cin, command))
2148 if (command == "quit")
2153 else if (command == "ponderhit" || command == "stop")
2159 // print_pv_info() prints to standard output and eventually to log file information on
2160 // the current PV line. It is called at each iteration or after a new pv is found.
2162 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) {
2164 cout << "info depth " << Iteration
2165 << " score " << value_to_uci(value)
2166 << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
2167 << " time " << current_search_time()
2168 << " nodes " << pos.nodes_searched()
2169 << " nps " << nps(pos)
2172 for (Move* m = pv; *m != MOVE_NONE; m++)
2179 ValueType t = value >= beta ? VALUE_TYPE_LOWER :
2180 value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
2182 LogFile << pretty_pv(pos, current_search_time(), Iteration, value, t, pv) << endl;
2187 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2188 // the PV back into the TT. This makes sure the old PV moves are searched
2189 // first, even if the old TT entries have been overwritten.
2191 void insert_pv_in_tt(const Position& pos, Move pv[]) {
2195 Position p(pos, pos.thread());
2196 Value v, m = VALUE_NONE;
2198 for (int i = 0; pv[i] != MOVE_NONE; i++)
2200 tte = TT.retrieve(p.get_key());
2201 if (!tte || tte->move() != pv[i])
2203 v = (p.is_check() ? VALUE_NONE : evaluate(p, m));
2204 TT.store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[i], v, m);
2206 p.do_move(pv[i], st);
2211 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2212 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2213 // allow to always have a ponder move even when we fail high at root and also a
2214 // long PV to print that is important for position analysis.
2216 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]) {
2220 Position p(pos, pos.thread());
2223 assert(bestMove != MOVE_NONE);
2226 p.do_move(pv[ply++], st);
2228 while ( (tte = TT.retrieve(p.get_key())) != NULL
2229 && tte->move() != MOVE_NONE
2230 && move_is_legal(p, tte->move())
2232 && (!p.is_draw() || ply < 2))
2234 pv[ply] = tte->move();
2235 p.do_move(pv[ply++], st);
2237 pv[ply] = MOVE_NONE;
2241 // init_thread() is the function which is called when a new thread is
2242 // launched. It simply calls the idle_loop() function with the supplied
2243 // threadID. There are two versions of this function; one for POSIX
2244 // threads and one for Windows threads.
2246 #if !defined(_MSC_VER)
2248 void* init_thread(void* threadID) {
2250 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2256 DWORD WINAPI init_thread(LPVOID threadID) {
2258 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2265 /// The ThreadsManager class
2268 // read_uci_options() updates number of active threads and other internal
2269 // parameters according to the UCI options values. It is called before
2270 // to start a new search.
2272 void ThreadsManager::read_uci_options() {
2274 maxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value<int>();
2275 minimumSplitDepth = Options["Minimum Split Depth"].value<int>() * ONE_PLY;
2276 useSleepingThreads = Options["Use Sleeping Threads"].value<bool>();
2277 activeThreads = Options["Threads"].value<int>();
2281 // idle_loop() is where the threads are parked when they have no work to do.
2282 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2283 // object for which the current thread is the master.
2285 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2287 assert(threadID >= 0 && threadID < MAX_THREADS);
2290 bool allFinished = false;
2294 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2295 // master should exit as last one.
2296 if (allThreadsShouldExit)
2299 threads[threadID].state = THREAD_TERMINATED;
2303 // If we are not thinking, wait for a condition to be signaled
2304 // instead of wasting CPU time polling for work.
2305 while ( threadID >= activeThreads || threads[threadID].state == THREAD_INITIALIZING
2306 || (useSleepingThreads && threads[threadID].state == THREAD_AVAILABLE))
2308 assert(!sp || useSleepingThreads);
2309 assert(threadID != 0 || useSleepingThreads);
2311 if (threads[threadID].state == THREAD_INITIALIZING)
2312 threads[threadID].state = THREAD_AVAILABLE;
2314 // Grab the lock to avoid races with wake_sleeping_thread()
2315 lock_grab(&sleepLock[threadID]);
2317 // If we are master and all slaves have finished do not go to sleep
2318 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2319 allFinished = (i == activeThreads);
2321 if (allFinished || allThreadsShouldExit)
2323 lock_release(&sleepLock[threadID]);
2327 // Do sleep here after retesting sleep conditions
2328 if (threadID >= activeThreads || threads[threadID].state == THREAD_AVAILABLE)
2329 cond_wait(&sleepCond[threadID], &sleepLock[threadID]);
2331 lock_release(&sleepLock[threadID]);
2334 // If this thread has been assigned work, launch a search
2335 if (threads[threadID].state == THREAD_WORKISWAITING)
2337 assert(!allThreadsShouldExit);
2339 threads[threadID].state = THREAD_SEARCHING;
2341 // Here we call search() with SplitPoint template parameter set to true
2342 SplitPoint* tsp = threads[threadID].splitPoint;
2343 Position pos(*tsp->pos, threadID);
2344 SearchStack* ss = tsp->sstack[threadID] + 1;
2348 search<PV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2350 search<NonPV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2352 assert(threads[threadID].state == THREAD_SEARCHING);
2354 threads[threadID].state = THREAD_AVAILABLE;
2356 // Wake up master thread so to allow it to return from the idle loop in
2357 // case we are the last slave of the split point.
2358 if (useSleepingThreads && threadID != tsp->master && threads[tsp->master].state == THREAD_AVAILABLE)
2359 wake_sleeping_thread(tsp->master);
2362 // If this thread is the master of a split point and all slaves have
2363 // finished their work at this split point, return from the idle loop.
2364 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2365 allFinished = (i == activeThreads);
2369 // Because sp->slaves[] is reset under lock protection,
2370 // be sure sp->lock has been released before to return.
2371 lock_grab(&(sp->lock));
2372 lock_release(&(sp->lock));
2374 // In helpful master concept a master can help only a sub-tree, and
2375 // because here is all finished is not possible master is booked.
2376 assert(threads[threadID].state == THREAD_AVAILABLE);
2378 threads[threadID].state = THREAD_SEARCHING;
2385 // init_threads() is called during startup. It launches all helper threads,
2386 // and initializes the split point stack and the global locks and condition
2389 void ThreadsManager::init_threads() {
2391 int i, arg[MAX_THREADS];
2394 // Initialize global locks
2397 for (i = 0; i < MAX_THREADS; i++)
2399 lock_init(&sleepLock[i]);
2400 cond_init(&sleepCond[i]);
2403 // Initialize splitPoints[] locks
2404 for (i = 0; i < MAX_THREADS; i++)
2405 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2406 lock_init(&(threads[i].splitPoints[j].lock));
2408 // Will be set just before program exits to properly end the threads
2409 allThreadsShouldExit = false;
2411 // Threads will be put all threads to sleep as soon as created
2414 // All threads except the main thread should be initialized to THREAD_INITIALIZING
2415 threads[0].state = THREAD_SEARCHING;
2416 for (i = 1; i < MAX_THREADS; i++)
2417 threads[i].state = THREAD_INITIALIZING;
2419 // Launch the helper threads
2420 for (i = 1; i < MAX_THREADS; i++)
2424 #if !defined(_MSC_VER)
2425 pthread_t pthread[1];
2426 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
2427 pthread_detach(pthread[0]);
2429 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
2433 cout << "Failed to create thread number " << i << endl;
2437 // Wait until the thread has finished launching and is gone to sleep
2438 while (threads[i].state == THREAD_INITIALIZING) {}
2443 // exit_threads() is called when the program exits. It makes all the
2444 // helper threads exit cleanly.
2446 void ThreadsManager::exit_threads() {
2448 allThreadsShouldExit = true; // Let the woken up threads to exit idle_loop()
2450 // Wake up all the threads and waits for termination
2451 for (int i = 1; i < MAX_THREADS; i++)
2453 wake_sleeping_thread(i);
2454 while (threads[i].state != THREAD_TERMINATED) {}
2457 // Now we can safely destroy the locks
2458 for (int i = 0; i < MAX_THREADS; i++)
2459 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2460 lock_destroy(&(threads[i].splitPoints[j].lock));
2462 lock_destroy(&mpLock);
2464 // Now we can safely destroy the wait conditions
2465 for (int i = 0; i < MAX_THREADS; i++)
2467 lock_destroy(&sleepLock[i]);
2468 cond_destroy(&sleepCond[i]);
2473 // cutoff_at_splitpoint() checks whether a beta cutoff has occurred in
2474 // the thread's currently active split point, or in some ancestor of
2475 // the current split point.
2477 bool ThreadsManager::cutoff_at_splitpoint(int threadID) const {
2479 assert(threadID >= 0 && threadID < activeThreads);
2481 SplitPoint* sp = threads[threadID].splitPoint;
2483 for ( ; sp && !sp->betaCutoff; sp = sp->parent) {}
2488 // thread_is_available() checks whether the thread with threadID "slave" is
2489 // available to help the thread with threadID "master" at a split point. An
2490 // obvious requirement is that "slave" must be idle. With more than two
2491 // threads, this is not by itself sufficient: If "slave" is the master of
2492 // some active split point, it is only available as a slave to the other
2493 // threads which are busy searching the split point at the top of "slave"'s
2494 // split point stack (the "helpful master concept" in YBWC terminology).
2496 bool ThreadsManager::thread_is_available(int slave, int master) const {
2498 assert(slave >= 0 && slave < activeThreads);
2499 assert(master >= 0 && master < activeThreads);
2500 assert(activeThreads > 1);
2502 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2505 // Make a local copy to be sure doesn't change under our feet
2506 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2508 // No active split points means that the thread is available as
2509 // a slave for any other thread.
2510 if (localActiveSplitPoints == 0 || activeThreads == 2)
2513 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2514 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2515 // could have been set to 0 by another thread leading to an out of bound access.
2516 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2523 // available_thread_exists() tries to find an idle thread which is available as
2524 // a slave for the thread with threadID "master".
2526 bool ThreadsManager::available_thread_exists(int master) const {
2528 assert(master >= 0 && master < activeThreads);
2529 assert(activeThreads > 1);
2531 for (int i = 0; i < activeThreads; i++)
2532 if (thread_is_available(i, master))
2539 // split() does the actual work of distributing the work at a node between
2540 // several available threads. If it does not succeed in splitting the
2541 // node (because no idle threads are available, or because we have no unused
2542 // split point objects), the function immediately returns. If splitting is
2543 // possible, a SplitPoint object is initialized with all the data that must be
2544 // copied to the helper threads and we tell our helper threads that they have
2545 // been assigned work. This will cause them to instantly leave their idle loops and
2546 // call search().When all threads have returned from search() then split() returns.
2548 template <bool Fake>
2549 void ThreadsManager::split(Position& pos, SearchStack* ss, int ply, Value* alpha,
2550 const Value beta, Value* bestValue, Depth depth, Move threatMove,
2551 bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) {
2552 assert(pos.is_ok());
2553 assert(ply > 0 && ply < PLY_MAX);
2554 assert(*bestValue >= -VALUE_INFINITE);
2555 assert(*bestValue <= *alpha);
2556 assert(*alpha < beta);
2557 assert(beta <= VALUE_INFINITE);
2558 assert(depth > DEPTH_ZERO);
2559 assert(pos.thread() >= 0 && pos.thread() < activeThreads);
2560 assert(activeThreads > 1);
2562 int i, master = pos.thread();
2563 Thread& masterThread = threads[master];
2567 // If no other thread is available to help us, or if we have too many
2568 // active split points, don't split.
2569 if ( !available_thread_exists(master)
2570 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2572 lock_release(&mpLock);
2576 // Pick the next available split point object from the split point stack
2577 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2579 // Initialize the split point object
2580 splitPoint.parent = masterThread.splitPoint;
2581 splitPoint.master = master;
2582 splitPoint.betaCutoff = false;
2583 splitPoint.ply = ply;
2584 splitPoint.depth = depth;
2585 splitPoint.threatMove = threatMove;
2586 splitPoint.mateThreat = mateThreat;
2587 splitPoint.alpha = *alpha;
2588 splitPoint.beta = beta;
2589 splitPoint.pvNode = pvNode;
2590 splitPoint.bestValue = *bestValue;
2592 splitPoint.moveCount = moveCount;
2593 splitPoint.pos = &pos;
2594 splitPoint.nodes = 0;
2595 splitPoint.parentSstack = ss;
2596 for (i = 0; i < activeThreads; i++)
2597 splitPoint.slaves[i] = 0;
2599 masterThread.splitPoint = &splitPoint;
2601 // If we are here it means we are not available
2602 assert(masterThread.state != THREAD_AVAILABLE);
2604 int workersCnt = 1; // At least the master is included
2606 // Allocate available threads setting state to THREAD_BOOKED
2607 for (i = 0; !Fake && i < activeThreads && workersCnt < maxThreadsPerSplitPoint; i++)
2608 if (thread_is_available(i, master))
2610 threads[i].state = THREAD_BOOKED;
2611 threads[i].splitPoint = &splitPoint;
2612 splitPoint.slaves[i] = 1;
2616 assert(Fake || workersCnt > 1);
2618 // We can release the lock because slave threads are already booked and master is not available
2619 lock_release(&mpLock);
2621 // Tell the threads that they have work to do. This will make them leave
2622 // their idle loop. But before copy search stack tail for each thread.
2623 for (i = 0; i < activeThreads; i++)
2624 if (i == master || splitPoint.slaves[i])
2626 memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
2628 assert(i == master || threads[i].state == THREAD_BOOKED);
2630 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2632 if (useSleepingThreads && i != master)
2633 wake_sleeping_thread(i);
2636 // Everything is set up. The master thread enters the idle loop, from
2637 // which it will instantly launch a search, because its state is
2638 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2639 // idle loop, which means that the main thread will return from the idle
2640 // loop when all threads have finished their work at this split point.
2641 idle_loop(master, &splitPoint);
2643 // We have returned from the idle loop, which means that all threads are
2644 // finished. Update alpha and bestValue, and return.
2647 *alpha = splitPoint.alpha;
2648 *bestValue = splitPoint.bestValue;
2649 masterThread.activeSplitPoints--;
2650 masterThread.splitPoint = splitPoint.parent;
2651 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
2653 lock_release(&mpLock);
2657 // wake_sleeping_thread() wakes up the thread with the given threadID
2658 // when it is time to start a new search.
2660 void ThreadsManager::wake_sleeping_thread(int threadID) {
2662 lock_grab(&sleepLock[threadID]);
2663 cond_signal(&sleepCond[threadID]);
2664 lock_release(&sleepLock[threadID]);
2668 /// The RootMoveList class
2670 // RootMoveList c'tor
2672 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) {
2674 SearchStack ss[PLY_MAX_PLUS_2];
2675 MoveStack mlist[MOVES_MAX];
2677 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
2679 // Initialize search stack
2680 init_ss_array(ss, PLY_MAX_PLUS_2);
2681 ss[0].eval = ss[0].evalMargin = VALUE_NONE;
2683 // Generate all legal moves
2684 MoveStack* last = generate_moves(pos, mlist);
2686 // Add each move to the moves[] array
2687 for (MoveStack* cur = mlist; cur != last; cur++)
2689 bool includeMove = includeAllMoves;
2691 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
2692 includeMove = (searchMoves[k] == cur->move);
2697 // Find a quick score for the move and add to the list
2699 rm.move = ss[0].currentMove = rm.pv[0] = cur->move;
2700 rm.pv[1] = MOVE_NONE;
2701 pos.do_move(cur->move, st);
2702 rm.pv_score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
2703 pos.undo_move(cur->move);
2709 // Score root moves using the standard way used in main search, the moves
2710 // are scored according to the order in which are returned by MovePicker.
2711 // This is the second order score that is used to compare the moves when
2712 // the first order pv scores of both moves are equal.
2714 void RootMoveList::set_non_pv_scores(const Position& pos)
2717 Value score = VALUE_ZERO;
2718 MovePicker mp(pos, MOVE_NONE, ONE_PLY, H);
2720 while ((move = mp.get_next_move()) != MOVE_NONE)
2721 for (Base::iterator it = begin(); it != end(); ++it)
2722 if (it->move == move)
2724 it->non_pv_score = score--;
2729 // RootMoveList::sort_multipv() sorts the first few moves in the root move
2730 // list by their scores and depths. It is used to order the different PVs
2731 // correctly in MultiPV mode.
2733 void RootMoveList::sort_multipv(int n) {
2737 for (i = 1; i <= n; i++)
2739 const RootMove& rm = this->at(i);
2740 for (j = i; j > 0 && this->at(j - 1) < rm; j--)
2741 (*this)[j] = this->at(j - 1);