Reverse Futility Pruning

From Chessprogramming wiki
Jump to: navigation, search

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 [1]:

Pseudo Code

EFP

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 );
    ...
  }
  ...
}

RFP

int search( int alpha, int beta, ... ) {
  int eval = evaluate(...);
  int margin = ...;
  if (... && eval - margin >= beta) {
    return eval - margin; /* fail soft */
  ...
}

See also

Forum Posts

2008 ...

2010 ...

2015 ...

References

Up one Level