One of the most novel and compelling demonstrations of the
power of genetic algorithms was presented by Chellapilla and Fogel 2001, who
used a GA to evolve neural networks that could play the
game of checkers. The authors state that one of the major
difficulties in these sorts of strategy-related problems is
the credit assignment problem - in other words, how
does one write a fitness function? It has been widely
believed that the mere criterion of win, lose or draw does
not provide sufficient information for an evolutionary
algorithm to figure out what constitutes good play.
In this paper, Chellapilla and Fogel overturn that
assumption. Given only the spatial positions of pieces on
the checkerboard and the total number of pieces possessed
by each side, they were able to evolve a checkers program
that plays at a level competitive with human experts,
without any intelligent input as to what constitutes good
play - indeed, the individuals in the evolutionary algorithm
were not even told what the criteria for a win were, nor were
they told the result of any one game.
In Chellapilla and Fogel's representation, the game state was
represented by a numeric list of 32 elements, with each position in the
list corresponding to an available position on the board. The value at
each position was either 0 for an unoccupied square, -1 if that
square was occupied by an enemy checker, +1 if that square
was occupied by one of the program's checkers, and -K or +K
for a square occupied by an enemy or friendly king. (The
value of K was not pre-specified, but again was determined
by evolution over the course of the algorithm.)
Accompanying this was a neural network with multiple
processing layers and one input layer with a node for each
of the possible 4x4, 5x5, 6x6, 7x7 and 8x8 squares on the
board. The output of the neural net for any given
arrangement of pieces was a value from -1 to +1 indicating
how good it felt that position was for it. For each move,
the neural network was presented with a game tree listing
all possible moves up to four turns into the future, and a
move decision was made based on which branch of the tree
produced the best results for it.
The evolutionary algorithm began with a population of 15 neural
networks with randomly generated weights and biases assigned to each
node and link; each individual then reproduced once, generating an
offspring with variations in the values of the network. These 30
individuals then competed for survival by playing against each other,
with each individual competing against 5 randomly chosen opponents per
turn. 1 point was awarded for each win and 2 points were deducted for
each loss. The 15 best performers, based on total score, were selected
to produce offspring for the next generation, and the process repeated.
Evolution was continued for 840 generations (approximately six months
of computer time).
|
The single best individual that emerged from this selection was entered as a competitor on the gaming website www.zone.com. Over a period of two months, it played against 165 human opponents comprising a range of high skill levels, from class C to master, according to the ranking system of the United States Chess Federation (shown at left, some ranks omitted for clarity). Of these games, the neural net won 94, lost 39 and drew 32; based on the rankings of the opponents in these games, the evolved neural net was equivalent to a player with a mean rating of 2045.85, placing it at the expert level - a higher ranking than 99.61% of over 80,000 players registered at the website. One of the neural net's most significant victories was when it defeated a player ranked 98th out of all registered players, whose rating was just 27 points below master level. |
Tests conducted with a simple piece-differential program (which bases moves solely on the difference between the number of checkers remaining to each side) with an eight-move look-ahead showed the neural net to be significantly superior, with a rating over 400 points higher. "A program that relies only on the piece count and an eight-ply search will defeat a lot of people, but it is not an expert. The best evolved neural network is" (p.425). Even when it was searching positions two further moves ahead than the neural net, the piece-differential program lost decisively in eight out of ten games. This conclusively demonstrates that the evolved neural net is not merely counting pieces, but is somehow processing spatial characteristics of the board to decide its moves. The authors point out that opponents on zone.com often commented that the neural net's moves were "strange", but its overall level of play was described as "very tough" or with similar complimentary terms.
To further test the evolved neural network (which the authors named "Anaconda" since it often won by restricting its opponents' mobility), it was played against a commercial checkers program, Hoyle's Classic Games, distributed by Sierra Online (Chellapilla and Fogel 2000). This program comes with a variety of built-in characters, each of whom plays at a different skill level. Anaconda was tested against three characters ("Beatrice", "Natasha" and "Leopold") designated as expert-level players, playing one game as red and one game as white against each of them with a six-ply look-ahead. Though the authors doubted that this depth of look-ahead would give Anaconda the ability to play at the expert skill level it had previously shown, it won six straight victories out of all six games played. Based on this outcome, the authors expressed skepticism over whether the Hoyle software played at the skill level advertised, though it should be noted that they reached this conclusion based solely on the ease with which Anaconda defeated it!
The ultimate test of Anaconda was given in Chellapilla and Fogel 2002, where the evolved neural net was matched against the best checkers player in the world: Chinook, a program designed principally by Dr. Jonathan Schaeffer of the University of Alberta. Rated at 2814 in 1996 (with its closest human competitors rated in the 2600s), Chinook incorporates a book of opening moves provided by human grandmasters, a sophisticated set of middle-game algorithms, and a complete database of all possible moves with ten pieces on the board or less, so it never makes a mistake in the endgame. An enormous amount of human intelligence and expertise went into the design of this program.
Chellapilla and Fogel pitted Anaconda against Chinook in a 10-game tournament, with Chinook playing at a 5-ply skill level, making it roughly approximate to master level. Chinook won this contest, four wins to two with four draws. (Interestingly, the authors note, in two of the games that ended as draws, Anaconda held the lead with four kings to Chinook's three. Furthermore, one of Chinook's wins came from a 10-ply series of movies drawn from its endgame database, which Anaconda with an 8-ply look-ahead could not have anticipated. If Anaconda had had access to an endgame database of the same quality as Chinook's, the outcome of the tournament might well have been a victory for Anaconda, four wins to three.) These results "provide good support for the expert-level rating that Anaconda earned on www.zone.com" (p.76), with an overall rating of 2030-2055, comparable to the 2045 rating it earned by playing against humans. While Anaconda is not an invulnerable player, it is able to play competitively at the expert level and hold its own against a variety of extremely skilled human checkers players. When one considers the very simple fitness criterion under which these results were obtained, the emergence of Anaconda provides dramatic corroboration of the power of evolution.
Original Link: http://www.talkorigins.org/faqs/genalg/genalg.html