X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=58feb77d7038fc49dcb24821dbf9b762fa84925c;hp=4d4653bbc2656201aff6ffca454443538145df71;hb=cbcc581a86417ead9f75ae3a9556f97df63b22bf;hpb=a5c85d3cfcdd4992100fb7c77562778c40ae92b9 diff --git a/src/search.cpp b/src/search.cpp index 4d4653bb..58feb77d 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -38,6 +38,7 @@ #include "lock.h" #include "san.h" #include "search.h" +#include "timeman.h" #include "thread.h" #include "tt.h" #include "ucioption.h" @@ -90,7 +91,7 @@ namespace { template void split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue, - Depth depth, bool mateThreat, int* moveCount, MovePicker* mp, bool pvNode); + Depth depth, Move threatMove, bool mateThreat, int* moveCount, MovePicker* mp, bool pvNode); private: friend void poll(); @@ -98,7 +99,6 @@ namespace { int ActiveThreads; volatile bool AllThreadsShouldExit, AllThreadsShouldSleep; Thread threads[MAX_THREADS]; - SplitPoint SplitPointStack[MAX_THREADS][ACTIVE_SPLIT_POINTS_MAX]; Lock MPLock, WaitLock; @@ -199,7 +199,7 @@ namespace { Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2]; // Minimum depth for use of singular extension - const Depth SingularExtensionDepth[2] = { 8 * OnePly /* non-PV */, 6 * OnePly /* PV */}; + const Depth SingularExtensionDepth[2] = { 7 * OnePly /* non-PV */, 6 * OnePly /* PV */}; // If the TT move is at least SingularExtensionMargin better then the // remaining ones we will extend it. @@ -234,12 +234,6 @@ namespace { // better than the second best move. const Value EasyMoveMargin = Value(0x200); - // Last seconds noise filtering (LSN) - const bool UseLSNFiltering = true; - const int LSNTime = 100; // In milliseconds - const Value LSNValue = value_from_centipawns(200); - bool loseOnTime = false; - /// Global variables @@ -257,8 +251,8 @@ namespace { int MultiPV; // Time managment variables - int SearchStartTime, MaxNodes, MaxDepth, MaxSearchTime; - int AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime; + int SearchStartTime, MaxNodes, MaxDepth, OptimumSearchTime; + int MaximumSearchTime, ExtraSearchTime, ExactMaxTime; bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit; bool FirstRootMove, AbortSearch, Quit, AspirationFailLow; @@ -298,6 +292,8 @@ namespace { bool connected_moves(const Position& pos, Move m1, Move m2); bool value_is_mate(Value value); + Value value_to_tt(Value v, int ply); + Value value_from_tt(Value v, int ply); bool move_is_killer(Move m, SearchStack* ss); bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply); bool connected_threat(const Position& pos, Move m, Move threat); @@ -307,12 +303,15 @@ namespace { void update_gains(const Position& pos, Move move, Value before, Value after); int current_search_time(); + std::string value_to_uci(Value v); int nps(); void poll(); void ponderhit(); void wait_for_stop_or_ponderhit(); void init_ss_array(SearchStack* ss, int size); void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value); + void insert_pv_in_tt(const Position& pos, Move pv[]); + void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]); #if !defined(_MSC_VER) void *init_thread(void *threadID); @@ -346,8 +345,8 @@ void init_search() { // Init reductions array for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++) { - double pvRed = log(double(hd)) * log(double(mc)) / 3.0; - double nonPVRed = log(double(hd)) * log(double(mc)) / 1.5; + double pvRed = 0.33 + log(double(hd)) * log(double(mc)) / 4.5; + double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25; ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0); ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0); } @@ -362,24 +361,6 @@ void init_search() { } -// SearchStack::init() initializes a search stack entry. -// Called at the beginning of search() when starting to examine a new node. -void SearchStack::init() { - - currentMove = threatMove = bestMove = MOVE_NONE; - reduction = Depth(0); - eval = VALUE_NONE; -} - -// SearchStack::initKillers() initializes killers for a search stack entry -void SearchStack::initKillers() { - - mateKiller = MOVE_NONE; - for (int i = 0; i < KILLER_MAX; i++) - killers[i] = MOVE_NONE; -} - - /// 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. @@ -415,13 +396,12 @@ int perft(Position& pos, Depth depth) /// 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, - int time[], int increment[], int movesToGo, int maxDepth, - int maxNodes, int maxTime, Move searchMoves[]) { +bool think(const Position& pos, bool infinite, bool ponder, int time[], int increment[], + int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) { // Initialize global search variables StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false; - MaxSearchTime = AbsoluteMaxSearchTime = ExtraSearchTime = 0; + OptimumSearchTime = MaximumSearchTime = ExtraSearchTime = 0; NodesSincePoll = 0; TM.resetNodeCounters(); SearchStartTime = get_system_time(); @@ -449,10 +429,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, } } - // Reset loseOnTime flag at the beginning of a new game - if (button_was_pressed("New Game")) - loseOnTime = false; - // Read UCI option values TT.set_size(get_option_value_int("Hash")); if (button_was_pressed("Clear Hash")) @@ -494,41 +470,17 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, TM.wake_sleeping_threads(); // Set thinking time - int myTime = time[side_to_move]; - int myIncrement = increment[side_to_move]; + int myTime = time[pos.side_to_move()]; + int myIncrement = increment[pos.side_to_move()]; if (UseTimeManagement) { - if (!movesToGo) // Sudden death time control - { - if (myIncrement) - { - MaxSearchTime = myTime / 30 + myIncrement; - AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100); - } - else // Blitz game without increment - { - MaxSearchTime = myTime / 30; - AbsoluteMaxSearchTime = myTime / 8; - } - } - else // (x moves) / (y minutes) - { - if (movesToGo == 1) - { - MaxSearchTime = myTime / 2; - AbsoluteMaxSearchTime = (myTime > 3000)? (myTime - 500) : ((myTime * 3) / 4); - } - else - { - MaxSearchTime = myTime / Min(movesToGo, 20); - AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3); - } - } + get_search_times(myTime, myIncrement, movesToGo, pos.startpos_ply_counter(), + &OptimumSearchTime, &MaximumSearchTime); if (get_option_value_bool("Ponder")) { - MaxSearchTime += MaxSearchTime / 4; - MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime); + OptimumSearchTime += OptimumSearchTime / 4; + OptimumSearchTime = Min(OptimumSearchTime, MaximumSearchTime); } } @@ -552,36 +504,8 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, << " increment: " << myIncrement << " moves to go: " << movesToGo << endl; - // LSN filtering. Used only for developing purposes, disabled by default - if ( UseLSNFiltering - && loseOnTime) - { - // Step 2. If after last move we decided to lose on time, do it now! - while (SearchStartTime + myTime + 1000 > get_system_time()) - /* wait here */; - } - // We're ready to start thinking. Call the iterative deepening loop function - Value v = id_loop(pos, searchMoves); - - if (UseLSNFiltering) - { - // Step 1. If this is sudden death game and our position is hopeless, - // decide to lose on time. - if ( !loseOnTime // If we already lost on time, go to step 3. - && myTime < LSNTime - && myIncrement == 0 - && movesToGo == 0 - && v < -LSNValue) - { - loseOnTime = true; - } - else if (loseOnTime) - { - // Step 3. Now after stepping over the time limit, reset flag for next match. - loseOnTime = false; - } - } + id_loop(pos, searchMoves); if (UseLogFile) LogFile.close(); @@ -623,7 +547,7 @@ namespace { // so to output information also for iteration 1. cout << "info depth " << 1 << "\ninfo depth " << 1 - << " score " << value_to_string(rml.get_move_score(0)) + << " score " << value_to_uci(rml.get_move_score(0)) << " time " << current_search_time() << " nodes " << TM.nodes_searched() << " nps " << nps() @@ -669,7 +593,7 @@ namespace { // Write PV to transposition table, in case the relevant entries have // been overwritten during the search. - TT.insert_pv(p, pv); + insert_pv_in_tt(p, pv); if (AbortSearch) break; // Value cannot be trusted. Break out immediately! @@ -702,20 +626,20 @@ namespace { if ( Iteration >= 8 && EasyMove == pv[0] && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100 - && current_search_time() > MaxSearchTime / 16) + && current_search_time() > OptimumSearchTime / 16) ||( rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100 - && current_search_time() > MaxSearchTime / 32))) + && current_search_time() > OptimumSearchTime / 32))) stopSearch = true; // Add some extra time if the best move has changed during the last two iterations if (Iteration > 5 && Iteration <= 50) - ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2) - + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3); + ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (OptimumSearchTime / 2) + + BestMoveChangesByIteration[Iteration-1] * (OptimumSearchTime / 3); // Stop search if most of MaxSearchTime is consumed at the end of the // iteration. We probably don't have enough time to search the first // move at the next iteration anyway. - if (current_search_time() > ((MaxSearchTime + ExtraSearchTime) * 80) / 128) + if (current_search_time() > ((OptimumSearchTime + ExtraSearchTime) * 80) / 128) stopSearch = true; if (stopSearch) @@ -739,8 +663,7 @@ namespace { // Print final search statistics cout << "info nodes " << TM.nodes_searched() << " nps " << nps() - << " time " << current_search_time() - << " hashfull " << TT.full() << endl; + << " time " << current_search_time() << endl; // Print the best move and the ponder move to the standard output if (pv[0] == MOVE_NONE) @@ -802,15 +725,16 @@ namespace { beta = *betaPtr; isCheck = pos.is_check(); - // Step 1. Initialize node and poll (omitted at root, init_ss_array() has already initialized root node) + // Step 1. Initialize node (polling is omitted at root) + ss->currentMove = ss->bestMove = MOVE_NONE; + // Step 2. Check for aborted search (omitted at root) // Step 3. Mate distance pruning (omitted at root) // Step 4. Transposition table lookup (omitted at root) // Step 5. Evaluate the position statically // At root we do this only to get reference value for child nodes - if (!isCheck) - ss->eval = evaluate(pos, ei); + ss->eval = isCheck ? VALUE_NONE : evaluate(pos, ei); // Step 6. Razoring (omitted at root) // Step 7. Static null move pruning (omitted at root) @@ -936,7 +860,7 @@ namespace { // the score before research in case we run out of time while researching. rml.set_move_score(i, value); ss->bestMove = move; - TT.extract_pv(pos, move, pv, PLY_MAX); + extract_pv_from_tt(pos, move, pv); rml.set_move_pv(i, pv); // Print information to the standard output @@ -976,7 +900,7 @@ namespace { // Update PV rml.set_move_score(i, value); ss->bestMove = move; - TT.extract_pv(pos, move, pv, PLY_MAX); + extract_pv_from_tt(pos, move, pv); rml.set_move_pv(i, pv); if (MultiPV == 1) @@ -1000,7 +924,7 @@ namespace { for (int j = 0; j < Min(MultiPV, rml.move_count()); j++) { cout << "info multipv " << j + 1 - << " score " << value_to_string(rml.get_move_score(j)) + << " score " << value_to_uci(rml.get_move_score(j)) << " depth " << (j <= i ? Iteration : Iteration - 1) << " time " << current_search_time() << " nodes " << TM.nodes_searched() @@ -1055,9 +979,9 @@ namespace { Move movesSearched[256]; EvalInfo ei; StateInfo st; - const TTEntry* tte; + const TTEntry *tte, *ttx; Key posKey; - Move ttMove, move, excludedMove; + Move ttMove, move, excludedMove, threatMove; Depth ext, newDepth; Value bestValue, value, oldAlpha; Value refinedValue, nullValue, futilityValueScaled; // Non-PV specific @@ -1070,8 +994,8 @@ namespace { // Step 1. Initialize node and poll. Polling can abort search TM.incrementNodeCounter(threadID); - ss->init(); - (ss+2)->initKillers(); + ss->currentMove = ss->bestMove = threatMove = MOVE_NONE; + (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE; if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls) { @@ -1115,7 +1039,7 @@ namespace { // Refresh tte entry to avoid aging TT.store(posKey, tte->value(), tte->type(), tte->depth(), ttMove, tte->static_value(), tte->king_danger()); - ss->currentMove = ttMove; // Can be MOVE_NONE + ss->bestMove = ttMove; // Can be MOVE_NONE return value_from_tt(tte->value(), ply); } @@ -1124,17 +1048,23 @@ namespace { isCheck = pos.is_check(); if (!isCheck) { - if (tte && tte->static_value() != VALUE_NONE) + if (tte) { + assert(tte->static_value() != VALUE_NONE); ss->eval = tte->static_value(); ei.kingDanger[pos.side_to_move()] = tte->king_danger(); } else + { ss->eval = evaluate(pos, ei); + TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]); + } refinedValue = refine_eval(tte, ss->eval, ply); // Enhance accuracy with TT value if possible update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval); } + else + ss->eval = VALUE_NONE; // Step 6. Razoring (is omitted in PV nodes) if ( !PvNode @@ -1146,10 +1076,6 @@ namespace { && !value_is_mate(beta) && !pos.has_pawn_on_7th(pos.side_to_move())) { - // Pass ss->eval to qsearch() and avoid an evaluate call - if (!tte || tte->static_value() == VALUE_NONE) - TT.store(posKey, ss->eval, VALUE_TYPE_EXACT, Depth(-127*OnePly), MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]); - Value rbeta = beta - razor_margin(depth); Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply); if (v < rbeta) @@ -1205,12 +1131,12 @@ namespace { if (nullValue >= value_mate_in(PLY_MAX)) nullValue = beta; - // Do zugzwang verification search at high depths if (depth < 6 * OnePly) return nullValue; + // Do verification search at high depths ss->skipNullMove = true; - Value v = search(pos, ss, alpha, beta, depth-5*OnePly, ply); + Value v = search(pos, ss, alpha, beta, depth-R*OnePly, ply); ss->skipNullMove = false; if (v >= beta) @@ -1227,10 +1153,10 @@ namespace { if (nullValue == value_mated_in(ply + 2)) mateThreat = true; - ss->threatMove = (ss+1)->currentMove; + threatMove = (ss+1)->bestMove; if ( depth < ThreatDepth && (ss-1)->reduction - && connected_moves(pos, (ss-1)->currentMove, ss->threatMove)) + && connected_moves(pos, (ss-1)->currentMove, threatMove)) return beta - 1; } } @@ -1281,16 +1207,30 @@ namespace { // Step 11. Decide the new search depth ext = extension(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous); - // Singular extension search. We extend the TT move if its value is much better than - // its siblings. To verify this we do a reduced search on all the other moves but the - // ttMove, if result is lower then ttValue minus a margin then we extend ttMove. + // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s), + // and just one fails high on (alpha, beta), then that move is singular and should be extended. + // To verify this we do a reduced search on all the other moves but the ttMove, if result is + // lower then ttValue minus a margin then we extend ttMove. if ( singularExtensionNode && move == tte->move() && ext < OnePly) { + // Avoid to do an expensive singular extension search on nodes where + // such search have already been done in the past, so assume the last + // singular extension search result is still valid. + if ( !PvNode + && depth < SingularExtensionDepth[PvNode] + 5 * OnePly + && ((ttx = TT.retrieve(pos.get_exclusion_key())) != NULL)) + { + if (is_upper_bound(ttx->type())) + ext = OnePly; + + singularExtensionNode = false; + } + Value ttValue = value_from_tt(tte->value(), ply); - if (abs(ttValue) < VALUE_KNOWN_WIN) + if (singularExtensionNode && abs(ttValue) < VALUE_KNOWN_WIN) { Value b = ttValue - SingularExtensionMargin; ss->excludedMove = move; @@ -1298,7 +1238,7 @@ namespace { Value v = search(pos, ss, b - 1, b, depth / 2, ply); ss->skipNullMove = false; ss->excludedMove = MOVE_NONE; - if (v < ttValue - SingularExtensionMargin) + if (v < b) ext = OnePly; } } @@ -1318,7 +1258,7 @@ namespace { { // Move count based pruning if ( moveCount >= futility_move_count(depth) - && !(ss->threatMove && connected_threat(pos, move, ss->threatMove)) + && !(threatMove && connected_threat(pos, move, threatMove)) && bestValue > value_mated_in(PLY_MAX)) continue; @@ -1426,7 +1366,7 @@ namespace { && !TM.thread_should_stop(threadID) && Iteration <= 99) TM.split(pos, ss, ply, &alpha, beta, &bestValue, depth, - mateThreat, &moveCount, &mp, PvNode); + threatMove, mateThreat, &moveCount, &mp, PvNode); } // Step 19. Check for mate and stalemate @@ -1487,7 +1427,6 @@ namespace { TM.incrementNodeCounter(pos.thread()); ss->bestMove = ss->currentMove = MOVE_NONE; - ss->eval = VALUE_NONE; // Check for an instant draw or maximum ply reached if (pos.is_draw() || ply >= PLY_MAX - 1) @@ -1500,7 +1439,7 @@ namespace { if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply)) { - ss->currentMove = ttMove; // Can be MOVE_NONE + ss->bestMove = ttMove; // Can be MOVE_NONE return value_from_tt(tte->value(), ply); } @@ -1510,12 +1449,14 @@ namespace { if (isCheck) { bestValue = futilityBase = -VALUE_INFINITE; + ss->eval = VALUE_NONE; deepChecks = enoughMaterial = false; } else { - if (tte && tte->static_value() != VALUE_NONE) + if (tte) { + assert(tte->static_value() != VALUE_NONE); ei.kingDanger[pos.side_to_move()] = tte->king_danger(); bestValue = tte->static_value(); } @@ -1529,7 +1470,7 @@ namespace { if (bestValue >= beta) { if (!tte) - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, Depth(-127*OnePly), MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]); + TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]); return bestValue; } @@ -1699,7 +1640,7 @@ namespace { { // Move count based pruning if ( moveCount >= futility_move_count(sp->depth) - && !(ss->threatMove && connected_threat(pos, move, ss->threatMove)) + && !(sp->threatMove && connected_threat(pos, move, sp->threatMove)) && sp->bestValue > value_mated_in(PLY_MAX)) { lock_grab(&(sp->lock)); @@ -1863,8 +1804,8 @@ namespace { } - // value_is_mate() checks if the given value is a mate one - // eventually compensated for the ply. + // value_is_mate() checks if the given value is a mate one eventually + // compensated for the ply. bool value_is_mate(Value value) { @@ -1875,15 +1816,43 @@ namespace { } - // move_is_killer() checks if the given move is among the - // killer moves of that ply. + // value_to_tt() adjusts a mate score from "plies to mate from the root" to + // "plies to mate from the current ply". Non-mate scores are unchanged. + // The function is called before storing a value to the transposition table. + + Value value_to_tt(Value v, int ply) { + + if (v >= value_mate_in(PLY_MAX)) + return v + ply; + + if (v <= value_mated_in(PLY_MAX)) + return v - ply; + + return v; + } + + + // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from + // the transposition table to a mate score corrected for the current ply. + + Value value_from_tt(Value v, int ply) { + + if (v >= value_mate_in(PLY_MAX)) + return v - ply; + + if (v <= value_mated_in(PLY_MAX)) + return v + ply; + + return v; + } + + + // move_is_killer() checks if the given move is among the killer moves bool move_is_killer(Move m, SearchStack* ss) { - const Move* k = ss->killers; - for (int i = 0; i < KILLER_MAX; i++, k++) - if (*k == m) - return true; + if (ss->killers[0] == m || ss->killers[1] == m) + return true; return false; } @@ -2060,9 +2029,7 @@ namespace { if (m == ss->killers[0]) return; - for (int i = KILLER_MAX - 1; i > 0; i--) - ss->killers[i] = ss->killers[i - 1]; - + ss->killers[1] = ss->killers[0]; ss->killers[0] = m; } @@ -2091,6 +2058,20 @@ namespace { } + // value_to_uci() converts a value to a string suitable for use with the UCI protocol + + std::string value_to_uci(Value v) { + + std::stringstream s; + + if (abs(v) < VALUE_MATE - PLY_MAX * OnePly) + s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100 + else + s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 ); + + return s.str(); + } + // nps() computes the current nodes/second count. int nps() { @@ -2154,7 +2135,7 @@ namespace { dbg_print_hit_rate(); cout << "info nodes " << TM.nodes_searched() << " nps " << nps() - << " time " << t << " hashfull " << TT.full() << endl; + << " time " << t << endl; } // Should we stop the search? @@ -2163,9 +2144,9 @@ namespace { bool stillAtFirstMove = FirstRootMove && !AspirationFailLow - && t > MaxSearchTime + ExtraSearchTime; + && t > OptimumSearchTime + ExtraSearchTime; - bool noMoreTime = t > AbsoluteMaxSearchTime + bool noMoreTime = t > MaximumSearchTime || stillAtFirstMove; if ( (Iteration >= 3 && UseTimeManagement && noMoreTime) @@ -2186,9 +2167,9 @@ namespace { bool stillAtFirstMove = FirstRootMove && !AspirationFailLow - && t > MaxSearchTime + ExtraSearchTime; + && t > OptimumSearchTime + ExtraSearchTime; - bool noMoreTime = t > AbsoluteMaxSearchTime + bool noMoreTime = t > MaximumSearchTime || stillAtFirstMove; if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit)) @@ -2205,12 +2186,10 @@ namespace { { ss->excludedMove = MOVE_NONE; ss->skipNullMove = false; + ss->reduction = Depth(0); if (i < 3) - { - ss->init(); - ss->initKillers(); - } + ss->killers[0] = ss->killers[1] = ss->mateKiller = MOVE_NONE; } } @@ -2248,7 +2227,7 @@ namespace { void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) { cout << "info depth " << Iteration - << " score " << value_to_string(value) + << " score " << value_to_uci(value) << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "") << " time " << current_search_time() << " nodes " << TM.nodes_searched() @@ -2271,6 +2250,61 @@ namespace { } + // insert_pv_in_tt() is called at the end of a search iteration, and inserts + // the PV back into the TT. This makes sure the old PV moves are searched + // first, even if the old TT entries have been overwritten. + + void insert_pv_in_tt(const Position& pos, Move pv[]) { + + StateInfo st; + TTEntry* tte; + Position p(pos, pos.thread()); + EvalInfo ei; + Value v; + + for (int i = 0; pv[i] != MOVE_NONE; i++) + { + tte = TT.retrieve(p.get_key()); + if (!tte || tte->move() != pv[i]) + { + v = (p.is_check() ? VALUE_NONE : evaluate(p, ei)); + TT.store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[i], v, ei.kingDanger[pos.side_to_move()]); + } + p.do_move(pv[i], st); + } + } + + + // extract_pv_from_tt() builds a PV by adding moves from the transposition table. + // We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes. This + // allow to always have a ponder move even when we fail high at root and also a + // long PV to print that is important for position analysis. + + void extract_pv_from_tt(const Position& pos, Move bestMove, Move pv[]) { + + StateInfo st; + TTEntry* tte; + Position p(pos, pos.thread()); + int ply = 0; + + assert(bestMove != MOVE_NONE); + + pv[ply] = bestMove; + p.do_move(pv[ply++], st); + + while ( (tte = TT.retrieve(p.get_key())) != NULL + && tte->move() != MOVE_NONE + && move_is_legal(p, tte->move()) + && ply < PLY_MAX + && (!p.is_draw() || ply < 2)) + { + pv[ply] = tte->move(); + p.do_move(pv[ply++], st); + } + pv[ply] = MOVE_NONE; + } + + // init_thread() is the function which is called when a new thread is // launched. It simply calls the idle_loop() function with the supplied // threadID. There are two versions of this function; one for POSIX @@ -2426,8 +2460,8 @@ namespace { #endif // Initialize global locks - lock_init(&MPLock, NULL); - lock_init(&WaitLock, NULL); + lock_init(&MPLock); + lock_init(&WaitLock); #if !defined(_MSC_VER) pthread_cond_init(&WaitCond, NULL); @@ -2436,10 +2470,10 @@ namespace { SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0); #endif - // Initialize SplitPointStack locks + // Initialize splitPoints[] locks for (i = 0; i < MAX_THREADS; i++) - for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++) - lock_init(&(SplitPointStack[i][j].lock), NULL); + for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++) + lock_init(&(threads[i].splitPoints[j].lock)); // Will be set just before program exits to properly end the threads AllThreadsShouldExit = false; @@ -2493,8 +2527,8 @@ namespace { // Now we can safely destroy the locks for (int i = 0; i < MAX_THREADS; i++) - for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++) - lock_destroy(&(SplitPointStack[i][j].lock)); + for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++) + lock_destroy(&(threads[i].splitPoints[j].lock)); lock_destroy(&WaitLock); lock_destroy(&MPLock); @@ -2547,7 +2581,7 @@ namespace { // Apply the "helpful master" concept if possible. Use localActiveSplitPoints // that is known to be > 0, instead of threads[slave].activeSplitPoints that // could have been set to 0 by another thread leading to an out of bound access. - if (SplitPointStack[slave][localActiveSplitPoints - 1].slaves[master]) + if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master]) return true; return false; @@ -2582,8 +2616,8 @@ namespace { template void ThreadsManager::split(const Position& p, SearchStack* ss, int ply, Value* alpha, - const Value beta, Value* bestValue, Depth depth, bool mateThreat, - int* moveCount, MovePicker* mp, bool pvNode) { + const Value beta, Value* bestValue, Depth depth, Move threatMove, + bool mateThreat, int* moveCount, MovePicker* mp, bool pvNode) { assert(p.is_ok()); assert(ply > 0 && ply < PLY_MAX); assert(*bestValue >= -VALUE_INFINITE); @@ -2594,54 +2628,55 @@ namespace { assert(p.thread() >= 0 && p.thread() < ActiveThreads); assert(ActiveThreads > 1); - int master = p.thread(); + int i, master = p.thread(); + Thread& masterThread = threads[master]; lock_grab(&MPLock); // If no other thread is available to help us, or if we have too many // active split points, don't split. if ( !available_thread_exists(master) - || threads[master].activeSplitPoints >= ACTIVE_SPLIT_POINTS_MAX) + || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS) { lock_release(&MPLock); return; } // Pick the next available split point object from the split point stack - SplitPoint* splitPoint = &SplitPointStack[master][threads[master].activeSplitPoints]; + SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++]; // Initialize the split point object - splitPoint->parent = threads[master].splitPoint; - splitPoint->stopRequest = false; - splitPoint->ply = ply; - splitPoint->depth = depth; - splitPoint->mateThreat = mateThreat; - splitPoint->alpha = *alpha; - splitPoint->beta = beta; - splitPoint->pvNode = pvNode; - splitPoint->bestValue = *bestValue; - splitPoint->mp = mp; - splitPoint->moveCount = *moveCount; - splitPoint->pos = &p; - splitPoint->parentSstack = ss; - for (int i = 0; i < ActiveThreads; i++) - splitPoint->slaves[i] = 0; - - threads[master].splitPoint = splitPoint; - threads[master].activeSplitPoints++; + splitPoint.parent = masterThread.splitPoint; + splitPoint.stopRequest = false; + splitPoint.ply = ply; + splitPoint.depth = depth; + splitPoint.threatMove = threatMove; + splitPoint.mateThreat = mateThreat; + splitPoint.alpha = *alpha; + splitPoint.beta = beta; + splitPoint.pvNode = pvNode; + splitPoint.bestValue = *bestValue; + splitPoint.mp = mp; + splitPoint.moveCount = *moveCount; + splitPoint.pos = &p; + splitPoint.parentSstack = ss; + for (i = 0; i < ActiveThreads; i++) + splitPoint.slaves[i] = 0; + + masterThread.splitPoint = &splitPoint; // If we are here it means we are not available - assert(threads[master].state != THREAD_AVAILABLE); + assert(masterThread.state != THREAD_AVAILABLE); int workersCnt = 1; // At least the master is included // Allocate available threads setting state to THREAD_BOOKED - for (int i = 0; !Fake && i < ActiveThreads && workersCnt < MaxThreadsPerSplitPoint; i++) + for (i = 0; !Fake && i < ActiveThreads && workersCnt < MaxThreadsPerSplitPoint; i++) if (thread_is_available(i, master)) { threads[i].state = THREAD_BOOKED; - threads[i].splitPoint = splitPoint; - splitPoint->slaves[i] = 1; + threads[i].splitPoint = &splitPoint; + splitPoint.slaves[i] = 1; workersCnt++; } @@ -2652,10 +2687,10 @@ namespace { // Tell the threads that they have work to do. This will make them leave // their idle loop. But before copy search stack tail for each thread. - for (int i = 0; i < ActiveThreads; i++) - if (i == master || splitPoint->slaves[i]) + for (i = 0; i < ActiveThreads; i++) + if (i == master || splitPoint.slaves[i]) { - memcpy(splitPoint->sstack[i], ss - 1, 4 * sizeof(SearchStack)); + memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack)); assert(i == master || threads[i].state == THREAD_BOOKED); @@ -2667,16 +2702,16 @@ namespace { // THREAD_WORKISWAITING. We send the split point as a second parameter to the // idle loop, which means that the main thread will return from the idle // loop when all threads have finished their work at this split point. - idle_loop(master, splitPoint); + idle_loop(master, &splitPoint); // We have returned from the idle loop, which means that all threads are // finished. Update alpha and bestValue, and return. lock_grab(&MPLock); - *alpha = splitPoint->alpha; - *bestValue = splitPoint->bestValue; - threads[master].activeSplitPoints--; - threads[master].splitPoint = splitPoint->parent; + *alpha = splitPoint.alpha; + *bestValue = splitPoint.bestValue; + masterThread.activeSplitPoints--; + masterThread.splitPoint = splitPoint.parent; lock_release(&MPLock); } @@ -2730,6 +2765,11 @@ namespace { StateInfo st; bool includeAllMoves = (searchMoves[0] == MOVE_NONE); + // Initialize search stack + init_ss_array(ss, PLY_MAX_PLUS_2); + ss[0].currentMove = ss[0].bestMove = MOVE_NONE; + ss[0].eval = VALUE_NONE; + // Generate all legal moves MoveStack* last = generate_moves(pos, mlist); @@ -2745,8 +2785,8 @@ namespace { continue; // Find a quick score for the move - init_ss_array(ss, PLY_MAX_PLUS_2); pos.do_move(cur->move, st); + ss[0].currentMove = cur->move; moves[count].move = cur->move; moves[count].score = -qsearch(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1); moves[count].pv[0] = cur->move;