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);
661 // Print RootMoveList c'tor startup scoring to the standard output,
662 // so that we print information also for iteration 1.
663 std::cout << "info depth " << 1 << "\ninfo depth " << 1
664 << " score " << value_to_string(rml.get_move_score(0))
665 << " time " << current_search_time()
666 << " nodes " << nodes_searched()
668 << " pv " << rml.get_move(0) << "\n";
673 for (int i = 0; i < 3; i++)
678 IterationInfo[1] = IterationInfoType(rml.get_move_score(0), rml.get_move_score(0));
681 Move EasyMove = rml.scan_for_easy_move();
683 // Iterative deepening loop
684 while (Iteration < PLY_MAX)
686 // Initialize iteration
689 BestMoveChangesByIteration[Iteration] = 0;
693 std::cout << "info depth " << Iteration << std::endl;
695 // Calculate dynamic search window based on previous iterations
698 if (MultiPV == 1 && Iteration >= 6 && abs(IterationInfo[Iteration - 1].value) < VALUE_KNOWN_WIN)
700 int prevDelta1 = IterationInfo[Iteration - 1].speculatedValue - IterationInfo[Iteration - 2].speculatedValue;
701 int prevDelta2 = IterationInfo[Iteration - 2].speculatedValue - IterationInfo[Iteration - 3].speculatedValue;
703 int delta = Max(2 * abs(prevDelta1) + abs(prevDelta2), ProblemMargin);
705 alpha = Max(IterationInfo[Iteration - 1].value - delta, -VALUE_INFINITE);
706 beta = Min(IterationInfo[Iteration - 1].value + delta, VALUE_INFINITE);
710 alpha = - VALUE_INFINITE;
711 beta = VALUE_INFINITE;
714 // Search to the current depth
715 Value value = root_search(p, ss, rml, alpha, beta);
717 // Write PV to transposition table, in case the relevant entries have
718 // been overwritten during the search.
719 TT.insert_pv(p, ss[0].pv);
722 break; // Value cannot be trusted. Break out immediately!
724 //Save info about search result
725 Value speculatedValue;
728 Value delta = value - IterationInfo[Iteration - 1].value;
735 speculatedValue = value + delta;
736 BestMoveChangesByIteration[Iteration] += 2; // Allocate more time
738 else if (value <= alpha)
740 assert(value == alpha);
744 speculatedValue = value + delta;
745 BestMoveChangesByIteration[Iteration] += 3; // Allocate more time
747 speculatedValue = value;
749 speculatedValue = Min(Max(speculatedValue, -VALUE_INFINITE), VALUE_INFINITE);
750 IterationInfo[Iteration] = IterationInfoType(value, speculatedValue);
752 // Erase the easy move if it differs from the new best move
753 if (ss[0].pv[0] != EasyMove)
754 EasyMove = MOVE_NONE;
761 bool stopSearch = false;
763 // Stop search early if there is only a single legal move
764 if (Iteration >= 6 && rml.move_count() == 1)
767 // Stop search early when the last two iterations returned a mate score
769 && abs(IterationInfo[Iteration].value) >= abs(VALUE_MATE) - 100
770 && abs(IterationInfo[Iteration-1].value) >= abs(VALUE_MATE) - 100)
773 // Stop search early if one move seems to be much better than the rest
774 int64_t nodes = nodes_searched();
778 && EasyMove == ss[0].pv[0]
779 && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
780 && current_search_time() > MaxSearchTime / 16)
781 ||( rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100
782 && current_search_time() > MaxSearchTime / 32)))
785 // Add some extra time if the best move has changed during the last two iterations
786 if (Iteration > 5 && Iteration <= 50)
787 ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2)
788 + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3);
790 // Stop search if most of MaxSearchTime is consumed at the end of the
791 // iteration. We probably don't have enough time to search the first
792 // move at the next iteration anyway.
793 if (current_search_time() > ((MaxSearchTime + ExtraSearchTime)*80) / 128)
798 //FIXME: Implement fail-low emergency measures
802 StopOnPonderhit = true;
806 if (MaxDepth && Iteration >= MaxDepth)
812 // If we are pondering, we shouldn't print the best move before we
815 wait_for_stop_or_ponderhit();
817 // Print final search statistics
818 std::cout << "info nodes " << nodes_searched()
820 << " time " << current_search_time()
821 << " hashfull " << TT.full() << std::endl;
823 // Print the best move and the ponder move to the standard output
824 if (ss[0].pv[0] == MOVE_NONE)
826 ss[0].pv[0] = rml.get_move(0);
827 ss[0].pv[1] = MOVE_NONE;
829 std::cout << "bestmove " << ss[0].pv[0];
830 if (ss[0].pv[1] != MOVE_NONE)
831 std::cout << " ponder " << ss[0].pv[1];
833 std::cout << std::endl;
838 dbg_print_mean(LogFile);
840 if (dbg_show_hit_rate)
841 dbg_print_hit_rate(LogFile);
844 LogFile << "Nodes: " << nodes_searched() << std::endl
845 << "Nodes/second: " << nps() << std::endl
846 << "Best move: " << move_to_san(p, ss[0].pv[0]) << std::endl;
848 p.do_move(ss[0].pv[0], st);
849 LogFile << "Ponder move: " << move_to_san(p, ss[0].pv[1])
850 << std::endl << std::endl;
852 return rml.get_move_score(0);
856 // root_search() is the function which searches the root node. It is
857 // similar to search_pv except that it uses a different move ordering
858 // scheme (perhaps we should try to use this at internal PV nodes, too?)
859 // and prints some information to the standard output.
861 Value root_search(Position& pos, SearchStack ss[], RootMoveList &rml, Value alpha, Value beta) {
863 Value oldAlpha = alpha;
865 Bitboard dcCandidates = pos.discovered_check_candidates(pos.side_to_move());
867 // Loop through all the moves in the root move list
868 for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
872 // We failed high, invalidate and skip next moves, leave node-counters
873 // and beta-counters as they are and quickly return, we will try to do
874 // a research at the next iteration with a bigger aspiration window.
875 rml.set_move_score(i, -VALUE_INFINITE);
883 RootMoveNumber = i + 1;
886 // Remember the node count before the move is searched. The node counts
887 // are used to sort the root moves at the next iteration.
888 nodes = nodes_searched();
890 // Reset beta cut-off counters
893 // Pick the next root move, and print the move and the move number to
894 // the standard output.
895 move = ss[0].currentMove = rml.get_move(i);
896 if (current_search_time() >= 1000)
897 std::cout << "info currmove " << move
898 << " currmovenumber " << i + 1 << std::endl;
900 // Decide search depth for this move
901 bool moveIsCapture = pos.move_is_capture(move);
903 ext = extension(pos, move, true, moveIsCapture, pos.move_is_check(move), false, false, &dangerous);
904 newDepth = (Iteration - 2) * OnePly + ext + InitialDepth;
906 // Make the move, and search it
907 pos.do_move(move, st, dcCandidates);
911 // Aspiration window is disabled in multi-pv case
913 alpha = -VALUE_INFINITE;
915 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
916 // If the value has dropped a lot compared to the last iteration,
917 // set the boolean variable Problem to true. This variable is used
918 // for time managment: When Problem is true, we try to complete the
919 // current iteration before playing a move.
920 Problem = (Iteration >= 2 && value <= IterationInfo[Iteration-1].value - ProblemMargin);
922 if (Problem && StopOnPonderhit)
923 StopOnPonderhit = false;
927 if ( newDepth >= 3*OnePly
928 && i >= MultiPV + LMRPVMoves
931 && !move_is_promotion(move)
932 && !move_is_castle(move))
934 ss[0].reduction = OnePly;
935 value = -search(pos, ss, -alpha, newDepth-OnePly, 1, true, 0);
937 value = alpha + 1; // Just to trigger next condition
941 value = -search(pos, ss, -alpha, newDepth, 1, true, 0);
944 // Fail high! Set the boolean variable FailHigh to true, and
945 // re-search the move with a big window. The variable FailHigh is
946 // used for time managment: We try to avoid aborting the search
947 // prematurely during a fail high research.
949 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
956 // Finished searching the move. If AbortSearch is true, the search
957 // was aborted because the user interrupted the search or because we
958 // ran out of time. In this case, the return value of the search cannot
959 // be trusted, and we break out of the loop without updating the best
964 // Remember the node count for this move. The node counts are used to
965 // sort the root moves at the next iteration.
966 rml.set_move_nodes(i, nodes_searched() - nodes);
968 // Remember the beta-cutoff statistics
970 BetaCounter.read(pos.side_to_move(), our, their);
971 rml.set_beta_counters(i, our, their);
973 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
975 if (value <= alpha && i >= MultiPV)
976 rml.set_move_score(i, -VALUE_INFINITE);
979 // PV move or new best move!
982 rml.set_move_score(i, value);
984 TT.extract_pv(pos, ss[0].pv);
985 rml.set_move_pv(i, ss[0].pv);
989 // We record how often the best move has been changed in each
990 // iteration. This information is used for time managment: When
991 // the best move changes frequently, we allocate some more time.
993 BestMoveChangesByIteration[Iteration]++;
995 // Print search information to the standard output
996 std::cout << "info depth " << Iteration
997 << " score " << value_to_string(value)
999 " lowerbound" : ((value <= alpha)? " upperbound" : ""))
1000 << " time " << current_search_time()
1001 << " nodes " << nodes_searched()
1005 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
1006 std::cout << ss[0].pv[j] << " ";
1008 std::cout << std::endl;
1011 LogFile << pretty_pv(pos, current_search_time(), Iteration, nodes_searched(), value, ss[0].pv)
1017 // Reset the global variable Problem to false if the value isn't too
1018 // far below the final value from the last iteration.
1019 if (value > IterationInfo[Iteration - 1].value - NoProblemMargin)
1024 rml.sort_multipv(i);
1025 for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
1028 std::cout << "info multipv " << j + 1
1029 << " score " << value_to_string(rml.get_move_score(j))
1030 << " depth " << ((j <= i)? Iteration : Iteration - 1)
1031 << " time " << current_search_time()
1032 << " nodes " << nodes_searched()
1036 for (k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
1037 std::cout << rml.get_move_pv(j, k) << " ";
1039 std::cout << std::endl;
1041 alpha = rml.get_move_score(Min(i, MultiPV-1));
1043 } // New best move case
1045 assert(alpha >= oldAlpha);
1047 FailLow = (alpha == oldAlpha);
1053 // search_pv() is the main search function for PV nodes.
1055 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta,
1056 Depth depth, int ply, int threadID) {
1058 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1059 assert(beta > alpha && beta <= VALUE_INFINITE);
1060 assert(ply >= 0 && ply < PLY_MAX);
1061 assert(threadID >= 0 && threadID < ActiveThreads);
1064 return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID);
1066 // Initialize, and make an early exit in case of an aborted search,
1067 // an instant draw, maximum ply reached, etc.
1068 init_node(pos, ss, ply, threadID);
1070 // After init_node() that calls poll()
1071 if (AbortSearch || thread_should_stop(threadID))
1079 if (ply >= PLY_MAX - 1)
1080 return evaluate(pos, ei, threadID);
1082 // Mate distance pruning
1083 Value oldAlpha = alpha;
1084 alpha = Max(value_mated_in(ply), alpha);
1085 beta = Min(value_mate_in(ply+1), beta);
1089 // Transposition table lookup. At PV nodes, we don't use the TT for
1090 // pruning, but only for move ordering.
1091 const TTEntry* tte = TT.retrieve(pos.get_key());
1092 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1094 // Go with internal iterative deepening if we don't have a TT move
1095 if (UseIIDAtPVNodes && ttMove == MOVE_NONE && depth >= 5*OnePly)
1097 search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID);
1098 ttMove = ss[ply].pv[ply];
1101 // Initialize a MovePicker object for the current position, and prepare
1102 // to search all moves
1103 Move move, movesSearched[256];
1105 Value value, bestValue = -VALUE_INFINITE;
1106 Color us = pos.side_to_move();
1107 bool isCheck = pos.is_check();
1108 bool mateThreat = pos.has_mate_threat(opposite_color(us));
1110 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1111 Bitboard dcCandidates = mp.discovered_check_candidates();
1113 // Loop through all legal moves until no moves remain or a beta cutoff
1115 while ( alpha < beta
1116 && (move = mp.get_next_move()) != MOVE_NONE
1117 && !thread_should_stop(threadID))
1119 assert(move_is_ok(move));
1121 bool singleReply = (isCheck && mp.number_of_evasions() == 1);
1122 bool moveIsCheck = pos.move_is_check(move, dcCandidates);
1123 bool moveIsCapture = pos.move_is_capture(move);
1125 movesSearched[moveCount++] = ss[ply].currentMove = move;
1127 // Decide the new search depth
1129 Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous);
1130 Depth newDepth = depth - OnePly + ext;
1132 // Make and search the move
1134 pos.do_move(move, st, dcCandidates);
1136 if (moveCount == 1) // The first move in list is the PV
1137 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1140 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1141 // if the move fails high will be re-searched at full depth.
1142 if ( depth >= 3*OnePly
1143 && moveCount >= LMRPVMoves
1146 && !move_is_promotion(move)
1147 && !move_is_castle(move)
1148 && !move_is_killer(move, ss[ply]))
1150 ss[ply].reduction = OnePly;
1151 value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, threadID);
1154 value = alpha + 1; // Just to trigger next condition
1156 if (value > alpha) // Go with full depth non-pv search
1158 ss[ply].reduction = Depth(0);
1159 value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID);
1160 if (value > alpha && value < beta)
1162 // When the search fails high at ply 1 while searching the first
1163 // move at the root, set the flag failHighPly1. This is used for
1164 // time managment: We don't want to stop the search early in
1165 // such cases, because resolving the fail high at ply 1 could
1166 // result in a big drop in score at the root.
1167 if (ply == 1 && RootMoveNumber == 1)
1168 Threads[threadID].failHighPly1 = true;
1170 // A fail high occurred. Re-search at full window (pv search)
1171 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1172 Threads[threadID].failHighPly1 = false;
1176 pos.undo_move(move);
1178 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1181 if (value > bestValue)
1188 if (value == value_mate_in(ply + 1))
1189 ss[ply].mateKiller = move;
1191 // If we are at ply 1, and we are searching the first root move at
1192 // ply 0, set the 'Problem' variable if the score has dropped a lot
1193 // (from the computer's point of view) since the previous iteration.
1196 && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
1201 if ( ActiveThreads > 1
1203 && depth >= MinimumSplitDepth
1205 && idle_thread_exists(threadID)
1207 && !thread_should_stop(threadID)
1208 && split(pos, ss, ply, &alpha, &beta, &bestValue, depth,
1209 &moveCount, &mp, dcCandidates, threadID, true))
1213 // All legal moves have been searched. A special case: If there were
1214 // no legal moves, it must be mate or stalemate.
1216 return (isCheck ? value_mated_in(ply) : VALUE_DRAW);
1218 // If the search is not aborted, update the transposition table,
1219 // history counters, and killer moves.
1220 if (AbortSearch || thread_should_stop(threadID))
1223 if (bestValue <= oldAlpha)
1224 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1226 else if (bestValue >= beta)
1228 BetaCounter.add(pos.side_to_move(), depth, threadID);
1229 Move m = ss[ply].pv[ply];
1230 if (ok_to_history(pos, m)) // Only non capture moves are considered
1232 update_history(pos, m, depth, movesSearched, moveCount);
1233 update_killers(m, ss[ply]);
1235 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m);
1238 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
1244 // search() is the search function for zero-width nodes.
1246 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth,
1247 int ply, bool allowNullmove, int threadID) {
1249 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1250 assert(ply >= 0 && ply < PLY_MAX);
1251 assert(threadID >= 0 && threadID < ActiveThreads);
1254 return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1256 // Initialize, and make an early exit in case of an aborted search,
1257 // an instant draw, maximum ply reached, etc.
1258 init_node(pos, ss, ply, threadID);
1260 // After init_node() that calls poll()
1261 if (AbortSearch || thread_should_stop(threadID))
1269 if (ply >= PLY_MAX - 1)
1270 return evaluate(pos, ei, threadID);
1272 // Mate distance pruning
1273 if (value_mated_in(ply) >= beta)
1276 if (value_mate_in(ply + 1) < beta)
1279 // Transposition table lookup
1280 const TTEntry* tte = TT.retrieve(pos.get_key());
1281 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1283 if (tte && ok_to_use_TT(tte, depth, beta, ply))
1285 ss[ply].currentMove = ttMove; // can be MOVE_NONE
1286 return value_from_tt(tte->value(), ply);
1289 Value approximateEval = quick_evaluate(pos);
1290 bool mateThreat = false;
1291 bool isCheck = pos.is_check();
1297 && !value_is_mate(beta)
1298 && ok_to_do_nullmove(pos)
1299 && approximateEval >= beta - NullMoveMargin)
1301 ss[ply].currentMove = MOVE_NULL;
1304 pos.do_null_move(st);
1305 int R = (depth >= 5 * OnePly ? 4 : 3); // Null move dynamic reduction
1307 Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);
1309 pos.undo_null_move();
1311 if (nullValue >= beta)
1313 if (depth < 6 * OnePly)
1316 // Do zugzwang verification search
1317 Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
1321 // The null move failed low, which means that we may be faced with
1322 // some kind of threat. If the previous move was reduced, check if
1323 // the move that refuted the null move was somehow connected to the
1324 // move which was reduced. If a connection is found, return a fail
1325 // low score (which will cause the reduced move to fail high in the
1326 // parent node, which will trigger a re-search with full depth).
1327 if (nullValue == value_mated_in(ply + 2))
1330 ss[ply].threatMove = ss[ply + 1].currentMove;
1331 if ( depth < ThreatDepth
1332 && ss[ply - 1].reduction
1333 && connected_moves(pos, ss[ply - 1].currentMove, ss[ply].threatMove))
1337 // Null move search not allowed, try razoring
1338 else if ( !value_is_mate(beta)
1339 && depth < RazorDepth
1340 && approximateEval < beta - RazorApprMargins[int(depth) - 2]
1341 && ss[ply - 1].currentMove != MOVE_NULL
1342 && ttMove == MOVE_NONE
1343 && !pos.has_pawn_on_7th(pos.side_to_move()))
1345 Value v = qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1346 if (v < beta - RazorMargins[int(depth) - 2])
1350 // Go with internal iterative deepening if we don't have a TT move
1351 if (UseIIDAtNonPVNodes && ttMove == MOVE_NONE && depth >= 8*OnePly &&
1352 evaluate(pos, ei, threadID) >= beta - IIDMargin)
1354 search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID);
1355 ttMove = ss[ply].pv[ply];
1358 // Initialize a MovePicker object for the current position, and prepare
1359 // to search all moves.
1360 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1362 Move move, movesSearched[256];
1364 Value value, bestValue = -VALUE_INFINITE;
1365 Bitboard dcCandidates = mp.discovered_check_candidates();
1366 Value futilityValue = VALUE_NONE;
1367 bool useFutilityPruning = depth < SelectiveDepth
1370 // Loop through all legal moves until no moves remain or a beta cutoff
1372 while ( bestValue < beta
1373 && (move = mp.get_next_move()) != MOVE_NONE
1374 && !thread_should_stop(threadID))
1376 assert(move_is_ok(move));
1378 bool singleReply = (isCheck && mp.number_of_evasions() == 1);
1379 bool moveIsCheck = pos.move_is_check(move, dcCandidates);
1380 bool moveIsCapture = pos.move_is_capture(move);
1382 movesSearched[moveCount++] = ss[ply].currentMove = move;
1384 // Decide the new search depth
1386 Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous);
1387 Depth newDepth = depth - OnePly + ext;
1390 if ( useFutilityPruning
1393 && !move_is_promotion(move))
1395 // History pruning. See ok_to_prune() definition
1396 if ( moveCount >= 2 + int(depth)
1397 && ok_to_prune(pos, move, ss[ply].threatMove, depth))
1400 // Value based pruning
1401 if (approximateEval < beta)
1403 if (futilityValue == VALUE_NONE)
1404 futilityValue = evaluate(pos, ei, threadID)
1405 + FutilityMargins[int(depth) - 2];
1407 if (futilityValue < beta)
1409 if (futilityValue > bestValue)
1410 bestValue = futilityValue;
1416 // Make and search the move
1418 pos.do_move(move, st, dcCandidates);
1420 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1421 // if the move fails high will be re-searched at full depth.
1422 if ( depth >= 3*OnePly
1423 && moveCount >= LMRNonPVMoves
1426 && !move_is_promotion(move)
1427 && !move_is_castle(move)
1428 && !move_is_killer(move, ss[ply]))
1430 ss[ply].reduction = OnePly;
1431 value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);
1434 value = beta; // Just to trigger next condition
1436 if (value >= beta) // Go with full depth non-pv search
1438 ss[ply].reduction = Depth(0);
1439 value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID);
1441 pos.undo_move(move);
1443 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1446 if (value > bestValue)
1452 if (value == value_mate_in(ply + 1))
1453 ss[ply].mateKiller = move;
1457 if ( ActiveThreads > 1
1459 && depth >= MinimumSplitDepth
1461 && idle_thread_exists(threadID)
1463 && !thread_should_stop(threadID)
1464 && split(pos, ss, ply, &beta, &beta, &bestValue, depth, &moveCount,
1465 &mp, dcCandidates, threadID, false))
1469 // All legal moves have been searched. A special case: If there were
1470 // no legal moves, it must be mate or stalemate.
1472 return (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW);
1474 // If the search is not aborted, update the transposition table,
1475 // history counters, and killer moves.
1476 if (AbortSearch || thread_should_stop(threadID))
1479 if (bestValue < beta)
1480 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1483 BetaCounter.add(pos.side_to_move(), depth, threadID);
1484 Move m = ss[ply].pv[ply];
1485 if (ok_to_history(pos, m)) // Only non capture moves are considered
1487 update_history(pos, m, depth, movesSearched, moveCount);
1488 update_killers(m, ss[ply]);
1490 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m);
1493 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1499 // qsearch() is the quiescence search function, which is called by the main
1500 // search function when the remaining depth is zero (or, to be more precise,
1501 // less than OnePly).
1503 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta,
1504 Depth depth, int ply, int threadID) {
1506 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1507 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1509 assert(ply >= 0 && ply < PLY_MAX);
1510 assert(threadID >= 0 && threadID < ActiveThreads);
1512 // Initialize, and make an early exit in case of an aborted search,
1513 // an instant draw, maximum ply reached, etc.
1514 init_node(pos, ss, ply, threadID);
1516 // After init_node() that calls poll()
1517 if (AbortSearch || thread_should_stop(threadID))
1523 // Transposition table lookup, only when not in PV
1524 TTEntry* tte = NULL;
1525 bool pvNode = (beta - alpha != 1);
1528 tte = TT.retrieve(pos.get_key());
1529 if (tte && ok_to_use_TT(tte, depth, beta, ply))
1531 assert(tte->type() != VALUE_TYPE_EVAL);
1533 return value_from_tt(tte->value(), ply);
1536 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1538 // Evaluate the position statically
1541 bool isCheck = pos.is_check();
1542 ei.futilityMargin = Value(0); // Manually initialize futilityMargin
1545 staticValue = -VALUE_INFINITE;
1547 else if (tte && (tte->type() & VALUE_TYPE_EVAL))
1549 // Use the cached evaluation score if possible
1550 assert(ei.futilityMargin == Value(0));
1552 staticValue = tte->value();
1555 staticValue = evaluate(pos, ei, threadID);
1557 if (ply == PLY_MAX - 1)
1558 return evaluate(pos, ei, threadID);
1560 // Initialize "stand pat score", and return it immediately if it is
1562 Value bestValue = staticValue;
1564 if (bestValue >= beta)
1566 // Store the score to avoid a future costly evaluation() call
1567 if (!isCheck && !tte && ei.futilityMargin == 0)
1568 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EV_LO, Depth(-127*OnePly), MOVE_NONE);
1573 if (bestValue > alpha)
1576 // Initialize a MovePicker object for the current position, and prepare
1577 // to search the moves. Because the depth is <= 0 here, only captures,
1578 // queen promotions and checks (only if depth == 0) will be generated.
1579 MovePicker mp = MovePicker(pos, ttMove, depth, H);
1582 Bitboard dcCandidates = mp.discovered_check_candidates();
1583 Color us = pos.side_to_move();
1584 bool enoughMaterial = pos.non_pawn_material(us) > RookValueMidgame;
1586 // Loop through the moves until no moves remain or a beta cutoff
1588 while ( alpha < beta
1589 && (move = mp.get_next_move()) != MOVE_NONE)
1591 assert(move_is_ok(move));
1594 ss[ply].currentMove = move;
1600 && !move_is_promotion(move)
1601 && !pos.move_is_check(move, dcCandidates)
1602 && !pos.move_is_passed_pawn_push(move))
1604 Value futilityValue = staticValue
1605 + Max(pos.midgame_value_of_piece_on(move_to(move)),
1606 pos.endgame_value_of_piece_on(move_to(move)))
1607 + (move_is_ep(move) ? PawnValueEndgame : Value(0))
1609 + ei.futilityMargin;
1611 if (futilityValue < alpha)
1613 if (futilityValue > bestValue)
1614 bestValue = futilityValue;
1619 // Don't search captures and checks with negative SEE values
1621 && !move_is_promotion(move)
1622 && pos.see_sign(move) < 0)
1625 // Make and search the move.
1627 pos.do_move(move, st, dcCandidates);
1628 Value value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID);
1629 pos.undo_move(move);
1631 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1634 if (value > bestValue)
1645 // All legal moves have been searched. A special case: If we're in check
1646 // and no legal moves were found, it is checkmate.
1647 if (pos.is_check() && moveCount == 0) // Mate!
1648 return value_mated_in(ply);
1650 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1652 // Update transposition table
1653 Move m = ss[ply].pv[ply];
1656 // If bestValue isn't changed it means it is still the static evaluation of
1657 // the node, so keep this info to avoid a future costly evaluation() call.
1658 ValueType type = (bestValue == staticValue && !ei.futilityMargin ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER);
1659 Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
1661 if (bestValue < beta)
1662 TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE);
1664 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, m);
1667 // Update killers only for good check moves
1668 if (alpha >= beta && ok_to_history(pos, m)) // Only non capture moves are considered
1669 update_killers(m, ss[ply]);
1675 // sp_search() is used to search from a split point. This function is called
1676 // by each thread working at the split point. It is similar to the normal
1677 // search() function, but simpler. Because we have already probed the hash
1678 // table, done a null move search, and searched the first move before
1679 // splitting, we don't have to repeat all this work in sp_search(). We
1680 // also don't need to store anything to the hash table here: This is taken
1681 // care of after we return from the split point.
1683 void sp_search(SplitPoint* sp, int threadID) {
1685 assert(threadID >= 0 && threadID < ActiveThreads);
1686 assert(ActiveThreads > 1);
1688 Position pos = Position(sp->pos);
1689 SearchStack* ss = sp->sstack[threadID];
1692 bool isCheck = pos.is_check();
1693 bool useFutilityPruning = sp->depth < SelectiveDepth
1696 while ( sp->bestValue < sp->beta
1697 && !thread_should_stop(threadID)
1698 && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE)
1700 assert(move_is_ok(move));
1702 bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates);
1703 bool moveIsCapture = pos.move_is_capture(move);
1705 lock_grab(&(sp->lock));
1706 int moveCount = ++sp->moves;
1707 lock_release(&(sp->lock));
1709 ss[sp->ply].currentMove = move;
1711 // Decide the new search depth.
1713 Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, false, false, &dangerous);
1714 Depth newDepth = sp->depth - OnePly + ext;
1717 if ( useFutilityPruning
1720 && !move_is_promotion(move)
1721 && moveCount >= 2 + int(sp->depth)
1722 && ok_to_prune(pos, move, ss[sp->ply].threatMove, sp->depth))
1725 // Make and search the move.
1727 pos.do_move(move, st, sp->dcCandidates);
1729 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1730 // if the move fails high will be re-searched at full depth.
1732 && moveCount >= LMRNonPVMoves
1734 && !move_is_promotion(move)
1735 && !move_is_castle(move)
1736 && !move_is_killer(move, ss[sp->ply]))
1738 ss[sp->ply].reduction = OnePly;
1739 value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, true, threadID);
1742 value = sp->beta; // Just to trigger next condition
1744 if (value >= sp->beta) // Go with full depth non-pv search
1746 ss[sp->ply].reduction = Depth(0);
1747 value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID);
1749 pos.undo_move(move);
1751 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1753 if (thread_should_stop(threadID))
1757 lock_grab(&(sp->lock));
1758 if (value > sp->bestValue && !thread_should_stop(threadID))
1760 sp->bestValue = value;
1761 if (sp->bestValue >= sp->beta)
1763 sp_update_pv(sp->parentSstack, ss, sp->ply);
1764 for (int i = 0; i < ActiveThreads; i++)
1765 if (i != threadID && (i == sp->master || sp->slaves[i]))
1766 Threads[i].stop = true;
1768 sp->finished = true;
1771 lock_release(&(sp->lock));
1774 lock_grab(&(sp->lock));
1776 // If this is the master thread and we have been asked to stop because of
1777 // a beta cutoff higher up in the tree, stop all slave threads.
1778 if (sp->master == threadID && thread_should_stop(threadID))
1779 for (int i = 0; i < ActiveThreads; i++)
1781 Threads[i].stop = true;
1784 sp->slaves[threadID] = 0;
1786 lock_release(&(sp->lock));
1790 // sp_search_pv() is used to search from a PV split point. This function
1791 // is called by each thread working at the split point. It is similar to
1792 // the normal search_pv() function, but simpler. Because we have already
1793 // probed the hash table and searched the first move before splitting, we
1794 // don't have to repeat all this work in sp_search_pv(). We also don't
1795 // need to store anything to the hash table here: This is taken care of
1796 // after we return from the split point.
1798 void sp_search_pv(SplitPoint* sp, int threadID) {
1800 assert(threadID >= 0 && threadID < ActiveThreads);
1801 assert(ActiveThreads > 1);
1803 Position pos = Position(sp->pos);
1804 SearchStack* ss = sp->sstack[threadID];
1808 while ( sp->alpha < sp->beta
1809 && !thread_should_stop(threadID)
1810 && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE)
1812 bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates);
1813 bool moveIsCapture = pos.move_is_capture(move);
1815 assert(move_is_ok(move));
1817 lock_grab(&(sp->lock));
1818 int moveCount = ++sp->moves;
1819 lock_release(&(sp->lock));
1821 ss[sp->ply].currentMove = move;
1823 // Decide the new search depth.
1825 Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, false, false, &dangerous);
1826 Depth newDepth = sp->depth - OnePly + ext;
1828 // Make and search the move.
1830 pos.do_move(move, st, sp->dcCandidates);
1832 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1833 // if the move fails high will be re-searched at full depth.
1835 && moveCount >= LMRPVMoves
1837 && !move_is_promotion(move)
1838 && !move_is_castle(move)
1839 && !move_is_killer(move, ss[sp->ply]))
1841 ss[sp->ply].reduction = OnePly;
1842 value = -search(pos, ss, -sp->alpha, newDepth - OnePly, sp->ply+1, true, threadID);
1845 value = sp->alpha + 1; // Just to trigger next condition
1847 if (value > sp->alpha) // Go with full depth non-pv search
1849 ss[sp->ply].reduction = Depth(0);
1850 value = -search(pos, ss, -sp->alpha, newDepth, sp->ply+1, true, threadID);
1852 if (value > sp->alpha && value < sp->beta)
1854 // When the search fails high at ply 1 while searching the first
1855 // move at the root, set the flag failHighPly1. This is used for
1856 // time managment: We don't want to stop the search early in
1857 // such cases, because resolving the fail high at ply 1 could
1858 // result in a big drop in score at the root.
1859 if (sp->ply == 1 && RootMoveNumber == 1)
1860 Threads[threadID].failHighPly1 = true;
1862 value = -search_pv(pos, ss, -sp->beta, -sp->alpha, newDepth, sp->ply+1, threadID);
1863 Threads[threadID].failHighPly1 = false;
1866 pos.undo_move(move);
1868 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1870 if (thread_should_stop(threadID))
1874 lock_grab(&(sp->lock));
1875 if (value > sp->bestValue && !thread_should_stop(threadID))
1877 sp->bestValue = value;
1878 if (value > sp->alpha)
1881 sp_update_pv(sp->parentSstack, ss, sp->ply);
1882 if (value == value_mate_in(sp->ply + 1))
1883 ss[sp->ply].mateKiller = move;
1885 if (value >= sp->beta)
1887 for (int i = 0; i < ActiveThreads; i++)
1888 if (i != threadID && (i == sp->master || sp->slaves[i]))
1889 Threads[i].stop = true;
1891 sp->finished = true;
1894 // If we are at ply 1, and we are searching the first root move at
1895 // ply 0, set the 'Problem' variable if the score has dropped a lot
1896 // (from the computer's point of view) since the previous iteration.
1899 && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
1902 lock_release(&(sp->lock));
1905 lock_grab(&(sp->lock));
1907 // If this is the master thread and we have been asked to stop because of
1908 // a beta cutoff higher up in the tree, stop all slave threads.
1909 if (sp->master == threadID && thread_should_stop(threadID))
1910 for (int i = 0; i < ActiveThreads; i++)
1912 Threads[i].stop = true;
1915 sp->slaves[threadID] = 0;
1917 lock_release(&(sp->lock));
1920 /// The BetaCounterType class
1922 BetaCounterType::BetaCounterType() { clear(); }
1924 void BetaCounterType::clear() {
1926 for (int i = 0; i < THREAD_MAX; i++)
1927 Threads[i].betaCutOffs[WHITE] = Threads[i].betaCutOffs[BLACK] = 0ULL;
1930 void BetaCounterType::add(Color us, Depth d, int threadID) {
1932 // Weighted count based on depth
1933 Threads[threadID].betaCutOffs[us] += unsigned(d);
1936 void BetaCounterType::read(Color us, int64_t& our, int64_t& their) {
1939 for (int i = 0; i < THREAD_MAX; i++)
1941 our += Threads[i].betaCutOffs[us];
1942 their += Threads[i].betaCutOffs[opposite_color(us)];
1947 /// The RootMove class
1951 RootMove::RootMove() {
1952 nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL;
1955 // RootMove::operator<() is the comparison function used when
1956 // sorting the moves. A move m1 is considered to be better
1957 // than a move m2 if it has a higher score, or if the moves
1958 // have equal score but m1 has the higher node count.
1960 bool RootMove::operator<(const RootMove& m) {
1962 if (score != m.score)
1963 return (score < m.score);
1965 return theirBeta <= m.theirBeta;
1968 /// The RootMoveList class
1972 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
1974 MoveStack mlist[MaxRootMoves];
1975 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
1977 // Generate all legal moves
1978 MoveStack* last = generate_moves(pos, mlist);
1980 // Add each move to the moves[] array
1981 for (MoveStack* cur = mlist; cur != last; cur++)
1983 bool includeMove = includeAllMoves;
1985 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
1986 includeMove = (searchMoves[k] == cur->move);
1991 // Find a quick score for the move
1993 SearchStack ss[PLY_MAX_PLUS_2];
1995 moves[count].move = cur->move;
1996 pos.do_move(moves[count].move, st);
1997 moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0);
1998 pos.undo_move(moves[count].move);
1999 moves[count].pv[0] = moves[count].move;
2000 moves[count].pv[1] = MOVE_NONE; // FIXME
2007 // Simple accessor methods for the RootMoveList class
2009 inline Move RootMoveList::get_move(int moveNum) const {
2010 return moves[moveNum].move;
2013 inline Value RootMoveList::get_move_score(int moveNum) const {
2014 return moves[moveNum].score;
2017 inline void RootMoveList::set_move_score(int moveNum, Value score) {
2018 moves[moveNum].score = score;
2021 inline void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
2022 moves[moveNum].nodes = nodes;
2023 moves[moveNum].cumulativeNodes += nodes;
2026 inline void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
2027 moves[moveNum].ourBeta = our;
2028 moves[moveNum].theirBeta = their;
2031 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
2033 for(j = 0; pv[j] != MOVE_NONE; j++)
2034 moves[moveNum].pv[j] = pv[j];
2035 moves[moveNum].pv[j] = MOVE_NONE;
2038 inline Move RootMoveList::get_move_pv(int moveNum, int i) const {
2039 return moves[moveNum].pv[i];
2042 inline int64_t RootMoveList::get_move_cumulative_nodes(int moveNum) const {
2043 return moves[moveNum].cumulativeNodes;
2046 inline int RootMoveList::move_count() const {
2051 // RootMoveList::scan_for_easy_move() is called at the end of the first
2052 // iteration, and is used to detect an "easy move", i.e. a move which appears
2053 // to be much bester than all the rest. If an easy move is found, the move
2054 // is returned, otherwise the function returns MOVE_NONE. It is very
2055 // important that this function is called at the right moment: The code
2056 // assumes that the first iteration has been completed and the moves have
2057 // been sorted. This is done in RootMoveList c'tor.
2059 Move RootMoveList::scan_for_easy_move() const {
2066 // moves are sorted so just consider the best and the second one
2067 if (get_move_score(0) > get_move_score(1) + EasyMoveMargin)
2073 // RootMoveList::sort() sorts the root move list at the beginning of a new
2076 inline void RootMoveList::sort() {
2078 sort_multipv(count - 1); // all items
2082 // RootMoveList::sort_multipv() sorts the first few moves in the root move
2083 // list by their scores and depths. It is used to order the different PVs
2084 // correctly in MultiPV mode.
2086 void RootMoveList::sort_multipv(int n) {
2088 for (int i = 1; i <= n; i++)
2090 RootMove rm = moves[i];
2092 for (j = i; j > 0 && moves[j-1] < rm; j--)
2093 moves[j] = moves[j-1];
2099 // init_node() is called at the beginning of all the search functions
2100 // (search(), search_pv(), qsearch(), and so on) and initializes the search
2101 // stack object corresponding to the current node. Once every
2102 // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
2103 // for user input and checks whether it is time to stop the search.
2105 void init_node(const Position& pos, SearchStack ss[], int ply, int threadID) {
2107 assert(ply >= 0 && ply < PLY_MAX);
2108 assert(threadID >= 0 && threadID < ActiveThreads);
2110 if (Slowdown && Iteration >= 3)
2113 Threads[threadID].nodes++;
2118 if (NodesSincePoll >= NodesBetweenPolls)
2125 ss[ply+2].initKillers();
2127 if (Threads[threadID].printCurrentLine)
2128 print_current_line(ss, ply, threadID);
2132 // update_pv() is called whenever a search returns a value > alpha. It
2133 // updates the PV in the SearchStack object corresponding to the current
2136 void update_pv(SearchStack ss[], int ply) {
2137 assert(ply >= 0 && ply < PLY_MAX);
2139 ss[ply].pv[ply] = ss[ply].currentMove;
2141 for(p = ply + 1; ss[ply+1].pv[p] != MOVE_NONE; p++)
2142 ss[ply].pv[p] = ss[ply+1].pv[p];
2143 ss[ply].pv[p] = MOVE_NONE;
2147 // sp_update_pv() is a variant of update_pv for use at split points. The
2148 // difference between the two functions is that sp_update_pv also updates
2149 // the PV at the parent node.
2151 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply) {
2152 assert(ply >= 0 && ply < PLY_MAX);
2154 ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
2156 for(p = ply + 1; ss[ply+1].pv[p] != MOVE_NONE; p++)
2157 ss[ply].pv[p] = pss[ply].pv[p] = ss[ply+1].pv[p];
2158 ss[ply].pv[p] = pss[ply].pv[p] = MOVE_NONE;
2162 // connected_moves() tests whether two moves are 'connected' in the sense
2163 // that the first move somehow made the second move possible (for instance
2164 // if the moving piece is the same in both moves). The first move is
2165 // assumed to be the move that was made to reach the current position, while
2166 // the second move is assumed to be a move from the current position.
2168 bool connected_moves(const Position& pos, Move m1, Move m2) {
2170 Square f1, t1, f2, t2;
2173 assert(move_is_ok(m1));
2174 assert(move_is_ok(m2));
2176 if (m2 == MOVE_NONE)
2179 // Case 1: The moving piece is the same in both moves
2185 // Case 2: The destination square for m2 was vacated by m1
2191 // Case 3: Moving through the vacated square
2192 if ( piece_is_slider(pos.piece_on(f2))
2193 && bit_is_set(squares_between(f2, t2), f1))
2196 // Case 4: The destination square for m2 is attacked by the moving piece in m1
2197 p = pos.piece_on(t1);
2198 if (bit_is_set(pos.attacks_from(p, t1), t2))
2201 // Case 5: Discovered check, checking piece is the piece moved in m1
2202 if ( piece_is_slider(p)
2203 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
2204 && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
2206 Bitboard occ = pos.occupied_squares();
2207 Color us = pos.side_to_move();
2208 Square ksq = pos.king_square(us);
2209 clear_bit(&occ, f2);
2210 if (type_of_piece(p) == BISHOP)
2212 if (bit_is_set(bishop_attacks_bb(ksq, occ), t1))
2215 else if (type_of_piece(p) == ROOK)
2217 if (bit_is_set(rook_attacks_bb(ksq, occ), t1))
2222 assert(type_of_piece(p) == QUEEN);
2223 if (bit_is_set(queen_attacks_bb(ksq, occ), t1))
2231 // value_is_mate() checks if the given value is a mate one
2232 // eventually compensated for the ply.
2234 bool value_is_mate(Value value) {
2236 assert(abs(value) <= VALUE_INFINITE);
2238 return value <= value_mated_in(PLY_MAX)
2239 || value >= value_mate_in(PLY_MAX);
2243 // move_is_killer() checks if the given move is among the
2244 // killer moves of that ply.
2246 bool move_is_killer(Move m, const SearchStack& ss) {
2248 const Move* k = ss.killers;
2249 for (int i = 0; i < KILLER_MAX; i++, k++)
2257 // extension() decides whether a move should be searched with normal depth,
2258 // or with extended depth. Certain classes of moves (checking moves, in
2259 // particular) are searched with bigger depth than ordinary moves and in
2260 // any case are marked as 'dangerous'. Note that also if a move is not
2261 // extended, as example because the corresponding UCI option is set to zero,
2262 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
2264 Depth extension(const Position& pos, Move m, bool pvNode, bool capture, bool check,
2265 bool singleReply, bool mateThreat, bool* dangerous) {
2267 assert(m != MOVE_NONE);
2269 Depth result = Depth(0);
2270 *dangerous = check | singleReply | mateThreat;
2275 result += CheckExtension[pvNode];
2278 result += SingleReplyExtension[pvNode];
2281 result += MateThreatExtension[pvNode];
2284 if (pos.type_of_piece_on(move_from(m)) == PAWN)
2286 Color c = pos.side_to_move();
2287 if (relative_rank(c, move_to(m)) == RANK_7)
2289 result += PawnPushTo7thExtension[pvNode];
2292 if (pos.pawn_is_passed(c, move_to(m)))
2294 result += PassedPawnExtension[pvNode];
2300 && pos.type_of_piece_on(move_to(m)) != PAWN
2301 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
2302 - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))
2303 && !move_is_promotion(m)
2306 result += PawnEndgameExtension[pvNode];
2312 && pos.type_of_piece_on(move_to(m)) != PAWN
2313 && pos.see_sign(m) >= 0)
2319 return Min(result, OnePly);
2323 // ok_to_do_nullmove() looks at the current position and decides whether
2324 // doing a 'null move' should be allowed. In order to avoid zugzwang
2325 // problems, null moves are not allowed when the side to move has very
2326 // little material left. Currently, the test is a bit too simple: Null
2327 // moves are avoided only when the side to move has only pawns left. It's
2328 // probably a good idea to avoid null moves in at least some more
2329 // complicated endgames, e.g. KQ vs KR. FIXME
2331 bool ok_to_do_nullmove(const Position& pos) {
2333 return pos.non_pawn_material(pos.side_to_move()) != Value(0);
2337 // ok_to_prune() tests whether it is safe to forward prune a move. Only
2338 // non-tactical moves late in the move list close to the leaves are
2339 // candidates for pruning.
2341 bool ok_to_prune(const Position& pos, Move m, Move threat, Depth d) {
2343 assert(move_is_ok(m));
2344 assert(threat == MOVE_NONE || move_is_ok(threat));
2345 assert(!move_is_promotion(m));
2346 assert(!pos.move_is_check(m));
2347 assert(!pos.move_is_capture(m));
2348 assert(!pos.move_is_passed_pawn_push(m));
2349 assert(d >= OnePly);
2351 Square mfrom, mto, tfrom, tto;
2353 mfrom = move_from(m);
2355 tfrom = move_from(threat);
2356 tto = move_to(threat);
2358 // Case 1: Castling moves are never pruned
2359 if (move_is_castle(m))
2362 // Case 2: Don't prune moves which move the threatened piece
2363 if (!PruneEscapeMoves && threat != MOVE_NONE && mfrom == tto)
2366 // Case 3: If the threatened piece has value less than or equal to the
2367 // value of the threatening piece, don't prune move which defend it.
2368 if ( !PruneDefendingMoves
2369 && threat != MOVE_NONE
2370 && pos.move_is_capture(threat)
2371 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
2372 || pos.type_of_piece_on(tfrom) == KING)
2373 && pos.move_attacks_square(m, tto))
2376 // Case 4: Don't prune moves with good history
2377 if (!H.ok_to_prune(pos.piece_on(mfrom), mto, d))
2380 // Case 5: If the moving piece in the threatened move is a slider, don't
2381 // prune safe moves which block its ray.
2382 if ( !PruneBlockingMoves
2383 && threat != MOVE_NONE
2384 && piece_is_slider(pos.piece_on(tfrom))
2385 && bit_is_set(squares_between(tfrom, tto), mto)
2386 && pos.see_sign(m) >= 0)
2393 // ok_to_use_TT() returns true if a transposition table score
2394 // can be used at a given point in search.
2396 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
2398 Value v = value_from_tt(tte->value(), ply);
2400 return ( tte->depth() >= depth
2401 || v >= Max(value_mate_in(100), beta)
2402 || v < Min(value_mated_in(100), beta))
2404 && ( (is_lower_bound(tte->type()) && v >= beta)
2405 || (is_upper_bound(tte->type()) && v < beta));
2409 // ok_to_history() returns true if a move m can be stored
2410 // in history. Should be a non capturing move nor a promotion.
2412 bool ok_to_history(const Position& pos, Move m) {
2414 return !pos.move_is_capture(m) && !move_is_promotion(m);
2418 // update_history() registers a good move that produced a beta-cutoff
2419 // in history and marks as failures all the other moves of that ply.
2421 void update_history(const Position& pos, Move m, Depth depth,
2422 Move movesSearched[], int moveCount) {
2424 H.success(pos.piece_on(move_from(m)), move_to(m), depth);
2426 for (int i = 0; i < moveCount - 1; i++)
2428 assert(m != movesSearched[i]);
2429 if (ok_to_history(pos, movesSearched[i]))
2430 H.failure(pos.piece_on(move_from(movesSearched[i])), move_to(movesSearched[i]));
2435 // update_killers() add a good move that produced a beta-cutoff
2436 // among the killer moves of that ply.
2438 void update_killers(Move m, SearchStack& ss) {
2440 if (m == ss.killers[0])
2443 for (int i = KILLER_MAX - 1; i > 0; i--)
2444 ss.killers[i] = ss.killers[i - 1];
2450 // slowdown() simply wastes CPU cycles doing nothing useful. It's used
2451 // in strength handicap mode.
2453 void slowdown(const Position &pos) {
2456 for (i = 0; i < n; i++) {
2457 Square s = Square(i&63);
2458 if (count_1s(pos.attackers_to(s)) > 63)
2459 std::cout << "This can't happen, but I put this string here anyway, in order to "
2460 "prevent the compiler from optimizing away the useless computation." << std::endl;
2465 // fail_high_ply_1() checks if some thread is currently resolving a fail
2466 // high at ply 1 at the node below the first root node. This information
2467 // is used for time managment.
2469 bool fail_high_ply_1() {
2471 for(int i = 0; i < ActiveThreads; i++)
2472 if (Threads[i].failHighPly1)
2479 // current_search_time() returns the number of milliseconds which have passed
2480 // since the beginning of the current search.
2482 int current_search_time() {
2483 return get_system_time() - SearchStartTime;
2487 // nps() computes the current nodes/second count.
2490 int t = current_search_time();
2491 return (t > 0)? int((nodes_searched() * 1000) / t) : 0;
2495 // poll() performs two different functions: It polls for user input, and it
2496 // looks at the time consumed so far and decides if it's time to abort the
2501 static int lastInfoTime;
2502 int t = current_search_time();
2507 // We are line oriented, don't read single chars
2508 std::string command;
2509 if (!std::getline(std::cin, command))
2512 if (command == "quit")
2515 PonderSearch = false;
2519 else if (command == "stop")
2522 PonderSearch = false;
2524 else if (command == "ponderhit")
2527 // Print search information
2531 else if (lastInfoTime > t)
2532 // HACK: Must be a new search where we searched less than
2533 // NodesBetweenPolls nodes during the first second of search.
2536 else if (t - lastInfoTime >= 1000)
2543 if (dbg_show_hit_rate)
2544 dbg_print_hit_rate();
2546 std::cout << "info nodes " << nodes_searched() << " nps " << nps()
2547 << " time " << t << " hashfull " << TT.full() << std::endl;
2548 lock_release(&IOLock);
2549 if (ShowCurrentLine)
2550 Threads[0].printCurrentLine = true;
2552 // Should we stop the search?
2556 bool overTime = t > AbsoluteMaxSearchTime
2557 || (RootMoveNumber == 1 && t > MaxSearchTime + ExtraSearchTime && !FailLow) //FIXME: We are not checking any problem flags, BUG?
2558 || ( !FailHigh && !FailLow && !fail_high_ply_1() && !Problem
2559 && t > 6*(MaxSearchTime + ExtraSearchTime));
2561 if ( (Iteration >= 3 && (!InfiniteSearch && overTime))
2562 || (ExactMaxTime && t >= ExactMaxTime)
2563 || (Iteration >= 3 && MaxNodes && nodes_searched() >= MaxNodes))
2568 // ponderhit() is called when the program is pondering (i.e. thinking while
2569 // it's the opponent's turn to move) in order to let the engine know that
2570 // it correctly predicted the opponent's move.
2574 int t = current_search_time();
2575 PonderSearch = false;
2576 if (Iteration >= 3 &&
2577 (!InfiniteSearch && (StopOnPonderhit ||
2578 t > AbsoluteMaxSearchTime ||
2579 (RootMoveNumber == 1 &&
2580 t > MaxSearchTime + ExtraSearchTime && !FailLow) ||
2581 (!FailHigh && !FailLow && !fail_high_ply_1() && !Problem &&
2582 t > 6*(MaxSearchTime + ExtraSearchTime)))))
2587 // print_current_line() prints the current line of search for a given
2588 // thread. Called when the UCI option UCI_ShowCurrLine is 'true'.
2590 void print_current_line(SearchStack ss[], int ply, int threadID) {
2592 assert(ply >= 0 && ply < PLY_MAX);
2593 assert(threadID >= 0 && threadID < ActiveThreads);
2595 if (!Threads[threadID].idle)
2598 std::cout << "info currline " << (threadID + 1);
2599 for (int p = 0; p < ply; p++)
2600 std::cout << " " << ss[p].currentMove;
2602 std::cout << std::endl;
2603 lock_release(&IOLock);
2605 Threads[threadID].printCurrentLine = false;
2606 if (threadID + 1 < ActiveThreads)
2607 Threads[threadID + 1].printCurrentLine = true;
2611 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2612 // while the program is pondering. The point is to work around a wrinkle in
2613 // the UCI protocol: When pondering, the engine is not allowed to give a
2614 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2615 // We simply wait here until one of these commands is sent, and return,
2616 // after which the bestmove and pondermove will be printed (in id_loop()).
2618 void wait_for_stop_or_ponderhit() {
2620 std::string command;
2624 if (!std::getline(std::cin, command))
2627 if (command == "quit")
2632 else if (command == "ponderhit" || command == "stop")
2638 // idle_loop() is where the threads are parked when they have no work to do.
2639 // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint
2640 // object for which the current thread is the master.
2642 void idle_loop(int threadID, SplitPoint* waitSp) {
2643 assert(threadID >= 0 && threadID < THREAD_MAX);
2645 Threads[threadID].running = true;
2648 if(AllThreadsShouldExit && threadID != 0)
2651 // If we are not thinking, wait for a condition to be signaled instead
2652 // of wasting CPU time polling for work:
2653 while(threadID != 0 && (Idle || threadID >= ActiveThreads)) {
2654 #if !defined(_MSC_VER)
2655 pthread_mutex_lock(&WaitLock);
2656 if(Idle || threadID >= ActiveThreads)
2657 pthread_cond_wait(&WaitCond, &WaitLock);
2658 pthread_mutex_unlock(&WaitLock);
2660 WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2664 // If this thread has been assigned work, launch a search
2665 if(Threads[threadID].workIsWaiting) {
2666 Threads[threadID].workIsWaiting = false;
2667 if(Threads[threadID].splitPoint->pvNode)
2668 sp_search_pv(Threads[threadID].splitPoint, threadID);
2670 sp_search(Threads[threadID].splitPoint, threadID);
2671 Threads[threadID].idle = true;
2674 // If this thread is the master of a split point and all threads have
2675 // finished their work at this split point, return from the idle loop.
2676 if(waitSp != NULL && waitSp->cpus == 0)
2680 Threads[threadID].running = false;
2684 // init_split_point_stack() is called during program initialization, and
2685 // initializes all split point objects.
2687 void init_split_point_stack() {
2688 for(int i = 0; i < THREAD_MAX; i++)
2689 for(int j = 0; j < MaxActiveSplitPoints; j++) {
2690 SplitPointStack[i][j].parent = NULL;
2691 lock_init(&(SplitPointStack[i][j].lock), NULL);
2696 // destroy_split_point_stack() is called when the program exits, and
2697 // destroys all locks in the precomputed split point objects.
2699 void destroy_split_point_stack() {
2700 for(int i = 0; i < THREAD_MAX; i++)
2701 for(int j = 0; j < MaxActiveSplitPoints; j++)
2702 lock_destroy(&(SplitPointStack[i][j].lock));
2706 // thread_should_stop() checks whether the thread with a given threadID has
2707 // been asked to stop, directly or indirectly. This can happen if a beta
2708 // cutoff has occured in thre thread's currently active split point, or in
2709 // some ancestor of the current split point.
2711 bool thread_should_stop(int threadID) {
2712 assert(threadID >= 0 && threadID < ActiveThreads);
2716 if(Threads[threadID].stop)
2718 if(ActiveThreads <= 2)
2720 for(sp = Threads[threadID].splitPoint; sp != NULL; sp = sp->parent)
2722 Threads[threadID].stop = true;
2729 // thread_is_available() checks whether the thread with threadID "slave" is
2730 // available to help the thread with threadID "master" at a split point. An
2731 // obvious requirement is that "slave" must be idle. With more than two
2732 // threads, this is not by itself sufficient: If "slave" is the master of
2733 // some active split point, it is only available as a slave to the other
2734 // threads which are busy searching the split point at the top of "slave"'s
2735 // split point stack (the "helpful master concept" in YBWC terminology).
2737 bool thread_is_available(int slave, int master) {
2738 assert(slave >= 0 && slave < ActiveThreads);
2739 assert(master >= 0 && master < ActiveThreads);
2740 assert(ActiveThreads > 1);
2742 if(!Threads[slave].idle || slave == master)
2745 if(Threads[slave].activeSplitPoints == 0)
2746 // No active split points means that the thread is available as a slave
2747 // for any other thread.
2750 if(ActiveThreads == 2)
2753 // Apply the "helpful master" concept if possible.
2754 if(SplitPointStack[slave][Threads[slave].activeSplitPoints-1].slaves[master])
2761 // idle_thread_exists() tries to find an idle thread which is available as
2762 // a slave for the thread with threadID "master".
2764 bool idle_thread_exists(int master) {
2765 assert(master >= 0 && master < ActiveThreads);
2766 assert(ActiveThreads > 1);
2768 for(int i = 0; i < ActiveThreads; i++)
2769 if(thread_is_available(i, master))
2775 // split() does the actual work of distributing the work at a node between
2776 // several threads at PV nodes. If it does not succeed in splitting the
2777 // node (because no idle threads are available, or because we have no unused
2778 // split point objects), the function immediately returns false. If
2779 // splitting is possible, a SplitPoint object is initialized with all the
2780 // data that must be copied to the helper threads (the current position and
2781 // search stack, alpha, beta, the search depth, etc.), and we tell our
2782 // helper threads that they have been assigned work. This will cause them
2783 // to instantly leave their idle loops and call sp_search_pv(). When all
2784 // threads have returned from sp_search_pv (or, equivalently, when
2785 // splitPoint->cpus becomes 0), split() returns true.
2787 bool split(const Position& p, SearchStack* sstck, int ply,
2788 Value* alpha, Value* beta, Value* bestValue, Depth depth, int* moves,
2789 MovePicker* mp, Bitboard dcCandidates, int master, bool pvNode) {
2792 assert(sstck != NULL);
2793 assert(ply >= 0 && ply < PLY_MAX);
2794 assert(*bestValue >= -VALUE_INFINITE && *bestValue <= *alpha);
2795 assert(!pvNode || *alpha < *beta);
2796 assert(*beta <= VALUE_INFINITE);
2797 assert(depth > Depth(0));
2798 assert(master >= 0 && master < ActiveThreads);
2799 assert(ActiveThreads > 1);
2801 SplitPoint* splitPoint;
2806 // If no other thread is available to help us, or if we have too many
2807 // active split points, don't split.
2808 if(!idle_thread_exists(master) ||
2809 Threads[master].activeSplitPoints >= MaxActiveSplitPoints) {
2810 lock_release(&MPLock);
2814 // Pick the next available split point object from the split point stack
2815 splitPoint = SplitPointStack[master] + Threads[master].activeSplitPoints;
2816 Threads[master].activeSplitPoints++;
2818 // Initialize the split point object
2819 splitPoint->parent = Threads[master].splitPoint;
2820 splitPoint->finished = false;
2821 splitPoint->ply = ply;
2822 splitPoint->depth = depth;
2823 splitPoint->alpha = pvNode? *alpha : (*beta - 1);
2824 splitPoint->beta = *beta;
2825 splitPoint->pvNode = pvNode;
2826 splitPoint->dcCandidates = dcCandidates;
2827 splitPoint->bestValue = *bestValue;
2828 splitPoint->master = master;
2829 splitPoint->mp = mp;
2830 splitPoint->moves = *moves;
2831 splitPoint->cpus = 1;
2832 splitPoint->pos.copy(p);
2833 splitPoint->parentSstack = sstck;
2834 for(i = 0; i < ActiveThreads; i++)
2835 splitPoint->slaves[i] = 0;
2837 // Copy the current position and the search stack to the master thread
2838 memcpy(splitPoint->sstack[master], sstck, (ply+1)*sizeof(SearchStack));
2839 Threads[master].splitPoint = splitPoint;
2841 // Make copies of the current position and search stack for each thread
2842 for(i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint;
2844 if(thread_is_available(i, master)) {
2845 memcpy(splitPoint->sstack[i], sstck, (ply+1)*sizeof(SearchStack));
2846 Threads[i].splitPoint = splitPoint;
2847 splitPoint->slaves[i] = 1;
2851 // Tell the threads that they have work to do. This will make them leave
2853 for(i = 0; i < ActiveThreads; i++)
2854 if(i == master || splitPoint->slaves[i]) {
2855 Threads[i].workIsWaiting = true;
2856 Threads[i].idle = false;
2857 Threads[i].stop = false;
2860 lock_release(&MPLock);
2862 // Everything is set up. The master thread enters the idle loop, from
2863 // which it will instantly launch a search, because its workIsWaiting
2864 // slot is 'true'. We send the split point as a second parameter to the
2865 // idle loop, which means that the main thread will return from the idle
2866 // loop when all threads have finished their work at this split point
2867 // (i.e. when // splitPoint->cpus == 0).
2868 idle_loop(master, splitPoint);
2870 // We have returned from the idle loop, which means that all threads are
2871 // finished. Update alpha, beta and bestvalue, and return.
2873 if(pvNode) *alpha = splitPoint->alpha;
2874 *beta = splitPoint->beta;
2875 *bestValue = splitPoint->bestValue;
2876 Threads[master].stop = false;
2877 Threads[master].idle = false;
2878 Threads[master].activeSplitPoints--;
2879 Threads[master].splitPoint = splitPoint->parent;
2880 lock_release(&MPLock);
2886 // wake_sleeping_threads() wakes up all sleeping threads when it is time
2887 // to start a new search from the root.
2889 void wake_sleeping_threads() {
2890 if(ActiveThreads > 1) {
2891 for(int i = 1; i < ActiveThreads; i++) {
2892 Threads[i].idle = true;
2893 Threads[i].workIsWaiting = false;
2895 #if !defined(_MSC_VER)
2896 pthread_mutex_lock(&WaitLock);
2897 pthread_cond_broadcast(&WaitCond);
2898 pthread_mutex_unlock(&WaitLock);
2900 for(int i = 1; i < THREAD_MAX; i++)
2901 SetEvent(SitIdleEvent[i]);
2907 // init_thread() is the function which is called when a new thread is
2908 // launched. It simply calls the idle_loop() function with the supplied
2909 // threadID. There are two versions of this function; one for POSIX threads
2910 // and one for Windows threads.
2912 #if !defined(_MSC_VER)
2914 void *init_thread(void *threadID) {
2915 idle_loop(*(int *)threadID, NULL);
2921 DWORD WINAPI init_thread(LPVOID threadID) {
2922 idle_loop(*(int *)threadID, NULL);