Proceedings:
Proceedings of the AAAI Conference on Artificial Intelligence, 12
Volume
Issue:
Search and Genetic Algorithms
Track:
Two-Player Games
Downloads:
Abstract:
We present a very simple selective search algorithm for two-player games. It always expands next the frontier node that determines the minimax value of the root. The algorithm requires no information other than a static evaluation function, and its time overhead per node is similar to that of alpha-beta minimax. We also present an implementation of the algorithm that reduces its space complexity from exponential to linear in the search depth, at the cost of increased time complexity. In the game of Othello, using the evaluation function from BiIl (Lee and Mahajan 1990), best-first minimax outplays alpha-beta at moderate depths. A hybrid best-first extension algorithm, which combines alpha-beta and best-first minimax, performs significantly better than either pure algorithm even at greater depths. Similar results were also obtained for a class of random game trees.
AAAI
Search and Genetic Algorithms