// 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();
template <NodeType NT>
Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth);
- template <bool PvNode>
- 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);
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 <bool PvNode>
+ 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
StateInfo st;
const TTEntry *tte;
Key posKey;
+ Bitboard pinned;
Move ttMove, move, excludedMove, threatMove;
Depth ext, newDepth;
ValueType vt;
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;
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)
{
// 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);
// Step 2. Check for aborted search and immediate draw
if (( StopRequest
- || Threads[threadID].cutoff_occurred()
- || pos.is_draw()
+ || pos.is_draw<false>()
|| ss->ply > PLY_MAX) && !RootNode)
return VALUE_DRAW;
// 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
}
}
- // 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())
+ && !thread.cutoff_occurred())
{
assert(move_is_ok(move));
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;
- if ( depth >= 3 * ONE_PLY
+ if ( depth > 3 * ONE_PLY
&& !captureOrPromotion
&& !dangerous
&& !move_is_castle(move)
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));
alpha = sp->alpha;
}
- if (value > bestValue && !(SpNode && Threads[threadID].cutoff_occurred()))
+ if (value > bestValue && !(SpNode && thread.cutoff_occurred()))
{
bestValue = value;
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()
&& bestValue < beta
- && Threads.available_slave_exists(threadID)
+ && Threads.available_slave_exists(pos.thread())
&& !StopRequest
- && !Threads[threadID].cutoff_occurred())
+ && !thread.cutoff_occurred())
Threads.split<FakeSplit>(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
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));
}
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<true>() || ss->ply > PLY_MAX)
return VALUE_DRAW;
// Decide whether or not to include checks, this fixes also the type of
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)
{
}
- // 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 <bool PvNode>
- 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.
&& 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<false>() || ply < 2))
{
pv[ply] = tte->move();
pos.do_move(pv[ply++], *st++);
}
// 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;