The work on automatic chess therefore started when men, such as the musician-chess player Philidor (1749), formulated general principles of play. Then the decision of whether to regard that position, 7r, as an endpoint, when analysing a position, no, depends on the following considerations: (a) The depth (i.e., the number of moves ahead) of the position From the point of view of strict logic, chess is a game of pure skill, but it is a physical impossibility to avoid some degree of chance. Closely allied to the problem of selecting endpoints on an analysis tree, is the selection of which moves to discard without analysis. This problem is discussed in Appendix H. Hence, from the point of view of the Borel-von Neumann theory of games, chess is'trivial' (see Appendix A).
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. Toda (1962), in a whimsical and illuminating paper, has discussed the problems facing an automaton in a simple artificial environment. The reader may find it illuminating to imagine himself (the automaton) before a screen on which is displayed a complex pattern which changes from time to time (sequence of states). These are: 1. the subjective environment graph (figure 1), 2. the stored graph which is that portion of the subjective environment graph which the automaton has stored in its memory as a result of its experience (figure 2 (b)), and 3. the option graph which is that fragment of the stored graph which the automaton'knows' how to reach (figure 2(c)).
In brief, we believe that programs for learning large games will need to have at their disposal good rules for learning small games. Each separate box functions as a separate learning machine: it is only brought into play when the corresponding board position arises, and its sole task is to arrive at a good choice of move for that specific position. The demon's task is to make his choices in successive plays in such a way as to maximise his expected number of wins over some specified period. By a development of Laplace's Law of Succession we can determine the probability, This defines the score associated with the node N. To make a move the automaton examines all the legal alternatives and chooses the move leading to the position having the highest associated score, ties being decided by a random choice.
Before discussing in detail an example of a simple heuristic problemsolving program, the Graph Traverser, I shall give an indication of the most important work carried out in this field, stressing the more fundamental ideas. Bobrow (1964) describes a question-answering system for high school algebra word problems'. I shall distinguish four: (1) the external application problem to which the program has been applied; (2) the internal problem which the program generates from the application problem and which it must solve in order to produce a solution to the application problem (this internal problem will be an'idealised' version of the application problem, and will typically vary little from one application to another. It is important to realise that more than one internal problem may be capable of derivation from a given application problem); (3) the strategy which the program uses to solve the internal problem; (4) the translation process from the application problem to the internal problem.
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. One approach, based on state-evaluation, generates all the states of the problem which can be reached in a small number of moves from the current state, and then seeks by some process of evaluation to decide which state shall form the next point of departure. In the classical studies of Newell, Shaw & Simon (1960) selection is applied by going down a priority sequence of operators, applying to each in turn a number of tests, first of applicability to the current state and then of whether the operator conduces towards one or another of various desirable intermediate states, or subgoals.