If we are at all concerned with the automation of intelligent behavior, then we ought to study the
field of Artificial Intelligence, according to George Luger.
p.1"Artificial Intelligence (AI) may be defined as the branch of computer science that is concerned
with the automation of intelligent behavior."
Intelligence and heuristics seem to be inseparable.
p.21"Much of what we commonly call intelligence seems to reside in the heuristics used by humans
to solve problems."
Making a computer form "plans", especially long range plans, is difficult. Humans do not seem to
have this difficulty. Then again, humans that are intelligent do not have problems predicting the behavior of entities in
their environment. Neither do they have trouble coming up with simple and elegant "tricks" that guarantee predictable results
when faced with trivial problems.
p.27"While humans plan effortlessly, creating a computer program that can do the same is a difficult
challenge."
Think of a heuristic as a means to guide a search along the most promising paths in an uncertain
environment. This does not guarantee that the best solution, or any solution, will be found. Sometimes, however, this
is good enough for the task at hand.
p.123-124"heuristics are formalized rules for choosing those branches in a state space that are
most likely to lead to an acceptable problem solution. AI problem solvers employ heuristics in two basic situations: 1. A
problem may not have an exact solution because of inherent ambiguities in the problem statement or available data... 2. A
problem may have an exact solution, but the computational cost of finding it may be prohibitive... Heuristics attack this
complexity by guiding the search along the most 'promising' path through the space... Unfortunately, like all rules of discovery
and invention, heuristics are fallible. A heuristic is only an informed guess of the next step to be taken in solving a problem.
It is often based on experience or intuition. Because heuristics use limited information, such as knowledge of the present
situation or descriptions of states currently on the open list, they are seldom able to predict the exact behavior of the
state space farther along in the search. A heuristic can lead a search algorithm to a suboptimal solution or fail to find
any solution at all. This is an inherent limitation of heuristic search... Heuristics and the design of algorithms to implement
heuristic search have long been a core concern of artificial intelligence. Game playing and theorem proving are two of the
oldest applications in artificial intelligence; both of these require heuristics to prune spaces of possible solutions. It
is not feasible to examine every inference that can be made in a mathematics domain or every possible move that can be made
on a chessboard, Heuristic search is often the only practical answer."
When we use minimax to look ahead in a search tree, we often will not be able to see far enough
ahead to reach the final checkmate positions. We will use a heuristic to estimate how winnable the game is at the endpoint
positions.
p.152"In applying minimax to more complicated games, it is seldom possible to expand the state space
graph out to the leaf nodes [checkmate, for example]. Instead, the state space is searched to a predefined number of levels,
as determined by available resources of time and memory. This strategy is called an n-ply look-ahead, where n is the number
of levels explored. As the leaves of this subgraph are not final states of the game, it is not possible to give them values
that reflect a win or a loss. Instead, each node is given a value according to some heuristic evaluation function. The value
that is propagated back to the root node is not an indication of whether or not a win can be achieved (as in the previous
example) but is simply the heuristic value of the best state that can be reached in n moves from the root [position]. Look-ahead
increases the power of a heuristic by allowing it to be applied over a greater area of the state space. "
An informed search might be the best (most promising) solution to a complex problem. A
simpler rule of thumb that can be applied to many more possibilities might also be the most promising solution.
p.159"In the attempt to bring down the branching of a search or otherwise constrain the search space,
we presented the notion of more informed heuristics. The more informed the search, the less space must be searched to get
the minimal path solution. As we pointed out in Section 4.4, the computational costs of the additional information needed
to further cut down the search space may not always be acceptable... As the information included in the heuristic increases,
the cpu cost of the heuristic increases. Similarly, as the heuristic gets more informed, the cpu cost of evaluating states
gets smaller, because fewer states are considered. The critical cost, however, is the total cost of computing the heuristic
PLUS evaluating states, and it is usually desirable that this cost be minimized."
The knowledge base of an intelligent system is a critical component and the source of the
power to solve problems.
p.277"The first principle of knowledge engineering is that the problem-solving power exhibited by
an intelligent agent's performance is primarily the consequence of its knowledge base, and only secondarily a consequence
of the inference method employed. Expert systems must be knowledge-rich even if they are methods-poor. This is an important
result and one that has only recently become well understood in AI. For a long time AI has focused its attention almost exclusively
on the development of clever inference methods; almost any inference method will do. The power resides in the knowledge."
Edward Feigenbaum, Stanford University
Human expertise is a complex amalgamation of several factors. We will be using heuristics to emulate
the problem solving skills of an expert.
p.298"Human expertise is an extremely complex amalgamation of theoretical knowledge, experience-based
problem-solving heuristics, examples of past problems and and their solutions, perceptual and interpretive skills and other
abilities that are so poorly understood that we can only describe them as intuitive."
