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

Abstract

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 adaptation to changes in complex environments is critical.

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