============================= (1) the complete title of the papers ------------------------------------------------ Attaining Human-Competitive Game Playing with Genetic Programming GP-Gammon: Genetically Programming Backgammon Players GP-Robocode: Using Genetic Programming to Evolve Robocode Players GP-EndChess: Using Genetic Programming to Evolve Chess Endgame GP-Gammon: Using Genetic Programming to Evolve Backgammon Players (2) the name, physical mailing address... ----------------------------------------- moshe sipper, sipper@cs.bgu.ac.il yaniv azaria, azariaya@bioinformatics.buffalo.edu ami hauptman, amiha@cs.bgu.ac.il yoanatan shichel, shichel@cs.bgu.ac.il eran ziserman, eranz@cs.bgu.ac.il physical address for all: Department of Computer Science, Ben-Gurion University, P.O. Box 653, Beer-Sheva 84105 ISRAEL phone: +972-8-647-7880 (3) the name of the corresponding author ---------------------------------------- moshe sipper (4) the abstract(s) of the paper(s) ----------------------------------- Title: Attaining Human-Competitive Game Playing with Genetic Programming Abstract: We have recently shown that genetically programming game players, after having imbued the evolutionary process with human intelligence, produces human-competitive strategies for three games: backgammon, chess endgames, and robocode (tank-fight simulation). Evolved game players are able to hold their own---and often win---against human or human-based competitors. This paper has a twofold objective: first, to review our recent results of applying genetic programming in the domain of games; second, to formulate the merits of genetic programming in acting as a tool for developing strategies in general, and to discuss the possible design of a strategizing machine. Title: GP-Gammon: Genetically Programming Backgammon Players Abstract: We apply genetic programming to the evolution of strategies for playing the game of backgammon. We explore two different strategies of learning: using a fixed external opponent as teacher, and letting the individuals play against each other. We conclude that the second approach is better and leads to excellent results: Pitted in a 1000-game tournament against a standard benchmark player---\textit{Pubeval}---our best evolved program wins 62.4\% of the games, the highest result to date. Moreover, several other evolved programs attain win percentages not far behind the champion, evidencing the repeatability of our approach. Title: GP-Robocode: Using Genetic Programming to Evolve Robocode Players Abstract: This paper describes the first attempt to introduce evolutionarily designed players into the international Robocode league, a simulation-based game wherein robotic tanks fight to destruction in a closed arena. Using genetic programming to evolve tank strategies for this highly active forum, we were able to rank third out of twenty-seven players in the category of HaikuBots. Our GPBot was the only entry not written by a human. Title: GP-EndChess: Using Genetic Programming to Evolve Chess Endgame Players Abstract: We apply genetic programming to the evolution of strategies for playing chess endgames. Our evolved programs are able to draw or win against an expert human-based strategy, and draw against CRAFTY---a world-class chess program, which finished second in the 2004 Computer Chess Championship. Title: GP-Gammon: Using Genetic Programming to Evolve Backgammon Players Abstract: We apply genetic programming to the evolution of strategies for playing the game of backgammon. Pitted in a 1000-game tournament against a standard benchmark player---\textit{Pubeval}---our best evolved program wins 58\% of the games, the highest verifiable result to date. Moreover, several other evolved programs attain win percentages not far behind the champion, evidencing the repeatability of our approach. (5) a list containing one or more of the eight letters ------------------------------------------------------ (H) The result holds its own or wins a regulated competition involving human contestants (in the form of either live human players or human-written computer programs). (6) a statement stating why the result satisfies that criteria -------------------------------------------------------------- We were able to attain human-competitive results in three games: 1. Robocode. A simulation-based game in which robotic tanks fight to destruction in a closed arena (robocode.alphaworks.ibm.com). The programmers implement their robots in the Java programming language, and can test their creations either by using a graphical environment in which battles are held, or by submitting them to a central web site where online tournaments regularly take place. We evolved robocode players able to rank high in the weekly held tournaments of the international league (second and third place on several occasions). For example, http://robocode.yajags.com/20050101/haiku-1v1.html: GP-Robocode comes in 2nd of 28 -- *ALL* other 27 players were written by humans. 2. Backgammon. We evolved full-fledged players for the non-doubling-cube version of the game. Pitted against Pubeval, a standard benchmark program supplied by Tesauro, our top programs won 62% of the matches, 10% higher than top previous players. We do not have direct results against humans; however, HC-Gammon (Pollack, Blair, Land), which wins only 40% vs. Pubeval (cf. our 62%), has been pitted against humans: 58%/38% wins counting/not counting abandoned games as wins. By transitivity, our evolved players are most likely excellent against humans. Comparison of GP-Gammon with previous works (backgammon players) -- win percentage in tournament against Pubeval: PLAYER %WINS GP-Gammon 62.4 Darwen 52.7 GMARLB-Gammon 51.2 ACT-R-Gammon 45.94 HC-Gammon 40.00 3. Chess (endgames). We evolved players able to play 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. Indeed, in the chess lore much has been said and written about endgames. We pitted our GP-EndChess evolved players vs. two very strong programs (in human terms): 1) A program we wrote (`Master') based upon consultation with several high-ranking chess players (the highest being Boris Gutkin, ELO 2400, International Master); 2) CRAFTY -- a world-class chess program, which finished second in the 2004 World Computer Speed Chess Championship (www.cs.biu.ac.il/games/). Speed chess (``blitz'') involves a time-limit per move, which we imposed both on CRAFTY and on our players. Not only did we thus seek to evolve good players, but ones that play well *and fast*. Percent of wins, advantages, and draws for best GP-EndChess player in tournament against two top competitors: %Wins %Advs %Draws Master 6.00 2.00 68.00 CRAFTY 2.00 4.00 72.00 In summary, for all three games we evolved players able to win or hold their own against humans. (7) a full citation of the papers + links to full text ------------------------------------------------------ 1. M. Sipper, Y. Azaria, A. Hauptman, and Y. Shichel, "Attaining human-competitive game playing with genetic programming," IEEE Transactions on Systems, Man and Cybernetics -- Part C, conditionally accepted, 2005. Link: http://www.cs.bgu.ac.il/~sipper/papabs/gpgames.pdf 2. Y. Azaria and M. Sipper, "GP-Gammon: Genetically programming backgammon players," Genetic Programming and Evolvable Machines, in press, 2005. Link: http://www.cs.bgu.ac.il/~sipper/papabs/gpgammon.pdf 3. Y. Shichel, E. Ziserman, and M. Sipper, "GP-Robocode: Using genetic programming to evolve robocode players," in Proceedings of 8th European Conference on Genetic Programming (EuroGP2005), M. Keijzer, A. Tettamanzi, P. Collet, J. van Hemert, and M. Tomassini, Eds. 2005, vol. 3447 of Lecture Notes in Computer Science, pp. 143-154, Springer-Verlag, Heidelberg. Link: http://www.cs.bgu.ac.il/~sipper/papabs/eurogprobo-final.pdf 4. A. Hauptman and M. Sipper, "GP-EndChess: Using genetic programming to evolve chess endgame players," in Proceedings of 8th European Conference on Genetic Programming (EuroGP2005), M. Keijzer, A. Tettamanzi, P. Collet, J. van Hemert, and M. Tomassini, Eds. 2005, vol. 3447 of Lecture Notes in Computer Science, pp. 120-131, Springer-Verlag, Heidelberg. Link: http://www.cs.bgu.ac.il/~sipper/papabs/eurogpchess-final.pdf 5. Y. Azaria and M. Sipper, "GP-Gammon: Using genetic programming to evolve backgammon players," in Proceedings of 8th European Conference on Genetic Programming (EuroGP2005), M. Keijzer, A. Tettamanzi, P. Collet, J. van Hemert, and M. Tomassini, Eds. 2005, vol. 3447 of Lecture Notes in Computer Science, pp. 132-141, Springer-Verlag, Heidelberg. Link: http://www.cs.bgu.ac.il/~sipper/papabs/eurogpgammon-final.pdf