Whether or not a computer might actually be intelligent, it can certainly put up a good show. In the more relaxed years following World War II people on both sides of the Atlantic borrowed time on the new computing machines to try out their unconventional ideas. One of the earliest areas of interest was chess playing programs (chess being a game that clearly demands intelligence, yet is easy to describe in symbolic terms), and early in the 1950s a number of chess playing programs were devised (including one by the ubiquitous Alan Turing). In 1955 Alan Newell, J. C. Shaw, and H. A. Simon at the Systems Research Laboratory of the RAND Corporation (in breaks from writing an Air Defense radar simulator) turned their attention to producing a theorem-proving program, called the `Logic Theorist', for mathematical logic. The idea was to take logic theorems (from the standard book on predicate logic by Russell and Whitehead) and prove that they could be deduced either from five basic axioms or from previously proven theorems.
Theorem proving is pretty mundane work for mathematicians, but was a great leap forward for computers. Until then, computer programs had had the form of algorithms: step-by-step instructions on how to reach the solution to a problem. Here is an algorithm (adapted from British Telecom's instructions on how to use a Phonecard):
The algorithm is not foolproof -- the phone may be vandalized, or the card may be torn -- but it is guaranteed to find a solution (let you make a phone call) if a solution exists.
To make the call, you, the caller, must follow the instructions and perform the actions; with an algorithm in the form of a computer program, that task is carried out by the computer. The following line is an algorithm to draw a square written in the computer language Logo:
repeat 4 [forward 100 right 90]
When this is typed to a computer running Logo, a blip of light on the screen moves forward 100 units; it then changes direction by 90 degrees and so on four times. The computer directly interprets the algorithm. (Just how the computer interprets the instructions of a program is a long story. In brief, the instructions are converted automatically into a longer list of primitive instructions which correspond to actions that the computer hardware can carry out.) What Newell, Shaw, and Simon invented was the notion of a programmable heuristic. A heuristic corresponds roughly to a `rule of thumb'. It may help in solving a problem but, unlike an algorithm, it is not guaranteed to find a solution. Newell, Shaw, and Simon defined `heuristic' thus: ``A process that may solve a given problem, but offers no guarantee of doing so, is called a `heuristic' for that problem'' (Newell, Shaw, and Simon, 1963b). (Since then, the term has been used in other ways -- for instance, to describe methods that improve the efficiency of algorithms by making use of specific facts about the problem domain.) Below is an example of a heuristic, from an incident that happened to one of the authors.
I used to go skiing at Glenshee in Scotland, a resort notorious for its sudden changes in weather. Just as I reached the top of a ski tow mist suddenly descended and the wind blew up to an icy gale. I could not see more than five feet ahead. A small group of us skied gingerly away from the tow and then when the wind became too strong, took of our skis and walked.After about 20 minutes trying to find the ski run we realized that we were hopelessly lost. We flung off our characteristic British reserve and argued furiously about where to go. At this point an exparatrooper took command. ``What we have to do,'' he said ``is to turn round and walk back along the contour line of the hill, not going up or down. Providing we are below the top of the ski-tow, we will eventually get back to it.''
Now this is a perfectly rigorous specification for action. If we had been carrying altimeters, we could have written a set of instructions of the form
But the instructions are not guaranteed to find a solution to the problem.
[IMAGE ]
Figure 1.2: A situation in which the `contour' heuristic fails.
Suppose we had been in the situation shown in figure 1.2. In that case, following the contour line from the decision point would just have led the party round in circles on hill B and they would never have reached the tow.
Although a heuristic does not guarantee a solution, it is a powerful computational tool. Knowledge of the problem domain (in this case the knowledge that the ski tow should cross the contour line at some point around the hill) can make all the difference in finding a practical solution to a problem: the strategy was successful and the party soon found the ski tow (a domain general solution to the problem would have been to fan out in every direction, searching in wider and wider circles; some of the party would certainly have collapsed from exhaustion before they could reach civilization!).
In the case of the Logic Theorist a domain general algorithm would start with the five basic axioms and would work by applying the rules of deduction in turn to generate more and more possible theorems, until it happened to come up with one that was in Russell and Whitehead's book. To prove 50 theorems by this method would take a modern computer billions of years. But using heuristics to guide the generation, the Logic Theorist managed to find 38 of the first 52 proofs in the book in a few hours of computer time.
The success of the Logic Theorist attracted the attention of other mathematicians and computer scientists, and in 1956 the term artificial intelligence was coined when John McCarthy organized a ``two month ten-man study of artificial intelligence'' at Dartmouth College, New Hampshire. Among the participants were Newell and Simon, and Marvin Minsky from Massachusetts Institute of Technology, who was to be one of the leading proponents of AI during the next decade.
In the 1960s general problem solving methods, supplemented by domain specific heuristics, were applied to a wide range of problems, and AI gradually separated out into the application areas of language understanding and generation, game playing, theorem proving, vision, and robotics. With a few exceptions (such as Newell and Simon's monumental work Human Problem Solving, 1972) there was little attempt to construct programs that accurately modelled the human mind; the emphasis was on performance -- computer systems that acted in intelligent ways by, for instance, playing chess or solving mathematical problems. The general approach was one of successive refinement: start with a method that approximates the desired action (e.g., a program that plays chess badly, or solves puzzles in a large number of steps) and then refine it until it behaves to the standard expected of an intelligent human.
To return again to computer-generated poetry: a first approximation might be to write a program that picked at random from a large list of words, taking a new line say every five words:
Crinoline it erase hostile delve
Gourd transit self low care
Ton oyster irrigate fly coriander
Clearly this will not do. We need a method of forming the words into an orderly pattern. So, the next step in the refinement process might be to group the words according to part of speech, collecting together:
nouns: aardvark, abacus, abalone, ..., zebra
verbs: abandon, abase, abate, ..., zoom
and so on. By specifying an appropriate pattern of parts of speech, such as
adverb article adjective noun verb
preposition adjective adjective noun
we could instruct the computer to generate words in a better order:
Elegantly a patient seed flush
Over inarticulate translucent demon
The next refinement would be to ensure that the words agreed in number (i.e., singular or plural) and tense (past, present, future). The stage after that would be to add a list of `meaning tags' to each word:
WORD PART OF SPEECH MEANING TAGS
rock noun inanimate, still, groundbird noun animal, moving, air
snowflake noun inanimate, moving, air
and rewrite the program so that it chooses words with similar meaning tags. This is the method used to generate the poem shown earlier, in section 1.3. But here we come to a dead halt. Human poets do not merely pour out words to fixed patterns, matched for meaning; they call on experience of past events, their emotions, and knowledge of how the world is organized.
Since 1970 there have been major advances in AI: in the design of prototype programs such as Winograd's SHRDLU (described in chapter 3); in the application of AI to commerce and industry through expert systems which can perform some of the tasks of a human expert in, for example, diagnosing diseases or identifying mineral deposits (but without the extensive background knowledge of a true human expert); and in the design of new programming languages and computers to help the AI programmer. But to progress further towards the goal of intelligent systems, AI researchers now need to understand more about the workings of the human mind. How to represent commonsense knowledge, experience, emotion and senses in a symbolic form that can be manipulated by computer is one of the main themes of present-day research in artificial intelligence and a major topic of this book.
![[IMAGE ]](img5.gif){kind=link}