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 respectively. 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.