Abstract
General Video Game AI (GVGAI) agents often struggle in environments with sparse rewards, where feedback is infrequent and the path to victory is unclear. This study explores Statistical Forward Planning (SFP) techniques, specifically Monte Carlo Tree Search (MCTS) and Rolling Horizon Evolutionary Algorithms (RHEA), to address this challenge. By implementing extreme rollout lengths and a novel dynamic length adjustment based on fitness landscape variance, the research demonstrates that increased lookahead significantly improves win rates in sparse and deceptive games. However, results also indicate a trade-off between long-term planning and immediate reaction, highlighting the need for adaptive search strategies in real-time gaming.
Introduction
Most General AI (GAI) agents rely on immediate feedback, such as score increases, to evaluate the quality of their actions. In "dense reward" games like Space Invaders or Aliens, every successful action provides a clear signal. Conversely, "sparse reward" games require an agent to perform hundreds of actions before receiving any points (e.g., navigating a complex maze). In these scenarios, standard algorithms like Monte Carlo Tree Search (MCTS) often fail because the lack of immediate rewards makes all potential actions appear equally unpromising. This paper addresses the need for agents that can "see" far enough into the future to identify distant rewards while remaining responsive to immediate, fast-paced threats.
Methodology
The authors focus on two primary Statistical Forward Planning (SFP) methods: Monte Carlo Tree Search (MCTS) and Rolling Horizon Evolutionary Algorithms (RHEA).
To overcome the sparse reward problem, two modifications were proposed:
- Extreme Length Rollouts: Simulation depth ($L$) was increased from a standard 14 steps to 200 steps. The computational budget (Forward Model calls) was increased proportionally to allow for deeper "lookahead" simulations.
- Dynamic Length Rollouts: This approach adjusts the search depth based on the "flatness" of the fitness landscape, measured by the standard deviation of scores found during the search. If the landscape is flat (low variance), the agent increases rollout length to find distant rewards. If the landscape is "busy" (high variance), it shortens rollouts to focus on immediate maneuvers.
Experimental Setup
The study utilized the General Video Game AI (GVGAI) framework. Agents were evaluated across 20 real-time games, categorized into "Sparse" (e.g., Camel Race, Escape) and "Dense" (e.g., Aliens, Butterflies). Additionally, five "Deceptive" games were included, which provide misleading rewards that lead agents away from the actual winning conditions.
Results and Key Insights
The experiments yielded several critical findings regarding the efficacy of extended lookahead:
- Performance Boost in Sparse Games: Increasing rollout length to 200 significantly improved win rates. MCTS win rates rose from 6.90% to 30.98%, while RHEA saw an increase from 25.59% to 37.04%.
- MCTS Dynamic Adaptation: The dynamic length adjustment was particularly successful for MCTS, improving its overall win rate from 40.40% to 44.04%. This suggests that MCTS can effectively transition between deep exploration and precise local control.
- RHEA Architecture Constraints: While RHEA generally outperformed MCTS in sparse environments, it struggled with dynamic length adjustments. The "shift buffer" used in RHEA to carry over action sequences between game ticks became inconsistent when sequence lengths changed frequently, disrupting the evolutionary process.
- Robustness to Deception: Longer lookaheads allowed agents to better navigate deceptive games by identifying that immediate small rewards might lead to eventual losses.
- The "Chopper" Trade-off: A notable performance drop occurred in the game Chopper when using extreme rollouts (win rate falling from 100% to 4%). This illustrates the risk of "over-planning," where an agent focused on distant goals ignores immediate, fatal obstacles.
Discussion and Future Work
While increasing rollout length proves effective for sparse rewards, it introduces significant computational costs. Current real-time constraints (typically 40ms per tick) make extreme lengths difficult to implement in practice. Future research may explore "macro-actions"—repeating a single action for multiple steps—to traverse state spaces more efficiently without increasing raw simulation depth. Additionally, finding ways to integrate dynamic lengths into RHEA without breaking the shift buffer remains a key challenge for improving evolutionary-based planning.
Summary updated