×

Non-depth-first search against independent distributions on an AND-OR tree. (English) Zbl 1453.68174

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.

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.)
PDFBibTeX XMLCite
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.