Genetic algorithms and the art of Zen

Jack Coldridge; Martyn Amos

doi:10.1109/BICTA.2010.5645284

Genetic algorithms and the art of Zen

Jack Coldridge^*, Martyn Amos

^*Corresponding author for this work

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

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. We then compare the performance of the genetic algorithm with that of the A * algorithm. Our results 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. We conclude with a brief discussion of the implications of our findings for game solving and other "real world" problems.

Original language	English
Title of host publication	Proceedings 2010 IEEE 5th International Conference on Bio-Inspired Computing
Subtitle of host publication	Theories and Applications, BIC-TA 2010
Publisher	IEEE
Pages	1417-1423
Number of pages	7
ISBN (Electronic)	9781424464401
ISBN (Print)	9781424464388, 9781424464371
DOIs	https://doi.org/10.1109/BICTA.2010.5645284
Publication status	Published - 29 Nov 2010
Event	2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010 - Changsha, China Duration: 23 Sept 2010 → 26 Sept 2010

Conference

Conference	2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010
Country/Territory	China
City	Changsha
Period	23/09/10 → 26/09/10

Access to Document

10.1109/BICTA.2010.5645284

Cite this

@inproceedings{ed44bb3d46614cb1845f6d61f4080905,

title = "Genetic algorithms and the art of Zen",

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. We then compare the performance of the genetic algorithm with that of the A * algorithm. Our results 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. We conclude with a brief discussion of the implications of our findings for game solving and other {"}real world{"} problems.",

author = "Jack Coldridge and Martyn Amos",

year = "2010",

month = nov,

day = "29",

doi = "10.1109/BICTA.2010.5645284",

language = "English",

isbn = "9781424464388",

pages = "1417--1423",

booktitle = "Proceedings 2010 IEEE 5th International Conference on Bio-Inspired Computing",

publisher = "IEEE",

address = "United States",

note = "2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010 ; Conference date: 23-09-2010 Through 26-09-2010",

}

Coldridge, J & Amos, M 2010, Genetic algorithms and the art of Zen. in Proceedings 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010., 5645284, IEEE, pp. 1417-1423, 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010, Changsha, China, 23/09/10. https://doi.org/10.1109/BICTA.2010.5645284

TY - GEN

T1 - Genetic algorithms and the art of Zen

AU - Coldridge, Jack

AU - Amos, Martyn

PY - 2010/11/29

Y1 - 2010/11/29

N2 - 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. We then compare the performance of the genetic algorithm with that of the A * algorithm. Our results 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. We conclude with a brief discussion of the implications of our findings for game solving and other "real world" problems.

AB - 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. We then compare the performance of the genetic algorithm with that of the A * algorithm. Our results 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. We conclude with a brief discussion of the implications of our findings for game solving and other "real world" problems.

UR - https://www.scopus.com/pages/publications/78650601329

U2 - 10.1109/BICTA.2010.5645284

DO - 10.1109/BICTA.2010.5645284

M3 - Conference contribution

AN - SCOPUS:78650601329

SN - 9781424464388

SN - 9781424464371

SP - 1417

EP - 1423

BT - Proceedings 2010 IEEE 5th International Conference on Bio-Inspired Computing

PB - IEEE

T2 - 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010

Y2 - 23 September 2010 through 26 September 2010

ER -

Genetic algorithms and the art of Zen

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this