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/>.
44 #include "ucioption.h"
50 //// Local definitions
56 enum NodeType { NonPV, PV };
58 // Set to true to force running with one thread.
59 // Used for debugging SMP code.
60 const bool FakeSplit = false;
62 // Fast lookup table of sliding pieces indexed by Piece
63 const bool Slidings[18] = { 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1 };
64 inline bool piece_is_slider(Piece p) { return Slidings[p]; }
66 // ThreadsManager class is used to handle all the threads related stuff in search,
67 // init, starting, parking and, the most important, launching a slave thread at a
68 // split point are what this class does. All the access to shared thread data is
69 // done through this class, so that we avoid using global variables instead.
71 class ThreadsManager {
72 /* As long as the single ThreadsManager object is defined as a global we don't
73 need to explicitly initialize to zero its data members because variables with
74 static storage duration are automatically set to zero before enter main()
80 int active_threads() const { return ActiveThreads; }
81 void set_active_threads(int newActiveThreads) { ActiveThreads = newActiveThreads; }
83 bool available_thread_exists(int master) const;
84 bool thread_is_available(int slave, int master) const;
85 bool thread_should_stop(int threadID) const;
86 void wake_sleeping_thread(int threadID);
87 void idle_loop(int threadID, SplitPoint* sp);
90 void split(Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
91 Depth depth, Move threatMove, bool mateThreat, int moveCount, MovePicker* mp, bool pvNode);
95 volatile bool AllThreadsShouldExit;
96 Thread threads[MAX_THREADS];
97 Lock MPLock, WaitLock;
98 WaitCondition WaitCond[MAX_THREADS];
102 // RootMove struct is used for moves at the root at the tree. For each
103 // root move, we store a score, a node count, and a PV (really a refutation
104 // in the case of moves which fail low).
108 RootMove() : mp_score(0), nodes(0) {}
110 // RootMove::operator<() is the comparison function used when
111 // sorting the moves. A move m1 is considered to be better
112 // than a move m2 if it has a higher score, or if the moves
113 // have equal score but m1 has the higher beta cut-off count.
114 bool operator<(const RootMove& m) const {
116 return score != m.score ? score < m.score : mp_score <= m.mp_score;
123 Move pv[PLY_MAX_PLUS_2];
127 // The RootMoveList class is essentially an array of RootMove objects, with
128 // a handful of methods for accessing the data in the individual moves.
133 RootMoveList(Position& pos, Move searchMoves[]);
135 Move move(int moveNum) const { return moves[moveNum].move; }
136 Move move_pv(int moveNum, int i) const { return moves[moveNum].pv[i]; }
137 int move_count() const { return count; }
138 Value move_score(int moveNum) const { return moves[moveNum].score; }
139 int64_t move_nodes(int moveNum) const { return moves[moveNum].nodes; }
140 void add_move_nodes(int moveNum, int64_t nodes) { moves[moveNum].nodes += nodes; }
141 void set_move_score(int moveNum, Value score) { moves[moveNum].score = score; }
143 void set_move_pv(int moveNum, const Move pv[]);
144 void score_moves(const Position& pos);
146 void sort_multipv(int n);
149 RootMove moves[MOVES_MAX];
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 use it to properly format castling moves.
162 std::ostream& operator<< (std::ostream& os, const set960& m) {
164 os.iword(0) = int(m);
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], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
196 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
198 // Minimum depth for use of singular extension
199 const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */};
201 // If the TT move is at least SingularExtensionMargin better then the
202 // remaining ones we will extend it.
203 const Value SingularExtensionMargin = Value(0x20);
205 // Step 12. Futility pruning
207 // Futility margin for quiescence search
208 const Value FutilityMarginQS = Value(0x80);
210 // Futility lookup tables (initialized at startup) and their getter functions
211 Value FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
212 int FutilityMoveCountArray[32]; // [depth]
214 inline Value futility_margin(Depth d, int mn) { return d < 7 * ONE_PLY ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE; }
215 inline int futility_move_count(Depth d) { return d < 16 * ONE_PLY ? FutilityMoveCountArray[d] : 512; }
217 // Step 14. Reduced search
219 // Reduction lookup tables (initialized at startup) and their getter functions
220 int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
222 template <NodeType PV>
223 inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
225 // Common adjustments
227 // Search depth at iteration 1
228 const Depth InitialDepth = ONE_PLY;
230 // Easy move margin. An easy move candidate must be at least this much
231 // better than the second best move.
232 const Value EasyMoveMargin = Value(0x200);
235 /// Namespace variables
243 // Scores and number of times the best move changed for each iteration
244 Value ValueByIteration[PLY_MAX_PLUS_2];
245 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
247 // Search window management
253 // Time managment variables
254 int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
255 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
256 bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
261 std::ofstream LogFile;
263 // Multi-threads related variables
264 Depth MinimumSplitDepth;
265 int MaxThreadsPerSplitPoint;
266 ThreadsManager ThreadsMgr;
268 // Node counters, used only by thread[0] but try to keep in different cache
269 // lines (64 bytes each) from the heavy multi-thread read accessed variables.
271 int NodesBetweenPolls = 30000;
278 Value id_loop(Position& pos, Move searchMoves[]);
279 Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
281 template <NodeType PvNode, bool SpNode>
282 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
284 template <NodeType PvNode>
285 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
287 template <NodeType PvNode>
288 inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
290 return depth < ONE_PLY ? qsearch<PvNode>(pos, ss, alpha, beta, DEPTH_ZERO, ply)
291 : search<PvNode, false>(pos, ss, alpha, beta, depth, ply);
294 template <NodeType PvNode>
295 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
297 bool connected_moves(const Position& pos, Move m1, Move m2);
298 bool value_is_mate(Value value);
299 Value value_to_tt(Value v, int ply);
300 Value value_from_tt(Value v, int ply);
301 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
302 bool connected_threat(const Position& pos, Move m, Move threat);
303 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
304 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
305 void update_killers(Move m, SearchStack* ss);
306 void update_gains(const Position& pos, Move move, Value before, Value after);
308 int current_search_time();
309 std::string value_to_uci(Value v);
310 int nps(const Position& pos);
311 void poll(const Position& pos);
313 void wait_for_stop_or_ponderhit();
314 void init_ss_array(SearchStack* ss, int size);
315 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value);
316 void insert_pv_in_tt(const Position& pos, Move pv[]);
317 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]);
319 #if !defined(_MSC_VER)
320 void* init_thread(void* threadID);
322 DWORD WINAPI init_thread(LPVOID threadID);
332 /// init_threads(), exit_threads() and nodes_searched() are helpers to
333 /// give accessibility to some TM methods from outside of current file.
335 void init_threads() { ThreadsMgr.init_threads(); }
336 void exit_threads() { ThreadsMgr.exit_threads(); }
339 /// init_search() is called during startup. It initializes various lookup tables
343 int d; // depth (ONE_PLY == 2)
344 int hd; // half depth (ONE_PLY == 1)
347 // Init reductions array
348 for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
350 double pvRed = log(double(hd)) * log(double(mc)) / 3.0;
351 double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
352 ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0);
353 ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0);
356 // Init futility margins array
357 for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
358 FutilityMarginsMatrix[d][mc] = Value(112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45);
360 // Init futility move count array
361 for (d = 0; d < 32; d++)
362 FutilityMoveCountArray[d] = int(3.001 + 0.25 * pow(d, 2.0));
366 /// perft() is our utility to verify move generation is bug free. All the legal
367 /// moves up to given depth are generated and counted and the sum returned.
369 int perft(Position& pos, Depth depth)
371 MoveStack mlist[MOVES_MAX];
376 // Generate all legal moves
377 MoveStack* last = generate_moves(pos, mlist);
379 // If we are at the last ply we don't need to do and undo
380 // the moves, just to count them.
381 if (depth <= ONE_PLY)
382 return int(last - mlist);
384 // Loop through all legal moves
386 for (MoveStack* cur = mlist; cur != last; cur++)
389 pos.do_move(m, st, ci, pos.move_is_check(m, ci));
390 sum += perft(pos, depth - ONE_PLY);
397 /// think() is the external interface to Stockfish's search, and is called when
398 /// the program receives the UCI 'go' command. It initializes various
399 /// search-related global variables, and calls root_search(). It returns false
400 /// when a quit command is received during the search.
402 bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[],
403 int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) {
405 // Initialize global search variables
406 StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
408 SearchStartTime = get_system_time();
409 ExactMaxTime = maxTime;
412 InfiniteSearch = infinite;
413 PonderSearch = ponder;
414 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
416 // Look for a book move, only during games, not tests
417 if (UseTimeManagement && Options["OwnBook"].value<bool>())
419 if (Options["Book File"].value<std::string>() != OpeningBook.file_name())
420 OpeningBook.open(Options["Book File"].value<std::string>());
422 Move bookMove = OpeningBook.get_move(pos, Options["Best Book Move"].value<bool>());
423 if (bookMove != MOVE_NONE)
426 wait_for_stop_or_ponderhit();
428 cout << "bestmove " << bookMove << endl;
433 // Read UCI option values
434 TT.set_size(Options["Hash"].value<int>());
435 if (Options["Clear Hash"].value<bool>())
437 Options["Clear Hash"].set_value("false");
441 CheckExtension[1] = Options["Check Extension (PV nodes)"].value<Depth>();
442 CheckExtension[0] = Options["Check Extension (non-PV nodes)"].value<Depth>();
443 SingleEvasionExtension[1] = Options["Single Evasion Extension (PV nodes)"].value<Depth>();
444 SingleEvasionExtension[0] = Options["Single Evasion Extension (non-PV nodes)"].value<Depth>();
445 PawnPushTo7thExtension[1] = Options["Pawn Push to 7th Extension (PV nodes)"].value<Depth>();
446 PawnPushTo7thExtension[0] = Options["Pawn Push to 7th Extension (non-PV nodes)"].value<Depth>();
447 PassedPawnExtension[1] = Options["Passed Pawn Extension (PV nodes)"].value<Depth>();
448 PassedPawnExtension[0] = Options["Passed Pawn Extension (non-PV nodes)"].value<Depth>();
449 PawnEndgameExtension[1] = Options["Pawn Endgame Extension (PV nodes)"].value<Depth>();
450 PawnEndgameExtension[0] = Options["Pawn Endgame Extension (non-PV nodes)"].value<Depth>();
451 MateThreatExtension[1] = Options["Mate Threat Extension (PV nodes)"].value<Depth>();
452 MateThreatExtension[0] = Options["Mate Threat Extension (non-PV nodes)"].value<Depth>();
454 MinimumSplitDepth = Options["Minimum Split Depth"].value<int>() * ONE_PLY;
455 MaxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value<int>();
456 MultiPV = Options["MultiPV"].value<int>();
457 UseLogFile = Options["Use Search Log"].value<bool>();
460 LogFile.open(Options["Search Log Filename"].value<std::string>().c_str(), std::ios::out | std::ios::app);
462 read_weights(pos.side_to_move());
464 // Set the number of active threads
465 int newActiveThreads = Options["Threads"].value<int>();
466 if (newActiveThreads != ThreadsMgr.active_threads())
468 ThreadsMgr.set_active_threads(newActiveThreads);
469 init_eval(ThreadsMgr.active_threads());
472 // Wake up needed threads
473 for (int i = 1; i < newActiveThreads; i++)
474 ThreadsMgr.wake_sleeping_thread(i);
477 int myTime = time[pos.side_to_move()];
478 int myIncrement = increment[pos.side_to_move()];
479 if (UseTimeManagement)
480 TimeMgr.init(myTime, myIncrement, movesToGo, pos.startpos_ply_counter());
482 // Set best NodesBetweenPolls interval to avoid lagging under
483 // heavy time pressure.
485 NodesBetweenPolls = Min(MaxNodes, 30000);
486 else if (myTime && myTime < 1000)
487 NodesBetweenPolls = 1000;
488 else if (myTime && myTime < 5000)
489 NodesBetweenPolls = 5000;
491 NodesBetweenPolls = 30000;
493 // Write search information to log file
495 LogFile << "Searching: " << pos.to_fen() << endl
496 << "infinite: " << infinite
497 << " ponder: " << ponder
498 << " time: " << myTime
499 << " increment: " << myIncrement
500 << " moves to go: " << movesToGo << endl;
502 // We're ready to start thinking. Call the iterative deepening loop function
503 id_loop(pos, searchMoves);
508 // This makes all the threads to go to sleep
509 ThreadsMgr.set_active_threads(1);
517 // id_loop() is the main iterative deepening loop. It calls root_search
518 // repeatedly with increasing depth until the allocated thinking time has
519 // been consumed, the user stops the search, or the maximum search depth is
522 Value id_loop(Position& pos, Move searchMoves[]) {
524 SearchStack ss[PLY_MAX_PLUS_2];
525 Move pv[PLY_MAX_PLUS_2];
526 Move EasyMove = MOVE_NONE;
527 Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
529 // Moves to search are verified, copied, scored and sorted
530 RootMoveList rml(pos, searchMoves);
532 // Handle special case of searching on a mate/stale position
533 if (rml.move_count() == 0)
536 wait_for_stop_or_ponderhit();
538 return pos.is_check() ? -VALUE_MATE : VALUE_DRAW;
541 // Print RootMoveList startup scoring to the standard output,
542 // so to output information also for iteration 1.
543 cout << set960(pos.is_chess960()) // Is enough to set once at the beginning
544 << "info depth " << 1
545 << "\ninfo depth " << 1
546 << " score " << value_to_uci(rml.move_score(0))
547 << " time " << current_search_time()
548 << " nodes " << pos.nodes_searched()
549 << " nps " << nps(pos)
550 << " pv " << rml.move(0) << "\n";
555 init_ss_array(ss, PLY_MAX_PLUS_2);
556 pv[0] = pv[1] = MOVE_NONE;
557 ValueByIteration[1] = rml.move_score(0);
560 // Is one move significantly better than others after initial scoring ?
561 if ( rml.move_count() == 1
562 || rml.move_score(0) > rml.move_score(1) + EasyMoveMargin)
563 EasyMove = rml.move(0);
565 // Iterative deepening loop
566 while (Iteration < PLY_MAX)
568 // Initialize iteration
570 BestMoveChangesByIteration[Iteration] = 0;
572 cout << "info depth " << Iteration << endl;
574 // Calculate dynamic aspiration window based on previous iterations
575 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
577 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
578 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
580 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
581 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
583 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
584 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
587 // Search to the current depth, rml is updated and sorted, alpha and beta could change
588 value = root_search(pos, ss, pv, rml, &alpha, &beta);
590 // Write PV to transposition table, in case the relevant entries have
591 // been overwritten during the search.
592 insert_pv_in_tt(pos, pv);
595 break; // Value cannot be trusted. Break out immediately!
597 //Save info about search result
598 ValueByIteration[Iteration] = value;
600 // Drop the easy move if differs from the new best move
601 if (pv[0] != EasyMove)
602 EasyMove = MOVE_NONE;
604 if (UseTimeManagement)
607 bool stopSearch = false;
609 // Stop search early if there is only a single legal move,
610 // we search up to Iteration 6 anyway to get a proper score.
611 if (Iteration >= 6 && rml.move_count() == 1)
614 // Stop search early when the last two iterations returned a mate score
616 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
617 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
620 // Stop search early if one move seems to be much better than the others
623 && ( ( rml.move_nodes(0) > (pos.nodes_searched() * 85) / 100
624 && current_search_time() > TimeMgr.available_time() / 16)
625 ||( rml.move_nodes(0) > (pos.nodes_searched() * 98) / 100
626 && current_search_time() > TimeMgr.available_time() / 32)))
629 // Add some extra time if the best move has changed during the last two iterations
630 if (Iteration > 5 && Iteration <= 50)
631 TimeMgr.pv_instability(BestMoveChangesByIteration[Iteration],
632 BestMoveChangesByIteration[Iteration-1]);
634 // Stop search if most of MaxSearchTime is consumed at the end of the
635 // iteration. We probably don't have enough time to search the first
636 // move at the next iteration anyway.
637 if (current_search_time() > (TimeMgr.available_time() * 80) / 128)
643 StopOnPonderhit = true;
649 if (MaxDepth && Iteration >= MaxDepth)
653 // If we are pondering or in infinite search, we shouldn't print the
654 // best move before we are told to do so.
655 if (!AbortSearch && (PonderSearch || InfiniteSearch))
656 wait_for_stop_or_ponderhit();
658 // Print final search statistics
659 cout << "info nodes " << pos.nodes_searched()
660 << " nps " << nps(pos)
661 << " time " << current_search_time() << endl;
663 // Print the best move and the ponder move to the standard output
664 if (pv[0] == MOVE_NONE || MultiPV > 1)
670 assert(pv[0] != MOVE_NONE);
672 cout << "bestmove " << pv[0];
674 if (pv[1] != MOVE_NONE)
675 cout << " ponder " << pv[1];
682 dbg_print_mean(LogFile);
684 if (dbg_show_hit_rate)
685 dbg_print_hit_rate(LogFile);
687 LogFile << "\nNodes: " << pos.nodes_searched()
688 << "\nNodes/second: " << nps(pos)
689 << "\nBest move: " << move_to_san(pos, pv[0]);
692 pos.do_move(pv[0], st);
693 LogFile << "\nPonder move: "
694 << move_to_san(pos, pv[1]) // Works also with MOVE_NONE
697 return rml.move_score(0);
701 // root_search() is the function which searches the root node. It is
702 // similar to search_pv except that it uses a different move ordering
703 // scheme, prints some information to the standard output and handles
704 // the fail low/high loops.
706 Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
712 Depth depth, ext, newDepth;
713 Value value, alpha, beta;
714 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
715 int researchCountFH, researchCountFL;
717 researchCountFH = researchCountFL = 0;
720 isCheck = pos.is_check();
721 depth = (Iteration - 2) * ONE_PLY + InitialDepth;
723 // Step 1. Initialize node (polling is omitted at root)
724 ss->currentMove = ss->bestMove = MOVE_NONE;
726 // Step 2. Check for aborted search (omitted at root)
727 // Step 3. Mate distance pruning (omitted at root)
728 // Step 4. Transposition table lookup (omitted at root)
730 // Step 5. Evaluate the position statically
731 // At root we do this only to get reference value for child nodes
732 ss->evalMargin = VALUE_NONE;
733 ss->eval = isCheck ? VALUE_NONE : evaluate(pos, ss->evalMargin);
735 // Step 6. Razoring (omitted at root)
736 // Step 7. Static null move pruning (omitted at root)
737 // Step 8. Null move search with verification search (omitted at root)
738 // Step 9. Internal iterative deepening (omitted at root)
740 // Step extra. Fail low loop
741 // We start with small aspiration window and in case of fail low, we research
742 // with bigger window until we are not failing low anymore.
745 // Sort the moves before to (re)search
746 rml.score_moves(pos);
749 // Step 10. Loop through all moves in the root move list
750 for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
752 // This is used by time management
753 FirstRootMove = (i == 0);
755 // Save the current node count before the move is searched
756 nodes = pos.nodes_searched();
758 // Pick the next root move, and print the move and the move number to
759 // the standard output.
760 move = ss->currentMove = rml.move(i);
762 if (current_search_time() >= 1000)
763 cout << "info currmove " << move
764 << " currmovenumber " << i + 1 << endl;
766 moveIsCheck = pos.move_is_check(move);
767 captureOrPromotion = pos.move_is_capture_or_promotion(move);
769 // Step 11. Decide the new search depth
770 ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
771 newDepth = depth + ext;
773 // Step 12. Futility pruning (omitted at root)
775 // Step extra. Fail high loop
776 // If move fails high, we research with bigger window until we are not failing
778 value = - VALUE_INFINITE;
782 // Step 13. Make the move
783 pos.do_move(move, st, ci, moveIsCheck);
785 // Step extra. pv search
786 // We do pv search for first moves (i < MultiPV)
787 // and for fail high research (value > alpha)
788 if (i < MultiPV || value > alpha)
790 // Aspiration window is disabled in multi-pv case
792 alpha = -VALUE_INFINITE;
794 // Full depth PV search, done on first move or after a fail high
795 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
799 // Step 14. Reduced search
800 // if the move fails high will be re-searched at full depth
801 bool doFullDepthSearch = true;
803 if ( depth >= 3 * ONE_PLY
805 && !captureOrPromotion
806 && !move_is_castle(move))
808 ss->reduction = reduction<PV>(depth, i - MultiPV + 2);
811 assert(newDepth-ss->reduction >= ONE_PLY);
813 // Reduced depth non-pv search using alpha as upperbound
814 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
815 doFullDepthSearch = (value > alpha);
818 // The move failed high, but if reduction is very big we could
819 // face a false positive, retry with a less aggressive reduction,
820 // if the move fails high again then go with full depth search.
821 if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
823 assert(newDepth - ONE_PLY >= ONE_PLY);
825 ss->reduction = ONE_PLY;
826 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
827 doFullDepthSearch = (value > alpha);
829 ss->reduction = DEPTH_ZERO; // Restore original reduction
832 // Step 15. Full depth search
833 if (doFullDepthSearch)
835 // Full depth non-pv search using alpha as upperbound
836 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, 1);
838 // If we are above alpha then research at same depth but as PV
839 // to get a correct score or eventually a fail high above beta.
841 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
845 // Step 16. Undo move
848 // Can we exit fail high loop ?
849 if (AbortSearch || value < beta)
852 // We are failing high and going to do a research. It's important to update
853 // the score before research in case we run out of time while researching.
854 rml.set_move_score(i, value);
856 extract_pv_from_tt(pos, move, pv);
857 rml.set_move_pv(i, pv);
859 // Print information to the standard output
860 print_pv_info(pos, pv, alpha, beta, value);
862 // Prepare for a research after a fail high, each time with a wider window
863 *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
866 } // End of fail high loop
868 // Finished searching the move. If AbortSearch is true, the search
869 // was aborted because the user interrupted the search or because we
870 // ran out of time. In this case, the return value of the search cannot
871 // be trusted, and we break out of the loop without updating the best
876 // Remember searched nodes counts for this move
877 rml.add_move_nodes(i, pos.nodes_searched() - nodes);
879 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
880 assert(value < beta);
882 // Step 17. Check for new best move
883 if (value <= alpha && i >= MultiPV)
884 rml.set_move_score(i, -VALUE_INFINITE);
887 // PV move or new best move!
890 rml.set_move_score(i, value);
892 extract_pv_from_tt(pos, move, pv);
893 rml.set_move_pv(i, pv);
897 // We record how often the best move has been changed in each
898 // iteration. This information is used for time managment: When
899 // the best move changes frequently, we allocate some more time.
901 BestMoveChangesByIteration[Iteration]++;
903 // Print information to the standard output
904 print_pv_info(pos, pv, alpha, beta, value);
906 // Raise alpha to setup proper non-pv search upper bound
913 for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
915 cout << "info multipv " << j + 1
916 << " score " << value_to_uci(rml.move_score(j))
917 << " depth " << (j <= i ? Iteration : Iteration - 1)
918 << " time " << current_search_time()
919 << " nodes " << pos.nodes_searched()
920 << " nps " << nps(pos)
923 for (int k = 0; rml.move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
924 cout << rml.move_pv(j, k) << " ";
928 alpha = rml.move_score(Min(i, MultiPV - 1));
930 } // PV move or new best move
932 assert(alpha >= *alphaPtr);
934 AspirationFailLow = (alpha == *alphaPtr);
936 if (AspirationFailLow && StopOnPonderhit)
937 StopOnPonderhit = false;
940 // Can we exit fail low loop ?
941 if (AbortSearch || !AspirationFailLow)
944 // Prepare for a research after a fail low, each time with a wider window
945 *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
950 // Sort the moves before to return
957 // search<>() is the main search function for both PV and non-PV nodes and for
958 // normal and SplitPoint nodes. When called just after a split point the search
959 // is simpler because we have already probed the hash table, done a null move
960 // search, and searched the first move before splitting, we don't have to repeat
961 // all this work again. We also don't need to store anything to the hash table
962 // here: This is taken care of after we return from the split point.
964 template <NodeType PvNode, bool SpNode>
965 Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
967 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
968 assert(beta > alpha && beta <= VALUE_INFINITE);
969 assert(PvNode || alpha == beta - 1);
970 assert(ply > 0 && ply < PLY_MAX);
971 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
973 Move movesSearched[MOVES_MAX];
977 Move ttMove, move, excludedMove, threatMove;
980 Value bestValue, value, oldAlpha;
981 Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
982 bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
983 bool mateThreat = false;
985 int threadID = pos.thread();
986 SplitPoint* sp = NULL;
987 refinedValue = bestValue = value = -VALUE_INFINITE;
989 isCheck = pos.is_check();
995 ttMove = excludedMove = MOVE_NONE;
996 threatMove = sp->threatMove;
997 mateThreat = sp->mateThreat;
998 goto split_point_start;
999 } else {} // Hack to fix icc's "statement is unreachable" warning
1001 // Step 1. Initialize node and poll. Polling can abort search
1002 ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
1003 (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE;
1005 if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls)
1011 // Step 2. Check for aborted search and immediate draw
1012 if ( AbortSearch || ThreadsMgr.thread_should_stop(threadID)
1013 || pos.is_draw() || ply >= PLY_MAX - 1)
1016 // Step 3. Mate distance pruning
1017 alpha = Max(value_mated_in(ply), alpha);
1018 beta = Min(value_mate_in(ply+1), beta);
1022 // Step 4. Transposition table lookup
1024 // We don't want the score of a partial search to overwrite a previous full search
1025 // TT value, so we use a different position key in case of an excluded move exists.
1026 excludedMove = ss->excludedMove;
1027 posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1029 tte = TT.retrieve(posKey);
1030 ttMove = tte ? tte->move() : MOVE_NONE;
1032 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1033 // This is to avoid problems in the following areas:
1035 // * Repetition draw detection
1036 // * Fifty move rule detection
1037 // * Searching for a mate
1038 // * Printing of full PV line
1039 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1042 ss->bestMove = ttMove; // Can be MOVE_NONE
1043 return value_from_tt(tte->value(), ply);
1046 // Step 5. Evaluate the position statically and
1047 // update gain statistics of parent move.
1049 ss->eval = ss->evalMargin = VALUE_NONE;
1052 assert(tte->static_value() != VALUE_NONE);
1054 ss->eval = tte->static_value();
1055 ss->evalMargin = tte->static_value_margin();
1056 refinedValue = refine_eval(tte, ss->eval, ply);
1060 refinedValue = ss->eval = evaluate(pos, ss->evalMargin);
1061 TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);
1064 // Save gain for the parent non-capture move
1065 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1067 // Step 6. Razoring (is omitted in PV nodes)
1069 && depth < RazorDepth
1071 && refinedValue < beta - razor_margin(depth)
1072 && ttMove == MOVE_NONE
1073 && !value_is_mate(beta)
1074 && !pos.has_pawn_on_7th(pos.side_to_move()))
1076 Value rbeta = beta - razor_margin(depth);
1077 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply);
1079 // Logically we should return (v + razor_margin(depth)), but
1080 // surprisingly this did slightly weaker in tests.
1084 // Step 7. Static null move pruning (is omitted in PV nodes)
1085 // We're betting that the opponent doesn't have a move that will reduce
1086 // the score by more than futility_margin(depth) if we do a null move.
1088 && !ss->skipNullMove
1089 && depth < RazorDepth
1091 && refinedValue >= beta + futility_margin(depth, 0)
1092 && !value_is_mate(beta)
1093 && pos.non_pawn_material(pos.side_to_move()))
1094 return refinedValue - futility_margin(depth, 0);
1096 // Step 8. Null move search with verification search (is omitted in PV nodes)
1098 && !ss->skipNullMove
1101 && refinedValue >= beta
1102 && !value_is_mate(beta)
1103 && pos.non_pawn_material(pos.side_to_move()))
1105 ss->currentMove = MOVE_NULL;
1107 // Null move dynamic reduction based on depth
1108 int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
1110 // Null move dynamic reduction based on value
1111 if (refinedValue - beta > PawnValueMidgame)
1114 pos.do_null_move(st);
1115 (ss+1)->skipNullMove = true;
1116 nullValue = -search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1);
1117 (ss+1)->skipNullMove = false;
1118 pos.undo_null_move();
1120 if (nullValue >= beta)
1122 // Do not return unproven mate scores
1123 if (nullValue >= value_mate_in(PLY_MAX))
1126 if (depth < 6 * ONE_PLY)
1129 // Do verification search at high depths
1130 ss->skipNullMove = true;
1131 Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY, ply);
1132 ss->skipNullMove = false;
1139 // The null move failed low, which means that we may be faced with
1140 // some kind of threat. If the previous move was reduced, check if
1141 // the move that refuted the null move was somehow connected to the
1142 // move which was reduced. If a connection is found, return a fail
1143 // low score (which will cause the reduced move to fail high in the
1144 // parent node, which will trigger a re-search with full depth).
1145 if (nullValue == value_mated_in(ply + 2))
1148 threatMove = (ss+1)->bestMove;
1149 if ( depth < ThreatDepth
1150 && (ss-1)->reduction
1151 && connected_moves(pos, (ss-1)->currentMove, threatMove))
1156 // Step 9. Internal iterative deepening
1157 if ( depth >= IIDDepth[PvNode]
1158 && ttMove == MOVE_NONE
1159 && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
1161 Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
1163 ss->skipNullMove = true;
1164 search<PvNode>(pos, ss, alpha, beta, d, ply);
1165 ss->skipNullMove = false;
1167 ttMove = ss->bestMove;
1168 tte = TT.retrieve(posKey);
1171 // Expensive mate threat detection (only for PV nodes)
1173 mateThreat = pos.has_mate_threat();
1175 split_point_start: // At split points actual search starts from here
1177 // Initialize a MovePicker object for the current position
1178 // FIXME currently MovePicker() c'tor is needless called also in SplitPoint
1179 MovePicker mpBase(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
1180 MovePicker& mp = SpNode ? *sp->mp : mpBase;
1182 ss->bestMove = MOVE_NONE;
1183 singleEvasion = !SpNode && isCheck && mp.number_of_evasions() == 1;
1184 futilityBase = ss->eval + ss->evalMargin;
1185 singularExtensionNode = !SpNode
1186 && depth >= SingularExtensionDepth[PvNode]
1189 && !excludedMove // Do not allow recursive singular extension search
1190 && (tte->type() & VALUE_TYPE_LOWER)
1191 && tte->depth() >= depth - 3 * ONE_PLY;
1194 lock_grab(&(sp->lock));
1195 bestValue = sp->bestValue;
1198 // Step 10. Loop through moves
1199 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1200 while ( bestValue < beta
1201 && (move = mp.get_next_move()) != MOVE_NONE
1202 && !ThreadsMgr.thread_should_stop(threadID))
1204 assert(move_is_ok(move));
1208 moveCount = ++sp->moveCount;
1209 lock_release(&(sp->lock));
1211 else if (move == excludedMove)
1214 movesSearched[moveCount++] = move;
1216 moveIsCheck = pos.move_is_check(move, ci);
1217 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1219 // Step 11. Decide the new search depth
1220 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1222 // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s),
1223 // and just one fails high on (alpha, beta), then that move is singular and should be extended.
1224 // To verify this we do a reduced search on all the other moves but the ttMove, if result is
1225 // lower then ttValue minus a margin then we extend ttMove.
1226 if ( singularExtensionNode
1227 && move == tte->move()
1230 Value ttValue = value_from_tt(tte->value(), ply);
1232 if (abs(ttValue) < VALUE_KNOWN_WIN)
1234 Value b = ttValue - SingularExtensionMargin;
1235 ss->excludedMove = move;
1236 ss->skipNullMove = true;
1237 Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
1238 ss->skipNullMove = false;
1239 ss->excludedMove = MOVE_NONE;
1240 ss->bestMove = MOVE_NONE;
1246 // Update current move (this must be done after singular extension search)
1247 ss->currentMove = move;
1248 newDepth = depth - ONE_PLY + ext;
1250 // Step 12. Futility pruning (is omitted in PV nodes)
1252 && !captureOrPromotion
1256 && !move_is_castle(move))
1258 // Move count based pruning
1259 if ( moveCount >= futility_move_count(depth)
1260 && !(threatMove && connected_threat(pos, move, threatMove))
1261 && bestValue > value_mated_in(PLY_MAX)) // FIXME bestValue is racy
1264 lock_grab(&(sp->lock));
1269 // Value based pruning
1270 // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
1271 // but fixing this made program slightly weaker.
1272 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1273 futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount)
1274 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1276 if (futilityValueScaled < beta)
1280 lock_grab(&(sp->lock));
1281 if (futilityValueScaled > sp->bestValue)
1282 sp->bestValue = bestValue = futilityValueScaled;
1284 else if (futilityValueScaled > bestValue)
1285 bestValue = futilityValueScaled;
1290 // Prune neg. see moves at low depths
1291 if ( predictedDepth < 2 * ONE_PLY
1292 && bestValue > value_mated_in(PLY_MAX)
1293 && pos.see_sign(move) < 0)
1296 lock_grab(&(sp->lock));
1302 // Step 13. Make the move
1303 pos.do_move(move, st, ci, moveIsCheck);
1305 // Step extra. pv search (only in PV nodes)
1306 // The first move in list is the expected PV
1307 if (!SpNode && PvNode && moveCount == 1)
1308 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1311 // Step 14. Reduced depth search
1312 // If the move fails high will be re-searched at full depth.
1313 bool doFullDepthSearch = true;
1315 if ( depth >= 3 * ONE_PLY
1316 && !captureOrPromotion
1318 && !move_is_castle(move)
1319 && !(ss->killers[0] == move || ss->killers[1] == move))
1321 ss->reduction = reduction<PvNode>(depth, moveCount);
1324 alpha = SpNode ? sp->alpha : alpha;
1325 Depth d = newDepth - ss->reduction;
1326 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1328 doFullDepthSearch = (value > alpha);
1331 // The move failed high, but if reduction is very big we could
1332 // face a false positive, retry with a less aggressive reduction,
1333 // if the move fails high again then go with full depth search.
1334 if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
1336 assert(newDepth - ONE_PLY >= ONE_PLY);
1338 ss->reduction = ONE_PLY;
1339 alpha = SpNode ? sp->alpha : alpha;
1340 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, ply+1);
1341 doFullDepthSearch = (value > alpha);
1343 ss->reduction = DEPTH_ZERO; // Restore original reduction
1346 // Step 15. Full depth search
1347 if (doFullDepthSearch)
1349 alpha = SpNode ? sp->alpha : alpha;
1350 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1352 // Step extra. pv search (only in PV nodes)
1353 // Search only for possible new PV nodes, if instead value >= beta then
1354 // parent node fails low with value <= alpha and tries another move.
1355 if (PvNode && value > alpha && value < beta)
1356 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1360 // Step 16. Undo move
1361 pos.undo_move(move);
1363 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1365 // Step 17. Check for new best move
1368 lock_grab(&(sp->lock));
1369 bestValue = sp->bestValue;
1373 if (value > bestValue && !(SpNode && ThreadsMgr.thread_should_stop(threadID)))
1378 sp->bestValue = value;
1382 if (SpNode && (!PvNode || value >= beta))
1383 sp->stopRequest = true;
1385 if (PvNode && value < beta) // We want always alpha < beta
1392 if (value == value_mate_in(ply + 1))
1393 ss->mateKiller = move;
1395 ss->bestMove = move;
1398 sp->parentSstack->bestMove = move;
1402 // Step 18. Check for split
1404 && depth >= MinimumSplitDepth
1405 && ThreadsMgr.active_threads() > 1
1407 && ThreadsMgr.available_thread_exists(threadID)
1409 && !ThreadsMgr.thread_should_stop(threadID)
1411 ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1412 threatMove, mateThreat, moveCount, &mp, PvNode);
1415 // Step 19. Check for mate and stalemate
1416 // All legal moves have been searched and if there are
1417 // no legal moves, it must be mate or stalemate.
1418 // If one move was excluded return fail low score.
1419 if (!SpNode && !moveCount)
1420 return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW;
1422 // Step 20. Update tables
1423 // If the search is not aborted, update the transposition table,
1424 // history counters, and killer moves.
1425 if (!SpNode && !AbortSearch && !ThreadsMgr.thread_should_stop(threadID))
1427 move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
1428 vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
1429 : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
1431 TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, ss->evalMargin);
1433 // Update killers and history only for non capture moves that fails high
1434 if ( bestValue >= beta
1435 && !pos.move_is_capture_or_promotion(move))
1437 update_history(pos, move, depth, movesSearched, moveCount);
1438 update_killers(move, ss);
1444 // Here we have the lock still grabbed
1445 sp->slaves[threadID] = 0;
1446 sp->nodes += pos.nodes_searched();
1447 lock_release(&(sp->lock));
1450 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1456 // qsearch() is the quiescence search function, which is called by the main
1457 // search function when the remaining depth is zero (or, to be more precise,
1458 // less than ONE_PLY).
1460 template <NodeType PvNode>
1461 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1463 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1464 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1465 assert(PvNode || alpha == beta - 1);
1467 assert(ply > 0 && ply < PLY_MAX);
1468 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1472 Value bestValue, value, evalMargin, futilityValue, futilityBase;
1473 bool isCheck, deepChecks, enoughMaterial, moveIsCheck, evasionPrunable;
1475 Value oldAlpha = alpha;
1477 ss->bestMove = ss->currentMove = MOVE_NONE;
1479 // Check for an instant draw or maximum ply reached
1480 if (pos.is_draw() || ply >= PLY_MAX - 1)
1483 // Transposition table lookup. At PV nodes, we don't use the TT for
1484 // pruning, but only for move ordering.
1485 tte = TT.retrieve(pos.get_key());
1486 ttMove = (tte ? tte->move() : MOVE_NONE);
1488 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1490 ss->bestMove = ttMove; // Can be MOVE_NONE
1491 return value_from_tt(tte->value(), ply);
1494 isCheck = pos.is_check();
1496 // Evaluate the position statically
1499 bestValue = futilityBase = -VALUE_INFINITE;
1500 ss->eval = evalMargin = VALUE_NONE;
1501 deepChecks = enoughMaterial = false;
1507 assert(tte->static_value() != VALUE_NONE);
1509 evalMargin = tte->static_value_margin();
1510 ss->eval = bestValue = tte->static_value();
1513 ss->eval = bestValue = evaluate(pos, evalMargin);
1515 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1517 // Stand pat. Return immediately if static value is at least beta
1518 if (bestValue >= beta)
1521 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1526 if (PvNode && bestValue > alpha)
1529 // If we are near beta then try to get a cutoff pushing checks a bit further
1530 deepChecks = (depth == -ONE_PLY && bestValue >= beta - PawnValueMidgame / 8);
1532 // Futility pruning parameters, not needed when in check
1533 futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1534 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1537 // Initialize a MovePicker object for the current position, and prepare
1538 // to search the moves. Because the depth is <= 0 here, only captures,
1539 // queen promotions and checks (only if depth == 0 or depth == -ONE_PLY
1540 // and we are near beta) will be generated.
1541 MovePicker mp = MovePicker(pos, ttMove, deepChecks ? DEPTH_ZERO : depth, H);
1544 // Loop through the moves until no moves remain or a beta cutoff occurs
1545 while ( alpha < beta
1546 && (move = mp.get_next_move()) != MOVE_NONE)
1548 assert(move_is_ok(move));
1550 moveIsCheck = pos.move_is_check(move, ci);
1558 && !move_is_promotion(move)
1559 && !pos.move_is_passed_pawn_push(move))
1561 futilityValue = futilityBase
1562 + pos.endgame_value_of_piece_on(move_to(move))
1563 + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1565 if (futilityValue < alpha)
1567 if (futilityValue > bestValue)
1568 bestValue = futilityValue;
1573 // Detect non-capture evasions that are candidate to be pruned
1574 evasionPrunable = isCheck
1575 && bestValue > value_mated_in(PLY_MAX)
1576 && !pos.move_is_capture(move)
1577 && !pos.can_castle(pos.side_to_move());
1579 // Don't search moves with negative SEE values
1581 && (!isCheck || evasionPrunable)
1583 && !move_is_promotion(move)
1584 && pos.see_sign(move) < 0)
1587 // Update current move
1588 ss->currentMove = move;
1590 // Make and search the move
1591 pos.do_move(move, st, ci, moveIsCheck);
1592 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1);
1593 pos.undo_move(move);
1595 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1598 if (value > bestValue)
1604 ss->bestMove = move;
1609 // All legal moves have been searched. A special case: If we're in check
1610 // and no legal moves were found, it is checkmate.
1611 if (isCheck && bestValue == -VALUE_INFINITE)
1612 return value_mated_in(ply);
1614 // Update transposition table
1615 Depth d = (depth == DEPTH_ZERO ? DEPTH_ZERO : DEPTH_ZERO - ONE_PLY);
1616 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1617 TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, d, ss->bestMove, ss->eval, evalMargin);
1619 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1625 // connected_moves() tests whether two moves are 'connected' in the sense
1626 // that the first move somehow made the second move possible (for instance
1627 // if the moving piece is the same in both moves). The first move is assumed
1628 // to be the move that was made to reach the current position, while the
1629 // second move is assumed to be a move from the current position.
1631 bool connected_moves(const Position& pos, Move m1, Move m2) {
1633 Square f1, t1, f2, t2;
1636 assert(move_is_ok(m1));
1637 assert(move_is_ok(m2));
1639 if (m2 == MOVE_NONE)
1642 // Case 1: The moving piece is the same in both moves
1648 // Case 2: The destination square for m2 was vacated by m1
1654 // Case 3: Moving through the vacated square
1655 if ( piece_is_slider(pos.piece_on(f2))
1656 && bit_is_set(squares_between(f2, t2), f1))
1659 // Case 4: The destination square for m2 is defended by the moving piece in m1
1660 p = pos.piece_on(t1);
1661 if (bit_is_set(pos.attacks_from(p, t1), t2))
1664 // Case 5: Discovered check, checking piece is the piece moved in m1
1665 if ( piece_is_slider(p)
1666 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1667 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1669 // discovered_check_candidates() works also if the Position's side to
1670 // move is the opposite of the checking piece.
1671 Color them = opposite_color(pos.side_to_move());
1672 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1674 if (bit_is_set(dcCandidates, f2))
1681 // value_is_mate() checks if the given value is a mate one eventually
1682 // compensated for the ply.
1684 bool value_is_mate(Value value) {
1686 assert(abs(value) <= VALUE_INFINITE);
1688 return value <= value_mated_in(PLY_MAX)
1689 || value >= value_mate_in(PLY_MAX);
1693 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1694 // "plies to mate from the current ply". Non-mate scores are unchanged.
1695 // The function is called before storing a value to the transposition table.
1697 Value value_to_tt(Value v, int ply) {
1699 if (v >= value_mate_in(PLY_MAX))
1702 if (v <= value_mated_in(PLY_MAX))
1709 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1710 // the transposition table to a mate score corrected for the current ply.
1712 Value value_from_tt(Value v, int ply) {
1714 if (v >= value_mate_in(PLY_MAX))
1717 if (v <= value_mated_in(PLY_MAX))
1724 // extension() decides whether a move should be searched with normal depth,
1725 // or with extended depth. Certain classes of moves (checking moves, in
1726 // particular) are searched with bigger depth than ordinary moves and in
1727 // any case are marked as 'dangerous'. Note that also if a move is not
1728 // extended, as example because the corresponding UCI option is set to zero,
1729 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1730 template <NodeType PvNode>
1731 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1732 bool singleEvasion, bool mateThreat, bool* dangerous) {
1734 assert(m != MOVE_NONE);
1736 Depth result = DEPTH_ZERO;
1737 *dangerous = moveIsCheck | singleEvasion | mateThreat;
1741 if (moveIsCheck && pos.see_sign(m) >= 0)
1742 result += CheckExtension[PvNode];
1745 result += SingleEvasionExtension[PvNode];
1748 result += MateThreatExtension[PvNode];
1751 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1753 Color c = pos.side_to_move();
1754 if (relative_rank(c, move_to(m)) == RANK_7)
1756 result += PawnPushTo7thExtension[PvNode];
1759 if (pos.pawn_is_passed(c, move_to(m)))
1761 result += PassedPawnExtension[PvNode];
1766 if ( captureOrPromotion
1767 && pos.type_of_piece_on(move_to(m)) != PAWN
1768 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1769 - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1770 && !move_is_promotion(m)
1773 result += PawnEndgameExtension[PvNode];
1778 && captureOrPromotion
1779 && pos.type_of_piece_on(move_to(m)) != PAWN
1780 && pos.see_sign(m) >= 0)
1782 result += ONE_PLY / 2;
1786 return Min(result, ONE_PLY);
1790 // connected_threat() tests whether it is safe to forward prune a move or if
1791 // is somehow coonected to the threat move returned by null search.
1793 bool connected_threat(const Position& pos, Move m, Move threat) {
1795 assert(move_is_ok(m));
1796 assert(threat && move_is_ok(threat));
1797 assert(!pos.move_is_check(m));
1798 assert(!pos.move_is_capture_or_promotion(m));
1799 assert(!pos.move_is_passed_pawn_push(m));
1801 Square mfrom, mto, tfrom, tto;
1803 mfrom = move_from(m);
1805 tfrom = move_from(threat);
1806 tto = move_to(threat);
1808 // Case 1: Don't prune moves which move the threatened piece
1812 // Case 2: If the threatened piece has value less than or equal to the
1813 // value of the threatening piece, don't prune move which defend it.
1814 if ( pos.move_is_capture(threat)
1815 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1816 || pos.type_of_piece_on(tfrom) == KING)
1817 && pos.move_attacks_square(m, tto))
1820 // Case 3: If the moving piece in the threatened move is a slider, don't
1821 // prune safe moves which block its ray.
1822 if ( piece_is_slider(pos.piece_on(tfrom))
1823 && bit_is_set(squares_between(tfrom, tto), mto)
1824 && pos.see_sign(m) >= 0)
1831 // ok_to_use_TT() returns true if a transposition table score
1832 // can be used at a given point in search.
1834 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1836 Value v = value_from_tt(tte->value(), ply);
1838 return ( tte->depth() >= depth
1839 || v >= Max(value_mate_in(PLY_MAX), beta)
1840 || v < Min(value_mated_in(PLY_MAX), beta))
1842 && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1843 || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1847 // refine_eval() returns the transposition table score if
1848 // possible otherwise falls back on static position evaluation.
1850 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1854 Value v = value_from_tt(tte->value(), ply);
1856 if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1857 || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1864 // update_history() registers a good move that produced a beta-cutoff
1865 // in history and marks as failures all the other moves of that ply.
1867 void update_history(const Position& pos, Move move, Depth depth,
1868 Move movesSearched[], int moveCount) {
1871 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
1873 for (int i = 0; i < moveCount - 1; i++)
1875 m = movesSearched[i];
1879 if (!pos.move_is_capture_or_promotion(m))
1880 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
1885 // update_killers() add a good move that produced a beta-cutoff
1886 // among the killer moves of that ply.
1888 void update_killers(Move m, SearchStack* ss) {
1890 if (m == ss->killers[0])
1893 ss->killers[1] = ss->killers[0];
1898 // update_gains() updates the gains table of a non-capture move given
1899 // the static position evaluation before and after the move.
1901 void update_gains(const Position& pos, Move m, Value before, Value after) {
1904 && before != VALUE_NONE
1905 && after != VALUE_NONE
1906 && pos.captured_piece_type() == PIECE_TYPE_NONE
1907 && !move_is_special(m))
1908 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
1912 // current_search_time() returns the number of milliseconds which have passed
1913 // since the beginning of the current search.
1915 int current_search_time() {
1917 return get_system_time() - SearchStartTime;
1921 // value_to_uci() converts a value to a string suitable for use with the UCI protocol
1923 std::string value_to_uci(Value v) {
1925 std::stringstream s;
1927 if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
1928 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100
1930 s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
1935 // nps() computes the current nodes/second count.
1937 int nps(const Position& pos) {
1939 int t = current_search_time();
1940 return (t > 0 ? int((pos.nodes_searched() * 1000) / t) : 0);
1944 // poll() performs two different functions: It polls for user input, and it
1945 // looks at the time consumed so far and decides if it's time to abort the
1948 void poll(const Position& pos) {
1950 static int lastInfoTime;
1951 int t = current_search_time();
1954 if (data_available())
1956 // We are line oriented, don't read single chars
1957 std::string command;
1959 if (!std::getline(std::cin, command))
1962 if (command == "quit")
1965 PonderSearch = false;
1969 else if (command == "stop")
1972 PonderSearch = false;
1974 else if (command == "ponderhit")
1978 // Print search information
1982 else if (lastInfoTime > t)
1983 // HACK: Must be a new search where we searched less than
1984 // NodesBetweenPolls nodes during the first second of search.
1987 else if (t - lastInfoTime >= 1000)
1994 if (dbg_show_hit_rate)
1995 dbg_print_hit_rate();
1997 cout << "info nodes " << pos.nodes_searched() << " nps " << nps(pos)
1998 << " time " << t << endl;
2001 // Should we stop the search?
2005 bool stillAtFirstMove = FirstRootMove
2006 && !AspirationFailLow
2007 && t > TimeMgr.available_time();
2009 bool noMoreTime = t > TimeMgr.maximum_time()
2010 || stillAtFirstMove;
2012 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2013 || (ExactMaxTime && t >= ExactMaxTime)
2014 || (Iteration >= 3 && MaxNodes && pos.nodes_searched() >= MaxNodes))
2019 // ponderhit() is called when the program is pondering (i.e. thinking while
2020 // it's the opponent's turn to move) in order to let the engine know that
2021 // it correctly predicted the opponent's move.
2025 int t = current_search_time();
2026 PonderSearch = false;
2028 bool stillAtFirstMove = FirstRootMove
2029 && !AspirationFailLow
2030 && t > TimeMgr.available_time();
2032 bool noMoreTime = t > TimeMgr.maximum_time()
2033 || stillAtFirstMove;
2035 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2040 // init_ss_array() does a fast reset of the first entries of a SearchStack
2041 // array and of all the excludedMove and skipNullMove entries.
2043 void init_ss_array(SearchStack* ss, int size) {
2045 for (int i = 0; i < size; i++, ss++)
2047 ss->excludedMove = MOVE_NONE;
2048 ss->skipNullMove = false;
2049 ss->reduction = DEPTH_ZERO;
2053 ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE;
2058 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2059 // while the program is pondering. The point is to work around a wrinkle in
2060 // the UCI protocol: When pondering, the engine is not allowed to give a
2061 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2062 // We simply wait here until one of these commands is sent, and return,
2063 // after which the bestmove and pondermove will be printed (in id_loop()).
2065 void wait_for_stop_or_ponderhit() {
2067 std::string command;
2071 if (!std::getline(std::cin, command))
2074 if (command == "quit")
2079 else if (command == "ponderhit" || command == "stop")
2085 // print_pv_info() prints to standard output and eventually to log file information on
2086 // the current PV line. It is called at each iteration or after a new pv is found.
2088 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) {
2090 cout << "info depth " << Iteration
2091 << " score " << value_to_uci(value)
2092 << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
2093 << " time " << current_search_time()
2094 << " nodes " << pos.nodes_searched()
2095 << " nps " << nps(pos)
2098 for (Move* m = pv; *m != MOVE_NONE; m++)
2105 ValueType t = value >= beta ? VALUE_TYPE_LOWER :
2106 value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
2108 LogFile << pretty_pv(pos, current_search_time(), Iteration, value, t, pv) << endl;
2113 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2114 // the PV back into the TT. This makes sure the old PV moves are searched
2115 // first, even if the old TT entries have been overwritten.
2117 void insert_pv_in_tt(const Position& pos, Move pv[]) {
2121 Position p(pos, pos.thread());
2122 Value v, m = VALUE_NONE;
2124 for (int i = 0; pv[i] != MOVE_NONE; i++)
2126 tte = TT.retrieve(p.get_key());
2127 if (!tte || tte->move() != pv[i])
2129 v = (p.is_check() ? VALUE_NONE : evaluate(p, m));
2130 TT.store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[i], v, m);
2132 p.do_move(pv[i], st);
2137 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2138 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2139 // allow to always have a ponder move even when we fail high at root and also a
2140 // long PV to print that is important for position analysis.
2142 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]) {
2146 Position p(pos, pos.thread());
2149 assert(bestMove != MOVE_NONE);
2152 p.do_move(pv[ply++], st);
2154 while ( (tte = TT.retrieve(p.get_key())) != NULL
2155 && tte->move() != MOVE_NONE
2156 && move_is_legal(p, tte->move())
2158 && (!p.is_draw() || ply < 2))
2160 pv[ply] = tte->move();
2161 p.do_move(pv[ply++], st);
2163 pv[ply] = MOVE_NONE;
2167 // init_thread() is the function which is called when a new thread is
2168 // launched. It simply calls the idle_loop() function with the supplied
2169 // threadID. There are two versions of this function; one for POSIX
2170 // threads and one for Windows threads.
2172 #if !defined(_MSC_VER)
2174 void* init_thread(void* threadID) {
2176 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2182 DWORD WINAPI init_thread(LPVOID threadID) {
2184 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2191 /// The ThreadsManager class
2194 // idle_loop() is where the threads are parked when they have no work to do.
2195 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2196 // object for which the current thread is the master.
2198 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2200 assert(threadID >= 0 && threadID < MAX_THREADS);
2204 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2205 // master should exit as last one.
2206 if (AllThreadsShouldExit)
2209 threads[threadID].state = THREAD_TERMINATED;
2213 // If we are not thinking, wait for a condition to be signaled
2214 // instead of wasting CPU time polling for work.
2215 while (threadID >= ActiveThreads || threads[threadID].state == THREAD_INITIALIZING)
2218 assert(threadID != 0);
2220 if (AllThreadsShouldExit)
2223 threads[threadID].state = THREAD_AVAILABLE;
2225 lock_grab(&WaitLock);
2227 if (threadID >= ActiveThreads || threads[threadID].state == THREAD_INITIALIZING)
2228 cond_wait(&WaitCond[threadID], &WaitLock);
2230 lock_release(&WaitLock);
2233 // If this thread has been assigned work, launch a search
2234 if (threads[threadID].state == THREAD_WORKISWAITING)
2236 assert(!AllThreadsShouldExit);
2238 threads[threadID].state = THREAD_SEARCHING;
2240 // Here we call search() with SplitPoint template parameter set to true
2241 SplitPoint* tsp = threads[threadID].splitPoint;
2242 Position pos(*tsp->pos, threadID);
2243 SearchStack* ss = tsp->sstack[threadID] + 1;
2247 search<PV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2249 search<NonPV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2251 assert(threads[threadID].state == THREAD_SEARCHING);
2253 threads[threadID].state = THREAD_AVAILABLE;
2256 // If this thread is the master of a split point and all slaves have
2257 // finished their work at this split point, return from the idle loop.
2259 for ( ; sp && i < ActiveThreads && !sp->slaves[i]; i++) {}
2261 if (i == ActiveThreads)
2263 // Because sp->slaves[] is reset under lock protection,
2264 // be sure sp->lock has been released before to return.
2265 lock_grab(&(sp->lock));
2266 lock_release(&(sp->lock));
2268 // In helpful master concept a master can help only a sub-tree, and
2269 // because here is all finished is not possible master is booked.
2270 assert(threads[threadID].state == THREAD_AVAILABLE);
2272 threads[threadID].state = THREAD_SEARCHING;
2279 // init_threads() is called during startup. It launches all helper threads,
2280 // and initializes the split point stack and the global locks and condition
2283 void ThreadsManager::init_threads() {
2285 int i, arg[MAX_THREADS];
2288 // Initialize global locks
2290 lock_init(&WaitLock);
2292 for (i = 0; i < MAX_THREADS; i++)
2293 cond_init(&WaitCond[i]);
2295 // Initialize splitPoints[] locks
2296 for (i = 0; i < MAX_THREADS; i++)
2297 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2298 lock_init(&(threads[i].splitPoints[j].lock));
2300 // Will be set just before program exits to properly end the threads
2301 AllThreadsShouldExit = false;
2303 // Threads will be put all threads to sleep as soon as created
2306 // All threads except the main thread should be initialized to THREAD_INITIALIZING
2307 threads[0].state = THREAD_SEARCHING;
2308 for (i = 1; i < MAX_THREADS; i++)
2309 threads[i].state = THREAD_INITIALIZING;
2311 // Launch the helper threads
2312 for (i = 1; i < MAX_THREADS; i++)
2316 #if !defined(_MSC_VER)
2317 pthread_t pthread[1];
2318 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
2319 pthread_detach(pthread[0]);
2321 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
2325 cout << "Failed to create thread number " << i << endl;
2329 // Wait until the thread has finished launching and is gone to sleep
2330 while (threads[i].state == THREAD_INITIALIZING) {}
2335 // exit_threads() is called when the program exits. It makes all the
2336 // helper threads exit cleanly.
2338 void ThreadsManager::exit_threads() {
2340 AllThreadsShouldExit = true; // Let the woken up threads to exit idle_loop()
2342 // Wake up all the threads and waits for termination
2343 for (int i = 1; i < MAX_THREADS; i++)
2345 wake_sleeping_thread(i);
2346 while (threads[i].state != THREAD_TERMINATED) {}
2349 // Now we can safely destroy the locks
2350 for (int i = 0; i < MAX_THREADS; i++)
2351 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2352 lock_destroy(&(threads[i].splitPoints[j].lock));
2354 lock_destroy(&WaitLock);
2355 lock_destroy(&MPLock);
2357 // Now we can safely destroy the wait conditions
2358 for (int i = 0; i < MAX_THREADS; i++)
2359 cond_destroy(&WaitCond[i]);
2363 // thread_should_stop() checks whether the thread should stop its search.
2364 // This can happen if a beta cutoff has occurred in the thread's currently
2365 // active split point, or in some ancestor of the current split point.
2367 bool ThreadsManager::thread_should_stop(int threadID) const {
2369 assert(threadID >= 0 && threadID < ActiveThreads);
2371 SplitPoint* sp = threads[threadID].splitPoint;
2373 for ( ; sp && !sp->stopRequest; sp = sp->parent) {}
2378 // thread_is_available() checks whether the thread with threadID "slave" is
2379 // available to help the thread with threadID "master" at a split point. An
2380 // obvious requirement is that "slave" must be idle. With more than two
2381 // threads, this is not by itself sufficient: If "slave" is the master of
2382 // some active split point, it is only available as a slave to the other
2383 // threads which are busy searching the split point at the top of "slave"'s
2384 // split point stack (the "helpful master concept" in YBWC terminology).
2386 bool ThreadsManager::thread_is_available(int slave, int master) const {
2388 assert(slave >= 0 && slave < ActiveThreads);
2389 assert(master >= 0 && master < ActiveThreads);
2390 assert(ActiveThreads > 1);
2392 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2395 // Make a local copy to be sure doesn't change under our feet
2396 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2398 // No active split points means that the thread is available as
2399 // a slave for any other thread.
2400 if (localActiveSplitPoints == 0 || ActiveThreads == 2)
2403 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2404 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2405 // could have been set to 0 by another thread leading to an out of bound access.
2406 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2413 // available_thread_exists() tries to find an idle thread which is available as
2414 // a slave for the thread with threadID "master".
2416 bool ThreadsManager::available_thread_exists(int master) const {
2418 assert(master >= 0 && master < ActiveThreads);
2419 assert(ActiveThreads > 1);
2421 for (int i = 0; i < ActiveThreads; i++)
2422 if (thread_is_available(i, master))
2429 // split() does the actual work of distributing the work at a node between
2430 // several available threads. If it does not succeed in splitting the
2431 // node (because no idle threads are available, or because we have no unused
2432 // split point objects), the function immediately returns. If splitting is
2433 // possible, a SplitPoint object is initialized with all the data that must be
2434 // copied to the helper threads and we tell our helper threads that they have
2435 // been assigned work. This will cause them to instantly leave their idle loops and
2436 // call search().When all threads have returned from search() then split() returns.
2438 template <bool Fake>
2439 void ThreadsManager::split(Position& pos, SearchStack* ss, int ply, Value* alpha,
2440 const Value beta, Value* bestValue, Depth depth, Move threatMove,
2441 bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) {
2442 assert(pos.is_ok());
2443 assert(ply > 0 && ply < PLY_MAX);
2444 assert(*bestValue >= -VALUE_INFINITE);
2445 assert(*bestValue <= *alpha);
2446 assert(*alpha < beta);
2447 assert(beta <= VALUE_INFINITE);
2448 assert(depth > DEPTH_ZERO);
2449 assert(pos.thread() >= 0 && pos.thread() < ActiveThreads);
2450 assert(ActiveThreads > 1);
2452 int i, master = pos.thread();
2453 Thread& masterThread = threads[master];
2457 // If no other thread is available to help us, or if we have too many
2458 // active split points, don't split.
2459 if ( !available_thread_exists(master)
2460 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2462 lock_release(&MPLock);
2466 // Pick the next available split point object from the split point stack
2467 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2469 // Initialize the split point object
2470 splitPoint.parent = masterThread.splitPoint;
2471 splitPoint.stopRequest = false;
2472 splitPoint.ply = ply;
2473 splitPoint.depth = depth;
2474 splitPoint.threatMove = threatMove;
2475 splitPoint.mateThreat = mateThreat;
2476 splitPoint.alpha = *alpha;
2477 splitPoint.beta = beta;
2478 splitPoint.pvNode = pvNode;
2479 splitPoint.bestValue = *bestValue;
2481 splitPoint.moveCount = moveCount;
2482 splitPoint.pos = &pos;
2483 splitPoint.nodes = 0;
2484 splitPoint.parentSstack = ss;
2485 for (i = 0; i < ActiveThreads; i++)
2486 splitPoint.slaves[i] = 0;
2488 masterThread.splitPoint = &splitPoint;
2490 // If we are here it means we are not available
2491 assert(masterThread.state != THREAD_AVAILABLE);
2493 int workersCnt = 1; // At least the master is included
2495 // Allocate available threads setting state to THREAD_BOOKED
2496 for (i = 0; !Fake && i < ActiveThreads && workersCnt < MaxThreadsPerSplitPoint; i++)
2497 if (thread_is_available(i, master))
2499 threads[i].state = THREAD_BOOKED;
2500 threads[i].splitPoint = &splitPoint;
2501 splitPoint.slaves[i] = 1;
2505 assert(Fake || workersCnt > 1);
2507 // We can release the lock because slave threads are already booked and master is not available
2508 lock_release(&MPLock);
2510 // Tell the threads that they have work to do. This will make them leave
2511 // their idle loop. But before copy search stack tail for each thread.
2512 for (i = 0; i < ActiveThreads; i++)
2513 if (i == master || splitPoint.slaves[i])
2515 memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
2517 assert(i == master || threads[i].state == THREAD_BOOKED);
2519 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2522 // Everything is set up. The master thread enters the idle loop, from
2523 // which it will instantly launch a search, because its state is
2524 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2525 // idle loop, which means that the main thread will return from the idle
2526 // loop when all threads have finished their work at this split point.
2527 idle_loop(master, &splitPoint);
2529 // We have returned from the idle loop, which means that all threads are
2530 // finished. Update alpha and bestValue, and return.
2533 *alpha = splitPoint.alpha;
2534 *bestValue = splitPoint.bestValue;
2535 masterThread.activeSplitPoints--;
2536 masterThread.splitPoint = splitPoint.parent;
2537 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
2539 lock_release(&MPLock);
2543 // wake_sleeping_thread() wakes up all sleeping threads when it is time
2544 // to start a new search from the root.
2546 void ThreadsManager::wake_sleeping_thread(int threadID) {
2548 lock_grab(&WaitLock);
2549 cond_signal(&WaitCond[threadID]);
2550 lock_release(&WaitLock);
2554 /// The RootMoveList class
2556 // RootMoveList c'tor
2558 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) {
2560 SearchStack ss[PLY_MAX_PLUS_2];
2561 MoveStack mlist[MOVES_MAX];
2563 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
2565 // Initialize search stack
2566 init_ss_array(ss, PLY_MAX_PLUS_2);
2567 ss[0].eval = ss[0].evalMargin = VALUE_NONE;
2570 // Generate all legal moves
2571 MoveStack* last = generate_moves(pos, mlist);
2573 // Add each move to the moves[] array
2574 for (MoveStack* cur = mlist; cur != last; cur++)
2576 bool includeMove = includeAllMoves;
2578 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
2579 includeMove = (searchMoves[k] == cur->move);
2584 // Find a quick score for the move
2585 moves[count].move = ss[0].currentMove = moves[count].pv[0] = cur->move;
2586 moves[count].pv[1] = MOVE_NONE;
2587 pos.do_move(cur->move, st);
2588 moves[count].score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
2589 pos.undo_move(cur->move);
2595 // Score root moves using the standard way used in main search, the moves
2596 // are scored according to the order in which are returned by MovePicker.
2598 void RootMoveList::score_moves(const Position& pos)
2602 MovePicker mp = MovePicker(pos, MOVE_NONE, ONE_PLY, H);
2604 while ((move = mp.get_next_move()) != MOVE_NONE)
2605 for (int i = 0; i < count; i++)
2606 if (moves[i].move == move)
2608 moves[i].mp_score = score--;
2613 // RootMoveList simple methods definitions
2615 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
2619 for (j = 0; pv[j] != MOVE_NONE; j++)
2620 moves[moveNum].pv[j] = pv[j];
2622 moves[moveNum].pv[j] = MOVE_NONE;
2626 // RootMoveList::sort() sorts the root move list at the beginning of a new
2629 void RootMoveList::sort() {
2631 sort_multipv(count - 1); // Sort all items
2635 // RootMoveList::sort_multipv() sorts the first few moves in the root move
2636 // list by their scores and depths. It is used to order the different PVs
2637 // correctly in MultiPV mode.
2639 void RootMoveList::sort_multipv(int n) {
2643 for (i = 1; i <= n; i++)
2645 RootMove rm = moves[i];
2646 for (j = i; j > 0 && moves[j - 1] < rm; j--)
2647 moves[j] = moves[j - 1];