The Computational Complexity of Game Trees by Eigen-Distribution

DOI10.1007/978-3-540-73556-4_34MaRDI QIDQ3611985zbMATH OpenOpenAlexFDO

Authors Chenguang Liu, Kazuyuki Tanaka

Publication date 3 March 2009

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73556-4_34

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) 2-person games (91A05)

Recommendations

• The eigen-distribution of weighted game trees
• The Complexity of Algorithms Computing Game Trees on Random Assignments
• Eigen-distribution on random assignments for game trees
• Tree projections: Game characterization and computational aspects
• Structure theorems for game trees
• On the complexity of searching game trees and other recursion trees
• scientific article; zbMATH DE number 1342211
• The Variance of Two Game Tree Algorithms
• On Complexity of Ehrenfeucht-Fraïssé Games
• On complexity of Ehrenfeucht-Fraïssé games

Cited in

(11)

• The eigen-distribution of weighted game trees
• Computing branching distances with quantitative games
• Eigen-distribution on random assignments for game trees
• A game characterisation of tree-like Q-resolution size
• The eigen-distribution for multi-branching weighted trees on independent distributions
• The Variance of Two Game Tree Algorithms
• The Complexity of Algorithms Computing Game Trees on Random Assignments
• Kazuyuki Tanaka's Work on AND-OR Trees and Subsequent Developments
• The equilibria of independent distributions on unbalanced game trees
• Randomized vs. deterministic decision tree complexity for read-once Boolean functions
• The distributional complexity of game trees over correlated distributions and independent distributions

This page was built for publication: The Computational Complexity of Game Trees by Eigen-Distribution

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