Artificial Intelligence Illuminated

Artificial IntelligenceIlluminatedBen CoppinJONES AND BARTLETT PUBLISHERS

World HeadquartersJones and Bartlett Publishers40 Tall Pine DriveSudbury, MA 01776978-443-5000info@jbpub.comwww.jbpub.comJones and Bartlett PublishersCanada2406 Nikanna RoadMississauga, ON L5C 2W6CANADAJones and Bartlett PublishersInternationalBarb House, Barb MewsLondon W6 7PAUKCopyright 2004 by Jones and Bartlett Publishers, Inc.Cover image PhotodiscLibrary of Congress Cataloging-in-Publication DataCoppin, Ben.Artificial intelligence illuminated / by Ben Coppin.--1st ed.p. cm.Includes bibliographical references and index.ISBN 0-7637-3230-31. Artificial intelligence. I. Title.Q335.C586 2004006.3--dc2220030206043382All rights reserved. No part of the material protected by this copyright notice may bereproduced or utilized in any form, electronic or mechanical, including photocopying,recording, or any information storage or retrieval system, without written permissionfrom the copyright owner.Acquisitions Editor: Stephen SolomonProduction Manager: Amy RoseMarketing Manager: Matthew BennettEditorial Assistant: Caroline SenayManufacturing Buyer: Therese BräuerCover Design: Kristin E. OhlinText Design: Kristin E. OhlinComposition: Northeast CompositorsTechnical Artist: George NicholsPrinting and Binding: Malloy, Inc.Cover Printing: Malloy, Inc.Printed in the United States of America08 07 06 05 0410 9 8 7 6 5 4 3 2 1

For Erin

This page intentionally left blank

PrefaceWho Should Read This BookThis book is intended for students of computer science at the college level,or students of other subjects that cover Artificial Intelligence. It also isintended to be an interesting and relevant introduction to the subject forother students or individuals who simply have an interest in the subject.The book assumes very little knowledge of computer science, but doesassume some familiarity with basic concepts of algorithms and computersystems. Data structures such as trees, graphs, and stacks are explainedbriefly in this book, but if you do not already have some familiarity withthese concepts, you should probably seek out a suitable book on algorithmsor data structures.It would be an advantage to have some experience in a programming language such as C or Java, or one of the languages commonly used in Artificial Intelligence research, such as PROLOG and LISP, but this experienceis neither necessary nor assumed.Many of the chapters include practical exercises that require the reader todevelop an algorithm or program in a programming language of his or herchoice. Most readers should have no difficulty with these exercises. However, if any reader does not have the necessary skills he or she simply shoulddescribe in words (or in pseudocode) how his or her programs work, givingas much detail as possible.

viPrefaceHow to Read This BookThis book can be read in several ways. Some readers will choose to read thechapters through in order from Chapter 1 through Chapter 21. Any chapterthat uses material which is presented in another chapter gives a clear reference to that chapter, and readers following the book from start to finishshould not need to jump forward at any point, as the chapter dependenciestend to work in a forward direction.Another perfectly reasonable way to use this book is as a reference. When areader needs to know more about a particular subject, he or she can pick upthis book and select the appropriate chapter or chapters, and can be illuminated on the subject (at least, that is the author’s intent!)Chapter 12 contains a diagram that shows how the dependencies betweenchapters work (Section 12.6.2). This diagram shows, for example, that if areader wants to read Chapter 8, it would be a good idea to already have readChapter 7.This book is divided into six parts, each of which is further divided into anumber of chapters. The chapters are laid out as follows:Part 1: Introduction to Artificial IntelligenceChapter 1: A Brief History of Artificial IntelligenceChapter 2: Uses and LimitationsChapter 3: Knowledge RepresentationPart 2: SearchChapter 4: Search MethodologiesChapter 5: Advanced SearchChapter 6: Game PlayingPart 3: LogicChapter 7: Propositional and Predicate LogicChapter 8: Inference and Resolution for Problem SolvingChapter 9: Rules and Expert Systems

