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"
47 //// Local definitions
54 // IterationInfoType stores search results for each iteration
56 // Because we use relatively small (dynamic) aspiration window,
57 // there happens many fail highs and fail lows in root. And
58 // because we don't do researches in those cases, "value" stored
59 // here is not necessarily exact. Instead in case of fail high/low
60 // we guess what the right value might be and store our guess
61 // as a "speculated value" and then move on. Speculated values are
62 // used just to calculate aspiration window width, so also if are
63 // not exact is not big a problem.
65 struct IterationInfoType {
67 IterationInfoType(Value v = Value(0), Value sv = Value(0))
68 : value(v), speculatedValue(sv) {}
70 Value value, speculatedValue;
74 // The BetaCounterType class is used to order moves at ply one.
75 // Apart for the first one that has its score, following moves
76 // normally have score -VALUE_INFINITE, so are ordered according
77 // to the number of beta cutoffs occurred under their subtree during
78 // the last iteration. The counters are per thread variables to avoid
79 // concurrent accessing under SMP case.
81 struct BetaCounterType {
85 void add(Color us, Depth d, int threadID);
86 void read(Color us, int64_t& our, int64_t& their);
90 // The RootMove class is used for moves at the root at the tree. For each
91 // root move, we store a score, a node count, and a PV (really a refutation
92 // in the case of moves which fail low).
97 bool operator<(const RootMove&); // used to sort
101 int64_t nodes, cumulativeNodes;
102 Move pv[PLY_MAX_PLUS_2];
103 int64_t ourBeta, theirBeta;
107 // The RootMoveList class is essentially an array of RootMove objects, with
108 // a handful of methods for accessing the data in the individual moves.
113 RootMoveList(Position& pos, Move searchMoves[]);
114 inline Move get_move(int moveNum) const;
115 inline Value get_move_score(int moveNum) const;
116 inline void set_move_score(int moveNum, Value score);
117 inline void set_move_nodes(int moveNum, int64_t nodes);
118 inline void set_beta_counters(int moveNum, int64_t our, int64_t their);
119 void set_move_pv(int moveNum, const Move pv[]);
120 inline Move get_move_pv(int moveNum, int i) const;
121 inline int64_t get_move_cumulative_nodes(int moveNum) const;
122 inline int move_count() const;
123 Move scan_for_easy_move() const;
125 void sort_multipv(int n);
128 static const int MaxRootMoves = 500;
129 RootMove moves[MaxRootMoves];
136 // Search depth at iteration 1
137 const Depth InitialDepth = OnePly /*+ OnePly/2*/;
139 // Depth limit for selective search
140 const Depth SelectiveDepth = 7 * OnePly;
142 // Use internal iterative deepening?
143 const bool UseIIDAtPVNodes = true;
144 const bool UseIIDAtNonPVNodes = false;
146 // Internal iterative deepening margin. At Non-PV moves, when
147 // UseIIDAtNonPVNodes is true, we do an internal iterative deepening
148 // search when the static evaluation is at most IIDMargin below beta.
149 const Value IIDMargin = Value(0x100);
151 // Easy move margin. An easy move candidate must be at least this much
152 // better than the second best move.
153 const Value EasyMoveMargin = Value(0x200);
155 // Problem margin. If the score of the first move at iteration N+1 has
156 // dropped by more than this since iteration N, the boolean variable
157 // "Problem" is set to true, which will make the program spend some extra
158 // time looking for a better move.
159 const Value ProblemMargin = Value(0x28);
161 // No problem margin. If the boolean "Problem" is true, and a new move
162 // is found at the root which is less than NoProblemMargin worse than the
163 // best move from the previous iteration, Problem is set back to false.
164 const Value NoProblemMargin = Value(0x14);
166 // Null move margin. A null move search will not be done if the approximate
167 // evaluation of the position is more than NullMoveMargin below beta.
168 const Value NullMoveMargin = Value(0x300);
170 // Pruning criterions. See the code and comments in ok_to_prune() to
171 // understand their precise meaning.
172 const bool PruneEscapeMoves = false;
173 const bool PruneDefendingMoves = false;
174 const bool PruneBlockingMoves = false;
176 // Margins for futility pruning in the quiescence search, and at frontier
177 // and near frontier nodes.
178 const Value FutilityMarginQS = Value(0x80);
180 // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply
181 const Value FutilityMargins[12] = { Value(0x100), Value(0x120), Value(0x200), Value(0x220), Value(0x250), Value(0x270),
182 // 4 ply 4.5 ply 5 ply 5.5 ply 6 ply 6.5 ply
183 Value(0x2A0), Value(0x2C0), Value(0x340), Value(0x360), Value(0x3A0), Value(0x3C0) };
185 const Depth RazorDepth = 4*OnePly;
187 // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply
188 const Value RazorMargins[6] = { Value(0x180), Value(0x300), Value(0x300), Value(0x3C0), Value(0x3C0), Value(0x3C0) };
190 // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply
191 const Value RazorApprMargins[6] = { Value(0x520), Value(0x300), Value(0x300), Value(0x300), Value(0x300), Value(0x300) };
193 // The main transposition table
194 TranspositionTable TT;
197 /// Variables initialized by UCI options
199 // Adjustable playing strength
201 const int SlowdownArray[32] = {
202 19, 41, 70, 110, 160, 230, 320, 430, 570, 756, 1000, 1300, 1690, 2197,
203 2834, 3600, 4573, 5809, 7700, 9863, 12633, 16181, 20726, 26584, 34005,
204 43557, 55792, 71463, 91536, 117247, 150180, 192363
207 const int MaxStrength = 25;
209 // Minimum number of full depth (i.e. non-reduced) moves at PV and non-PV nodes
210 int LMRPVMoves, LMRNonPVMoves; // heavy SMP read access for the latter
212 // Depth limit for use of dynamic threat detection
213 Depth ThreatDepth; // heavy SMP read access
215 // Last seconds noise filtering (LSN)
216 const bool UseLSNFiltering = true;
217 const int LSNTime = 4000; // In milliseconds
218 const Value LSNValue = value_from_centipawns(200);
219 bool loseOnTime = false;
221 // Extensions. Array index 0 is used at non-PV nodes, index 1 at PV nodes.
222 // There is heavy SMP read access on these arrays
223 Depth CheckExtension[2], SingleReplyExtension[2], PawnPushTo7thExtension[2];
224 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
226 // Iteration counters
228 BetaCounterType BetaCounter; // has per-thread internal data
230 // Scores and number of times the best move changed for each iteration
231 IterationInfoType IterationInfo[PLY_MAX_PLUS_2];
232 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
237 // Time managment variables
239 int MaxNodes, MaxDepth;
240 int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
244 bool StopOnPonderhit;
245 bool AbortSearch; // heavy SMP read access
251 // Show current line?
252 bool ShowCurrentLine;
256 std::ofstream LogFile;
258 // MP related variables
259 int ActiveThreads = 1;
260 Depth MinimumSplitDepth;
261 int MaxThreadsPerSplitPoint;
262 Thread Threads[THREAD_MAX];
265 bool AllThreadsShouldExit = false;
266 const int MaxActiveSplitPoints = 8;
267 SplitPoint SplitPointStack[THREAD_MAX][MaxActiveSplitPoints];
270 #if !defined(_MSC_VER)
271 pthread_cond_t WaitCond;
272 pthread_mutex_t WaitLock;
274 HANDLE SitIdleEvent[THREAD_MAX];
277 // Node counters, used only by thread[0] but try to keep in different
278 // cache lines (64 bytes each) from the heavy SMP read accessed variables.
280 int NodesBetweenPolls = 30000;
288 Value id_loop(const Position& pos, Move searchMoves[]);
289 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta);
290 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
291 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID);
292 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
293 void sp_search(SplitPoint* sp, int threadID);
294 void sp_search_pv(SplitPoint* sp, int threadID);
295 void init_node(const Position& pos, 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 Depth extension(const Position& pos, Move m, bool pvNode, bool capture, bool check, bool singleReply, bool mateThreat, bool* dangerous);
302 bool ok_to_do_nullmove(const Position& pos);
303 bool ok_to_prune(const Position& pos, Move m, Move threat, Depth d);
304 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
305 bool ok_to_history(const Position& pos, Move m);
306 void update_history(const Position& pos, Move m, Depth depth, Move movesSearched[], int moveCount);
307 void update_killers(Move m, SearchStack& ss);
308 void slowdown(const Position& pos);
310 bool fail_high_ply_1();
311 int current_search_time();
315 void print_current_line(SearchStack ss[], int ply, int threadID);
316 void wait_for_stop_or_ponderhit();
318 void idle_loop(int threadID, SplitPoint* waitSp);
319 void init_split_point_stack();
320 void destroy_split_point_stack();
321 bool thread_should_stop(int threadID);
322 bool thread_is_available(int slave, int master);
323 bool idle_thread_exists(int master);
324 bool split(const Position& pos, SearchStack* ss, int ply,
325 Value *alpha, Value *beta, Value *bestValue, Depth depth, int *moves,
326 MovePicker *mp, Bitboard dcCandidates, int master, bool pvNode);
327 void wake_sleeping_threads();
329 #if !defined(_MSC_VER)
330 void *init_thread(void *threadID);
332 DWORD WINAPI init_thread(LPVOID threadID);
342 /// think() is the external interface to Stockfish's search, and is called when
343 /// the program receives the UCI 'go' command. It initializes various
344 /// search-related global variables, and calls root_search(). It returns false
345 /// when a quit command is received during the search.
347 bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
348 int time[], int increment[], int movesToGo, int maxDepth,
349 int maxNodes, int maxTime, Move searchMoves[]) {
351 // Look for a book move
352 if (!infinite && !ponder && get_option_value_bool("OwnBook"))
355 if (get_option_value_string("Book File") != OpeningBook.file_name())
356 OpeningBook.open("book.bin");
358 bookMove = OpeningBook.get_move(pos);
359 if (bookMove != MOVE_NONE)
361 std::cout << "bestmove " << bookMove << std::endl;
366 // Initialize global search variables
368 SearchStartTime = get_system_time();
369 for (int i = 0; i < THREAD_MAX; i++)
371 Threads[i].nodes = 0ULL;
372 Threads[i].failHighPly1 = false;
375 InfiniteSearch = infinite;
376 PonderSearch = ponder;
377 StopOnPonderhit = false;
383 ExactMaxTime = maxTime;
385 // Read UCI option values
386 TT.set_size(get_option_value_int("Hash"));
387 if (button_was_pressed("Clear Hash"))
390 loseOnTime = false; // reset at the beginning of a new game
393 bool PonderingEnabled = get_option_value_bool("Ponder");
394 MultiPV = get_option_value_int("MultiPV");
396 CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)"));
397 CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)"));
399 SingleReplyExtension[1] = Depth(get_option_value_int("Single Reply Extension (PV nodes)"));
400 SingleReplyExtension[0] = Depth(get_option_value_int("Single Reply Extension (non-PV nodes)"));
402 PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)"));
403 PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
405 PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
406 PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
408 PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
409 PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)"));
411 MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
412 MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
414 LMRPVMoves = get_option_value_int("Full Depth Moves (PV nodes)") + 1;
415 LMRNonPVMoves = get_option_value_int("Full Depth Moves (non-PV nodes)") + 1;
416 ThreatDepth = get_option_value_int("Threat Depth") * OnePly;
418 Chess960 = get_option_value_bool("UCI_Chess960");
419 ShowCurrentLine = get_option_value_bool("UCI_ShowCurrLine");
420 UseLogFile = get_option_value_bool("Use Search Log");
422 LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app);
424 MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly;
425 MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point");
427 read_weights(pos.side_to_move());
429 // Set the number of active threads. If UCI_LimitStrength is enabled, never
430 // use more than one thread.
431 int newActiveThreads =
432 get_option_value_bool("UCI_LimitStrength")? 1 : get_option_value_int("Threads");
433 if (newActiveThreads != ActiveThreads)
435 ActiveThreads = newActiveThreads;
436 init_eval(ActiveThreads);
439 // Wake up sleeping threads
440 wake_sleeping_threads();
442 for (int i = 1; i < ActiveThreads; i++)
443 assert(thread_is_available(i, 0));
445 // Set playing strength
446 if (get_option_value_bool("UCI_LimitStrength"))
448 Strength = (get_option_value_int("UCI_Elo") - 2100) / 25;
450 (Strength == MaxStrength)? 0 : SlowdownArray[Max(0, 31-Strength)];
454 Strength = MaxStrength;
459 int myTime = time[side_to_move];
460 int myIncrement = increment[side_to_move];
462 if (!movesToGo) // Sudden death time control
466 MaxSearchTime = myTime / 30 + myIncrement;
467 AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
468 } else { // Blitz game without increment
469 MaxSearchTime = myTime / 30;
470 AbsoluteMaxSearchTime = myTime / 8;
473 else // (x moves) / (y minutes)
477 MaxSearchTime = myTime / 2;
478 AbsoluteMaxSearchTime = Min(myTime / 2, myTime - 500);
480 MaxSearchTime = myTime / Min(movesToGo, 20);
481 AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
485 if (PonderingEnabled)
487 MaxSearchTime += MaxSearchTime / 4;
488 MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime);
491 // Fixed depth or fixed number of nodes?
494 InfiniteSearch = true; // HACK
499 NodesBetweenPolls = Min(MaxNodes, 30000);
500 InfiniteSearch = true; // HACK
503 if (Slowdown > 50000) NodesBetweenPolls = 30;
504 else if (Slowdown > 10000) NodesBetweenPolls = 100;
505 else if (Slowdown > 1000) NodesBetweenPolls = 500;
506 else if (Slowdown > 100) NodesBetweenPolls = 3000;
507 else NodesBetweenPolls = 15000;
510 NodesBetweenPolls = 30000;
512 // Write information to search log file
514 LogFile << "Searching: " << pos.to_fen() << std::endl
515 << "infinite: " << infinite
516 << " ponder: " << ponder
517 << " time: " << myTime
518 << " increment: " << myIncrement
519 << " moves to go: " << movesToGo << std::endl;
522 // We're ready to start thinking. Call the iterative deepening loop function
524 // FIXME we really need to cleanup all this LSN ugliness
527 Value v = id_loop(pos, searchMoves);
528 loseOnTime = ( UseLSNFiltering
535 loseOnTime = false; // reset for next match
536 while (SearchStartTime + myTime + 1000 > get_system_time())
538 id_loop(pos, searchMoves); // to fail gracefully
549 /// init_threads() is called during startup. It launches all helper threads,
550 /// and initializes the split point stack and the global locks and condition
553 void init_threads() {
557 #if !defined(_MSC_VER)
558 pthread_t pthread[1];
561 for (i = 0; i < THREAD_MAX; i++)
562 Threads[i].activeSplitPoints = 0;
564 // Initialize global locks
565 lock_init(&MPLock, NULL);
566 lock_init(&IOLock, NULL);
568 init_split_point_stack();
570 #if !defined(_MSC_VER)
571 pthread_mutex_init(&WaitLock, NULL);
572 pthread_cond_init(&WaitCond, NULL);
574 for (i = 0; i < THREAD_MAX; i++)
575 SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0);
578 // All threads except the main thread should be initialized to idle state
579 for (i = 1; i < THREAD_MAX; i++)
581 Threads[i].stop = false;
582 Threads[i].workIsWaiting = false;
583 Threads[i].idle = true;
584 Threads[i].running = false;
587 // Launch the helper threads
588 for(i = 1; i < THREAD_MAX; i++)
590 #if !defined(_MSC_VER)
591 pthread_create(pthread, NULL, init_thread, (void*)(&i));
594 CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID);
597 // Wait until the thread has finished launching
598 while (!Threads[i].running);
603 /// stop_threads() is called when the program exits. It makes all the
604 /// helper threads exit cleanly.
606 void stop_threads() {
608 ActiveThreads = THREAD_MAX; // HACK
609 Idle = false; // HACK
610 wake_sleeping_threads();
611 AllThreadsShouldExit = true;
612 for (int i = 1; i < THREAD_MAX; i++)
614 Threads[i].stop = true;
615 while(Threads[i].running);
617 destroy_split_point_stack();
621 /// nodes_searched() returns the total number of nodes searched so far in
622 /// the current search.
624 int64_t nodes_searched() {
626 int64_t result = 0ULL;
627 for (int i = 0; i < ActiveThreads; i++)
628 result += Threads[i].nodes;
633 // SearchStack::init() initializes a search stack. Used at the beginning of a
634 // new search from the root.
635 void SearchStack::init(int ply) {
637 pv[ply] = pv[ply + 1] = MOVE_NONE;
638 currentMove = threatMove = MOVE_NONE;
639 reduction = Depth(0);
642 void SearchStack::initKillers() {
644 mateKiller = MOVE_NONE;
645 for (int i = 0; i < KILLER_MAX; i++)
646 killers[i] = MOVE_NONE;
651 // id_loop() is the main iterative deepening loop. It calls root_search
652 // repeatedly with increasing depth until the allocated thinking time has
653 // been consumed, the user stops the search, or the maximum search depth is
656 Value id_loop(const Position& pos, Move searchMoves[]) {
659 SearchStack ss[PLY_MAX_PLUS_2];
661 // searchMoves are verified, copied, scored and sorted
662 RootMoveList rml(p, searchMoves);
666 p.setTranspositionTable(&TT);
668 for (int i = 0; i < 3; i++)
673 IterationInfo[1] = IterationInfoType(rml.get_move_score(0), rml.get_move_score(0));
676 Move EasyMove = rml.scan_for_easy_move();
678 // Iterative deepening loop
679 while (Iteration < PLY_MAX)
681 // Initialize iteration
684 BestMoveChangesByIteration[Iteration] = 0;
688 std::cout << "info depth " << Iteration << std::endl;
690 // Calculate dynamic search window based on previous iterations
693 if (MultiPV == 1 && Iteration >= 6 && abs(IterationInfo[Iteration - 1].value) < VALUE_KNOWN_WIN)
695 int prevDelta1 = IterationInfo[Iteration - 1].speculatedValue - IterationInfo[Iteration - 2].speculatedValue;
696 int prevDelta2 = IterationInfo[Iteration - 2].speculatedValue - IterationInfo[Iteration - 3].speculatedValue;
698 int delta = Max(2 * abs(prevDelta1) + abs(prevDelta2), ProblemMargin);
700 alpha = Max(IterationInfo[Iteration - 1].value - delta, -VALUE_INFINITE);
701 beta = Min(IterationInfo[Iteration - 1].value + delta, VALUE_INFINITE);
705 alpha = - VALUE_INFINITE;
706 beta = VALUE_INFINITE;
709 // Search to the current depth
710 Value value = root_search(p, ss, rml, alpha, beta);
712 // Write PV to transposition table, in case the relevant entries have
713 // been overwritten during the search.
714 TT.insert_pv(p, ss[0].pv);
717 break; // Value cannot be trusted. Break out immediately!
719 //Save info about search result
720 Value speculatedValue;
723 Value delta = value - IterationInfo[Iteration - 1].value;
730 speculatedValue = value + delta;
731 BestMoveChangesByIteration[Iteration] += 2; // Allocate more time
733 else if (value <= alpha)
735 assert(value == alpha);
739 speculatedValue = value + delta;
740 BestMoveChangesByIteration[Iteration] += 3; // Allocate more time
742 speculatedValue = value;
744 speculatedValue = Min(Max(speculatedValue, -VALUE_INFINITE), VALUE_INFINITE);
745 IterationInfo[Iteration] = IterationInfoType(value, speculatedValue);
747 // Erase the easy move if it differs from the new best move
748 if (ss[0].pv[0] != EasyMove)
749 EasyMove = MOVE_NONE;
756 bool stopSearch = false;
758 // Stop search early if there is only a single legal move
759 if (Iteration >= 6 && rml.move_count() == 1)
762 // Stop search early when the last two iterations returned a mate score
764 && abs(IterationInfo[Iteration].value) >= abs(VALUE_MATE) - 100
765 && abs(IterationInfo[Iteration-1].value) >= abs(VALUE_MATE) - 100)
768 // Stop search early if one move seems to be much better than the rest
769 int64_t nodes = nodes_searched();
773 && EasyMove == ss[0].pv[0]
774 && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
775 && current_search_time() > MaxSearchTime / 16)
776 ||( rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100
777 && current_search_time() > MaxSearchTime / 32)))
780 // Add some extra time if the best move has changed during the last two iterations
781 if (Iteration > 5 && Iteration <= 50)
782 ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2)
783 + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3);
785 // Stop search if most of MaxSearchTime is consumed at the end of the
786 // iteration. We probably don't have enough time to search the first
787 // move at the next iteration anyway.
788 if (current_search_time() > ((MaxSearchTime + ExtraSearchTime)*80) / 128)
793 //FIXME: Implement fail-low emergency measures
797 StopOnPonderhit = true;
801 if (MaxDepth && Iteration >= MaxDepth)
807 // If we are pondering, we shouldn't print the best move before we
810 wait_for_stop_or_ponderhit();
812 // Print final search statistics
813 std::cout << "info nodes " << nodes_searched()
815 << " time " << current_search_time()
816 << " hashfull " << TT.full() << std::endl;
818 // Print the best move and the ponder move to the standard output
819 if (ss[0].pv[0] == MOVE_NONE)
821 ss[0].pv[0] = rml.get_move(0);
822 ss[0].pv[1] = MOVE_NONE;
824 std::cout << "bestmove " << ss[0].pv[0];
825 if (ss[0].pv[1] != MOVE_NONE)
826 std::cout << " ponder " << ss[0].pv[1];
828 std::cout << std::endl;
833 dbg_print_mean(LogFile);
835 if (dbg_show_hit_rate)
836 dbg_print_hit_rate(LogFile);
839 LogFile << "Nodes: " << nodes_searched() << std::endl
840 << "Nodes/second: " << nps() << std::endl
841 << "Best move: " << move_to_san(p, ss[0].pv[0]) << std::endl;
843 p.do_move(ss[0].pv[0], st);
844 LogFile << "Ponder move: " << move_to_san(p, ss[0].pv[1])
845 << std::endl << std::endl;
847 return rml.get_move_score(0);
851 // root_search() is the function which searches the root node. It is
852 // similar to search_pv except that it uses a different move ordering
853 // scheme (perhaps we should try to use this at internal PV nodes, too?)
854 // and prints some information to the standard output.
856 Value root_search(Position& pos, SearchStack ss[], RootMoveList &rml, Value alpha, Value beta) {
858 Value oldAlpha = alpha;
860 Bitboard dcCandidates = pos.discovered_check_candidates(pos.side_to_move());
862 // Loop through all the moves in the root move list
863 for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
867 // We failed high, invalidate and skip next moves, leave node-counters
868 // and beta-counters as they are and quickly return, we will try to do
869 // a research at the next iteration with a bigger aspiration window.
870 rml.set_move_score(i, -VALUE_INFINITE);
878 RootMoveNumber = i + 1;
881 // Remember the node count before the move is searched. The node counts
882 // are used to sort the root moves at the next iteration.
883 nodes = nodes_searched();
885 // Reset beta cut-off counters
888 // Pick the next root move, and print the move and the move number to
889 // the standard output.
890 move = ss[0].currentMove = rml.get_move(i);
891 if (current_search_time() >= 1000)
892 std::cout << "info currmove " << move
893 << " currmovenumber " << i + 1 << std::endl;
895 // Decide search depth for this move
896 bool moveIsCapture = pos.move_is_capture(move);
898 ext = extension(pos, move, true, moveIsCapture, pos.move_is_check(move), false, false, &dangerous);
899 newDepth = (Iteration - 2) * OnePly + ext + InitialDepth;
901 // Make the move, and search it
902 pos.do_move(move, st, dcCandidates);
906 // Aspiration window is disabled in multi-pv case
908 alpha = -VALUE_INFINITE;
910 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
911 // If the value has dropped a lot compared to the last iteration,
912 // set the boolean variable Problem to true. This variable is used
913 // for time managment: When Problem is true, we try to complete the
914 // current iteration before playing a move.
915 Problem = (Iteration >= 2 && value <= IterationInfo[Iteration-1].value - ProblemMargin);
917 if (Problem && StopOnPonderhit)
918 StopOnPonderhit = false;
922 if ( newDepth >= 3*OnePly
923 && i >= MultiPV + LMRPVMoves - 2 // Remove -2 and decrease LMRPVMoves instead ?
926 && !move_is_promotion(move)
927 && !move_is_castle(move))
929 ss[0].reduction = OnePly;
930 value = -search(pos, ss, -alpha, newDepth-OnePly, 1, true, 0);
932 value = alpha + 1; // Just to trigger next condition
936 value = -search(pos, ss, -alpha, newDepth, 1, true, 0);
939 // Fail high! Set the boolean variable FailHigh to true, and
940 // re-search the move with a big window. The variable FailHigh is
941 // used for time managment: We try to avoid aborting the search
942 // prematurely during a fail high research.
944 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
951 // Finished searching the move. If AbortSearch is true, the search
952 // was aborted because the user interrupted the search or because we
953 // ran out of time. In this case, the return value of the search cannot
954 // be trusted, and we break out of the loop without updating the best
959 // Remember the node count for this move. The node counts are used to
960 // sort the root moves at the next iteration.
961 rml.set_move_nodes(i, nodes_searched() - nodes);
963 // Remember the beta-cutoff statistics
965 BetaCounter.read(pos.side_to_move(), our, their);
966 rml.set_beta_counters(i, our, their);
968 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
970 if (value <= alpha && i >= MultiPV)
971 rml.set_move_score(i, -VALUE_INFINITE);
974 // PV move or new best move!
977 rml.set_move_score(i, value);
979 TT.extract_pv(pos, ss[0].pv);
980 rml.set_move_pv(i, ss[0].pv);
984 // We record how often the best move has been changed in each
985 // iteration. This information is used for time managment: When
986 // the best move changes frequently, we allocate some more time.
988 BestMoveChangesByIteration[Iteration]++;
990 // Print search information to the standard output
991 std::cout << "info depth " << Iteration
992 << " score " << value_to_string(value)
994 " lowerbound" : ((value <= alpha)? " upperbound" : ""))
995 << " time " << current_search_time()
996 << " nodes " << nodes_searched()
1000 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
1001 std::cout << ss[0].pv[j] << " ";
1003 std::cout << std::endl;
1006 LogFile << pretty_pv(pos, current_search_time(), Iteration, nodes_searched(), value, ss[0].pv)
1012 // Reset the global variable Problem to false if the value isn't too
1013 // far below the final value from the last iteration.
1014 if (value > IterationInfo[Iteration - 1].value - NoProblemMargin)
1019 rml.sort_multipv(i);
1020 for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
1023 std::cout << "info multipv " << j + 1
1024 << " score " << value_to_string(rml.get_move_score(j))
1025 << " depth " << ((j <= i)? Iteration : Iteration - 1)
1026 << " time " << current_search_time()
1027 << " nodes " << nodes_searched()
1031 for (k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
1032 std::cout << rml.get_move_pv(j, k) << " ";
1034 std::cout << std::endl;
1036 alpha = rml.get_move_score(Min(i, MultiPV-1));
1038 } // New best move case
1040 assert(alpha >= oldAlpha);
1042 FailLow = (alpha == oldAlpha);
1048 // search_pv() is the main search function for PV nodes.
1050 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta,
1051 Depth depth, int ply, int threadID) {
1053 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1054 assert(beta > alpha && beta <= VALUE_INFINITE);
1055 assert(ply >= 0 && ply < PLY_MAX);
1056 assert(threadID >= 0 && threadID < ActiveThreads);
1059 return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID);
1061 // Initialize, and make an early exit in case of an aborted search,
1062 // an instant draw, maximum ply reached, etc.
1063 init_node(pos, ss, ply, threadID);
1065 // After init_node() that calls poll()
1066 if (AbortSearch || thread_should_stop(threadID))
1074 if (ply >= PLY_MAX - 1)
1075 return evaluate(pos, ei, threadID);
1077 // Mate distance pruning
1078 Value oldAlpha = alpha;
1079 alpha = Max(value_mated_in(ply), alpha);
1080 beta = Min(value_mate_in(ply+1), beta);
1084 // Transposition table lookup. At PV nodes, we don't use the TT for
1085 // pruning, but only for move ordering.
1086 const TTEntry* tte = TT.retrieve(pos.get_key());
1087 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1089 // Go with internal iterative deepening if we don't have a TT move
1090 if (UseIIDAtPVNodes && ttMove == MOVE_NONE && depth >= 5*OnePly)
1092 search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID);
1093 ttMove = ss[ply].pv[ply];
1096 // Initialize a MovePicker object for the current position, and prepare
1097 // to search all moves
1098 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1100 Move move, movesSearched[256];
1102 Value value, bestValue = -VALUE_INFINITE;
1103 Bitboard dcCandidates = mp.discovered_check_candidates();
1104 Color us = pos.side_to_move();
1105 bool isCheck = pos.is_check();
1106 bool mateThreat = pos.has_mate_threat(opposite_color(us));
1108 // Loop through all legal moves until no moves remain or a beta cutoff
1110 while ( alpha < beta
1111 && (move = mp.get_next_move()) != MOVE_NONE
1112 && !thread_should_stop(threadID))
1114 assert(move_is_ok(move));
1116 bool singleReply = (isCheck && mp.number_of_moves() == 1);
1117 bool moveIsCheck = pos.move_is_check(move, dcCandidates);
1118 bool moveIsCapture = pos.move_is_capture(move);
1120 movesSearched[moveCount++] = ss[ply].currentMove = move;
1122 // Decide the new search depth
1124 Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous);
1125 Depth newDepth = depth - OnePly + ext;
1127 // Make and search the move
1129 pos.do_move(move, st, dcCandidates);
1131 if (moveCount == 1) // The first move in list is the PV
1132 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1135 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1136 // if the move fails high will be re-searched at full depth.
1137 if ( depth >= 3*OnePly
1138 && moveCount >= LMRPVMoves
1141 && !move_is_promotion(move)
1142 && !move_is_castle(move)
1143 && !move_is_killer(move, ss[ply]))
1145 ss[ply].reduction = OnePly;
1146 value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, threadID);
1149 value = alpha + 1; // Just to trigger next condition
1151 if (value > alpha) // Go with full depth non-pv search
1153 ss[ply].reduction = Depth(0);
1154 value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID);
1155 if (value > alpha && value < beta)
1157 // When the search fails high at ply 1 while searching the first
1158 // move at the root, set the flag failHighPly1. This is used for
1159 // time managment: We don't want to stop the search early in
1160 // such cases, because resolving the fail high at ply 1 could
1161 // result in a big drop in score at the root.
1162 if (ply == 1 && RootMoveNumber == 1)
1163 Threads[threadID].failHighPly1 = true;
1165 // A fail high occurred. Re-search at full window (pv search)
1166 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1167 Threads[threadID].failHighPly1 = false;
1171 pos.undo_move(move);
1173 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1176 if (value > bestValue)
1183 if (value == value_mate_in(ply + 1))
1184 ss[ply].mateKiller = move;
1186 // If we are at ply 1, and we are searching the first root move at
1187 // ply 0, set the 'Problem' variable if the score has dropped a lot
1188 // (from the computer's point of view) since the previous iteration.
1191 && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
1196 if ( ActiveThreads > 1
1198 && depth >= MinimumSplitDepth
1200 && idle_thread_exists(threadID)
1202 && !thread_should_stop(threadID)
1203 && split(pos, ss, ply, &alpha, &beta, &bestValue, depth,
1204 &moveCount, &mp, dcCandidates, threadID, true))
1208 // All legal moves have been searched. A special case: If there were
1209 // no legal moves, it must be mate or stalemate.
1211 return (isCheck ? value_mated_in(ply) : VALUE_DRAW);
1213 // If the search is not aborted, update the transposition table,
1214 // history counters, and killer moves.
1215 if (AbortSearch || thread_should_stop(threadID))
1218 if (bestValue <= oldAlpha)
1219 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1221 else if (bestValue >= beta)
1223 BetaCounter.add(pos.side_to_move(), depth, threadID);
1224 Move m = ss[ply].pv[ply];
1225 if (ok_to_history(pos, m)) // Only non capture moves are considered
1227 update_history(pos, m, depth, movesSearched, moveCount);
1228 update_killers(m, ss[ply]);
1230 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m);
1233 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
1239 // search() is the search function for zero-width nodes.
1241 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth,
1242 int ply, bool allowNullmove, int threadID) {
1244 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1245 assert(ply >= 0 && ply < PLY_MAX);
1246 assert(threadID >= 0 && threadID < ActiveThreads);
1249 return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1251 // Initialize, and make an early exit in case of an aborted search,
1252 // an instant draw, maximum ply reached, etc.
1253 init_node(pos, ss, ply, threadID);
1255 // After init_node() that calls poll()
1256 if (AbortSearch || thread_should_stop(threadID))
1264 if (ply >= PLY_MAX - 1)
1265 return evaluate(pos, ei, threadID);
1267 // Mate distance pruning
1268 if (value_mated_in(ply) >= beta)
1271 if (value_mate_in(ply + 1) < beta)
1274 // Transposition table lookup
1275 const TTEntry* tte = TT.retrieve(pos.get_key());
1276 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1278 if (tte && ok_to_use_TT(tte, depth, beta, ply))
1280 ss[ply].currentMove = ttMove; // can be MOVE_NONE
1281 return value_from_tt(tte->value(), ply);
1284 Value approximateEval = quick_evaluate(pos);
1285 bool mateThreat = false;
1286 bool isCheck = pos.is_check();
1292 && !value_is_mate(beta)
1293 && ok_to_do_nullmove(pos)
1294 && approximateEval >= beta - NullMoveMargin)
1296 ss[ply].currentMove = MOVE_NULL;
1299 pos.do_null_move(st);
1300 int R = (depth >= 5 * OnePly ? 4 : 3); // Null move dynamic reduction
1302 Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);
1304 pos.undo_null_move();
1306 if (nullValue >= beta)
1308 if (depth < 6 * OnePly)
1311 // Do zugzwang verification search
1312 Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
1316 // The null move failed low, which means that we may be faced with
1317 // some kind of threat. If the previous move was reduced, check if
1318 // the move that refuted the null move was somehow connected to the
1319 // move which was reduced. If a connection is found, return a fail
1320 // low score (which will cause the reduced move to fail high in the
1321 // parent node, which will trigger a re-search with full depth).
1322 if (nullValue == value_mated_in(ply + 2))
1325 ss[ply].threatMove = ss[ply + 1].currentMove;
1326 if ( depth < ThreatDepth
1327 && ss[ply - 1].reduction
1328 && connected_moves(pos, ss[ply - 1].currentMove, ss[ply].threatMove))
1332 // Null move search not allowed, try razoring
1333 else if ( !value_is_mate(beta)
1334 && depth < RazorDepth
1335 && approximateEval < beta - RazorApprMargins[int(depth) - 2]
1336 && ss[ply - 1].currentMove != MOVE_NULL
1337 && ttMove == MOVE_NONE
1338 && !pos.has_pawn_on_7th(pos.side_to_move()))
1340 Value v = qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1341 if (v < beta - RazorMargins[int(depth) - 2])
1345 // Go with internal iterative deepening if we don't have a TT move
1346 if (UseIIDAtNonPVNodes && ttMove == MOVE_NONE && depth >= 8*OnePly &&
1347 evaluate(pos, ei, threadID) >= beta - IIDMargin)
1349 search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID);
1350 ttMove = ss[ply].pv[ply];
1353 // Initialize a MovePicker object for the current position, and prepare
1354 // to search all moves.
1355 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1357 Move move, movesSearched[256];
1359 Value value, bestValue = -VALUE_INFINITE;
1360 Bitboard dcCandidates = mp.discovered_check_candidates();
1361 Value futilityValue = VALUE_NONE;
1362 bool useFutilityPruning = depth < SelectiveDepth
1365 // Loop through all legal moves until no moves remain or a beta cutoff
1367 while ( bestValue < beta
1368 && (move = mp.get_next_move()) != MOVE_NONE
1369 && !thread_should_stop(threadID))
1371 assert(move_is_ok(move));
1373 bool singleReply = (isCheck && mp.number_of_moves() == 1);
1374 bool moveIsCheck = pos.move_is_check(move, dcCandidates);
1375 bool moveIsCapture = pos.move_is_capture(move);
1377 movesSearched[moveCount++] = ss[ply].currentMove = move;
1379 // Decide the new search depth
1381 Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous);
1382 Depth newDepth = depth - OnePly + ext;
1385 if ( useFutilityPruning
1388 && !move_is_promotion(move))
1390 // History pruning. See ok_to_prune() definition
1391 if ( moveCount >= 2 + int(depth)
1392 && ok_to_prune(pos, move, ss[ply].threatMove, depth))
1395 // Value based pruning
1396 if (approximateEval < beta)
1398 if (futilityValue == VALUE_NONE)
1399 futilityValue = evaluate(pos, ei, threadID)
1400 + FutilityMargins[int(depth) - 2];
1402 if (futilityValue < beta)
1404 if (futilityValue > bestValue)
1405 bestValue = futilityValue;
1411 // Make and search the move
1413 pos.do_move(move, st, dcCandidates);
1415 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1416 // if the move fails high will be re-searched at full depth.
1417 if ( depth >= 3*OnePly
1418 && moveCount >= LMRNonPVMoves
1421 && !move_is_promotion(move)
1422 && !move_is_castle(move)
1423 && !move_is_killer(move, ss[ply]))
1425 ss[ply].reduction = OnePly;
1426 value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);
1429 value = beta; // Just to trigger next condition
1431 if (value >= beta) // Go with full depth non-pv search
1433 ss[ply].reduction = Depth(0);
1434 value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID);
1436 pos.undo_move(move);
1438 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1441 if (value > bestValue)
1447 if (value == value_mate_in(ply + 1))
1448 ss[ply].mateKiller = move;
1452 if ( ActiveThreads > 1
1454 && depth >= MinimumSplitDepth
1456 && idle_thread_exists(threadID)
1458 && !thread_should_stop(threadID)
1459 && split(pos, ss, ply, &beta, &beta, &bestValue, depth, &moveCount,
1460 &mp, dcCandidates, threadID, false))
1464 // All legal moves have been searched. A special case: If there were
1465 // no legal moves, it must be mate or stalemate.
1467 return (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW);
1469 // If the search is not aborted, update the transposition table,
1470 // history counters, and killer moves.
1471 if (AbortSearch || thread_should_stop(threadID))
1474 if (bestValue < beta)
1475 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1478 BetaCounter.add(pos.side_to_move(), depth, threadID);
1479 Move m = ss[ply].pv[ply];
1480 if (ok_to_history(pos, m)) // Only non capture moves are considered
1482 update_history(pos, m, depth, movesSearched, moveCount);
1483 update_killers(m, ss[ply]);
1485 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m);
1488 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1494 // qsearch() is the quiescence search function, which is called by the main
1495 // search function when the remaining depth is zero (or, to be more precise,
1496 // less than OnePly).
1498 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta,
1499 Depth depth, int ply, int threadID) {
1501 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1502 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1504 assert(ply >= 0 && ply < PLY_MAX);
1505 assert(threadID >= 0 && threadID < ActiveThreads);
1507 // Initialize, and make an early exit in case of an aborted search,
1508 // an instant draw, maximum ply reached, etc.
1509 init_node(pos, ss, ply, threadID);
1511 // After init_node() that calls poll()
1512 if (AbortSearch || thread_should_stop(threadID))
1518 // Transposition table lookup, only when not in PV
1519 TTEntry* tte = NULL;
1520 bool pvNode = (beta - alpha != 1);
1523 tte = TT.retrieve(pos.get_key());
1524 if (tte && ok_to_use_TT(tte, depth, beta, ply))
1526 assert(tte->type() != VALUE_TYPE_EVAL);
1528 return value_from_tt(tte->value(), ply);
1531 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1533 // Evaluate the position statically
1536 bool isCheck = pos.is_check();
1537 ei.futilityMargin = Value(0); // Manually initialize futilityMargin
1540 staticValue = -VALUE_INFINITE;
1542 else if (tte && tte->type() == VALUE_TYPE_EVAL)
1544 // Use the cached evaluation score if possible
1545 assert(ei.futilityMargin == Value(0));
1547 staticValue = tte->value();
1550 staticValue = evaluate(pos, ei, threadID);
1552 if (ply == PLY_MAX - 1)
1553 return evaluate(pos, ei, threadID);
1555 // Initialize "stand pat score", and return it immediately if it is
1557 Value bestValue = staticValue;
1559 if (bestValue >= beta)
1561 // Store the score to avoid a future costly evaluation() call
1562 if (!isCheck && !tte && ei.futilityMargin == 0)
1563 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EVAL, Depth(-127*OnePly), MOVE_NONE);
1568 if (bestValue > alpha)
1571 // Initialize a MovePicker object for the current position, and prepare
1572 // to search the moves. Because the depth is <= 0 here, only captures,
1573 // queen promotions and checks (only if depth == 0) will be generated.
1574 MovePicker mp = MovePicker(pos, ttMove, depth, H);
1577 Bitboard dcCandidates = mp.discovered_check_candidates();
1578 Color us = pos.side_to_move();
1579 bool enoughMaterial = pos.non_pawn_material(us) > RookValueMidgame;
1581 // Loop through the moves until no moves remain or a beta cutoff
1583 while ( alpha < beta
1584 && (move = mp.get_next_move()) != MOVE_NONE)
1586 assert(move_is_ok(move));
1589 ss[ply].currentMove = move;
1595 && !move_is_promotion(move)
1596 && !pos.move_is_check(move, dcCandidates)
1597 && !pos.move_is_passed_pawn_push(move))
1599 Value futilityValue = staticValue
1600 + Max(pos.midgame_value_of_piece_on(move_to(move)),
1601 pos.endgame_value_of_piece_on(move_to(move)))
1602 + (move_is_ep(move) ? PawnValueEndgame : Value(0))
1604 + ei.futilityMargin;
1606 if (futilityValue < alpha)
1608 if (futilityValue > bestValue)
1609 bestValue = futilityValue;
1614 // Don't search captures and checks with negative SEE values
1616 && !move_is_promotion(move)
1617 && pos.see_sign(move) < 0)
1620 // Make and search the move.
1622 pos.do_move(move, st, dcCandidates);
1623 Value value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID);
1624 pos.undo_move(move);
1626 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1629 if (value > bestValue)
1640 // All legal moves have been searched. A special case: If we're in check
1641 // and no legal moves were found, it is checkmate.
1642 if (pos.is_check() && moveCount == 0) // Mate!
1643 return value_mated_in(ply);
1645 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1647 // Update transposition table
1648 Move m = ss[ply].pv[ply];
1651 Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
1652 if (bestValue < beta)
1653 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, d, MOVE_NONE);
1655 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, m);
1658 // Update killers only for good check moves
1659 if (alpha >= beta && ok_to_history(pos, m)) // Only non capture moves are considered
1660 update_killers(m, ss[ply]);
1666 // sp_search() is used to search from a split point. This function is called
1667 // by each thread working at the split point. It is similar to the normal
1668 // search() function, but simpler. Because we have already probed the hash
1669 // table, done a null move search, and searched the first move before
1670 // splitting, we don't have to repeat all this work in sp_search(). We
1671 // also don't need to store anything to the hash table here: This is taken
1672 // care of after we return from the split point.
1674 void sp_search(SplitPoint* sp, int threadID) {
1676 assert(threadID >= 0 && threadID < ActiveThreads);
1677 assert(ActiveThreads > 1);
1679 Position pos = Position(sp->pos);
1680 SearchStack* ss = sp->sstack[threadID];
1683 bool isCheck = pos.is_check();
1684 bool useFutilityPruning = sp->depth < SelectiveDepth
1687 while ( sp->bestValue < sp->beta
1688 && !thread_should_stop(threadID)
1689 && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE)
1691 assert(move_is_ok(move));
1693 bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates);
1694 bool moveIsCapture = pos.move_is_capture(move);
1696 lock_grab(&(sp->lock));
1697 int moveCount = ++sp->moves;
1698 lock_release(&(sp->lock));
1700 ss[sp->ply].currentMove = move;
1702 // Decide the new search depth.
1704 Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, false, false, &dangerous);
1705 Depth newDepth = sp->depth - OnePly + ext;
1708 if ( useFutilityPruning
1711 && !move_is_promotion(move)
1712 && moveCount >= 2 + int(sp->depth)
1713 && ok_to_prune(pos, move, ss[sp->ply].threatMove, sp->depth))
1716 // Make and search the move.
1718 pos.do_move(move, st, sp->dcCandidates);
1720 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1721 // if the move fails high will be re-searched at full depth.
1723 && moveCount >= LMRNonPVMoves
1725 && !move_is_promotion(move)
1726 && !move_is_castle(move)
1727 && !move_is_killer(move, ss[sp->ply]))
1729 ss[sp->ply].reduction = OnePly;
1730 value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, true, threadID);
1733 value = sp->beta; // Just to trigger next condition
1735 if (value >= sp->beta) // Go with full depth non-pv search
1737 ss[sp->ply].reduction = Depth(0);
1738 value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID);
1740 pos.undo_move(move);
1742 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1744 if (thread_should_stop(threadID))
1748 lock_grab(&(sp->lock));
1749 if (value > sp->bestValue && !thread_should_stop(threadID))
1751 sp->bestValue = value;
1752 if (sp->bestValue >= sp->beta)
1754 sp_update_pv(sp->parentSstack, ss, sp->ply);
1755 for (int i = 0; i < ActiveThreads; i++)
1756 if (i != threadID && (i == sp->master || sp->slaves[i]))
1757 Threads[i].stop = true;
1759 sp->finished = true;
1762 lock_release(&(sp->lock));
1765 lock_grab(&(sp->lock));
1767 // If this is the master thread and we have been asked to stop because of
1768 // a beta cutoff higher up in the tree, stop all slave threads.
1769 if (sp->master == threadID && thread_should_stop(threadID))
1770 for (int i = 0; i < ActiveThreads; i++)
1772 Threads[i].stop = true;
1775 sp->slaves[threadID] = 0;
1777 lock_release(&(sp->lock));
1781 // sp_search_pv() is used to search from a PV split point. This function
1782 // is called by each thread working at the split point. It is similar to
1783 // the normal search_pv() function, but simpler. Because we have already
1784 // probed the hash table and searched the first move before splitting, we
1785 // don't have to repeat all this work in sp_search_pv(). We also don't
1786 // need to store anything to the hash table here: This is taken care of
1787 // after we return from the split point.
1789 void sp_search_pv(SplitPoint* sp, int threadID) {
1791 assert(threadID >= 0 && threadID < ActiveThreads);
1792 assert(ActiveThreads > 1);
1794 Position pos = Position(sp->pos);
1795 SearchStack* ss = sp->sstack[threadID];
1799 while ( sp->alpha < sp->beta
1800 && !thread_should_stop(threadID)
1801 && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE)
1803 bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates);
1804 bool moveIsCapture = pos.move_is_capture(move);
1806 assert(move_is_ok(move));
1808 lock_grab(&(sp->lock));
1809 int moveCount = ++sp->moves;
1810 lock_release(&(sp->lock));
1812 ss[sp->ply].currentMove = move;
1814 // Decide the new search depth.
1816 Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, false, false, &dangerous);
1817 Depth newDepth = sp->depth - OnePly + ext;
1819 // Make and search the move.
1821 pos.do_move(move, st, sp->dcCandidates);
1823 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1824 // if the move fails high will be re-searched at full depth.
1826 && moveCount >= LMRPVMoves
1828 && !move_is_promotion(move)
1829 && !move_is_castle(move)
1830 && !move_is_killer(move, ss[sp->ply]))
1832 ss[sp->ply].reduction = OnePly;
1833 value = -search(pos, ss, -sp->alpha, newDepth - OnePly, sp->ply+1, true, threadID);
1836 value = sp->alpha + 1; // Just to trigger next condition
1838 if (value > sp->alpha) // Go with full depth non-pv search
1840 ss[sp->ply].reduction = Depth(0);
1841 value = -search(pos, ss, -sp->alpha, newDepth, sp->ply+1, true, threadID);
1843 if (value > sp->alpha && value < sp->beta)
1845 // When the search fails high at ply 1 while searching the first
1846 // move at the root, set the flag failHighPly1. This is used for
1847 // time managment: We don't want to stop the search early in
1848 // such cases, because resolving the fail high at ply 1 could
1849 // result in a big drop in score at the root.
1850 if (sp->ply == 1 && RootMoveNumber == 1)
1851 Threads[threadID].failHighPly1 = true;
1853 value = -search_pv(pos, ss, -sp->beta, -sp->alpha, newDepth, sp->ply+1, threadID);
1854 Threads[threadID].failHighPly1 = false;
1857 pos.undo_move(move);
1859 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1861 if (thread_should_stop(threadID))
1865 lock_grab(&(sp->lock));
1866 if (value > sp->bestValue && !thread_should_stop(threadID))
1868 sp->bestValue = value;
1869 if (value > sp->alpha)
1872 sp_update_pv(sp->parentSstack, ss, sp->ply);
1873 if (value == value_mate_in(sp->ply + 1))
1874 ss[sp->ply].mateKiller = move;
1876 if (value >= sp->beta)
1878 for (int i = 0; i < ActiveThreads; i++)
1879 if (i != threadID && (i == sp->master || sp->slaves[i]))
1880 Threads[i].stop = true;
1882 sp->finished = true;
1885 // If we are at ply 1, and we are searching the first root move at
1886 // ply 0, set the 'Problem' variable if the score has dropped a lot
1887 // (from the computer's point of view) since the previous iteration.
1890 && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
1893 lock_release(&(sp->lock));
1896 lock_grab(&(sp->lock));
1898 // If this is the master thread and we have been asked to stop because of
1899 // a beta cutoff higher up in the tree, stop all slave threads.
1900 if (sp->master == threadID && thread_should_stop(threadID))
1901 for (int i = 0; i < ActiveThreads; i++)
1903 Threads[i].stop = true;
1906 sp->slaves[threadID] = 0;
1908 lock_release(&(sp->lock));
1911 /// The BetaCounterType class
1913 BetaCounterType::BetaCounterType() { clear(); }
1915 void BetaCounterType::clear() {
1917 for (int i = 0; i < THREAD_MAX; i++)
1918 Threads[i].betaCutOffs[WHITE] = Threads[i].betaCutOffs[BLACK] = 0ULL;
1921 void BetaCounterType::add(Color us, Depth d, int threadID) {
1923 // Weighted count based on depth
1924 Threads[threadID].betaCutOffs[us] += unsigned(d);
1927 void BetaCounterType::read(Color us, int64_t& our, int64_t& their) {
1930 for (int i = 0; i < THREAD_MAX; i++)
1932 our += Threads[i].betaCutOffs[us];
1933 their += Threads[i].betaCutOffs[opposite_color(us)];
1938 /// The RootMove class
1942 RootMove::RootMove() {
1943 nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL;
1946 // RootMove::operator<() is the comparison function used when
1947 // sorting the moves. A move m1 is considered to be better
1948 // than a move m2 if it has a higher score, or if the moves
1949 // have equal score but m1 has the higher node count.
1951 bool RootMove::operator<(const RootMove& m) {
1953 if (score != m.score)
1954 return (score < m.score);
1956 return theirBeta <= m.theirBeta;
1959 /// The RootMoveList class
1963 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
1965 MoveStack mlist[MaxRootMoves];
1966 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
1968 // Generate all legal moves
1969 int lm_count = generate_legal_moves(pos, mlist);
1971 // Add each move to the moves[] array
1972 for (int i = 0; i < lm_count; i++)
1974 bool includeMove = includeAllMoves;
1976 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
1977 includeMove = (searchMoves[k] == mlist[i].move);
1982 // Find a quick score for the move
1984 SearchStack ss[PLY_MAX_PLUS_2];
1986 moves[count].move = mlist[i].move;
1987 pos.do_move(moves[count].move, st);
1988 moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0);
1989 pos.undo_move(moves[count].move);
1990 moves[count].pv[0] = moves[count].move;
1991 moves[count].pv[1] = MOVE_NONE; // FIXME
1998 // Simple accessor methods for the RootMoveList class
2000 inline Move RootMoveList::get_move(int moveNum) const {
2001 return moves[moveNum].move;
2004 inline Value RootMoveList::get_move_score(int moveNum) const {
2005 return moves[moveNum].score;
2008 inline void RootMoveList::set_move_score(int moveNum, Value score) {
2009 moves[moveNum].score = score;
2012 inline void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
2013 moves[moveNum].nodes = nodes;
2014 moves[moveNum].cumulativeNodes += nodes;
2017 inline void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
2018 moves[moveNum].ourBeta = our;
2019 moves[moveNum].theirBeta = their;
2022 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
2024 for(j = 0; pv[j] != MOVE_NONE; j++)
2025 moves[moveNum].pv[j] = pv[j];
2026 moves[moveNum].pv[j] = MOVE_NONE;
2029 inline Move RootMoveList::get_move_pv(int moveNum, int i) const {
2030 return moves[moveNum].pv[i];
2033 inline int64_t RootMoveList::get_move_cumulative_nodes(int moveNum) const {
2034 return moves[moveNum].cumulativeNodes;
2037 inline int RootMoveList::move_count() const {
2042 // RootMoveList::scan_for_easy_move() is called at the end of the first
2043 // iteration, and is used to detect an "easy move", i.e. a move which appears
2044 // to be much bester than all the rest. If an easy move is found, the move
2045 // is returned, otherwise the function returns MOVE_NONE. It is very
2046 // important that this function is called at the right moment: The code
2047 // assumes that the first iteration has been completed and the moves have
2048 // been sorted. This is done in RootMoveList c'tor.
2050 Move RootMoveList::scan_for_easy_move() const {
2057 // moves are sorted so just consider the best and the second one
2058 if (get_move_score(0) > get_move_score(1) + EasyMoveMargin)
2064 // RootMoveList::sort() sorts the root move list at the beginning of a new
2067 inline void RootMoveList::sort() {
2069 sort_multipv(count - 1); // all items
2073 // RootMoveList::sort_multipv() sorts the first few moves in the root move
2074 // list by their scores and depths. It is used to order the different PVs
2075 // correctly in MultiPV mode.
2077 void RootMoveList::sort_multipv(int n) {
2079 for (int i = 1; i <= n; i++)
2081 RootMove rm = moves[i];
2083 for (j = i; j > 0 && moves[j-1] < rm; j--)
2084 moves[j] = moves[j-1];
2090 // init_node() is called at the beginning of all the search functions
2091 // (search(), search_pv(), qsearch(), and so on) and initializes the search
2092 // stack object corresponding to the current node. Once every
2093 // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
2094 // for user input and checks whether it is time to stop the search.
2096 void init_node(const Position& pos, SearchStack ss[], int ply, int threadID) {
2098 assert(ply >= 0 && ply < PLY_MAX);
2099 assert(threadID >= 0 && threadID < ActiveThreads);
2101 if (Slowdown && Iteration >= 3)
2104 Threads[threadID].nodes++;
2109 if (NodesSincePoll >= NodesBetweenPolls)
2116 ss[ply+2].initKillers();
2118 if (Threads[threadID].printCurrentLine)
2119 print_current_line(ss, ply, threadID);
2123 // update_pv() is called whenever a search returns a value > alpha. It
2124 // updates the PV in the SearchStack object corresponding to the current
2127 void update_pv(SearchStack ss[], int ply) {
2128 assert(ply >= 0 && ply < PLY_MAX);
2130 ss[ply].pv[ply] = ss[ply].currentMove;
2132 for(p = ply + 1; ss[ply+1].pv[p] != MOVE_NONE; p++)
2133 ss[ply].pv[p] = ss[ply+1].pv[p];
2134 ss[ply].pv[p] = MOVE_NONE;
2138 // sp_update_pv() is a variant of update_pv for use at split points. The
2139 // difference between the two functions is that sp_update_pv also updates
2140 // the PV at the parent node.
2142 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply) {
2143 assert(ply >= 0 && ply < PLY_MAX);
2145 ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
2147 for(p = ply + 1; ss[ply+1].pv[p] != MOVE_NONE; p++)
2148 ss[ply].pv[p] = pss[ply].pv[p] = ss[ply+1].pv[p];
2149 ss[ply].pv[p] = pss[ply].pv[p] = MOVE_NONE;
2153 // connected_moves() tests whether two moves are 'connected' in the sense
2154 // that the first move somehow made the second move possible (for instance
2155 // if the moving piece is the same in both moves). The first move is
2156 // assumed to be the move that was made to reach the current position, while
2157 // the second move is assumed to be a move from the current position.
2159 bool connected_moves(const Position& pos, Move m1, Move m2) {
2160 Square f1, t1, f2, t2;
2162 assert(move_is_ok(m1));
2163 assert(move_is_ok(m2));
2165 if (m2 == MOVE_NONE)
2168 // Case 1: The moving piece is the same in both moves
2174 // Case 2: The destination square for m2 was vacated by m1
2180 // Case 3: Moving through the vacated square
2181 if ( piece_is_slider(pos.piece_on(f2))
2182 && bit_is_set(squares_between(f2, t2), f1))
2185 // Case 4: The destination square for m2 is attacked by the moving piece in m1
2186 if (pos.piece_attacks_square(pos.piece_on(t1), t1, t2))
2189 // Case 5: Discovered check, checking piece is the piece moved in m1
2190 if ( piece_is_slider(pos.piece_on(t1))
2191 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
2192 && !bit_is_set(squares_between(t2, pos.king_square(pos.side_to_move())), t2))
2194 Bitboard occ = pos.occupied_squares();
2195 Color us = pos.side_to_move();
2196 Square ksq = pos.king_square(us);
2197 clear_bit(&occ, f2);
2198 if (pos.type_of_piece_on(t1) == BISHOP)
2200 if (bit_is_set(bishop_attacks_bb(ksq, occ), t1))
2203 else if (pos.type_of_piece_on(t1) == ROOK)
2205 if (bit_is_set(rook_attacks_bb(ksq, occ), t1))
2210 assert(pos.type_of_piece_on(t1) == QUEEN);
2211 if (bit_is_set(queen_attacks_bb(ksq, occ), t1))
2219 // value_is_mate() checks if the given value is a mate one
2220 // eventually compensated for the ply.
2222 bool value_is_mate(Value value) {
2224 assert(abs(value) <= VALUE_INFINITE);
2226 return value <= value_mated_in(PLY_MAX)
2227 || value >= value_mate_in(PLY_MAX);
2231 // move_is_killer() checks if the given move is among the
2232 // killer moves of that ply.
2234 bool move_is_killer(Move m, const SearchStack& ss) {
2236 const Move* k = ss.killers;
2237 for (int i = 0; i < KILLER_MAX; i++, k++)
2245 // extension() decides whether a move should be searched with normal depth,
2246 // or with extended depth. Certain classes of moves (checking moves, in
2247 // particular) are searched with bigger depth than ordinary moves and in
2248 // any case are marked as 'dangerous'. Note that also if a move is not
2249 // extended, as example because the corresponding UCI option is set to zero,
2250 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
2252 Depth extension(const Position& pos, Move m, bool pvNode, bool capture, bool check,
2253 bool singleReply, bool mateThreat, bool* dangerous) {
2255 assert(m != MOVE_NONE);
2257 Depth result = Depth(0);
2258 *dangerous = check | singleReply | mateThreat;
2263 result += CheckExtension[pvNode];
2266 result += SingleReplyExtension[pvNode];
2269 result += MateThreatExtension[pvNode];
2272 if (pos.type_of_piece_on(move_from(m)) == PAWN)
2274 if (pos.move_is_pawn_push_to_7th(m))
2276 result += PawnPushTo7thExtension[pvNode];
2279 if (pos.move_is_passed_pawn_push(m))
2281 result += PassedPawnExtension[pvNode];
2287 && pos.type_of_piece_on(move_to(m)) != PAWN
2288 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
2289 - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))
2290 && !move_is_promotion(m)
2293 result += PawnEndgameExtension[pvNode];
2299 && pos.type_of_piece_on(move_to(m)) != PAWN
2300 && pos.see_sign(m) >= 0)
2306 return Min(result, OnePly);
2310 // ok_to_do_nullmove() looks at the current position and decides whether
2311 // doing a 'null move' should be allowed. In order to avoid zugzwang
2312 // problems, null moves are not allowed when the side to move has very
2313 // little material left. Currently, the test is a bit too simple: Null
2314 // moves are avoided only when the side to move has only pawns left. It's
2315 // probably a good idea to avoid null moves in at least some more
2316 // complicated endgames, e.g. KQ vs KR. FIXME
2318 bool ok_to_do_nullmove(const Position& pos) {
2320 return pos.non_pawn_material(pos.side_to_move()) != Value(0);
2324 // ok_to_prune() tests whether it is safe to forward prune a move. Only
2325 // non-tactical moves late in the move list close to the leaves are
2326 // candidates for pruning.
2328 bool ok_to_prune(const Position& pos, Move m, Move threat, Depth d) {
2330 assert(move_is_ok(m));
2331 assert(threat == MOVE_NONE || move_is_ok(threat));
2332 assert(!move_is_promotion(m));
2333 assert(!pos.move_is_check(m));
2334 assert(!pos.move_is_capture(m));
2335 assert(!pos.move_is_passed_pawn_push(m));
2336 assert(d >= OnePly);
2338 Square mfrom, mto, tfrom, tto;
2340 mfrom = move_from(m);
2342 tfrom = move_from(threat);
2343 tto = move_to(threat);
2345 // Case 1: Castling moves are never pruned
2346 if (move_is_castle(m))
2349 // Case 2: Don't prune moves which move the threatened piece
2350 if (!PruneEscapeMoves && threat != MOVE_NONE && mfrom == tto)
2353 // Case 3: If the threatened piece has value less than or equal to the
2354 // value of the threatening piece, don't prune move which defend it.
2355 if ( !PruneDefendingMoves
2356 && threat != MOVE_NONE
2357 && pos.move_is_capture(threat)
2358 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
2359 || pos.type_of_piece_on(tfrom) == KING)
2360 && pos.move_attacks_square(m, tto))
2363 // Case 4: Don't prune moves with good history
2364 if (!H.ok_to_prune(pos.piece_on(mfrom), mto, d))
2367 // Case 5: If the moving piece in the threatened move is a slider, don't
2368 // prune safe moves which block its ray.
2369 if ( !PruneBlockingMoves
2370 && threat != MOVE_NONE
2371 && piece_is_slider(pos.piece_on(tfrom))
2372 && bit_is_set(squares_between(tfrom, tto), mto)
2373 && pos.see_sign(m) >= 0)
2380 // ok_to_use_TT() returns true if a transposition table score
2381 // can be used at a given point in search.
2383 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
2385 Value v = value_from_tt(tte->value(), ply);
2387 return ( tte->depth() >= depth
2388 || v >= Max(value_mate_in(100), beta)
2389 || v < Min(value_mated_in(100), beta))
2391 && ( (is_lower_bound(tte->type()) && v >= beta)
2392 || (is_upper_bound(tte->type()) && v < beta));
2396 // ok_to_history() returns true if a move m can be stored
2397 // in history. Should be a non capturing move nor a promotion.
2399 bool ok_to_history(const Position& pos, Move m) {
2401 return !pos.move_is_capture(m) && !move_is_promotion(m);
2405 // update_history() registers a good move that produced a beta-cutoff
2406 // in history and marks as failures all the other moves of that ply.
2408 void update_history(const Position& pos, Move m, Depth depth,
2409 Move movesSearched[], int moveCount) {
2411 H.success(pos.piece_on(move_from(m)), move_to(m), depth);
2413 for (int i = 0; i < moveCount - 1; i++)
2415 assert(m != movesSearched[i]);
2416 if (ok_to_history(pos, movesSearched[i]))
2417 H.failure(pos.piece_on(move_from(movesSearched[i])), move_to(movesSearched[i]));
2422 // update_killers() add a good move that produced a beta-cutoff
2423 // among the killer moves of that ply.
2425 void update_killers(Move m, SearchStack& ss) {
2427 if (m == ss.killers[0])
2430 for (int i = KILLER_MAX - 1; i > 0; i--)
2431 ss.killers[i] = ss.killers[i - 1];
2437 // slowdown() simply wastes CPU cycles doing nothing useful. It's used
2438 // in strength handicap mode.
2440 void slowdown(const Position &pos) {
2443 for (i = 0; i < n; i++) {
2444 Square s = Square(i&63);
2445 if (count_1s(pos.attacks_to(s)) > 63)
2446 std::cout << "This can't happen, but I put this string here anyway, in order to prevent the compiler from optimizing away the useless computation." << std::endl;
2451 // fail_high_ply_1() checks if some thread is currently resolving a fail
2452 // high at ply 1 at the node below the first root node. This information
2453 // is used for time managment.
2455 bool fail_high_ply_1() {
2457 for(int i = 0; i < ActiveThreads; i++)
2458 if (Threads[i].failHighPly1)
2465 // current_search_time() returns the number of milliseconds which have passed
2466 // since the beginning of the current search.
2468 int current_search_time() {
2469 return get_system_time() - SearchStartTime;
2473 // nps() computes the current nodes/second count.
2476 int t = current_search_time();
2477 return (t > 0)? int((nodes_searched() * 1000) / t) : 0;
2481 // poll() performs two different functions: It polls for user input, and it
2482 // looks at the time consumed so far and decides if it's time to abort the
2487 static int lastInfoTime;
2488 int t = current_search_time();
2493 // We are line oriented, don't read single chars
2494 std::string command;
2495 if (!std::getline(std::cin, command))
2498 if (command == "quit")
2501 PonderSearch = false;
2505 else if (command == "stop")
2508 PonderSearch = false;
2510 else if (command == "ponderhit")
2513 // Print search information
2517 else if (lastInfoTime > t)
2518 // HACK: Must be a new search where we searched less than
2519 // NodesBetweenPolls nodes during the first second of search.
2522 else if (t - lastInfoTime >= 1000)
2529 if (dbg_show_hit_rate)
2530 dbg_print_hit_rate();
2532 std::cout << "info nodes " << nodes_searched() << " nps " << nps()
2533 << " time " << t << " hashfull " << TT.full() << std::endl;
2534 lock_release(&IOLock);
2535 if (ShowCurrentLine)
2536 Threads[0].printCurrentLine = true;
2538 // Should we stop the search?
2542 bool overTime = t > AbsoluteMaxSearchTime
2543 || (RootMoveNumber == 1 && t > MaxSearchTime + ExtraSearchTime && !FailLow) //FIXME: We are not checking any problem flags, BUG?
2544 || ( !FailHigh && !FailLow && !fail_high_ply_1() && !Problem
2545 && t > 6*(MaxSearchTime + ExtraSearchTime));
2547 if ( (Iteration >= 3 && (!InfiniteSearch && overTime))
2548 || (ExactMaxTime && t >= ExactMaxTime)
2549 || (Iteration >= 3 && MaxNodes && nodes_searched() >= MaxNodes))
2554 // ponderhit() is called when the program is pondering (i.e. thinking while
2555 // it's the opponent's turn to move) in order to let the engine know that
2556 // it correctly predicted the opponent's move.
2560 int t = current_search_time();
2561 PonderSearch = false;
2562 if (Iteration >= 3 &&
2563 (!InfiniteSearch && (StopOnPonderhit ||
2564 t > AbsoluteMaxSearchTime ||
2565 (RootMoveNumber == 1 &&
2566 t > MaxSearchTime + ExtraSearchTime && !FailLow) ||
2567 (!FailHigh && !FailLow && !fail_high_ply_1() && !Problem &&
2568 t > 6*(MaxSearchTime + ExtraSearchTime)))))
2573 // print_current_line() prints the current line of search for a given
2574 // thread. Called when the UCI option UCI_ShowCurrLine is 'true'.
2576 void print_current_line(SearchStack ss[], int ply, int threadID) {
2578 assert(ply >= 0 && ply < PLY_MAX);
2579 assert(threadID >= 0 && threadID < ActiveThreads);
2581 if (!Threads[threadID].idle)
2584 std::cout << "info currline " << (threadID + 1);
2585 for (int p = 0; p < ply; p++)
2586 std::cout << " " << ss[p].currentMove;
2588 std::cout << std::endl;
2589 lock_release(&IOLock);
2591 Threads[threadID].printCurrentLine = false;
2592 if (threadID + 1 < ActiveThreads)
2593 Threads[threadID + 1].printCurrentLine = true;
2597 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2598 // while the program is pondering. The point is to work around a wrinkle in
2599 // the UCI protocol: When pondering, the engine is not allowed to give a
2600 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2601 // We simply wait here until one of these commands is sent, and return,
2602 // after which the bestmove and pondermove will be printed (in id_loop()).
2604 void wait_for_stop_or_ponderhit() {
2606 std::string command;
2610 if (!std::getline(std::cin, command))
2613 if (command == "quit")
2618 else if (command == "ponderhit" || command == "stop")
2624 // idle_loop() is where the threads are parked when they have no work to do.
2625 // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint
2626 // object for which the current thread is the master.
2628 void idle_loop(int threadID, SplitPoint* waitSp) {
2629 assert(threadID >= 0 && threadID < THREAD_MAX);
2631 Threads[threadID].running = true;
2634 if(AllThreadsShouldExit && threadID != 0)
2637 // If we are not thinking, wait for a condition to be signaled instead
2638 // of wasting CPU time polling for work:
2639 while(threadID != 0 && (Idle || threadID >= ActiveThreads)) {
2640 #if !defined(_MSC_VER)
2641 pthread_mutex_lock(&WaitLock);
2642 if(Idle || threadID >= ActiveThreads)
2643 pthread_cond_wait(&WaitCond, &WaitLock);
2644 pthread_mutex_unlock(&WaitLock);
2646 WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2650 // If this thread has been assigned work, launch a search
2651 if(Threads[threadID].workIsWaiting) {
2652 Threads[threadID].workIsWaiting = false;
2653 if(Threads[threadID].splitPoint->pvNode)
2654 sp_search_pv(Threads[threadID].splitPoint, threadID);
2656 sp_search(Threads[threadID].splitPoint, threadID);
2657 Threads[threadID].idle = true;
2660 // If this thread is the master of a split point and all threads have
2661 // finished their work at this split point, return from the idle loop.
2662 if(waitSp != NULL && waitSp->cpus == 0)
2666 Threads[threadID].running = false;
2670 // init_split_point_stack() is called during program initialization, and
2671 // initializes all split point objects.
2673 void init_split_point_stack() {
2674 for(int i = 0; i < THREAD_MAX; i++)
2675 for(int j = 0; j < MaxActiveSplitPoints; j++) {
2676 SplitPointStack[i][j].parent = NULL;
2677 lock_init(&(SplitPointStack[i][j].lock), NULL);
2682 // destroy_split_point_stack() is called when the program exits, and
2683 // destroys all locks in the precomputed split point objects.
2685 void destroy_split_point_stack() {
2686 for(int i = 0; i < THREAD_MAX; i++)
2687 for(int j = 0; j < MaxActiveSplitPoints; j++)
2688 lock_destroy(&(SplitPointStack[i][j].lock));
2692 // thread_should_stop() checks whether the thread with a given threadID has
2693 // been asked to stop, directly or indirectly. This can happen if a beta
2694 // cutoff has occured in thre thread's currently active split point, or in
2695 // some ancestor of the current split point.
2697 bool thread_should_stop(int threadID) {
2698 assert(threadID >= 0 && threadID < ActiveThreads);
2702 if(Threads[threadID].stop)
2704 if(ActiveThreads <= 2)
2706 for(sp = Threads[threadID].splitPoint; sp != NULL; sp = sp->parent)
2708 Threads[threadID].stop = true;
2715 // thread_is_available() checks whether the thread with threadID "slave" is
2716 // available to help the thread with threadID "master" at a split point. An
2717 // obvious requirement is that "slave" must be idle. With more than two
2718 // threads, this is not by itself sufficient: If "slave" is the master of
2719 // some active split point, it is only available as a slave to the other
2720 // threads which are busy searching the split point at the top of "slave"'s
2721 // split point stack (the "helpful master concept" in YBWC terminology).
2723 bool thread_is_available(int slave, int master) {
2724 assert(slave >= 0 && slave < ActiveThreads);
2725 assert(master >= 0 && master < ActiveThreads);
2726 assert(ActiveThreads > 1);
2728 if(!Threads[slave].idle || slave == master)
2731 if(Threads[slave].activeSplitPoints == 0)
2732 // No active split points means that the thread is available as a slave
2733 // for any other thread.
2736 if(ActiveThreads == 2)
2739 // Apply the "helpful master" concept if possible.
2740 if(SplitPointStack[slave][Threads[slave].activeSplitPoints-1].slaves[master])
2747 // idle_thread_exists() tries to find an idle thread which is available as
2748 // a slave for the thread with threadID "master".
2750 bool idle_thread_exists(int master) {
2751 assert(master >= 0 && master < ActiveThreads);
2752 assert(ActiveThreads > 1);
2754 for(int i = 0; i < ActiveThreads; i++)
2755 if(thread_is_available(i, master))
2761 // split() does the actual work of distributing the work at a node between
2762 // several threads at PV nodes. If it does not succeed in splitting the
2763 // node (because no idle threads are available, or because we have no unused
2764 // split point objects), the function immediately returns false. If
2765 // splitting is possible, a SplitPoint object is initialized with all the
2766 // data that must be copied to the helper threads (the current position and
2767 // search stack, alpha, beta, the search depth, etc.), and we tell our
2768 // helper threads that they have been assigned work. This will cause them
2769 // to instantly leave their idle loops and call sp_search_pv(). When all
2770 // threads have returned from sp_search_pv (or, equivalently, when
2771 // splitPoint->cpus becomes 0), split() returns true.
2773 bool split(const Position& p, SearchStack* sstck, int ply,
2774 Value* alpha, Value* beta, Value* bestValue, Depth depth, int* moves,
2775 MovePicker* mp, Bitboard dcCandidates, int master, bool pvNode) {
2778 assert(sstck != NULL);
2779 assert(ply >= 0 && ply < PLY_MAX);
2780 assert(*bestValue >= -VALUE_INFINITE && *bestValue <= *alpha);
2781 assert(!pvNode || *alpha < *beta);
2782 assert(*beta <= VALUE_INFINITE);
2783 assert(depth > Depth(0));
2784 assert(master >= 0 && master < ActiveThreads);
2785 assert(ActiveThreads > 1);
2787 SplitPoint* splitPoint;
2792 // If no other thread is available to help us, or if we have too many
2793 // active split points, don't split.
2794 if(!idle_thread_exists(master) ||
2795 Threads[master].activeSplitPoints >= MaxActiveSplitPoints) {
2796 lock_release(&MPLock);
2800 // Pick the next available split point object from the split point stack
2801 splitPoint = SplitPointStack[master] + Threads[master].activeSplitPoints;
2802 Threads[master].activeSplitPoints++;
2804 // Initialize the split point object
2805 splitPoint->parent = Threads[master].splitPoint;
2806 splitPoint->finished = false;
2807 splitPoint->ply = ply;
2808 splitPoint->depth = depth;
2809 splitPoint->alpha = pvNode? *alpha : (*beta - 1);
2810 splitPoint->beta = *beta;
2811 splitPoint->pvNode = pvNode;
2812 splitPoint->dcCandidates = dcCandidates;
2813 splitPoint->bestValue = *bestValue;
2814 splitPoint->master = master;
2815 splitPoint->mp = mp;
2816 splitPoint->moves = *moves;
2817 splitPoint->cpus = 1;
2818 splitPoint->pos.copy(p);
2819 splitPoint->parentSstack = sstck;
2820 for(i = 0; i < ActiveThreads; i++)
2821 splitPoint->slaves[i] = 0;
2823 // Copy the current position and the search stack to the master thread
2824 memcpy(splitPoint->sstack[master], sstck, (ply+1)*sizeof(SearchStack));
2825 Threads[master].splitPoint = splitPoint;
2827 // Make copies of the current position and search stack for each thread
2828 for(i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint;
2830 if(thread_is_available(i, master)) {
2831 memcpy(splitPoint->sstack[i], sstck, (ply+1)*sizeof(SearchStack));
2832 Threads[i].splitPoint = splitPoint;
2833 splitPoint->slaves[i] = 1;
2837 // Tell the threads that they have work to do. This will make them leave
2839 for(i = 0; i < ActiveThreads; i++)
2840 if(i == master || splitPoint->slaves[i]) {
2841 Threads[i].workIsWaiting = true;
2842 Threads[i].idle = false;
2843 Threads[i].stop = false;
2846 lock_release(&MPLock);
2848 // Everything is set up. The master thread enters the idle loop, from
2849 // which it will instantly launch a search, because its workIsWaiting
2850 // slot is 'true'. We send the split point as a second parameter to the
2851 // idle loop, which means that the main thread will return from the idle
2852 // loop when all threads have finished their work at this split point
2853 // (i.e. when // splitPoint->cpus == 0).
2854 idle_loop(master, splitPoint);
2856 // We have returned from the idle loop, which means that all threads are
2857 // finished. Update alpha, beta and bestvalue, and return.
2859 if(pvNode) *alpha = splitPoint->alpha;
2860 *beta = splitPoint->beta;
2861 *bestValue = splitPoint->bestValue;
2862 Threads[master].stop = false;
2863 Threads[master].idle = false;
2864 Threads[master].activeSplitPoints--;
2865 Threads[master].splitPoint = splitPoint->parent;
2866 lock_release(&MPLock);
2872 // wake_sleeping_threads() wakes up all sleeping threads when it is time
2873 // to start a new search from the root.
2875 void wake_sleeping_threads() {
2876 if(ActiveThreads > 1) {
2877 for(int i = 1; i < ActiveThreads; i++) {
2878 Threads[i].idle = true;
2879 Threads[i].workIsWaiting = false;
2881 #if !defined(_MSC_VER)
2882 pthread_mutex_lock(&WaitLock);
2883 pthread_cond_broadcast(&WaitCond);
2884 pthread_mutex_unlock(&WaitLock);
2886 for(int i = 1; i < THREAD_MAX; i++)
2887 SetEvent(SitIdleEvent[i]);
2893 // init_thread() is the function which is called when a new thread is
2894 // launched. It simply calls the idle_loop() function with the supplied
2895 // threadID. There are two versions of this function; one for POSIX threads
2896 // and one for Windows threads.
2898 #if !defined(_MSC_VER)
2900 void *init_thread(void *threadID) {
2901 idle_loop(*(int *)threadID, NULL);
2907 DWORD WINAPI init_thread(LPVOID threadID) {
2908 idle_loop(*(int *)threadID, NULL);