Results


Using Patterns and Plans in Chess

Classics (Collection 2)

The purpose of this research is to investigate the extent to which knowledge can replace and support search in selecting a chess move and to delineate the issues involved. This has been carried out by constructing a program. PARADISE (PArtern Recognition Applied to Directing SEarch), which finds the best move in tactically sharp middle game positions from the games of chess masters. The actions of the rules post concepts in the data base while the conditions match patterns in the chess position and data base. The program uses the knowledge base to discover plans during static analysis and to guide a small tree search which confirms that a particular plan is best.


Prolegomena to a Theory of Mechanized Formal Reasoning

Classics (Collection 2)

This is an informal description of my ideas about using formal logic as a tool for reasoning systems using computers. Introduction The title of this paper contains both the words'mechanized' and'theory'. I want to make the point that the ideas presented here are not only of interest to theoreticians. I believe that any theory of interest to artificial intelligence must be realizable on a computer. I will not present difficult examples.


Achieving Several Goals Simultaneously

Classics (Collection 2)

In the synthesis of a plan or computer program, the problem of achieving several goals simultaneously presents special difficulties, since a plan to achieve one goal may interfere with attaining the others. This paper develops the following strategy: to achieve two goals simultaneously, develop a plan to achieve one of them and then modify that plan to achieve the second as well. A systematic program modification technique is presented to support this strategy. The technique requires the introduction of a special "skeleton model" to represent a changing world that can accommodate modifications in the plan. This skeleton model also provides a novel approach to the "frame problem."


Planning and Meta-Planning (MOLGEN: Part 2)

Classics (Collection 2)

The selection of what to do next is often the hardest part of resource-limited problem solving. In planning problems, there are typically many goals to be achieved in some order. The goals interact with each other in ways which depend both on the order in which they are achieved and on the particular operators which are used to achieve them. A planning program needs to keep its options open because decisions about one part of a plan are likely to have consequences for another part. This paper describes an approach to planning which integrates and extends two strategies termed the least-commitment and the heuristic strategies.


CONSULTATION SYSTEMS / 323

Classics (Collection 2)

ABSTRACT Computer systems for use by physicians have had limited impact on clinical medicine. When one examines the most common reasons for poor acceptance of medical computing systems, the potential relevance of artificial intelligence techniques becomes evident. This paper proposes design criteria for clinical computing systems and demonstrates their relationship to current research in knowledge engineering. The MYCIN System is used to illustrate the ways in which our research group has attempted to respond to the design criteria cited. My goal is to present design criteria which may encourage the use of computer programs by physicians, and to show that Al offers some particularly pertinent methods for responding to the design criteria outlined.


Generalization as Search

Classics (Collection 2)

We learn (memorize) multiplication tables, learn (discover how) to walk, learn (build UP an understanding of, then an ability to synthesize) languages. Many subtasks and capabilities are involved in these various kinds of learning. One capability central to many kinds of learning is the ability to generalize: to take into account a large number of specific observations, then to extract and retain the important common features that characterize classes of these observations. This generalization problem has received considerable attention for two decades in the fields of Artificial Intelligence, Psychology, and Pattern Recognition (e.g., [Bruner, The results so far have been tantalizing: Partially successful generalization programs have been written for problems ranging from learning fragments of spoken English to learning rules of Chemical spectroscopy. But comparing alternative strategies, and developing a general understanding of techniques has been difficult because of differences in data representations, terminology, and problem characteristics.


EPISTEMOLOGICAL PROBLEMS OF Al / 459

Classics (Collection 2)

EPISTEMOLOGICAL PROBLEMS OF ARTIFICIAL INTELLIGENCE John McCarthy Computer Science Department Stanford University Stanford, California 94305 Introduction In (McCarthy and Hayes 1969), we proposed dividing the artificial intelligence problem into two parts - an epistemological part and a heuristic part. This lecture further explains this division, explains some of the epistemological problems, and presents some new results and approaches. The epistemological part of Al studies what kinds of facts about the world are available to an observer with given Opportunities to observe, how these facts can be represented in the memory of a computer, and what rules permit legitimate conclusions to be drawn from these facts. It leaves aside the heuristic problems of how to search spaces of possibilities and how to match patterns. Considering epistemological problems separately has the following advantages: I. The same problems of what information is available to an observer and what conclusions ...


PROGRAM SYNTHESIS / 141

Classics (Collection 2)

Program synthesis is the systematic derivation of a program from a given specification. A deductive approach to program synthesis is presented for the construction of recursive programs. This approach regards program synthesis as a theorem-proving task and relies on a theorem-proving method that combines the features of transformation rules, unification, and mathematical induction within a single framework. MOTIVATION The early work in program synthesis relied strongly on mechanical theoremproving techniques. More recently, program synthesis and theorem proving have tended to go their separate ways.


202 / PROBLEM-SOLVING AND PLANNING

Classics (Collection 2)

APPLICATION OF THEOREM PROVING TO PROBLEM SOLVING *t Cordell Green Stanford Research Institute Menlo Park, California Abstract This paper shows how an extension of the resolution proof procedure can be used to construct problem solutions. The extended proof procedure can solve problems involving state transformations. The paper explores several alternate problem representations and provides a discussion of solutions to sample problems including the "Monkey and Bananas" puzzle and the "Tower of Hanoi" puzzle. The paper exhibits solutions to these problems obtained by QA3, a computer program based on these theorem-proving methods. In addition, the paper shows how QA3 can write simple computer programs and can solve practical problems for a simple robot.


DEVISING HEURISTICS / 23 A PROBLEM SIMILARITY APPROACH TO DEVISING HEURISTICS: FIRST RESULTS

Classics (Collection 2)

John Gaschnig Department of Computer Science Carnegie-Mellon University Pittsburgh, PA 15213 Abstract Here we describe an approach, based upon a notion of problem similarity, that can be used when attempting to devise a heuristic for a given search problem (of a sort represented by graphs). The next step is to find an algorithm for finding paths in P2, then apply this algorithm in a certain way as a heuristic for P1. Using the As algorithm, we experimentally compare the performance of this "maxsort" heuristic for the 8-puzzle with others in the literature. Many combinatorially large problems cannot be solved feasibly by exhaustive case analysis or brute force search, but can be solved efficiently if a heuristic can be devised to guide the search. Research to date on devising heuristics has spanned several problem-solving domains and several approaches.