"Although the problem of determining the minimum cost path through a graph arises naturally in a number of interesting applications, there has been no underlying theory to guide the development of efficient search procedures. Moreover, there is no adequate conceptual framework within which the various ad hoc search strategies proposed to date can be compared. This paper describes how heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching and demonstrates an optimality property of a class of search strategies." IEEE Transactions on Systems Science and Cybernetics, SSC-4 (2), 100-107. See also correction: http://dl.acm.org/citation.cfm?id=1056779.

BOXES is the name of a computer program. This is what the chess player does when he lumps together large numbers of positions as being'similar' to each other, by neglecting the strategically irrelevant features in which they differ. The resultant small game can be said to be a'model' of the large game. To give a brutally extreme example, consider a specification of chess positions so incomplete as to map from the viewpoint of White the approximately 1050 positions of the large game on to the seven shown in Figure 1. Even this simple classification may have a role in the learning of chess.

Young animals play games in order to prepare themselves for the business of serious living, without getting hurt in the training period. Game-playing on computers serves a similar function. It can teach us something about the structure of thought processes and the theory of struggle and has the advantage over economic modelling that the rules and objectives are clear-cut. If the machine wins tournaments it must be a good player. The complexity and originality of a master chess player is perhaps greater than that of a professional economist. The chess player continually pits his wits against other players and the precision of the rules makes feasible a depth of thinking comparable to that in mathematics. No program has yet been written that plays chess of even good amateur standard. A really good chess program would be a breakthrough in work on machine intelligence, and would be a great encouragement to workers in other parts of this field and to those who sponsor such work. In criticism of the writing of a chess program, Macdonald (1950) quoted a remark to the effect that a machine for smoking tobacco could be built, but would serve no useful purpose. The irony is that smoking machines have since been built in order to help research on the medical effects of smoking. This does not prove that a chess program should be written, but suggests that the arguments against it might be shallow. Many branches of science, and of pure and applied mathematics, have started with a study of apparently frivolous things such as puzzles and games. It is pertinent to ask in what way a good chess program would take us beyond the draughts program of A. The answer is related to the much greater complication of chess, the much larger number of variations and possible positions. In fact, the number of possible chess positions is about the cube or fourth power of the number of possible draughts positions (see Appendix E). Samuel was able to make considerable use of the storage of thousands of positions that had occurred in the previous experience of the machine, and this led to a very useful increase in the depth of analysis of individual positions. The value of this device depends on the probability that, at any moment in the analysis, we run into a position that has already been analysed and stored. This applies more generally to the goals and subgoals that occur to the chess player. Thus there should be'specificallydirected' as well as'routinely-directed' analysis. Another important aspect of chess thinking, also required in most other problem-solving, is what de Groot (1946, 1965) calls'progressive deepening' of an analysis. Typically an analysis of a position by a human player does not simply follow a tree formation, but contains cycles in which a piece of analysis is retraced and improved.

In Proc. 23rd ACM National Conference.

THE "EXPLANATORY" USE OF THIS FRAMEWORK RESIDES IN THE NECESSARY CLAIM THAT, ALTHOUGH THERE CAN BE COMPOUND INSTANCES OF A SINGLE CASE (THROUGH NOUN PHRASE CONJUNCTION), EACH CASE RELATIONSHIP OCCURS ONLY ONCE IN A SIMPLE SENTENCE.

This paper describes some of the difficulties in maintaining large computer systems and considers how machine perception techniques can be applied to the problem. A program called the'engineer's assistant' is described as a step in the right direction. Elaborations are made on the meaning of'the right direction', and an experimental implementation of some of these ideas is described.

During the past few years there has been a rapid advance in the technology of time-sharing systems and software to permit quick access to large files of structured data. This has led to a growing interest in communicating with computer files directly in a natural language such as English. The natural language systems described in the literature are largely small-scale research vehicles dealing with small data bases of restricted subject scope. Giuliano (1965), among others, has questioned the generalization of these systems to wider universes of discourse. Developments in this area have been reviewed by Simmons (1966), and by Bobrow, Fraser and Quillan (1967).

Work performed under the auspices of the U. S. Atomic Energy Commission. To view the rest of this content please follow the download PDF link above.

Attempts to write'intelligent' computer programs have commonly involved the choice for attack of some particular aspect of intelligent behaviour, together with the choice of some relevant task, or range of tasks, which the program must perform. The emphasis is sometimes on the generality of the program's ability, sometimes on the importance of the particular task which it can perform. Well-known examples of such programs are Newell, Shaw, and Simon's General Problem Solver (1959; see also Ernst and Newell, 1967), which is applicable to a wide range of simple problems, Samuel's checker (draughts) playing program (1959, 1967), and the program written by Evans (1964), which solves geometric analogy problems. However, there is another approach to the goal of machine intelligence which stresses the relationship of an organism to its environment and which sets out from the start to understand what is involved in this relationship. Long ago Grey Walter (1953) experimented with mechanical'tortoises' which could range over the floor in a lifelike manner. Toda (1962), in a whimsical and illuminating paper, has discussed the problems facing an automaton in a simple artificial environment. Friedman (1967), a psychologist, has described a computer simulation of instinctive behaviour involving an automaton equipped with sensory and motor systems.

The generalized resolution principle is a single inference principle which provides, by itself, a complete formulation of the quantifier-free first-order predicate calculus with equality. It is a natural generalization of the various versions and extensions of the resolution principle, each of which it includes as special cases; but in addition it supplies all of the inferential machinery which is needed in order to be able to treat the intended interpretation of the equality symbol as'built in', and obviates the need to include special axioms of equality in the formulation of every theorem-proving problem which makes use of that notion. The completeness theory of the generalized resolution principle exploits the very intuitive and natural idea of attempting to construct counterexamples to the theorems for which proofs are wanted, and makes this the central concept. It is shown how a proof of a theorem is generated automatically by the breakdown of a sustained attempt to construct a counterexample for it. The kind of proof one gets depends entirely on the way in which the attempt to construct a counterexample is organized, and the theory places virtually no restrictions on how this shall be done. Consequently there is a very wide freedom in the form which proofs may take: the individual inferences in a proof may be very'small' or very'large' (in a scale of measurement which, roughly speaking, weighs the amount of computing necessary to check that the inference is correct). It is even correct to infer the truth of a true proposition in just one step, but, presumably, to offer such a proof to someone who wishes to be convinced of the proposition's truth would not be helpful epistemologically. His conviction would come, not from contemplating the proof itself, but rather from examining the computation which shows the correctness of its single inference step.