PrefacePart 4: Machine LearningChapter 10: Introduction to Machine LearningChapter 11: Neural NetworksChapter 12: Probabilistic Reasoning and Bayesian Belief NetworksChapter 13: Artificial Life: Learning through Emergent BehaviorChapter 14: Genetic AlgorithmsPart 5: PlanningChapter 15: Introduction to PlanningChapter 16: Planning MethodsPart 6: Advanced TopicsChapter 17: Advanced Knowledge RepresentationChapter 18: Fuzzy ReasoningChapter 19: Intelligent AgentsChapter 20: Understanding LanguageChapter 21: Machine VisionEach chapter includes an introduction that explains what the chapter covers, a summary of the chapter, some exercises and review questions, andsome suggestions for further reading. There is a complete bibliography atthe back of the book.This book also has a glossary, which includes a brief definition of most ofthe important terms used in this book. When a new term is introduced inthe text it is highlighted in bold, and most of these words are included inthe glossary. The only such terms that are not included in the glossary arethe ones that are defined in the text, but that are not used elsewhere in thebook.The use of third person pronouns is always a contentious issue for authorsof text books, and this author has chosen to use he and she interchangeably.In some cases the word “he” is used, and in other cases “she.” This is notintended to follow any particular pattern, or to make any representationsabout the genders, but simply is in the interests of balance.vii

viiiPrefaceThe first few chapters of this book provide introductory material, explaining the nature of Artificial Intelligence and providing a historical background, as well as describing some of the connections with otherdisciplines. Some readers will prefer to skip these chapters, but it is advisable to at least glance through Chapter 3 to ensure that you are familiarwith the concepts of that chapter, as they are vital to the understanding ofmost of the rest of the book.AcknowledgmentsAlthough I wrote this book single-handedly, it was not without help. Iwould like to thank, in chronological order, Frank Abelson; Neil Salkindand everyone at Studio B; Michael Stranz, Caroline Senay, StephenSolomon, and Tracey Chapman at Jones & Bartlett; also a number of people who read chapters of the book: Martin Charlesworth, Patrick Coyle,Peter and Petra Farrell, Robert Kealey, Geoffrey Price, Nick Pycraft, ChrisSwannack, Edwin Young, my parents, Tony and Frances, and of courseErin—better late than never.Thanks also to:The MIT Press for the excerpt from ‘Learning in Multiagent Systems’ bySandip Sen and Gerhard Weiss, 2001, The MIT Press.The MIT Press for the excerpt from ‘Adaptation in Natural and ArtificialSystems’ by John H. Holland, 1992, The MIT Press.The MIT Press for the excerpt from ‘The Artificial Life Roots of ArtificialIntelligence’ by Luc Steels, 1994, the Massachusetts Institute of Technology.The IEEE for the excerpt from ‘Steps Towards Artificial Intelligence’ byMarvin Minsky, 2001, IEEE.I have attempted to contact the copyright holders of all copyrighted quotesused in this book. If I have used any quotes without permission, then thiswas inadvertent, and I apologize. I will take all measures possible to rectifythe situation in future printings of the book.

ContentsPrefacevPA R T 1Introduction to Artificial IntelligenceChapter 11.11.21.31.41.51.61.71.81.91.10A Brief History of Artificial IntelligenceIntroduction 3What Is Artificial Intelligence? 4Strong Methods and Weak Methods 5From Aristotle to Babbage 6Alan Turing and the 1950s 7The 1960s to the 1990s 9Philosophy 10Linguistics 11Human Psychology and Biology 12All Programming Languages 121.10.1 PROLOG 131.10.2 LISP 141.11 Chapter Summary 151.12 Review Questions 161.13 Further Reading 1713

xContentsChapter 22.12.22.32.42.52.62.7Uses and Limitations 19Introduction 19The Chinese Room 20HAL—Fantasy or Reality? 21AI in the 21st Century 23Chapter Summary 24Review Questions 24Further Reading 25Chapter 33.13.23.33.43.5Knowledge Representation 27Introduction 27The Need for a Good Representation 28Semantic Nets 29Inheritance 31Frames 323.5.1 Why Are Frames Useful? 343.5.2 Inheritance 343.5.3 Slots as Frames 353.5.4 Multiple Inheritance 363.5.5 Procedures 373.5.6 Demons 383.5.7 Implementation 383.5.8 Combining Frames with Rules 403.5.9 Representational Adequacy 40Object-Oriented Programming 41Search Spaces 42Semantic Trees 44Search Trees 463.9.1 Example 1: Missionaries and Cannibals 473.9.2 Improving the Representation 493.9.3 Example 2: The Traveling Salesman 503.9.4 Example 3: The Towers of Hanoi 543.9.5 Example 4: Describe and Match 56Combinatorial Explosion 57Problem Reduction 573.63.73.83.93.103.11

