Independent distributions on a multi-branching AND-OR tree of height 2

DOI10.1016/J.DAM.2020.05.007MaRDI QIDQ2197433zbMATH OpenOpenAlexFDO

Authors Mika Shigemizu, Toshio Suzuki, Koki Usami

Publication date 31 August 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.06601

zbMATH Keywords

analysis of algorithmscomputational complexitydepth-first algorithmindependent distributionmulti-branching tree

Mathematics Subject Classification ID

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

Abstract: We investigate an AND-OR tree T and a probability distribution d on the truth assignments to the leaves. Tarsi (1983) showed that if d is an independent and identical distribution (IID) such that probability of a leaf having value 0 is neither 0 nor 1 then, under a certain assumptions, there exists an optimal algorithm that is depth-first. We investigate the case where d is an independent distribution (ID) and probability depends on each leaf. It is known that in this general case, if height is greater than or equal to 3, Tarsi-type result does not hold. It is also known that for a complete binary tree of height 2, Tarsi-type result certainly holds. In this paper, we ask whether Tarsi-type result holds for an AND-OR tree of height 2. Here, a child node of the root is either an OR-gate or a leaf: The number of child nodes of an internal node is arbitrary, and depends on an internal node. We give an affirmative answer. Our strategy of the proof is to reduce the problem to the case of directional algorithms. We perform induction on the number of leaves, and modify Tarsi's method to suite height 2 trees. We discuss why our proof does not apply to height 3 trees.

Recommendations

• Non-depth-first search against independent distributions on an AND-OR tree
• Optimal depth-first algorithms and equilibria of independent distributions on multi-branching trees
• Equilibrium points of an AND-OR tree: under constraints on probability
• And/or trees: A local limit point of view
• And/Or Trees Revisited

Cites work

• An analysis of alpha-beta pruning
• Asymptotic properties of minimax trees and game-searching procedures
• Eigen-distribution on random assignments for game trees
• Equilibrium points of an AND-OR tree: under constraints on probability
• scientific article; zbMATH DE number 7696296 (Why is no real title available?)
• Kazuyuki Tanaka's Work on AND-OR Trees and Subsequent Developments
• Non-depth-first search against independent distributions on an AND-OR tree
• Optimal depth-first algorithms and equilibria of independent distributions on multi-branching trees
• Optimal Search on Some Game Trees
• The solution for the branching factor of the alpha-beta pruning algorithm and its optimality

Cited in

(5)

• Non-depth-first search against independent distributions on an AND-OR tree
• Optimal depth-first algorithms and equilibria of independent distributions on multi-branching trees
• The eigen-distribution for multi-branching weighted trees on independent distributions
• Equilibrium points of an AND-OR tree: under constraints on probability
• Kazuyuki Tanaka's Work on AND-OR Trees and Subsequent Developments

This page was built for publication: Independent distributions on a multi-branching AND-OR tree of height 2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197433)