Equilibrium points of an AND-OR tree: under constraints on probability

DOI10.1016/J.APAL.2015.07.002MaRDI QIDQ490867zbMATH OpenOpenAlexFDO

Authors Toshio Suzuki, Yoshinao Niida

Publication date 21 August 2015

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

AND-OR treecomputational complexitygame treeindependent identical distributionOR-AND 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 study a probability distribution d on the truth assignments to a uniform binary AND-OR tree. Liu and Tanaka [2007, Inform. Process. Lett.] showed the following: If d achieves the equilibrium among independent distributions (ID) then d is an independent identical distribution (IID). We show a stronger form of the above result. Given a real number r such that 0 < r < 1, we consider a constraint that the probability of the root node having the value 0 is r. Our main result is the following: When we restrict ourselves to IDs satisfying this constraint, the above result of Liu and Tanaka still holds. The proof employs clever tricks of induction. In particular, we show two fundamental relationships between expected cost and probability in an IID on an OR-AND tree: (1) The ratio of the cost to the probability (of the root having the value 0) is a decreasing function of the probability x of the leaf. (2) The ratio of derivative of the cost to the derivative of the probability is a decreasing function of x, too.

Recommendations

• Non-depth-first search against independent distributions on an AND-OR tree
• Independent distributions on a multi-branching AND-OR tree of height 2
• Optimal depth-first algorithms and equilibria of independent distributions on multi-branching trees
• And/or tree probabilities of Boolean functions
• Finding optimal satisficing strategies for and-or trees

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
• scientific article; zbMATH DE number 7696296 (Why is no real title available?)
• On the branching factor of the alpha-beta pruning algorithm
• Optimal Search on Some Game Trees
• The solution for the branching factor of the alpha-beta pruning algorithm and its optimality

Cited in

(10)

• Non-depth-first search against independent distributions on an AND-OR tree
• Independent distributions on a multi-branching AND-OR tree of height 2
• Optimal depth-first algorithms and equilibria of independent distributions on multi-branching trees
• The eigen-distribution for multi-branching weighted trees on independent distributions
• Bounded branching process and and/or tree evaluation
• Uniqueness of optimal randomized algorithms for balanced AND-OR trees
• Kazuyuki Tanaka's Work on AND-OR Trees and Subsequent Developments
• The equilibria of independent distributions on unbalanced game trees
• Optimal randomized algorithms of weakly-balanced multi-branching AND-OR trees
• The distributional complexity of game trees over correlated distributions and independent distributions

This page was built for publication: Equilibrium points of an AND-OR tree: under constraints on probability

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