Received 20.09.2024, Revised 22.11.2024, Accepted 26.12.2024

Analysis of the decision-making algorithm efficiency in complex game environments on the example of Pac-Man

Artem Novikov, Volodymyr Yanovskyi

Game simulations such as Pac-Man are substantial for testing decision-making algorithms in conditions that mimic real-life scenarios. This creates new opportunities for the development of autonomous systems that can adapt to changing environmental conditions and interact with other agents. The study aimed to compare Expectimax, Monte Carlo Tree Search, and Alpha-Beta Pruning algorithms in the changed conditions of the Pac-Man game to determine the most efficient approach to decision-making in complex environments. For this purpose, simulation modelling was used to evaluate the effectiveness of agents in various game mazes that differ in complexity. The study measured such indicators as the number of points, game time, and percentage of winnings, which were used to assess the effectiveness of algorithms in different situations. The analysis of the experiments determined that the Monte Carlo algorithm is the most effective among the tested methods for solving less complex mazes, confirming quickly optimal path search in simple conditions. The Alpha-Beta Pruning algorithm demonstrated less efficiency, which indicates the need to optimise it for more complex environments. Expectimax demonstrated significantly lower performance, which indicates its limited suitability for complex game mazes. The study demonstrated that increasing the complexity of the mazes significantly reduces the performance of all algorithms, especially with more obstacles, highlighting the importance of developing more robust methods for highly complex environments. Optimising the Monte Carlo and Alpha-Beta Pruning algorithms for complex environments can significantly improve their performance and make them effective for real-world applications in navigation and control of moving devices. The results of this study can be used to develop efficient navigation algorithms for autonomous vehicles, drones and other robotic systems where adaptation to changes in complex environments is critical

simulation environments; Expectimax; MCTS; Alpha-Beta Pruning; autonomous navigation
108-118
Novikov, A., & Yanovskyi, V. (2024). Analysis of the decision-making algorithm efficiency in complex game environments on the example of Pac-Man. Information Technologies and Computer Engineering, 21(3), 108-118. https://doi.org/10.63341/vitce/3.2024.108

References

[1] Busatto-Gaston, D., Chakraborty, D., & Raskin, J.-F. (2020). Monte Carlo tree search guided by symbolic advice for MDPs. In 31st international conference on concurrency theory (CONCUR 2020). Leibniz international proceedings in informatics (LIPIcs) (Vol. 171, pp. 40:1-40:24). Schloss Dagstuhl: Leibniz-Zentrum für Informatik. doi: 10.4230/LIPIcs. CONCUR.2020.40.

[2] Cheng, K. M., Liu, H., & Dou, X. (2024). Randomized Pacman maze generation algorithm. Applied and Computational Engineering, 42, 156-162. doi: 10.54254/2755-2721/42/20230771.

[3] Cheng, Y., Hu, X., Tang, Q., Qi, H., & Yang, H. (2020). Monte Carlo Tree search-based mixed traffic flow control algorithm for arterial intersections. Transportation Research Record, 2674(8), 167-178. doi: 10.1177/0361198120919746.

[4] Evillasio2. (2022). The Pac-Man Ghosts Alt. DeviantArt. Retrieved from https://www.deviantart.com/evilasio2/art/ The-Pac-Man-Ghosts-Alt-916669643.

[5] Guerreiro, J.M.P. (2021). Learning agent in the Ms. Pac-Man vs Ghosts game. (Master’s Thesis, Instituto Superior Técnico, Lisboa, Portugal).

[6] Li, W., Liu, Y., Ma, Y., Xu, K., Qiu, J., & Gan, Z. (2023). A self-learning Monte Carlo tree search algorithm for robot path planning. Frontiers in Neurorobotics, 17. doi: 10.3389/fnbot.2023.1039644.

[7] Liu, X., Li, Y., He, S., Fu, Y., Yang, J., Ji, D., & Chen, Y. (2009). To create intelligent adaptive game opponent by using Monte-Carlo for the game of Pac-Man. In Fifth international conference on natural computation (pp. 598-602). Tianjian: IEEE. doi: 10.1109/ICNC.2009.633.

