Many problems in artificial intelligence involve the searching of large trees of alternative possibilities--for example, game-playing and theorem-proving. The problem of efficiently searching large trees is discussed. A new method called "dynamic ordering" is described, and the older minimax and Alpha-Beta procedures are described for comparison purposes. Performance figures are given for six variations of the game of kalah. A quantity called "depth ratio" is derived which is a measure of the efficiency of a search procedure.

The problem discussed in this paper, namely that of finding a function to satisfy a given argument-value table, is by no means new to computing science, or to mathematics. Thus, for example, the problem of fitting a curve to a set of points is a part of numerical analysis. However, I am concerned with finding a function over a non-metric space, and so my work is closer to that of Feldman et al. (1969) in what they call, 'grammatical inference' or to the automaton-synthesizing programs described by Fogel, Owens and Walsh (1966).

Grammars or syntax specifications address themselves to the characterisation in symbolic terms of the structure of complex expressions. Two types of expression of empirical interest have been studied: sentences in English and other'natural' languages, and programs written in some high-level procedural language like ALGOL. Expressions in these languages consist of sets of elements (words and characters) coordinated with one another according to the sensorily manifest relationship'alongside', more commonly termed'followed by'.

A robot, in order to act intelligently, must be able to reason from facts which its sensors detect to conclusions which govern its actions. This reasoning process is so central to human intelligence that it seems immediately relevant to the problems of robot design to consider its properties, how it might be analysed and imitated.

The problem of producing sentences of a transformational grammar by using a random generator to create phrase structure trees for input to the lexical insertion and transformational phases is discussed. A purely random generator will produce base trees which will be blocked by the transformations, and which are frequently too long to be of practical interest. A solution is offered in the form of a computer program which allows the user to constrain and direct the generation by the simple but powerful device of restricted subtrees. The program is a directed random generator which accepts as input a subtree with restrictions and produces around it a tree which satisfies the restrictions and is ready for the next phase of the grammar. The underlying linguistic model is that of Noam Chomsky, as presented in Aspects of the Theory of Syntax.

This paper is a survey and discussion of research work relevant to the task of constructing some kind of reasoning robot. The emphasis is entirely on the organization of the reasoning processes, in particular planning, rather than on hardware. In practice the reasoning would most probably be carried out within a digital computer. My objective is to clarify the relationship between some superficially rather disparate approaches to this task, and simultaneously to indicate what seem to be the key problem areas. No new experimental results are presented, but the approach to the subject which I have adopted is a consequence of earlier experimentation with a simple computer simulation of a robot (Doran 1968a, 1969).

A minimal:robot,Icnown as Freddy, has been constructed with the aim of connecting a usable device online to the Department's lc L 4130, under the Multi-Pop time-sharing system, and discovering the snags. (See figure 1). Various technical problems arise when such a device runs free. It is much easier to anchor it and allow it to push its world about. Our present world is a three-foot diameter sandwich of hardboard and polystyrene which is light and rigid.

Computer Science Department, Stanford University (1969). Ph.D. dissertation

Machine Intelligence 5. B. Meltzer & D. Michie (eds.), 78-98. Edinburgh: Edinburgh University Press.

A computer program capable of acting intelligently in the world must have a general representation of the world in terms of which its inputs are interpreted. Designing such a program requires commitments about what knowledge is and how it is obtained. Thus, some of the major traditional problems of philosophy arise in artificial intelligence. More specifically, we want a computer program that decides what to do by inferring in a formal language that a certain strategy will achieve its assigned goal. This requires formalizing concepts of causality, ability, and knowledge. Such formalisms are also considered in philosophical logic. The first part of the paper begins with a philosophical point of view that seems to arise naturally once we take seriously the idea of actually making an intelligent machine.