Invited article

Evolving Game-Playing Strategies with Genetic Programming

by Moshe Sipper


We have recently used genetic programming, wherein computer programs evolve by artificial selection, to obtain human-competitive game-playing strategies for three games: chess, backgammon, and Robocode.

The idea of applying the biological principle of natural evolution to artificial systems, introduced over four decades ago, has seen impressive growth in the past few years. Evolutionary algorithms have been successfully applied to numerous problems from different domains, including optimization, automatic programming, circuit design, machine learning, economics, immune systems, ecology, and population genetics, to mention but a few. Our group focuses on the evolutionary methodology known as genetic programming.

In genetic programming we evolve a population of computer programs, whose basic building blocks are designed for the problem at hand. For example, when we evolved backgammon-playing programs the list of elements from which programs could be constructed included:

The full list (for backgammon) comprises over 20 such programmatic elements.

Being randomly generated, the first-generation individuals usually exhibit poor performance. However, some individuals are better than others, ie, (as in nature) variability exists, and through the mechanism of natural (or, in our case, artificial) selection, these have a higher probability of being selected to parent the next generation. Once individuals have been probabilistically selected in accordance with fitness, two genetically inspired operators are applied: crossover, which takes two individual programs, 'cuts' each in two, and then combines the four resulting pieces to create two new viable offspring; and mutation, which takes one program and mutates it, ie, changes it in some random manner that results in a different (legal) program. Thus we have gone through one evaluate-select-crossover-mutate cycle, known as a generation. Repeating this procedure, cycling through several generations, may ultimately lead to good solutions to the given problem, in our case an artificial player able to hold its own against human or machine players.

Robocode interface.
Figure 1: Robocode interface.

Other than backgammon we tested our evolutionary approach on two other games - chess, and Robocode - obtaining excellent results:

Figure 2: Generic programming flowchart.
Figure 2: Generic programming flowchart. M is the population size and Gen is the generation counter. The termination criterion can be the completion of a fixed number of generations or the discovery of a good-enough individual.

These results recently earned us a Bronze Medal in the 2005 Human-Competitive Awards in Genetic and Evolutionary Computation competition, where the objective was to have evolution produce results competitive with humans.

Links:
Author's website: http://www.moshesipper.com/
Human-competitive awards: http://www.human-competitive.org/
GP-Robocode wins first place: http://robocode.yajags.com/20050625/haiku-1v1.html

Please contact:
Moshe Sipper, Ben-Gurion University, Israel
E-mail: sipper@cs.bgu.ac.il