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.

(Nega)scout, MTD, SSS*, alpha-beta, game tree search, minimax search, solution trees
hdl.handle.net/1765/468
Erasmus School of Economics

Pijls, W.H.L.M, de Bruin, A, & Plaat, A. (1996). A theory of game trees, based on solution trees. Retrieved from http://hdl.handle.net/1765/468