Related Work

Although it enjoys wide-spread use there does not exist much published material about futility pruning at frontier nodes. Schaeffer briefly explains the underlying futility idea in his 1986 Ph.D. thesis [182]. To the best of our knowledge, this is the earliest publication that presents quantitative experimental data illustrating the effectiveness of futility pruning at frontier nodes. Ye and Marsland's 1992 article [216] about forward pruning and search extensions in Chinese chess supports Schaeffer's findings by independent experiments. Section 1.3.4 discusses futility pruning at frontier nodes in detail.

Marsland's excellent (yet meanwhile somewhat outdated) overview of computer chess and search from 1992 [141] mentions three other statically selective pruning techniques that gained broad attention in the early days of computer chess. But Newborn's GAMMA algorithm [166], Slagle's marginal forward pruning [189], and Birmingham & Kent's razoring [34] seem to generate only little interest today (if any at all) because their aggressive selectiveness incurs too many tactical risks. Nevertheless, we deem the fundamental ideas of these forward pruning schemes as still very valuable. With the right additions and modifications, static forward pruning following a similar spirit like the above can work great as presented in the remainder of this article.

Null-move pruning [20,77] and Buro's PROBCUT enhancement [50] differ from the selective pruning schemes mentioned so far because they base their pruning decisions on dynamic rather than static criteria at the respective nodes. Both try to save work by speculatively replacing normal searches with much cheaper searches of reduced depths. The full-width nature of the reduced searches makes these two forward pruning techniques quite safe and successful in practice.1.4

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