Contents3.12 Goal Trees 583.12.1 Top Down or Bottom Up?3.12.2 Uses of Goal Trees 61Example 1: Map ColoringExample 2: Proving TheoremsExample 3: Parsing Sentences 63Example 4: Games3.13 Chapter Summary 643.14 Review Questions 653.15 Exercises 653.16 Further Reading 66PA R T 2Chapter 44.14.24.34.44.54.64.74.84.94.104.114.1260Search 69Search Methodologies 71Introduction 71Problem Solving as Search 72Data-Driven or Goal-Driven Search 73Generate and Test 74Depth-First Search 75Breadth-First Search 76Properties of Search Methods 784.7.1 Complexity 784.7.2 Completeness 794.7.3 Optimality 794.7.4 Irrevocability 80Why Humans Use Depth-First Search? 804.8.1 Example 1: Traversing a Maze 814.8.2 Example 2: Searching for a Gift 81Implementing Depth-First and Breadth-First SearchExample: Web Spidering 88Depth-First Iterative Deepening 88Using Heuristics for Search 904.12.1 Informed and Uninformed Methods 914.12.2 Choosing a Good Heuristic 924.12.3 The 8-Puzzle 9283xi

xiiContents4.134.144.154.164.174.184.194.20Chapter 55.15.25.35.45.55.65.75.84.12.4 Monotonicity 954.12.5 Example: The Modified Traveling SalesmanProblem 96Hill Climbing 984.13.1 Steepest Ascent Hill Climbing 984.13.2 Foothills, Plateaus, and Ridges 101Best-First Search 104Beam Search 106Identifying Optimal Paths 1074.16.1 A* Algorithms 1084.16.2 Uniform Cost Search 1104.16.3 Greedy Search 1114.16.4 Example: The Knapsack Problem 111Chapter Summary 113Review Questions 114Exercises 115Further Reading 116Advanced Search 117Introduction 117Constraint Satisfaction Search 118Forward Checking 121Most-Constrained Variables 121Example: Cryptographic Problems 122Heuristic Repair 123Combinatorial Optimization Problems 125Local Search and Metaheuristics 1265.8.1 Exchanging Heuristics 1265.8.2 Iterated Local Search 1275.8.3 Tabu Search 1275.8.4 Ant Colony Optimization 1285.9 Simulated Annealing 1285.9.1 Uses of Simulated Annealing 1305.10 Genetic Algorithms for Search 1315.11 Real-Time A* 131

Contents5.12 Iterative-Deepening A* (IDA*) 1325.13 Parallel Search 1325.13.1 Task Distribution 1345.13.2 Tree Ordering 1355.13.3 Search Engines 1355.14 Bidirectional Search 1365.15 Nondeterministic Search 1365.16 Island-Driven Search 1375.17 Nonchronological Backtracking 1375.18 Chapter Summary 1385.19 Review Questions 1395.20 Exercises 1405.21 Further Reading 141Chapter 6 Game Playing 1436.1 Introduction 1436.2 Game Trees 1446.2.1 Rationality, Zero Sum, and OtherAssumptions 1456.2.2 Evaluation Functions 1466.2.3 Searching Game Trees 1486.3 Minimax 1496.3.1 Bounded Lookahead 1516.4 Alpha-Beta Pruning 1536.4.1 The Effectiveness of Alpha-Beta Pruning6.4.2 Implementation 1556.5 Checkers 1596.5.1 Chinook 1606.5.2 Chinook’s Databases 1616.5.3 Chinook’s Evaluation Function 1626.5.4 Forward Pruning 1636.5.5 Limitations of Minimax 1636.5.6 Blondie 24 1646.6 Chess 164154xiii