X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=f7ddfa0481f2f32697400015c408b91bdf75abc0;hp=d8c0c7dd3f4ad89db231456a5fe3c82c3324fc35;hb=30075e4abcf0430cef78ae0b7823390013e75618;hpb=b4a04d80385d76bb701f6727b0150889ec437723 diff --git a/src/search.cpp b/src/search.cpp index d8c0c7dd..f7ddfa04 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -32,7 +32,9 @@ #include "evaluate.h" #include "history.h" #include "misc.h" +#include "movegen.h" #include "movepick.h" +#include "lock.h" #include "san.h" #include "search.h" #include "thread.h" @@ -107,7 +109,7 @@ namespace { class RootMoveList { public: - RootMoveList(Position &pos, Move searchMoves[]); + RootMoveList(Position& pos, Move searchMoves[]); inline Move get_move(int moveNum) const; inline Value get_move_score(int moveNum) const; inline void set_move_score(int moveNum, Value score); @@ -128,94 +130,90 @@ namespace { }; - /// Constants and variables initialized from UCI options + /// Constants - // Minimum number of full depth (i.e. non-reduced) moves at PV and non-PV - // nodes - int LMRPVMoves, LMRNonPVMoves; - - // Depth limit for use of dynamic threat detection - Depth ThreatDepth; + // Search depth at iteration 1 + const Depth InitialDepth = OnePly /*+ OnePly/2*/; // Depth limit for selective search - const Depth SelectiveDepth = 7*OnePly; + const Depth SelectiveDepth = 7 * OnePly; // Use internal iterative deepening? const bool UseIIDAtPVNodes = true; const bool UseIIDAtNonPVNodes = false; - // Internal iterative deepening margin. At Non-PV moves, when - // UseIIDAtNonPVNodes is true, we do an internal iterative deepening search - // when the static evaluation is at most IIDMargin below beta. + // Internal iterative deepening margin. At Non-PV moves, when + // UseIIDAtNonPVNodes is true, we do an internal iterative deepening + // search when the static evaluation is at most IIDMargin below beta. const Value IIDMargin = Value(0x100); - // Easy move margin. An easy move candidate must be at least this much + // Easy move margin. An easy move candidate must be at least this much // better than the second best move. const Value EasyMoveMargin = Value(0x200); - // Problem margin. If the score of the first move at iteration N+1 has + // Problem margin. If the score of the first move at iteration N+1 has // dropped by more than this since iteration N, the boolean variable // "Problem" is set to true, which will make the program spend some extra // time looking for a better move. const Value ProblemMargin = Value(0x28); - // No problem margin. If the boolean "Problem" is true, and a new move + // No problem margin. If the boolean "Problem" is true, and a new move // is found at the root which is less than NoProblemMargin worse than the // best move from the previous iteration, Problem is set back to false. const Value NoProblemMargin = Value(0x14); - // Null move margin. A null move search will not be done if the approximate + // Null move margin. A null move search will not be done if the approximate // evaluation of the position is more than NullMoveMargin below beta. const Value NullMoveMargin = Value(0x300); - // Pruning criterions. See the code and comments in ok_to_prune() to + // Pruning criterions. See the code and comments in ok_to_prune() to // understand their precise meaning. - const bool PruneEscapeMoves = false; + const bool PruneEscapeMoves = false; const bool PruneDefendingMoves = false; - const bool PruneBlockingMoves = false; - - // Use futility pruning? - bool UseQSearchFutilityPruning, UseFutilityPruning; + const bool PruneBlockingMoves = false; // Margins for futility pruning in the quiescence search, and at frontier - // and near frontier nodes + // and near frontier nodes. const Value FutilityMarginQS = Value(0x80); - // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply - const Value FutilityMargins[12] = { Value(0x100), Value(0x120), Value(0x200), Value(0x220), Value(0x250), Value(0x270), + // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply + const Value FutilityMargins[12] = { Value(0x100), Value(0x120), Value(0x200), Value(0x220), Value(0x250), Value(0x270), // 4 ply 4.5 ply 5 ply 5.5 ply 6 ply 6.5 ply Value(0x2A0), Value(0x2C0), Value(0x340), Value(0x360), Value(0x3A0), Value(0x3C0) }; - // Razoring - const Depth RazorDepth = 4*OnePly; + // Razoring + const Depth RazorDepth = 4*OnePly; // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply const Value RazorMargins[6] = { Value(0x180), Value(0x300), Value(0x300), Value(0x3C0), Value(0x3C0), Value(0x3C0) }; // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply - const Value RazorApprMargins[6] = { Value(0x520), Value(0x300), Value(0x300), Value(0x300), Value(0x300), Value(0x300) }; + const Value RazorApprMargins[6] = { Value(0x520), Value(0x300), Value(0x300), Value(0x300), Value(0x300), Value(0x300) }; + + + /// Variables initialized by UCI options + + // Minimum number of full depth (i.e. non-reduced) moves at PV and non-PV nodes + int LMRPVMoves, LMRNonPVMoves; // heavy SMP read access for the latter + + // Depth limit for use of dynamic threat detection + Depth ThreatDepth; // heavy SMP read access // Last seconds noise filtering (LSN) - bool UseLSNFiltering; - bool looseOnTime = false; - int LSNTime; // In milliseconds - Value LSNValue; + const bool UseLSNFiltering = true; + const int LSNTime = 4000; // In milliseconds + const Value LSNValue = value_from_centipawns(200); + bool loseOnTime = false; // Extensions. Array index 0 is used at non-PV nodes, index 1 at PV nodes. + // There is heavy SMP read access on these arrays Depth CheckExtension[2], SingleReplyExtension[2], PawnPushTo7thExtension[2]; Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2]; - // Search depth at iteration 1 - const Depth InitialDepth = OnePly /*+ OnePly/2*/; - - // Node counters - int NodesSincePoll; - int NodesBetweenPolls = 30000; - // Iteration counters int Iteration; - BetaCounterType BetaCounter; + BetaCounterType BetaCounter; // has per-thread internal data - // Scores and number of times the best move changed for each iteration: + // Scores and number of times the best move changed for each iteration IterationInfoType IterationInfo[PLY_MAX_PLUS_2]; int BestMoveChangesByIteration[PLY_MAX_PLUS_2]; @@ -225,19 +223,16 @@ namespace { // Time managment variables int SearchStartTime; int MaxNodes, MaxDepth; - int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime; - Move EasyMove; + int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime; int RootMoveNumber; bool InfiniteSearch; bool PonderSearch; bool StopOnPonderhit; - bool AbortSearch; + bool AbortSearch; // heavy SMP read access bool Quit; bool FailHigh; bool FailLow; bool Problem; - bool PonderingEnabled; - int ExactMaxTime; // Show current line? bool ShowCurrentLine; @@ -247,10 +242,12 @@ namespace { std::ofstream LogFile; // MP related variables + int ActiveThreads = 1; Depth MinimumSplitDepth; int MaxThreadsPerSplitPoint; Thread Threads[THREAD_MAX]; Lock MPLock; + Lock IOLock; bool AllThreadsShouldExit = false; const int MaxActiveSplitPoints = 8; SplitPoint SplitPointStack[THREAD_MAX][MaxActiveSplitPoints]; @@ -263,28 +260,35 @@ namespace { HANDLE SitIdleEvent[THREAD_MAX]; #endif + // Node counters, used only by thread[0] but try to keep in different + // cache lines (64 bytes each) from the heavy SMP read accessed variables. + int NodesSincePoll; + int NodesBetweenPolls = 30000; + + // History table + History H; + /// Functions - Value id_loop(const Position &pos, Move searchMoves[]); - Value root_search(Position &pos, SearchStack ss[], RootMoveList &rml, Value alpha, Value beta); - Value search_pv(Position &pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID); - Value search(Position &pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID); - Value qsearch(Position &pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID); - void sp_search(SplitPoint *sp, int threadID); - void sp_search_pv(SplitPoint *sp, int threadID); + Value id_loop(const Position& pos, Move searchMoves[]); + Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta); + Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID); + Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID); + Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID); + void sp_search(SplitPoint* sp, int threadID); + void sp_search_pv(SplitPoint* sp, int threadID); void init_node(SearchStack ss[], int ply, int threadID); void update_pv(SearchStack ss[], int ply); - void sp_update_pv(SearchStack *pss, SearchStack ss[], int ply); - bool connected_moves(const Position &pos, Move m1, Move m2); + void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply); + bool connected_moves(const Position& pos, Move m1, Move m2); bool value_is_mate(Value value); bool move_is_killer(Move m, const SearchStack& ss); - Depth extension(const Position &pos, Move m, bool pvNode, bool capture, bool check, bool singleReply, bool mateThreat, bool* dangerous); - bool ok_to_do_nullmove(const Position &pos); - bool ok_to_prune(const Position &pos, Move m, Move threat, Depth d, const History& H); + Depth extension(const Position& pos, Move m, bool pvNode, bool capture, bool check, bool singleReply, bool mateThreat, bool* dangerous); + bool ok_to_do_nullmove(const Position& pos); + bool ok_to_prune(const Position& pos, Move m, Move threat, Depth d); bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply); - bool ok_to_history(const Position &pos, Move m); - void update_history(const Position& pos, Move m, Depth depth, History& H, Move movesSearched[], int moveCount); + void update_history(const Position& pos, Move m, Depth depth, Move movesSearched[], int moveCount); void update_killers(Move m, SearchStack& ss); bool fail_high_ply_1(); @@ -294,15 +298,18 @@ namespace { void ponderhit(); void print_current_line(SearchStack ss[], int ply, int threadID); void wait_for_stop_or_ponderhit(); + void init_ss_array(SearchStack ss[]); - void idle_loop(int threadID, SplitPoint *waitSp); + void idle_loop(int threadID, SplitPoint* waitSp); void init_split_point_stack(); void destroy_split_point_stack(); bool thread_should_stop(int threadID); bool thread_is_available(int slave, int master); bool idle_thread_exists(int master); - bool split(const Position &pos, SearchStack *ss, int ply, - Value *alpha, Value *beta, Value *bestValue, Depth depth, int *moves, + bool split(const Position& pos, SearchStack* ss, int ply, + Value *alpha, Value *beta, Value *bestValue, + const Value futilityValue, const Value approximateValue, + Depth depth, int *moves, MovePicker *mp, Bitboard dcCandidates, int master, bool pvNode); void wake_sleeping_threads(); @@ -316,48 +323,46 @@ namespace { //// -//// Global variables +//// Functions //// -// The main transposition table -TranspositionTable TT; +/// perft() is our utility to verify move generation is bug free. All the +/// legal moves up to given depth are generated and counted and the sum returned. -// Number of active threads: -int ActiveThreads = 1; - -// Locks. In principle, there is no need for IOLock to be a global variable, -// but it could turn out to be useful for debugging. -Lock IOLock; - - -// SearchStack::init() initializes a search stack. Used at the beginning of a -// new search from the root. -void SearchStack::init(int ply) { - - pv[ply] = pv[ply + 1] = MOVE_NONE; - currentMove = threatMove = MOVE_NONE; - reduction = Depth(0); -} +int perft(Position& pos, Depth depth) +{ + Move move; + MovePicker mp = MovePicker(pos, MOVE_NONE, depth, H); + Bitboard dcCandidates = pos.discovered_check_candidates(pos.side_to_move()); + int sum = 0; -void SearchStack::initKillers() { + // If we are at the last ply we don't need to do and undo + // the moves, just to count them. + if (depth <= OnePly) // Replace with '<' to test also qsearch + { + while ((move = mp.get_next_move()) != MOVE_NONE) sum++; + return sum; + } - mateKiller = MOVE_NONE; - for (int i = 0; i < KILLER_MAX; i++) - killers[i] = MOVE_NONE; + // Loop through all legal moves + while ((move = mp.get_next_move()) != MOVE_NONE) + { + StateInfo st; + pos.do_move(move, st, dcCandidates); + sum += perft(pos, depth - OnePly); + pos.undo_move(move); + } + return sum; } -//// -//// Functions -//// - /// think() is the external interface to Stockfish's search, and is called when /// the program receives the UCI 'go' command. It initializes various /// search-related global variables, and calls root_search(). It returns false /// when a quit command is received during the search. -bool think(const Position &pos, bool infinite, bool ponder, int side_to_move, +bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, int time[], int increment[], int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) { @@ -379,7 +384,6 @@ bool think(const Position &pos, bool infinite, bool ponder, int side_to_move, // Initialize global search variables Idle = false; SearchStartTime = get_system_time(); - EasyMove = MOVE_NONE; for (int i = 0; i < THREAD_MAX; i++) { Threads[i].nodes = 0ULL; @@ -399,9 +403,12 @@ bool think(const Position &pos, bool infinite, bool ponder, int side_to_move, // Read UCI option values TT.set_size(get_option_value_int("Hash")); if (button_was_pressed("Clear Hash")) + { TT.clear(); + loseOnTime = false; // reset at the beginning of a new game + } - PonderingEnabled = get_option_value_bool("Ponder"); + bool PonderingEnabled = get_option_value_bool("Ponder"); MultiPV = get_option_value_int("MultiPV"); CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)")); @@ -422,9 +429,9 @@ bool think(const Position &pos, bool infinite, bool ponder, int side_to_move, MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)")); MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)")); - LMRPVMoves = get_option_value_int("Full Depth Moves (PV nodes)") + 1; - LMRNonPVMoves = get_option_value_int("Full Depth Moves (non-PV nodes)") + 1; - ThreatDepth = get_option_value_int("Threat Depth") * OnePly; + LMRPVMoves = get_option_value_int("Full Depth Moves (PV nodes)") + 1; + LMRNonPVMoves = get_option_value_int("Full Depth Moves (non-PV nodes)") + 1; + ThreatDepth = get_option_value_int("Threat Depth") * OnePly; Chess960 = get_option_value_bool("UCI_Chess960"); ShowCurrentLine = get_option_value_bool("UCI_ShowCurrLine"); @@ -432,18 +439,12 @@ bool think(const Position &pos, bool infinite, bool ponder, int side_to_move, if (UseLogFile) LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app); - UseQSearchFutilityPruning = get_option_value_bool("Futility Pruning (Quiescence Search)"); - UseFutilityPruning = get_option_value_bool("Futility Pruning (Main Search)"); - - UseLSNFiltering = get_option_value_bool("LSN filtering"); - LSNTime = get_option_value_int("LSN Time Margin (sec)") * 1000; - LSNValue = value_from_centipawns(get_option_value_int("LSN Value Margin")); - MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly; MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point"); read_weights(pos.side_to_move()); + // Set the number of active threads int newActiveThreads = get_option_value_int("Threads"); if (newActiveThreads != ActiveThreads) { @@ -451,13 +452,13 @@ bool think(const Position &pos, bool infinite, bool ponder, int side_to_move, init_eval(ActiveThreads); } - // Wake up sleeping threads: + // Wake up sleeping threads wake_sleeping_threads(); for (int i = 1; i < ActiveThreads; i++) assert(thread_is_available(i, 0)); - // Set thinking time: + // Set thinking time int myTime = time[side_to_move]; int myIncrement = increment[side_to_move]; @@ -477,7 +478,8 @@ bool think(const Position &pos, bool infinite, bool ponder, int side_to_move, if (movesToGo == 1) { MaxSearchTime = myTime / 2; - AbsoluteMaxSearchTime = Min(myTime / 2, myTime - 500); + AbsoluteMaxSearchTime = + (myTime > 3000)? (myTime - 500) : ((myTime * 3) / 4); } else { MaxSearchTime = myTime / Min(movesToGo, 20); AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3); @@ -501,33 +503,37 @@ bool think(const Position &pos, bool infinite, bool ponder, int side_to_move, NodesBetweenPolls = Min(MaxNodes, 30000); InfiniteSearch = true; // HACK } + else if (myTime && myTime < 1000) + NodesBetweenPolls = 1000; + else if (myTime && myTime < 5000) + NodesBetweenPolls = 5000; else NodesBetweenPolls = 30000; - - // Write information to search log file: + // Write information to search log file if (UseLogFile) LogFile << "Searching: " << pos.to_fen() << std::endl - << "infinite: " << infinite - << " ponder: " << ponder - << " time: " << myTime + << "infinite: " << infinite + << " ponder: " << ponder + << " time: " << myTime << " increment: " << myIncrement << " moves to go: " << movesToGo << std::endl; - // We're ready to start thinking. Call the iterative deepening loop - // function: - if (!looseOnTime) + // We're ready to start thinking. Call the iterative deepening loop function + // + // FIXME we really need to cleanup all this LSN ugliness + if (!loseOnTime) { Value v = id_loop(pos, searchMoves); - looseOnTime = ( UseLSNFiltering - && myTime < LSNTime - && myIncrement == 0 - && v < -LSNValue); + loseOnTime = ( UseLSNFiltering + && myTime < LSNTime + && myIncrement == 0 + && v < -LSNValue); } else { - looseOnTime = false; // reset for next match + loseOnTime = false; // reset for next match while (SearchStartTime + myTime + 1000 > get_system_time()) ; // wait here id_loop(pos, searchMoves); // to fail gracefully @@ -556,7 +562,7 @@ void init_threads() { for (i = 0; i < THREAD_MAX; i++) Threads[i].activeSplitPoints = 0; - // Initialize global locks: + // Initialize global locks lock_init(&MPLock, NULL); lock_init(&IOLock, NULL); @@ -589,7 +595,7 @@ void init_threads() { CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID); #endif - // Wait until the thread has finished launching: + // Wait until the thread has finished launching while (!Threads[i].running); } } @@ -625,6 +631,22 @@ int64_t nodes_searched() { } +// SearchStack::init() initializes a search stack. Used at the beginning of a +// new search from the root. +void SearchStack::init(int ply) { + + pv[ply] = pv[ply + 1] = MOVE_NONE; + currentMove = threatMove = MOVE_NONE; + reduction = Depth(0); +} + +void SearchStack::initKillers() { + + mateKiller = MOVE_NONE; + for (int i = 0; i < KILLER_MAX; i++) + killers[i] = MOVE_NONE; +} + namespace { // id_loop() is the main iterative deepening loop. It calls root_search @@ -632,7 +654,7 @@ namespace { // been consumed, the user stops the search, or the maximum search depth is // reached. - Value id_loop(const Position &pos, Move searchMoves[]) { + Value id_loop(const Position& pos, Move searchMoves[]) { Position p(pos); SearchStack ss[PLY_MAX_PLUS_2]; @@ -640,20 +662,23 @@ namespace { // searchMoves are verified, copied, scored and sorted RootMoveList rml(p, searchMoves); + // Print RootMoveList c'tor startup scoring to the standard output, + // so that we print information also for iteration 1. + std::cout << "info depth " << 1 << "\ninfo depth " << 1 + << " score " << value_to_string(rml.get_move_score(0)) + << " time " << current_search_time() + << " nodes " << nodes_searched() + << " nps " << nps() + << " pv " << rml.get_move(0) << "\n"; + // Initialize TT.new_search(); - for (int i = 0; i < THREAD_MAX; i++) - Threads[i].H.clear(); - - for (int i = 0; i < 3; i++) - { - ss[i].init(i); - ss[i].initKillers(); - } + H.clear(); + init_ss_array(ss); IterationInfo[1] = IterationInfoType(rml.get_move_score(0), rml.get_move_score(0)); Iteration = 1; - EasyMove = rml.scan_for_easy_move(); + Move EasyMove = rml.scan_for_easy_move(); // Iterative deepening loop while (Iteration < PLY_MAX) @@ -670,7 +695,7 @@ namespace { // Calculate dynamic search window based on previous iterations Value alpha, beta; - if (MultiPV == 1 && Iteration >= 6) + if (MultiPV == 1 && Iteration >= 6 && abs(IterationInfo[Iteration - 1].value) < VALUE_KNOWN_WIN) { int prevDelta1 = IterationInfo[Iteration - 1].speculatedValue - IterationInfo[Iteration - 2].speculatedValue; int prevDelta2 = IterationInfo[Iteration - 2].speculatedValue - IterationInfo[Iteration - 3].speculatedValue; @@ -735,7 +760,7 @@ namespace { // Time to stop? bool stopSearch = false; - // Stop search early if there is only a single legal move: + // Stop search early if there is only a single legal move if (Iteration >= 6 && rml.move_count() == 1) stopSearch = true; @@ -833,7 +858,7 @@ namespace { // scheme (perhaps we should try to use this at internal PV nodes, too?) // and prints some information to the standard output. - Value root_search(Position &pos, SearchStack ss[], RootMoveList &rml, Value alpha, Value beta) { + Value root_search(Position& pos, SearchStack ss[], RootMoveList &rml, Value alpha, Value beta) { Value oldAlpha = alpha; Value value; @@ -873,8 +898,9 @@ namespace { << " currmovenumber " << i + 1 << std::endl; // Decide search depth for this move + bool captureOrPromotion = pos.move_is_capture_or_promotion(move); bool dangerous; - ext = extension(pos, move, true, pos.move_is_capture(move), pos.move_is_check(move), false, false, &dangerous); + ext = extension(pos, move, true, captureOrPromotion, pos.move_is_check(move), false, false, &dangerous); newDepth = (Iteration - 2) * OnePly + ext + InitialDepth; // Make the move, and search it @@ -898,15 +924,29 @@ namespace { } else { - value = -search(pos, ss, -alpha, newDepth, 1, true, 0); + if ( newDepth >= 3*OnePly + && i >= MultiPV + LMRPVMoves + && !dangerous + && !captureOrPromotion + && !move_is_castle(move)) + { + ss[0].reduction = OnePly; + value = -search(pos, ss, -alpha, newDepth-OnePly, 1, true, 0); + } else + value = alpha + 1; // Just to trigger next condition + if (value > alpha) { - // Fail high! Set the boolean variable FailHigh to true, and - // re-search the move with a big window. The variable FailHigh is - // used for time managment: We try to avoid aborting the search - // prematurely during a fail high research. - FailHigh = true; - value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); + value = -search(pos, ss, -alpha, newDepth, 1, true, 0); + if (value > alpha) + { + // Fail high! Set the boolean variable FailHigh to true, and + // re-search the move with a big window. The variable FailHigh is + // used for time managment: We try to avoid aborting the search + // prematurely during a fail high research. + FailHigh = true; + value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); + } } } @@ -940,6 +980,7 @@ namespace { // Update PV rml.set_move_score(i, value); update_pv(ss, 0); + TT.extract_pv(pos, ss[0].pv, PLY_MAX); rml.set_move_pv(i, ss[0].pv); if (MultiPV == 1) @@ -950,9 +991,11 @@ namespace { if (i > 0) BestMoveChangesByIteration[Iteration]++; - // Print search information to the standard output: + // Print search information to the standard output std::cout << "info depth " << Iteration << " score " << value_to_string(value) + << ((value >= beta)? + " lowerbound" : ((value <= alpha)? " upperbound" : "")) << " time " << current_search_time() << " nodes " << nodes_searched() << " nps " << nps() @@ -964,7 +1007,10 @@ namespace { std::cout << std::endl; if (UseLogFile) - LogFile << pretty_pv(pos, current_search_time(), Iteration, nodes_searched(), value, ss[0].pv) + LogFile << pretty_pv(pos, current_search_time(), Iteration, nodes_searched(), value, + ((value >= beta)? VALUE_TYPE_LOWER + : ((value <= alpha)? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT)), + ss[0].pv) << std::endl; if (value > alpha) @@ -1008,7 +1054,7 @@ namespace { // search_pv() is the main search function for PV nodes. - Value search_pv(Position &pos, SearchStack ss[], Value alpha, Value beta, + Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID) { assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); @@ -1016,6 +1062,18 @@ namespace { assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); + Move movesSearched[256]; + EvalInfo ei; + StateInfo st; + Bitboard dcCandidates; + const TTEntry* tte; + Move ttMove, move; + Depth ext, newDepth; + Value oldAlpha, value; + bool isCheck, mateThreat, singleReply, moveIsCheck, captureOrPromotion, dangerous; + int moveCount = 0; + Value bestValue = -VALUE_INFINITE; + if (depth < OnePly) return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID); @@ -1030,13 +1088,11 @@ namespace { if (pos.is_draw()) return VALUE_DRAW; - EvalInfo ei; - if (ply >= PLY_MAX - 1) - return evaluate(pos, ei, threadID); + return pos.is_check() ? quick_evaluate(pos) : evaluate(pos, ei, threadID); // Mate distance pruning - Value oldAlpha = alpha; + oldAlpha = alpha; alpha = Max(value_mated_in(ply), alpha); beta = Min(value_mate_in(ply+1), beta); if (alpha >= beta) @@ -1044,8 +1100,8 @@ namespace { // Transposition table lookup. At PV nodes, we don't use the TT for // pruning, but only for move ordering. - const TTEntry* tte = TT.retrieve(pos.get_key()); - Move ttMove = (tte ? tte->move() : MOVE_NONE); + tte = TT.retrieve(pos.get_key()); + ttMove = (tte ? tte->move() : MOVE_NONE); // Go with internal iterative deepening if we don't have a TT move if (UseIIDAtPVNodes && ttMove == MOVE_NONE && depth >= 5*OnePly) @@ -1056,15 +1112,11 @@ namespace { // Initialize a MovePicker object for the current position, and prepare // to search all moves - MovePicker mp = MovePicker(pos, true, ttMove, depth, Threads[threadID].H, &ss[ply]); - - Move move, movesSearched[256]; - int moveCount = 0; - Value value, bestValue = -VALUE_INFINITE; - Bitboard dcCandidates = mp.discovered_check_candidates(); - Color us = pos.side_to_move(); - bool isCheck = pos.is_check(); - bool mateThreat = pos.has_mate_threat(opposite_color(us)); + isCheck = pos.is_check(); + mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move())); + CheckInfo ci(pos); + dcCandidates = ci.dc; + MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); // Loop through all legal moves until no moves remain or a beta cutoff // occurs. @@ -1074,19 +1126,17 @@ namespace { { assert(move_is_ok(move)); - bool singleReply = (isCheck && mp.number_of_moves() == 1); - bool moveIsCheck = pos.move_is_check(move, dcCandidates); - bool moveIsCapture = pos.move_is_capture(move); + singleReply = (isCheck && mp.number_of_evasions() == 1); + moveIsCheck = pos.move_is_check(move, dcCandidates); + captureOrPromotion = pos.move_is_capture_or_promotion(move); movesSearched[moveCount++] = ss[ply].currentMove = move; // Decide the new search depth - bool dangerous; - Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous); - Depth newDepth = depth - OnePly + ext; + ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, singleReply, mateThreat, &dangerous); + newDepth = depth - OnePly + ext; // Make and search the move - StateInfo st; pos.do_move(move, st, dcCandidates); if (moveCount == 1) // The first move in list is the PV @@ -1095,11 +1145,10 @@ namespace { { // Try to reduce non-pv search depth by one ply if move seems not problematic, // if the move fails high will be re-searched at full depth. - if ( depth >= 2*OnePly + if ( depth >= 3*OnePly && moveCount >= LMRPVMoves && !dangerous - && !moveIsCapture - && !move_promotion(move) + && !captureOrPromotion && !move_is_castle(move) && !move_is_killer(move, ss[ply])) { @@ -1146,7 +1195,7 @@ namespace { } // If we are at ply 1, and we are searching the first root move at // ply 0, set the 'Problem' variable if the score has dropped a lot - // (from the computer's point of view) since the previous iteration: + // (from the computer's point of view) since the previous iteration. if ( ply == 1 && Iteration >= 2 && -value <= IterationInfo[Iteration-1].value - ProblemMargin) @@ -1161,13 +1210,13 @@ namespace { && idle_thread_exists(threadID) && !AbortSearch && !thread_should_stop(threadID) - && split(pos, ss, ply, &alpha, &beta, &bestValue, depth, + && split(pos, ss, ply, &alpha, &beta, &bestValue, VALUE_NONE, VALUE_NONE, depth, &moveCount, &mp, dcCandidates, threadID, true)) break; } // All legal moves have been searched. A special case: If there were - // no legal moves, it must be mate or stalemate: + // no legal moves, it must be mate or stalemate. if (moveCount == 0) return (isCheck ? value_mated_in(ply) : VALUE_DRAW); @@ -1182,13 +1231,13 @@ namespace { else if (bestValue >= beta) { BetaCounter.add(pos.side_to_move(), depth, threadID); - Move m = ss[ply].pv[ply]; - if (ok_to_history(pos, m)) // Only non capture moves are considered + move = ss[ply].pv[ply]; + if (!pos.move_is_capture_or_promotion(move)) { - update_history(pos, m, depth, Threads[threadID].H, movesSearched, moveCount); - update_killers(m, ss[ply]); + update_history(pos, move, depth, movesSearched, moveCount); + update_killers(move, ss[ply]); } - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m); + TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move); } else TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]); @@ -1199,13 +1248,26 @@ namespace { // search() is the search function for zero-width nodes. - Value search(Position &pos, SearchStack ss[], Value beta, Depth depth, + Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID) { assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE); assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); + Move movesSearched[256]; + EvalInfo ei; + StateInfo st; + Bitboard dcCandidates; + const TTEntry* tte; + Move ttMove, move; + Depth ext, newDepth; + Value approximateEval, nullValue, value, futilityValue; + bool isCheck, useFutilityPruning, singleReply, moveIsCheck, captureOrPromotion, dangerous; + bool mateThreat = false; + int moveCount = 0; + Value bestValue = -VALUE_INFINITE; + if (depth < OnePly) return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID); @@ -1220,10 +1282,8 @@ namespace { if (pos.is_draw()) return VALUE_DRAW; - EvalInfo ei; - if (ply >= PLY_MAX - 1) - return evaluate(pos, ei, threadID); + return pos.is_check() ? quick_evaluate(pos) : evaluate(pos, ei, threadID); // Mate distance pruning if (value_mated_in(ply) >= beta) @@ -1233,8 +1293,8 @@ namespace { return beta - 1; // Transposition table lookup - const TTEntry* tte = TT.retrieve(pos.get_key()); - Move ttMove = (tte ? tte->move() : MOVE_NONE); + tte = TT.retrieve(pos.get_key()); + ttMove = (tte ? tte->move() : MOVE_NONE); if (tte && ok_to_use_TT(tte, depth, beta, ply)) { @@ -1242,9 +1302,8 @@ namespace { return value_from_tt(tte->value(), ply); } - Value approximateEval = quick_evaluate(pos); - bool mateThreat = false; - bool isCheck = pos.is_check(); + approximateEval = quick_evaluate(pos); + isCheck = pos.is_check(); // Null move search if ( allowNullmove @@ -1256,19 +1315,14 @@ namespace { { ss[ply].currentMove = MOVE_NULL; - StateInfo st; pos.do_null_move(st); int R = (depth >= 5 * OnePly ? 4 : 3); // Null move dynamic reduction - Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID); + nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID); pos.undo_null_move(); - if (value_is_mate(nullValue)) - { - /* Do not return unproven mates */ - } - else if (nullValue >= beta) + if (nullValue >= beta) { if (depth < 6 * OnePly) return beta; @@ -1316,17 +1370,16 @@ namespace { } // Initialize a MovePicker object for the current position, and prepare - // to search all moves: - MovePicker mp = MovePicker(pos, false, ttMove, depth, Threads[threadID].H, &ss[ply]); + // to search all moves. + MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); + CheckInfo ci(pos); + dcCandidates = ci.dc; + futilityValue = VALUE_NONE; + useFutilityPruning = depth < SelectiveDepth && !isCheck; - Move move, movesSearched[256]; - int moveCount = 0; - Value value, bestValue = -VALUE_INFINITE; - Bitboard dcCandidates = mp.discovered_check_candidates(); - Value futilityValue = VALUE_NONE; - bool useFutilityPruning = UseFutilityPruning - && depth < SelectiveDepth - && !isCheck; + // Avoid calling evaluate() if we already have the score in TT + if (tte && (tte->type() & VALUE_TYPE_EVAL)) + futilityValue = value_from_tt(tte->value(), ply) + FutilityMargins[int(depth) - 2]; // Loop through all legal moves until no moves remain or a beta cutoff // occurs. @@ -1336,26 +1389,25 @@ namespace { { assert(move_is_ok(move)); - bool singleReply = (isCheck && mp.number_of_moves() == 1); - bool moveIsCheck = pos.move_is_check(move, dcCandidates); - bool moveIsCapture = pos.move_is_capture(move); + singleReply = (isCheck && mp.number_of_evasions() == 1); + moveIsCheck = pos.move_is_check(move, dcCandidates); + captureOrPromotion = pos.move_is_capture_or_promotion(move); movesSearched[moveCount++] = ss[ply].currentMove = move; // Decide the new search depth - bool dangerous; - Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous); - Depth newDepth = depth - OnePly + ext; + ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, singleReply, mateThreat, &dangerous); + newDepth = depth - OnePly + ext; // Futility pruning if ( useFutilityPruning && !dangerous - && !moveIsCapture - && !move_promotion(move)) + && !captureOrPromotion) { // History pruning. See ok_to_prune() definition if ( moveCount >= 2 + int(depth) - && ok_to_prune(pos, move, ss[ply].threatMove, depth, Threads[threadID].H)) + && ok_to_prune(pos, move, ss[ply].threatMove, depth) + && bestValue > value_mated_in(PLY_MAX)) continue; // Value based pruning @@ -1375,16 +1427,14 @@ namespace { } // Make and search the move - StateInfo st; pos.do_move(move, st, dcCandidates); // Try to reduce non-pv search depth by one ply if move seems not problematic, // if the move fails high will be re-searched at full depth. - if ( depth >= 2*OnePly + if ( depth >= 3*OnePly && moveCount >= LMRNonPVMoves && !dangerous - && !moveIsCapture - && !move_promotion(move) + && !captureOrPromotion && !move_is_castle(move) && !move_is_killer(move, ss[ply])) { @@ -1422,7 +1472,7 @@ namespace { && idle_thread_exists(threadID) && !AbortSearch && !thread_should_stop(threadID) - && split(pos, ss, ply, &beta, &beta, &bestValue, depth, &moveCount, + && split(pos, ss, ply, &beta, &beta, &bestValue, futilityValue, approximateEval, depth, &moveCount, &mp, dcCandidates, threadID, false)) break; } @@ -1442,13 +1492,13 @@ namespace { else { BetaCounter.add(pos.side_to_move(), depth, threadID); - Move m = ss[ply].pv[ply]; - if (ok_to_history(pos, m)) // Only non capture moves are considered + move = ss[ply].pv[ply]; + if (!pos.move_is_capture_or_promotion(move)) { - update_history(pos, m, depth, Threads[threadID].H, movesSearched, moveCount); - update_killers(m, ss[ply]); + update_history(pos, move, depth, movesSearched, moveCount); + update_killers(move, ss[ply]); } - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m); + TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move); } assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1461,7 +1511,7 @@ namespace { // search function when the remaining depth is zero (or, to be more precise, // less than OnePly). - Value qsearch(Position &pos, SearchStack ss[], Value alpha, Value beta, + Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID) { assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); @@ -1470,6 +1520,16 @@ namespace { assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); + EvalInfo ei; + StateInfo st; + Bitboard dcCandidates; + Move ttMove, move; + Value staticValue, bestValue, value, futilityValue; + bool isCheck, enoughMaterial; + const TTEntry* tte = NULL; + int moveCount = 0; + bool pvNode = (beta - alpha != 1); + // Initialize, and make an early exit in case of an aborted search, // an instant draw, maximum ply reached, etc. init_node(ss, ply, threadID); @@ -1482,8 +1542,6 @@ namespace { return VALUE_DRAW; // Transposition table lookup, only when not in PV - TTEntry* tte = NULL; - bool pvNode = (beta - alpha != 1); if (!pvNode) { tte = TT.retrieve(pos.get_key()); @@ -1494,21 +1552,18 @@ namespace { return value_from_tt(tte->value(), ply); } } - Move ttMove = (tte ? tte->move() : MOVE_NONE); + ttMove = (tte ? tte->move() : MOVE_NONE); // Evaluate the position statically - EvalInfo ei; - Value staticValue; - bool isCheck = pos.is_check(); + isCheck = pos.is_check(); ei.futilityMargin = Value(0); // Manually initialize futilityMargin if (isCheck) staticValue = -VALUE_INFINITE; - else if (tte && tte->type() == VALUE_TYPE_EVAL) + else if (tte && (tte->type() & VALUE_TYPE_EVAL)) { // Use the cached evaluation score if possible - assert(tte->value() == evaluate(pos, ei, threadID)); assert(ei.futilityMargin == Value(0)); staticValue = tte->value(); @@ -1516,18 +1571,18 @@ namespace { else staticValue = evaluate(pos, ei, threadID); - if (ply == PLY_MAX - 1) - return evaluate(pos, ei, threadID); + if (ply >= PLY_MAX - 1) + return pos.is_check() ? quick_evaluate(pos) : evaluate(pos, ei, threadID); // Initialize "stand pat score", and return it immediately if it is // at least beta. - Value bestValue = staticValue; + bestValue = staticValue; if (bestValue >= beta) { // Store the score to avoid a future costly evaluation() call if (!isCheck && !tte && ei.futilityMargin == 0) - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EVAL, Depth(-127*OnePly), MOVE_NONE); + TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EV_LO, Depth(-127*OnePly), MOVE_NONE); return bestValue; } @@ -1538,12 +1593,10 @@ namespace { // Initialize a MovePicker object for the current position, and prepare // to search the moves. Because the depth is <= 0 here, only captures, // queen promotions and checks (only if depth == 0) will be generated. - MovePicker mp = MovePicker(pos, pvNode, ttMove, depth, Threads[threadID].H); - Move move; - int moveCount = 0; - Bitboard dcCandidates = mp.discovered_check_candidates(); - Color us = pos.side_to_move(); - bool enoughMaterial = pos.non_pawn_material(us) > RookValueMidgame; + MovePicker mp = MovePicker(pos, ttMove, depth, H); + CheckInfo ci(pos); + dcCandidates = ci.dc; + enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame; // Loop through the moves until no moves remain or a beta cutoff // occurs. @@ -1556,20 +1609,19 @@ namespace { ss[ply].currentMove = move; // Futility pruning - if ( UseQSearchFutilityPruning - && enoughMaterial + if ( enoughMaterial && !isCheck && !pvNode - && !move_promotion(move) + && !move_is_promotion(move) && !pos.move_is_check(move, dcCandidates) && !pos.move_is_passed_pawn_push(move)) { - Value futilityValue = staticValue - + Max(pos.midgame_value_of_piece_on(move_to(move)), - pos.endgame_value_of_piece_on(move_to(move))) - + (move_is_ep(move) ? PawnValueEndgame : Value(0)) - + FutilityMarginQS - + ei.futilityMargin; + futilityValue = staticValue + + Max(pos.midgame_value_of_piece_on(move_to(move)), + pos.endgame_value_of_piece_on(move_to(move))) + + (move_is_ep(move) ? PawnValueEndgame : Value(0)) + + FutilityMarginQS + + ei.futilityMargin; if (futilityValue < alpha) { @@ -1581,16 +1633,14 @@ namespace { // Don't search captures and checks with negative SEE values if ( !isCheck - && !move_promotion(move) - && (pos.midgame_value_of_piece_on(move_from(move)) > - pos.midgame_value_of_piece_on(move_to(move))) - && pos.see(move) < 0) + && move != ttMove + && !move_is_promotion(move) + && pos.see_sign(move) < 0) continue; - // Make and search the move. - StateInfo st; + // Make and search the move pos.do_move(move, st, dcCandidates); - Value value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID); + value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID); pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); @@ -1608,26 +1658,30 @@ namespace { } // All legal moves have been searched. A special case: If we're in check - // and no legal moves were found, it is checkmate: - if (pos.is_check() && moveCount == 0) // Mate! + // and no legal moves were found, it is checkmate. + if (!moveCount && pos.is_check()) // Mate! return value_mated_in(ply); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); // Update transposition table - Move m = ss[ply].pv[ply]; + move = ss[ply].pv[ply]; if (!pvNode) { + // If bestValue isn't changed it means it is still the static evaluation of + // the node, so keep this info to avoid a future costly evaluation() call. + ValueType type = (bestValue == staticValue && !ei.futilityMargin ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER); Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1)); + if (bestValue < beta) - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, d, MOVE_NONE); + TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE); else - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, m); + TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, move); } // Update killers only for good check moves - if (alpha >= beta && ok_to_history(pos, m)) // Only non capture moves are considered - update_killers(m, ss[ply]); + if (alpha >= beta && !pos.move_is_capture_or_promotion(move)) + update_killers(move, ss[ply]); return bestValue; } @@ -1641,18 +1695,17 @@ namespace { // also don't need to store anything to the hash table here: This is taken // care of after we return from the split point. - void sp_search(SplitPoint *sp, int threadID) { + void sp_search(SplitPoint* sp, int threadID) { assert(threadID >= 0 && threadID < ActiveThreads); assert(ActiveThreads > 1); Position pos = Position(sp->pos); - SearchStack *ss = sp->sstack[threadID]; + SearchStack* ss = sp->sstack[threadID]; Value value; Move move; bool isCheck = pos.is_check(); - bool useFutilityPruning = UseFutilityPruning - && sp->depth < SelectiveDepth + bool useFutilityPruning = sp->depth < SelectiveDepth && !isCheck; while ( sp->bestValue < sp->beta @@ -1662,7 +1715,7 @@ namespace { assert(move_is_ok(move)); bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates); - bool moveIsCapture = pos.move_is_capture(move); + bool captureOrPromotion = pos.move_is_capture_or_promotion(move); lock_grab(&(sp->lock)); int moveCount = ++sp->moves; @@ -1672,17 +1725,43 @@ namespace { // Decide the new search depth. bool dangerous; - Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, false, false, &dangerous); + Depth ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous); Depth newDepth = sp->depth - OnePly + ext; // Prune? if ( useFutilityPruning && !dangerous - && !moveIsCapture - && !move_promotion(move) - && moveCount >= 2 + int(sp->depth) - && ok_to_prune(pos, move, ss[sp->ply].threatMove, sp->depth, Threads[threadID].H)) - continue; + && !captureOrPromotion) + { + // History pruning. See ok_to_prune() definition + if ( moveCount >= 2 + int(sp->depth) + && ok_to_prune(pos, move, ss[sp->ply].threatMove, sp->depth) + && sp->bestValue > value_mated_in(PLY_MAX)) + continue; + + // Value based pruning + if (sp->approximateEval < sp->beta) + { + if (sp->futilityValue == VALUE_NONE) + { + EvalInfo ei; + sp->futilityValue = evaluate(pos, ei, threadID) + + FutilityMargins[int(sp->depth) - 2]; + } + + if (sp->futilityValue < sp->beta) + { + if (sp->futilityValue > sp->bestValue) // Less then 1% of cases + { + lock_grab(&(sp->lock)); + if (sp->futilityValue > sp->bestValue) + sp->bestValue = sp->futilityValue; + lock_release(&(sp->lock)); + } + continue; + } + } + } // Make and search the move. StateInfo st; @@ -1692,8 +1771,7 @@ namespace { // if the move fails high will be re-searched at full depth. if ( !dangerous && moveCount >= LMRNonPVMoves - && !moveIsCapture - && !move_promotion(move) + && !captureOrPromotion && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) { @@ -1716,27 +1794,30 @@ namespace { break; // New best move? - lock_grab(&(sp->lock)); - if (value > sp->bestValue && !thread_should_stop(threadID)) + if (value > sp->bestValue) // Less then 2% of cases { - sp->bestValue = value; - if (sp->bestValue >= sp->beta) + lock_grab(&(sp->lock)); + if (value > sp->bestValue && !thread_should_stop(threadID)) { - sp_update_pv(sp->parentSstack, ss, sp->ply); - for (int i = 0; i < ActiveThreads; i++) - if (i != threadID && (i == sp->master || sp->slaves[i])) - Threads[i].stop = true; + sp->bestValue = value; + if (sp->bestValue >= sp->beta) + { + sp_update_pv(sp->parentSstack, ss, sp->ply); + for (int i = 0; i < ActiveThreads; i++) + if (i != threadID && (i == sp->master || sp->slaves[i])) + Threads[i].stop = true; - sp->finished = true; - } + sp->finished = true; + } + } + lock_release(&(sp->lock)); } - lock_release(&(sp->lock)); } lock_grab(&(sp->lock)); // If this is the master thread and we have been asked to stop because of - // a beta cutoff higher up in the tree, stop all slave threads: + // a beta cutoff higher up in the tree, stop all slave threads. if (sp->master == threadID && thread_should_stop(threadID)) for (int i = 0; i < ActiveThreads; i++) if (sp->slaves[i]) @@ -1754,16 +1835,16 @@ namespace { // the normal search_pv() function, but simpler. Because we have already // probed the hash table and searched the first move before splitting, we // don't have to repeat all this work in sp_search_pv(). We also don't - // need to store anything to the hash table here: This is taken care of + // need to store anything to the hash table here: This is taken care of // after we return from the split point. - void sp_search_pv(SplitPoint *sp, int threadID) { + void sp_search_pv(SplitPoint* sp, int threadID) { assert(threadID >= 0 && threadID < ActiveThreads); assert(ActiveThreads > 1); Position pos = Position(sp->pos); - SearchStack *ss = sp->sstack[threadID]; + SearchStack* ss = sp->sstack[threadID]; Value value; Move move; @@ -1772,7 +1853,7 @@ namespace { && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE) { bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates); - bool moveIsCapture = pos.move_is_capture(move); + bool captureOrPromotion = pos.move_is_capture_or_promotion(move); assert(move_is_ok(move)); @@ -1784,7 +1865,7 @@ namespace { // Decide the new search depth. bool dangerous; - Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, false, false, &dangerous); + Depth ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous); Depth newDepth = sp->depth - OnePly + ext; // Make and search the move. @@ -1795,8 +1876,7 @@ namespace { // if the move fails high will be re-searched at full depth. if ( !dangerous && moveCount >= LMRPVMoves - && !moveIsCapture - && !move_promotion(move) + && !captureOrPromotion && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) { @@ -1815,7 +1895,7 @@ namespace { { // When the search fails high at ply 1 while searching the first // move at the root, set the flag failHighPly1. This is used for - // time managment: We don't want to stop the search early in + // time managment: We don't want to stop the search early in // such cases, because resolving the fail high at ply 1 could // result in a big drop in score at the root. if (sp->ply == 1 && RootMoveNumber == 1) @@ -1844,10 +1924,10 @@ namespace { if (value == value_mate_in(sp->ply + 1)) ss[sp->ply].mateKiller = move; - if(value >= sp->beta) + if (value >= sp->beta) { - for(int i = 0; i < ActiveThreads; i++) - if(i != threadID && (i == sp->master || sp->slaves[i])) + for (int i = 0; i < ActiveThreads; i++) + if (i != threadID && (i == sp->master || sp->slaves[i])) Threads[i].stop = true; sp->finished = true; @@ -1937,15 +2017,15 @@ namespace { bool includeAllMoves = (searchMoves[0] == MOVE_NONE); // Generate all legal moves - int lm_count = generate_legal_moves(pos, mlist); + MoveStack* last = generate_moves(pos, mlist); // Add each move to the moves[] array - for (int i = 0; i < lm_count; i++) + for (MoveStack* cur = mlist; cur != last; cur++) { bool includeMove = includeAllMoves; for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++) - includeMove = (searchMoves[k] == mlist[i].move); + includeMove = (searchMoves[k] == cur->move); if (!includeMove) continue; @@ -1953,8 +2033,9 @@ namespace { // Find a quick score for the move StateInfo st; SearchStack ss[PLY_MAX_PLUS_2]; + init_ss_array(ss); - moves[count].move = mlist[i].move; + moves[count].move = cur->move; pos.do_move(moves[count].move, st); moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0); pos.undo_move(moves[count].move); @@ -2065,24 +2146,26 @@ namespace { // for user input and checks whether it is time to stop the search. void init_node(SearchStack ss[], int ply, int threadID) { + assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); Threads[threadID].nodes++; - if(threadID == 0) { - NodesSincePoll++; - if(NodesSincePoll >= NodesBetweenPolls) { - poll(); - NodesSincePoll = 0; - } + if (threadID == 0) + { + NodesSincePoll++; + if (NodesSincePoll >= NodesBetweenPolls) + { + poll(); + NodesSincePoll = 0; + } } - ss[ply].init(ply); ss[ply+2].initKillers(); - if(Threads[threadID].printCurrentLine) - print_current_line(ss, ply, threadID); + if (Threads[threadID].printCurrentLine) + print_current_line(ss, ply, threadID); } @@ -2105,7 +2188,7 @@ namespace { // difference between the two functions is that sp_update_pv also updates // the PV at the parent node. - void sp_update_pv(SearchStack *pss, SearchStack ss[], int ply) { + void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply) { assert(ply >= 0 && ply < PLY_MAX); ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove; @@ -2122,62 +2205,65 @@ namespace { // assumed to be the move that was made to reach the current position, while // the second move is assumed to be a move from the current position. - bool connected_moves(const Position &pos, Move m1, Move m2) { + bool connected_moves(const Position& pos, Move m1, Move m2) { + Square f1, t1, f2, t2; + Piece p; assert(move_is_ok(m1)); assert(move_is_ok(m2)); - if(m2 == MOVE_NONE) - return false; + if (m2 == MOVE_NONE) + return false; - // Case 1: The moving piece is the same in both moves. + // Case 1: The moving piece is the same in both moves f2 = move_from(m2); t1 = move_to(m1); - if(f2 == t1) - return true; + if (f2 == t1) + return true; - // Case 2: The destination square for m2 was vacated by m1. + // Case 2: The destination square for m2 was vacated by m1 t2 = move_to(m2); f1 = move_from(m1); - if(t2 == f1) - return true; + if (t2 == f1) + return true; - // Case 3: Moving through the vacated square: - if(piece_is_slider(pos.piece_on(f2)) && - bit_is_set(squares_between(f2, t2), f1)) + // Case 3: Moving through the vacated square + if ( piece_is_slider(pos.piece_on(f2)) + && bit_is_set(squares_between(f2, t2), f1)) return true; - // Case 4: The destination square for m2 is attacked by the moving piece - // in m1: - if(pos.piece_attacks_square(pos.piece_on(t1), t1, t2)) - return true; + // Case 4: The destination square for m2 is attacked by the moving piece in m1 + p = pos.piece_on(t1); + if (bit_is_set(pos.attacks_from(p, t1), t2)) + return true; - // Case 5: Discovered check, checking piece is the piece moved in m1: - if(piece_is_slider(pos.piece_on(t1)) && - bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), - f2) && - !bit_is_set(squares_between(t2, pos.king_square(pos.side_to_move())), - t2)) { - Bitboard occ = pos.occupied_squares(); - Color us = pos.side_to_move(); - Square ksq = pos.king_square(us); - clear_bit(&occ, f2); - if(pos.type_of_piece_on(t1) == BISHOP) { - if(bit_is_set(bishop_attacks_bb(ksq, occ), t1)) - return true; - } - else if(pos.type_of_piece_on(t1) == ROOK) { - if(bit_is_set(rook_attacks_bb(ksq, occ), t1)) - return true; - } - else { - assert(pos.type_of_piece_on(t1) == QUEEN); - if(bit_is_set(queen_attacks_bb(ksq, occ), t1)) - return true; - } + // Case 5: Discovered check, checking piece is the piece moved in m1 + if ( piece_is_slider(p) + && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2) + && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2)) + { + Bitboard occ = pos.occupied_squares(); + Color us = pos.side_to_move(); + Square ksq = pos.king_square(us); + clear_bit(&occ, f2); + if (type_of_piece(p) == BISHOP) + { + if (bit_is_set(bishop_attacks_bb(ksq, occ), t1)) + return true; + } + else if (type_of_piece(p) == ROOK) + { + if (bit_is_set(rook_attacks_bb(ksq, occ), t1)) + return true; + } + else + { + assert(type_of_piece(p) == QUEEN); + if (bit_is_set(queen_attacks_bb(ksq, occ), t1)) + return true; + } } - return false; } @@ -2215,42 +2301,46 @@ namespace { // extended, as example because the corresponding UCI option is set to zero, // the move is marked as 'dangerous' so, at least, we avoid to prune it. - Depth extension(const Position& pos, Move m, bool pvNode, bool capture, bool check, - bool singleReply, bool mateThreat, bool* dangerous) { + Depth extension(const Position& pos, Move m, bool pvNode, bool captureOrPromotion, + bool check, bool singleReply, bool mateThreat, bool* dangerous) { assert(m != MOVE_NONE); Depth result = Depth(0); - *dangerous = check || singleReply || mateThreat; + *dangerous = check | singleReply | mateThreat; - if (check) - result += CheckExtension[pvNode]; + if (*dangerous) + { + if (check) + result += CheckExtension[pvNode]; - if (singleReply) - result += SingleReplyExtension[pvNode]; + if (singleReply) + result += SingleReplyExtension[pvNode]; - if (mateThreat) - result += MateThreatExtension[pvNode]; + if (mateThreat) + result += MateThreatExtension[pvNode]; + } if (pos.type_of_piece_on(move_from(m)) == PAWN) { - if (pos.move_is_pawn_push_to_7th(m)) + Color c = pos.side_to_move(); + if (relative_rank(c, move_to(m)) == RANK_7) { result += PawnPushTo7thExtension[pvNode]; *dangerous = true; } - if (pos.move_is_passed_pawn_push(m)) + if (pos.pawn_is_passed(c, move_to(m))) { result += PassedPawnExtension[pvNode]; *dangerous = true; } } - if ( capture + if ( captureOrPromotion && pos.type_of_piece_on(move_to(m)) != PAWN && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) - pos.midgame_value_of_piece_on(move_to(m)) == Value(0)) - && !move_promotion(m) + && !move_is_promotion(m) && !move_is_ep(m)) { result += PawnEndgameExtension[pvNode]; @@ -2258,9 +2348,9 @@ namespace { } if ( pvNode - && capture + && captureOrPromotion && pos.type_of_piece_on(move_to(m)) != PAWN - && pos.see(m) >= 0) + && pos.see_sign(m) >= 0) { result += OnePly/2; *dangerous = true; @@ -2278,10 +2368,9 @@ namespace { // probably a good idea to avoid null moves in at least some more // complicated endgames, e.g. KQ vs KR. FIXME - bool ok_to_do_nullmove(const Position &pos) { - if(pos.non_pawn_material(pos.side_to_move()) == Value(0)) - return false; - return true; + bool ok_to_do_nullmove(const Position& pos) { + + return pos.non_pawn_material(pos.side_to_move()) != Value(0); } @@ -2289,23 +2378,23 @@ namespace { // non-tactical moves late in the move list close to the leaves are // candidates for pruning. - bool ok_to_prune(const Position &pos, Move m, Move threat, Depth d, const History& H) { - Square mfrom, mto, tfrom, tto; + bool ok_to_prune(const Position& pos, Move m, Move threat, Depth d) { assert(move_is_ok(m)); assert(threat == MOVE_NONE || move_is_ok(threat)); - assert(!move_promotion(m)); assert(!pos.move_is_check(m)); - assert(!pos.move_is_capture(m)); + assert(!pos.move_is_capture_or_promotion(m)); assert(!pos.move_is_passed_pawn_push(m)); assert(d >= OnePly); + Square mfrom, mto, tfrom, tto; + mfrom = move_from(m); mto = move_to(m); tfrom = move_from(threat); tto = move_to(threat); - // Case 1: Castling moves are never pruned. + // Case 1: Castling moves are never pruned if (move_is_castle(m)) return false; @@ -2321,9 +2410,9 @@ namespace { && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto) || pos.type_of_piece_on(tfrom) == KING) && pos.move_attacks_square(m, tto)) - return false; + return false; - // Case 4: Don't prune moves with good history. + // Case 4: Don't prune moves with good history if (!H.ok_to_prune(pos.piece_on(mfrom), mto, d)) return false; @@ -2333,8 +2422,8 @@ namespace { && threat != MOVE_NONE && piece_is_slider(pos.piece_on(tfrom)) && bit_is_set(squares_between(tfrom, tto), mto) - && pos.see(m) >= 0) - return false; + && pos.see_sign(m) >= 0) + return false; return true; } @@ -2356,19 +2445,10 @@ namespace { } - // ok_to_history() returns true if a move m can be stored - // in history. Should be a non capturing move nor a promotion. - - bool ok_to_history(const Position& pos, Move m) { - - return !pos.move_is_capture(m) && !move_promotion(m); - } - - // update_history() registers a good move that produced a beta-cutoff // in history and marks as failures all the other moves of that ply. - void update_history(const Position& pos, Move m, Depth depth, History& H, + void update_history(const Position& pos, Move m, Depth depth, Move movesSearched[], int moveCount) { H.success(pos.piece_on(move_from(m)), move_to(m), depth); @@ -2376,7 +2456,7 @@ namespace { for (int i = 0; i < moveCount - 1; i++) { assert(m != movesSearched[i]); - if (ok_to_history(pos, movesSearched[i])) + if (!pos.move_is_capture_or_promotion(movesSearched[i])) H.failure(pos.piece_on(move_from(movesSearched[i])), move_to(movesSearched[i])); } } @@ -2396,14 +2476,17 @@ namespace { ss.killers[0] = m; } + // fail_high_ply_1() checks if some thread is currently resolving a fail // high at ply 1 at the node below the first root node. This information // is used for time managment. bool fail_high_ply_1() { + for(int i = 0; i < ActiveThreads; i++) - if(Threads[i].failHighPly1) - return true; + if (Threads[i].failHighPly1) + return true; + return false; } @@ -2448,12 +2531,12 @@ namespace { Quit = true; return; } - else if(command == "stop") + else if (command == "stop") { AbortSearch = true; PonderSearch = false; } - else if(command == "ponderhit") + else if (command == "ponderhit") ponderhit(); } // Print search information @@ -2502,9 +2585,10 @@ namespace { // it correctly predicted the opponent's move. void ponderhit() { + int t = current_search_time(); PonderSearch = false; - if(Iteration >= 3 && + if (Iteration >= 3 && (!InfiniteSearch && (StopOnPonderhit || t > AbsoluteMaxSearchTime || (RootMoveNumber == 1 && @@ -2519,20 +2603,35 @@ namespace { // thread. Called when the UCI option UCI_ShowCurrLine is 'true'. void print_current_line(SearchStack ss[], int ply, int threadID) { + assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); - if(!Threads[threadID].idle) { - lock_grab(&IOLock); - std::cout << "info currline " << (threadID + 1); - for(int p = 0; p < ply; p++) - std::cout << " " << ss[p].currentMove; - std::cout << std::endl; - lock_release(&IOLock); + if (!Threads[threadID].idle) + { + lock_grab(&IOLock); + std::cout << "info currline " << (threadID + 1); + for (int p = 0; p < ply; p++) + std::cout << " " << ss[p].currentMove; + + std::cout << std::endl; + lock_release(&IOLock); } Threads[threadID].printCurrentLine = false; - if(threadID + 1 < ActiveThreads) - Threads[threadID + 1].printCurrentLine = true; + if (threadID + 1 < ActiveThreads) + Threads[threadID + 1].printCurrentLine = true; + } + + + // init_ss_array() does a fast reset of the first entries of a SearchStack array + + void init_ss_array(SearchStack ss[]) { + + for (int i = 0; i < 3; i++) + { + ss[i].init(i); + ss[i].initKillers(); + } } @@ -2557,7 +2656,7 @@ namespace { Quit = true; break; } - else if(command == "ponderhit" || command == "stop") + else if (command == "ponderhit" || command == "stop") break; } } @@ -2567,7 +2666,7 @@ namespace { // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint // object for which the current thread is the master. - void idle_loop(int threadID, SplitPoint *waitSp) { + void idle_loop(int threadID, SplitPoint* waitSp) { assert(threadID >= 0 && threadID < THREAD_MAX); Threads[threadID].running = true; @@ -2589,7 +2688,7 @@ namespace { #endif } - // If this thread has been assigned work, launch a search: + // If this thread has been assigned work, launch a search if(Threads[threadID].workIsWaiting) { Threads[threadID].workIsWaiting = false; if(Threads[threadID].splitPoint->pvNode) @@ -2600,7 +2699,7 @@ namespace { } // If this thread is the master of a split point and all threads have - // finished their work at this split point, return from the idle loop: + // finished their work at this split point, return from the idle loop. if(waitSp != NULL && waitSp->cpus == 0) return; } @@ -2639,7 +2738,7 @@ namespace { bool thread_should_stop(int threadID) { assert(threadID >= 0 && threadID < ActiveThreads); - SplitPoint *sp; + SplitPoint* sp; if(Threads[threadID].stop) return true; @@ -2712,9 +2811,10 @@ namespace { // threads have returned from sp_search_pv (or, equivalently, when // splitPoint->cpus becomes 0), split() returns true. - bool split(const Position &p, SearchStack *sstck, int ply, - Value *alpha, Value *beta, Value *bestValue, Depth depth, int *moves, - MovePicker *mp, Bitboard dcCandidates, int master, bool pvNode) { + bool split(const Position& p, SearchStack* sstck, int ply, + Value* alpha, Value* beta, Value* bestValue, const Value futilityValue, + const Value approximateEval, Depth depth, int* moves, + MovePicker* mp, Bitboard dcCandidates, int master, bool pvNode) { assert(p.is_ok()); assert(sstck != NULL); @@ -2726,24 +2826,24 @@ namespace { assert(master >= 0 && master < ActiveThreads); assert(ActiveThreads > 1); - SplitPoint *splitPoint; + SplitPoint* splitPoint; int i; lock_grab(&MPLock); // If no other thread is available to help us, or if we have too many - // active split points, don't split: + // active split points, don't split. if(!idle_thread_exists(master) || Threads[master].activeSplitPoints >= MaxActiveSplitPoints) { lock_release(&MPLock); return false; } - // Pick the next available split point object from the split point stack: + // Pick the next available split point object from the split point stack splitPoint = SplitPointStack[master] + Threads[master].activeSplitPoints; Threads[master].activeSplitPoints++; - // Initialize the split point object: + // Initialize the split point object splitPoint->parent = Threads[master].splitPoint; splitPoint->finished = false; splitPoint->ply = ply; @@ -2753,6 +2853,8 @@ namespace { splitPoint->pvNode = pvNode; splitPoint->dcCandidates = dcCandidates; splitPoint->bestValue = *bestValue; + splitPoint->futilityValue = futilityValue; + splitPoint->approximateEval = approximateEval; splitPoint->master = master; splitPoint->mp = mp; splitPoint->moves = *moves; @@ -2762,11 +2864,11 @@ namespace { for(i = 0; i < ActiveThreads; i++) splitPoint->slaves[i] = 0; - // Copy the current position and the search stack to the master thread: + // Copy the current position and the search stack to the master thread memcpy(splitPoint->sstack[master], sstck, (ply+1)*sizeof(SearchStack)); Threads[master].splitPoint = splitPoint; - // Make copies of the current position and search stack for each thread: + // Make copies of the current position and search stack for each thread for(i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint; i++) if(thread_is_available(i, master)) { @@ -2796,7 +2898,7 @@ namespace { idle_loop(master, splitPoint); // We have returned from the idle loop, which means that all threads are - // finished. Update alpha, beta and bestvalue, and return: + // finished. Update alpha, beta and bestvalue, and return. lock_grab(&MPLock); if(pvNode) *alpha = splitPoint->alpha; *beta = splitPoint->beta;