Control Systems and Computers

https://doi.org/10.15407/csc.2024.04.019

Control Systems and Computers, 2024, Issue 4 (308), pp. 19-33

UDC 004.94

O.A. NOVIKOV, PhD student, Institute of Computer Science and Artificial Intelligence Department of Mathematical Modeling and Data Analysis, Karazin Kharkiv National University, Svobody, Sq 4, Kharkiv, Ukraine, 61022, ORCID: https://orcid.org/0009-0004-5914-7098, artem.slick@gmail.com

V.V. YANOVSKY, Doctor of Physical and Mathematical Sciences, Professor of Department of Artificial Intelligence Systems, “Institute for Single Crystals” of National Academy of Sciences, Nauky ave. 60, Kharkiv, 61001, Ukraine, ORCID: https://orcid.org/0000-0003-0461-749X, yanovsky@isc.kharkov.ua

ANALYSIS OF SEARCH AND MULTI-AGENT ALGORITHMS
IN THE PAC-MAN GAME

This paper examines the performance of search and multi-agent algorithms within the context of the Pac-Man game. The game is used as a platform to simulate autonomous system management tasks, where an agent must complete missions in a two-dimensional space while avoiding dynamic obstacles. Classical search algorithms such as A* and BFS, along with multi-agent approaches like Alpha-Beta, Expectimax, and Monte Carlo Tree Search (MCTS), are analyzed in terms of their effectiveness under different maze complexities and game conditions. The study explores how maze size, ghost behaviors, and environmental dynamics influence the performance of each algorithm, particularly in terms of execution time, score, and win percentage.

Download full text! (On English)

Keywords: search algorithms, multi-agent algorithms, Pac-Man, path optimization, Alpha-Beta, Expectimax, MCTS.

1. Foderaro, G., Swingler, A., Ferrari, S. (2017). “A Model-Based Approach to Optimizing Ms. Pac-Man Game Strategies in Real Time.” IEEE Transactions on Computational Intelligence and AI in Games, 9 (2), pp. 153−165.
   https://doi.org/10.1109/TCIAIG.2016.2523508
2. Rohlfshagen, P., Liu, J., Perez-Liebana, D., Lucas, S.M. (2018). “Pac-Man Conquers Academia: Two Decades of Research Using a Classic Arcade Game.” IEEE Transactions on Games, 10 (3), pp. 233−256.
   https://doi.org/10.1109/TG.2017.2737145
3. Gallagher, M., Ryan, A. (2003). “Learning to play Pac-Man: an evolutionary, rule-based approach.” The 2003 Congress on Evolutionary Computation, Canberra, ACT, Australia, Vol. 4, pp. 2462-2469.
   https://doi.org/10.1109/CEC.2003.1299397
4. Foderaro, G., Raju, V., Ferrari, S. (2011) “A cell decomposition approach to online evasive path planning and the video game Ms. Pac-Man.” IEEE International Symposium on Intelligent Control, Denver, CO, USA, pp. 191−197.
   https://doi.org/10.1109/ISIC.2011.6045414
5. Tucnik, P., Nachazel, T., Cech, P., Bures, V. (2018) “Comparative analysis of selected path-planning approaches in large-scale multi-agent-based environments.” Expert Systems with Applications, 113, pp. 415−427.
   https://doi.org/10.1016/j.eswa.2018.07.001
6. Sajid, Q., Luna, R., Bekris, K. (2012) “Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives.” Proceedings of the 5th Annual Symposium on Combinatorial Search, pp. 88−96.
   https://doi.org/10.1609/socs.v3i1.18243
7. Saccon, E., Palopoli, L., Roveri, M. (2023) “Comparing Multi-Agent Path Finding Algorithms in a Real Industrial Scenario.” In: Dovier, A., Montanari, A., Orlandini, A. (eds) AIxIA 2022 – Advances in Artificial Intelligence. Lecture Notes in Computer Science, vol 13796. Springer, Cham. DOI:
   https://doi.org/10.1007/978-3-031-27181-6_13
8. Erdem, E., Kisa, D., Oztok, U., Schuller, P. (2013) “A General Formal Framework for Pathfinding Problems with Multiple Agents.” Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI-2013.
   https://doi.org/10.1609/aaai.v27i1.8592
9. Hewawasam, H., Ibrahim, Y., Appuhamillage, G. (2022) “Past, Present and Future of Path-Planning Algorithms for Mobile Robot Navigation in Dynamic Environments.” IEEE Open Journal of the Industrial Electronics Society, 3 (1), pp. 353−365.
   https://doi.org/10.1109/OJIES.2022.3179617
10. Lu, Y., Huo, X., Arslan, O., Tsiotras, P. (2012) “Incremental Multi-Scale Search Algorithm for Dynamic Path Planning With Low Worst-Case Complexity.” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 41, pp. 1556−1570.
    https://doi.org/10.1109/TSMCB.2011.2157493
11. Saffidine, A., Finnsson, H., Buro, M. (2012) “Alpha-Beta Pruning for Games with Simultaneous Moves.” Proceedings of the National Conference on Artificial Intelligence, no 1.
12. Lee, S. (2019) “Exploring to Learn Winning Strategy.” International Conferences Interfaces and Human Computer Interaction, Game and Entertainment Technologies, and Computer Graphics, Visualization, Computer Vision and Image Processing, pp. 377−380.
    https://doi.org/10.33965/g2019_201906C052
13. Dam, T., D’Eramo, C., Peters, J., Pajarinen, J. (2022) “A Unified Perspective on Value Backup and Exploration in Monte-Carlo Tree Search.” ArXiv abs/2202.07071
14. Mirsoleimani, S. A., Plaat, A., van den Herik, J., Vermaseren, J A.M. (2015) “Ensemble UCT Needs High Exploitation.” ArXiv abs/1509.08434.
    https://doi.org/10.5220/0005711603700376
15. Felner, A., Stern, R., Shimony, S.E., Boyarski, E., Goldenberg, M., Sharon, G., Sturtevant, N. R., Wagner, G., Surynek, P. (2021) “Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges.” Symposium on Combinatorial Search. DOI:
    https://doi.org/10.1609/socs.v8i1.18423
16. Khandelwal, P., Liebman, E., Niekum, S., Scott, A., Stone, P. (2016) “On the Analysis of Complex Backup Strategies in Monte Carlo Tree Search.” International Conference on Machine Learning, pp. 1319−1328.
17. Ou, T., Cao, J., Lu, Y., Wang, Y.-P., Wu, X. (2023) “A New Decision-Making Approach via Monte Carlo Tree Search and A2C.” 2023 3rd International Conference on Computer Science, Electronic Information Engineering and Intelligent Control Technology (CEI), pp. 204−210. DOI:
    https://doi.org/10.1109/CEI60616.2023.10527918
18. Silva, M. A. L., Souza, S. R. de, Freitas Souza, M. J., Felizardo de França Filho, M. (2018) “Hybrid metaheuristics and multi-agent systems for solving optimization problems: A review of frameworks and a comparative analysis.” Applied Soft Computing, 71, pp. 433−459. DOI:
    https://doi.org/10.1016/j.asoc.2018.06.050

Received 21.08.2024