A general game-playing program must know the rules of the particular playing game. These rules are:(1) an algorithm indicating the winning state;(2) an algorithm enumerating legal moves. A move gives a set of changes from the present situation.There are two means of giving these rules:(1) We can write a subroutine which recognizes if we have won and another which enumerates legal moves. Such a subroutine is a black box giving to the calling program the answer: 'you win' or 'you do not win', or the list of legal moves. But it cannot know what is in that subroutine.(2) We can also define a language in which we describe the rules of a game. The program investigates the rules written with this language and finds some indications to improve its play. Artificial Intelligence and Heuristic Programming Edinburgh University Press

Machine Intelligence 6

Inference systems Τ and search strategies E for T are distinguished from proof procedures β = (T,E) The completeness of procedures is studied by studying separately the completeness of inference systems and of search strategies. Completeness proofs for resolution systems are obtained by the construction of semantic trees. These systems include minimal α-restricted binary resolution, minimal α-restricted M-clash resolution and maximal pseudo-clash resolution. Certain refinements of hyper-resolution systems with equality axioms are shown to be complete and equivalent to refinements of the pararmodulation method for dealing with equality. The completeness and efficiency of search strategies for theorem-proving problems is studied in sufficient generality to include the case of search strategies for path-search problems in graphs. The notion of theorem-proving problem is defined abstractly so as to be dual to that of and" or tree. Special attention is given to resolution problems and to search strategies which generate simpler before more complex proofs. For efficiency, a proof procedure (T,E) requires an efficient search strategy E as well as an inference system T which admits both simple proofs and relatively few redundant and irrelevant derivations. The theory of efficient proof procedures outlined here is applied to proving the increased efficiency of the usual method for deleting tautologies and subsumed clauses. Counter-examples are exhibited for both the completeness and efficiency of alternative methods for deleting subsumed clauses. The efficiency of resolution procedures is improved by replacing the single operation of resolving a clash by the two operations of generating factors of clauses and of resolving a clash of factors. Several factoring methods are investigated for completeness. Of these the m-factoring method is shown to be always more efficient than the Wos-Robinson method. The University of Edinburgh

This paper describes an effort to design a heuristic problem-solving program which accepts problems stated in a nondeterministic programming language and applies constraint satisfaction methods and heuristic search methods to find solutions. The use of nondeterministic programming languages for stating problems is discussed, and ref, the language accepted by the problem solver arf, is described. Various extensions to ref are considered. The conceptual structure of the program is described in detail and various possibilities for extending it are discussed. The use of the input language and the behaviour of the program are described and analyzed in sixteen sample problems.

The game of Go invites analysis. The rules seem few and simple, suggesting that the game may have helpful theorems. Tens of millions of people play and skill has developed over centuries to extraordinary levels. Thus, computer analysis can be tested against analysis by highly skilled human players. We study M × N boards, rather than the usual 19 × 19.

This paper investigates the problem of implementing machine learning of heuristics. First, a method of representing heuristics as production rules is developed which facilitates dynamic manipulation of the heuristics by the program embodying them. Second, procedures are developed which permit a problem-solving program employing heuristics in production rule form to learn to improve its performance by evaluating and modifying existing heuristics and hypothesizing new ones, either during an explicit training process or during normal program operation. Third, the feasibility of these ideas in a complex problem-solving situation is demonstrated by using them in a program to make the bet decision in draw poker. Finally, problems which merit further investigation are discussed, including the problem of defining the task environment and the problem of adapting the system to board games.

Full text available for a fee. The main purpose of the research reported here is to show that a new and more powerful type of computer-assisted instruction (CAI), based on extensive application of artificial-intelligence (AI) techniques, is feasible, and to demonstrate some of its major capabilities. A set of computer programs was written and given the name SCHOLAR. Due to its complexity, only the conception and educational aspects of this system (including an actual on-line protocol) are presented in this paper. IEEE Transactions on Man-Machine Systems MMS-ll:190-202

Full text available for a fee. "The use of augmented transition network grammars for the analysis of natural language sentences is described. Structure-building actions associated with the arcs of the grammar network allow for the reordering, restructuring, and copying of constituents necessary to produce deep-structure representations of the type normally obtained from a transformational analysis, and conditions on the arcs allow for a powerful selectivity which can rule out meaningless analyses and take advantage of semantic information to guide the parsing. The advantages of this model for natural language analysis are discussed in detail and illustrated by examples. An implementation of an experimental parsing system for transition network grammars is briefly described." Communications of the ACM, Vol. 13, No. 10, October, 1970, pp. 591-606 (reprinted in RNLP: 71-88).

The M & N procedure is an improvement to the mini-max backing-up procedure widely used in computer programs for game-playing and other purposes. It is based on the principle that it is desirable to have many options when making decisions in the face of uncertainty. The mini-max procedure assigns to a MAX (MIN) node the value of the highest (lowest) valued successor to that node. The M & N procedure assigns to a MAX (MIN) node some function of the M (N) highest (lowest) valued successors. An M & N procedure was written in LISP to play the game of kalah, and it was demonstrated that the M & N procedure is significantly superior to the mini-max procedure.

A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR(k) algorithm and the familiar top-down algorithm. It has a time bound proportional to n3 (where n is the length of the string being parsed) in general; it has an n2 bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars. In an empirical comparison it appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.