Abstract | ||
---|---|---|
Abstract This paper has three main contributions to our understanding of fixed-depth minimax,search: (A) 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* = α-β + transposition tables. The crucial step is the realization that transposition tables contai n 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. (B) Based on the insights gained in our attempts at understanding SSS*, we present a framework,that facilitates the construction of several best-first fixed- |
Year | Venue | Keywords |
---|---|---|
2017 | arXiv: Artificial Intelligence | tree structure,search algorithm,transposition tables,alpha beta |
Field | DocType | Volume |
Minimax,Negamax,Monte Carlo tree search,Search algorithm,Expectiminimax tree,Computer science,Transposition table,Artificial intelligence,Machine learning,Alpha–beta pruning,Iterative deepening depth-first search | Journal | abs/1702.03401 |
Citations | PageRank | References |
5 | 0.64 | 29 |
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 |