X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=1dd6940098f58464fc7a2ef786fb8d3d8506c0fa;hp=aa577c79b7c4fdc2eab25bb2663170defb68e91f;hb=c20a41c9cf15a2819a7b482ece15b67e1879ce18;hpb=276513c19f333eebb2405cb4eea0bb6f8cc31a7b diff --git a/src/search.cpp b/src/search.cpp index aa577c79..1dd69400 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -281,10 +281,12 @@ namespace { template Value search(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE); + template + Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID); + template Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous); - 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); @@ -1030,6 +1032,7 @@ namespace { assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); assert(beta > alpha && beta <= VALUE_INFINITE); + assert(PvNode || alpha == beta - 1); assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < TM.active_threads()); @@ -1048,7 +1051,7 @@ namespace { oldAlpha = alpha; if (depth < OnePly) - return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID); + return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID); // Step 1. Initialize node and poll // Polling can abort search. @@ -1118,7 +1121,7 @@ namespace { && !pos.has_pawn_on_7th(pos.side_to_move())) { Value rbeta = beta - razor_margin(depth); - Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID); + Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID); if (v < rbeta) // Logically we should return (v + razor_margin(depth)), but // surprisingly this did slightly weaker in tests. @@ -1247,9 +1250,10 @@ namespace { if (abs(ttValue) < VALUE_KNOWN_WIN) { - Value excValue = search(pos, ss, ttValue - SingularExtensionMargin - 1, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move); + Value b = ttValue - SingularExtensionMargin; + Value v = search(pos, ss, b - 1, b, depth / 2, ply, false, threadID, move); - if (excValue < ttValue - SingularExtensionMargin) + if (v < ttValue - SingularExtensionMargin) ext = OnePly; } } @@ -1274,7 +1278,7 @@ namespace { continue; // Value based pruning - Depth predictedDepth = newDepth - reduction(depth, moveCount); // We illogically ignore reduction condition depth >= 3*OnePly + Depth predictedDepth = newDepth - reduction(depth, moveCount); // FIXME We illogically ignore reduction condition depth >= 3*OnePly futilityValueScaled = ss[ply].eval + futility_margin(predictedDepth, moveCount) + H.gain(pos.piece_on(move_from(move)), move_to(move)); @@ -1295,34 +1299,36 @@ namespace { value = -search(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID); else { - // Step 14. Reduced search - // if the move fails high will be re-searched at full depth. - bool doFullDepthSearch = true; - - if ( depth >= 3 * OnePly - && !dangerous - && !captureOrPromotion - && !move_is_castle(move) - && !move_is_killer(move, ss[ply])) - { - ss[ply].reduction = reduction(depth, moveCount); - if (ss[ply].reduction) - { - value = -search(pos, ss, -(alpha+1), -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID); - doFullDepthSearch = (value > alpha); - } - } - - // Step 15. Full depth search - if (doFullDepthSearch) - { - ss[ply].reduction = Depth(0); - value = -search(pos, ss, -(alpha+1), -alpha, newDepth, ply+1, true, threadID); + // Step 14. Reduced search + // if the move fails high will be re-searched at full depth. + bool doFullDepthSearch = true; + + if ( depth >= 3 * OnePly + && !dangerous + && !captureOrPromotion + && !move_is_castle(move) + && !move_is_killer(move, ss[ply])) + { + ss[ply].reduction = reduction(depth, moveCount); + if (ss[ply].reduction) + { + value = -search(pos, ss, -(alpha+1), -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID); + doFullDepthSearch = (value > alpha); + } + } - // Step extra. pv search (only in PV nodes) - if (PvNode && value > alpha && value < beta) - value = -search(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID); - } + // Step 15. Full depth search + if (doFullDepthSearch) + { + ss[ply].reduction = Depth(0); + value = -search(pos, ss, -(alpha+1), -alpha, newDepth, ply+1, true, threadID); + + // Step extra. pv search (only in PV nodes) + // Search only for possible new PV nodes, if instead value >= beta then + // parent node fails low with value <= alpha and tries another move. + if (PvNode && value > alpha && value < beta) + value = -search(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID); + } } // Step 16. Undo move @@ -1396,11 +1402,13 @@ namespace { // search function when the remaining depth is zero (or, to be more precise, // less than OnePly). + template Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID) { assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE); + assert(PvNode || alpha == beta - 1); assert(depth <= 0); assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < TM.active_threads()); @@ -1412,7 +1420,6 @@ namespace { bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable; const TTEntry* tte = NULL; int moveCount = 0; - bool pvNode = (beta - alpha != 1); Value oldAlpha = alpha; // Initialize, and make an early exit in case of an aborted search, @@ -1431,7 +1438,7 @@ namespace { tte = TT.retrieve(pos.get_key()); ttMove = (tte ? tte->move() : MOVE_NONE); - if (!pvNode && tte && ok_to_use_TT(tte, depth, beta, ply)) + if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply)) { assert(tte->type() != VALUE_TYPE_EVAL); @@ -1496,9 +1503,9 @@ namespace { ss[ply].currentMove = move; // Futility pruning - if ( enoughMaterial + if ( !PvNode + && enoughMaterial && !isCheck - && !pvNode && !moveIsCheck && move != ttMove && !move_is_promotion(move) @@ -1524,8 +1531,8 @@ namespace { && !pos.can_castle(pos.side_to_move()); // Don't search moves with negative SEE values - if ( (!isCheck || evasionPrunable) - && !pvNode + if ( !PvNode + && (!isCheck || evasionPrunable) && move != ttMove && !move_is_promotion(move) && pos.see_sign(move) < 0) @@ -1533,7 +1540,7 @@ namespace { // Make and search the move pos.do_move(move, st, ci, moveIsCheck); - 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); @@ -2864,7 +2871,7 @@ namespace { init_ss_array(ss); pos.do_move(cur->move, st); moves[count].move = cur->move; - moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0); + moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0); moves[count].pv[0] = cur->move; moves[count].pv[1] = MOVE_NONE; pos.undo_move(cur->move);