Home *Search *Selectivity *Pruning * Futility Pruning

M. C. Escher, Relativity, 1953^[1]

Futility Pruning,
discards moves that have no potential of raisingalpha, which in turn requires some estimate of a potential value of a move. This is calculated by adding a safety margin to the evaluation of the current position. If this does not exceed alpha then the futility pruning is triggered to skip this move. Modern engines also perform futility pruning at non-leaf nodes, and scales margin bydepth.

Conditions

Fortactical 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 givecheck

Futility pruning is not used when theside to move is incheck , or when eitheralpha orbeta are close to themate value, since it would leave the program blind to certaincheckmates.Tord Romstad reported that in his early programGothmog 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 byOmid David: then simply return alpha (to faillow buthard).

Move Count Based Pruning

A further variation of Extended Futility Pruning combining the ideas ofFruit'sHistory Leaf Pruning andLate Move Reductions is calledMove Count Based Pruning orLate Move Pruning (LMP) as implemented inStockfish^[4].

Historical Implementations

Historically, futility pruning is implemented at thefrontier nodes (depth == 1) with oneply left to the horizon. The following are past ideas related to futility pruning. These ideas are not used to modern engine development, either because they are superseded or failed under strict testing. The ideas are documented below for historical reasons.

Extended Futility Pruning

Ernst A. Heinz advocated using so-calledextended futility pruning^[5]. It means employing similar algorithm atpre frontier nodes atdepth == 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.

Deep Futility Pruning

Deep Futility Pruning was proposed byHarm Geert Muller^[6]. It is applied at depths of1<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 byAlessandro Damiani,rgcc, November 14, 1997
• Extended Futility Pruning - anyone tried it? byTom King,rgcc, August 16, 1998
• Extensions and Futility Pruning byJames Robertson,CCC, May 04, 1999 »Extensions
• Extended futility pruning and hashtables byGian-Carlo Pascutto,CCC, December 30, 1999 »Transposition Table

2000 ...

• Futility Pruning (I think) Question byBrian Richardson,CCC, April 02, 2000
• Caution K v KBN and lazy eval or futility byBrian Richardson,CCC, May 14, 2000 »KBNK Endgame,Lazy Evaluation
• Something wrong with my futility pruning? bySeveri Salminen,CCC, December 05, 2000
• About history heuristics, killers and my futil. pruning code bySeveri 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? byStuart Cracraft,CCC, August 29, 2001
• Futility + WAC byStefan Knappe,Winboard Forum, November 07, 2001 »Matador,Win at Chess
• Re: Futility Pruning byVincent Diepeveen,CCC, December 20, 2002
• To Stefan Knappe byRahman Paidar,Winboard Forum, June 21, 2003 »Stefan Knappe
• futility pruning? byDaniel Shawul,CCC, November 09, 2003
• Unexpected problem with futility pruning ? by Geoff,CCC, December 29, 2003
• Question for Tom Likens byMatt McKnight,Winboard Forum, February 07, 2004 »Djinn
• Extended futility pruning not working by Cesar Contreras,CCC, August 03, 2004
• Futility byStuart Cracraft,CCC, October 14, 2004
• Futility Prune question byStuart Cracraft,CCC, October 17, 2004
• Futility @ 1/Extended Futility @ 2/Limited Razoring @ 3 = % node reduce? byStuart Cracraft,CCC, October 19, 2004

2005 ...

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

2010 ...

• Futility Idea based on total score byMark Lefler,CCC, February 06, 2010
• Confused by futility pruning byMichel Van den Bergh,CCC, March 03, 2010
• move count based pruning byTom 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 byEngin Üstün,CCC, May 25, 2011 »Stockfish
• Reverse Futility Pruning byMatthew R. Brades,CCC, December 02, 2011 »Reverse Futility Pruning
• How to get futility pruning to work? byRobert Purves,CCC, March 05, 2012
• futility pruning, razoring question byMarco Belli,CCC, April 04, 2012 »Razoring
• A search enhancement? byDaniel Homan,CCC, April 30, 2012 »Move Count Based Pruning
• LMP in PV nodes byPeter Österlund,CCC, December 27, 2014 »PV-Node,Texel

2015 ...

• Problem understanding futility pruning byNicu Ionita,CCC, May 11, 2015
• Razoring vs Futility pruning byShawn Chidester,CCC, August 16, 2015 »Razoring

2016

• futility pruning byFolkert van Heusden,CCC, February 20, 2016
• Futile attempts at futility pruning byMartin Fierz,CCC, March 27, 2016 »Reverse Futility Pruning
• Futility prunning byDaniel Anulliero,CCC, August 11, 2016 »Reverse Futility Pruning
• Futility Pruning byDavid Cimbalista,CCC, October 11, 2016

2017 ...

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

2020 ...

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

External Links

Pruning

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

Misc

• futility - Wiktionary

futile - Wiktionary

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

References

Up one Level

• M. C. Escher
• Porcupine Tree