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, Value* alpha, const Value beta, Value* bestValue,
83 Depth depth, Move threatMove, 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];
196 Depth PassedPawnExtension[2], PawnEndgameExtension[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 / ONE_PLY, 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);
272 template <NodeType PvNode>
273 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth);
275 template <NodeType PvNode>
276 inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) {
278 return depth < ONE_PLY ? qsearch<PvNode>(pos, ss, alpha, beta, DEPTH_ZERO)
279 : search<PvNode, false, false>(pos, ss, alpha, beta, depth);
282 template <NodeType PvNode>
283 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, 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 UCIMultiPV = Options["MultiPV"].value<int>();
488 SkillLevel = Options["Skill level"].value<int>();
489 UseLogFile = Options["Use Search Log"].value<bool>();
491 read_evaluation_uci_options(pos.side_to_move());
493 if (Options["Clear Hash"].value<bool>())
495 Options["Clear Hash"].set_value("false");
498 TT.set_size(Options["Hash"].value<int>());
500 // Do we have to play with skill handicap? In this case enable MultiPV that
501 // we will use behind the scenes to retrieve a set of possible moves.
502 SkillLevelEnabled = (SkillLevel < 20);
503 MultiPV = (SkillLevelEnabled ? Max(UCIMultiPV, 4) : UCIMultiPV);
505 // Set the number of active threads
506 ThreadsMgr.read_uci_options();
507 init_eval(ThreadsMgr.active_threads());
509 // Wake up needed threads. Main thread, with threadID == 0, is always active
510 for (int i = 1; i < ThreadsMgr.active_threads(); i++)
511 ThreadsMgr.wake_sleeping_thread(i);
514 int myTime = time[pos.side_to_move()];
515 int myIncrement = increment[pos.side_to_move()];
516 if (UseTimeManagement)
517 TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter());
519 // Set best NodesBetweenPolls interval to avoid lagging under time pressure
521 NodesBetweenPolls = Min(MaxNodes, 30000);
522 else if (myTime && myTime < 1000)
523 NodesBetweenPolls = 1000;
524 else if (myTime && myTime < 5000)
525 NodesBetweenPolls = 5000;
527 NodesBetweenPolls = 30000;
529 // Write search information to log file
532 std::string name = Options["Search Log Filename"].value<std::string>();
533 LogFile.open(name.c_str(), std::ios::out | std::ios::app);
535 LogFile << "\nSearching: " << pos.to_fen()
536 << "\ninfinite: " << infinite
537 << " ponder: " << ponder
538 << " time: " << myTime
539 << " increment: " << myIncrement
540 << " moves to go: " << movesToGo
544 // We're ready to start thinking. Call the iterative deepening loop function
545 Move ponderMove = MOVE_NONE;
546 Move bestMove = id_loop(pos, searchMoves, &ponderMove);
548 // Print final search statistics
549 cout << "info" << speed_to_uci(pos.nodes_searched()) << endl;
553 int t = current_search_time();
555 LogFile << "Nodes: " << pos.nodes_searched()
556 << "\nNodes/second: " << (t > 0 ? int(pos.nodes_searched() * 1000 / t) : 0)
557 << "\nBest move: " << move_to_san(pos, bestMove);
560 pos.do_move(bestMove, st);
561 LogFile << "\nPonder move: " << move_to_san(pos, ponderMove) << endl;
562 pos.undo_move(bestMove); // Return from think() with unchanged position
566 // This makes all the threads to go to sleep
567 ThreadsMgr.set_active_threads(1);
569 // If we are pondering or in infinite search, we shouldn't print the
570 // best move before we are told to do so.
571 if (!StopRequest && (Pondering || InfiniteSearch))
572 wait_for_stop_or_ponderhit();
574 // Could be MOVE_NONE when searching on a stalemate position
575 cout << "bestmove " << bestMove;
577 // UCI protol is not clear on allowing sending an empty ponder move, instead
578 // it is clear that ponder move is optional. So skip it if empty.
579 if (ponderMove != MOVE_NONE)
580 cout << " ponder " << ponderMove;
590 // id_loop() is the main iterative deepening loop. It calls search() repeatedly
591 // with increasing depth until the allocated thinking time has been consumed,
592 // user stops the search, or the maximum search depth is reached.
594 Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove) {
596 SearchStack ss[PLY_MAX_PLUS_2];
597 Value bestValues[PLY_MAX_PLUS_2];
598 int bestMoveChanges[PLY_MAX_PLUS_2];
599 int depth, aspirationDelta;
600 Value value, alpha, beta;
601 Move bestMove, easyMove, skillBest, skillPonder;
603 // Initialize stuff before a new search
604 memset(ss, 0, 4 * sizeof(SearchStack));
607 *ponderMove = bestMove = easyMove = skillBest = skillPonder = MOVE_NONE;
608 depth = aspirationDelta = 0;
609 alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
610 ss->currentMove = MOVE_NULL; // Hack to skip update_gains()
612 // Moves to search are verified and copied
613 Rml.init(pos, searchMoves);
615 // Handle special case of searching on a mate/stalemate position
618 cout << "info depth 0 score "
619 << value_to_uci(pos.is_check() ? -VALUE_MATE : VALUE_DRAW)
625 // Iterative deepening loop
626 while (++depth <= PLY_MAX && (!MaxDepth || depth <= MaxDepth) && !StopRequest)
628 Rml.bestMoveChanges = 0;
629 cout << set960(pos.is_chess960()) << "info depth " << depth << endl;
631 // Calculate dynamic aspiration window based on previous iterations
632 if (MultiPV == 1 && depth >= 5 && abs(bestValues[depth - 1]) < VALUE_KNOWN_WIN)
634 int prevDelta1 = bestValues[depth - 1] - bestValues[depth - 2];
635 int prevDelta2 = bestValues[depth - 2] - bestValues[depth - 3];
637 aspirationDelta = Min(Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16), 24);
638 aspirationDelta = (aspirationDelta + 7) / 8 * 8; // Round to match grainSize
640 alpha = Max(bestValues[depth - 1] - aspirationDelta, -VALUE_INFINITE);
641 beta = Min(bestValues[depth - 1] + aspirationDelta, VALUE_INFINITE);
644 // Start with a small aspiration window and, in case of fail high/low,
645 // research with bigger window until not failing high/low anymore.
647 // Search starting from ss+1 to allow calling update_gains()
648 value = search<PV, false, true>(pos, ss+1, alpha, beta, depth * ONE_PLY);
650 // Write PV back to transposition table in case the relevant entries
651 // have been overwritten during the search.
652 for (int i = 0; i < Min(MultiPV, (int)Rml.size()); i++)
653 Rml[i].insert_pv_in_tt(pos);
655 // Value cannot be trusted. Break out immediately!
659 assert(value >= alpha);
661 // In case of failing high/low increase aspiration window and research,
662 // otherwise exit the fail high/low loop.
665 beta = Min(beta + aspirationDelta, VALUE_INFINITE);
666 aspirationDelta += aspirationDelta / 2;
668 else if (value <= alpha)
670 AspirationFailLow = true;
671 StopOnPonderhit = false;
673 alpha = Max(alpha - aspirationDelta, -VALUE_INFINITE);
674 aspirationDelta += aspirationDelta / 2;
679 } while (abs(value) < VALUE_KNOWN_WIN);
681 // Collect info about search result
682 bestMove = Rml[0].pv[0];
683 *ponderMove = Rml[0].pv[1];
684 bestValues[depth] = value;
685 bestMoveChanges[depth] = Rml.bestMoveChanges;
687 // Do we need to pick now the best and the ponder moves ?
688 if (SkillLevelEnabled && depth == 1 + SkillLevel)
689 do_skill_level(&skillBest, &skillPonder);
691 // Send PV line to GUI and to log file
692 for (int i = 0; i < Min(UCIMultiPV, (int)Rml.size()); i++)
693 cout << Rml[i].pv_info_to_uci(pos, depth, alpha, beta, i) << endl;
696 LogFile << pretty_pv(pos, depth, value, current_search_time(), Rml[0].pv) << endl;
698 // Init easyMove after first iteration or drop if differs from the best move
699 if (depth == 1 && (Rml.size() == 1 || Rml[0].pv_score > Rml[1].pv_score + EasyMoveMargin))
701 else if (bestMove != easyMove)
702 easyMove = MOVE_NONE;
704 if (UseTimeManagement && !StopRequest)
707 bool noMoreTime = false;
709 // Stop search early when the last two iterations returned a mate score
711 && abs(bestValues[depth]) >= abs(VALUE_MATE) - 100
712 && abs(bestValues[depth - 1]) >= abs(VALUE_MATE) - 100)
715 // Stop search early if one move seems to be much better than the
716 // others or if there is only a single legal move. In this latter
717 // case we search up to Iteration 8 anyway to get a proper score.
719 && easyMove == bestMove
721 ||( Rml[0].nodes > (pos.nodes_searched() * 85) / 100
722 && current_search_time() > TimeMgr.available_time() / 16)
723 ||( Rml[0].nodes > (pos.nodes_searched() * 98) / 100
724 && current_search_time() > TimeMgr.available_time() / 32)))
727 // Add some extra time if the best move has changed during the last two iterations
728 if (depth > 4 && depth < 50)
729 TimeMgr.pv_instability(bestMoveChanges[depth], bestMoveChanges[depth-1]);
731 // Stop search if most of MaxSearchTime is consumed at the end of the
732 // iteration. We probably don't have enough time to search the first
733 // move at the next iteration anyway.
734 if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
740 StopOnPonderhit = true;
747 // When using skills fake best and ponder moves with the sub-optimal ones
748 if (SkillLevelEnabled)
750 if (skillBest == MOVE_NONE) // Still unassigned ?
751 do_skill_level(&skillBest, &skillPonder);
753 bestMove = skillBest;
754 *ponderMove = skillPonder;
761 // search<>() is the main search function for both PV and non-PV nodes and for
762 // normal and SplitPoint nodes. When called just after a split point the search
763 // is simpler because we have already probed the hash table, done a null move
764 // search, and searched the first move before splitting, we don't have to repeat
765 // all this work again. We also don't need to store anything to the hash table
766 // here: This is taken care of after we return from the split point.
768 template <NodeType PvNode, bool SpNode, bool Root>
769 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) {
771 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
772 assert(beta > alpha && beta <= VALUE_INFINITE);
773 assert(PvNode || alpha == beta - 1);
774 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
776 Move movesSearched[MOVES_MAX];
781 Move ttMove, move, excludedMove, threatMove;
784 Value bestValue, value, oldAlpha;
785 Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
786 bool isPvMove, isCheck, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous, isBadCap;
787 int moveCount = 0, playedMoveCount = 0;
788 int threadID = pos.thread();
789 SplitPoint* sp = NULL;
791 refinedValue = bestValue = value = -VALUE_INFINITE;
793 isCheck = pos.is_check();
794 ss->ply = (ss-1)->ply + 1;
800 ttMove = excludedMove = MOVE_NONE;
801 threatMove = sp->threatMove;
802 goto split_point_start;
807 // Step 1. Initialize node and poll. Polling can abort search
808 ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE;
809 (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO;
810 (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
812 if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
818 // Step 2. Check for aborted search and immediate draw
820 || ThreadsMgr.cutoff_at_splitpoint(threadID)
822 || ss->ply > PLY_MAX) && !Root)
825 // Step 3. Mate distance pruning
826 alpha = Max(value_mated_in(ss->ply), alpha);
827 beta = Min(value_mate_in(ss->ply+1), beta);
831 // Step 4. Transposition table lookup
832 // We don't want the score of a partial search to overwrite a previous full search
833 // TT value, so we use a different position key in case of an excluded move.
834 excludedMove = ss->excludedMove;
835 posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
837 tte = TT.retrieve(posKey);
838 ttMove = tte ? tte->move() : MOVE_NONE;
840 // At PV nodes we check for exact scores, while at non-PV nodes we check for
841 // a fail high/low. Biggest advantage at probing at PV nodes is to have a
842 // smooth experience in analysis mode.
845 && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT
846 : ok_to_use_TT(tte, depth, beta, ss->ply)))
849 ss->bestMove = ttMove; // Can be MOVE_NONE
850 return value_from_tt(tte->value(), ss->ply);
853 // Step 5. Evaluate the position statically and update parent's gain statistics
855 ss->eval = ss->evalMargin = VALUE_NONE;
858 assert(tte->static_value() != VALUE_NONE);
860 ss->eval = tte->static_value();
861 ss->evalMargin = tte->static_value_margin();
862 refinedValue = refine_eval(tte, ss->eval, ss->ply);
866 refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
867 TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
870 // Save gain for the parent non-capture move
871 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
873 // Step 6. Razoring (is omitted in PV nodes)
875 && depth < RazorDepth
877 && refinedValue + razor_margin(depth) < beta
878 && ttMove == MOVE_NONE
879 && abs(beta) < VALUE_MATE_IN_PLY_MAX
880 && !pos.has_pawn_on_7th(pos.side_to_move()))
882 Value rbeta = beta - razor_margin(depth);
883 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO);
885 // Logically we should return (v + razor_margin(depth)), but
886 // surprisingly this did slightly weaker in tests.
890 // Step 7. Static null move pruning (is omitted in PV nodes)
891 // We're betting that the opponent doesn't have a move that will reduce
892 // the score by more than futility_margin(depth) if we do a null move.
895 && depth < RazorDepth
897 && refinedValue - futility_margin(depth, 0) >= beta
898 && abs(beta) < VALUE_MATE_IN_PLY_MAX
899 && pos.non_pawn_material(pos.side_to_move()))
900 return refinedValue - futility_margin(depth, 0);
902 // Step 8. Null move search with verification search (is omitted in PV nodes)
907 && refinedValue >= beta
908 && abs(beta) < VALUE_MATE_IN_PLY_MAX
909 && pos.non_pawn_material(pos.side_to_move()))
911 ss->currentMove = MOVE_NULL;
913 // Null move dynamic reduction based on depth
914 int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
916 // Null move dynamic reduction based on value
917 if (refinedValue - PawnValueMidgame > beta)
920 pos.do_null_move(st);
921 (ss+1)->skipNullMove = true;
922 nullValue = -search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY);
923 (ss+1)->skipNullMove = false;
924 pos.undo_null_move();
926 if (nullValue >= beta)
928 // Do not return unproven mate scores
929 if (nullValue >= VALUE_MATE_IN_PLY_MAX)
932 if (depth < 6 * ONE_PLY)
935 // Do verification search at high depths
936 ss->skipNullMove = true;
937 Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY);
938 ss->skipNullMove = false;
945 // The null move failed low, which means that we may be faced with
946 // some kind of threat. If the previous move was reduced, check if
947 // the move that refuted the null move was somehow connected to the
948 // move which was reduced. If a connection is found, return a fail
949 // low score (which will cause the reduced move to fail high in the
950 // parent node, which will trigger a re-search with full depth).
951 threatMove = (ss+1)->bestMove;
953 if ( depth < ThreatDepth
955 && threatMove != MOVE_NONE
956 && connected_moves(pos, (ss-1)->currentMove, threatMove))
961 // Step 9. Internal iterative deepening
962 if ( depth >= IIDDepth[PvNode]
963 && ttMove == MOVE_NONE
964 && (PvNode || (!isCheck && ss->eval + IIDMargin >= beta)))
966 Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
968 ss->skipNullMove = true;
969 search<PvNode>(pos, ss, alpha, beta, d);
970 ss->skipNullMove = false;
972 ttMove = ss->bestMove;
973 tte = TT.retrieve(posKey);
976 split_point_start: // At split points actual search starts from here
978 // Initialize a MovePicker object for the current position
979 MovePickerExt<SpNode, Root> mp(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
981 ss->bestMove = MOVE_NONE;
982 futilityBase = ss->eval + ss->evalMargin;
983 singularExtensionNode = !Root
985 && depth >= SingularExtensionDepth[PvNode]
988 && !excludedMove // Do not allow recursive singular extension search
989 && (tte->type() & VALUE_TYPE_LOWER)
990 && tte->depth() >= depth - 3 * ONE_PLY;
993 lock_grab(&(sp->lock));
994 bestValue = sp->bestValue;
997 // Step 10. Loop through moves
998 // Loop through all legal moves until no moves remain or a beta cutoff occurs
999 while ( bestValue < beta
1000 && (move = mp.get_next_move()) != MOVE_NONE
1001 && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1003 assert(move_is_ok(move));
1007 moveCount = ++sp->moveCount;
1008 lock_release(&(sp->lock));
1010 else if (move == excludedMove)
1017 // This is used by time management
1018 FirstRootMove = (moveCount == 1);
1020 // Save the current node count before the move is searched
1021 nodes = pos.nodes_searched();
1023 // If it's time to send nodes info, do it here where we have the
1024 // correct accumulated node counts searched by each thread.
1025 if (SendSearchedNodes)
1027 SendSearchedNodes = false;
1028 cout << "info" << speed_to_uci(pos.nodes_searched()) << endl;
1031 if (current_search_time() > 2000)
1032 cout << "info currmove " << move
1033 << " currmovenumber " << moveCount << endl;
1036 // At Root and at first iteration do a PV search on all the moves to score root moves
1037 isPvMove = (PvNode && moveCount <= (Root ? depth <= ONE_PLY ? 1000 : MultiPV : 1));
1038 moveIsCheck = pos.move_is_check(move, ci);
1039 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1041 // Step 11. Decide the new search depth
1042 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, &dangerous);
1044 // Singular extension search. If all moves but one fail low on a search of
1045 // (alpha-s, beta-s), and just one fails high on (alpha, beta), then that move
1046 // is singular and should be extended. To verify this we do a reduced search
1047 // on all the other moves but the ttMove, if result is lower than ttValue minus
1048 // a margin then we extend ttMove.
1049 if ( singularExtensionNode
1050 && move == tte->move()
1053 Value ttValue = value_from_tt(tte->value(), ss->ply);
1055 if (abs(ttValue) < VALUE_KNOWN_WIN)
1057 Value rBeta = ttValue - int(depth);
1058 ss->excludedMove = move;
1059 ss->skipNullMove = true;
1060 Value v = search<NonPV>(pos, ss, rBeta - 1, rBeta, depth / 2);
1061 ss->skipNullMove = false;
1062 ss->excludedMove = MOVE_NONE;
1063 ss->bestMove = MOVE_NONE;
1069 // Update current move (this must be done after singular extension search)
1070 ss->currentMove = move;
1071 newDepth = depth - ONE_PLY + ext;
1073 // Step 12. Futility pruning (is omitted in PV nodes)
1075 && !captureOrPromotion
1079 && !move_is_castle(move))
1081 // Move count based pruning
1082 if ( moveCount >= futility_move_count(depth)
1083 && (!threatMove || !connected_threat(pos, move, threatMove))
1084 && bestValue > VALUE_MATED_IN_PLY_MAX) // FIXME bestValue is racy
1087 lock_grab(&(sp->lock));
1092 // Value based pruning
1093 // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
1094 // but fixing this made program slightly weaker.
1095 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1096 futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount)
1097 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1099 if (futilityValueScaled < beta)
1103 lock_grab(&(sp->lock));
1104 if (futilityValueScaled > sp->bestValue)
1105 sp->bestValue = bestValue = futilityValueScaled;
1107 else if (futilityValueScaled > bestValue)
1108 bestValue = futilityValueScaled;
1113 // Prune moves with negative SEE at low depths
1114 if ( predictedDepth < 2 * ONE_PLY
1115 && bestValue > VALUE_MATED_IN_PLY_MAX
1116 && pos.see_sign(move) < 0)
1119 lock_grab(&(sp->lock));
1125 // Bad capture detection. Will be used by prob-cut search
1126 isBadCap = depth >= 3 * ONE_PLY
1127 && depth < 8 * ONE_PLY
1128 && captureOrPromotion
1131 && !move_is_promotion(move)
1132 && abs(alpha) < VALUE_MATE_IN_PLY_MAX
1133 && pos.see_sign(move) < 0;
1135 // Step 13. Make the move
1136 pos.do_move(move, st, ci, moveIsCheck);
1138 if (!SpNode && !captureOrPromotion)
1139 movesSearched[playedMoveCount++] = move;
1141 // Step extra. pv search (only in PV nodes)
1142 // The first move in list is the expected PV
1145 // Aspiration window is disabled in multi-pv case
1146 if (Root && MultiPV > 1)
1147 alpha = -VALUE_INFINITE;
1149 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth);
1153 // Step 14. Reduced depth search
1154 // If the move fails high will be re-searched at full depth.
1155 bool doFullDepthSearch = true;
1156 alpha = SpNode ? sp->alpha : alpha;
1158 if ( depth >= 3 * ONE_PLY
1159 && !captureOrPromotion
1161 && !move_is_castle(move)
1162 && ss->killers[0] != move
1163 && ss->killers[1] != move)
1165 ss->reduction = reduction<PvNode>(depth, moveCount);
1168 alpha = SpNode ? sp->alpha : alpha;
1169 Depth d = newDepth - ss->reduction;
1170 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d);
1172 doFullDepthSearch = (value > alpha);
1174 ss->reduction = DEPTH_ZERO; // Restore original reduction
1177 // Probcut search for bad captures. If a reduced search returns a value
1178 // very below beta then we can (almost) safely prune the bad capture.
1181 ss->reduction = 3 * ONE_PLY;
1182 Value rAlpha = alpha - 300;
1183 Depth d = newDepth - ss->reduction;
1184 value = -search<NonPV>(pos, ss+1, -(rAlpha+1), -rAlpha, d);
1185 doFullDepthSearch = (value > rAlpha);
1186 ss->reduction = DEPTH_ZERO; // Restore original reduction
1189 // Step 15. Full depth search
1190 if (doFullDepthSearch)
1192 alpha = SpNode ? sp->alpha : alpha;
1193 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth);
1195 // Step extra. pv search (only in PV nodes)
1196 // Search only for possible new PV nodes, if instead value >= beta then
1197 // parent node fails low with value <= alpha and tries another move.
1198 if (PvNode && value > alpha && (Root || value < beta))
1199 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth);
1203 // Step 16. Undo move
1204 pos.undo_move(move);
1206 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1208 // Step 17. Check for new best move
1211 lock_grab(&(sp->lock));
1212 bestValue = sp->bestValue;
1216 if (value > bestValue && !(SpNode && ThreadsMgr.cutoff_at_splitpoint(threadID)))
1221 sp->bestValue = value;
1223 if (!Root && value > alpha)
1225 if (PvNode && value < beta) // We want always alpha < beta
1233 sp->betaCutoff = true;
1235 if (value == value_mate_in(ss->ply + 1))
1236 ss->mateKiller = move;
1238 ss->bestMove = move;
1241 sp->ss->bestMove = move;
1247 // Finished searching the move. If StopRequest is true, the search
1248 // was aborted because the user interrupted the search or because we
1249 // ran out of time. In this case, the return value of the search cannot
1250 // be trusted, and we break out of the loop without updating the best
1255 // Remember searched nodes counts for this move
1256 mp.rm->nodes += pos.nodes_searched() - nodes;
1258 // PV move or new best move ?
1259 if (isPvMove || value > alpha)
1262 ss->bestMove = move;
1263 mp.rm->pv_score = value;
1264 mp.rm->extract_pv_from_tt(pos);
1266 // We record how often the best move has been changed in each
1267 // iteration. This information is used for time management: When
1268 // the best move changes frequently, we allocate some more time.
1269 if (!isPvMove && MultiPV == 1)
1270 Rml.bestMoveChanges++;
1272 Rml.sort_multipv(moveCount);
1274 // Update alpha. In multi-pv we don't use aspiration window, so
1275 // set alpha equal to minimum score among the PV lines.
1277 alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount?
1278 else if (value > alpha)
1282 mp.rm->pv_score = -VALUE_INFINITE;
1286 // Step 18. Check for split
1289 && depth >= ThreadsMgr.min_split_depth()
1290 && ThreadsMgr.active_threads() > 1
1292 && ThreadsMgr.available_thread_exists(threadID)
1294 && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1295 ThreadsMgr.split<FakeSplit>(pos, ss, &alpha, beta, &bestValue, depth,
1296 threatMove, moveCount, &mp, PvNode);
1299 // Step 19. Check for mate and stalemate
1300 // All legal moves have been searched and if there are
1301 // no legal moves, it must be mate or stalemate.
1302 // If one move was excluded return fail low score.
1303 if (!SpNode && !moveCount)
1304 return excludedMove ? oldAlpha : isCheck ? value_mated_in(ss->ply) : VALUE_DRAW;
1306 // Step 20. Update tables
1307 // If the search is not aborted, update the transposition table,
1308 // history counters, and killer moves.
1309 if (!SpNode && !StopRequest && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1311 move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
1312 vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
1313 : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
1315 TT.store(posKey, value_to_tt(bestValue, ss->ply), vt, depth, move, ss->eval, ss->evalMargin);
1317 // Update killers and history only for non capture moves that fails high
1318 if ( bestValue >= beta
1319 && !pos.move_is_capture_or_promotion(move))
1321 if (move != ss->killers[0])
1323 ss->killers[1] = ss->killers[0];
1324 ss->killers[0] = move;
1326 update_history(pos, move, depth, movesSearched, playedMoveCount);
1332 // Here we have the lock still grabbed
1333 sp->slaves[threadID] = 0;
1334 sp->nodes += pos.nodes_searched();
1335 lock_release(&(sp->lock));
1338 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1343 // qsearch() is the quiescence search function, which is called by the main
1344 // search function when the remaining depth is zero (or, to be more precise,
1345 // less than ONE_PLY).
1347 template <NodeType PvNode>
1348 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) {
1350 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1351 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1352 assert(PvNode || alpha == beta - 1);
1354 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1358 Value bestValue, value, evalMargin, futilityValue, futilityBase;
1359 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1362 Value oldAlpha = alpha;
1364 ss->bestMove = ss->currentMove = MOVE_NONE;
1365 ss->ply = (ss-1)->ply + 1;
1367 // Check for an instant draw or maximum ply reached
1368 if (ss->ply > PLY_MAX || pos.is_draw())
1371 // Decide whether or not to include checks, this fixes also the type of
1372 // TT entry depth that we are going to use. Note that in qsearch we use
1373 // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
1374 isCheck = pos.is_check();
1375 ttDepth = (isCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS);
1377 // Transposition table lookup. At PV nodes, we don't use the TT for
1378 // pruning, but only for move ordering.
1379 tte = TT.retrieve(pos.get_key());
1380 ttMove = (tte ? tte->move() : MOVE_NONE);
1382 if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ss->ply))
1384 ss->bestMove = ttMove; // Can be MOVE_NONE
1385 return value_from_tt(tte->value(), ss->ply);
1388 // Evaluate the position statically
1391 bestValue = futilityBase = -VALUE_INFINITE;
1392 ss->eval = evalMargin = VALUE_NONE;
1393 enoughMaterial = false;
1399 assert(tte->static_value() != VALUE_NONE);
1401 evalMargin = tte->static_value_margin();
1402 ss->eval = bestValue = tte->static_value();
1405 ss->eval = bestValue = evaluate(pos, evalMargin);
1407 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1409 // Stand pat. Return immediately if static value is at least beta
1410 if (bestValue >= beta)
1413 TT.store(pos.get_key(), value_to_tt(bestValue, ss->ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1418 if (PvNode && bestValue > alpha)
1421 // Futility pruning parameters, not needed when in check
1422 futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1423 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1426 // Initialize a MovePicker object for the current position, and prepare
1427 // to search the moves. Because the depth is <= 0 here, only captures,
1428 // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
1430 MovePicker mp(pos, ttMove, depth, H);
1433 // Loop through the moves until no moves remain or a beta cutoff occurs
1434 while ( alpha < beta
1435 && (move = mp.get_next_move()) != MOVE_NONE)
1437 assert(move_is_ok(move));
1439 moveIsCheck = pos.move_is_check(move, ci);
1447 && !move_is_promotion(move)
1448 && !pos.move_is_passed_pawn_push(move))
1450 futilityValue = futilityBase
1451 + pos.endgame_value_of_piece_on(move_to(move))
1452 + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1454 if (futilityValue < alpha)
1456 if (futilityValue > bestValue)
1457 bestValue = futilityValue;
1461 // Prune moves with negative or equal SEE
1462 if ( futilityBase < beta
1463 && depth < DEPTH_ZERO
1464 && pos.see(move) <= 0)
1468 // Detect non-capture evasions that are candidate to be pruned
1469 evasionPrunable = isCheck
1470 && bestValue > VALUE_MATED_IN_PLY_MAX
1471 && !pos.move_is_capture(move)
1472 && !pos.can_castle(pos.side_to_move());
1474 // Don't search moves with negative SEE values
1476 && (!isCheck || evasionPrunable)
1478 && !move_is_promotion(move)
1479 && pos.see_sign(move) < 0)
1482 // Don't search useless checks
1487 && !pos.move_is_capture_or_promotion(move)
1488 && ss->eval + PawnValueMidgame / 4 < beta
1489 && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue))
1491 if (ss->eval + PawnValueMidgame / 4 > bestValue)
1492 bestValue = ss->eval + PawnValueMidgame / 4;
1497 // Update current move
1498 ss->currentMove = move;
1500 // Make and search the move
1501 pos.do_move(move, st, ci, moveIsCheck);
1502 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY);
1503 pos.undo_move(move);
1505 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1508 if (value > bestValue)
1514 ss->bestMove = move;
1519 // All legal moves have been searched. A special case: If we're in check
1520 // and no legal moves were found, it is checkmate.
1521 if (isCheck && bestValue == -VALUE_INFINITE)
1522 return value_mated_in(ss->ply);
1524 // Update transposition table
1525 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1526 TT.store(pos.get_key(), value_to_tt(bestValue, ss->ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin);
1528 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1534 // check_is_dangerous() tests if a checking move can be pruned in qsearch().
1535 // bestValue is updated only when returning false because in that case move
1538 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bestValue)
1540 Bitboard b, occ, oldAtt, newAtt, kingAtt;
1541 Square from, to, ksq, victimSq;
1544 Value futilityValue, bv = *bestValue;
1546 from = move_from(move);
1548 them = opposite_color(pos.side_to_move());
1549 ksq = pos.king_square(them);
1550 kingAtt = pos.attacks_from<KING>(ksq);
1551 pc = pos.piece_on(from);
1553 occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL << ksq);
1554 oldAtt = pos.attacks_from(pc, from, occ);
1555 newAtt = pos.attacks_from(pc, to, occ);
1557 // Rule 1. Checks which give opponent's king at most one escape square are dangerous
1558 b = kingAtt & ~pos.pieces_of_color(them) & ~newAtt & ~(1ULL << to);
1560 if (!(b && (b & (b - 1))))
1563 // Rule 2. Queen contact check is very dangerous
1564 if ( type_of_piece(pc) == QUEEN
1565 && bit_is_set(kingAtt, to))
1568 // Rule 3. Creating new double threats with checks
1569 b = pos.pieces_of_color(them) & newAtt & ~oldAtt & ~(1ULL << ksq);
1573 victimSq = pop_1st_bit(&b);
1574 futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq);
1576 // Note that here we generate illegal "double move"!
1577 if ( futilityValue >= beta
1578 && pos.see_sign(make_move(from, victimSq)) >= 0)
1581 if (futilityValue > bv)
1585 // Update bestValue only if check is not dangerous (because we will prune the move)
1591 // connected_moves() tests whether two moves are 'connected' in the sense
1592 // that the first move somehow made the second move possible (for instance
1593 // if the moving piece is the same in both moves). The first move is assumed
1594 // to be the move that was made to reach the current position, while the
1595 // second move is assumed to be a move from the current position.
1597 bool connected_moves(const Position& pos, Move m1, Move m2) {
1599 Square f1, t1, f2, t2;
1602 assert(m1 && move_is_ok(m1));
1603 assert(m2 && move_is_ok(m2));
1605 // Case 1: The moving piece is the same in both moves
1611 // Case 2: The destination square for m2 was vacated by m1
1617 // Case 3: Moving through the vacated square
1618 if ( piece_is_slider(pos.piece_on(f2))
1619 && bit_is_set(squares_between(f2, t2), f1))
1622 // Case 4: The destination square for m2 is defended by the moving piece in m1
1623 p = pos.piece_on(t1);
1624 if (bit_is_set(pos.attacks_from(p, t1), t2))
1627 // Case 5: Discovered check, checking piece is the piece moved in m1
1628 if ( piece_is_slider(p)
1629 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1630 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1632 // discovered_check_candidates() works also if the Position's side to
1633 // move is the opposite of the checking piece.
1634 Color them = opposite_color(pos.side_to_move());
1635 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1637 if (bit_is_set(dcCandidates, f2))
1644 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1645 // "plies to mate from the current ply". Non-mate scores are unchanged.
1646 // The function is called before storing a value to the transposition table.
1648 Value value_to_tt(Value v, int ply) {
1650 if (v >= VALUE_MATE_IN_PLY_MAX)
1653 if (v <= VALUE_MATED_IN_PLY_MAX)
1660 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1661 // the transposition table to a mate score corrected for the current ply.
1663 Value value_from_tt(Value v, int ply) {
1665 if (v >= VALUE_MATE_IN_PLY_MAX)
1668 if (v <= VALUE_MATED_IN_PLY_MAX)
1675 // extension() decides whether a move should be searched with normal depth,
1676 // or with extended depth. Certain classes of moves (checking moves, in
1677 // particular) are searched with bigger depth than ordinary moves and in
1678 // any case are marked as 'dangerous'. Note that also if a move is not
1679 // extended, as example because the corresponding UCI option is set to zero,
1680 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1681 template <NodeType PvNode>
1682 Depth extension(const Position& pos, Move m, bool captureOrPromotion,
1683 bool moveIsCheck, bool* dangerous) {
1685 assert(m != MOVE_NONE);
1687 Depth result = DEPTH_ZERO;
1688 *dangerous = moveIsCheck;
1690 if (moveIsCheck && pos.see_sign(m) >= 0)
1691 result += CheckExtension[PvNode];
1693 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1695 Color c = pos.side_to_move();
1696 if (relative_rank(c, move_to(m)) == RANK_7)
1698 result += PawnPushTo7thExtension[PvNode];
1701 if (pos.pawn_is_passed(c, move_to(m)))
1703 result += PassedPawnExtension[PvNode];
1708 if ( captureOrPromotion
1709 && pos.type_of_piece_on(move_to(m)) != PAWN
1710 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1711 - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1712 && !move_is_promotion(m)
1715 result += PawnEndgameExtension[PvNode];
1719 return Min(result, ONE_PLY);
1723 // connected_threat() tests whether it is safe to forward prune a move or if
1724 // is somehow connected to the threat move returned by null search.
1726 bool connected_threat(const Position& pos, Move m, Move threat) {
1728 assert(move_is_ok(m));
1729 assert(threat && move_is_ok(threat));
1730 assert(!pos.move_is_check(m));
1731 assert(!pos.move_is_capture_or_promotion(m));
1732 assert(!pos.move_is_passed_pawn_push(m));
1734 Square mfrom, mto, tfrom, tto;
1736 mfrom = move_from(m);
1738 tfrom = move_from(threat);
1739 tto = move_to(threat);
1741 // Case 1: Don't prune moves which move the threatened piece
1745 // Case 2: If the threatened piece has value less than or equal to the
1746 // value of the threatening piece, don't prune moves which defend it.
1747 if ( pos.move_is_capture(threat)
1748 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1749 || pos.type_of_piece_on(tfrom) == KING)
1750 && pos.move_attacks_square(m, tto))
1753 // Case 3: If the moving piece in the threatened move is a slider, don't
1754 // prune safe moves which block its ray.
1755 if ( piece_is_slider(pos.piece_on(tfrom))
1756 && bit_is_set(squares_between(tfrom, tto), mto)
1757 && pos.see_sign(m) >= 0)
1764 // ok_to_use_TT() returns true if a transposition table score
1765 // can be used at a given point in search.
1767 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1769 Value v = value_from_tt(tte->value(), ply);
1771 return ( tte->depth() >= depth
1772 || v >= Max(VALUE_MATE_IN_PLY_MAX, beta)
1773 || v < Min(VALUE_MATED_IN_PLY_MAX, beta))
1775 && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1776 || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1780 // refine_eval() returns the transposition table score if
1781 // possible otherwise falls back on static position evaluation.
1783 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1787 Value v = value_from_tt(tte->value(), ply);
1789 if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1790 || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1797 // update_history() registers a good move that produced a beta-cutoff
1798 // in history and marks as failures all the other moves of that ply.
1800 void update_history(const Position& pos, Move move, Depth depth,
1801 Move movesSearched[], int moveCount) {
1803 Value bonus = Value(int(depth) * int(depth));
1805 H.update(pos.piece_on(move_from(move)), move_to(move), bonus);
1807 for (int i = 0; i < moveCount - 1; i++)
1809 m = movesSearched[i];
1813 H.update(pos.piece_on(move_from(m)), move_to(m), -bonus);
1818 // update_gains() updates the gains table of a non-capture move given
1819 // the static position evaluation before and after the move.
1821 void update_gains(const Position& pos, Move m, Value before, Value after) {
1824 && before != VALUE_NONE
1825 && after != VALUE_NONE
1826 && pos.captured_piece_type() == PIECE_TYPE_NONE
1827 && !move_is_special(m))
1828 H.update_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
1832 // current_search_time() returns the number of milliseconds which have passed
1833 // since the beginning of the current search.
1835 int current_search_time() {
1837 return get_system_time() - SearchStartTime;
1841 // value_to_uci() converts a value to a string suitable for use with the UCI
1842 // protocol specifications:
1844 // cp <x> The score from the engine's point of view in centipawns.
1845 // mate <y> Mate in y moves, not plies. If the engine is getting mated
1846 // use negative values for y.
1848 std::string value_to_uci(Value v) {
1850 std::stringstream s;
1852 if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
1853 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to centipawns
1855 s << "mate " << (v > 0 ? VALUE_MATE - v + 1 : -VALUE_MATE - v) / 2;
1861 // speed_to_uci() returns a string with time stats of current search suitable
1862 // to be sent to UCI gui.
1864 std::string speed_to_uci(int64_t nodes) {
1866 std::stringstream s;
1867 int t = current_search_time();
1869 s << " nodes " << nodes
1870 << " nps " << (t > 0 ? int(nodes * 1000 / t) : 0)
1877 // poll() performs two different functions: It polls for user input, and it
1878 // looks at the time consumed so far and decides if it's time to abort the
1881 void poll(const Position& pos) {
1883 static int lastInfoTime;
1884 int t = current_search_time();
1887 if (input_available())
1889 // We are line oriented, don't read single chars
1890 std::string command;
1892 if (!std::getline(std::cin, command) || command == "quit")
1894 // Quit the program as soon as possible
1896 QuitRequest = StopRequest = true;
1899 else if (command == "stop")
1901 // Stop calculating as soon as possible, but still send the "bestmove"
1902 // and possibly the "ponder" token when finishing the search.
1906 else if (command == "ponderhit")
1908 // The opponent has played the expected move. GUI sends "ponderhit" if
1909 // we were told to ponder on the same move the opponent has played. We
1910 // should continue searching but switching from pondering to normal search.
1913 if (StopOnPonderhit)
1918 // Print search information
1922 else if (lastInfoTime > t)
1923 // HACK: Must be a new search where we searched less than
1924 // NodesBetweenPolls nodes during the first second of search.
1927 else if (t - lastInfoTime >= 1000)
1932 dbg_print_hit_rate();
1934 // Send info on searched nodes as soon as we return to root
1935 SendSearchedNodes = true;
1938 // Should we stop the search?
1942 bool stillAtFirstMove = FirstRootMove
1943 && !AspirationFailLow
1944 && t > TimeMgr.available_time();
1946 bool noMoreTime = t > TimeMgr.maximum_time()
1947 || stillAtFirstMove;
1949 if ( (UseTimeManagement && noMoreTime)
1950 || (ExactMaxTime && t >= ExactMaxTime)
1951 || (MaxNodes && pos.nodes_searched() >= MaxNodes)) // FIXME
1956 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
1957 // while the program is pondering. The point is to work around a wrinkle in
1958 // the UCI protocol: When pondering, the engine is not allowed to give a
1959 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
1960 // We simply wait here until one of these commands is sent, and return,
1961 // after which the bestmove and pondermove will be printed.
1963 void wait_for_stop_or_ponderhit() {
1965 std::string command;
1967 // Wait for a command from stdin
1968 while ( std::getline(std::cin, command)
1969 && command != "ponderhit" && command != "stop" && command != "quit") {};
1971 if (command != "ponderhit" && command != "stop")
1972 QuitRequest = true; // Must be "quit" or getline() returned false
1976 // init_thread() is the function which is called when a new thread is
1977 // launched. It simply calls the idle_loop() function with the supplied
1978 // threadID. There are two versions of this function; one for POSIX
1979 // threads and one for Windows threads.
1981 #if !defined(_MSC_VER)
1983 void* init_thread(void* threadID) {
1985 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
1991 DWORD WINAPI init_thread(LPVOID threadID) {
1993 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2000 /// The ThreadsManager class
2003 // read_uci_options() updates number of active threads and other internal
2004 // parameters according to the UCI options values. It is called before
2005 // to start a new search.
2007 void ThreadsManager::read_uci_options() {
2009 maxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value<int>();
2010 minimumSplitDepth = Options["Minimum Split Depth"].value<int>() * ONE_PLY;
2011 useSleepingThreads = Options["Use Sleeping Threads"].value<bool>();
2012 activeThreads = Options["Threads"].value<int>();
2016 // idle_loop() is where the threads are parked when they have no work to do.
2017 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2018 // object for which the current thread is the master.
2020 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2022 assert(threadID >= 0 && threadID < MAX_THREADS);
2025 bool allFinished = false;
2029 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2030 // master should exit as last one.
2031 if (allThreadsShouldExit)
2034 threads[threadID].state = THREAD_TERMINATED;
2038 // If we are not thinking, wait for a condition to be signaled
2039 // instead of wasting CPU time polling for work.
2040 while ( threadID >= activeThreads || threads[threadID].state == THREAD_INITIALIZING
2041 || (useSleepingThreads && threads[threadID].state == THREAD_AVAILABLE))
2043 assert(!sp || useSleepingThreads);
2044 assert(threadID != 0 || useSleepingThreads);
2046 if (threads[threadID].state == THREAD_INITIALIZING)
2047 threads[threadID].state = THREAD_AVAILABLE;
2049 // Grab the lock to avoid races with wake_sleeping_thread()
2050 lock_grab(&sleepLock[threadID]);
2052 // If we are master and all slaves have finished do not go to sleep
2053 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2054 allFinished = (i == activeThreads);
2056 if (allFinished || allThreadsShouldExit)
2058 lock_release(&sleepLock[threadID]);
2062 // Do sleep here after retesting sleep conditions
2063 if (threadID >= activeThreads || threads[threadID].state == THREAD_AVAILABLE)
2064 cond_wait(&sleepCond[threadID], &sleepLock[threadID]);
2066 lock_release(&sleepLock[threadID]);
2069 // If this thread has been assigned work, launch a search
2070 if (threads[threadID].state == THREAD_WORKISWAITING)
2072 assert(!allThreadsShouldExit);
2074 threads[threadID].state = THREAD_SEARCHING;
2076 // Copy SplitPoint position and search stack and call search()
2077 // with SplitPoint template parameter set to true.
2078 SearchStack ss[PLY_MAX_PLUS_2];
2079 SplitPoint* tsp = threads[threadID].splitPoint;
2080 Position pos(*tsp->pos, threadID);
2082 memcpy(ss, tsp->ss - 1, 4 * sizeof(SearchStack));
2086 search<PV, true, false>(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth);
2088 search<NonPV, true, false>(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth);
2090 assert(threads[threadID].state == THREAD_SEARCHING);
2092 threads[threadID].state = THREAD_AVAILABLE;
2094 // Wake up master thread so to allow it to return from the idle loop in
2095 // case we are the last slave of the split point.
2096 if (useSleepingThreads && threadID != tsp->master && threads[tsp->master].state == THREAD_AVAILABLE)
2097 wake_sleeping_thread(tsp->master);
2100 // If this thread is the master of a split point and all slaves have
2101 // finished their work at this split point, return from the idle loop.
2102 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2103 allFinished = (i == activeThreads);
2107 // Because sp->slaves[] is reset under lock protection,
2108 // be sure sp->lock has been released before to return.
2109 lock_grab(&(sp->lock));
2110 lock_release(&(sp->lock));
2112 // In helpful master concept a master can help only a sub-tree, and
2113 // because here is all finished is not possible master is booked.
2114 assert(threads[threadID].state == THREAD_AVAILABLE);
2116 threads[threadID].state = THREAD_SEARCHING;
2123 // init_threads() is called during startup. It launches all helper threads,
2124 // and initializes the split point stack and the global locks and condition
2127 void ThreadsManager::init_threads() {
2129 int i, arg[MAX_THREADS];
2132 // Initialize global locks
2135 for (i = 0; i < MAX_THREADS; i++)
2137 lock_init(&sleepLock[i]);
2138 cond_init(&sleepCond[i]);
2141 // Initialize splitPoints[] locks
2142 for (i = 0; i < MAX_THREADS; i++)
2143 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2144 lock_init(&(threads[i].splitPoints[j].lock));
2146 // Will be set just before program exits to properly end the threads
2147 allThreadsShouldExit = false;
2149 // Threads will be put all threads to sleep as soon as created
2152 // All threads except the main thread should be initialized to THREAD_INITIALIZING
2153 threads[0].state = THREAD_SEARCHING;
2154 for (i = 1; i < MAX_THREADS; i++)
2155 threads[i].state = THREAD_INITIALIZING;
2157 // Launch the helper threads
2158 for (i = 1; i < MAX_THREADS; i++)
2162 #if !defined(_MSC_VER)
2163 pthread_t pthread[1];
2164 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
2165 pthread_detach(pthread[0]);
2167 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
2171 cout << "Failed to create thread number " << i << endl;
2175 // Wait until the thread has finished launching and is gone to sleep
2176 while (threads[i].state == THREAD_INITIALIZING) {}
2181 // exit_threads() is called when the program exits. It makes all the
2182 // helper threads exit cleanly.
2184 void ThreadsManager::exit_threads() {
2186 allThreadsShouldExit = true; // Let the woken up threads to exit idle_loop()
2188 // Wake up all the threads and waits for termination
2189 for (int i = 1; i < MAX_THREADS; i++)
2191 wake_sleeping_thread(i);
2192 while (threads[i].state != THREAD_TERMINATED) {}
2195 // Now we can safely destroy the locks
2196 for (int i = 0; i < MAX_THREADS; i++)
2197 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2198 lock_destroy(&(threads[i].splitPoints[j].lock));
2200 lock_destroy(&mpLock);
2202 // Now we can safely destroy the wait conditions
2203 for (int i = 0; i < MAX_THREADS; i++)
2205 lock_destroy(&sleepLock[i]);
2206 cond_destroy(&sleepCond[i]);
2211 // cutoff_at_splitpoint() checks whether a beta cutoff has occurred in
2212 // the thread's currently active split point, or in some ancestor of
2213 // the current split point.
2215 bool ThreadsManager::cutoff_at_splitpoint(int threadID) const {
2217 assert(threadID >= 0 && threadID < activeThreads);
2219 SplitPoint* sp = threads[threadID].splitPoint;
2221 for ( ; sp && !sp->betaCutoff; sp = sp->parent) {}
2226 // thread_is_available() checks whether the thread with threadID "slave" is
2227 // available to help the thread with threadID "master" at a split point. An
2228 // obvious requirement is that "slave" must be idle. With more than two
2229 // threads, this is not by itself sufficient: If "slave" is the master of
2230 // some active split point, it is only available as a slave to the other
2231 // threads which are busy searching the split point at the top of "slave"'s
2232 // split point stack (the "helpful master concept" in YBWC terminology).
2234 bool ThreadsManager::thread_is_available(int slave, int master) const {
2236 assert(slave >= 0 && slave < activeThreads);
2237 assert(master >= 0 && master < activeThreads);
2238 assert(activeThreads > 1);
2240 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2243 // Make a local copy to be sure doesn't change under our feet
2244 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2246 // No active split points means that the thread is available as
2247 // a slave for any other thread.
2248 if (localActiveSplitPoints == 0 || activeThreads == 2)
2251 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2252 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2253 // could have been set to 0 by another thread leading to an out of bound access.
2254 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2261 // available_thread_exists() tries to find an idle thread which is available as
2262 // a slave for the thread with threadID "master".
2264 bool ThreadsManager::available_thread_exists(int master) const {
2266 assert(master >= 0 && master < activeThreads);
2267 assert(activeThreads > 1);
2269 for (int i = 0; i < activeThreads; i++)
2270 if (thread_is_available(i, master))
2277 // split() does the actual work of distributing the work at a node between
2278 // several available threads. If it does not succeed in splitting the
2279 // node (because no idle threads are available, or because we have no unused
2280 // split point objects), the function immediately returns. If splitting is
2281 // possible, a SplitPoint object is initialized with all the data that must be
2282 // copied to the helper threads and we tell our helper threads that they have
2283 // been assigned work. This will cause them to instantly leave their idle loops and
2284 // call search().When all threads have returned from search() then split() returns.
2286 template <bool Fake>
2287 void ThreadsManager::split(Position& pos, SearchStack* ss, Value* alpha, const Value beta,
2288 Value* bestValue, Depth depth, Move threatMove,
2289 int moveCount, MovePicker* mp, bool pvNode) {
2290 assert(pos.is_ok());
2291 assert(*bestValue >= -VALUE_INFINITE);
2292 assert(*bestValue <= *alpha);
2293 assert(*alpha < beta);
2294 assert(beta <= VALUE_INFINITE);
2295 assert(depth > DEPTH_ZERO);
2296 assert(pos.thread() >= 0 && pos.thread() < activeThreads);
2297 assert(activeThreads > 1);
2299 int i, master = pos.thread();
2300 Thread& masterThread = threads[master];
2304 // If no other thread is available to help us, or if we have too many
2305 // active split points, don't split.
2306 if ( !available_thread_exists(master)
2307 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2309 lock_release(&mpLock);
2313 // Pick the next available split point object from the split point stack
2314 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2316 // Initialize the split point object
2317 splitPoint.parent = masterThread.splitPoint;
2318 splitPoint.master = master;
2319 splitPoint.betaCutoff = false;
2320 splitPoint.depth = depth;
2321 splitPoint.threatMove = threatMove;
2322 splitPoint.alpha = *alpha;
2323 splitPoint.beta = beta;
2324 splitPoint.pvNode = pvNode;
2325 splitPoint.bestValue = *bestValue;
2327 splitPoint.moveCount = moveCount;
2328 splitPoint.pos = &pos;
2329 splitPoint.nodes = 0;
2331 for (i = 0; i < activeThreads; i++)
2332 splitPoint.slaves[i] = 0;
2334 masterThread.splitPoint = &splitPoint;
2336 // If we are here it means we are not available
2337 assert(masterThread.state != THREAD_AVAILABLE);
2339 int workersCnt = 1; // At least the master is included
2341 // Allocate available threads setting state to THREAD_BOOKED
2342 for (i = 0; !Fake && i < activeThreads && workersCnt < maxThreadsPerSplitPoint; i++)
2343 if (thread_is_available(i, master))
2345 threads[i].state = THREAD_BOOKED;
2346 threads[i].splitPoint = &splitPoint;
2347 splitPoint.slaves[i] = 1;
2351 assert(Fake || workersCnt > 1);
2353 // We can release the lock because slave threads are already booked and master is not available
2354 lock_release(&mpLock);
2356 // Tell the threads that they have work to do. This will make them leave
2358 for (i = 0; i < activeThreads; i++)
2359 if (i == master || splitPoint.slaves[i])
2361 assert(i == master || threads[i].state == THREAD_BOOKED);
2363 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2365 if (useSleepingThreads && i != master)
2366 wake_sleeping_thread(i);
2369 // Everything is set up. The master thread enters the idle loop, from
2370 // which it will instantly launch a search, because its state is
2371 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2372 // idle loop, which means that the main thread will return from the idle
2373 // loop when all threads have finished their work at this split point.
2374 idle_loop(master, &splitPoint);
2376 // We have returned from the idle loop, which means that all threads are
2377 // finished. Update alpha and bestValue, and return.
2380 *alpha = splitPoint.alpha;
2381 *bestValue = splitPoint.bestValue;
2382 masterThread.activeSplitPoints--;
2383 masterThread.splitPoint = splitPoint.parent;
2384 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
2386 lock_release(&mpLock);
2390 // wake_sleeping_thread() wakes up the thread with the given threadID
2391 // when it is time to start a new search.
2393 void ThreadsManager::wake_sleeping_thread(int threadID) {
2395 lock_grab(&sleepLock[threadID]);
2396 cond_signal(&sleepCond[threadID]);
2397 lock_release(&sleepLock[threadID]);
2401 /// RootMove and RootMoveList method's definitions
2403 RootMove::RootMove() {
2406 pv_score = non_pv_score = -VALUE_INFINITE;
2410 RootMove& RootMove::operator=(const RootMove& rm) {
2412 const Move* src = rm.pv;
2415 // Avoid a costly full rm.pv[] copy
2416 do *dst++ = *src; while (*src++ != MOVE_NONE);
2419 pv_score = rm.pv_score;
2420 non_pv_score = rm.non_pv_score;
2424 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2425 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2426 // allow to always have a ponder move even when we fail high at root and also a
2427 // long PV to print that is important for position analysis.
2429 void RootMove::extract_pv_from_tt(Position& pos) {
2431 StateInfo state[PLY_MAX_PLUS_2], *st = state;
2435 assert(pv[0] != MOVE_NONE && pos.move_is_legal(pv[0]));
2437 pos.do_move(pv[0], *st++);
2439 while ( (tte = TT.retrieve(pos.get_key())) != NULL
2440 && tte->move() != MOVE_NONE
2441 && pos.move_is_legal(tte->move())
2443 && (!pos.is_draw() || ply < 2))
2445 pv[ply] = tte->move();
2446 pos.do_move(pv[ply++], *st++);
2448 pv[ply] = MOVE_NONE;
2450 do pos.undo_move(pv[--ply]); while (ply);
2453 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2454 // the PV back into the TT. This makes sure the old PV moves are searched
2455 // first, even if the old TT entries have been overwritten.
2457 void RootMove::insert_pv_in_tt(Position& pos) {
2459 StateInfo state[PLY_MAX_PLUS_2], *st = state;
2462 Value v, m = VALUE_NONE;
2465 assert(pv[0] != MOVE_NONE && pos.move_is_legal(pv[0]));
2469 tte = TT.retrieve(k);
2471 // Don't overwrite existing correct entries
2472 if (!tte || tte->move() != pv[ply])
2474 v = (pos.is_check() ? VALUE_NONE : evaluate(pos, m));
2475 TT.store(k, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[ply], v, m);
2477 pos.do_move(pv[ply], *st++);
2479 } while (pv[++ply] != MOVE_NONE);
2481 do pos.undo_move(pv[--ply]); while (ply);
2484 // pv_info_to_uci() returns a string with information on the current PV line
2485 // formatted according to UCI specification.
2487 std::string RootMove::pv_info_to_uci(Position& pos, int depth, Value alpha,
2488 Value beta, int pvIdx) {
2489 std::stringstream s, l;
2492 while (*m != MOVE_NONE)
2495 s << "info depth " << depth
2496 << " seldepth " << int(m - pv)
2497 << " multipv " << pvIdx + 1
2498 << " score " << value_to_uci(pv_score)
2499 << (pv_score >= beta ? " lowerbound" : pv_score <= alpha ? " upperbound" : "")
2500 << speed_to_uci(pos.nodes_searched())
2501 << " pv " << l.str();
2507 void RootMoveList::init(Position& pos, Move searchMoves[]) {
2509 MoveStack mlist[MOVES_MAX];
2513 bestMoveChanges = 0;
2515 // Generate all legal moves and add them to RootMoveList
2516 MoveStack* last = generate<MV_LEGAL>(pos, mlist);
2517 for (MoveStack* cur = mlist; cur != last; cur++)
2519 // If we have a searchMoves[] list then verify cur->move
2520 // is in the list before to add it.
2521 for (sm = searchMoves; *sm && *sm != cur->move; sm++) {}
2523 if (searchMoves[0] && *sm != cur->move)
2527 rm.pv[0] = cur->move;
2528 rm.pv[1] = MOVE_NONE;
2529 rm.pv_score = -VALUE_INFINITE;
2535 // When playing with strength handicap choose best move among the MultiPV set
2536 // using a statistical rule dependent on SkillLevel. Idea by Heinz van Saanen.
2537 void do_skill_level(Move* best, Move* ponder) {
2539 assert(MultiPV > 1);
2541 // Rml list is already sorted by pv_score in descending order
2543 int max_s = -VALUE_INFINITE;
2544 int size = Min(MultiPV, (int)Rml.size());
2545 int max = Rml[0].pv_score;
2546 int var = Min(max - Rml[size - 1].pv_score, PawnValueMidgame);
2547 int wk = 120 - 2 * SkillLevel;
2549 // PRNG sequence should be non deterministic
2550 for (int i = abs(get_system_time() % 50); i > 0; i--)
2551 RK.rand<unsigned>();
2553 // Choose best move. For each move's score we add two terms both dependent
2554 // on wk, one deterministic and bigger for weaker moves, and one random,
2555 // then we choose the move with the resulting highest score.
2556 for (int i = 0; i < size; i++)
2558 s = Rml[i].pv_score;
2560 // Don't allow crazy blunders even at very low skills
2561 if (i > 0 && Rml[i-1].pv_score > s + EasyMoveMargin)
2564 // This is our magical formula
2565 s += ((max - s) * wk + var * (RK.rand<unsigned>() % wk)) / 128;
2570 *best = Rml[i].pv[0];
2571 *ponder = Rml[i].pv[1];