Empirical evidence suggests that searching deeper in game trees using the minimax propagation rule usually improves the quality of decisions significantly. However, despite many recent theoretical analyses of the effects of minimax look ahead, however, this phenomenon has still not been convincingly explained. Instead, much attention has been given to so-called pathological behavior, which occurs under certain assumptions. This article supports the view that pathology is a direct result of these underlying theoretical assumptions. Pathology does not occur in practice, because these assumptions do not apply in realistic domains. The article presents several arguments in favor of minimaxing and focuses attention on the gap between their analytical formulation and their practical meaning. A new model is presented based on the strict separation of static and dynamic aspects in practical programs. finally, certain methods of improving minimax look-ahead are discussed, drawing on insights gained from this research.

Citing the confusing statements in the AI literature concerning the relationship between branch and bound (B&B) and heuristic search procedures were present a simple and general formulation of B&B which should help dispel much of the confusion. We illustrate the utility of the formulation by showing that through it some apparently very different algorithms for searching And/Or trees reveal the specific nature of their similarities and differences. In addition to giving new insights into the relationships among some AI search algorithms, the general formulation also provides suggestions on how existing search procedures may be varied to obtain new algorithms.

A new procedure is presented for growing min-max game trees. In large games, such as chess, decisions must be based on incomplete search trees. The new tree-growth procedure is based on “conspiracy numbers” as a measure of the accuracy of the root minimax value of an incomplete tree. Conspiracy numbers measure the number of leaf nodes whose value must change in order to change the minimax root value by a given amount. Trees are grown in a way that maximizes the conspiracy required to change the root value.

Get Citation Alerts New Citation Alert added!

Methods from computational group theory are used to improve the speed of backtrack searching on problems with symmetry. The symmetry testing algorithm, which is similar to a color automorphism algorithm, takes the symmetry group as input and uses it to avoid searching equivalent portions of the search space. The algorithm permits dynamic search rearrangement in conjunction with symmetry testing. Experimental results confirm that the algorithm saves a considerable amount of time on some search problems.

As a book about search, it is thorough, at the state of the art, and contains expositions that will delight the expert with their clarity and depth. However, it is not, per se, a book about AI (nor was it intended to be) or about the history, philosophy, or cognitive aspects of heuristic knowledge.

To fully appreciate Professor Pearl's book, begin with a and the numerous techniques for representing knowledge careful reading of the title. It is a book about "..Intelligent-and uncertainty in common use in mainstream AI. ..Strategies.." for the discovery and use of "Heuristics.. " Chapter 5 begins a quantitative performance analysis of to allow computers to solve ".. Search.. ' ' problems. This includes a nice exposition on is a critical component in AI programs (Nilsson 1980, Barr branching processes, although the mathematically unsophisticated and Feigenbaum 1982), and in this sense Pearl's book is a reader may find it difficult. Here Pearl introduces strong contribution to the field of AI. It serves as an excellent probabilistic models to complement probabilistic heuristics. As a book about search, it is thorough, at analysis of search heuristics, and to a probabilistic analysis the state of the art, and contains expositions that will delight of nonadmissible heuristics in ...

The system presented here shows how Soar, an architecture for general problem solving and learning, can acquire general search-control knowledge from outside guidance. The guidance can be either direct advice about what the system should do, or a problem that illustrates a relevant idea. The system makes use of the guidance by first formulating an appropriate goal for itself. In the process of achieving this goal, it learns general search-control chunks. In the case of learning from direct advice, the goal is to verify that the advice is correct. The verification allows the system to obtain general conditions of applicability of the advice, and to protect itself from erroneous advice. The system learns from illustrative problems by setting the goal of solving the problem provided. It can then transfer the lessons it learns along the way to its original problem. This transfer constitutes a rudimentary form of analogy.

This report contains the reading list for the Qualifying Examination in Artificial Intelligence. Areas covered include search, representation, reasoning, planning and problem solving, learning, expert systems, vision, robotics, natural language, perspectives and AI programming. An extensive bibliography is also provided.

Annual Review of Computer Science