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).

The author's main source was from personal discussion.)

In the'condition omitted' column: denotes that the full complement of heuristic devices was in use denotes that the coefficient of the feature L was set to zero denotes that the coefficient of the feature B was set to zero de,notes that the coefficient of the feature E was set to zero denotes that the coefficient of the feature T was set to zero PD denotes that all neighbours of a node were produced at one development M denotes that the example group was not in use 44 POPPLESTONE F denotes that the equality was proved in reverse, i.e., that the RHS was converted into the LHS. Note that the LHS is longer than the RHS in every problem where the lengths are different. In the'result' column: S denotes that the problem was solved F denotes that the problem was unsolved after 100 distinct nodes had been produced - FF denotes that the problem was unsolved after 100 distinct nodes had been produced but that the problem was solved after restarting one or more times from the most promising node produced so far (see Doran's paper in this volume). FL denotes that the problem was unsolved because a term too large to hold in the array assigned to hold it was produced. The nodes listed' column gives the total number of distinct nodes produced.

RELATION TO PHYSIOLOGY It is possible to compare the organisation of this system with the organisation of the visual system, as revealed by microelectrode studies in the cat (Hubel & Wiesel 1962, 1965) and the frog (Lettvin, Maturana, McCulloch & Pitts 1959). Briefly the following points emerge: (1) Cells in the visual cortex only respond to local properties of the visual scene, e.g., edges, line segments. This mirrors the immediate constituent constraint imposed for economic reasons in the picture grammar.

Psychological theory attempts to explain how thinking--the subject matter of psychology--is possible by a brain composed of single mechanistic elements--the basic assumption of psychology. The problem of programming digital computers to behave in complex fashions is equivalent to this aspect of the psychological problem. Today automata theorists agree that no fundamental barrier blocks the development of machines which can think, by any reasonable definition of the term. However, the precise techniques for implementing general thinking proceGseE-J have been only partially developed. An example of a high-level, general thinking process is comprehension: the understanding of passages of a natural language.