Game Tree Algorithms and Solution Trees
Wim Pijls, Arie de Bruin · EUR Research Repository (Erasmus University Rotterdam) · 1998
. In this paper a theory of game tree algorithms is presented, entirely based upon the concept of a solution tree. Two types of solution trees are distinguished: max and min trees. Every game tree algorithm tries to prune as many nodes as possible from the game tree. A cut-o# criterion in terms of solution trees will be formulated, which can be used to eliminate nodes from the search without a#ecting 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 cuto# criterion are applied in major game tree algorithms like alphabeta and MTD. Keywords: Game tree search, Minimax search, Solution trees, Alphabeta, SSS*, MTD. 1 Introduction A game tree models the behavior of a two-player game. Each node n in such a tree represents a position in a game. An example of a game tree with game values is found in Figure 1. The players are called Max and Min. Max is moving from the squ...