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

Figure 12.1
A simple game.

---

game – after all, a human player may well make a mistake. It is merely
to say that there is an algorithmic winning strategy available to white.
Exercise 12.1
Assume that black wins the toss and complete the generation
tree depicted in Figure 12.1 according to the procedure we
have described. Is there a winning strategy available to black
from this initial combination if black is to move first?
The solution to Exercise 12.1 demonstrates that for the game
described, and given the initial position which results in the assign-
ment of terminal nodes as depicted in Figure 12.1, the player who wins
the toss has a winning strategy available to them. This may not be the
case for other initial positions of the game but it is a deliberate feature
of the example assignments of winning players to terminal nodes.
Exercise 12.2 (Challenge)
Consider the generation tree for tic-tac-toe. Assume that all
nodes representing winning positions are terminal.
(a)
How many nodes are there at the first iteration?
(b)
At which iteration are terminal nodes first generated?
(c)
How many nodes are there on the tree in total?
(d)
How many terminal nodes does the tree contain?
(e)
How many of these nodes represent winning states for
either player?
While this procedure of working backwards from terminal nodes is
e
fficient in delivering winning strategies, its application is limited to
124
  
Figure 12.2
Winning strategy for white.

---

only the simplest of games. As we saw in the last chapter, the genera-
tion trees for more interesting and complex games tend to grow
exponentially, rendering a procedure such as this computationally
untenable.
To determine methods of searching for winning strategies in games
such as chess, we will need to employ heuristics.
12.2 MINIMAX
We saw in section 11.3 that we can apply a heuristic function to a node
which evaluates, according to criteria relevant to the system, the
closeness to solution of that node. In the context of a two-player
game, the states which will count as solution states are those repre-
senting wins for (an arbitrary) one of the players. In this case, the fur-
thest a game could be from a solution state would be a state
representing a win for the other player.
Consequently, our heuristic values will represent how a game state
stands with respect to a possible win for either player. For the sake of
example, lets stipulate that lower numbers will represent closeness to
a win for black and higher numbers will represent closeness to a win
for white.
So unlike the example we saw in section 11.3 – in which the root
node was as far from solution as possible – the root node for a two-
player game will take a heuristic value exactly in the middle of the
range (presuming the initial position is not prejudiced towards either
player).
Heuristic functions evaluate nodes based on certain internal fea-
tures of the state represented at the node. So, for example, in chess we
can take account of material advantage, dominance of the centre and
advancement of certain pieces in order to generate a value which rep-
resents the goodness of that state for each player. Even a very good
heuristic function, however, is limited in only considering features
internal to the state.
Contrast this with the procedure we considered in the previous
section. Using information about states generated at further iter-
ations to evaluate prior nodes is a procedure which considers features
external to states.
We can greatly increase the accuracy of a method for determining
strategies in complex games by using a combination of internal and
external features as a guide. In other words, we can combine the use
of a heuristic function with a method for working backwards from
evaluated nodes to determine a value for prior nodes.

125

---

We’ve seen that we can’t feasibly construct the entire generation
tree for chess. What we can do, however, is search ahead just a few
moves and apply a heuristic function to the nodes which are at the
search horizon. We can then use a minimax procedure to work back-
wards from the search horizon to determine a value for the node we’re
evaluating.
Given our earlier stipulation that lower heuristic values will repre-
sent closeness to a win for black, black will be a minimiser and white
will be a maximiser. In other words, black will always be seeking to
move to states which have lower heuristic values, and white will seek
to move to states with higher values.
Let’s make a minor modification to the simple game we described
in the previous section, such that the game no longer always results in
a clear win for one player at the end of three turns. Now let’s suppose
that we select an initial position and draw up the generation tree for
only the first three moves, then apply a heuristic function to get the
values depicted at the horizon nodes in Figure 12.3.
Using the heuristic values at the horizon nodes, we can apply a
minimax procedure to determine a value for the selected initial pos-
ition, as follows.
Assume white wins the toss, in which case at the iteration immedi-
ately prior to the search horizon it is white’s turn to move. White is a
maximiser so the value of a node at that iteration will be the maximum
of the values of the immediate descendant nodes.
At the iteration immediately prior to that, it is black’s turn to move.
Black is a minimiser so the value of a node at that iteration will be the
minimum of the values of the immediate descendant nodes.
Using this procedure, we work backwards from the horizon nodes
to determine the value of the root node, as Figure 12.4 depicts.
126
  