X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=c2168bbbddd6171ed6632798d1f779e23dfa3b5c;hp=cea95b47de6fa7ca97cee47ee87e76d727168b4a;hb=fca0a2dd881e6bde0a01d3342dd385600e01730b;hpb=013dc43d5d297ee78526f8d03651915673cf2d49 diff --git a/src/search.cpp b/src/search.cpp index cea95b47..c2168bbb 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -96,7 +96,7 @@ namespace { // MovePickerExt template class extends MovePicker and allows to choose at compile // time the proper moves source according to the type of node. In the default case // we simply create and use a standard MovePicker object. - template struct MovePickerExt : public MovePicker { + template struct MovePickerExt : public MovePicker { MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) : MovePicker(p, ttm, d, h, ss, b) {} @@ -105,19 +105,23 @@ namespace { }; // In case of a SpNode we use split point's shared MovePicker object as moves source - template<> struct MovePickerExt : public MovePicker { + template<> struct MovePickerExt : public MovePickerExt { MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) - : MovePicker(p, ttm, d, h, ss, b), mp(ss->sp->mp) {} + : MovePickerExt(p, ttm, d, h, ss, b), mp(ss->sp->mp) {} Move get_next_move() { return mp->get_next_move(); } - - RootMoveList::iterator rm; // Dummy, needed to compile MovePicker* mp; }; + template<> struct MovePickerExt : public MovePickerExt { + + MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) + : MovePickerExt(p, ttm, d, h, ss, b) {} + }; + // In case of a Root node we use RootMoveList as moves source - template<> struct MovePickerExt : public MovePicker { + template<> struct MovePickerExt : public MovePicker { MovePickerExt(const Position&, Move, Depth, const History&, SearchStack*, Value); Move get_next_move(); @@ -673,6 +677,7 @@ namespace { StateInfo st; const TTEntry *tte; Key posKey; + Bitboard pinned; Move ttMove, move, excludedMove, threatMove; Depth ext, newDepth; ValueType vt; @@ -706,7 +711,7 @@ namespace { // Step 1. Initialize node and poll. Polling can abort search ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE; (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; - (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE; + (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls) { @@ -858,7 +863,37 @@ namespace { } } - // Step 9. Internal iterative deepening + // Step 9. ProbCut (is omitted in PV nodes) + // If we have a very good capture (i.e. SEE > seeValues[captured_piece_type]) + // and a reduced search returns a value much above beta, we can (almost) safely + // prune the previous move. + if ( !PvNode + && depth >= RazorDepth + ONE_PLY + && !inCheck + && !ss->skipNullMove + && excludedMove == MOVE_NONE + && abs(beta) < VALUE_MATE_IN_PLY_MAX) + { + Value rbeta = beta + 200; + Depth rdepth = depth - ONE_PLY - 3 * ONE_PLY; + + assert(rdepth >= ONE_PLY); + + MovePicker mp(pos, ttMove, H, Position::see_value(pos.captured_piece_type())); + pinned = pos.pinned_pieces(pos.side_to_move()); + + while ((move = mp.get_next_move()) != MOVE_NONE) + if (pos.pl_move_is_legal(move, pinned)) + { + pos.do_move(move, st); + value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth); + pos.undo_move(move); + if (value >= rbeta) + return value; + } + } + + // Step 10. Internal iterative deepening if ( depth >= IIDDepth[PvNode] && ttMove == MOVE_NONE && (PvNode || (!inCheck && ss->eval + IIDMargin >= beta))) @@ -876,9 +911,9 @@ namespace { split_point_start: // At split points actual search starts from here // Initialize a MovePicker object for the current position - MovePickerExt mp(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta)); + MovePickerExt mp(pos, ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta); CheckInfo ci(pos); - Bitboard pinned = pos.pinned_pieces(pos.side_to_move()); + pinned = pos.pinned_pieces(pos.side_to_move()); ss->bestMove = MOVE_NONE; futilityBase = ss->eval + ss->evalMargin; singularExtensionNode = !RootNode @@ -894,8 +929,8 @@ split_point_start: // At split points actual search starts from here bestValue = sp->bestValue; } - // Step 10. Loop through moves - // Loop through all legal moves until no moves remain or a beta cutoff occurs + // 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.get_next_move()) != MOVE_NONE && !Threads[threadID].cutoff_occurred()) @@ -943,7 +978,7 @@ split_point_start: // At split points actual search starts from here givesCheck = pos.move_gives_check(move, ci); captureOrPromotion = pos.move_is_capture(move) || move_is_promotion(move); - // Step 11. Decide the new search depth + // Step 12. Decide the new search depth ext = extension(pos, move, captureOrPromotion, givesCheck, &dangerous); // Singular extension search. If all moves but one fail low on a search of @@ -975,7 +1010,7 @@ split_point_start: // At split points actual search starts from here // Update current move (this must be done after singular extension search) newDepth = depth - ONE_PLY + ext; - // Step 12. Futility pruning (is omitted in PV nodes) + // Step 13. Futility pruning (is omitted in PV nodes) if ( !PvNode && !captureOrPromotion && !inCheck @@ -1036,7 +1071,7 @@ split_point_start: // At split points actual search starts from here ss->currentMove = move; - // Step 13. Make the move + // Step 14. Make the move pos.do_move(move, st, ci, givesCheck); if (!SpNode && !captureOrPromotion) @@ -1055,7 +1090,7 @@ split_point_start: // At split points actual search starts from here } else { - // Step 14. Reduced depth search + // Step 15. Reduced depth search // If the move fails high will be re-searched at full depth. bool doFullDepthSearch = true; alpha = SpNode ? sp->alpha : alpha; @@ -1078,26 +1113,7 @@ split_point_start: // At split points actual search starts from here ss->reduction = DEPTH_ZERO; // Restore original reduction } - // Probcut search for bad captures. If a reduced search returns a value - // very below beta then we can (almost) safely prune the bad capture. - if ( depth >= 3 * ONE_PLY - && depth < 8 * ONE_PLY - && mp.isBadCapture() - && move != ttMove - && !dangerous - && !move_is_promotion(move) - && abs(alpha) < VALUE_MATE_IN_PLY_MAX) - { - ss->reduction = 3 * ONE_PLY; - Value rAlpha = alpha - 300; - Depth d = newDepth - ss->reduction; - value = d < ONE_PLY ? -qsearch(pos, ss+1, -(rAlpha+1), -rAlpha, DEPTH_ZERO) - : - search(pos, ss+1, -(rAlpha+1), -rAlpha, d); - doFullDepthSearch = (value > rAlpha); - ss->reduction = DEPTH_ZERO; // Restore original reduction - } - - // Step 15. Full depth search + // Step 16. Full depth search if (doFullDepthSearch) { alpha = SpNode ? sp->alpha : alpha; @@ -1113,12 +1129,12 @@ split_point_start: // At split points actual search starts from here } } - // Step 16. Undo move + // Step 17. Undo move pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // Step 17. Check for new best move + // Step 18. Check for new best move if (SpNode) { lock_grab(&(sp->lock)); @@ -1145,9 +1161,6 @@ split_point_start: // At split points actual search starts from here else if (SpNode) sp->is_betaCutoff = true; - if (value == value_mate_in(ss->ply + 1)) - ss->mateKiller = move; - ss->bestMove = move; if (SpNode) @@ -1196,7 +1209,7 @@ split_point_start: // At split points actual search starts from here } // RootNode - // Step 18. Check for split + // Step 19. Check for split if ( !RootNode && !SpNode && depth >= Threads.min_split_depth() @@ -1208,14 +1221,14 @@ split_point_start: // At split points actual search starts from here threatMove, moveCount, &mp, PvNode); } - // Step 19. Check for mate and stalemate + // 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. // If one move was excluded return fail low score. if (!SpNode && !moveCount) return excludedMove ? oldAlpha : inCheck ? value_mated_in(ss->ply) : VALUE_DRAW; - // Step 20. Update tables + // Step 21. Update tables // If the search is not aborted, update the transposition table, // history counters, and killer moves. if (!SpNode && !StopRequest && !Threads[threadID].cutoff_occurred()) @@ -2077,9 +2090,9 @@ split_point_start: // At split points actual search starts from here } // Specializations for MovePickerExt in case of Root node - MovePickerExt::MovePickerExt(const Position& p, Move ttm, Depth d, + MovePickerExt::MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) - : MovePicker(p, ttm, d, h, ss, b), firstCall(true) { + : MovePicker(p, ttm, d, h, ss, b), firstCall(true) { Move move; Value score = VALUE_ZERO; @@ -2099,7 +2112,7 @@ split_point_start: // At split points actual search starts from here rm = Rml.begin(); } - Move MovePickerExt::get_next_move() { + Move MovePickerExt::get_next_move() { if (!firstCall) ++rm;