nach oben

Natural Computing

Erschienen in:

01.09.2012

A genetic algorithm for the Zen Puzzle Garden game

verfasst von: Martyn Amos, Jack Coldridge

Erschienen in: Natural Computing | Ausgabe 3/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we present a novel genetic algorithm (GA) solution to a simple yet challenging commercial puzzle game known as Zen Puzzle Garden (ZPG). We describe the game in detail, before presenting a suitable encoding scheme and fitness function for candidate solutions. By constructing a simulator for the game, we compare the performance of the GA with that of the A* algorithm. We show that the GA is competitive with informed search in terms of solution quality, and significantly out-performs it in terms of computational resource requirements. By highlighting relevant features of the game we hope to stimulate further work on its study, and we conclude by presenting several possible areas for future research.

Vorheriger Artikel Foreword

Nächster Artikel Stateless multicounter 5′ → 3′ Watson–Crick automata: the deterministic case

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Berger MS, Lawton JH (2007) Multi-agent planning in Sokoban. Multi-agent systems and applications V. Lecture notes in computer science, vol 4696. Springer, pp 334–336

Botea A, Müller M, Schaeffer J (2003) Using abstraction for planning in Sokoban. In Schaeffer J, Müller M, Björnsson Y (eds) Computers and Games 2002, number 2883 in Lecture notes in computer science. Springer Verlag, pp 360–375

Dechter R, Pearl J (1985) Generalized best-first strategies and the optimality of A*. J ACM 32(3):505–536MathSciNetMATHCrossRef

Demaine ED, Hoffmann M (2001) Pushing blocks is NP-complete for noncrossing solution paths. Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG 2001), Waterloo, Ontario, Canada, 13–15 August 2001, pp 65–68

Dor D, Zwick U (1999) SOKOBAN and other motion planning problems. Comput Geom Theory Appl 13(4):215–228MathSciNetMATHCrossRef

Goldberg DE (1989a) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, BostonMATH

Goldberg DE (1989b) Zen and the art of genetic algorithms. Proceedings of the 3rd international conference on genetic algorithms, pp 80–85

Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4(2):100–107CrossRef

Hong T-P, Huang J-Y, Lin W-Y (2002) Applying genetic algorithms to game search trees. Soft Comput 6(3–4):277–283MATHCrossRef

Houston R, White J, Amos M (2011) Zen puzzle garden is NP-complete (submitted)

Junghanns A, Schaeffer J (2001a) Sokoban: enhancing general single-agent search methods using domain knowledge. Artif Intell 129(1–2):219–251MathSciNetMATHCrossRef

Junghanns A, Schaeffer J (2001b) Sokoban: improving the search with relevance cuts. Theor Comput Sci 252(1–2):151–175MathSciNetMATHCrossRef

Kendall, G, Spoerer, K (2004) Scripting the game of Lemmings with a genetic algorithm. Proceedings of the 2004 Congress on Evolutionary Computation (CEC2004), June 19–23, Portland, Oregon, USA, IEEE Press, pp 117–124

Kendall G, Parkes A, Spoerer K (2008) A survey of NP-complete puzzles. ICGA J 31(1):13–34

Korf RE (1997) Finding optimal solutions to Rubik’s Cube using pattern databases. Proceedings of the AAAI Conference on Artificial Intelligence, Providence, RI, USA, Wiley, pp. 700–705

Lexaloffle Games. Zen Puzzle Garden. Trial version downloadable at http://www.lexaloffle.com/zen.htm

Mantere T, Koljonen J (2007) Solving, rating and generating Sodoku puzzles with GA. Proceedings IEEE Congress on Evolutionary Computation (CEC) September 25–28, 2007, Singapore, IEEE Press, pp 1382–1389

Meffert K, Rotstan N, Knowles C, Sangiorgi U JGAP: Java genetic algorithms and genetic programming package. http://jgap.sf.net

Osborne MJ, Rubinstein A (1999) A course in game theory. MIT Press, Cambridge

Pirsig RM (1976) Zen and the art of motorcycle maintenance. Corgi, London

Titel: A genetic algorithm for the Zen Puzzle Garden game
verfasst von: Martyn Amos
Jack Coldridge
Publikationsdatum: 01.09.2012
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 3/2012
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-011-9284-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2012

Using enzymatic numerical P systems for modeling mobile robot controllers

Parallel predator–prey interaction for evolutionary multi-objective optimization

Evolutionary mechanics: new engineering principles for the emergence of flexibility in a dynamic and uncertain world

Step-wise tile assembly with a constant number of tile types

Stateless multicounter 5′ → 3′ Watson–Crick automata: the deterministic case

Emergence of synchronicity in a self-organizing spiking neuron network: an approach via genetic algorithms