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
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
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);
// 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;
}
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.
return;
case PH_GOOD_CAPTURES:
+ case PH_GOOD_PROBCUT:
lastMove = generate<MV_CAPTURE>(pos, moves);
score_captures();
return;
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
}
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
StateInfo st;
const TTEntry *tte;
Key posKey;
+ Bitboard pinned;
Move ttMove, move, excludedMove, threatMove;
Depth ext, newDepth;
ValueType vt;
}
}
- // 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)))
// 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
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
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
// 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
ss->currentMove = move;
- // Step 13. Make the move
+ // Step 14. Make the move
pos.do_move(move, st, ci, givesCheck);
if (!SpNode && !captureOrPromotion)
}
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;
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;
}
}
- // 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));
} // RootNode
- // Step 18. Check for split
+ // Step 19. Check for split
if ( !RootNode
&& !SpNode
&& depth >= Threads.min_split_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())