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-2009 Marco Costalba
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
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* waitSp);
86 bool split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
87 Depth depth, int* moves, MovePicker* mp, int master, bool pvNode);
90 friend void poll(SearchStack ss[], int ply);
93 volatile bool AllThreadsShouldExit, AllThreadsShouldSleep;
94 Thread threads[MAX_THREADS];
95 SplitPoint SplitPointStack[MAX_THREADS][ACTIVE_SPLIT_POINTS_MAX];
99 #if !defined(_MSC_VER)
100 pthread_cond_t WaitCond;
101 pthread_mutex_t WaitLock;
103 HANDLE SitIdleEvent[MAX_THREADS];
109 // RootMove struct is used for moves at the root at the tree. For each
110 // root move, we store a score, a node count, and a PV (really a refutation
111 // in the case of moves which fail low).
115 RootMove() { nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL; }
117 // RootMove::operator<() is the comparison function used when
118 // sorting the moves. A move m1 is considered to be better
119 // than a move m2 if it has a higher score, or if the moves
120 // have equal score but m1 has the higher node count.
121 bool operator<(const RootMove& m) const {
123 return score != m.score ? score < m.score : theirBeta <= m.theirBeta;
128 int64_t nodes, cumulativeNodes, ourBeta, theirBeta;
129 Move pv[PLY_MAX_PLUS_2];
133 // The RootMoveList class is essentially an array of RootMove objects, with
134 // a handful of methods for accessing the data in the individual moves.
139 RootMoveList(Position& pos, Move searchMoves[]);
141 int move_count() const { return count; }
142 Move get_move(int moveNum) const { return moves[moveNum].move; }
143 Value get_move_score(int moveNum) const { return moves[moveNum].score; }
144 void set_move_score(int moveNum, Value score) { moves[moveNum].score = score; }
145 Move get_move_pv(int moveNum, int i) const { return moves[moveNum].pv[i]; }
146 int64_t get_move_cumulative_nodes(int moveNum) const { return moves[moveNum].cumulativeNodes; }
148 void set_move_nodes(int moveNum, int64_t nodes);
149 void set_beta_counters(int moveNum, int64_t our, int64_t their);
150 void set_move_pv(int moveNum, const Move pv[]);
152 void sort_multipv(int n);
155 static const int MaxRootMoves = 500;
156 RootMove moves[MaxRootMoves];
165 const Depth RazorDepth = 4 * OnePly;
166 inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * d); }
168 // Search depth at iteration 1
169 const Depth InitialDepth = OnePly;
171 // Use internal iterative deepening?
172 const bool UseIIDAtPVNodes = true;
173 const bool UseIIDAtNonPVNodes = true;
175 // Internal iterative deepening margin. At Non-PV moves, when
176 // UseIIDAtNonPVNodes is true, we do an internal iterative deepening
177 // search when the static evaluation is at most IIDMargin below beta.
178 const Value IIDMargin = Value(0x100);
180 // Easy move margin. An easy move candidate must be at least this much
181 // better than the second best move.
182 const Value EasyMoveMargin = Value(0x200);
184 // Null move margin. A null move search will not be done if the static
185 // evaluation of the position is more than NullMoveMargin below beta.
186 const Value NullMoveMargin = Value(0x200);
188 // If the TT move is at least SingleReplyMargin better then the
189 // remaining ones we will extend it.
190 const Value SingleReplyMargin = Value(0x20);
192 /// Lookup tables initialized at startup
194 // Reduction lookup tables and their getter functions
195 int8_t PVReductionMatrix[64][64]; // [depth][moveNumber]
196 int8_t NonPVReductionMatrix[64][64]; // [depth][moveNumber]
198 inline Depth pv_reduction(Depth d, int mn) { return (Depth) PVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; }
199 inline Depth nonpv_reduction(Depth d, int mn) { return (Depth) NonPVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; }
201 // Futility lookup tables and their getter functions
202 const Value FutilityMarginQS = Value(0x80);
203 int32_t FutilityMarginsMatrix[14][64]; // [depth][moveNumber]
204 int FutilityMoveCountArray[32]; // [depth]
206 inline Value futility_margin(Depth d, int mn) { return Value(d < 7*OnePly ? FutilityMarginsMatrix[Max(d, 0)][Min(mn, 63)] : 2 * VALUE_INFINITE); }
207 inline int futility_move_count(Depth d) { return d < 16*OnePly ? FutilityMoveCountArray[d] : 512; }
209 /// Variables initialized by UCI options
211 // Depth limit for use of dynamic threat detection
214 // Last seconds noise filtering (LSN)
215 const bool UseLSNFiltering = true;
216 const int LSNTime = 4000; // In milliseconds
217 const Value LSNValue = value_from_centipawns(200);
218 bool loseOnTime = false;
220 // Extensions. Array index 0 is used at non-PV nodes, index 1 at PV nodes.
221 Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2];
222 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
224 // Iteration counters
227 // Scores and number of times the best move changed for each iteration
228 Value ValueByIteration[PLY_MAX_PLUS_2];
229 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
231 // Search window management
237 // Time managment variables
240 int MaxNodes, MaxDepth;
241 int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
242 bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
243 bool AbortSearch, Quit;
244 bool AspirationFailLow;
246 // Show current line?
247 bool ShowCurrentLine;
251 std::ofstream LogFile;
253 // MP related variables
254 Depth MinimumSplitDepth;
255 int MaxThreadsPerSplitPoint;
258 // Node counters, used only by thread[0] but try to keep in different
259 // cache lines (64 bytes each) from the heavy SMP read accessed variables.
261 int NodesBetweenPolls = 30000;
268 Value id_loop(const Position& pos, Move searchMoves[]);
269 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta);
270 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
271 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE);
272 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
273 void sp_search(SplitPoint* sp, int threadID);
274 void sp_search_pv(SplitPoint* sp, int threadID);
275 void init_node(SearchStack ss[], int ply, int threadID);
276 void update_pv(SearchStack ss[], int ply);
277 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply);
278 bool connected_moves(const Position& pos, Move m1, Move m2);
279 bool value_is_mate(Value value);
280 bool move_is_killer(Move m, const SearchStack& ss);
281 Depth extension(const Position&, Move, bool, bool, bool, bool, bool, bool*);
282 bool ok_to_do_nullmove(const Position& pos);
283 bool ok_to_prune(const Position& pos, Move m, Move threat);
284 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
285 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
286 void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
287 void update_killers(Move m, SearchStack& ss);
288 void update_gains(const Position& pos, Move move, Value before, Value after);
290 int current_search_time();
292 void poll(SearchStack ss[], int ply);
294 void wait_for_stop_or_ponderhit();
295 void init_ss_array(SearchStack ss[]);
297 #if !defined(_MSC_VER)
298 void *init_thread(void *threadID);
300 DWORD WINAPI init_thread(LPVOID threadID);
310 /// init_threads(), exit_threads() and nodes_searched() are helpers to
311 /// give accessibility to some TM methods from outside of current file.
313 void init_threads() { TM.init_threads(); }
314 void exit_threads() { TM.exit_threads(); }
315 int64_t nodes_searched() { return TM.nodes_searched(); }
318 /// perft() is our utility to verify move generation is bug free. All the legal
319 /// moves up to given depth are generated and counted and the sum returned.
321 int perft(Position& pos, Depth depth)
325 MovePicker mp = MovePicker(pos, MOVE_NONE, depth, H);
327 // If we are at the last ply we don't need to do and undo
328 // the moves, just to count them.
329 if (depth <= OnePly) // Replace with '<' to test also qsearch
331 while (mp.get_next_move()) sum++;
335 // Loop through all legal moves
337 while ((move = mp.get_next_move()) != MOVE_NONE)
340 pos.do_move(move, st, ci, pos.move_is_check(move, ci));
341 sum += perft(pos, depth - OnePly);
348 /// think() is the external interface to Stockfish's search, and is called when
349 /// the program receives the UCI 'go' command. It initializes various
350 /// search-related global variables, and calls root_search(). It returns false
351 /// when a quit command is received during the search.
353 bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
354 int time[], int increment[], int movesToGo, int maxDepth,
355 int maxNodes, int maxTime, Move searchMoves[]) {
357 // Initialize global search variables
358 StopOnPonderhit = AbortSearch = Quit = false;
359 AspirationFailLow = false;
361 SearchStartTime = get_system_time();
362 ExactMaxTime = maxTime;
365 InfiniteSearch = infinite;
366 PonderSearch = ponder;
367 UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
369 // Look for a book move, only during games, not tests
370 if (UseTimeManagement && get_option_value_bool("OwnBook"))
373 if (get_option_value_string("Book File") != OpeningBook.file_name())
374 OpeningBook.open(get_option_value_string("Book File"));
376 bookMove = OpeningBook.get_move(pos);
377 if (bookMove != MOVE_NONE)
380 wait_for_stop_or_ponderhit();
382 cout << "bestmove " << bookMove << endl;
387 TM.resetNodeCounters();
389 if (button_was_pressed("New Game"))
390 loseOnTime = false; // Reset at the beginning of a new game
392 // Read UCI option values
393 TT.set_size(get_option_value_int("Hash"));
394 if (button_was_pressed("Clear Hash"))
397 bool PonderingEnabled = get_option_value_bool("Ponder");
398 MultiPV = get_option_value_int("MultiPV");
400 CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)"));
401 CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)"));
403 SingleEvasionExtension[1] = Depth(get_option_value_int("Single Evasion Extension (PV nodes)"));
404 SingleEvasionExtension[0] = Depth(get_option_value_int("Single Evasion Extension (non-PV nodes)"));
406 PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)"));
407 PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
409 PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
410 PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
412 PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
413 PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)"));
415 MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
416 MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
418 ThreatDepth = get_option_value_int("Threat Depth") * OnePly;
420 Chess960 = get_option_value_bool("UCI_Chess960");
421 ShowCurrentLine = get_option_value_bool("UCI_ShowCurrLine");
422 UseLogFile = get_option_value_bool("Use Search Log");
424 LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app);
426 MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly;
427 MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point");
429 read_weights(pos.side_to_move());
431 // Set the number of active threads
432 int newActiveThreads = get_option_value_int("Threads");
433 if (newActiveThreads != TM.active_threads())
435 TM.set_active_threads(newActiveThreads);
436 init_eval(TM.active_threads());
437 // HACK: init_eval() destroys the static castleRightsMask[] array in the
438 // Position class. The below line repairs the damage.
439 Position p(pos.to_fen());
443 // Wake up sleeping threads
444 TM.wake_sleeping_threads();
447 int myTime = time[side_to_move];
448 int myIncrement = increment[side_to_move];
449 if (UseTimeManagement)
451 if (!movesToGo) // Sudden death time control
455 MaxSearchTime = myTime / 30 + myIncrement;
456 AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
458 else // Blitz game without increment
460 MaxSearchTime = myTime / 30;
461 AbsoluteMaxSearchTime = myTime / 8;
464 else // (x moves) / (y minutes)
468 MaxSearchTime = myTime / 2;
469 AbsoluteMaxSearchTime = (myTime > 3000)? (myTime - 500) : ((myTime * 3) / 4);
473 MaxSearchTime = myTime / Min(movesToGo, 20);
474 AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
478 if (PonderingEnabled)
480 MaxSearchTime += MaxSearchTime / 4;
481 MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime);
485 // Set best NodesBetweenPolls interval
487 NodesBetweenPolls = Min(MaxNodes, 30000);
488 else if (myTime && myTime < 1000)
489 NodesBetweenPolls = 1000;
490 else if (myTime && myTime < 5000)
491 NodesBetweenPolls = 5000;
493 NodesBetweenPolls = 30000;
495 // Write information to search log file
497 LogFile << "Searching: " << pos.to_fen() << endl
498 << "infinite: " << infinite
499 << " ponder: " << ponder
500 << " time: " << myTime
501 << " increment: " << myIncrement
502 << " moves to go: " << movesToGo << endl;
504 // LSN filtering. Used only for developing purpose. Disabled by default.
508 // Step 2. If after last move we decided to lose on time, do it now!
509 while (SearchStartTime + myTime + 1000 > get_system_time())
513 // We're ready to start thinking. Call the iterative deepening loop function
514 Value v = id_loop(pos, searchMoves);
518 // Step 1. If this is sudden death game and our position is hopeless,
519 // decide to lose on time.
520 if ( !loseOnTime // If we already lost on time, go to step 3.
530 // Step 3. Now after stepping over the time limit, reset flag for next match.
538 TM.put_threads_to_sleep();
544 /// init_search() is called during startup. It initializes various lookup tables
548 // Init our reduction lookup tables
549 for (int i = 1; i < 64; i++) // i == depth (OnePly = 1)
550 for (int j = 1; j < 64; j++) // j == moveNumber
552 double pvRed = 0.5 + log(double(i)) * log(double(j)) / 6.0;
553 double nonPVRed = 0.5 + log(double(i)) * log(double(j)) / 3.0;
554 PVReductionMatrix[i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0);
555 NonPVReductionMatrix[i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0);
558 // Init futility margins array
559 for (int i = 0; i < 14; i++) // i == depth (OnePly = 2)
560 for (int j = 0; j < 64; j++) // j == moveNumber
562 FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j; // FIXME: test using log instead of BSR
565 // Init futility move count array
566 for (int i = 0; i < 32; i++) // i == depth (OnePly = 2)
567 FutilityMoveCountArray[i] = 3 + (1 << (3 * i / 8));
571 // SearchStack::init() initializes a search stack. Used at the beginning of a
572 // new search from the root.
573 void SearchStack::init(int ply) {
575 pv[ply] = pv[ply + 1] = MOVE_NONE;
576 currentMove = threatMove = MOVE_NONE;
577 reduction = Depth(0);
581 void SearchStack::initKillers() {
583 mateKiller = MOVE_NONE;
584 for (int i = 0; i < KILLER_MAX; i++)
585 killers[i] = MOVE_NONE;
590 // id_loop() is the main iterative deepening loop. It calls root_search
591 // repeatedly with increasing depth until the allocated thinking time has
592 // been consumed, the user stops the search, or the maximum search depth is
595 Value id_loop(const Position& pos, Move searchMoves[]) {
598 SearchStack ss[PLY_MAX_PLUS_2];
600 // searchMoves are verified, copied, scored and sorted
601 RootMoveList rml(p, searchMoves);
603 // Handle special case of searching on a mate/stale position
604 if (rml.move_count() == 0)
607 wait_for_stop_or_ponderhit();
609 return pos.is_check()? -VALUE_MATE : VALUE_DRAW;
612 // Print RootMoveList c'tor startup scoring to the standard output,
613 // so that we print information also for iteration 1.
614 cout << "info depth " << 1 << "\ninfo depth " << 1
615 << " score " << value_to_string(rml.get_move_score(0))
616 << " time " << current_search_time()
617 << " nodes " << TM.nodes_searched()
619 << " pv " << rml.get_move(0) << "\n";
625 ValueByIteration[1] = rml.get_move_score(0);
628 // Is one move significantly better than others after initial scoring ?
629 Move EasyMove = MOVE_NONE;
630 if ( rml.move_count() == 1
631 || rml.get_move_score(0) > rml.get_move_score(1) + EasyMoveMargin)
632 EasyMove = rml.get_move(0);
634 // Iterative deepening loop
635 while (Iteration < PLY_MAX)
637 // Initialize iteration
640 BestMoveChangesByIteration[Iteration] = 0;
644 cout << "info depth " << Iteration << endl;
646 // Calculate dynamic search window based on previous iterations
649 if (MultiPV == 1 && Iteration >= 6 && abs(ValueByIteration[Iteration - 1]) < VALUE_KNOWN_WIN)
651 int prevDelta1 = ValueByIteration[Iteration - 1] - ValueByIteration[Iteration - 2];
652 int prevDelta2 = ValueByIteration[Iteration - 2] - ValueByIteration[Iteration - 3];
654 AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
655 AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
657 alpha = Max(ValueByIteration[Iteration - 1] - AspirationDelta, -VALUE_INFINITE);
658 beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
662 alpha = - VALUE_INFINITE;
663 beta = VALUE_INFINITE;
666 // Search to the current depth
667 Value value = root_search(p, ss, rml, alpha, beta);
669 // Write PV to transposition table, in case the relevant entries have
670 // been overwritten during the search.
671 TT.insert_pv(p, ss[0].pv);
674 break; // Value cannot be trusted. Break out immediately!
676 //Save info about search result
677 ValueByIteration[Iteration] = value;
679 // Drop the easy move if it differs from the new best move
680 if (ss[0].pv[0] != EasyMove)
681 EasyMove = MOVE_NONE;
683 if (UseTimeManagement)
686 bool stopSearch = false;
688 // Stop search early if there is only a single legal move,
689 // we search up to Iteration 6 anyway to get a proper score.
690 if (Iteration >= 6 && rml.move_count() == 1)
693 // Stop search early when the last two iterations returned a mate score
695 && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
696 && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
699 // Stop search early if one move seems to be much better than the rest
700 int64_t nodes = TM.nodes_searched();
702 && EasyMove == ss[0].pv[0]
703 && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
704 && current_search_time() > MaxSearchTime / 16)
705 ||( rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100
706 && current_search_time() > MaxSearchTime / 32)))
709 // Add some extra time if the best move has changed during the last two iterations
710 if (Iteration > 5 && Iteration <= 50)
711 ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2)
712 + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3);
714 // Stop search if most of MaxSearchTime is consumed at the end of the
715 // iteration. We probably don't have enough time to search the first
716 // move at the next iteration anyway.
717 if (current_search_time() > ((MaxSearchTime + ExtraSearchTime) * 80) / 128)
725 StopOnPonderhit = true;
729 if (MaxDepth && Iteration >= MaxDepth)
735 // If we are pondering or in infinite search, we shouldn't print the
736 // best move before we are told to do so.
737 if (!AbortSearch && (PonderSearch || InfiniteSearch))
738 wait_for_stop_or_ponderhit();
740 // Print final search statistics
741 cout << "info nodes " << TM.nodes_searched()
743 << " time " << current_search_time()
744 << " hashfull " << TT.full() << endl;
746 // Print the best move and the ponder move to the standard output
747 if (ss[0].pv[0] == MOVE_NONE)
749 ss[0].pv[0] = rml.get_move(0);
750 ss[0].pv[1] = MOVE_NONE;
752 cout << "bestmove " << ss[0].pv[0];
753 if (ss[0].pv[1] != MOVE_NONE)
754 cout << " ponder " << ss[0].pv[1];
761 dbg_print_mean(LogFile);
763 if (dbg_show_hit_rate)
764 dbg_print_hit_rate(LogFile);
766 LogFile << "\nNodes: " << TM.nodes_searched()
767 << "\nNodes/second: " << nps()
768 << "\nBest move: " << move_to_san(p, ss[0].pv[0]);
771 p.do_move(ss[0].pv[0], st);
772 LogFile << "\nPonder move: " << move_to_san(p, ss[0].pv[1]) << endl;
774 return rml.get_move_score(0);
778 // root_search() is the function which searches the root node. It is
779 // similar to search_pv except that it uses a different move ordering
780 // scheme and prints some information to the standard output.
782 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta) {
787 Depth depth, ext, newDepth;
790 int researchCount = 0;
791 bool moveIsCheck, captureOrPromotion, dangerous;
792 Value alpha = oldAlpha;
793 bool isCheck = pos.is_check();
795 // Evaluate the position statically
797 ss[0].eval = !isCheck ? evaluate(pos, ei, 0) : VALUE_NONE;
799 while (1) // Fail low loop
802 // Loop through all the moves in the root move list
803 for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
807 // We failed high, invalidate and skip next moves, leave node-counters
808 // and beta-counters as they are and quickly return, we will try to do
809 // a research at the next iteration with a bigger aspiration window.
810 rml.set_move_score(i, -VALUE_INFINITE);
814 RootMoveNumber = i + 1;
816 // Save the current node count before the move is searched
817 nodes = TM.nodes_searched();
819 // Reset beta cut-off counters
820 TM.resetBetaCounters();
822 // Pick the next root move, and print the move and the move number to
823 // the standard output.
824 move = ss[0].currentMove = rml.get_move(i);
826 if (current_search_time() >= 1000)
827 cout << "info currmove " << move
828 << " currmovenumber " << RootMoveNumber << endl;
830 // Decide search depth for this move
831 moveIsCheck = pos.move_is_check(move);
832 captureOrPromotion = pos.move_is_capture_or_promotion(move);
833 depth = (Iteration - 2) * OnePly + InitialDepth;
834 ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
835 newDepth = depth + ext;
837 value = - VALUE_INFINITE;
839 while (1) // Fail high loop
842 // Make the move, and search it
843 pos.do_move(move, st, ci, moveIsCheck);
845 if (i < MultiPV || value > alpha)
847 // Aspiration window is disabled in multi-pv case
849 alpha = -VALUE_INFINITE;
851 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
855 // Try to reduce non-pv search depth by one ply if move seems not problematic,
856 // if the move fails high will be re-searched at full depth.
857 bool doFullDepthSearch = true;
859 if ( depth >= 3*OnePly // FIXME was newDepth
861 && !captureOrPromotion
862 && !move_is_castle(move))
864 ss[0].reduction = pv_reduction(depth, RootMoveNumber - MultiPV + 1);
867 value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0);
868 doFullDepthSearch = (value > alpha);
872 if (doFullDepthSearch)
874 ss[0].reduction = Depth(0);
875 value = -search(pos, ss, -alpha, newDepth, 1, true, 0);
878 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
884 // Can we exit fail high loop ?
885 if (AbortSearch || value < beta)
888 // We are failing high and going to do a research. It's important to update score
889 // before research in case we run out of time while researching.
890 rml.set_move_score(i, value);
892 TT.extract_pv(pos, ss[0].pv, PLY_MAX);
893 rml.set_move_pv(i, ss[0].pv);
895 // Print search information to the standard output
896 cout << "info depth " << Iteration
897 << " score " << value_to_string(value)
898 << ((value >= beta) ? " lowerbound" :
899 ((value <= alpha)? " upperbound" : ""))
900 << " time " << current_search_time()
901 << " nodes " << TM.nodes_searched()
905 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
906 cout << ss[0].pv[j] << " ";
912 ValueType type = (value >= beta ? VALUE_TYPE_LOWER
913 : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT));
915 LogFile << pretty_pv(pos, current_search_time(), Iteration,
916 TM.nodes_searched(), value, type, ss[0].pv) << endl;
919 // Prepare for a research after a fail high, each time with a wider window
921 beta = Min(beta + AspirationDelta * (1 << researchCount), VALUE_INFINITE);
923 } // End of fail high loop
925 // Finished searching the move. If AbortSearch is true, the search
926 // was aborted because the user interrupted the search or because we
927 // ran out of time. In this case, the return value of the search cannot
928 // be trusted, and we break out of the loop without updating the best
933 // Remember beta-cutoff and searched nodes counts for this move. The
934 // info is used to sort the root moves at the next iteration.
936 TM.get_beta_counters(pos.side_to_move(), our, their);
937 rml.set_beta_counters(i, our, their);
938 rml.set_move_nodes(i, TM.nodes_searched() - nodes);
940 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
942 if (value <= alpha && i >= MultiPV)
943 rml.set_move_score(i, -VALUE_INFINITE);
946 // PV move or new best move!
949 rml.set_move_score(i, value);
951 TT.extract_pv(pos, ss[0].pv, PLY_MAX);
952 rml.set_move_pv(i, ss[0].pv);
956 // We record how often the best move has been changed in each
957 // iteration. This information is used for time managment: When
958 // the best move changes frequently, we allocate some more time.
960 BestMoveChangesByIteration[Iteration]++;
962 // Print search information to the standard output
963 cout << "info depth " << Iteration
964 << " score " << value_to_string(value)
965 << ((value >= beta) ? " lowerbound" :
966 ((value <= alpha)? " upperbound" : ""))
967 << " time " << current_search_time()
968 << " nodes " << TM.nodes_searched()
972 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
973 cout << ss[0].pv[j] << " ";
979 ValueType type = (value >= beta ? VALUE_TYPE_LOWER
980 : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT));
982 LogFile << pretty_pv(pos, current_search_time(), Iteration,
983 TM.nodes_searched(), value, type, ss[0].pv) << endl;
991 for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
993 cout << "info multipv " << j + 1
994 << " score " << value_to_string(rml.get_move_score(j))
995 << " depth " << ((j <= i)? Iteration : Iteration - 1)
996 << " time " << current_search_time()
997 << " nodes " << TM.nodes_searched()
1001 for (int k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
1002 cout << rml.get_move_pv(j, k) << " ";
1006 alpha = rml.get_move_score(Min(i, MultiPV-1));
1008 } // PV move or new best move
1010 assert(alpha >= oldAlpha);
1012 AspirationFailLow = (alpha == oldAlpha);
1014 if (AspirationFailLow && StopOnPonderhit)
1015 StopOnPonderhit = false;
1018 // Can we exit fail low loop ?
1019 if (AbortSearch || alpha > oldAlpha)
1022 // Prepare for a research after a fail low, each time with a wider window
1024 alpha = Max(alpha - AspirationDelta * (1 << researchCount), -VALUE_INFINITE);
1033 // search_pv() is the main search function for PV nodes.
1035 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta,
1036 Depth depth, int ply, int threadID) {
1038 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1039 assert(beta > alpha && beta <= VALUE_INFINITE);
1040 assert(ply >= 0 && ply < PLY_MAX);
1041 assert(threadID >= 0 && threadID < TM.active_threads());
1043 Move movesSearched[256];
1048 Depth ext, newDepth;
1049 Value bestValue, value, oldAlpha;
1050 bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
1051 bool mateThreat = false;
1053 bestValue = value = -VALUE_INFINITE;
1056 return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID);
1058 // Step 1. Initialize node and poll
1059 // Polling can abort search.
1060 init_node(ss, ply, threadID);
1062 // Step 2. Check for aborted search and immediate draw
1063 if (AbortSearch || TM.thread_should_stop(threadID))
1066 if (pos.is_draw() || ply >= PLY_MAX - 1)
1069 // 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
1077 // At PV nodes, we don't use the TT for pruning, but only for move ordering.
1078 // This is to avoid problems in the following areas:
1080 // * Repetition draw detection
1081 // * Fifty move rule detection
1082 // * Searching for a mate
1083 // * Printing of full PV line
1084 tte = TT.retrieve(pos.get_key());
1085 ttMove = (tte ? tte->move() : MOVE_NONE);
1087 // Step 5. Evaluate the position statically
1088 // At PV nodes we do this only to update gain statistics
1089 isCheck = pos.is_check();
1092 ss[ply].eval = evaluate(pos, ei, threadID);
1093 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1096 // Step 6. Razoring (is omitted in PV nodes)
1097 // Step 7. Static null move pruning (is omitted in PV nodes)
1098 // Step 8. Null move search with verification search (is omitted in PV nodes)
1100 // Step 9. Internal iterative deepening
1101 if ( UseIIDAtPVNodes
1102 && depth >= 5*OnePly
1103 && ttMove == MOVE_NONE)
1105 search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID);
1106 ttMove = ss[ply].pv[ply];
1107 tte = TT.retrieve(pos.get_key());
1110 // Step 10. Loop through moves
1111 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1113 // Initialize a MovePicker object for the current position
1114 mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move()));
1115 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1118 while ( alpha < beta
1119 && (move = mp.get_next_move()) != MOVE_NONE
1120 && !TM.thread_should_stop(threadID))
1122 assert(move_is_ok(move));
1124 singleEvasion = (isCheck && mp.number_of_evasions() == 1);
1125 moveIsCheck = pos.move_is_check(move, ci);
1126 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1128 // Step 11. Decide the new search depth
1129 ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1131 // Singular extension search. We extend the TT move if its value is much better than
1132 // its siblings. To verify this we do a reduced search on all the other moves but the
1133 // ttMove, if result is lower then ttValue minus a margin then we extend ttMove.
1134 if ( depth >= 6 * OnePly
1136 && move == tte->move()
1138 && is_lower_bound(tte->type())
1139 && tte->depth() >= depth - 3 * OnePly)
1141 Value ttValue = value_from_tt(tte->value(), ply);
1143 if (abs(ttValue) < VALUE_KNOWN_WIN)
1145 Value excValue = search(pos, ss, ttValue - SingleReplyMargin, depth / 2, ply, false, threadID, move);
1147 if (excValue < ttValue - SingleReplyMargin)
1152 newDepth = depth - OnePly + ext;
1154 // Update current move (this must be done after singular extension search)
1155 movesSearched[moveCount++] = ss[ply].currentMove = move;
1157 // Step 12. Futility pruning (is omitted in PV nodes)
1159 // Step 13. Make the move
1160 pos.do_move(move, st, ci, moveIsCheck);
1162 // Step extra. pv search (only in PV nodes)
1163 // The first move in list is the expected PV
1165 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1168 // Step 14. Reduced search
1169 // if the move fails high will be re-searched at full depth.
1170 bool doFullDepthSearch = true;
1172 if ( depth >= 3*OnePly
1174 && !captureOrPromotion
1175 && !move_is_castle(move)
1176 && !move_is_killer(move, ss[ply]))
1178 ss[ply].reduction = pv_reduction(depth, moveCount);
1179 if (ss[ply].reduction)
1181 value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
1182 doFullDepthSearch = (value > alpha);
1186 // Step 15. Full depth search
1187 if (doFullDepthSearch)
1189 ss[ply].reduction = Depth(0);
1190 value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID);
1192 // Step extra. pv search (only in PV nodes)
1193 if (value > alpha && value < beta)
1194 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1198 // Step 16. Undo move
1199 pos.undo_move(move);
1201 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1203 // Step 17. Check for new best move
1204 if (value > bestValue)
1211 if (value == value_mate_in(ply + 1))
1212 ss[ply].mateKiller = move;
1216 // Step 18. Check for split
1217 if ( TM.active_threads() > 1
1219 && depth >= MinimumSplitDepth
1221 && TM.available_thread_exists(threadID)
1223 && !TM.thread_should_stop(threadID)
1224 && TM.split(pos, ss, ply, &alpha, beta, &bestValue,
1225 depth, &moveCount, &mp, threadID, true))
1229 // Step 19. Check for mate and stalemate
1230 // All legal moves have been searched and if there were
1231 // no legal moves, it must be mate or stalemate.
1233 return (isCheck ? value_mated_in(ply) : VALUE_DRAW);
1235 // Step 20. Update tables
1236 // If the search is not aborted, update the transposition table,
1237 // history counters, and killer moves.
1238 if (AbortSearch || TM.thread_should_stop(threadID))
1241 if (bestValue <= oldAlpha)
1242 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1244 else if (bestValue >= beta)
1246 TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
1247 move = ss[ply].pv[ply];
1248 if (!pos.move_is_capture_or_promotion(move))
1250 update_history(pos, move, depth, movesSearched, moveCount);
1251 update_killers(move, ss[ply]);
1253 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
1256 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
1262 // search() is the search function for zero-width nodes.
1264 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth,
1265 int ply, bool allowNullmove, int threadID, Move excludedMove) {
1267 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1268 assert(ply >= 0 && ply < PLY_MAX);
1269 assert(threadID >= 0 && threadID < TM.active_threads());
1271 Move movesSearched[256];
1276 Depth ext, newDepth;
1277 Value bestValue, refinedValue, nullValue, value, futilityValueScaled;
1278 bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
1279 bool mateThreat = false;
1281 refinedValue = bestValue = value = -VALUE_INFINITE;
1284 return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1286 // Step 1. Initialize node and poll
1287 // Polling can abort search.
1288 init_node(ss, ply, threadID);
1290 // Step 2. Check for aborted search and immediate draw
1291 if (AbortSearch || TM.thread_should_stop(threadID))
1294 if (pos.is_draw() || ply >= PLY_MAX - 1)
1297 // Step 3. Mate distance pruning
1298 if (value_mated_in(ply) >= beta)
1301 if (value_mate_in(ply + 1) < beta)
1304 // Step 4. Transposition table lookup
1306 // We don't want the score of a partial search to overwrite a previous full search
1307 // TT value, so we use a different position key in case of an excluded move exists.
1308 Key posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
1310 tte = TT.retrieve(posKey);
1311 ttMove = (tte ? tte->move() : MOVE_NONE);
1313 if (tte && ok_to_use_TT(tte, depth, beta, ply))
1315 ss[ply].currentMove = ttMove; // Can be MOVE_NONE
1316 return value_from_tt(tte->value(), ply);
1319 // Step 5. Evaluate the position statically
1320 isCheck = pos.is_check();
1324 if (tte && (tte->type() & VALUE_TYPE_EVAL))
1325 ss[ply].eval = value_from_tt(tte->value(), ply);
1327 ss[ply].eval = evaluate(pos, ei, threadID);
1329 refinedValue = refine_eval(tte, ss[ply].eval, ply); // Enhance accuracy with TT value if possible
1330 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1334 if ( !value_is_mate(beta)
1336 && depth < RazorDepth
1337 && refinedValue < beta - razor_margin(depth)
1338 && ss[ply - 1].currentMove != MOVE_NULL
1339 && ttMove == MOVE_NONE
1340 && !pos.has_pawn_on_7th(pos.side_to_move()))
1342 Value rbeta = beta - razor_margin(depth);
1343 Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID);
1345 return v; //FIXME: Logically should be: return (v + razor_margin(depth));
1348 // Step 7. Static null move pruning
1349 // We're betting that the opponent doesn't have a move that will reduce
1350 // the score by more than fuility_margin(depth) if we do a null move.
1353 && depth < RazorDepth
1354 && refinedValue - futility_margin(depth, 0) >= beta)
1355 return refinedValue - futility_margin(depth, 0);
1357 // Step 8. Null move search with verification search
1358 // When we jump directly to qsearch() we do a null move only if static value is
1359 // at least beta. Otherwise we do a null move if static value is not more than
1360 // NullMoveMargin under beta.
1364 && !value_is_mate(beta)
1365 && ok_to_do_nullmove(pos)
1366 && refinedValue >= beta - (depth >= 4 * OnePly ? NullMoveMargin : 0))
1368 ss[ply].currentMove = MOVE_NULL;
1370 pos.do_null_move(st);
1372 // Null move dynamic reduction based on depth
1373 int R = 3 + (depth >= 5 * OnePly ? depth / 8 : 0);
1375 // Null move dynamic reduction based on value
1376 if (refinedValue - beta > PawnValueMidgame)
1379 nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);
1381 pos.undo_null_move();
1383 if (nullValue >= beta)
1385 if (depth < 6 * OnePly)
1388 // Do zugzwang verification search
1389 Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
1393 // The null move failed low, which means that we may be faced with
1394 // some kind of threat. If the previous move was reduced, check if
1395 // the move that refuted the null move was somehow connected to the
1396 // move which was reduced. If a connection is found, return a fail
1397 // low score (which will cause the reduced move to fail high in the
1398 // parent node, which will trigger a re-search with full depth).
1399 if (nullValue == value_mated_in(ply + 2))
1402 ss[ply].threatMove = ss[ply + 1].currentMove;
1403 if ( depth < ThreatDepth
1404 && ss[ply - 1].reduction
1405 && connected_moves(pos, ss[ply - 1].currentMove, ss[ply].threatMove))
1410 // Step 9. Internal iterative deepening
1411 if (UseIIDAtNonPVNodes && ttMove == MOVE_NONE && depth >= 8*OnePly &&
1412 !isCheck && ss[ply].eval >= beta - IIDMargin)
1414 search(pos, ss, beta, depth/2, ply, false, threadID);
1415 ttMove = ss[ply].pv[ply];
1416 tte = TT.retrieve(posKey);
1419 // Step 10. Loop through moves
1420 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1422 // Initialize a MovePicker object for the current position
1423 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1426 while ( bestValue < beta
1427 && (move = mp.get_next_move()) != MOVE_NONE
1428 && !TM.thread_should_stop(threadID))
1430 assert(move_is_ok(move));
1432 if (move == excludedMove)
1435 moveIsCheck = pos.move_is_check(move, ci);
1436 singleEvasion = (isCheck && mp.number_of_evasions() == 1);
1437 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1439 // Step 11. Decide the new search depth
1440 ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
1442 // Singular extension search. We extend the TT move if its value is much better than
1443 // its siblings. To verify this we do a reduced search on all the other moves but the
1444 // ttMove, if result is lower then ttValue minus a margin then we extend ttMove.
1445 if ( depth >= 8 * OnePly
1447 && move == tte->move()
1448 && !excludedMove // Do not allow recursive single-reply search
1450 && is_lower_bound(tte->type())
1451 && tte->depth() >= depth - 3 * OnePly)
1453 Value ttValue = value_from_tt(tte->value(), ply);
1455 if (abs(ttValue) < VALUE_KNOWN_WIN)
1457 Value excValue = search(pos, ss, ttValue - SingleReplyMargin, depth / 2, ply, false, threadID, move);
1459 if (excValue < ttValue - SingleReplyMargin)
1464 newDepth = depth - OnePly + ext;
1466 // Update current move (this must be done after singular extension search)
1467 movesSearched[moveCount++] = ss[ply].currentMove = move;
1469 // Step 12. Futility pruning
1472 && !captureOrPromotion
1473 && !move_is_castle(move)
1476 // Move count based pruning
1477 if ( moveCount >= futility_move_count(depth)
1478 && ok_to_prune(pos, move, ss[ply].threatMove)
1479 && bestValue > value_mated_in(PLY_MAX))
1482 // Value based pruning
1483 Depth predictedDepth = newDepth - nonpv_reduction(depth, moveCount); //FIXME: We are ignoring condition: depth >= 3*OnePly, BUG??
1484 futilityValueScaled = ss[ply].eval + futility_margin(predictedDepth, moveCount)
1485 + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45;
1487 if (futilityValueScaled < beta)
1489 if (futilityValueScaled > bestValue)
1490 bestValue = futilityValueScaled;
1495 // Step 13. Make the move
1496 pos.do_move(move, st, ci, moveIsCheck);
1498 // Step 14. Reduced search
1499 // if the move fails high will be re-searched at full depth.
1500 bool doFullDepthSearch = true;
1502 if ( depth >= 3*OnePly
1504 && !captureOrPromotion
1505 && !move_is_castle(move)
1506 && !move_is_killer(move, ss[ply]))
1508 ss[ply].reduction = nonpv_reduction(depth, moveCount);
1509 if (ss[ply].reduction)
1511 value = -search(pos, ss, -(beta-1), newDepth-ss[ply].reduction, ply+1, true, threadID);
1512 doFullDepthSearch = (value >= beta);
1516 // Step 15. Full depth search
1517 if (doFullDepthSearch)
1519 ss[ply].reduction = Depth(0);
1520 value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID);
1523 // Step 16. Undo move
1524 pos.undo_move(move);
1526 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1528 // Step 17. Check for new best move
1529 if (value > bestValue)
1535 if (value == value_mate_in(ply + 1))
1536 ss[ply].mateKiller = move;
1539 // Step 18. Check for split
1540 if ( TM.active_threads() > 1
1542 && depth >= MinimumSplitDepth
1544 && TM.available_thread_exists(threadID)
1546 && !TM.thread_should_stop(threadID)
1547 && TM.split(pos, ss, ply, NULL, beta, &bestValue,
1548 depth, &moveCount, &mp, threadID, false))
1552 // Step 19. Check for mate and stalemate
1553 // All legal moves have been searched and if there were
1554 // no legal moves, it must be mate or stalemate.
1555 // If one move was excluded return fail low.
1557 return excludedMove ? beta - 1 : (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW);
1559 // Step 20. Update tables
1560 // If the search is not aborted, update the transposition table,
1561 // history counters, and killer moves.
1562 if (AbortSearch || TM.thread_should_stop(threadID))
1565 if (bestValue < beta)
1566 TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1569 TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
1570 move = ss[ply].pv[ply];
1571 TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
1572 if (!pos.move_is_capture_or_promotion(move))
1574 update_history(pos, move, depth, movesSearched, moveCount);
1575 update_killers(move, ss[ply]);
1580 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1586 // qsearch() is the quiescence search function, which is called by the main
1587 // search function when the remaining depth is zero (or, to be more precise,
1588 // less than OnePly).
1590 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta,
1591 Depth depth, int ply, int threadID) {
1593 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1594 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1596 assert(ply >= 0 && ply < PLY_MAX);
1597 assert(threadID >= 0 && threadID < TM.active_threads());
1602 Value staticValue, bestValue, value, futilityBase, futilityValue;
1603 bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
1604 const TTEntry* tte = NULL;
1606 bool pvNode = (beta - alpha != 1);
1607 Value oldAlpha = alpha;
1609 // Initialize, and make an early exit in case of an aborted search,
1610 // an instant draw, maximum ply reached, etc.
1611 init_node(ss, ply, threadID);
1613 // After init_node() that calls poll()
1614 if (AbortSearch || TM.thread_should_stop(threadID))
1617 if (pos.is_draw() || ply >= PLY_MAX - 1)
1620 // Transposition table lookup. At PV nodes, we don't use the TT for
1621 // pruning, but only for move ordering.
1622 tte = TT.retrieve(pos.get_key());
1623 ttMove = (tte ? tte->move() : MOVE_NONE);
1625 if (!pvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
1627 assert(tte->type() != VALUE_TYPE_EVAL);
1629 ss[ply].currentMove = ttMove; // Can be MOVE_NONE
1630 return value_from_tt(tte->value(), ply);
1633 isCheck = pos.is_check();
1635 // Evaluate the position statically
1637 staticValue = -VALUE_INFINITE;
1638 else if (tte && (tte->type() & VALUE_TYPE_EVAL))
1639 staticValue = value_from_tt(tte->value(), ply);
1641 staticValue = evaluate(pos, ei, threadID);
1645 ss[ply].eval = staticValue;
1646 update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
1649 // Initialize "stand pat score", and return it immediately if it is
1651 bestValue = staticValue;
1653 if (bestValue >= beta)
1655 // Store the score to avoid a future costly evaluation() call
1656 if (!isCheck && !tte && ei.futilityMargin[pos.side_to_move()] == 0)
1657 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EV_LO, Depth(-127*OnePly), MOVE_NONE);
1662 if (bestValue > alpha)
1665 // If we are near beta then try to get a cutoff pushing checks a bit further
1666 bool deepChecks = depth == -OnePly && staticValue >= beta - PawnValueMidgame / 8;
1668 // Initialize a MovePicker object for the current position, and prepare
1669 // to search the moves. Because the depth is <= 0 here, only captures,
1670 // queen promotions and checks (only if depth == 0 or depth == -OnePly
1671 // and we are near beta) will be generated.
1672 MovePicker mp = MovePicker(pos, ttMove, deepChecks ? Depth(0) : depth, H);
1674 enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
1675 futilityBase = staticValue + FutilityMarginQS + ei.futilityMargin[pos.side_to_move()];
1677 // Loop through the moves until no moves remain or a beta cutoff
1679 while ( alpha < beta
1680 && (move = mp.get_next_move()) != MOVE_NONE)
1682 assert(move_is_ok(move));
1684 moveIsCheck = pos.move_is_check(move, ci);
1686 // Update current move
1688 ss[ply].currentMove = move;
1696 && !move_is_promotion(move)
1697 && !pos.move_is_passed_pawn_push(move))
1699 futilityValue = futilityBase
1700 + pos.endgame_value_of_piece_on(move_to(move))
1701 + (move_is_ep(move) ? PawnValueEndgame : Value(0));
1703 if (futilityValue < alpha)
1705 if (futilityValue > bestValue)
1706 bestValue = futilityValue;
1711 // Detect blocking evasions that are candidate to be pruned
1712 evasionPrunable = isCheck
1713 && bestValue != -VALUE_INFINITE
1714 && !pos.move_is_capture(move)
1715 && pos.type_of_piece_on(move_from(move)) != KING
1716 && !pos.can_castle(pos.side_to_move());
1718 // Don't search moves with negative SEE values
1719 if ( (!isCheck || evasionPrunable)
1722 && !move_is_promotion(move)
1723 && pos.see_sign(move) < 0)
1726 // Make and search the move
1727 pos.do_move(move, st, ci, moveIsCheck);
1728 value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID);
1729 pos.undo_move(move);
1731 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1734 if (value > bestValue)
1745 // All legal moves have been searched. A special case: If we're in check
1746 // and no legal moves were found, it is checkmate.
1747 if (!moveCount && pos.is_check()) // Mate!
1748 return value_mated_in(ply);
1750 // Update transposition table
1751 Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
1752 if (bestValue <= oldAlpha)
1754 // If bestValue isn't changed it means it is still the static evaluation
1755 // of the node, so keep this info to avoid a future evaluation() call.
1756 ValueType type = (bestValue == staticValue && !ei.futilityMargin[pos.side_to_move()] ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER);
1757 TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE);
1759 else if (bestValue >= beta)
1761 move = ss[ply].pv[ply];
1762 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, move);
1764 // Update killers only for good checking moves
1765 if (!pos.move_is_capture_or_promotion(move))
1766 update_killers(move, ss[ply]);
1769 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, d, ss[ply].pv[ply]);
1771 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1777 // sp_search() is used to search from a split point. This function is called
1778 // by each thread working at the split point. It is similar to the normal
1779 // search() function, but simpler. Because we have already probed the hash
1780 // table, done a null move search, and searched the first move before
1781 // splitting, we don't have to repeat all this work in sp_search(). We
1782 // also don't need to store anything to the hash table here: This is taken
1783 // care of after we return from the split point.
1784 // FIXME: We are currently ignoring mateThreat flag here
1786 void sp_search(SplitPoint* sp, int threadID) {
1788 assert(threadID >= 0 && threadID < TM.active_threads());
1789 assert(TM.active_threads() > 1);
1793 Depth ext, newDepth;
1794 Value value, futilityValueScaled;
1795 bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
1797 value = -VALUE_INFINITE;
1799 Position pos(*sp->pos);
1801 SearchStack* ss = sp->sstack[threadID];
1802 isCheck = pos.is_check();
1804 // Step 10. Loop through moves
1805 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1806 lock_grab(&(sp->lock));
1808 while ( sp->bestValue < sp->beta
1809 && !TM.thread_should_stop(threadID)
1810 && (move = sp->mp->get_next_move()) != MOVE_NONE)
1812 moveCount = ++sp->moves;
1813 lock_release(&(sp->lock));
1815 assert(move_is_ok(move));
1817 moveIsCheck = pos.move_is_check(move, ci);
1818 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1820 // Step 11. Decide the new search depth
1821 ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous);
1822 newDepth = sp->depth - OnePly + ext;
1824 // Update current move
1825 ss[sp->ply].currentMove = move;
1827 // Step 12. Futility pruning
1830 && !captureOrPromotion
1831 && !move_is_castle(move))
1833 // Move count based pruning
1834 if ( moveCount >= futility_move_count(sp->depth)
1835 && ok_to_prune(pos, move, ss[sp->ply].threatMove)
1836 && sp->bestValue > value_mated_in(PLY_MAX))
1838 lock_grab(&(sp->lock));
1842 // Value based pruning
1843 Depth predictedDepth = newDepth - nonpv_reduction(sp->depth, moveCount);
1844 futilityValueScaled = ss[sp->ply].eval + futility_margin(predictedDepth, moveCount)
1845 + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45;
1847 if (futilityValueScaled < sp->beta)
1849 lock_grab(&(sp->lock));
1851 if (futilityValueScaled > sp->bestValue)
1852 sp->bestValue = futilityValueScaled;
1857 // Step 13. Make the move
1858 pos.do_move(move, st, ci, moveIsCheck);
1860 // Step 14. Reduced search
1861 // if the move fails high will be re-searched at full depth.
1862 bool doFullDepthSearch = true;
1865 && !captureOrPromotion
1866 && !move_is_castle(move)
1867 && !move_is_killer(move, ss[sp->ply]))
1869 ss[sp->ply].reduction = nonpv_reduction(sp->depth, moveCount);
1870 if (ss[sp->ply].reduction)
1872 value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
1873 doFullDepthSearch = (value >= sp->beta && !TM.thread_should_stop(threadID));
1877 // Step 15. Full depth search
1878 if (doFullDepthSearch)
1880 ss[sp->ply].reduction = Depth(0);
1881 value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID);
1884 // Step 16. Undo move
1885 pos.undo_move(move);
1887 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1889 // Step 17. Check for new best move
1890 lock_grab(&(sp->lock));
1892 if (value > sp->bestValue && !TM.thread_should_stop(threadID))
1894 sp->bestValue = value;
1895 if (sp->bestValue >= sp->beta)
1897 sp->stopRequest = true;
1898 sp_update_pv(sp->parentSstack, ss, sp->ply);
1903 /* Here we have the lock still grabbed */
1905 sp->slaves[threadID] = 0;
1908 lock_release(&(sp->lock));
1912 // sp_search_pv() is used to search from a PV split point. This function
1913 // is called by each thread working at the split point. It is similar to
1914 // the normal search_pv() function, but simpler. Because we have already
1915 // probed the hash table and searched the first move before splitting, we
1916 // don't have to repeat all this work in sp_search_pv(). We also don't
1917 // need to store anything to the hash table here: This is taken care of
1918 // after we return from the split point.
1919 // FIXME: We are ignoring mateThreat flag!
1921 void sp_search_pv(SplitPoint* sp, int threadID) {
1923 assert(threadID >= 0 && threadID < TM.active_threads());
1924 assert(TM.active_threads() > 1);
1928 Depth ext, newDepth;
1930 bool moveIsCheck, captureOrPromotion, dangerous;
1932 value = -VALUE_INFINITE;
1934 Position pos(*sp->pos);
1936 SearchStack* ss = sp->sstack[threadID];
1938 // Step 10. Loop through moves
1939 // Loop through all legal moves until no moves remain or a beta cutoff occurs
1940 lock_grab(&(sp->lock));
1942 while ( sp->alpha < sp->beta
1943 && !TM.thread_should_stop(threadID)
1944 && (move = sp->mp->get_next_move()) != MOVE_NONE)
1946 moveCount = ++sp->moves;
1947 lock_release(&(sp->lock));
1949 assert(move_is_ok(move));
1951 moveIsCheck = pos.move_is_check(move, ci);
1952 captureOrPromotion = pos.move_is_capture_or_promotion(move);
1954 // Step 11. Decide the new search depth
1955 ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
1956 newDepth = sp->depth - OnePly + ext;
1958 // Update current move
1959 ss[sp->ply].currentMove = move;
1961 // Step 12. Futility pruning (is omitted in PV nodes)
1963 // Step 13. Make the move
1964 pos.do_move(move, st, ci, moveIsCheck);
1966 // Step 14. Reduced search
1967 // if the move fails high will be re-searched at full depth.
1968 bool doFullDepthSearch = true;
1971 && !captureOrPromotion
1972 && !move_is_castle(move)
1973 && !move_is_killer(move, ss[sp->ply]))
1975 ss[sp->ply].reduction = pv_reduction(sp->depth, moveCount);
1976 if (ss[sp->ply].reduction)
1978 Value localAlpha = sp->alpha;
1979 value = -search(pos, ss, -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
1980 doFullDepthSearch = (value > localAlpha && !TM.thread_should_stop(threadID));
1984 // Step 15. Full depth search
1985 if (doFullDepthSearch)
1987 Value localAlpha = sp->alpha;
1988 ss[sp->ply].reduction = Depth(0);
1989 value = -search(pos, ss, -localAlpha, newDepth, sp->ply+1, true, threadID);
1991 if (value > localAlpha && value < sp->beta && !TM.thread_should_stop(threadID))
1993 // If another thread has failed high then sp->alpha has been increased
1994 // to be higher or equal then beta, if so, avoid to start a PV search.
1995 localAlpha = sp->alpha;
1996 if (localAlpha < sp->beta)
1997 value = -search_pv(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, threadID);
2001 // Step 16. Undo move
2002 pos.undo_move(move);
2004 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
2006 // Step 17. Check for new best move
2007 lock_grab(&(sp->lock));
2009 if (value > sp->bestValue && !TM.thread_should_stop(threadID))
2011 sp->bestValue = value;
2012 if (value > sp->alpha)
2014 // Ask threads to stop before to modify sp->alpha
2015 if (value >= sp->beta)
2016 sp->stopRequest = true;
2020 sp_update_pv(sp->parentSstack, ss, sp->ply);
2021 if (value == value_mate_in(sp->ply + 1))
2022 ss[sp->ply].mateKiller = move;
2027 /* Here we have the lock still grabbed */
2029 sp->slaves[threadID] = 0;
2032 lock_release(&(sp->lock));
2036 // init_node() is called at the beginning of all the search functions
2037 // (search(), search_pv(), qsearch(), and so on) and initializes the
2038 // search stack object corresponding to the current node. Once every
2039 // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
2040 // for user input and checks whether it is time to stop the search.
2042 void init_node(SearchStack ss[], int ply, int threadID) {
2044 assert(ply >= 0 && ply < PLY_MAX);
2045 assert(threadID >= 0 && threadID < TM.active_threads());
2047 TM.incrementNodeCounter(threadID);
2052 if (NodesSincePoll >= NodesBetweenPolls)
2059 ss[ply + 2].initKillers();
2063 // update_pv() is called whenever a search returns a value > alpha.
2064 // It updates the PV in the SearchStack object corresponding to the
2067 void update_pv(SearchStack ss[], int ply) {
2069 assert(ply >= 0 && ply < PLY_MAX);
2073 ss[ply].pv[ply] = ss[ply].currentMove;
2075 for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
2076 ss[ply].pv[p] = ss[ply + 1].pv[p];
2078 ss[ply].pv[p] = MOVE_NONE;
2082 // sp_update_pv() is a variant of update_pv for use at split points. The
2083 // difference between the two functions is that sp_update_pv also updates
2084 // the PV at the parent node.
2086 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply) {
2088 assert(ply >= 0 && ply < PLY_MAX);
2092 ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
2094 for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
2095 ss[ply].pv[p] = pss[ply].pv[p] = ss[ply + 1].pv[p];
2097 ss[ply].pv[p] = pss[ply].pv[p] = MOVE_NONE;
2101 // connected_moves() tests whether two moves are 'connected' in the sense
2102 // that the first move somehow made the second move possible (for instance
2103 // if the moving piece is the same in both moves). The first move is assumed
2104 // to be the move that was made to reach the current position, while the
2105 // second move is assumed to be a move from the current position.
2107 bool connected_moves(const Position& pos, Move m1, Move m2) {
2109 Square f1, t1, f2, t2;
2112 assert(move_is_ok(m1));
2113 assert(move_is_ok(m2));
2115 if (m2 == MOVE_NONE)
2118 // Case 1: The moving piece is the same in both moves
2124 // Case 2: The destination square for m2 was vacated by m1
2130 // Case 3: Moving through the vacated square
2131 if ( piece_is_slider(pos.piece_on(f2))
2132 && bit_is_set(squares_between(f2, t2), f1))
2135 // Case 4: The destination square for m2 is defended by the moving piece in m1
2136 p = pos.piece_on(t1);
2137 if (bit_is_set(pos.attacks_from(p, t1), t2))
2140 // Case 5: Discovered check, checking piece is the piece moved in m1
2141 if ( piece_is_slider(p)
2142 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
2143 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
2145 // discovered_check_candidates() works also if the Position's side to
2146 // move is the opposite of the checking piece.
2147 Color them = opposite_color(pos.side_to_move());
2148 Bitboard dcCandidates = pos.discovered_check_candidates(them);
2150 if (bit_is_set(dcCandidates, f2))
2157 // value_is_mate() checks if the given value is a mate one
2158 // eventually compensated for the ply.
2160 bool value_is_mate(Value value) {
2162 assert(abs(value) <= VALUE_INFINITE);
2164 return value <= value_mated_in(PLY_MAX)
2165 || value >= value_mate_in(PLY_MAX);
2169 // move_is_killer() checks if the given move is among the
2170 // killer moves of that ply.
2172 bool move_is_killer(Move m, const SearchStack& ss) {
2174 const Move* k = ss.killers;
2175 for (int i = 0; i < KILLER_MAX; i++, k++)
2183 // extension() decides whether a move should be searched with normal depth,
2184 // or with extended depth. Certain classes of moves (checking moves, in
2185 // particular) are searched with bigger depth than ordinary moves and in
2186 // any case are marked as 'dangerous'. Note that also if a move is not
2187 // extended, as example because the corresponding UCI option is set to zero,
2188 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
2190 Depth extension(const Position& pos, Move m, bool pvNode, bool captureOrPromotion,
2191 bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous) {
2193 assert(m != MOVE_NONE);
2195 Depth result = Depth(0);
2196 *dangerous = moveIsCheck | singleEvasion | mateThreat;
2201 result += CheckExtension[pvNode];
2204 result += SingleEvasionExtension[pvNode];
2207 result += MateThreatExtension[pvNode];
2210 if (pos.type_of_piece_on(move_from(m)) == PAWN)
2212 Color c = pos.side_to_move();
2213 if (relative_rank(c, move_to(m)) == RANK_7)
2215 result += PawnPushTo7thExtension[pvNode];
2218 if (pos.pawn_is_passed(c, move_to(m)))
2220 result += PassedPawnExtension[pvNode];
2225 if ( captureOrPromotion
2226 && pos.type_of_piece_on(move_to(m)) != PAWN
2227 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
2228 - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))
2229 && !move_is_promotion(m)
2232 result += PawnEndgameExtension[pvNode];
2237 && captureOrPromotion
2238 && pos.type_of_piece_on(move_to(m)) != PAWN
2239 && pos.see_sign(m) >= 0)
2245 return Min(result, OnePly);
2249 // ok_to_do_nullmove() looks at the current position and decides whether
2250 // doing a 'null move' should be allowed. In order to avoid zugzwang
2251 // problems, null moves are not allowed when the side to move has very
2252 // little material left. Currently, the test is a bit too simple: Null
2253 // moves are avoided only when the side to move has only pawns left.
2254 // It's probably a good idea to avoid null moves in at least some more
2255 // complicated endgames, e.g. KQ vs KR. FIXME
2257 bool ok_to_do_nullmove(const Position& pos) {
2259 return pos.non_pawn_material(pos.side_to_move()) != Value(0);
2263 // ok_to_prune() tests whether it is safe to forward prune a move. Only
2264 // non-tactical moves late in the move list close to the leaves are
2265 // candidates for pruning.
2267 bool ok_to_prune(const Position& pos, Move m, Move threat) {
2269 assert(move_is_ok(m));
2270 assert(threat == MOVE_NONE || move_is_ok(threat));
2271 assert(!pos.move_is_check(m));
2272 assert(!pos.move_is_capture_or_promotion(m));
2273 assert(!pos.move_is_passed_pawn_push(m));
2275 Square mfrom, mto, tfrom, tto;
2277 // Prune if there isn't any threat move
2278 if (threat == MOVE_NONE)
2281 mfrom = move_from(m);
2283 tfrom = move_from(threat);
2284 tto = move_to(threat);
2286 // Case 1: Don't prune moves which move the threatened piece
2290 // Case 2: If the threatened piece has value less than or equal to the
2291 // value of the threatening piece, don't prune move which defend it.
2292 if ( pos.move_is_capture(threat)
2293 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
2294 || pos.type_of_piece_on(tfrom) == KING)
2295 && pos.move_attacks_square(m, tto))
2298 // Case 3: If the moving piece in the threatened move is a slider, don't
2299 // prune safe moves which block its ray.
2300 if ( piece_is_slider(pos.piece_on(tfrom))
2301 && bit_is_set(squares_between(tfrom, tto), mto)
2302 && pos.see_sign(m) >= 0)
2309 // ok_to_use_TT() returns true if a transposition table score
2310 // can be used at a given point in search.
2312 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
2314 Value v = value_from_tt(tte->value(), ply);
2316 return ( tte->depth() >= depth
2317 || v >= Max(value_mate_in(PLY_MAX), beta)
2318 || v < Min(value_mated_in(PLY_MAX), beta))
2320 && ( (is_lower_bound(tte->type()) && v >= beta)
2321 || (is_upper_bound(tte->type()) && v < beta));
2325 // refine_eval() returns the transposition table score if
2326 // possible otherwise falls back on static position evaluation.
2328 Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
2333 Value v = value_from_tt(tte->value(), ply);
2335 if ( (is_lower_bound(tte->type()) && v >= defaultEval)
2336 || (is_upper_bound(tte->type()) && v < defaultEval))
2343 // update_history() registers a good move that produced a beta-cutoff
2344 // in history and marks as failures all the other moves of that ply.
2346 void update_history(const Position& pos, Move move, Depth depth,
2347 Move movesSearched[], int moveCount) {
2351 H.success(pos.piece_on(move_from(move)), move_to(move), depth);
2353 for (int i = 0; i < moveCount - 1; i++)
2355 m = movesSearched[i];
2359 if (!pos.move_is_capture_or_promotion(m))
2360 H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
2365 // update_killers() add a good move that produced a beta-cutoff
2366 // among the killer moves of that ply.
2368 void update_killers(Move m, SearchStack& ss) {
2370 if (m == ss.killers[0])
2373 for (int i = KILLER_MAX - 1; i > 0; i--)
2374 ss.killers[i] = ss.killers[i - 1];
2380 // update_gains() updates the gains table of a non-capture move given
2381 // the static position evaluation before and after the move.
2383 void update_gains(const Position& pos, Move m, Value before, Value after) {
2386 && before != VALUE_NONE
2387 && after != VALUE_NONE
2388 && pos.captured_piece() == NO_PIECE_TYPE
2389 && !move_is_castle(m)
2390 && !move_is_promotion(m))
2391 H.set_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
2395 // current_search_time() returns the number of milliseconds which have passed
2396 // since the beginning of the current search.
2398 int current_search_time() {
2400 return get_system_time() - SearchStartTime;
2404 // nps() computes the current nodes/second count.
2408 int t = current_search_time();
2409 return (t > 0 ? int((TM.nodes_searched() * 1000) / t) : 0);
2413 // poll() performs two different functions: It polls for user input, and it
2414 // looks at the time consumed so far and decides if it's time to abort the
2417 void poll(SearchStack ss[], int ply) {
2419 static int lastInfoTime;
2420 int t = current_search_time();
2425 // We are line oriented, don't read single chars
2426 std::string command;
2428 if (!std::getline(std::cin, command))
2431 if (command == "quit")
2434 PonderSearch = false;
2438 else if (command == "stop")
2441 PonderSearch = false;
2443 else if (command == "ponderhit")
2447 // Print search information
2451 else if (lastInfoTime > t)
2452 // HACK: Must be a new search where we searched less than
2453 // NodesBetweenPolls nodes during the first second of search.
2456 else if (t - lastInfoTime >= 1000)
2463 if (dbg_show_hit_rate)
2464 dbg_print_hit_rate();
2466 cout << "info nodes " << TM.nodes_searched() << " nps " << nps()
2467 << " time " << t << " hashfull " << TT.full() << endl;
2469 // We only support current line printing in single thread mode
2470 if (ShowCurrentLine && TM.active_threads() == 1)
2472 cout << "info currline";
2473 for (int p = 0; p < ply; p++)
2474 cout << " " << ss[p].currentMove;
2480 // Should we stop the search?
2484 bool stillAtFirstMove = RootMoveNumber == 1
2485 && !AspirationFailLow
2486 && t > MaxSearchTime + ExtraSearchTime;
2488 bool noMoreTime = t > AbsoluteMaxSearchTime
2489 || stillAtFirstMove;
2491 if ( (Iteration >= 3 && UseTimeManagement && noMoreTime)
2492 || (ExactMaxTime && t >= ExactMaxTime)
2493 || (Iteration >= 3 && MaxNodes && TM.nodes_searched() >= MaxNodes))
2498 // ponderhit() is called when the program is pondering (i.e. thinking while
2499 // it's the opponent's turn to move) in order to let the engine know that
2500 // it correctly predicted the opponent's move.
2504 int t = current_search_time();
2505 PonderSearch = false;
2507 bool stillAtFirstMove = RootMoveNumber == 1
2508 && !AspirationFailLow
2509 && t > MaxSearchTime + ExtraSearchTime;
2511 bool noMoreTime = t > AbsoluteMaxSearchTime
2512 || stillAtFirstMove;
2514 if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
2519 // init_ss_array() does a fast reset of the first entries of a SearchStack array
2521 void init_ss_array(SearchStack ss[]) {
2523 for (int i = 0; i < 3; i++)
2526 ss[i].initKillers();
2531 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2532 // while the program is pondering. The point is to work around a wrinkle in
2533 // the UCI protocol: When pondering, the engine is not allowed to give a
2534 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2535 // We simply wait here until one of these commands is sent, and return,
2536 // after which the bestmove and pondermove will be printed (in id_loop()).
2538 void wait_for_stop_or_ponderhit() {
2540 std::string command;
2544 if (!std::getline(std::cin, command))
2547 if (command == "quit")
2552 else if (command == "ponderhit" || command == "stop")
2558 // init_thread() is the function which is called when a new thread is
2559 // launched. It simply calls the idle_loop() function with the supplied
2560 // threadID. There are two versions of this function; one for POSIX
2561 // threads and one for Windows threads.
2563 #if !defined(_MSC_VER)
2565 void* init_thread(void *threadID) {
2567 TM.idle_loop(*(int*)threadID, NULL);
2573 DWORD WINAPI init_thread(LPVOID threadID) {
2575 TM.idle_loop(*(int*)threadID, NULL);
2582 /// The ThreadsManager class
2584 // resetNodeCounters(), resetBetaCounters(), searched_nodes() and
2585 // get_beta_counters() are getters/setters for the per thread
2586 // counters used to sort the moves at root.
2588 void ThreadsManager::resetNodeCounters() {
2590 for (int i = 0; i < MAX_THREADS; i++)
2591 threads[i].nodes = 0ULL;
2594 void ThreadsManager::resetBetaCounters() {
2596 for (int i = 0; i < MAX_THREADS; i++)
2597 threads[i].betaCutOffs[WHITE] = threads[i].betaCutOffs[BLACK] = 0ULL;
2600 int64_t ThreadsManager::nodes_searched() const {
2602 int64_t result = 0ULL;
2603 for (int i = 0; i < ActiveThreads; i++)
2604 result += threads[i].nodes;
2609 void ThreadsManager::get_beta_counters(Color us, int64_t& our, int64_t& their) const {
2612 for (int i = 0; i < MAX_THREADS; i++)
2614 our += threads[i].betaCutOffs[us];
2615 their += threads[i].betaCutOffs[opposite_color(us)];
2620 // idle_loop() is where the threads are parked when they have no work to do.
2621 // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint
2622 // object for which the current thread is the master.
2624 void ThreadsManager::idle_loop(int threadID, SplitPoint* waitSp) {
2626 assert(threadID >= 0 && threadID < MAX_THREADS);
2630 // Slave threads can exit as soon as AllThreadsShouldExit raises,
2631 // master should exit as last one.
2632 if (AllThreadsShouldExit)
2635 threads[threadID].state = THREAD_TERMINATED;
2639 // If we are not thinking, wait for a condition to be signaled
2640 // instead of wasting CPU time polling for work.
2641 while (AllThreadsShouldSleep || threadID >= ActiveThreads)
2644 assert(threadID != 0);
2645 threads[threadID].state = THREAD_SLEEPING;
2647 #if !defined(_MSC_VER)
2648 pthread_mutex_lock(&WaitLock);
2649 if (AllThreadsShouldSleep || threadID >= ActiveThreads)
2650 pthread_cond_wait(&WaitCond, &WaitLock);
2651 pthread_mutex_unlock(&WaitLock);
2653 WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2657 // If thread has just woken up, mark it as available
2658 if (threads[threadID].state == THREAD_SLEEPING)
2659 threads[threadID].state = THREAD_AVAILABLE;
2661 // If this thread has been assigned work, launch a search
2662 if (threads[threadID].state == THREAD_WORKISWAITING)
2664 assert(!AllThreadsShouldExit && !AllThreadsShouldSleep);
2666 threads[threadID].state = THREAD_SEARCHING;
2668 if (threads[threadID].splitPoint->pvNode)
2669 sp_search_pv(threads[threadID].splitPoint, threadID);
2671 sp_search(threads[threadID].splitPoint, threadID);
2673 assert(threads[threadID].state == THREAD_SEARCHING);
2675 threads[threadID].state = THREAD_AVAILABLE;
2678 // If this thread is the master of a split point and all threads have
2679 // finished their work at this split point, return from the idle loop.
2680 if (waitSp != NULL && waitSp->cpus == 0)
2682 assert(threads[threadID].state == THREAD_AVAILABLE);
2684 threads[threadID].state = THREAD_SEARCHING;
2691 // init_threads() is called during startup. It launches all helper threads,
2692 // and initializes the split point stack and the global locks and condition
2695 void ThreadsManager::init_threads() {
2700 #if !defined(_MSC_VER)
2701 pthread_t pthread[1];
2704 // Initialize global locks
2705 lock_init(&MPLock, NULL);
2707 // Initialize SplitPointStack locks
2708 for (i = 0; i < MAX_THREADS; i++)
2709 for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
2711 SplitPointStack[i][j].parent = NULL;
2712 lock_init(&(SplitPointStack[i][j].lock), NULL);
2715 #if !defined(_MSC_VER)
2716 pthread_mutex_init(&WaitLock, NULL);
2717 pthread_cond_init(&WaitCond, NULL);
2719 for (i = 0; i < MAX_THREADS; i++)
2720 SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0);
2723 // Will be set just before program exits to properly end the threads
2724 AllThreadsShouldExit = false;
2726 // Threads will be put to sleep as soon as created
2727 AllThreadsShouldSleep = true;
2729 // All threads except the main thread should be initialized to THREAD_AVAILABLE
2731 threads[0].state = THREAD_SEARCHING;
2732 for (i = 1; i < MAX_THREADS; i++)
2733 threads[i].state = THREAD_AVAILABLE;
2735 // Launch the helper threads
2736 for (i = 1; i < MAX_THREADS; i++)
2739 #if !defined(_MSC_VER)
2740 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&i)) == 0);
2743 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID) != NULL);
2748 cout << "Failed to create thread number " << i << endl;
2749 Application::exit_with_failure();
2752 // Wait until the thread has finished launching and is gone to sleep
2753 while (threads[i].state != THREAD_SLEEPING);
2758 // exit_threads() is called when the program exits. It makes all the
2759 // helper threads exit cleanly.
2761 void ThreadsManager::exit_threads() {
2763 ActiveThreads = MAX_THREADS; // HACK
2764 AllThreadsShouldSleep = true; // HACK
2765 wake_sleeping_threads();
2767 // This makes the threads to exit idle_loop()
2768 AllThreadsShouldExit = true;
2770 // Wait for thread termination
2771 for (int i = 1; i < MAX_THREADS; i++)
2772 while (threads[i].state != THREAD_TERMINATED);
2774 // Now we can safely destroy the locks
2775 for (int i = 0; i < MAX_THREADS; i++)
2776 for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++)
2777 lock_destroy(&(SplitPointStack[i][j].lock));
2781 // thread_should_stop() checks whether the thread should stop its search.
2782 // This can happen if a beta cutoff has occurred in the thread's currently
2783 // active split point, or in some ancestor of the current split point.
2785 bool ThreadsManager::thread_should_stop(int threadID) const {
2787 assert(threadID >= 0 && threadID < ActiveThreads);
2791 for (sp = threads[threadID].splitPoint; sp && !sp->stopRequest; sp = sp->parent);
2796 // thread_is_available() checks whether the thread with threadID "slave" is
2797 // available to help the thread with threadID "master" at a split point. An
2798 // obvious requirement is that "slave" must be idle. With more than two
2799 // threads, this is not by itself sufficient: If "slave" is the master of
2800 // some active split point, it is only available as a slave to the other
2801 // threads which are busy searching the split point at the top of "slave"'s
2802 // split point stack (the "helpful master concept" in YBWC terminology).
2804 bool ThreadsManager::thread_is_available(int slave, int master) const {
2806 assert(slave >= 0 && slave < ActiveThreads);
2807 assert(master >= 0 && master < ActiveThreads);
2808 assert(ActiveThreads > 1);
2810 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
2813 // Make a local copy to be sure doesn't change under our feet
2814 int localActiveSplitPoints = threads[slave].activeSplitPoints;
2816 if (localActiveSplitPoints == 0)
2817 // No active split points means that the thread is available as
2818 // a slave for any other thread.
2821 if (ActiveThreads == 2)
2824 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
2825 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
2826 // could have been set to 0 by another thread leading to an out of bound access.
2827 if (SplitPointStack[slave][localActiveSplitPoints - 1].slaves[master])
2834 // available_thread_exists() tries to find an idle thread which is available as
2835 // a slave for the thread with threadID "master".
2837 bool ThreadsManager::available_thread_exists(int master) const {
2839 assert(master >= 0 && master < ActiveThreads);
2840 assert(ActiveThreads > 1);
2842 for (int i = 0; i < ActiveThreads; i++)
2843 if (thread_is_available(i, master))
2850 // split() does the actual work of distributing the work at a node between
2851 // several threads at PV nodes. If it does not succeed in splitting the
2852 // node (because no idle threads are available, or because we have no unused
2853 // split point objects), the function immediately returns false. If
2854 // splitting is possible, a SplitPoint object is initialized with all the
2855 // data that must be copied to the helper threads (the current position and
2856 // search stack, alpha, beta, the search depth, etc.), and we tell our
2857 // helper threads that they have been assigned work. This will cause them
2858 // to instantly leave their idle loops and call sp_search_pv(). When all
2859 // threads have returned from sp_search_pv (or, equivalently, when
2860 // splitPoint->cpus becomes 0), split() returns true.
2862 bool ThreadsManager::split(const Position& p, SearchStack* sstck, int ply,
2863 Value* alpha, const Value beta, Value* bestValue,
2864 Depth depth, int* moves, MovePicker* mp, int master, bool pvNode) {
2867 assert(sstck != NULL);
2868 assert(ply >= 0 && ply < PLY_MAX);
2869 assert(*bestValue >= -VALUE_INFINITE);
2870 assert( ( pvNode && *bestValue <= *alpha)
2871 || (!pvNode && *bestValue < beta ));
2872 assert(!pvNode || *alpha < beta);
2873 assert(beta <= VALUE_INFINITE);
2874 assert(depth > Depth(0));
2875 assert(master >= 0 && master < ActiveThreads);
2876 assert(ActiveThreads > 1);
2878 SplitPoint* splitPoint;
2882 // If no other thread is available to help us, or if we have too many
2883 // active split points, don't split.
2884 if ( !available_thread_exists(master)
2885 || threads[master].activeSplitPoints >= ACTIVE_SPLIT_POINTS_MAX)
2887 lock_release(&MPLock);
2891 // Pick the next available split point object from the split point stack
2892 splitPoint = &SplitPointStack[master][threads[master].activeSplitPoints];
2894 // Initialize the split point object
2895 splitPoint->parent = threads[master].splitPoint;
2896 splitPoint->stopRequest = false;
2897 splitPoint->ply = ply;
2898 splitPoint->depth = depth;
2899 splitPoint->alpha = pvNode ? *alpha : beta - 1;
2900 splitPoint->beta = beta;
2901 splitPoint->pvNode = pvNode;
2902 splitPoint->bestValue = *bestValue;
2903 splitPoint->master = master;
2904 splitPoint->mp = mp;
2905 splitPoint->moves = *moves;
2906 splitPoint->cpus = 1;
2907 splitPoint->pos = &p;
2908 splitPoint->parentSstack = sstck;
2909 for (int i = 0; i < ActiveThreads; i++)
2910 splitPoint->slaves[i] = 0;
2912 threads[master].splitPoint = splitPoint;
2913 threads[master].activeSplitPoints++;
2915 // If we are here it means we are not available
2916 assert(threads[master].state != THREAD_AVAILABLE);
2918 // Allocate available threads setting state to THREAD_BOOKED
2919 for (int i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint; i++)
2920 if (thread_is_available(i, master))
2922 threads[i].state = THREAD_BOOKED;
2923 threads[i].splitPoint = splitPoint;
2924 splitPoint->slaves[i] = 1;
2928 assert(splitPoint->cpus > 1);
2930 // We can release the lock because slave threads are already booked and master is not available
2931 lock_release(&MPLock);
2933 // Tell the threads that they have work to do. This will make them leave
2934 // their idle loop. But before copy search stack tail for each thread.
2935 for (int i = 0; i < ActiveThreads; i++)
2936 if (i == master || splitPoint->slaves[i])
2938 memcpy(splitPoint->sstack[i] + ply - 1, sstck + ply - 1, 4 * sizeof(SearchStack));
2940 assert(i == master || threads[i].state == THREAD_BOOKED);
2942 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
2945 // Everything is set up. The master thread enters the idle loop, from
2946 // which it will instantly launch a search, because its state is
2947 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
2948 // idle loop, which means that the main thread will return from the idle
2949 // loop when all threads have finished their work at this split point
2950 // (i.e. when splitPoint->cpus == 0).
2951 idle_loop(master, splitPoint);
2953 // We have returned from the idle loop, which means that all threads are
2954 // finished. Update alpha, beta and bestValue, and return.
2958 *alpha = splitPoint->alpha;
2960 *bestValue = splitPoint->bestValue;
2961 threads[master].activeSplitPoints--;
2962 threads[master].splitPoint = splitPoint->parent;
2964 lock_release(&MPLock);
2969 // wake_sleeping_threads() wakes up all sleeping threads when it is time
2970 // to start a new search from the root.
2972 void ThreadsManager::wake_sleeping_threads() {
2974 assert(AllThreadsShouldSleep);
2975 assert(ActiveThreads > 0);
2977 AllThreadsShouldSleep = false;
2979 if (ActiveThreads == 1)
2982 for (int i = 1; i < ActiveThreads; i++)
2983 assert(threads[i].state == THREAD_SLEEPING);
2985 #if !defined(_MSC_VER)
2986 pthread_mutex_lock(&WaitLock);
2987 pthread_cond_broadcast(&WaitCond);
2988 pthread_mutex_unlock(&WaitLock);
2990 for (int i = 1; i < MAX_THREADS; i++)
2991 SetEvent(SitIdleEvent[i]);
2997 // put_threads_to_sleep() makes all the threads go to sleep just before
2998 // to leave think(), at the end of the search. Threads should have already
2999 // finished the job and should be idle.
3001 void ThreadsManager::put_threads_to_sleep() {
3003 assert(!AllThreadsShouldSleep);
3005 // This makes the threads to go to sleep
3006 AllThreadsShouldSleep = true;
3009 /// The RootMoveList class
3011 // RootMoveList c'tor
3013 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
3015 SearchStack ss[PLY_MAX_PLUS_2];
3016 MoveStack mlist[MaxRootMoves];
3018 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
3020 // Generate all legal moves
3021 MoveStack* last = generate_moves(pos, mlist);
3023 // Add each move to the moves[] array
3024 for (MoveStack* cur = mlist; cur != last; cur++)
3026 bool includeMove = includeAllMoves;
3028 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
3029 includeMove = (searchMoves[k] == cur->move);
3034 // Find a quick score for the move
3036 pos.do_move(cur->move, st);
3037 moves[count].move = cur->move;
3038 moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0);
3039 moves[count].pv[0] = cur->move;
3040 moves[count].pv[1] = MOVE_NONE;
3041 pos.undo_move(cur->move);
3048 // RootMoveList simple methods definitions
3050 void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
3052 moves[moveNum].nodes = nodes;
3053 moves[moveNum].cumulativeNodes += nodes;
3056 void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
3058 moves[moveNum].ourBeta = our;
3059 moves[moveNum].theirBeta = their;
3062 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
3066 for (j = 0; pv[j] != MOVE_NONE; j++)
3067 moves[moveNum].pv[j] = pv[j];
3069 moves[moveNum].pv[j] = MOVE_NONE;
3073 // RootMoveList::sort() sorts the root move list at the beginning of a new
3076 void RootMoveList::sort() {
3078 sort_multipv(count - 1); // Sort all items
3082 // RootMoveList::sort_multipv() sorts the first few moves in the root move
3083 // list by their scores and depths. It is used to order the different PVs
3084 // correctly in MultiPV mode.
3086 void RootMoveList::sort_multipv(int n) {
3090 for (i = 1; i <= n; i++)
3092 RootMove rm = moves[i];
3093 for (j = i; j > 0 && moves[j - 1] < rm; j--)
3094 moves[j] = moves[j - 1];