Genetically programmed strategies for chess endgame

ABSTRACT

Classical chess engines exhaustively explore moving possibilities from a chessboard configuration to choose what the next best move to play is. In this article we present a new method to solve chess endgames without using Brute-Force algorithms or endgame tables. We are proposing to use Genetic Programming to combine elementary chess patterns defined by a chess expert. We apply this method specifically to the classical King-Rook-King endgame. We show that computed strategies are both effective and generic for they manage to win against several opponents (human players and artificial ones such as the chess engine CRAFTY). Besides, the method allows to propose strategies that are clearly readable and useable for a purpose such as teaching chess.

REFERENCES

• 1: M. Au onès, A. Beck, P. Camacho, N. Lassabe, H. Luga, and F. Scharffe. Evaluation of chess position by modular neural ne work genera ed by genetic algorithm. In EuroGP pages 1--10, 2004.
• 2: M. Bain , S. Muggleton, Learning optimal chess strategies, Machine intelligence 13: machine intelligence and inductive learning, Oxford University Press, Inc., New York, NY, 1994
• 3: J. Burmeister and J. Wiles. The challenge of go as a domain for ai research:a comparison between go an chess. In Proceedings of the Third Austral ian and New Zealand Conference on Intelligent Information Systems IEEE Conference on Evolutionary Computation volume volume 2, 1995.
• 4: A. E. Elo. The Rating of Chessplayers, Past and Present Arco Pub., New York, 2nd edition, 1978.
• 5: G. J. Ferrer and W. N. Martin. Using genetic programming to evolve board evaluation functions for a boardgame. In 1995 IEEE Conference on Evolutionary Computation volume 2, page 747, Perth, Australia, 29--1 1995. IEEE Press.
• 6: D. Gleich. Machine learning in computer chess: Genetic programmig and krk, 2003.
• 7: R. Groß , K. Albrecht , Wolfgang Kantschik , Wolfgang Banzhaf, Evolving Chess Playing Programs, Proceedings of the Genetic and Evolutionary Computation Conference, p.740-747, July 09-13, 2002
• 8: A. Hauptman and M. Sipper. GP-endchess: Using genetic programming o evolve chess endgame players. In Proceedings of the 8th European Conference on Genetic Programming volume 3447 of Lecture Notes in Computer Science pages 120--131, Lausanne, Switzerland, 30 Mar.--1 Apr. 2005. Springer.
• 9: G. Kendall and G. Whitwell. An evolutionary approach for the uning of a chess evaluation function using population dynamics. In Proceedings of the 2001 Congress on Evolutionary Computation CEC2001 pages 995--1002. IEEE Press, 27-30 2001.
• 10: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 11: E. Morales. On learning how to play. In Advances in Computer Chess 8 pages 235--250. Universiteit Maastricht, 1997.
• 12: E. V. Nalimov, G. Haworth, and E. A. Heinz. Space-efficient indexing of endgame databases for chess. ICGA Journal Vol. 23(No. 3):148--162, 2000.
• 13: A. Newell, J. Shaw, and H. Simon. Chess-playing programs and the problem of complexity. IBM Journal of Research and Development 2:320--335, 1958.
• 14: A. E. G. Rober M. Hyatt, Harry L. Nelson. Cray blitz. In in Computers, Chess, and Cognition pages 111--130. Springer-Verlag, 1990.
• 15: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 16: Yasser Seirawan , Herbert A. Simon , Toshinori Munakata, The implications of Kasparov vs. Deep Blue, Communications of the ACM, v.40 n.8, p.21-25, Aug. 1997 [doi>10.1145/257874.257878]
• 17: C. Shannon. Programming a computer for playing chess. Phil. Mag., 41:256--275, 1950.
• 18: H. Simon and W. Chase. Skill in chess. American Scientist 61:394--403, 1973.
• 19: J.-C. Weill. How hard is he correct coding of an easy endgame. In H. J. v. d. Herik, I. S. Herschberg, and J. W. H. M. Uiterwijk, editors, Advances in Computer Chess 7 pages 163--176. University of Limburg, 1994.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Design

Keywords:
chess, evolving strategies, genetic programming