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:

• Player-Exposed(n): Test whether the player has exactly one checker at board location n
• Player-Blocked(n): Test whether the player has two or more checkers at location n
• Enemy-Exposed(n): Test whether the enemy has exactly one checker at board location n
• Sub(F, F) : Subtract two real numbers.

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.

Figure 1: Robocode interface.

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

• Backgammon: We evolved full-fledged players for the non-doubling-cube version of the game. Pitted against Pubeval, a standard benchmark program, our top programs won 62% of the matches, 10% higher than top previous machine players - quite a significant improvement.
• Chess (endgames): We evolved players able to play several types of endgames. While endgames typically contain but a few pieces, the problem of evaluation is still hard, as the pieces are usually free to move all over the board, resulting in complex game trees - both deep and with high branching factors. We pitted our evolved GP-EndChess players against two very strong programs: MASTER (which we wrote based on consultation with high-ranking chess players) and CRAFTY - a world-class chess program, which finished second in the 2004 World Computer Speed Chess Championship. GP-EndChess was able to draw most of the time and even win now and again, ie, the evolved program definitely holds its own.
• Robocode: A simulation-based game in which robotic tanks fight to destruction in a closed arena. The programmers implement their robots in the Java programming language and may submit them to a central web site where online tournaments regularly take place. GP-Robocode's best score was first place of 28 in the international league, with all other 27 players having been written by humans.

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: sippercs.bgu.ac.il