Chess - Programming - Futility Pruning

At a frontier node (one ply away from quiescence), if the static evaluation plus some margin is less than alpha, proceed straight to quiescence or even return an evaluation immediately.

Works best in combination with lazy evaluation.

Lower margins give a faster - but less accurate - search.

If the margin is larger than the maximum possible score improvement, futility pruning is completely theoretically sound but does not prune anywhere near so many nodes.

The idea of not pruning moves that are likely to change the score is very simple and effective.


What Futility Pruning Options to use

Options include:

The considerations are taken because these moves are likely to change the score more than average (e.g. moving a pawn to 7th rank will always make it a passed pawn, capturing the queen usually alters the king safety quite a bit etc.).

If the move still is getting pruned after these considerations a final check is made to see if the evaluation is above the best evaluation of the node, if it is that evaluation is recorded so the node does not risk exiting without any evaluation.

If one non-capture is futile, so is the rest so basically that check could be done before even generating the non-captures.


It is worth including captures in the futility.

Try not pruning pawns advancing to the seventh rank or similar, since they will most likely increase the score quite a bit.


There is the possibility of all moves in a node fitting the requirements for futility pruning.


Futility Pruning