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

DOI10.1016/J.APAL.2015.07.002zbMATH Open1335.68244arXiv1401.8175OpenAlexW1492148130MaRDI QIDQ490867FDOQ490867

Authors: Toshio Suzuki, Yoshinao Niida 

Publication date: 21 August 2015

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

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.

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

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

zbMATH Keywords

computational complexityAND-OR treegame treeindependent identical distributionOR-AND tree

Mathematics Subject Classification ID

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

Cites Work

• An analysis of alpha-beta pruning
• Asymptotic properties of minimax trees and game-searching procedures
• On the branching factor of the alpha-beta pruning algorithm
• Eigen-distribution on random assignments for game trees
• Optimal Search on Some Game Trees
• The solution for the branching factor of the alpha-beta pruning algorithm and its optimality
• Title not available (Why is that?)

Cited In (9)

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

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)