Solution trees as a basis for game tree search

Arie de Bruin, Wim Pijls and Aske Plaat
Additional contact information
Aske Plaat: Erasmus University, Department of Computer Science

No 100, Discussion Paper from Erasmus University Rotterdam, Faculty of Economics

Abstract: A game tree algorithm is an algorithm computing the minimax value of the root of a game tree. Many algorithms use the notion of establishing proofs that this value lies above or below some boundary value. We show that this amounts to the construction of a solution tree. We discuss the role of solution trees and critical trees in the following algorithms: Principal Variation Search, alpha-beta, and SSS-2. A general procedure for the construction of a solution tree, based on alpha-beta and Null-Window-Search, is given. Furthermore two new examples of solution tree-based algorithms are presented, that surpass alpha-beta, i.e., never visit more nodes than alpha-beta, and often less

Keywords: Minimax problemen; Algoritmen (search for similar items in EconPapers)
Date: 1994
References: View references in EconPapers View complete reference list from CitEc
Citations View citations in EconPapers (2) Track citations by RSS feed

Downloads: (external link)
http://www.eur.nl/WebDOC/doc/informatica/inf19960111120025.ps (application/postscript)
Our link check indicates that this URL is bad, the error code is: 404 Not Found

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:dgr:eureco:1997100

Access Statistics for this paper

More papers in Discussion Paper from Erasmus University Rotterdam, Faculty of Economics
Series data maintained by Anneke Kop (). This e-mail address is bad, please contact .