raklaptudirm/mess

search: add futility pruning

Closed this issue · 0 comments

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
}