Best-first fixed-depth minimax algorithms
| Autor: | Arie de Bruin, Jonathan Shaeffer, Aske Plaat, Wim Pijls |
|---|---|
| Rok vydání: | 1996 |
| Předmět: |
Linguistics and Language
Null-window search Computational complexity theory Negamax Computer science Computational Mechanics 02 engineering and technology 0102 computer and information sciences Solution trees 01 natural sciences Minimax search Language and Linguistics Game-tree search Transposition tables Search algorithm Artificial Intelligence Algorithmics 0202 electrical engineering electronic engineering information engineering Computer Science (miscellaneous) Mathematics Alpha-Beta Minimax Computer Graphics and Computer-Aided Design SSS Human-Computer Interaction Automated theorem proving 010201 computation theory & mathematics SSS∗ 020201 artificial intelligence & image processing Algorithm Transposition table |
| Zdroj: | Artificial Intelligence. 87(1-2):255-293 |
| ISSN: | 0004-3702 |
| DOI: | 10.1016/0004-3702(95)00126-3 |
| Popis: | This article has three main contributions to our understanding of minimax search: First, a new formulation for Stockman's SSS ∗ algorithm, based on Alpha-Beta, is presented. It solves all the perceived drawbacks of SSS ∗ , finally transforming it into a practical algorithm. In effect, we show that SSS ∗ = Alpha-Beta + transposition tables. The crucial step is the realization that transposition tables contain so-called solution trees, structures that are used in best-first search algorithms like SSS ∗ . Having created a practical version, we present performance measurements with tournament game-playing programs for three different minimax games, yielding results that contradict a number of publications. Second, based on the insights gained in our attempts at understanding SSS ∗ , we present a framework that facilitates the construction of several best-first fixed-depth game-tree search algorithms, known and new. The framework is based on depth-first null-window Alpha-Beta search, enhanced with storage to allow for the refining of previous search results. It focuses attention on the essential differences between algorithms. Third, a new instance of this framework is presented. It performs better than algorithms that are currently used in most state-of-the-art game-playing programs. We provide experimental evidence to explain why this new algorithm, MTD( f ), performs better than other fixed-depth minimax algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect