EXPLORING THE LIMITS OF MCTS IN PAC-MAN: MAZE SIZE, SIMULATIONS, AND PERFORMANCE

Abstract

This paper explores the performance and limitations of Monte Carlo Tree Search (MCTS) when applied to the Pac-Man game, with a particular focus on how maze complexity and the number of simulations affect the agent’s decision-making process. The game serves as a dynamic environment where the MCTS agent must navigate mazes filled with rewards (capsules and food) and avoid adversarial agents (ghosts), creating a challenging testbed for decision-making algorithms.

The primary objective of this work is to assess the efficiency of MCTS across mazes of varying sizes and configurations, from small, optimized layouts to large, non-optimized ones. We aim to understand the trade-offs between computational resources (e.g., number of simulations) and the agent's overall performance, particularly in terms of score, win rate, and decision-making time. The experiments were conducted using different numbers of simulations per move, allowing the MCTS agent to build decision trees that guide its actions. This enabled us to observe how performance metrics evolve as the complexity of the environment increases.

The findings indicate that MCTS performs effectively in smaller, optimized mazes where paths are clearer, and the decision space is more manageable. However, as maze complexity grows—particularly in non-optimized environments filled with obstacles and unpredictable paths—the agent's performance deteriorates. A key insight is that increasing the number of simulations does improve decision quality to an extent, but only up to a point; beyond that, additional simulations incur a computational overhead that does not yield proportional gains in performance. Moreover, the experiments reveal that optimized maze designs allow the MCTS agent to make more informed and efficient decisions, while non-optimized mazes exacerbate the agent’s struggle with unpredictability and more complex decision spaces. These findings underscore the limitations of MCTS in handling dynamic and irregular environments.

Key conclusions include the necessity of enhancing MCTS for complex scenarios by incorporating more advanced heuristic functions to evaluate game states more accurately, along with adaptive simulation strategies to better manage computational resources. Additionally, combining MCTS with reinforcement learning or neural networks could offer more robust solutions for tackling the growing complexity of both in-game and real-world environments. This research highlights several promising avenues for future exploration, particularly in applying MCTS to more intricate AI challenges such as autonomous navigation and real-time decision-making in robotics.