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.