Practice

Real chess programs tend to sacrifice the theoretical soundness of futility pruning in favor of using it as a truly selective pruning technique. As mentioned above the tightness of the bound on positional scores greatly influences the futility cutoff-rate. Viewed the other way round, the introduction of a configurable futility margin instead of the theoretical bound max posn score allows for a variable leverage of the cutoff-rate. By choosing specific margins, chess programs can exert effective control over the futility cutoff-rate and the desired degree of selectiveness.

With margins ranging from 2-4 Pawns, selective futility pruning at frontier nodes proves to be quite safe in practice. While causing hardly any tactical mistakes it shrinks the search trees by 60% on average according to independent experiments by various researchers (e.g. Schaeffer [182], Ye and Marsland [216]). Many implementations increase the selectiveness even further by severely restricting possible search extensions in the subtrees of non-futile captures and checking moves at otherwise futile frontier nodes.

% latex2html id marker 13049
\fbox{{{\parbox{359pt}{\smallskip\smallskip
\center...
...derline{~}val\}\,<\,max\underline{~}posn\underline{~}score
\end{displaymath}}}}}



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