search: add futility pruning
Closed this issue · 0 comments
raklaptudirm commented
If we're close to the horizon, and even with a large margin the static evaluation can't be raised above alpha, we're probably in a fail-low node, and many moves can be probably be pruned. So set a flag so we don't waste time searching moves that suck and probably don't even have a chance of raising alpha.
// inside negamax
if depth <= FutilityPruningDepthLimit &&
alpha < Checkmate && beta < Checkmate {
margin := FutilityMargins[depth]
canFutilityPrune = staticScore+margin <= alpha
}
// inside search loop
if canFutilityPrune &&
legalMoves > 1 &&
!search.Pos.InCheck() &&
!move.IsTactical() {
search.Pos.UndoMove(move)
continue
}