// 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<bool SpNode, bool Root> struct MovePickerExt : public MovePicker {
+ template<NodeType> 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) {}
};
// In case of a SpNode we use split point's shared MovePicker object as moves source
- template<> struct MovePickerExt<true, false> : public MovePicker {
+ template<> struct MovePickerExt<SplitPointNonPV> : public MovePickerExt<NonPV> {
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<NonPV>(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<SplitPointPV> : public MovePickerExt<SplitPointNonPV> {
+
+ MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b)
+ : MovePickerExt<SplitPointNonPV>(p, ttm, d, h, ss, b) {}
+ };
+
// In case of a Root node we use RootMoveList as moves source
- template<> struct MovePickerExt<false, true> : public MovePicker {
+ template<> struct MovePickerExt<Root> : public MovePicker {
MovePickerExt(const Position&, Move, Depth, const History&, SearchStack*, Value);
Move get_next_move();
StateInfo st;
const TTEntry *tte;
Key posKey;
+ Bitboard pinned;
Move ttMove, move, excludedMove, threatMove;
Depth ext, newDepth;
ValueType vt;
// 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)
{
}
}
- // 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)))
split_point_start: // At split points actual search starts from here
// Initialize a MovePicker object for the current position
- MovePickerExt<SpNode, RootNode> mp(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
+ 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
- // 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())
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));
else if (SpNode)
sp->is_betaCutoff = true;
- if (value == value_mate_in(ss->ply + 1))
- ss->mateKiller = move;
-
ss->bestMove = move;
if (SpNode)
} // 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())
}
// Specializations for MovePickerExt in case of Root node
- MovePickerExt<false, true>::MovePickerExt(const Position& p, Move ttm, Depth d,
+ MovePickerExt<Root>::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;
rm = Rml.begin();
}
- Move MovePickerExt<false, true>::get_next_move() {
+ Move MovePickerExt<Root>::get_next_move() {
if (!firstCall)
++rm;
projects / stockfish / blobdiff