A Minimax Algorithm Better than Alpha-Beta No and YesReport as inadecuate




A Minimax Algorithm Better than Alpha-Beta No and Yes - Download this document for free, or read online. Document in PDF available to download.

Simulations, Game-tree search, SSS*, Null window search, Alpha-Beta, Transposition tables, Solution trees, Minimax search

Additional contributors:

Subject-Keyword: Simulations Game-tree search SSS* Null window search Alpha-Beta Transposition tables Solution trees Minimax search

Type of item: Computing Science Technical Report

Computing science technical report ID: TR95-15

Language: English

Place:

Time:

Description: Technical report TR95-15. 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* = 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. 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-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. C We present a new instance of the framework, MTDf. It is well-suited for use with iterative deepening, and performs better than algorithms that are currently used in most state-of-the-art game-playing programs. We provide experimental evidence to explain why MTDf performs better than the other fixed-depth minimax algorithms.

Date created: 1995

DOI: doi:10.7939-R3C53F29R

License information: Creative Commons Attribution 3.0 Unported

Rights:





Author: Plaat, Aske Schaeffer, Jonathan Pijls, Wim de Bruin, Arie

Source: https://era.library.ualberta.ca/


Teaser



University of Alberta A Minimax Algorithm Better than Alpha-Beta? No and Yes by Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin Technical Report TR 95–15 June 1995 DEPARTMENT OF COMPUTING SCIENCE The University of Alberta Edmonton, Alberta, Canada i A Minimax Algorithm Better than Alpha-Beta? No and Yes Aske Plaat, Erasmus University, plaat@cs.few.eur.nl Jonathan Schaeffer, University of Alberta, jonathan@cs.ualberta.ca Wim Pijls, Erasmus University, whlmp@cs.few.eur.nl Arie de Bruin, Erasmus University, arie@cs.few.eur.nl Erasmus University, Department of Computer Science, Room H4-31, P.O.
Box 1738, 3000 DR Rotterdam, The Netherlands University of Alberta, Department of Computing Science, 615 General Services Building, Edmonton, Alberta, Canada T6G 2H1 July 6, 1995 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 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. (B) Based on the insights gained in our attempts at understanding SSS*, we present a framework that facilitates the construction of several best-first fixeddepth 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. (C) We present a new instance of the framework, MTD(ƒ).
...





Related documents