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) };
194 /// Variables initialized by UCI options
196 // Adjustable playing strength
198 const int SlowdownArray[32] = {
199 19, 41, 70, 110, 160, 230, 320, 430, 570, 756, 1000, 1300, 1690, 2197,
200 2834, 3600, 4573, 5809, 7700, 9863, 12633, 16181, 20726, 26584, 34005,
201 43557, 55792, 71463, 91536, 117247, 150180, 192363
204 const int MaxStrength = 25;
206 // Minimum number of full depth (i.e. non-reduced) moves at PV and non-PV nodes
207 int LMRPVMoves, LMRNonPVMoves; // heavy SMP read access for the latter
209 // Depth limit for use of dynamic threat detection
210 Depth ThreatDepth; // heavy SMP read access
212 // Last seconds noise filtering (LSN)
213 const bool UseLSNFiltering = true;
214 const int LSNTime = 4000; // In milliseconds
215 const Value LSNValue = value_from_centipawns(200);
216 bool loseOnTime = false;
218 // Extensions. Array index 0 is used at non-PV nodes, index 1 at PV nodes.
219 // There is heavy SMP read access on these arrays
220 Depth CheckExtension[2], SingleReplyExtension[2], PawnPushTo7thExtension[2];
221 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
223 // Iteration counters
225 BetaCounterType BetaCounter; // has per-thread internal data
227 // Scores and number of times the best move changed for each iteration
228 IterationInfoType IterationInfo[PLY_MAX_PLUS_2];
229 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
234 // Time managment variables
236 int MaxNodes, MaxDepth;
237 int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
241 bool StopOnPonderhit;
242 bool AbortSearch; // heavy SMP read access
248 // Show current line?
249 bool ShowCurrentLine;
253 std::ofstream LogFile;
255 // MP related variables
256 int ActiveThreads = 1;
257 Depth MinimumSplitDepth;
258 int MaxThreadsPerSplitPoint;
259 Thread Threads[THREAD_MAX];
262 bool AllThreadsShouldExit = false;
263 const int MaxActiveSplitPoints = 8;
264 SplitPoint SplitPointStack[THREAD_MAX][MaxActiveSplitPoints];
267 #if !defined(_MSC_VER)
268 pthread_cond_t WaitCond;
269 pthread_mutex_t WaitLock;
271 HANDLE SitIdleEvent[THREAD_MAX];
274 // Node counters, used only by thread[0] but try to keep in different
275 // cache lines (64 bytes each) from the heavy SMP read accessed variables.
277 int NodesBetweenPolls = 30000;
285 Value id_loop(const Position& pos, Move searchMoves[]);
286 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta);
287 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
288 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID);
289 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
290 void sp_search(SplitPoint* sp, int threadID);
291 void sp_search_pv(SplitPoint* sp, int threadID);
292 void init_node(const Position& pos, SearchStack ss[], int ply, int threadID);
293 void update_pv(SearchStack ss[], int ply);
294 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply);
295 bool connected_moves(const Position& pos, Move m1, Move m2);
296 bool value_is_mate(Value value);
297 bool move_is_killer(Move m, const SearchStack& ss);
298 Depth extension(const Position& pos, Move m, bool pvNode, bool capture, bool check, bool singleReply, bool mateThreat, bool* dangerous);
299 bool ok_to_do_nullmove(const Position& pos);
300 bool ok_to_prune(const Position& pos, Move m, Move threat, Depth d);
301 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
302 bool ok_to_history(const Position& pos, Move m);
303 void update_history(const Position& pos, Move m, Depth depth, Move movesSearched[], int moveCount);
304 void update_killers(Move m, SearchStack& ss);
305 void slowdown(const Position& pos);
307 bool fail_high_ply_1();
308 int current_search_time();
312 void print_current_line(SearchStack ss[], int ply, int threadID);
313 void wait_for_stop_or_ponderhit();
315 void idle_loop(int threadID, SplitPoint* waitSp);
316 void init_split_point_stack();
317 void destroy_split_point_stack();
318 bool thread_should_stop(int threadID);
319 bool thread_is_available(int slave, int master);
320 bool idle_thread_exists(int master);
321 bool split(const Position& pos, SearchStack* ss, int ply,
322 Value *alpha, Value *beta, Value *bestValue, Depth depth, int *moves,
323 MovePicker *mp, Bitboard dcCandidates, int master, bool pvNode);
324 void wake_sleeping_threads();
326 #if !defined(_MSC_VER)
327 void *init_thread(void *threadID);
329 DWORD WINAPI init_thread(LPVOID threadID);
339 /// think() is the external interface to Stockfish's search, and is called when
340 /// the program receives the UCI 'go' command. It initializes various
341 /// search-related global variables, and calls root_search(). It returns false
342 /// when a quit command is received during the search.
344 bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
345 int time[], int increment[], int movesToGo, int maxDepth,
346 int maxNodes, int maxTime, Move searchMoves[]) {
348 // Look for a book move
349 if (!infinite && !ponder && get_option_value_bool("OwnBook"))
352 if (get_option_value_string("Book File") != OpeningBook.file_name())
353 OpeningBook.open("book.bin");
355 bookMove = OpeningBook.get_move(pos);
356 if (bookMove != MOVE_NONE)
358 std::cout << "bestmove " << bookMove << std::endl;
363 // Initialize global search variables
365 SearchStartTime = get_system_time();
366 for (int i = 0; i < THREAD_MAX; i++)
368 Threads[i].nodes = 0ULL;
369 Threads[i].failHighPly1 = false;
372 InfiniteSearch = infinite;
373 PonderSearch = ponder;
374 StopOnPonderhit = false;
380 ExactMaxTime = maxTime;
382 // Read UCI option values
383 TT.set_size(get_option_value_int("Hash"));
384 if (button_was_pressed("Clear Hash"))
387 loseOnTime = false; // reset at the beginning of a new game
390 bool PonderingEnabled = get_option_value_bool("Ponder");
391 MultiPV = get_option_value_int("MultiPV");
393 CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)"));
394 CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)"));
396 SingleReplyExtension[1] = Depth(get_option_value_int("Single Reply Extension (PV nodes)"));
397 SingleReplyExtension[0] = Depth(get_option_value_int("Single Reply Extension (non-PV nodes)"));
399 PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)"));
400 PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
402 PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
403 PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
405 PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
406 PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)"));
408 MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
409 MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
411 LMRPVMoves = get_option_value_int("Full Depth Moves (PV nodes)") + 1;
412 LMRNonPVMoves = get_option_value_int("Full Depth Moves (non-PV nodes)") + 1;
413 ThreatDepth = get_option_value_int("Threat Depth") * OnePly;
415 Chess960 = get_option_value_bool("UCI_Chess960");
416 ShowCurrentLine = get_option_value_bool("UCI_ShowCurrLine");
417 UseLogFile = get_option_value_bool("Use Search Log");
419 LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app);
421 MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly;
422 MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point");
424 read_weights(pos.side_to_move());
426 // Set the number of active threads. If UCI_LimitStrength is enabled, never
427 // use more than one thread.
428 int newActiveThreads =
429 get_option_value_bool("UCI_LimitStrength")? 1 : get_option_value_int("Threads");
430 if (newActiveThreads != ActiveThreads)
432 ActiveThreads = newActiveThreads;
433 init_eval(ActiveThreads);
436 // Wake up sleeping threads
437 wake_sleeping_threads();
439 for (int i = 1; i < ActiveThreads; i++)
440 assert(thread_is_available(i, 0));
442 // Set playing strength
443 if (get_option_value_bool("UCI_LimitStrength"))
445 Strength = (get_option_value_int("UCI_Elo") - 2100) / 25;
447 (Strength == MaxStrength)? 0 : SlowdownArray[Max(0, 31-Strength)];
451 Strength = MaxStrength;
456 int myTime = time[side_to_move];
457 int myIncrement = increment[side_to_move];
459 if (!movesToGo) // Sudden death time control
463 MaxSearchTime = myTime / 30 + myIncrement;
464 AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
465 } else { // Blitz game without increment
466 MaxSearchTime = myTime / 30;
467 AbsoluteMaxSearchTime = myTime / 8;
470 else // (x moves) / (y minutes)
474 MaxSearchTime = myTime / 2;
475 AbsoluteMaxSearchTime = Min(myTime / 2, myTime - 500);
477 MaxSearchTime = myTime / Min(movesToGo, 20);
478 AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
482 if (PonderingEnabled)
484 MaxSearchTime += MaxSearchTime / 4;
485 MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime);
488 // Fixed depth or fixed number of nodes?
491 InfiniteSearch = true; // HACK
496 NodesBetweenPolls = Min(MaxNodes, 30000);
497 InfiniteSearch = true; // HACK
500 if (Slowdown > 50000) NodesBetweenPolls = 30;
501 else if (Slowdown > 10000) NodesBetweenPolls = 100;
502 else if (Slowdown > 1000) NodesBetweenPolls = 500;
503 else if (Slowdown > 100) NodesBetweenPolls = 3000;
504 else NodesBetweenPolls = 15000;
507 NodesBetweenPolls = 30000;
509 // Write information to search log file
511 LogFile << "Searching: " << pos.to_fen() << std::endl
512 << "infinite: " << infinite
513 << " ponder: " << ponder
514 << " time: " << myTime
515 << " increment: " << myIncrement
516 << " moves to go: " << movesToGo << std::endl;
519 // We're ready to start thinking. Call the iterative deepening loop function
521 // FIXME we really need to cleanup all this LSN ugliness
524 Value v = id_loop(pos, searchMoves);
525 loseOnTime = ( UseLSNFiltering
532 loseOnTime = false; // reset for next match
533 while (SearchStartTime + myTime + 1000 > get_system_time())
535 id_loop(pos, searchMoves); // to fail gracefully
546 /// init_threads() is called during startup. It launches all helper threads,
547 /// and initializes the split point stack and the global locks and condition
550 void init_threads() {
554 #if !defined(_MSC_VER)
555 pthread_t pthread[1];
558 for (i = 0; i < THREAD_MAX; i++)
559 Threads[i].activeSplitPoints = 0;
561 // Initialize global locks
562 lock_init(&MPLock, NULL);
563 lock_init(&IOLock, NULL);
565 init_split_point_stack();
567 #if !defined(_MSC_VER)
568 pthread_mutex_init(&WaitLock, NULL);
569 pthread_cond_init(&WaitCond, NULL);
571 for (i = 0; i < THREAD_MAX; i++)
572 SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0);
575 // All threads except the main thread should be initialized to idle state
576 for (i = 1; i < THREAD_MAX; i++)
578 Threads[i].stop = false;
579 Threads[i].workIsWaiting = false;
580 Threads[i].idle = true;
581 Threads[i].running = false;
584 // Launch the helper threads
585 for(i = 1; i < THREAD_MAX; i++)
587 #if !defined(_MSC_VER)
588 pthread_create(pthread, NULL, init_thread, (void*)(&i));
591 CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID);
594 // Wait until the thread has finished launching
595 while (!Threads[i].running);
600 /// stop_threads() is called when the program exits. It makes all the
601 /// helper threads exit cleanly.
603 void stop_threads() {
605 ActiveThreads = THREAD_MAX; // HACK
606 Idle = false; // HACK
607 wake_sleeping_threads();
608 AllThreadsShouldExit = true;
609 for (int i = 1; i < THREAD_MAX; i++)
611 Threads[i].stop = true;
612 while(Threads[i].running);
614 destroy_split_point_stack();
618 /// nodes_searched() returns the total number of nodes searched so far in
619 /// the current search.
621 int64_t nodes_searched() {
623 int64_t result = 0ULL;
624 for (int i = 0; i < ActiveThreads; i++)
625 result += Threads[i].nodes;
630 // SearchStack::init() initializes a search stack. Used at the beginning of a
631 // new search from the root.
632 void SearchStack::init(int ply) {
634 pv[ply] = pv[ply + 1] = MOVE_NONE;
635 currentMove = threatMove = MOVE_NONE;
636 reduction = Depth(0);
639 void SearchStack::initKillers() {
641 mateKiller = MOVE_NONE;
642 for (int i = 0; i < KILLER_MAX; i++)
643 killers[i] = MOVE_NONE;
648 // id_loop() is the main iterative deepening loop. It calls root_search
649 // repeatedly with increasing depth until the allocated thinking time has
650 // been consumed, the user stops the search, or the maximum search depth is
653 Value id_loop(const Position& pos, Move searchMoves[]) {
656 SearchStack ss[PLY_MAX_PLUS_2];
658 // searchMoves are verified, copied, scored and sorted
659 RootMoveList rml(p, searchMoves);
664 for (int i = 0; i < 3; i++)
669 IterationInfo[1] = IterationInfoType(rml.get_move_score(0), rml.get_move_score(0));
672 Move EasyMove = rml.scan_for_easy_move();
674 // Iterative deepening loop
675 while (Iteration < PLY_MAX)
677 // Initialize iteration
680 BestMoveChangesByIteration[Iteration] = 0;
684 std::cout << "info depth " << Iteration << std::endl;
686 // Calculate dynamic search window based on previous iterations
689 if (MultiPV == 1 && Iteration >= 6 && abs(IterationInfo[Iteration - 1].value) < VALUE_KNOWN_WIN)
691 int prevDelta1 = IterationInfo[Iteration - 1].speculatedValue - IterationInfo[Iteration - 2].speculatedValue;
692 int prevDelta2 = IterationInfo[Iteration - 2].speculatedValue - IterationInfo[Iteration - 3].speculatedValue;
694 int delta = Max(2 * abs(prevDelta1) + abs(prevDelta2), ProblemMargin);
696 alpha = Max(IterationInfo[Iteration - 1].value - delta, -VALUE_INFINITE);
697 beta = Min(IterationInfo[Iteration - 1].value + delta, VALUE_INFINITE);
701 alpha = - VALUE_INFINITE;
702 beta = VALUE_INFINITE;
705 // Search to the current depth
706 Value value = root_search(p, ss, rml, alpha, beta);
708 // Write PV to transposition table, in case the relevant entries have
709 // been overwritten during the search.
710 TT.insert_pv(p, ss[0].pv);
713 break; // Value cannot be trusted. Break out immediately!
715 //Save info about search result
716 Value speculatedValue;
719 Value delta = value - IterationInfo[Iteration - 1].value;
726 speculatedValue = value + delta;
727 BestMoveChangesByIteration[Iteration] += 2; // Allocate more time
729 else if (value <= alpha)
731 assert(value == alpha);
735 speculatedValue = value + delta;
736 BestMoveChangesByIteration[Iteration] += 3; // Allocate more time
738 speculatedValue = value;
740 speculatedValue = Min(Max(speculatedValue, -VALUE_INFINITE), VALUE_INFINITE);
741 IterationInfo[Iteration] = IterationInfoType(value, speculatedValue);
743 // Erase the easy move if it differs from the new best move
744 if (ss[0].pv[0] != EasyMove)
745 EasyMove = MOVE_NONE;
752 bool stopSearch = false;
754 // Stop search early if there is only a single legal move
755 if (Iteration >= 6 && rml.move_count() == 1)
758 // Stop search early when the last two iterations returned a mate score
760 && abs(IterationInfo[Iteration].value) >= abs(VALUE_MATE) - 100
761 && abs(IterationInfo[Iteration-1].value) >= abs(VALUE_MATE) - 100)
764 // Stop search early if one move seems to be much better than the rest
765 int64_t nodes = nodes_searched();
769 && EasyMove == ss[0].pv[0]
770 && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
771 && current_search_time() > MaxSearchTime / 16)
772 ||( rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100
773 && current_search_time() > MaxSearchTime / 32)))
776 // Add some extra time if the best move has changed during the last two iterations
777 if (Iteration > 5 && Iteration <= 50)
778 ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2)
779 + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3);
781 // Stop search if most of MaxSearchTime is consumed at the end of the
782 // iteration. We probably don't have enough time to search the first
783 // move at the next iteration anyway.
784 if (current_search_time() > ((MaxSearchTime + ExtraSearchTime)*80) / 128)
789 //FIXME: Implement fail-low emergency measures
793 StopOnPonderhit = true;
797 if (MaxDepth && Iteration >= MaxDepth)
803 // If we are pondering, we shouldn't print the best move before we
806 wait_for_stop_or_ponderhit();
808 // Print final search statistics
809 std::cout << "info nodes " << nodes_searched()
811 << " time " << current_search_time()
812 << " hashfull " << TT.full() << std::endl;
814 // Print the best move and the ponder move to the standard output
815 if (ss[0].pv[0] == MOVE_NONE)
817 ss[0].pv[0] = rml.get_move(0);
818 ss[0].pv[1] = MOVE_NONE;
820 std::cout << "bestmove " << ss[0].pv[0];
821 if (ss[0].pv[1] != MOVE_NONE)
822 std::cout << " ponder " << ss[0].pv[1];
824 std::cout << std::endl;
829 dbg_print_mean(LogFile);
831 if (dbg_show_hit_rate)
832 dbg_print_hit_rate(LogFile);
835 LogFile << "Nodes: " << nodes_searched() << std::endl
836 << "Nodes/second: " << nps() << std::endl
837 << "Best move: " << move_to_san(p, ss[0].pv[0]) << std::endl;
839 p.do_move(ss[0].pv[0], st);
840 LogFile << "Ponder move: " << move_to_san(p, ss[0].pv[1])
841 << std::endl << std::endl;
843 return rml.get_move_score(0);
847 // root_search() is the function which searches the root node. It is
848 // similar to search_pv except that it uses a different move ordering
849 // scheme (perhaps we should try to use this at internal PV nodes, too?)
850 // and prints some information to the standard output.
852 Value root_search(Position& pos, SearchStack ss[], RootMoveList &rml, Value alpha, Value beta) {
854 Value oldAlpha = alpha;
856 Bitboard dcCandidates = pos.discovered_check_candidates(pos.side_to_move());
858 // Loop through all the moves in the root move list
859 for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
863 // We failed high, invalidate and skip next moves, leave node-counters
864 // and beta-counters as they are and quickly return, we will try to do
865 // a research at the next iteration with a bigger aspiration window.
866 rml.set_move_score(i, -VALUE_INFINITE);
874 RootMoveNumber = i + 1;
877 // Remember the node count before the move is searched. The node counts
878 // are used to sort the root moves at the next iteration.
879 nodes = nodes_searched();
881 // Reset beta cut-off counters
884 // Pick the next root move, and print the move and the move number to
885 // the standard output.
886 move = ss[0].currentMove = rml.get_move(i);
887 if (current_search_time() >= 1000)
888 std::cout << "info currmove " << move
889 << " currmovenumber " << i + 1 << std::endl;
891 // Decide search depth for this move
892 bool moveIsCapture = pos.move_is_capture(move);
894 ext = extension(pos, move, true, moveIsCapture, pos.move_is_check(move), false, false, &dangerous);
895 newDepth = (Iteration - 2) * OnePly + ext + InitialDepth;
897 // Make the move, and search it
898 pos.do_move(move, st, dcCandidates);
902 // Aspiration window is disabled in multi-pv case
904 alpha = -VALUE_INFINITE;
906 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
907 // If the value has dropped a lot compared to the last iteration,
908 // set the boolean variable Problem to true. This variable is used
909 // for time managment: When Problem is true, we try to complete the
910 // current iteration before playing a move.
911 Problem = (Iteration >= 2 && value <= IterationInfo[Iteration-1].value - ProblemMargin);
913 if (Problem && StopOnPonderhit)
914 StopOnPonderhit = false;
918 if ( newDepth >= 3*OnePly
919 && i >= MultiPV + LMRPVMoves
922 && !move_is_promotion(move)
923 && !move_is_castle(move))
925 ss[0].reduction = OnePly;
926 value = -search(pos, ss, -alpha, newDepth-OnePly, 1, true, 0);
928 value = alpha + 1; // Just to trigger next condition
932 value = -search(pos, ss, -alpha, newDepth, 1, true, 0);
935 // Fail high! Set the boolean variable FailHigh to true, and
936 // re-search the move with a big window. The variable FailHigh is
937 // used for time managment: We try to avoid aborting the search
938 // prematurely during a fail high research.
940 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
947 // Finished searching the move. If AbortSearch is true, the search
948 // was aborted because the user interrupted the search or because we
949 // ran out of time. In this case, the return value of the search cannot
950 // be trusted, and we break out of the loop without updating the best
955 // Remember the node count for this move. The node counts are used to
956 // sort the root moves at the next iteration.
957 rml.set_move_nodes(i, nodes_searched() - nodes);
959 // Remember the beta-cutoff statistics
961 BetaCounter.read(pos.side_to_move(), our, their);
962 rml.set_beta_counters(i, our, their);
964 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
966 if (value <= alpha && i >= MultiPV)
967 rml.set_move_score(i, -VALUE_INFINITE);
970 // PV move or new best move!
973 rml.set_move_score(i, value);
975 TT.extract_pv(pos, ss[0].pv);
976 rml.set_move_pv(i, ss[0].pv);
980 // We record how often the best move has been changed in each
981 // iteration. This information is used for time managment: When
982 // the best move changes frequently, we allocate some more time.
984 BestMoveChangesByIteration[Iteration]++;
986 // Print search information to the standard output
987 std::cout << "info depth " << Iteration
988 << " score " << value_to_string(value)
990 " lowerbound" : ((value <= alpha)? " upperbound" : ""))
991 << " time " << current_search_time()
992 << " nodes " << nodes_searched()
996 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
997 std::cout << ss[0].pv[j] << " ";
999 std::cout << std::endl;
1002 LogFile << pretty_pv(pos, current_search_time(), Iteration, nodes_searched(), value, ss[0].pv)
1008 // Reset the global variable Problem to false if the value isn't too
1009 // far below the final value from the last iteration.
1010 if (value > IterationInfo[Iteration - 1].value - NoProblemMargin)
1015 rml.sort_multipv(i);
1016 for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
1019 std::cout << "info multipv " << j + 1
1020 << " score " << value_to_string(rml.get_move_score(j))
1021 << " depth " << ((j <= i)? Iteration : Iteration - 1)
1022 << " time " << current_search_time()
1023 << " nodes " << nodes_searched()
1027 for (k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
1028 std::cout << rml.get_move_pv(j, k) << " ";
1030 std::cout << std::endl;
1032 alpha = rml.get_move_score(Min(i, MultiPV-1));
1034 } // New best move case
1036 assert(alpha >= oldAlpha);
1038 FailLow = (alpha == oldAlpha);
1044 // search_pv() is the main search function for PV nodes.
1046 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta,
1047 Depth depth, int ply, int threadID) {
1049 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1050 assert(beta > alpha && beta <= VALUE_INFINITE);
1051 assert(ply >= 0 && ply < PLY_MAX);
1052 assert(threadID >= 0 && threadID < ActiveThreads);
1055 return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID);
1057 // Initialize, and make an early exit in case of an aborted search,
1058 // an instant draw, maximum ply reached, etc.
1059 init_node(pos, ss, ply, threadID);
1061 // After init_node() that calls poll()
1062 if (AbortSearch || thread_should_stop(threadID))
1070 if (ply >= PLY_MAX - 1)
1071 return evaluate(pos, ei, threadID);
1073 // Mate distance pruning
1074 Value oldAlpha = alpha;
1075 alpha = Max(value_mated_in(ply), alpha);
1076 beta = Min(value_mate_in(ply+1), beta);
1080 // Transposition table lookup. At PV nodes, we don't use the TT for
1081 // pruning, but only for move ordering.
1082 const TTEntry* tte = TT.retrieve(pos.get_key());
1083 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1085 // Go with internal iterative deepening if we don't have a TT move
1086 if (UseIIDAtPVNodes && ttMove == MOVE_NONE && depth >= 5*OnePly)
1088 search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID);
1089 ttMove = ss[ply].pv[ply];
1092 // Initialize a MovePicker object for the current position, and prepare
1093 // to search all moves
1094 Move move, movesSearched[256];
1096 Value value, bestValue = -VALUE_INFINITE;
1097 Color us = pos.side_to_move();
1098 bool isCheck = pos.is_check();
1099 bool mateThreat = pos.has_mate_threat(opposite_color(us));
1101 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1102 Bitboard dcCandidates = mp.discovered_check_candidates();
1104 // Loop through all legal moves until no moves remain or a beta cutoff
1106 while ( alpha < beta
1107 && (move = mp.get_next_move()) != MOVE_NONE
1108 && !thread_should_stop(threadID))
1110 assert(move_is_ok(move));
1112 bool singleReply = (isCheck && mp.number_of_evasions() == 1);
1113 bool moveIsCheck = pos.move_is_check(move, dcCandidates);
1114 bool moveIsCapture = pos.move_is_capture(move);
1116 movesSearched[moveCount++] = ss[ply].currentMove = move;
1118 // Decide the new search depth
1120 Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous);
1121 Depth newDepth = depth - OnePly + ext;
1123 // Make and search the move
1125 pos.do_move(move, st, dcCandidates);
1127 if (moveCount == 1) // The first move in list is the PV
1128 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1131 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1132 // if the move fails high will be re-searched at full depth.
1133 if ( depth >= 3*OnePly
1134 && moveCount >= LMRPVMoves
1137 && !move_is_promotion(move)
1138 && !move_is_castle(move)
1139 && !move_is_killer(move, ss[ply]))
1141 ss[ply].reduction = OnePly;
1142 value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, threadID);
1145 value = alpha + 1; // Just to trigger next condition
1147 if (value > alpha) // Go with full depth non-pv search
1149 ss[ply].reduction = Depth(0);
1150 value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID);
1151 if (value > alpha && value < beta)
1153 // When the search fails high at ply 1 while searching the first
1154 // move at the root, set the flag failHighPly1. This is used for
1155 // time managment: We don't want to stop the search early in
1156 // such cases, because resolving the fail high at ply 1 could
1157 // result in a big drop in score at the root.
1158 if (ply == 1 && RootMoveNumber == 1)
1159 Threads[threadID].failHighPly1 = true;
1161 // A fail high occurred. Re-search at full window (pv search)
1162 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1163 Threads[threadID].failHighPly1 = false;
1167 pos.undo_move(move);
1169 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1172 if (value > bestValue)
1179 if (value == value_mate_in(ply + 1))
1180 ss[ply].mateKiller = move;
1182 // If we are at ply 1, and we are searching the first root move at
1183 // ply 0, set the 'Problem' variable if the score has dropped a lot
1184 // (from the computer's point of view) since the previous iteration.
1187 && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
1192 if ( ActiveThreads > 1
1194 && depth >= MinimumSplitDepth
1196 && idle_thread_exists(threadID)
1198 && !thread_should_stop(threadID)
1199 && split(pos, ss, ply, &alpha, &beta, &bestValue, depth,
1200 &moveCount, &mp, dcCandidates, threadID, true))
1204 // All legal moves have been searched. A special case: If there were
1205 // no legal moves, it must be mate or stalemate.
1207 return (isCheck ? value_mated_in(ply) : VALUE_DRAW);
1209 // If the search is not aborted, update the transposition table,
1210 // history counters, and killer moves.
1211 if (AbortSearch || thread_should_stop(threadID))
1214 if (bestValue <= oldAlpha)
1215 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1217 else if (bestValue >= beta)
1219 BetaCounter.add(pos.side_to_move(), depth, threadID);
1220 Move m = ss[ply].pv[ply];
1221 if (ok_to_history(pos, m)) // Only non capture moves are considered
1223 update_history(pos, m, depth, movesSearched, moveCount);
1224 update_killers(m, ss[ply]);
1226 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m);
1229 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
1235 // search() is the search function for zero-width nodes.
1237 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth,
1238 int ply, bool allowNullmove, int threadID) {
1240 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1241 assert(ply >= 0 && ply < PLY_MAX);
1242 assert(threadID >= 0 && threadID < ActiveThreads);
1245 return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1247 // Initialize, and make an early exit in case of an aborted search,
1248 // an instant draw, maximum ply reached, etc.
1249 init_node(pos, ss, ply, threadID);
1251 // After init_node() that calls poll()
1252 if (AbortSearch || thread_should_stop(threadID))
1260 if (ply >= PLY_MAX - 1)
1261 return evaluate(pos, ei, threadID);
1263 // Mate distance pruning
1264 if (value_mated_in(ply) >= beta)
1267 if (value_mate_in(ply + 1) < beta)
1270 // Transposition table lookup
1271 const TTEntry* tte = TT.retrieve(pos.get_key());
1272 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1274 if (tte && ok_to_use_TT(tte, depth, beta, ply))
1276 ss[ply].currentMove = ttMove; // can be MOVE_NONE
1277 return value_from_tt(tte->value(), ply);
1280 Value approximateEval = quick_evaluate(pos);
1281 bool mateThreat = false;
1282 bool isCheck = pos.is_check();
1288 && !value_is_mate(beta)
1289 && ok_to_do_nullmove(pos)
1290 && approximateEval >= beta - NullMoveMargin)
1292 ss[ply].currentMove = MOVE_NULL;
1295 pos.do_null_move(st);
1296 int R = (depth >= 5 * OnePly ? 4 : 3); // Null move dynamic reduction
1298 Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);
1300 pos.undo_null_move();
1302 if (nullValue >= beta)
1304 if (depth < 6 * OnePly)
1307 // Do zugzwang verification search
1308 Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
1312 // The null move failed low, which means that we may be faced with
1313 // some kind of threat. If the previous move was reduced, check if
1314 // the move that refuted the null move was somehow connected to the
1315 // move which was reduced. If a connection is found, return a fail
1316 // low score (which will cause the reduced move to fail high in the
1317 // parent node, which will trigger a re-search with full depth).
1318 if (nullValue == value_mated_in(ply + 2))
1321 ss[ply].threatMove = ss[ply + 1].currentMove;
1322 if ( depth < ThreatDepth
1323 && ss[ply - 1].reduction
1324 && connected_moves(pos, ss[ply - 1].currentMove, ss[ply].threatMove))
1328 // Null move search not allowed, try razoring
1329 else if ( !value_is_mate(beta)
1330 && depth < RazorDepth
1331 && approximateEval < beta - RazorApprMargins[int(depth) - 2]
1332 && ss[ply - 1].currentMove != MOVE_NULL
1333 && ttMove == MOVE_NONE
1334 && !pos.has_pawn_on_7th(pos.side_to_move()))
1336 Value v = qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1337 if (v < beta - RazorMargins[int(depth) - 2])
1341 // Go with internal iterative deepening if we don't have a TT move
1342 if (UseIIDAtNonPVNodes && ttMove == MOVE_NONE && depth >= 8*OnePly &&
1343 evaluate(pos, ei, threadID) >= beta - IIDMargin)
1345 search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID);
1346 ttMove = ss[ply].pv[ply];
1349 // Initialize a MovePicker object for the current position, and prepare
1350 // to search all moves.
1351 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1353 Move move, movesSearched[256];
1355 Value value, bestValue = -VALUE_INFINITE;
1356 Bitboard dcCandidates = mp.discovered_check_candidates();
1357 Value futilityValue = VALUE_NONE;
1358 bool useFutilityPruning = depth < SelectiveDepth
1361 // Loop through all legal moves until no moves remain or a beta cutoff
1363 while ( bestValue < beta
1364 && (move = mp.get_next_move()) != MOVE_NONE
1365 && !thread_should_stop(threadID))
1367 assert(move_is_ok(move));
1369 bool singleReply = (isCheck && mp.number_of_evasions() == 1);
1370 bool moveIsCheck = pos.move_is_check(move, dcCandidates);
1371 bool moveIsCapture = pos.move_is_capture(move);
1373 movesSearched[moveCount++] = ss[ply].currentMove = move;
1375 // Decide the new search depth
1377 Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous);
1378 Depth newDepth = depth - OnePly + ext;
1381 if ( useFutilityPruning
1384 && !move_is_promotion(move))
1386 // History pruning. See ok_to_prune() definition
1387 if ( moveCount >= 2 + int(depth)
1388 && ok_to_prune(pos, move, ss[ply].threatMove, depth))
1391 // Value based pruning
1392 if (approximateEval < beta)
1394 if (futilityValue == VALUE_NONE)
1395 futilityValue = evaluate(pos, ei, threadID)
1396 + FutilityMargins[int(depth) - 2];
1398 if (futilityValue < beta)
1400 if (futilityValue > bestValue)
1401 bestValue = futilityValue;
1407 // Make and search the move
1409 pos.do_move(move, st, dcCandidates);
1411 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1412 // if the move fails high will be re-searched at full depth.
1413 if ( depth >= 3*OnePly
1414 && moveCount >= LMRNonPVMoves
1417 && !move_is_promotion(move)
1418 && !move_is_castle(move)
1419 && !move_is_killer(move, ss[ply]))
1421 ss[ply].reduction = OnePly;
1422 value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);
1425 value = beta; // Just to trigger next condition
1427 if (value >= beta) // Go with full depth non-pv search
1429 ss[ply].reduction = Depth(0);
1430 value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID);
1432 pos.undo_move(move);
1434 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1437 if (value > bestValue)
1443 if (value == value_mate_in(ply + 1))
1444 ss[ply].mateKiller = move;
1448 if ( ActiveThreads > 1
1450 && depth >= MinimumSplitDepth
1452 && idle_thread_exists(threadID)
1454 && !thread_should_stop(threadID)
1455 && split(pos, ss, ply, &beta, &beta, &bestValue, depth, &moveCount,
1456 &mp, dcCandidates, threadID, false))
1460 // All legal moves have been searched. A special case: If there were
1461 // no legal moves, it must be mate or stalemate.
1463 return (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW);
1465 // If the search is not aborted, update the transposition table,
1466 // history counters, and killer moves.
1467 if (AbortSearch || thread_should_stop(threadID))
1470 if (bestValue < beta)
1471 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1474 BetaCounter.add(pos.side_to_move(), depth, threadID);
1475 Move m = ss[ply].pv[ply];
1476 if (ok_to_history(pos, m)) // Only non capture moves are considered
1478 update_history(pos, m, depth, movesSearched, moveCount);
1479 update_killers(m, ss[ply]);
1481 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m);
1484 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1490 // qsearch() is the quiescence search function, which is called by the main
1491 // search function when the remaining depth is zero (or, to be more precise,
1492 // less than OnePly).
1494 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta,
1495 Depth depth, int ply, int threadID) {
1497 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1498 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1500 assert(ply >= 0 && ply < PLY_MAX);
1501 assert(threadID >= 0 && threadID < ActiveThreads);
1503 // Initialize, and make an early exit in case of an aborted search,
1504 // an instant draw, maximum ply reached, etc.
1505 init_node(pos, ss, ply, threadID);
1507 // After init_node() that calls poll()
1508 if (AbortSearch || thread_should_stop(threadID))
1514 // Transposition table lookup, only when not in PV
1515 TTEntry* tte = NULL;
1516 bool pvNode = (beta - alpha != 1);
1519 tte = TT.retrieve(pos.get_key());
1520 if (tte && ok_to_use_TT(tte, depth, beta, ply))
1522 assert(tte->type() != VALUE_TYPE_EVAL);
1524 return value_from_tt(tte->value(), ply);
1527 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1529 // Evaluate the position statically
1532 bool isCheck = pos.is_check();
1533 ei.futilityMargin = Value(0); // Manually initialize futilityMargin
1536 staticValue = -VALUE_INFINITE;
1538 else if (tte && (tte->type() & VALUE_TYPE_EVAL))
1540 // Use the cached evaluation score if possible
1541 assert(ei.futilityMargin == Value(0));
1543 staticValue = tte->value();
1546 staticValue = evaluate(pos, ei, threadID);
1548 if (ply == PLY_MAX - 1)
1549 return evaluate(pos, ei, threadID);
1551 // Initialize "stand pat score", and return it immediately if it is
1553 Value bestValue = staticValue;
1555 if (bestValue >= beta)
1557 // Store the score to avoid a future costly evaluation() call
1558 if (!isCheck && !tte && ei.futilityMargin == 0)
1559 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EV_LO, Depth(-127*OnePly), MOVE_NONE);
1564 if (bestValue > alpha)
1567 // Initialize a MovePicker object for the current position, and prepare
1568 // to search the moves. Because the depth is <= 0 here, only captures,
1569 // queen promotions and checks (only if depth == 0) will be generated.
1570 MovePicker mp = MovePicker(pos, ttMove, depth, H);
1573 Bitboard dcCandidates = mp.discovered_check_candidates();
1574 Color us = pos.side_to_move();
1575 bool enoughMaterial = pos.non_pawn_material(us) > RookValueMidgame;
1577 // Loop through the moves until no moves remain or a beta cutoff
1579 while ( alpha < beta
1580 && (move = mp.get_next_move()) != MOVE_NONE)
1582 assert(move_is_ok(move));
1585 ss[ply].currentMove = move;
1591 && !move_is_promotion(move)
1592 && !pos.move_is_check(move, dcCandidates)
1593 && !pos.move_is_passed_pawn_push(move))
1595 Value futilityValue = staticValue
1596 + Max(pos.midgame_value_of_piece_on(move_to(move)),
1597 pos.endgame_value_of_piece_on(move_to(move)))
1598 + (move_is_ep(move) ? PawnValueEndgame : Value(0))
1600 + ei.futilityMargin;
1602 if (futilityValue < alpha)
1604 if (futilityValue > bestValue)
1605 bestValue = futilityValue;
1610 // Don't search captures and checks with negative SEE values
1612 && !move_is_promotion(move)
1613 && pos.see_sign(move) < 0)
1616 // Make and search the move.
1618 pos.do_move(move, st, dcCandidates);
1619 Value value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID);
1620 pos.undo_move(move);
1622 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1625 if (value > bestValue)
1636 // All legal moves have been searched. A special case: If we're in check
1637 // and no legal moves were found, it is checkmate.
1638 if (pos.is_check() && moveCount == 0) // Mate!
1639 return value_mated_in(ply);
1641 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1643 // Update transposition table
1644 Move m = ss[ply].pv[ply];
1647 // If bestValue isn't changed it means it is still the static evaluation of
1648 // the node, so keep this info to avoid a future costly evaluation() call.
1649 ValueType type = (bestValue == staticValue && !ei.futilityMargin ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER);
1650 Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
1652 if (bestValue < beta)
1653 TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, 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 MoveStack* last = generate_moves(pos, mlist);
1971 // Add each move to the moves[] array
1972 for (MoveStack* cur = mlist; cur != last; cur++)
1974 bool includeMove = includeAllMoves;
1976 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
1977 includeMove = (searchMoves[k] == cur->move);
1982 // Find a quick score for the move
1984 SearchStack ss[PLY_MAX_PLUS_2];
1986 moves[count].move = cur->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) {
2161 Square f1, t1, f2, t2;
2164 assert(move_is_ok(m1));
2165 assert(move_is_ok(m2));
2167 if (m2 == MOVE_NONE)
2170 // Case 1: The moving piece is the same in both moves
2176 // Case 2: The destination square for m2 was vacated by m1
2182 // Case 3: Moving through the vacated square
2183 if ( piece_is_slider(pos.piece_on(f2))
2184 && bit_is_set(squares_between(f2, t2), f1))
2187 // Case 4: The destination square for m2 is attacked by the moving piece in m1
2188 p = pos.piece_on(t1);
2189 if (bit_is_set(pos.attacks_from(p, t1), t2))
2192 // Case 5: Discovered check, checking piece is the piece moved in m1
2193 if ( piece_is_slider(p)
2194 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
2195 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
2197 Bitboard occ = pos.occupied_squares();
2198 Color us = pos.side_to_move();
2199 Square ksq = pos.king_square(us);
2200 clear_bit(&occ, f2);
2201 if (type_of_piece(p) == BISHOP)
2203 if (bit_is_set(bishop_attacks_bb(ksq, occ), t1))
2206 else if (type_of_piece(p) == ROOK)
2208 if (bit_is_set(rook_attacks_bb(ksq, occ), t1))
2213 assert(type_of_piece(p) == QUEEN);
2214 if (bit_is_set(queen_attacks_bb(ksq, occ), t1))
2222 // value_is_mate() checks if the given value is a mate one
2223 // eventually compensated for the ply.
2225 bool value_is_mate(Value value) {
2227 assert(abs(value) <= VALUE_INFINITE);
2229 return value <= value_mated_in(PLY_MAX)
2230 || value >= value_mate_in(PLY_MAX);
2234 // move_is_killer() checks if the given move is among the
2235 // killer moves of that ply.
2237 bool move_is_killer(Move m, const SearchStack& ss) {
2239 const Move* k = ss.killers;
2240 for (int i = 0; i < KILLER_MAX; i++, k++)
2248 // extension() decides whether a move should be searched with normal depth,
2249 // or with extended depth. Certain classes of moves (checking moves, in
2250 // particular) are searched with bigger depth than ordinary moves and in
2251 // any case are marked as 'dangerous'. Note that also if a move is not
2252 // extended, as example because the corresponding UCI option is set to zero,
2253 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
2255 Depth extension(const Position& pos, Move m, bool pvNode, bool capture, bool check,
2256 bool singleReply, bool mateThreat, bool* dangerous) {
2258 assert(m != MOVE_NONE);
2260 Depth result = Depth(0);
2261 *dangerous = check | singleReply | mateThreat;
2266 result += CheckExtension[pvNode];
2269 result += SingleReplyExtension[pvNode];
2272 result += MateThreatExtension[pvNode];
2275 if (pos.type_of_piece_on(move_from(m)) == PAWN)
2277 Color c = pos.side_to_move();
2278 if (relative_rank(c, move_to(m)) == RANK_7)
2280 result += PawnPushTo7thExtension[pvNode];
2283 if (pos.pawn_is_passed(c, move_to(m)))
2285 result += PassedPawnExtension[pvNode];
2291 && pos.type_of_piece_on(move_to(m)) != PAWN
2292 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
2293 - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))
2294 && !move_is_promotion(m)
2297 result += PawnEndgameExtension[pvNode];
2303 && pos.type_of_piece_on(move_to(m)) != PAWN
2304 && pos.see_sign(m) >= 0)
2310 return Min(result, OnePly);
2314 // ok_to_do_nullmove() looks at the current position and decides whether
2315 // doing a 'null move' should be allowed. In order to avoid zugzwang
2316 // problems, null moves are not allowed when the side to move has very
2317 // little material left. Currently, the test is a bit too simple: Null
2318 // moves are avoided only when the side to move has only pawns left. It's
2319 // probably a good idea to avoid null moves in at least some more
2320 // complicated endgames, e.g. KQ vs KR. FIXME
2322 bool ok_to_do_nullmove(const Position& pos) {
2324 return pos.non_pawn_material(pos.side_to_move()) != Value(0);
2328 // ok_to_prune() tests whether it is safe to forward prune a move. Only
2329 // non-tactical moves late in the move list close to the leaves are
2330 // candidates for pruning.
2332 bool ok_to_prune(const Position& pos, Move m, Move threat, Depth d) {
2334 assert(move_is_ok(m));
2335 assert(threat == MOVE_NONE || move_is_ok(threat));
2336 assert(!move_is_promotion(m));
2337 assert(!pos.move_is_check(m));
2338 assert(!pos.move_is_capture(m));
2339 assert(!pos.move_is_passed_pawn_push(m));
2340 assert(d >= OnePly);
2342 Square mfrom, mto, tfrom, tto;
2344 mfrom = move_from(m);
2346 tfrom = move_from(threat);
2347 tto = move_to(threat);
2349 // Case 1: Castling moves are never pruned
2350 if (move_is_castle(m))
2353 // Case 2: Don't prune moves which move the threatened piece
2354 if (!PruneEscapeMoves && threat != MOVE_NONE && mfrom == tto)
2357 // Case 3: If the threatened piece has value less than or equal to the
2358 // value of the threatening piece, don't prune move which defend it.
2359 if ( !PruneDefendingMoves
2360 && threat != MOVE_NONE
2361 && pos.move_is_capture(threat)
2362 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
2363 || pos.type_of_piece_on(tfrom) == KING)
2364 && pos.move_attacks_square(m, tto))
2367 // Case 4: Don't prune moves with good history
2368 if (!H.ok_to_prune(pos.piece_on(mfrom), mto, d))
2371 // Case 5: If the moving piece in the threatened move is a slider, don't
2372 // prune safe moves which block its ray.
2373 if ( !PruneBlockingMoves
2374 && threat != MOVE_NONE
2375 && piece_is_slider(pos.piece_on(tfrom))
2376 && bit_is_set(squares_between(tfrom, tto), mto)
2377 && pos.see_sign(m) >= 0)
2384 // ok_to_use_TT() returns true if a transposition table score
2385 // can be used at a given point in search.
2387 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
2389 Value v = value_from_tt(tte->value(), ply);
2391 return ( tte->depth() >= depth
2392 || v >= Max(value_mate_in(100), beta)
2393 || v < Min(value_mated_in(100), beta))
2395 && ( (is_lower_bound(tte->type()) && v >= beta)
2396 || (is_upper_bound(tte->type()) && v < beta));
2400 // ok_to_history() returns true if a move m can be stored
2401 // in history. Should be a non capturing move nor a promotion.
2403 bool ok_to_history(const Position& pos, Move m) {
2405 return !pos.move_is_capture(m) && !move_is_promotion(m);
2409 // update_history() registers a good move that produced a beta-cutoff
2410 // in history and marks as failures all the other moves of that ply.
2412 void update_history(const Position& pos, Move m, Depth depth,
2413 Move movesSearched[], int moveCount) {
2415 H.success(pos.piece_on(move_from(m)), move_to(m), depth);
2417 for (int i = 0; i < moveCount - 1; i++)
2419 assert(m != movesSearched[i]);
2420 if (ok_to_history(pos, movesSearched[i]))
2421 H.failure(pos.piece_on(move_from(movesSearched[i])), move_to(movesSearched[i]));
2426 // update_killers() add a good move that produced a beta-cutoff
2427 // among the killer moves of that ply.
2429 void update_killers(Move m, SearchStack& ss) {
2431 if (m == ss.killers[0])
2434 for (int i = KILLER_MAX - 1; i > 0; i--)
2435 ss.killers[i] = ss.killers[i - 1];
2441 // slowdown() simply wastes CPU cycles doing nothing useful. It's used
2442 // in strength handicap mode.
2444 void slowdown(const Position &pos) {
2447 for (i = 0; i < n; i++) {
2448 Square s = Square(i&63);
2449 if (count_1s(pos.attackers_to(s)) > 63)
2450 std::cout << "This can't happen, but I put this string here anyway, in order to "
2451 "prevent the compiler from optimizing away the useless computation." << std::endl;
2456 // fail_high_ply_1() checks if some thread is currently resolving a fail
2457 // high at ply 1 at the node below the first root node. This information
2458 // is used for time managment.
2460 bool fail_high_ply_1() {
2462 for(int i = 0; i < ActiveThreads; i++)
2463 if (Threads[i].failHighPly1)
2470 // current_search_time() returns the number of milliseconds which have passed
2471 // since the beginning of the current search.
2473 int current_search_time() {
2474 return get_system_time() - SearchStartTime;
2478 // nps() computes the current nodes/second count.
2481 int t = current_search_time();
2482 return (t > 0)? int((nodes_searched() * 1000) / t) : 0;
2486 // poll() performs two different functions: It polls for user input, and it
2487 // looks at the time consumed so far and decides if it's time to abort the
2492 static int lastInfoTime;
2493 int t = current_search_time();
2498 // We are line oriented, don't read single chars
2499 std::string command;
2500 if (!std::getline(std::cin, command))
2503 if (command == "quit")
2506 PonderSearch = false;
2510 else if (command == "stop")
2513 PonderSearch = false;
2515 else if (command == "ponderhit")
2518 // Print search information
2522 else if (lastInfoTime > t)
2523 // HACK: Must be a new search where we searched less than
2524 // NodesBetweenPolls nodes during the first second of search.
2527 else if (t - lastInfoTime >= 1000)
2534 if (dbg_show_hit_rate)
2535 dbg_print_hit_rate();
2537 std::cout << "info nodes " << nodes_searched() << " nps " << nps()
2538 << " time " << t << " hashfull " << TT.full() << std::endl;
2539 lock_release(&IOLock);
2540 if (ShowCurrentLine)
2541 Threads[0].printCurrentLine = true;
2543 // Should we stop the search?
2547 bool overTime = t > AbsoluteMaxSearchTime
2548 || (RootMoveNumber == 1 && t > MaxSearchTime + ExtraSearchTime && !FailLow) //FIXME: We are not checking any problem flags, BUG?
2549 || ( !FailHigh && !FailLow && !fail_high_ply_1() && !Problem
2550 && t > 6*(MaxSearchTime + ExtraSearchTime));
2552 if ( (Iteration >= 3 && (!InfiniteSearch && overTime))
2553 || (ExactMaxTime && t >= ExactMaxTime)
2554 || (Iteration >= 3 && MaxNodes && nodes_searched() >= MaxNodes))
2559 // ponderhit() is called when the program is pondering (i.e. thinking while
2560 // it's the opponent's turn to move) in order to let the engine know that
2561 // it correctly predicted the opponent's move.
2565 int t = current_search_time();
2566 PonderSearch = false;
2567 if (Iteration >= 3 &&
2568 (!InfiniteSearch && (StopOnPonderhit ||
2569 t > AbsoluteMaxSearchTime ||
2570 (RootMoveNumber == 1 &&
2571 t > MaxSearchTime + ExtraSearchTime && !FailLow) ||
2572 (!FailHigh && !FailLow && !fail_high_ply_1() && !Problem &&
2573 t > 6*(MaxSearchTime + ExtraSearchTime)))))
2578 // print_current_line() prints the current line of search for a given
2579 // thread. Called when the UCI option UCI_ShowCurrLine is 'true'.
2581 void print_current_line(SearchStack ss[], int ply, int threadID) {
2583 assert(ply >= 0 && ply < PLY_MAX);
2584 assert(threadID >= 0 && threadID < ActiveThreads);
2586 if (!Threads[threadID].idle)
2589 std::cout << "info currline " << (threadID + 1);
2590 for (int p = 0; p < ply; p++)
2591 std::cout << " " << ss[p].currentMove;
2593 std::cout << std::endl;
2594 lock_release(&IOLock);
2596 Threads[threadID].printCurrentLine = false;
2597 if (threadID + 1 < ActiveThreads)
2598 Threads[threadID + 1].printCurrentLine = true;
2602 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2603 // while the program is pondering. The point is to work around a wrinkle in
2604 // the UCI protocol: When pondering, the engine is not allowed to give a
2605 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2606 // We simply wait here until one of these commands is sent, and return,
2607 // after which the bestmove and pondermove will be printed (in id_loop()).
2609 void wait_for_stop_or_ponderhit() {
2611 std::string command;
2615 if (!std::getline(std::cin, command))
2618 if (command == "quit")
2623 else if (command == "ponderhit" || command == "stop")
2629 // idle_loop() is where the threads are parked when they have no work to do.
2630 // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint
2631 // object for which the current thread is the master.
2633 void idle_loop(int threadID, SplitPoint* waitSp) {
2634 assert(threadID >= 0 && threadID < THREAD_MAX);
2636 Threads[threadID].running = true;
2639 if(AllThreadsShouldExit && threadID != 0)
2642 // If we are not thinking, wait for a condition to be signaled instead
2643 // of wasting CPU time polling for work:
2644 while(threadID != 0 && (Idle || threadID >= ActiveThreads)) {
2645 #if !defined(_MSC_VER)
2646 pthread_mutex_lock(&WaitLock);
2647 if(Idle || threadID >= ActiveThreads)
2648 pthread_cond_wait(&WaitCond, &WaitLock);
2649 pthread_mutex_unlock(&WaitLock);
2651 WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2655 // If this thread has been assigned work, launch a search
2656 if(Threads[threadID].workIsWaiting) {
2657 Threads[threadID].workIsWaiting = false;
2658 if(Threads[threadID].splitPoint->pvNode)
2659 sp_search_pv(Threads[threadID].splitPoint, threadID);
2661 sp_search(Threads[threadID].splitPoint, threadID);
2662 Threads[threadID].idle = true;
2665 // If this thread is the master of a split point and all threads have
2666 // finished their work at this split point, return from the idle loop.
2667 if(waitSp != NULL && waitSp->cpus == 0)
2671 Threads[threadID].running = false;
2675 // init_split_point_stack() is called during program initialization, and
2676 // initializes all split point objects.
2678 void init_split_point_stack() {
2679 for(int i = 0; i < THREAD_MAX; i++)
2680 for(int j = 0; j < MaxActiveSplitPoints; j++) {
2681 SplitPointStack[i][j].parent = NULL;
2682 lock_init(&(SplitPointStack[i][j].lock), NULL);
2687 // destroy_split_point_stack() is called when the program exits, and
2688 // destroys all locks in the precomputed split point objects.
2690 void destroy_split_point_stack() {
2691 for(int i = 0; i < THREAD_MAX; i++)
2692 for(int j = 0; j < MaxActiveSplitPoints; j++)
2693 lock_destroy(&(SplitPointStack[i][j].lock));
2697 // thread_should_stop() checks whether the thread with a given threadID has
2698 // been asked to stop, directly or indirectly. This can happen if a beta
2699 // cutoff has occured in thre thread's currently active split point, or in
2700 // some ancestor of the current split point.
2702 bool thread_should_stop(int threadID) {
2703 assert(threadID >= 0 && threadID < ActiveThreads);
2707 if(Threads[threadID].stop)
2709 if(ActiveThreads <= 2)
2711 for(sp = Threads[threadID].splitPoint; sp != NULL; sp = sp->parent)
2713 Threads[threadID].stop = true;
2720 // thread_is_available() checks whether the thread with threadID "slave" is
2721 // available to help the thread with threadID "master" at a split point. An
2722 // obvious requirement is that "slave" must be idle. With more than two
2723 // threads, this is not by itself sufficient: If "slave" is the master of
2724 // some active split point, it is only available as a slave to the other
2725 // threads which are busy searching the split point at the top of "slave"'s
2726 // split point stack (the "helpful master concept" in YBWC terminology).
2728 bool thread_is_available(int slave, int master) {
2729 assert(slave >= 0 && slave < ActiveThreads);
2730 assert(master >= 0 && master < ActiveThreads);
2731 assert(ActiveThreads > 1);
2733 if(!Threads[slave].idle || slave == master)
2736 if(Threads[slave].activeSplitPoints == 0)
2737 // No active split points means that the thread is available as a slave
2738 // for any other thread.
2741 if(ActiveThreads == 2)
2744 // Apply the "helpful master" concept if possible.
2745 if(SplitPointStack[slave][Threads[slave].activeSplitPoints-1].slaves[master])
2752 // idle_thread_exists() tries to find an idle thread which is available as
2753 // a slave for the thread with threadID "master".
2755 bool idle_thread_exists(int master) {
2756 assert(master >= 0 && master < ActiveThreads);
2757 assert(ActiveThreads > 1);
2759 for(int i = 0; i < ActiveThreads; i++)
2760 if(thread_is_available(i, master))
2766 // split() does the actual work of distributing the work at a node between
2767 // several threads at PV nodes. If it does not succeed in splitting the
2768 // node (because no idle threads are available, or because we have no unused
2769 // split point objects), the function immediately returns false. If
2770 // splitting is possible, a SplitPoint object is initialized with all the
2771 // data that must be copied to the helper threads (the current position and
2772 // search stack, alpha, beta, the search depth, etc.), and we tell our
2773 // helper threads that they have been assigned work. This will cause them
2774 // to instantly leave their idle loops and call sp_search_pv(). When all
2775 // threads have returned from sp_search_pv (or, equivalently, when
2776 // splitPoint->cpus becomes 0), split() returns true.
2778 bool split(const Position& p, SearchStack* sstck, int ply,
2779 Value* alpha, Value* beta, Value* bestValue, Depth depth, int* moves,
2780 MovePicker* mp, Bitboard dcCandidates, int master, bool pvNode) {
2783 assert(sstck != NULL);
2784 assert(ply >= 0 && ply < PLY_MAX);
2785 assert(*bestValue >= -VALUE_INFINITE && *bestValue <= *alpha);
2786 assert(!pvNode || *alpha < *beta);
2787 assert(*beta <= VALUE_INFINITE);
2788 assert(depth > Depth(0));
2789 assert(master >= 0 && master < ActiveThreads);
2790 assert(ActiveThreads > 1);
2792 SplitPoint* splitPoint;
2797 // If no other thread is available to help us, or if we have too many
2798 // active split points, don't split.
2799 if(!idle_thread_exists(master) ||
2800 Threads[master].activeSplitPoints >= MaxActiveSplitPoints) {
2801 lock_release(&MPLock);
2805 // Pick the next available split point object from the split point stack
2806 splitPoint = SplitPointStack[master] + Threads[master].activeSplitPoints;
2807 Threads[master].activeSplitPoints++;
2809 // Initialize the split point object
2810 splitPoint->parent = Threads[master].splitPoint;
2811 splitPoint->finished = false;
2812 splitPoint->ply = ply;
2813 splitPoint->depth = depth;
2814 splitPoint->alpha = pvNode? *alpha : (*beta - 1);
2815 splitPoint->beta = *beta;
2816 splitPoint->pvNode = pvNode;
2817 splitPoint->dcCandidates = dcCandidates;
2818 splitPoint->bestValue = *bestValue;
2819 splitPoint->master = master;
2820 splitPoint->mp = mp;
2821 splitPoint->moves = *moves;
2822 splitPoint->cpus = 1;
2823 splitPoint->pos.copy(p);
2824 splitPoint->parentSstack = sstck;
2825 for(i = 0; i < ActiveThreads; i++)
2826 splitPoint->slaves[i] = 0;
2828 // Copy the current position and the search stack to the master thread
2829 memcpy(splitPoint->sstack[master], sstck, (ply+1)*sizeof(SearchStack));
2830 Threads[master].splitPoint = splitPoint;
2832 // Make copies of the current position and search stack for each thread
2833 for(i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint;
2835 if(thread_is_available(i, master)) {
2836 memcpy(splitPoint->sstack[i], sstck, (ply+1)*sizeof(SearchStack));
2837 Threads[i].splitPoint = splitPoint;
2838 splitPoint->slaves[i] = 1;
2842 // Tell the threads that they have work to do. This will make them leave
2844 for(i = 0; i < ActiveThreads; i++)
2845 if(i == master || splitPoint->slaves[i]) {
2846 Threads[i].workIsWaiting = true;
2847 Threads[i].idle = false;
2848 Threads[i].stop = false;
2851 lock_release(&MPLock);
2853 // Everything is set up. The master thread enters the idle loop, from
2854 // which it will instantly launch a search, because its workIsWaiting
2855 // slot is 'true'. We send the split point as a second parameter to the
2856 // idle loop, which means that the main thread will return from the idle
2857 // loop when all threads have finished their work at this split point
2858 // (i.e. when // splitPoint->cpus == 0).
2859 idle_loop(master, splitPoint);
2861 // We have returned from the idle loop, which means that all threads are
2862 // finished. Update alpha, beta and bestvalue, and return.
2864 if(pvNode) *alpha = splitPoint->alpha;
2865 *beta = splitPoint->beta;
2866 *bestValue = splitPoint->bestValue;
2867 Threads[master].stop = false;
2868 Threads[master].idle = false;
2869 Threads[master].activeSplitPoints--;
2870 Threads[master].splitPoint = splitPoint->parent;
2871 lock_release(&MPLock);
2877 // wake_sleeping_threads() wakes up all sleeping threads when it is time
2878 // to start a new search from the root.
2880 void wake_sleeping_threads() {
2881 if(ActiveThreads > 1) {
2882 for(int i = 1; i < ActiveThreads; i++) {
2883 Threads[i].idle = true;
2884 Threads[i].workIsWaiting = false;
2886 #if !defined(_MSC_VER)
2887 pthread_mutex_lock(&WaitLock);
2888 pthread_cond_broadcast(&WaitCond);
2889 pthread_mutex_unlock(&WaitLock);
2891 for(int i = 1; i < THREAD_MAX; i++)
2892 SetEvent(SitIdleEvent[i]);
2898 // init_thread() is the function which is called when a new thread is
2899 // launched. It simply calls the idle_loop() function with the supplied
2900 // threadID. There are two versions of this function; one for POSIX threads
2901 // and one for Windows threads.
2903 #if !defined(_MSC_VER)
2905 void *init_thread(void *threadID) {
2906 idle_loop(*(int *)threadID, NULL);
2912 DWORD WINAPI init_thread(LPVOID threadID) {
2913 idle_loop(*(int *)threadID, NULL);