Simulating human grandmasters: evolution and coevolution of evaluation functions

ABSTRACT

This paper demonstrates the use of genetic algorithms for evolving a grandmaster-level evaluation function for a chess program. This is achieved by combining supervised and unsupervised learning. In the supervised learning phase the organisms are evolved to mimic the behavior of human grandmasters, and in the unsupervised learning phase these evolved organisms are further improved upon by means of coevolution.

While past attempts succeeded in creating a grandmaster-level program by mimicking the behavior of existing computer chess programs, this paper presents the first successful attempt at evolving a state-of-the-art evaluation function by learning only from databases of games played by humans. Our results demonstrate that the evolved program outperforms a two-time World Computer Chess Champion.

REFERENCES

• 1: Selim G. Akl , Monroe M. Newborn, The principal continuation and the killer heuristic, Proceedings of the 1977 annual conference, p.466-473, January 1977 [doi>10.1145/800179.810240]
• 2: P. Aksenov.phGenetic algorithms for optimising chess position scoring. M. Sc. Thesis, University of Joensuu, Finland, 2004.
• 3: T.S. Anantharaman.Extension heuristics. ICCA Journal, 14(2):47--65, 1991.
• 4: Jonathan Baxter , Andrew Tridgell , Lex Weaver, Learning to Play Chess Using Temporal Differences, Machine Learning, v.40 n.3, p.243-263, Sept. 2000 [doi>10.1023/A:1007634325138]
• 5: D.F. Beal.Experiments with the null move. Advances in Computer Chess 5, ed. D.F. Beal, pages 65--79. Elsevier Science, Amsterdam, 1989.
• 6: D.F. Beal and M.C. Smith. Quantification of search extension benefits. ICCA Journal, 18(4):205--218, 1995.
• 7: Yngvi Björnsson , T. Anthony Marsland, Multi-cut Pruning in Alpha-Beta Search, Proceedings of the First International Conference on Computers and Games, p.15-24, November 11-12, 1998
• 8: Yngvi Björnsson , Tony A. Marsland, Multi-cut &agr;&bgr;-pruning in game-tree search, Theoretical Computer Science, v.252 n.1-2, p.177-196, Feb. 6, 2001 [doi>10.1016/S0304-3975(00)00081-5]
• 9: M.S. Campbell and T.A. Marsland. A comparison of minimax tree search algorithms. Artificial Intelligence, 20(4):347--367, 1983.
• 10: J.R. Capablanca. Chess Fundamentals, ed. N. de Firmian, Random House, Revised ed., 2006.
• 11: S. Chinchalkar. An upper bound for the number of reachable positions. ICCA Journal, 19(3):181--183, 1996.
• 12: Omid David-Tabibi , Moshe Koppel , Nathan S. Netanyahu, Genetic algorithms for mentor-assisted evaluation function optimization, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389382]
• 13: Omid David-Tabibi , Nathan S. Netanyahu, Extended Null-Move Reductions, Proceedings of the 6th international conference on Computers and Games, p.205-216, September 29-October 01, 2008, Beijing, China [doi>10.1007/978-3-540-87608-3_19]
• 14: C. Donninger. Null move and deep search: Selective search heuristics for obtuse chess programs. ICCA Journal, 16(3):137--143, 1993.
• 15: J.J. Gillogly. The technology chess program. Artificial Intelligence, 3(1-3):145--163, 1972.
• 16: 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
• 17: A. Hauptman and M. Sipper. Using genetic programming to evolve chess endgame players. In Proceedings of the 2005 European Conference on Genetic Programming, pages 120--131. Springer, Lausanne, Switzerland, 2005.
• 18: A. Hauptman and M. Sipper. Evolution of an efficient search algorithm for the Mate-in-N problem in chess. In Proceedings of the 2007 European Conference on Genetic Programming, pages 78--89. Springer, Valencia, Spain, 2007.
• 19: E.A. Heinz. Extended futility pruning. ICCA Journal, 21(2):75--83, 1998.
• 20: T. Anthony Marsland , J. Schaeffer, Computers, Chess, and Cognition, Springer-Verlag New York, Inc., Secaucus, NJ, 1990
• 21: G. Kendall and G. Whitwell. An evolutionary approach for the tuning of a chess evaluationfunction using population dynamics. In Proceedings of the 2001 Congress on Evolutionary Computation, pages 995--1002. IEEE Press, World Trade Center, Seoul, Korea, 2001.
• 22: H.L. Nelson. Hash tables in Cray Blitz.phICCA Journal, 8(1):3--13, 1985.
• 23: A. Reinfeld. An improvement to the Scout tree-search algorithm. ICCA Journal, 6(4):4--14, 1983.
• 24: J. Schaeffer. The history heuristic. ICCA Journal, 6(3):16--19, 1983.
• 25: J. Schaeffer, The History Heuristic and Alpha-Beta Search Enhancements in Practice, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.11, p.1203-1212, November 1989 [doi>10.1109/34.42858]
• 26: J. Schaeffer, M. Hlynka, and V. Jussila. Temporal difference learning applied to a high-performance game-playing program. In Proceedings of the 2001 International Joint Conference on Artificial Intelligence, pages 529--534. Seattle, WA, 2001.
• 27: J.J. Scott. A chess-playing program. Machine Intelligence 4, eds. B. Meltzer and D. Michie, pages 255--265. Edinburgh University Press, Edinburgh, 1969.
• 28: D.J. Slate and L.R. Atkin. Chess 4.5 -- The Northwestern University chess program. Chess Skill in Man and Machine, ed. P.W. Frey, pages 82--118. Springer-Verlag, New York, 2nd ed., 1983.
• 29: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 30: Gerald Tesauro, Practical Issues in Temporal Difference Learning, Machine Learning, v.8 n.3-4, p.257-277, May 1992 [doi>10.1007/BF00992697]
• 31: W. Tunstall-Pedoe. Genetic algorithms optimising evaluation functions. ICCA Journal, 14(3):119--128, 1991.
• 32: M.A. Wiering. TD learning of game evaluation functions with hierarchical neural architectures. Master's Thesis, University of Amsterdam, 1995.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Parameter learning

General Terms:
Algorithms

Keywords:
computer chess, fitness evaluation, games, genetic algorithms, parameter tuning