Browse files

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 <mcostalba@gmail.com>
  • Loading branch information...
1 parent 462a39e commit fca0a2dd881e6bde0a01d3342dd385600e01730b @mcostalba committed May 21, 2011
Showing with 87 additions and 42 deletions.
  1. +36 −8 src/movepick.cpp
  2. +2 −2 src/movepick.h
  3. +5 −0 src/position.h
  4. +44 −32 src/search.cpp
View
44 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,19 +45,18 @@ 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
/// move ordering is at the current node.
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<MV_CAPTURE>(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
View
4 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 @@ class MovePicker {
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];
View
5 src/position.h
@@ -213,6 +213,7 @@ class Position {
// 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;
}
View
76 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<NonPV>(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 @@ namespace {
// Initialize a MovePicker object for the current position
MovePickerExt<NT> 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 @@ namespace {
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 @@ namespace {
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<PvNode>(pos, move, captureOrPromotion, givesCheck, &dangerous);
// Singular extension search. If all moves but one fail low on a search of
@@ -979,7 +1010,7 @@ namespace {
// 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 @@ namespace {
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 @@ namespace {
}
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 @@ namespace {
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<NonPV>(pos, ss+1, -(rAlpha+1), -rAlpha, DEPTH_ZERO)
- : - search<NonPV>(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 @@ namespace {
}
}
- // 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 @@ namespace {
} // RootNode
- // Step 18. Check for split
+ // Step 19. Check for split
if ( !RootNode
&& !SpNode
&& depth >= Threads.min_split_depth()
@@ -1209,14 +1221,14 @@ namespace {
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())

0 comments on commit fca0a2d

Please sign in to comment.