ERA

Download the full-sized PDF of A New Paradigm for Minimax SearchDownload the full-sized PDF

Analytics

Share

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

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 New Paradigm for Minimax Search Open Access

Descriptions

Author or creator
Plaat, Aske
Schaeffer, Jonathan
Pijls, Wim
de Bruin, Arie
Additional contributors
Subject/Keyword
minimax game-tree search algorithms
Type of item
Computing Science Technical Report
Computing science technical report ID
TR94-18
Language
English
Place
Time
Description
Technical report TR94-18. This paper introduces a new paradigm for minimax game-tree search algorithms. MT is a memory-enhanced version of Pearl's Test procedure. By changing the way MT is called, a number of best-first game-tree search algorithms can be simply and elegantly constructed (including SSS). Most of the assessments of minimax search algorithms have been based on simulations. However, these simulations generally do not address two of the key ingredients of high performance game-playing programs: iterative deepening and memory usage. This paper presents experimental data from three game-playing programs (checkers, Othello and chess), covering the range from low to high branching factor. The improved move ordering due to iterative deepening and memory usage results in significantly different results from those portrayed in the literature. Whereas some simulations show AB expanding almost 100% more leaf nodes than other algorithms, our results showed variations of less than 20%. One new instance of our framework (MTD-f) out-performs our best alpha-beta searcher (aspiration NegaScout) on leaf nodes, total nodes and execution time. To our knowledge, these are the first reported results that compare both depth-first and best-first algorithms given the same amount of memory.
Date created
1994
DOI
doi:10.7939/R3H12VB6B
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-04-29T15:21:06.597+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: 369505
Last modified: 2015:10:12 20:46:04-06:00
Filename: TR94-18.pdf
Original checksum: 08bbb85ddf50f90cabd6b954ea80db77
Well formed: true
Valid: true
Page count: 27
Activity of users you follow
User Activity Date