Suzuki, Toshio Non-depth-first search against independent distributions on an AND-OR tree. (English) Zbl 1453.68174 Inf. Process. Lett. 139, 13-17 (2018). Summary: The first author and Y. Niida [Ann. Pure Appl. Logic 166, No. 11, 1150–1164 (2015; Zbl 1335.68244)] showed the following results on independent distributions (IDs) on an AND-OR tree, where they took only depth-first algorithms into consideration. (1) Suppose that a positive real number \(r<1\) is given, and let \(I(r)\) denote the class of all IDs such that the probability of the root having value 0 is \(r\); if, among members of \(I(r)\), \(d\) is a maximizer of cost of the best algorithm then \(d\) is an independent and identical distribution (IID). (2) The same as above holds for the set of all IDs in place of \(I(r)\). In the case where non-depth-first algorithms are taken into consideration, the counterparts of (1) and (2) are left open in the above work. W. Peng et al. [Inf. Process. Lett. 125, 41–45 (2017; Zbl 1409.68272)] extended (1) and (2) to multi-branching trees, where in (2) they put an additional hypothesis on ID \(d\) that the probability of the root having value 0 is neither 0 nor 1. We give positive answers for the two questions of Suzuki-Niida. A key to the proof is that if ID \(d\) achieves the equilibrium among IDs then \(d\) has an optimal algorithm that is depth-first. In addition, we extend theorem 3 of Peng et al. to the case where non-depth-first algorithms are taken into consideration. Cited in 2 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:non-depth-first algorithm; independent distribution; multi-branching tree; computational complexity; analysis of algorithms Citations:Zbl 1335.68244; Zbl 1409.68272 PDFBibTeX XMLCite \textit{T. Suzuki}, Inf. Process. Lett. 139, 13--17 (2018; Zbl 1453.68174) Full Text: DOI arXiv References: [1] Knuth, Donald E.; Moore, Ronald W., An analysis of alpha-beta pruning, Artif. Intell., 6, 293-326, (1975) · Zbl 0358.68143 [2] Liu, ChenGuang; Tanaka, Kazuyuki, Eigen-distribution on random assignments for game trees, Inf. Process. Lett., 104, 73-77, (2007) · Zbl 1184.68475 [3] Pearl, Judea, Asymptotic properties of minimax trees and game-searching procedures, Artif. Intell., 14, 113-138, (1980) · Zbl 0445.68048 [4] Pearl, Judea, The solution for the branching factor of the alpha-beta pruning algorithm and its optimality, Commun. ACM, 25, 559-564, (1982) · Zbl 0486.68056 [5] Peng, Weiguang; Peng, NingNing; Ng, KengMeng; Tanaka, Kazuyuki; Yang, Yue, Optimal depth-first algorithms and equilibria of independent distributions on multi-branching trees, Inf. Process. Lett., 125, 41-45, (2017) · Zbl 1409.68272 [6] Peng, Weiguang; Okisaka, Shohei; Li, Wenjuan; Tanaka, Kazuyuki, The uniqueness of eigen-distribution under non-directional algorithms, IAENG Int. J. Comput. Sci., 43, 318-325, (2016) · Zbl 1470.68049 [7] Saks, Michael; Wigderson, Avi, Probabilistic Boolean decision trees and the complexity of evaluating game trees, (Proc. 27th IEEE FOCS, (1986)), 29-38 [8] Suzuki, Toshio, Kazuyuki Tanaka’s work on AND-OR trees and subsequent developments, Ann. Japan Assoc. Philos. Sci., 25, 79-88, (2017), open access · Zbl 1506.68129 [9] Suzuki, Toshio; Nakamura, Ryota, The eigen distribution of an AND-OR tree under directional algorithms, IAENG Int. J. Appl. Math., 42, 122-128, (2012) · Zbl 1512.68314 [10] Suzuki, Toshio; Niida, Yoshinao, Equilibrium points of an AND-OR tree: under constraints on probability, Ann. Pure Appl. Logic, 166, 1150-1164, (2015) · Zbl 1335.68244 [11] Tarsi, Michael, Optimal search on some game trees, J. ACM, 30, 389-396, (1983) · Zbl 0628.68072 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.