2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2009 Marco Costalba
6 Stockfish is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 Stockfish is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
43 #include "ucioption.h"
47 //// Local definitions
54 // IterationInfoType stores search results for each iteration
56 // Because we use relatively small (dynamic) aspiration window,
57 // there happens many fail highs and fail lows in root. And
58 // because we don't do researches in those cases, "value" stored
59 // here is not necessarily exact. Instead in case of fail high/low
60 // we guess what the right value might be and store our guess
61 // as a "speculated value" and then move on. Speculated values are
62 // used just to calculate aspiration window width, so also if are
63 // not exact is not big a problem.
65 struct IterationInfoType {
67 IterationInfoType(Value v = Value(0), Value sv = Value(0))
68 : value(v), speculatedValue(sv) {}
70 Value value, speculatedValue;
74 // The BetaCounterType class is used to order moves at ply one.
75 // Apart for the first one that has its score, following moves
76 // normally have score -VALUE_INFINITE, so are ordered according
77 // to the number of beta cutoffs occurred under their subtree during
78 // the last iteration. The counters are per thread variables to avoid
79 // concurrent accessing under SMP case.
81 struct BetaCounterType {
85 void add(Color us, Depth d, int threadID);
86 void read(Color us, int64_t& our, int64_t& their);
90 // The RootMove class is used for moves at the root at the tree. For each
91 // root move, we store a score, a node count, and a PV (really a refutation
92 // in the case of moves which fail low).
97 bool operator<(const RootMove&); // used to sort
101 int64_t nodes, cumulativeNodes;
102 Move pv[PLY_MAX_PLUS_2];
103 int64_t ourBeta, theirBeta;
107 // The RootMoveList class is essentially an array of RootMove objects, with
108 // a handful of methods for accessing the data in the individual moves.
113 RootMoveList(Position& pos, Move searchMoves[]);
114 inline Move get_move(int moveNum) const;
115 inline Value get_move_score(int moveNum) const;
116 inline void set_move_score(int moveNum, Value score);
117 inline void set_move_nodes(int moveNum, int64_t nodes);
118 inline void set_beta_counters(int moveNum, int64_t our, int64_t their);
119 void set_move_pv(int moveNum, const Move pv[]);
120 inline Move get_move_pv(int moveNum, int i) const;
121 inline int64_t get_move_cumulative_nodes(int moveNum) const;
122 inline int move_count() const;
123 Move scan_for_easy_move() const;
125 void sort_multipv(int n);
128 static const int MaxRootMoves = 500;
129 RootMove moves[MaxRootMoves];
136 // Search depth at iteration 1
137 const Depth InitialDepth = OnePly /*+ OnePly/2*/;
139 // Depth limit for selective search
140 const Depth SelectiveDepth = 7 * OnePly;
142 // Use internal iterative deepening?
143 const bool UseIIDAtPVNodes = true;
144 const bool UseIIDAtNonPVNodes = false;
146 // Internal iterative deepening margin. At Non-PV moves, when
147 // UseIIDAtNonPVNodes is true, we do an internal iterative deepening
148 // search when the static evaluation is at most IIDMargin below beta.
149 const Value IIDMargin = Value(0x100);
151 // Easy move margin. An easy move candidate must be at least this much
152 // better than the second best move.
153 const Value EasyMoveMargin = Value(0x200);
155 // Problem margin. If the score of the first move at iteration N+1 has
156 // dropped by more than this since iteration N, the boolean variable
157 // "Problem" is set to true, which will make the program spend some extra
158 // time looking for a better move.
159 const Value ProblemMargin = Value(0x28);
161 // No problem margin. If the boolean "Problem" is true, and a new move
162 // is found at the root which is less than NoProblemMargin worse than the
163 // best move from the previous iteration, Problem is set back to false.
164 const Value NoProblemMargin = Value(0x14);
166 // Null move margin. A null move search will not be done if the approximate
167 // evaluation of the position is more than NullMoveMargin below beta.
168 const Value NullMoveMargin = Value(0x300);
170 // Pruning criterions. See the code and comments in ok_to_prune() to
171 // understand their precise meaning.
172 const bool PruneEscapeMoves = false;
173 const bool PruneDefendingMoves = false;
174 const bool PruneBlockingMoves = false;
176 // Margins for futility pruning in the quiescence search, and at frontier
177 // and near frontier nodes.
178 const Value FutilityMarginQS = Value(0x80);
180 // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply
181 const Value FutilityMargins[12] = { Value(0x100), Value(0x120), Value(0x200), Value(0x220), Value(0x250), Value(0x270),
182 // 4 ply 4.5 ply 5 ply 5.5 ply 6 ply 6.5 ply
183 Value(0x2A0), Value(0x2C0), Value(0x340), Value(0x360), Value(0x3A0), Value(0x3C0) };
185 const Depth RazorDepth = 4*OnePly;
187 // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply
188 const Value RazorMargins[6] = { Value(0x180), Value(0x300), Value(0x300), Value(0x3C0), Value(0x3C0), Value(0x3C0) };
190 // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply
191 const Value RazorApprMargins[6] = { Value(0x520), Value(0x300), Value(0x300), Value(0x300), Value(0x300), Value(0x300) };
193 // The main transposition table
194 TranspositionTable TT;
197 /// Variables initialized by UCI options
199 // Adjustable playing strength
201 const int SlowdownArray[32] = {
202 19, 41, 70, 110, 160, 230, 320, 430, 570, 756, 1000, 1300, 1690, 2197,
203 2834, 3600, 4573, 5809, 7700, 9863, 12633, 16181, 20726, 26584, 34005,
204 43557, 55792, 71463, 91536, 117247, 150180, 192363
207 const int MaxStrength = 25;
209 // Minimum number of full depth (i.e. non-reduced) moves at PV and non-PV nodes
210 int LMRPVMoves, LMRNonPVMoves; // heavy SMP read access for the latter
212 // Depth limit for use of dynamic threat detection
213 Depth ThreatDepth; // heavy SMP read access
215 // Last seconds noise filtering (LSN)
216 const bool UseLSNFiltering = true;
217 const int LSNTime = 4000; // In milliseconds
218 const Value LSNValue = value_from_centipawns(200);
219 bool loseOnTime = false;
221 // Extensions. Array index 0 is used at non-PV nodes, index 1 at PV nodes.
222 // There is heavy SMP read access on these arrays
223 Depth CheckExtension[2], SingleReplyExtension[2], PawnPushTo7thExtension[2];
224 Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2];
226 // Iteration counters
228 BetaCounterType BetaCounter; // has per-thread internal data
230 // Scores and number of times the best move changed for each iteration
231 IterationInfoType IterationInfo[PLY_MAX_PLUS_2];
232 int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
237 // Time managment variables
239 int MaxNodes, MaxDepth;
240 int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
244 bool StopOnPonderhit;
245 bool AbortSearch; // heavy SMP read access
251 // Show current line?
252 bool ShowCurrentLine;
256 std::ofstream LogFile;
258 // MP related variables
259 int ActiveThreads = 1;
260 Depth MinimumSplitDepth;
261 int MaxThreadsPerSplitPoint;
262 Thread Threads[THREAD_MAX];
265 bool AllThreadsShouldExit = false;
266 const int MaxActiveSplitPoints = 8;
267 SplitPoint SplitPointStack[THREAD_MAX][MaxActiveSplitPoints];
270 #if !defined(_MSC_VER)
271 pthread_cond_t WaitCond;
272 pthread_mutex_t WaitLock;
274 HANDLE SitIdleEvent[THREAD_MAX];
277 // Node counters, used only by thread[0] but try to keep in different
278 // cache lines (64 bytes each) from the heavy SMP read accessed variables.
280 int NodesBetweenPolls = 30000;
288 Value id_loop(const Position& pos, Move searchMoves[]);
289 Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta);
290 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
291 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID);
292 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
293 void sp_search(SplitPoint* sp, int threadID);
294 void sp_search_pv(SplitPoint* sp, int threadID);
295 void init_node(const Position& pos, SearchStack ss[], int ply, int threadID);
296 void update_pv(SearchStack ss[], int ply);
297 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply);
298 bool connected_moves(const Position& pos, Move m1, Move m2);
299 bool value_is_mate(Value value);
300 bool move_is_killer(Move m, const SearchStack& ss);
301 Depth extension(const Position& pos, Move m, bool pvNode, bool capture, bool check, bool singleReply, bool mateThreat, bool* dangerous);
302 bool ok_to_do_nullmove(const Position& pos);
303 bool ok_to_prune(const Position& pos, Move m, Move threat, Depth d);
304 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
305 bool ok_to_history(const Position& pos, Move m);
306 void update_history(const Position& pos, Move m, Depth depth, Move movesSearched[], int moveCount);
307 void update_killers(Move m, SearchStack& ss);
308 void slowdown(const Position& pos);
309 void build_pv(const Position& pos, Move pv[]);
311 bool fail_high_ply_1();
312 int current_search_time();
316 void print_current_line(SearchStack ss[], int ply, int threadID);
317 void wait_for_stop_or_ponderhit();
319 void idle_loop(int threadID, SplitPoint* waitSp);
320 void init_split_point_stack();
321 void destroy_split_point_stack();
322 bool thread_should_stop(int threadID);
323 bool thread_is_available(int slave, int master);
324 bool idle_thread_exists(int master);
325 bool split(const Position& pos, SearchStack* ss, int ply,
326 Value *alpha, Value *beta, Value *bestValue, Depth depth, int *moves,
327 MovePicker *mp, Bitboard dcCandidates, int master, bool pvNode);
328 void wake_sleeping_threads();
330 #if !defined(_MSC_VER)
331 void *init_thread(void *threadID);
333 DWORD WINAPI init_thread(LPVOID threadID);
343 /// think() is the external interface to Stockfish's search, and is called when
344 /// the program receives the UCI 'go' command. It initializes various
345 /// search-related global variables, and calls root_search(). It returns false
346 /// when a quit command is received during the search.
348 bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
349 int time[], int increment[], int movesToGo, int maxDepth,
350 int maxNodes, int maxTime, Move searchMoves[]) {
352 // Look for a book move
353 if (!infinite && !ponder && get_option_value_bool("OwnBook"))
356 if (get_option_value_string("Book File") != OpeningBook.file_name())
357 OpeningBook.open("book.bin");
359 bookMove = OpeningBook.get_move(pos);
360 if (bookMove != MOVE_NONE)
362 std::cout << "bestmove " << bookMove << std::endl;
367 // Initialize global search variables
369 SearchStartTime = get_system_time();
370 for (int i = 0; i < THREAD_MAX; i++)
372 Threads[i].nodes = 0ULL;
373 Threads[i].failHighPly1 = false;
376 InfiniteSearch = infinite;
377 PonderSearch = ponder;
378 StopOnPonderhit = false;
384 ExactMaxTime = maxTime;
386 // Read UCI option values
387 TT.set_size(get_option_value_int("Hash"));
388 if (button_was_pressed("Clear Hash"))
391 loseOnTime = false; // reset at the beginning of a new game
394 bool PonderingEnabled = get_option_value_bool("Ponder");
395 MultiPV = get_option_value_int("MultiPV");
397 CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)"));
398 CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)"));
400 SingleReplyExtension[1] = Depth(get_option_value_int("Single Reply Extension (PV nodes)"));
401 SingleReplyExtension[0] = Depth(get_option_value_int("Single Reply Extension (non-PV nodes)"));
403 PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)"));
404 PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
406 PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
407 PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
409 PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
410 PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)"));
412 MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
413 MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
415 LMRPVMoves = get_option_value_int("Full Depth Moves (PV nodes)") + 1;
416 LMRNonPVMoves = get_option_value_int("Full Depth Moves (non-PV nodes)") + 1;
417 ThreatDepth = get_option_value_int("Threat Depth") * OnePly;
419 Chess960 = get_option_value_bool("UCI_Chess960");
420 ShowCurrentLine = get_option_value_bool("UCI_ShowCurrLine");
421 UseLogFile = get_option_value_bool("Use Search Log");
423 LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app);
425 MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly;
426 MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point");
428 read_weights(pos.side_to_move());
430 // Set the number of active threads. If UCI_LimitStrength is enabled, never
431 // use more than one thread.
432 int newActiveThreads =
433 get_option_value_bool("UCI_LimitStrength")? 1 : get_option_value_int("Threads");
434 if (newActiveThreads != ActiveThreads)
436 ActiveThreads = newActiveThreads;
437 init_eval(ActiveThreads);
440 // Wake up sleeping threads
441 wake_sleeping_threads();
443 for (int i = 1; i < ActiveThreads; i++)
444 assert(thread_is_available(i, 0));
446 // Set playing strength
447 if (get_option_value_bool("UCI_LimitStrength"))
449 Strength = (get_option_value_int("UCI_Elo") - 2100) / 25;
451 (Strength == MaxStrength)? 0 : SlowdownArray[Max(0, 31-Strength)];
455 Strength = MaxStrength;
460 int myTime = time[side_to_move];
461 int myIncrement = increment[side_to_move];
463 if (!movesToGo) // Sudden death time control
467 MaxSearchTime = myTime / 30 + myIncrement;
468 AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
469 } else { // Blitz game without increment
470 MaxSearchTime = myTime / 30;
471 AbsoluteMaxSearchTime = myTime / 8;
474 else // (x moves) / (y minutes)
478 MaxSearchTime = myTime / 2;
479 AbsoluteMaxSearchTime = Min(myTime / 2, myTime - 500);
481 MaxSearchTime = myTime / Min(movesToGo, 20);
482 AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
486 if (PonderingEnabled)
488 MaxSearchTime += MaxSearchTime / 4;
489 MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime);
492 // Fixed depth or fixed number of nodes?
495 InfiniteSearch = true; // HACK
500 NodesBetweenPolls = Min(MaxNodes, 30000);
501 InfiniteSearch = true; // HACK
504 if (Slowdown > 50000) NodesBetweenPolls = 30;
505 else if (Slowdown > 10000) NodesBetweenPolls = 100;
506 else if (Slowdown > 1000) NodesBetweenPolls = 500;
507 else if (Slowdown > 100) NodesBetweenPolls = 3000;
508 else NodesBetweenPolls = 15000;
511 NodesBetweenPolls = 30000;
513 // Write information to search log file
515 LogFile << "Searching: " << pos.to_fen() << std::endl
516 << "infinite: " << infinite
517 << " ponder: " << ponder
518 << " time: " << myTime
519 << " increment: " << myIncrement
520 << " moves to go: " << movesToGo << std::endl;
523 // We're ready to start thinking. Call the iterative deepening loop function
525 // FIXME we really need to cleanup all this LSN ugliness
528 Value v = id_loop(pos, searchMoves);
529 loseOnTime = ( UseLSNFiltering
536 loseOnTime = false; // reset for next match
537 while (SearchStartTime + myTime + 1000 > get_system_time())
539 id_loop(pos, searchMoves); // to fail gracefully
550 /// init_threads() is called during startup. It launches all helper threads,
551 /// and initializes the split point stack and the global locks and condition
554 void init_threads() {
558 #if !defined(_MSC_VER)
559 pthread_t pthread[1];
562 for (i = 0; i < THREAD_MAX; i++)
563 Threads[i].activeSplitPoints = 0;
565 // Initialize global locks
566 lock_init(&MPLock, NULL);
567 lock_init(&IOLock, NULL);
569 init_split_point_stack();
571 #if !defined(_MSC_VER)
572 pthread_mutex_init(&WaitLock, NULL);
573 pthread_cond_init(&WaitCond, NULL);
575 for (i = 0; i < THREAD_MAX; i++)
576 SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0);
579 // All threads except the main thread should be initialized to idle state
580 for (i = 1; i < THREAD_MAX; i++)
582 Threads[i].stop = false;
583 Threads[i].workIsWaiting = false;
584 Threads[i].idle = true;
585 Threads[i].running = false;
588 // Launch the helper threads
589 for(i = 1; i < THREAD_MAX; i++)
591 #if !defined(_MSC_VER)
592 pthread_create(pthread, NULL, init_thread, (void*)(&i));
595 CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID);
598 // Wait until the thread has finished launching
599 while (!Threads[i].running);
604 /// stop_threads() is called when the program exits. It makes all the
605 /// helper threads exit cleanly.
607 void stop_threads() {
609 ActiveThreads = THREAD_MAX; // HACK
610 Idle = false; // HACK
611 wake_sleeping_threads();
612 AllThreadsShouldExit = true;
613 for (int i = 1; i < THREAD_MAX; i++)
615 Threads[i].stop = true;
616 while(Threads[i].running);
618 destroy_split_point_stack();
622 /// nodes_searched() returns the total number of nodes searched so far in
623 /// the current search.
625 int64_t nodes_searched() {
627 int64_t result = 0ULL;
628 for (int i = 0; i < ActiveThreads; i++)
629 result += Threads[i].nodes;
634 // SearchStack::init() initializes a search stack. Used at the beginning of a
635 // new search from the root.
636 void SearchStack::init(int ply) {
638 pv[ply] = pv[ply + 1] = MOVE_NONE;
639 currentMove = threatMove = MOVE_NONE;
640 reduction = Depth(0);
643 void SearchStack::initKillers() {
645 mateKiller = MOVE_NONE;
646 for (int i = 0; i < KILLER_MAX; i++)
647 killers[i] = MOVE_NONE;
652 // id_loop() is the main iterative deepening loop. It calls root_search
653 // repeatedly with increasing depth until the allocated thinking time has
654 // been consumed, the user stops the search, or the maximum search depth is
657 Value id_loop(const Position& pos, Move searchMoves[]) {
660 SearchStack ss[PLY_MAX_PLUS_2];
662 // searchMoves are verified, copied, scored and sorted
663 RootMoveList rml(p, searchMoves);
668 for (int i = 0; i < 3; i++)
673 IterationInfo[1] = IterationInfoType(rml.get_move_score(0), rml.get_move_score(0));
676 Move EasyMove = rml.scan_for_easy_move();
678 // Iterative deepening loop
679 while (Iteration < PLY_MAX)
681 // Initialize iteration
684 BestMoveChangesByIteration[Iteration] = 0;
688 std::cout << "info depth " << Iteration << std::endl;
690 // Calculate dynamic search window based on previous iterations
693 if (MultiPV == 1 && Iteration >= 6 && abs(IterationInfo[Iteration - 1].value) < VALUE_KNOWN_WIN)
695 int prevDelta1 = IterationInfo[Iteration - 1].speculatedValue - IterationInfo[Iteration - 2].speculatedValue;
696 int prevDelta2 = IterationInfo[Iteration - 2].speculatedValue - IterationInfo[Iteration - 3].speculatedValue;
698 int delta = Max(2 * abs(prevDelta1) + abs(prevDelta2), ProblemMargin);
700 alpha = Max(IterationInfo[Iteration - 1].value - delta, -VALUE_INFINITE);
701 beta = Min(IterationInfo[Iteration - 1].value + delta, VALUE_INFINITE);
705 alpha = - VALUE_INFINITE;
706 beta = VALUE_INFINITE;
709 // Search to the current depth
710 Value value = root_search(p, ss, rml, alpha, beta);
712 // Write PV to transposition table, in case the relevant entries have
713 // been overwritten during the search.
714 TT.insert_pv(p, ss[0].pv);
717 break; // Value cannot be trusted. Break out immediately!
719 //Save info about search result
720 Value speculatedValue;
723 Value delta = value - IterationInfo[Iteration - 1].value;
730 speculatedValue = value + delta;
731 BestMoveChangesByIteration[Iteration] += 2; // Allocate more time
733 else if (value <= alpha)
735 assert(value == alpha);
739 speculatedValue = value + delta;
740 BestMoveChangesByIteration[Iteration] += 3; // Allocate more time
742 speculatedValue = value;
744 speculatedValue = Min(Max(speculatedValue, -VALUE_INFINITE), VALUE_INFINITE);
745 IterationInfo[Iteration] = IterationInfoType(value, speculatedValue);
747 // Erase the easy move if it differs from the new best move
748 if (ss[0].pv[0] != EasyMove)
749 EasyMove = MOVE_NONE;
756 bool stopSearch = false;
758 // Stop search early if there is only a single legal move
759 if (Iteration >= 6 && rml.move_count() == 1)
762 // Stop search early when the last two iterations returned a mate score
764 && abs(IterationInfo[Iteration].value) >= abs(VALUE_MATE) - 100
765 && abs(IterationInfo[Iteration-1].value) >= abs(VALUE_MATE) - 100)
768 // Stop search early if one move seems to be much better than the rest
769 int64_t nodes = nodes_searched();
773 && EasyMove == ss[0].pv[0]
774 && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
775 && current_search_time() > MaxSearchTime / 16)
776 ||( rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100
777 && current_search_time() > MaxSearchTime / 32)))
780 // Add some extra time if the best move has changed during the last two iterations
781 if (Iteration > 5 && Iteration <= 50)
782 ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2)
783 + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3);
785 // Stop search if most of MaxSearchTime is consumed at the end of the
786 // iteration. We probably don't have enough time to search the first
787 // move at the next iteration anyway.
788 if (current_search_time() > ((MaxSearchTime + ExtraSearchTime)*80) / 128)
793 //FIXME: Implement fail-low emergency measures
797 StopOnPonderhit = true;
801 if (MaxDepth && Iteration >= MaxDepth)
807 // If we are pondering, we shouldn't print the best move before we
810 wait_for_stop_or_ponderhit();
812 // Print final search statistics
813 std::cout << "info nodes " << nodes_searched()
815 << " time " << current_search_time()
816 << " hashfull " << TT.full() << std::endl;
818 // Print the best move and the ponder move to the standard output
819 if (ss[0].pv[0] == MOVE_NONE)
821 ss[0].pv[0] = rml.get_move(0);
822 ss[0].pv[1] = MOVE_NONE;
824 std::cout << "bestmove " << ss[0].pv[0];
825 if (ss[0].pv[1] != MOVE_NONE)
826 std::cout << " ponder " << ss[0].pv[1];
828 std::cout << std::endl;
833 dbg_print_mean(LogFile);
835 if (dbg_show_hit_rate)
836 dbg_print_hit_rate(LogFile);
839 LogFile << "Nodes: " << nodes_searched() << std::endl
840 << "Nodes/second: " << nps() << std::endl
841 << "Best move: " << move_to_san(p, ss[0].pv[0]) << std::endl;
843 p.do_move(ss[0].pv[0], st);
844 LogFile << "Ponder move: " << move_to_san(p, ss[0].pv[1])
845 << std::endl << std::endl;
847 return rml.get_move_score(0);
851 // root_search() is the function which searches the root node. It is
852 // similar to search_pv except that it uses a different move ordering
853 // scheme (perhaps we should try to use this at internal PV nodes, too?)
854 // and prints some information to the standard output.
856 Value root_search(Position& pos, SearchStack ss[], RootMoveList &rml, Value alpha, Value beta) {
858 Value oldAlpha = alpha;
860 Bitboard dcCandidates = pos.discovered_check_candidates(pos.side_to_move());
862 // Loop through all the moves in the root move list
863 for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
867 // We failed high, invalidate and skip next moves, leave node-counters
868 // and beta-counters as they are and quickly return, we will try to do
869 // a research at the next iteration with a bigger aspiration window.
870 rml.set_move_score(i, -VALUE_INFINITE);
878 RootMoveNumber = i + 1;
881 // Remember the node count before the move is searched. The node counts
882 // are used to sort the root moves at the next iteration.
883 nodes = nodes_searched();
885 // Reset beta cut-off counters
888 // Pick the next root move, and print the move and the move number to
889 // the standard output.
890 move = ss[0].currentMove = rml.get_move(i);
891 if (current_search_time() >= 1000)
892 std::cout << "info currmove " << move
893 << " currmovenumber " << i + 1 << std::endl;
895 // Decide search depth for this move
896 bool moveIsCapture = pos.move_is_capture(move);
898 ext = extension(pos, move, true, pos.move_is_capture(move), pos.move_is_check(move), false, false, &dangerous);
899 newDepth = (Iteration - 2) * OnePly + ext + InitialDepth;
901 // Make the move, and search it
902 pos.do_move(move, st, dcCandidates);
906 // Aspiration window is disabled in multi-pv case
908 alpha = -VALUE_INFINITE;
910 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
911 // If the value has dropped a lot compared to the last iteration,
912 // set the boolean variable Problem to true. This variable is used
913 // for time managment: When Problem is true, we try to complete the
914 // current iteration before playing a move.
915 Problem = (Iteration >= 2 && value <= IterationInfo[Iteration-1].value - ProblemMargin);
917 if (Problem && StopOnPonderhit)
918 StopOnPonderhit = false;
922 if (newDepth >= 3*OnePly
923 && i + MultiPV >= LMRPVMoves
926 && !move_is_promotion(move)
927 && !move_is_castle(move))
929 ss[0].reduction = OnePly;
930 value = -search(pos, ss, -alpha, newDepth-OnePly, 1, true, 0);
933 value = alpha + 1; // Just to trigger next condition
936 value = -search(pos, ss, -alpha, newDepth, 1, true, 0);
939 // Fail high! Set the boolean variable FailHigh to true, and
940 // re-search the move with a big window. The variable FailHigh is
941 // used for time managment: We try to avoid aborting the search
942 // prematurely during a fail high research.
944 value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0);
951 // Finished searching the move. If AbortSearch is true, the search
952 // was aborted because the user interrupted the search or because we
953 // ran out of time. In this case, the return value of the search cannot
954 // be trusted, and we break out of the loop without updating the best
959 // Remember the node count for this move. The node counts are used to
960 // sort the root moves at the next iteration.
961 rml.set_move_nodes(i, nodes_searched() - nodes);
963 // Remember the beta-cutoff statistics
965 BetaCounter.read(pos.side_to_move(), our, their);
966 rml.set_beta_counters(i, our, their);
968 assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
970 if (value <= alpha && i >= MultiPV)
971 rml.set_move_score(i, -VALUE_INFINITE);
974 // PV move or new best move!
977 rml.set_move_score(i, value);
979 build_pv(pos, ss[0].pv);
980 rml.set_move_pv(i, ss[0].pv);
984 // We record how often the best move has been changed in each
985 // iteration. This information is used for time managment: When
986 // the best move changes frequently, we allocate some more time.
988 BestMoveChangesByIteration[Iteration]++;
990 // Print search information to the standard output
991 std::cout << "info depth " << Iteration
992 << " score " << value_to_string(value)
993 << " time " << current_search_time()
994 << " nodes " << nodes_searched()
998 for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
999 std::cout << ss[0].pv[j] << " ";
1001 std::cout << std::endl;
1004 LogFile << pretty_pv(pos, current_search_time(), Iteration, nodes_searched(), value, ss[0].pv)
1010 // Reset the global variable Problem to false if the value isn't too
1011 // far below the final value from the last iteration.
1012 if (value > IterationInfo[Iteration - 1].value - NoProblemMargin)
1017 rml.sort_multipv(i);
1018 for (int j = 0; j < Min(MultiPV, rml.move_count()); j++)
1021 std::cout << "info multipv " << j + 1
1022 << " score " << value_to_string(rml.get_move_score(j))
1023 << " depth " << ((j <= i)? Iteration : Iteration - 1)
1024 << " time " << current_search_time()
1025 << " nodes " << nodes_searched()
1029 for (k = 0; rml.get_move_pv(j, k) != MOVE_NONE && k < PLY_MAX; k++)
1030 std::cout << rml.get_move_pv(j, k) << " ";
1032 std::cout << std::endl;
1034 alpha = rml.get_move_score(Min(i, MultiPV-1));
1036 } // New best move case
1038 assert(alpha >= oldAlpha);
1040 FailLow = (alpha == oldAlpha);
1046 // search_pv() is the main search function for PV nodes.
1048 Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta,
1049 Depth depth, int ply, int threadID) {
1051 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1052 assert(beta > alpha && beta <= VALUE_INFINITE);
1053 assert(ply >= 0 && ply < PLY_MAX);
1054 assert(threadID >= 0 && threadID < ActiveThreads);
1057 return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID);
1059 // Initialize, and make an early exit in case of an aborted search,
1060 // an instant draw, maximum ply reached, etc.
1061 init_node(pos, ss, ply, threadID);
1063 // After init_node() that calls poll()
1064 if (AbortSearch || thread_should_stop(threadID))
1072 if (ply >= PLY_MAX - 1)
1073 return evaluate(pos, ei, threadID);
1075 // Mate distance pruning
1076 Value oldAlpha = alpha;
1077 alpha = Max(value_mated_in(ply), alpha);
1078 beta = Min(value_mate_in(ply+1), beta);
1082 // Transposition table lookup. At PV nodes, we don't use the TT for
1083 // pruning, but only for move ordering.
1084 const TTEntry* tte = TT.retrieve(pos.get_key());
1085 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1087 // Go with internal iterative deepening if we don't have a TT move
1088 if (UseIIDAtPVNodes && ttMove == MOVE_NONE && depth >= 5*OnePly)
1090 search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID);
1091 ttMove = ss[ply].pv[ply];
1094 // Initialize a MovePicker object for the current position, and prepare
1095 // to search all moves
1096 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1098 Move move, movesSearched[256];
1100 Value value, bestValue = -VALUE_INFINITE;
1101 Bitboard dcCandidates = mp.discovered_check_candidates();
1102 Color us = pos.side_to_move();
1103 bool isCheck = pos.is_check();
1104 bool mateThreat = pos.has_mate_threat(opposite_color(us));
1106 // Loop through all legal moves until no moves remain or a beta cutoff
1108 while ( alpha < beta
1109 && (move = mp.get_next_move()) != MOVE_NONE
1110 && !thread_should_stop(threadID))
1112 assert(move_is_ok(move));
1114 bool singleReply = (isCheck && mp.number_of_moves() == 1);
1115 bool moveIsCheck = pos.move_is_check(move, dcCandidates);
1116 bool moveIsCapture = pos.move_is_capture(move);
1118 movesSearched[moveCount++] = ss[ply].currentMove = move;
1120 // Decide the new search depth
1122 Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous);
1123 Depth newDepth = depth - OnePly + ext;
1125 // Make and search the move
1127 pos.do_move(move, st, dcCandidates);
1129 if (moveCount == 1) // The first move in list is the PV
1130 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1133 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1134 // if the move fails high will be re-searched at full depth.
1135 if ( depth >= 3*OnePly
1136 && moveCount >= LMRPVMoves
1139 && !move_is_promotion(move)
1140 && !move_is_castle(move)
1141 && !move_is_killer(move, ss[ply]))
1143 ss[ply].reduction = OnePly;
1144 value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, threadID);
1147 value = alpha + 1; // Just to trigger next condition
1149 if (value > alpha) // Go with full depth non-pv search
1151 ss[ply].reduction = Depth(0);
1152 value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID);
1153 if (value > alpha && value < beta)
1155 // When the search fails high at ply 1 while searching the first
1156 // move at the root, set the flag failHighPly1. This is used for
1157 // time managment: We don't want to stop the search early in
1158 // such cases, because resolving the fail high at ply 1 could
1159 // result in a big drop in score at the root.
1160 if (ply == 1 && RootMoveNumber == 1)
1161 Threads[threadID].failHighPly1 = true;
1163 // A fail high occurred. Re-search at full window (pv search)
1164 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
1165 Threads[threadID].failHighPly1 = false;
1169 pos.undo_move(move);
1171 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1174 if (value > bestValue)
1181 if (value == value_mate_in(ply + 1))
1182 ss[ply].mateKiller = move;
1184 // If we are at ply 1, and we are searching the first root move at
1185 // ply 0, set the 'Problem' variable if the score has dropped a lot
1186 // (from the computer's point of view) since the previous iteration.
1189 && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
1194 if ( ActiveThreads > 1
1196 && depth >= MinimumSplitDepth
1198 && idle_thread_exists(threadID)
1200 && !thread_should_stop(threadID)
1201 && split(pos, ss, ply, &alpha, &beta, &bestValue, depth,
1202 &moveCount, &mp, dcCandidates, threadID, true))
1206 // All legal moves have been searched. A special case: If there were
1207 // no legal moves, it must be mate or stalemate.
1209 return (isCheck ? value_mated_in(ply) : VALUE_DRAW);
1211 // If the search is not aborted, update the transposition table,
1212 // history counters, and killer moves.
1213 if (AbortSearch || thread_should_stop(threadID))
1216 if (bestValue <= oldAlpha)
1217 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1219 else if (bestValue >= beta)
1221 BetaCounter.add(pos.side_to_move(), depth, threadID);
1222 Move m = ss[ply].pv[ply];
1223 if (ok_to_history(pos, m)) // Only non capture moves are considered
1225 update_history(pos, m, depth, movesSearched, moveCount);
1226 update_killers(m, ss[ply]);
1228 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m);
1231 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
1237 // search() is the search function for zero-width nodes.
1239 Value search(Position& pos, SearchStack ss[], Value beta, Depth depth,
1240 int ply, bool allowNullmove, int threadID) {
1242 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1243 assert(ply >= 0 && ply < PLY_MAX);
1244 assert(threadID >= 0 && threadID < ActiveThreads);
1247 return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1249 // Initialize, and make an early exit in case of an aborted search,
1250 // an instant draw, maximum ply reached, etc.
1251 init_node(pos, ss, ply, threadID);
1253 // After init_node() that calls poll()
1254 if (AbortSearch || thread_should_stop(threadID))
1262 if (ply >= PLY_MAX - 1)
1263 return evaluate(pos, ei, threadID);
1265 // Mate distance pruning
1266 if (value_mated_in(ply) >= beta)
1269 if (value_mate_in(ply + 1) < beta)
1272 // Transposition table lookup
1273 const TTEntry* tte = TT.retrieve(pos.get_key());
1274 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1276 if (tte && ok_to_use_TT(tte, depth, beta, ply))
1278 ss[ply].currentMove = ttMove; // can be MOVE_NONE
1279 return value_from_tt(tte->value(), ply);
1282 Value approximateEval = quick_evaluate(pos);
1283 bool mateThreat = false;
1284 bool isCheck = pos.is_check();
1290 && !value_is_mate(beta)
1291 && ok_to_do_nullmove(pos)
1292 && approximateEval >= beta - NullMoveMargin)
1294 ss[ply].currentMove = MOVE_NULL;
1297 pos.do_null_move(st);
1298 int R = (depth >= 5 * OnePly ? 4 : 3); // Null move dynamic reduction
1300 Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);
1302 pos.undo_null_move();
1304 if (nullValue >= beta)
1306 if (depth < 6 * OnePly)
1309 // Do zugzwang verification search
1310 Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
1314 // The null move failed low, which means that we may be faced with
1315 // some kind of threat. If the previous move was reduced, check if
1316 // the move that refuted the null move was somehow connected to the
1317 // move which was reduced. If a connection is found, return a fail
1318 // low score (which will cause the reduced move to fail high in the
1319 // parent node, which will trigger a re-search with full depth).
1320 if (nullValue == value_mated_in(ply + 2))
1323 ss[ply].threatMove = ss[ply + 1].currentMove;
1324 if ( depth < ThreatDepth
1325 && ss[ply - 1].reduction
1326 && connected_moves(pos, ss[ply - 1].currentMove, ss[ply].threatMove))
1330 // Null move search not allowed, try razoring
1331 else if ( !value_is_mate(beta)
1332 && depth < RazorDepth
1333 && approximateEval < beta - RazorApprMargins[int(depth) - 2]
1334 && ss[ply - 1].currentMove != MOVE_NULL
1335 && ttMove == MOVE_NONE
1336 && !pos.has_pawn_on_7th(pos.side_to_move()))
1338 Value v = qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
1339 if (v < beta - RazorMargins[int(depth) - 2])
1343 // Go with internal iterative deepening if we don't have a TT move
1344 if (UseIIDAtNonPVNodes && ttMove == MOVE_NONE && depth >= 8*OnePly &&
1345 evaluate(pos, ei, threadID) >= beta - IIDMargin)
1347 search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID);
1348 ttMove = ss[ply].pv[ply];
1351 // Initialize a MovePicker object for the current position, and prepare
1352 // to search all moves.
1353 MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
1355 Move move, movesSearched[256];
1357 Value value, bestValue = -VALUE_INFINITE;
1358 Bitboard dcCandidates = mp.discovered_check_candidates();
1359 Value futilityValue = VALUE_NONE;
1360 bool useFutilityPruning = depth < SelectiveDepth
1363 // Loop through all legal moves until no moves remain or a beta cutoff
1365 while ( bestValue < beta
1366 && (move = mp.get_next_move()) != MOVE_NONE
1367 && !thread_should_stop(threadID))
1369 assert(move_is_ok(move));
1371 bool singleReply = (isCheck && mp.number_of_moves() == 1);
1372 bool moveIsCheck = pos.move_is_check(move, dcCandidates);
1373 bool moveIsCapture = pos.move_is_capture(move);
1375 movesSearched[moveCount++] = ss[ply].currentMove = move;
1377 // Decide the new search depth
1379 Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous);
1380 Depth newDepth = depth - OnePly + ext;
1383 if ( useFutilityPruning
1386 && !move_is_promotion(move))
1388 // History pruning. See ok_to_prune() definition
1389 if ( moveCount >= 2 + int(depth)
1390 && ok_to_prune(pos, move, ss[ply].threatMove, depth))
1393 // Value based pruning
1394 if (approximateEval < beta)
1396 if (futilityValue == VALUE_NONE)
1397 futilityValue = evaluate(pos, ei, threadID)
1398 + FutilityMargins[int(depth) - 2];
1400 if (futilityValue < beta)
1402 if (futilityValue > bestValue)
1403 bestValue = futilityValue;
1409 // Make and search the move
1411 pos.do_move(move, st, dcCandidates);
1413 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1414 // if the move fails high will be re-searched at full depth.
1415 if ( depth >= 3*OnePly
1416 && moveCount >= LMRNonPVMoves
1419 && !move_is_promotion(move)
1420 && !move_is_castle(move)
1421 && !move_is_killer(move, ss[ply]))
1423 ss[ply].reduction = OnePly;
1424 value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);
1427 value = beta; // Just to trigger next condition
1429 if (value >= beta) // Go with full depth non-pv search
1431 ss[ply].reduction = Depth(0);
1432 value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID);
1434 pos.undo_move(move);
1436 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1439 if (value > bestValue)
1445 if (value == value_mate_in(ply + 1))
1446 ss[ply].mateKiller = move;
1450 if ( ActiveThreads > 1
1452 && depth >= MinimumSplitDepth
1454 && idle_thread_exists(threadID)
1456 && !thread_should_stop(threadID)
1457 && split(pos, ss, ply, &beta, &beta, &bestValue, depth, &moveCount,
1458 &mp, dcCandidates, threadID, false))
1462 // All legal moves have been searched. A special case: If there were
1463 // no legal moves, it must be mate or stalemate.
1465 return (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW);
1467 // If the search is not aborted, update the transposition table,
1468 // history counters, and killer moves.
1469 if (AbortSearch || thread_should_stop(threadID))
1472 if (bestValue < beta)
1473 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
1476 BetaCounter.add(pos.side_to_move(), depth, threadID);
1477 Move m = ss[ply].pv[ply];
1478 if (ok_to_history(pos, m)) // Only non capture moves are considered
1480 update_history(pos, m, depth, movesSearched, moveCount);
1481 update_killers(m, ss[ply]);
1483 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m);
1486 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1492 // qsearch() is the quiescence search function, which is called by the main
1493 // search function when the remaining depth is zero (or, to be more precise,
1494 // less than OnePly).
1496 Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta,
1497 Depth depth, int ply, int threadID) {
1499 assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
1500 assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
1502 assert(ply >= 0 && ply < PLY_MAX);
1503 assert(threadID >= 0 && threadID < ActiveThreads);
1505 // Initialize, and make an early exit in case of an aborted search,
1506 // an instant draw, maximum ply reached, etc.
1507 init_node(pos, ss, ply, threadID);
1509 // After init_node() that calls poll()
1510 if (AbortSearch || thread_should_stop(threadID))
1516 // Transposition table lookup, only when not in PV
1517 TTEntry* tte = NULL;
1518 bool pvNode = (beta - alpha != 1);
1521 tte = TT.retrieve(pos.get_key());
1522 if (tte && ok_to_use_TT(tte, depth, beta, ply))
1524 assert(tte->type() != VALUE_TYPE_EVAL);
1526 return value_from_tt(tte->value(), ply);
1529 Move ttMove = (tte ? tte->move() : MOVE_NONE);
1531 // Evaluate the position statically
1534 bool isCheck = pos.is_check();
1535 ei.futilityMargin = Value(0); // Manually initialize futilityMargin
1538 staticValue = -VALUE_INFINITE;
1540 else if (tte && tte->type() == VALUE_TYPE_EVAL)
1542 // Use the cached evaluation score if possible
1543 assert(ei.futilityMargin == Value(0));
1545 staticValue = tte->value();
1548 staticValue = evaluate(pos, ei, threadID);
1550 if (ply == PLY_MAX - 1)
1551 return evaluate(pos, ei, threadID);
1553 // Initialize "stand pat score", and return it immediately if it is
1555 Value bestValue = staticValue;
1557 if (bestValue >= beta)
1559 // Store the score to avoid a future costly evaluation() call
1560 if (!isCheck && !tte && ei.futilityMargin == 0)
1561 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EVAL, Depth(-127*OnePly), MOVE_NONE);
1566 if (bestValue > alpha)
1569 // Initialize a MovePicker object for the current position, and prepare
1570 // to search the moves. Because the depth is <= 0 here, only captures,
1571 // queen promotions and checks (only if depth == 0) will be generated.
1572 MovePicker mp = MovePicker(pos, ttMove, depth, H);
1575 Bitboard dcCandidates = mp.discovered_check_candidates();
1576 Color us = pos.side_to_move();
1577 bool enoughMaterial = pos.non_pawn_material(us) > RookValueMidgame;
1579 // Loop through the moves until no moves remain or a beta cutoff
1581 while ( alpha < beta
1582 && (move = mp.get_next_move()) != MOVE_NONE)
1584 assert(move_is_ok(move));
1587 ss[ply].currentMove = move;
1593 && !move_is_promotion(move)
1594 && !pos.move_is_check(move, dcCandidates)
1595 && !pos.move_is_passed_pawn_push(move))
1597 Value futilityValue = staticValue
1598 + Max(pos.midgame_value_of_piece_on(move_to(move)),
1599 pos.endgame_value_of_piece_on(move_to(move)))
1600 + (move_is_ep(move) ? PawnValueEndgame : Value(0))
1602 + ei.futilityMargin;
1604 if (futilityValue < alpha)
1606 if (futilityValue > bestValue)
1607 bestValue = futilityValue;
1612 // Don't search captures and checks with negative SEE values
1614 && !move_is_promotion(move)
1615 && pos.see_sign(move) < 0)
1618 // Make and search the move.
1620 pos.do_move(move, st, dcCandidates);
1621 Value value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID);
1622 pos.undo_move(move);
1624 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1627 if (value > bestValue)
1638 // All legal moves have been searched. A special case: If we're in check
1639 // and no legal moves were found, it is checkmate.
1640 if (pos.is_check() && moveCount == 0) // Mate!
1641 return value_mated_in(ply);
1643 assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
1645 // Update transposition table
1646 Move m = ss[ply].pv[ply];
1649 Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
1650 if (bestValue < beta)
1651 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, d, MOVE_NONE);
1653 TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, m);
1656 // Update killers only for good check moves
1657 if (alpha >= beta && ok_to_history(pos, m)) // Only non capture moves are considered
1658 update_killers(m, ss[ply]);
1664 // sp_search() is used to search from a split point. This function is called
1665 // by each thread working at the split point. It is similar to the normal
1666 // search() function, but simpler. Because we have already probed the hash
1667 // table, done a null move search, and searched the first move before
1668 // splitting, we don't have to repeat all this work in sp_search(). We
1669 // also don't need to store anything to the hash table here: This is taken
1670 // care of after we return from the split point.
1672 void sp_search(SplitPoint* sp, int threadID) {
1674 assert(threadID >= 0 && threadID < ActiveThreads);
1675 assert(ActiveThreads > 1);
1677 Position pos = Position(sp->pos);
1678 SearchStack* ss = sp->sstack[threadID];
1681 bool isCheck = pos.is_check();
1682 bool useFutilityPruning = sp->depth < SelectiveDepth
1685 while ( sp->bestValue < sp->beta
1686 && !thread_should_stop(threadID)
1687 && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE)
1689 assert(move_is_ok(move));
1691 bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates);
1692 bool moveIsCapture = pos.move_is_capture(move);
1694 lock_grab(&(sp->lock));
1695 int moveCount = ++sp->moves;
1696 lock_release(&(sp->lock));
1698 ss[sp->ply].currentMove = move;
1700 // Decide the new search depth.
1702 Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, false, false, &dangerous);
1703 Depth newDepth = sp->depth - OnePly + ext;
1706 if ( useFutilityPruning
1709 && !move_is_promotion(move)
1710 && moveCount >= 2 + int(sp->depth)
1711 && ok_to_prune(pos, move, ss[sp->ply].threatMove, sp->depth))
1714 // Make and search the move.
1716 pos.do_move(move, st, sp->dcCandidates);
1718 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1719 // if the move fails high will be re-searched at full depth.
1721 && moveCount >= LMRNonPVMoves
1723 && !move_is_promotion(move)
1724 && !move_is_castle(move)
1725 && !move_is_killer(move, ss[sp->ply]))
1727 ss[sp->ply].reduction = OnePly;
1728 value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, true, threadID);
1731 value = sp->beta; // Just to trigger next condition
1733 if (value >= sp->beta) // Go with full depth non-pv search
1735 ss[sp->ply].reduction = Depth(0);
1736 value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID);
1738 pos.undo_move(move);
1740 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1742 if (thread_should_stop(threadID))
1746 lock_grab(&(sp->lock));
1747 if (value > sp->bestValue && !thread_should_stop(threadID))
1749 sp->bestValue = value;
1750 if (sp->bestValue >= sp->beta)
1752 sp_update_pv(sp->parentSstack, ss, sp->ply);
1753 for (int i = 0; i < ActiveThreads; i++)
1754 if (i != threadID && (i == sp->master || sp->slaves[i]))
1755 Threads[i].stop = true;
1757 sp->finished = true;
1760 lock_release(&(sp->lock));
1763 lock_grab(&(sp->lock));
1765 // If this is the master thread and we have been asked to stop because of
1766 // a beta cutoff higher up in the tree, stop all slave threads.
1767 if (sp->master == threadID && thread_should_stop(threadID))
1768 for (int i = 0; i < ActiveThreads; i++)
1770 Threads[i].stop = true;
1773 sp->slaves[threadID] = 0;
1775 lock_release(&(sp->lock));
1779 // sp_search_pv() is used to search from a PV split point. This function
1780 // is called by each thread working at the split point. It is similar to
1781 // the normal search_pv() function, but simpler. Because we have already
1782 // probed the hash table and searched the first move before splitting, we
1783 // don't have to repeat all this work in sp_search_pv(). We also don't
1784 // need to store anything to the hash table here: This is taken care of
1785 // after we return from the split point.
1787 void sp_search_pv(SplitPoint* sp, int threadID) {
1789 assert(threadID >= 0 && threadID < ActiveThreads);
1790 assert(ActiveThreads > 1);
1792 Position pos = Position(sp->pos);
1793 SearchStack* ss = sp->sstack[threadID];
1797 while ( sp->alpha < sp->beta
1798 && !thread_should_stop(threadID)
1799 && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE)
1801 bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates);
1802 bool moveIsCapture = pos.move_is_capture(move);
1804 assert(move_is_ok(move));
1806 lock_grab(&(sp->lock));
1807 int moveCount = ++sp->moves;
1808 lock_release(&(sp->lock));
1810 ss[sp->ply].currentMove = move;
1812 // Decide the new search depth.
1814 Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, false, false, &dangerous);
1815 Depth newDepth = sp->depth - OnePly + ext;
1817 // Make and search the move.
1819 pos.do_move(move, st, sp->dcCandidates);
1821 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1822 // if the move fails high will be re-searched at full depth.
1824 && moveCount >= LMRPVMoves
1826 && !move_is_promotion(move)
1827 && !move_is_castle(move)
1828 && !move_is_killer(move, ss[sp->ply]))
1830 ss[sp->ply].reduction = OnePly;
1831 value = -search(pos, ss, -sp->alpha, newDepth - OnePly, sp->ply+1, true, threadID);
1834 value = sp->alpha + 1; // Just to trigger next condition
1836 if (value > sp->alpha) // Go with full depth non-pv search
1838 ss[sp->ply].reduction = Depth(0);
1839 value = -search(pos, ss, -sp->alpha, newDepth, sp->ply+1, true, threadID);
1841 if (value > sp->alpha && value < sp->beta)
1843 // When the search fails high at ply 1 while searching the first
1844 // move at the root, set the flag failHighPly1. This is used for
1845 // time managment: We don't want to stop the search early in
1846 // such cases, because resolving the fail high at ply 1 could
1847 // result in a big drop in score at the root.
1848 if (sp->ply == 1 && RootMoveNumber == 1)
1849 Threads[threadID].failHighPly1 = true;
1851 value = -search_pv(pos, ss, -sp->beta, -sp->alpha, newDepth, sp->ply+1, threadID);
1852 Threads[threadID].failHighPly1 = false;
1855 pos.undo_move(move);
1857 assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
1859 if (thread_should_stop(threadID))
1863 lock_grab(&(sp->lock));
1864 if (value > sp->bestValue && !thread_should_stop(threadID))
1866 sp->bestValue = value;
1867 if (value > sp->alpha)
1870 sp_update_pv(sp->parentSstack, ss, sp->ply);
1871 if (value == value_mate_in(sp->ply + 1))
1872 ss[sp->ply].mateKiller = move;
1874 if (value >= sp->beta)
1876 for (int i = 0; i < ActiveThreads; i++)
1877 if (i != threadID && (i == sp->master || sp->slaves[i]))
1878 Threads[i].stop = true;
1880 sp->finished = true;
1883 // If we are at ply 1, and we are searching the first root move at
1884 // ply 0, set the 'Problem' variable if the score has dropped a lot
1885 // (from the computer's point of view) since the previous iteration.
1888 && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
1891 lock_release(&(sp->lock));
1894 lock_grab(&(sp->lock));
1896 // If this is the master thread and we have been asked to stop because of
1897 // a beta cutoff higher up in the tree, stop all slave threads.
1898 if (sp->master == threadID && thread_should_stop(threadID))
1899 for (int i = 0; i < ActiveThreads; i++)
1901 Threads[i].stop = true;
1904 sp->slaves[threadID] = 0;
1906 lock_release(&(sp->lock));
1909 /// The BetaCounterType class
1911 BetaCounterType::BetaCounterType() { clear(); }
1913 void BetaCounterType::clear() {
1915 for (int i = 0; i < THREAD_MAX; i++)
1916 Threads[i].betaCutOffs[WHITE] = Threads[i].betaCutOffs[BLACK] = 0ULL;
1919 void BetaCounterType::add(Color us, Depth d, int threadID) {
1921 // Weighted count based on depth
1922 Threads[threadID].betaCutOffs[us] += unsigned(d);
1925 void BetaCounterType::read(Color us, int64_t& our, int64_t& their) {
1928 for (int i = 0; i < THREAD_MAX; i++)
1930 our += Threads[i].betaCutOffs[us];
1931 their += Threads[i].betaCutOffs[opposite_color(us)];
1936 /// The RootMove class
1940 RootMove::RootMove() {
1941 nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL;
1944 // RootMove::operator<() is the comparison function used when
1945 // sorting the moves. A move m1 is considered to be better
1946 // than a move m2 if it has a higher score, or if the moves
1947 // have equal score but m1 has the higher node count.
1949 bool RootMove::operator<(const RootMove& m) {
1951 if (score != m.score)
1952 return (score < m.score);
1954 return theirBeta <= m.theirBeta;
1957 /// The RootMoveList class
1961 RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
1963 MoveStack mlist[MaxRootMoves];
1964 bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
1966 // Generate all legal moves
1967 int lm_count = generate_legal_moves(pos, mlist);
1969 // Add each move to the moves[] array
1970 for (int i = 0; i < lm_count; i++)
1972 bool includeMove = includeAllMoves;
1974 for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++)
1975 includeMove = (searchMoves[k] == mlist[i].move);
1980 // Find a quick score for the move
1982 SearchStack ss[PLY_MAX_PLUS_2];
1984 moves[count].move = mlist[i].move;
1985 pos.do_move(moves[count].move, st);
1986 moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0);
1987 pos.undo_move(moves[count].move);
1988 moves[count].pv[0] = moves[count].move;
1989 moves[count].pv[1] = MOVE_NONE; // FIXME
1996 // Simple accessor methods for the RootMoveList class
1998 inline Move RootMoveList::get_move(int moveNum) const {
1999 return moves[moveNum].move;
2002 inline Value RootMoveList::get_move_score(int moveNum) const {
2003 return moves[moveNum].score;
2006 inline void RootMoveList::set_move_score(int moveNum, Value score) {
2007 moves[moveNum].score = score;
2010 inline void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
2011 moves[moveNum].nodes = nodes;
2012 moves[moveNum].cumulativeNodes += nodes;
2015 inline void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
2016 moves[moveNum].ourBeta = our;
2017 moves[moveNum].theirBeta = their;
2020 void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
2022 for(j = 0; pv[j] != MOVE_NONE; j++)
2023 moves[moveNum].pv[j] = pv[j];
2024 moves[moveNum].pv[j] = MOVE_NONE;
2027 inline Move RootMoveList::get_move_pv(int moveNum, int i) const {
2028 return moves[moveNum].pv[i];
2031 inline int64_t RootMoveList::get_move_cumulative_nodes(int moveNum) const {
2032 return moves[moveNum].cumulativeNodes;
2035 inline int RootMoveList::move_count() const {
2040 // RootMoveList::scan_for_easy_move() is called at the end of the first
2041 // iteration, and is used to detect an "easy move", i.e. a move which appears
2042 // to be much bester than all the rest. If an easy move is found, the move
2043 // is returned, otherwise the function returns MOVE_NONE. It is very
2044 // important that this function is called at the right moment: The code
2045 // assumes that the first iteration has been completed and the moves have
2046 // been sorted. This is done in RootMoveList c'tor.
2048 Move RootMoveList::scan_for_easy_move() const {
2055 // moves are sorted so just consider the best and the second one
2056 if (get_move_score(0) > get_move_score(1) + EasyMoveMargin)
2062 // RootMoveList::sort() sorts the root move list at the beginning of a new
2065 inline void RootMoveList::sort() {
2067 sort_multipv(count - 1); // all items
2071 // RootMoveList::sort_multipv() sorts the first few moves in the root move
2072 // list by their scores and depths. It is used to order the different PVs
2073 // correctly in MultiPV mode.
2075 void RootMoveList::sort_multipv(int n) {
2077 for (int i = 1; i <= n; i++)
2079 RootMove rm = moves[i];
2081 for (j = i; j > 0 && moves[j-1] < rm; j--)
2082 moves[j] = moves[j-1];
2088 // init_node() is called at the beginning of all the search functions
2089 // (search(), search_pv(), qsearch(), and so on) and initializes the search
2090 // stack object corresponding to the current node. Once every
2091 // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
2092 // for user input and checks whether it is time to stop the search.
2094 void init_node(const Position& pos, SearchStack ss[], int ply, int threadID) {
2096 assert(ply >= 0 && ply < PLY_MAX);
2097 assert(threadID >= 0 && threadID < ActiveThreads);
2099 if (Slowdown && Iteration >= 3)
2102 Threads[threadID].nodes++;
2107 if (NodesSincePoll >= NodesBetweenPolls)
2114 ss[ply+2].initKillers();
2116 if (Threads[threadID].printCurrentLine)
2117 print_current_line(ss, ply, threadID);
2121 // update_pv() is called whenever a search returns a value > alpha. It
2122 // updates the PV in the SearchStack object corresponding to the current
2125 void update_pv(SearchStack ss[], int ply) {
2126 assert(ply >= 0 && ply < PLY_MAX);
2128 ss[ply].pv[ply] = ss[ply].currentMove;
2130 for(p = ply + 1; ss[ply+1].pv[p] != MOVE_NONE; p++)
2131 ss[ply].pv[p] = ss[ply+1].pv[p];
2132 ss[ply].pv[p] = MOVE_NONE;
2136 // sp_update_pv() is a variant of update_pv for use at split points. The
2137 // difference between the two functions is that sp_update_pv also updates
2138 // the PV at the parent node.
2140 void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply) {
2141 assert(ply >= 0 && ply < PLY_MAX);
2143 ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
2145 for(p = ply + 1; ss[ply+1].pv[p] != MOVE_NONE; p++)
2146 ss[ply].pv[p] = pss[ply].pv[p] = ss[ply+1].pv[p];
2147 ss[ply].pv[p] = pss[ply].pv[p] = MOVE_NONE;
2151 // connected_moves() tests whether two moves are 'connected' in the sense
2152 // that the first move somehow made the second move possible (for instance
2153 // if the moving piece is the same in both moves). The first move is
2154 // assumed to be the move that was made to reach the current position, while
2155 // the second move is assumed to be a move from the current position.
2157 bool connected_moves(const Position& pos, Move m1, Move m2) {
2158 Square f1, t1, f2, t2;
2160 assert(move_is_ok(m1));
2161 assert(move_is_ok(m2));
2163 if (m2 == MOVE_NONE)
2166 // Case 1: The moving piece is the same in both moves
2172 // Case 2: The destination square for m2 was vacated by m1
2178 // Case 3: Moving through the vacated square
2179 if ( piece_is_slider(pos.piece_on(f2))
2180 && bit_is_set(squares_between(f2, t2), f1))
2183 // Case 4: The destination square for m2 is attacked by the moving piece in m1
2184 if (pos.piece_attacks_square(pos.piece_on(t1), t1, t2))
2187 // Case 5: Discovered check, checking piece is the piece moved in m1
2188 if ( piece_is_slider(pos.piece_on(t1))
2189 && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
2190 && !bit_is_set(squares_between(t2, pos.king_square(pos.side_to_move())), t2))
2192 Bitboard occ = pos.occupied_squares();
2193 Color us = pos.side_to_move();
2194 Square ksq = pos.king_square(us);
2195 clear_bit(&occ, f2);
2196 if (pos.type_of_piece_on(t1) == BISHOP)
2198 if (bit_is_set(bishop_attacks_bb(ksq, occ), t1))
2201 else if (pos.type_of_piece_on(t1) == ROOK)
2203 if (bit_is_set(rook_attacks_bb(ksq, occ), t1))
2208 assert(pos.type_of_piece_on(t1) == QUEEN);
2209 if (bit_is_set(queen_attacks_bb(ksq, occ), t1))
2217 // value_is_mate() checks if the given value is a mate one
2218 // eventually compensated for the ply.
2220 bool value_is_mate(Value value) {
2222 assert(abs(value) <= VALUE_INFINITE);
2224 return value <= value_mated_in(PLY_MAX)
2225 || value >= value_mate_in(PLY_MAX);
2229 // move_is_killer() checks if the given move is among the
2230 // killer moves of that ply.
2232 bool move_is_killer(Move m, const SearchStack& ss) {
2234 const Move* k = ss.killers;
2235 for (int i = 0; i < KILLER_MAX; i++, k++)
2243 // extension() decides whether a move should be searched with normal depth,
2244 // or with extended depth. Certain classes of moves (checking moves, in
2245 // particular) are searched with bigger depth than ordinary moves and in
2246 // any case are marked as 'dangerous'. Note that also if a move is not
2247 // extended, as example because the corresponding UCI option is set to zero,
2248 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
2250 Depth extension(const Position& pos, Move m, bool pvNode, bool capture, bool check,
2251 bool singleReply, bool mateThreat, bool* dangerous) {
2253 assert(m != MOVE_NONE);
2255 Depth result = Depth(0);
2256 *dangerous = check | singleReply | mateThreat;
2261 result += CheckExtension[pvNode];
2264 result += SingleReplyExtension[pvNode];
2267 result += MateThreatExtension[pvNode];
2270 if (pos.type_of_piece_on(move_from(m)) == PAWN)
2272 if (pos.move_is_pawn_push_to_7th(m))
2274 result += PawnPushTo7thExtension[pvNode];
2277 if (pos.move_is_passed_pawn_push(m))
2279 result += PassedPawnExtension[pvNode];
2285 && pos.type_of_piece_on(move_to(m)) != PAWN
2286 && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
2287 - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))
2288 && !move_is_promotion(m)
2291 result += PawnEndgameExtension[pvNode];
2297 && pos.type_of_piece_on(move_to(m)) != PAWN
2298 && pos.see_sign(m) >= 0)
2304 return Min(result, OnePly);
2308 // ok_to_do_nullmove() looks at the current position and decides whether
2309 // doing a 'null move' should be allowed. In order to avoid zugzwang
2310 // problems, null moves are not allowed when the side to move has very
2311 // little material left. Currently, the test is a bit too simple: Null
2312 // moves are avoided only when the side to move has only pawns left. It's
2313 // probably a good idea to avoid null moves in at least some more
2314 // complicated endgames, e.g. KQ vs KR. FIXME
2316 bool ok_to_do_nullmove(const Position& pos) {
2318 return pos.non_pawn_material(pos.side_to_move()) != Value(0);
2322 // ok_to_prune() tests whether it is safe to forward prune a move. Only
2323 // non-tactical moves late in the move list close to the leaves are
2324 // candidates for pruning.
2326 bool ok_to_prune(const Position& pos, Move m, Move threat, Depth d) {
2328 assert(move_is_ok(m));
2329 assert(threat == MOVE_NONE || move_is_ok(threat));
2330 assert(!move_is_promotion(m));
2331 assert(!pos.move_is_check(m));
2332 assert(!pos.move_is_capture(m));
2333 assert(!pos.move_is_passed_pawn_push(m));
2334 assert(d >= OnePly);
2336 Square mfrom, mto, tfrom, tto;
2338 mfrom = move_from(m);
2340 tfrom = move_from(threat);
2341 tto = move_to(threat);
2343 // Case 1: Castling moves are never pruned
2344 if (move_is_castle(m))
2347 // Case 2: Don't prune moves which move the threatened piece
2348 if (!PruneEscapeMoves && threat != MOVE_NONE && mfrom == tto)
2351 // Case 3: If the threatened piece has value less than or equal to the
2352 // value of the threatening piece, don't prune move which defend it.
2353 if ( !PruneDefendingMoves
2354 && threat != MOVE_NONE
2355 && pos.move_is_capture(threat)
2356 && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
2357 || pos.type_of_piece_on(tfrom) == KING)
2358 && pos.move_attacks_square(m, tto))
2361 // Case 4: Don't prune moves with good history
2362 if (!H.ok_to_prune(pos.piece_on(mfrom), mto, d))
2365 // Case 5: If the moving piece in the threatened move is a slider, don't
2366 // prune safe moves which block its ray.
2367 if ( !PruneBlockingMoves
2368 && threat != MOVE_NONE
2369 && piece_is_slider(pos.piece_on(tfrom))
2370 && bit_is_set(squares_between(tfrom, tto), mto)
2371 && pos.see_sign(m) >= 0)
2378 // ok_to_use_TT() returns true if a transposition table score
2379 // can be used at a given point in search.
2381 bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
2383 Value v = value_from_tt(tte->value(), ply);
2385 return ( tte->depth() >= depth
2386 || v >= Max(value_mate_in(100), beta)
2387 || v < Min(value_mated_in(100), beta))
2389 && ( (is_lower_bound(tte->type()) && v >= beta)
2390 || (is_upper_bound(tte->type()) && v < beta));
2394 // ok_to_history() returns true if a move m can be stored
2395 // in history. Should be a non capturing move nor a promotion.
2397 bool ok_to_history(const Position& pos, Move m) {
2399 return !pos.move_is_capture(m) && !move_is_promotion(m);
2403 // update_history() registers a good move that produced a beta-cutoff
2404 // in history and marks as failures all the other moves of that ply.
2406 void update_history(const Position& pos, Move m, Depth depth,
2407 Move movesSearched[], int moveCount) {
2409 H.success(pos.piece_on(move_from(m)), move_to(m), depth);
2411 for (int i = 0; i < moveCount - 1; i++)
2413 assert(m != movesSearched[i]);
2414 if (ok_to_history(pos, movesSearched[i]))
2415 H.failure(pos.piece_on(move_from(movesSearched[i])), move_to(movesSearched[i]));
2420 // update_killers() add a good move that produced a beta-cutoff
2421 // among the killer moves of that ply.
2423 void update_killers(Move m, SearchStack& ss) {
2425 if (m == ss.killers[0])
2428 for (int i = KILLER_MAX - 1; i > 0; i--)
2429 ss.killers[i] = ss.killers[i - 1];
2435 // slowdown() simply wastes CPU cycles doing nothing useful. It's used
2436 // in strength handicap mode.
2438 void slowdown(const Position &pos) {
2441 for (i = 0; i < n; i++) {
2442 Square s = Square(i&63);
2443 if (count_1s(pos.attacks_to(s)) > 63)
2444 std::cout << "This can't happen, but I put this string here anyway, in order to prevent the compiler from optimizing away the useless computation." << std::endl;
2449 // build_pv() extends a PV by adding moves from the transposition table at
2450 // the end. This should ensure that the PV is almost always at least two
2451 // plies long, which is important, because otherwise we will often get
2452 // single-move PVs when the search stops while failing high, and a
2453 // single-move PV means that we don't have a ponder move.
2455 void build_pv(const Position& pos, Move pv[]) {
2460 for (ply = 0; pv[ply] != MOVE_NONE; ply++)
2461 p.do_move(pv[ply], st[ply]);
2465 for (stop = false, tte = TT.retrieve(p.get_key());
2466 tte && tte->move() != MOVE_NONE && !stop;
2467 tte = TT.retrieve(p.get_key()), ply++)
2469 if (!move_is_legal(p, tte->move(), p.pinned_pieces(p.side_to_move())))
2471 pv[ply] = tte->move();
2472 p.do_move(pv[ply], st[ply]);
2473 for (int j = 0; j < ply; j++)
2474 if (st[j].key == p.get_key()) stop = true;
2476 pv[ply] = MOVE_NONE;
2480 // fail_high_ply_1() checks if some thread is currently resolving a fail
2481 // high at ply 1 at the node below the first root node. This information
2482 // is used for time managment.
2484 bool fail_high_ply_1() {
2486 for(int i = 0; i < ActiveThreads; i++)
2487 if (Threads[i].failHighPly1)
2494 // current_search_time() returns the number of milliseconds which have passed
2495 // since the beginning of the current search.
2497 int current_search_time() {
2498 return get_system_time() - SearchStartTime;
2502 // nps() computes the current nodes/second count.
2505 int t = current_search_time();
2506 return (t > 0)? int((nodes_searched() * 1000) / t) : 0;
2510 // poll() performs two different functions: It polls for user input, and it
2511 // looks at the time consumed so far and decides if it's time to abort the
2516 static int lastInfoTime;
2517 int t = current_search_time();
2522 // We are line oriented, don't read single chars
2523 std::string command;
2524 if (!std::getline(std::cin, command))
2527 if (command == "quit")
2530 PonderSearch = false;
2534 else if (command == "stop")
2537 PonderSearch = false;
2539 else if (command == "ponderhit")
2542 // Print search information
2546 else if (lastInfoTime > t)
2547 // HACK: Must be a new search where we searched less than
2548 // NodesBetweenPolls nodes during the first second of search.
2551 else if (t - lastInfoTime >= 1000)
2558 if (dbg_show_hit_rate)
2559 dbg_print_hit_rate();
2561 std::cout << "info nodes " << nodes_searched() << " nps " << nps()
2562 << " time " << t << " hashfull " << TT.full() << std::endl;
2563 lock_release(&IOLock);
2564 if (ShowCurrentLine)
2565 Threads[0].printCurrentLine = true;
2567 // Should we stop the search?
2571 bool overTime = t > AbsoluteMaxSearchTime
2572 || (RootMoveNumber == 1 && t > MaxSearchTime + ExtraSearchTime && !FailLow) //FIXME: We are not checking any problem flags, BUG?
2573 || ( !FailHigh && !FailLow && !fail_high_ply_1() && !Problem
2574 && t > 6*(MaxSearchTime + ExtraSearchTime));
2576 if ( (Iteration >= 3 && (!InfiniteSearch && overTime))
2577 || (ExactMaxTime && t >= ExactMaxTime)
2578 || (Iteration >= 3 && MaxNodes && nodes_searched() >= MaxNodes))
2583 // ponderhit() is called when the program is pondering (i.e. thinking while
2584 // it's the opponent's turn to move) in order to let the engine know that
2585 // it correctly predicted the opponent's move.
2589 int t = current_search_time();
2590 PonderSearch = false;
2591 if (Iteration >= 3 &&
2592 (!InfiniteSearch && (StopOnPonderhit ||
2593 t > AbsoluteMaxSearchTime ||
2594 (RootMoveNumber == 1 &&
2595 t > MaxSearchTime + ExtraSearchTime && !FailLow) ||
2596 (!FailHigh && !FailLow && !fail_high_ply_1() && !Problem &&
2597 t > 6*(MaxSearchTime + ExtraSearchTime)))))
2602 // print_current_line() prints the current line of search for a given
2603 // thread. Called when the UCI option UCI_ShowCurrLine is 'true'.
2605 void print_current_line(SearchStack ss[], int ply, int threadID) {
2607 assert(ply >= 0 && ply < PLY_MAX);
2608 assert(threadID >= 0 && threadID < ActiveThreads);
2610 if (!Threads[threadID].idle)
2613 std::cout << "info currline " << (threadID + 1);
2614 for (int p = 0; p < ply; p++)
2615 std::cout << " " << ss[p].currentMove;
2617 std::cout << std::endl;
2618 lock_release(&IOLock);
2620 Threads[threadID].printCurrentLine = false;
2621 if (threadID + 1 < ActiveThreads)
2622 Threads[threadID + 1].printCurrentLine = true;
2626 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2627 // while the program is pondering. The point is to work around a wrinkle in
2628 // the UCI protocol: When pondering, the engine is not allowed to give a
2629 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2630 // We simply wait here until one of these commands is sent, and return,
2631 // after which the bestmove and pondermove will be printed (in id_loop()).
2633 void wait_for_stop_or_ponderhit() {
2635 std::string command;
2639 if (!std::getline(std::cin, command))
2642 if (command == "quit")
2647 else if (command == "ponderhit" || command == "stop")
2653 // idle_loop() is where the threads are parked when they have no work to do.
2654 // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint
2655 // object for which the current thread is the master.
2657 void idle_loop(int threadID, SplitPoint* waitSp) {
2658 assert(threadID >= 0 && threadID < THREAD_MAX);
2660 Threads[threadID].running = true;
2663 if(AllThreadsShouldExit && threadID != 0)
2666 // If we are not thinking, wait for a condition to be signaled instead
2667 // of wasting CPU time polling for work:
2668 while(threadID != 0 && (Idle || threadID >= ActiveThreads)) {
2669 #if !defined(_MSC_VER)
2670 pthread_mutex_lock(&WaitLock);
2671 if(Idle || threadID >= ActiveThreads)
2672 pthread_cond_wait(&WaitCond, &WaitLock);
2673 pthread_mutex_unlock(&WaitLock);
2675 WaitForSingleObject(SitIdleEvent[threadID], INFINITE);
2679 // If this thread has been assigned work, launch a search
2680 if(Threads[threadID].workIsWaiting) {
2681 Threads[threadID].workIsWaiting = false;
2682 if(Threads[threadID].splitPoint->pvNode)
2683 sp_search_pv(Threads[threadID].splitPoint, threadID);
2685 sp_search(Threads[threadID].splitPoint, threadID);
2686 Threads[threadID].idle = true;
2689 // If this thread is the master of a split point and all threads have
2690 // finished their work at this split point, return from the idle loop.
2691 if(waitSp != NULL && waitSp->cpus == 0)
2695 Threads[threadID].running = false;
2699 // init_split_point_stack() is called during program initialization, and
2700 // initializes all split point objects.
2702 void init_split_point_stack() {
2703 for(int i = 0; i < THREAD_MAX; i++)
2704 for(int j = 0; j < MaxActiveSplitPoints; j++) {
2705 SplitPointStack[i][j].parent = NULL;
2706 lock_init(&(SplitPointStack[i][j].lock), NULL);
2711 // destroy_split_point_stack() is called when the program exits, and
2712 // destroys all locks in the precomputed split point objects.
2714 void destroy_split_point_stack() {
2715 for(int i = 0; i < THREAD_MAX; i++)
2716 for(int j = 0; j < MaxActiveSplitPoints; j++)
2717 lock_destroy(&(SplitPointStack[i][j].lock));
2721 // thread_should_stop() checks whether the thread with a given threadID has
2722 // been asked to stop, directly or indirectly. This can happen if a beta
2723 // cutoff has occured in thre thread's currently active split point, or in
2724 // some ancestor of the current split point.
2726 bool thread_should_stop(int threadID) {
2727 assert(threadID >= 0 && threadID < ActiveThreads);
2731 if(Threads[threadID].stop)
2733 if(ActiveThreads <= 2)
2735 for(sp = Threads[threadID].splitPoint; sp != NULL; sp = sp->parent)
2737 Threads[threadID].stop = true;
2744 // thread_is_available() checks whether the thread with threadID "slave" is
2745 // available to help the thread with threadID "master" at a split point. An
2746 // obvious requirement is that "slave" must be idle. With more than two
2747 // threads, this is not by itself sufficient: If "slave" is the master of
2748 // some active split point, it is only available as a slave to the other
2749 // threads which are busy searching the split point at the top of "slave"'s
2750 // split point stack (the "helpful master concept" in YBWC terminology).
2752 bool thread_is_available(int slave, int master) {
2753 assert(slave >= 0 && slave < ActiveThreads);
2754 assert(master >= 0 && master < ActiveThreads);
2755 assert(ActiveThreads > 1);
2757 if(!Threads[slave].idle || slave == master)
2760 if(Threads[slave].activeSplitPoints == 0)
2761 // No active split points means that the thread is available as a slave
2762 // for any other thread.
2765 if(ActiveThreads == 2)
2768 // Apply the "helpful master" concept if possible.
2769 if(SplitPointStack[slave][Threads[slave].activeSplitPoints-1].slaves[master])
2776 // idle_thread_exists() tries to find an idle thread which is available as
2777 // a slave for the thread with threadID "master".
2779 bool idle_thread_exists(int master) {
2780 assert(master >= 0 && master < ActiveThreads);
2781 assert(ActiveThreads > 1);
2783 for(int i = 0; i < ActiveThreads; i++)
2784 if(thread_is_available(i, master))
2790 // split() does the actual work of distributing the work at a node between
2791 // several threads at PV nodes. If it does not succeed in splitting the
2792 // node (because no idle threads are available, or because we have no unused
2793 // split point objects), the function immediately returns false. If
2794 // splitting is possible, a SplitPoint object is initialized with all the
2795 // data that must be copied to the helper threads (the current position and
2796 // search stack, alpha, beta, the search depth, etc.), and we tell our
2797 // helper threads that they have been assigned work. This will cause them
2798 // to instantly leave their idle loops and call sp_search_pv(). When all
2799 // threads have returned from sp_search_pv (or, equivalently, when
2800 // splitPoint->cpus becomes 0), split() returns true.
2802 bool split(const Position& p, SearchStack* sstck, int ply,
2803 Value* alpha, Value* beta, Value* bestValue, Depth depth, int* moves,
2804 MovePicker* mp, Bitboard dcCandidates, int master, bool pvNode) {
2807 assert(sstck != NULL);
2808 assert(ply >= 0 && ply < PLY_MAX);
2809 assert(*bestValue >= -VALUE_INFINITE && *bestValue <= *alpha);
2810 assert(!pvNode || *alpha < *beta);
2811 assert(*beta <= VALUE_INFINITE);
2812 assert(depth > Depth(0));
2813 assert(master >= 0 && master < ActiveThreads);
2814 assert(ActiveThreads > 1);
2816 SplitPoint* splitPoint;
2821 // If no other thread is available to help us, or if we have too many
2822 // active split points, don't split.
2823 if(!idle_thread_exists(master) ||
2824 Threads[master].activeSplitPoints >= MaxActiveSplitPoints) {
2825 lock_release(&MPLock);
2829 // Pick the next available split point object from the split point stack
2830 splitPoint = SplitPointStack[master] + Threads[master].activeSplitPoints;
2831 Threads[master].activeSplitPoints++;
2833 // Initialize the split point object
2834 splitPoint->parent = Threads[master].splitPoint;
2835 splitPoint->finished = false;
2836 splitPoint->ply = ply;
2837 splitPoint->depth = depth;
2838 splitPoint->alpha = pvNode? *alpha : (*beta - 1);
2839 splitPoint->beta = *beta;
2840 splitPoint->pvNode = pvNode;
2841 splitPoint->dcCandidates = dcCandidates;
2842 splitPoint->bestValue = *bestValue;
2843 splitPoint->master = master;
2844 splitPoint->mp = mp;
2845 splitPoint->moves = *moves;
2846 splitPoint->cpus = 1;
2847 splitPoint->pos.copy(p);
2848 splitPoint->parentSstack = sstck;
2849 for(i = 0; i < ActiveThreads; i++)
2850 splitPoint->slaves[i] = 0;
2852 // Copy the current position and the search stack to the master thread
2853 memcpy(splitPoint->sstack[master], sstck, (ply+1)*sizeof(SearchStack));
2854 Threads[master].splitPoint = splitPoint;
2856 // Make copies of the current position and search stack for each thread
2857 for(i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint;
2859 if(thread_is_available(i, master)) {
2860 memcpy(splitPoint->sstack[i], sstck, (ply+1)*sizeof(SearchStack));
2861 Threads[i].splitPoint = splitPoint;
2862 splitPoint->slaves[i] = 1;
2866 // Tell the threads that they have work to do. This will make them leave
2868 for(i = 0; i < ActiveThreads; i++)
2869 if(i == master || splitPoint->slaves[i]) {
2870 Threads[i].workIsWaiting = true;
2871 Threads[i].idle = false;
2872 Threads[i].stop = false;
2875 lock_release(&MPLock);
2877 // Everything is set up. The master thread enters the idle loop, from
2878 // which it will instantly launch a search, because its workIsWaiting
2879 // slot is 'true'. We send the split point as a second parameter to the
2880 // idle loop, which means that the main thread will return from the idle
2881 // loop when all threads have finished their work at this split point
2882 // (i.e. when // splitPoint->cpus == 0).
2883 idle_loop(master, splitPoint);
2885 // We have returned from the idle loop, which means that all threads are
2886 // finished. Update alpha, beta and bestvalue, and return.
2888 if(pvNode) *alpha = splitPoint->alpha;
2889 *beta = splitPoint->beta;
2890 *bestValue = splitPoint->bestValue;
2891 Threads[master].stop = false;
2892 Threads[master].idle = false;
2893 Threads[master].activeSplitPoints--;
2894 Threads[master].splitPoint = splitPoint->parent;
2895 lock_release(&MPLock);
2901 // wake_sleeping_threads() wakes up all sleeping threads when it is time
2902 // to start a new search from the root.
2904 void wake_sleeping_threads() {
2905 if(ActiveThreads > 1) {
2906 for(int i = 1; i < ActiveThreads; i++) {
2907 Threads[i].idle = true;
2908 Threads[i].workIsWaiting = false;
2910 #if !defined(_MSC_VER)
2911 pthread_mutex_lock(&WaitLock);
2912 pthread_cond_broadcast(&WaitCond);
2913 pthread_mutex_unlock(&WaitLock);
2915 for(int i = 1; i < THREAD_MAX; i++)
2916 SetEvent(SitIdleEvent[i]);
2922 // init_thread() is the function which is called when a new thread is
2923 // launched. It simply calls the idle_loop() function with the supplied
2924 // threadID. There are two versions of this function; one for POSIX threads
2925 // and one for Windows threads.
2927 #if !defined(_MSC_VER)
2929 void *init_thread(void *threadID) {
2930 idle_loop(*(int *)threadID, NULL);
2936 DWORD WINAPI init_thread(LPVOID threadID) {
2937 idle_loop(*(int *)threadID, NULL);