Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Evolving SQL Queries from Examples with Developmental Genetic Programming Read chapter Read first chapter

2013 | OriginalPaper | Chapter

12. More or Less? Two Approaches to Evolving Game-Playing Strategies

Authors : Amit Benbassat, Achiya Elyasaf, Moshe Sipper

Published in: Genetic Programming Theory and Practice X

Publisher: Springer New York

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We present two opposing approaches to the evolution of game strategies, one wherein a minimal amount of domain expertise is injected into the process, the other infusing the evolutionary setup with expertise in the form of domain heuristics. We show that the first approach works well for several popular board games, while the second produces top-notch solvers for the hard game of FreeCell.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter A Framework for the Empirical Analysis of Genetic Programming System Performance
next chapter Symbolic Regression Is Not Enough: It Takes a Village to Raise a Model
Footnotes
1
Note that since we are using DFS and not BFS we do not find all such states.
 
Literature
Aler R, Borrajo D, Isasi P (2002) Using genetic programming to learn and improve knowledge. Artificial Intelligence 141(1–2):29–56MATHCrossRef
Benbassat A, Sipper M (2012) Evolving competent board game players for mutiple games with little domain knowledge (in preparation)
Berlekamp ER, Conway JH, Guy RK (1982) Winning Ways for your Mathematical Plays. Academic Press, New York, NY, USAMATH
Burke EK, Hyde M, Kendall G, Ochoa G, Ozcan E, Woodward JR (2010) A classification of hyper-heuristic approaches. In: Gendreau M, Potvin J (eds) Handbook of Meta-Heuristics 2nd Edition, Springer, pp 449–468
Elyasaf A, Hauptman A, Sipper M (2011) GA-FreeCell: Evolving Solvers for the Game of FreeCell. In: Krasnogor N, et al (eds) GECCO ’11: Proceedings of the 13th annual conference on Genetic and evolutionary computation, ACM, Dublin, Ireland, pp 1931–1938, DOI doi:10.1145/ 2001576.2001836
Elyasaf A, Hauptman A, Sipper M (2012) Evolutionary design of freecell solvers (submitted)
Hauptman A, Sipper M (2005) GP-endchess: Using genetic programming to evolve chess endgame players. In: Keijzer M, Tettamanzi A, Collet P, van Hemert JI, Tomassini M (eds) Proceedings of the 8th European Conference on Genetic Programming, Springer, Lausanne, Switzerland, Lecture Notes in Computer Science, vol 3447, pp 120–131, DOI doi:10.1007/b107383, URL http://​www.​cs.​bgu.​ac.​il/​~sipper/​papabs/​eurogpchess-final.​pdf
Hauptman A, Sipper M (2007) Evolution of an efficient search algorithm for the mate-in-N problem in chess. In: Ebner M, O’Neill M, Ekárt A, Vanneschi L, Esparcia-Alcázar AI (eds) Proceedings of the 10th European Conference on Genetic Programming, Springer, Valencia, Spain, Lecture Notes in Computer Science, vol 4445, pp 78–89, DOI doi:10. 1007/978-3-540-71605-1-8
Hauptman A, Elyasaf A, Sipper M, Karmon A (2009) GP-rush: using genetic programming to evolve solvers for the rush hour puzzle. In: Raidl G, Rothlauf F, Squillero G, Drechsler R, Stuetzle T, Birattari M, Congdon CB, Middendorf M, Blum C, Cotta C, Bosman P, Grahl J, Knowles J, Corne D, Beyer HG, Stanley K, Miller JF, van Hemert J, Lenaerts T, Ebner M, Bacardit J, O’Neill M, Di Penta M, Doerr B, Jansen T, Poli R, Alba E (eds) GECCO ’09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, ACM, Montreal, pp 955–962, DOI doi:10.1145/1569901.1570032
Hauptman A, Elyasaf A, Sipper M (2010) Evolving hyper heuristic-based solvers for Rush Hour and FreeCell. In: SoCS ’10: Proceedings of the 3rd Annual Symposium on Combinatorial Search (SoCS 2010), pp 149–150
Heineman GT (2009) Algorithm to solve FreeCell solitaire games. Broadcast. oreilly. com/2009/01/january-column-graph-algorithm.html. Blog column associated with the book “Algorithms in a Nutshell book,” by G. T. Heineman, G. Pollice, and S. Selkow, O’Reilly Media, 2008
Hillis WD (1992) Co-evolving parasites improve simulated evolution as an optimization procedure. In: Langton CG, Taylor CE, Farmer JD, Rasmussen S (eds) Artificial Life II, Santa Fe Institute Studies in the Sciences of Complexity, vol X, Addison-Wesley, Santa Fe Institute, New Mexico, USA, pp 313–324
Hlynka M, Schaeffer J (2006) Automatic generation of search engines. In: Advances in Computer Games, pp 23–38
Lee KF, Mahajan S (1990) The development of a world class othello program. Artificial Intelligence 43(1):21–36, DOI DOI:10.1016/ 0004-3702(90)90068-B
Moriarty DE, Miikkulainen R (1995) Discovering complex (othello) strategies through evolutionary neural networks. Connection Science 7(3):195–210CrossRef
Rosenbloom PS (1982) A world-championship-level othello program. Artificial Intelligence 19(3):279–320, DOI DOI:10.1016/0004-3702(82) 90003-0
Samadi M, Felner A, Schaeffer J (2008) Learning from multiple heuristics. In: Fox D, Gomes CP (eds) Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI 2008), AAAI Press, pp 357–362
Metadata
Title
More or Less? Two Approaches to Evolving Game-Playing Strategies
Authors
Amit Benbassat
Achiya Elyasaf
Moshe Sipper
Copyright Year
2013
Publisher
Springer New York
Book
Genetic Programming Theory and Practice X

Print ISBN: 978-1-4614-6845-5

Electronic ISBN: 978-1-4614-6846-2

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-1-4614-6846-2_12

Premium Partner

    Image Credits