Аналіз ефективності алгоритмів прийняття рішень в умовах складних ігрових середовищ на прикладі Pac-Man
Артем Новіков, Володимир ЯновськийІгрові симуляції типу Pac-Man є важливим інструментом для тестування алгоритмів прийняття рішень в умовах, що імітують реальні сценарії. Це відкриває нові можливості для розробки автономних систем, які можуть адаптуватися до мінливих умов навколишнього середовища та взаємодіяти з іншими агентами. Метою цієї роботи було порівняння алгоритмів Expectimax, Monte Carlo Tree Search та Alpha-Beta Pruning у змінених умовах гри Pac-Man для визначення найбільш ефективного підходу до прийняття рішень у складних середовищах. Для цього було використано імітаційне моделювання для оцінки ефективності роботи агентів у різних ігрових лабіринтах, що відрізняються за складністю. У дослідженні вимірювалися такі показники, як кількість балів, час гри та відсоток виграшів, що дозволило оцінити ефективність алгоритмів у різних ситуаціях. Аналіз проведених експериментів продемонстрував, що алгоритм Монте-Карло є найбільш ефективним серед протестованих методів для вирішення менш складних лабіринтів, підтверджуючи його здатність швидко знаходити оптимальні шляхи в простих умовах. Алгоритм Alpha-Beta Pruning показав меншу ефективність, що вказує на необхідність його оптимізації для роботи в більш складних середовищах. Expectimax продемонстрував значно нижчу продуктивність, що свідчить про його обмежену придатність для складних ігрових лабіринтів. Дослідження показало, що збільшення складності лабіринтів значно знижує продуктивність усіх алгоритмів, особливо при більшій кількості перешкод, підкреслюючи важливість розробки більш стійких методів для роботи у високоскладних умовах. Оптимізація алгоритмів Монте-Карло та Alpha-Beta Pruning для роботи в складних середовищах може суттєво покращити їх результативність та зробити їх ефективними для реальних застосувань у навігації та керуванні рухомими пристроями. Результати цього дослідження можуть бути використані для розробки ефективних алгоритмів навігації для автономних транспортних засобів, дронів та інших робототехнічних систем, де адаптація до змін у складних умовах є критично важливою
Використані джерела
[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.