ac

Using Genetic Algorithm to Solve Puzzle Games: A Review

Authors

  • Iksan Bukhori Universitas Presiden
  • Jason Felix Universitas Presiden
  • Saddam Ali Universitas Presiden

DOI:

10.47709/cnahpc.v6i1.3348

Keywords:

Genetic Algorithms, Jigsaw, Puzzle Games, Sliding Block, Sudoku, Tetris, Tic-Tac-Toe

Dimension 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

Download data is not yet available.
Google Scholar Cite Analysis
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

Submitted Date: 2023-12-19
Accepted Date: 2023-12-21
Published Date: 2024-01-05

How to Cite

Bukhori, I. ., Felix, J. ., & Ali, S. . (2024). Using Genetic Algorithm to Solve Puzzle Games: A Review. Journal of Computer Networks, Architecture and High Performance Computing, 6(1), 201-211. https://doi.org/10.47709/cnahpc.v6i1.3348