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;
1291 // Prune neg. see moves at low depths
1292 if ( predictedDepth < 2 * ONE_PLY
1293 && bestValue > value_mated_in(PLY_MAX)
1294 && pos.see_sign(move) < 0)
1297 lock_grab(&(sp->lock));
1303 // Step 13. Make the move
1304 pos.do_move(move, st, ci, moveIsCheck);
1306 // Step extra. pv search (only in PV nodes)
1307 // The first move in list is the expected PV
1308 if (!SpNode && PvNode && moveCount == 1)
1309 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1312 // Step 14. Reduced depth search
1313 // If the move fails high will be re-searched at full depth.
1314 bool doFullDepthSearch = true;
1316 if ( depth >= 3 * ONE_PLY
1317 && !captureOrPromotion
1319 && !move_is_castle(move)
1320 && !(ss->killers[0] == move || ss->killers[1] == move))
1322 ss->reduction = reduction<PvNode>(depth, moveCount);
1325 alpha = SpNode ? sp->alpha : alpha;
1326 Depth d = newDepth - ss->reduction;
1327 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, ply+1);
1329 doFullDepthSearch = (value > alpha);
1332 // The move failed high, but if reduction is very big we could
1333 // face a false positive, retry with a less aggressive reduction,
1334 // if the move fails high again then go with full depth search.
1335 if (doFullDepthSearch && ss->reduction > 2 * ONE_PLY)
1337 assert(newDepth - ONE_PLY >= ONE_PLY);
1339 ss->reduction = ONE_PLY;
1340 alpha = SpNode ? sp->alpha : alpha;
1341 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, ply+1);
1342 doFullDepthSearch = (value > alpha);
1344 ss->reduction = DEPTH_ZERO; // Restore original reduction
1347 // Step 15. Full depth search
1348 if (doFullDepthSearch)
1350 alpha = SpNode ? sp->alpha : alpha;
1351 value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1);
1353 // Step extra. pv search (only in PV nodes)
1354 // Search only for possible new PV nodes, if instead value >= beta then
1355 // parent node fails low with value <= alpha and tries another move.
1356 if (PvNode && value > alpha && value < beta)
1357 value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
1361 // Step 16. Undo move
1362 pos.undo_move(move);
1364 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1366 // Step 17. Check for new best move
1369 lock_grab(&(sp->lock));
1370 bestValue = sp->bestValue;
1374 if (value > bestValue && !(SpNode && ThreadsMgr.thread_should_stop(threadID)))
1379 sp->bestValue = value;
1383 if (SpNode && (!PvNode || value >= beta))
1384 sp->stopRequest = true;
1386 if (PvNode && value < beta) // We want always alpha < beta
1393 if (value == value_mate_in(ply + 1))
1394 ss->mateKiller = move;
1396 ss->bestMove = move;
1399 sp->parentSstack->bestMove = move;
1403 // Step 18. Check for split
1405 && depth >= MinimumSplitDepth
1406 && ThreadsMgr.active_threads() > 1
1408 && ThreadsMgr.available_thread_exists(threadID)
1410 && !ThreadsMgr.thread_should_stop(threadID)
1412 ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
1413 threatMove, mateThreat, moveCount, &mp, PvNode);
1416 // Step 19. Check for mate and stalemate
1417 // All legal moves have been searched and if there are
1418 // no legal moves, it must be mate or stalemate.
1419 // If one move was excluded return fail low score.
1420 if (!SpNode && !moveCount)
1421 return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW;
1423 // Step 20. Update tables
1424 // If the search is not aborted, update the transposition table,
1425 // history counters, and killer moves.
1426 if (!SpNode && !AbortSearch && !ThreadsMgr.thread_should_stop(threadID))
1428 move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
1429 vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
1430 : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT;
1432 TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, ss->evalMargin);
1434 // Update killers and history only for non capture moves that fails high
1435 if ( bestValue >= beta
1436 && !pos.move_is_capture_or_promotion(move))
1438 update_history(pos, move, depth, movesSearched, moveCount);
1439 update_killers(move, ss);
1445 // Here we have the lock still grabbed
1446 sp->slaves[threadID] = 0;
1447 sp->nodes += pos.nodes_searched();
1448 lock_release(&(sp->lock));
1451 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1457 // qsearch() is the quiescence search function, which is called by the main
1458 // search function when the remaining depth is zero (or, to be more precise,
1459 // less than ONE_PLY).
1461 template <NodeType PvNode>
1462 Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) {
1464 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1465 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1466 assert(PvNode || alpha == beta - 1);
1468 assert(ply > 0 && ply < PLY_MAX);
1469 assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads());
1473 Value bestValue, value, evalMargin, futilityValue, futilityBase;
1474 bool isCheck, deepChecks, enoughMaterial, moveIsCheck, evasionPrunable;
1476 Value oldAlpha = alpha;
1478 ss->bestMove = ss->currentMove = MOVE_NONE;
1480 // Check for an instant draw or maximum ply reached
1481 if (pos.is_draw() || ply >= PLY_MAX - 1)
1484 // Transposition table lookup. At PV nodes, we don't use the TT for
1485 // pruning, but only for move ordering.
1486 tte = TT.retrieve(pos.get_key());
1487 ttMove = (tte ? tte->move() : MOVE_NONE);
1489 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1491 ss->bestMove = ttMove; // Can be MOVE_NONE
1492 return value_from_tt(tte->value(), ply);
1495 isCheck = pos.is_check();
1497 // Evaluate the position statically
1500 bestValue = futilityBase = -VALUE_INFINITE;
1501 ss->eval = evalMargin = VALUE_NONE;
1502 deepChecks = enoughMaterial = false;
1508 assert(tte->static_value() != VALUE_NONE);
1510 evalMargin = tte->static_value_margin();
1511 ss->eval = bestValue = tte->static_value();
1514 ss->eval = bestValue = evaluate(pos, evalMargin);
1516 update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
1518 // Stand pat. Return immediately if static value is at least beta
1519 if (bestValue >= beta)
1522 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
1527 if (PvNode && bestValue > alpha)
1530 // If we are near beta then try to get a cutoff pushing checks a bit further
1531 deepChecks = (depth == -ONE_PLY && bestValue >= beta - PawnValueMidgame / 8);
1533 // Futility pruning parameters, not needed when in check
1534 futilityBase = ss->eval + evalMargin + FutilityMarginQS;
1535 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1538 // Initialize a MovePicker object for the current position, and prepare
1539 // to search the moves. Because the depth is <= 0 here, only captures,
1540 // queen promotions and checks (only if depth == 0 or depth == -ONE_PLY
1541 // and we are near beta) will be generated.
1542 MovePicker mp = MovePicker(pos, ttMove, deepChecks ? DEPTH_ZERO : depth, H);
1545 // Loop through the moves until no moves remain or a beta cutoff occurs
1546 while ( alpha < beta
1547 && (move = mp.get_next_move()) != MOVE_NONE)
1549 assert(move_is_ok(move));
1551 moveIsCheck = pos.move_is_check(move, ci);
1559 && !move_is_promotion(move)
1560 && !pos.move_is_passed_pawn_push(move))
1562 futilityValue = futilityBase
1563 + pos.endgame_value_of_piece_on(move_to(move))
1564 + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO);
1566 if (futilityValue < alpha)
1568 if (futilityValue > bestValue)
1569 bestValue = futilityValue;
1574 // Detect non-capture evasions that are candidate to be pruned
1575 evasionPrunable = isCheck
1576 && bestValue > value_mated_in(PLY_MAX)
1577 && !pos.move_is_capture(move)
1578 && !pos.can_castle(pos.side_to_move());
1580 // Don't search moves with negative SEE values
1582 && (!isCheck || evasionPrunable)
1584 && !move_is_promotion(move)
1585 && pos.see_sign(move) < 0)
1588 // Update current move
1589 ss->currentMove = move;
1591 // Make and search the move
1592 pos.do_move(move, st, ci, moveIsCheck);
1593 value = -qsearch<PvNode>(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1);
1594 pos.undo_move(move);
1596 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1599 if (value > bestValue)
1605 ss->bestMove = move;
1610 // All legal moves have been searched. A special case: If we're in check
1611 // and no legal moves were found, it is checkmate.
1612 if (isCheck && bestValue == -VALUE_INFINITE)
1613 return value_mated_in(ply);
1615 // Update transposition table
1616 Depth d = (depth == DEPTH_ZERO ? DEPTH_ZERO : DEPTH_ZERO - ONE_PLY);
1617 ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
1618 TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, d, ss->bestMove, ss->eval, evalMargin);
1620 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1626 // connected_moves() tests whether two moves are 'connected' in the sense
1627 // that the first move somehow made the second move possible (for instance
1628 // if the moving piece is the same in both moves). The first move is assumed
1629 // to be the move that was made to reach the current position, while the
1630 // second move is assumed to be a move from the current position.
1632 bool connected_moves(const Position& pos, Move m1, Move m2) {
1634 Square f1, t1, f2, t2;
1637 assert(move_is_ok(m1));
1638 assert(move_is_ok(m2));
1640 if (m2 == MOVE_NONE)
1643 // Case 1: The moving piece is the same in both moves
1649 // Case 2: The destination square for m2 was vacated by m1
1655 // Case 3: Moving through the vacated square
1656 if ( piece_is_slider(pos.piece_on(f2))
1657 && bit_is_set(squares_between(f2, t2), f1))
1660 // Case 4: The destination square for m2 is defended by the moving piece in m1
1661 p = pos.piece_on(t1);
1662 if (bit_is_set(pos.attacks_from(p, t1), t2))
1665 // Case 5: Discovered check, checking piece is the piece moved in m1
1666 if ( piece_is_slider(p)
1667 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1668 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1670 // discovered_check_candidates() works also if the Position's side to
1671 // move is the opposite of the checking piece.
1672 Color them = opposite_color(pos.side_to_move());
1673 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1675 if (bit_is_set(dcCandidates, f2))
1682 // value_is_mate() checks if the given value is a mate one eventually
1683 // compensated for the ply.
1685 bool value_is_mate(Value value) {
1687 assert(abs(value) <= VALUE_INFINITE);
1689 return value <= value_mated_in(PLY_MAX)
1690 || value >= value_mate_in(PLY_MAX);
1694 // value_to_tt() adjusts a mate score from "plies to mate from the root" to
1695 // "plies to mate from the current ply". Non-mate scores are unchanged.
1696 // The function is called before storing a value to the transposition table.
1698 Value value_to_tt(Value v, int ply) {
1700 if (v >= value_mate_in(PLY_MAX))
1703 if (v <= value_mated_in(PLY_MAX))
1710 // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
1711 // the transposition table to a mate score corrected for the current ply.
1713 Value value_from_tt(Value v, int ply) {
1715 if (v >= value_mate_in(PLY_MAX))
1718 if (v <= value_mated_in(PLY_MAX))
1725 // extension() decides whether a move should be searched with normal depth,
1726 // or with extended depth. Certain classes of moves (checking moves, in
1727 // particular) are searched with bigger depth than ordinary moves and in
1728 // any case are marked as 'dangerous'. Note that also if a move is not
1729 // extended, as example because the corresponding UCI option is set to zero,
1730 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1731 template <NodeType PvNode>
1732 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1733 bool singleEvasion, bool mateThreat, bool* dangerous) {
1735 assert(m != MOVE_NONE);
1737 Depth result = DEPTH_ZERO;
1738 *dangerous = moveIsCheck | singleEvasion | mateThreat;
1742 if (moveIsCheck && pos.see_sign(m) >= 0)
1743 result += CheckExtension[PvNode];
1746 result += SingleEvasionExtension[PvNode];
1749 result += MateThreatExtension[PvNode];
1752 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1754 Color c = pos.side_to_move();
1755 if (relative_rank(c, move_to(m)) == RANK_7)
1757 result += PawnPushTo7thExtension[PvNode];
1760 if (pos.pawn_is_passed(c, move_to(m)))
1762 result += PassedPawnExtension[PvNode];
1767 if ( captureOrPromotion
1768 && pos.type_of_piece_on(move_to(m)) != PAWN
1769 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1770 - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
1771 && !move_is_promotion(m)
1774 result += PawnEndgameExtension[PvNode];
1779 && captureOrPromotion
1780 && pos.type_of_piece_on(move_to(m)) != PAWN
1781 && pos.see_sign(m) >= 0)
1783 result += ONE_PLY / 2;
1787 return Min(result, ONE_PLY);
1791 // connected_threat() tests whether it is safe to forward prune a move or if
1792 // is somehow coonected to the threat move returned by null search.
1794 bool connected_threat(const Position& pos, Move m, Move threat) {
1796 assert(move_is_ok(m));
1797 assert(threat && move_is_ok(threat));
1798 assert(!pos.move_is_check(m));
1799 assert(!pos.move_is_capture_or_promotion(m));
1800 assert(!pos.move_is_passed_pawn_push(m));
1802 Square mfrom, mto, tfrom, tto;
1804 mfrom = move_from(m);
1806 tfrom = move_from(threat);
1807 tto = move_to(threat);
1809 // Case 1: Don't prune moves which move the threatened piece
1813 // Case 2: If the threatened piece has value less than or equal to the
1814 // value of the threatening piece, don't prune move which defend it.
1815 if ( pos.move_is_capture(threat)
1816 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
1817 || pos.type_of_piece_on(tfrom) == KING)
1818 && pos.move_attacks_square(m, tto))
1821 // Case 3: If the moving piece in the threatened move is a slider, don't
1822 // prune safe moves which block its ray.
1823 if ( piece_is_slider(pos.piece_on(tfrom))
1824 && bit_is_set(squares_between(tfrom, tto), mto)
1825 && pos.see_sign(m) >= 0)
1832 // ok_to_use_TT() returns true if a transposition table score
1833 // can be used at a given point in search.
1835 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
1837 Value v = value_from_tt(tte->value(), ply);
1839 return ( tte->depth() >= depth
1840 || v >= Max(value_mate_in(PLY_MAX), beta)
1841 || v < Min(value_mated_in(PLY_MAX), beta))
1843 && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
1844 || ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
1848 // refine_eval() returns the transposition table score if
1849 // possible otherwise falls back on static position evaluation.
1851 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
1855 Value v = value_from_tt(tte->value(), ply);
1857 if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval)
1858 || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval))
1865 // update_history() registers a good move that produced a beta-cutoff
1866 // in history and marks as failures all the other moves of that ply.
1868 void update_history(const Position& pos, Move move, Depth depth,
1869 Move movesSearched[], int moveCount) {
1872 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
1874 for (int i = 0; i < moveCount - 1; i++)
1876 m = movesSearched[i];
1880 if (!pos.move_is_capture_or_promotion(m))
1881 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
1886 // update_killers() add a good move that produced a beta-cutoff
1887 // among the killer moves of that ply.
1889 void update_killers(Move m, SearchStack* ss) {
1891 if (m == ss->killers[0])
1894 ss->killers[1] = ss->killers[0];
1899 // update_gains() updates the gains table of a non-capture move given
1900 // the static position evaluation before and after the move.
1902 void update_gains(const Position& pos, Move m, Value before, Value after) {
1905 && before != VALUE_NONE
1906 && after != VALUE_NONE
1907 && pos.captured_piece_type() == PIECE_TYPE_NONE
1908 && !move_is_special(m))
1909 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
1913 // current_search_time() returns the number of milliseconds which have passed
1914 // since the beginning of the current search.
1916 int current_search_time() {
1918 return get_system_time() - SearchStartTime;
1922 // value_to_uci() converts a value to a string suitable for use with the UCI protocol
1924 std::string value_to_uci(Value v) {
1926 std::stringstream s;
1928 if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
1929 s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100
1931 s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 );
1936 // nps() computes the current nodes/second count.
1938 int nps(const Position& pos) {
1940 int t = current_search_time();
1941 return (t > 0 ? int((pos.nodes_searched() * 1000) / t) : 0);
1945 // poll() performs two different functions: It polls for user input, and it
1946 // looks at the time consumed so far and decides if it's time to abort the
1949 void poll(const Position& pos) {
1951 static int lastInfoTime;
1952 int t = current_search_time();
1955 if (data_available())
1957 // We are line oriented, don't read single chars
1958 std::string command;
1960 if (!std::getline(std::cin, command))
1963 if (command == "quit")
1966 PonderSearch = false;
1970 else if (command == "stop")
1973 PonderSearch = false;
1975 else if (command == "ponderhit")
1979 // Print search information
1983 else if (lastInfoTime > t)
1984 // HACK: Must be a new search where we searched less than
1985 // NodesBetweenPolls nodes during the first second of search.
1988 else if (t - lastInfoTime >= 1000)
1995 if (dbg_show_hit_rate)
1996 dbg_print_hit_rate();
1998 cout << "info nodes " << pos.nodes_searched() << " nps " << nps(pos)
1999 << " time " << t << endl;
2002 // Should we stop the search?
2006 bool stillAtFirstMove = FirstRootMove
2007 && !AspirationFailLow
2008 && t > TimeMgr.available_time();
2010 bool noMoreTime = t > TimeMgr.maximum_time()
2011 || stillAtFirstMove;
2013 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2014 || (ExactMaxTime && t >= ExactMaxTime)
2015 || (Iteration >= 3 && MaxNodes && pos.nodes_searched() >= MaxNodes))
2020 // ponderhit() is called when the program is pondering (i.e. thinking while
2021 // it's the opponent's turn to move) in order to let the engine know that
2022 // it correctly predicted the opponent's move.
2026 int t = current_search_time();
2027 PonderSearch = false;
2029 bool stillAtFirstMove = FirstRootMove
2030 && !AspirationFailLow
2031 && t > TimeMgr.available_time();
2033 bool noMoreTime = t > TimeMgr.maximum_time()
2034 || stillAtFirstMove;
2036 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2041 // init_ss_array() does a fast reset of the first entries of a SearchStack
2042 // array and of all the excludedMove and skipNullMove entries.
2044 void init_ss_array(SearchStack* ss, int size) {
2046 for (int i = 0; i < size; i++, ss++)
2048 ss->excludedMove = MOVE_NONE;
2049 ss->skipNullMove = false;
2050 ss->reduction = DEPTH_ZERO;
2054 ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE;
2059 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2060 // while the program is pondering. The point is to work around a wrinkle in
2061 // the UCI protocol: When pondering, the engine is not allowed to give a
2062 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2063 // We simply wait here until one of these commands is sent, and return,
2064 // after which the bestmove and pondermove will be printed (in id_loop()).
2066 void wait_for_stop_or_ponderhit() {
2068 std::string command;
2072 if (!std::getline(std::cin, command))
2075 if (command == "quit")
2080 else if (command == "ponderhit" || command == "stop")
2086 // print_pv_info() prints to standard output and eventually to log file information on
2087 // the current PV line. It is called at each iteration or after a new pv is found.
2089 void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) {
2091 cout << "info depth " << Iteration
2092 << " score " << value_to_uci(value)
2093 << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
2094 << " time " << current_search_time()
2095 << " nodes " << pos.nodes_searched()
2096 << " nps " << nps(pos)
2099 for (Move* m = pv; *m != MOVE_NONE; m++)
2106 ValueType t = value >= beta ? VALUE_TYPE_LOWER :
2107 value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
2109 LogFile << pretty_pv(pos, current_search_time(), Iteration, value, t, pv) << endl;
2114 // insert_pv_in_tt() is called at the end of a search iteration, and inserts
2115 // the PV back into the TT. This makes sure the old PV moves are searched
2116 // first, even if the old TT entries have been overwritten.
2118 void insert_pv_in_tt(const Position& pos, Move pv[]) {
2122 Position p(pos, pos.thread());
2123 Value v, m = VALUE_NONE;
2125 for (int i = 0; pv[i] != MOVE_NONE; i++)
2127 tte = TT.retrieve(p.get_key());
2128 if (!tte || tte->move() != pv[i])
2130 v = (p.is_check() ? VALUE_NONE : evaluate(p, m));
2131 TT.store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[i], v, m);
2133 p.do_move(pv[i], st);
2138 // extract_pv_from_tt() builds a PV by adding moves from the transposition table.
2139 // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This
2140 // allow to always have a ponder move even when we fail high at root and also a
2141 // long PV to print that is important for position analysis.
2143 void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]) {
2147 Position p(pos, pos.thread());
2150 assert(bestMove != MOVE_NONE);
2153 p.do_move(pv[ply++], st);
2155 while ( (tte = TT.retrieve(p.get_key())) != NULL
2156 && tte->move() != MOVE_NONE
2157 && move_is_legal(p, tte->move())
2159 && (!p.is_draw() || ply < 2))
2161 pv[ply] = tte->move();
2162 p.do_move(pv[ply++], st);
2164 pv[ply] = MOVE_NONE;
2168 // init_thread() is the function which is called when a new thread is
2169 // launched. It simply calls the idle_loop() function with the supplied
2170 // threadID. There are two versions of this function; one for POSIX
2171 // threads and one for Windows threads.
2173 #if !defined(_MSC_VER)
2175 void* init_thread(void* threadID) {
2177 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2183 DWORD WINAPI init_thread(LPVOID threadID) {
2185 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
2192 /// The ThreadsManager class
2195 // idle_loop() is where the threads are parked when they have no work to do.
2196 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2197 // object for which the current thread is the master.
2199 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2201 assert(threadID >= 0 && threadID < MAX_THREADS);
2205 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2206 // master should exit as last one.
2207 if (AllThreadsShouldExit)
2210 threads[threadID].state = THREAD_TERMINATED;
2214 // If we are not thinking, wait for a condition to be signaled
2215 // instead of wasting CPU time polling for work.
2216 while (threadID >= ActiveThreads || threads[threadID].state == THREAD_INITIALIZING)
2219 assert(threadID != 0);
2221 if (AllThreadsShouldExit)
2224 threads[threadID].state = THREAD_AVAILABLE;
2226 lock_grab(&WaitLock);
2228 if (threadID >= ActiveThreads || threads[threadID].state == THREAD_INITIALIZING)
2229 cond_wait(&WaitCond[threadID], &WaitLock);
2231 lock_release(&WaitLock);
2234 // If this thread has been assigned work, launch a search
2235 if (threads[threadID].state == THREAD_WORKISWAITING)
2237 assert(!AllThreadsShouldExit);
2239 threads[threadID].state = THREAD_SEARCHING;
2241 // Here we call search() with SplitPoint template parameter set to true
2242 SplitPoint* tsp = threads[threadID].splitPoint;
2243 Position pos(*tsp->pos, threadID);
2244 SearchStack* ss = tsp->sstack[threadID] + 1;
2248 search<PV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2250 search<NonPV, true>(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply);
2252 assert(threads[threadID].state == THREAD_SEARCHING);
2254 threads[threadID].state = THREAD_AVAILABLE;
2257 // If this thread is the master of a split point and all slaves have
2258 // finished their work at this split point, return from the idle loop.
2260 for ( ; sp && i < ActiveThreads && !sp->slaves[i]; i++) {}
2262 if (i == ActiveThreads)
2264 // Because sp->slaves[] is reset under lock protection,
2265 // be sure sp->lock has been released before to return.
2266 lock_grab(&(sp->lock));
2267 lock_release(&(sp->lock));
2269 // In helpful master concept a master can help only a sub-tree, and
2270 // because here is all finished is not possible master is booked.
2271 assert(threads[threadID].state == THREAD_AVAILABLE);
2273 threads[threadID].state = THREAD_SEARCHING;
2280 // init_threads() is called during startup. It launches all helper threads,
2281 // and initializes the split point stack and the global locks and condition
2284 void ThreadsManager::init_threads() {
2286 int i, arg[MAX_THREADS];
2289 // Initialize global locks
2291 lock_init(&WaitLock);
2293 for (i = 0; i < MAX_THREADS; i++)
2294 cond_init(&WaitCond[i]);
2296 // Initialize splitPoints[] locks
2297 for (i = 0; i < MAX_THREADS; i++)
2298 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2299 lock_init(&(threads[i].splitPoints[j].lock));
2301 // Will be set just before program exits to properly end the threads
2302 AllThreadsShouldExit = false;
2304 // Threads will be put all threads to sleep as soon as created
2307 // All threads except the main thread should be initialized to THREAD_INITIALIZING
2308 threads[0].state = THREAD_SEARCHING;
2309 for (i = 1; i < MAX_THREADS; i++)
2310 threads[i].state = THREAD_INITIALIZING;
2312 // Launch the helper threads
2313 for (i = 1; i < MAX_THREADS; i++)
2317 #if !defined(_MSC_VER)
2318 pthread_t pthread[1];
2319 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
2320 pthread_detach(pthread[0]);
2322 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
2326 cout << "Failed to create thread number " << i << endl;
2330 // Wait until the thread has finished launching and is gone to sleep
2331 while (threads[i].state == THREAD_INITIALIZING) {}
2336 // exit_threads() is called when the program exits. It makes all the
2337 // helper threads exit cleanly.
2339 void ThreadsManager::exit_threads() {
2341 AllThreadsShouldExit = true; // Let the woken up threads to exit idle_loop()
2343 // Wake up all the threads and waits for termination
2344 for (int i = 1; i < MAX_THREADS; i++)
2346 wake_sleeping_thread(i);
2347 while (threads[i].state != THREAD_TERMINATED) {}
2350 // Now we can safely destroy the locks
2351 for (int i = 0; i < MAX_THREADS; i++)
2352 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
2353 lock_destroy(&(threads[i].splitPoints[j].lock));
2355 lock_destroy(&WaitLock);
2356 lock_destroy(&MPLock);
2358 // Now we can safely destroy the wait conditions
2359 for (int i = 0; i < MAX_THREADS; i++)
2360 cond_destroy(&WaitCond[i]);
2364 // thread_should_stop() checks whether the thread should stop its search.
2365 // This can happen if a beta cutoff has occurred in the thread's currently
2366 // active split point, or in some ancestor of the current split point.
2368 bool ThreadsManager::thread_should_stop(int threadID) const {
2370 assert(threadID >= 0 && threadID < ActiveThreads);
2372 SplitPoint* sp = threads[threadID].splitPoint;
2374 for ( ; sp && !sp->stopRequest; sp = sp->parent) {}
2379 // thread_is_available() checks whether the thread with threadID "slave" is
2380 // available to help the thread with threadID "master" at a split point. An
2381 // obvious requirement is that "slave" must be idle. With more than two
2382 // threads, this is not by itself sufficient: If "slave" is the master of
2383 // some active split point, it is only available as a slave to the other
2384 // threads which are busy searching the split point at the top of "slave"'s
2385 // split point stack (the "helpful master concept" in YBWC terminology).
2387 bool ThreadsManager::thread_is_available(int slave, int master) const {
2389 assert(slave >= 0 && slave < ActiveThreads);
2390 assert(master >= 0 && master < ActiveThreads);
2391 assert(ActiveThreads > 1);
2393 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2396 // Make a local copy to be sure doesn't change under our feet
2397 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2399 // No active split points means that the thread is available as
2400 // a slave for any other thread.
2401 if (localActiveSplitPoints == 0 || ActiveThreads == 2)
2404 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2405 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2406 // could have been set to 0 by another thread leading to an out of bound access.
2407 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
2414 // available_thread_exists() tries to find an idle thread which is available as
2415 // a slave for the thread with threadID "master".
2417 bool ThreadsManager::available_thread_exists(int master) const {
2419 assert(master >= 0 && master < ActiveThreads);
2420 assert(ActiveThreads > 1);
2422 for (int i = 0; i < ActiveThreads; i++)
2423 if (thread_is_available(i, master))
2430 // split() does the actual work of distributing the work at a node between
2431 // several available threads. If it does not succeed in splitting the
2432 // node (because no idle threads are available, or because we have no unused
2433 // split point objects), the function immediately returns. If splitting is
2434 // possible, a SplitPoint object is initialized with all the data that must be
2435 // copied to the helper threads and we tell our helper threads that they have
2436 // been assigned work. This will cause them to instantly leave their idle loops and
2437 // call search().When all threads have returned from search() then split() returns.
2439 template <bool Fake>
2440 void ThreadsManager::split(Position& pos, SearchStack* ss, int ply, Value* alpha,
2441 const Value beta, Value* bestValue, Depth depth, Move threatMove,
2442 bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) {
2443 assert(pos.is_ok());
2444 assert(ply > 0 && ply < PLY_MAX);
2445 assert(*bestValue >= -VALUE_INFINITE);
2446 assert(*bestValue <= *alpha);
2447 assert(*alpha < beta);
2448 assert(beta <= VALUE_INFINITE);
2449 assert(depth > DEPTH_ZERO);
2450 assert(pos.thread() >= 0 && pos.thread() < ActiveThreads);
2451 assert(ActiveThreads > 1);
2453 int i, master = pos.thread();
2454 Thread& masterThread = threads[master];
2458 // If no other thread is available to help us, or if we have too many
2459 // active split points, don't split.
2460 if ( !available_thread_exists(master)
2461 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
2463 lock_release(&MPLock);
2467 // Pick the next available split point object from the split point stack
2468 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
2470 // Initialize the split point object
2471 splitPoint.parent = masterThread.splitPoint;
2472 splitPoint.stopRequest = false;
2473 splitPoint.ply = ply;
2474 splitPoint.depth = depth;
2475 splitPoint.threatMove = threatMove;
2476 splitPoint.mateThreat = mateThreat;
2477 splitPoint.alpha = *alpha;
2478 splitPoint.beta = beta;
2479 splitPoint.pvNode = pvNode;
2480 splitPoint.bestValue = *bestValue;
2482 splitPoint.moveCount = moveCount;
2483 splitPoint.pos = &pos;
2484 splitPoint.nodes = 0;
2485 splitPoint.parentSstack = ss;
2486 for (i = 0; i < ActiveThreads; i++)
2487 splitPoint.slaves[i] = 0;
2489 masterThread.splitPoint = &splitPoint;
2491 // If we are here it means we are not available
2492 assert(masterThread.state != THREAD_AVAILABLE);
2494 int workersCnt = 1; // At least the master is included
2496 // Allocate available threads setting state to THREAD_BOOKED
2497 for (i = 0; !Fake && i < ActiveThreads && workersCnt < MaxThreadsPerSplitPoint; i++)
2498 if (thread_is_available(i, master))
2500 threads[i].state = THREAD_BOOKED;
2501 threads[i].splitPoint = &splitPoint;
2502 splitPoint.slaves[i] = 1;
2506 assert(Fake || workersCnt > 1);
2508 // We can release the lock because slave threads are already booked and master is not available
2509 lock_release(&MPLock);
2511 // Tell the threads that they have work to do. This will make them leave
2512 // their idle loop. But before copy search stack tail for each thread.
2513 for (i = 0; i < ActiveThreads; i++)
2514 if (i == master || splitPoint.slaves[i])
2516 memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack));
2518 assert(i == master || threads[i].state == THREAD_BOOKED);
2520 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2523 // Everything is set up. The master thread enters the idle loop, from
2524 // which it will instantly launch a search, because its state is
2525 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2526 // idle loop, which means that the main thread will return from the idle
2527 // loop when all threads have finished their work at this split point.
2528 idle_loop(master, &splitPoint);
2530 // We have returned from the idle loop, which means that all threads are
2531 // finished. Update alpha and bestValue, and return.
2534 *alpha = splitPoint.alpha;
2535 *bestValue = splitPoint.bestValue;
2536 masterThread.activeSplitPoints--;
2537 masterThread.splitPoint = splitPoint.parent;
2538 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
2540 lock_release(&MPLock);
2544 // wake_sleeping_thread() wakes up all sleeping threads when it is time
2545 // to start a new search from the root.
2547 void ThreadsManager::wake_sleeping_thread(int threadID) {
2549 lock_grab(&WaitLock);
2550 cond_signal(&WaitCond[threadID]);
2551 lock_release(&WaitLock);
2555 /// The RootMoveList class
2557 // RootMoveList c'tor
2559 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) {
2561 SearchStack ss[PLY_MAX_PLUS_2];
2562 MoveStack mlist[MOVES_MAX];
2564 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
2566 // Initialize search stack
2567 init_ss_array(ss, PLY_MAX_PLUS_2);
2568 ss[0].eval = ss[0].evalMargin = VALUE_NONE;
2571 // Generate all legal moves
2572 MoveStack* last = generate_moves(pos, mlist);
2574 // Add each move to the moves[] array
2575 for (MoveStack* cur = mlist; cur != last; cur++)
2577 bool includeMove = includeAllMoves;
2579 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
2580 includeMove = (searchMoves[k] == cur->move);
2585 // Find a quick score for the move
2586 moves[count].move = ss[0].currentMove = moves[count].pv[0] = cur->move;
2587 moves[count].pv[1] = MOVE_NONE;
2588 pos.do_move(cur->move, st);
2589 moves[count].score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
2590 pos.undo_move(cur->move);
2596 // Score root moves using the standard way used in main search, the moves
2597 // are scored according to the order in which are returned by MovePicker.
2599 void RootMoveList::score_moves(const Position& pos)
2603 MovePicker mp = MovePicker(pos, MOVE_NONE, ONE_PLY, H);
2605 while ((move = mp.get_next_move()) != MOVE_NONE)
2606 for (int i = 0; i < count; i++)
2607 if (moves[i].move == move)
2609 moves[i].mp_score = score--;
2614 // RootMoveList simple methods definitions
2616 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
2620 for (j = 0; pv[j] != MOVE_NONE; j++)
2621 moves[moveNum].pv[j] = pv[j];
2623 moves[moveNum].pv[j] = MOVE_NONE;
2627 // RootMoveList::sort() sorts the root move list at the beginning of a new
2630 void RootMoveList::sort() {
2632 sort_multipv(count - 1); // Sort all items
2636 // RootMoveList::sort_multipv() sorts the first few moves in the root move
2637 // list by their scores and depths. It is used to order the different PVs
2638 // correctly in MultiPV mode.
2640 void RootMoveList::sort_multipv(int n) {
2644 for (i = 1; i <= n; i++)
2646 RootMove rm = moves[i];
2647 for (j = i; j > 0 && moves[j - 1] < rm; j--)
2648 moves[j] = moves[j - 1];