Game tree algorithms and solution trees
January 1998
Research Paper
| Related Files |
|---|
View PDF Version
(eur-few-cs-98-02.pdf, 0.2MB) |
In this paper, a theory of game tree algorithms is presented, entirely based upon the concept of solution tree. Two types of solution trees are distinguished: max and min trees. Every game tree algorithm tries to prune nodes as many as possible from the game tree. A cut-off criterion in terms of solution trees will be formulated, which can be used to eliminate nodes from the search without affecting the result. Further, we show that any algorithm actually constructs a superposition of a max and a min solution tree. Finally, we will see, how solution trees and the related cutoff criterion are applied in major game tree algorithms, like alpha-beta and MTD.
Keywords
Automatically Extracted Terms
- value
- search tree
- search
- node n
- algorithm
- min tree
- solution
- max tree
- theorem
- max tree t
- game tree
- figure
- solution trees
- nition
- game tree algorithms
- game tree algorithm
- terminal
- result
- failure
- subcall
