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; move = pv[0] = MOVE_NONE; }
117 RootMove(const RootMove& rm) { *this = rm; }
118 RootMove& operator=(const RootMove& rm); // Skip costly full pv[] copy
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 pvScore, or if it has
123 // equal pvScore but m1 has the higher nonPvScore. In this way
124 // 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 : non_pv_score <= m.non_pv_score;
128 void set_pv(const Move newPv[]);
131 Value pv_score, non_pv_score;
132 Move move, pv[PLY_MAX_PLUS_2];
135 RootMove& RootMove::operator=(const RootMove& rm) {
137 pv_score = rm.pv_score; non_pv_score = rm.non_pv_score;
138 nodes = rm.nodes; move = rm.move;
143 void RootMove::set_pv(const Move newPv[]) {
147 while (newPv[++i] != MOVE_NONE)
154 // The RootMoveList struct is essentially a std::vector<> of RootMove objects,
155 // with an handful of methods above the standard ones.
157 struct RootMoveList : public std::vector<RootMove> {
159 typedef std::vector<RootMove> Base;
161 RootMoveList(Position& pos, Move searchMoves[]);
162 void sort() { sort_multipv((int)size() - 1); } // Sort all items
164 void set_non_pv_scores(const Position& pos);
165 void sort_multipv(int n);
169 // When formatting a move for std::cout we must know if we are in Chess960
170 // or not. To keep using the handy operator<<() on the move the trick is to
171 // embed this flag in the stream itself. Function-like named enum set960 is
172 // used as a custom manipulator and the stream internal general-purpose array,
173 // accessed through ios_base::iword(), is used to pass the flag to the move's
174 // operator<<() that will use it to properly format castling moves.
177 std::ostream& operator<< (std::ostream& os, const set960& m) {
179 os.iword(0) = int(m);
188 // Maximum depth for razoring
189 const Depth RazorDepth = 4 * ONE_PLY;
191 // Dynamic razoring margin based on depth
192 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
194 // Maximum depth for use of dynamic threat detection when null move fails low
195 const Depth ThreatDepth = 5 * ONE_PLY;
197 // Step 9. Internal iterative deepening
199 // Minimum depth for use of internal iterative deepening
200 const Depth IIDDepth[2] = { 8 * ONE_PLY /* non-PV */, 5 * ONE_PLY /* PV */};
202 // At Non-PV nodes we do an internal iterative deepening search
203 // when the static evaluation is bigger then beta - IIDMargin.
204 const Value IIDMargin = Value(0x100);
206 // Step 11. Decide the new search depth
208 // Extensions. Configurable UCI options
209 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
210 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
211 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
213 // Minimum depth for use of singular extension
214 const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */};
216 // If the TT move is at least SingularExtensionMargin better then the
217 // remaining ones we will extend it.
218 const Value SingularExtensionMargin = Value(0x20);
220 // Step 12. Futility pruning
222 // Futility margin for quiescence search
223 const Value FutilityMarginQS = Value(0x80);
225 // Futility lookup tables (initialized at startup) and their getter functions
226 Value FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
227 int FutilityMoveCountArray[32]; // [depth]
229 inline Value futility_margin(Depth d, int mn) { return d < 7 * ONE_PLY ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE; }
230 inline int futility_move_count(Depth d) { return d < 16 * ONE_PLY ? FutilityMoveCountArray[d] : 512; }
232 // Step 14. Reduced search
234 // Reduction lookup tables (initialized at startup) and their getter functions
235 int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
237 template <NodeType PV>
238 inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
240 // Common adjustments
242 // Search depth at iteration 1
243 const Depth InitialDepth = ONE_PLY;
245 // Easy move margin. An easy move candidate must be at least this much
246 // better than the second best move.
247 const Value EasyMoveMargin = Value(0x200);
250 /// Namespace variables
258 // Scores and number of times the best move changed for each iteration
259 Value ValueByIteration[PLY_MAX_PLUS_2];
260 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
262 // Search window management
268 // Time managment variables
269 int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
270 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
271 bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
276 std::ofstream LogFile;
278 // Multi-threads manager object
279 ThreadsManager ThreadsMgr;
281 // Node counters, used only by thread[0] but try to keep in different cache
282 // lines (64 bytes each) from the heavy multi-thread read accessed variables.
284 int NodesBetweenPolls = 30000;
291 Value id_loop(Position& pos, Move searchMoves[]);
292 Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
294 template <NodeType PvNode, bool SpNode>
295 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
297 template <NodeType PvNode>
298 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
300 template <NodeType PvNode>
301 inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
303 return depth < ONE_PLY ? qsearch<PvNode>(pos, ss, alpha, beta, DEPTH_ZERO, ply)
304 : search<PvNode, false>(pos, ss, alpha, beta, depth, ply);
307 template <NodeType PvNode>
308 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
310 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue);
311 bool connected_moves(const Position& pos, Move m1, Move m2);
312 bool value_is_mate(Value value);
313 Value value_to_tt(Value v, int ply);
314 Value value_from_tt(Value v, int ply);
315 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
316 bool connected_threat(const Position& pos, Move m, Move threat);
317 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
318 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
319 void update_killers(Move m, SearchStack* ss);
320 void update_gains(const Position& pos, Move move, Value before, Value after);
322 int current_search_time();
323 std::string value_to_uci(Value v);
324 int nps(const Position& pos);
325 void poll(const Position& pos);
327 void wait_for_stop_or_ponderhit();
328 void init_ss_array(SearchStack* ss, int size);
329 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value);
330 void insert_pv_in_tt(const Position& pos, Move pv[]);
331 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]);
333 #if !defined(_MSC_VER)
334 void* init_thread(void* threadID);
336 DWORD WINAPI init_thread(LPVOID threadID);
346 /// init_threads(), exit_threads() and nodes_searched() are helpers to
347 /// give accessibility to some TM methods from outside of current file.
349 void init_threads() { ThreadsMgr.init_threads(); }
350 void exit_threads() { ThreadsMgr.exit_threads(); }
353 /// init_search() is called during startup. It initializes various lookup tables
357 int d; // depth (ONE_PLY == 2)
358 int hd; // half depth (ONE_PLY == 1)
361 // Init reductions array
362 for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
364 double pvRed = log(double(hd)) * log(double(mc)) / 3.0;
365 double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
366 ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0);
367 ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0);
370 // Init futility margins array
371 for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
372 FutilityMarginsMatrix[d][mc] = Value(112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45);
374 // Init futility move count array
375 for (d = 0; d < 32; d++)
376 FutilityMoveCountArray[d] = int(3.001 + 0.25 * pow(d, 2.0));
380 /// perft() is our utility to verify move generation is bug free. All the legal
381 /// moves up to given depth are generated and counted and the sum returned.
383 int perft(Position& pos, Depth depth)
385 MoveStack mlist[MOVES_MAX];
390 // Generate all legal moves
391 MoveStack* last = generate_moves(pos, mlist);
393 // If we are at the last ply we don't need to do and undo
394 // the moves, just to count them.
395 if (depth <= ONE_PLY)
396 return int(last - mlist);
398 // Loop through all legal moves
400 for (MoveStack* cur = mlist; cur != last; cur++)
403 pos.do_move(m, st, ci, pos.move_is_check(m, ci));
404 sum += perft(pos, depth - ONE_PLY);
411 /// think() is the external interface to Stockfish's search, and is called when
412 /// the program receives the UCI 'go' command. It initializes various
413 /// search-related global variables, and calls root_search(). It returns false
414 /// when a quit command is received during the search.
416 bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[],
417 int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) {
419 // Initialize global search variables
420 StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
422 SearchStartTime = get_system_time();
423 ExactMaxTime = maxTime;
426 InfiniteSearch = infinite;
427 PonderSearch = ponder;
428 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
430 // Look for a book move, only during games, not tests
431 if (UseTimeManagement && Options["OwnBook"].value<bool>())
433 if (Options["Book File"].value<std::string>() != OpeningBook.file_name())
434 OpeningBook.open(Options["Book File"].value<std::string>());
436 Move bookMove = OpeningBook.get_move(pos, Options["Best Book Move"].value<bool>());
437 if (bookMove != MOVE_NONE)
440 wait_for_stop_or_ponderhit();
442 cout << "bestmove " << bookMove << endl;
447 // Read UCI option values
448 TT.set_size(Options["Hash"].value<int>());
449 if (Options["Clear Hash"].value<bool>())
451 Options["Clear Hash"].set_value("false");
455 CheckExtension[1] = Options["Check Extension (PV nodes)"].value<Depth>();
456 CheckExtension[0] = Options["Check Extension (non-PV nodes)"].value<Depth>();
457 SingleEvasionExtension[1] = Options["Single Evasion Extension (PV nodes)"].value<Depth>();
458 SingleEvasionExtension[0] = Options["Single Evasion Extension (non-PV nodes)"].value<Depth>();
459 PawnPushTo7thExtension[1] = Options["Pawn Push to 7th Extension (PV nodes)"].value<Depth>();
460 PawnPushTo7thExtension[0] = Options["Pawn Push to 7th Extension (non-PV nodes)"].value<Depth>();
461 PassedPawnExtension[1] = Options["Passed Pawn Extension (PV nodes)"].value<Depth>();
462 PassedPawnExtension[0] = Options["Passed Pawn Extension (non-PV nodes)"].value<Depth>();
463 PawnEndgameExtension[1] = Options["Pawn Endgame Extension (PV nodes)"].value<Depth>();
464 PawnEndgameExtension[0] = Options["Pawn Endgame Extension (non-PV nodes)"].value<Depth>();
465 MateThreatExtension[1] = Options["Mate Threat Extension (PV nodes)"].value<Depth>();
466 MateThreatExtension[0] = Options["Mate Threat Extension (non-PV nodes)"].value<Depth>();
467 MultiPV = Options["MultiPV"].value<int>();
468 UseLogFile = Options["Use Search Log"].value<bool>();
471 LogFile.open(Options["Search Log Filename"].value<std::string>().c_str(), std::ios::out | std::ios::app);
473 read_weights(pos.side_to_move());
475 // Set the number of active threads
476 ThreadsMgr.read_uci_options();
477 init_eval(ThreadsMgr.active_threads());
479 // Wake up needed threads
480 for (int i = 1; i < ThreadsMgr.active_threads(); i++)
481 ThreadsMgr.wake_sleeping_thread(i);
484 int myTime = time[pos.side_to_move()];
485 int myIncrement = increment[pos.side_to_move()];
486 if (UseTimeManagement)
487 TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter());
489 // Set best NodesBetweenPolls interval to avoid lagging under
490 // heavy time pressure.
492 NodesBetweenPolls = Min(MaxNodes, 30000);
493 else if (myTime && myTime < 1000)
494 NodesBetweenPolls = 1000;
495 else if (myTime && myTime < 5000)
496 NodesBetweenPolls = 5000;
498 NodesBetweenPolls = 30000;
500 // Write search information to log file
502 LogFile << "Searching: " << pos.to_fen() << endl
503 << "infinite: " << infinite
504 << " ponder: " << ponder
505 << " time: " << myTime
506 << " increment: " << myIncrement
507 << " moves to go: " << movesToGo << endl;
509 // We're ready to start thinking. Call the iterative deepening loop function
510 id_loop(pos, searchMoves);
515 // This makes all the threads to go to sleep
516 ThreadsMgr.set_active_threads(1);
524 // id_loop() is the main iterative deepening loop. It calls root_search
525 // repeatedly with increasing depth until the allocated thinking time has
526 // been consumed, the user stops the search, or the maximum search depth is
529 Value id_loop(Position& pos, Move searchMoves[]) {
531 SearchStack ss[PLY_MAX_PLUS_2];
532 Move pv[PLY_MAX_PLUS_2];
533 Move EasyMove = MOVE_NONE;
534 Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
536 // Moves to search are verified, copied, scored and sorted
537 RootMoveList rml(pos, searchMoves);
539 // Handle special case of searching on a mate/stale position
543 wait_for_stop_or_ponderhit();
545 return pos.is_check() ? -VALUE_MATE : VALUE_DRAW;
548 // Print RootMoveList startup scoring to the standard output,
549 // so to output information also for iteration 1.
550 cout << set960(pos.is_chess960()) // Is enough to set once at the beginning
551 << "info depth " << 1
552 << "\ninfo depth " << 1
553 << " score " << value_to_uci(rml[0].pv_score)
554 << " time " << current_search_time()
555 << " nodes " << pos.nodes_searched()
556 << " nps " << nps(pos)
557 << " pv " << rml[0].move << "\n";
562 init_ss_array(ss, PLY_MAX_PLUS_2);
563 pv[0] = pv[1] = MOVE_NONE;
564 ValueByIteration[1] = rml[0].pv_score;
567 // Is one move significantly better than others after initial scoring ?
569 || rml[0].pv_score > rml[1].pv_score + EasyMoveMargin)
570 EasyMove = rml[0].move;
572 // Iterative deepening loop
573 while (Iteration < PLY_MAX)
575 // Initialize iteration
577 BestMoveChangesByIteration[Iteration] = 0;
579 cout << "info depth " << Iteration << endl;
581 // Calculate dynamic aspiration window based on previous iterations
582 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
584 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
585 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
587 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
588 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
590 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
591 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
594 // Search to the current depth, rml is updated and sorted, alpha and beta could change
595 value = root_search(pos, ss, pv, rml, &alpha, &beta);
597 // Write PV to transposition table, in case the relevant entries have
598 // been overwritten during the search.
599 insert_pv_in_tt(pos, pv);
602 break; // Value cannot be trusted. Break out immediately!
604 //Save info about search result
605 ValueByIteration[Iteration] = value;
607 // Drop the easy move if differs from the new best move
608 if (pv[0] != EasyMove)
609 EasyMove = MOVE_NONE;
611 if (UseTimeManagement)
614 bool stopSearch = false;
616 // Stop search early if there is only a single legal move,
617 // we search up to Iteration 6 anyway to get a proper score.
618 if (Iteration >= 6 && rml.size() == 1)
621 // Stop search early when the last two iterations returned a mate score
623 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
624 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
627 // Stop search early if one move seems to be much better than the others
630 && ( ( rml[0].nodes > (pos.nodes_searched() * 85) / 100
631 && current_search_time() > TimeMgr.available_time() / 16)
632 ||( rml[0].nodes > (pos.nodes_searched() * 98) / 100
633 && current_search_time() > TimeMgr.available_time() / 32)))
636 // Add some extra time if the best move has changed during the last two iterations
637 if (Iteration > 5 && Iteration <= 50)
638 TimeMgr.pv_instability(BestMoveChangesByIteration[Iteration],
639 BestMoveChangesByIteration[Iteration-1]);
641 // Stop search if most of MaxSearchTime is consumed at the end of the
642 // iteration. We probably don't have enough time to search the first
643 // move at the next iteration anyway.
644 if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
650 StopOnPonderhit = true;
656 if (MaxDepth && Iteration >= MaxDepth)
660 // If we are pondering or in infinite search, we shouldn't print the
661 // best move before we are told to do so.
662 if (!AbortSearch && (PonderSearch || InfiniteSearch))
663 wait_for_stop_or_ponderhit();
665 // Print final search statistics
666 cout << "info nodes " << pos.nodes_searched()
667 << " nps " << nps(pos)
668 << " time " << current_search_time() << endl;
670 // Print the best move and the ponder move to the standard output
671 if (pv[0] == MOVE_NONE || MultiPV > 1)
677 assert(pv[0] != MOVE_NONE);
679 cout << "bestmove " << pv[0];
681 if (pv[1] != MOVE_NONE)
682 cout << " ponder " << pv[1];
689 dbg_print_mean(LogFile);
691 if (dbg_show_hit_rate)
692 dbg_print_hit_rate(LogFile);
694 LogFile << "\nNodes: " << pos.nodes_searched()
695 << "\nNodes/second: " << nps(pos)
696 << "\nBest move: " << move_to_san(pos, pv[0]);
699 pos.do_move(pv[0], st);
700 LogFile << "\nPonder move: "
701 << move_to_san(pos, pv[1]) // Works also with MOVE_NONE
704 return rml[0].pv_score;
708 // root_search() is the function which searches the root node. It is
709 // similar to search_pv except that it uses a different move ordering
710 // scheme, prints some information to the standard output and handles
711 // the fail low/high loops.
713 Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
719 Depth depth, ext, newDepth;
720 Value value, alpha, beta;
721 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
722 int researchCountFH, researchCountFL;
724 researchCountFH = researchCountFL = 0;
727 isCheck = pos.is_check();
728 depth = (Iteration - 2) * ONE_PLY + InitialDepth;
730 // Step 1. Initialize node (polling is omitted at root)
731 ss->currentMove = ss->bestMove = MOVE_NONE;
733 // Step 2. Check for aborted search (omitted at root)
734 // Step 3. Mate distance pruning (omitted at root)
735 // Step 4. Transposition table lookup (omitted at root)
737 // Step 5. Evaluate the position statically
738 // At root we do this only to get reference value for child nodes
739 ss->evalMargin = VALUE_NONE;
740 ss->eval = isCheck ? VALUE_NONE : evaluate(pos, ss->evalMargin);
742 // Step 6. Razoring (omitted at root)
743 // Step 7. Static null move pruning (omitted at root)
744 // Step 8. Null move search with verification search (omitted at root)
745 // Step 9. Internal iterative deepening (omitted at root)
747 // Step extra. Fail low loop
748 // We start with small aspiration window and in case of fail low, we research
749 // with bigger window until we are not failing low anymore.
752 // Sort the moves before to (re)search
753 rml.set_non_pv_scores(pos);
756 // Step 10. Loop through all moves in the root move list
757 for (int i = 0; i < (int)rml.size() && !AbortSearch; i++)
759 // This is used by time management
760 FirstRootMove = (i == 0);
762 // Save the current node count before the move is searched
763 nodes = pos.nodes_searched();
765 // Pick the next root move, and print the move and the move number to
766 // the standard output.
767 move = ss->currentMove = rml[i].move;
769 if (current_search_time() >= 1000)
770 cout << "info currmove " << move
771 << " currmovenumber " << i + 1 << endl;
773 moveIsCheck = pos.move_is_check(move);
774 captureOrPromotion = pos.move_is_capture_or_promotion(move);
776 // Step 11. Decide the new search depth
777 ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
778 newDepth = depth + ext;
780 // Step 12. Futility pruning (omitted at root)
782 // Step extra. Fail high loop
783 // If move fails high, we research with bigger window until we are not failing
785 value = -VALUE_INFINITE;
789 // Step 13. Make the move
790 pos.do_move(move, st, ci, moveIsCheck);
792 // Step extra. pv search
793 // We do pv search for first moves (i < MultiPV)
794 // and for fail high research (value > alpha)
795 if (i < MultiPV || value > alpha)
797 // Aspiration window is disabled in multi-pv case
799 alpha = -VALUE_INFINITE;
801 // Full depth PV search, done on first move or after a fail high
802 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
806 // Step 14. Reduced search
807 // if the move fails high will be re-searched at full depth
808 bool doFullDepthSearch = true;
810 if ( depth >= 3 * ONE_PLY
812 && !captureOrPromotion
813 && !move_is_castle(move))
815 ss->reduction = reduction<PV>(depth, i - MultiPV + 2);
818 assert(newDepth-ss->reduction >= ONE_PLY);
820 // Reduced depth non-pv search using alpha as upperbound
821 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
822 doFullDepthSearch = (value > alpha);
825 // The move failed high, but if reduction is very big we could
826 // face a false positive, retry with a less aggressive reduction,
827 // if the move fails high again then go with full depth search.
828 if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
830 assert(newDepth - ONE_PLY >= ONE_PLY);
832 ss->reduction = ONE_PLY;
833 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
834 doFullDepthSearch = (value > alpha);
836 ss->reduction = DEPTH_ZERO; // Restore original reduction
839 // Step 15. Full depth search
840 if (doFullDepthSearch)
842 // Full depth non-pv search using alpha as upperbound
843 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, 1);
845 // If we are above alpha then research at same depth but as PV
846 // to get a correct score or eventually a fail high above beta.
848 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
852 // Step 16. Undo move
855 // Can we exit fail high loop ?
856 if (AbortSearch || value < beta)
859 // We are failing high and going to do a research. It's important to update
860 // the score before research in case we run out of time while researching.
861 rml[i].pv_score = value;
863 extract_pv_from_tt(pos, move, pv);
866 // Print information to the standard output
867 print_pv_info(pos, pv, alpha, beta, value);
869 // Prepare for a research after a fail high, each time with a wider window
870 *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
873 } // End of fail high loop
875 // Finished searching the move. If AbortSearch is true, the search
876 // was aborted because the user interrupted the search or because we
877 // ran out of time. In this case, the return value of the search cannot
878 // be trusted, and we break out of the loop without updating the best
883 // Remember searched nodes counts for this move
884 rml[i].nodes += pos.nodes_searched() - nodes;
886 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
887 assert(value < beta);
889 // Step 17. Check for new best move
890 if (value <= alpha && i >= MultiPV)
891 rml[i].pv_score = -VALUE_INFINITE;
894 // PV move or new best move!
897 rml[i].pv_score = value;
899 extract_pv_from_tt(pos, move, pv);
904 // We record how often the best move has been changed in each
905 // iteration. This information is used for time managment: When
906 // the best move changes frequently, we allocate some more time.
908 BestMoveChangesByIteration[Iteration]++;
910 // Print information to the standard output
911 print_pv_info(pos, pv, alpha, beta, value);
913 // Raise alpha to setup proper non-pv search upper bound
920 for (int j = 0; j < Min(MultiPV, (int)rml.size()); j++)
922 cout << "info multipv " << j + 1
923 << " score " << value_to_uci(rml[j].pv_score)
924 << " depth " << (j <= i ? Iteration : Iteration - 1)
925 << " time " << current_search_time()
926 << " nodes " << pos.nodes_searched()
927 << " nps " << nps(pos)
930 for (int k = 0; rml[j].pv[k] != MOVE_NONE && k < PLY_MAX; k++)
931 cout << rml[j].pv[k] << " ";
935 alpha = rml[Min(i, MultiPV - 1)].pv_score;
937 } // PV move or new best move
939 assert(alpha >= *alphaPtr);
941 AspirationFailLow = (alpha == *alphaPtr);
943 if (AspirationFailLow && StopOnPonderhit)
944 StopOnPonderhit = false;
947 // Can we exit fail low loop ?
948 if (AbortSearch || !AspirationFailLow)
951 // Prepare for a research after a fail low, each time with a wider window
952 *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
957 // Sort the moves before to return
964 // search<>() is the main search function for both PV and non-PV nodes and for
965 // normal and SplitPoint nodes. When called just after a split point the search
966 // is simpler because we have already probed the hash table, done a null move
967 // search, and searched the first move before splitting, we don't have to repeat
968 // all this work again. We also don't need to store anything to the hash table
969 // here: This is taken care of after we return from the split point.
971 template <NodeType PvNode, bool SpNode>
972 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
974 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
975 assert(beta > alpha && beta <= VALUE_INFINITE);
976 assert(PvNode || alpha == beta - 1);
977 assert(ply > 0 && ply < PLY_MAX);
978 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
980 Move movesSearched[MOVES_MAX];
984 Move ttMove, move, excludedMove, threatMove;
987 Value bestValue, value, oldAlpha;
988 Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
989 bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
990 bool mateThreat = false;
992 int threadID = pos.thread();
993 SplitPoint* sp = NULL;
994 refinedValue = bestValue = value = -VALUE_INFINITE;
996 isCheck = pos.is_check();
1002 ttMove = excludedMove = MOVE_NONE;
1003 threatMove = sp->threatMove;
1004 mateThreat = sp->mateThreat;
1005 goto split_point_start;
1007 else {} // Hack to fix icc's "statement is unreachable" warning
1009 // Step 1. Initialize node and poll. Polling can abort search
1010 ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
1011 (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
1013 if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
1019 // Step 2. Check for aborted search and immediate draw
1021 || ThreadsMgr.cutoff_at_splitpoint(threadID)
1023 || ply >= PLY_MAX - 1)
1026 // Step 3. Mate distance pruning
1027 alpha = Max(value_mated_in(ply), alpha);
1028 beta = Min(value_mate_in(ply+1), beta);
1032 // Step 4. Transposition table lookup
1034 // We don't want the score of a partial search to overwrite a previous full search
1035 // TT value, so we use a different position key in case of an excluded move exists.
1036 excludedMove = ss->excludedMove;
1037 posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1039 tte = TT.retrieve(posKey);
1040 ttMove = tte ? tte->move() : MOVE_NONE;
1042 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1043 // This is to avoid problems in the following areas:
1045 // * Repetition draw detection
1046 // * Fifty move rule detection
1047 // * Searching for a mate
1048 // * Printing of full PV line
1049 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1052 ss->bestMove = ttMove; // Can be MOVE_NONE
1053 return value_from_tt(tte->value(), ply);
1056 // Step 5. Evaluate the position statically and
1057 // update gain statistics of parent move.
1059 ss->eval = ss->evalMargin = VALUE_NONE;
1062 assert(tte->static_value() != VALUE_NONE);
1064 ss->eval = tte->static_value();
1065 ss->evalMargin = tte->static_value_margin();
1066 refinedValue = refine_eval(tte, ss->eval, ply);
1070 refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
1071 TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
1074 // Save gain for the parent non-capture move
1075 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1077 // Step 6. Razoring (is omitted in PV nodes)
1079 && depth < RazorDepth
1081 && refinedValue < beta - razor_margin(depth)
1082 && ttMove == MOVE_NONE
1083 && !value_is_mate(beta)
1084 && !pos.has_pawn_on_7th(pos.side_to_move()))
1086 Value rbeta = beta - razor_margin(depth);
1087 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply);
1089 // Logically we should return (v + razor_margin(depth)), but
1090 // surprisingly this did slightly weaker in tests.
1094 // Step 7. Static null move pruning (is omitted in PV nodes)
1095 // We're betting that the opponent doesn't have a move that will reduce
1096 // the score by more than futility_margin(depth) if we do a null move.
1098 && !ss->skipNullMove
1099 && depth < RazorDepth
1101 && refinedValue >= beta + futility_margin(depth, 0)
1102 && !value_is_mate(beta)
1103 && pos.non_pawn_material(pos.side_to_move()))
1104 return refinedValue - futility_margin(depth, 0);
1106 // Step 8. Null move search with verification search (is omitted in PV nodes)
1108 && !ss->skipNullMove
1111 && refinedValue >= beta
1112 && !value_is_mate(beta)
1113 && pos.non_pawn_material(pos.side_to_move()))
1115 ss->currentMove = MOVE_NULL;
1117 // Null move dynamic reduction based on depth
1118 int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
1120 // Null move dynamic reduction based on value
1121 if (refinedValue - beta > PawnValueMidgame)
1124 pos.do_null_move(st);
1125 (ss+1)->skipNullMove = true;
1126 nullValue = -search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1);
1127 (ss+1)->skipNullMove = false;
1128 pos.undo_null_move();
1130 if (nullValue >= beta)
1132 // Do not return unproven mate scores
1133 if (nullValue >= value_mate_in(PLY_MAX))
1136 if (depth < 6 * ONE_PLY)
1139 // Do verification search at high depths
1140 ss->skipNullMove = true;
1141 Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY, ply);
1142 ss->skipNullMove = false;
1149 // The null move failed low, which means that we may be faced with
1150 // some kind of threat. If the previous move was reduced, check if
1151 // the move that refuted the null move was somehow connected to the
1152 // move which was reduced. If a connection is found, return a fail
1153 // low score (which will cause the reduced move to fail high in the
1154 // parent node, which will trigger a re-search with full depth).
1155 if (nullValue == value_mated_in(ply + 2))
1158 threatMove = (ss+1)->bestMove;
1159 if ( depth < ThreatDepth
1160 && (ss-1)->reduction
1161 && threatMove != MOVE_NONE
1162 && connected_moves(pos, (ss-1)->currentMove, threatMove))
1167 // Step 9. Internal iterative deepening
1168 if ( depth >= IIDDepth[PvNode]
1169 && ttMove == MOVE_NONE
1170 && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
1172 Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
1174 ss->skipNullMove = true;
1175 search<PvNode>(pos, ss, alpha, beta, d, ply);
1176 ss->skipNullMove = false;
1178 ttMove = ss->bestMove;
1179 tte = TT.retrieve(posKey);
1182 // Expensive mate threat detection (only for PV nodes)
1184 mateThreat = pos.has_mate_threat();
1186 split_point_start: // At split points actual search starts from here
1188 // Initialize a MovePicker object for the current position
1189 // FIXME currently MovePicker() c'tor is needless called also in SplitPoint
1190 MovePicker mpBase(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
1191 MovePicker& mp = SpNode ? *sp->mp : mpBase;
1193 ss->bestMove = MOVE_NONE;
1194 singleEvasion = !SpNode && isCheck && mp.number_of_evasions() == 1;
1195 futilityBase = ss->eval + ss->evalMargin;
1196 singularExtensionNode = !SpNode
1197 && depth >= SingularExtensionDepth[PvNode]
1200 && !excludedMove // Do not allow recursive singular extension search
1201 && (tte->type() & VALUE_TYPE_LOWER)
1202 && tte->depth() >= depth - 3 * ONE_PLY;
1205 lock_grab(&(sp->lock));
1206 bestValue = sp->bestValue;
1209 // Step 10. Loop through moves
1210 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1211 while ( bestValue < beta
1212 && (move = mp.get_next_move()) != MOVE_NONE
1213 && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1215 assert(move_is_ok(move));
1219 moveCount = ++sp->moveCount;
1220 lock_release(&(sp->lock));
1222 else if (move == excludedMove)
1225 movesSearched[moveCount++] = move;
1227 moveIsCheck = pos.move_is_check(move, ci);
1228 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1230 // Step 11. Decide the new search depth
1231 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1233 // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s),
1234 // and just one fails high on (alpha, beta), then that move is singular and should be extended.
1235 // To verify this we do a reduced search on all the other moves but the ttMove, if result is
1236 // lower then ttValue minus a margin then we extend ttMove.
1237 if ( singularExtensionNode
1238 && move == tte->move()
1241 Value ttValue = value_from_tt(tte->value(), ply);
1243 if (abs(ttValue) < VALUE_KNOWN_WIN)
1245 Value b = ttValue - SingularExtensionMargin;
1246 ss->excludedMove = move;
1247 ss->skipNullMove = true;
1248 Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
1249 ss->skipNullMove = false;
1250 ss->excludedMove = MOVE_NONE;
1251 ss->bestMove = MOVE_NONE;
1257 // Update current move (this must be done after singular extension search)
1258 ss->currentMove = move;
1259 newDepth = depth - ONE_PLY + ext;
1261 // Step 12. Futility pruning (is omitted in PV nodes)
1263 && !captureOrPromotion
1267 && !move_is_castle(move))
1269 // Move count based pruning
1270 if ( moveCount >= futility_move_count(depth)
1271 && !(threatMove && connected_threat(pos, move, threatMove))
1272 && bestValue > value_mated_in(PLY_MAX)) // FIXME bestValue is racy
1275 lock_grab(&(sp->lock));
1280 // Value based pruning
1281 // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
1282 // but fixing this made program slightly weaker.
1283 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1284 futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount)
1285 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1287 if (futilityValueScaled < beta)
1291 lock_grab(&(sp->lock));
1292 if (futilityValueScaled > sp->bestValue)
1293 sp->bestValue = bestValue = futilityValueScaled;
1295 else if (futilityValueScaled > bestValue)
1296 bestValue = futilityValueScaled;
1301 // Prune moves with negative SEE at low depths
1302 if ( predictedDepth < 2 * ONE_PLY
1303 && bestValue > value_mated_in(PLY_MAX)
1304 && pos.see_sign(move) < 0)
1307 lock_grab(&(sp->lock));
1313 // Step 13. Make the move
1314 pos.do_move(move, st, ci, moveIsCheck);
1316 // Step extra. pv search (only in PV nodes)
1317 // The first move in list is the expected PV
1318 if (PvNode && moveCount == 1)
1319 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1322 // Step 14. Reduced depth search
1323 // If the move fails high will be re-searched at full depth.
1324 bool doFullDepthSearch = true;
1326 if ( depth >= 3 * ONE_PLY
1327 && !captureOrPromotion
1329 && !move_is_castle(move)
1330 && ss->killers[0] != move
1331 && ss->killers[1] != move)
1333 ss->reduction = reduction<PvNode>(depth, moveCount);
1337 alpha = SpNode ? sp->alpha : alpha;
1338 Depth d = newDepth - ss->reduction;
1339 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1341 doFullDepthSearch = (value > alpha);
1344 // The move failed high, but if reduction is very big we could
1345 // face a false positive, retry with a less aggressive reduction,
1346 // if the move fails high again then go with full depth search.
1347 if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
1349 assert(newDepth - ONE_PLY >= ONE_PLY);
1351 ss->reduction = ONE_PLY;
1352 alpha = SpNode ? sp->alpha : alpha;
1353 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, ply+1);
1354 doFullDepthSearch = (value > alpha);
1356 ss->reduction = DEPTH_ZERO; // Restore original reduction
1359 // Step 15. Full depth search
1360 if (doFullDepthSearch)
1362 alpha = SpNode ? sp->alpha : alpha;
1363 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1365 // Step extra. pv search (only in PV nodes)
1366 // Search only for possible new PV nodes, if instead value >= beta then
1367 // parent node fails low with value <= alpha and tries another move.
1368 if (PvNode && value > alpha && value < beta)
1369 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1373 // Step 16. Undo move
1374 pos.undo_move(move);
1376 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1378 // Step 17. Check for new best move
1381 lock_grab(&(sp->lock));
1382 bestValue = sp->bestValue;
1386 if (value > bestValue && !(SpNode && ThreadsMgr.cutoff_at_splitpoint(threadID)))
1391 sp->bestValue = value;
1395 if (PvNode && value < beta) // We want always alpha < beta
1403 sp->betaCutoff = true;
1405 if (value == value_mate_in(ply + 1))
1406 ss->mateKiller = move;
1408 ss->bestMove = move;
1411 sp->parentSstack->bestMove = move;
1415 // Step 18. Check for split
1417 && depth >= ThreadsMgr.min_split_depth()
1418 && ThreadsMgr.active_threads() > 1
1420 && ThreadsMgr.available_thread_exists(threadID)
1422 && !ThreadsMgr.cutoff_at_splitpoint(threadID)
1424 ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1425 threatMove, mateThreat, moveCount, &mp, PvNode);
1428 // Step 19. Check for mate and stalemate
1429 // All legal moves have been searched and if there are
1430 // no legal moves, it must be mate or stalemate.
1431 // If one move was excluded return fail low score.
1432 if (!SpNode && !moveCount)
1433 return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW;
1435 // Step 20. Update tables
1436 // If the search is not aborted, update the transposition table,
1437 // history counters, and killer moves.
1438 if (!SpNode && !AbortSearch && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1440 move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
1441 vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
1442 : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
1444 TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, ss->evalMargin);
1446 // Update killers and history only for non capture moves that fails high
1447 if ( bestValue >= beta
1448 && !pos.move_is_capture_or_promotion(move))
1450 update_history(pos, move, depth, movesSearched, moveCount);
1451 update_killers(move, ss);
1457 // Here we have the lock still grabbed
1458 sp->slaves[threadID] = 0;
1459 sp->nodes += pos.nodes_searched();
1460 lock_release(&(sp->lock));
1463 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1468 // qsearch() is the quiescence search function, which is called by the main
1469 // search function when the remaining depth is zero (or, to be more precise,
1470 // less than ONE_PLY).
1472 template <NodeType PvNode>
1473 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1475 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1476 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1477 assert(PvNode || alpha == beta - 1);
1479 assert(ply > 0 && ply < PLY_MAX);
1480 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1484 Value bestValue, value, evalMargin, futilityValue, futilityBase;
1485 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1488 Value oldAlpha = alpha;
1490 ss->bestMove = ss->currentMove = MOVE_NONE;
1492 // Check for an instant draw or maximum ply reached
1493 if (pos.is_draw() || ply >= PLY_MAX - 1)
1496 // Decide whether or not to include checks, this fixes also the type of
1497 // TT entry depth that we are going to use. Note that in qsearch we use
1498 // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
1499 isCheck = pos.is_check();
1500 ttDepth = (isCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS);
1502 // Transposition table lookup. At PV nodes, we don't use the TT for
1503 // pruning, but only for move ordering.
1504 tte = TT.retrieve(pos.get_key());
1505 ttMove = (tte ? tte->move() : MOVE_NONE);
1507 if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ply))
1509 ss->bestMove = ttMove; // Can be MOVE_NONE
1510 return value_from_tt(tte->value(), ply);
1513 // Evaluate the position statically
1516 bestValue = futilityBase = -VALUE_INFINITE;
1517 ss->eval = evalMargin = VALUE_NONE;
1518 enoughMaterial = false;
1524 assert(tte->static_value() != VALUE_NONE);
1526 evalMargin = tte->static_value_margin();
1527 ss->eval = bestValue = tte->static_value();
1530 ss->eval = bestValue = evaluate(pos, evalMargin);
1532 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1534 // Stand pat. Return immediately if static value is at least beta
1535 if (bestValue >= beta)
1538 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1543 if (PvNode && bestValue > alpha)
1546 // Futility pruning parameters, not needed when in check
1547 futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1548 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1551 // Initialize a MovePicker object for the current position, and prepare
1552 // to search the moves. Because the depth is <= 0 here, only captures,
1553 // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
1555 MovePicker mp(pos, ttMove, depth, H);
1558 // Loop through the moves until no moves remain or a beta cutoff occurs
1559 while ( alpha < beta
1560 && (move = mp.get_next_move()) != MOVE_NONE)
1562 assert(move_is_ok(move));
1564 moveIsCheck = pos.move_is_check(move, ci);
1572 && !move_is_promotion(move)
1573 && !pos.move_is_passed_pawn_push(move))
1575 futilityValue = futilityBase
1576 + pos.endgame_value_of_piece_on(move_to(move))
1577 + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1579 if (futilityValue < alpha)
1581 if (futilityValue > bestValue)
1582 bestValue = futilityValue;
1587 // Detect non-capture evasions that are candidate to be pruned
1588 evasionPrunable = isCheck
1589 && bestValue > value_mated_in(PLY_MAX)
1590 && !pos.move_is_capture(move)
1591 && !pos.can_castle(pos.side_to_move());
1593 // Don't search moves with negative SEE values
1595 && (!isCheck || evasionPrunable)
1597 && !move_is_promotion(move)
1598 && pos.see_sign(move) < 0)
1601 // Don't search useless checks
1606 && !pos.move_is_capture_or_promotion(move)
1607 && ss->eval + PawnValueMidgame / 4 < beta
1608 && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue))
1610 if (ss->eval + PawnValueMidgame / 4 > bestValue)
1611 bestValue = ss->eval + PawnValueMidgame / 4;
1616 // Update current move
1617 ss->currentMove = move;
1619 // Make and search the move
1620 pos.do_move(move, st, ci, moveIsCheck);
1621 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1);
1622 pos.undo_move(move);
1624 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1627 if (value > bestValue)
1633 ss->bestMove = move;
1638 // All legal moves have been searched. A special case: If we're in check
1639 // and no legal moves were found, it is checkmate.
1640 if (isCheck && bestValue == -VALUE_INFINITE)
1641 return value_mated_in(ply);
1643 // Update transposition table
1644 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1645 TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin);
1647 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1653 // check_is_dangerous() tests if a checking move can be pruned in qsearch().
1654 // bestValue is updated only when returning false because in that case move
1657 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bestValue)
1659 Bitboard b, occ, oldAtt, newAtt, kingAtt;
1660 Square from, to, ksq, victimSq;
1663 Value futilityValue, bv = *bestValue;
1665 from = move_from(move);
1667 them = opposite_color(pos.side_to_move());
1668 ksq = pos.king_square(them);
1669 kingAtt = pos.attacks_from<KING>(ksq);
1670 pc = pos.piece_on(from);
1672 occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL << ksq);
1673 oldAtt = pos.attacks_from(pc, from, occ);
1674 newAtt = pos.attacks_from(pc, to, occ);
1676 // Rule 1. Checks which give opponent's king at most one escape square are dangerous
1677 b = kingAtt & ~pos.pieces_of_color(them) & ~newAtt & ~(1ULL << to);
1679 if (!(b && (b & (b - 1))))
1682 // Rule 2. Queen contact check is very dangerous
1683 if ( type_of_piece(pc) == QUEEN
1684 && bit_is_set(kingAtt, to))
1687 // Rule 3. Creating new double threats with checks
1688 b = pos.pieces_of_color(them) & newAtt & ~oldAtt & ~(1ULL << ksq);
1692 victimSq = pop_1st_bit(&b);
1693 futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq);
1695 // Note that here we generate illegal "double move"!
1696 if ( futilityValue >= beta
1697 && pos.see_sign(make_move(from, victimSq)) >= 0)
1700 if (futilityValue > bv)
1704 // Update bestValue only if check is not dangerous (because we will prune the move)
1710 // connected_moves() tests whether two moves are 'connected' in the sense
1711 // that the first move somehow made the second move possible (for instance
1712 // if the moving piece is the same in both moves). The first move is assumed
1713 // to be the move that was made to reach the current position, while the
1714 // second move is assumed to be a move from the current position.
1716 bool connected_moves(const Position& pos, Move m1, Move m2) {
1718 Square f1, t1, f2, t2;
1721 assert(m1 && move_is_ok(m1));
1722 assert(m2 && move_is_ok(m2));
1724 // Case 1: The moving piece is the same in both moves
1730 // Case 2: The destination square for m2 was vacated by m1
1736 // Case 3: Moving through the vacated square
1737 if ( piece_is_slider(pos.piece_on(f2))
1738 && bit_is_set(squares_between(f2, t2), f1))
1741 // Case 4: The destination square for m2 is defended by the moving piece in m1
1742 p = pos.piece_on(t1);
1743 if (bit_is_set(pos.attacks_from(p, t1), t2))
1746 // Case 5: Discovered check, checking piece is the piece moved in m1
1747 if ( piece_is_slider(p)
1748 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1749 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1751 // discovered_check_candidates() works also if the Position's side to
1752 // move is the opposite of the checking piece.
1753 Color them = opposite_color(pos.side_to_move());
1754 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1756 if (bit_is_set(dcCandidates, f2))
1763 // value_is_mate() checks if the given value is a mate one eventually
1764 // compensated for the ply.
1766 bool value_is_mate(Value value) {
1768 assert(abs(value) <= VALUE_INFINITE);
1770 return value <= value_mated_in(PLY_MAX)
1771 || value >= value_mate_in(PLY_MAX);
1775 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1776 // "plies to mate from the current ply". Non-mate scores are unchanged.
1777 // The function is called before storing a value to the transposition table.
1779 Value value_to_tt(Value v, int ply) {
1781 if (v >= value_mate_in(PLY_MAX))
1784 if (v <= value_mated_in(PLY_MAX))
1791 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1792 // the transposition table to a mate score corrected for the current ply.
1794 Value value_from_tt(Value v, int ply) {
1796 if (v >= value_mate_in(PLY_MAX))
1799 if (v <= value_mated_in(PLY_MAX))
1806 // extension() decides whether a move should be searched with normal depth,
1807 // or with extended depth. Certain classes of moves (checking moves, in
1808 // particular) are searched with bigger depth than ordinary moves and in
1809 // any case are marked as 'dangerous'. Note that also if a move is not
1810 // extended, as example because the corresponding UCI option is set to zero,
1811 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1812 template <NodeType PvNode>
1813 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1814 bool singleEvasion, bool mateThreat, bool* dangerous) {
1816 assert(m != MOVE_NONE);
1818 Depth result = DEPTH_ZERO;
1819 *dangerous = moveIsCheck | singleEvasion | mateThreat;
1823 if (moveIsCheck && pos.see_sign(m) >= 0)
1824 result += CheckExtension[PvNode];
1827 result += SingleEvasionExtension[PvNode];
1830 result += MateThreatExtension[PvNode];
1833 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1835 Color c = pos.side_to_move();
1836 if (relative_rank(c, move_to(m)) == RANK_7)
1838 result += PawnPushTo7thExtension[PvNode];
1841 if (pos.pawn_is_passed(c, move_to(m)))
1843 result += PassedPawnExtension[PvNode];
1848 if ( captureOrPromotion
1849 && pos.type_of_piece_on(move_to(m)) != PAWN
1850 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1851 - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1852 && !move_is_promotion(m)
1855 result += PawnEndgameExtension[PvNode];
1860 && captureOrPromotion
1861 && pos.type_of_piece_on(move_to(m)) != PAWN
1862 && pos.see_sign(m) >= 0)
1864 result += ONE_PLY / 2;
1868 return Min(result, ONE_PLY);
1872 // connected_threat() tests whether it is safe to forward prune a move or if
1873 // is somehow coonected to the threat move returned by null search.
1875 bool connected_threat(const Position& pos, Move m, Move threat) {
1877 assert(move_is_ok(m));
1878 assert(threat && move_is_ok(threat));
1879 assert(!pos.move_is_check(m));
1880 assert(!pos.move_is_capture_or_promotion(m));
1881 assert(!pos.move_is_passed_pawn_push(m));
1883 Square mfrom, mto, tfrom, tto;
1885 mfrom = move_from(m);
1887 tfrom = move_from(threat);
1888 tto = move_to(threat);
1890 // Case 1: Don't prune moves which move the threatened piece
1894 // Case 2: If the threatened piece has value less than or equal to the
1895 // value of the threatening piece, don't prune move which defend it.
1896 if ( pos.move_is_capture(threat)
1897 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1898 || pos.type_of_piece_on(tfrom) == KING)
1899 && pos.move_attacks_square(m, tto))
1902 // Case 3: If the moving piece in the threatened move is a slider, don't
1903 // prune safe moves which block its ray.
1904 if ( piece_is_slider(pos.piece_on(tfrom))
1905 && bit_is_set(squares_between(tfrom, tto), mto)
1906 && pos.see_sign(m) >= 0)
1913 // ok_to_use_TT() returns true if a transposition table score
1914 // can be used at a given point in search.
1916 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1918 Value v = value_from_tt(tte->value(), ply);
1920 return ( tte->depth() >= depth
1921 || v >= Max(value_mate_in(PLY_MAX), beta)
1922 || v < Min(value_mated_in(PLY_MAX), beta))
1924 && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1925 || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1929 // refine_eval() returns the transposition table score if
1930 // possible otherwise falls back on static position evaluation.
1932 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1936 Value v = value_from_tt(tte->value(), ply);
1938 if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1939 || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1946 // update_history() registers a good move that produced a beta-cutoff
1947 // in history and marks as failures all the other moves of that ply.
1949 void update_history(const Position& pos, Move move, Depth depth,
1950 Move movesSearched[], int moveCount) {
1953 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
1955 for (int i = 0; i < moveCount - 1; i++)
1957 m = movesSearched[i];
1961 if (!pos.move_is_capture_or_promotion(m))
1962 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
1967 // update_killers() add a good move that produced a beta-cutoff
1968 // among the killer moves of that ply.
1970 void update_killers(Move m, SearchStack* ss) {
1972 if (m == ss->killers[0])
1975 ss->killers[1] = ss->killers[0];
1980 // update_gains() updates the gains table of a non-capture move given
1981 // the static position evaluation before and after the move.
1983 void update_gains(const Position& pos, Move m, Value before, Value after) {
1986 && before != VALUE_NONE
1987 && after != VALUE_NONE
1988 && pos.captured_piece_type() == PIECE_TYPE_NONE
1989 && !move_is_special(m))
1990 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
1994 // current_search_time() returns the number of milliseconds which have passed
1995 // since the beginning of the current search.
1997 int current_search_time() {
1999 return get_system_time() - SearchStartTime;
2003 // value_to_uci() converts a value to a string suitable for use with the UCI protocol
2005 std::string value_to_uci(Value v) {
2007 std::stringstream s;
2009 if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
2010 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100
2012 s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
2017 // nps() computes the current nodes/second count.
2019 int nps(const Position& pos) {
2021 int t = current_search_time();
2022 return (t > 0 ? int((pos.nodes_searched() * 1000) / t) : 0);
2026 // poll() performs two different functions: It polls for user input, and it
2027 // looks at the time consumed so far and decides if it's time to abort the
2030 void poll(const Position& pos) {
2032 static int lastInfoTime;
2033 int t = current_search_time();
2036 if (data_available())
2038 // We are line oriented, don't read single chars
2039 std::string command;
2041 if (!std::getline(std::cin, command))
2044 if (command == "quit")
2047 PonderSearch = false;
2051 else if (command == "stop")
2054 PonderSearch = false;
2056 else if (command == "ponderhit")
2060 // Print search information
2064 else if (lastInfoTime > t)
2065 // HACK: Must be a new search where we searched less than
2066 // NodesBetweenPolls nodes during the first second of search.
2069 else if (t - lastInfoTime >= 1000)
2076 if (dbg_show_hit_rate)
2077 dbg_print_hit_rate();
2079 cout << "info nodes " << pos.nodes_searched() << " nps " << nps(pos)
2080 << " time " << t << endl;
2083 // Should we stop the search?
2087 bool stillAtFirstMove = FirstRootMove
2088 && !AspirationFailLow
2089 && t > TimeMgr.available_time();
2091 bool noMoreTime = t > TimeMgr.maximum_time()
2092 || stillAtFirstMove;
2094 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2095 || (ExactMaxTime && t >= ExactMaxTime)
2096 || (Iteration >= 3 && MaxNodes && pos.nodes_searched() >= MaxNodes))
2101 // ponderhit() is called when the program is pondering (i.e. thinking while
2102 // it's the opponent's turn to move) in order to let the engine know that
2103 // it correctly predicted the opponent's move.
2107 int t = current_search_time();
2108 PonderSearch = false;
2110 bool stillAtFirstMove = FirstRootMove
2111 && !AspirationFailLow
2112 && t > TimeMgr.available_time();
2114 bool noMoreTime = t > TimeMgr.maximum_time()
2115 || stillAtFirstMove;
2117 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2122 // init_ss_array() does a fast reset of the first entries of a SearchStack
2123 // array and of all the excludedMove and skipNullMove entries.
2125 void init_ss_array(SearchStack* ss, int size) {
2127 for (int i = 0; i < size; i++, ss++)
2129 ss->excludedMove = MOVE_NONE;
2130 ss->skipNullMove = false;
2131 ss->reduction = DEPTH_ZERO;
2135 ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE;
2140 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2141 // while the program is pondering. The point is to work around a wrinkle in
2142 // the UCI protocol: When pondering, the engine is not allowed to give a
2143 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2144 // We simply wait here until one of these commands is sent, and return,
2145 // after which the bestmove and pondermove will be printed (in id_loop()).
2147 void wait_for_stop_or_ponderhit() {
2149 std::string command;
2153 if (!std::getline(std::cin, command))
2156 if (command == "quit")
2161 else if (command == "ponderhit" || command == "stop")
2167 // print_pv_info() prints to standard output and eventually to log file information on
2168 // the current PV line. It is called at each iteration or after a new pv is found.
2170 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) {
2172 cout << "info depth " << Iteration
2173 << " score " << value_to_uci(value)
2174 << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
2175 << " time " << current_search_time()
2176 << " nodes " << pos.nodes_searched()
2177 << " nps " << nps(pos)
2180 for (Move* m = pv; *m != MOVE_NONE; m++)
2187 ValueType t = value >= beta ? VALUE_TYPE_LOWER :
2188 value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
2190 LogFile << pretty_pv(pos, current_search_time(), Iteration, value, t, pv) << endl;
2195 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2196 // the PV back into the TT. This makes sure the old PV moves are searched
2197 // first, even if the old TT entries have been overwritten.
2199 void insert_pv_in_tt(const Position& pos, Move pv[]) {
2203 Position p(pos, pos.thread());
2204 Value v, m = VALUE_NONE;
2206 for (int i = 0; pv[i] != MOVE_NONE; i++)
2208 tte = TT.retrieve(p.get_key());
2209 if (!tte || tte->move() != pv[i])
2211 v = (p.is_check() ? VALUE_NONE : evaluate(p, m));
2212 TT.store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[i], v, m);
2214 p.do_move(pv[i], st);
2219 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2220 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2221 // allow to always have a ponder move even when we fail high at root and also a
2222 // long PV to print that is important for position analysis.
2224 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]) {
2228 Position p(pos, pos.thread());
2231 assert(bestMove != MOVE_NONE);
2234 p.do_move(pv[ply++], st);
2236 while ( (tte = TT.retrieve(p.get_key())) != NULL
2237 && tte->move() != MOVE_NONE
2238 && move_is_legal(p, tte->move())
2240 && (!p.is_draw() || ply < 2))
2242 pv[ply] = tte->move();
2243 p.do_move(pv[ply++], st);
2245 pv[ply] = MOVE_NONE;
2249 // init_thread() is the function which is called when a new thread is
2250 // launched. It simply calls the idle_loop() function with the supplied
2251 // threadID. There are two versions of this function; one for POSIX
2252 // threads and one for Windows threads.
2254 #if !defined(_MSC_VER)
2256 void* init_thread(void* threadID) {
2258 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2264 DWORD WINAPI init_thread(LPVOID threadID) {
2266 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2273 /// The ThreadsManager class
2276 // read_uci_options() updates number of active threads and other internal
2277 // parameters according to the UCI options values. It is called before
2278 // to start a new search.
2280 void ThreadsManager::read_uci_options() {
2282 maxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value<int>();
2283 minimumSplitDepth = Options["Minimum Split Depth"].value<int>() * ONE_PLY;
2284 useSleepingThreads = Options["Use Sleeping Threads"].value<bool>();
2285 activeThreads = Options["Threads"].value<int>();
2289 // idle_loop() is where the threads are parked when they have no work to do.
2290 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2291 // object for which the current thread is the master.
2293 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2295 assert(threadID >= 0 && threadID < MAX_THREADS);
2298 bool allFinished = false;
2302 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2303 // master should exit as last one.
2304 if (allThreadsShouldExit)
2307 threads[threadID].state = THREAD_TERMINATED;
2311 // If we are not thinking, wait for a condition to be signaled
2312 // instead of wasting CPU time polling for work.
2313 while ( threadID >= activeThreads || threads[threadID].state == THREAD_INITIALIZING
2314 || (useSleepingThreads && threads[threadID].state == THREAD_AVAILABLE))
2316 assert(!sp || useSleepingThreads);
2317 assert(threadID != 0 || useSleepingThreads);
2319 if (threads[threadID].state == THREAD_INITIALIZING)
2320 threads[threadID].state = THREAD_AVAILABLE;
2322 // Grab the lock to avoid races with wake_sleeping_thread()
2323 lock_grab(&sleepLock[threadID]);
2325 // If we are master and all slaves have finished do not go to sleep
2326 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2327 allFinished = (i == activeThreads);
2329 if (allFinished || allThreadsShouldExit)
2331 lock_release(&sleepLock[threadID]);
2335 // Do sleep here after retesting sleep conditions
2336 if (threadID >= activeThreads || threads[threadID].state == THREAD_AVAILABLE)
2337 cond_wait(&sleepCond[threadID], &sleepLock[threadID]);
2339 lock_release(&sleepLock[threadID]);
2342 // If this thread has been assigned work, launch a search
2343 if (threads[threadID].state == THREAD_WORKISWAITING)
2345 assert(!allThreadsShouldExit);
2347 threads[threadID].state = THREAD_SEARCHING;
2349 // Here we call search() with SplitPoint template parameter set to true
2350 SplitPoint* tsp = threads[threadID].splitPoint;
2351 Position pos(*tsp->pos, threadID);
2352 SearchStack* ss = tsp->sstack[threadID] + 1;
2356 search<PV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2358 search<NonPV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2360 assert(threads[threadID].state == THREAD_SEARCHING);
2362 threads[threadID].state = THREAD_AVAILABLE;
2364 // Wake up master thread so to allow it to return from the idle loop in
2365 // case we are the last slave of the split point.
2366 if (useSleepingThreads && threadID != tsp->master && threads[tsp->master].state == THREAD_AVAILABLE)
2367 wake_sleeping_thread(tsp->master);
2370 // If this thread is the master of a split point and all slaves have
2371 // finished their work at this split point, return from the idle loop.
2372 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2373 allFinished = (i == activeThreads);
2377 // Because sp->slaves[] is reset under lock protection,
2378 // be sure sp->lock has been released before to return.
2379 lock_grab(&(sp->lock));
2380 lock_release(&(sp->lock));
2382 // In helpful master concept a master can help only a sub-tree, and
2383 // because here is all finished is not possible master is booked.
2384 assert(threads[threadID].state == THREAD_AVAILABLE);
2386 threads[threadID].state = THREAD_SEARCHING;
2393 // init_threads() is called during startup. It launches all helper threads,
2394 // and initializes the split point stack and the global locks and condition
2397 void ThreadsManager::init_threads() {
2399 int i, arg[MAX_THREADS];
2402 // Initialize global locks
2405 for (i = 0; i < MAX_THREADS; i++)
2407 lock_init(&sleepLock[i]);
2408 cond_init(&sleepCond[i]);
2411 // Initialize splitPoints[] locks
2412 for (i = 0; i < MAX_THREADS; i++)
2413 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2414 lock_init(&(threads[i].splitPoints[j].lock));
2416 // Will be set just before program exits to properly end the threads
2417 allThreadsShouldExit = false;
2419 // Threads will be put all threads to sleep as soon as created
2422 // All threads except the main thread should be initialized to THREAD_INITIALIZING
2423 threads[0].state = THREAD_SEARCHING;
2424 for (i = 1; i < MAX_THREADS; i++)
2425 threads[i].state = THREAD_INITIALIZING;
2427 // Launch the helper threads
2428 for (i = 1; i < MAX_THREADS; i++)
2432 #if !defined(_MSC_VER)
2433 pthread_t pthread[1];
2434 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
2435 pthread_detach(pthread[0]);
2437 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
2441 cout << "Failed to create thread number " << i << endl;
2445 // Wait until the thread has finished launching and is gone to sleep
2446 while (threads[i].state == THREAD_INITIALIZING) {}
2451 // exit_threads() is called when the program exits. It makes all the
2452 // helper threads exit cleanly.
2454 void ThreadsManager::exit_threads() {
2456 allThreadsShouldExit = true; // Let the woken up threads to exit idle_loop()
2458 // Wake up all the threads and waits for termination
2459 for (int i = 1; i < MAX_THREADS; i++)
2461 wake_sleeping_thread(i);
2462 while (threads[i].state != THREAD_TERMINATED) {}
2465 // Now we can safely destroy the locks
2466 for (int i = 0; i < MAX_THREADS; i++)
2467 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2468 lock_destroy(&(threads[i].splitPoints[j].lock));
2470 lock_destroy(&mpLock);
2472 // Now we can safely destroy the wait conditions
2473 for (int i = 0; i < MAX_THREADS; i++)
2475 lock_destroy(&sleepLock[i]);
2476 cond_destroy(&sleepCond[i]);
2481 // cutoff_at_splitpoint() checks whether a beta cutoff has occurred in
2482 // the thread's currently active split point, or in some ancestor of
2483 // the current split point.
2485 bool ThreadsManager::cutoff_at_splitpoint(int threadID) const {
2487 assert(threadID >= 0 && threadID < activeThreads);
2489 SplitPoint* sp = threads[threadID].splitPoint;
2491 for ( ; sp && !sp->betaCutoff; sp = sp->parent) {}
2496 // thread_is_available() checks whether the thread with threadID "slave" is
2497 // available to help the thread with threadID "master" at a split point. An
2498 // obvious requirement is that "slave" must be idle. With more than two
2499 // threads, this is not by itself sufficient: If "slave" is the master of
2500 // some active split point, it is only available as a slave to the other
2501 // threads which are busy searching the split point at the top of "slave"'s
2502 // split point stack (the "helpful master concept" in YBWC terminology).
2504 bool ThreadsManager::thread_is_available(int slave, int master) const {
2506 assert(slave >= 0 && slave < activeThreads);
2507 assert(master >= 0 && master < activeThreads);
2508 assert(activeThreads > 1);
2510 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2513 // Make a local copy to be sure doesn't change under our feet
2514 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2516 // No active split points means that the thread is available as
2517 // a slave for any other thread.
2518 if (localActiveSplitPoints == 0 || activeThreads == 2)
2521 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2522 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2523 // could have been set to 0 by another thread leading to an out of bound access.
2524 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2531 // available_thread_exists() tries to find an idle thread which is available as
2532 // a slave for the thread with threadID "master".
2534 bool ThreadsManager::available_thread_exists(int master) const {
2536 assert(master >= 0 && master < activeThreads);
2537 assert(activeThreads > 1);
2539 for (int i = 0; i < activeThreads; i++)
2540 if (thread_is_available(i, master))
2547 // split() does the actual work of distributing the work at a node between
2548 // several available threads. If it does not succeed in splitting the
2549 // node (because no idle threads are available, or because we have no unused
2550 // split point objects), the function immediately returns. If splitting is
2551 // possible, a SplitPoint object is initialized with all the data that must be
2552 // copied to the helper threads and we tell our helper threads that they have
2553 // been assigned work. This will cause them to instantly leave their idle loops and
2554 // call search().When all threads have returned from search() then split() returns.
2556 template <bool Fake>
2557 void ThreadsManager::split(Position& pos, SearchStack* ss, int ply, Value* alpha,
2558 const Value beta, Value* bestValue, Depth depth, Move threatMove,
2559 bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) {
2560 assert(pos.is_ok());
2561 assert(ply > 0 && ply < PLY_MAX);
2562 assert(*bestValue >= -VALUE_INFINITE);
2563 assert(*bestValue <= *alpha);
2564 assert(*alpha < beta);
2565 assert(beta <= VALUE_INFINITE);
2566 assert(depth > DEPTH_ZERO);
2567 assert(pos.thread() >= 0 && pos.thread() < activeThreads);
2568 assert(activeThreads > 1);
2570 int i, master = pos.thread();
2571 Thread& masterThread = threads[master];
2575 // If no other thread is available to help us, or if we have too many
2576 // active split points, don't split.
2577 if ( !available_thread_exists(master)
2578 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2580 lock_release(&mpLock);
2584 // Pick the next available split point object from the split point stack
2585 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2587 // Initialize the split point object
2588 splitPoint.parent = masterThread.splitPoint;
2589 splitPoint.master = master;
2590 splitPoint.betaCutoff = false;
2591 splitPoint.ply = ply;
2592 splitPoint.depth = depth;
2593 splitPoint.threatMove = threatMove;
2594 splitPoint.mateThreat = mateThreat;
2595 splitPoint.alpha = *alpha;
2596 splitPoint.beta = beta;
2597 splitPoint.pvNode = pvNode;
2598 splitPoint.bestValue = *bestValue;
2600 splitPoint.moveCount = moveCount;
2601 splitPoint.pos = &pos;
2602 splitPoint.nodes = 0;
2603 splitPoint.parentSstack = ss;
2604 for (i = 0; i < activeThreads; i++)
2605 splitPoint.slaves[i] = 0;
2607 masterThread.splitPoint = &splitPoint;
2609 // If we are here it means we are not available
2610 assert(masterThread.state != THREAD_AVAILABLE);
2612 int workersCnt = 1; // At least the master is included
2614 // Allocate available threads setting state to THREAD_BOOKED
2615 for (i = 0; !Fake && i < activeThreads && workersCnt < maxThreadsPerSplitPoint; i++)
2616 if (thread_is_available(i, master))
2618 threads[i].state = THREAD_BOOKED;
2619 threads[i].splitPoint = &splitPoint;
2620 splitPoint.slaves[i] = 1;
2624 assert(Fake || workersCnt > 1);
2626 // We can release the lock because slave threads are already booked and master is not available
2627 lock_release(&mpLock);
2629 // Tell the threads that they have work to do. This will make them leave
2630 // their idle loop. But before copy search stack tail for each thread.
2631 for (i = 0; i < activeThreads; i++)
2632 if (i == master || splitPoint.slaves[i])
2634 memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
2636 assert(i == master || threads[i].state == THREAD_BOOKED);
2638 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2640 if (useSleepingThreads && i != master)
2641 wake_sleeping_thread(i);
2644 // Everything is set up. The master thread enters the idle loop, from
2645 // which it will instantly launch a search, because its state is
2646 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2647 // idle loop, which means that the main thread will return from the idle
2648 // loop when all threads have finished their work at this split point.
2649 idle_loop(master, &splitPoint);
2651 // We have returned from the idle loop, which means that all threads are
2652 // finished. Update alpha and bestValue, and return.
2655 *alpha = splitPoint.alpha;
2656 *bestValue = splitPoint.bestValue;
2657 masterThread.activeSplitPoints--;
2658 masterThread.splitPoint = splitPoint.parent;
2659 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
2661 lock_release(&mpLock);
2665 // wake_sleeping_thread() wakes up the thread with the given threadID
2666 // when it is time to start a new search.
2668 void ThreadsManager::wake_sleeping_thread(int threadID) {
2670 lock_grab(&sleepLock[threadID]);
2671 cond_signal(&sleepCond[threadID]);
2672 lock_release(&sleepLock[threadID]);
2676 /// The RootMoveList class
2678 // RootMoveList c'tor
2680 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) {
2682 SearchStack ss[PLY_MAX_PLUS_2];
2683 MoveStack mlist[MOVES_MAX];
2685 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
2687 // Initialize search stack
2688 init_ss_array(ss, PLY_MAX_PLUS_2);
2689 ss[0].eval = ss[0].evalMargin = VALUE_NONE;
2691 // Generate all legal moves
2692 MoveStack* last = generate_moves(pos, mlist);
2694 // Add each move to the moves[] array
2695 for (MoveStack* cur = mlist; cur != last; cur++)
2697 bool includeMove = includeAllMoves;
2699 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
2700 includeMove = (searchMoves[k] == cur->move);
2705 // Find a quick score for the move and add to the list
2707 rm.move = ss[0].currentMove = rm.pv[0] = cur->move;
2708 rm.pv[1] = MOVE_NONE;
2709 pos.do_move(cur->move, st);
2710 rm.pv_score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
2711 pos.undo_move(cur->move);
2717 // Score root moves using the standard way used in main search, the moves
2718 // are scored according to the order in which are returned by MovePicker.
2719 // This is the second order score that is used to compare the moves when
2720 // the first order pv scores of both moves are equal.
2722 void RootMoveList::set_non_pv_scores(const Position& pos)
2725 Value score = VALUE_ZERO;
2726 MovePicker mp(pos, MOVE_NONE, ONE_PLY, H);
2728 while ((move = mp.get_next_move()) != MOVE_NONE)
2729 for (Base::iterator it = begin(); it != end(); ++it)
2730 if (it->move == move)
2732 it->non_pv_score = score--;
2737 // RootMoveList::sort_multipv() sorts the first few moves in the root move
2738 // list by their scores and depths. It is used to order the different PVs
2739 // correctly in MultiPV mode.
2741 void RootMoveList::sort_multipv(int n) {
2745 for (i = 1; i <= n; i++)
2747 const RootMove rm = this->at(i);
2748 for (j = i; j > 0 && this->at(j - 1) < rm; j--)
2749 (*this)[j] = this->at(j - 1);