Addison-Wesley, 1984)
. This book, written by a reputed specialist, is a valuable and very interesting contribution to a subfield of Artificial Intelligence which has not been the topic of many extensive tutorials until now. Indeed, heuristic strategies are only superficially presented in most of the A.I. textbooks, although they are commonly considered as an important part of problem solving, if we except the books by N. Nilsson.' Thereby noticeable results were scattered in reports, proceedings, and journals.
J. Pearl's book is divided in three main parts. The first one offers a structured, unified, and thorough presentation of the general techniques which have been developed for heuristic search in graphs (state space representation) or in hypergraphs (subproblem space representation): uninformed (or blind) search, informed (or ordered) search including the Z*, A*, AO, AO* algorithms and their variants. The properties of these different techniques are carefully stated and established. The second part is devoted to mathematical performance analysis (in terms of the number of appeared or expanded nodes) of the above-mentioned techniques, using probabilistic models. The first chapter in the third part describes basic heuristic schemas for guiding the choice of a move in two-player, perfectinformation games (mainly the min max, a-P, SSS,* and SCOUT methods). The second chapter studies the performances of these schemas (using probabilistic models again), while the third one discusses the decision quality in game searching.
Most of the ten chapters of this book are enriched with bibliographical and historical remarks, which help the reader to have a synthetic view on the different methods presented by the author and the variants developed by others. Moreover, texts of appropriate exercises are proposed at the end of each chapter. Naturally, the book largely reflects the author's research; it explains the important place given to the theoretical study of the performances based on probabilistic models (in Chapters 5 to 10). In contrast, we may regret the almost complete lack of concrete examples (with an exception at the end of Chapter 8) or even real applications; only classical toy-problems such as the 8-puzzle, the %queen problem, the traveling salesman problem, the Hanoi towers, etc . . . are considered.
The third part, entitled "Game-playing programs" is devoted to a presentation and an analysis of strategies and models for game-playing and searching; however, implementation aspects are not discussed and games such as checkers, chess, backgammon, . . . are not considered.