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 = 0.33 + log(double(hd)) * log(double(mc)) / 4.5;
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 && (ss-1)->currentMove != MOVE_NULL
1074 && !value_is_mate(beta)
1075 && !pos.has_pawn_on_7th(pos.side_to_move()))
1077 Value rbeta = beta - razor_margin(depth);
1078 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply);
1080 // Logically we should return (v + razor_margin(depth)), but
1081 // surprisingly this did slightly weaker in tests.
1085 // Step 7. Static null move pruning (is omitted in PV nodes)
1086 // We're betting that the opponent doesn't have a move that will reduce
1087 // the score by more than futility_margin(depth) if we do a null move.
1089 && !ss->skipNullMove
1090 && depth < RazorDepth
1092 && refinedValue >= beta + futility_margin(depth, 0)
1093 && !value_is_mate(beta)
1094 && pos.non_pawn_material(pos.side_to_move()))
1095 return refinedValue - futility_margin(depth, 0);
1097 // Step 8. Null move search with verification search (is omitted in PV nodes)
1099 && !ss->skipNullMove
1102 && refinedValue >= beta
1103 && !value_is_mate(beta)
1104 && pos.non_pawn_material(pos.side_to_move()))
1106 ss->currentMove = MOVE_NULL;
1108 // Null move dynamic reduction based on depth
1109 int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);
1111 // Null move dynamic reduction based on value
1112 if (refinedValue - beta > PawnValueMidgame)
1115 pos.do_null_move(st);
1116 (ss+1)->skipNullMove = true;
1117 nullValue = -search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1);
1118 (ss+1)->skipNullMove = false;
1119 pos.undo_null_move();
1121 if (nullValue >= beta)
1123 // Do not return unproven mate scores
1124 if (nullValue >= value_mate_in(PLY_MAX))
1127 if (depth < 6 * ONE_PLY)
1130 // Do verification search at high depths
1131 ss->skipNullMove = true;
1132 Value v = search<NonPV>(pos, ss, alpha, beta, depth-R*ONE_PLY, ply);
1133 ss->skipNullMove = false;
1140 // The null move failed low, which means that we may be faced with
1141 // some kind of threat. If the previous move was reduced, check if
1142 // the move that refuted the null move was somehow connected to the
1143 // move which was reduced. If a connection is found, return a fail
1144 // low score (which will cause the reduced move to fail high in the
1145 // parent node, which will trigger a re-search with full depth).
1146 if (nullValue == value_mated_in(ply + 2))
1149 threatMove = (ss+1)->bestMove;
1150 if ( depth < ThreatDepth
1151 && (ss-1)->reduction
1152 && connected_moves(pos, (ss-1)->currentMove, threatMove))
1157 // Step 9. Internal iterative deepening
1158 if ( depth >= IIDDepth[PvNode]
1159 && ttMove == MOVE_NONE
1160 && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
1162 Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);
1164 ss->skipNullMove = true;
1165 search<PvNode>(pos, ss, alpha, beta, d, ply);
1166 ss->skipNullMove = false;
1168 ttMove = ss->bestMove;
1169 tte = TT.retrieve(posKey);
1172 // Expensive mate threat detection (only for PV nodes)
1174 mateThreat = pos.has_mate_threat();
1176 split_point_start: // At split points actual search starts from here
1178 // Initialize a MovePicker object for the current position
1179 // FIXME currently MovePicker() c'tor is needless called also in SplitPoint
1180 MovePicker mpBase(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
1181 MovePicker& mp = SpNode ? *sp->mp : mpBase;
1183 ss->bestMove = MOVE_NONE;
1184 singleEvasion = !SpNode && isCheck && mp.number_of_evasions() == 1;
1185 futilityBase = ss->eval + ss->evalMargin;
1186 singularExtensionNode = !SpNode
1187 && depth >= SingularExtensionDepth[PvNode]
1190 && !excludedMove // Do not allow recursive singular extension search
1191 && (tte->type() & VALUE_TYPE_LOWER)
1192 && tte->depth() >= depth - 3 * ONE_PLY;
1195 lock_grab(&(sp->lock));
1196 bestValue = sp->bestValue;
1199 // Step 10. Loop through moves
1200 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1201 while ( bestValue < beta
1202 && (move = mp.get_next_move()) != MOVE_NONE
1203 && !ThreadsMgr.thread_should_stop(threadID))
1205 assert(move_is_ok(move));
1209 moveCount = ++sp->moveCount;
1210 lock_release(&(sp->lock));
1212 else if (move == excludedMove)
1215 movesSearched[moveCount++] = move;
1217 moveIsCheck = pos.move_is_check(move, ci);
1218 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1220 // Step 11. Decide the new search depth
1221 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1223 // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s),
1224 // and just one fails high on (alpha, beta), then that move is singular and should be extended.
1225 // To verify this we do a reduced search on all the other moves but the ttMove, if result is
1226 // lower then ttValue minus a margin then we extend ttMove.
1227 if ( singularExtensionNode
1228 && move == tte->move()
1231 Value ttValue = value_from_tt(tte->value(), ply);
1233 if (abs(ttValue) < VALUE_KNOWN_WIN)
1235 Value b = ttValue - SingularExtensionMargin;
1236 ss->excludedMove = move;
1237 ss->skipNullMove = true;
1238 Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
1239 ss->skipNullMove = false;
1240 ss->excludedMove = MOVE_NONE;
1241 ss->bestMove = MOVE_NONE;
1247 // Update current move (this must be done after singular extension search)
1248 ss->currentMove = move;
1249 newDepth = depth - ONE_PLY + ext;
1251 // Step 12. Futility pruning (is omitted in PV nodes)
1253 && !captureOrPromotion
1257 && !move_is_castle(move))
1259 // Move count based pruning
1260 if ( moveCount >= futility_move_count(depth)
1261 && !(threatMove && connected_threat(pos, move, threatMove))
1262 && bestValue > value_mated_in(PLY_MAX)) // FIXME bestValue is racy
1265 lock_grab(&(sp->lock));
1270 // Value based pruning
1271 // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth,
1272 // but fixing this made program slightly weaker.
1273 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount);
1274 futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount)
1275 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1277 if (futilityValueScaled < beta)
1281 lock_grab(&(sp->lock));
1282 if (futilityValueScaled > sp->bestValue)
1283 sp->bestValue = bestValue = futilityValueScaled;
1285 else if (futilityValueScaled > bestValue)
1286 bestValue = futilityValueScaled;
1292 // Step 13. Make the move
1293 pos.do_move(move, st, ci, moveIsCheck);
1295 // Step extra. pv search (only in PV nodes)
1296 // The first move in list is the expected PV
1297 if (!SpNode && PvNode && moveCount == 1)
1298 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1301 // Step 14. Reduced depth search
1302 // If the move fails high will be re-searched at full depth.
1303 bool doFullDepthSearch = true;
1305 if ( depth >= 3 * ONE_PLY
1306 && !captureOrPromotion
1308 && !move_is_castle(move)
1309 && !(ss->killers[0] == move || ss->killers[1] == move))
1311 ss->reduction = reduction<PvNode>(depth, moveCount);
1314 alpha = SpNode ? sp->alpha : alpha;
1315 Depth d = newDepth - ss->reduction;
1316 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1318 doFullDepthSearch = (value > alpha);
1321 // The move failed high, but if reduction is very big we could
1322 // face a false positive, retry with a less aggressive reduction,
1323 // if the move fails high again then go with full depth search.
1324 if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
1326 assert(newDepth - ONE_PLY >= ONE_PLY);
1328 ss->reduction = ONE_PLY;
1329 alpha = SpNode ? sp->alpha : alpha;
1330 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, ply+1);
1331 doFullDepthSearch = (value > alpha);
1333 ss->reduction = DEPTH_ZERO; // Restore original reduction
1336 // Step 15. Full depth search
1337 if (doFullDepthSearch)
1339 alpha = SpNode ? sp->alpha : alpha;
1340 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1342 // Step extra. pv search (only in PV nodes)
1343 // Search only for possible new PV nodes, if instead value >= beta then
1344 // parent node fails low with value <= alpha and tries another move.
1345 if (PvNode && value > alpha && value < beta)
1346 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1350 // Step 16. Undo move
1351 pos.undo_move(move);
1353 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1355 // Step 17. Check for new best move
1358 lock_grab(&(sp->lock));
1359 bestValue = sp->bestValue;
1363 if (value > bestValue && !(SpNode && ThreadsMgr.thread_should_stop(threadID)))
1368 sp->bestValue = value;
1372 if (SpNode && (!PvNode || value >= beta))
1373 sp->stopRequest = true;
1375 if (PvNode && value < beta) // We want always alpha < beta
1382 if (value == value_mate_in(ply + 1))
1383 ss->mateKiller = move;
1385 ss->bestMove = move;
1388 sp->parentSstack->bestMove = move;
1392 // Step 18. Check for split
1394 && depth >= MinimumSplitDepth
1395 && ThreadsMgr.active_threads() > 1
1397 && ThreadsMgr.available_thread_exists(threadID)
1399 && !ThreadsMgr.thread_should_stop(threadID)
1401 ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1402 threatMove, mateThreat, moveCount, &mp, PvNode);
1405 // Step 19. Check for mate and stalemate
1406 // All legal moves have been searched and if there are
1407 // no legal moves, it must be mate or stalemate.
1408 // If one move was excluded return fail low score.
1409 if (!SpNode && !moveCount)
1410 return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW;
1412 // Step 20. Update tables
1413 // If the search is not aborted, update the transposition table,
1414 // history counters, and killer moves.
1415 if (!SpNode && !AbortSearch && !ThreadsMgr.thread_should_stop(threadID))
1417 move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
1418 vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
1419 : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
1421 TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, ss->evalMargin);
1423 // Update killers and history only for non capture moves that fails high
1424 if ( bestValue >= beta
1425 && !pos.move_is_capture_or_promotion(move))
1427 update_history(pos, move, depth, movesSearched, moveCount);
1428 update_killers(move, ss);
1434 // Here we have the lock still grabbed
1435 sp->slaves[threadID] = 0;
1436 sp->nodes += pos.nodes_searched();
1437 lock_release(&(sp->lock));
1440 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1446 // qsearch() is the quiescence search function, which is called by the main
1447 // search function when the remaining depth is zero (or, to be more precise,
1448 // less than ONE_PLY).
1450 template <NodeType PvNode>
1451 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1453 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1454 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1455 assert(PvNode || alpha == beta - 1);
1457 assert(ply > 0 && ply < PLY_MAX);
1458 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1462 Value bestValue, value, evalMargin, futilityValue, futilityBase;
1463 bool isCheck, deepChecks, enoughMaterial, moveIsCheck, evasionPrunable;
1465 Value oldAlpha = alpha;
1467 ss->bestMove = ss->currentMove = MOVE_NONE;
1469 // Check for an instant draw or maximum ply reached
1470 if (pos.is_draw() || ply >= PLY_MAX - 1)
1473 // Transposition table lookup. At PV nodes, we don't use the TT for
1474 // pruning, but only for move ordering.
1475 tte = TT.retrieve(pos.get_key());
1476 ttMove = (tte ? tte->move() : MOVE_NONE);
1478 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1480 ss->bestMove = ttMove; // Can be MOVE_NONE
1481 return value_from_tt(tte->value(), ply);
1484 isCheck = pos.is_check();
1486 // Evaluate the position statically
1489 bestValue = futilityBase = -VALUE_INFINITE;
1490 ss->eval = evalMargin = VALUE_NONE;
1491 deepChecks = enoughMaterial = false;
1497 assert(tte->static_value() != VALUE_NONE);
1499 evalMargin = tte->static_value_margin();
1500 ss->eval = bestValue = tte->static_value();
1503 ss->eval = bestValue = evaluate(pos, evalMargin);
1505 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1507 // Stand pat. Return immediately if static value is at least beta
1508 if (bestValue >= beta)
1511 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1516 if (PvNode && bestValue > alpha)
1519 // If we are near beta then try to get a cutoff pushing checks a bit further
1520 deepChecks = (depth == -ONE_PLY && bestValue >= beta - PawnValueMidgame / 8);
1522 // Futility pruning parameters, not needed when in check
1523 futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1524 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1527 // Initialize a MovePicker object for the current position, and prepare
1528 // to search the moves. Because the depth is <= 0 here, only captures,
1529 // queen promotions and checks (only if depth == 0 or depth == -ONE_PLY
1530 // and we are near beta) will be generated.
1531 MovePicker mp = MovePicker(pos, ttMove, deepChecks ? DEPTH_ZERO : depth, H);
1534 // Loop through the moves until no moves remain or a beta cutoff occurs
1535 while ( alpha < beta
1536 && (move = mp.get_next_move()) != MOVE_NONE)
1538 assert(move_is_ok(move));
1540 moveIsCheck = pos.move_is_check(move, ci);
1548 && !move_is_promotion(move)
1549 && !pos.move_is_passed_pawn_push(move))
1551 futilityValue = futilityBase
1552 + pos.endgame_value_of_piece_on(move_to(move))
1553 + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1555 if (futilityValue < alpha)
1557 if (futilityValue > bestValue)
1558 bestValue = futilityValue;
1563 // Detect non-capture evasions that are candidate to be pruned
1564 evasionPrunable = isCheck
1565 && bestValue > value_mated_in(PLY_MAX)
1566 && !pos.move_is_capture(move)
1567 && !pos.can_castle(pos.side_to_move());
1569 // Don't search moves with negative SEE values
1571 && (!isCheck || evasionPrunable)
1573 && !move_is_promotion(move)
1574 && pos.see_sign(move) < 0)
1577 // Update current move
1578 ss->currentMove = move;
1580 // Make and search the move
1581 pos.do_move(move, st, ci, moveIsCheck);
1582 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1);
1583 pos.undo_move(move);
1585 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1588 if (value > bestValue)
1594 ss->bestMove = move;
1599 // All legal moves have been searched. A special case: If we're in check
1600 // and no legal moves were found, it is checkmate.
1601 if (isCheck && bestValue == -VALUE_INFINITE)
1602 return value_mated_in(ply);
1604 // Update transposition table
1605 Depth d = (depth == DEPTH_ZERO ? DEPTH_ZERO : DEPTH_ZERO - ONE_PLY);
1606 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1607 TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, d, ss->bestMove, ss->eval, evalMargin);
1609 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1615 // connected_moves() tests whether two moves are 'connected' in the sense
1616 // that the first move somehow made the second move possible (for instance
1617 // if the moving piece is the same in both moves). The first move is assumed
1618 // to be the move that was made to reach the current position, while the
1619 // second move is assumed to be a move from the current position.
1621 bool connected_moves(const Position& pos, Move m1, Move m2) {
1623 Square f1, t1, f2, t2;
1626 assert(move_is_ok(m1));
1627 assert(move_is_ok(m2));
1629 if (m2 == MOVE_NONE)
1632 // Case 1: The moving piece is the same in both moves
1638 // Case 2: The destination square for m2 was vacated by m1
1644 // Case 3: Moving through the vacated square
1645 if ( piece_is_slider(pos.piece_on(f2))
1646 && bit_is_set(squares_between(f2, t2), f1))
1649 // Case 4: The destination square for m2 is defended by the moving piece in m1
1650 p = pos.piece_on(t1);
1651 if (bit_is_set(pos.attacks_from(p, t1), t2))
1654 // Case 5: Discovered check, checking piece is the piece moved in m1
1655 if ( piece_is_slider(p)
1656 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1657 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1659 // discovered_check_candidates() works also if the Position's side to
1660 // move is the opposite of the checking piece.
1661 Color them = opposite_color(pos.side_to_move());
1662 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1664 if (bit_is_set(dcCandidates, f2))
1671 // value_is_mate() checks if the given value is a mate one eventually
1672 // compensated for the ply.
1674 bool value_is_mate(Value value) {
1676 assert(abs(value) <= VALUE_INFINITE);
1678 return value <= value_mated_in(PLY_MAX)
1679 || value >= value_mate_in(PLY_MAX);
1683 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1684 // "plies to mate from the current ply". Non-mate scores are unchanged.
1685 // The function is called before storing a value to the transposition table.
1687 Value value_to_tt(Value v, int ply) {
1689 if (v >= value_mate_in(PLY_MAX))
1692 if (v <= value_mated_in(PLY_MAX))
1699 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1700 // the transposition table to a mate score corrected for the current ply.
1702 Value value_from_tt(Value v, int ply) {
1704 if (v >= value_mate_in(PLY_MAX))
1707 if (v <= value_mated_in(PLY_MAX))
1714 // extension() decides whether a move should be searched with normal depth,
1715 // or with extended depth. Certain classes of moves (checking moves, in
1716 // particular) are searched with bigger depth than ordinary moves and in
1717 // any case are marked as 'dangerous'. Note that also if a move is not
1718 // extended, as example because the corresponding UCI option is set to zero,
1719 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1720 template <NodeType PvNode>
1721 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1722 bool singleEvasion, bool mateThreat, bool* dangerous) {
1724 assert(m != MOVE_NONE);
1726 Depth result = DEPTH_ZERO;
1727 *dangerous = moveIsCheck | singleEvasion | mateThreat;
1731 if (moveIsCheck && pos.see_sign(m) >= 0)
1732 result += CheckExtension[PvNode];
1735 result += SingleEvasionExtension[PvNode];
1738 result += MateThreatExtension[PvNode];
1741 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1743 Color c = pos.side_to_move();
1744 if (relative_rank(c, move_to(m)) == RANK_7)
1746 result += PawnPushTo7thExtension[PvNode];
1749 if (pos.pawn_is_passed(c, move_to(m)))
1751 result += PassedPawnExtension[PvNode];
1756 if ( captureOrPromotion
1757 && pos.type_of_piece_on(move_to(m)) != PAWN
1758 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1759 - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1760 && !move_is_promotion(m)
1763 result += PawnEndgameExtension[PvNode];
1768 && captureOrPromotion
1769 && pos.type_of_piece_on(move_to(m)) != PAWN
1770 && pos.see_sign(m) >= 0)
1772 result += ONE_PLY / 2;
1776 return Min(result, ONE_PLY);
1780 // connected_threat() tests whether it is safe to forward prune a move or if
1781 // is somehow coonected to the threat move returned by null search.
1783 bool connected_threat(const Position& pos, Move m, Move threat) {
1785 assert(move_is_ok(m));
1786 assert(threat && move_is_ok(threat));
1787 assert(!pos.move_is_check(m));
1788 assert(!pos.move_is_capture_or_promotion(m));
1789 assert(!pos.move_is_passed_pawn_push(m));
1791 Square mfrom, mto, tfrom, tto;
1793 mfrom = move_from(m);
1795 tfrom = move_from(threat);
1796 tto = move_to(threat);
1798 // Case 1: Don't prune moves which move the threatened piece
1802 // Case 2: If the threatened piece has value less than or equal to the
1803 // value of the threatening piece, don't prune move which defend it.
1804 if ( pos.move_is_capture(threat)
1805 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1806 || pos.type_of_piece_on(tfrom) == KING)
1807 && pos.move_attacks_square(m, tto))
1810 // Case 3: If the moving piece in the threatened move is a slider, don't
1811 // prune safe moves which block its ray.
1812 if ( piece_is_slider(pos.piece_on(tfrom))
1813 && bit_is_set(squares_between(tfrom, tto), mto)
1814 && pos.see_sign(m) >= 0)
1821 // ok_to_use_TT() returns true if a transposition table score
1822 // can be used at a given point in search.
1824 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1826 Value v = value_from_tt(tte->value(), ply);
1828 return ( tte->depth() >= depth
1829 || v >= Max(value_mate_in(PLY_MAX), beta)
1830 || v < Min(value_mated_in(PLY_MAX), beta))
1832 && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1833 || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1837 // refine_eval() returns the transposition table score if
1838 // possible otherwise falls back on static position evaluation.
1840 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1844 Value v = value_from_tt(tte->value(), ply);
1846 if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1847 || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1854 // update_history() registers a good move that produced a beta-cutoff
1855 // in history and marks as failures all the other moves of that ply.
1857 void update_history(const Position& pos, Move move, Depth depth,
1858 Move movesSearched[], int moveCount) {
1861 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
1863 for (int i = 0; i < moveCount - 1; i++)
1865 m = movesSearched[i];
1869 if (!pos.move_is_capture_or_promotion(m))
1870 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
1875 // update_killers() add a good move that produced a beta-cutoff
1876 // among the killer moves of that ply.
1878 void update_killers(Move m, SearchStack* ss) {
1880 if (m == ss->killers[0])
1883 ss->killers[1] = ss->killers[0];
1888 // update_gains() updates the gains table of a non-capture move given
1889 // the static position evaluation before and after the move.
1891 void update_gains(const Position& pos, Move m, Value before, Value after) {
1894 && before != VALUE_NONE
1895 && after != VALUE_NONE
1896 && pos.captured_piece_type() == PIECE_TYPE_NONE
1897 && !move_is_special(m))
1898 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
1902 // current_search_time() returns the number of milliseconds which have passed
1903 // since the beginning of the current search.
1905 int current_search_time() {
1907 return get_system_time() - SearchStartTime;
1911 // value_to_uci() converts a value to a string suitable for use with the UCI protocol
1913 std::string value_to_uci(Value v) {
1915 std::stringstream s;
1917 if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
1918 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100
1920 s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
1925 // nps() computes the current nodes/second count.
1927 int nps(const Position& pos) {
1929 int t = current_search_time();
1930 return (t > 0 ? int((pos.nodes_searched() * 1000) / t) : 0);
1934 // poll() performs two different functions: It polls for user input, and it
1935 // looks at the time consumed so far and decides if it's time to abort the
1938 void poll(const Position& pos) {
1940 static int lastInfoTime;
1941 int t = current_search_time();
1944 if (data_available())
1946 // We are line oriented, don't read single chars
1947 std::string command;
1949 if (!std::getline(std::cin, command))
1952 if (command == "quit")
1955 PonderSearch = false;
1959 else if (command == "stop")
1962 PonderSearch = false;
1964 else if (command == "ponderhit")
1968 // Print search information
1972 else if (lastInfoTime > t)
1973 // HACK: Must be a new search where we searched less than
1974 // NodesBetweenPolls nodes during the first second of search.
1977 else if (t - lastInfoTime >= 1000)
1984 if (dbg_show_hit_rate)
1985 dbg_print_hit_rate();
1987 cout << "info nodes " << pos.nodes_searched() << " nps " << nps(pos)
1988 << " time " << t << endl;
1991 // Should we stop the search?
1995 bool stillAtFirstMove = FirstRootMove
1996 && !AspirationFailLow
1997 && t > TimeMgr.available_time();
1999 bool noMoreTime = t > TimeMgr.maximum_time()
2000 || stillAtFirstMove;
2002 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2003 || (ExactMaxTime && t >= ExactMaxTime)
2004 || (Iteration >= 3 && MaxNodes && pos.nodes_searched() >= MaxNodes))
2009 // ponderhit() is called when the program is pondering (i.e. thinking while
2010 // it's the opponent's turn to move) in order to let the engine know that
2011 // it correctly predicted the opponent's move.
2015 int t = current_search_time();
2016 PonderSearch = false;
2018 bool stillAtFirstMove = FirstRootMove
2019 && !AspirationFailLow
2020 && t > TimeMgr.available_time();
2022 bool noMoreTime = t > TimeMgr.maximum_time()
2023 || stillAtFirstMove;
2025 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2030 // init_ss_array() does a fast reset of the first entries of a SearchStack
2031 // array and of all the excludedMove and skipNullMove entries.
2033 void init_ss_array(SearchStack* ss, int size) {
2035 for (int i = 0; i < size; i++, ss++)
2037 ss->excludedMove = MOVE_NONE;
2038 ss->skipNullMove = false;
2039 ss->reduction = DEPTH_ZERO;
2043 ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE;
2048 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2049 // while the program is pondering. The point is to work around a wrinkle in
2050 // the UCI protocol: When pondering, the engine is not allowed to give a
2051 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2052 // We simply wait here until one of these commands is sent, and return,
2053 // after which the bestmove and pondermove will be printed (in id_loop()).
2055 void wait_for_stop_or_ponderhit() {
2057 std::string command;
2061 if (!std::getline(std::cin, command))
2064 if (command == "quit")
2069 else if (command == "ponderhit" || command == "stop")
2075 // print_pv_info() prints to standard output and eventually to log file information on
2076 // the current PV line. It is called at each iteration or after a new pv is found.
2078 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) {
2080 cout << "info depth " << Iteration
2081 << " score " << value_to_uci(value)
2082 << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
2083 << " time " << current_search_time()
2084 << " nodes " << pos.nodes_searched()
2085 << " nps " << nps(pos)
2088 for (Move* m = pv; *m != MOVE_NONE; m++)
2095 ValueType t = value >= beta ? VALUE_TYPE_LOWER :
2096 value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
2098 LogFile << pretty_pv(pos, current_search_time(), Iteration, value, t, pv) << endl;
2103 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2104 // the PV back into the TT. This makes sure the old PV moves are searched
2105 // first, even if the old TT entries have been overwritten.
2107 void insert_pv_in_tt(const Position& pos, Move pv[]) {
2111 Position p(pos, pos.thread());
2112 Value v, m = VALUE_NONE;
2114 for (int i = 0; pv[i] != MOVE_NONE; i++)
2116 tte = TT.retrieve(p.get_key());
2117 if (!tte || tte->move() != pv[i])
2119 v = (p.is_check() ? VALUE_NONE : evaluate(p, m));
2120 TT.store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[i], v, m);
2122 p.do_move(pv[i], st);
2127 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2128 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2129 // allow to always have a ponder move even when we fail high at root and also a
2130 // long PV to print that is important for position analysis.
2132 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]) {
2136 Position p(pos, pos.thread());
2139 assert(bestMove != MOVE_NONE);
2142 p.do_move(pv[ply++], st);
2144 while ( (tte = TT.retrieve(p.get_key())) != NULL
2145 && tte->move() != MOVE_NONE
2146 && move_is_legal(p, tte->move())
2148 && (!p.is_draw() || ply < 2))
2150 pv[ply] = tte->move();
2151 p.do_move(pv[ply++], st);
2153 pv[ply] = MOVE_NONE;
2157 // init_thread() is the function which is called when a new thread is
2158 // launched. It simply calls the idle_loop() function with the supplied
2159 // threadID. There are two versions of this function; one for POSIX
2160 // threads and one for Windows threads.
2162 #if !defined(_MSC_VER)
2164 void* init_thread(void* threadID) {
2166 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2172 DWORD WINAPI init_thread(LPVOID threadID) {
2174 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2181 /// The ThreadsManager class
2184 // idle_loop() is where the threads are parked when they have no work to do.
2185 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2186 // object for which the current thread is the master.
2188 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2190 assert(threadID >= 0 && threadID < MAX_THREADS);
2194 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2195 // master should exit as last one.
2196 if (AllThreadsShouldExit)
2199 threads[threadID].state = THREAD_TERMINATED;
2203 // If we are not thinking, wait for a condition to be signaled
2204 // instead of wasting CPU time polling for work.
2205 while (threadID >= ActiveThreads || threads[threadID].state == THREAD_INITIALIZING)
2208 assert(threadID != 0);
2210 if (AllThreadsShouldExit)
2213 threads[threadID].state = THREAD_AVAILABLE;
2215 lock_grab(&WaitLock);
2217 if (threadID >= ActiveThreads || threads[threadID].state == THREAD_INITIALIZING)
2218 cond_wait(&WaitCond[threadID], &WaitLock);
2220 lock_release(&WaitLock);
2223 // If this thread has been assigned work, launch a search
2224 if (threads[threadID].state == THREAD_WORKISWAITING)
2226 assert(!AllThreadsShouldExit);
2228 threads[threadID].state = THREAD_SEARCHING;
2230 // Here we call search() with SplitPoint template parameter set to true
2231 SplitPoint* tsp = threads[threadID].splitPoint;
2232 Position pos(*tsp->pos, threadID);
2233 SearchStack* ss = tsp->sstack[threadID] + 1;
2237 search<PV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2239 search<NonPV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2241 assert(threads[threadID].state == THREAD_SEARCHING);
2243 threads[threadID].state = THREAD_AVAILABLE;
2246 // If this thread is the master of a split point and all slaves have
2247 // finished their work at this split point, return from the idle loop.
2249 for ( ; sp && i < ActiveThreads && !sp->slaves[i]; i++) {}
2251 if (i == ActiveThreads)
2253 // Because sp->slaves[] is reset under lock protection,
2254 // be sure sp->lock has been released before to return.
2255 lock_grab(&(sp->lock));
2256 lock_release(&(sp->lock));
2258 // In helpful master concept a master can help only a sub-tree, and
2259 // because here is all finished is not possible master is booked.
2260 assert(threads[threadID].state == THREAD_AVAILABLE);
2262 threads[threadID].state = THREAD_SEARCHING;
2269 // init_threads() is called during startup. It launches all helper threads,
2270 // and initializes the split point stack and the global locks and condition
2273 void ThreadsManager::init_threads() {
2275 int i, arg[MAX_THREADS];
2278 // Initialize global locks
2280 lock_init(&WaitLock);
2282 for (i = 0; i < MAX_THREADS; i++)
2283 cond_init(&WaitCond[i]);
2285 // Initialize splitPoints[] locks
2286 for (i = 0; i < MAX_THREADS; i++)
2287 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2288 lock_init(&(threads[i].splitPoints[j].lock));
2290 // Will be set just before program exits to properly end the threads
2291 AllThreadsShouldExit = false;
2293 // Threads will be put all threads to sleep as soon as created
2296 // All threads except the main thread should be initialized to THREAD_INITIALIZING
2297 threads[0].state = THREAD_SEARCHING;
2298 for (i = 1; i < MAX_THREADS; i++)
2299 threads[i].state = THREAD_INITIALIZING;
2301 // Launch the helper threads
2302 for (i = 1; i < MAX_THREADS; i++)
2306 #if !defined(_MSC_VER)
2307 pthread_t pthread[1];
2308 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
2309 pthread_detach(pthread[0]);
2311 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
2315 cout << "Failed to create thread number " << i << endl;
2319 // Wait until the thread has finished launching and is gone to sleep
2320 while (threads[i].state == THREAD_INITIALIZING) {}
2325 // exit_threads() is called when the program exits. It makes all the
2326 // helper threads exit cleanly.
2328 void ThreadsManager::exit_threads() {
2330 AllThreadsShouldExit = true; // Let the woken up threads to exit idle_loop()
2332 // Wake up all the threads and waits for termination
2333 for (int i = 1; i < MAX_THREADS; i++)
2335 wake_sleeping_thread(i);
2336 while (threads[i].state != THREAD_TERMINATED) {}
2339 // Now we can safely destroy the locks
2340 for (int i = 0; i < MAX_THREADS; i++)
2341 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2342 lock_destroy(&(threads[i].splitPoints[j].lock));
2344 lock_destroy(&WaitLock);
2345 lock_destroy(&MPLock);
2347 // Now we can safely destroy the wait conditions
2348 for (int i = 0; i < MAX_THREADS; i++)
2349 cond_destroy(&WaitCond[i]);
2353 // thread_should_stop() checks whether the thread should stop its search.
2354 // This can happen if a beta cutoff has occurred in the thread's currently
2355 // active split point, or in some ancestor of the current split point.
2357 bool ThreadsManager::thread_should_stop(int threadID) const {
2359 assert(threadID >= 0 && threadID < ActiveThreads);
2361 SplitPoint* sp = threads[threadID].splitPoint;
2363 for ( ; sp && !sp->stopRequest; sp = sp->parent) {}
2368 // thread_is_available() checks whether the thread with threadID "slave" is
2369 // available to help the thread with threadID "master" at a split point. An
2370 // obvious requirement is that "slave" must be idle. With more than two
2371 // threads, this is not by itself sufficient: If "slave" is the master of
2372 // some active split point, it is only available as a slave to the other
2373 // threads which are busy searching the split point at the top of "slave"'s
2374 // split point stack (the "helpful master concept" in YBWC terminology).
2376 bool ThreadsManager::thread_is_available(int slave, int master) const {
2378 assert(slave >= 0 && slave < ActiveThreads);
2379 assert(master >= 0 && master < ActiveThreads);
2380 assert(ActiveThreads > 1);
2382 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2385 // Make a local copy to be sure doesn't change under our feet
2386 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2388 // No active split points means that the thread is available as
2389 // a slave for any other thread.
2390 if (localActiveSplitPoints == 0 || ActiveThreads == 2)
2393 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2394 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2395 // could have been set to 0 by another thread leading to an out of bound access.
2396 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2403 // available_thread_exists() tries to find an idle thread which is available as
2404 // a slave for the thread with threadID "master".
2406 bool ThreadsManager::available_thread_exists(int master) const {
2408 assert(master >= 0 && master < ActiveThreads);
2409 assert(ActiveThreads > 1);
2411 for (int i = 0; i < ActiveThreads; i++)
2412 if (thread_is_available(i, master))
2419 // split() does the actual work of distributing the work at a node between
2420 // several available threads. If it does not succeed in splitting the
2421 // node (because no idle threads are available, or because we have no unused
2422 // split point objects), the function immediately returns. If splitting is
2423 // possible, a SplitPoint object is initialized with all the data that must be
2424 // copied to the helper threads and we tell our helper threads that they have
2425 // been assigned work. This will cause them to instantly leave their idle loops and
2426 // call search().When all threads have returned from search() then split() returns.
2428 template <bool Fake>
2429 void ThreadsManager::split(Position& pos, SearchStack* ss, int ply, Value* alpha,
2430 const Value beta, Value* bestValue, Depth depth, Move threatMove,
2431 bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) {
2432 assert(pos.is_ok());
2433 assert(ply > 0 && ply < PLY_MAX);
2434 assert(*bestValue >= -VALUE_INFINITE);
2435 assert(*bestValue <= *alpha);
2436 assert(*alpha < beta);
2437 assert(beta <= VALUE_INFINITE);
2438 assert(depth > DEPTH_ZERO);
2439 assert(pos.thread() >= 0 && pos.thread() < ActiveThreads);
2440 assert(ActiveThreads > 1);
2442 int i, master = pos.thread();
2443 Thread& masterThread = threads[master];
2447 // If no other thread is available to help us, or if we have too many
2448 // active split points, don't split.
2449 if ( !available_thread_exists(master)
2450 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2452 lock_release(&MPLock);
2456 // Pick the next available split point object from the split point stack
2457 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2459 // Initialize the split point object
2460 splitPoint.parent = masterThread.splitPoint;
2461 splitPoint.stopRequest = false;
2462 splitPoint.ply = ply;
2463 splitPoint.depth = depth;
2464 splitPoint.threatMove = threatMove;
2465 splitPoint.mateThreat = mateThreat;
2466 splitPoint.alpha = *alpha;
2467 splitPoint.beta = beta;
2468 splitPoint.pvNode = pvNode;
2469 splitPoint.bestValue = *bestValue;
2471 splitPoint.moveCount = moveCount;
2472 splitPoint.pos = &pos;
2473 splitPoint.nodes = 0;
2474 splitPoint.parentSstack = ss;
2475 for (i = 0; i < ActiveThreads; i++)
2476 splitPoint.slaves[i] = 0;
2478 masterThread.splitPoint = &splitPoint;
2480 // If we are here it means we are not available
2481 assert(masterThread.state != THREAD_AVAILABLE);
2483 int workersCnt = 1; // At least the master is included
2485 // Allocate available threads setting state to THREAD_BOOKED
2486 for (i = 0; !Fake && i < ActiveThreads && workersCnt < MaxThreadsPerSplitPoint; i++)
2487 if (thread_is_available(i, master))
2489 threads[i].state = THREAD_BOOKED;
2490 threads[i].splitPoint = &splitPoint;
2491 splitPoint.slaves[i] = 1;
2495 assert(Fake || workersCnt > 1);
2497 // We can release the lock because slave threads are already booked and master is not available
2498 lock_release(&MPLock);
2500 // Tell the threads that they have work to do. This will make them leave
2501 // their idle loop. But before copy search stack tail for each thread.
2502 for (i = 0; i < ActiveThreads; i++)
2503 if (i == master || splitPoint.slaves[i])
2505 memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
2507 assert(i == master || threads[i].state == THREAD_BOOKED);
2509 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2512 // Everything is set up. The master thread enters the idle loop, from
2513 // which it will instantly launch a search, because its state is
2514 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2515 // idle loop, which means that the main thread will return from the idle
2516 // loop when all threads have finished their work at this split point.
2517 idle_loop(master, &splitPoint);
2519 // We have returned from the idle loop, which means that all threads are
2520 // finished. Update alpha and bestValue, and return.
2523 *alpha = splitPoint.alpha;
2524 *bestValue = splitPoint.bestValue;
2525 masterThread.activeSplitPoints--;
2526 masterThread.splitPoint = splitPoint.parent;
2527 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
2529 lock_release(&MPLock);
2533 // wake_sleeping_thread() wakes up all sleeping threads when it is time
2534 // to start a new search from the root.
2536 void ThreadsManager::wake_sleeping_thread(int threadID) {
2538 lock_grab(&WaitLock);
2539 cond_signal(&WaitCond[threadID]);
2540 lock_release(&WaitLock);
2544 /// The RootMoveList class
2546 // RootMoveList c'tor
2548 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) {
2550 SearchStack ss[PLY_MAX_PLUS_2];
2551 MoveStack mlist[MOVES_MAX];
2553 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
2555 // Initialize search stack
2556 init_ss_array(ss, PLY_MAX_PLUS_2);
2557 ss[0].eval = ss[0].evalMargin = VALUE_NONE;
2560 // Generate all legal moves
2561 MoveStack* last = generate_moves(pos, mlist);
2563 // Add each move to the moves[] array
2564 for (MoveStack* cur = mlist; cur != last; cur++)
2566 bool includeMove = includeAllMoves;
2568 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
2569 includeMove = (searchMoves[k] == cur->move);
2574 // Find a quick score for the move
2575 moves[count].move = ss[0].currentMove = moves[count].pv[0] = cur->move;
2576 moves[count].pv[1] = MOVE_NONE;
2577 pos.do_move(cur->move, st);
2578 moves[count].score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
2579 pos.undo_move(cur->move);
2585 // Score root moves using the standard way used in main search, the moves
2586 // are scored according to the order in which are returned by MovePicker.
2588 void RootMoveList::score_moves(const Position& pos)
2592 MovePicker mp = MovePicker(pos, MOVE_NONE, ONE_PLY, H);
2594 while ((move = mp.get_next_move()) != MOVE_NONE)
2595 for (int i = 0; i < count; i++)
2596 if (moves[i].move == move)
2598 moves[i].mp_score = score--;
2603 // RootMoveList simple methods definitions
2605 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
2609 for (j = 0; pv[j] != MOVE_NONE; j++)
2610 moves[moveNum].pv[j] = pv[j];
2612 moves[moveNum].pv[j] = MOVE_NONE;
2616 // RootMoveList::sort() sorts the root move list at the beginning of a new
2619 void RootMoveList::sort() {
2621 sort_multipv(count - 1); // Sort all items
2625 // RootMoveList::sort_multipv() sorts the first few moves in the root move
2626 // list by their scores and depths. It is used to order the different PVs
2627 // correctly in MultiPV mode.
2629 void RootMoveList::sort_multipv(int n) {
2633 for (i = 1; i <= n; i++)
2635 RootMove rm = moves[i];
2636 for (j = i; j > 0 && moves[j - 1] < rm; j--)
2637 moves[j] = moves[j - 1];