ERA

Download the full-sized PDF of A Minimax Algorithm Better than Alpha-Beta? No and YesDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3C53F29R

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

A Minimax Algorithm Better than Alpha-Beta? No and Yes Open Access

Descriptions

Author or creator
Plaat, Aske
Schaeffer, Jonathan
Pijls, Wim
de Bruin, Arie
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, MTD(f). 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 MTD(f) 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

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-05-01T03:30:37.958+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 695338
Last modified: 2015:10:12 17:08:29-06:00
Filename: TR95-15.pdf
Original checksum: 5aaf95a9b2136cd1affd4dde0bd7ab51
Well formed: true
Valid: true
Page count: 50
Activity of users you follow
User Activity Date