2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad
6 Stockfish is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 Stockfish is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
45 #include "ucioption.h"
51 //// Local definitions
57 enum NodeType { NonPV, PV };
59 // Set to true to force running with one thread.
60 // Used for debugging SMP code.
61 const bool FakeSplit = false;
63 // Fast lookup table of sliding pieces indexed by Piece
64 const bool Slidings[18] = { 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1 };
65 inline bool piece_is_slider(Piece p) { return Slidings[p]; }
67 // ThreadsManager class is used to handle all the threads related stuff in search,
68 // init, starting, parking and, the most important, launching a slave thread at a
69 // split point are what this class does. All the access to shared thread data is
70 // done through this class, so that we avoid using global variables instead.
72 class ThreadsManager {
73 /* As long as the single ThreadsManager object is defined as a global we don't
74 need to explicitly initialize to zero its data members because variables with
75 static storage duration are automatically set to zero before enter main()
81 int min_split_depth() const { return minimumSplitDepth; }
82 int active_threads() const { return activeThreads; }
83 void set_active_threads(int cnt) { activeThreads = cnt; }
85 void read_uci_options();
86 bool available_thread_exists(int master) const;
87 bool thread_is_available(int slave, int master) const;
88 bool cutoff_at_splitpoint(int threadID) const;
89 void wake_sleeping_thread(int threadID);
90 void idle_loop(int threadID, SplitPoint* sp);
93 void split(Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
94 Depth depth, Move threatMove, bool mateThreat, int moveCount, MovePicker* mp, bool pvNode);
97 Depth minimumSplitDepth;
98 int maxThreadsPerSplitPoint;
99 bool useSleepingThreads;
101 volatile bool allThreadsShouldExit;
102 Thread threads[MAX_THREADS];
103 Lock mpLock, sleepLock[MAX_THREADS];
104 WaitCondition sleepCond[MAX_THREADS];
108 // RootMove struct is used for moves at the root at the tree. For each root
109 // move, we store two scores, a node count, and a PV (really a refutation
110 // in the case of moves which fail low). Value pv_score is normally set at
111 // -VALUE_INFINITE for all non-pv moves, while non_pv_score is computed
112 // according to the order in which moves are returned by MovePicker.
117 RootMove(const RootMove& rm) { *this = rm; }
118 RootMove& operator=(const RootMove& rm);
120 // RootMove::operator<() is the comparison function used when
121 // sorting the moves. A move m1 is considered to be better
122 // than a move m2 if it has an higher pv_score, or if it has
123 // equal pv_score but m1 has the higher non_pv_score. In this
124 // way we are guaranteed that PV moves are always sorted as first.
125 bool operator<(const RootMove& m) const {
126 return pv_score != m.pv_score ? pv_score < m.pv_score
127 : non_pv_score <= m.non_pv_score;
129 void set_pv(const Move newPv[]);
135 Move pv[PLY_MAX_PLUS_2];
138 RootMove::RootMove() {
141 pv_score = non_pv_score = -VALUE_INFINITE;
142 move = pv[0] = MOVE_NONE;
145 RootMove& RootMove::operator=(const RootMove& rm) {
148 pv_score = rm.pv_score;
149 non_pv_score = rm.non_pv_score;
151 set_pv(rm.pv); // Skip costly full pv[] copy
155 void RootMove::set_pv(const Move newPv[]) {
159 do *p++ = *newPv; while (*newPv++ != MOVE_NONE);
163 // RootMoveList struct is essentially a std::vector<> of RootMove objects,
164 // with an handful of methods above the standard ones.
166 struct RootMoveList : public std::vector<RootMove> {
168 typedef std::vector<RootMove> Base;
170 RootMoveList(Position& pos, Move searchMoves[]);
171 void set_non_pv_scores(const Position& pos);
173 void sort() { insertion_sort<RootMove, Base::iterator>(begin(), end()); }
174 void sort_multipv(int n) { insertion_sort<RootMove, Base::iterator>(begin(), begin() + n); }
178 // When formatting a move for std::cout we must know if we are in Chess960
179 // or not. To keep using the handy operator<<() on the move the trick is to
180 // embed this flag in the stream itself. Function-like named enum set960 is
181 // used as a custom manipulator and the stream internal general-purpose array,
182 // accessed through ios_base::iword(), is used to pass the flag to the move's
183 // operator<<() that will use it to properly format castling moves.
186 std::ostream& operator<< (std::ostream& os, const set960& m) {
188 os.iword(0) = int(m);
197 // Maximum depth for razoring
198 const Depth RazorDepth = 4 * ONE_PLY;
200 // Dynamic razoring margin based on depth
201 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
203 // Maximum depth for use of dynamic threat detection when null move fails low
204 const Depth ThreatDepth = 5 * ONE_PLY;
206 // Step 9. Internal iterative deepening
208 // Minimum depth for use of internal iterative deepening
209 const Depth IIDDepth[2] = { 8 * ONE_PLY /* non-PV */, 5 * ONE_PLY /* PV */};
211 // At Non-PV nodes we do an internal iterative deepening search
212 // when the static evaluation is bigger then beta - IIDMargin.
213 const Value IIDMargin = Value(0x100);
215 // Step 11. Decide the new search depth
217 // Extensions. Configurable UCI options
218 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
219 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
220 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
222 // Minimum depth for use of singular extension
223 const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */};
225 // If the TT move is at least SingularExtensionMargin better then the
226 // remaining ones we will extend it.
227 const Value SingularExtensionMargin = Value(0x20);
229 // Step 12. Futility pruning
231 // Futility margin for quiescence search
232 const Value FutilityMarginQS = Value(0x80);
234 // Futility lookup tables (initialized at startup) and their getter functions
235 Value FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
236 int FutilityMoveCountArray[32]; // [depth]
238 inline Value futility_margin(Depth d, int mn) { return d < 7 * ONE_PLY ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE; }
239 inline int futility_move_count(Depth d) { return d < 16 * ONE_PLY ? FutilityMoveCountArray[d] : 512; }
241 // Step 14. Reduced search
243 // Reduction lookup tables (initialized at startup) and their getter functions
244 int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
246 template <NodeType PV>
247 inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
249 // Common adjustments
251 // Search depth at iteration 1
252 const Depth InitialDepth = ONE_PLY;
254 // Easy move margin. An easy move candidate must be at least this much
255 // better than the second best move.
256 const Value EasyMoveMargin = Value(0x200);
259 /// Namespace variables
267 // Scores and number of times the best move changed for each iteration
268 Value ValueByIteration[PLY_MAX_PLUS_2];
269 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
271 // Search window management
277 // Time managment variables
278 int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
279 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
280 bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
285 std::ofstream LogFile;
287 // Multi-threads manager object
288 ThreadsManager ThreadsMgr;
290 // Node counters, used only by thread[0] but try to keep in different cache
291 // lines (64 bytes each) from the heavy multi-thread read accessed variables.
293 int NodesBetweenPolls = 30000;
300 Value id_loop(Position& pos, Move searchMoves[]);
301 Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
303 template <NodeType PvNode, bool SpNode>
304 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
306 template <NodeType PvNode>
307 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
309 template <NodeType PvNode>
310 inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
312 return depth < ONE_PLY ? qsearch<PvNode>(pos, ss, alpha, beta, DEPTH_ZERO, ply)
313 : search<PvNode, false>(pos, ss, alpha, beta, depth, ply);
316 template <NodeType PvNode>
317 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
319 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue);
320 bool connected_moves(const Position& pos, Move m1, Move m2);
321 bool value_is_mate(Value value);
322 Value value_to_tt(Value v, int ply);
323 Value value_from_tt(Value v, int ply);
324 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
325 bool connected_threat(const Position& pos, Move m, Move threat);
326 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
327 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
328 void update_killers(Move m, SearchStack* ss);
329 void update_gains(const Position& pos, Move move, Value before, Value after);
331 int current_search_time();
332 std::string value_to_uci(Value v);
333 int nps(const Position& pos);
334 void poll(const Position& pos);
336 void wait_for_stop_or_ponderhit();
337 void init_ss_array(SearchStack* ss, int size);
338 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value);
339 void insert_pv_in_tt(const Position& pos, Move pv[]);
340 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]);
342 #if !defined(_MSC_VER)
343 void* init_thread(void* threadID);
345 DWORD WINAPI init_thread(LPVOID threadID);
355 /// init_threads(), exit_threads() and nodes_searched() are helpers to
356 /// give accessibility to some TM methods from outside of current file.
358 void init_threads() { ThreadsMgr.init_threads(); }
359 void exit_threads() { ThreadsMgr.exit_threads(); }
362 /// init_search() is called during startup. It initializes various lookup tables
366 int d; // depth (ONE_PLY == 2)
367 int hd; // half depth (ONE_PLY == 1)
370 // Init reductions array
371 for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
373 double pvRed = log(double(hd)) * log(double(mc)) / 3.0;
374 double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
375 ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0);
376 ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0);
379 // Init futility margins array
380 for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
381 FutilityMarginsMatrix[d][mc] = Value(112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45);
383 // Init futility move count array
384 for (d = 0; d < 32; d++)
385 FutilityMoveCountArray[d] = int(3.001 + 0.25 * pow(d, 2.0));
389 /// perft() is our utility to verify move generation is bug free. All the legal
390 /// moves up to given depth are generated and counted and the sum returned.
392 int perft(Position& pos, Depth depth)
394 MoveStack mlist[MOVES_MAX];
399 // Generate all legal moves
400 MoveStack* last = generate_moves(pos, mlist);
402 // If we are at the last ply we don't need to do and undo
403 // the moves, just to count them.
404 if (depth <= ONE_PLY)
405 return int(last - mlist);
407 // Loop through all legal moves
409 for (MoveStack* cur = mlist; cur != last; cur++)
412 pos.do_move(m, st, ci, pos.move_is_check(m, ci));
413 sum += perft(pos, depth - ONE_PLY);
420 /// think() is the external interface to Stockfish's search, and is called when
421 /// the program receives the UCI 'go' command. It initializes various
422 /// search-related global variables, and calls root_search(). It returns false
423 /// when a quit command is received during the search.
425 bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[],
426 int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) {
428 // Initialize global search variables
429 StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
431 SearchStartTime = get_system_time();
432 ExactMaxTime = maxTime;
435 InfiniteSearch = infinite;
436 PonderSearch = ponder;
437 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
439 // Look for a book move, only during games, not tests
440 if (UseTimeManagement && Options["OwnBook"].value<bool>())
442 if (Options["Book File"].value<std::string>() != OpeningBook.file_name())
443 OpeningBook.open(Options["Book File"].value<std::string>());
445 Move bookMove = OpeningBook.get_move(pos, Options["Best Book Move"].value<bool>());
446 if (bookMove != MOVE_NONE)
449 wait_for_stop_or_ponderhit();
451 cout << "bestmove " << bookMove << endl;
456 // Read UCI option values
457 TT.set_size(Options["Hash"].value<int>());
458 if (Options["Clear Hash"].value<bool>())
460 Options["Clear Hash"].set_value("false");
464 CheckExtension[1] = Options["Check Extension (PV nodes)"].value<Depth>();
465 CheckExtension[0] = Options["Check Extension (non-PV nodes)"].value<Depth>();
466 SingleEvasionExtension[1] = Options["Single Evasion Extension (PV nodes)"].value<Depth>();
467 SingleEvasionExtension[0] = Options["Single Evasion Extension (non-PV nodes)"].value<Depth>();
468 PawnPushTo7thExtension[1] = Options["Pawn Push to 7th Extension (PV nodes)"].value<Depth>();
469 PawnPushTo7thExtension[0] = Options["Pawn Push to 7th Extension (non-PV nodes)"].value<Depth>();
470 PassedPawnExtension[1] = Options["Passed Pawn Extension (PV nodes)"].value<Depth>();
471 PassedPawnExtension[0] = Options["Passed Pawn Extension (non-PV nodes)"].value<Depth>();
472 PawnEndgameExtension[1] = Options["Pawn Endgame Extension (PV nodes)"].value<Depth>();
473 PawnEndgameExtension[0] = Options["Pawn Endgame Extension (non-PV nodes)"].value<Depth>();
474 MateThreatExtension[1] = Options["Mate Threat Extension (PV nodes)"].value<Depth>();
475 MateThreatExtension[0] = Options["Mate Threat Extension (non-PV nodes)"].value<Depth>();
476 MultiPV = Options["MultiPV"].value<int>();
477 UseLogFile = Options["Use Search Log"].value<bool>();
480 LogFile.open(Options["Search Log Filename"].value<std::string>().c_str(), std::ios::out | std::ios::app);
482 read_weights(pos.side_to_move());
484 // Set the number of active threads
485 ThreadsMgr.read_uci_options();
486 init_eval(ThreadsMgr.active_threads());
488 // Wake up needed threads
489 for (int i = 1; i < ThreadsMgr.active_threads(); i++)
490 ThreadsMgr.wake_sleeping_thread(i);
493 int myTime = time[pos.side_to_move()];
494 int myIncrement = increment[pos.side_to_move()];
495 if (UseTimeManagement)
496 TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter());
498 // Set best NodesBetweenPolls interval to avoid lagging under
499 // heavy time pressure.
501 NodesBetweenPolls = Min(MaxNodes, 30000);
502 else if (myTime && myTime < 1000)
503 NodesBetweenPolls = 1000;
504 else if (myTime && myTime < 5000)
505 NodesBetweenPolls = 5000;
507 NodesBetweenPolls = 30000;
509 // Write search information to log file
511 LogFile << "Searching: " << pos.to_fen() << endl
512 << "infinite: " << infinite
513 << " ponder: " << ponder
514 << " time: " << myTime
515 << " increment: " << myIncrement
516 << " moves to go: " << movesToGo << endl;
518 // We're ready to start thinking. Call the iterative deepening loop function
519 id_loop(pos, searchMoves);
524 // This makes all the threads to go to sleep
525 ThreadsMgr.set_active_threads(1);
533 // id_loop() is the main iterative deepening loop. It calls root_search
534 // repeatedly with increasing depth until the allocated thinking time has
535 // been consumed, the user stops the search, or the maximum search depth is
538 Value id_loop(Position& pos, Move searchMoves[]) {
540 SearchStack ss[PLY_MAX_PLUS_2];
541 Move pv[PLY_MAX_PLUS_2];
542 Move EasyMove = MOVE_NONE;
543 Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
545 // Moves to search are verified, copied, scored and sorted
546 RootMoveList rml(pos, searchMoves);
548 // Handle special case of searching on a mate/stale position
552 wait_for_stop_or_ponderhit();
554 return pos.is_check() ? -VALUE_MATE : VALUE_DRAW;
557 // Print RootMoveList startup scoring to the standard output,
558 // so to output information also for iteration 1.
559 cout << set960(pos.is_chess960()) // Is enough to set once at the beginning
560 << "info depth " << 1
561 << "\ninfo depth " << 1
562 << " score " << value_to_uci(rml[0].pv_score)
563 << " time " << current_search_time()
564 << " nodes " << pos.nodes_searched()
565 << " nps " << nps(pos)
566 << " pv " << rml[0].move << "\n";
571 init_ss_array(ss, PLY_MAX_PLUS_2);
572 pv[0] = pv[1] = MOVE_NONE;
573 ValueByIteration[1] = rml[0].pv_score;
576 // Is one move significantly better than others after initial scoring ?
578 || rml[0].pv_score > rml[1].pv_score + EasyMoveMargin)
579 EasyMove = rml[0].move;
581 // Iterative deepening loop
582 while (Iteration < PLY_MAX)
584 // Initialize iteration
586 BestMoveChangesByIteration[Iteration] = 0;
588 cout << "info depth " << Iteration << endl;
590 // Calculate dynamic aspiration window based on previous iterations
591 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
593 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
594 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
596 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
597 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
599 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
600 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
603 // Search to the current depth, rml is updated and sorted, alpha and beta could change
604 value = root_search(pos, ss, pv, rml, &alpha, &beta);
606 // Write PV to transposition table, in case the relevant entries have
607 // been overwritten during the search.
608 insert_pv_in_tt(pos, pv);
611 break; // Value cannot be trusted. Break out immediately!
613 //Save info about search result
614 ValueByIteration[Iteration] = value;
616 // Drop the easy move if differs from the new best move
617 if (pv[0] != EasyMove)
618 EasyMove = MOVE_NONE;
620 if (UseTimeManagement)
623 bool stopSearch = false;
625 // Stop search early if there is only a single legal move,
626 // we search up to Iteration 6 anyway to get a proper score.
627 if (Iteration >= 6 && rml.size() == 1)
630 // Stop search early when the last two iterations returned a mate score
632 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
633 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
636 // Stop search early if one move seems to be much better than the others
639 && ( ( rml[0].nodes > (pos.nodes_searched() * 85) / 100
640 && current_search_time() > TimeMgr.available_time() / 16)
641 ||( rml[0].nodes > (pos.nodes_searched() * 98) / 100
642 && current_search_time() > TimeMgr.available_time() / 32)))
645 // Add some extra time if the best move has changed during the last two iterations
646 if (Iteration > 5 && Iteration <= 50)
647 TimeMgr.pv_instability(BestMoveChangesByIteration[Iteration],
648 BestMoveChangesByIteration[Iteration-1]);
650 // Stop search if most of MaxSearchTime is consumed at the end of the
651 // iteration. We probably don't have enough time to search the first
652 // move at the next iteration anyway.
653 if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
659 StopOnPonderhit = true;
665 if (MaxDepth && Iteration >= MaxDepth)
669 // If we are pondering or in infinite search, we shouldn't print the
670 // best move before we are told to do so.
671 if (!AbortSearch && (PonderSearch || InfiniteSearch))
672 wait_for_stop_or_ponderhit();
674 // Print final search statistics
675 cout << "info nodes " << pos.nodes_searched()
676 << " nps " << nps(pos)
677 << " time " << current_search_time() << endl;
679 // Print the best move and the ponder move to the standard output
680 if (pv[0] == MOVE_NONE || MultiPV > 1)
686 assert(pv[0] != MOVE_NONE);
688 cout << "bestmove " << pv[0];
690 if (pv[1] != MOVE_NONE)
691 cout << " ponder " << pv[1];
698 dbg_print_mean(LogFile);
700 if (dbg_show_hit_rate)
701 dbg_print_hit_rate(LogFile);
703 LogFile << "\nNodes: " << pos.nodes_searched()
704 << "\nNodes/second: " << nps(pos)
705 << "\nBest move: " << move_to_san(pos, pv[0]);
708 pos.do_move(pv[0], st);
709 LogFile << "\nPonder move: "
710 << move_to_san(pos, pv[1]) // Works also with MOVE_NONE
713 return rml[0].pv_score;
717 // root_search() is the function which searches the root node. It is
718 // similar to search_pv except that it uses a different move ordering
719 // scheme, prints some information to the standard output and handles
720 // the fail low/high loops.
722 Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
728 Depth depth, ext, newDepth;
729 Value value, alpha, beta;
730 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
731 int researchCountFH, researchCountFL;
733 researchCountFH = researchCountFL = 0;
736 isCheck = pos.is_check();
737 depth = (Iteration - 2) * ONE_PLY + InitialDepth;
739 // Step 1. Initialize node (polling is omitted at root)
740 ss->currentMove = ss->bestMove = MOVE_NONE;
742 // Step 2. Check for aborted search (omitted at root)
743 // Step 3. Mate distance pruning (omitted at root)
744 // Step 4. Transposition table lookup (omitted at root)
746 // Step 5. Evaluate the position statically
747 // At root we do this only to get reference value for child nodes
748 ss->evalMargin = VALUE_NONE;
749 ss->eval = isCheck ? VALUE_NONE : evaluate(pos, ss->evalMargin);
751 // Step 6. Razoring (omitted at root)
752 // Step 7. Static null move pruning (omitted at root)
753 // Step 8. Null move search with verification search (omitted at root)
754 // Step 9. Internal iterative deepening (omitted at root)
756 // Step extra. Fail low loop
757 // We start with small aspiration window and in case of fail low, we research
758 // with bigger window until we are not failing low anymore.
761 // Sort the moves before to (re)search
762 rml.set_non_pv_scores(pos);
765 // Step 10. Loop through all moves in the root move list
766 for (int i = 0; i < (int)rml.size() && !AbortSearch; i++)
768 // This is used by time management
769 FirstRootMove = (i == 0);
771 // Save the current node count before the move is searched
772 nodes = pos.nodes_searched();
774 // Pick the next root move, and print the move and the move number to
775 // the standard output.
776 move = ss->currentMove = rml[i].move;
778 if (current_search_time() >= 1000)
779 cout << "info currmove " << move
780 << " currmovenumber " << i + 1 << endl;
782 moveIsCheck = pos.move_is_check(move);
783 captureOrPromotion = pos.move_is_capture_or_promotion(move);
785 // Step 11. Decide the new search depth
786 ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
787 newDepth = depth + ext;
789 // Step 12. Futility pruning (omitted at root)
791 // Step extra. Fail high loop
792 // If move fails high, we research with bigger window until we are not failing
794 value = -VALUE_INFINITE;
798 // Step 13. Make the move
799 pos.do_move(move, st, ci, moveIsCheck);
801 // Step extra. pv search
802 // We do pv search for first moves (i < MultiPV)
803 // and for fail high research (value > alpha)
804 if (i < MultiPV || value > alpha)
806 // Aspiration window is disabled in multi-pv case
808 alpha = -VALUE_INFINITE;
810 // Full depth PV search, done on first move or after a fail high
811 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
815 // Step 14. Reduced search
816 // if the move fails high will be re-searched at full depth
817 bool doFullDepthSearch = true;
819 if ( depth >= 3 * ONE_PLY
821 && !captureOrPromotion
822 && !move_is_castle(move))
824 ss->reduction = reduction<PV>(depth, i - MultiPV + 2);
827 assert(newDepth-ss->reduction >= ONE_PLY);
829 // Reduced depth non-pv search using alpha as upperbound
830 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
831 doFullDepthSearch = (value > alpha);
833 ss->reduction = DEPTH_ZERO; // Restore original reduction
836 // Step 15. Full depth search
837 if (doFullDepthSearch)
839 // Full depth non-pv search using alpha as upperbound
840 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, 1);
842 // If we are above alpha then research at same depth but as PV
843 // to get a correct score or eventually a fail high above beta.
845 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
849 // Step 16. Undo move
852 // Can we exit fail high loop ?
853 if (AbortSearch || value < beta)
856 // We are failing high and going to do a research. It's important to update
857 // the score before research in case we run out of time while researching.
858 rml[i].pv_score = value;
860 extract_pv_from_tt(pos, move, pv);
863 // Print information to the standard output
864 print_pv_info(pos, pv, alpha, beta, value);
866 // Prepare for a research after a fail high, each time with a wider window
867 *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
870 } // End of fail high loop
872 // Finished searching the move. If AbortSearch is true, the search
873 // was aborted because the user interrupted the search or because we
874 // ran out of time. In this case, the return value of the search cannot
875 // be trusted, and we break out of the loop without updating the best
880 // Remember searched nodes counts for this move
881 rml[i].nodes += pos.nodes_searched() - nodes;
883 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
884 assert(value < beta);
886 // Step 17. Check for new best move
887 if (value <= alpha && i >= MultiPV)
888 rml[i].pv_score = -VALUE_INFINITE;
891 // PV move or new best move!
894 rml[i].pv_score = value;
896 extract_pv_from_tt(pos, move, pv);
901 // We record how often the best move has been changed in each
902 // iteration. This information is used for time managment: When
903 // the best move changes frequently, we allocate some more time.
905 BestMoveChangesByIteration[Iteration]++;
907 // Print information to the standard output
908 print_pv_info(pos, pv, alpha, beta, value);
910 // Raise alpha to setup proper non-pv search upper bound
917 for (int j = 0; j < Min(MultiPV, (int)rml.size()); j++)
919 cout << "info multipv " << j + 1
920 << " score " << value_to_uci(rml[j].pv_score)
921 << " depth " << (j <= i ? Iteration : Iteration - 1)
922 << " time " << current_search_time()
923 << " nodes " << pos.nodes_searched()
924 << " nps " << nps(pos)
927 for (int k = 0; rml[j].pv[k] != MOVE_NONE && k < PLY_MAX; k++)
928 cout << rml[j].pv[k] << " ";
932 alpha = rml[Min(i, MultiPV - 1)].pv_score;
934 } // PV move or new best move
936 assert(alpha >= *alphaPtr);
938 AspirationFailLow = (alpha == *alphaPtr);
940 if (AspirationFailLow && StopOnPonderhit)
941 StopOnPonderhit = false;
944 // Can we exit fail low loop ?
945 if (AbortSearch || !AspirationFailLow)
948 // Prepare for a research after a fail low, each time with a wider window
949 *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
954 // Sort the moves before to return
961 // search<>() is the main search function for both PV and non-PV nodes and for
962 // normal and SplitPoint nodes. When called just after a split point the search
963 // is simpler because we have already probed the hash table, done a null move
964 // search, and searched the first move before splitting, we don't have to repeat
965 // all this work again. We also don't need to store anything to the hash table
966 // here: This is taken care of after we return from the split point.
968 template <NodeType PvNode, bool SpNode>
969 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
971 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
972 assert(beta > alpha && beta <= VALUE_INFINITE);
973 assert(PvNode || alpha == beta - 1);
974 assert(ply > 0 && ply < PLY_MAX);
975 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
977 Move movesSearched[MOVES_MAX];
981 Move ttMove, move, excludedMove, threatMove;
984 Value bestValue, value, oldAlpha;
985 Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
986 bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
987 bool mateThreat = false;
989 int threadID = pos.thread();
990 SplitPoint* sp = NULL;
991 refinedValue = bestValue = value = -VALUE_INFINITE;
993 isCheck = pos.is_check();
999 ttMove = excludedMove = MOVE_NONE;
1000 threatMove = sp->threatMove;
1001 mateThreat = sp->mateThreat;
1002 goto split_point_start;
1004 else {} // Hack to fix icc's "statement is unreachable" warning
1006 // Step 1. Initialize node and poll. Polling can abort search
1007 ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
1008 (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
1010 if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
1016 // Step 2. Check for aborted search and immediate draw
1018 || ThreadsMgr.cutoff_at_splitpoint(threadID)
1020 || ply >= PLY_MAX - 1)
1023 // Step 3. Mate distance pruning
1024 alpha = Max(value_mated_in(ply), alpha);
1025 beta = Min(value_mate_in(ply+1), beta);
1029 // Step 4. Transposition table lookup
1031 // We don't want the score of a partial search to overwrite a previous full search
1032 // TT value, so we use a different position key in case of an excluded move exists.
1033 excludedMove = ss->excludedMove;
1034 posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1036 tte = TT.retrieve(posKey);
1037 ttMove = tte ? tte->move() : MOVE_NONE;
1039 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1040 // This is to avoid problems in the following areas:
1042 // * Repetition draw detection
1043 // * Fifty move rule detection
1044 // * Searching for a mate
1045 // * Printing of full PV line
1046 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1049 ss->bestMove = ttMove; // Can be MOVE_NONE
1050 return value_from_tt(tte->value(), ply);
1053 // Step 5. Evaluate the position statically and
1054 // update gain statistics of parent move.
1056 ss->eval = ss->evalMargin = VALUE_NONE;
1059 assert(tte->static_value() != VALUE_NONE);
1061 ss->eval = tte->static_value();
1062 ss->evalMargin = tte->static_value_margin();
1063 refinedValue = refine_eval(tte, ss->eval, ply);
1067 refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
1068 TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
1071 // Save gain for the parent non-capture move
1072 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1074 // Step 6. Razoring (is omitted in PV nodes)
1076 && depth < RazorDepth
1078 && refinedValue < beta - razor_margin(depth)
1079 && ttMove == MOVE_NONE
1080 && !value_is_mate(beta)
1081 && !pos.has_pawn_on_7th(pos.side_to_move()))
1083 Value rbeta = beta - razor_margin(depth);
1084 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply);
1086 // Logically we should return (v + razor_margin(depth)), but
1087 // surprisingly this did slightly weaker in tests.
1091 // Step 7. Static null move pruning (is omitted in PV nodes)
1092 // We're betting that the opponent doesn't have a move that will reduce
1093 // the score by more than futility_margin(depth) if we do a null move.
1095 && !ss->skipNullMove
1096 && depth < RazorDepth
1098 && refinedValue >= beta + futility_margin(depth, 0)
1099 && !value_is_mate(beta)
1100 && pos.non_pawn_material(pos.side_to_move()))
1101 return refinedValue - futility_margin(depth, 0);
1103 // Step 8. Null move search with verification search (is omitted in PV nodes)
1105 && !ss->skipNullMove
1108 && refinedValue >= beta
1109 && !value_is_mate(beta)
1110 && pos.non_pawn_material(pos.side_to_move()))
1112 ss->currentMove = MOVE_NULL;
1114 // Null move dynamic reduction based on depth
1115 int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
1117 // Null move dynamic reduction based on value
1118 if (refinedValue - beta > PawnValueMidgame)
1121 pos.do_null_move(st);
1122 (ss+1)->skipNullMove = true;
1123 nullValue = -search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1);
1124 (ss+1)->skipNullMove = false;
1125 pos.undo_null_move();
1127 if (nullValue >= beta)
1129 // Do not return unproven mate scores
1130 if (nullValue >= value_mate_in(PLY_MAX))
1133 if (depth < 6 * ONE_PLY)
1136 // Do verification search at high depths
1137 ss->skipNullMove = true;
1138 Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY, ply);
1139 ss->skipNullMove = false;
1146 // The null move failed low, which means that we may be faced with
1147 // some kind of threat. If the previous move was reduced, check if
1148 // the move that refuted the null move was somehow connected to the
1149 // move which was reduced. If a connection is found, return a fail
1150 // low score (which will cause the reduced move to fail high in the
1151 // parent node, which will trigger a re-search with full depth).
1152 if (nullValue == value_mated_in(ply + 2))
1155 threatMove = (ss+1)->bestMove;
1156 if ( depth < ThreatDepth
1157 && (ss-1)->reduction
1158 && threatMove != MOVE_NONE
1159 && connected_moves(pos, (ss-1)->currentMove, threatMove))
1164 // Step 9. Internal iterative deepening
1165 if ( depth >= IIDDepth[PvNode]
1166 && ttMove == MOVE_NONE
1167 && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
1169 Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
1171 ss->skipNullMove = true;
1172 search<PvNode>(pos, ss, alpha, beta, d, ply);
1173 ss->skipNullMove = false;
1175 ttMove = ss->bestMove;
1176 tte = TT.retrieve(posKey);
1179 // Expensive mate threat detection (only for PV nodes)
1181 mateThreat = pos.has_mate_threat();
1183 split_point_start: // At split points actual search starts from here
1185 // Initialize a MovePicker object for the current position
1186 // FIXME currently MovePicker() c'tor is needless called also in SplitPoint
1187 MovePicker mpBase(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
1188 MovePicker& mp = SpNode ? *sp->mp : mpBase;
1190 ss->bestMove = MOVE_NONE;
1191 singleEvasion = !SpNode && isCheck && mp.number_of_evasions() == 1;
1192 futilityBase = ss->eval + ss->evalMargin;
1193 singularExtensionNode = !SpNode
1194 && depth >= SingularExtensionDepth[PvNode]
1197 && !excludedMove // Do not allow recursive singular extension search
1198 && (tte->type() & VALUE_TYPE_LOWER)
1199 && tte->depth() >= depth - 3 * ONE_PLY;
1202 lock_grab(&(sp->lock));
1203 bestValue = sp->bestValue;
1206 // Step 10. Loop through moves
1207 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1208 while ( bestValue < beta
1209 && (move = mp.get_next_move()) != MOVE_NONE
1210 && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1212 assert(move_is_ok(move));
1216 moveCount = ++sp->moveCount;
1217 lock_release(&(sp->lock));
1219 else if (move == excludedMove)
1222 movesSearched[moveCount++] = move;
1224 moveIsCheck = pos.move_is_check(move, ci);
1225 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1227 // Step 11. Decide the new search depth
1228 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1230 // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s),
1231 // and just one fails high on (alpha, beta), then that move is singular and should be extended.
1232 // To verify this we do a reduced search on all the other moves but the ttMove, if result is
1233 // lower then ttValue minus a margin then we extend ttMove.
1234 if ( singularExtensionNode
1235 && move == tte->move()
1238 Value ttValue = value_from_tt(tte->value(), ply);
1240 if (abs(ttValue) < VALUE_KNOWN_WIN)
1242 Value b = ttValue - SingularExtensionMargin;
1243 ss->excludedMove = move;
1244 ss->skipNullMove = true;
1245 Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
1246 ss->skipNullMove = false;
1247 ss->excludedMove = MOVE_NONE;
1248 ss->bestMove = MOVE_NONE;
1254 // Update current move (this must be done after singular extension search)
1255 ss->currentMove = move;
1256 newDepth = depth - ONE_PLY + ext;
1258 // Step 12. Futility pruning (is omitted in PV nodes)
1260 && !captureOrPromotion
1264 && !move_is_castle(move))
1266 // Move count based pruning
1267 if ( moveCount >= futility_move_count(depth)
1268 && !(threatMove && connected_threat(pos, move, threatMove))
1269 && bestValue > value_mated_in(PLY_MAX)) // FIXME bestValue is racy
1272 lock_grab(&(sp->lock));
1277 // Value based pruning
1278 // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
1279 // but fixing this made program slightly weaker.
1280 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1281 futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount)
1282 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1284 if (futilityValueScaled < beta)
1288 lock_grab(&(sp->lock));
1289 if (futilityValueScaled > sp->bestValue)
1290 sp->bestValue = bestValue = futilityValueScaled;
1292 else if (futilityValueScaled > bestValue)
1293 bestValue = futilityValueScaled;
1298 // Prune moves with negative SEE at low depths
1299 if ( predictedDepth < 2 * ONE_PLY
1300 && bestValue > value_mated_in(PLY_MAX)
1301 && pos.see_sign(move) < 0)
1304 lock_grab(&(sp->lock));
1310 // Step 13. Make the move
1311 pos.do_move(move, st, ci, moveIsCheck);
1313 // Step extra. pv search (only in PV nodes)
1314 // The first move in list is the expected PV
1315 if (PvNode && moveCount == 1)
1316 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1319 // Step 14. Reduced depth search
1320 // If the move fails high will be re-searched at full depth.
1321 bool doFullDepthSearch = true;
1323 if ( depth >= 3 * ONE_PLY
1324 && !captureOrPromotion
1326 && !move_is_castle(move)
1327 && ss->killers[0] != move
1328 && ss->killers[1] != move)
1330 ss->reduction = reduction<PvNode>(depth, moveCount);
1334 alpha = SpNode ? sp->alpha : alpha;
1335 Depth d = newDepth - ss->reduction;
1336 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1338 doFullDepthSearch = (value > alpha);
1340 ss->reduction = DEPTH_ZERO; // Restore original reduction
1343 // Step 15. Full depth search
1344 if (doFullDepthSearch)
1346 alpha = SpNode ? sp->alpha : alpha;
1347 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1349 // Step extra. pv search (only in PV nodes)
1350 // Search only for possible new PV nodes, if instead value >= beta then
1351 // parent node fails low with value <= alpha and tries another move.
1352 if (PvNode && value > alpha && value < beta)
1353 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1357 // Step 16. Undo move
1358 pos.undo_move(move);
1360 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1362 // Step 17. Check for new best move
1365 lock_grab(&(sp->lock));
1366 bestValue = sp->bestValue;
1370 if (value > bestValue && !(SpNode && ThreadsMgr.cutoff_at_splitpoint(threadID)))
1375 sp->bestValue = value;
1379 if (PvNode && value < beta) // We want always alpha < beta
1387 sp->betaCutoff = true;
1389 if (value == value_mate_in(ply + 1))
1390 ss->mateKiller = move;
1392 ss->bestMove = move;
1395 sp->parentSstack->bestMove = move;
1399 // Step 18. Check for split
1401 && depth >= ThreadsMgr.min_split_depth()
1402 && ThreadsMgr.active_threads() > 1
1404 && ThreadsMgr.available_thread_exists(threadID)
1406 && !ThreadsMgr.cutoff_at_splitpoint(threadID)
1408 ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1409 threatMove, mateThreat, moveCount, &mp, PvNode);
1412 // Step 19. Check for mate and stalemate
1413 // All legal moves have been searched and if there are
1414 // no legal moves, it must be mate or stalemate.
1415 // If one move was excluded return fail low score.
1416 if (!SpNode && !moveCount)
1417 return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW;
1419 // Step 20. Update tables
1420 // If the search is not aborted, update the transposition table,
1421 // history counters, and killer moves.
1422 if (!SpNode && !AbortSearch && !ThreadsMgr.cutoff_at_splitpoint(threadID))
1424 move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
1425 vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
1426 : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
1428 TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, ss->evalMargin);
1430 // Update killers and history only for non capture moves that fails high
1431 if ( bestValue >= beta
1432 && !pos.move_is_capture_or_promotion(move))
1434 update_history(pos, move, depth, movesSearched, moveCount);
1435 update_killers(move, ss);
1441 // Here we have the lock still grabbed
1442 sp->slaves[threadID] = 0;
1443 sp->nodes += pos.nodes_searched();
1444 lock_release(&(sp->lock));
1447 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1452 // qsearch() is the quiescence search function, which is called by the main
1453 // search function when the remaining depth is zero (or, to be more precise,
1454 // less than ONE_PLY).
1456 template <NodeType PvNode>
1457 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1459 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1460 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1461 assert(PvNode || alpha == beta - 1);
1463 assert(ply > 0 && ply < PLY_MAX);
1464 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1468 Value bestValue, value, evalMargin, futilityValue, futilityBase;
1469 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1472 Value oldAlpha = alpha;
1474 ss->bestMove = ss->currentMove = MOVE_NONE;
1476 // Check for an instant draw or maximum ply reached
1477 if (pos.is_draw() || ply >= PLY_MAX - 1)
1480 // Decide whether or not to include checks, this fixes also the type of
1481 // TT entry depth that we are going to use. Note that in qsearch we use
1482 // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
1483 isCheck = pos.is_check();
1484 ttDepth = (isCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS);
1486 // Transposition table lookup. At PV nodes, we don't use the TT for
1487 // pruning, but only for move ordering.
1488 tte = TT.retrieve(pos.get_key());
1489 ttMove = (tte ? tte->move() : MOVE_NONE);
1491 if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ply))
1493 ss->bestMove = ttMove; // Can be MOVE_NONE
1494 return value_from_tt(tte->value(), ply);
1497 // Evaluate the position statically
1500 bestValue = futilityBase = -VALUE_INFINITE;
1501 ss->eval = evalMargin = VALUE_NONE;
1502 enoughMaterial = false;
1508 assert(tte->static_value() != VALUE_NONE);
1510 evalMargin = tte->static_value_margin();
1511 ss->eval = bestValue = tte->static_value();
1514 ss->eval = bestValue = evaluate(pos, evalMargin);
1516 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1518 // Stand pat. Return immediately if static value is at least beta
1519 if (bestValue >= beta)
1522 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1527 if (PvNode && bestValue > alpha)
1530 // Futility pruning parameters, not needed when in check
1531 futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1532 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1535 // Initialize a MovePicker object for the current position, and prepare
1536 // to search the moves. Because the depth is <= 0 here, only captures,
1537 // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
1539 MovePicker mp(pos, ttMove, depth, H);
1542 // Loop through the moves until no moves remain or a beta cutoff occurs
1543 while ( alpha < beta
1544 && (move = mp.get_next_move()) != MOVE_NONE)
1546 assert(move_is_ok(move));
1548 moveIsCheck = pos.move_is_check(move, ci);
1556 && !move_is_promotion(move)
1557 && !pos.move_is_passed_pawn_push(move))
1559 futilityValue = futilityBase
1560 + pos.endgame_value_of_piece_on(move_to(move))
1561 + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1563 if (futilityValue < alpha)
1565 if (futilityValue > bestValue)
1566 bestValue = futilityValue;
1571 // Detect non-capture evasions that are candidate to be pruned
1572 evasionPrunable = isCheck
1573 && bestValue > value_mated_in(PLY_MAX)
1574 && !pos.move_is_capture(move)
1575 && !pos.can_castle(pos.side_to_move());
1577 // Don't search moves with negative SEE values
1579 && (!isCheck || evasionPrunable)
1581 && !move_is_promotion(move)
1582 && pos.see_sign(move) < 0)
1585 // Don't search useless checks
1590 && !pos.move_is_capture_or_promotion(move)
1591 && ss->eval + PawnValueMidgame / 4 < beta
1592 && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue))
1594 if (ss->eval + PawnValueMidgame / 4 > bestValue)
1595 bestValue = ss->eval + PawnValueMidgame / 4;
1600 // Update current move
1601 ss->currentMove = move;
1603 // Make and search the move
1604 pos.do_move(move, st, ci, moveIsCheck);
1605 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1);
1606 pos.undo_move(move);
1608 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1611 if (value > bestValue)
1617 ss->bestMove = move;
1622 // All legal moves have been searched. A special case: If we're in check
1623 // and no legal moves were found, it is checkmate.
1624 if (isCheck && bestValue == -VALUE_INFINITE)
1625 return value_mated_in(ply);
1627 // Update transposition table
1628 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1629 TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin);
1631 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1637 // check_is_dangerous() tests if a checking move can be pruned in qsearch().
1638 // bestValue is updated only when returning false because in that case move
1641 bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bestValue)
1643 Bitboard b, occ, oldAtt, newAtt, kingAtt;
1644 Square from, to, ksq, victimSq;
1647 Value futilityValue, bv = *bestValue;
1649 from = move_from(move);
1651 them = opposite_color(pos.side_to_move());
1652 ksq = pos.king_square(them);
1653 kingAtt = pos.attacks_from<KING>(ksq);
1654 pc = pos.piece_on(from);
1656 occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL << ksq);
1657 oldAtt = pos.attacks_from(pc, from, occ);
1658 newAtt = pos.attacks_from(pc, to, occ);
1660 // Rule 1. Checks which give opponent's king at most one escape square are dangerous
1661 b = kingAtt & ~pos.pieces_of_color(them) & ~newAtt & ~(1ULL << to);
1663 if (!(b && (b & (b - 1))))
1666 // Rule 2. Queen contact check is very dangerous
1667 if ( type_of_piece(pc) == QUEEN
1668 && bit_is_set(kingAtt, to))
1671 // Rule 3. Creating new double threats with checks
1672 b = pos.pieces_of_color(them) & newAtt & ~oldAtt & ~(1ULL << ksq);
1676 victimSq = pop_1st_bit(&b);
1677 futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq);
1679 // Note that here we generate illegal "double move"!
1680 if ( futilityValue >= beta
1681 && pos.see_sign(make_move(from, victimSq)) >= 0)
1684 if (futilityValue > bv)
1688 // Update bestValue only if check is not dangerous (because we will prune the move)
1694 // connected_moves() tests whether two moves are 'connected' in the sense
1695 // that the first move somehow made the second move possible (for instance
1696 // if the moving piece is the same in both moves). The first move is assumed
1697 // to be the move that was made to reach the current position, while the
1698 // second move is assumed to be a move from the current position.
1700 bool connected_moves(const Position& pos, Move m1, Move m2) {
1702 Square f1, t1, f2, t2;
1705 assert(m1 && move_is_ok(m1));
1706 assert(m2 && move_is_ok(m2));
1708 // Case 1: The moving piece is the same in both moves
1714 // Case 2: The destination square for m2 was vacated by m1
1720 // Case 3: Moving through the vacated square
1721 if ( piece_is_slider(pos.piece_on(f2))
1722 && bit_is_set(squares_between(f2, t2), f1))
1725 // Case 4: The destination square for m2 is defended by the moving piece in m1
1726 p = pos.piece_on(t1);
1727 if (bit_is_set(pos.attacks_from(p, t1), t2))
1730 // Case 5: Discovered check, checking piece is the piece moved in m1
1731 if ( piece_is_slider(p)
1732 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1733 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1735 // discovered_check_candidates() works also if the Position's side to
1736 // move is the opposite of the checking piece.
1737 Color them = opposite_color(pos.side_to_move());
1738 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1740 if (bit_is_set(dcCandidates, f2))
1747 // value_is_mate() checks if the given value is a mate one eventually
1748 // compensated for the ply.
1750 bool value_is_mate(Value value) {
1752 assert(abs(value) <= VALUE_INFINITE);
1754 return value <= value_mated_in(PLY_MAX)
1755 || value >= value_mate_in(PLY_MAX);
1759 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1760 // "plies to mate from the current ply". Non-mate scores are unchanged.
1761 // The function is called before storing a value to the transposition table.
1763 Value value_to_tt(Value v, int ply) {
1765 if (v >= value_mate_in(PLY_MAX))
1768 if (v <= value_mated_in(PLY_MAX))
1775 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1776 // the transposition table to a mate score corrected for the current ply.
1778 Value value_from_tt(Value v, int ply) {
1780 if (v >= value_mate_in(PLY_MAX))
1783 if (v <= value_mated_in(PLY_MAX))
1790 // extension() decides whether a move should be searched with normal depth,
1791 // or with extended depth. Certain classes of moves (checking moves, in
1792 // particular) are searched with bigger depth than ordinary moves and in
1793 // any case are marked as 'dangerous'. Note that also if a move is not
1794 // extended, as example because the corresponding UCI option is set to zero,
1795 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1796 template <NodeType PvNode>
1797 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1798 bool singleEvasion, bool mateThreat, bool* dangerous) {
1800 assert(m != MOVE_NONE);
1802 Depth result = DEPTH_ZERO;
1803 *dangerous = moveIsCheck | singleEvasion | mateThreat;
1807 if (moveIsCheck && pos.see_sign(m) >= 0)
1808 result += CheckExtension[PvNode];
1811 result += SingleEvasionExtension[PvNode];
1814 result += MateThreatExtension[PvNode];
1817 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1819 Color c = pos.side_to_move();
1820 if (relative_rank(c, move_to(m)) == RANK_7)
1822 result += PawnPushTo7thExtension[PvNode];
1825 if (pos.pawn_is_passed(c, move_to(m)))
1827 result += PassedPawnExtension[PvNode];
1832 if ( captureOrPromotion
1833 && pos.type_of_piece_on(move_to(m)) != PAWN
1834 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1835 - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1836 && !move_is_promotion(m)
1839 result += PawnEndgameExtension[PvNode];
1844 && captureOrPromotion
1845 && pos.type_of_piece_on(move_to(m)) != PAWN
1846 && pos.see_sign(m) >= 0)
1848 result += ONE_PLY / 2;
1852 return Min(result, ONE_PLY);
1856 // connected_threat() tests whether it is safe to forward prune a move or if
1857 // is somehow coonected to the threat move returned by null search.
1859 bool connected_threat(const Position& pos, Move m, Move threat) {
1861 assert(move_is_ok(m));
1862 assert(threat && move_is_ok(threat));
1863 assert(!pos.move_is_check(m));
1864 assert(!pos.move_is_capture_or_promotion(m));
1865 assert(!pos.move_is_passed_pawn_push(m));
1867 Square mfrom, mto, tfrom, tto;
1869 mfrom = move_from(m);
1871 tfrom = move_from(threat);
1872 tto = move_to(threat);
1874 // Case 1: Don't prune moves which move the threatened piece
1878 // Case 2: If the threatened piece has value less than or equal to the
1879 // value of the threatening piece, don't prune move which defend it.
1880 if ( pos.move_is_capture(threat)
1881 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1882 || pos.type_of_piece_on(tfrom) == KING)
1883 && pos.move_attacks_square(m, tto))
1886 // Case 3: If the moving piece in the threatened move is a slider, don't
1887 // prune safe moves which block its ray.
1888 if ( piece_is_slider(pos.piece_on(tfrom))
1889 && bit_is_set(squares_between(tfrom, tto), mto)
1890 && pos.see_sign(m) >= 0)
1897 // ok_to_use_TT() returns true if a transposition table score
1898 // can be used at a given point in search.
1900 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1902 Value v = value_from_tt(tte->value(), ply);
1904 return ( tte->depth() >= depth
1905 || v >= Max(value_mate_in(PLY_MAX), beta)
1906 || v < Min(value_mated_in(PLY_MAX), beta))
1908 && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1909 || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1913 // refine_eval() returns the transposition table score if
1914 // possible otherwise falls back on static position evaluation.
1916 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1920 Value v = value_from_tt(tte->value(), ply);
1922 if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1923 || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1930 // update_history() registers a good move that produced a beta-cutoff
1931 // in history and marks as failures all the other moves of that ply.
1933 void update_history(const Position& pos, Move move, Depth depth,
1934 Move movesSearched[], int moveCount) {
1937 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
1939 for (int i = 0; i < moveCount - 1; i++)
1941 m = movesSearched[i];
1945 if (!pos.move_is_capture_or_promotion(m))
1946 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
1951 // update_killers() add a good move that produced a beta-cutoff
1952 // among the killer moves of that ply.
1954 void update_killers(Move m, SearchStack* ss) {
1956 if (m == ss->killers[0])
1959 ss->killers[1] = ss->killers[0];
1964 // update_gains() updates the gains table of a non-capture move given
1965 // the static position evaluation before and after the move.
1967 void update_gains(const Position& pos, Move m, Value before, Value after) {
1970 && before != VALUE_NONE
1971 && after != VALUE_NONE
1972 && pos.captured_piece_type() == PIECE_TYPE_NONE
1973 && !move_is_special(m))
1974 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
1978 // current_search_time() returns the number of milliseconds which have passed
1979 // since the beginning of the current search.
1981 int current_search_time() {
1983 return get_system_time() - SearchStartTime;
1987 // value_to_uci() converts a value to a string suitable for use with the UCI protocol
1989 std::string value_to_uci(Value v) {
1991 std::stringstream s;
1993 if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
1994 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100
1996 s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
2001 // nps() computes the current nodes/second count.
2003 int nps(const Position& pos) {
2005 int t = current_search_time();
2006 return (t > 0 ? int((pos.nodes_searched() * 1000) / t) : 0);
2010 // poll() performs two different functions: It polls for user input, and it
2011 // looks at the time consumed so far and decides if it's time to abort the
2014 void poll(const Position& pos) {
2016 static int lastInfoTime;
2017 int t = current_search_time();
2020 if (data_available())
2022 // We are line oriented, don't read single chars
2023 std::string command;
2025 if (!std::getline(std::cin, command))
2028 if (command == "quit")
2031 PonderSearch = false;
2035 else if (command == "stop")
2038 PonderSearch = false;
2040 else if (command == "ponderhit")
2044 // Print search information
2048 else if (lastInfoTime > t)
2049 // HACK: Must be a new search where we searched less than
2050 // NodesBetweenPolls nodes during the first second of search.
2053 else if (t - lastInfoTime >= 1000)
2060 if (dbg_show_hit_rate)
2061 dbg_print_hit_rate();
2063 cout << "info nodes " << pos.nodes_searched() << " nps " << nps(pos)
2064 << " time " << t << endl;
2067 // Should we stop the search?
2071 bool stillAtFirstMove = FirstRootMove
2072 && !AspirationFailLow
2073 && t > TimeMgr.available_time();
2075 bool noMoreTime = t > TimeMgr.maximum_time()
2076 || stillAtFirstMove;
2078 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2079 || (ExactMaxTime && t >= ExactMaxTime)
2080 || (Iteration >= 3 && MaxNodes && pos.nodes_searched() >= MaxNodes))
2085 // ponderhit() is called when the program is pondering (i.e. thinking while
2086 // it's the opponent's turn to move) in order to let the engine know that
2087 // it correctly predicted the opponent's move.
2091 int t = current_search_time();
2092 PonderSearch = false;
2094 bool stillAtFirstMove = FirstRootMove
2095 && !AspirationFailLow
2096 && t > TimeMgr.available_time();
2098 bool noMoreTime = t > TimeMgr.maximum_time()
2099 || stillAtFirstMove;
2101 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2106 // init_ss_array() does a fast reset of the first entries of a SearchStack
2107 // array and of all the excludedMove and skipNullMove entries.
2109 void init_ss_array(SearchStack* ss, int size) {
2111 for (int i = 0; i < size; i++, ss++)
2113 ss->excludedMove = MOVE_NONE;
2114 ss->skipNullMove = false;
2115 ss->reduction = DEPTH_ZERO;
2119 ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE;
2124 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2125 // while the program is pondering. The point is to work around a wrinkle in
2126 // the UCI protocol: When pondering, the engine is not allowed to give a
2127 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2128 // We simply wait here until one of these commands is sent, and return,
2129 // after which the bestmove and pondermove will be printed (in id_loop()).
2131 void wait_for_stop_or_ponderhit() {
2133 std::string command;
2137 if (!std::getline(std::cin, command))
2140 if (command == "quit")
2145 else if (command == "ponderhit" || command == "stop")
2151 // print_pv_info() prints to standard output and eventually to log file information on
2152 // the current PV line. It is called at each iteration or after a new pv is found.
2154 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) {
2156 cout << "info depth " << Iteration
2157 << " score " << value_to_uci(value)
2158 << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
2159 << " time " << current_search_time()
2160 << " nodes " << pos.nodes_searched()
2161 << " nps " << nps(pos)
2164 for (Move* m = pv; *m != MOVE_NONE; m++)
2171 ValueType t = value >= beta ? VALUE_TYPE_LOWER :
2172 value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
2174 LogFile << pretty_pv(pos, current_search_time(), Iteration, value, t, pv) << endl;
2179 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2180 // the PV back into the TT. This makes sure the old PV moves are searched
2181 // first, even if the old TT entries have been overwritten.
2183 void insert_pv_in_tt(const Position& pos, Move pv[]) {
2187 Position p(pos, pos.thread());
2188 Value v, m = VALUE_NONE;
2190 for (int i = 0; pv[i] != MOVE_NONE; i++)
2192 tte = TT.retrieve(p.get_key());
2193 if (!tte || tte->move() != pv[i])
2195 v = (p.is_check() ? VALUE_NONE : evaluate(p, m));
2196 TT.store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[i], v, m);
2198 p.do_move(pv[i], st);
2203 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2204 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2205 // allow to always have a ponder move even when we fail high at root and also a
2206 // long PV to print that is important for position analysis.
2208 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]) {
2212 Position p(pos, pos.thread());
2215 assert(bestMove != MOVE_NONE);
2218 p.do_move(pv[ply++], st);
2220 while ( (tte = TT.retrieve(p.get_key())) != NULL
2221 && tte->move() != MOVE_NONE
2222 && move_is_legal(p, tte->move())
2224 && (!p.is_draw() || ply < 2))
2226 pv[ply] = tte->move();
2227 p.do_move(pv[ply++], st);
2229 pv[ply] = MOVE_NONE;
2233 // init_thread() is the function which is called when a new thread is
2234 // launched. It simply calls the idle_loop() function with the supplied
2235 // threadID. There are two versions of this function; one for POSIX
2236 // threads and one for Windows threads.
2238 #if !defined(_MSC_VER)
2240 void* init_thread(void* threadID) {
2242 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2248 DWORD WINAPI init_thread(LPVOID threadID) {
2250 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2257 /// The ThreadsManager class
2260 // read_uci_options() updates number of active threads and other internal
2261 // parameters according to the UCI options values. It is called before
2262 // to start a new search.
2264 void ThreadsManager::read_uci_options() {
2266 maxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value<int>();
2267 minimumSplitDepth = Options["Minimum Split Depth"].value<int>() * ONE_PLY;
2268 useSleepingThreads = Options["Use Sleeping Threads"].value<bool>();
2269 activeThreads = Options["Threads"].value<int>();
2273 // idle_loop() is where the threads are parked when they have no work to do.
2274 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2275 // object for which the current thread is the master.
2277 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2279 assert(threadID >= 0 && threadID < MAX_THREADS);
2282 bool allFinished = false;
2286 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2287 // master should exit as last one.
2288 if (allThreadsShouldExit)
2291 threads[threadID].state = THREAD_TERMINATED;
2295 // If we are not thinking, wait for a condition to be signaled
2296 // instead of wasting CPU time polling for work.
2297 while ( threadID >= activeThreads || threads[threadID].state == THREAD_INITIALIZING
2298 || (useSleepingThreads && threads[threadID].state == THREAD_AVAILABLE))
2300 assert(!sp || useSleepingThreads);
2301 assert(threadID != 0 || useSleepingThreads);
2303 if (threads[threadID].state == THREAD_INITIALIZING)
2304 threads[threadID].state = THREAD_AVAILABLE;
2306 // Grab the lock to avoid races with wake_sleeping_thread()
2307 lock_grab(&sleepLock[threadID]);
2309 // If we are master and all slaves have finished do not go to sleep
2310 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2311 allFinished = (i == activeThreads);
2313 if (allFinished || allThreadsShouldExit)
2315 lock_release(&sleepLock[threadID]);
2319 // Do sleep here after retesting sleep conditions
2320 if (threadID >= activeThreads || threads[threadID].state == THREAD_AVAILABLE)
2321 cond_wait(&sleepCond[threadID], &sleepLock[threadID]);
2323 lock_release(&sleepLock[threadID]);
2326 // If this thread has been assigned work, launch a search
2327 if (threads[threadID].state == THREAD_WORKISWAITING)
2329 assert(!allThreadsShouldExit);
2331 threads[threadID].state = THREAD_SEARCHING;
2333 // Here we call search() with SplitPoint template parameter set to true
2334 SplitPoint* tsp = threads[threadID].splitPoint;
2335 Position pos(*tsp->pos, threadID);
2336 SearchStack* ss = tsp->sstack[threadID] + 1;
2340 search<PV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2342 search<NonPV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2344 assert(threads[threadID].state == THREAD_SEARCHING);
2346 threads[threadID].state = THREAD_AVAILABLE;
2348 // Wake up master thread so to allow it to return from the idle loop in
2349 // case we are the last slave of the split point.
2350 if (useSleepingThreads && threadID != tsp->master && threads[tsp->master].state == THREAD_AVAILABLE)
2351 wake_sleeping_thread(tsp->master);
2354 // If this thread is the master of a split point and all slaves have
2355 // finished their work at this split point, return from the idle loop.
2356 for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {}
2357 allFinished = (i == activeThreads);
2361 // Because sp->slaves[] is reset under lock protection,
2362 // be sure sp->lock has been released before to return.
2363 lock_grab(&(sp->lock));
2364 lock_release(&(sp->lock));
2366 // In helpful master concept a master can help only a sub-tree, and
2367 // because here is all finished is not possible master is booked.
2368 assert(threads[threadID].state == THREAD_AVAILABLE);
2370 threads[threadID].state = THREAD_SEARCHING;
2377 // init_threads() is called during startup. It launches all helper threads,
2378 // and initializes the split point stack and the global locks and condition
2381 void ThreadsManager::init_threads() {
2383 int i, arg[MAX_THREADS];
2386 // Initialize global locks
2389 for (i = 0; i < MAX_THREADS; i++)
2391 lock_init(&sleepLock[i]);
2392 cond_init(&sleepCond[i]);
2395 // Initialize splitPoints[] locks
2396 for (i = 0; i < MAX_THREADS; i++)
2397 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2398 lock_init(&(threads[i].splitPoints[j].lock));
2400 // Will be set just before program exits to properly end the threads
2401 allThreadsShouldExit = false;
2403 // Threads will be put all threads to sleep as soon as created
2406 // All threads except the main thread should be initialized to THREAD_INITIALIZING
2407 threads[0].state = THREAD_SEARCHING;
2408 for (i = 1; i < MAX_THREADS; i++)
2409 threads[i].state = THREAD_INITIALIZING;
2411 // Launch the helper threads
2412 for (i = 1; i < MAX_THREADS; i++)
2416 #if !defined(_MSC_VER)
2417 pthread_t pthread[1];
2418 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
2419 pthread_detach(pthread[0]);
2421 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
2425 cout << "Failed to create thread number " << i << endl;
2429 // Wait until the thread has finished launching and is gone to sleep
2430 while (threads[i].state == THREAD_INITIALIZING) {}
2435 // exit_threads() is called when the program exits. It makes all the
2436 // helper threads exit cleanly.
2438 void ThreadsManager::exit_threads() {
2440 allThreadsShouldExit = true; // Let the woken up threads to exit idle_loop()
2442 // Wake up all the threads and waits for termination
2443 for (int i = 1; i < MAX_THREADS; i++)
2445 wake_sleeping_thread(i);
2446 while (threads[i].state != THREAD_TERMINATED) {}
2449 // Now we can safely destroy the locks
2450 for (int i = 0; i < MAX_THREADS; i++)
2451 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2452 lock_destroy(&(threads[i].splitPoints[j].lock));
2454 lock_destroy(&mpLock);
2456 // Now we can safely destroy the wait conditions
2457 for (int i = 0; i < MAX_THREADS; i++)
2459 lock_destroy(&sleepLock[i]);
2460 cond_destroy(&sleepCond[i]);
2465 // cutoff_at_splitpoint() checks whether a beta cutoff has occurred in
2466 // the thread's currently active split point, or in some ancestor of
2467 // the current split point.
2469 bool ThreadsManager::cutoff_at_splitpoint(int threadID) const {
2471 assert(threadID >= 0 && threadID < activeThreads);
2473 SplitPoint* sp = threads[threadID].splitPoint;
2475 for ( ; sp && !sp->betaCutoff; sp = sp->parent) {}
2480 // thread_is_available() checks whether the thread with threadID "slave" is
2481 // available to help the thread with threadID "master" at a split point. An
2482 // obvious requirement is that "slave" must be idle. With more than two
2483 // threads, this is not by itself sufficient: If "slave" is the master of
2484 // some active split point, it is only available as a slave to the other
2485 // threads which are busy searching the split point at the top of "slave"'s
2486 // split point stack (the "helpful master concept" in YBWC terminology).
2488 bool ThreadsManager::thread_is_available(int slave, int master) const {
2490 assert(slave >= 0 && slave < activeThreads);
2491 assert(master >= 0 && master < activeThreads);
2492 assert(activeThreads > 1);
2494 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2497 // Make a local copy to be sure doesn't change under our feet
2498 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2500 // No active split points means that the thread is available as
2501 // a slave for any other thread.
2502 if (localActiveSplitPoints == 0 || activeThreads == 2)
2505 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2506 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2507 // could have been set to 0 by another thread leading to an out of bound access.
2508 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2515 // available_thread_exists() tries to find an idle thread which is available as
2516 // a slave for the thread with threadID "master".
2518 bool ThreadsManager::available_thread_exists(int master) const {
2520 assert(master >= 0 && master < activeThreads);
2521 assert(activeThreads > 1);
2523 for (int i = 0; i < activeThreads; i++)
2524 if (thread_is_available(i, master))
2531 // split() does the actual work of distributing the work at a node between
2532 // several available threads. If it does not succeed in splitting the
2533 // node (because no idle threads are available, or because we have no unused
2534 // split point objects), the function immediately returns. If splitting is
2535 // possible, a SplitPoint object is initialized with all the data that must be
2536 // copied to the helper threads and we tell our helper threads that they have
2537 // been assigned work. This will cause them to instantly leave their idle loops and
2538 // call search().When all threads have returned from search() then split() returns.
2540 template <bool Fake>
2541 void ThreadsManager::split(Position& pos, SearchStack* ss, int ply, Value* alpha,
2542 const Value beta, Value* bestValue, Depth depth, Move threatMove,
2543 bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) {
2544 assert(pos.is_ok());
2545 assert(ply > 0 && ply < PLY_MAX);
2546 assert(*bestValue >= -VALUE_INFINITE);
2547 assert(*bestValue <= *alpha);
2548 assert(*alpha < beta);
2549 assert(beta <= VALUE_INFINITE);
2550 assert(depth > DEPTH_ZERO);
2551 assert(pos.thread() >= 0 && pos.thread() < activeThreads);
2552 assert(activeThreads > 1);
2554 int i, master = pos.thread();
2555 Thread& masterThread = threads[master];
2559 // If no other thread is available to help us, or if we have too many
2560 // active split points, don't split.
2561 if ( !available_thread_exists(master)
2562 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2564 lock_release(&mpLock);
2568 // Pick the next available split point object from the split point stack
2569 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2571 // Initialize the split point object
2572 splitPoint.parent = masterThread.splitPoint;
2573 splitPoint.master = master;
2574 splitPoint.betaCutoff = false;
2575 splitPoint.ply = ply;
2576 splitPoint.depth = depth;
2577 splitPoint.threatMove = threatMove;
2578 splitPoint.mateThreat = mateThreat;
2579 splitPoint.alpha = *alpha;
2580 splitPoint.beta = beta;
2581 splitPoint.pvNode = pvNode;
2582 splitPoint.bestValue = *bestValue;
2584 splitPoint.moveCount = moveCount;
2585 splitPoint.pos = &pos;
2586 splitPoint.nodes = 0;
2587 splitPoint.parentSstack = ss;
2588 for (i = 0; i < activeThreads; i++)
2589 splitPoint.slaves[i] = 0;
2591 masterThread.splitPoint = &splitPoint;
2593 // If we are here it means we are not available
2594 assert(masterThread.state != THREAD_AVAILABLE);
2596 int workersCnt = 1; // At least the master is included
2598 // Allocate available threads setting state to THREAD_BOOKED
2599 for (i = 0; !Fake && i < activeThreads && workersCnt < maxThreadsPerSplitPoint; i++)
2600 if (thread_is_available(i, master))
2602 threads[i].state = THREAD_BOOKED;
2603 threads[i].splitPoint = &splitPoint;
2604 splitPoint.slaves[i] = 1;
2608 assert(Fake || workersCnt > 1);
2610 // We can release the lock because slave threads are already booked and master is not available
2611 lock_release(&mpLock);
2613 // Tell the threads that they have work to do. This will make them leave
2614 // their idle loop. But before copy search stack tail for each thread.
2615 for (i = 0; i < activeThreads; i++)
2616 if (i == master || splitPoint.slaves[i])
2618 memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
2620 assert(i == master || threads[i].state == THREAD_BOOKED);
2622 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2624 if (useSleepingThreads && i != master)
2625 wake_sleeping_thread(i);
2628 // Everything is set up. The master thread enters the idle loop, from
2629 // which it will instantly launch a search, because its state is
2630 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2631 // idle loop, which means that the main thread will return from the idle
2632 // loop when all threads have finished their work at this split point.
2633 idle_loop(master, &splitPoint);
2635 // We have returned from the idle loop, which means that all threads are
2636 // finished. Update alpha and bestValue, and return.
2639 *alpha = splitPoint.alpha;
2640 *bestValue = splitPoint.bestValue;
2641 masterThread.activeSplitPoints--;
2642 masterThread.splitPoint = splitPoint.parent;
2643 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
2645 lock_release(&mpLock);
2649 // wake_sleeping_thread() wakes up the thread with the given threadID
2650 // when it is time to start a new search.
2652 void ThreadsManager::wake_sleeping_thread(int threadID) {
2654 lock_grab(&sleepLock[threadID]);
2655 cond_signal(&sleepCond[threadID]);
2656 lock_release(&sleepLock[threadID]);
2660 /// The RootMoveList class
2662 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) {
2664 SearchStack ss[PLY_MAX_PLUS_2];
2665 MoveStack mlist[MOVES_MAX];
2669 // Initialize search stack
2670 init_ss_array(ss, PLY_MAX_PLUS_2);
2671 ss[0].eval = ss[0].evalMargin = VALUE_NONE;
2673 // Generate all legal moves
2674 MoveStack* last = generate_moves(pos, mlist);
2676 // Add each move to the RootMoveList's vector
2677 for (MoveStack* cur = mlist; cur != last; cur++)
2679 // If we have a searchMoves[] list then verify cur->move
2680 // is in the list before to add it.
2681 for (sm = searchMoves; *sm && *sm != cur->move; sm++) {}
2683 if (searchMoves[0] && *sm != cur->move)
2686 // Find a quick score for the move and add to the list
2687 pos.do_move(cur->move, st);
2690 rm.move = ss[0].currentMove = rm.pv[0] = cur->move;
2691 rm.pv[1] = MOVE_NONE;
2692 rm.pv_score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
2695 pos.undo_move(cur->move);
2700 // Score root moves using the standard way used in main search, the moves
2701 // are scored according to the order in which are returned by MovePicker.
2702 // This is the second order score that is used to compare the moves when
2703 // the first order pv scores of both moves are equal.
2705 void RootMoveList::set_non_pv_scores(const Position& pos)
2708 Value score = VALUE_ZERO;
2709 MovePicker mp(pos, MOVE_NONE, ONE_PLY, H);
2711 while ((move = mp.get_next_move()) != MOVE_NONE)
2712 for (Base::iterator it = begin(); it != end(); ++it)
2713 if (it->move == move)
2715 it->non_pv_score = score--;