Theory

The practical success of futility pruning at frontier nodes springs from the chess-related meaning of the selective futility condition. If the condition mat balance(node) + futil margin  <= alpha(node) holds for a node the side-to-move suffers from a material disadvantage of at least futil margin  >= 2 * pawn val with respect to the lower search bound. Because this bound must be exceeded in order to avoid a fail-low alpha cutoff, the side-to-move clearly features a bad position at the given node (relative to the bound).

In bad positions it is generally quite unusual in chess that quiet moves or non-checking captures with small material gains substantially improve the situation. The probability of such an improvement depends on the actual disadvantage alpha(node) - mat balance(node) and the remaining search depth at the node. The greater the disadvantage and the smaller the remaining depth are, the more unlikely will searches of these moves reveal any improvements over checking moves and captures with large material gains. In the case of selective futility pruning at frontier nodes the disadvantage amounts to at least 2 Pawns with a remaining depth = 1. The practical results of selective futility pruning at frontier nodes show that 1-ply searches of presumably futile moves almost never discover better compensation for disadvantages of  >= 2 Pawns than 1-ply searches of truly non-futile moves.

Because extended futility pruning applies at pre-frontier nodes with a remaining depth = 2, the margin of material disadvantage triggering extended cutoffs of presumably futile moves must be considerably higher than the normal futility margin. Otherwise, the selective risks of extended futility pruning would easily exceed its gains. Values ranging from Rook to Rook+Pawn for the extended futility margin make good sense from a chess point of view and they prove to work very well in practice (see below). For additional safety, extended futility pruning reuses an idea from razoring and does not perform any cutoffs at pre-frontier nodes if the immediately predecessing move caused an extension of search depth.

% latex2html id marker 13071
\fbox{{{\parbox{359pt}{\smallskip\smallskip
\center...
...~}val\,\ldots\,rook\underline{~}val+pawn\underline{~}val\}
\end{displaymath}}}}}



Created by Ernst A. Heinz, Thu Dec 16 23:28:11 EST 1999