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 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/>.
39 #include "ucioption.h"
43 //// Local definitions
50 // The BetaCounterType class is used to order moves at ply one.
51 // Apart for the first one that has its score, following moves
52 // normally have score -VALUE_INFINITE, so are ordered according
53 // to the number of beta cutoffs occurred under their subtree during
54 // the last iteration.
56 struct BetaCounterType
{
60 void add(Color us
, Depth d
, int threadID
);
61 void read(Color us
, int64_t& our
, int64_t& their
);
63 int64_t hits
[THREAD_MAX
][2];
67 // The RootMove class is used for moves at the root at the tree. For each
68 // root move, we store a score, a node count, and a PV (really a refutation
69 // in the case of moves which fail low).
74 bool operator<(const RootMove
&); // used to sort
78 int64_t nodes
, cumulativeNodes
;
79 Move pv
[PLY_MAX_PLUS_2
];
80 int64_t ourBeta
, theirBeta
;
84 // The RootMoveList class is essentially an array of RootMove objects, with
85 // a handful of methods for accessing the data in the individual moves.
90 RootMoveList(Position
&pos
, Move searchMoves
[]);
91 inline Move
get_move(int moveNum
) const;
92 inline Value
get_move_score(int moveNum
) const;
93 inline void set_move_score(int moveNum
, Value score
);
94 inline void set_move_nodes(int moveNum
, int64_t nodes
);
95 inline void set_beta_counters(int moveNum
, int64_t our
, int64_t their
);
96 void set_move_pv(int moveNum
, const Move pv
[]);
97 inline Move
get_move_pv(int moveNum
, int i
) const;
98 inline int64_t get_move_cumulative_nodes(int moveNum
) const;
99 inline int move_count() const;
100 Move
scan_for_easy_move() const;
102 void sort_multipv(int n
);
105 static const int MaxRootMoves
= 500;
106 RootMove moves
[MaxRootMoves
];
111 /// Constants and variables
113 // Minimum number of full depth (i.e. non-reduced) moves at PV and non-PV
116 int LMRNonPVMoves
= 4;
118 // Depth limit for use of dynamic threat detection:
119 Depth ThreatDepth
= 5*OnePly
;
121 // Depth limit for selective search:
122 Depth SelectiveDepth
= 7*OnePly
;
124 // Use internal iterative deepening?
125 const bool UseIIDAtPVNodes
= true;
126 const bool UseIIDAtNonPVNodes
= false;
128 // Internal iterative deepening margin. At Non-PV moves, when
129 // UseIIDAtNonPVNodes is true, we do an internal iterative deepening search
130 // when the static evaluation is at most IIDMargin below beta.
131 const Value IIDMargin
= Value(0x100);
133 // Easy move margin. An easy move candidate must be at least this much
134 // better than the second best move.
135 const Value EasyMoveMargin
= Value(0x200);
137 // Problem margin. If the score of the first move at iteration N+1 has
138 // dropped by more than this since iteration N, the boolean variable
139 // "Problem" is set to true, which will make the program spend some extra
140 // time looking for a better move.
141 const Value ProblemMargin
= Value(0x28);
143 // No problem margin. If the boolean "Problem" is true, and a new move
144 // is found at the root which is less than NoProblemMargin worse than the
145 // best move from the previous iteration, Problem is set back to false.
146 const Value NoProblemMargin
= Value(0x14);
148 // Null move margin. A null move search will not be done if the approximate
149 // evaluation of the position is more than NullMoveMargin below beta.
150 const Value NullMoveMargin
= Value(0x300);
152 // Pruning criterions. See the code and comments in ok_to_prune() to
153 // understand their precise meaning.
154 const bool PruneEscapeMoves
= false;
155 const bool PruneDefendingMoves
= false;
156 const bool PruneBlockingMoves
= false;
158 // Use futility pruning?
159 bool UseQSearchFutilityPruning
= true;
160 bool UseFutilityPruning
= true;
162 // Margins for futility pruning in the quiescence search, and at frontier
163 // and near frontier nodes
164 Value FutilityMarginQS
= Value(0x80);
165 Value FutilityMargins
[6] = { Value(0x100), Value(0x200), Value(0x250),
166 Value(0x2A0), Value(0x340), Value(0x3A0) };
169 const bool RazorAtDepthOne
= false;
170 Depth RazorDepth
= 4*OnePly
;
171 Value RazorMargin
= Value(0x300);
173 // Last seconds noise filtering (LSN)
174 bool UseLSNFiltering
= false;
175 bool looseOnTime
= false;
176 int LSNTime
= 4 * 1000; // In milliseconds
177 Value LSNValue
= Value(0x200);
179 // Extensions. Array index 0 is used at non-PV nodes, index 1 at PV nodes.
180 Depth CheckExtension
[2] = {OnePly
, OnePly
};
181 Depth SingleReplyExtension
[2] = {OnePly
/ 2, OnePly
/ 2};
182 Depth PawnPushTo7thExtension
[2] = {OnePly
/ 2, OnePly
/ 2};
183 Depth PassedPawnExtension
[2] = {Depth(0), Depth(0)};
184 Depth PawnEndgameExtension
[2] = {OnePly
, OnePly
};
185 Depth MateThreatExtension
[2] = {Depth(0), Depth(0)};
187 // Search depth at iteration 1
188 const Depth InitialDepth
= OnePly
/*+ OnePly/2*/;
192 int NodesBetweenPolls
= 30000;
194 // Iteration counters
196 BetaCounterType BetaCounter
;
198 // Scores and number of times the best move changed for each iteration:
199 Value ValueByIteration
[PLY_MAX_PLUS_2
];
200 int BestMoveChangesByIteration
[PLY_MAX_PLUS_2
];
205 // Time managment variables
207 int MaxNodes
, MaxDepth
;
208 int MaxSearchTime
, AbsoluteMaxSearchTime
, ExtraSearchTime
;
213 bool StopOnPonderhit
;
218 bool PonderingEnabled
;
221 // Show current line?
222 bool ShowCurrentLine
= false;
225 bool UseLogFile
= false;
226 std::ofstream LogFile
;
228 // MP related variables
229 Depth MinimumSplitDepth
= 4*OnePly
;
230 int MaxThreadsPerSplitPoint
= 4;
231 Thread Threads
[THREAD_MAX
];
233 bool AllThreadsShouldExit
= false;
234 const int MaxActiveSplitPoints
= 8;
235 SplitPoint SplitPointStack
[THREAD_MAX
][MaxActiveSplitPoints
];
238 #if !defined(_MSC_VER)
239 pthread_cond_t WaitCond
;
240 pthread_mutex_t WaitLock
;
242 HANDLE SitIdleEvent
[THREAD_MAX
];
248 Value
id_loop(const Position
&pos
, Move searchMoves
[]);
249 Value
root_search(Position
&pos
, SearchStack ss
[], RootMoveList
&rml
);
250 Value
search_pv(Position
&pos
, SearchStack ss
[], Value alpha
, Value beta
,
251 Depth depth
, int ply
, int threadID
);
252 Value
search(Position
&pos
, SearchStack ss
[], Value beta
,
253 Depth depth
, int ply
, bool allowNullmove
, int threadID
);
254 Value
qsearch(Position
&pos
, SearchStack ss
[], Value alpha
, Value beta
,
255 Depth depth
, int ply
, int threadID
);
256 void sp_search(SplitPoint
*sp
, int threadID
);
257 void sp_search_pv(SplitPoint
*sp
, int threadID
);
258 void init_node(SearchStack ss
[], int ply
, int threadID
);
259 void update_pv(SearchStack ss
[], int ply
);
260 void sp_update_pv(SearchStack
*pss
, SearchStack ss
[], int ply
);
261 bool connected_moves(const Position
&pos
, Move m1
, Move m2
);
262 bool value_is_mate(Value value
);
263 bool move_is_killer(Move m
, const SearchStack
& ss
);
264 Depth
extension(const Position
&pos
, Move m
, bool pvNode
, bool capture
, bool check
, bool singleReply
, bool mateThreat
, bool* dangerous
);
265 bool ok_to_do_nullmove(const Position
&pos
);
266 bool ok_to_prune(const Position
&pos
, Move m
, Move threat
, Depth d
);
267 bool ok_to_use_TT(const TTEntry
* tte
, Depth depth
, Value beta
, int ply
);
268 bool ok_to_history(const Position
&pos
, Move m
);
269 void update_history(const Position
& pos
, Move m
, Depth depth
, Move movesSearched
[], int moveCount
);
270 void update_killers(Move m
, SearchStack
& ss
);
272 bool fail_high_ply_1();
273 int current_search_time();
277 void print_current_line(SearchStack ss
[], int ply
, int threadID
);
278 void wait_for_stop_or_ponderhit();
280 void idle_loop(int threadID
, SplitPoint
*waitSp
);
281 void init_split_point_stack();
282 void destroy_split_point_stack();
283 bool thread_should_stop(int threadID
);
284 bool thread_is_available(int slave
, int master
);
285 bool idle_thread_exists(int master
);
286 bool split(const Position
&pos
, SearchStack
*ss
, int ply
,
287 Value
*alpha
, Value
*beta
, Value
*bestValue
, Depth depth
, int *moves
,
288 MovePicker
*mp
, Bitboard dcCandidates
, int master
, bool pvNode
);
289 void wake_sleeping_threads();
291 #if !defined(_MSC_VER)
292 void *init_thread(void *threadID
);
294 DWORD WINAPI
init_thread(LPVOID threadID
);
301 //// Global variables
304 // The main transposition table
305 TranspositionTable TT
= TranspositionTable(TTDefaultSize
);
308 // Number of active threads:
309 int ActiveThreads
= 1;
311 // Locks. In principle, there is no need for IOLock to be a global variable,
312 // but it could turn out to be useful for debugging.
315 History H
; // Should be made local?
317 // The empty search stack
318 SearchStack EmptySearchStack
;
321 // SearchStack::init() initializes a search stack. Used at the beginning of a
322 // new search from the root.
323 void SearchStack::init(int ply
) {
325 pv
[ply
] = pv
[ply
+ 1] = MOVE_NONE
;
326 currentMove
= threatMove
= MOVE_NONE
;
327 reduction
= Depth(0);
328 currentMoveCaptureValue
= Value(0);
331 void SearchStack::initKillers() {
333 mateKiller
= MOVE_NONE
;
334 for (int i
= 0; i
< KILLER_MAX
; i
++)
335 killers
[i
] = MOVE_NONE
;
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()
347 void think(const Position
&pos
, bool infinite
, bool ponder
, int side_to_move
,
348 int time
[], int increment
[], int movesToGo
, int maxDepth
,
349 int maxNodes
, int maxTime
, Move searchMoves
[]) {
351 // Look for a book move
352 if (!infinite
&& !ponder
&& get_option_value_bool("OwnBook"))
355 if (get_option_value_string("Book File") != OpeningBook
.file_name())
358 OpeningBook
.open("book.bin");
360 bookMove
= OpeningBook
.get_move(pos
);
361 if (bookMove
!= MOVE_NONE
)
363 std::cout
<< "bestmove " << bookMove
<< std::endl
;
368 // Initialize global search variables
370 SearchStartTime
= get_system_time();
371 EasyMove
= MOVE_NONE
;
372 for (int i
= 0; i
< THREAD_MAX
; i
++)
374 Threads
[i
].nodes
= 0ULL;
375 Threads
[i
].failHighPly1
= false;
378 InfiniteSearch
= infinite
;
379 PonderSearch
= ponder
;
380 StopOnPonderhit
= false;
385 ExactMaxTime
= maxTime
;
387 // Read UCI option values
388 TT
.set_size(get_option_value_int("Hash"));
389 if (button_was_pressed("Clear Hash"))
392 PonderingEnabled
= get_option_value_bool("Ponder");
393 MultiPV
= get_option_value_int("MultiPV");
395 CheckExtension
[1] = Depth(get_option_value_int("Check Extension (PV nodes)"));
396 CheckExtension
[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)"));
398 SingleReplyExtension
[1] = Depth(get_option_value_int("Single Reply Extension (PV nodes)"));
399 SingleReplyExtension
[0] = Depth(get_option_value_int("Single Reply Extension (non-PV nodes)"));
401 PawnPushTo7thExtension
[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)"));
402 PawnPushTo7thExtension
[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)"));
404 PassedPawnExtension
[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)"));
405 PassedPawnExtension
[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)"));
407 PawnEndgameExtension
[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)"));
408 PawnEndgameExtension
[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)"));
410 MateThreatExtension
[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
411 MateThreatExtension
[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
413 LMRPVMoves
= get_option_value_int("Full Depth Moves (PV nodes)") + 1;
414 LMRNonPVMoves
= get_option_value_int("Full Depth Moves (non-PV nodes)") + 1;
415 ThreatDepth
= get_option_value_int("Threat Depth") * OnePly
;
416 SelectiveDepth
= get_option_value_int("Selective Plies") * OnePly
;
418 Chess960
= get_option_value_bool("UCI_Chess960");
419 ShowCurrentLine
= get_option_value_bool("UCI_ShowCurrLine");
420 UseLogFile
= get_option_value_bool("Use Search Log");
422 LogFile
.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out
| std::ios::app
);
424 UseQSearchFutilityPruning
= get_option_value_bool("Futility Pruning (Quiescence Search)");
425 UseFutilityPruning
= get_option_value_bool("Futility Pruning (Main Search)");
427 FutilityMarginQS
= value_from_centipawns(get_option_value_int("Futility Margin (Quiescence Search)"));
428 int fmScale
= get_option_value_int("Futility Margin Scale Factor (Main Search)");
429 for (int i
= 0; i
< 6; i
++)
430 FutilityMargins
[i
] = (FutilityMargins
[i
] * fmScale
) / 100;
432 RazorDepth
= (get_option_value_int("Maximum Razoring Depth") + 1) * OnePly
;
433 RazorMargin
= value_from_centipawns(get_option_value_int("Razoring Margin"));
435 UseLSNFiltering
= get_option_value_bool("LSN filtering");
436 LSNTime
= get_option_value_int("LSN Time Margin (sec)") * 1000;
437 LSNValue
= value_from_centipawns(get_option_value_int("LSN Value Margin"));
439 MinimumSplitDepth
= get_option_value_int("Minimum Split Depth") * OnePly
;
440 MaxThreadsPerSplitPoint
= get_option_value_int("Maximum Number of Threads per Split Point");
442 read_weights(pos
.side_to_move());
444 int newActiveThreads
= get_option_value_int("Threads");
445 if (newActiveThreads
!= ActiveThreads
)
447 ActiveThreads
= newActiveThreads
;
448 init_eval(ActiveThreads
);
451 // Wake up sleeping threads:
452 wake_sleeping_threads();
454 for (int i
= 1; i
< ActiveThreads
; i
++)
455 assert(thread_is_available(i
, 0));
457 // Set thinking time:
458 int myTime
= time
[side_to_move
];
459 int myIncrement
= increment
[side_to_move
];
461 if (!movesToGo
) // Sudden death time control
465 MaxSearchTime
= myTime
/ 30 + myIncrement
;
466 AbsoluteMaxSearchTime
= Max(myTime
/ 4, myIncrement
- 100);
467 } else { // Blitz game without increment
468 MaxSearchTime
= myTime
/ 30;
469 AbsoluteMaxSearchTime
= myTime
/ 8;
472 else // (x moves) / (y minutes)
476 MaxSearchTime
= myTime
/ 2;
477 AbsoluteMaxSearchTime
= Min(myTime
/ 2, myTime
- 500);
479 MaxSearchTime
= myTime
/ Min(movesToGo
, 20);
480 AbsoluteMaxSearchTime
= Min((4 * myTime
) / movesToGo
, myTime
/ 3);
484 if (PonderingEnabled
)
486 MaxSearchTime
+= MaxSearchTime
/ 4;
487 MaxSearchTime
= Min(MaxSearchTime
, AbsoluteMaxSearchTime
);
490 // Fixed depth or fixed number of nodes?
493 InfiniteSearch
= true; // HACK
498 NodesBetweenPolls
= Min(MaxNodes
, 30000);
499 InfiniteSearch
= true; // HACK
502 NodesBetweenPolls
= 30000;
505 // Write information to search log file:
507 LogFile
<< "Searching: " << pos
.to_fen() << std::endl
508 << "infinite: " << infinite
509 << " ponder: " << ponder
510 << " time: " << myTime
511 << " increment: " << myIncrement
512 << " moves to go: " << movesToGo
<< std::endl
;
515 // We're ready to start thinking. Call the iterative deepening loop
519 Value v
= id_loop(pos
, searchMoves
);
520 looseOnTime
= ( UseLSNFiltering
527 looseOnTime
= false; // reset for next match
528 while (SearchStartTime
+ myTime
+ 1000 > get_system_time())
530 id_loop(pos
, searchMoves
); // to fail gracefully
547 /// init_threads() is called during startup. It launches all helper threads,
548 /// and initializes the split point stack and the global locks and condition
551 void init_threads() {
555 #if !defined(_MSC_VER)
556 pthread_t pthread
[1];
559 for (i
= 0; i
< THREAD_MAX
; i
++)
560 Threads
[i
].activeSplitPoints
= 0;
562 // Initialize global locks:
563 lock_init(&MPLock
, NULL
);
564 lock_init(&IOLock
, NULL
);
566 init_split_point_stack();
568 #if !defined(_MSC_VER)
569 pthread_mutex_init(&WaitLock
, NULL
);
570 pthread_cond_init(&WaitCond
, NULL
);
572 for (i
= 0; i
< THREAD_MAX
; i
++)
573 SitIdleEvent
[i
] = CreateEvent(0, FALSE
, FALSE
, 0);
576 // All threads except the main thread should be initialized to idle state
577 for (i
= 1; i
< THREAD_MAX
; i
++)
579 Threads
[i
].stop
= false;
580 Threads
[i
].workIsWaiting
= false;
581 Threads
[i
].idle
= true;
582 Threads
[i
].running
= false;
585 // Launch the helper threads
586 for(i
= 1; i
< THREAD_MAX
; i
++)
588 #if !defined(_MSC_VER)
589 pthread_create(pthread
, NULL
, init_thread
, (void*)(&i
));
592 CreateThread(NULL
, 0, init_thread
, (LPVOID
)(&i
), 0, iID
);
595 // Wait until the thread has finished launching:
596 while (!Threads
[i
].running
);
599 // Init also the empty search stack
600 EmptySearchStack
.init(0);
601 EmptySearchStack
.initKillers();
605 /// stop_threads() is called when the program exits. It makes all the
606 /// helper threads exit cleanly.
608 void stop_threads() {
610 ActiveThreads
= THREAD_MAX
; // HACK
611 Idle
= false; // HACK
612 wake_sleeping_threads();
613 AllThreadsShouldExit
= true;
614 for (int i
= 1; i
< THREAD_MAX
; i
++)
616 Threads
[i
].stop
= true;
617 while(Threads
[i
].running
);
619 destroy_split_point_stack();
623 /// nodes_searched() returns the total number of nodes searched so far in
624 /// the current search.
626 int64_t nodes_searched() {
628 int64_t result
= 0ULL;
629 for (int i
= 0; i
< ActiveThreads
; i
++)
630 result
+= Threads
[i
].nodes
;
637 // id_loop() is the main iterative deepening loop. It calls root_search
638 // repeatedly with increasing depth until the allocated thinking time has
639 // been consumed, the user stops the search, or the maximum search depth is
642 Value
id_loop(const Position
&pos
, Move searchMoves
[]) {
645 SearchStack ss
[PLY_MAX_PLUS_2
];
647 // searchMoves are verified, copied, scored and sorted
648 RootMoveList
rml(p
, searchMoves
);
653 for (int i
= 0; i
< 3; i
++)
658 ValueByIteration
[0] = Value(0);
659 ValueByIteration
[1] = rml
.get_move_score(0);
662 EasyMove
= rml
.scan_for_easy_move();
664 // Iterative deepening loop
665 while (!AbortSearch
&& Iteration
< PLY_MAX
)
667 // Initialize iteration
670 BestMoveChangesByIteration
[Iteration
] = 0;
674 std::cout
<< "info depth " << Iteration
<< std::endl
;
676 // Search to the current depth
677 ValueByIteration
[Iteration
] = root_search(p
, ss
, rml
);
679 // Erase the easy move if it differs from the new best move
680 if (ss
[0].pv
[0] != EasyMove
)
681 EasyMove
= MOVE_NONE
;
688 bool stopSearch
= false;
690 // Stop search early if there is only a single legal move:
691 if (Iteration
>= 6 && rml
.move_count() == 1)
694 // Stop search early when the last two iterations returned a mate score
696 && abs(ValueByIteration
[Iteration
]) >= abs(VALUE_MATE
) - 100
697 && abs(ValueByIteration
[Iteration
-1]) >= abs(VALUE_MATE
) - 100)
700 // Stop search early if one move seems to be much better than the rest
701 int64_t nodes
= nodes_searched();
703 && EasyMove
== ss
[0].pv
[0]
704 && ( ( rml
.get_move_cumulative_nodes(0) > (nodes
* 85) / 100
705 && current_search_time() > MaxSearchTime
/ 16)
706 ||( rml
.get_move_cumulative_nodes(0) > (nodes
* 98) / 100
707 && current_search_time() > MaxSearchTime
/ 32)))
710 // Add some extra time if the best move has changed during the last two iterations
711 if (Iteration
> 5 && Iteration
<= 50)
712 ExtraSearchTime
= BestMoveChangesByIteration
[Iteration
] * (MaxSearchTime
/ 2)
713 + BestMoveChangesByIteration
[Iteration
-1] * (MaxSearchTime
/ 3);
715 // Stop search if most of MaxSearchTime is consumed at the end of the
716 // iteration. We probably don't have enough time to search the first
717 // move at the next iteration anyway.
718 if (current_search_time() > ((MaxSearchTime
+ ExtraSearchTime
)*80) / 128)
726 StopOnPonderhit
= true;
729 // Write PV to transposition table, in case the relevant entries have
730 // been overwritten during the search:
731 TT
.insert_pv(p
, ss
[0].pv
);
733 if (MaxDepth
&& Iteration
>= MaxDepth
)
739 // If we are pondering, we shouldn't print the best move before we
742 wait_for_stop_or_ponderhit();
744 // Print final search statistics
745 std::cout
<< "info nodes " << nodes_searched()
747 << " time " << current_search_time()
748 << " hashfull " << TT
.full() << std::endl
;
750 // Print the best move and the ponder move to the standard output
751 if (ss
[0].pv
[0] == MOVE_NONE
)
753 ss
[0].pv
[0] = rml
.get_move(0);
754 ss
[0].pv
[1] = MOVE_NONE
;
756 std::cout
<< "bestmove " << ss
[0].pv
[0];
757 if (ss
[0].pv
[1] != MOVE_NONE
)
758 std::cout
<< " ponder " << ss
[0].pv
[1];
760 std::cout
<< std::endl
;
765 dbg_print_mean(LogFile
);
767 if (dbg_show_hit_rate
)
768 dbg_print_hit_rate(LogFile
);
771 LogFile
<< "Nodes: " << nodes_searched() << std::endl
772 << "Nodes/second: " << nps() << std::endl
773 << "Best move: " << move_to_san(p
, ss
[0].pv
[0]) << std::endl
;
775 p
.do_move(ss
[0].pv
[0], st
);
776 LogFile
<< "Ponder move: " << move_to_san(p
, ss
[0].pv
[1])
777 << std::endl
<< std::endl
;
779 return rml
.get_move_score(0);
783 // root_search() is the function which searches the root node. It is
784 // similar to search_pv except that it uses a different move ordering
785 // scheme (perhaps we should try to use this at internal PV nodes, too?)
786 // and prints some information to the standard output.
788 Value
root_search(Position
&pos
, SearchStack ss
[], RootMoveList
&rml
) {
790 Value alpha
= -VALUE_INFINITE
;
791 Value beta
= VALUE_INFINITE
, value
;
792 Bitboard dcCandidates
= pos
.discovered_check_candidates(pos
.side_to_move());
794 // Loop through all the moves in the root move list
795 for (int i
= 0; i
< rml
.move_count() && !AbortSearch
; i
++)
802 RootMoveNumber
= i
+ 1;
805 // Remember the node count before the move is searched. The node counts
806 // are used to sort the root moves at the next iteration.
807 nodes
= nodes_searched();
809 // Reset beta cut-off counters
812 // Pick the next root move, and print the move and the move number to
813 // the standard output.
814 move
= ss
[0].currentMove
= rml
.get_move(i
);
815 if (current_search_time() >= 1000)
816 std::cout
<< "info currmove " << move
817 << " currmovenumber " << i
+ 1 << std::endl
;
819 // Decide search depth for this move
821 ext
= extension(pos
, move
, true, pos
.move_is_capture(move
), pos
.move_is_check(move
), false, false, &dangerous
);
822 newDepth
= (Iteration
- 2) * OnePly
+ ext
+ InitialDepth
;
824 // Make the move, and search it
825 pos
.do_move(move
, st
, dcCandidates
);
829 value
= -search_pv(pos
, ss
, -beta
, VALUE_INFINITE
, newDepth
, 1, 0);
830 // If the value has dropped a lot compared to the last iteration,
831 // set the boolean variable Problem to true. This variable is used
832 // for time managment: When Problem is true, we try to complete the
833 // current iteration before playing a move.
834 Problem
= (Iteration
>= 2 && value
<= ValueByIteration
[Iteration
-1] - ProblemMargin
);
836 if (Problem
&& StopOnPonderhit
)
837 StopOnPonderhit
= false;
841 value
= -search(pos
, ss
, -alpha
, newDepth
, 1, true, 0);
844 // Fail high! Set the boolean variable FailHigh to true, and
845 // re-search the move with a big window. The variable FailHigh is
846 // used for time managment: We try to avoid aborting the search
847 // prematurely during a fail high research.
849 value
= -search_pv(pos
, ss
, -beta
, -alpha
, newDepth
, 1, 0);
855 // Finished searching the move. If AbortSearch is true, the search
856 // was aborted because the user interrupted the search or because we
857 // ran out of time. In this case, the return value of the search cannot
858 // be trusted, and we break out of the loop without updating the best
863 // Remember the node count for this move. The node counts are used to
864 // sort the root moves at the next iteration.
865 rml
.set_move_nodes(i
, nodes_searched() - nodes
);
867 // Remember the beta-cutoff statistics
869 BetaCounter
.read(pos
.side_to_move(), our
, their
);
870 rml
.set_beta_counters(i
, our
, their
);
872 assert(value
>= -VALUE_INFINITE
&& value
<= VALUE_INFINITE
);
874 if (value
<= alpha
&& i
>= MultiPV
)
875 rml
.set_move_score(i
, -VALUE_INFINITE
);
881 rml
.set_move_score(i
, value
);
883 rml
.set_move_pv(i
, ss
[0].pv
);
887 // We record how often the best move has been changed in each
888 // iteration. This information is used for time managment: When
889 // the best move changes frequently, we allocate some more time.
891 BestMoveChangesByIteration
[Iteration
]++;
893 // Print search information to the standard output:
894 std::cout
<< "info depth " << Iteration
895 << " score " << value_to_string(value
)
896 << " time " << current_search_time()
897 << " nodes " << nodes_searched()
901 for (int j
= 0; ss
[0].pv
[j
] != MOVE_NONE
&& j
< PLY_MAX
; j
++)
902 std::cout
<< ss
[0].pv
[j
] << " ";
904 std::cout
<< std::endl
;
907 LogFile
<< pretty_pv(pos
, current_search_time(), Iteration
, nodes_searched(), value
, ss
[0].pv
)
912 // Reset the global variable Problem to false if the value isn't too
913 // far below the final value from the last iteration.
914 if (value
> ValueByIteration
[Iteration
- 1] - NoProblemMargin
)
920 for (int j
= 0; j
< Min(MultiPV
, rml
.move_count()); j
++)
923 std::cout
<< "info multipv " << j
+ 1
924 << " score " << value_to_string(rml
.get_move_score(j
))
925 << " depth " << ((j
<= i
)? Iteration
: Iteration
- 1)
926 << " time " << current_search_time()
927 << " nodes " << nodes_searched()
931 for (k
= 0; rml
.get_move_pv(j
, k
) != MOVE_NONE
&& k
< PLY_MAX
; k
++)
932 std::cout
<< rml
.get_move_pv(j
, k
) << " ";
934 std::cout
<< std::endl
;
936 alpha
= rml
.get_move_score(Min(i
, MultiPV
-1));
944 // search_pv() is the main search function for PV nodes.
946 Value
search_pv(Position
&pos
, SearchStack ss
[], Value alpha
, Value beta
,
947 Depth depth
, int ply
, int threadID
) {
949 assert(alpha
>= -VALUE_INFINITE
&& alpha
<= VALUE_INFINITE
);
950 assert(beta
> alpha
&& beta
<= VALUE_INFINITE
);
951 assert(ply
>= 0 && ply
< PLY_MAX
);
952 assert(threadID
>= 0 && threadID
< ActiveThreads
);
955 return qsearch(pos
, ss
, alpha
, beta
, Depth(0), ply
, threadID
);
957 // Initialize, and make an early exit in case of an aborted search,
958 // an instant draw, maximum ply reached, etc.
959 init_node(ss
, ply
, threadID
);
961 // After init_node() that calls poll()
962 if (AbortSearch
|| thread_should_stop(threadID
))
970 if (ply
>= PLY_MAX
- 1)
971 return evaluate(pos
, ei
, threadID
);
973 // Mate distance pruning
974 Value oldAlpha
= alpha
;
975 alpha
= Max(value_mated_in(ply
), alpha
);
976 beta
= Min(value_mate_in(ply
+1), beta
);
980 // Transposition table lookup. At PV nodes, we don't use the TT for
981 // pruning, but only for move ordering.
982 const TTEntry
* tte
= TT
.retrieve(pos
);
983 Move ttMove
= (tte
? tte
->move() : MOVE_NONE
);
985 // Go with internal iterative deepening if we don't have a TT move
986 if (UseIIDAtPVNodes
&& ttMove
== MOVE_NONE
&& depth
>= 5*OnePly
)
988 search_pv(pos
, ss
, alpha
, beta
, depth
-2*OnePly
, ply
, threadID
);
989 ttMove
= ss
[ply
].pv
[ply
];
992 // Initialize a MovePicker object for the current position, and prepare
993 // to search all moves
994 MovePicker mp
= MovePicker(pos
, true, ttMove
, ss
[ply
], depth
);
996 Move move
, movesSearched
[256];
998 Value value
, bestValue
= -VALUE_INFINITE
;
999 Bitboard dcCandidates
= mp
.discovered_check_candidates();
1000 Color us
= pos
.side_to_move();
1001 bool isCheck
= pos
.is_check();
1002 bool mateThreat
= pos
.has_mate_threat(opposite_color(us
));
1004 // Loop through all legal moves until no moves remain or a beta cutoff
1006 while ( alpha
< beta
1007 && (move
= mp
.get_next_move()) != MOVE_NONE
1008 && !thread_should_stop(threadID
))
1010 assert(move_is_ok(move
));
1012 bool singleReply
= (isCheck
&& mp
.number_of_moves() == 1);
1013 bool moveIsCheck
= pos
.move_is_check(move
, dcCandidates
);
1014 bool moveIsCapture
= pos
.move_is_capture(move
);
1016 movesSearched
[moveCount
++] = ss
[ply
].currentMove
= move
;
1019 ss
[ply
].currentMoveCaptureValue
=
1020 move_is_ep(move
)? PawnValueMidgame
: pos
.midgame_value_of_piece_on(move_to(move
));
1022 ss
[ply
].currentMoveCaptureValue
= Value(0);
1024 // Decide the new search depth
1026 Depth ext
= extension(pos
, move
, true, moveIsCapture
, moveIsCheck
, singleReply
, mateThreat
, &dangerous
);
1027 Depth newDepth
= depth
- OnePly
+ ext
;
1029 // Make and search the move
1031 pos
.do_move(move
, st
, dcCandidates
);
1033 if (moveCount
== 1) // The first move in list is the PV
1034 value
= -search_pv(pos
, ss
, -beta
, -alpha
, newDepth
, ply
+1, threadID
);
1037 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1038 // if the move fails high will be re-searched at full depth.
1039 if ( depth
>= 2*OnePly
1040 && moveCount
>= LMRPVMoves
1043 && !move_promotion(move
)
1044 && !move_is_castle(move
)
1045 && !move_is_killer(move
, ss
[ply
]))
1047 ss
[ply
].reduction
= OnePly
;
1048 value
= -search(pos
, ss
, -alpha
, newDepth
-OnePly
, ply
+1, true, threadID
);
1051 value
= alpha
+ 1; // Just to trigger next condition
1053 if (value
> alpha
) // Go with full depth non-pv search
1055 ss
[ply
].reduction
= Depth(0);
1056 value
= -search(pos
, ss
, -alpha
, newDepth
, ply
+1, true, threadID
);
1057 if (value
> alpha
&& value
< beta
)
1059 // When the search fails high at ply 1 while searching the first
1060 // move at the root, set the flag failHighPly1. This is used for
1061 // time managment: We don't want to stop the search early in
1062 // such cases, because resolving the fail high at ply 1 could
1063 // result in a big drop in score at the root.
1064 if (ply
== 1 && RootMoveNumber
== 1)
1065 Threads
[threadID
].failHighPly1
= true;
1067 // A fail high occurred. Re-search at full window (pv search)
1068 value
= -search_pv(pos
, ss
, -beta
, -alpha
, newDepth
, ply
+1, threadID
);
1069 Threads
[threadID
].failHighPly1
= false;
1073 pos
.undo_move(move
);
1075 assert(value
> -VALUE_INFINITE
&& value
< VALUE_INFINITE
);
1078 if (value
> bestValue
)
1085 if (value
== value_mate_in(ply
+ 1))
1086 ss
[ply
].mateKiller
= move
;
1088 // If we are at ply 1, and we are searching the first root move at
1089 // ply 0, set the 'Problem' variable if the score has dropped a lot
1090 // (from the computer's point of view) since the previous iteration:
1093 && -value
<= ValueByIteration
[Iteration
-1] - ProblemMargin
)
1098 if ( ActiveThreads
> 1
1100 && depth
>= MinimumSplitDepth
1102 && idle_thread_exists(threadID
)
1104 && !thread_should_stop(threadID
)
1105 && split(pos
, ss
, ply
, &alpha
, &beta
, &bestValue
, depth
,
1106 &moveCount
, &mp
, dcCandidates
, threadID
, true))
1110 // All legal moves have been searched. A special case: If there were
1111 // no legal moves, it must be mate or stalemate:
1113 return (isCheck
? value_mated_in(ply
) : VALUE_DRAW
);
1115 // If the search is not aborted, update the transposition table,
1116 // history counters, and killer moves.
1117 if (AbortSearch
|| thread_should_stop(threadID
))
1120 if (bestValue
<= oldAlpha
)
1121 TT
.store(pos
, value_to_tt(bestValue
, ply
), depth
, MOVE_NONE
, VALUE_TYPE_UPPER
);
1123 else if (bestValue
>= beta
)
1125 BetaCounter
.add(pos
.side_to_move(), depth
, threadID
);
1126 Move m
= ss
[ply
].pv
[ply
];
1127 if (ok_to_history(pos
, m
)) // Only non capture moves are considered
1129 update_history(pos
, m
, depth
, movesSearched
, moveCount
);
1130 update_killers(m
, ss
[ply
]);
1132 TT
.store(pos
, value_to_tt(bestValue
, ply
), depth
, m
, VALUE_TYPE_LOWER
);
1135 TT
.store(pos
, value_to_tt(bestValue
, ply
), depth
, ss
[ply
].pv
[ply
], VALUE_TYPE_EXACT
);
1141 // search() is the search function for zero-width nodes.
1143 Value
search(Position
&pos
, SearchStack ss
[], Value beta
, Depth depth
,
1144 int ply
, bool allowNullmove
, int threadID
) {
1146 assert(beta
>= -VALUE_INFINITE
&& beta
<= VALUE_INFINITE
);
1147 assert(ply
>= 0 && ply
< PLY_MAX
);
1148 assert(threadID
>= 0 && threadID
< ActiveThreads
);
1151 return qsearch(pos
, ss
, beta
-1, beta
, Depth(0), ply
, threadID
);
1153 // Initialize, and make an early exit in case of an aborted search,
1154 // an instant draw, maximum ply reached, etc.
1155 init_node(ss
, ply
, threadID
);
1157 // After init_node() that calls poll()
1158 if (AbortSearch
|| thread_should_stop(threadID
))
1166 if (ply
>= PLY_MAX
- 1)
1167 return evaluate(pos
, ei
, threadID
);
1169 // Mate distance pruning
1170 if (value_mated_in(ply
) >= beta
)
1173 if (value_mate_in(ply
+ 1) < beta
)
1176 // Transposition table lookup
1177 const TTEntry
* tte
= TT
.retrieve(pos
);
1178 Move ttMove
= (tte
? tte
->move() : MOVE_NONE
);
1180 if (tte
&& ok_to_use_TT(tte
, depth
, beta
, ply
))
1182 ss
[ply
].currentMove
= ttMove
; // can be MOVE_NONE
1183 return value_from_tt(tte
->value(), ply
);
1186 Value approximateEval
= quick_evaluate(pos
);
1187 bool mateThreat
= false;
1188 bool isCheck
= pos
.is_check();
1194 && !value_is_mate(beta
)
1195 && ok_to_do_nullmove(pos
)
1196 && approximateEval
>= beta
- NullMoveMargin
)
1198 ss
[ply
].currentMove
= MOVE_NULL
;
1201 pos
.do_null_move(st
);
1202 int R
= (depth
>= 5 * OnePly
? 4 : 3); // Null move dynamic reduction
1204 Value nullValue
= -search(pos
, ss
, -(beta
-1), depth
-R
*OnePly
, ply
+1, false, threadID
);
1206 pos
.undo_null_move();
1208 if (value_is_mate(nullValue
))
1210 /* Do not return unproven mates */
1212 else if (nullValue
>= beta
)
1214 if (depth
< 6 * OnePly
)
1217 // Do zugzwang verification search
1218 Value v
= search(pos
, ss
, beta
, depth
-5*OnePly
, ply
, false, threadID
);
1222 // The null move failed low, which means that we may be faced with
1223 // some kind of threat. If the previous move was reduced, check if
1224 // the move that refuted the null move was somehow connected to the
1225 // move which was reduced. If a connection is found, return a fail
1226 // low score (which will cause the reduced move to fail high in the
1227 // parent node, which will trigger a re-search with full depth).
1228 if (nullValue
== value_mated_in(ply
+ 2))
1231 ss
[ply
].threatMove
= ss
[ply
+ 1].currentMove
;
1232 if ( depth
< ThreatDepth
1233 && ss
[ply
- 1].reduction
1234 && connected_moves(pos
, ss
[ply
- 1].currentMove
, ss
[ply
].threatMove
))
1238 // Null move search not allowed, try razoring
1239 else if ( !value_is_mate(beta
)
1240 && approximateEval
< beta
- RazorMargin
1241 && depth
< RazorDepth
1242 && (RazorAtDepthOne
|| depth
> OnePly
)
1243 && ttMove
== MOVE_NONE
1244 && !pos
.has_pawn_on_7th(pos
.side_to_move()))
1246 Value v
= qsearch(pos
, ss
, beta
-1, beta
, Depth(0), ply
, threadID
);
1247 if ( (v
< beta
- RazorMargin
- RazorMargin
/ 4)
1248 || (depth
<= 2*OnePly
&& v
< beta
- RazorMargin
)
1249 || (depth
<= OnePly
&& v
< beta
- RazorMargin
/ 2))
1253 // Go with internal iterative deepening if we don't have a TT move
1254 if (UseIIDAtNonPVNodes
&& ttMove
== MOVE_NONE
&& depth
>= 8*OnePly
&&
1255 evaluate(pos
, ei
, threadID
) >= beta
- IIDMargin
)
1257 search(pos
, ss
, beta
, Min(depth
/2, depth
-2*OnePly
), ply
, false, threadID
);
1258 ttMove
= ss
[ply
].pv
[ply
];
1261 // Initialize a MovePicker object for the current position, and prepare
1262 // to search all moves:
1263 MovePicker mp
= MovePicker(pos
, false, ttMove
, ss
[ply
], depth
);
1265 Move move
, movesSearched
[256];
1267 Value value
, bestValue
= -VALUE_INFINITE
;
1268 Bitboard dcCandidates
= mp
.discovered_check_candidates();
1269 Value futilityValue
= VALUE_NONE
;
1270 bool useFutilityPruning
= UseFutilityPruning
1271 && depth
< SelectiveDepth
1274 // Loop through all legal moves until no moves remain or a beta cutoff
1276 while ( bestValue
< beta
1277 && (move
= mp
.get_next_move()) != MOVE_NONE
1278 && !thread_should_stop(threadID
))
1280 assert(move_is_ok(move
));
1282 bool singleReply
= (isCheck
&& mp
.number_of_moves() == 1);
1283 bool moveIsCheck
= pos
.move_is_check(move
, dcCandidates
);
1284 bool moveIsCapture
= pos
.move_is_capture(move
);
1286 movesSearched
[moveCount
++] = ss
[ply
].currentMove
= move
;
1288 // Decide the new search depth
1290 Depth ext
= extension(pos
, move
, false, moveIsCapture
, moveIsCheck
, singleReply
, mateThreat
, &dangerous
);
1291 Depth newDepth
= depth
- OnePly
+ ext
;
1294 if ( useFutilityPruning
1297 && !move_promotion(move
))
1299 // History pruning. See ok_to_prune() definition
1300 if ( moveCount
>= 2 + int(depth
)
1301 && ok_to_prune(pos
, move
, ss
[ply
].threatMove
, depth
))
1304 // Value based pruning
1305 if (depth
< 7 * OnePly
&& approximateEval
< beta
)
1307 if (futilityValue
== VALUE_NONE
)
1308 futilityValue
= evaluate(pos
, ei
, threadID
)
1309 + FutilityMargins
[int(depth
)/2 - 1]
1312 if (futilityValue
< beta
)
1314 if (futilityValue
> bestValue
)
1315 bestValue
= futilityValue
;
1321 // Make and search the move
1323 pos
.do_move(move
, st
, dcCandidates
);
1325 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1326 // if the move fails high will be re-searched at full depth.
1327 if ( depth
>= 2*OnePly
1328 && moveCount
>= LMRNonPVMoves
1331 && !move_promotion(move
)
1332 && !move_is_castle(move
)
1333 && !move_is_killer(move
, ss
[ply
]))
1335 ss
[ply
].reduction
= OnePly
;
1336 value
= -search(pos
, ss
, -(beta
-1), newDepth
-OnePly
, ply
+1, true, threadID
);
1339 value
= beta
; // Just to trigger next condition
1341 if (value
>= beta
) // Go with full depth non-pv search
1343 ss
[ply
].reduction
= Depth(0);
1344 value
= -search(pos
, ss
, -(beta
-1), newDepth
, ply
+1, true, threadID
);
1346 pos
.undo_move(move
);
1348 assert(value
> -VALUE_INFINITE
&& value
< VALUE_INFINITE
);
1351 if (value
> bestValue
)
1357 if (value
== value_mate_in(ply
+ 1))
1358 ss
[ply
].mateKiller
= move
;
1362 if ( ActiveThreads
> 1
1364 && depth
>= MinimumSplitDepth
1366 && idle_thread_exists(threadID
)
1368 && !thread_should_stop(threadID
)
1369 && split(pos
, ss
, ply
, &beta
, &beta
, &bestValue
, depth
, &moveCount
,
1370 &mp
, dcCandidates
, threadID
, false))
1374 // All legal moves have been searched. A special case: If there were
1375 // no legal moves, it must be mate or stalemate.
1377 return (pos
.is_check() ? value_mated_in(ply
) : VALUE_DRAW
);
1379 // If the search is not aborted, update the transposition table,
1380 // history counters, and killer moves.
1381 if (AbortSearch
|| thread_should_stop(threadID
))
1384 if (bestValue
< beta
)
1385 TT
.store(pos
, value_to_tt(bestValue
, ply
), depth
, MOVE_NONE
, VALUE_TYPE_UPPER
);
1388 BetaCounter
.add(pos
.side_to_move(), depth
, threadID
);
1389 Move m
= ss
[ply
].pv
[ply
];
1390 if (ok_to_history(pos
, m
)) // Only non capture moves are considered
1392 update_history(pos
, m
, depth
, movesSearched
, moveCount
);
1393 update_killers(m
, ss
[ply
]);
1395 TT
.store(pos
, value_to_tt(bestValue
, ply
), depth
, m
, VALUE_TYPE_LOWER
);
1398 assert(bestValue
> -VALUE_INFINITE
&& bestValue
< VALUE_INFINITE
);
1404 // qsearch() is the quiescence search function, which is called by the main
1405 // search function when the remaining depth is zero (or, to be more precise,
1406 // less than OnePly).
1408 Value
qsearch(Position
&pos
, SearchStack ss
[], Value alpha
, Value beta
,
1409 Depth depth
, int ply
, int threadID
) {
1411 assert(alpha
>= -VALUE_INFINITE
&& alpha
<= VALUE_INFINITE
);
1412 assert(beta
>= -VALUE_INFINITE
&& beta
<= VALUE_INFINITE
);
1414 assert(ply
>= 0 && ply
< PLY_MAX
);
1415 assert(threadID
>= 0 && threadID
< ActiveThreads
);
1417 // Initialize, and make an early exit in case of an aborted search,
1418 // an instant draw, maximum ply reached, etc.
1419 init_node(ss
, ply
, threadID
);
1421 // After init_node() that calls poll()
1422 if (AbortSearch
|| thread_should_stop(threadID
))
1428 // Transposition table lookup, only when not in PV
1429 TTEntry
* tte
= NULL
;
1430 bool pvNode
= (beta
- alpha
!= 1);
1433 tte
= TT
.retrieve(pos
);
1434 if (tte
&& ok_to_use_TT(tte
, depth
, beta
, ply
))
1436 assert(tte
->type() != VALUE_TYPE_EVAL
);
1438 return value_from_tt(tte
->value(), ply
);
1442 // Evaluate the position statically
1445 bool isCheck
= pos
.is_check();
1446 ei
.futilityMargin
= Value(0); // Manually initialize futilityMargin
1449 staticValue
= -VALUE_INFINITE
;
1451 else if (tte
&& tte
->type() == VALUE_TYPE_EVAL
)
1453 // Use the cached evaluation score if possible
1454 assert(tte
->value() == evaluate(pos
, ei
, threadID
));
1455 assert(ei
.futilityMargin
== Value(0));
1457 staticValue
= tte
->value();
1460 staticValue
= evaluate(pos
, ei
, threadID
);
1462 if (ply
== PLY_MAX
- 1)
1463 return evaluate(pos
, ei
, threadID
);
1465 // Initialize "stand pat score", and return it immediately if it is
1467 Value bestValue
= staticValue
;
1469 if (bestValue
>= beta
)
1471 // Store the score to avoid a future costly evaluation() call
1472 if (!isCheck
&& !tte
&& ei
.futilityMargin
== 0)
1473 TT
.store(pos
, value_to_tt(bestValue
, ply
), Depth(-127*OnePly
), MOVE_NONE
, VALUE_TYPE_EVAL
);
1478 if (bestValue
> alpha
)
1481 // Initialize a MovePicker object for the current position, and prepare
1482 // to search the moves. Because the depth is <= 0 here, only captures,
1483 // queen promotions and checks (only if depth == 0) will be generated.
1484 MovePicker mp
= MovePicker(pos
, pvNode
, MOVE_NONE
, EmptySearchStack
, depth
);
1487 Bitboard dcCandidates
= mp
.discovered_check_candidates();
1488 Color us
= pos
.side_to_move();
1489 bool enoughMaterial
= pos
.non_pawn_material(us
) > RookValueMidgame
;
1491 // Loop through the moves until no moves remain or a beta cutoff
1493 while ( alpha
< beta
1494 && (move
= mp
.get_next_move()) != MOVE_NONE
)
1496 assert(move_is_ok(move
));
1499 ss
[ply
].currentMove
= move
;
1502 if ( UseQSearchFutilityPruning
1506 && !move_promotion(move
)
1507 && !pos
.move_is_check(move
, dcCandidates
)
1508 && !pos
.move_is_passed_pawn_push(move
))
1510 Value futilityValue
= staticValue
1511 + Max(pos
.midgame_value_of_piece_on(move_to(move
)),
1512 pos
.endgame_value_of_piece_on(move_to(move
)))
1513 + (move_is_ep(move
) ? PawnValueEndgame
: Value(0))
1515 + ei
.futilityMargin
;
1517 if (futilityValue
< alpha
)
1519 if (futilityValue
> bestValue
)
1520 bestValue
= futilityValue
;
1525 // Don't search captures and checks with negative SEE values
1527 && !move_promotion(move
)
1528 && (pos
.midgame_value_of_piece_on(move_from(move
)) >
1529 pos
.midgame_value_of_piece_on(move_to(move
)))
1530 && pos
.see(move
) < 0)
1533 // Make and search the move.
1535 pos
.do_move(move
, st
, dcCandidates
);
1536 Value value
= -qsearch(pos
, ss
, -beta
, -alpha
, depth
-OnePly
, ply
+1, threadID
);
1537 pos
.undo_move(move
);
1539 assert(value
> -VALUE_INFINITE
&& value
< VALUE_INFINITE
);
1542 if (value
> bestValue
)
1553 // All legal moves have been searched. A special case: If we're in check
1554 // and no legal moves were found, it is checkmate:
1555 if (pos
.is_check() && moveCount
== 0) // Mate!
1556 return value_mated_in(ply
);
1558 assert(bestValue
> -VALUE_INFINITE
&& bestValue
< VALUE_INFINITE
);
1560 // Update transposition table
1563 Depth d
= (depth
== Depth(0) ? Depth(0) : Depth(-1));
1564 if (bestValue
< beta
)
1565 TT
.store(pos
, value_to_tt(bestValue
, ply
), d
, MOVE_NONE
, VALUE_TYPE_UPPER
);
1567 TT
.store(pos
, value_to_tt(bestValue
, ply
), d
, MOVE_NONE
, VALUE_TYPE_LOWER
);
1570 // Update killers only for good check moves
1571 Move m
= ss
[ply
].currentMove
;
1572 if (alpha
>= beta
&& ok_to_history(pos
, m
)) // Only non capture moves are considered
1574 // Wrong to update history when depth is <= 0
1575 update_killers(m
, ss
[ply
]);
1581 // sp_search() is used to search from a split point. This function is called
1582 // by each thread working at the split point. It is similar to the normal
1583 // search() function, but simpler. Because we have already probed the hash
1584 // table, done a null move search, and searched the first move before
1585 // splitting, we don't have to repeat all this work in sp_search(). We
1586 // also don't need to store anything to the hash table here: This is taken
1587 // care of after we return from the split point.
1589 void sp_search(SplitPoint
*sp
, int threadID
) {
1591 assert(threadID
>= 0 && threadID
< ActiveThreads
);
1592 assert(ActiveThreads
> 1);
1594 Position pos
= Position(sp
->pos
);
1595 SearchStack
*ss
= sp
->sstack
[threadID
];
1598 bool isCheck
= pos
.is_check();
1599 bool useFutilityPruning
= UseFutilityPruning
1600 && sp
->depth
< SelectiveDepth
1603 while ( sp
->bestValue
< sp
->beta
1604 && !thread_should_stop(threadID
)
1605 && (move
= sp
->mp
->get_next_move(sp
->lock
)) != MOVE_NONE
)
1607 assert(move_is_ok(move
));
1609 bool moveIsCheck
= pos
.move_is_check(move
, sp
->dcCandidates
);
1610 bool moveIsCapture
= pos
.move_is_capture(move
);
1612 lock_grab(&(sp
->lock
));
1613 int moveCount
= ++sp
->moves
;
1614 lock_release(&(sp
->lock
));
1616 ss
[sp
->ply
].currentMove
= move
;
1618 // Decide the new search depth.
1620 Depth ext
= extension(pos
, move
, false, moveIsCapture
, moveIsCheck
, false, false, &dangerous
);
1621 Depth newDepth
= sp
->depth
- OnePly
+ ext
;
1624 if ( useFutilityPruning
1627 && !move_promotion(move
)
1628 && moveCount
>= 2 + int(sp
->depth
)
1629 && ok_to_prune(pos
, move
, ss
[sp
->ply
].threatMove
, sp
->depth
))
1632 // Make and search the move.
1634 pos
.do_move(move
, st
, sp
->dcCandidates
);
1636 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1637 // if the move fails high will be re-searched at full depth.
1639 && moveCount
>= LMRNonPVMoves
1641 && !move_promotion(move
)
1642 && !move_is_castle(move
)
1643 && !move_is_killer(move
, ss
[sp
->ply
]))
1645 ss
[sp
->ply
].reduction
= OnePly
;
1646 value
= -search(pos
, ss
, -(sp
->beta
-1), newDepth
- OnePly
, sp
->ply
+1, true, threadID
);
1649 value
= sp
->beta
; // Just to trigger next condition
1651 if (value
>= sp
->beta
) // Go with full depth non-pv search
1653 ss
[sp
->ply
].reduction
= Depth(0);
1654 value
= -search(pos
, ss
, -(sp
->beta
- 1), newDepth
, sp
->ply
+1, true, threadID
);
1656 pos
.undo_move(move
);
1658 assert(value
> -VALUE_INFINITE
&& value
< VALUE_INFINITE
);
1660 if (thread_should_stop(threadID
))
1664 lock_grab(&(sp
->lock
));
1665 if (value
> sp
->bestValue
&& !thread_should_stop(threadID
))
1667 sp
->bestValue
= value
;
1668 if (sp
->bestValue
>= sp
->beta
)
1670 sp_update_pv(sp
->parentSstack
, ss
, sp
->ply
);
1671 for (int i
= 0; i
< ActiveThreads
; i
++)
1672 if (i
!= threadID
&& (i
== sp
->master
|| sp
->slaves
[i
]))
1673 Threads
[i
].stop
= true;
1675 sp
->finished
= true;
1678 lock_release(&(sp
->lock
));
1681 lock_grab(&(sp
->lock
));
1683 // If this is the master thread and we have been asked to stop because of
1684 // a beta cutoff higher up in the tree, stop all slave threads:
1685 if (sp
->master
== threadID
&& thread_should_stop(threadID
))
1686 for (int i
= 0; i
< ActiveThreads
; i
++)
1688 Threads
[i
].stop
= true;
1691 sp
->slaves
[threadID
] = 0;
1693 lock_release(&(sp
->lock
));
1697 // sp_search_pv() is used to search from a PV split point. This function
1698 // is called by each thread working at the split point. It is similar to
1699 // the normal search_pv() function, but simpler. Because we have already
1700 // probed the hash table and searched the first move before splitting, we
1701 // don't have to repeat all this work in sp_search_pv(). We also don't
1702 // need to store anything to the hash table here: This is taken care of
1703 // after we return from the split point.
1705 void sp_search_pv(SplitPoint
*sp
, int threadID
) {
1707 assert(threadID
>= 0 && threadID
< ActiveThreads
);
1708 assert(ActiveThreads
> 1);
1710 Position pos
= Position(sp
->pos
);
1711 SearchStack
*ss
= sp
->sstack
[threadID
];
1715 while ( sp
->alpha
< sp
->beta
1716 && !thread_should_stop(threadID
)
1717 && (move
= sp
->mp
->get_next_move(sp
->lock
)) != MOVE_NONE
)
1719 bool moveIsCheck
= pos
.move_is_check(move
, sp
->dcCandidates
);
1720 bool moveIsCapture
= pos
.move_is_capture(move
);
1722 assert(move_is_ok(move
));
1725 ss
[sp
->ply
].currentMoveCaptureValue
=
1726 move_is_ep(move
)? PawnValueMidgame
: pos
.midgame_value_of_piece_on(move_to(move
));
1728 ss
[sp
->ply
].currentMoveCaptureValue
= Value(0);
1730 lock_grab(&(sp
->lock
));
1731 int moveCount
= ++sp
->moves
;
1732 lock_release(&(sp
->lock
));
1734 ss
[sp
->ply
].currentMove
= move
;
1736 // Decide the new search depth.
1738 Depth ext
= extension(pos
, move
, true, moveIsCapture
, moveIsCheck
, false, false, &dangerous
);
1739 Depth newDepth
= sp
->depth
- OnePly
+ ext
;
1741 // Make and search the move.
1743 pos
.do_move(move
, st
, sp
->dcCandidates
);
1745 // Try to reduce non-pv search depth by one ply if move seems not problematic,
1746 // if the move fails high will be re-searched at full depth.
1748 && moveCount
>= LMRPVMoves
1750 && !move_promotion(move
)
1751 && !move_is_castle(move
)
1752 && !move_is_killer(move
, ss
[sp
->ply
]))
1754 ss
[sp
->ply
].reduction
= OnePly
;
1755 value
= -search(pos
, ss
, -sp
->alpha
, newDepth
- OnePly
, sp
->ply
+1, true, threadID
);
1758 value
= sp
->alpha
+ 1; // Just to trigger next condition
1760 if (value
> sp
->alpha
) // Go with full depth non-pv search
1762 ss
[sp
->ply
].reduction
= Depth(0);
1763 value
= -search(pos
, ss
, -sp
->alpha
, newDepth
, sp
->ply
+1, true, threadID
);
1765 if (value
> sp
->alpha
&& value
< sp
->beta
)
1767 // When the search fails high at ply 1 while searching the first
1768 // move at the root, set the flag failHighPly1. This is used for
1769 // time managment: We don't want to stop the search early in
1770 // such cases, because resolving the fail high at ply 1 could
1771 // result in a big drop in score at the root.
1772 if (sp
->ply
== 1 && RootMoveNumber
== 1)
1773 Threads
[threadID
].failHighPly1
= true;
1775 value
= -search_pv(pos
, ss
, -sp
->beta
, -sp
->alpha
, newDepth
, sp
->ply
+1, threadID
);
1776 Threads
[threadID
].failHighPly1
= false;
1779 pos
.undo_move(move
);
1781 assert(value
> -VALUE_INFINITE
&& value
< VALUE_INFINITE
);
1783 if (thread_should_stop(threadID
))
1787 lock_grab(&(sp
->lock
));
1788 if (value
> sp
->bestValue
&& !thread_should_stop(threadID
))
1790 sp
->bestValue
= value
;
1791 if (value
> sp
->alpha
)
1794 sp_update_pv(sp
->parentSstack
, ss
, sp
->ply
);
1795 if (value
== value_mate_in(sp
->ply
+ 1))
1796 ss
[sp
->ply
].mateKiller
= move
;
1798 if(value
>= sp
->beta
)
1800 for(int i
= 0; i
< ActiveThreads
; i
++)
1801 if(i
!= threadID
&& (i
== sp
->master
|| sp
->slaves
[i
]))
1802 Threads
[i
].stop
= true;
1804 sp
->finished
= true;
1807 // If we are at ply 1, and we are searching the first root move at
1808 // ply 0, set the 'Problem' variable if the score has dropped a lot
1809 // (from the computer's point of view) since the previous iteration.
1812 && -value
<= ValueByIteration
[Iteration
-1] - ProblemMargin
)
1815 lock_release(&(sp
->lock
));
1818 lock_grab(&(sp
->lock
));
1820 // If this is the master thread and we have been asked to stop because of
1821 // a beta cutoff higher up in the tree, stop all slave threads.
1822 if (sp
->master
== threadID
&& thread_should_stop(threadID
))
1823 for (int i
= 0; i
< ActiveThreads
; i
++)
1825 Threads
[i
].stop
= true;
1828 sp
->slaves
[threadID
] = 0;
1830 lock_release(&(sp
->lock
));
1833 /// The BetaCounterType class
1835 BetaCounterType::BetaCounterType() { clear(); }
1837 void BetaCounterType::clear() {
1839 for (int i
= 0; i
< THREAD_MAX
; i
++)
1840 hits
[i
][WHITE
] = hits
[i
][BLACK
] = 0ULL;
1843 void BetaCounterType::add(Color us
, Depth d
, int threadID
) {
1845 // Weighted count based on depth
1846 hits
[threadID
][us
] += int(d
);
1849 void BetaCounterType::read(Color us
, int64_t& our
, int64_t& their
) {
1852 for (int i
= 0; i
< THREAD_MAX
; i
++)
1855 their
+= hits
[i
][opposite_color(us
)];
1860 /// The RootMove class
1864 RootMove::RootMove() {
1865 nodes
= cumulativeNodes
= 0ULL;
1868 // RootMove::operator<() is the comparison function used when
1869 // sorting the moves. A move m1 is considered to be better
1870 // than a move m2 if it has a higher score, or if the moves
1871 // have equal score but m1 has the higher node count.
1873 bool RootMove::operator<(const RootMove
& m
) {
1875 if (score
!= m
.score
)
1876 return (score
< m
.score
);
1878 return theirBeta
<= m
.theirBeta
;
1881 /// The RootMoveList class
1885 RootMoveList::RootMoveList(Position
& pos
, Move searchMoves
[]) : count(0) {
1887 MoveStack mlist
[MaxRootMoves
];
1888 bool includeAllMoves
= (searchMoves
[0] == MOVE_NONE
);
1890 // Generate all legal moves
1891 int lm_count
= generate_legal_moves(pos
, mlist
);
1893 // Add each move to the moves[] array
1894 for (int i
= 0; i
< lm_count
; i
++)
1896 bool includeMove
= includeAllMoves
;
1898 for (int k
= 0; !includeMove
&& searchMoves
[k
] != MOVE_NONE
; k
++)
1899 includeMove
= (searchMoves
[k
] == mlist
[i
].move
);
1903 // Find a quick score for the move
1905 SearchStack ss
[PLY_MAX_PLUS_2
];
1907 moves
[count
].move
= mlist
[i
].move
;
1908 moves
[count
].nodes
= 0ULL;
1909 pos
.do_move(moves
[count
].move
, st
);
1910 moves
[count
].score
= -qsearch(pos
, ss
, -VALUE_INFINITE
, VALUE_INFINITE
,
1912 pos
.undo_move(moves
[count
].move
);
1913 moves
[count
].pv
[0] = moves
[i
].move
;
1914 moves
[count
].pv
[1] = MOVE_NONE
; // FIXME
1922 // Simple accessor methods for the RootMoveList class
1924 inline Move
RootMoveList::get_move(int moveNum
) const {
1925 return moves
[moveNum
].move
;
1928 inline Value
RootMoveList::get_move_score(int moveNum
) const {
1929 return moves
[moveNum
].score
;
1932 inline void RootMoveList::set_move_score(int moveNum
, Value score
) {
1933 moves
[moveNum
].score
= score
;
1936 inline void RootMoveList::set_move_nodes(int moveNum
, int64_t nodes
) {
1937 moves
[moveNum
].nodes
= nodes
;
1938 moves
[moveNum
].cumulativeNodes
+= nodes
;
1941 inline void RootMoveList::set_beta_counters(int moveNum
, int64_t our
, int64_t their
) {
1942 moves
[moveNum
].ourBeta
= our
;
1943 moves
[moveNum
].theirBeta
= their
;
1946 void RootMoveList::set_move_pv(int moveNum
, const Move pv
[]) {
1948 for(j
= 0; pv
[j
] != MOVE_NONE
; j
++)
1949 moves
[moveNum
].pv
[j
] = pv
[j
];
1950 moves
[moveNum
].pv
[j
] = MOVE_NONE
;
1953 inline Move
RootMoveList::get_move_pv(int moveNum
, int i
) const {
1954 return moves
[moveNum
].pv
[i
];
1957 inline int64_t RootMoveList::get_move_cumulative_nodes(int moveNum
) const {
1958 return moves
[moveNum
].cumulativeNodes
;
1961 inline int RootMoveList::move_count() const {
1966 // RootMoveList::scan_for_easy_move() is called at the end of the first
1967 // iteration, and is used to detect an "easy move", i.e. a move which appears
1968 // to be much bester than all the rest. If an easy move is found, the move
1969 // is returned, otherwise the function returns MOVE_NONE. It is very
1970 // important that this function is called at the right moment: The code
1971 // assumes that the first iteration has been completed and the moves have
1972 // been sorted. This is done in RootMoveList c'tor.
1974 Move
RootMoveList::scan_for_easy_move() const {
1981 // moves are sorted so just consider the best and the second one
1982 if (get_move_score(0) > get_move_score(1) + EasyMoveMargin
)
1988 // RootMoveList::sort() sorts the root move list at the beginning of a new
1991 inline void RootMoveList::sort() {
1993 sort_multipv(count
- 1); // all items
1997 // RootMoveList::sort_multipv() sorts the first few moves in the root move
1998 // list by their scores and depths. It is used to order the different PVs
1999 // correctly in MultiPV mode.
2001 void RootMoveList::sort_multipv(int n
) {
2003 for (int i
= 1; i
<= n
; i
++)
2005 RootMove rm
= moves
[i
];
2007 for (j
= i
; j
> 0 && moves
[j
-1] < rm
; j
--)
2008 moves
[j
] = moves
[j
-1];
2014 // init_node() is called at the beginning of all the search functions
2015 // (search(), search_pv(), qsearch(), and so on) and initializes the search
2016 // stack object corresponding to the current node. Once every
2017 // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
2018 // for user input and checks whether it is time to stop the search.
2020 void init_node(SearchStack ss
[], int ply
, int threadID
) {
2021 assert(ply
>= 0 && ply
< PLY_MAX
);
2022 assert(threadID
>= 0 && threadID
< ActiveThreads
);
2024 Threads
[threadID
].nodes
++;
2028 if(NodesSincePoll
>= NodesBetweenPolls
) {
2035 ss
[ply
+2].initKillers();
2037 if(Threads
[threadID
].printCurrentLine
)
2038 print_current_line(ss
, ply
, threadID
);
2042 // update_pv() is called whenever a search returns a value > alpha. It
2043 // updates the PV in the SearchStack object corresponding to the current
2046 void update_pv(SearchStack ss
[], int ply
) {
2047 assert(ply
>= 0 && ply
< PLY_MAX
);
2049 ss
[ply
].pv
[ply
] = ss
[ply
].currentMove
;
2051 for(p
= ply
+ 1; ss
[ply
+1].pv
[p
] != MOVE_NONE
; p
++)
2052 ss
[ply
].pv
[p
] = ss
[ply
+1].pv
[p
];
2053 ss
[ply
].pv
[p
] = MOVE_NONE
;
2057 // sp_update_pv() is a variant of update_pv for use at split points. The
2058 // difference between the two functions is that sp_update_pv also updates
2059 // the PV at the parent node.
2061 void sp_update_pv(SearchStack
*pss
, SearchStack ss
[], int ply
) {
2062 assert(ply
>= 0 && ply
< PLY_MAX
);
2064 ss
[ply
].pv
[ply
] = pss
[ply
].pv
[ply
] = ss
[ply
].currentMove
;
2066 for(p
= ply
+ 1; ss
[ply
+1].pv
[p
] != MOVE_NONE
; p
++)
2067 ss
[ply
].pv
[p
] = pss
[ply
].pv
[p
] = ss
[ply
+1].pv
[p
];
2068 ss
[ply
].pv
[p
] = pss
[ply
].pv
[p
] = MOVE_NONE
;
2072 // connected_moves() tests whether two moves are 'connected' in the sense
2073 // that the first move somehow made the second move possible (for instance
2074 // if the moving piece is the same in both moves). The first move is
2075 // assumed to be the move that was made to reach the current position, while
2076 // the second move is assumed to be a move from the current position.
2078 bool connected_moves(const Position
&pos
, Move m1
, Move m2
) {
2079 Square f1
, t1
, f2
, t2
;
2081 assert(move_is_ok(m1
));
2082 assert(move_is_ok(m2
));
2087 // Case 1: The moving piece is the same in both moves.
2093 // Case 2: The destination square for m2 was vacated by m1.
2099 // Case 3: Moving through the vacated square:
2100 if(piece_is_slider(pos
.piece_on(f2
)) &&
2101 bit_is_set(squares_between(f2
, t2
), f1
))
2104 // Case 4: The destination square for m2 is attacked by the moving piece
2106 if(pos
.piece_attacks_square(pos
.piece_on(t1
), t1
, t2
))
2109 // Case 5: Discovered check, checking piece is the piece moved in m1:
2110 if(piece_is_slider(pos
.piece_on(t1
)) &&
2111 bit_is_set(squares_between(t1
, pos
.king_square(pos
.side_to_move())),
2113 !bit_is_set(squares_between(t2
, pos
.king_square(pos
.side_to_move())),
2115 Bitboard occ
= pos
.occupied_squares();
2116 Color us
= pos
.side_to_move();
2117 Square ksq
= pos
.king_square(us
);
2118 clear_bit(&occ
, f2
);
2119 if(pos
.type_of_piece_on(t1
) == BISHOP
) {
2120 if(bit_is_set(bishop_attacks_bb(ksq
, occ
), t1
))
2123 else if(pos
.type_of_piece_on(t1
) == ROOK
) {
2124 if(bit_is_set(rook_attacks_bb(ksq
, occ
), t1
))
2128 assert(pos
.type_of_piece_on(t1
) == QUEEN
);
2129 if(bit_is_set(queen_attacks_bb(ksq
, occ
), t1
))
2138 // value_is_mate() checks if the given value is a mate one
2139 // eventually compensated for the ply.
2141 bool value_is_mate(Value value
) {
2143 assert(abs(value
) <= VALUE_INFINITE
);
2145 return value
<= value_mated_in(PLY_MAX
)
2146 || value
>= value_mate_in(PLY_MAX
);
2150 // move_is_killer() checks if the given move is among the
2151 // killer moves of that ply.
2153 bool move_is_killer(Move m
, const SearchStack
& ss
) {
2155 const Move
* k
= ss
.killers
;
2156 for (int i
= 0; i
< KILLER_MAX
; i
++, k
++)
2164 // extension() decides whether a move should be searched with normal depth,
2165 // or with extended depth. Certain classes of moves (checking moves, in
2166 // particular) are searched with bigger depth than ordinary moves and in
2167 // any case are marked as 'dangerous'. Note that also if a move is not
2168 // extended, as example because the corresponding UCI option is set to zero,
2169 // the move is marked as 'dangerous' so, at least, we avoid to prune it.
2171 Depth
extension(const Position
& pos
, Move m
, bool pvNode
, bool capture
, bool check
,
2172 bool singleReply
, bool mateThreat
, bool* dangerous
) {
2174 assert(m
!= MOVE_NONE
);
2176 Depth result
= Depth(0);
2177 *dangerous
= check
|| singleReply
|| mateThreat
;
2180 result
+= CheckExtension
[pvNode
];
2183 result
+= SingleReplyExtension
[pvNode
];
2186 result
+= MateThreatExtension
[pvNode
];
2188 if (pos
.type_of_piece_on(move_from(m
)) == PAWN
)
2190 if (pos
.move_is_pawn_push_to_7th(m
))
2192 result
+= PawnPushTo7thExtension
[pvNode
];
2195 if (pos
.move_is_passed_pawn_push(m
))
2197 result
+= PassedPawnExtension
[pvNode
];
2203 && pos
.type_of_piece_on(move_to(m
)) != PAWN
2204 && ( pos
.non_pawn_material(WHITE
) + pos
.non_pawn_material(BLACK
)
2205 - pos
.midgame_value_of_piece_on(move_to(m
)) == Value(0))
2206 && !move_promotion(m
)
2209 result
+= PawnEndgameExtension
[pvNode
];
2215 && pos
.type_of_piece_on(move_to(m
)) != PAWN
2222 return Min(result
, OnePly
);
2226 // ok_to_do_nullmove() looks at the current position and decides whether
2227 // doing a 'null move' should be allowed. In order to avoid zugzwang
2228 // problems, null moves are not allowed when the side to move has very
2229 // little material left. Currently, the test is a bit too simple: Null
2230 // moves are avoided only when the side to move has only pawns left. It's
2231 // probably a good idea to avoid null moves in at least some more
2232 // complicated endgames, e.g. KQ vs KR. FIXME
2234 bool ok_to_do_nullmove(const Position
&pos
) {
2235 if(pos
.non_pawn_material(pos
.side_to_move()) == Value(0))
2241 // ok_to_prune() tests whether it is safe to forward prune a move. Only
2242 // non-tactical moves late in the move list close to the leaves are
2243 // candidates for pruning.
2245 bool ok_to_prune(const Position
&pos
, Move m
, Move threat
, Depth d
) {
2246 Square mfrom
, mto
, tfrom
, tto
;
2248 assert(move_is_ok(m
));
2249 assert(threat
== MOVE_NONE
|| move_is_ok(threat
));
2250 assert(!move_promotion(m
));
2251 assert(!pos
.move_is_check(m
));
2252 assert(!pos
.move_is_capture(m
));
2253 assert(!pos
.move_is_passed_pawn_push(m
));
2254 assert(d
>= OnePly
);
2256 mfrom
= move_from(m
);
2258 tfrom
= move_from(threat
);
2259 tto
= move_to(threat
);
2261 // Case 1: Castling moves are never pruned.
2262 if (move_is_castle(m
))
2265 // Case 2: Don't prune moves which move the threatened piece
2266 if (!PruneEscapeMoves
&& threat
!= MOVE_NONE
&& mfrom
== tto
)
2269 // Case 3: If the threatened piece has value less than or equal to the
2270 // value of the threatening piece, don't prune move which defend it.
2271 if ( !PruneDefendingMoves
2272 && threat
!= MOVE_NONE
2273 && pos
.move_is_capture(threat
)
2274 && ( pos
.midgame_value_of_piece_on(tfrom
) >= pos
.midgame_value_of_piece_on(tto
)
2275 || pos
.type_of_piece_on(tfrom
) == KING
)
2276 && pos
.move_attacks_square(m
, tto
))
2279 // Case 4: Don't prune moves with good history.
2280 if (!H
.ok_to_prune(pos
.piece_on(move_from(m
)), m
, d
))
2283 // Case 5: If the moving piece in the threatened move is a slider, don't
2284 // prune safe moves which block its ray.
2285 if ( !PruneBlockingMoves
2286 && threat
!= MOVE_NONE
2287 && piece_is_slider(pos
.piece_on(tfrom
))
2288 && bit_is_set(squares_between(tfrom
, tto
), mto
)
2296 // ok_to_use_TT() returns true if a transposition table score
2297 // can be used at a given point in search.
2299 bool ok_to_use_TT(const TTEntry
* tte
, Depth depth
, Value beta
, int ply
) {
2301 Value v
= value_from_tt(tte
->value(), ply
);
2303 return ( tte
->depth() >= depth
2304 || v
>= Max(value_mate_in(100), beta
)
2305 || v
< Min(value_mated_in(100), beta
))
2307 && ( (is_lower_bound(tte
->type()) && v
>= beta
)
2308 || (is_upper_bound(tte
->type()) && v
< beta
));
2312 // ok_to_history() returns true if a move m can be stored
2313 // in history. Should be a non capturing move nor a promotion.
2315 bool ok_to_history(const Position
& pos
, Move m
) {
2317 return !pos
.move_is_capture(m
) && !move_promotion(m
);
2321 // update_history() registers a good move that produced a beta-cutoff
2322 // in history and marks as failures all the other moves of that ply.
2324 void update_history(const Position
& pos
, Move m
, Depth depth
,
2325 Move movesSearched
[], int moveCount
) {
2327 H
.success(pos
.piece_on(move_from(m
)), m
, depth
);
2329 for (int i
= 0; i
< moveCount
- 1; i
++)
2331 assert(m
!= movesSearched
[i
]);
2332 if (ok_to_history(pos
, movesSearched
[i
]))
2333 H
.failure(pos
.piece_on(move_from(movesSearched
[i
])), movesSearched
[i
]);
2338 // update_killers() add a good move that produced a beta-cutoff
2339 // among the killer moves of that ply.
2341 void update_killers(Move m
, SearchStack
& ss
) {
2343 if (m
== ss
.killers
[0])
2346 for (int i
= KILLER_MAX
- 1; i
> 0; i
--)
2347 ss
.killers
[i
] = ss
.killers
[i
- 1];
2352 // fail_high_ply_1() checks if some thread is currently resolving a fail
2353 // high at ply 1 at the node below the first root node. This information
2354 // is used for time managment.
2356 bool fail_high_ply_1() {
2357 for(int i
= 0; i
< ActiveThreads
; i
++)
2358 if(Threads
[i
].failHighPly1
)
2364 // current_search_time() returns the number of milliseconds which have passed
2365 // since the beginning of the current search.
2367 int current_search_time() {
2368 return get_system_time() - SearchStartTime
;
2372 // nps() computes the current nodes/second count.
2375 int t
= current_search_time();
2376 return (t
> 0)? int((nodes_searched() * 1000) / t
) : 0;
2380 // poll() performs two different functions: It polls for user input, and it
2381 // looks at the time consumed so far and decides if it's time to abort the
2386 static int lastInfoTime
;
2387 int t
= current_search_time();
2392 // We are line oriented, don't read single chars
2393 std::string command
;
2394 if (!std::getline(std::cin
, command
))
2397 if (command
== "quit")
2400 PonderSearch
= false;
2403 else if(command
== "stop")
2406 PonderSearch
= false;
2408 else if(command
== "ponderhit")
2411 // Print search information
2415 else if (lastInfoTime
> t
)
2416 // HACK: Must be a new search where we searched less than
2417 // NodesBetweenPolls nodes during the first second of search.
2420 else if (t
- lastInfoTime
>= 1000)
2427 if (dbg_show_hit_rate
)
2428 dbg_print_hit_rate();
2430 std::cout
<< "info nodes " << nodes_searched() << " nps " << nps()
2431 << " time " << t
<< " hashfull " << TT
.full() << std::endl
;
2432 lock_release(&IOLock
);
2433 if (ShowCurrentLine
)
2434 Threads
[0].printCurrentLine
= true;
2436 // Should we stop the search?
2440 bool overTime
= t
> AbsoluteMaxSearchTime
2441 || (RootMoveNumber
== 1 && t
> MaxSearchTime
+ ExtraSearchTime
)
2442 || ( !FailHigh
&& !fail_high_ply_1() && !Problem
2443 && t
> 6*(MaxSearchTime
+ ExtraSearchTime
));
2445 if ( (Iteration
>= 3 && (!InfiniteSearch
&& overTime
))
2446 || (ExactMaxTime
&& t
>= ExactMaxTime
)
2447 || (Iteration
>= 3 && MaxNodes
&& nodes_searched() >= MaxNodes
))
2452 // ponderhit() is called when the program is pondering (i.e. thinking while
2453 // it's the opponent's turn to move) in order to let the engine know that
2454 // it correctly predicted the opponent's move.
2457 int t
= current_search_time();
2458 PonderSearch
= false;
2459 if(Iteration
>= 3 &&
2460 (!InfiniteSearch
&& (StopOnPonderhit
||
2461 t
> AbsoluteMaxSearchTime
||
2462 (RootMoveNumber
== 1 &&
2463 t
> MaxSearchTime
+ ExtraSearchTime
) ||
2464 (!FailHigh
&& !fail_high_ply_1() && !Problem
&&
2465 t
> 6*(MaxSearchTime
+ ExtraSearchTime
)))))
2470 // print_current_line() prints the current line of search for a given
2471 // thread. Called when the UCI option UCI_ShowCurrLine is 'true'.
2473 void print_current_line(SearchStack ss
[], int ply
, int threadID
) {
2474 assert(ply
>= 0 && ply
< PLY_MAX
);
2475 assert(threadID
>= 0 && threadID
< ActiveThreads
);
2477 if(!Threads
[threadID
].idle
) {
2479 std::cout
<< "info currline " << (threadID
+ 1);
2480 for(int p
= 0; p
< ply
; p
++)
2481 std::cout
<< " " << ss
[p
].currentMove
;
2482 std::cout
<< std::endl
;
2483 lock_release(&IOLock
);
2485 Threads
[threadID
].printCurrentLine
= false;
2486 if(threadID
+ 1 < ActiveThreads
)
2487 Threads
[threadID
+ 1].printCurrentLine
= true;
2491 // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
2492 // while the program is pondering. The point is to work around a wrinkle in
2493 // the UCI protocol: When pondering, the engine is not allowed to give a
2494 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command.
2495 // We simply wait here until one of these commands is sent, and return,
2496 // after which the bestmove and pondermove will be printed (in id_loop()).
2498 void wait_for_stop_or_ponderhit() {
2499 std::string command
;
2502 if(!std::getline(std::cin
, command
))
2505 if(command
== "quit") {
2506 OpeningBook
.close();
2511 else if(command
== "ponderhit" || command
== "stop")
2517 // idle_loop() is where the threads are parked when they have no work to do.
2518 // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint
2519 // object for which the current thread is the master.
2521 void idle_loop(int threadID
, SplitPoint
*waitSp
) {
2522 assert(threadID
>= 0 && threadID
< THREAD_MAX
);
2524 Threads
[threadID
].running
= true;
2527 if(AllThreadsShouldExit
&& threadID
!= 0)
2530 // If we are not thinking, wait for a condition to be signaled instead
2531 // of wasting CPU time polling for work:
2532 while(threadID
!= 0 && (Idle
|| threadID
>= ActiveThreads
)) {
2533 #if !defined(_MSC_VER)
2534 pthread_mutex_lock(&WaitLock
);
2535 if(Idle
|| threadID
>= ActiveThreads
)
2536 pthread_cond_wait(&WaitCond
, &WaitLock
);
2537 pthread_mutex_unlock(&WaitLock
);
2539 WaitForSingleObject(SitIdleEvent
[threadID
], INFINITE
);
2543 // If this thread has been assigned work, launch a search:
2544 if(Threads
[threadID
].workIsWaiting
) {
2545 Threads
[threadID
].workIsWaiting
= false;
2546 if(Threads
[threadID
].splitPoint
->pvNode
)
2547 sp_search_pv(Threads
[threadID
].splitPoint
, threadID
);
2549 sp_search(Threads
[threadID
].splitPoint
, threadID
);
2550 Threads
[threadID
].idle
= true;
2553 // If this thread is the master of a split point and all threads have
2554 // finished their work at this split point, return from the idle loop:
2555 if(waitSp
!= NULL
&& waitSp
->cpus
== 0)
2559 Threads
[threadID
].running
= false;
2563 // init_split_point_stack() is called during program initialization, and
2564 // initializes all split point objects.
2566 void init_split_point_stack() {
2567 for(int i
= 0; i
< THREAD_MAX
; i
++)
2568 for(int j
= 0; j
< MaxActiveSplitPoints
; j
++) {
2569 SplitPointStack
[i
][j
].parent
= NULL
;
2570 lock_init(&(SplitPointStack
[i
][j
].lock
), NULL
);
2575 // destroy_split_point_stack() is called when the program exits, and
2576 // destroys all locks in the precomputed split point objects.
2578 void destroy_split_point_stack() {
2579 for(int i
= 0; i
< THREAD_MAX
; i
++)
2580 for(int j
= 0; j
< MaxActiveSplitPoints
; j
++)
2581 lock_destroy(&(SplitPointStack
[i
][j
].lock
));
2585 // thread_should_stop() checks whether the thread with a given threadID has
2586 // been asked to stop, directly or indirectly. This can happen if a beta
2587 // cutoff has occured in thre thread's currently active split point, or in
2588 // some ancestor of the current split point.
2590 bool thread_should_stop(int threadID
) {
2591 assert(threadID
>= 0 && threadID
< ActiveThreads
);
2595 if(Threads
[threadID
].stop
)
2597 if(ActiveThreads
<= 2)
2599 for(sp
= Threads
[threadID
].splitPoint
; sp
!= NULL
; sp
= sp
->parent
)
2601 Threads
[threadID
].stop
= true;
2608 // thread_is_available() checks whether the thread with threadID "slave" is
2609 // available to help the thread with threadID "master" at a split point. An
2610 // obvious requirement is that "slave" must be idle. With more than two
2611 // threads, this is not by itself sufficient: If "slave" is the master of
2612 // some active split point, it is only available as a slave to the other
2613 // threads which are busy searching the split point at the top of "slave"'s
2614 // split point stack (the "helpful master concept" in YBWC terminology).
2616 bool thread_is_available(int slave
, int master
) {
2617 assert(slave
>= 0 && slave
< ActiveThreads
);
2618 assert(master
>= 0 && master
< ActiveThreads
);
2619 assert(ActiveThreads
> 1);
2621 if(!Threads
[slave
].idle
|| slave
== master
)
2624 if(Threads
[slave
].activeSplitPoints
== 0)
2625 // No active split points means that the thread is available as a slave
2626 // for any other thread.
2629 if(ActiveThreads
== 2)
2632 // Apply the "helpful master" concept if possible.
2633 if(SplitPointStack
[slave
][Threads
[slave
].activeSplitPoints
-1].slaves
[master
])
2640 // idle_thread_exists() tries to find an idle thread which is available as
2641 // a slave for the thread with threadID "master".
2643 bool idle_thread_exists(int master
) {
2644 assert(master
>= 0 && master
< ActiveThreads
);
2645 assert(ActiveThreads
> 1);
2647 for(int i
= 0; i
< ActiveThreads
; i
++)
2648 if(thread_is_available(i
, master
))
2654 // split() does the actual work of distributing the work at a node between
2655 // several threads at PV nodes. If it does not succeed in splitting the
2656 // node (because no idle threads are available, or because we have no unused
2657 // split point objects), the function immediately returns false. If
2658 // splitting is possible, a SplitPoint object is initialized with all the
2659 // data that must be copied to the helper threads (the current position and
2660 // search stack, alpha, beta, the search depth, etc.), and we tell our
2661 // helper threads that they have been assigned work. This will cause them
2662 // to instantly leave their idle loops and call sp_search_pv(). When all
2663 // threads have returned from sp_search_pv (or, equivalently, when
2664 // splitPoint->cpus becomes 0), split() returns true.
2666 bool split(const Position
&p
, SearchStack
*sstck
, int ply
,
2667 Value
*alpha
, Value
*beta
, Value
*bestValue
, Depth depth
, int *moves
,
2668 MovePicker
*mp
, Bitboard dcCandidates
, int master
, bool pvNode
) {
2671 assert(sstck
!= NULL
);
2672 assert(ply
>= 0 && ply
< PLY_MAX
);
2673 assert(*bestValue
>= -VALUE_INFINITE
&& *bestValue
<= *alpha
);
2674 assert(!pvNode
|| *alpha
< *beta
);
2675 assert(*beta
<= VALUE_INFINITE
);
2676 assert(depth
> Depth(0));
2677 assert(master
>= 0 && master
< ActiveThreads
);
2678 assert(ActiveThreads
> 1);
2680 SplitPoint
*splitPoint
;
2685 // If no other thread is available to help us, or if we have too many
2686 // active split points, don't split:
2687 if(!idle_thread_exists(master
) ||
2688 Threads
[master
].activeSplitPoints
>= MaxActiveSplitPoints
) {
2689 lock_release(&MPLock
);
2693 // Pick the next available split point object from the split point stack:
2694 splitPoint
= SplitPointStack
[master
] + Threads
[master
].activeSplitPoints
;
2695 Threads
[master
].activeSplitPoints
++;
2697 // Initialize the split point object:
2698 splitPoint
->parent
= Threads
[master
].splitPoint
;
2699 splitPoint
->finished
= false;
2700 splitPoint
->ply
= ply
;
2701 splitPoint
->depth
= depth
;
2702 splitPoint
->alpha
= pvNode
? *alpha
: (*beta
- 1);
2703 splitPoint
->beta
= *beta
;
2704 splitPoint
->pvNode
= pvNode
;
2705 splitPoint
->dcCandidates
= dcCandidates
;
2706 splitPoint
->bestValue
= *bestValue
;
2707 splitPoint
->master
= master
;
2708 splitPoint
->mp
= mp
;
2709 splitPoint
->moves
= *moves
;
2710 splitPoint
->cpus
= 1;
2711 splitPoint
->pos
.copy(p
);
2712 splitPoint
->parentSstack
= sstck
;
2713 for(i
= 0; i
< ActiveThreads
; i
++)
2714 splitPoint
->slaves
[i
] = 0;
2716 // Copy the current position and the search stack to the master thread:
2717 memcpy(splitPoint
->sstack
[master
], sstck
, (ply
+1)*sizeof(SearchStack
));
2718 Threads
[master
].splitPoint
= splitPoint
;
2720 // Make copies of the current position and search stack for each thread:
2721 for(i
= 0; i
< ActiveThreads
&& splitPoint
->cpus
< MaxThreadsPerSplitPoint
;
2723 if(thread_is_available(i
, master
)) {
2724 memcpy(splitPoint
->sstack
[i
], sstck
, (ply
+1)*sizeof(SearchStack
));
2725 Threads
[i
].splitPoint
= splitPoint
;
2726 splitPoint
->slaves
[i
] = 1;
2730 // Tell the threads that they have work to do. This will make them leave
2732 for(i
= 0; i
< ActiveThreads
; i
++)
2733 if(i
== master
|| splitPoint
->slaves
[i
]) {
2734 Threads
[i
].workIsWaiting
= true;
2735 Threads
[i
].idle
= false;
2736 Threads
[i
].stop
= false;
2739 lock_release(&MPLock
);
2741 // Everything is set up. The master thread enters the idle loop, from
2742 // which it will instantly launch a search, because its workIsWaiting
2743 // slot is 'true'. We send the split point as a second parameter to the
2744 // idle loop, which means that the main thread will return from the idle
2745 // loop when all threads have finished their work at this split point
2746 // (i.e. when // splitPoint->cpus == 0).
2747 idle_loop(master
, splitPoint
);
2749 // We have returned from the idle loop, which means that all threads are
2750 // finished. Update alpha, beta and bestvalue, and return:
2752 if(pvNode
) *alpha
= splitPoint
->alpha
;
2753 *beta
= splitPoint
->beta
;
2754 *bestValue
= splitPoint
->bestValue
;
2755 Threads
[master
].stop
= false;
2756 Threads
[master
].idle
= false;
2757 Threads
[master
].activeSplitPoints
--;
2758 Threads
[master
].splitPoint
= splitPoint
->parent
;
2759 lock_release(&MPLock
);
2765 // wake_sleeping_threads() wakes up all sleeping threads when it is time
2766 // to start a new search from the root.
2768 void wake_sleeping_threads() {
2769 if(ActiveThreads
> 1) {
2770 for(int i
= 1; i
< ActiveThreads
; i
++) {
2771 Threads
[i
].idle
= true;
2772 Threads
[i
].workIsWaiting
= false;
2774 #if !defined(_MSC_VER)
2775 pthread_mutex_lock(&WaitLock
);
2776 pthread_cond_broadcast(&WaitCond
);
2777 pthread_mutex_unlock(&WaitLock
);
2779 for(int i
= 1; i
< THREAD_MAX
; i
++)
2780 SetEvent(SitIdleEvent
[i
]);
2786 // init_thread() is the function which is called when a new thread is
2787 // launched. It simply calls the idle_loop() function with the supplied
2788 // threadID. There are two versions of this function; one for POSIX threads
2789 // and one for Windows threads.
2791 #if !defined(_MSC_VER)
2793 void *init_thread(void *threadID
) {
2794 idle_loop(*(int *)threadID
, NULL
);
2800 DWORD WINAPI
init_thread(LPVOID threadID
) {
2801 idle_loop(*(int *)threadID
, NULL
);