Futility Pruning,
in its pure form implemented at the frontier nodes (depth == 1) with one ply left to the horizon. It discards the moves that have no potential of raising alpha, which in turn requires some estimate of a potential value of a move. This is calculated by adding a futility margin (representing the largest conceivable positional gain) to the evaluation of the current position. If this does not exceed alpha then the futility pruning is triggered to skip this move (which further means setting a flag like f_prune = 1 to indicate not all moves were tried).
Futility pruning is not used when the side to move is in check , or when either alpha or beta are close to the mate value, since it would leave the program blind to certain checkmates. Tord Romstad reported that in his early program Gothmog one more condition was necessary - namely that futility pruning requires checking for the existence of at least one legal move [2][3] to avoid returning erroneous stalemate scores. As replied by Omid David: then simply return alpha (to fail low but hard).
Extended Futility Pruning
Ernst A. Heinz advocated using so-called extended futility pruning[4]. It means employing similar algorithm at pre frontier nodes at depth == 2, only with the greater margin. If at depth 1 the margin does not exceed the value of a minor piece, at depth 2 it should be more like the value of a rook.
in its pure form implemented at the frontier nodes (depth == 1) with one ply left to the horizon. It discards the moves that have no potential of raising alpha, which in turn requires some estimate of a potential value of a move. This is calculated by adding a futility margin (representing the largest conceivable positional gain) to the evaluation of the current position. If this does not exceed alpha then the futility pruning is triggered to skip this move (which further means setting a flag like f_prune = 1 to indicate not all moves were tried).
Table of Contents
Conditions
For tactical stability, even in such a node we ought to search the following moves:Futility pruning is not used when the side to move is in check , or when either alpha or beta are close to the mate value, since it would leave the program blind to certain checkmates. Tord Romstad reported that in his early program Gothmog one more condition was necessary - namely that futility pruning requires checking for the existence of at least one legal move [2] [3] to avoid returning erroneous stalemate scores. As replied by Omid David: then simply return alpha (to fail low but hard).
Extended Futility Pruning
Ernst A. Heinz advocated using so-called extended futility pruning [4]. It means employing similar algorithm at pre frontier nodes at depth == 2, only with the greater margin. If at depth 1 the margin does not exceed the value of a minor piece, at depth 2 it should be more like the value of a rook.Move Count Based Pruning
A further variation of Extended Futility Pruning combining the ideas of Fruit's History Leaf Pruning and Late Move Reductions is called Move Count Based Pruning or Late Move Pruning (LMP) as implemented in Stockfish [5].Deep Futility Pruning
Deep Futility Pruning was proposed by Harm Geert Muller [6]. It is applied at depths of 1<d<=3+R, i.e. with two moves to go:See also
Publications
Forum Posts
1995 ...
2000 ...
2005 ...
2010 ...
2015 ...
- Problem understanding futility pruning by Nicu Ionita, CCC, May 11, 2015
- Razoring vs Futility pruning by Shawn Chidester, CCC, August 16, 2015 » Razoring
2016- futility pruning by Folkert van Heusden, CCC, February 20, 2016
- Futile attempts at futility pruning by Martin Fierz, CCC, March 27, 2016 » Reverse Futility Pruning
- Futility prunning by Daniel Anulliero, CCC, August 11, 2016 » Reverse Futility Pruning
- Futility Pruning by David Cimbalista, CCC, October 11, 2016
2017External Links
Pruning
Misc
futile - Wiktionary
References
What links here?
Up one Level