A Theory of Game Trees, Based on Solution Trees

摘要

In this paper, a theory of game tree algorithms is presented, entirely based upon the concept of solution tree. During execution of a game tree algorithm, one may distinguish between so-called alive and dead nodes. It will turn out, that only alive nodes have to be considered, whereas dead nodes should be neglected. The algorithm may stop, when every node is dead. Further, it is proved that every algorithm needs to build a critical tree. Finally, we show, that some common game tree algorithms agree with this theory.