X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=17a221110462c6173f4d83602881a7031e9b8ab9;hp=cea95b47de6fa7ca97cee47ee87e76d727168b4a;hb=91b919fd1de3fc36df7bc2769f4d1e6196d7ce51;hpb=013dc43d5d297ee78526f8d03651915673cf2d49 diff --git a/src/search.cpp b/src/search.cpp index cea95b47..17a22111 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; @@ -680,7 +685,7 @@ namespace { Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific bool isPvMove, inCheck, singularExtensionNode, givesCheck, captureOrPromotion, dangerous; int moveCount = 0, playedMoveCount = 0; - int threadID = pos.thread(); + Thread& thread = Threads[pos.thread()]; SplitPoint* sp = NULL; refinedValue = bestValue = value = -VALUE_INFINITE; @@ -689,8 +694,8 @@ namespace { ss->ply = (ss-1)->ply + 1; // Used to send selDepth info to GUI - if (PvNode && Threads[threadID].maxPly < ss->ply) - Threads[threadID].maxPly = ss->ply; + if (PvNode && thread.maxPly < ss->ply) + thread.maxPly = ss->ply; if (SpNode) { @@ -706,9 +711,9 @@ 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) + if (pos.thread() == 0 && ++NodesSincePoll > NodesBetweenPolls) { NodesSincePoll = 0; poll(pos); @@ -716,7 +721,6 @@ namespace { // Step 2. Check for aborted search and immediate draw if (( StopRequest - || Threads[threadID].cutoff_occurred() || pos.is_draw() || ss->ply > PLY_MAX) && !RootNode) return VALUE_DRAW; @@ -739,10 +743,8 @@ namespace { // 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. - if ( !RootNode - && tte - && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT - : ok_to_use_TT(tte, depth, beta, ss->ply))) + if (tte && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT + : ok_to_use_TT(tte, depth, beta, ss->ply))) { TT.refresh(tte); ss->bestMove = ttMove; // Can be MOVE_NONE @@ -858,7 +860,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 +908,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,11 +926,11 @@ 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()) + && !thread.cutoff_occurred()) { assert(move_is_ok(move)); @@ -943,7 +975,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 +1007,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 +1068,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 +1087,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 +1110,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 +1126,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)); @@ -1126,7 +1139,7 @@ split_point_start: // At split points actual search starts from here alpha = sp->alpha; } - if (value > bestValue && !(SpNode && Threads[threadID].cutoff_occurred())) + if (value > bestValue && !(SpNode && thread.cutoff_occurred())) { bestValue = value; @@ -1145,9 +1158,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,29 +1206,29 @@ 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() && bestValue < beta - && Threads.available_slave_exists(threadID) + && Threads.available_slave_exists(pos.thread()) && !StopRequest - && !Threads[threadID].cutoff_occurred()) + && !thread.cutoff_occurred()) Threads.split(pos, ss, &alpha, beta, &bestValue, depth, 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()) + if (!SpNode && !StopRequest && !thread.cutoff_occurred()) { move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove; vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER @@ -1243,7 +1253,7 @@ split_point_start: // At split points actual search starts from here if (SpNode) { // Here we have the lock still grabbed - sp->is_slave[threadID] = false; + sp->is_slave[pos.thread()] = false; sp->nodes += pos.nodes_searched(); lock_release(&(sp->lock)); } @@ -2077,9 +2087,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 +2109,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;