Solution trees as a basis for game tree search
January 1994
Research Paper
| Related Files |
|---|
View PDF Version
(eur-few-cs-94-04.pdf, 0.1MB) |
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
Automatically Extracted Terms
- solution
- value
- max solution tree
- search
- game tree
- min solution tree
- alpha-beta
- algorithm
- search tree
- game value
- solution trees
- procedure
- s-alpha-beta
- solution tree
- sss -2
- sss -0
- postcondition
- minimax value
- figure
- node n
