A Theory of Game Trees, Based on Solution Trees

In this paper a complete theory of game tree algorithms is presented, entirely based upon the notion of a solution tree. Two types of solution trees are distinguished: max and min solution trees respctively. We show that most game tree algorithms construct a superposition of a max and a min solution tree. Moreover, we formulate a general cut-off criterion in terms of solution trees. In the second half of this paper four well known algorithms, viz., alphabeta, SSS*, MTD and Scout are studied extensively. We show how solution trees feature in these algorithms and how the cut-off criterion is applied. Keywords: Game tree search, Minimax search, Solution trees, Alpha-beta, SSS*, MTD, (Nega)Scout. 1 Introduction A game tree models the behavior of a two-player game. The nodes in such a tree represent positions of a game, whereas edges represent moves. Given a payoff in the leaves of a game tree, the best move in each position can be determined by means of the so-called minimax function. Ov..