X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=3862e27b74a1c4d6123441616cbcefa428a0f201;hp=cea95b47de6fa7ca97cee47ee87e76d727168b4a;hb=a24c0a736c6d27335c6c4401a2626f3cf44036cf;hpb=013dc43d5d297ee78526f8d03651915673cf2d49 diff --git a/src/search.cpp b/src/search.cpp index cea95b47..3862e27b 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(); @@ -239,9 +243,6 @@ namespace { template Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth); - template - Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool* dangerous); - bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue); bool connected_moves(const Position& pos, Move m1, Move m2); Value value_to_tt(Value v, int ply); @@ -281,6 +282,51 @@ namespace { return os; } + // extension() decides whether a move should be searched with normal depth, + // or with extended depth. Certain classes of moves (checking moves, in + // particular) are searched with bigger depth than ordinary moves and in + // any case are marked as 'dangerous'. Note that also if a move is not + // extended, as example because the corresponding UCI option is set to zero, + // the move is marked as 'dangerous' so, at least, we avoid to prune it. + template + FORCE_INLINE Depth extension(const Position& pos, Move m, bool captureOrPromotion, + bool moveIsCheck, bool* dangerous) { + assert(m != MOVE_NONE); + + Depth result = DEPTH_ZERO; + *dangerous = moveIsCheck; + + if (moveIsCheck && pos.see_sign(m) >= 0) + result += CheckExtension[PvNode]; + + if (pos.type_of_piece_on(move_from(m)) == PAWN) + { + Color c = pos.side_to_move(); + if (relative_rank(c, move_to(m)) == RANK_7) + { + result += PawnPushTo7thExtension[PvNode]; + *dangerous = true; + } + if (pos.pawn_is_passed(c, move_to(m))) + { + result += PassedPawnExtension[PvNode]; + *dangerous = true; + } + } + + if ( captureOrPromotion + && pos.type_of_piece_on(move_to(m)) != PAWN + && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) + - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO) + && !move_is_special(m)) + { + result += PawnEndgameExtension[PvNode]; + *dangerous = true; + } + + return Min(result, ONE_PLY); + } + } // namespace @@ -673,6 +719,7 @@ namespace { StateInfo st; const TTEntry *tte; Key posKey; + Bitboard pinned; Move ttMove, move, excludedMove, threatMove; Depth ext, newDepth; ValueType vt; @@ -680,7 +727,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 +736,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 +753,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,8 +763,7 @@ namespace { // Step 2. Check for aborted search and immediate draw if (( StopRequest - || Threads[threadID].cutoff_occurred() - || pos.is_draw() + || pos.is_draw() || ss->ply > PLY_MAX) && !RootNode) return VALUE_DRAW; @@ -739,10 +785,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 +902,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 +950,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 +968,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 +1017,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 +1049,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 +1110,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,12 +1129,12 @@ 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; - if ( depth >= 3 * ONE_PLY + if ( depth > 3 * ONE_PLY && !captureOrPromotion && !dangerous && !move_is_castle(move) @@ -1078,26 +1152,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 +1168,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 +1181,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 +1200,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 +1248,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 +1295,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)); } @@ -1281,7 +1333,7 @@ split_point_start: // At split points actual search starts from here ss->ply = (ss-1)->ply + 1; // Check for an instant draw or maximum ply reached - if (ss->ply > PLY_MAX || pos.is_draw()) + if (pos.is_draw() || ss->ply > PLY_MAX) return VALUE_DRAW; // Decide whether or not to include checks, this fixes also the type of @@ -1320,8 +1372,6 @@ split_point_start: // At split points actual search starts from here else ss->eval = bestValue = evaluate(pos, evalMargin); - update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval); - // Stand pat. Return immediately if static value is at least beta if (bestValue >= beta) { @@ -1595,53 +1645,6 @@ split_point_start: // At split points actual search starts from here } - // extension() decides whether a move should be searched with normal depth, - // or with extended depth. Certain classes of moves (checking moves, in - // particular) are searched with bigger depth than ordinary moves and in - // any case are marked as 'dangerous'. Note that also if a move is not - // extended, as example because the corresponding UCI option is set to zero, - // the move is marked as 'dangerous' so, at least, we avoid to prune it. - template - Depth extension(const Position& pos, Move m, bool captureOrPromotion, - bool moveIsCheck, bool* dangerous) { - - assert(m != MOVE_NONE); - - Depth result = DEPTH_ZERO; - *dangerous = moveIsCheck; - - if (moveIsCheck && pos.see_sign(m) >= 0) - result += CheckExtension[PvNode]; - - if (pos.type_of_piece_on(move_from(m)) == PAWN) - { - Color c = pos.side_to_move(); - if (relative_rank(c, move_to(m)) == RANK_7) - { - result += PawnPushTo7thExtension[PvNode]; - *dangerous = true; - } - if (pos.pawn_is_passed(c, move_to(m))) - { - result += PassedPawnExtension[PvNode]; - *dangerous = true; - } - } - - if ( captureOrPromotion - && pos.type_of_piece_on(move_to(m)) != PAWN - && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) - - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO) - && !move_is_special(m)) - { - result += PawnEndgameExtension[PvNode]; - *dangerous = true; - } - - return Min(result, ONE_PLY); - } - - // connected_threat() tests whether it is safe to forward prune a move or if // is somehow connected to the threat move returned by null search. @@ -2014,7 +2017,7 @@ split_point_start: // At split points actual search starts from here && pos.move_is_pl(tte->move()) && pos.pl_move_is_legal(tte->move(), pos.pinned_pieces(pos.side_to_move())) && ply < PLY_MAX - && (!pos.is_draw() || ply < 2)) + && (!pos.is_draw() || ply < 2)) { pv[ply] = tte->move(); pos.do_move(pv[ply++], *st++); @@ -2077,9 +2080,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 +2102,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;