research-article

Simulating human grandmasters: evolution and coevolution of evaluation functions

Authors:

Omid David-Tabibi,

H. Jaap van den Herik,

Nathan S. NetanyahuAuthors Info & Claims

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Pages 1483 - 1490

https://doi.org/10.1145/1569901.1570100

Published: 08 July 2009 Publication History

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]

S.G. Akl and M.M. Newborn. The principal continuation and the killer heuristic. In Proceedings of the Fifth Annual ACM Computer Science Conference, pages 466--473. ACM Press, Seattle, WA, 1977.

Digital Library

[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]

J. Baxter, A. Tridgell, L. and Weaver. Learning to play chess using temporal-differences. Machine Learning, 40(3):243--263, 2000.

Digital Library

[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]

Y. Bjornsson and T.A. Marsland. Multi-cut pruning in alpha-beta search. In Proceedings of the First International Conference on Computers and Games, pages 15--24, Tsukuba, Japan, 1998.

Digital Library

[8]

Y. Bjornsson and T.A. Marsland. Multi-cut alpha-beta-pruning in game-tree search. Theoretical Computer Science, 252(1-2):177--196, 2001.

Digital Library

[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]

O. David-Tabibi, M. Koppel, and N.S. Netanyahu. Genetic algorithms for mentor-assisted evaluation function optimization. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1469--1476. Atlanta, GA, 2008.

Digital Library

[13]

O. David-Tabibi and N.S. Netanyahu. Extended null-move reductions. In Proceedings of the 2008 International Conference on Computers and Games, eds. H.J. van den Herik, X. Xu, Z. Ma, and M.H.M. Winands, pages 205--216. Springer (LNCS 5131), Beijing, China, 2008.

Digital Library

[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.

Digital Library

[16]

R. Gross, K. Albrecht, W. Kantschik, and W. Banzhaf. Evolving chess playing programs. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 740--747. New York, NY, 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.

Digital Library

[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.

Digital Library

[19]

E.A. Heinz. Extended futility pruning. ICCA Journal, 21(2):75--83, 1998.

[20]

R.M. Hyatt, A.E. Gower, and H.L. Nelson. Cray Blitz. Computers, Chess, and Cognition, eds. T.A. Marsland and J. Schaeffer, pages 227--237. Springer-Verlag, New York, 1990.

Digital Library

[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, 11(11):1203--1212, 1989.

Digital Library

[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.

Digital Library

[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]

R.S. Sutton and A.G. Barto. Reinforcement Learning: An Introduction, MIT Press, Cambridge, MA, 1998.

Digital Library

[30]

G. Tesauro. Practical issues in temporal difference learning. Machine Learning, 8(3-4):257--277, 1992.

Digital Library

[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.

Cited By

Vazquez-Fernandez ECoello C(2013)An adaptive evolutionary algorithm based on tactical and positional chess problems to adjust the weights of a chess engine2013 IEEE Congress on Evolutionary Computation10.1109/CEC.2013.6557727(1395-1402)Online publication date: Jun-2013
https://doi.org/10.1109/CEC.2013.6557727
Vazquez-Fernandez ECoello Coello CTroncoso F(2012)An evolutionary algorithm coupled with the Hooke-Jeeves algorithm for tuning a chess evaluation function2012 IEEE Congress on Evolutionary Computation10.1109/CEC.2012.6252977(1-8)Online publication date: Jun-2012
https://doi.org/10.1109/CEC.2012.6252977

Index Terms

Simulating human grandmasters: evolution and coevolution of evaluation functions
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
    2. Machine learning approaches
      1. Markov decision processes
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Markov decision processes

Recommendations

Genetic algorithms for mentor-assisted evaluation function optimization
GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

In this paper we demonstrate how genetic algorithms can be used to reverse engineer an evaluation function's parameters for computer chess. Our results show that using an appropriate mentor, we can evolve a program that is on par with top tournament-...
Expert-driven genetic algorithms for simulating evaluation functions

In this paper we demonstrate how genetic algorithms can be used to reverse engineer an evaluation function's parameters for computer chess. Our results show that using an appropriate expert (or mentor), we can evolve a program that is on par with top ...
Learning long-term chess strategies from databases

We propose an approach to the learning of long-term plans for playing chess endgames. We assume that a computer-generated database for an endgame is available, such as the king and rook vs. king, or king and queen vs. king and rook endgame. For each ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

July 2009

2036 pages

ISBN:9781605583259

DOI:10.1145/1569901

General Chair:
Franz Rothlauf
University of Mainz, Germany

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO09

Sponsor:

GECCO09: Genetic and Evolutionary Computation Conference

July 8 - 12, 2009

Québec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
304
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Vazquez-Fernandez ECoello C(2013)An adaptive evolutionary algorithm based on tactical and positional chess problems to adjust the weights of a chess engine2013 IEEE Congress on Evolutionary Computation10.1109/CEC.2013.6557727(1395-1402)Online publication date: Jun-2013
https://doi.org/10.1109/CEC.2013.6557727
Vazquez-Fernandez ECoello Coello CTroncoso F(2012)An evolutionary algorithm coupled with the Hooke-Jeeves algorithm for tuning a chess evaluation function2012 IEEE Congress on Evolutionary Computation10.1109/CEC.2012.6252977(1-8)Online publication date: Jun-2012
https://doi.org/10.1109/CEC.2012.6252977

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents