From: Marco Costalba Date: Wed, 3 Oct 2012 12:11:20 +0000 (+0200) Subject: Rewrite search best value update X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=d471c49700fbe828159ba54a97946979f41500ae Rewrite search best value update A simplification and also a small speed-up of about 1% mainly due to reducing calls to thisThread->cutoff_occurred(). Worst case split point recovering time after a cut-off occurred is limited to 3 msec on my slow PC, and usually is below 1 msec, so it seems safe to remove the cutoff_occurred() check. No functional change. --- diff --git a/src/search.cpp b/src/search.cpp index 77300708..95f99d01 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -55,6 +55,9 @@ namespace { // Set to true to force running with one thread. Used for debugging const bool FakeSplit = false; + // This is the minimum interval in msec between two check_time() calls + const int TimerResolution = 5; + // Different node types, used as template parameter enum NodeType { Root, PV, NonPV, SplitPointRoot, SplitPointPV, SplitPointNonPV }; @@ -88,10 +91,6 @@ namespace { return (Depth) Reductions[PvNode][std::min(int(d) / ONE_PLY, 63)][std::min(mn, 63)]; } - // This is the minimum interval in msec between two check_time() calls - const int TimerResolution = 5; - - size_t MultiPV, UCIMultiPV, PVIdx; TimeManager TimeMgr; int BestMoveChanges; @@ -99,7 +98,6 @@ namespace { bool SkillLevelEnabled, Chess960; History H; - template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); @@ -505,7 +503,7 @@ namespace { Key posKey; Move ttMove, move, excludedMove, bestMove, threatMove; Depth ext, newDepth; - Value bestValue, value, oldAlpha, ttValue; + Value bestValue, value, ttValue; Value refinedValue, nullValue, futilityValue; bool pvMove, inCheck, singularExtensionNode, givesCheck; bool captureOrPromotion, dangerous, doFullDepthSearch; @@ -514,7 +512,6 @@ namespace { // Step 1. Initialize node Thread* thisThread = pos.this_thread(); moveCount = playedMoveCount = 0; - oldAlpha = alpha; inCheck = pos.in_check(); if (SpNode) @@ -771,10 +768,7 @@ split_point_start: // At split points actual search starts from here // Step 11. Loop through moves // Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs - while ( bestValue < beta - && (move = mp.next_move()) != MOVE_NONE - && !thisThread->cutoff_occurred() - && !Signals.stop) + while (bestValue < beta && (move = mp.next_move()) != MOVE_NONE) { assert(is_ok(move)); @@ -958,7 +952,10 @@ split_point_start: // At split points actual search starts from here // was aborted because the user interrupted the search or because we // ran out of time. In this case, the return value of the search cannot // be trusted, and we don't update the best move and/or PV. - if (RootNode && !Signals.stop) + if (Signals.stop || thisThread->cutoff_occurred()) + return bestValue; + + if (RootNode) { RootMove& rm = *std::find(RootMoves.begin(), RootMoves.end(), move); @@ -984,16 +981,16 @@ split_point_start: // At split points actual search starts from here if (value > bestValue) { bestValue = value; - bestMove = move; - if ( PvNode - && value > alpha - && value < beta) // We want always alpha < beta + if (value > alpha) { - alpha = bestValue; // Update alpha here! + bestMove = move; + + if (PvNode && value < beta) + alpha = bestValue; // Update alpha here! Always alpha < beta } - if (SpNode && !thisThread->cutoff_occurred()) + if (SpNode) { sp->bestValue = bestValue; sp->bestMove = bestMove; @@ -1004,17 +1001,18 @@ split_point_start: // At split points actual search starts from here } } - // Step 19. Check for split + // Step 19. Check for splitting the search if ( !SpNode && depth >= Threads.min_split_depth() && bestValue < beta - && Threads.available_slave_exists(thisThread) - && !Signals.stop - && !thisThread->cutoff_occurred()) + && Threads.available_slave_exists(thisThread)) bestValue = Threads.split(pos, ss, alpha, beta, bestValue, &bestMove, depth, threatMove, moveCount, mp, NT); } + if (SpNode) + return bestValue; + // Step 20. Check for mate and stalemate // All legal moves have been searched and if there are no legal moves, it // must be mate or stalemate. Note that we can have a false positive in @@ -1022,7 +1020,7 @@ split_point_start: // At split points actual search starts from here // harmless because return value is discarded anyhow in the parent nodes. // If we are in a singular extension search then return a fail low score. // A split node has at least one move, the one tried before to be splitted. - if (!SpNode && !moveCount) + if (!moveCount) return excludedMove ? alpha : inCheck ? mated_in(ss->ply) : VALUE_DRAW; // If we have pruned all the moves without searching return a fail-low score @@ -1033,20 +1031,12 @@ split_point_start: // At split points actual search starts from here bestValue = alpha; } - // Step 21. Update tables - // Update transposition table entry, killers and history - if (!SpNode && !Signals.stop && !thisThread->cutoff_occurred()) + if (bestValue >= beta) // Failed high { - Move ttm = bestValue <= oldAlpha ? MOVE_NONE : bestMove; - Bound bt = bestValue <= oldAlpha ? BOUND_UPPER - : bestValue >= beta ? BOUND_LOWER : BOUND_EXACT; - - TT.store(posKey, value_to_tt(bestValue, ss->ply), bt, depth, ttm, ss->eval, ss->evalMargin); + TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth, + bestMove, ss->eval, ss->evalMargin); - // Update killers and history for non capture cut-off moves - if ( bestValue >= beta - && !pos.is_capture_or_promotion(bestMove) - && !inCheck) + if (!pos.is_capture_or_promotion(bestMove) && !inCheck) { if (bestMove != ss->killers[0]) { @@ -1066,6 +1056,10 @@ split_point_start: // At split points actual search starts from here } } } + else // Failed low or PV search + TT.store(posKey, value_to_tt(bestValue, ss->ply), + PvNode && bestMove != MOVE_NONE ? BOUND_EXACT : BOUND_UPPER, + depth, bestMove, ss->eval, ss->evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);