ACM Computing Survey 12:213-253

Earlier version in IJCAI 6 (1979). Artificial Intelligence, 14 (2), 165-203.

An algorithm based on state space search is introduced for computing the minimax value of game trees. The new algorithm SSS∗ is shown to be more efficient than α-ß in the sense that SSS∗ never evaluates a node that α-ß can ignore. Moreover, for practical distributions of tip node values, SSS∗ can expect to do strictly better than α-ß in terms of average number of nodes explored. In order to be more informed than α-ß, SSS∗ sinks paths in parallel across the full breadth of the game tree. The penalty for maintaining these alternate search paths is a large increase in storage requirement relative to α-ß.

The determination of subgraph and graph isomorphisms is an important application for the algebraic manipulation of networks of binary constraints. Simplified and streamlined arc consistency and tree search algorithms are introduced, and experimental results show substantial reduction in timings compared with previous algorithms for determining isomorphisms. Several path consistency algorithms, including a new one, have been timed experimentally on isomorphism problems, and found not to be cost effective despite their theoretical appeal. The importance of this result is enhanced by the absence of previously published experimentation with path consistency. A theoretical study of the new path consistency algorithm provides insight into the experimental results.

Artificial Intelligence, 12 (1), 23-40.

I will remain Ion8 and deeply indebted to Herb Simon, H. T. Kung, AI Newell, Jay

Our purpose in studying natural language understanding in conjunction with problem solving is to bring together the constraints of what formal representation can actually be obtained with the question of what knowledge is required in order to solve a wide range of problems in a semantically rich domain. We believe that these issues cannot sensibly be tackled in isolation. In practical terms we have had the benefits of an increased awareness of common problems in both areas and a realisation that some of our techniques are applicable to both the control of inference and the control of parsing. Early work on solving mathematical problems stated in natural language was done by Bobrow (STUDENT - (i]) and Chamiak (CARPS - [5]). However the rudimentary parsing and simple semantic structures used by Bobrow and Charniak are inadequate for any but the easiest problems. Our intention has been to build on B/RG Chris This work was supported by SRC grant number 94493 and an SRC research studentship for Mellish.

A constraint network representation is presented for a combinatorial search problem: finding values for a set of variables subject to a set of constraints. A theory of consistency levels in such networks is formulated, which is related to problems of backtrack tree search efficiency. An algorithm is developed that can achieve any level of consistency desired, in order to preprocess the problem for subsequent backtrack search, or to function as an alternative to backtrack search by explicitly determining all solutions.

An analysis of the alpha-beta pruning algorithm is presented which takes into account both shallow and deep cut-offs. A formula is first developed to measure the average number of terminal nodes examined by the algorithm in a uniform tree of degree n and depth d when ties are allowed among the bottom positions: specifically, all bottom values are assumed to be independent identically distributed random variables drawn from a discrete probability distribution. A worst case analysis over all possible probability distributions is then presented by considering the limiting case when the discrete probability distribution tends to a continuous probability distribution. The branching factor of the alpha-beta pruning algorithm is shown to grow with n as Θ(n/lnn), therefore confirming a claim by Knuth and Moore that deep cut-offs only have a second order effect on the behavior of the algorithm.

Optimal decision table conversion has been tackled in the literature using two approaches, dynamic programming and branch-and-bound. The former technique is quite effective, but its time and space requirements are independent of how "easy" the given table is. Furthermore, it cannot be used to produce good, quasioptimal solutions. The branch-and-bound technique uses a good heuristic to direct the search, but is cluttered up by an enormous search space, since the number of solutions increases with the number of test variables according to a double exponential. In this paper we suggest a heuristically guided top-down search algorithm which, like dynamic programming, recognizes identical subproblems but which can be used to find both optimal and quasioptimal solutions. The heuristic search method introduced in this paper combines the positive aspects of the above two techniques.