vii This book is about heuristics, popularly known as rules of thumb, educated guesses, intuitive
judgments or simply common sense. In more precise terms, heuristics stand for strategies using readily accessible
though loosely applicable information to control problem-solving processes in human beings and machine[s].
xi The study of heuristics draws its inspiration from the ever-amazing observation of how much people can
accomplish with that simplistic, unreliable information source known as intuition... Early attempts to equip machines
with humanlike intelligence have quickly revealed that machines, too, cannot possibly be expected to operate with only precise
and detailed knowledge of their task environment. Rather, this knowledge must, in some way, be summarized or abstracted
so as to provide, like human intuition, a steady stream of tentative, unpolished, yet swift and informative advice for managing
the primitive computational steps that make up a problem-solving process. The information content of this advice
came to be known as heuristic knowledge.
p.3 Heuristics are criteria, methods, or principles for deciding which among several alternative
courses of action promises to be the most effective in order to achieve some goal. They represent compromises between
two requirements: the need to make criteria simple and, at the same time, the desire to see them discriminate correctly between
good and bad choices.
A heuristic may be a rule of thumb that is used to guide one's actions.
p.4 It is the nature of good heuristics both that they provide a simple means of indicating
which among several course of action is to be preferred, and that they are not necessarily guaranteed to identify
the most effective course of action, but do so sufficiently often.
p.13-14 Each of the five preceding example problems presents us with repetitive choices among a multitude
of exploration paths that might be taken to reach a solution. In each case, we have exhibited a heuristic function that serves
to indicate which among all those paths seem the most likely to lead to a solution. The heuristics are simple to calculate
relative to the complexity of finding a solution and, although they do not necessarily always guide the search in the correct
direction, they quite often do. Moreover, whenever they do not, we can resort to some recovery scheme to resume the
search from a different point. The key is that these heuristics save time by avoiding many futile explorations.
But how do you find a good heuristic, and when you have found one, how should you use it
most effectively and how would you evaluate its merit?
The main objective of this book is to try to answer such questions and to quantify the characteristics
of heuristics that produce the most beneficial results.
p.46-47 In Chapter 1 (Section 1.1) we saw examples in which familiarity with the problem domain enabled
us to judge certain directions of search more promising than others, this using knowledge beyond that which is built into
the state and operator definitions. In this section, we see how this heuristic knowledge can be used in the formalism of systematic
search.
The most natural stage for using heuristic information is in deciding which node to expand
next.
p.48 The promise of a node can be estimated in various ways. One way is to assess the difficulty of solving
the subproblem represented by the node. Another way is to estimate the quality of the set of candidate solutions encoded by
the node. A third alternative is to consider the amount of information that we anticipate gaining by expanding a given node
and the importance of this information in guiding the overall search strategy. In all these cases, the promise of a node is
estimated numerically by a heuristic evaluation function f(n) which, in general, may depend on the description of
n, the description of the goal, the information gathered by the search up to that point, and most important, on any
extra knowledge about the problem domain.
p.79 The power of the heuristic estimate h( ) is measured by the amount of pruning induced
by h and depends, of course, on the accuracy of this estimate. [JLJ - I would say that the power of a heuristic
is the ability to uncover the truly promising lines of play and the extension of the depth of exploration along these
lines.]
p.92-93 Our task now is to devise a rule for scheduling nodes for expansion... What is the basis of our
regrets for not having explored [node] n? ...Every node competing for expansion could then be characterized
by a function R(C) measuring the risk associated with leaving that node unexplored, and we can impose the
requirement that the search will continue until the risk associated with every (unexplored) node on OPEN becomes lower than
some acceptable level [delta].
p.115 Instead of seeking a mathematical function h(n) to approximate h*(n) [The cheapest
cost of paths going from n to the set of goal nodes], we can actually complete the solution using the relaxed version of the
puzzle, count the number of steps required, and use this count as an estimate of h*(n).
p.115 Heuristics are discovered by consulting simplified models of the problem domain...
The preceding example, however, specifically demonstrates the use of one important class of simplified models; that
generated by removing constraints which forbid or penalize certain moves in the original problem. We call models
obtained by such constraint-deletion processes relaxed models.
p.118 We return now to the relaxation scheme and to show how the deletion of constraints can be systematized
to the point that natural heuristics, such as those demonstrated in Chapter 1, can be generated by mechanical means. The constraint-relaxation
scheme is particularly suitable for this purpose because it is often convenient to represent problem domains by specifying
the constraints that govern the applicability and impact of the various transformations in that domain.
p.122 the General Problem Solver (Ernst and Newell, 1969) is controlled by "differences," a set of features
that make the goal different from the current state [JLJ - provided, of course, that your strategy involves pursuing only
this goal]. The programmer has to specify, though, along what dimensions these differences are measured, which differences
are easier to remove, what operators have the potential of reducing each of the differences, and under what conditions each
reduction operator is applicable.
p.124 Although the effort invested in searching for an appropriate relaxed model may seem heavy, the payoffs
expected are rather rewarding. Once a simplified model is found, it can be used to generate heuristics for all
instances of the original problem domain.
p.126 Sampling is perhaps the oldest and the most widely practiced of all heuristic methods.
p.131 Rather than ignoring constraints altogether, an alternative way of relaxing problems by mathematical
manipulations is to penalize the cost function for some constraint violations and reward it when some constraints are satisfied.
p.169 In chapter 4 it was argued that heuristic methods usually derive their knowledge from simplified models
of the problem environment. It is natural to expect, therefore, that the utility of the heuristic used should depend on the
proximity between its underlying model and the reality of the problem at hand. The more faithful the model, the more
efficient the search.
p.221 The skill of playing games such as chess, checkers, or GO has long been regarded as a distinctive
mark of human intelligence. It is natural, therefore, that the general public continues to monitor the success of
game-playing programs as a measure of progress in artificial intelligence.
p.226 Using Evaluation Functions. Having no practical way of evaluating the exact status of successor game
positions, one may naturally resorts [sic] to heuristic approximations. Experience teaches us that certain features
in a game position contribute to its strength, whereas others tend to weaken it. Thus we may be able to select a
reasonably "good" move if we can list a sufficient number of features for each one of the resulting positions, aggregate their
contributions into a single evaluation function e, and then choose the move leading toward the game position of highest merit.
Such a simplistic decision would obviously lead to poor play unless the evaluation function were
extremely accurate, that is, if it correlated very closely with the actual status of the nodes evaluated... An obvious
generalization is not to use the board evaluation immediately, but use it after the play has extended through several rounds
of move and counter move.
p.229 Highly sophisticated evaluation functions may permit us to get by with shallow search,
whereas deep search may make up for deficiencies in the evaluation function.
p.299 A straightforward way of obtaining [move] ordering information is to compute the static evaluation
functions of contending successors, and use these values to determine which should be explored first. Such informed
ordering requires that whenever we generate a node, some evaluation be applied to all its siblings, even to those that would
eventually be cut off by the search. The question now arises whether this extra ordering computation will pay off
