A genetic algorithm for the Zen Puzzle Garden game

作者：Amos Martyn^*; Coldridge Jack

来源：Natural Computing, 2012, 11(3): 353-359.

DOI：10.1007/s11047-011-9284-7

• Genetic algorithm
• Transport puzzle
• NP-complete
• Game A*

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.

• 出版日期2012-9