Robotics Reference
In-Depth Information
rows of the edge of the board and those positions in which it is not.
Then it might sub-divide each of these classes further, according to other
criteria suggested by useful Chess heuristics. This “divide and conquer”
approach is employed by CLS to build
decision trees
that learn from their
training examples to discriminate between different classes of examples.
In 1979 Ross Quinlan, the leading AI practitioner in Australia, adapt-
ed the CLS model of concept formation to develop a variation on its
algorithm which he called ID3.
45
Quinlan made two significant modifi-
cations to the original algorithm. Firstly, rather than have the attributes
proposed by human operators of the system, the attributes in ID3 were
chosen by heuristics so as to be applied in an order which reflected their
usefulness as discriminators, with the most useful being applied first. The
other significant change was to allow only a selection of examples within
a class, those that fell within a “window” specified by the system, to be
used for training the decision tree—the other examples in that class were
then tested on the tree and when it made a mistake the tree was modi-
fied in order to correct the mistake. Both of these changes speeded up
the tree creation process considerably by enabling Quinlan's algorithm to
learn from a relatively small set of training examples. Quinlan also used
a combination of mathematics and logic to enable ID3 to operate on
both numerical and non-numerical data, thereby making it applicable to
many more classification problems than are those algorithms which can
cope only with numerical data.
Quinlan tested ID3 on the Chess endgame of king and rook versus
king and knight. We saw in Chapter 3 how Ken Thompson and others
were building huge databases of Chess endgame positions together with
the correct move for each, so that programs can look up any of these po-
sitions and know instantly which was the right move. Instead, Quinlan
and Donald Michie became intrigued by the problem of using databases
to
teach
a program by example, teaching it the heuristic rules for play-
ing endgames. This idea was inspired by Torres y Quevedo's success at
isolating the few rules that were necessary for his machine to play with
king and rook versus a lone king. ID3 was also adopted for other em-
ployment at the chessboard by two of Michie's research students in Edin-
bugh, Tim Niblett and Alen Shapiro. Michie had long been interested in
computer Chess and, at that time, was particularly fascinated by the idea
of automatically inducing rules for playing Chess endgames, rather than
45
For Itemized Dichotomizer.
