INTRODUCTION 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. Sandewall (1967) has gone deeply into an automaton/environment relationship with a rather more formal approach. This list is far from complete. In particular, robots of various kinds are under construction at a number of research centres, notably at the Stanford Research Institute (Nilsson and Raphael, 1967). The reader may find it helpful to meditate on the situation of, say, a rat in a cage, as seen by the rat.

The general problem of re-Presentation is concerned with the relationship between different ways of formulating a problem to a problem solving system and the efficiency with which the system can be expected to find a solution to the problem. An understanding of the relationship between problem formulation and problem solving efficiency is a prerequisite for the design of procedures that can automatically choose the most appropriate' representation of a problem (they can find a point of view' of the problem that maximally simplifies the process of finding a solution). Many problems of practical importance are problems of reasoning about actions. In these problems, a course of action has to be found that satisfies a number of specified conditions. A formal definition of this class of problems is given in the next section, in the context of a general conceptual framework for formulating these problems for computers. Everyday examples of reasoning about actions include planning an airplane trip, organizing a dinner party, etc. There are many examples of industrial and military problems in this category, such as scheduling assembly and transportation processes, designing a program for a computer, planning a military operation, etc. The research presented in this paper was sponsored in part by the Air Force Office of Scientific Research, under Contract Number A F49(638)-1184. Part of this work was done while the author was on a visiting appointment at the Computer Science Department of the Carnegie Institute of Technology, Pittsburgh, Pa.

The original intention was to demonstrate the on-line typewriter to visitors via a simple system which reacted to the user, in this case by refusing to be beaten twice in the same way at the game of Kalah. The mechanism to achieve this is a memory, built up from information obtained in previous games, which is stored on magnetic tape. The program was designed to keep the size of this memory to small proportions by implementing two mechanisms the author believes to be commonly used by humans when solving problems. The two mechanisms are: 1. ignoring irrelevant information in the sense that, although it exists, it is highly probable that its precise structure or properties cannot alter the relevant information or characteristics of the problem being considered, and 2. accepting positions close to a solution or win, providing the opponent is further from a win. Some of the difficulties of testing these ideas in practice are discussed and suggestions are made on how to overcome them, in particular with the game of solo whist.

Networks as models of word storage: G. R. Kiss

Networks as models of word storage: G. R. Kiss

'For the last few weeks, the "Fifteen-puzzle" has been prominently before the American Public, and may safely be said to have engaged the attention of nine out of ten persons of both sexes and of all ages and conditions of the community.' The Tight-puzzle' is a reduced form of the'Fifteen-puzzle', the subject of the somewhat extravagant claim quoted above. Its use in the study of learning processes, both human and programmed, is described in two other papers in this volume, Michie (p. This paper describes the calculation of optimum solutions to all the 20 160 possible versions of the puzzle. The'Eight-puzzle' consists of eight square pieces, numbered 0-7,f capable of sliding in a shallow square tray of size nine times that of the individual pieces: there is thus one empty square.

I shall discuss automatic methods of search for solutions in problems susceptible of a particular formal representation, namely that on which the Graph Traverser program (Doran & Michie 1966, and see Doran p. 105) has been based. In this representation which is essentially that of Newell, Shaw & Simon (1960) a problem consists of a set of states, one or more of which is labelled'goal', together with a rule-book. The rule-book lays down for each state what moves may be made from it to reach other, neighbouring, states. Solution consists in a demonstration that a goal state can be reached from some given initial state via a sequence of intermediate states, sometimes with the additional requirement that an actual sequence, or path, be demonstrated as part of the solution; in this last case, as in the sliding block problem discussed later, the goal (or goals) is typically specified in full as part of the statement of the problem. In other cases, where the goal is only specified in terms of some defining property (such as cost in a transportation problem, or simplicity in a problem of algebraic manipulation) we are interested solely in discovering states possessing this property, and not at all interested in the particular paths leading to them.

A digital computer program, the Graph Traverser (Doran & Michie 1966), can seek a solution to any problem which may be interpreted as that of finding a path from one specified node of a graph to another. Emphasis is placed Upon the evaluation of intermediate states of the problem (nodes of the graph) according to the extent to which they resemble the'goal' state. Sample results from first applications of the program, and possible future developments, are discussed. The program is related to other problemsolving programs. INTRODUCTION: PROBLEMS AND PROBLEM-SOLVING PROGRAMS How to travel from London to Birmingham may, in some circumstances, be a'problem'.

INTRODUCTION This paper is a report on some preliminary work undertaken as part of a longer term study of the problems which arise in designing and implementing digital computer programs which'learn'. A program has been written which learns to play the board game'Go-Moku' using a particular learning mechanism to be described later. The program is to be regarded as an experimental tool by means of which the particular learning mechanism can be investigated in some depth. Go-Moku is a simple but not a trivial game with an intellectual content comparable with a game of draughts (checkers). Opinions have sometimes been expressed that there is nothing to be learnt (no pun intended!) by programming simple games. Present knowledge of programming learning is such that it is useful to experiment with programs operating in a simple task environment. It is not so much what game the program learns as how it learns it. It is emphasised that the object of the present work is not to write a program which plays a difficult game better than anyone or anything has played it before, but to isolate and investigate particular aspects of a learning process which might be valid over a range of ill-structured problems. For the record, however, the current learning programs learn to play a good (basically defensive) game. The modifications currently being made to the program should give it a learning capacity to become unbeatable.

SEARCH TREES We will talk about problems with the following characteristics: (i) We could recognise a solution to the problem if given one. Let us call the set of objects which is known to contain the solutions the'candidates'. We include cases where there is more than one solution or where an optimal solution is required. Some examples are: (i) In playing chess there are only a finite number of possible strategies (candidates) but the number is far too large to enumerate. Any assignment is a candidate and there are a finite, but usually large, number of assignments. The candidates are the (n -- I)! permutations of the points omitting the starting point. In this section we will describe in an abstract way two approaches to problems of this type. We will give examples of their use, first in'Some problems about sets' (p. Although both the approaches have often been used before, the discussion may help to clarify those features common to the different applications. Our two approaches are both search techniques (partial enumeration techniques).