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/>.
40 #include "ucioption.h"
47 // Different node types, used as template parameter
48 enum NodeType { NonPV, PV };
50 // Set to true to force running with one thread. Used for debugging.
51 const bool FakeSplit = false;
53 // Lookup table to check if a Piece is a slider and its access function
54 const bool Slidings[18] = { 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1 };
55 inline bool piece_is_slider(Piece p) { return Slidings[p]; }
57 // ThreadsManager class is used to handle all the threads related stuff like init,
58 // starting, parking and, the most important, launching a slave thread at a split
59 // point. All the access to shared thread data is done through this class.
61 class ThreadsManager {
62 /* As long as the single ThreadsManager object is defined as a global we don't
63 need to explicitly initialize to zero its data members because variables with
64 static storage duration are automatically set to zero before enter main()
70 int min_split_depth() const { return minimumSplitDepth; }
71 int active_threads() const { return activeThreads; }
72 void set_active_threads(int cnt) { activeThreads = cnt; }
74 void read_uci_options();
75 bool available_thread_exists(int master) const;
76 bool thread_is_available(int slave, int master) const;
77 bool cutoff_at_splitpoint(int threadID) const;
78 void wake_sleeping_thread(int threadID);
79 void idle_loop(int threadID, SplitPoint* sp);
82 void split(Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
83 Depth depth, Move threatMove, bool mateThreat, int moveCount, MovePicker* mp, bool pvNode);
86 Depth minimumSplitDepth;
87 int maxThreadsPerSplitPoint;
88 bool useSleepingThreads;
90 volatile bool allThreadsShouldExit;
91 Thread threads[MAX_THREADS];
92 Lock mpLock, sleepLock[MAX_THREADS];
93 WaitCondition sleepCond[MAX_THREADS];
97 // RootMove struct is used for moves at the root of the tree. For each root
98 // move, we store two scores, a node count, and a PV (really a refutation
99 // in the case of moves which fail low). Value pv_score is normally set at
100 // -VALUE_INFINITE for all non-pv moves, while non_pv_score is computed
101 // according to the order in which moves are returned by MovePicker.
106 RootMove(const RootMove& rm) { *this = rm; }
107 RootMove& operator=(const RootMove& rm);
109 // RootMove::operator<() is the comparison function used when
110 // sorting the moves. A move m1 is considered to be better
111 // than a move m2 if it has an higher pv_score, or if it has
112 // equal pv_score but m1 has the higher non_pv_score. In this way
113 // we are guaranteed that PV moves are always sorted as first.
114 bool operator<(const RootMove& m) const {
115 return pv_score != m.pv_score ? pv_score < m.pv_score
116 : non_pv_score < m.non_pv_score;
119 void extract_pv_from_tt(Position& pos);
120 void insert_pv_in_tt(Position& pos);
121 std::string pv_info_to_uci(Position& pos, int depth, Value alpha, Value beta, int pvIdx);
126 Move pv[PLY_MAX_PLUS_2];
130 // RootMoveList struct is just a std::vector<> of RootMove objects,
131 // with an handful of methods above the standard ones.
133 struct RootMoveList : public std::vector<RootMove> {
135 typedef std::vector<RootMove> Base;
137 void init(Position& pos, Move searchMoves[]);
138 void sort() { insertion_sort<RootMove, Base::iterator>(begin(), end()); }
139 void sort_multipv(int n) { insertion_sort<RootMove, Base::iterator>(begin(), begin() + n); }
145 // Overload operator<<() to make it easier to print moves in a coordinate
146 // notation compatible with UCI protocol.
147 std::ostream& operator<<(std::ostream& os, Move m) {
149 bool chess960 = (os.iword(0) != 0); // See set960()
150 return os << move_to_uci(m, chess960);
154 // When formatting a move for std::cout we must know if we are in Chess960
155 // or not. To keep using the handy operator<<() on the move the trick is to
156 // embed this flag in the stream itself. Function-like named enum set960 is
157 // used as a custom manipulator and the stream internal general-purpose array,
158 // accessed through ios_base::iword(), is used to pass the flag to the move's
159 // operator<<() that will read it to properly format castling moves.
162 std::ostream& operator<< (std::ostream& os, const set960& f) {
164 os.iword(0) = int(f);
173 // Maximum depth for razoring
174 const Depth RazorDepth = 4 * ONE_PLY;
176 // Dynamic razoring margin based on depth
177 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
179 // Maximum depth for use of dynamic threat detection when null move fails low
180 const Depth ThreatDepth = 5 * ONE_PLY;
182 // Step 9. Internal iterative deepening
184 // Minimum depth for use of internal iterative deepening
185 const Depth IIDDepth[2] = { 8 * ONE_PLY /* non-PV */, 5 * ONE_PLY /* PV */};
187 // At Non-PV nodes we do an internal iterative deepening search
188 // when the static evaluation is bigger then beta - IIDMargin.
189 const Value IIDMargin = Value(0x100);
191 // Step 11. Decide the new search depth
193 // Extensions. Configurable UCI options
194 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
195 Depth CheckExtension[2], PawnPushTo7thExtension[2], PassedPawnExtension[2];
196 Depth PawnEndgameExtension[2], MateThreatExtension[2];
198 // Minimum depth for use of singular extension
199 const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */};
201 // Step 12. Futility pruning
203 // Futility margin for quiescence search
204 const Value FutilityMarginQS = Value(0x80);
206 // Futility lookup tables (initialized at startup) and their access functions
207 Value FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
208 int FutilityMoveCountArray[32]; // [depth]
210 inline Value futility_margin(Depth d, int mn) { return d < 7 * ONE_PLY ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE; }
211 inline int futility_move_count(Depth d) { return d < 16 * ONE_PLY ? FutilityMoveCountArray[d] : 512; }
213 // Step 14. Reduced search
215 // Reduction lookup tables (initialized at startup) and their getter functions
216 int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
218 template <NodeType PV>
219 inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
221 // Easy move margin. An easy move candidate must be at least this much
222 // better than the second best move.
223 const Value EasyMoveMargin = Value(0x200);
226 /// Namespace variables
235 int MultiPV, UCIMultiPV;
237 // Time management variables
238 int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
239 bool UseTimeManagement, InfiniteSearch, Pondering, StopOnPonderhit;
240 bool FirstRootMove, StopRequest, QuitRequest, AspirationFailLow;
245 std::ofstream LogFile;
247 // Skill level adjustment
249 bool SkillLevelEnabled;
252 // Multi-threads manager
253 ThreadsManager ThreadsMgr;
255 // Node counters, used only by thread[0] but try to keep in different cache
256 // lines (64 bytes each) from the heavy multi-thread read accessed variables.
257 bool SendSearchedNodes;
259 int NodesBetweenPolls = 30000;
267 Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove);
269 template <NodeType PvNode, bool SpNode, bool Root>
270 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
272 template <NodeType PvNode>
273 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
275 template <NodeType PvNode>
276 inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
278 return depth < ONE_PLY ? qsearch<PvNode>(pos, ss, alpha, beta, DEPTH_ZERO, ply)
279 : search<PvNode, false, false>(pos, ss, alpha, beta, depth, ply);
282 template <NodeType PvNode>
283 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool mateThreat, bool* dangerous);
285 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue);
286 bool connected_moves(const Position& pos, Move m1, Move m2);
287 Value value_to_tt(Value v, int ply);
288 Value value_from_tt(Value v, int ply);
289 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
290 bool connected_threat(const Position& pos, Move m, Move threat);
291 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
292 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
293 void update_gains(const Position& pos, Move move, Value before, Value after);
294 void do_skill_level(Move* best, Move* ponder);
296 int current_search_time();
297 std::string value_to_uci(Value v);
298 std::string speed_to_uci(int64_t nodes);
299 void poll(const Position& pos);
300 void wait_for_stop_or_ponderhit();
302 #if !defined(_MSC_VER)
303 void* init_thread(void* threadID);
305 DWORD WINAPI init_thread(LPVOID threadID);
309 // MovePickerExt is an extended MovePicker used to choose at compile time
310 // the proper move source according to the type of node.
311 template<bool SpNode, bool Root> struct MovePickerExt;
313 // In Root nodes use RootMoveList as source. Score and sort the root moves
314 // before to search them.
315 template<> struct MovePickerExt<false, true> : public MovePicker {
317 MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b)
318 : MovePicker(p, ttm, d, h, ss, b), firstCall(true) {
320 Value score = VALUE_ZERO;
322 // Score root moves using standard ordering used in main search, the moves
323 // are scored according to the order in which they are returned by MovePicker.
324 // This is the second order score that is used to compare the moves when
325 // the first orders pv_score of both moves are equal.
326 while ((move = MovePicker::get_next_move()) != MOVE_NONE)
327 for (rm = Rml.begin(); rm != Rml.end(); ++rm)
328 if (rm->pv[0] == move)
330 rm->non_pv_score = score--;
338 Move get_next_move() {
345 return rm != Rml.end() ? rm->pv[0] : MOVE_NONE;
348 RootMoveList::iterator rm;
352 // In SpNodes use split point's shared MovePicker object as move source
353 template<> struct MovePickerExt<true, false> : public MovePicker {
355 MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b)
356 : MovePicker(p, ttm, d, h, ss, b), mp(ss->sp->mp) {}
358 Move get_next_move() { return mp->get_next_move(); }
360 RootMoveList::iterator rm; // Dummy, needed to compile
364 // Default case, create and use a MovePicker object as source
365 template<> struct MovePickerExt<false, false> : public MovePicker {
367 MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b)
368 : MovePicker(p, ttm, d, h, ss, b) {}
370 RootMoveList::iterator rm; // Dummy, needed to compile
376 /// init_threads() is called during startup. It initializes various lookup tables
377 /// and creates and launches search threads.
379 void init_threads() {
381 int d; // depth (ONE_PLY == 2)
382 int hd; // half depth (ONE_PLY == 1)
385 // Init reductions array
386 for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
388 double pvRed = log(double(hd)) * log(double(mc)) / 3.0;
389 double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
390 ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0);
391 ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0);
394 // Init futility margins array
395 for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
396 FutilityMarginsMatrix[d][mc] = Value(112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45);
398 // Init futility move count array
399 for (d = 0; d < 32; d++)
400 FutilityMoveCountArray[d] = int(3.001 + 0.25 * pow(d, 2.0));
402 // Create and startup threads
403 ThreadsMgr.init_threads();
407 /// exit_threads() is a trampoline to access ThreadsMgr from outside of current file
408 void exit_threads() { ThreadsMgr.exit_threads(); }
411 /// perft() is our utility to verify move generation. All the legal moves up to
412 /// given depth are generated and counted and the sum returned.
414 int64_t perft(Position& pos, Depth depth) {
416 MoveStack mlist[MOVES_MAX];
421 // Generate all legal moves
422 MoveStack* last = generate<MV_LEGAL>(pos, mlist);
424 // If we are at the last ply we don't need to do and undo
425 // the moves, just to count them.
426 if (depth <= ONE_PLY)
427 return int(last - mlist);
429 // Loop through all legal moves
431 for (MoveStack* cur = mlist; cur != last; cur++)
434 pos.do_move(m, st, ci, pos.move_is_check(m, ci));
435 sum += perft(pos, depth - ONE_PLY);
442 /// think() is the external interface to Stockfish's search, and is called when
443 /// the program receives the UCI 'go' command. It initializes various global
444 /// variables, and calls id_loop(). It returns false when a quit command is
445 /// received during the search.
447 bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[],
448 int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) {
450 // Initialize global search-related variables
451 StopOnPonderhit = StopRequest = QuitRequest = AspirationFailLow = SendSearchedNodes = false;
453 SearchStartTime = get_system_time();
454 ExactMaxTime = maxTime;
457 InfiniteSearch = infinite;
459 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
461 // Look for a book move, only during games, not tests
462 if (UseTimeManagement && Options["OwnBook"].value<bool>())
464 if (Options["Book File"].value<std::string>() != OpeningBook.name())
465 OpeningBook.open(Options["Book File"].value<std::string>());
467 Move bookMove = OpeningBook.get_move(pos, Options["Best Book Move"].value<bool>());
468 if (bookMove != MOVE_NONE)
471 wait_for_stop_or_ponderhit();
473 cout << "bestmove " << bookMove << endl;
479 CheckExtension[1] = Options["Check Extension (PV nodes)"].value<Depth>();
480 CheckExtension[0] = Options["Check Extension (non-PV nodes)"].value<Depth>();
481 PawnPushTo7thExtension[1] = Options["Pawn Push to 7th Extension (PV nodes)"].value<Depth>();
482 PawnPushTo7thExtension[0] = Options["Pawn Push to 7th Extension (non-PV nodes)"].value<Depth>();
483 PassedPawnExtension[1] = Options["Passed Pawn Extension (PV nodes)"].value<Depth>();
484 PassedPawnExtension[0] = Options["Passed Pawn Extension (non-PV nodes)"].value<Depth>();
485 PawnEndgameExtension[1] = Options["Pawn Endgame Extension (PV nodes)"].value<Depth>();
486 PawnEndgameExtension[0] = Options["Pawn Endgame Extension (non-PV nodes)"].value<Depth>();
487 MateThreatExtension[1] = Options["Mate Threat Extension (PV nodes)"].value<Depth>();
488 MateThreatExtension[0] = Options["Mate Threat Extension (non-PV nodes)"].value<Depth>();
489 UCIMultiPV = Options["MultiPV"].value<int>();
490 SkillLevel = Options["Skill level"].value<int>();
491 UseLogFile = Options["Use Search Log"].value<bool>();
493 read_evaluation_uci_options(pos.side_to_move());
495 if (Options["Clear Hash"].value<bool>())
497 Options["Clear Hash"].set_value("false");
500 TT.set_size(Options["Hash"].value<int>());
502 // Do we have to play with skill handicap? In this case enable MultiPV that
503 // we will use behind the scenes to retrieve a set of possible moves.
504 SkillLevelEnabled = (SkillLevel < 20);
505 MultiPV = (SkillLevelEnabled ? Max(UCIMultiPV, 4) : UCIMultiPV);
507 // Set the number of active threads
508 ThreadsMgr.read_uci_options();
509 init_eval(ThreadsMgr.active_threads());
511 // Wake up needed threads. Main thread, with threadID == 0, is always active
512 for (int i = 1; i < ThreadsMgr.active_threads(); i++)
513 ThreadsMgr.wake_sleeping_thread(i);
516 int myTime = time[pos.side_to_move()];
517 int myIncrement = increment[pos.side_to_move()];
518 if (UseTimeManagement)
519 TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter());
521 // Set best NodesBetweenPolls interval to avoid lagging under time pressure
523 NodesBetweenPolls = Min(MaxNodes, 30000);
524 else if (myTime && myTime < 1000)
525 NodesBetweenPolls = 1000;
526 else if (myTime && myTime < 5000)
527 NodesBetweenPolls = 5000;
529 NodesBetweenPolls = 30000;
531 // Write search information to log file
534 std::string name = Options["Search Log Filename"].value<std::string>();
535 LogFile.open(name.c_str(), std::ios::out | std::ios::app);
537 LogFile << "\nSearching: " << pos.to_fen()
538 << "\ninfinite: " << infinite
539 << " ponder: " << ponder
540 << " time: " << myTime
541 << " increment: " << myIncrement
542 << " moves to go: " << movesToGo
546 // We're ready to start thinking. Call the iterative deepening loop function
547 Move ponderMove = MOVE_NONE;
548 Move bestMove = id_loop(pos, searchMoves, &ponderMove);
550 // Print final search statistics
551 cout << "info" << speed_to_uci(pos.nodes_searched()) << endl;
555 int t = current_search_time();
557 LogFile << "Nodes: " << pos.nodes_searched()
558 << "\nNodes/second: " << (t > 0 ? int(pos.nodes_searched() * 1000 / t) : 0)
559 << "\nBest move: " << move_to_san(pos, bestMove);
562 pos.do_move(bestMove, st);
563 LogFile << "\nPonder move: " << move_to_san(pos, ponderMove) << endl;
564 pos.undo_move(bestMove); // Return from think() with unchanged position
568 // This makes all the threads to go to sleep
569 ThreadsMgr.set_active_threads(1);
571 // If we are pondering or in infinite search, we shouldn't print the
572 // best move before we are told to do so.
573 if (!StopRequest && (Pondering || InfiniteSearch))
574 wait_for_stop_or_ponderhit();
576 // Could be MOVE_NONE when searching on a stalemate position
577 cout << "bestmove " << bestMove;
579 // UCI protol is not clear on allowing sending an empty ponder move, instead
580 // it is clear that ponder move is optional. So skip it if empty.
581 if (ponderMove != MOVE_NONE)
582 cout << " ponder " << ponderMove;
592 // id_loop() is the main iterative deepening loop. It calls search() repeatedly
593 // with increasing depth until the allocated thinking time has been consumed,
594 // user stops the search, or the maximum search depth is reached.
596 Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove) {
598 SearchStack ss[PLY_MAX_PLUS_2];
599 Value bestValues[PLY_MAX_PLUS_2];
600 int bestMoveChanges[PLY_MAX_PLUS_2];
601 int depth, aspirationDelta, skillSamplingDepth;
602 Value value, alpha, beta;
603 Move bestMove, easyMove, skillBest, skillPonder;
605 // Initialize stuff before a new search
606 memset(ss, 0, 4 * sizeof(SearchStack));
609 *ponderMove = bestMove = easyMove = skillBest = skillPonder = MOVE_NONE;
610 depth = aspirationDelta = skillSamplingDepth = 0;
611 alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
612 ss->currentMove = MOVE_NULL; // Hack to skip update_gains()
614 // Moves to search are verified and copied
615 Rml.init(pos, searchMoves);
617 // Handle special case of searching on a mate/stalemate position
620 cout << "info depth 0 score "
621 << value_to_uci(pos.is_check() ? -VALUE_MATE : VALUE_DRAW)
627 // Choose a random sampling depth according to SkillLevel so that at low
628 // skills there is an higher risk to pick up a blunder.
629 if (SkillLevelEnabled)
630 skillSamplingDepth = 4 + SkillLevel + (RK.rand<unsigned>() % 4);
632 // Iterative deepening loop
633 while (++depth <= PLY_MAX && (!MaxDepth || depth <= MaxDepth) && !StopRequest)
635 Rml.bestMoveChanges = 0;
636 cout << set960(pos.is_chess960()) << "info depth " << depth << endl;
638 // Calculate dynamic aspiration window based on previous iterations
639 if (MultiPV == 1 && depth >= 5 && abs(bestValues[depth - 1]) < VALUE_KNOWN_WIN)
641 int prevDelta1 = bestValues[depth - 1] - bestValues[depth - 2];
642 int prevDelta2 = bestValues[depth - 2] - bestValues[depth - 3];
644 aspirationDelta = Min(Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16), 24);
645 aspirationDelta = (aspirationDelta + 7) / 8 * 8; // Round to match grainSize
647 alpha = Max(bestValues[depth - 1] - aspirationDelta, -VALUE_INFINITE);
648 beta = Min(bestValues[depth - 1] + aspirationDelta, VALUE_INFINITE);
651 // Start with a small aspiration window and, in case of fail high/low,
652 // research with bigger window until not failing high/low anymore.
654 // Search starting from ss+1 to allow calling update_gains()
655 value = search<PV, false, true>(pos, ss+1, alpha, beta, depth * ONE_PLY, 0);
657 // Write PV back to transposition table in case the relevant entries
658 // have been overwritten during the search.
659 for (int i = 0; i < Min(MultiPV, (int)Rml.size()); i++)
660 Rml[i].insert_pv_in_tt(pos);
662 // Value cannot be trusted. Break out immediately!
666 assert(value >= alpha);
668 // In case of failing high/low increase aspiration window and research,
669 // otherwise exit the fail high/low loop.
672 beta = Min(beta + aspirationDelta, VALUE_INFINITE);
673 aspirationDelta += aspirationDelta / 2;
675 else if (value <= alpha)
677 AspirationFailLow = true;
678 StopOnPonderhit = false;
680 alpha = Max(alpha - aspirationDelta, -VALUE_INFINITE);
681 aspirationDelta += aspirationDelta / 2;
686 } while (abs(value) < VALUE_KNOWN_WIN);
688 // Collect info about search result
689 bestMove = Rml[0].pv[0];
690 *ponderMove = Rml[0].pv[1];
691 bestValues[depth] = value;
692 bestMoveChanges[depth] = Rml.bestMoveChanges;
694 // Do we need to pick now the best and the ponder moves ?
695 if (SkillLevelEnabled && depth == skillSamplingDepth)
696 do_skill_level(&skillBest, &skillPonder);
698 // Send PV line to GUI and to log file
699 for (int i = 0; i < Min(UCIMultiPV, (int)Rml.size()); i++)
700 cout << Rml[i].pv_info_to_uci(pos, depth, alpha, beta, i) << endl;
703 LogFile << pretty_pv(pos, depth, value, current_search_time(), Rml[0].pv) << endl;
705 // Init easyMove after first iteration or drop if differs from the best move
706 if (depth == 1 && (Rml.size() == 1 || Rml[0].pv_score > Rml[1].pv_score + EasyMoveMargin))
708 else if (bestMove != easyMove)
709 easyMove = MOVE_NONE;
711 if (UseTimeManagement && !StopRequest)
714 bool noMoreTime = false;
716 // Stop search early when the last two iterations returned a mate score
718 && abs(bestValues[depth]) >= abs(VALUE_MATE) - 100
719 && abs(bestValues[depth - 1]) >= abs(VALUE_MATE) - 100)
722 // Stop search early if one move seems to be much better than the
723 // others or if there is only a single legal move. In this latter
724 // case we search up to Iteration 8 anyway to get a proper score.
726 && easyMove == bestMove
728 ||( Rml[0].nodes > (pos.nodes_searched() * 85) / 100
729 && current_search_time() > TimeMgr.available_time() / 16)
730 ||( Rml[0].nodes > (pos.nodes_searched() * 98) / 100
731 && current_search_time() > TimeMgr.available_time() / 32)))
734 // Add some extra time if the best move has changed during the last two iterations
735 if (depth > 4 && depth < 50)
736 TimeMgr.pv_instability(bestMoveChanges[depth], bestMoveChanges[depth-1]);
738 // Stop search if most of MaxSearchTime is consumed at the end of the
739 // iteration. We probably don't have enough time to search the first
740 // move at the next iteration anyway.
741 if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
747 StopOnPonderhit = true;
754 // When using skills fake best and ponder moves with the sub-optimal ones
755 if (SkillLevelEnabled)
757 if (skillBest == MOVE_NONE) // Still unassigned ?
758 do_skill_level(&skillBest, &skillPonder);
760 bestMove = skillBest;
761 *ponderMove = skillPonder;
768 // search<>() is the main search function for both PV and non-PV nodes and for
769 // normal and SplitPoint nodes. When called just after a split point the search
770 // is simpler because we have already probed the hash table, done a null move
771 // search, and searched the first move before splitting, we don't have to repeat
772 // all this work again. We also don't need to store anything to the hash table
773 // here: This is taken care of after we return from the split point.
775 template <NodeType PvNode, bool SpNode, bool Root>
776 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
778 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
779 assert(beta > alpha && beta <= VALUE_INFINITE);
780 assert(PvNode || alpha == beta - 1);
781 assert((Root || ply > 0) && ply < PLY_MAX);
782 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
784 Move movesSearched[MOVES_MAX];
789 Move ttMove, move, excludedMove, threatMove;
792 Value bestValue, value, oldAlpha;
793 Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
794 bool isPvMove, isCheck, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous, isBadCap;
795 bool mateThreat = false;
796 int moveCount = 0, playedMoveCount = 0;
797 int threadID = pos.thread();
798 SplitPoint* sp = NULL;
800 refinedValue = bestValue = value = -VALUE_INFINITE;
802 isCheck = pos.is_check();
808 ttMove = excludedMove = MOVE_NONE;
809 threatMove = sp->threatMove;
810 mateThreat = sp->mateThreat;
811 goto split_point_start;
816 // Step 1. Initialize node and poll. Polling can abort search
817 ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE;
818 (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO;
819 (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
821 if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
827 // Step 2. Check for aborted search and immediate draw
829 || ThreadsMgr.cutoff_at_splitpoint(threadID)
831 || ply >= PLY_MAX - 1) && !Root)
834 // Step 3. Mate distance pruning
835 alpha = Max(value_mated_in(ply), alpha);
836 beta = Min(value_mate_in(ply+1), beta);
840 // Step 4. Transposition table lookup
841 // We don't want the score of a partial search to overwrite a previous full search
842 // TT value, so we use a different position key in case of an excluded move.
843 excludedMove = ss->excludedMove;
844 posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
846 tte = TT.retrieve(posKey);
847 ttMove = tte ? tte->move() : MOVE_NONE;
849 // At PV nodes we check for exact scores, while at non-PV nodes we check for
850 // a fail high/low. Biggest advantage at probing at PV nodes is to have a
851 // smooth experience in analysis mode.
854 && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT
855 : ok_to_use_TT(tte, depth, beta, ply)))
858 ss->bestMove = ttMove; // Can be MOVE_NONE
859 return value_from_tt(tte->value(), ply);
862 // Step 5. Evaluate the position statically and update parent's gain statistics
864 ss->eval = ss->evalMargin = VALUE_NONE;
867 assert(tte->static_value() != VALUE_NONE);
869 ss->eval = tte->static_value();
870 ss->evalMargin = tte->static_value_margin();
871 refinedValue = refine_eval(tte, ss->eval, ply);
875 refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
876 TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
879 // Save gain for the parent non-capture move
880 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
882 // Step 6. Razoring (is omitted in PV nodes)
884 && depth < RazorDepth
886 && refinedValue + razor_margin(depth) < beta
887 && ttMove == MOVE_NONE
888 && abs(beta) < VALUE_MATE_IN_PLY_MAX
889 && !pos.has_pawn_on_7th(pos.side_to_move()))
891 Value rbeta = beta - razor_margin(depth);
892 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply);
894 // Logically we should return (v + razor_margin(depth)), but
895 // surprisingly this did slightly weaker in tests.
899 // Step 7. Static null move pruning (is omitted in PV nodes)
900 // We're betting that the opponent doesn't have a move that will reduce
901 // the score by more than futility_margin(depth) if we do a null move.
904 && depth < RazorDepth
906 && refinedValue - futility_margin(depth, 0) >= beta
907 && abs(beta) < VALUE_MATE_IN_PLY_MAX
908 && pos.non_pawn_material(pos.side_to_move()))
909 return refinedValue - futility_margin(depth, 0);
911 // Step 8. Null move search with verification search (is omitted in PV nodes)
916 && refinedValue >= beta
917 && abs(beta) < VALUE_MATE_IN_PLY_MAX
918 && pos.non_pawn_material(pos.side_to_move()))
920 ss->currentMove = MOVE_NULL;
922 // Null move dynamic reduction based on depth
923 int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
925 // Null move dynamic reduction based on value
926 if (refinedValue - PawnValueMidgame > beta)
929 pos.do_null_move(st);
930 (ss+1)->skipNullMove = true;
931 nullValue = -search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1);
932 (ss+1)->skipNullMove = false;
933 pos.undo_null_move();
935 if (nullValue >= beta)
937 // Do not return unproven mate scores
938 if (nullValue >= VALUE_MATE_IN_PLY_MAX)
941 if (depth < 6 * ONE_PLY)
944 // Do verification search at high depths
945 ss->skipNullMove = true;
946 Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY, ply);
947 ss->skipNullMove = false;
954 // The null move failed low, which means that we may be faced with
955 // some kind of threat. If the previous move was reduced, check if
956 // the move that refuted the null move was somehow connected to the
957 // move which was reduced. If a connection is found, return a fail
958 // low score (which will cause the reduced move to fail high in the
959 // parent node, which will trigger a re-search with full depth).
960 if (nullValue == value_mated_in(ply + 2))
963 threatMove = (ss+1)->bestMove;
965 if ( depth < ThreatDepth
967 && threatMove != MOVE_NONE
968 && connected_moves(pos, (ss-1)->currentMove, threatMove))
973 // Step 9. Internal iterative deepening
974 if ( depth >= IIDDepth[PvNode]
975 && ttMove == MOVE_NONE
976 && (PvNode || (!isCheck && ss->eval + IIDMargin >= beta)))
978 Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
980 ss->skipNullMove = true;
981 search<PvNode>(pos, ss, alpha, beta, d, ply);
982 ss->skipNullMove = false;
984 ttMove = ss->bestMove;
985 tte = TT.retrieve(posKey);
988 // Mate threat detection for PV nodes, otherwise we use null move search
990 mateThreat = pos.has_mate_threat();
992 split_point_start: // At split points actual search starts from here
994 // Initialize a MovePicker object for the current position
995 MovePickerExt<SpNode, Root> mp(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
997 ss->bestMove = MOVE_NONE;
998 futilityBase = ss->eval + ss->evalMargin;
999 singularExtensionNode = !Root
1001 && depth >= SingularExtensionDepth[PvNode]
1004 && !excludedMove // Do not allow recursive singular extension search
1005 && (tte->type() & VALUE_TYPE_LOWER)
1006 && tte->depth() >= depth - 3 * ONE_PLY;
1009 lock_grab(&(sp->lock));
1010 bestValue = sp->bestValue;
1013 // Step 10. Loop through moves
1014 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1015 while ( bestValue < beta
1016 && (move = mp.get_next_move()) != MOVE_NONE
1017 && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1019 assert(move_is_ok(move));
1023 moveCount = ++sp->moveCount;
1024 lock_release(&(sp->lock));
1026 else if (move == excludedMove)
1033 // This is used by time management
1034 FirstRootMove = (moveCount == 1);
1036 // Save the current node count before the move is searched
1037 nodes = pos.nodes_searched();
1039 // If it's time to send nodes info, do it here where we have the
1040 // correct accumulated node counts searched by each thread.
1041 if (SendSearchedNodes)
1043 SendSearchedNodes = false;
1044 cout << "info" << speed_to_uci(pos.nodes_searched()) << endl;
1047 if (current_search_time() > 2000)
1048 cout << "info currmove " << move
1049 << " currmovenumber " << moveCount << endl;
1052 // At Root and at first iteration do a PV search on all the moves to score root moves
1053 isPvMove = (PvNode && moveCount <= (Root ? depth <= ONE_PLY ? 1000 : MultiPV : 1));
1054 moveIsCheck = pos.move_is_check(move, ci);
1055 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1057 // Step 11. Decide the new search depth
1058 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, mateThreat, &dangerous);
1060 // Singular extension search. If all moves but one fail low on a search of
1061 // (alpha-s, beta-s), and just one fails high on (alpha, beta), then that move
1062 // is singular and should be extended. To verify this we do a reduced search
1063 // on all the other moves but the ttMove, if result is lower than ttValue minus
1064 // a margin then we extend ttMove.
1065 if ( singularExtensionNode
1066 && move == tte->move()
1069 Value ttValue = value_from_tt(tte->value(), ply);
1071 if (abs(ttValue) < VALUE_KNOWN_WIN)
1073 Value rBeta = ttValue - int(depth);
1074 ss->excludedMove = move;
1075 ss->skipNullMove = true;
1076 Value v = search<NonPV>(pos, ss, rBeta - 1, rBeta, depth / 2, ply);
1077 ss->skipNullMove = false;
1078 ss->excludedMove = MOVE_NONE;
1079 ss->bestMove = MOVE_NONE;
1085 // Update current move (this must be done after singular extension search)
1086 ss->currentMove = move;
1087 newDepth = depth - ONE_PLY + ext;
1089 // Step 12. Futility pruning (is omitted in PV nodes)
1091 && !captureOrPromotion
1095 && !move_is_castle(move))
1097 // Move count based pruning
1098 if ( moveCount >= futility_move_count(depth)
1099 && (!threatMove || !connected_threat(pos, move, threatMove))
1100 && bestValue > VALUE_MATED_IN_PLY_MAX) // FIXME bestValue is racy
1103 lock_grab(&(sp->lock));
1108 // Value based pruning
1109 // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
1110 // but fixing this made program slightly weaker.
1111 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1112 futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount)
1113 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1115 if (futilityValueScaled < beta)
1119 lock_grab(&(sp->lock));
1120 if (futilityValueScaled > sp->bestValue)
1121 sp->bestValue = bestValue = futilityValueScaled;
1123 else if (futilityValueScaled > bestValue)
1124 bestValue = futilityValueScaled;
1129 // Prune moves with negative SEE at low depths
1130 if ( predictedDepth < 2 * ONE_PLY
1131 && bestValue > VALUE_MATED_IN_PLY_MAX
1132 && pos.see_sign(move) < 0)
1135 lock_grab(&(sp->lock));
1141 // Bad capture detection. Will be used by prob-cut search
1142 isBadCap = depth >= 3 * ONE_PLY
1143 && depth < 8 * ONE_PLY
1144 && captureOrPromotion
1147 && !move_is_promotion(move)
1148 && abs(alpha) < VALUE_MATE_IN_PLY_MAX
1149 && pos.see_sign(move) < 0;
1151 // Step 13. Make the move
1152 pos.do_move(move, st, ci, moveIsCheck);
1154 if (!SpNode && !captureOrPromotion)
1155 movesSearched[playedMoveCount++] = move;
1157 // Step extra. pv search (only in PV nodes)
1158 // The first move in list is the expected PV
1161 // Aspiration window is disabled in multi-pv case
1162 if (Root && MultiPV > 1)
1163 alpha = -VALUE_INFINITE;
1165 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1169 // Step 14. Reduced depth search
1170 // If the move fails high will be re-searched at full depth.
1171 bool doFullDepthSearch = true;
1172 alpha = SpNode ? sp->alpha : alpha;
1174 if ( depth >= 3 * ONE_PLY
1175 && !captureOrPromotion
1177 && !move_is_castle(move)
1178 && ss->killers[0] != move
1179 && ss->killers[1] != move)
1181 ss->reduction = reduction<PvNode>(depth, moveCount);
1184 alpha = SpNode ? sp->alpha : alpha;
1185 Depth d = newDepth - ss->reduction;
1186 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1188 doFullDepthSearch = (value > alpha);
1190 ss->reduction = DEPTH_ZERO; // Restore original reduction
1193 // Probcut search for bad captures. If a reduced search returns a value
1194 // very below beta then we can (almost) safely prune the bad capture.
1197 ss->reduction = 3 * ONE_PLY;
1198 Value rAlpha = alpha - 300;
1199 Depth d = newDepth - ss->reduction;
1200 value = -search<NonPV>(pos, ss+1, -(rAlpha+1), -rAlpha, d, ply+1);
1201 doFullDepthSearch = (value > rAlpha);
1202 ss->reduction = DEPTH_ZERO; // Restore original reduction
1205 // Step 15. Full depth search
1206 if (doFullDepthSearch)
1208 alpha = SpNode ? sp->alpha : alpha;
1209 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1211 // Step extra. pv search (only in PV nodes)
1212 // Search only for possible new PV nodes, if instead value >= beta then
1213 // parent node fails low with value <= alpha and tries another move.
1214 if (PvNode && value > alpha && (Root || value < beta))
1215 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1219 // Step 16. Undo move
1220 pos.undo_move(move);
1222 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1224 // Step 17. Check for new best move
1227 lock_grab(&(sp->lock));
1228 bestValue = sp->bestValue;
1232 if (value > bestValue && !(SpNode && ThreadsMgr.cutoff_at_splitpoint(threadID)))
1237 sp->bestValue = value;
1239 if (!Root && value > alpha)
1241 if (PvNode && value < beta) // We want always alpha < beta
1249 sp->betaCutoff = true;
1251 if (value == value_mate_in(ply + 1))
1252 ss->mateKiller = move;
1254 ss->bestMove = move;
1257 sp->ss->bestMove = move;
1263 // Finished searching the move. If StopRequest is true, the search
1264 // was aborted because the user interrupted the search or because we
1265 // ran out of time. In this case, the return value of the search cannot
1266 // be trusted, and we break out of the loop without updating the best
1271 // Remember searched nodes counts for this move
1272 mp.rm->nodes += pos.nodes_searched() - nodes;
1274 // PV move or new best move ?
1275 if (isPvMove || value > alpha)
1278 ss->bestMove = move;
1279 mp.rm->pv_score = value;
1280 mp.rm->extract_pv_from_tt(pos);
1282 // We record how often the best move has been changed in each
1283 // iteration. This information is used for time management: When
1284 // the best move changes frequently, we allocate some more time.
1285 if (!isPvMove && MultiPV == 1)
1286 Rml.bestMoveChanges++;
1288 Rml.sort_multipv(moveCount);
1290 // Update alpha. In multi-pv we don't use aspiration window, so
1291 // set alpha equal to minimum score among the PV lines.
1293 alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount?
1294 else if (value > alpha)
1298 mp.rm->pv_score = -VALUE_INFINITE;
1302 // Step 18. Check for split
1305 && depth >= ThreadsMgr.min_split_depth()
1306 && ThreadsMgr.active_threads() > 1
1308 && ThreadsMgr.available_thread_exists(threadID)
1310 && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1311 ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1312 threatMove, mateThreat, moveCount, &mp, PvNode);
1315 // Step 19. Check for mate and stalemate
1316 // All legal moves have been searched and if there are
1317 // no legal moves, it must be mate or stalemate.
1318 // If one move was excluded return fail low score.
1319 if (!SpNode && !moveCount)
1320 return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW;
1322 // Step 20. Update tables
1323 // If the search is not aborted, update the transposition table,
1324 // history counters, and killer moves.
1325 if (!SpNode && !StopRequest && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1327 move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
1328 vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
1329 : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
1331 TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, ss->evalMargin);
1333 // Update killers and history only for non capture moves that fails high
1334 if ( bestValue >= beta
1335 && !pos.move_is_capture_or_promotion(move))
1337 if (move != ss->killers[0])
1339 ss->killers[1] = ss->killers[0];
1340 ss->killers[0] = move;
1342 update_history(pos, move, depth, movesSearched, playedMoveCount);
1348 // Here we have the lock still grabbed
1349 sp->slaves[threadID] = 0;
1350 sp->nodes += pos.nodes_searched();
1351 lock_release(&(sp->lock));
1354 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1359 // qsearch() is the quiescence search function, which is called by the main
1360 // search function when the remaining depth is zero (or, to be more precise,
1361 // less than ONE_PLY).
1363 template <NodeType PvNode>
1364 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1366 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1367 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1368 assert(PvNode || alpha == beta - 1);
1370 assert(ply > 0 && ply < PLY_MAX);
1371 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1375 Value bestValue, value, evalMargin, futilityValue, futilityBase;
1376 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1379 Value oldAlpha = alpha;
1381 ss->bestMove = ss->currentMove = MOVE_NONE;
1383 // Check for an instant draw or maximum ply reached
1384 if (pos.is_draw() || ply >= PLY_MAX - 1)
1387 // Decide whether or not to include checks, this fixes also the type of
1388 // TT entry depth that we are going to use. Note that in qsearch we use
1389 // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
1390 isCheck = pos.is_check();
1391 ttDepth = (isCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS);
1393 // Transposition table lookup. At PV nodes, we don't use the TT for
1394 // pruning, but only for move ordering.
1395 tte = TT.retrieve(pos.get_key());
1396 ttMove = (tte ? tte->move() : MOVE_NONE);
1398 if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ply))
1400 ss->bestMove = ttMove; // Can be MOVE_NONE
1401 return value_from_tt(tte->value(), ply);
1404 // Evaluate the position statically
1407 bestValue = futilityBase = -VALUE_INFINITE;
1408 ss->eval = evalMargin = VALUE_NONE;
1409 enoughMaterial = false;
1415 assert(tte->static_value() != VALUE_NONE);
1417 evalMargin = tte->static_value_margin();
1418 ss->eval = bestValue = tte->static_value();
1421 ss->eval = bestValue = evaluate(pos, evalMargin);
1423 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1425 // Stand pat. Return immediately if static value is at least beta
1426 if (bestValue >= beta)
1429 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1434 if (PvNode && bestValue > alpha)
1437 // Futility pruning parameters, not needed when in check
1438 futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1439 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1442 // Initialize a MovePicker object for the current position, and prepare
1443 // to search the moves. Because the depth is <= 0 here, only captures,
1444 // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
1446 MovePicker mp(pos, ttMove, depth, H);
1449 // Loop through the moves until no moves remain or a beta cutoff occurs
1450 while ( alpha < beta
1451 && (move = mp.get_next_move()) != MOVE_NONE)
1453 assert(move_is_ok(move));
1455 moveIsCheck = pos.move_is_check(move, ci);
1463 && !move_is_promotion(move)
1464 && !pos.move_is_passed_pawn_push(move))
1466 futilityValue = futilityBase
1467 + pos.endgame_value_of_piece_on(move_to(move))
1468 + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1470 if (futilityValue < alpha)
1472 if (futilityValue > bestValue)
1473 bestValue = futilityValue;
1477 // Prune moves with negative or equal SEE
1478 if ( futilityBase < beta
1479 && depth < DEPTH_ZERO
1480 && pos.see(move) <= 0)
1484 // Detect non-capture evasions that are candidate to be pruned
1485 evasionPrunable = isCheck
1486 && bestValue > VALUE_MATED_IN_PLY_MAX
1487 && !pos.move_is_capture(move)
1488 && !pos.can_castle(pos.side_to_move());
1490 // Don't search moves with negative SEE values
1492 && (!isCheck || evasionPrunable)
1494 && !move_is_promotion(move)
1495 && pos.see_sign(move) < 0)
1498 // Don't search useless checks
1503 && !pos.move_is_capture_or_promotion(move)
1504 && ss->eval + PawnValueMidgame / 4 < beta
1505 && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue))
1507 if (ss->eval + PawnValueMidgame / 4 > bestValue)
1508 bestValue = ss->eval + PawnValueMidgame / 4;
1513 // Update current move
1514 ss->currentMove = move;
1516 // Make and search the move
1517 pos.do_move(move, st, ci, moveIsCheck);
1518 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1);
1519 pos.undo_move(move);
1521 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1524 if (value > bestValue)
1530 ss->bestMove = move;
1535 // All legal moves have been searched. A special case: If we're in check
1536 // and no legal moves were found, it is checkmate.
1537 if (isCheck && bestValue == -VALUE_INFINITE)
1538 return value_mated_in(ply);
1540 // Update transposition table
1541 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1542 TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin);
1544 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1550 // check_is_dangerous() tests if a checking move can be pruned in qsearch().
1551 // bestValue is updated only when returning false because in that case move
1554 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bestValue)
1556 Bitboard b, occ, oldAtt, newAtt, kingAtt;
1557 Square from, to, ksq, victimSq;
1560 Value futilityValue, bv = *bestValue;
1562 from = move_from(move);
1564 them = opposite_color(pos.side_to_move());
1565 ksq = pos.king_square(them);
1566 kingAtt = pos.attacks_from<KING>(ksq);
1567 pc = pos.piece_on(from);
1569 occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL << ksq);
1570 oldAtt = pos.attacks_from(pc, from, occ);
1571 newAtt = pos.attacks_from(pc, to, occ);
1573 // Rule 1. Checks which give opponent's king at most one escape square are dangerous
1574 b = kingAtt & ~pos.pieces_of_color(them) & ~newAtt & ~(1ULL << to);
1576 if (!(b && (b & (b - 1))))
1579 // Rule 2. Queen contact check is very dangerous
1580 if ( type_of_piece(pc) == QUEEN
1581 && bit_is_set(kingAtt, to))
1584 // Rule 3. Creating new double threats with checks
1585 b = pos.pieces_of_color(them) & newAtt & ~oldAtt & ~(1ULL << ksq);
1589 victimSq = pop_1st_bit(&b);
1590 futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq);
1592 // Note that here we generate illegal "double move"!
1593 if ( futilityValue >= beta
1594 && pos.see_sign(make_move(from, victimSq)) >= 0)
1597 if (futilityValue > bv)
1601 // Update bestValue only if check is not dangerous (because we will prune the move)
1607 // connected_moves() tests whether two moves are 'connected' in the sense
1608 // that the first move somehow made the second move possible (for instance
1609 // if the moving piece is the same in both moves). The first move is assumed
1610 // to be the move that was made to reach the current position, while the
1611 // second move is assumed to be a move from the current position.
1613 bool connected_moves(const Position& pos, Move m1, Move m2) {
1615 Square f1, t1, f2, t2;
1618 assert(m1 && move_is_ok(m1));
1619 assert(m2 && move_is_ok(m2));
1621 // Case 1: The moving piece is the same in both moves
1627 // Case 2: The destination square for m2 was vacated by m1
1633 // Case 3: Moving through the vacated square
1634 if ( piece_is_slider(pos.piece_on(f2))
1635 && bit_is_set(squares_between(f2, t2), f1))
1638 // Case 4: The destination square for m2 is defended by the moving piece in m1
1639 p = pos.piece_on(t1);
1640 if (bit_is_set(pos.attacks_from(p, t1), t2))
1643 // Case 5: Discovered check, checking piece is the piece moved in m1
1644 if ( piece_is_slider(p)
1645 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1646 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1648 // discovered_check_candidates() works also if the Position's side to
1649 // move is the opposite of the checking piece.
1650 Color them = opposite_color(pos.side_to_move());
1651 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1653 if (bit_is_set(dcCandidates, f2))
1660 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1661 // "plies to mate from the current ply". Non-mate scores are unchanged.
1662 // The function is called before storing a value to the transposition table.
1664 Value value_to_tt(Value v, int ply) {
1666 if (v >= VALUE_MATE_IN_PLY_MAX)
1669 if (v <= VALUE_MATED_IN_PLY_MAX)
1676 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1677 // the transposition table to a mate score corrected for the current ply.
1679 Value value_from_tt(Value v, int ply) {
1681 if (v >= VALUE_MATE_IN_PLY_MAX)
1684 if (v <= VALUE_MATED_IN_PLY_MAX)
1691 // extension() decides whether a move should be searched with normal depth,
1692 // or with extended depth. Certain classes of moves (checking moves, in
1693 // particular) are searched with bigger depth than ordinary moves and in
1694 // any case are marked as 'dangerous'. Note that also if a move is not
1695 // extended, as example because the corresponding UCI option is set to zero,
1696 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1697 template <NodeType PvNode>
1698 Depth extension(const Position& pos, Move m, bool captureOrPromotion,
1699 bool moveIsCheck, bool mateThreat, bool* dangerous) {
1701 assert(m != MOVE_NONE);
1703 Depth result = DEPTH_ZERO;
1704 *dangerous = moveIsCheck | mateThreat;
1708 if (moveIsCheck && pos.see_sign(m) >= 0)
1709 result += CheckExtension[PvNode];
1712 result += MateThreatExtension[PvNode];
1715 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1717 Color c = pos.side_to_move();
1718 if (relative_rank(c, move_to(m)) == RANK_7)
1720 result += PawnPushTo7thExtension[PvNode];
1723 if (pos.pawn_is_passed(c, move_to(m)))
1725 result += PassedPawnExtension[PvNode];
1730 if ( captureOrPromotion
1731 && pos.type_of_piece_on(move_to(m)) != PAWN
1732 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1733 - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1734 && !move_is_promotion(m)
1737 result += PawnEndgameExtension[PvNode];
1741 return Min(result, ONE_PLY);
1745 // connected_threat() tests whether it is safe to forward prune a move or if
1746 // is somehow connected to the threat move returned by null search.
1748 bool connected_threat(const Position& pos, Move m, Move threat) {
1750 assert(move_is_ok(m));
1751 assert(threat && move_is_ok(threat));
1752 assert(!pos.move_is_check(m));
1753 assert(!pos.move_is_capture_or_promotion(m));
1754 assert(!pos.move_is_passed_pawn_push(m));
1756 Square mfrom, mto, tfrom, tto;
1758 mfrom = move_from(m);
1760 tfrom = move_from(threat);
1761 tto = move_to(threat);
1763 // Case 1: Don't prune moves which move the threatened piece
1767 // Case 2: If the threatened piece has value less than or equal to the
1768 // value of the threatening piece, don't prune moves which defend it.
1769 if ( pos.move_is_capture(threat)
1770 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1771 || pos.type_of_piece_on(tfrom) == KING)
1772 && pos.move_attacks_square(m, tto))
1775 // Case 3: If the moving piece in the threatened move is a slider, don't
1776 // prune safe moves which block its ray.
1777 if ( piece_is_slider(pos.piece_on(tfrom))
1778 && bit_is_set(squares_between(tfrom, tto), mto)
1779 && pos.see_sign(m) >= 0)
1786 // ok_to_use_TT() returns true if a transposition table score
1787 // can be used at a given point in search.
1789 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1791 Value v = value_from_tt(tte->value(), ply);
1793 return ( tte->depth() >= depth
1794 || v >= Max(VALUE_MATE_IN_PLY_MAX, beta)
1795 || v < Min(VALUE_MATED_IN_PLY_MAX, beta))
1797 && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1798 || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1802 // refine_eval() returns the transposition table score if
1803 // possible otherwise falls back on static position evaluation.
1805 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1809 Value v = value_from_tt(tte->value(), ply);
1811 if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1812 || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1819 // update_history() registers a good move that produced a beta-cutoff
1820 // in history and marks as failures all the other moves of that ply.
1822 void update_history(const Position& pos, Move move, Depth depth,
1823 Move movesSearched[], int moveCount) {
1825 Value bonus = Value(int(depth) * int(depth));
1827 H.update(pos.piece_on(move_from(move)), move_to(move), bonus);
1829 for (int i = 0; i < moveCount - 1; i++)
1831 m = movesSearched[i];
1835 H.update(pos.piece_on(move_from(m)), move_to(m), -bonus);
1840 // update_gains() updates the gains table of a non-capture move given
1841 // the static position evaluation before and after the move.
1843 void update_gains(const Position& pos, Move m, Value before, Value after) {
1846 && before != VALUE_NONE
1847 && after != VALUE_NONE
1848 && pos.captured_piece_type() == PIECE_TYPE_NONE
1849 && !move_is_special(m))
1850 H.update_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
1854 // current_search_time() returns the number of milliseconds which have passed
1855 // since the beginning of the current search.
1857 int current_search_time() {
1859 return get_system_time() - SearchStartTime;
1863 // value_to_uci() converts a value to a string suitable for use with the UCI
1864 // protocol specifications:
1866 // cp <x> The score from the engine's point of view in centipawns.
1867 // mate <y> Mate in y moves, not plies. If the engine is getting mated
1868 // use negative values for y.
1870 std::string value_to_uci(Value v) {
1872 std::stringstream s;
1874 if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
1875 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to centipawns
1877 s << "mate " << (v > 0 ? VALUE_MATE - v + 1 : -VALUE_MATE - v) / 2;
1883 // speed_to_uci() returns a string with time stats of current search suitable
1884 // to be sent to UCI gui.
1886 std::string speed_to_uci(int64_t nodes) {
1888 std::stringstream s;
1889 int t = current_search_time();
1891 s << " nodes " << nodes
1892 << " nps " << (t > 0 ? int(nodes * 1000 / t) : 0)
1899 // poll() performs two different functions: It polls for user input, and it
1900 // looks at the time consumed so far and decides if it's time to abort the
1903 void poll(const Position& pos) {
1905 static int lastInfoTime;
1906 int t = current_search_time();
1909 if (input_available())
1911 // We are line oriented, don't read single chars
1912 std::string command;
1914 if (!std::getline(std::cin, command) || command == "quit")
1916 // Quit the program as soon as possible
1918 QuitRequest = StopRequest = true;
1921 else if (command == "stop")
1923 // Stop calculating as soon as possible, but still send the "bestmove"
1924 // and possibly the "ponder" token when finishing the search.
1928 else if (command == "ponderhit")
1930 // The opponent has played the expected move. GUI sends "ponderhit" if
1931 // we were told to ponder on the same move the opponent has played. We
1932 // should continue searching but switching from pondering to normal search.
1935 if (StopOnPonderhit)
1940 // Print search information
1944 else if (lastInfoTime > t)
1945 // HACK: Must be a new search where we searched less than
1946 // NodesBetweenPolls nodes during the first second of search.
1949 else if (t - lastInfoTime >= 1000)
1956 if (dbg_show_hit_rate)
1957 dbg_print_hit_rate();
1959 // Send info on searched nodes as soon as we return to root
1960 SendSearchedNodes = true;
1963 // Should we stop the search?
1967 bool stillAtFirstMove = FirstRootMove
1968 && !AspirationFailLow
1969 && t > TimeMgr.available_time();
1971 bool noMoreTime = t > TimeMgr.maximum_time()
1972 || stillAtFirstMove;
1974 if ( (UseTimeManagement && noMoreTime)
1975 || (ExactMaxTime && t >= ExactMaxTime)
1976 || (MaxNodes && pos.nodes_searched() >= MaxNodes)) // FIXME
1981 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
1982 // while the program is pondering. The point is to work around a wrinkle in
1983 // the UCI protocol: When pondering, the engine is not allowed to give a
1984 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
1985 // We simply wait here until one of these commands is sent, and return,
1986 // after which the bestmove and pondermove will be printed.
1988 void wait_for_stop_or_ponderhit() {
1990 std::string command;
1992 // Wait for a command from stdin
1993 while ( std::getline(std::cin, command)
1994 && command != "ponderhit" && command != "stop" && command != "quit") {};
1996 if (command != "ponderhit" && command != "stop")
1997 QuitRequest = true; // Must be "quit" or getline() returned false
2001 // init_thread() is the function which is called when a new thread is
2002 // launched. It simply calls the idle_loop() function with the supplied
2003 // threadID. There are two versions of this function; one for POSIX
2004 // threads and one for Windows threads.
2006 #if !defined(_MSC_VER)
2008 void* init_thread(void* threadID) {
2010 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2016 DWORD WINAPI init_thread(LPVOID threadID) {
2018 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2025 /// The ThreadsManager class
2028 // read_uci_options() updates number of active threads and other internal
2029 // parameters according to the UCI options values. It is called before
2030 // to start a new search.
2032 void ThreadsManager::read_uci_options() {
2034 maxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value<int>();
2035 minimumSplitDepth = Options["Minimum Split Depth"].value<int>() * ONE_PLY;
2036 useSleepingThreads = Options["Use Sleeping Threads"].value<bool>();
2037 activeThreads = Options["Threads"].value<int>();
2041 // idle_loop() is where the threads are parked when they have no work to do.
2042 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2043 // object for which the current thread is the master.
2045 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2047 assert(threadID >= 0 && threadID < MAX_THREADS);
2050 bool allFinished = false;
2054 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2055 // master should exit as last one.
2056 if (allThreadsShouldExit)
2059 threads[threadID].state = THREAD_TERMINATED;
2063 // If we are not thinking, wait for a condition to be signaled
2064 // instead of wasting CPU time polling for work.
2065 while ( threadID >= activeThreads || threads[threadID].state == THREAD_INITIALIZING
2066 || (useSleepingThreads && threads[threadID].state == THREAD_AVAILABLE))
2068 assert(!sp || useSleepingThreads);
2069 assert(threadID != 0 || useSleepingThreads);
2071 if (threads[threadID].state == THREAD_INITIALIZING)
2072 threads[threadID].state = THREAD_AVAILABLE;
2074 // Grab the lock to avoid races with wake_sleeping_thread()
2075 lock_grab(&sleepLock[threadID]);
2077 // If we are master and all slaves have finished do not go to sleep
2078 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2079 allFinished = (i == activeThreads);
2081 if (allFinished || allThreadsShouldExit)
2083 lock_release(&sleepLock[threadID]);
2087 // Do sleep here after retesting sleep conditions
2088 if (threadID >= activeThreads || threads[threadID].state == THREAD_AVAILABLE)
2089 cond_wait(&sleepCond[threadID], &sleepLock[threadID]);
2091 lock_release(&sleepLock[threadID]);
2094 // If this thread has been assigned work, launch a search
2095 if (threads[threadID].state == THREAD_WORKISWAITING)
2097 assert(!allThreadsShouldExit);
2099 threads[threadID].state = THREAD_SEARCHING;
2101 // Copy SplitPoint position and search stack and call search()
2102 // with SplitPoint template parameter set to true.
2103 SearchStack ss[PLY_MAX_PLUS_2];
2104 SplitPoint* tsp = threads[threadID].splitPoint;
2105 Position pos(*tsp->pos, threadID);
2107 memcpy(ss, tsp->ss - 1, 4 * sizeof(SearchStack));
2111 search<PV, true, false>(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2113 search<NonPV, true, false>(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2115 assert(threads[threadID].state == THREAD_SEARCHING);
2117 threads[threadID].state = THREAD_AVAILABLE;
2119 // Wake up master thread so to allow it to return from the idle loop in
2120 // case we are the last slave of the split point.
2121 if (useSleepingThreads && threadID != tsp->master && threads[tsp->master].state == THREAD_AVAILABLE)
2122 wake_sleeping_thread(tsp->master);
2125 // If this thread is the master of a split point and all slaves have
2126 // finished their work at this split point, return from the idle loop.
2127 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2128 allFinished = (i == activeThreads);
2132 // Because sp->slaves[] is reset under lock protection,
2133 // be sure sp->lock has been released before to return.
2134 lock_grab(&(sp->lock));
2135 lock_release(&(sp->lock));
2137 // In helpful master concept a master can help only a sub-tree, and
2138 // because here is all finished is not possible master is booked.
2139 assert(threads[threadID].state == THREAD_AVAILABLE);
2141 threads[threadID].state = THREAD_SEARCHING;
2148 // init_threads() is called during startup. It launches all helper threads,
2149 // and initializes the split point stack and the global locks and condition
2152 void ThreadsManager::init_threads() {
2154 int i, arg[MAX_THREADS];
2157 // Initialize global locks
2160 for (i = 0; i < MAX_THREADS; i++)
2162 lock_init(&sleepLock[i]);
2163 cond_init(&sleepCond[i]);
2166 // Initialize splitPoints[] locks
2167 for (i = 0; i < MAX_THREADS; i++)
2168 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2169 lock_init(&(threads[i].splitPoints[j].lock));
2171 // Will be set just before program exits to properly end the threads
2172 allThreadsShouldExit = false;
2174 // Threads will be put all threads to sleep as soon as created
2177 // All threads except the main thread should be initialized to THREAD_INITIALIZING
2178 threads[0].state = THREAD_SEARCHING;
2179 for (i = 1; i < MAX_THREADS; i++)
2180 threads[i].state = THREAD_INITIALIZING;
2182 // Launch the helper threads
2183 for (i = 1; i < MAX_THREADS; i++)
2187 #if !defined(_MSC_VER)
2188 pthread_t pthread[1];
2189 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
2190 pthread_detach(pthread[0]);
2192 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
2196 cout << "Failed to create thread number " << i << endl;
2200 // Wait until the thread has finished launching and is gone to sleep
2201 while (threads[i].state == THREAD_INITIALIZING) {}
2206 // exit_threads() is called when the program exits. It makes all the
2207 // helper threads exit cleanly.
2209 void ThreadsManager::exit_threads() {
2211 allThreadsShouldExit = true; // Let the woken up threads to exit idle_loop()
2213 // Wake up all the threads and waits for termination
2214 for (int i = 1; i < MAX_THREADS; i++)
2216 wake_sleeping_thread(i);
2217 while (threads[i].state != THREAD_TERMINATED) {}
2220 // Now we can safely destroy the locks
2221 for (int i = 0; i < MAX_THREADS; i++)
2222 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2223 lock_destroy(&(threads[i].splitPoints[j].lock));
2225 lock_destroy(&mpLock);
2227 // Now we can safely destroy the wait conditions
2228 for (int i = 0; i < MAX_THREADS; i++)
2230 lock_destroy(&sleepLock[i]);
2231 cond_destroy(&sleepCond[i]);
2236 // cutoff_at_splitpoint() checks whether a beta cutoff has occurred in
2237 // the thread's currently active split point, or in some ancestor of
2238 // the current split point.
2240 bool ThreadsManager::cutoff_at_splitpoint(int threadID) const {
2242 assert(threadID >= 0 && threadID < activeThreads);
2244 SplitPoint* sp = threads[threadID].splitPoint;
2246 for ( ; sp && !sp->betaCutoff; sp = sp->parent) {}
2251 // thread_is_available() checks whether the thread with threadID "slave" is
2252 // available to help the thread with threadID "master" at a split point. An
2253 // obvious requirement is that "slave" must be idle. With more than two
2254 // threads, this is not by itself sufficient: If "slave" is the master of
2255 // some active split point, it is only available as a slave to the other
2256 // threads which are busy searching the split point at the top of "slave"'s
2257 // split point stack (the "helpful master concept" in YBWC terminology).
2259 bool ThreadsManager::thread_is_available(int slave, int master) const {
2261 assert(slave >= 0 && slave < activeThreads);
2262 assert(master >= 0 && master < activeThreads);
2263 assert(activeThreads > 1);
2265 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2268 // Make a local copy to be sure doesn't change under our feet
2269 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2271 // No active split points means that the thread is available as
2272 // a slave for any other thread.
2273 if (localActiveSplitPoints == 0 || activeThreads == 2)
2276 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2277 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2278 // could have been set to 0 by another thread leading to an out of bound access.
2279 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2286 // available_thread_exists() tries to find an idle thread which is available as
2287 // a slave for the thread with threadID "master".
2289 bool ThreadsManager::available_thread_exists(int master) const {
2291 assert(master >= 0 && master < activeThreads);
2292 assert(activeThreads > 1);
2294 for (int i = 0; i < activeThreads; i++)
2295 if (thread_is_available(i, master))
2302 // split() does the actual work of distributing the work at a node between
2303 // several available threads. If it does not succeed in splitting the
2304 // node (because no idle threads are available, or because we have no unused
2305 // split point objects), the function immediately returns. If splitting is
2306 // possible, a SplitPoint object is initialized with all the data that must be
2307 // copied to the helper threads and we tell our helper threads that they have
2308 // been assigned work. This will cause them to instantly leave their idle loops and
2309 // call search().When all threads have returned from search() then split() returns.
2311 template <bool Fake>
2312 void ThreadsManager::split(Position& pos, SearchStack* ss, int ply, Value* alpha,
2313 const Value beta, Value* bestValue, Depth depth, Move threatMove,
2314 bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) {
2315 assert(pos.is_ok());
2316 assert(ply > 0 && ply < PLY_MAX);
2317 assert(*bestValue >= -VALUE_INFINITE);
2318 assert(*bestValue <= *alpha);
2319 assert(*alpha < beta);
2320 assert(beta <= VALUE_INFINITE);
2321 assert(depth > DEPTH_ZERO);
2322 assert(pos.thread() >= 0 && pos.thread() < activeThreads);
2323 assert(activeThreads > 1);
2325 int i, master = pos.thread();
2326 Thread& masterThread = threads[master];
2330 // If no other thread is available to help us, or if we have too many
2331 // active split points, don't split.
2332 if ( !available_thread_exists(master)
2333 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2335 lock_release(&mpLock);
2339 // Pick the next available split point object from the split point stack
2340 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2342 // Initialize the split point object
2343 splitPoint.parent = masterThread.splitPoint;
2344 splitPoint.master = master;
2345 splitPoint.betaCutoff = false;
2346 splitPoint.ply = ply;
2347 splitPoint.depth = depth;
2348 splitPoint.threatMove = threatMove;
2349 splitPoint.mateThreat = mateThreat;
2350 splitPoint.alpha = *alpha;
2351 splitPoint.beta = beta;
2352 splitPoint.pvNode = pvNode;
2353 splitPoint.bestValue = *bestValue;
2355 splitPoint.moveCount = moveCount;
2356 splitPoint.pos = &pos;
2357 splitPoint.nodes = 0;
2359 for (i = 0; i < activeThreads; i++)
2360 splitPoint.slaves[i] = 0;
2362 masterThread.splitPoint = &splitPoint;
2364 // If we are here it means we are not available
2365 assert(masterThread.state != THREAD_AVAILABLE);
2367 int workersCnt = 1; // At least the master is included
2369 // Allocate available threads setting state to THREAD_BOOKED
2370 for (i = 0; !Fake && i < activeThreads && workersCnt < maxThreadsPerSplitPoint; i++)
2371 if (thread_is_available(i, master))
2373 threads[i].state = THREAD_BOOKED;
2374 threads[i].splitPoint = &splitPoint;
2375 splitPoint.slaves[i] = 1;
2379 assert(Fake || workersCnt > 1);
2381 // We can release the lock because slave threads are already booked and master is not available
2382 lock_release(&mpLock);
2384 // Tell the threads that they have work to do. This will make them leave
2386 for (i = 0; i < activeThreads; i++)
2387 if (i == master || splitPoint.slaves[i])
2389 assert(i == master || threads[i].state == THREAD_BOOKED);
2391 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2393 if (useSleepingThreads && i != master)
2394 wake_sleeping_thread(i);
2397 // Everything is set up. The master thread enters the idle loop, from
2398 // which it will instantly launch a search, because its state is
2399 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2400 // idle loop, which means that the main thread will return from the idle
2401 // loop when all threads have finished their work at this split point.
2402 idle_loop(master, &splitPoint);
2404 // We have returned from the idle loop, which means that all threads are
2405 // finished. Update alpha and bestValue, and return.
2408 *alpha = splitPoint.alpha;
2409 *bestValue = splitPoint.bestValue;
2410 masterThread.activeSplitPoints--;
2411 masterThread.splitPoint = splitPoint.parent;
2412 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
2414 lock_release(&mpLock);
2418 // wake_sleeping_thread() wakes up the thread with the given threadID
2419 // when it is time to start a new search.
2421 void ThreadsManager::wake_sleeping_thread(int threadID) {
2423 lock_grab(&sleepLock[threadID]);
2424 cond_signal(&sleepCond[threadID]);
2425 lock_release(&sleepLock[threadID]);
2429 /// RootMove and RootMoveList method's definitions
2431 RootMove::RootMove() {
2434 pv_score = non_pv_score = -VALUE_INFINITE;
2438 RootMove& RootMove::operator=(const RootMove& rm) {
2440 const Move* src = rm.pv;
2443 // Avoid a costly full rm.pv[] copy
2444 do *dst++ = *src; while (*src++ != MOVE_NONE);
2447 pv_score = rm.pv_score;
2448 non_pv_score = rm.non_pv_score;
2452 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2453 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2454 // allow to always have a ponder move even when we fail high at root and also a
2455 // long PV to print that is important for position analysis.
2457 void RootMove::extract_pv_from_tt(Position& pos) {
2459 StateInfo state[PLY_MAX_PLUS_2], *st = state;
2463 assert(pv[0] != MOVE_NONE && move_is_legal(pos, pv[0]));
2465 pos.do_move(pv[0], *st++);
2467 while ( (tte = TT.retrieve(pos.get_key())) != NULL
2468 && tte->move() != MOVE_NONE
2469 && move_is_legal(pos, tte->move())
2471 && (!pos.is_draw() || ply < 2))
2473 pv[ply] = tte->move();
2474 pos.do_move(pv[ply++], *st++);
2476 pv[ply] = MOVE_NONE;
2478 do pos.undo_move(pv[--ply]); while (ply);
2481 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2482 // the PV back into the TT. This makes sure the old PV moves are searched
2483 // first, even if the old TT entries have been overwritten.
2485 void RootMove::insert_pv_in_tt(Position& pos) {
2487 StateInfo state[PLY_MAX_PLUS_2], *st = state;
2490 Value v, m = VALUE_NONE;
2493 assert(pv[0] != MOVE_NONE && move_is_legal(pos, pv[0]));
2497 tte = TT.retrieve(k);
2499 // Don't overwrite existing correct entries
2500 if (!tte || tte->move() != pv[ply])
2502 v = (pos.is_check() ? VALUE_NONE : evaluate(pos, m));
2503 TT.store(k, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[ply], v, m);
2505 pos.do_move(pv[ply], *st++);
2507 } while (pv[++ply] != MOVE_NONE);
2509 do pos.undo_move(pv[--ply]); while (ply);
2512 // pv_info_to_uci() returns a string with information on the current PV line
2513 // formatted according to UCI specification.
2515 std::string RootMove::pv_info_to_uci(Position& pos, int depth, Value alpha,
2516 Value beta, int pvIdx) {
2517 std::stringstream s, l;
2520 while (*m != MOVE_NONE)
2523 s << "info depth " << depth
2524 << " seldepth " << int(m - pv)
2525 << " multipv " << pvIdx + 1
2526 << " score " << value_to_uci(pv_score)
2527 << (pv_score >= beta ? " lowerbound" : pv_score <= alpha ? " upperbound" : "")
2528 << speed_to_uci(pos.nodes_searched())
2529 << " pv " << l.str();
2535 void RootMoveList::init(Position& pos, Move searchMoves[]) {
2537 MoveStack mlist[MOVES_MAX];
2541 bestMoveChanges = 0;
2543 // Generate all legal moves and add them to RootMoveList
2544 MoveStack* last = generate<MV_LEGAL>(pos, mlist);
2545 for (MoveStack* cur = mlist; cur != last; cur++)
2547 // If we have a searchMoves[] list then verify cur->move
2548 // is in the list before to add it.
2549 for (sm = searchMoves; *sm && *sm != cur->move; sm++) {}
2551 if (searchMoves[0] && *sm != cur->move)
2555 rm.pv[0] = cur->move;
2556 rm.pv[1] = MOVE_NONE;
2557 rm.pv_score = -VALUE_INFINITE;
2563 // When playing with strength handicap choose best move among the MultiPV set
2564 // using a statistical rule dependent on SkillLevel. Idea by Heinz van Saanen.
2565 void do_skill_level(Move* best, Move* ponder) {
2567 assert(MultiPV > 1);
2569 // Rml list is already sorted by pv_score in descending order
2571 int max_s = -VALUE_INFINITE;
2572 int size = Min(MultiPV, (int)Rml.size());
2573 int max = Rml[0].pv_score;
2574 int var = Min(max - Rml[size - 1].pv_score, PawnValueMidgame);
2575 int wk = 120 - 2 * SkillLevel;
2577 // PRNG sequence should be non deterministic
2578 for (int i = abs(get_system_time() % 50); i > 0; i--)
2579 RK.rand<unsigned>();
2581 // Choose best move. For each move's score we add two terms both dependent
2582 // on wk, one deterministic and bigger for weaker moves, and one random,
2583 // then we choose the move with the resulting highest score.
2584 for (int i = 0; i < size; i++)
2586 s = Rml[i].pv_score;
2588 // Don't allow crazy blunders even at very low skills
2589 if (i > 0 && Rml[i-1].pv_score > s + EasyMoveMargin)
2592 // This is our magical formula
2593 s += ((max - s) * wk + var * (RK.rand<unsigned>() % wk)) / 128;
2598 *best = Rml[i].pv[0];
2599 *ponder = Rml[i].pv[1];