×

Equilibrium points of an AND-OR tree: under constraints on probability. (English) Zbl 1335.68244

Summary: We consider a depth-first search based algorithm to find the truth value of the root of an AND-OR tree. The cost is measured by the number of leaves probed during the computation. We consider probability distributions on the truth assignments, and restrict the attention to distributions that have the following properties: 1. The inputs come from a product distribution. 2. The output probability (of the root being assigned zero) is some fixed \(r\) such that \(0 < r < 1\). Among such distributions we investigate the maximizer of the minimum expected cost. We show that the maximizer is an independent identical distributions (IID). The result may appear to be straightforward but, the fact is that the proof requires new ideas. As keys to the proof, we show fundamental relationships between the following two quantities: 1. The probability of the root being assigned zero. 2. The minimum expected cost. Our result justifies a claim in the paper of C. Liu and K. Tanaka [Inf. Process. Lett. 104, No. 2, 73–77 (2007; Zbl 1184.68475)].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q25 Analysis of algorithms and problem complexity
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Citations:

Zbl 1184.68475
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Baudet, G. M., On the branching factor of the alpha-beta pruning algorithm, Artificial Intelligence, 10, 173-199 (1978) · Zbl 0377.68023
[2] Knuth, D. E.; Moore, R. W., An analysis of alpha-beta pruning, Artificial Intelligence, 6, 293-326 (1975) · Zbl 0358.68143
[3] Liu, C.-G.; Tanaka, K., Eigen-distribution on random assignments for game trees, Inform. Process. Lett., 104, 73-77 (2007) · Zbl 1184.68475
[4] Pearl, J., Asymptotic properties of minimax trees and game-searching procedures, Artificial Intelligence, 14, 113-138 (1980) · Zbl 0445.68048
[5] Pearl, J., The solution for the branching factor of the alpha-beta pruning algorithm and its optimality, Commun. ACM, 25, 559-564 (1982) · Zbl 0486.68056
[6] Saks, M.; Wigderson, A., Probabilistic Boolean decision trees and the complexity of evaluating game trees, (Proc. 27th Annual IEEE Symposium on Foundations of Computer Science. Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, FOCS (1986)), 29-38
[7] Suzuki, T.; Nakamura, R., The eigen distribution of an AND-OR tree under directional algorithms, IAENG Int. J. Appl. Math., 42, 122-128 (2012), an online version may be found at the following · Zbl 1512.68314
[8] Tarsi, M., Optimal search on some game trees, J. ACM, 30, 389-396 (1983) · Zbl 0628.68072
[9] Yao, A. C.-C., Probabilistic computations: towards a unified measure of complexity, (Proc. 18th Annual IEEE Symposium on Foundations of Computer Science. Proc. 18th Annual IEEE Symposium on Foundations of Computer Science, FOCS (1977)), 222-227
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.