namespace {
/// Types
-
+ enum NodeType { NonPV, PV };
// ThreadsManager class is used to handle all the threads related stuff in search,
// init, starting, parking and, the most important, launching a slave thread at a
// Step 9. Internal iterative deepening
// Minimum depth for use of internal iterative deepening
- const Depth IIDDepthAtPVNodes = 5 * OnePly;
- const Depth IIDDepthAtNonPVNodes = 8 * OnePly;
+ const Depth IIDDepth[2] = { 8 * OnePly /* non-PV */, 5 * OnePly /* PV */};
// At Non-PV nodes we do an internal iterative deepening search
// when the static evaluation is at most IIDMargin below beta.
// Step 14. Reduced search
// Reduction lookup tables (initialized at startup) and their getter functions
- int8_t PVReductionMatrix[64][64]; // [depth][moveNumber]
- int8_t NonPVReductionMatrix[64][64]; // [depth][moveNumber]
+ int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]
- inline Depth pv_reduction(Depth d, int mn) { return (Depth) PVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; }
- inline Depth nonpv_reduction(Depth d, int mn) { return (Depth) NonPVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; }
+ template <NodeType PV>
+ inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }
// Common adjustments
Value id_loop(const Position& pos, Move searchMoves[]);
Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
- template <bool PvNode>
+ template <NodeType PvNode>
Value search(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE);
+ template <NodeType PvNode>
+ Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
+
Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
void sp_search(SplitPoint* sp, int threadID);
void sp_search_pv(SplitPoint* sp, int threadID);
bool connected_moves(const Position& pos, Move m1, Move m2);
bool value_is_mate(Value value);
bool move_is_killer(Move m, const SearchStack& ss);
- Depth extension(const Position&, Move, bool, bool, bool, bool, bool, bool*);
bool ok_to_do_nullmove(const Position& pos);
bool ok_to_prune(const Position& pos, Move m, Move threat);
bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
{
double pvRed = log(double(i)) * log(double(j)) / 3.0;
double nonPVRed = log(double(i)) * log(double(j)) / 1.5;
- PVReductionMatrix[i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0);
- NonPVReductionMatrix[i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0);
+ ReductionMatrix[PV][i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0);
+ ReductionMatrix[NonPV][i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0);
}
// Init futility margins array
// Step 11. Decide the new search depth
depth = (Iteration - 2) * OnePly + InitialDepth;
- ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
+ ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
newDepth = depth + ext;
// Step 12. Futility pruning (omitted at root)
alpha = -VALUE_INFINITE;
// Full depth PV search, done on first move or after a fail high
- value = -search<true>(pos, ss, -beta, -alpha, newDepth, 1, false, 0);
+ value = -search<PV>(pos, ss, -beta, -alpha, newDepth, 1, false, 0);
}
else
{
&& !captureOrPromotion
&& !move_is_castle(move))
{
- ss[0].reduction = pv_reduction(depth, i - MultiPV + 2);
+ ss[0].reduction = reduction<PV>(depth, i - MultiPV + 2);
if (ss[0].reduction)
{
// Reduced depth non-pv search using alpha as upperbound
- value = -search<false>(pos, ss, -(alpha+1), -alpha, newDepth-ss[0].reduction, 1, true, 0);
+ value = -search<NonPV>(pos, ss, -(alpha+1), -alpha, newDepth-ss[0].reduction, 1, true, 0);
doFullDepthSearch = (value > alpha);
}
}
{
// Full depth non-pv search using alpha as upperbound
ss[0].reduction = Depth(0);
- value = -search<false>(pos, ss, -(alpha+1), -alpha, newDepth, 1, true, 0);
+ value = -search<NonPV>(pos, ss, -(alpha+1), -alpha, newDepth, 1, true, 0);
// If we are above alpha then research at same depth but as PV
// to get a correct score or eventually a fail high above beta.
if (value > alpha)
- value = -search<true>(pos, ss, -beta, -alpha, newDepth, 1, false, 0);
+ value = -search<PV>(pos, ss, -beta, -alpha, newDepth, 1, false, 0);
}
}
}
- // search_pv() is the main search function for PV nodes.
+ // search<>() is the main search function for both PV and non-PV nodes
- template <bool PvNode>
+ template <NodeType PvNode>
Value search(Position& pos, SearchStack ss[], Value alpha, Value beta,
Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove) {
-
assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
assert(beta > alpha && beta <= VALUE_INFINITE);
assert(ply >= 0 && ply < PLY_MAX);
pos.do_null_move(st);
- nullValue = -search<false>(pos, ss, -beta, -alpha, depth-R*OnePly, ply+1, false, threadID);
+ nullValue = -search<NonPV>(pos, ss, -beta, -alpha, depth-R*OnePly, ply+1, false, threadID);
pos.undo_null_move();
return nullValue;
// Do zugzwang verification search
- Value v = search<false>(pos, ss, alpha, beta, depth-5*OnePly, ply, false, threadID);
+ Value v = search<NonPV>(pos, ss, alpha, beta, depth-5*OnePly, ply, false, threadID);
if (v >= beta)
return nullValue;
} else {
}
// Step 9. Internal iterative deepening
- // We have different rules for PV nodes and non-pv nodes
- if ( PvNode
- && depth >= IIDDepthAtPVNodes
- && ttMove == MOVE_NONE)
- {
- search<true>(pos, ss, alpha, beta, depth-2*OnePly, ply, false, threadID);
- ttMove = ss[ply].pv[ply];
- tte = TT.retrieve(posKey);
- }
-
- if ( !PvNode
- && depth >= IIDDepthAtNonPVNodes
+ if ( depth >= IIDDepth[PvNode]
&& ttMove == MOVE_NONE
- && !isCheck
- && ss[ply].eval >= beta - IIDMargin)
+ && (PvNode || (!isCheck && ss[ply].eval >= beta - IIDMargin)))
{
- search<false>(pos, ss, alpha, beta, depth/2, ply, false, threadID);
+ Depth d = (PvNode ? depth - 2 * OnePly : depth / 2);
+ search<PvNode>(pos, ss, alpha, beta, d, ply, false, threadID);
ttMove = ss[ply].pv[ply];
tte = TT.retrieve(posKey);
}
captureOrPromotion = pos.move_is_capture_or_promotion(move);
// Step 11. Decide the new search depth
- ext = extension(pos, move, PvNode, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
+ ext = extension<PvNode>(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
// Singular extension search. We extend the TT move if its value is much better than
// its siblings. To verify this we do a reduced search on all the other moves but the
if (abs(ttValue) < VALUE_KNOWN_WIN)
{
- Value excValue = search<false>(pos, ss, ttValue - SingularExtensionMargin - 1, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move);
+ Value excValue = search<NonPV>(pos, ss, ttValue - SingularExtensionMargin - 1, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move);
if (excValue < ttValue - SingularExtensionMargin)
ext = OnePly;
continue;
// Value based pruning
- Depth predictedDepth = newDepth - nonpv_reduction(depth, moveCount); // We illogically ignore reduction condition depth >= 3*OnePly
+ Depth predictedDepth = newDepth - reduction<NonPV>(depth, moveCount); // We illogically ignore reduction condition depth >= 3*OnePly
futilityValueScaled = ss[ply].eval + futility_margin(predictedDepth, moveCount)
+ H.gain(pos.piece_on(move_from(move)), move_to(move));
// Step extra. pv search (only in PV nodes)
// The first move in list is the expected PV
if (PvNode && moveCount == 1)
- value = -search<true>(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID);
+ value = -search<PV>(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID);
else
{
// Step 14. Reduced search
&& !move_is_castle(move)
&& !move_is_killer(move, ss[ply]))
{
- ss[ply].reduction = (PvNode ? pv_reduction(depth, moveCount) : nonpv_reduction(depth, moveCount));
+ ss[ply].reduction = reduction<PvNode>(depth, moveCount);
if (ss[ply].reduction)
{
- value = -search<false>(pos, ss, -(alpha+1), -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
+ value = -search<NonPV>(pos, ss, -(alpha+1), -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
doFullDepthSearch = (value > alpha);
}
}
if (doFullDepthSearch)
{
ss[ply].reduction = Depth(0);
- value = -search<false>(pos, ss, -(alpha+1), -alpha, newDepth, ply+1, true, threadID);
+ value = -search<NonPV>(pos, ss, -(alpha+1), -alpha, newDepth, ply+1, true, threadID);
// Step extra. pv search (only in PV nodes)
if (PvNode && value > alpha && value < beta)
- value = -search<true>(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID);
+ value = -search<PV>(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID);
}
}
captureOrPromotion = pos.move_is_capture_or_promotion(move);
// Step 11. Decide the new search depth
- ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous);
+ ext = extension<NonPV>(pos, move, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous);
newDepth = sp->depth - OnePly + ext;
// Update current move
}
// Value based pruning
- Depth predictedDepth = newDepth - nonpv_reduction(sp->depth, moveCount);
+ Depth predictedDepth = newDepth - reduction<NonPV>(sp->depth, moveCount);
futilityValueScaled = ss[sp->ply].eval + futility_margin(predictedDepth, moveCount)
+ H.gain(pos.piece_on(move_from(move)), move_to(move));
&& !move_is_castle(move)
&& !move_is_killer(move, ss[sp->ply]))
{
- ss[sp->ply].reduction = nonpv_reduction(sp->depth, moveCount);
+ ss[sp->ply].reduction = reduction<NonPV>(sp->depth, moveCount);
if (ss[sp->ply].reduction)
{
- value = -search<false>(pos, ss, -(sp->alpha+1), -(sp->alpha), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
+ value = -search<NonPV>(pos, ss, -(sp->alpha+1), -(sp->alpha), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
doFullDepthSearch = (value >= sp->beta && !TM.thread_should_stop(threadID));
}
}
if (doFullDepthSearch)
{
ss[sp->ply].reduction = Depth(0);
- value = -search<false>(pos, ss, -(sp->alpha+1), -(sp->alpha), newDepth, sp->ply+1, true, threadID);
+ value = -search<NonPV>(pos, ss, -(sp->alpha+1), -(sp->alpha), newDepth, sp->ply+1, true, threadID);
}
// Step 16. Undo move
captureOrPromotion = pos.move_is_capture_or_promotion(move);
// Step 11. Decide the new search depth
- ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous);
+ ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous);
newDepth = sp->depth - OnePly + ext;
// Update current move
&& !move_is_castle(move)
&& !move_is_killer(move, ss[sp->ply]))
{
- ss[sp->ply].reduction = pv_reduction(sp->depth, moveCount);
+ ss[sp->ply].reduction = reduction<PV>(sp->depth, moveCount);
if (ss[sp->ply].reduction)
{
Value localAlpha = sp->alpha;
- value = -search<false>(pos, ss, -(localAlpha+1), -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
+ value = -search<NonPV>(pos, ss, -(localAlpha+1), -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
doFullDepthSearch = (value > localAlpha && !TM.thread_should_stop(threadID));
}
}
{
Value localAlpha = sp->alpha;
ss[sp->ply].reduction = Depth(0);
- value = -search<false>(pos, ss, -(localAlpha+1), -localAlpha, newDepth, sp->ply+1, true, threadID);
+ value = -search<NonPV>(pos, ss, -(localAlpha+1), -localAlpha, newDepth, sp->ply+1, true, threadID);
if (value > localAlpha && value < sp->beta && !TM.thread_should_stop(threadID))
{
// to be higher or equal then beta, if so, avoid to start a PV search.
localAlpha = sp->alpha;
if (localAlpha < sp->beta)
- value = -search<true>(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, false, threadID);
+ value = -search<PV>(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, false, threadID);
}
}
// 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.
-
- Depth extension(const Position& pos, Move m, bool pvNode, bool captureOrPromotion,
- bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous) {
+ template <NodeType PvNode>
+ Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck,
+ bool singleEvasion, bool mateThreat, bool* dangerous) {
assert(m != MOVE_NONE);
if (*dangerous)
{
if (moveIsCheck)
- result += CheckExtension[pvNode];
+ result += CheckExtension[PvNode];
if (singleEvasion)
- result += SingleEvasionExtension[pvNode];
+ result += SingleEvasionExtension[PvNode];
if (mateThreat)
- result += MateThreatExtension[pvNode];
+ result += MateThreatExtension[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];
+ result += PawnPushTo7thExtension[PvNode];
*dangerous = true;
}
if (pos.pawn_is_passed(c, move_to(m)))
{
- result += PassedPawnExtension[pvNode];
+ result += PassedPawnExtension[PvNode];
*dangerous = true;
}
}
&& !move_is_promotion(m)
&& !move_is_ep(m))
{
- result += PawnEndgameExtension[pvNode];
+ result += PawnEndgameExtension[PvNode];
*dangerous = true;
}
- if ( pvNode
+ if ( PvNode
&& captureOrPromotion
&& pos.type_of_piece_on(move_to(m)) != PAWN
&& pos.see_sign(m) >= 0)
projects / stockfish / blobdiff