Eigen-distribution on random assignments for game trees

DOI10.1016/j.ipl.2007.05.008zbMath1184.68475OpenAlexW1990117122MaRDI QIDQ2380000

Kazuyuki Tanaka, Chenguang Liu

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.05.008

zbMATH Keywords

computational complexityrandomized algorithmsgame treedistributional complexityeigen-distribution

Mathematics Subject Classification ID

Games involving graphs (91A43) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Uniqueness of optimal randomized algorithms for balanced AND-OR trees, Optimal depth-first algorithms and equilibria of independent distributions on multi-branching trees, The eigen-distribution for multi-branching weighted trees on independent distributions, Independent distributions on a multi-branching AND-OR tree of height 2, Equilibrium points of an AND-OR tree: under constraints on probability, Non-depth-first search against independent distributions on an AND-OR tree

Cites Work

• Error propagation in game trees
• Asymptotic properties of minimax trees and game-searching procedures
• An analysis of alpha-beta pruning
• A comparison of minimax tree search algorithms
• Error analysis in minimax trees
• Best-first fixed-depth minimax algorithms
• Optimal Search on Some Game Trees
• The solution for the branching factor of the alpha-beta pruning algorithm and its optimality
• The Variance of Two Game Tree Algorithms