Using Genetic Algorithm to Solve Puzzle Games: A Review
DOI:
10.47709/cnahpc.v6i1.3348Keywords:
Genetic Algorithms, Jigsaw, Puzzle Games, Sliding Block, Sudoku, Tetris, Tic-Tac-ToeDimension Badge Record
Abstract
Puzzles have been recognized for their development as a popular form of entertainment due to their ability to intricately challenge the mind while engendering creativity in the player. The development of puzzle games has given rise to a new generation of puzzle games characterized by diverse sequences and different image variations. With the rapid development of puzzle games, we looked at solving approaches using Genetic Algorithms (GA). In this paper, we try to analyze several puzzle games such as Sliding Blocks, Sudoku, Tic-Tac-Toe, and Jigsaw that can be solved using GA. We found that 120 papers have examined the use of GA for puzzle games, and eliminated into 14 papers. We evaluated these 14 papers for each puzzle game we selected by comparing the chromosome representation, GA operator, GA parameters, and the results. Based on the discussion, the application of GA to solve puzzle games can be effectively executed with a high degree of accuracy. Puzzle games that use measurement methods such as Sliding Block, Sudoku, and Jigsaw run in a similar pattern. What is common to all of them is that the chromosomes are represented as matrices or arrays in all cases, and standard genetic operators such as selection, crossover, and mutation are used. The population size is large, often 1000 chromosomes, and parameters such as mutation rate are kept low, around 5%. On the other hand, the performance of GA for solving Tetris and Tic-Tac-Toe from each publication cannot be compared due to different measurement methods and metrics.
Downloads
Abstract viewed = 425 times
References
Gu, T. (2021, August 12). Newzoo Corporation. Retrieved from Newzoo Corporation Website: https://newzoo.com/resources/blog/puzzle-game-mobile-data-revenues-player-behavior-consumer-insights-us-japan-china-korea
Nayyar, A., Le, D.-N., & Nguyen, N. G. (2018). Advances in Swarm Intelligence for Optimizing Problems in Computer Science. In A. Nayyar, D.-N. Le, & N. G. Nguyen, Advances in Swarm Intelligence for Optimizing Problems in Computer Science (p. 28). CRC Press.
Sharma, H. (2022, November 07). SkillLync.Inc. Retrieved from LkillLync.Inc Website: https://skill-lync.com/student-projects/week-5-genetic-algorithm-104
Sivanandam, S., & Deepa, S. (2008). Introduction to Genetic Algorithms. In S. Sivanandam, & S. Deepa, Introduction to Genetic Algorithms (pp. 15-37). Berlin, Heidelberg: Springer.
Mitchell, M. (1995). Genetic Algorithms: An Overview. Complexity, 1(1), 31-39.
Britannica, T. Editors of Encyclopaedia (2009, July 21). Fifteen Puzzle. Encyclopedia Britannica. https://www.britannica.com/topic/Fifteen-Puzzle
Suh, J. Y., & Lee, C. D. (1989). Extending Distributed Genetic Algorithms to Problem Solving: The Case of the Sliding Block Puzzle. 1-56.
Sha'ban, R. Z., Alkallak, I. N., & Sulaiman, M. M. (2009). Genetic Algorithm to Solve Sliding Tile 8-Puzzle Problem. 1-13.
Wilson, R. (2023, May 5). sudoku. Encyclopedia Britannica. https://www.britannica.com/topic/sudoku
Mantere, T. (2010). Solving Rubik's Cube with Genetic Algorithm. 1-5.
Afriyudi. A, Pramudyo, A. S., & Akbar, M. (2008). Penyelesaian Puzzle Sudoku menggunakan Algoritma Genetik. 1-4.
Kazemi, S. M., & Fatemi, B. (2014). A Retrievable Genetic Algorithm for Efficient Solving. 1-5.
Britannica, T. Editors of Encyclopaedia (2023, October 29). Tetris. Encyclopedia Britannica. https://www.britannica.com/topic/Tetris
Flom, L., & Robinson, C. (2004). Using a Genetic Algorithm to Weight an Evaluation Function for Tetris. 1-5.
Lewis, J. (2015). Playing Tetris with Genetic Algorithms. 1-4.
Choi, A. S. (2021). Tic Tac Toe. 1-10
Hochmuth, G. (2003). On the Genetic Evolution of a Perfect Tic-Tac-Toe Strategy. 1-8.
Bhatt, A., Varshney, P., & Deb, K. (2008). In Search of No-loss Strategies for the Game of Tic-Tac-Toe using a Customiezd Genetic Algorithm. 1-8.
Ling, S. H., & Lam, H. K. (2011). Journal of Intelligent Learning System and Application . Playing Tic-Tac-Toe Using Genetic Neural Network with Double Transfer Functions, 37-44.
Mohammadi, H., Santos, M. V., & Borne, N. P. (2013). Evolving Tic-Tac-Toe Playing Algorithms Using Co-Evolution, Interactive. 1-6.
Britannica, T. Editors of Encyclopaedia (2021, July 26). jigsaw puzzle. Encyclopedia Britannica. https://www.britannica.com/topic/jigsaw-puzzle
Sholomon, D., David, O., & Netanyahu, N. S. (2013). A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles. 1-8.
Pomeranz, D., Shemesh, M., & Ben-Shahar, O. (2011). A Fully Automated Greedy Square Jigsaw Puzzle Solver. 1-8.
Hynek, J. (2014). Sequence Matching Genetic Algorithm for Square Jigsaw Puzzles. 1-8.
Toyama, F., Fujiki, Y., Shoji, K., Miyamichi, J.: Assembly of puzzles using a genetic algorithm. In Proc. of 16th International Conference on Pattern Recognition, Quebec, Canada, vol.4, pp.389-392 (2002).
Guo, W., Wei, W., Zhang, Y., & Fu, A. (2020). A Genetic Algorithm-Based Solver. 1-12.
Downloads
ARTICLE Published HISTORY
How to Cite
Issue
Section
License
Copyright (c) 2023 Iksan Bukhori, Jason Felix, Saddam Ali
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.