X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=a3d8781889a690e15e0b91c4044c0243245f90d1;hp=c9a8f58204a4dc9ecddce0f4c3013e1f21b64afd;hb=189b6fc270f91f4111c1a8049c97455093f8be97;hpb=1ac417edb8451a7837e989a6621faf20300f0bf0 diff --git a/src/search.cpp b/src/search.cpp index c9a8f582..a3d87818 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -104,36 +104,11 @@ namespace { bool connected_moves(const Position& pos, Move m1, Move m2); Value value_to_tt(Value v, int ply); Value value_from_tt(Value v, int ply); - bool can_return_tt(const TTEntry* tte, Depth depth, Value ttValue, Value beta); bool connected_threat(const Position& pos, Move m, Move threat); Value refine_eval(const TTEntry* tte, Value ttValue, Value defaultEval); Move do_skill_level(); string uci_pv(const Position& pos, int depth, Value alpha, Value beta); - // is_dangerous() checks whether a move belongs to some classes of known - // 'dangerous' moves so that we avoid to prune it. - FORCE_INLINE bool is_dangerous(const Position& pos, Move m, bool captureOrPromotion) { - - // Castle move? - if (type_of(m) == CASTLE) - return true; - - // Passed pawn move? - if ( type_of(pos.piece_moved(m)) == PAWN - && pos.pawn_is_passed(pos.side_to_move(), to_sq(m))) - return true; - - // Entering a pawn endgame? - if ( captureOrPromotion - && type_of(pos.piece_on(to_sq(m))) != PAWN - && type_of(m) == NORMAL - && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) - - PieceValue[Mg][pos.piece_on(to_sq(m))] == VALUE_ZERO)) - return true; - - return false; - } - } // namespace @@ -199,6 +174,9 @@ void Search::think() { Position& pos = RootPosition; Chess960 = pos.is_chess960(); Eval::RootColor = pos.side_to_move(); + int scaledCF = Eval::ContemptFactor * MaterialTable::game_phase(pos) / PHASE_MIDGAME; + Eval::ValueDraw[ Eval::RootColor] = VALUE_DRAW - Value(scaledCF); + Eval::ValueDraw[~Eval::RootColor] = VALUE_DRAW + Value(scaledCF); TimeMgr.init(Limits, pos.startpos_ply_counter(), pos.side_to_move()); TT.new_search(); H.clear(); @@ -500,7 +478,7 @@ namespace { Depth ext, newDepth; Value bestValue, value, ttValue; Value refinedValue, nullValue, futilityValue; - bool pvMove, inCheck, singularExtensionNode, givesCheck; + bool inCheck, givesCheck, pvMove, singularExtensionNode; bool captureOrPromotion, dangerous, doFullDepthSearch; int moveCount, playedMoveCount; @@ -538,7 +516,7 @@ namespace { { // Step 2. Check for aborted search and immediate draw if (Signals.stop || pos.is_draw() || ss->ply > MAX_PLY) - return Eval::ValueDrawContempt; + return Eval::ValueDraw[pos.side_to_move()]; // Step 3. Mate distance pruning. Even if we mate at the next move our score // would be at best mate_in(ss->ply+1), but if alpha is already bigger because @@ -565,8 +543,11 @@ namespace { // 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 && (PvNode ? tte->depth() >= depth && tte->type() == BOUND_EXACT - : can_return_tt(tte, depth, ttValue, beta))) + if ( !RootNode + && tte && tte->depth() >= depth + && ( PvNode ? tte->type() == BOUND_EXACT + : ttValue >= beta ? (tte->type() & BOUND_LOWER) + : (tte->type() & BOUND_UPPER))) { TT.refresh(tte); ss->currentMove = ttMove; // Can be MOVE_NONE @@ -798,10 +779,17 @@ split_point_start: // At split points actual search starts from here << " currmovenumber " << moveCount + PVIdx << sync_endl; } + ext = DEPTH_ZERO; captureOrPromotion = pos.is_capture_or_promotion(move); givesCheck = pos.move_gives_check(move, ci); - dangerous = givesCheck || is_dangerous(pos, move, captureOrPromotion); - ext = DEPTH_ZERO; + dangerous = givesCheck + || pos.is_passed_pawn_push(move) + || type_of(move) == CASTLE + || ( captureOrPromotion // Entering a pawn endgame? + && type_of(pos.piece_on(to_sq(move))) != PAWN + && type_of(move) == NORMAL + && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) + - PieceValue[Mg][pos.piece_on(to_sq(move))] == VALUE_ZERO)); // Step 12. Extend checks and, in PV nodes, also dangerous moves if (PvNode && dangerous) @@ -841,7 +829,8 @@ split_point_start: // At split points actual search starts from here && !inCheck && !dangerous && move != ttMove - && (bestValue > VALUE_MATED_IN_MAX_PLY || bestValue == -VALUE_INFINITE)) + && (bestValue > VALUE_MATED_IN_MAX_PLY || ( bestValue == -VALUE_INFINITE + && alpha > VALUE_MATED_IN_MAX_PLY))) { // Move count based pruning if ( depth < 16 * ONE_PLY @@ -987,7 +976,7 @@ split_point_start: // At split points actual search starts from here if (PvNode && value < beta) { alpha = value; // Update alpha here! Always alpha < beta - if (SpNode) sp->alpha = alpha; + if (SpNode) sp->alpha = value; } else // Fail high { @@ -1077,38 +1066,41 @@ split_point_start: // At split points actual search starts from here assert(NT == PV || NT == NonPV); assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE); - assert((alpha == beta - 1) || PvNode); + assert(PvNode || (alpha == beta - 1)); assert(depth <= DEPTH_ZERO); StateInfo st; - Move ttMove, move, bestMove; - Value ttValue, bestValue, value, evalMargin, futilityValue, futilityBase; - bool inCheck, enoughMaterial, givesCheck, evasionPrunable; const TTEntry* tte; + Key posKey; + Move ttMove, move, bestMove; + Value bestValue, value, ttValue, futilityValue, futilityBase; + bool inCheck, givesCheck, enoughMaterial, evasionPrunable; Depth ttDepth; - Bound bt; - Value oldAlpha = alpha; + inCheck = pos.in_check(); ss->currentMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; // Check for an instant draw or maximum ply reached if (pos.is_draw() || ss->ply > MAX_PLY) - return Eval::ValueDrawContempt; + return Eval::ValueDraw[pos.side_to_move()]; + + // Transposition table lookup. At PV nodes, we don't use the TT for + // pruning, but only for move ordering. + posKey = pos.key(); + tte = TT.probe(posKey); + ttMove = tte ? tte->move() : MOVE_NONE; + ttValue = tte ? value_from_tt(tte->value(),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. - inCheck = pos.in_check(); - ttDepth = (inCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS); + ttDepth = inCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS; - // Transposition table lookup. At PV nodes, we don't use the TT for - // pruning, but only for move ordering. - tte = TT.probe(pos.key()); - ttMove = (tte ? tte->move() : MOVE_NONE); - ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_ZERO; - - if (!PvNode && tte && can_return_tt(tte, ttDepth, ttValue, beta)) + if ( tte && tte->depth() >= ttDepth + && ( PvNode ? tte->type() == BOUND_EXACT + : ttValue >= beta ? (tte->type() & BOUND_LOWER) + : (tte->type() & BOUND_UPPER))) { ss->currentMove = ttMove; // Can be MOVE_NONE return ttValue; @@ -1117,8 +1109,8 @@ split_point_start: // At split points actual search starts from here // Evaluate the position statically if (inCheck) { + ss->eval = ss->evalMargin = VALUE_NONE; bestValue = futilityBase = -VALUE_INFINITE; - ss->eval = evalMargin = VALUE_NONE; enoughMaterial = false; } else @@ -1127,17 +1119,17 @@ split_point_start: // At split points actual search starts from here { assert(tte->static_value() != VALUE_NONE); - evalMargin = tte->static_value_margin(); ss->eval = bestValue = tte->static_value(); + ss->evalMargin = tte->static_value_margin(); } else - ss->eval = bestValue = evaluate(pos, evalMargin); + ss->eval = 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->eval, evalMargin); + TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin); return bestValue; } @@ -1145,7 +1137,7 @@ split_point_start: // At split points actual search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = ss->eval + evalMargin + Value(128); + futilityBase = ss->eval + ss->evalMargin + Value(128); enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMg; } @@ -1157,8 +1149,7 @@ split_point_start: // At split points actual search starts from here CheckInfo ci(pos); // Loop through the moves until no moves remain or a beta cutoff occurs - while ( bestValue < beta - && (move = mp.next_move()) != MOVE_NONE) + while ((move = mp.next_move()) != MOVE_NONE) { assert(is_ok(move)); @@ -1225,21 +1216,31 @@ split_point_start: // At split points actual search starts from here // Make and search the move pos.do_move(move, st, ci, givesCheck); - value = -qsearch(pos, ss+1, -beta, -alpha, depth-ONE_PLY); + value = -qsearch(pos, ss+1, -beta, -alpha, depth - ONE_PLY); pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // New best move? + // Check for new best move if (value > bestValue) { bestValue = value; - bestMove = move; - if ( PvNode - && value > alpha - && value < beta) // We want always alpha < beta - alpha = value; + if (value > alpha) + { + if (PvNode && value < beta) // Update alpha here! Always alpha < beta + { + alpha = value; + bestMove = move; + } + else // Fail high + { + TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, + ttDepth, move, ss->eval, ss->evalMargin); + + return value; + } + } } } @@ -1248,12 +1249,9 @@ split_point_start: // At split points actual search starts from here if (inCheck && bestValue == -VALUE_INFINITE) return mated_in(ss->ply); // Plies to mate from the root - // Update transposition table - move = bestValue <= oldAlpha ? MOVE_NONE : bestMove; - bt = bestValue <= oldAlpha ? BOUND_UPPER - : bestValue >= beta ? BOUND_LOWER : BOUND_EXACT; - - TT.store(pos.key(), value_to_tt(bestValue, ss->ply), bt, ttDepth, move, ss->eval, evalMargin); + TT.store(posKey, value_to_tt(bestValue, ss->ply), + PvNode && bestMove != MOVE_NONE ? BOUND_EXACT : BOUND_UPPER, + ttDepth, bestMove, ss->eval, ss->evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1426,20 +1424,6 @@ split_point_start: // At split points actual search starts from here } - // can_return_tt() returns true if a transposition table score can be used to - // cut-off at a given point in search. - - bool can_return_tt(const TTEntry* tte, Depth depth, Value v, Value beta) { - - return ( tte->depth() >= depth - || v >= std::max(VALUE_MATE_IN_MAX_PLY, beta) - || v < std::min(VALUE_MATED_IN_MAX_PLY, beta)) - - && ( ((tte->type() & BOUND_LOWER) && v >= beta) - || ((tte->type() & BOUND_UPPER) && v < beta)); - } - - // refine_eval() returns the transposition table score if possible, otherwise // falls back on static position evaluation.