X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=98f3e3fdf0ca44553b279ff9e024cd7c7cb746ed;hp=1109bf8e7fced83878af19e696d3205d0e1dbbae;hb=55db87147237e84a4a2341ca10fb56c1ccfac32c;hpb=2a585b63b80f5c3312fd0f6f250ddb337e87481b diff --git a/src/search.cpp b/src/search.cpp index 1109bf8e..98f3e3fd 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -482,7 +482,7 @@ namespace { Key posKey; Move ttMove, move, excludedMove, bestMove, threatMove; Depth ext, newDepth; - Value bestValue, value, ttValue; + Value bestValue, value, ttValue, ttValueUpper; Value eval, nullValue, futilityValue; bool inCheck, givesCheck, pvMove, singularExtensionNode; bool captureOrPromotion, dangerous, doFullDepthSearch; @@ -544,31 +544,43 @@ namespace { tte = TT.probe(posKey); ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE; ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; + ttValueUpper = tte ? value_from_tt(tte->value_upper(), ss->ply) : VALUE_NONE; // At PV nodes we check for exact scores, while at non-PV nodes we check for // a fail high/low. Biggest advantage at probing at PV nodes is to have a // smooth experience in analysis mode. We don't probe at Root nodes otherwise // we should also update RootMoveList to avoid bogus output. - if ( !RootNode - && tte - && tte->depth() >= depth - && ttValue != VALUE_NONE // Only in case of TT access race - && ( PvNode ? tte->type() == BOUND_EXACT - : ttValue >= beta ? (tte->type() & BOUND_LOWER) - : (tte->type() & BOUND_UPPER))) + if (!RootNode && tte) { - TT.refresh(tte); - ss->currentMove = ttMove; // Can be MOVE_NONE + // Fail High + if ( (tte->type() & BOUND_LOWER) + && ttValue >= beta + && tte->depth() >= depth + && ttValue != VALUE_NONE) // Only in case of TT access race + { + // Update killers, we assume ttMove caused a cut-off + if ( ttMove + && !pos.is_capture_or_promotion(ttMove) + && ttMove != ss->killers[0]) + { + ss->killers[1] = ss->killers[0]; + ss->killers[0] = ttMove; + } + TT.refresh(tte); + ss->currentMove = ttMove; // Can be MOVE_NONE + return ttValue; + } - if ( ttValue >= beta - && ttMove - && !pos.is_capture_or_promotion(ttMove) - && ttMove != ss->killers[0]) + // Fail Low + if ( (tte->type() & BOUND_UPPER) + && ttValueUpper <= alpha + && tte->depth_upper() >= depth + && ttValueUpper != VALUE_NONE) // Only in case of TT access race { - ss->killers[1] = ss->killers[0]; - ss->killers[0] = ttMove; + TT.refresh(tte); + ss->currentMove = ttMove; // Can be MOVE_NONE + return ttValueUpper; } - return ttValue; } // Step 5. Evaluate the position statically and update parent's gain statistics @@ -1037,8 +1049,7 @@ split_point_start: // At split points actual search starts from here if (bestValue >= beta) // Failed high { - TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth, - bestMove, ss->staticEval, ss->evalMargin); + TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth, bestMove); if (!pos.is_capture_or_promotion(bestMove) && !inCheck) { @@ -1063,7 +1074,7 @@ 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->staticEval, ss->evalMargin); + depth, bestMove); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1090,8 +1101,8 @@ split_point_start: // At split points actual search starts from here const TTEntry* tte; Key posKey; Move ttMove, move, bestMove; - Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; - bool givesCheck, enoughMaterial, evasionPrunable; + Value bestValue, value, ttValue, ttValueUpper, futilityValue, futilityBase, oldAlpha; + bool givesCheck, enoughMaterial, evasionPrunable, fromNull; Depth ttDepth; // To flag BOUND_EXACT a node with eval above alpha and no available moves @@ -1100,6 +1111,7 @@ split_point_start: // At split points actual search starts from here ss->currentMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; + fromNull = (ss-1)->currentMove == MOVE_NULL; // Check for an instant draw or maximum ply reached if (pos.is_draw() || ss->ply > MAX_PLY) @@ -1111,21 +1123,34 @@ split_point_start: // At split points actual search starts from here tte = TT.probe(posKey); ttMove = tte ? tte->move() : MOVE_NONE; ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE; + ttValueUpper = tte ? value_from_tt(tte->value_upper(),ss->ply) : VALUE_NONE; // Decide whether or not to include checks, this fixes also the type of // TT entry depth that we are going to use. Note that in qsearch we use // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS. ttDepth = InCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS; - if ( tte - && tte->depth() >= ttDepth - && ttValue != VALUE_NONE // Only in case of TT access race - && ( PvNode ? tte->type() == BOUND_EXACT - : ttValue >= beta ? (tte->type() & BOUND_LOWER) - : (tte->type() & BOUND_UPPER))) + if (tte) { - ss->currentMove = ttMove; // Can be MOVE_NONE - return ttValue; + // Fail High + if ( (tte->type() & BOUND_LOWER) + && ttValue >= beta + && tte->depth() >= ttDepth + && ttValue != VALUE_NONE) // Only in case of TT access race + { + ss->currentMove = ttMove; // Can be MOVE_NONE + return ttValue; + } + + // Fail Low + if ( (tte->type() & BOUND_UPPER) + && ttValueUpper <= alpha + && tte->depth_upper() >= ttDepth + && ttValueUpper != VALUE_NONE) // Only in case of TT access race + { + ss->currentMove = ttMove; // Can be MOVE_NONE + return ttValueUpper; + } } // Evaluate the position statically @@ -1137,14 +1162,20 @@ split_point_start: // At split points actual search starts from here } else { - ss->staticEval = bestValue = evaluate(pos, ss->evalMargin); + if (fromNull) + { + // Approximated score. Real one is slightly higher due to tempo + ss->staticEval = bestValue = -(ss-1)->staticEval; + ss->evalMargin = VALUE_ZERO; + } + else + ss->staticEval = bestValue = evaluate(pos, ss->evalMargin); // Stand pat. Return immediately if static value is at least beta if (bestValue >= beta) { if (!tte) - TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, - DEPTH_NONE, MOVE_NONE, ss->staticEval, ss->evalMargin); + TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, DEPTH_NONE, MOVE_NONE); return bestValue; } @@ -1173,6 +1204,7 @@ split_point_start: // At split points actual search starts from here // Futility pruning if ( !PvNode && !InCheck + && !fromNull && !givesCheck && move != ttMove && enoughMaterial @@ -1252,9 +1284,7 @@ split_point_start: // At split points actual search starts from here } else // Fail high { - TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, - ttDepth, move, ss->staticEval, ss->evalMargin); - + TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, ttDepth, move); return value; } } @@ -1268,7 +1298,7 @@ split_point_start: // At split points actual search starts from here TT.store(posKey, value_to_tt(bestValue, ss->ply), PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER, - ttDepth, bestMove, ss->staticEval, ss->evalMargin); + ttDepth, bestMove); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1559,20 +1589,12 @@ void RootMove::insert_pv_in_tt(Position& pos) { StateInfo state[MAX_PLY_PLUS_2], *st = state; TTEntry* tte; int ply = 0; - Value v, m; do { tte = TT.probe(pos.key()); if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries - { - if (pos.in_check()) - v = m = VALUE_NONE; - else - v = evaluate(pos, m); - - TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], v, m); - } + TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply]); assert(pos.move_is_legal(pv[ply])); pos.do_move(pv[ply++], *st++);