Futility Pruning

Home * Search * Selectivity * Pruning * Futility Pruning

M. C. Escher, Relativity, 1953

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). Modern engines also perform futility pruning at non-leaf nodes, and scales margin by depth.

Conditions

For tactical stability, even in such a node we ought to search the following moves:

• captures (either all or less typically only those that are capable of raising the score above alpha + margin)
• moves that give check

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 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 . 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 .

Deep Futility Pruning

Deep Futility Pruning was proposed by Harm Geert Muller . It is applied at depths of 1<d<=3+R, i.e. with two moves to go:

if ( CurEval <= Alpha - PVal[FirstPiece(Opponent)] - PVal[SecondPiece(Opponent)] - 2*PosMargin )
   prune

See also

• AEL-Pruning
• Delta Pruning
• Frontier Node
• History Leaf Pruning
• Late Move Reductions
• Lazy Evaluation
• Ostrich's Gamma-Algorithm
• Pre Frontier Node
• Razoring
• Reverse Futility Pruning
• Sibling Prediction Pruning

Publications

• Jonathan Schaeffer (1986). Experiments in Search and Knowledge. Ph.D. Thesis, University of Waterloo. Reprinted as Technical Report TR 86-12, Department of Computing Science, University of Alberta
• Chun Ye, Tony Marsland (1992). Experiments in Forward Pruning with Limited Extensions. ICCA Journal, Vol. 15, No. 2
• Ernst A. Heinz (1998). Extended Futility Pruning. ICCA Journal, Vol. 21, No. 2
• Jeroen Carolus (2006). Alpha-Beta with Sibling Prediction Pruning in Chess. Masters thesis, pdf
• Kunihito Hoki, Masakazu Muramatsu (2012). Efficiency of three Forward-Pruning Techniques in Shogi: Futility Pruning, Null-move Pruning, and Late Move Reduction (LMR). Entertainment Computing, Vol. 3, No. 3

Forum Posts

1995 ...

• futility cut-offs by Alessandro Damiani, rgcc, November 14, 1997
• Extended Futility Pruning - anyone tried it? by Tom King, rgcc, August 16, 1998
• Extensions and Futility Pruning by James Robertson, CCC, May 04, 1999 » Extensions
• Extended futility pruning and hashtables by Gian-Carlo Pascutto, CCC, December 30, 1999 » Transposition Table

2000 ...

• Futility Pruning (I think) Question by Brian Richardson, CCC, April 02, 2000
• Caution K v KBN and lazy eval or futility by Brian Richardson, CCC, May 14, 2000 » KBNK Endgame, Lazy Evaluation
• Something wrong with my futility pruning? by Severi Salminen, CCC, December 05, 2000
• About history heuristics, killers and my futil. pruning code by Severi Salminen, CCC, December 06, 2000 » History Heuristic, Killer Heuristic
• question about futility pruning and positional evaluation by Bert van den Akker, CCC, December 07, 2000  » Evaluation
• Futility Cutoff futile? by Stuart Cracraft, CCC, August 29, 2001
• Futility + WAC by Stefan Knappe, Winboard Forum, November 07, 2001 » Matador, Win at Chess
• Re: Futility Pruning by Vincent Diepeveen, CCC, December 20, 2002
• To Stefan Knappe by Rahman Paidar, Winboard Forum, June 21, 2003 » Stefan Knappe
• futility pruning? by Daniel Shawul, CCC, November 09, 2003
• Unexpected problem with futility pruning ? by Geoff, CCC, December 29, 2003
• Question for Tom Likens by Matt McKnight, Winboard Forum, February 07, 2004 » Djinn
• Extended futility pruning not working by Cesar Contreras, CCC, August 03, 2004
• Futility by Stuart Cracraft, CCC, October 14, 2004
• Futility Prune question by Stuart Cracraft, CCC, October 17, 2004
• Futility @ 1/Extended Futility @ 2/Limited Razoring @ 3 = % node reduce? by Stuart Cracraft, CCC, October 19, 2004

2005 ...

• Does simple futility prune work by Rasjid Chan, Winboard Forum, March 27, 2005
• Selective Futlity Condition at Quiescence Nodes by Pradu, Winboard Forum, October 26, 2005
• Null move, futility and LMR by Harm Geert Muller, Winboard Forum, September 26, 2006 » Null Move Pruning, LMR
• Hash Table handling with LMR/Futility pruning by Pradu, Winboard Forum, October 21, 2006
• Extended futility reduction by Michael Sherwin, Winboard Forum, November 18, 2006
• How much elo from futility? by Alessandro Scotti, CCC, September 05, 2007
• LMR and futility by Pawel Koziol, CCC, October 28, 2007
• Draw recognizers, futility... mess by Pawel Koziol, CCC, October 14, 2008
• futility pruning - razoring by Don Dailey, CCC, September 16, 2009 » Razoring
• Futility pruning, Ext futility pruning and Limited Razoring by Jesper Nielsen, CCC, November 26, 2009

2010 ...

• Futility Idea based on total score by Mark Lefler, CCC, February 06, 2010
• Confused by futility pruning by Michel Van den Bergh, CCC, March 03, 2010
• move count based pruning by Tom King, CCC, September 02, 2010
• LMR, Razoring, Futility.... with chess variant with drops? by Justin Madru, CCC, December 30, 2010
• Futility Methods by kenny stanley, CCC, January 21, 2011
• futility pruning in stockfish by Engin Üstün, CCC, May 25, 2011 » Stockfish
• Reverse Futility Pruning by Matthew R. Brades, CCC, December 02, 2011 » Reverse Futility Pruning
• How to get futility pruning to work? by Robert Purves, CCC, March 05, 2012
• futility pruning, razoring question by Marco Belli, CCC, April 04, 2012 » Razoring
• A search enhancement? by Daniel Homan, CCC, April 30, 2012 » Move Count Based Pruning
• LMP in PV nodes by Peter Österlund, CCC, December 27, 2014 » PV-Node, Texel

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

2017 ...

• Futility pruning ? by Mahmoud Uthman, CCC, March 04, 2017 » Reverse Futility Pruning
• futile futility pruning attempt by Folkert van Heusden, CCC, March 07, 2017
• Futility pruning... by thevinenator, OpenChess Forum, April 07, 2017
• increasing futility prunning depth by Alexandru Mosoi, CCC, April 28, 2017
• Tuning Futility Margin by Tamás Kuzmics, CCC, June 19, 2017
• A question about futility prunning by Vivien Clauzon, CCC, July 26, 2018

2020 ...

• Futility Pruning Issues by Cheney, CCC, July 07, 2020
• Futility Pruning and its Relation to Quiescence Search by Jakob Progsch, CCC, June 06, 2021 » Quiescence Search
• Futility reductions by Jost Triller, CCC, July 05, 2021

External Links

Pruning

• MadChess 3.0 Beta 6f3d17a (Late Move Pruning) by Erik Madsen, February 8, 2020 » LMP, MadChess
• Deep Futility Pruning by Harm Geert Muller

Misc

• futility - Wiktionary

futile - Wiktionary

• Futility from Wikipedia
• The Wreck of the Titan: Or, Futility - Wikipedia
• Porcupine Tree - Futile, Zeche Bochum, November 18, 2003, YouTube Video

References

Up one Level