Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence

Figure 11.3
Breadth first search.
Figure 11.4
Depth first search.

---

a tree, there is a danger in using it. If any of the branches of the tree
go infinite – as they often will in interesting formal systems – and we
use a depth first search, we run the risk of our search never terminat-
ing. If there are no solution states on a branch which goes infinite, our
depth first search will continue down the branch ad infinitum.
A useful strategy can be to combine depth first and breadth first
search. If we know, for instance, that some branches of the tree we are
interested in will go infinite and we suspect that there will be numer-
ous solution states distributed across nodes a long way down the tree,
we might do a depth first search only to a certain level. If we exhaust
the nodes down to that level without finding a solution state (which is
tantamount to having conducted a breadth first search to that level)
then we continue our depth first search to a deeper level.
11.3 HEURISTIC SEARCH
Breadth first and depth first are both what we call blind searches – they
are conducted without any consideration of the closeness to solution
of the nodes being searched.
Frequently, however, it will be the case that we have some e
ffective
procedure for determining, of a given node, the likelihood of there
being solution states among the descendants of that node. A function
which applies such an algorithm to nodes and assigns a value to them
accordingly is a heuristic function.
Determining good heuristics is very often the most di
fficult element
involved in solving complex problems in the symbolic artificial intel-
ligence tradition.
Consider, for instance, an exemplar classical artificial intelligence
project: determining an algorithm for playing chess well. One heuris-
tic for playing chess would be to simply construct the generation tree
for chess, then for any given game state – represented by a node of the
tree – assign a value in accordance with the number of descendant
nodes which represent winning states. Playing the game is then just a
matter of always moving to the position whose node has the best
value of those available.
Given a rule establishing an upper limit on the number of allow-
able moves in a game (such as the fifty move rule), we can keep the
tree finite, so this procedure seems feasible until we begin to quantify
the sheer complexity of chess.
The generation tree for chess su
ffers from drastic combinatorial
explosion. There are four hundred nodes at the second level alone. By
the time we get to the tenth iteration – by which time each player has

117

---

made only five moves – there are around nine billion nodes. At the
twentieth iteration there are something in the order of 10
30
nodes and
that is a very big number.
Even if we could generate one hundred trillion states per second, it
would still take around ten billion years to produce the generation
tree for only the first ten turns of chess.
Clearly then, the naive heuristic we described is computationally
untenable. Similarly, blind search techniques – while they have
their uses – are often computationally untenable for formal systems
of su
fficient complexity to be of interest to artificial intelligence
researchers. Investigating the generation trees of exponentially
complex formal systems is only possible with the aid of clever heuris-
tics which significantly reduce the computational load.
Determining heuristic functions to guide chess play su
fficiently
well so as to challenge the best human players turns out to be extra-
ordinarily di
fficult and computing these functions demands substan-
tial computational resources. We will discuss this further in the
following chapter when we contrast automated methods of game play
with human methods.
Given a heuristic function, we still need to decide how to be guided
by heuristic values in conducting a search. One such heuristic search
procedure is hill climbing.
A hill climbing search involves evaluating, at each node, the heuris-
tic value of its immediate descendant nodes and then moving to the
node with the best heuristic value. If we reach a terminal node without
finding a solution state, we backtrack to the next best possibility.
The letters in Figure 11.5 represent the order in which we would
search the depicted generation tree if our heuristic assigned values to
nodes as shown, where 0 represents a solution state.