Suzuki, Toshio; Niida, Yoshinao Equilibrium points of an AND-OR tree: under constraints on probability. (English) Zbl 1335.68244 Ann. Pure Appl. Logic 166, No. 11, 1150-1164 (2015). 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)]. Cited in 2 ReviewsCited in 4 Documents 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.) Keywords:game tree; AND-OR tree; OR-AND tree; independent identical distribution; computational complexity Citations:Zbl 1184.68475 PDFBibTeX XMLCite \textit{T. Suzuki} and \textit{Y. Niida}, Ann. Pure Appl. Logic 166, No. 11, 1150--1164 (2015; Zbl 1335.68244) 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.