Special Issue: Modeling of Complex Systems by Cellular Automata 2007; Guest Ed. J. Kroc, Jr. (University of West Bohemia, Czech Republic)No Access

EMERGENCE OF COMPLEX STRATEGIES IN THE EVOLUTION OF CHESS ENDGAME PLAYERS

AMI HAUPTMAN

Department of Computer Science, Ben-Gurion University, Israel

Search for more papers by this author

and

MOSHE SIPPER

Department of Computer Science, Ben-Gurion University, Israel

Search for more papers by this author

https://doi.org/10.1142/S0219525907001082Cited by:11 (Source: Crossref)

Abstract

We examine a strong chess-endgame player, previously developed by us through genetic programming, focusing on the player's emergent capabilities and tactics in the context of a chess match. First, we provide a detailed description of the evolutionary approach by which our player was developed. Then, using a number of methods we analyze the evolved player's building blocks and their effect on play level. We conclude that evolution has found combinations of building blocks that are far from trivial and cannot be explained through simple combination — thereby indicating the possible emergence of complex strategies.

Keywords:

References

P. J. Angeline and J. B. Pollack, Competitive environments evolve better solutions for complex tasks, Proc. 5th Int. Conf. Genetic Algorithms (GA-93) (1993) pp. 264–270. Google Scholar
M. Bain, Learning Logical Exceptions in Chess, Ph.D. thesis, University of Strathclyde, Glasgow, Scotland (1994) . Google Scholar
Bonanno, G., The logic of rational play in games of perfect information, Paper 347, California Davis–Institute of Governmental Affairs (1989), available at http://ideas.repec.org/p/fth/caldav/347.html . Google Scholar
M. Campbell, A. J. Hoane Jr. and F.-H. Hsu, Artif. Intell. 134(1–2), 57 (2002), DOI: 10.1016/S0004-3702(01)00129-1. Crossref, Web of Science, Google Scholar
C. F. Chabris and E. S. Hearst, Cogn. Sci. 27, 637 (2003), DOI: 10.1016/S0364-0213(03)00032-6. Crossref, Web of Science, Google Scholar
N. Charness , Toward a General Theory of Expertise: Prospects and Limits , eds. K. A. Ericsson and J. Smith ( Cambridge University Press , Cambridge , 1991 ) . Google Scholar
G. J. Ferrer and W. N. Martin, Using genetic programming to evolve board evaluation functions for a board game, 1995 IEEE Conf. Evolutionary Computation2 (IEEE Press, 1995) pp. 747–752. Google Scholar
D. Fogelet al., Proc. IEEE 92(12), 1947 (2004), DOI: 10.1109/JPROC.2004.837633. Crossref, Web of Science, Google Scholar
P. W. Frey , Chess Skill in Man and Machine ( Springer-Verlag , New York, NJ , 1979 ) . Google Scholar
J. Fürnkranz, Int. Comput. Chess Assoc. J. 19(3), 147 (1996). Google Scholar
R. Grosset al., Evolving chess playing programs, GECCO 2002: Proc. Genetic and Evolutionary Computation Conf., eds. W. B. Langdonet al. (Morgan Kaufmann Publishers, 2002) pp. 740–747. Google Scholar
A. Hauptman and M. Sipper, GP-endchess: Using genetic programming to evolve chess endgame players, Proc. 8th European Conf. Genetic Programming3447, Lecture Notes in Computer Science, eds. M. Keijzeret al. (Springer, 2005) pp. 120–131. Google Scholar
J. H. Holland , Adaptation in Natural Artificial Systems ( University of Michigan Press , Ann Arbor , 1975 ) . Google Scholar
A. X. Jiang and M. Buro, First experimental results of ProbCut applied to chess, Proc. 10th Advances in Computer Games Conf. (Kluwer Academic Publishers, Norwell, MA, 2003) pp. 19–32. Google Scholar
G. Kendall and G. Whitwell, An evolutionary approach for the tuning of a chess evaluation function using population dynamics, Proc. 2001 Congress on Evolutionary Computation CEC2001 (IEEE Press, 2001) pp. 995–1002. Google Scholar
J. R. Koza , Genetic Programming: On the Programming of Computers by Means of Natural Selection ( MIT Press , Cambridge, MA , 1992 ) . Google Scholar
J. R. Koza , Genetic Programming II: Automatic Discovery of Reusable Programs ( MIT Press , Cambridge MA , 1994 ) . Google Scholar
J. R. Koza et al. , Genetic Programming IV: Routine Human-Competitive Machine Intelligence ( Kluwer Academic Publishers , Norwell, MA , 2003 ) . Google Scholar
T. A. Marsland and M. S. Campbell, A survey of enhancements to the alpha-beta algorithm, Proc. ACM National Conf. (1981) pp. 109–114. Google Scholar
T. A. Marsland, A. Reinefeld and J. Schaeffer, Artif. Intell. 31, 185 (1987), DOI: 10.1016/0004-3702(87)90019-1. Crossref, Web of Science, Google Scholar
M. Mitchell , An Introduction to Genetic Algorithms ( MIT Press , Cambridge, MA , 1996 ) . Google Scholar
D. J. Montana, Evol. Comput. 3(2), 199 (1995), DOI: 10.1162/evco.1995.3.2.199. Crossref, Web of Science, Google Scholar
L. A. Panait and S. Luke, A comparison of two competitive fitness functions, GECCO 2002: Proc. Genetic and Evolutionary Computation Conf., eds. W. B. Langdonet al. (Morgan Kaufmann Publishers, 2002) pp. 503–511. Google Scholar
A. Reinefeld , Spielbaum-Suchverfahren ( Springer , Berlin , 1989 ) . Crossref, Google Scholar
A. L. Samuel, Tech. Rev. 62, 42 (1959). Google Scholar
E. Sanchez and M. Tomassini (eds.) , Papers from an international workshop , Evolutionary Algorithms in Towards Evolvable Hardware, The Evolutionary Engineering Approach 1062 , Lecture Notes in Computer Science ( Springer , 1996 ) . Google Scholar
J. Schaeffer, IEEE Trans. Patt. Anal. Mach. Intell. 11(11), 1203 (1989), DOI: 10.1109/34.42858. Crossref, Web of Science, Google Scholar
M. Sipper , Machine Nature: The Coming Age of Bio-Inspired Computing ( McGraw-Hill , New York , 2002 ) . Google Scholar
G. L. Steele Jr. , CommonLisp the Language , 2nd edn. ( Digital Press , 1990 ) . Google Scholar