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/>.
43 #include "ucioption.h"
49 //// Local definitions
55 enum NodeType { NonPV, PV };
57 // ThreadsManager class is used to handle all the threads related stuff in search,
58 // init, starting, parking and, the most important, launching a slave thread at a
59 // split point are what this class does. All the access to shared thread data is
60 // done through this class, so that we avoid using global variables instead.
62 class ThreadsManager {
63 /* As long as the single ThreadsManager object is defined as a global we don't
64 need to explicitly initialize to zero its data members because variables with
65 static storage duration are automatically set to zero before enter main()
71 int active_threads() const { return ActiveThreads; }
72 void set_active_threads(int newActiveThreads) { ActiveThreads = newActiveThreads; }
73 void incrementNodeCounter(int threadID) { threads[threadID].nodes++; }
74 void incrementBetaCounter(Color us, Depth d, int threadID) { threads[threadID].betaCutOffs[us] += unsigned(d); }
76 void resetNodeCounters();
77 void resetBetaCounters();
78 int64_t nodes_searched() const;
79 void get_beta_counters(Color us, int64_t& our, int64_t& their) const;
80 bool available_thread_exists(int master) const;
81 bool thread_is_available(int slave, int master) const;
82 bool thread_should_stop(int threadID) const;
83 void wake_sleeping_threads();
84 void put_threads_to_sleep();
85 void idle_loop(int threadID, SplitPoint* sp);
88 bool split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
89 Depth depth, bool mateThreat, int* moves, MovePicker* mp, int master, bool pvNode);
95 volatile bool AllThreadsShouldExit, AllThreadsShouldSleep;
96 Thread threads[MAX_THREADS];
97 SplitPoint SplitPointStack[MAX_THREADS][ACTIVE_SPLIT_POINTS_MAX];
99 Lock MPLock, WaitLock;
101 #if !defined(_MSC_VER)
102 pthread_cond_t WaitCond;
104 HANDLE SitIdleEvent[MAX_THREADS];
110 // RootMove struct is used for moves at the root at the tree. For each
111 // root move, we store a score, a node count, and a PV (really a refutation
112 // in the case of moves which fail low).
116 RootMove() { nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL; }
118 // RootMove::operator<() is the comparison function used when
119 // sorting the moves. A move m1 is considered to be better
120 // than a move m2 if it has a higher score, or if the moves
121 // have equal score but m1 has the higher node count.
122 bool operator<(const RootMove& m) const {
124 return score != m.score ? score < m.score : theirBeta <= m.theirBeta;
129 int64_t nodes, cumulativeNodes, ourBeta, theirBeta;
130 Move pv[PLY_MAX_PLUS_2];
134 // The RootMoveList class is essentially an array of RootMove objects, with
135 // a handful of methods for accessing the data in the individual moves.
140 RootMoveList(Position& pos, Move searchMoves[]);
142 int move_count() const { return count; }
143 Move get_move(int moveNum) const { return moves[moveNum].move; }
144 Value get_move_score(int moveNum) const { return moves[moveNum].score; }
145 void set_move_score(int moveNum, Value score) { moves[moveNum].score = score; }
146 Move get_move_pv(int moveNum, int i) const { return moves[moveNum].pv[i]; }
147 int64_t get_move_cumulative_nodes(int moveNum) const { return moves[moveNum].cumulativeNodes; }
149 void set_move_nodes(int moveNum, int64_t nodes);
150 void set_beta_counters(int moveNum, int64_t our, int64_t their);
151 void set_move_pv(int moveNum, const Move pv[]);
153 void sort_multipv(int n);
156 static const int MaxRootMoves = 500;
157 RootMove moves[MaxRootMoves];
166 // Maximum depth for razoring
167 const Depth RazorDepth = 4 * OnePly;
169 // Dynamic razoring margin based on depth
170 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * int(d)); }
172 // Step 8. Null move search with verification search
174 // Null move margin. A null move search will not be done if the static
175 // evaluation of the position is more than NullMoveMargin below beta.
176 const Value NullMoveMargin = Value(0x200);
178 // Maximum depth for use of dynamic threat detection when null move fails low
179 const Depth ThreatDepth = 5 * OnePly;
181 // Step 9. Internal iterative deepening
183 // Minimum depth for use of internal iterative deepening
184 const Depth IIDDepth[2] = { 8 * OnePly /* non-PV */, 5 * OnePly /* PV */};
186 // At Non-PV nodes we do an internal iterative deepening search
187 // when the static evaluation is at most IIDMargin below beta.
188 const Value IIDMargin = Value(0x100);
190 // Step 11. Decide the new search depth
192 // Extensions. Configurable UCI options
193 // Array index 0 is used at non-PV nodes, index 1 at PV nodes.
194 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
195 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
197 // Minimum depth for use of singular extension
198 const Depth SingularExtensionDepth[2] = { 8 * OnePly /* non-PV */, 6 * OnePly /* PV */};
200 // If the TT move is at least SingularExtensionMargin better then the
201 // remaining ones we will extend it.
202 const Value SingularExtensionMargin = Value(0x20);
204 // Step 12. Futility pruning
206 // Futility margin for quiescence search
207 const Value FutilityMarginQS = Value(0x80);
209 // Futility lookup tables (initialized at startup) and their getter functions
210 int32_t FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
211 int FutilityMoveCountArray[32]; // [depth]
213 inline Value futility_margin(Depth d, int mn) { return Value(d < 7 * OnePly ? FutilityMarginsMatrix[Max(d, 0)][Min(mn, 63)] : 2 * VALUE_INFINITE); }
214 inline int futility_move_count(Depth d) { return d < 16 * OnePly ? FutilityMoveCountArray[d] : 512; }
216 // Step 14. Reduced search
218 // Reduction lookup tables (initialized at startup) and their getter functions
219 int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
221 template <NodeType PV>
222 inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
224 // Common adjustments
226 // Search depth at iteration 1
227 const Depth InitialDepth = OnePly;
229 // Easy move margin. An easy move candidate must be at least this much
230 // better than the second best move.
231 const Value EasyMoveMargin = Value(0x200);
233 // Last seconds noise filtering (LSN)
234 const bool UseLSNFiltering = true;
235 const int LSNTime = 4000; // In milliseconds
236 const Value LSNValue = value_from_centipawns(200);
237 bool loseOnTime = false;
245 // Scores and number of times the best move changed for each iteration
246 Value ValueByIteration[PLY_MAX_PLUS_2];
247 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
249 // Search window management
255 // Time managment variables
256 int SearchStartTime, MaxNodes, MaxDepth, MaxSearchTime;
257 int AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
258 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
259 bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
263 std::ofstream LogFile;
265 // Multi-threads related variables
266 Depth MinimumSplitDepth;
267 int MaxThreadsPerSplitPoint;
270 // Node counters, used only by thread[0] but try to keep in different cache
271 // lines (64 bytes each) from the heavy multi-thread read accessed variables.
273 int NodesBetweenPolls = 30000;
280 Value id_loop(const Position& pos, Move searchMoves[]);
281 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
283 template <NodeType PvNode>
284 Value search(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE);
286 template <NodeType PvNode>
287 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
289 template <NodeType PvNode>
290 void sp_search(SplitPoint* sp, int threadID);
292 template <NodeType PvNode>
293 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
295 void init_node(SearchStack ss[], int ply, int threadID);
296 void update_pv(SearchStack ss[], int ply);
297 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply);
298 bool connected_moves(const Position& pos, Move m1, Move m2);
299 bool value_is_mate(Value value);
300 bool move_is_killer(Move m, const SearchStack& ss);
301 bool ok_to_do_nullmove(const Position& pos);
302 bool ok_to_prune(const Position& pos, Move m, Move threat);
303 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
304 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
305 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
306 void update_killers(Move m, SearchStack& ss);
307 void update_gains(const Position& pos, Move move, Value before, Value after);
309 int current_search_time();
313 void wait_for_stop_or_ponderhit();
314 void init_ss_array(SearchStack ss[]);
315 void print_pv_info(const Position& pos, SearchStack ss[], Value alpha, Value beta, Value value);
317 #if !defined(_MSC_VER)
318 void *init_thread(void *threadID);
320 DWORD WINAPI init_thread(LPVOID threadID);
330 /// init_threads(), exit_threads() and nodes_searched() are helpers to
331 /// give accessibility to some TM methods from outside of current file.
333 void init_threads() { TM.init_threads(); }
334 void exit_threads() { TM.exit_threads(); }
335 int64_t nodes_searched() { return TM.nodes_searched(); }
338 /// perft() is our utility to verify move generation is bug free. All the legal
339 /// moves up to given depth are generated and counted and the sum returned.
341 int perft(Position& pos, Depth depth)
346 MovePicker mp(pos, MOVE_NONE, depth, H);
348 // If we are at the last ply we don't need to do and undo
349 // the moves, just to count them.
350 if (depth <= OnePly) // Replace with '<' to test also qsearch
352 while (mp.get_next_move()) sum++;
356 // Loop through all legal moves
358 while ((move = mp.get_next_move()) != MOVE_NONE)
360 pos.do_move(move, st, ci, pos.move_is_check(move, ci));
361 sum += perft(pos, depth - OnePly);
368 /// think() is the external interface to Stockfish's search, and is called when
369 /// the program receives the UCI 'go' command. It initializes various
370 /// search-related global variables, and calls root_search(). It returns false
371 /// when a quit command is received during the search.
373 bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
374 int time[], int increment[], int movesToGo, int maxDepth,
375 int maxNodes, int maxTime, Move searchMoves[]) {
377 // Initialize global search variables
378 StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
379 MaxSearchTime = AbsoluteMaxSearchTime = ExtraSearchTime = 0;
381 TM.resetNodeCounters();
382 SearchStartTime = get_system_time();
383 ExactMaxTime = maxTime;
386 InfiniteSearch = infinite;
387 PonderSearch = ponder;
388 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
390 // Look for a book move, only during games, not tests
391 if (UseTimeManagement && get_option_value_bool("OwnBook"))
393 if (get_option_value_string("Book File") != OpeningBook.file_name())
394 OpeningBook.open(get_option_value_string("Book File"));
396 Move bookMove = OpeningBook.get_move(pos, get_option_value_bool("Best Book Move"));
397 if (bookMove != MOVE_NONE)
400 wait_for_stop_or_ponderhit();
402 cout << "bestmove " << bookMove << endl;
407 // Reset loseOnTime flag at the beginning of a new game
408 if (button_was_pressed("New Game"))
411 // Read UCI option values
412 TT.set_size(get_option_value_int("Hash"));
413 if (button_was_pressed("Clear Hash"))
416 CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)"));
417 CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)"));
418 SingleEvasionExtension[1] = Depth(get_option_value_int("Single Evasion Extension (PV nodes)"));
419 SingleEvasionExtension[0] = Depth(get_option_value_int("Single Evasion Extension (non-PV nodes)"));
420 PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)"));
421 PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
422 PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
423 PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
424 PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
425 PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)"));
426 MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
427 MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
429 MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly;
430 MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point");
431 MultiPV = get_option_value_int("MultiPV");
432 Chess960 = get_option_value_bool("UCI_Chess960");
433 UseLogFile = get_option_value_bool("Use Search Log");
436 LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app);
438 read_weights(pos.side_to_move());
440 // Set the number of active threads
441 int newActiveThreads = get_option_value_int("Threads");
442 if (newActiveThreads != TM.active_threads())
444 TM.set_active_threads(newActiveThreads);
445 init_eval(TM.active_threads());
448 // Wake up sleeping threads
449 TM.wake_sleeping_threads();
452 int myTime = time[side_to_move];
453 int myIncrement = increment[side_to_move];
454 if (UseTimeManagement)
456 if (!movesToGo) // Sudden death time control
460 MaxSearchTime = myTime / 30 + myIncrement;
461 AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
463 else // Blitz game without increment
465 MaxSearchTime = myTime / 30;
466 AbsoluteMaxSearchTime = myTime / 8;
469 else // (x moves) / (y minutes)
473 MaxSearchTime = myTime / 2;
474 AbsoluteMaxSearchTime = (myTime > 3000)? (myTime - 500) : ((myTime * 3) / 4);
478 MaxSearchTime = myTime / Min(movesToGo, 20);
479 AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
483 if (get_option_value_bool("Ponder"))
485 MaxSearchTime += MaxSearchTime / 4;
486 MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime);
490 // Set best NodesBetweenPolls interval to avoid lagging under
491 // heavy time pressure.
493 NodesBetweenPolls = Min(MaxNodes, 30000);
494 else if (myTime && myTime < 1000)
495 NodesBetweenPolls = 1000;
496 else if (myTime && myTime < 5000)
497 NodesBetweenPolls = 5000;
499 NodesBetweenPolls = 30000;
501 // Write search information to log file
503 LogFile << "Searching: " << pos.to_fen() << endl
504 << "infinite: " << infinite
505 << " ponder: " << ponder
506 << " time: " << myTime
507 << " increment: " << myIncrement
508 << " moves to go: " << movesToGo << endl;
510 // LSN filtering. Used only for developing purposes, disabled by default
514 // Step 2. If after last move we decided to lose on time, do it now!
515 while (SearchStartTime + myTime + 1000 > get_system_time())
519 // We're ready to start thinking. Call the iterative deepening loop function
520 Value v = id_loop(pos, searchMoves);
524 // Step 1. If this is sudden death game and our position is hopeless,
525 // decide to lose on time.
526 if ( !loseOnTime // If we already lost on time, go to step 3.
536 // Step 3. Now after stepping over the time limit, reset flag for next match.
544 TM.put_threads_to_sleep();
550 /// init_search() is called during startup. It initializes various lookup tables
554 // Init our reduction lookup tables
555 for (int i = 1; i < 64; i++) // i == depth (OnePly = 1)
556 for (int j = 1; j < 64; j++) // j == moveNumber
558 double pvRed = log(double(i)) * log(double(j)) / 3.0;
559 double nonPVRed = log(double(i)) * log(double(j)) / 1.5;
560 ReductionMatrix[PV][i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0);
561 ReductionMatrix[NonPV][i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0);
564 // Init futility margins array
565 for (int i = 0; i < 16; i++) // i == depth (OnePly = 2)
566 for (int j = 0; j < 64; j++) // j == moveNumber
568 // FIXME: test using log instead of BSR
569 FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j + 45;
572 // Init futility move count array
573 for (int i = 0; i < 32; i++) // i == depth (OnePly = 2)
574 FutilityMoveCountArray[i] = 3 + (1 << (3 * i / 8));
578 // SearchStack::init() initializes a search stack. Used at the beginning of a
579 // new search from the root.
580 void SearchStack::init(int ply) {
582 pv[ply] = pv[ply + 1] = MOVE_NONE;
583 currentMove = threatMove = MOVE_NONE;
584 reduction = Depth(0);
588 void SearchStack::initKillers() {
590 mateKiller = MOVE_NONE;
591 for (int i = 0; i < KILLER_MAX; i++)
592 killers[i] = MOVE_NONE;
597 // id_loop() is the main iterative deepening loop. It calls root_search
598 // repeatedly with increasing depth until the allocated thinking time has
599 // been consumed, the user stops the search, or the maximum search depth is
602 Value id_loop(const Position& pos, Move searchMoves[]) {
605 SearchStack ss[PLY_MAX_PLUS_2];
606 Move EasyMove = MOVE_NONE;
607 Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
609 // Moves to search are verified, copied, scored and sorted
610 RootMoveList rml(p, searchMoves);
612 // Handle special case of searching on a mate/stale position
613 if (rml.move_count() == 0)
616 wait_for_stop_or_ponderhit();
618 return pos.is_check() ? -VALUE_MATE : VALUE_DRAW;
621 // Print RootMoveList startup scoring to the standard output,
622 // so to output information also for iteration 1.
623 cout << "info depth " << 1
624 << "\ninfo depth " << 1
625 << " score " << value_to_string(rml.get_move_score(0))
626 << " time " << current_search_time()
627 << " nodes " << TM.nodes_searched()
629 << " pv " << rml.get_move(0) << "\n";
635 ValueByIteration[1] = rml.get_move_score(0);
638 // Is one move significantly better than others after initial scoring ?
639 if ( rml.move_count() == 1
640 || rml.get_move_score(0) > rml.get_move_score(1) + EasyMoveMargin)
641 EasyMove = rml.get_move(0);
643 // Iterative deepening loop
644 while (Iteration < PLY_MAX)
646 // Initialize iteration
648 BestMoveChangesByIteration[Iteration] = 0;
650 cout << "info depth " << Iteration << endl;
652 // Calculate dynamic aspiration window based on previous iterations
653 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
655 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
656 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
658 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
659 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
661 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
662 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
665 // Search to the current depth, rml is updated and sorted, alpha and beta could change
666 value = root_search(p, ss, rml, &alpha, &beta);
668 // Write PV to transposition table, in case the relevant entries have
669 // been overwritten during the search.
670 TT.insert_pv(p, ss[0].pv);
673 break; // Value cannot be trusted. Break out immediately!
675 //Save info about search result
676 ValueByIteration[Iteration] = value;
678 // Drop the easy move if differs from the new best move
679 if (ss[0].pv[0] != EasyMove)
680 EasyMove = MOVE_NONE;
682 if (UseTimeManagement)
685 bool stopSearch = false;
687 // Stop search early if there is only a single legal move,
688 // we search up to Iteration 6 anyway to get a proper score.
689 if (Iteration >= 6 && rml.move_count() == 1)
692 // Stop search early when the last two iterations returned a mate score
694 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
695 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
698 // Stop search early if one move seems to be much better than the others
699 int64_t nodes = TM.nodes_searched();
701 && EasyMove == ss[0].pv[0]
702 && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
703 && current_search_time() > MaxSearchTime / 16)
704 ||( rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100
705 && current_search_time() > MaxSearchTime / 32)))
708 // Add some extra time if the best move has changed during the last two iterations
709 if (Iteration > 5 && Iteration <= 50)
710 ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2)
711 + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3);
713 // Stop search if most of MaxSearchTime is consumed at the end of the
714 // iteration. We probably don't have enough time to search the first
715 // move at the next iteration anyway.
716 if (current_search_time() > ((MaxSearchTime + ExtraSearchTime) * 80) / 128)
722 StopOnPonderhit = true;
728 if (MaxDepth && Iteration >= MaxDepth)
732 // If we are pondering or in infinite search, we shouldn't print the
733 // best move before we are told to do so.
734 if (!AbortSearch && (PonderSearch || InfiniteSearch))
735 wait_for_stop_or_ponderhit();
737 // Print final search statistics
738 cout << "info nodes " << TM.nodes_searched()
740 << " time " << current_search_time()
741 << " hashfull " << TT.full() << endl;
743 // Print the best move and the ponder move to the standard output
744 if (ss[0].pv[0] == MOVE_NONE)
746 ss[0].pv[0] = rml.get_move(0);
747 ss[0].pv[1] = MOVE_NONE;
750 assert(ss[0].pv[0] != MOVE_NONE);
752 cout << "bestmove " << ss[0].pv[0];
754 if (ss[0].pv[1] != MOVE_NONE)
755 cout << " ponder " << ss[0].pv[1];
762 dbg_print_mean(LogFile);
764 if (dbg_show_hit_rate)
765 dbg_print_hit_rate(LogFile);
767 LogFile << "\nNodes: " << TM.nodes_searched()
768 << "\nNodes/second: " << nps()
769 << "\nBest move: " << move_to_san(p, ss[0].pv[0]);
772 p.do_move(ss[0].pv[0], st);
773 LogFile << "\nPonder move: "
774 << move_to_san(p, ss[0].pv[1]) // Works also with MOVE_NONE
777 return rml.get_move_score(0);
781 // root_search() is the function which searches the root node. It is
782 // similar to search_pv except that it uses a different move ordering
783 // scheme, prints some information to the standard output and handles
784 // the fail low/high loops.
786 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
793 Depth depth, ext, newDepth;
794 Value value, alpha, beta;
795 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
796 int researchCountFH, researchCountFL;
798 researchCountFH = researchCountFL = 0;
801 isCheck = pos.is_check();
803 // Step 1. Initialize node and poll (omitted at root, but I can see no good reason for this, FIXME)
804 // Step 2. Check for aborted search (omitted at root, because we do not initialize root node)
805 // Step 3. Mate distance pruning (omitted at root)
806 // Step 4. Transposition table lookup (omitted at root)
808 // Step 5. Evaluate the position statically
809 // At root we do this only to get reference value for child nodes
811 ss[0].eval = evaluate(pos, ei, 0);
813 ss[0].eval = VALUE_NONE; // HACK because we do not initialize root node
815 // Step 6. Razoring (omitted at root)
816 // Step 7. Static null move pruning (omitted at root)
817 // Step 8. Null move search with verification search (omitted at root)
818 // Step 9. Internal iterative deepening (omitted at root)
820 // Step extra. Fail low loop
821 // We start with small aspiration window and in case of fail low, we research
822 // with bigger window until we are not failing low anymore.
825 // Sort the moves before to (re)search
828 // Step 10. Loop through all moves in the root move list
829 for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
831 // This is used by time management
832 FirstRootMove = (i == 0);
834 // Save the current node count before the move is searched
835 nodes = TM.nodes_searched();
837 // Reset beta cut-off counters
838 TM.resetBetaCounters();
840 // Pick the next root move, and print the move and the move number to
841 // the standard output.
842 move = ss[0].currentMove = rml.get_move(i);
844 if (current_search_time() >= 1000)
845 cout << "info currmove " << move
846 << " currmovenumber " << i + 1 << endl;
848 moveIsCheck = pos.move_is_check(move);
849 captureOrPromotion = pos.move_is_capture_or_promotion(move);
851 // Step 11. Decide the new search depth
852 depth = (Iteration - 2) * OnePly + InitialDepth;
853 ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
854 newDepth = depth + ext;
856 // Step 12. Futility pruning (omitted at root)
858 // Step extra. Fail high loop
859 // If move fails high, we research with bigger window until we are not failing
861 value = - VALUE_INFINITE;
865 // Step 13. Make the move
866 pos.do_move(move, st, ci, moveIsCheck);
868 // Step extra. pv search
869 // We do pv search for first moves (i < MultiPV)
870 // and for fail high research (value > alpha)
871 if (i < MultiPV || value > alpha)
873 // Aspiration window is disabled in multi-pv case
875 alpha = -VALUE_INFINITE;
877 // Full depth PV search, done on first move or after a fail high
878 value = -search<PV>(pos, ss, -beta, -alpha, newDepth, 1, false, 0);
882 // Step 14. Reduced search
883 // if the move fails high will be re-searched at full depth
884 bool doFullDepthSearch = true;
886 if ( depth >= 3 * OnePly
888 && !captureOrPromotion
889 && !move_is_castle(move))
891 ss[0].reduction = reduction<PV>(depth, i - MultiPV + 2);
894 // Reduced depth non-pv search using alpha as upperbound
895 value = -search<NonPV>(pos, ss, -(alpha+1), -alpha, newDepth-ss[0].reduction, 1, true, 0);
896 doFullDepthSearch = (value > alpha);
900 // Step 15. Full depth search
901 if (doFullDepthSearch)
903 // Full depth non-pv search using alpha as upperbound
904 ss[0].reduction = Depth(0);
905 value = -search<NonPV>(pos, ss, -(alpha+1), -alpha, newDepth, 1, true, 0);
907 // If we are above alpha then research at same depth but as PV
908 // to get a correct score or eventually a fail high above beta.
910 value = -search<PV>(pos, ss, -beta, -alpha, newDepth, 1, false, 0);
914 // Step 16. Undo move
917 // Can we exit fail high loop ?
918 if (AbortSearch || value < beta)
921 // We are failing high and going to do a research. It's important to update
922 // the score before research in case we run out of time while researching.
923 rml.set_move_score(i, value);
925 TT.extract_pv(pos, ss[0].pv, PLY_MAX);
926 rml.set_move_pv(i, ss[0].pv);
928 // Print information to the standard output
929 print_pv_info(pos, ss, alpha, beta, value);
931 // Prepare for a research after a fail high, each time with a wider window
932 *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
935 } // End of fail high loop
937 // Finished searching the move. If AbortSearch is true, the search
938 // was aborted because the user interrupted the search or because we
939 // ran out of time. In this case, the return value of the search cannot
940 // be trusted, and we break out of the loop without updating the best
945 // Remember beta-cutoff and searched nodes counts for this move. The
946 // info is used to sort the root moves for the next iteration.
948 TM.get_beta_counters(pos.side_to_move(), our, their);
949 rml.set_beta_counters(i, our, their);
950 rml.set_move_nodes(i, TM.nodes_searched() - nodes);
952 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
953 assert(value < beta);
955 // Step 17. Check for new best move
956 if (value <= alpha && i >= MultiPV)
957 rml.set_move_score(i, -VALUE_INFINITE);
960 // PV move or new best move!
963 rml.set_move_score(i, value);
965 TT.extract_pv(pos, ss[0].pv, PLY_MAX);
966 rml.set_move_pv(i, ss[0].pv);
970 // We record how often the best move has been changed in each
971 // iteration. This information is used for time managment: When
972 // the best move changes frequently, we allocate some more time.
974 BestMoveChangesByIteration[Iteration]++;
976 // Print information to the standard output
977 print_pv_info(pos, ss, alpha, beta, value);
979 // Raise alpha to setup proper non-pv search upper bound
986 for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
988 cout << "info multipv " << j + 1
989 << " score " << value_to_string(rml.get_move_score(j))
990 << " depth " << (j <= i ? Iteration : Iteration - 1)
991 << " time " << current_search_time()
992 << " nodes " << TM.nodes_searched()
996 for (int k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
997 cout << rml.get_move_pv(j, k) << " ";
1001 alpha = rml.get_move_score(Min(i, MultiPV - 1));
1003 } // PV move or new best move
1005 assert(alpha >= *alphaPtr);
1007 AspirationFailLow = (alpha == *alphaPtr);
1009 if (AspirationFailLow && StopOnPonderhit)
1010 StopOnPonderhit = false;
1013 // Can we exit fail low loop ?
1014 if (AbortSearch || !AspirationFailLow)
1017 // Prepare for a research after a fail low, each time with a wider window
1018 *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
1023 // Sort the moves before to return
1030 // search<>() is the main search function for both PV and non-PV nodes
1032 template <NodeType PvNode>
1033 Value search(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth,
1034 int ply, bool allowNullmove, int threadID, Move excludedMove) {
1036 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1037 assert(beta > alpha && beta <= VALUE_INFINITE);
1038 assert(PvNode || alpha == beta - 1);
1039 assert(ply >= 0 && ply < PLY_MAX);
1040 assert(threadID >= 0 && threadID < TM.active_threads());
1042 Move movesSearched[256];
1047 Depth ext, newDepth;
1048 Value bestValue, value, oldAlpha;
1049 Value refinedValue, nullValue, futilityValueScaled; // Non-PV specific
1050 bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
1051 bool mateThreat = false;
1053 refinedValue = bestValue = value = -VALUE_INFINITE;
1057 return qsearch<PvNode>(pos, ss, alpha, beta, Depth(0), ply, threadID);
1059 // Step 1. Initialize node and poll
1060 // Polling can abort search.
1061 init_node(ss, ply, threadID);
1063 // Step 2. Check for aborted search and immediate draw
1064 if (AbortSearch || TM.thread_should_stop(threadID))
1067 if (pos.is_draw() || ply >= PLY_MAX - 1)
1070 // Step 3. Mate distance pruning
1071 alpha = Max(value_mated_in(ply), alpha);
1072 beta = Min(value_mate_in(ply+1), beta);
1076 // Step 4. Transposition table lookup
1078 // We don't want the score of a partial search to overwrite a previous full search
1079 // TT value, so we use a different position key in case of an excluded move exists.
1080 Key posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1082 tte = TT.retrieve(posKey);
1083 ttMove = (tte ? tte->move() : MOVE_NONE);
1085 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1086 // This is to avoid problems in the following areas:
1088 // * Repetition draw detection
1089 // * Fifty move rule detection
1090 // * Searching for a mate
1091 // * Printing of full PV line
1093 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1095 // Refresh tte entry to avoid aging
1096 TT.store(posKey, tte->value(), tte->type(), tte->depth(), ttMove);
1098 ss[ply].currentMove = ttMove; // Can be MOVE_NONE
1099 return value_from_tt(tte->value(), ply);
1102 // Step 5. Evaluate the position statically
1103 // At PV nodes we do this only to update gain statistics
1104 isCheck = pos.is_check();
1107 if (tte && (tte->type() & VALUE_TYPE_EVAL))
1108 ss[ply].eval = value_from_tt(tte->value(), ply);
1110 ss[ply].eval = evaluate(pos, ei, threadID);
1112 refinedValue = refine_eval(tte, ss[ply].eval, ply); // Enhance accuracy with TT value if possible
1113 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1116 // Step 6. Razoring (is omitted in PV nodes)
1118 && refinedValue < beta - razor_margin(depth)
1119 && ttMove == MOVE_NONE
1120 && ss[ply - 1].currentMove != MOVE_NULL
1121 && depth < RazorDepth
1123 && !value_is_mate(beta)
1124 && !pos.has_pawn_on_7th(pos.side_to_move()))
1126 Value rbeta = beta - razor_margin(depth);
1127 Value v = qsearch<NonPV>(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID);
1129 // Logically we should return (v + razor_margin(depth)), but
1130 // surprisingly this did slightly weaker in tests.
1134 // Step 7. Static null move pruning (is omitted in PV nodes)
1135 // We're betting that the opponent doesn't have a move that will reduce
1136 // the score by more than futility_margin(depth) if we do a null move.
1139 && depth < RazorDepth
1141 && !value_is_mate(beta)
1142 && ok_to_do_nullmove(pos)
1143 && refinedValue >= beta + futility_margin(depth, 0))
1144 return refinedValue - futility_margin(depth, 0);
1146 // Step 8. Null move search with verification search (is omitted in PV nodes)
1147 // When we jump directly to qsearch() we do a null move only if static value is
1148 // at least beta. Otherwise we do a null move if static value is not more than
1149 // NullMoveMargin under beta.
1154 && !value_is_mate(beta)
1155 && ok_to_do_nullmove(pos)
1156 && refinedValue >= beta - (depth >= 4 * OnePly ? NullMoveMargin : 0))
1158 ss[ply].currentMove = MOVE_NULL;
1160 // Null move dynamic reduction based on depth
1161 int R = 3 + (depth >= 5 * OnePly ? depth / 8 : 0);
1163 // Null move dynamic reduction based on value
1164 if (refinedValue - beta > PawnValueMidgame)
1167 pos.do_null_move(st);
1169 nullValue = -search<NonPV>(pos, ss, -beta, -alpha, depth-R*OnePly, ply+1, false, threadID);
1171 pos.undo_null_move();
1173 if (nullValue >= beta)
1175 // Do not return unproven mate scores
1176 if (nullValue >= value_mate_in(PLY_MAX))
1179 if (depth < 6 * OnePly)
1182 // Do zugzwang verification search
1183 Value v = search<NonPV>(pos, ss, alpha, beta, depth-5*OnePly, ply, false, threadID);
1187 // The null move failed low, which means that we may be faced with
1188 // some kind of threat. If the previous move was reduced, check if
1189 // the move that refuted the null move was somehow connected to the
1190 // move which was reduced. If a connection is found, return a fail
1191 // low score (which will cause the reduced move to fail high in the
1192 // parent node, which will trigger a re-search with full depth).
1193 if (nullValue == value_mated_in(ply + 2))
1196 ss[ply].threatMove = ss[ply + 1].currentMove;
1197 if ( depth < ThreatDepth
1198 && ss[ply - 1].reduction
1199 && connected_moves(pos, ss[ply - 1].currentMove, ss[ply].threatMove))
1204 // Step 9. Internal iterative deepening
1205 if ( depth >= IIDDepth[PvNode]
1206 && ttMove == MOVE_NONE
1207 && (PvNode || (!isCheck && ss[ply].eval >= beta - IIDMargin)))
1209 Depth d = (PvNode ? depth - 2 * OnePly : depth / 2);
1210 search<PvNode>(pos, ss, alpha, beta, d, ply, false, threadID);
1211 ttMove = ss[ply].pv[ply];
1212 tte = TT.retrieve(posKey);
1215 // Expensive mate threat detection (only for PV nodes)
1217 mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move()));
1219 // Initialize a MovePicker object for the current position
1220 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply], (PvNode ? -VALUE_INFINITE : beta));
1223 // Step 10. Loop through moves
1224 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1225 while ( bestValue < beta
1226 && (move = mp.get_next_move()) != MOVE_NONE
1227 && !TM.thread_should_stop(threadID))
1229 assert(move_is_ok(move));
1231 if (move == excludedMove)
1234 singleEvasion = (isCheck && mp.number_of_evasions() == 1);
1235 moveIsCheck = pos.move_is_check(move, ci);
1236 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1238 // Step 11. Decide the new search depth
1239 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1241 // Singular extension search. We extend the TT move if its value is much better than
1242 // its siblings. To verify this we do a reduced search on all the other moves but the
1243 // ttMove, if result is lower then ttValue minus a margin then we extend ttMove.
1244 if ( depth >= SingularExtensionDepth[PvNode]
1246 && move == tte->move()
1247 && !excludedMove // Do not allow recursive singular extension search
1249 && is_lower_bound(tte->type())
1250 && tte->depth() >= depth - 3 * OnePly)
1252 Value ttValue = value_from_tt(tte->value(), ply);
1254 if (abs(ttValue) < VALUE_KNOWN_WIN)
1256 Value b = ttValue - SingularExtensionMargin;
1257 Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply, false, threadID, move);
1259 if (v < ttValue - SingularExtensionMargin)
1264 newDepth = depth - OnePly + ext;
1266 // Update current move (this must be done after singular extension search)
1267 movesSearched[moveCount++] = ss[ply].currentMove = move;
1269 // Step 12. Futility pruning (is omitted in PV nodes)
1273 && !captureOrPromotion
1274 && !move_is_castle(move)
1277 // Move count based pruning
1278 if ( moveCount >= futility_move_count(depth)
1279 && ok_to_prune(pos, move, ss[ply].threatMove)
1280 && bestValue > value_mated_in(PLY_MAX))
1283 // Value based pruning
1284 Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount); // FIXME We illogically ignore reduction condition depth >= 3*OnePly
1285 futilityValueScaled = ss[ply].eval + futility_margin(predictedDepth, moveCount)
1286 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1288 if (futilityValueScaled < beta)
1290 if (futilityValueScaled > bestValue)
1291 bestValue = futilityValueScaled;
1296 // Step 13. Make the move
1297 pos.do_move(move, st, ci, moveIsCheck);
1299 // Step extra. pv search (only in PV nodes)
1300 // The first move in list is the expected PV
1301 if (PvNode && moveCount == 1)
1302 value = -search<PV>(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID);
1305 // Step 14. Reduced search
1306 // if the move fails high will be re-searched at full depth.
1307 bool doFullDepthSearch = true;
1309 if ( depth >= 3 * OnePly
1311 && !captureOrPromotion
1312 && !move_is_castle(move)
1313 && !move_is_killer(move, ss[ply]))
1315 ss[ply].reduction = reduction<PvNode>(depth, moveCount);
1316 if (ss[ply].reduction)
1318 value = -search<NonPV>(pos, ss, -(alpha+1), -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
1319 doFullDepthSearch = (value > alpha);
1323 // Step 15. Full depth search
1324 if (doFullDepthSearch)
1326 ss[ply].reduction = Depth(0);
1327 value = -search<NonPV>(pos, ss, -(alpha+1), -alpha, newDepth, ply+1, true, threadID);
1329 // Step extra. pv search (only in PV nodes)
1330 // Search only for possible new PV nodes, if instead value >= beta then
1331 // parent node fails low with value <= alpha and tries another move.
1332 if (PvNode && value > alpha && value < beta)
1333 value = -search<PV>(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID);
1337 // Step 16. Undo move
1338 pos.undo_move(move);
1340 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1342 // Step 17. Check for new best move
1343 if (value > bestValue)
1348 if (PvNode && value < beta) // This guarantees that always: alpha < beta
1352 if (value == value_mate_in(ply + 1))
1353 ss[ply].mateKiller = move;
1357 // Step 18. Check for split
1358 if ( TM.active_threads() > 1
1360 && depth >= MinimumSplitDepth
1362 && TM.available_thread_exists(threadID)
1364 && !TM.thread_should_stop(threadID)
1365 && TM.split<false>(pos, ss, ply, &alpha, beta, &bestValue,
1366 depth, mateThreat, &moveCount, &mp, threadID, PvNode))
1369 // Uncomment to debug sp_search() in single thread mode
1370 if ( bestValue < beta
1374 && !TM.thread_should_stop(threadID)
1375 && TM.split<true>(pos, ss, ply, &alpha, beta, &bestValue,
1376 depth, mateThreat, &moveCount, &mp, threadID, PvNode))
1380 // Step 19. Check for mate and stalemate
1381 // All legal moves have been searched and if there are
1382 // no legal moves, it must be mate or stalemate.
1383 // If one move was excluded return fail low score.
1385 return excludedMove ? oldAlpha : (isCheck ? value_mated_in(ply) : VALUE_DRAW);
1387 // Step 20. Update tables
1388 // If the search is not aborted, update the transposition table,
1389 // history counters, and killer moves.
1390 if (AbortSearch || TM.thread_should_stop(threadID))
1393 if (bestValue <= oldAlpha)
1394 TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1396 else if (bestValue >= beta)
1398 TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
1399 move = ss[ply].pv[ply];
1400 TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
1401 if (!pos.move_is_capture_or_promotion(move))
1403 update_history(pos, move, depth, movesSearched, moveCount);
1404 update_killers(move, ss[ply]);
1408 TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
1410 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1416 // qsearch() is the quiescence search function, which is called by the main
1417 // search function when the remaining depth is zero (or, to be more precise,
1418 // less than OnePly).
1420 template <NodeType PvNode>
1421 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta,
1422 Depth depth, int ply, int threadID) {
1424 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1425 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1426 assert(PvNode || alpha == beta - 1);
1428 assert(ply >= 0 && ply < PLY_MAX);
1429 assert(threadID >= 0 && threadID < TM.active_threads());
1434 Value staticValue, bestValue, value, futilityBase, futilityValue;
1435 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1436 const TTEntry* tte = NULL;
1438 Value oldAlpha = alpha;
1440 // Initialize, and make an early exit in case of an aborted search,
1441 // an instant draw, maximum ply reached, etc.
1442 init_node(ss, ply, threadID);
1444 // After init_node() that calls poll()
1445 if (AbortSearch || TM.thread_should_stop(threadID))
1448 if (pos.is_draw() || ply >= PLY_MAX - 1)
1451 // Transposition table lookup. At PV nodes, we don't use the TT for
1452 // pruning, but only for move ordering.
1453 tte = TT.retrieve(pos.get_key());
1454 ttMove = (tte ? tte->move() : MOVE_NONE);
1456 if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1458 assert(tte->type() != VALUE_TYPE_EVAL);
1460 ss[ply].currentMove = ttMove; // Can be MOVE_NONE
1461 return value_from_tt(tte->value(), ply);
1464 isCheck = pos.is_check();
1466 // Evaluate the position statically
1468 staticValue = -VALUE_INFINITE;
1469 else if (tte && (tte->type() & VALUE_TYPE_EVAL))
1470 staticValue = value_from_tt(tte->value(), ply);
1472 staticValue = evaluate(pos, ei, threadID);
1476 ss[ply].eval = staticValue;
1477 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1480 // Initialize "stand pat score", and return it immediately if it is
1482 bestValue = staticValue;
1484 if (bestValue >= beta)
1486 // Store the score to avoid a future costly evaluation() call
1487 if (!isCheck && !tte && ei.kingDanger[pos.side_to_move()] == 0)
1488 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EV_LO, Depth(-127*OnePly), MOVE_NONE);
1493 if (bestValue > alpha)
1496 // If we are near beta then try to get a cutoff pushing checks a bit further
1497 bool deepChecks = (depth == -OnePly && staticValue >= beta - PawnValueMidgame / 8);
1499 // Initialize a MovePicker object for the current position, and prepare
1500 // to search the moves. Because the depth is <= 0 here, only captures,
1501 // queen promotions and checks (only if depth == 0 or depth == -OnePly
1502 // and we are near beta) will be generated.
1503 MovePicker mp = MovePicker(pos, ttMove, deepChecks ? Depth(0) : depth, H);
1505 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1506 futilityBase = staticValue + FutilityMarginQS + ei.kingDanger[pos.side_to_move()];
1508 // Loop through the moves until no moves remain or a beta cutoff occurs
1509 while ( alpha < beta
1510 && (move = mp.get_next_move()) != MOVE_NONE)
1512 assert(move_is_ok(move));
1514 moveIsCheck = pos.move_is_check(move, ci);
1516 // Update current move
1518 ss[ply].currentMove = move;
1526 && !move_is_promotion(move)
1527 && !pos.move_is_passed_pawn_push(move))
1529 futilityValue = futilityBase
1530 + pos.endgame_value_of_piece_on(move_to(move))
1531 + (move_is_ep(move) ? PawnValueEndgame : Value(0));
1533 if (futilityValue < alpha)
1535 if (futilityValue > bestValue)
1536 bestValue = futilityValue;
1541 // Detect blocking evasions that are candidate to be pruned
1542 evasionPrunable = isCheck
1543 && bestValue > value_mated_in(PLY_MAX)
1544 && !pos.move_is_capture(move)
1545 && pos.type_of_piece_on(move_from(move)) != KING
1546 && !pos.can_castle(pos.side_to_move());
1548 // Don't search moves with negative SEE values
1550 && (!isCheck || evasionPrunable)
1552 && !move_is_promotion(move)
1553 && pos.see_sign(move) < 0)
1556 // Make and search the move
1557 pos.do_move(move, st, ci, moveIsCheck);
1558 value = -qsearch<PvNode>(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID);
1559 pos.undo_move(move);
1561 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1564 if (value > bestValue)
1575 // All legal moves have been searched. A special case: If we're in check
1576 // and no legal moves were found, it is checkmate.
1577 if (!moveCount && isCheck) // Mate!
1578 return value_mated_in(ply);
1580 // Update transposition table
1581 Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
1582 if (bestValue <= oldAlpha)
1584 // If bestValue isn't changed it means it is still the static evaluation
1585 // of the node, so keep this info to avoid a future evaluation() call.
1586 ValueType type = (bestValue == staticValue && !ei.kingDanger[pos.side_to_move()] ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER);
1587 TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE);
1589 else if (bestValue >= beta)
1591 move = ss[ply].pv[ply];
1592 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, move);
1594 // Update killers only for good checking moves
1595 if (!pos.move_is_capture_or_promotion(move))
1596 update_killers(move, ss[ply]);
1599 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, d, ss[ply].pv[ply]);
1601 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1607 // sp_search() is used to search from a split point. This function is called
1608 // by each thread working at the split point. It is similar to the normal
1609 // search() function, but simpler. Because we have already probed the hash
1610 // table, done a null move search, and searched the first move before
1611 // splitting, we don't have to repeat all this work in sp_search(). We
1612 // also don't need to store anything to the hash table here: This is taken
1613 // care of after we return from the split point.
1615 template <NodeType PvNode>
1616 void sp_search(SplitPoint* sp, int threadID) {
1618 assert(threadID >= 0 && threadID < TM.active_threads());
1622 Depth ext, newDepth;
1624 Value futilityValueScaled; // NonPV specific
1625 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
1627 value = -VALUE_INFINITE;
1629 Position pos(*sp->pos);
1631 SearchStack* ss = sp->sstack[threadID];
1632 isCheck = pos.is_check();
1634 // Step 10. Loop through moves
1635 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1636 lock_grab(&(sp->lock));
1638 while ( sp->bestValue < sp->beta
1639 && !TM.thread_should_stop(threadID)
1640 && (move = sp->mp->get_next_move()) != MOVE_NONE)
1642 moveCount = ++sp->moves;
1643 lock_release(&(sp->lock));
1645 assert(move_is_ok(move));
1647 moveIsCheck = pos.move_is_check(move, ci);
1648 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1650 // Step 11. Decide the new search depth
1651 ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous);
1652 newDepth = sp->depth - OnePly + ext;
1654 // Update current move
1655 ss[sp->ply].currentMove = move;
1657 // Step 12. Futility pruning (is omitted in PV nodes)
1661 && !captureOrPromotion
1662 && !move_is_castle(move))
1664 // Move count based pruning
1665 if ( moveCount >= futility_move_count(sp->depth)
1666 && ok_to_prune(pos, move, ss[sp->ply].threatMove)
1667 && sp->bestValue > value_mated_in(PLY_MAX))
1669 lock_grab(&(sp->lock));
1673 // Value based pruning
1674 Depth predictedDepth = newDepth - reduction<NonPV>(sp->depth, moveCount);
1675 futilityValueScaled = ss[sp->ply].eval + futility_margin(predictedDepth, moveCount)
1676 + H.gain(pos.piece_on(move_from(move)), move_to(move));
1678 if (futilityValueScaled < sp->beta)
1680 lock_grab(&(sp->lock));
1682 if (futilityValueScaled > sp->bestValue)
1683 sp->bestValue = futilityValueScaled;
1688 // Step 13. Make the move
1689 pos.do_move(move, st, ci, moveIsCheck);
1691 // Step 14. Reduced search
1692 // if the move fails high will be re-searched at full depth.
1693 bool doFullDepthSearch = true;
1696 && !captureOrPromotion
1697 && !move_is_castle(move)
1698 && !move_is_killer(move, ss[sp->ply]))
1700 ss[sp->ply].reduction = reduction<PvNode>(sp->depth, moveCount);
1701 if (ss[sp->ply].reduction)
1703 Value localAlpha = sp->alpha;
1704 value = -search<NonPV>(pos, ss, -(localAlpha+1), -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
1705 doFullDepthSearch = (value > localAlpha && !TM.thread_should_stop(threadID));
1709 // Step 15. Full depth search
1710 if (doFullDepthSearch)
1712 ss[sp->ply].reduction = Depth(0);
1713 Value localAlpha = sp->alpha;
1714 value = -search<NonPV>(pos, ss, -(localAlpha+1), -localAlpha, newDepth, sp->ply+1, true, threadID);
1716 if (PvNode && value > localAlpha && value < sp->beta && !TM.thread_should_stop(threadID))
1717 value = -search<PV>(pos, ss, -sp->beta, -sp->alpha, newDepth, sp->ply+1, false, threadID);
1720 // Step 16. Undo move
1721 pos.undo_move(move);
1723 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1725 // Step 17. Check for new best move
1726 lock_grab(&(sp->lock));
1728 if (value > sp->bestValue && !TM.thread_should_stop(threadID))
1730 sp->bestValue = value;
1732 if (sp->bestValue > sp->alpha)
1734 if (!PvNode || value >= sp->beta)
1735 sp->stopRequest = true;
1737 if (PvNode && value < sp->beta) // This guarantees that always: sp->alpha < sp->beta
1740 sp_update_pv(sp->parentSstack, ss, sp->ply);
1742 if (PvNode && value == value_mate_in(sp->ply + 1))
1743 ss[sp->ply].mateKiller = move;
1748 /* Here we have the lock still grabbed */
1750 sp->slaves[threadID] = 0;
1753 lock_release(&(sp->lock));
1756 // init_node() is called at the beginning of all the search functions
1757 // (search() qsearch(), and so on) and initializes the
1758 // search stack object corresponding to the current node. Once every
1759 // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
1760 // for user input and checks whether it is time to stop the search.
1762 void init_node(SearchStack ss[], int ply, int threadID) {
1764 assert(ply >= 0 && ply < PLY_MAX);
1765 assert(threadID >= 0 && threadID < TM.active_threads());
1767 TM.incrementNodeCounter(threadID);
1772 if (NodesSincePoll >= NodesBetweenPolls)
1779 ss[ply + 2].initKillers();
1784 // update_pv() is called whenever a search returns a value > alpha.
1785 // It updates the PV in the SearchStack object corresponding to the
1788 void update_pv(SearchStack ss[], int ply) {
1790 assert(ply >= 0 && ply < PLY_MAX);
1794 ss[ply].pv[ply] = ss[ply].currentMove;
1796 for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
1797 ss[ply].pv[p] = ss[ply + 1].pv[p];
1799 ss[ply].pv[p] = MOVE_NONE;
1803 // sp_update_pv() is a variant of update_pv for use at split points. The
1804 // difference between the two functions is that sp_update_pv also updates
1805 // the PV at the parent node.
1807 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply) {
1809 assert(ply >= 0 && ply < PLY_MAX);
1813 ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
1815 for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
1816 ss[ply].pv[p] = pss[ply].pv[p] = ss[ply + 1].pv[p];
1818 ss[ply].pv[p] = pss[ply].pv[p] = MOVE_NONE;
1822 // connected_moves() tests whether two moves are 'connected' in the sense
1823 // that the first move somehow made the second move possible (for instance
1824 // if the moving piece is the same in both moves). The first move is assumed
1825 // to be the move that was made to reach the current position, while the
1826 // second move is assumed to be a move from the current position.
1828 bool connected_moves(const Position& pos, Move m1, Move m2) {
1830 Square f1, t1, f2, t2;
1833 assert(move_is_ok(m1));
1834 assert(move_is_ok(m2));
1836 if (m2 == MOVE_NONE)
1839 // Case 1: The moving piece is the same in both moves
1845 // Case 2: The destination square for m2 was vacated by m1
1851 // Case 3: Moving through the vacated square
1852 if ( piece_is_slider(pos.piece_on(f2))
1853 && bit_is_set(squares_between(f2, t2), f1))
1856 // Case 4: The destination square for m2 is defended by the moving piece in m1
1857 p = pos.piece_on(t1);
1858 if (bit_is_set(pos.attacks_from(p, t1), t2))
1861 // Case 5: Discovered check, checking piece is the piece moved in m1
1862 if ( piece_is_slider(p)
1863 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
1864 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
1866 // discovered_check_candidates() works also if the Position's side to
1867 // move is the opposite of the checking piece.
1868 Color them = opposite_color(pos.side_to_move());
1869 Bitboard dcCandidates = pos.discovered_check_candidates(them);
1871 if (bit_is_set(dcCandidates, f2))
1878 // value_is_mate() checks if the given value is a mate one
1879 // eventually compensated for the ply.
1881 bool value_is_mate(Value value) {
1883 assert(abs(value) <= VALUE_INFINITE);
1885 return value <= value_mated_in(PLY_MAX)
1886 || value >= value_mate_in(PLY_MAX);
1890 // move_is_killer() checks if the given move is among the
1891 // killer moves of that ply.
1893 bool move_is_killer(Move m, const SearchStack& ss) {
1895 const Move* k = ss.killers;
1896 for (int i = 0; i < KILLER_MAX; i++, k++)
1904 // extension() decides whether a move should be searched with normal depth,
1905 // or with extended depth. Certain classes of moves (checking moves, in
1906 // particular) are searched with bigger depth than ordinary moves and in
1907 // any case are marked as 'dangerous'. Note that also if a move is not
1908 // extended, as example because the corresponding UCI option is set to zero,
1909 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
1910 template <NodeType PvNode>
1911 Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
1912 bool singleEvasion, bool mateThreat, bool* dangerous) {
1914 assert(m != MOVE_NONE);
1916 Depth result = Depth(0);
1917 *dangerous = moveIsCheck | singleEvasion | mateThreat;
1922 result += CheckExtension[PvNode];
1925 result += SingleEvasionExtension[PvNode];
1928 result += MateThreatExtension[PvNode];
1931 if (pos.type_of_piece_on(move_from(m)) == PAWN)
1933 Color c = pos.side_to_move();
1934 if (relative_rank(c, move_to(m)) == RANK_7)
1936 result += PawnPushTo7thExtension[PvNode];
1939 if (pos.pawn_is_passed(c, move_to(m)))
1941 result += PassedPawnExtension[PvNode];
1946 if ( captureOrPromotion
1947 && pos.type_of_piece_on(move_to(m)) != PAWN
1948 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
1949 - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))
1950 && !move_is_promotion(m)
1953 result += PawnEndgameExtension[PvNode];
1958 && captureOrPromotion
1959 && pos.type_of_piece_on(move_to(m)) != PAWN
1960 && pos.see_sign(m) >= 0)
1966 return Min(result, OnePly);
1970 // ok_to_do_nullmove() looks at the current position and decides whether
1971 // doing a 'null move' should be allowed. In order to avoid zugzwang
1972 // problems, null moves are not allowed when the side to move has very
1973 // little material left. Currently, the test is a bit too simple: Null
1974 // moves are avoided only when the side to move has only pawns left.
1975 // It's probably a good idea to avoid null moves in at least some more
1976 // complicated endgames, e.g. KQ vs KR. FIXME
1978 bool ok_to_do_nullmove(const Position& pos) {
1980 return pos.non_pawn_material(pos.side_to_move()) != Value(0);
1984 // ok_to_prune() tests whether it is safe to forward prune a move. Only
1985 // non-tactical moves late in the move list close to the leaves are
1986 // candidates for pruning.
1988 bool ok_to_prune(const Position& pos, Move m, Move threat) {
1990 assert(move_is_ok(m));
1991 assert(threat == MOVE_NONE || move_is_ok(threat));
1992 assert(!pos.move_is_check(m));
1993 assert(!pos.move_is_capture_or_promotion(m));
1994 assert(!pos.move_is_passed_pawn_push(m));
1996 Square mfrom, mto, tfrom, tto;
1998 // Prune if there isn't any threat move
1999 if (threat == MOVE_NONE)
2002 mfrom = move_from(m);
2004 tfrom = move_from(threat);
2005 tto = move_to(threat);
2007 // Case 1: Don't prune moves which move the threatened piece
2011 // Case 2: If the threatened piece has value less than or equal to the
2012 // value of the threatening piece, don't prune move which defend it.
2013 if ( pos.move_is_capture(threat)
2014 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
2015 || pos.type_of_piece_on(tfrom) == KING)
2016 && pos.move_attacks_square(m, tto))
2019 // Case 3: If the moving piece in the threatened move is a slider, don't
2020 // prune safe moves which block its ray.
2021 if ( piece_is_slider(pos.piece_on(tfrom))
2022 && bit_is_set(squares_between(tfrom, tto), mto)
2023 && pos.see_sign(m) >= 0)
2030 // ok_to_use_TT() returns true if a transposition table score
2031 // can be used at a given point in search.
2033 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
2035 Value v = value_from_tt(tte->value(), ply);
2037 return ( tte->depth() >= depth
2038 || v >= Max(value_mate_in(PLY_MAX), beta)
2039 || v < Min(value_mated_in(PLY_MAX), beta))
2041 && ( (is_lower_bound(tte->type()) && v >= beta)
2042 || (is_upper_bound(tte->type()) && v < beta));
2046 // refine_eval() returns the transposition table score if
2047 // possible otherwise falls back on static position evaluation.
2049 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
2054 Value v = value_from_tt(tte->value(), ply);
2056 if ( (is_lower_bound(tte->type()) && v >= defaultEval)
2057 || (is_upper_bound(tte->type()) && v < defaultEval))
2064 // update_history() registers a good move that produced a beta-cutoff
2065 // in history and marks as failures all the other moves of that ply.
2067 void update_history(const Position& pos, Move move, Depth depth,
2068 Move movesSearched[], int moveCount) {
2072 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
2074 for (int i = 0; i < moveCount - 1; i++)
2076 m = movesSearched[i];
2080 if (!pos.move_is_capture_or_promotion(m))
2081 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
2086 // update_killers() add a good move that produced a beta-cutoff
2087 // among the killer moves of that ply.
2089 void update_killers(Move m, SearchStack& ss) {
2091 if (m == ss.killers[0])
2094 for (int i = KILLER_MAX - 1; i > 0; i--)
2095 ss.killers[i] = ss.killers[i - 1];
2101 // update_gains() updates the gains table of a non-capture move given
2102 // the static position evaluation before and after the move.
2104 void update_gains(const Position& pos, Move m, Value before, Value after) {
2107 && before != VALUE_NONE
2108 && after != VALUE_NONE
2109 && pos.captured_piece() == NO_PIECE_TYPE
2110 && !move_is_castle(m)
2111 && !move_is_promotion(m))
2112 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
2116 // current_search_time() returns the number of milliseconds which have passed
2117 // since the beginning of the current search.
2119 int current_search_time() {
2121 return get_system_time() - SearchStartTime;
2125 // nps() computes the current nodes/second count.
2129 int t = current_search_time();
2130 return (t > 0 ? int((TM.nodes_searched() * 1000) / t) : 0);
2134 // poll() performs two different functions: It polls for user input, and it
2135 // looks at the time consumed so far and decides if it's time to abort the
2140 static int lastInfoTime;
2141 int t = current_search_time();
2146 // We are line oriented, don't read single chars
2147 std::string command;
2149 if (!std::getline(std::cin, command))
2152 if (command == "quit")
2155 PonderSearch = false;
2159 else if (command == "stop")
2162 PonderSearch = false;
2164 else if (command == "ponderhit")
2168 // Print search information
2172 else if (lastInfoTime > t)
2173 // HACK: Must be a new search where we searched less than
2174 // NodesBetweenPolls nodes during the first second of search.
2177 else if (t - lastInfoTime >= 1000)
2184 if (dbg_show_hit_rate)
2185 dbg_print_hit_rate();
2187 cout << "info nodes " << TM.nodes_searched() << " nps " << nps()
2188 << " time " << t << " hashfull " << TT.full() << endl;
2191 // Should we stop the search?
2195 bool stillAtFirstMove = FirstRootMove
2196 && !AspirationFailLow
2197 && t > MaxSearchTime + ExtraSearchTime;
2199 bool noMoreTime = t > AbsoluteMaxSearchTime
2200 || stillAtFirstMove;
2202 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2203 || (ExactMaxTime && t >= ExactMaxTime)
2204 || (Iteration >= 3 && MaxNodes && TM.nodes_searched() >= MaxNodes))
2209 // ponderhit() is called when the program is pondering (i.e. thinking while
2210 // it's the opponent's turn to move) in order to let the engine know that
2211 // it correctly predicted the opponent's move.
2215 int t = current_search_time();
2216 PonderSearch = false;
2218 bool stillAtFirstMove = FirstRootMove
2219 && !AspirationFailLow
2220 && t > MaxSearchTime + ExtraSearchTime;
2222 bool noMoreTime = t > AbsoluteMaxSearchTime
2223 || stillAtFirstMove;
2225 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2230 // init_ss_array() does a fast reset of the first entries of a SearchStack array
2232 void init_ss_array(SearchStack ss[]) {
2234 for (int i = 0; i < 3; i++)
2237 ss[i].initKillers();
2242 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2243 // while the program is pondering. The point is to work around a wrinkle in
2244 // the UCI protocol: When pondering, the engine is not allowed to give a
2245 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2246 // We simply wait here until one of these commands is sent, and return,
2247 // after which the bestmove and pondermove will be printed (in id_loop()).
2249 void wait_for_stop_or_ponderhit() {
2251 std::string command;
2255 if (!std::getline(std::cin, command))
2258 if (command == "quit")
2263 else if (command == "ponderhit" || command == "stop")
2269 // print_pv_info() prints to standard output and eventually to log file information on
2270 // the current PV line. It is called at each iteration or after a new pv is found.
2272 void print_pv_info(const Position& pos, SearchStack ss[], Value alpha, Value beta, Value value) {
2274 cout << "info depth " << Iteration
2275 << " score " << value_to_string(value)
2276 << ((value >= beta) ? " lowerbound" :
2277 ((value <= alpha)? " upperbound" : ""))
2278 << " time " << current_search_time()
2279 << " nodes " << TM.nodes_searched()
2283 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
2284 cout << ss[0].pv[j] << " ";
2290 ValueType type = (value >= beta ? VALUE_TYPE_LOWER
2291 : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT));
2293 LogFile << pretty_pv(pos, current_search_time(), Iteration,
2294 TM.nodes_searched(), value, type, ss[0].pv) << endl;
2299 // init_thread() is the function which is called when a new thread is
2300 // launched. It simply calls the idle_loop() function with the supplied
2301 // threadID. There are two versions of this function; one for POSIX
2302 // threads and one for Windows threads.
2304 #if !defined(_MSC_VER)
2306 void* init_thread(void *threadID) {
2308 TM.idle_loop(*(int*)threadID, NULL);
2314 DWORD WINAPI init_thread(LPVOID threadID) {
2316 TM.idle_loop(*(int*)threadID, NULL);
2323 /// The ThreadsManager class
2325 // resetNodeCounters(), resetBetaCounters(), searched_nodes() and
2326 // get_beta_counters() are getters/setters for the per thread
2327 // counters used to sort the moves at root.
2329 void ThreadsManager::resetNodeCounters() {
2331 for (int i = 0; i < MAX_THREADS; i++)
2332 threads[i].nodes = 0ULL;
2335 void ThreadsManager::resetBetaCounters() {
2337 for (int i = 0; i < MAX_THREADS; i++)
2338 threads[i].betaCutOffs[WHITE] = threads[i].betaCutOffs[BLACK] = 0ULL;
2341 int64_t ThreadsManager::nodes_searched() const {
2343 int64_t result = 0ULL;
2344 for (int i = 0; i < ActiveThreads; i++)
2345 result += threads[i].nodes;
2350 void ThreadsManager::get_beta_counters(Color us, int64_t& our, int64_t& their) const {
2353 for (int i = 0; i < MAX_THREADS; i++)
2355 our += threads[i].betaCutOffs[us];
2356 their += threads[i].betaCutOffs[opposite_color(us)];
2361 // idle_loop() is where the threads are parked when they have no work to do.
2362 // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint
2363 // object for which the current thread is the master.
2365 void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) {
2367 assert(threadID >= 0 && threadID < MAX_THREADS);
2371 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2372 // master should exit as last one.
2373 if (AllThreadsShouldExit)
2376 threads[threadID].state = THREAD_TERMINATED;
2380 // If we are not thinking, wait for a condition to be signaled
2381 // instead of wasting CPU time polling for work.
2382 while (AllThreadsShouldSleep || threadID >= ActiveThreads)
2385 assert(threadID != 0);
2386 threads[threadID].state = THREAD_SLEEPING;
2388 #if !defined(_MSC_VER)
2389 lock_grab(&WaitLock);
2390 if (AllThreadsShouldSleep || threadID >= ActiveThreads)
2391 pthread_cond_wait(&WaitCond, &WaitLock);
2392 lock_release(&WaitLock);
2394 WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2398 // If thread has just woken up, mark it as available
2399 if (threads[threadID].state == THREAD_SLEEPING)
2400 threads[threadID].state = THREAD_AVAILABLE;
2402 // If this thread has been assigned work, launch a search
2403 if (threads[threadID].state == THREAD_WORKISWAITING)
2405 assert(!AllThreadsShouldExit && !AllThreadsShouldSleep);
2407 threads[threadID].state = THREAD_SEARCHING;
2409 if (threads[threadID].splitPoint->pvNode)
2410 sp_search<PV>(threads[threadID].splitPoint, threadID);
2412 sp_search<NonPV>(threads[threadID].splitPoint, threadID);
2414 assert(threads[threadID].state == THREAD_SEARCHING);
2416 threads[threadID].state = THREAD_AVAILABLE;
2419 // If this thread is the master of a split point and all threads have
2420 // finished their work at this split point, return from the idle loop.
2421 if (sp && sp->cpus == 0)
2423 // Because sp->cpus is decremented under lock protection,
2424 // be sure sp->lock has been released before to proceed.
2425 lock_grab(&(sp->lock));
2426 lock_release(&(sp->lock));
2428 assert(threads[threadID].state == THREAD_AVAILABLE);
2430 threads[threadID].state = THREAD_SEARCHING;
2437 // init_threads() is called during startup. It launches all helper threads,
2438 // and initializes the split point stack and the global locks and condition
2441 void ThreadsManager::init_threads() {
2446 #if !defined(_MSC_VER)
2447 pthread_t pthread[1];
2450 // Initialize global locks
2451 lock_init(&MPLock, NULL);
2452 lock_init(&WaitLock, NULL);
2454 #if !defined(_MSC_VER)
2455 pthread_cond_init(&WaitCond, NULL);
2457 for (i = 0; i < MAX_THREADS; i++)
2458 SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0);
2461 // Initialize SplitPointStack locks
2462 for (i = 0; i < MAX_THREADS; i++)
2463 for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
2465 SplitPointStack[i][j].parent = NULL;
2466 lock_init(&(SplitPointStack[i][j].lock), NULL);
2469 // Will be set just before program exits to properly end the threads
2470 AllThreadsShouldExit = false;
2472 // Threads will be put to sleep as soon as created
2473 AllThreadsShouldSleep = true;
2475 // All threads except the main thread should be initialized to THREAD_AVAILABLE
2477 threads[0].state = THREAD_SEARCHING;
2478 for (i = 1; i < MAX_THREADS; i++)
2479 threads[i].state = THREAD_AVAILABLE;
2481 // Launch the helper threads
2482 for (i = 1; i < MAX_THREADS; i++)
2485 #if !defined(_MSC_VER)
2486 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&i)) == 0);
2488 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, NULL) != NULL);
2493 cout << "Failed to create thread number " << i << endl;
2494 Application::exit_with_failure();
2497 // Wait until the thread has finished launching and is gone to sleep
2498 while (threads[i].state != THREAD_SLEEPING) {}
2503 // exit_threads() is called when the program exits. It makes all the
2504 // helper threads exit cleanly.
2506 void ThreadsManager::exit_threads() {
2508 ActiveThreads = MAX_THREADS; // HACK
2509 AllThreadsShouldSleep = true; // HACK
2510 wake_sleeping_threads();
2512 // This makes the threads to exit idle_loop()
2513 AllThreadsShouldExit = true;
2515 // Wait for thread termination
2516 for (int i = 1; i < MAX_THREADS; i++)
2517 while (threads[i].state != THREAD_TERMINATED);
2519 // Now we can safely destroy the locks
2520 for (int i = 0; i < MAX_THREADS; i++)
2521 for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
2522 lock_destroy(&(SplitPointStack[i][j].lock));
2524 lock_destroy(&WaitLock);
2525 lock_destroy(&MPLock);
2529 // thread_should_stop() checks whether the thread should stop its search.
2530 // This can happen if a beta cutoff has occurred in the thread's currently
2531 // active split point, or in some ancestor of the current split point.
2533 bool ThreadsManager::thread_should_stop(int threadID) const {
2535 assert(threadID >= 0 && threadID < ActiveThreads);
2539 for (sp = threads[threadID].splitPoint; sp && !sp->stopRequest; sp = sp->parent) {}
2544 // thread_is_available() checks whether the thread with threadID "slave" is
2545 // available to help the thread with threadID "master" at a split point. An
2546 // obvious requirement is that "slave" must be idle. With more than two
2547 // threads, this is not by itself sufficient: If "slave" is the master of
2548 // some active split point, it is only available as a slave to the other
2549 // threads which are busy searching the split point at the top of "slave"'s
2550 // split point stack (the "helpful master concept" in YBWC terminology).
2552 bool ThreadsManager::thread_is_available(int slave, int master) const {
2554 assert(slave >= 0 && slave < ActiveThreads);
2555 assert(master >= 0 && master < ActiveThreads);
2556 assert(ActiveThreads > 1);
2558 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2561 // Make a local copy to be sure doesn't change under our feet
2562 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2564 if (localActiveSplitPoints == 0)
2565 // No active split points means that the thread is available as
2566 // a slave for any other thread.
2569 if (ActiveThreads == 2)
2572 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2573 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2574 // could have been set to 0 by another thread leading to an out of bound access.
2575 if (SplitPointStack[slave][localActiveSplitPoints - 1].slaves[master])
2582 // available_thread_exists() tries to find an idle thread which is available as
2583 // a slave for the thread with threadID "master".
2585 bool ThreadsManager::available_thread_exists(int master) const {
2587 assert(master >= 0 && master < ActiveThreads);
2588 assert(ActiveThreads > 1);
2590 for (int i = 0; i < ActiveThreads; i++)
2591 if (thread_is_available(i, master))
2598 // split() does the actual work of distributing the work at a node between
2599 // several threads at PV nodes. If it does not succeed in splitting the
2600 // node (because no idle threads are available, or because we have no unused
2601 // split point objects), the function immediately returns false. If
2602 // splitting is possible, a SplitPoint object is initialized with all the
2603 // data that must be copied to the helper threads (the current position and
2604 // search stack, alpha, beta, the search depth, etc.), and we tell our
2605 // helper threads that they have been assigned work. This will cause them
2606 // to instantly leave their idle loops and call sp_search_pv(). When all
2607 // threads have returned from sp_search_pv (or, equivalently, when
2608 // splitPoint->cpus becomes 0), split() returns true.
2610 template <bool Fake>
2611 bool ThreadsManager::split(const Position& p, SearchStack* sstck, int ply,
2612 Value* alpha, const Value beta, Value* bestValue,
2613 Depth depth, bool mateThreat, int* moves, MovePicker* mp, int master, bool pvNode) {
2616 assert(sstck != NULL);
2617 assert(ply >= 0 && ply < PLY_MAX);
2618 assert(*bestValue >= -VALUE_INFINITE);
2619 assert(*bestValue <= *alpha);
2620 assert(*alpha < beta);
2621 assert(beta <= VALUE_INFINITE);
2622 assert(depth > Depth(0));
2623 assert(master >= 0 && master < ActiveThreads);
2624 assert(Fake || ActiveThreads > 1);
2626 SplitPoint* splitPoint;
2630 // If no other thread is available to help us, or if we have too many
2631 // active split points, don't split.
2632 if ( (!Fake && !available_thread_exists(master))
2633 || threads[master].activeSplitPoints >= ACTIVE_SPLIT_POINTS_MAX)
2635 lock_release(&MPLock);
2639 // Pick the next available split point object from the split point stack
2640 splitPoint = &SplitPointStack[master][threads[master].activeSplitPoints];
2642 // Initialize the split point object
2643 splitPoint->parent = threads[master].splitPoint;
2644 splitPoint->stopRequest = false;
2645 splitPoint->ply = ply;
2646 splitPoint->depth = depth;
2647 splitPoint->mateThreat = mateThreat;
2648 splitPoint->alpha = *alpha;
2649 splitPoint->beta = beta;
2650 splitPoint->pvNode = pvNode;
2651 splitPoint->bestValue = *bestValue;
2652 splitPoint->master = master;
2653 splitPoint->mp = mp;
2654 splitPoint->moves = *moves;
2655 splitPoint->cpus = 1;
2656 splitPoint->pos = &p;
2657 splitPoint->parentSstack = sstck;
2658 for (int i = 0; i < ActiveThreads; i++)
2659 splitPoint->slaves[i] = 0;
2661 threads[master].splitPoint = splitPoint;
2662 threads[master].activeSplitPoints++;
2664 // If we are here it means we are not available
2665 assert(threads[master].state != THREAD_AVAILABLE);
2667 // Allocate available threads setting state to THREAD_BOOKED
2668 for (int i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint; i++)
2669 if (!Fake && thread_is_available(i, master))
2671 threads[i].state = THREAD_BOOKED;
2672 threads[i].splitPoint = splitPoint;
2673 splitPoint->slaves[i] = 1;
2677 assert(Fake || splitPoint->cpus > 1);
2679 // We can release the lock because slave threads are already booked and master is not available
2680 lock_release(&MPLock);
2682 // Tell the threads that they have work to do. This will make them leave
2683 // their idle loop. But before copy search stack tail for each thread.
2684 for (int i = 0; i < ActiveThreads; i++)
2685 if (i == master || splitPoint->slaves[i])
2687 memcpy(splitPoint->sstack[i] + ply - 1, sstck + ply - 1, 4 * sizeof(SearchStack));
2689 assert(i == master || threads[i].state == THREAD_BOOKED);
2691 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2694 // Everything is set up. The master thread enters the idle loop, from
2695 // which it will instantly launch a search, because its state is
2696 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2697 // idle loop, which means that the main thread will return from the idle
2698 // loop when all threads have finished their work at this split point
2699 // (i.e. when splitPoint->cpus == 0).
2700 idle_loop(master, splitPoint);
2702 // We have returned from the idle loop, which means that all threads are
2703 // finished. Update alpha and bestValue, and return.
2706 *alpha = splitPoint->alpha;
2707 *bestValue = splitPoint->bestValue;
2708 threads[master].activeSplitPoints--;
2709 threads[master].splitPoint = splitPoint->parent;
2711 lock_release(&MPLock);
2716 // wake_sleeping_threads() wakes up all sleeping threads when it is time
2717 // to start a new search from the root.
2719 void ThreadsManager::wake_sleeping_threads() {
2721 assert(AllThreadsShouldSleep);
2722 assert(ActiveThreads > 0);
2724 AllThreadsShouldSleep = false;
2726 if (ActiveThreads == 1)
2729 #if !defined(_MSC_VER)
2730 pthread_mutex_lock(&WaitLock);
2731 pthread_cond_broadcast(&WaitCond);
2732 pthread_mutex_unlock(&WaitLock);
2734 for (int i = 1; i < MAX_THREADS; i++)
2735 SetEvent(SitIdleEvent[i]);
2741 // put_threads_to_sleep() makes all the threads go to sleep just before
2742 // to leave think(), at the end of the search. Threads should have already
2743 // finished the job and should be idle.
2745 void ThreadsManager::put_threads_to_sleep() {
2747 assert(!AllThreadsShouldSleep);
2749 // This makes the threads to go to sleep
2750 AllThreadsShouldSleep = true;
2753 /// The RootMoveList class
2755 // RootMoveList c'tor
2757 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
2759 SearchStack ss[PLY_MAX_PLUS_2];
2760 MoveStack mlist[MaxRootMoves];
2762 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
2764 // Generate all legal moves
2765 MoveStack* last = generate_moves(pos, mlist);
2767 // Add each move to the moves[] array
2768 for (MoveStack* cur = mlist; cur != last; cur++)
2770 bool includeMove = includeAllMoves;
2772 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
2773 includeMove = (searchMoves[k] == cur->move);
2778 // Find a quick score for the move
2780 pos.do_move(cur->move, st);
2781 moves[count].move = cur->move;
2782 moves[count].score = -qsearch<PV>(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0);
2783 moves[count].pv[0] = cur->move;
2784 moves[count].pv[1] = MOVE_NONE;
2785 pos.undo_move(cur->move);
2792 // RootMoveList simple methods definitions
2794 void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
2796 moves[moveNum].nodes = nodes;
2797 moves[moveNum].cumulativeNodes += nodes;
2800 void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
2802 moves[moveNum].ourBeta = our;
2803 moves[moveNum].theirBeta = their;
2806 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
2810 for (j = 0; pv[j] != MOVE_NONE; j++)
2811 moves[moveNum].pv[j] = pv[j];
2813 moves[moveNum].pv[j] = MOVE_NONE;
2817 // RootMoveList::sort() sorts the root move list at the beginning of a new
2820 void RootMoveList::sort() {
2822 sort_multipv(count - 1); // Sort all items
2826 // RootMoveList::sort_multipv() sorts the first few moves in the root move
2827 // list by their scores and depths. It is used to order the different PVs
2828 // correctly in MultiPV mode.
2830 void RootMoveList::sort_multipv(int n) {
2834 for (i = 1; i <= n; i++)
2836 RootMove rm = moves[i];
2837 for (j = i; j > 0 && moves[j - 1] < rm; j--)
2838 moves[j] = moves[j - 1];