Genetically modified games. (English) Zbl 1490.91037
Summary: Genetic programming is the practice of evolving formulas using crossover and mutation of genes representing functional operations. Motivated by genetic evolution we introduce and solve two combinatorial games, and we demonstrate some advantages and pitfalls of using genetic programming to investigate Grundy values. We conclude by investigating a combinatorial game whose ruleset and starting positions are inspired by genetic structures.
MSC:
| 91A46 | Combinatorial games |
| 91A22 | Evolutionary games |
| 90C90 | Applications of mathematical programming |
Keywords:
Python package gpLearnReferences:
| [1] | M. H. Albert, R. J. Nowakowski, and D. Wolfe, Lessons in Play: An Introduction to Combi-natorial Game Theory, A K Peters, Ltd., Wellesley, MA, 2007. · Zbl 1184.91001 |
| [2] | E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, second edition, A K Peters, Ltd., Natick, MA, 2001. · Zbl 1005.00004 |
| [3] | E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 2, second edition, A K Peters, Ltd., Natick, MA, 2003. · Zbl 1083.00003 |
| [4] | E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 3, second edition, A K Peters, Ltd., Natick, MA, 2003. · Zbl 1083.00003 |
| [5] | E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 4, second edition, A K Peters, Ltd., Wellesley, MA, 2004. · Zbl 1084.00002 |
| [6] | A. Bradford, J. K. Day, L. Hutchinson, B. Kaperick, C. E. Larson, M. Mills, D. Muncy, and N. Van Cleemput, Automated Conjecturing II: Chomp and Reasoned Game Play, J. Artificial Intelligence Res. 68 (2020), 447-461. · Zbl 1445.68328 |
| [7] | R. M. Brady, Optimization strategies gleaned from biological evolution, Nature 317 (1985), 804-806. |
| [8] | J. H. Conway, On Numbers and Games, second edition, A K Peters, Ltd., Natick, MA, 2001. · Zbl 0972.11002 |
| [9] | H. E. Dudeney, The Canterbury Puzzles (and Other Curious Problems), EP Dutton, New York, 1908. |
| [10] | P. Galinier and J.-K. Hao, Hybrid evolutionary algorithms for graph coloring, J. Comb. Optim. 3 (1999), 379-397. · Zbl 0958.90071 |
| [11] | P. M. Grundy, Mathematics and games, Eureka 2 (1939), 6-8. |
| [12] | R. K. Guy and C. A. B. Smith, The G-values of various games, Math. Proc. Cambridge Philos. Soc. 52 (3), (1956), 514-526. · Zbl 0074.34503 |
| [13] | A. Hauptman and M. Sipper, Analyzing the intelligence of a genetically programmed chess player, In Late Breaking Papers at the Genetic and Evolutionary Computation Conference 2005. Washington DC, June 2005. |
| [14] | G. Hornby, A. Globus, D. Linden, and J. Lohn, Automated antenna design with evolutionary algorithms, Space 2006, 2006. |
| [15] | M. Huggan and B. Stevens, Polynomial time graph families for Arc Kayles, Integers 16 (2016), #A86. · Zbl 1371.05180 |
| [16] | M. Oltean, Evolving winning strategies for Nim-like games, IFIP Student Forum (2004), 353-364. |
| [17] | T. J. Schaefer, On the complexity of some two-person perfect-information games, J. Comput. System Sci. 16 (1978), 185-225. · Zbl 0383.90112 |
| [18] | M. Sipper, Y. Azaria, A. Hauptman, and Y. Shichel, Designing an evolutionary strategizing machine for game playing and beyond, IEEE Transactions on Systems, Man, and Cybernetics, Part C 37 (4), (2007), 583-593. |
| [19] | R. Sprague,Über mathematische kampfspiele, Tohoku Mathematical Journal, First Series 41 (1935), 438-444. · JFM 62.1070.03 |
| [20] | T. Stephens, Gplearn Model, Genetic Programming, Copyright, 2015. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
