Name
Abstract | ||
|---|---|---|
Most practitioners use a variant of the Alpha-Beta algorith m, a simple depth-first pro- cedure, for searching minimax trees. SSS*, with its best-first search strategy, reportedly offers the potential for more efficient search. However, the complex formulation of the al- gorithm and its alleged excessive memory requirements preclude its use in practice. For two decades, the search efficiency of "smart" best-first SSS* has cast doubt on the effectiveness of "dumb" depth-first Alpha-Beta. This paper presents a simple framework for calling Alpha-Beta that allows us to create a variety of algorithms, including SSS* and DUAL*. In effect, we formulate a best-first algorithm using depth-first search. Expressed in this framework SSS* is just a special case of Alpha-Beta, solving all of the perceived drawbacks of the algorithm. In practice, Alpha-Beta variants typically evaluate less nodes than SSS*. A new instance of this framework, MTD(ƒ), out-performs SSS* and NegaScout, the Alpha-Beta variant of choice by practitioners. |
Year | Venue | Keywords |
|---|---|---|
2015 | CoRR | depth first search |
Field | DocType | Volume |
Data mining,Minimax,Computer science,Depth-first search,Minimax search,Artificial intelligence,SSS*,Machine learning,Special case | Journal | abs/1505.01603 |
Citations | PageRank | References |
2 | 0.40 | 23 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aske Plaat | 1 | 524 | 72.18 |
| Jonathan Schaeffer | 2 | 1929 | 220.77 |
| Wim Pijls | 3 | 165 | 16.86 |
| Arie de Bruin | 4 | 252 | 26.86 |