[8] Lövétei, I. F., Kővári, B., & Bécsi, T. (2021). MCTS based approach for solving real-time railway rescheduling problem. Periodica Polytechnica Transportation Engineering, 49(3), 283-291. doi: 10.3311/PPtr.18584.

[9] Maddipati, H., Kundurthi, A., Raaj, P., Srilatha, K., & Surapaneni, R. (2020). Artificial Intelligence based Pacman Game. International Journal of Innovative Technology and Exploring Engineering, 9, 140-144. doi: 10.35940/ijitee. I6975.079920.

[10] Mishra, P., Patel, V., Mittal, P., & Patni, J.C. (2018). Algorithm analysis tool based on execution time-input instancebased runtime performance benchmarking. In International conference on recent developments in science, technology, humanities and management – 2017 (pp. 27-30). Kuala Lumpur: SRD.

[11] Mudda, M. (2022). Tic Tac Toe by Minimax Alpha-Beta Pruning using Arduino. International Journal for Research in Applied Science and Engineering Technology, 10(2), 157-165. doi: 10.22214/ijraset.2022.40115.

[12] Pepels, T., Winands, M. H. M., & Lanctot, M. (2014). Real-time Monte Carlo Tree search in Ms Pac-Man. IEEE Transactions on Computational Intelligence and AI in Games, 6(3), 245-257. doi: 10.1109/TCIAIG.2013.2291577.

[13] Permatasari, B.D., Haryanto, H., Zuni Astuti, E., & Dolphina, E. (2022). Peningkatan kemenangan non-playable character dalam permainan triple triad Menggunakan Alpha-Beta Pruning. Jurnal Komputasi, 10(1). doi: 10.23960/ komputasi.v10i1.2952.

[14] Ramadhan, A. W. R., & Udjulawa, D. (2020). Perbandingan algoritma dijkstra dan algoritma a star pada permainan Pac-Man. Jurnal Algoritme, 1(1), 12-20. doi: 10.35957/algoritme.v1i1.411.

[15] Salem, N., Haneya, H., Balbaid, H., & Asrar, M. (2024). Exploring the maze: A comparative study of path finding algorithms for PAC-Man game. In 21st learning and technology conference (L&T) (pp. 92-97). Jeddah: IEEE. doi: 10.1109/ LT60077.2024.10469459.

[16] Samothrakis, S., Robles, D., & Lucas, S. (2011). Fast approximate Max-n Monte Carlo Tree search for Ms Pac-Man. IEEE Transactions on Computational Intelligence and AI in Games, 3(2), 142-154. doi: 10.1109/TCIAIG.2011.2144597.

[17] Sharma, N. (2022). Introduction to artificial intelligence. Retrieved from https://inst.eecs.berkeley.edu/~cs188/fa22/ assets/notes/cs188-fa22-note06.pdf.

[18] Shevtekar, P.S., Malpe, M. & Bhaila, M. (2022). Analysis of game tree search algorithms using Minimax Algorithm and Alpha-Beta Pruning. International Journal of Scientific Research in Computer Science, Engineering and Information Technology (IJSRCSEIT), 8(6), 328-333. doi: 10.32628/CSEIT1228644.

[19] Singhal, S.P., & Sridevi, M. (2019). Comparative study of performance of parallel alpha Beta Pruning for different architectures. In 2019 IEEE 9th international conference on advanced computing (IACC) (pp. 115-119). Tiruchirappalli: IEEE. doi: 10.1109/IACC48062.2019.8971591.

[20] Świechowski, M., Godlewski, K., Sawicki, B., & Mańdziuk, J. (2023). Monte Carlo Tree search: A review of recent modifications and applications. Artificial Intelligence Review, 56, 2497-2562. doi: 10.1007/s10462-022-10228-y.

[21] Wang, B., Ma, R., Kuang, J., & Zhang, Y. (2020). How decisions are made in brains: Unpack “black box” of CNN with Ms. Pac-Man video game. IEEE Access, 8, 142446-142458. doi: 10.1109/ACCESS.2020.3013645.

[22] Zou, Y. (2021). General Pacman AI: Game agent with tree search, adversarial search and model-based RL algorithms. In 2nd International conference on big data & artificial intelligence & software engineering (ICBASE) (pp. 253-260). Zhuhai: IEEE. doi: 10.1109/ICBASE53849.2021.00053.