Single-Agent and Game-Tree Search
T.A. Marsland · ICGA Journal · 1991
Problem solving by exhaustive enumeration is a common computational technique that often relies on a decision tree framework to ensure that all combinations are considered.This approach is helped by a wealth of powerful tools for supporting tree searches.A related but slightly more general model is based on a state-space approach in which, from a given state of the system and a set of actions (that is, given a description vector), the successor states are expanded until a specified goal is reached."( ... ) "To illustrate these points [e.g., the limitation of storage space, the trade-off between space and time, and the use of heuristics], and to provide insights into widely applicable and generally useful techniques that can be used to improve many optimization methods, we will consider the subdomains of single agent (one person) and adversary (two-person) games.In both cases solutions can be found by traversing a decision tree that spans all the possible states in the "game".Since the order in which the decisions are made is not necessarily important, it is common for identical states to exist at different places in the decision tree.Under these circumstances such trees might be viewed as graphs.Because a tree is an intrinsically simpler structure, as well as being more regular than a graph, we will temporarily ignore such duplications, but later we will introduce methods that explicitly recognize and eliminate duplicates, and so reduce the effective size of the search space."