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.