Probabilistic Boolean decision trees and the complexity of evaluating game trees
Authors:
- 1 October 1986
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 29-38
Abstract
The Boolean Decision tree model is perhaps the simplest model that computes Boolean functions; it charges only for reading an input variable. We study the power of randomness (vs. both determinism and non-determinism) in this model, and prove separation results between the three complexity measures. These results are obtained via general and efficient methods for computing upper and lower bounds on the probabilistic complexity of evaluating Boolean formulae in which every variable appears exactly once (AND/OR tree with distinct leaves). These bounds are shown to be exactly tight for interesting families of such tree functions. We then apply our results to the complexity of evaluating game trees, which is a central problem in AI. These trees are similar to Boolean tree functions, except that input variables (leaves) may take values from a large set (of valuations to game positions) and the AND/OR nodes are replaced by MIN/MAX nodes. Here the cost is the number of positions (leaves) probed by the algorithm. The best known algorithm for this problem is the alpha-beta pruning method. As a deterministic algorithm, it will in the worst case have to examine all positions. Many papers studied the expected behavior of alpha-beta pruning (on uniform trees) under the unreasonable assumption that position values are drawn independently from some distribution. We analyze a randomized variant of alphabeta pruning, show that it is considerably faster than the deterministic one in worst case, and prove it optimal for uniform trees.Keywords
This publication has 11 references indexed in Scilit:
- The complexity of problems on probabilistic, nondeterministic, and alternating decision treesJournal of the ACM, 1985
- Lower bounds on probabilistic linear decision treesTheoretical Computer Science, 1985
- A topological approach to evasivenessCombinatorica, 1984
- Optimal Search on Some Game TreesJournal of the ACM, 1983
- The solution for the branching factor of the alpha-beta pruning algorithm and its optimalityCommunications of the ACM, 1982
- Asymptotic properties of minimax trees and game-searching proceduresArtificial Intelligence, 1980
- Further results on the Aanderaa-Rosenberg conjectureJournal of Combinatorial Theory, Series B, 1980
- Probabilistic computations: Toward a unified measure of complexity1977
- An analysis of alpha-beta pruningArtificial Intelligence, 1975
- On the time required to recognize properties of graphsACM SIGACT News, 1973