Interpreting Multi-objective Evolutionary Algorithms via Sokoban Level Generation

Qingquan Zhang, Yuchen Li, Yuhang Lin, Handing Wang, Jialin Liu

Abstract

Multi-objective Evolutionary Algorithms (MOEAs) are essential for solving complex optimization problems with conflicting goals, yet they often remain "black boxes" to students and researchers. This paper presents an interactive, web-based platform that utilizes the procedural generation of Sokoban game levels to demystify MOEA mechanics. By visualizing the real-time trade-offs between level emptiness and spatial diversity, the tool provides a tangible medium for understanding how evolutionary strategies navigate the Pareto front.

Introduction

Multi-objective optimization problems (MOPs)—scenarios where one must balance competing objectives such as cost versus safety or speed versus efficiency—are ubiquitous in engineering and artificial intelligence. While MOEAs are powerful tools for navigating these trade-offs, their internal logic is often difficult to visualize and intuitively grasp.

The authors identify a significant pedagogical gap between abstract algorithmic theory and practical intuition. To bridge this gap, they propose using Procedural Content Generation (PCG) in games as an educational testbed. Because game levels are inherently visual, they serve as an ideal proxy for mathematical fitness functions. Specifically, this work focuses on generating levels for Sokoban—a classic puzzle game involving pushing boxes onto targets—to demonstrate how algorithms balance minimalist design with structural complexity.

Methodology: The Two_Arch2 Algorithm

The platform is built around Two_Arch2, a high-performing MOEA designed to maintain a delicate balance between finding optimal solutions and exploring diverse possibilities. Unlike standard algorithms that may converge too quickly on a single type of solution, Two_Arch2 utilizes two distinct archives:

  • Convergence Archive (CA): This archive focuses on pushing the population toward the Pareto front, the set of solutions where no objective can be improved without degrading another.
  • Diversity Archive (DA): This archive ensures the algorithm maintains a wide variety of solutions, preventing it from becoming trapped in local optima and ensuring a broad exploration of the search space.

Fitness Functions

To evolve the Sokoban levels, the authors define two conflicting objectives:

  1. Emptiness ($f_{emp}$): This measures the percentage of empty tiles within a level, favoring minimalist, open designs.
  2. Spatial Diversity ($f_{div}$): An entropy-based metric that calculates how empty spaces are distributed across different segments of the level, favoring complex or asymmetrical layouts.

The interaction between these two functions creates a clear multi-objective challenge: a perfectly empty level has low spatial diversity, while a highly diverse level cannot be perfectly empty.

The Interactive Platform

The web-based tool (available at aingames.cn) visualizes the entire evolutionary pipeline. Users can observe the chromosome representation (the underlying grid encoding), mating selection, crossover, mutation, and survivor selection in real-time. This transparency transforms "black box" operations into observable, animated processes.

Key features of the platform include:

  • Real-time Pareto Visualization: A live scatter plot shows the "evolutionary frontier," allowing users to see how the population shifts as the algorithm balances $f_{emp}$ and $f_{div}$.
  • Playable Outcomes: Users can select any generated level from the Pareto front and play it immediately. This provides a qualitative "feel" for the math, showing how different fitness scores translate into actual gameplay experiences.
  • Customizable Parameters: Users can modify level dimensions and population sizes to see how the algorithm adapts its search strategy to different constraints.

Discussion and Insights

The project highlights the utility of PCG as a Pedagogical Bridge. By translating abstract mathematical trade-offs into visual game layouts, the platform makes the concept of the Pareto front immediately accessible. For example, a user can see that one end of the frontier produces sparse, simple rooms, while the other produces dense, chaotic puzzles.

Furthermore, the implementation of Dual Archives demonstrates the necessity of diversity in optimization. The Diversity Archive acts as a safeguard, ensuring that the generator does not simply find one "good" level and repeat it, but instead explores the full spectrum of possible Sokoban designs.

Conclusion

The authors have successfully developed a functional resource for MOEA education. By closing the loop between mathematical optimization and interactive gameplay, the platform serves as a valuable tool for researchers and educators to demonstrate complex AI mechanics without requiring deep programming knowledge.

Future work aims to expand the platform by including a wider variety of MOEAs for comparative study and applying the generative framework to other game genres. Additionally, the authors plan to conduct formal user studies to quantify the tool's effectiveness in a classroom setting.

Summary updated

BibTeX
@inproceedings{zhang2024interpreting,
  author = {Qingquan Zhang and Yuchen Li and Yuhang Lin and Handing Wang and Jialin Liu},
  title = {{Interpreting Multi-objective Evolutionary Algorithms via Sokoban Level Generation}},
  booktitle = {CoG},
  year = {2024},
  doi = {10.1109/cog60054.2024.10645559},
}
Figure