Optimal Search on Some Game Trees

DOI10.1145/2402.322383MaRDI QIDQ3765270zbMATH OpenOpenAlexFDO

Authors Michael Tarsi

Publication date 1983

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2402.322383

zbMATH Keywords

alpha-beta pruningaverage optimal algorithmsdirectional algorithmgame strategiesgame tree

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Artificial intelligence (68T99) 2-person games (91A05)

Recommendations

• On the Optimality of Randomized \alpha-\beta Search
• Game tree searching by min/max approximation
• On the complexity of searching game trees and other recursion trees
• scientific article; zbMATH DE number 269837
• A general framework for minimax search in game trees

Cited in

(39)

• Game tree searching by min/max approximation
• A game tree with distinct leaf values which is easy for the alpha-beta algorithm
• Searching minimax game trees under memory space constraint
• Optimal comparison strategies in Ulam's searching game with two errors
• Game tree algorithms and solution trees
• Decision trees for function evaluation: simultaneous optimization of worst and expected cost
• Non-depth-first search against independent distributions on an AND-OR tree
• Applying genetic algorithms to game search trees
• Independent distributions on a multi-branching AND-OR tree of height 2
• Eigen-distribution on random assignments for game trees
• Finding optimal satisficing strategies for 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
• Searching game trees under a partial order
• On tree search algorithms
• Optimal strategy in games with chance nodes
• Experimental Analysis of the Probability Method
• AWT: Aspiration with Timer Search Algorithm in Siguo
• On the complexity of searching game trees and other recursion trees
• scientific article; zbMATH DE number 67462 (Why is no real title available?)
• A Game Tree Search by Probability Method
• Bounded branching process and and/or tree evaluation
• A SEARCH GAME WITH TRAVELING COST ON A TREE
• Equilibrium points of an AND-OR tree: under constraints on probability
• On Monte-Carlo tree search for deterministic games with alternate moves and complete information
• Uniqueness of optimal randomized algorithms for balanced AND-OR trees
• On the problem of solving multimove games under time deficit
• A parallel search game
• OPTIMAL STRATEGY IN “GUESS WHO?”: BEYOND BINARY SEARCH
• Algorithms – ESA 2004
• Average probe complexity in quorum systems
• Game chains
• Partial order bounding: A new approach to evaluation in game tree search
• The equilibria of independent distributions on unbalanced game trees
• Randomized vs. deterministic decision tree complexity for read-once Boolean functions
• Randomized query composition and sabotage complexity
• The distributional complexity of game trees over correlated distributions and independent distributions
• The complexity of a simple stochastic OR-tree model in which ``directional search is bad
• A randomized competitive algorithm for evaluating priced AND/OR trees

This page was built for publication: Optimal Search on Some Game Trees

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