From fca0a2dd881e6bde0a01d3342dd385600e01730b Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sat, 21 May 2011 17:17:11 +0100 Subject: [PATCH 1/1] New extended probcut implementation Here the idea is to test probcut not only after bad captures, but after any bad move, i.e. any move that leaves the opponent with a good capture. Ported by a patch from Onno, the difference from original version is that we have moved probcut after null search. After 7917 games 4 threads 20"+0.1 Mod vs Orig: 1261 - 1095 - 5561 ELO +7 (+- 4.2) LOS 96% Signed-off-by: Marco Costalba --- src/movepick.cpp | 44 +++++++++++++++++++++++----- src/movepick.h | 4 +-- src/position.h | 5 ++++ src/search.cpp | 76 ++++++++++++++++++++++++++++-------------------- 4 files changed, 87 insertions(+), 42 deletions(-) diff --git a/src/movepick.cpp b/src/movepick.cpp index 9b195b1a..b35d1012 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -29,10 +29,11 @@ namespace { enum MovegenPhase { PH_TT_MOVE, // Transposition table move - PH_GOOD_CAPTURES, // Queen promotions and captures with SEE values >= 0 + PH_GOOD_CAPTURES, // Queen promotions and captures with SEE values >= captureThreshold (captureThreshold <= 0) + PH_GOOD_PROBCUT, // Queen promotions and captures with SEE values > captureThreshold (captureThreshold >= 0) PH_KILLERS, // Killer moves from the current ply PH_NONCAPTURES, // Non-captures and underpromotions - PH_BAD_CAPTURES, // Queen promotions and captures with SEE values < 0 + PH_BAD_CAPTURES, // Queen promotions and captures with SEE values < captureThreshold (captureThreshold <= 0) PH_EVASIONS, // Check evasions PH_QCAPTURES, // Captures in quiescence search PH_QCHECKS, // Non-capture checks in quiescence search @@ -44,11 +45,10 @@ namespace { const uint8_t EvasionTable[] = { PH_TT_MOVE, PH_EVASIONS, PH_STOP }; const uint8_t QsearchWithChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_QCHECKS, PH_STOP }; const uint8_t QsearchWithoutChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_STOP }; + const uint8_t ProbCutTable[] = { PH_TT_MOVE, PH_GOOD_PROBCUT, PH_STOP }; } -bool MovePicker::isBadCapture() const { return phase == PH_BAD_CAPTURES; } - -/// Constructor for the MovePicker class. As arguments we pass information +/// Constructors for the MovePicker class. As arguments we pass information /// to help it to return the presumably good moves first, to decide which /// moves to return (in the quiescence search, for instance, we only want to /// search captures, promotions and some checks) and about how important good @@ -56,7 +56,7 @@ bool MovePicker::isBadCapture() const { return phase == PH_BAD_CAPTURES; } MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value beta) : pos(p), H(h) { - badCaptureThreshold = 0; + captureThreshold = 0; badCaptures = moves + MAX_MOVES; assert(d > DEPTH_ZERO); @@ -74,7 +74,7 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h, // Consider sligtly negative captures as good if at low // depth and far from beta. if (ss && ss->eval < beta - PawnValueMidgame && d < 3 * ONE_PLY) - badCaptureThreshold = -PawnValueMidgame; + captureThreshold = -PawnValueMidgame; phasePtr = MainSearchTable; } @@ -109,6 +109,24 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h) go_next_phase(); } +MovePicker::MovePicker(const Position& p, Move ttm, const History& h, int parentCapture) + : pos(p), H(h) { + + assert (!pos.in_check()); + + // In ProbCut we consider only captures better than parent's move + captureThreshold = parentCapture; + phasePtr = ProbCutTable; + + if ( ttm != MOVE_NONE + && (!pos.move_is_capture(ttm) || pos.see(ttm) <= captureThreshold)) + ttm = MOVE_NONE; + + ttMove = (ttm && pos.move_is_pl(ttm) ? ttm : MOVE_NONE); + phasePtr += int(ttMove == MOVE_NONE) - 1; + go_next_phase(); +} + /// MovePicker::go_next_phase() generates, scores and sorts the next bunch /// of moves when there are no more moves to try for the current phase. @@ -124,6 +142,7 @@ void MovePicker::go_next_phase() { return; case PH_GOOD_CAPTURES: + case PH_GOOD_PROBCUT: lastMove = generate(pos, moves); score_captures(); return; @@ -270,9 +289,11 @@ Move MovePicker::get_next_move() { move = pick_best(curMove++, lastMove).move; if (move != ttMove) { + assert(captureThreshold <= 0); // Otherwise we must use see instead of see_sign + // Check for a non negative SEE now int seeValue = pos.see_sign(move); - if (seeValue >= badCaptureThreshold) + if (seeValue >= captureThreshold) return move; // Losing capture, move it to the tail of the array, note @@ -282,6 +303,13 @@ Move MovePicker::get_next_move() { } break; + case PH_GOOD_PROBCUT: + move = pick_best(curMove++, lastMove).move; + if ( move != ttMove + && pos.see(move) > captureThreshold) + return move; + break; + case PH_KILLERS: move = (curMove++)->move; if ( move != MOVE_NONE diff --git a/src/movepick.h b/src/movepick.h index 9bab6547..27c33047 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -42,8 +42,8 @@ class MovePicker { public: MovePicker(const Position&, Move, Depth, const History&, SearchStack*, Value); MovePicker(const Position&, Move, Depth, const History&); + MovePicker(const Position&, Move, const History&, int parentCapture); Move get_next_move(); - bool isBadCapture() const; private: void score_captures(); @@ -55,7 +55,7 @@ private: const History& H; Move ttMove; MoveStack killers[2]; - int badCaptureThreshold, phase; + int captureThreshold, phase; const uint8_t* phasePtr; MoveStack *curMove, *lastMove, *lastGoodNonCapture, *badCaptures; MoveStack moves[MAX_MOVES]; diff --git a/src/position.h b/src/position.h index af1e981c..49f89e6c 100644 --- a/src/position.h +++ b/src/position.h @@ -213,6 +213,7 @@ public: // Static exchange evaluation int see(Move m) const; int see_sign(Move m) const; + static int see_value(PieceType pt); // Accessing hash keys Key get_key() const; @@ -466,6 +467,10 @@ inline bool Position::square_is_weak(Square s, Color c) const { return !(pieces(PAWN, opposite_color(c)) & attack_span_mask(c, s)); } +inline int Position::see_value(PieceType pt) { + return seeValues[pt]; +} + inline Key Position::get_key() const { return st->key; } diff --git a/src/search.cpp b/src/search.cpp index 6ade1b43..c2168bbb 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -677,6 +677,7 @@ namespace { StateInfo st; const TTEntry *tte; Key posKey; + Bitboard pinned; Move ttMove, move, excludedMove, threatMove; Depth ext, newDepth; ValueType vt; @@ -862,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))) @@ -882,7 +913,7 @@ 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); 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 @@ -898,7 +929,7 @@ split_point_start: // At split points actual search starts from here bestValue = sp->bestValue; } - // Step 10. Loop through moves + // 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 @@ -947,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 @@ -979,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 @@ -1040,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) @@ -1059,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; @@ -1082,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; @@ -1117,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)); @@ -1197,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() @@ -1209,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()) -- 2.39.2