Eigen-distribution on assignments for game trees with random properties

ABSTRACT

In this paper, we investigate a special distribution, called eigen-distribution, on assignments for game tree T^k2 with random properties. There are two cases, where the assignments to leaves are independently distributed (ID) and correlated distributed (CD). In ID setting, we prove that the distributional probability ϱ belongs to [EQUATION] and ϱ is a strictly increasing function on rounds [EQUATION]. In CD setting, we propose a reverse assigning technique (RAT) to form 1-set and 0-set, then show that E¹-distribution (namely, a particular distribution on assignments of 1-set such that the complexity of any deterministic algorithm is equal) is the unique eigen-distribution.

REFERENCES

• 1: Pearl, J.: Asymptotic Properties of Minimax Tress and Game-Searching Procedures. Artificial Intelligence, <b>14</b>(1980):113--138
• 2: Saks, M., and Wigderson, A.: Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees. FOGS, (1986): 29--38.
• 3: Michael Tarsi, Optimal Search on Some Game Trees, Journal of the ACM (JACM), v.30 n.3, p.389-396, July 1983 [doi>10.1145/2402.322383]
• 4: Yao, A. C.-C.: Probabilistic Computations: Towards a Unified Measure of Complexity. FOCS,(1977): 222--227

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms

Keywords:
computational complexity, distributional complexity, eigen-distribution, game trees, randomized algorithms