25,161
edits
Changes
Created page with "'''Home * Search * Selectivity * Pruning * Reverse Futility Pruning''' '''Reverse Futility Pruning''', (RFP, Static Null Move Pruning)<br/> postpone..."
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Pruning]] * Reverse Futility Pruning'''
'''Reverse Futility Pruning''', (RFP, Static Null Move Pruning)<br/>
postpones a [[Futility Pruning#Extendedfutilitypruning|extended futility pruning]] (EFP) condition applied at [pre]... [[Pre Frontier Node|pre frontier nodes]] to skip moves inside its move loop if [[Material#Balance|material balance]] plus gain of the move and safety margin does not improve [[Alpha|alpha]], with the "reversed" or [[Negamax|negamaxed]] [[Fail-High|fail-high]] condition of a more reliable [[Score|score]] minus safety margin greater or equal than [[Beta|beta]] - after [[Make Move|making the move]], and calling the child and its [[Evaluation|static evaluation]]. Thus, Reverse Futility Pruning relies on the [[Null Move Observation|null move observation]], and is a generalisation of [[Quiescence Search#StandPat|standing pat]] at [[Quiescent Node|quiescent nodes]], or a special case of [[Null Move Pruning|null move pruning]] without explicitly making [[Null Move|one]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=41302&start=1 Re: Reverse Futility Pruning] by [[Don Dailey]], [[CCC]], December 02, 2011</ref>:
=Pseudo Code=
==EFP==
<pre>
int search( int alpha, int beta, ... ) {
bool fprune = ...;
int margin = ...;
for ( all moves ) {
if ( fprune && materialBalance + margin + gain(move) <= alpha ) continue;
make( move );
score = -search(-beta, -alpha, ...);
unmake( move );
...
}
...
}
</pre>
==RFP==
<pre>
int search( int alpha, int beta, ... ) {
int eval = evaluate(...);
int margin = ...;
if (... && eval - margin >= beta) {
return eval - margin; /* fail soft */
...
}
</pre>
=See also=
* [[AEL-Pruning]]
* [[Futility Pruning]]
* [[Null Move Observation]]
* [[Null Move Pruning]]
* [[Razoring]]
* [[Quiescence Search#StandPat|Standing Pat in Quiescence Search]]
=Forum Posts=
==2008 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=19316 Toga/Glaurung/Strelka Prunings/Reductions] by [[Edsel Apostol]], [[CCC]], January 31, 2008 » [[Toga]], [[Glaurung]], [[Strelka]], [[Reductions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=29439 Null move in quiescence search idea from Don Beal, 1986] by [[Eelco de Groot]], [[CCC]], August 17, 2009 » [[Quiescence Search]], [[Don Beal]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=34909 static null move pruning is stockfish] by [[Tom King]], [[CCC]], June 13, 2010 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=41302 Reverse Futility Pruning] by [[Matthew R. Brades]], [[CCC]], December 02, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=41337 mate distance pruning problems and static null move pruning] by Pierre Bokma, [[CCC]], December 04, 2011 » [[Mate Distance Pruning]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=59661 Futile attempts at futility pruning] by [[Martin Fierz]], [[CCC]], March 27, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61093 Futility prunning] by [[Daniel Anulliero]], [[CCC]], August 11, 2016 » [[Futility Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=62522 Static null move pruning] by Fernando Tenorio, [[CCC]], December 18, 2016
* [http://www.open-chess.org/viewtopic.php?f=5&t=3056 Static NULL Move] by thevinenator, [[Computer Chess Forums|OpenChess Forum]], December 26, 2016 » [[CPW-Engine_search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=63344 Futility pruning ?] by [[Mahmoud Uthman]], [[CCC]], March 04, 2017 » [[Futility Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=63852 increasing futility prunning depth] by [[Alexandru Mosoi]], [[CCC]], April 28, 2017
=References=
<references />
'''[[Pruning|Up one Level]]'''
'''Reverse Futility Pruning''', (RFP, Static Null Move Pruning)<br/>
postpones a [[Futility Pruning#Extendedfutilitypruning|extended futility pruning]] (EFP) condition applied at [pre]... [[Pre Frontier Node|pre frontier nodes]] to skip moves inside its move loop if [[Material#Balance|material balance]] plus gain of the move and safety margin does not improve [[Alpha|alpha]], with the "reversed" or [[Negamax|negamaxed]] [[Fail-High|fail-high]] condition of a more reliable [[Score|score]] minus safety margin greater or equal than [[Beta|beta]] - after [[Make Move|making the move]], and calling the child and its [[Evaluation|static evaluation]]. Thus, Reverse Futility Pruning relies on the [[Null Move Observation|null move observation]], and is a generalisation of [[Quiescence Search#StandPat|standing pat]] at [[Quiescent Node|quiescent nodes]], or a special case of [[Null Move Pruning|null move pruning]] without explicitly making [[Null Move|one]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=41302&start=1 Re: Reverse Futility Pruning] by [[Don Dailey]], [[CCC]], December 02, 2011</ref>:
=Pseudo Code=
==EFP==
<pre>
int search( int alpha, int beta, ... ) {
bool fprune = ...;
int margin = ...;
for ( all moves ) {
if ( fprune && materialBalance + margin + gain(move) <= alpha ) continue;
make( move );
score = -search(-beta, -alpha, ...);
unmake( move );
...
}
...
}
</pre>
==RFP==
<pre>
int search( int alpha, int beta, ... ) {
int eval = evaluate(...);
int margin = ...;
if (... && eval - margin >= beta) {
return eval - margin; /* fail soft */
...
}
</pre>
=See also=
* [[AEL-Pruning]]
* [[Futility Pruning]]
* [[Null Move Observation]]
* [[Null Move Pruning]]
* [[Razoring]]
* [[Quiescence Search#StandPat|Standing Pat in Quiescence Search]]
=Forum Posts=
==2008 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=19316 Toga/Glaurung/Strelka Prunings/Reductions] by [[Edsel Apostol]], [[CCC]], January 31, 2008 » [[Toga]], [[Glaurung]], [[Strelka]], [[Reductions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=29439 Null move in quiescence search idea from Don Beal, 1986] by [[Eelco de Groot]], [[CCC]], August 17, 2009 » [[Quiescence Search]], [[Don Beal]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=34909 static null move pruning is stockfish] by [[Tom King]], [[CCC]], June 13, 2010 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=41302 Reverse Futility Pruning] by [[Matthew R. Brades]], [[CCC]], December 02, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=41337 mate distance pruning problems and static null move pruning] by Pierre Bokma, [[CCC]], December 04, 2011 » [[Mate Distance Pruning]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=59661 Futile attempts at futility pruning] by [[Martin Fierz]], [[CCC]], March 27, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61093 Futility prunning] by [[Daniel Anulliero]], [[CCC]], August 11, 2016 » [[Futility Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=62522 Static null move pruning] by Fernando Tenorio, [[CCC]], December 18, 2016
* [http://www.open-chess.org/viewtopic.php?f=5&t=3056 Static NULL Move] by thevinenator, [[Computer Chess Forums|OpenChess Forum]], December 26, 2016 » [[CPW-Engine_search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=63344 Futility pruning ?] by [[Mahmoud Uthman]], [[CCC]], March 04, 2017 » [[Futility Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=63852 increasing futility prunning depth] by [[Alexandru Mosoi]], [[CCC]], April 28, 2017
=References=
<references />
'''[[Pruning|Up one Level]]'''
