Reverse Futility Pruning

Home * Search * Selectivity * Pruning * Reverse Futility Pruning

Reverse Futility Pruning, (RFP, Static Null Move Pruning)
postpones a extended futility pruning (EFP) condition applied at [pre]... pre frontier nodes to skip moves inside its move loop if material balance plus gain of the move and safety margin does not improve alpha, with the "reversed" or negamaxed fail-high condition of a more reliable score minus safety margin greater or equal than beta - after making the move, and calling the child and its static evaluation. Thus, Reverse Futility Pruning relies on the null move observation, and is a generalisation of standing pat at quiescent nodes, or a special case of null move pruning without explicitly making one :

Pseudo Code

int search( int alpha, int beta, ... ) {
  int eval = evaluate(...);
  int margin = ...; // e.g. 150 * depth
  if (... && eval >= beta + margin)
    return eval; // fail soft
  ...
}

Tweaks

Conditions

It is common to skip RFP when one of the following conditions are met:

• Position is in check
• Node type is a PV node.
• Position is or has been a PV node.
• TT move does not exist or is capture.

Margin Adjustments

The base RFP margin is usually a constant multiple of depth. The following additional tweaks to the RFP margin are also common in top engines.

• Reduce RFP margin when position is improving
• Tweak RFP margin by the aggregate history score of previous move, divided by some factor.

Return Value

Adjusting the return value of RFP is also found to gain strength in some engines. For example, some engines return (eval + beta) / 2 or beta + (eval - beta) / 3 on successful RFP.

See also

• AEL-Pruning
• Futility Pruning
• Null Move Observation
• Null Move Pruning
• Razoring
• Standing Pat in Quiescence Search

Forum Posts

2008 ...

• Toga/Glaurung/Strelka Prunings/Reductions by Edsel Apostol, CCC, January 31, 2008 » Toga, Glaurung, Strelka, Reductions
• Null move in quiescence search idea from Don Beal, 1986 by Eelco de Groot, CCC, August 17, 2009 » Quiescence Search, Don Beal

2010 ...

• static null move pruning is stockfish by Tom King, CCC, June 13, 2010 » Stockfish
• Reverse Futility Pruning by Matthew R. Brades, CCC, December 02, 2011
• mate distance pruning problems and static null move pruning by Pierre Bokma, CCC, December 04, 2011 » Mate Distance Pruning

2015 ...

• Futile attempts at futility pruning by Martin Fierz, CCC, March 27, 2016
• Futility prunning by Daniel Anulliero, CCC, August 11, 2016 » Futility Pruning
• Static null move pruning by Fernando Tenorio, CCC, December 18, 2016
• Static NULL Move by thevinenator, OpenChess Forum, December 26, 2016 » CPW-Engine_search
• Futility pruning ? by Mahmoud Uthman, CCC, March 04, 2017 » Futility Pruning
• increasing futility prunning depth by Alexandru Mosoi, CCC, April 28, 2017

References

Up one Level