Seeding the Future: Boosting Rolling Horizon Evolution in General Video Game Playing

TL;DR

Researchers have found a mid-point between pure randomness and exhaustive search: Population Seeding. By "priming" the Rolling Horizon Evolutionary Algorithm (RHEA) with a seed from Monte Carlo Tree Search (MCTS) or One Step Look Ahead (1SLA), agents can achieve expert-level performance in video games even with very small populations and short decision horizons.

Background: The Battle for Real-Time Efficiency

In the world of General Video Game Playing (GVGP), two titans usually clash: Monte Carlo Tree Search (MCTS) and Rolling Horizon Evolutionary Algorithms (RHEA).

• MCTS builds an asymmetrical tree, favoring promising moves.
• RHEA evolves a sequence of actions (individuals), constantly shifting its "horizon" as the game progresses.

While MCTS has historically dominated, RHEA offers a simpler, more flexible framework. However, RHEA suffers from a "cold start" problem—it usually starts with a random population. If the first generation is garbage, the evolution rarely has enough time (usually just 40ms) to find the diamond in the rough.

The Core Insight: Better Seeds, Better Harvests

The authors of this paper argue that we shouldn't leave the first generation to chance. They propose Seeding:

1. 1SLA Seeding: Use a greedy one-step look-ahead to pick the best immediate action and build an individual around it.
2. MCTS Seeding: Use half of your time budget to run a mini-MCTS, extract the "best" path found so far, and use that as the Alpha individual of your evolutionary population.

The logic is robust: give evolution a "warm start" in a high-value area of the search space, and let the mutation/crossover operators refine that solution rather than wandering blindly through the dark.

The UCB1 formula used during the MCTS seeding phase to balance exploration and exploitation.

Methodology: Testing Under Pressure

The researchers didn't just test this on one game; they used 20 games from the GVGAI corpus, ranging from deterministic puzzles to stochastic shooters like Aliens and Chopper. They varied two critical parameters:

• Population Size (P): How many action sequences are evolved.
• Individual Length (L): How far into the future the agent looks.

Experimental Results: A Performance Surge

The results were striking. The C-MCTS-S (MCTS Seeded RHEA) was the clear winner.

• Small Budget Superiority: Seeding helps most when the budget is tight (Small P and L). When resources are scarce, a random start is often fatal.
• Winning the Unwinnable: In games like Chopper, the MCTS seeding variant reached a 100% win rate, whereas the vanilla version struggled at 26%.
• Consistency: MCTS seeding outperformed vanilla RHEA in 80% of the games in terms of score.

A snapshot of results across various games. Notice the significant 'A, B' indicators showing C-MCTS-S outperforming its counterparts.

Critical Analysis & Conclusion

Why does this work?

Evolutionary algorithms are essentially "local" searchers. By providing a seed from a "global" (or at least more informed) searcher like MCTS, we provide the Inductive Bias needed to ignore 99% of useless game states.

Limitations

The authors noted a "ceiling effect." As the population size grows very large, the benefit of seeding decreases. Why? Because a large random population eventually covers enough of the search space that a single "good seed" matters less. However, in real-time gaming, we almost never have the luxury of large populations.

The Takeaway

This research proves that the future of Game AI isn't just "MCTS vs. RL" or "Evolution vs. Deep Learning." The real wins come from hybridization. By using MCTS to "inform" RHEA, we get the best of both worlds: the strategic depth of tree search and the rapid, flexible refinement of evolution.

Editor's Note: This work highlights a shift toward "Informed Evolution," a trend we expect to see more of as real-time constraints in complex simulations become even tighter.