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

Figure 11.5
Hill climbing search.

---

downwards, whereas the south-east path involves initially climbing a
small rise. My goal is at sea level and I want to expend as little e
ffort as
possible so I take the north-east path. It turns out, however that the
north-east path is meandering and involves climbing many rises along
the way. The south-east path though, after cresting the initial rise,
descends quickly to the beach, dropping in elevation all the way.
In the scenario described, a hill climbing search causes me to miss
the quickest search path to the solution, as that path appeared initially
disadvantageous. One way to accommodate such situations is to do a
best first search.
A best first search is just like a hill climbing search save that our
choice of nodes to move to is not restricted solely to immediate
descendant nodes. We also keep a record of the heuristic values of all
the nodes we have searched so far and we choose from among the col-
lection of immediate descendent nodes and these other nodes.
This means that if, during a search, we reach a node where all the
immediate descendant nodes are rated by our heuristic as further
from our solution than a node we searched earlier, we can go back up
the tree and search from the better rated node next.
As with hill climbing, best first search involves taking the path of
least resistance. The di
fference is just that we expand our available
choices from any given node – we no longer require that search paths
always lead down a branch to the next iteration.
Figure 11.6 shows how the same tree from Figure 11.5 would be
searched according to a best first search.
120
  
Figure 11.6
Best first search.

---

As we can see, using best first search allows us to discover, in this
case, a shorter derivation for our solution state – we find a solution
node at a prior iteration.
Best first search is clearly the most e
fficient search procedure we
have examined. It should be clear, however, that it is also the most
computationally expensive per node. Not only do we have to apply a
heuristic function to nodes, but we also need the memory space in
which to record the values of all the nodes we have searched so far.
As the complexity of the tree increases, this computational expense
can become significant. It is still the case, though, that the computa-
tional savings in terms of the number of nodes we need to search far
outweigh the computational cost the heuristic procedure incurs.
There is a lot more for us to say about heuristics, so in the following
chapter we are going to examine how me might employ heuristic
search for a classical artificial intelligence application – playing
games.

121

---

C H A P T E R 1 2
GAMES
Now that we have a basic understanding of search procedures and
heuristic functions, it is time to apply this understanding in consider-
ation of automated methods of game play.
This provides us with an entry point to a broader examination of
how we might employ formal systems to enact functions which are
taken to be constitutive of intelligence.
We are also going to compare these formal methods for game play
to our reflective understanding of how humans play such games,
before moving on in the following chapters to a more detailed and
informed such comparison with respect to the cognitive functions
implicated in reasoning and language.
12.1 A SIMPLE GAME
If a game is su
fficiently simple, we can very easily automate a proced-
ure for playing it. It is fairly trivial, for instance, to determine an algo-
rithm for playing tic-tac-toe such that following the algorithm will
always result in either a win or a draw.
In such cases, all we need do is construct the generation tree for the
game, then work backwards from the terminal nodes to determine a
strategy.
For instance, suppose we have a game that is played as
follows. First an initial position is chosen. From that position, and
each subsequent position, there are exactly three ways in which a
player might move. Players flip a coin to determine who begins,
then the first player makes a move, the second player makes a
move and the first player makes a final move. After these three
moves, the game ends in a position which is a clear win for one of
the players.
The generation tree for this game is easily constructed. It will have
three iterations and a branching factor of three, so there will be
122

---

twenty-seven terminal nodes, each of which is discernible as a win for
one player (white) or the other (black).
The generation tree depicted in Figure 12.1 assumes we have
chosen an initial position for the game and assigns to each terminal
node the player for whom it is a winning position. We needn’t know
the particulars of the game or its play – its form is all we’re concerned
with here. I’ve merely stipulated which nodes are wins for which
player for illustrative purposes.
With the information depicted in Figure 12.1, we can work our way
back up the tree and determine who the chosen initial position will be
a win for.
Let’s suppose, for instance, that white wins the toss and is to make
the first move. That means that on the last iteration before the termi-
nal nodes, it is white’s move. A node at that iteration will count as a
win for white – given that it is white’s move – if there is at least one
descendant node which results in a win for white, otherwise it will
count as a win for black.
In other words, if white can move to a winning position and it is
white’s turn, then the position is already a winning position for white.
If, however, the only available moves are to positions which are
winning positions for black, then the position is already a winning
position for black.
Similarly, at the previous iteration it will be black’s turn. A node at
that iteration will count as a win for black if there is at least one
descendant node which counts as a win for black, and will count as a
win for white otherwise.
Figure 12.2 applies this procedure to the tree depicted in Figure
12.1 and demonstrates that if white wins the toss, white has a winning
strategy available. This is not, however, to say that white will win the

123