Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Structured Semantic Representation of the QuestionSlide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29What Is an AI Technique? Artificial intelligence problems span a very broad spectrum. They appear to have verylittle in common except that they are hard. Are there any techniques that are appropriatefor the solution of a variety of these problems? The answer to this question is yes, thereare. What, then, if anything, can we say about those techniques besides the fact that theymanipulate symbols? How could we tell if those techniques might be useful in solvingother problems, perhaps ones not traditionally regarded as Al tasks? The rest of thisbook is an attempt to answer those questions in detail. But before we begin examiningclosely the individual techniques, it is enlightening to take a broad look at them to seewhat properties they ought to possess. One of the few hard and fast results to come out of the first three decades of AIresearch is that intelligence requires knowledge. To compensate for its one overpowering asset, indispensability, knowledge possesses some less desirable properties, including:• It is voluminous.• It is hard to characterize accurately.• It is constantly changing.• It differs from data by being organized in a way that corresponds to the ways it will be used.So where does this leave us in our attempt to define Al techniques? We are forcedto conclude that an AI technique is a method that exploits knowledge that should berepresented in such a way that:• The knowledge captures generalizations. In other words, it is not necessary to represent separately each individual situation . Instead , situations that share important properties are grouped together. If knowledge does not have this property, inordinate amounts of memory and updating will be required. So we usually call something without this property "data" rather than knowledge.• It can be understood by people who must provide it. Although for many programs, the bulk of the data can be acquired automatically (for example, by taking readings from a variety of instruments), in many AI domains, most of the knowledge a program has must ultimately be provided by people in terms they understand.• It can easily be modified to correct errors and to reflect changes in the world and in our world view.• It can be used in a great many situations even if it is not totally accurate or complete.• It can be used to help overcome its own sheer bulk by helping to narrow the range of possibilities that must usually be considered. Although AI techniques must be designed in keeping with these constraints imposedby AI problems, there is some degree of independence between problems and problem-solvingtechniques. It is possible to solve AI problems without using AI techniques (although, as we suggested above, those solutions are not likely to be very good).And it is possible to apply AI techniques to the solution of non-AI problems. This is likely tobe a good thing to do for problems that possess many of the same characteristics as doAI problems. In order to try to characterize AI techniques in as problem-independent away as possible, let's look at two very different problems and a series of approaches forsolving each of them.Tic-Tac-ToeIn this section , we present a series of three programs to play tic-tac-toe. The programsin this series increase in: • Their complexity • Their use of generalizations • The clarity of their knowledge • The extensibility of their approachThus they move toward being representations of what we call Al techniques.Program 1Data StructuresBoard A nine-element vector representing the board, where the elements of the vector correspond to the board positions as follows: 1 2 3 4 5 6 7 8 9An element contains the value 0 if the corresponding square is blank,I if it is filled with an X, or 2 if it is filled with an O.Movetable A large vector of 19,683 elements (3 raise to the power 9), each element of which is a nine-element vector. The contents of this vector are chosenspecifically to allow the algorithm to workThe AlgorithmTo make a move, do the following:I. View the vector Board as a ternary (base three) number. Convert it to a decimalnumber.2. Use the number computed in step I as an index into Movetable and access thevector stored there.3. The vector selected in step 2 represents the way the board will look after the movethat should be made. So set Board equal to that vector.CommentsThis program is very efficient in terms of time. And, in theory, it could play an optimalgame of tic-tac-toe. But it has several disadvantages: • It takes a lot of space to store the table that specifies the correct move to make from each board position. • Someone will have to do a lot of work specifying all the entries in the Movetable. • It is very unlikely that all the required Movetable entries can be determined and entered without any errors.• If we want to extend the game, say to three dimensions, we would have to start from scratch, and in fact this technique would no longer work at all, since (3 raise to the power of 27) board positions would have to be stored, thus overwhelming present computer memories.The technique embodied in this program does not appear to meet any of our requirementsfor a good AI technique. Let's see if we can do better.Program 2Data StructuresBoard A nine-element vector representing the board, as described for ProgramI . But instead of using the numbers 0, I , or 2 in each element,we store 2 (indicating blank), 3 (indicating X), or 5 (indicating O).Turn An integer indicating which move of the game is about to be played;1 indicates the first move, 9 the last.The AlgorithmThe main algorithm uses three subprocedures:Make2 Returns 5 if the center square of the board is blank, that is, if Board[5]= 2. Otherwise, this function returns any blank no corner square( 2, 4, 6, or 8).Posswin(p) Returns 0 if player p cannot win on his next move; otherwise, itreturns the number of the square that constitutes a winning move.This function will enable the program both to win and to block theopponent's win. Posswin operates by checking, one at a time, eachof the rows, columns, and diagonals. Because