|
|
 |
|
|
|
|
e, the strategic options open to the opponent; in simple cases, the set of pure strategies. |
|
|
|
|
|
|
|
|
 , a ranking of plans using the cumulative payoff functions, the "gambler's ruin" criterion being an example. |
|
|
|
|
|
|
|
|
4. Searches, Pattern Recognition, and Statistical Inference |
|
|
|
|
|
|
|
|
Searches occur as the principal element in most problem-solving and goal-attainment attempts, from maze-running through resource allocation to very complicated planning situations in business, government, and research. Games and searches have much in common and, from one viewpoint, a game is just a search (perturbed by opponents) in which the object is to find a winning position. The complementary viewpoint is that a search is just a game in which the moves are the transformations (choices, inferences) permissible in carrying out the search. Thus, this discussion of searches complements the previous discussion of games. |
|
|
|
|
|
|
|
|
In complicated searches the attainable situations  are not given explicitly; instead some initial situation (position in a maze, collection of facts, etc.) is specified and the searcher is given a repertory of transformations {hi} which can be applied (repeatedly) in carrying out the search. As in the case of games, a tree is a convenient abstract representation of the search. For searches, each edge corresponds to a possible transformation hi and the traverse of any path in the tree corresponds to the application of the associated sequence of transformations. The vertex at the end of a path extending from the initial vertex corresponds to the situation produced from the initial situation by the transformations associated with the path. The difficulty of solving a problem or attaining a goal is primarily a function of the size of the search tree and the cost of applying the transformations. In most cases of interest the trees are so vast that hope of tracing out all alternative paths must be abandoned. Somehow one must formulate a search plan which, over a wide range of searches, will act with sufficient efficiency to attain the goal or solve the problem. |
|
|
|
|
|
|
|
|
A typical search plan (see Newell, Shaw, and Simon's [1959] GPS or Samuel's [1959] procedure) involves the following elements: |
|
|
|
|
|
|
|
|
(i) An (ordered) set of feature detectors { , where Vi is the range of readings or outputs of the ith detector}. Typically, each detector is an algorithm which, when presented with a "scene" or situation, calculates a number; if the number is restricted to 0 or 1, it is convenient to think of the algorithm as detecting the presence or absence of a |
|
|
|
|
|