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

Figure 12.3
Minimax.

---

Exercise 12.3
Assume that black wins the toss and – using the same values
for horizon nodes depicted in Figure 12.3 – employ a
minimax procedure to determine the value of the initial
position.
12.3 PRUNING
We now have the makings of a procedure for searching for strategies
for playing a game as complex as chess. We search as far ahead as is
computationally tenable, apply a heuristic function to the nodes at the
search horizon, then use a minimax procedure to work back to the
node we are searching from.
This procedure, however, still su
ffers from combinatorial explo-
sion. Fortunately, there are further ways to maximise the e
fficiency of
our computational resources by cutting down the amount of search-
ing we have to do, or pruning the search tree.
One such method involves using what we have already discovered
in a search to determine that we can disregard certain branches. The
tree fragment depicted in Figure 12.5 shows a (greatly simplified) situ-
ation in which this is possible.
Given that black is a minimiser, we know that the value of node b
will be 3. We also know that the value of node c will be at most 2.
Consequently, we already know that the value of node a will be 3
(since white is a maximiser) regardless of the value of the node
marked with a question mark.
Certainly this is a trivial pruning in the example case. However, it
should be clear that the principle will extend to significantly more

127
Figure 12.4
Winning strategy for white.

---

complex cases and may allow us to disregard large parts of a search
tree, based on what we have antecedently discovered.
Another method for pruning is to find guiding principles which tell
us to simply not bother considering certain moves. It is often the case
with complex games that there will be certain legal moves available
from a given state that no one playing well would actually make, or
that no one would be at all likely to make. If we are informed with
respect to the unlikelihood of these moves obtaining, we can disre-
gard the branches of the search tree descending from those nodes.
A further pruning method involves playing out certain sequences
of moves from memory, without engaging in any search. In fact, this
is precisely how computers typically play chess openings. They have
access to a large database of standard openings and variations and
play the initial moves from a predetermined sequence.
The more we are able to prune the search tree, the more e
ffectively
our computational resources will be deployed. Consequently, in order
to program a machine to play a complex game well, we will need to
employ the best heuristics we can devise, in conjunction with various
methods for simplifying the search task.
12.4 HUMANS VERSUS COMPUTERS
We have now given some consideration to an activity which is gener-
ally taken as constitutive of intelligence – the ability to (at least learn
to) play well a complex game such as chess. We’ve seen – at least in
broad strokes – how to employ symbol systems and search methods
to automate the strategic play of such games.
In the case of chess, this involves a large database of opening
strategies, an optimised heuristic function for evaluating game states,
various principles for disregarding unlikely moves, and the deploy-
ment of significant computational resources to evaluate a very large
number of states per second. As I write this, the machines which are
128
  