Efficient Parallel Design for Self-Play in Two-Player Zero-Sum Games

Hongsong Tang, Bo Chen, Yingzhuo Liu, Kuoye Han, Jingqian Liu, Zhaowei QuSymmetry 2025 · DOI

TL;DR

This paper introduces the Mixed Hierarchical Oracle (MHO), a novel framework that significantly improves the efficiency and performance of self-play algorithms in complex two-player zero-sum games. MHO addresses computational inefficiencies in parallelized learning by better utilizing interaction data, consolidating resources, and intelligently balancing exploration and exploitation across a hierarchy of agents.

What Problem Does This Paper Address?

Self-play has become a dominant paradigm for achieving superhuman performance in complex games like Go, Chess, and StarCraft. The core idea is to train an agent by having it play against itself (or past versions of itself), which naturally creates a stable learning environment. However, scaling self-play to more complex games with vast strategy spaces presents significant computational challenges.

Existing approaches often involve parallelizing the learning process to speed things up. A prominent method is the Policy Space Response Oracle (PSRO) and its parallelized variants (P-PSRO, PSRO-rN). While these methods improve training, they suffer from inefficiencies:

  • Suboptimal Resource Utilization: Parallel learners often don't effectively share or utilize the data generated during interactions, leading to wasted computation. For instance, in P-PSRO, data from high-level policies playing against low-level ones isn't always used to train the low-level policies.
  • Cold-Start Problems: When new policies are introduced, they might start from scratch, leading to slow initial learning.
  • Balancing Exploration and Exploitation: Effectively exploring the vast strategy space while also exploiting learned knowledge is crucial but difficult to manage, especially in a hierarchical setting.

This paper aims to tackle these inefficiencies by proposing a more integrated and intelligent approach to parallelized self-play.

Methods

The paper introduces the Mixed Hierarchical Oracle (MHO) framework, built upon three key innovations:

  1. Parallelized Oracle (PO): This component addresses the data utilization issue. Unlike previous methods that might discard data from lower-level policies, PO ensures that interaction data generated between any two active policies (regardless of their hierarchical level) is used for training both participating policies. This effectively leverages cross-level interaction data, speeding up learning. It also maintains a fixed set of policies alongside the active ones, which helps stabilize training.
  2. Model Soups (MS): To combat the "cold-start" problem and consolidate fragmented computational resources, MS is employed. When a new, higher-level policy is introduced, it's initialized not from scratch, but by fusing the parameters of existing lower-level policies and fixed policies. This "soup" of parameters provides a strong, pre-trained foundation, enabling faster learning and better performance from the outset.
  3. Hierarchical Exploration (HE): This mechanism intelligently balances exploration and exploitation across the hierarchy of policies. Higher-level policies are encouraged to explore more (using an entropy regularization term in their objective function), while lower-level policies are geared towards exploitation. As training progresses, the exploration intensity is dynamically adjusted, allowing agents to discover new strategies early on and refine them later.

These three components are integrated to work synergistically, aiming to optimize compute resource utilization and improve overall training efficiency and strategic performance.

Datasets

The MHO framework is evaluated on two main environments:

  • AlphaStar888: This is a pre-existing matrix game derived from StarCraft II, featuring a payoff table with 888 policies. It serves as a benchmark for evaluating exploitability in a single-step, zero-sum game.
  • MiniStar: This is a newly introduced open-source environment designed specifically for self-play research in tactical combat scenarios. It's a simplified variant of the StarCraft II Multi-Agent Challenge (SMACv2). Unlike SMACv2, which trains agents against built-in bots, MiniStar allows for two learning agents to compete against each other, enabling true self-play. By focusing on smaller-scale skirmishes rather than full RTS gameplay, MiniStar reduces complexity and engineering overhead, making it a more accessible platform for studying self-play algorithms.

Key Insights and Ideas

  • Data is King (and Should Be Shared): The PO's core insight is that interaction data in parallel self-play is valuable for all participating agents, not just the higher-level ones. This simple but effective redistribution significantly boosts sample efficiency.
  • Leveraging Collective Wisdom: Model Soups demonstrate that combining existing policies into a new one isn't just about averaging; it's about creating a more robust starting point that inherits the strengths of its predecessors, mitigating the slow ramp-up of new agents.
  • Exploration with a Purpose: Hierarchical Exploration shows that a structured approach to exploration, where different levels of the hierarchy have different exploration strategies, can lead to more effective discovery and refinement of complex strategies.
  • Synergy is Key: The ablation studies strongly suggest that the MHO's components are not just additive; they work together synergistically to achieve superior results. Removing any single component leads to a noticeable performance degradation.

Key Results

  • AlphaStar888: The MHO algorithm consistently achieved the lowest exploitability compared to baseline methods (PSRO, P-PSRO, PSRO-rN, SP) over training iterations, indicating superior strategic performance.
  • MiniStar: In pairwise matches across three races (Protoss, Zerg, Terran) in 5v5 settings, MHO consistently outperformed all baseline methods, achieving the highest expected win rates.
  • Faster Convergence: Ablation studies and comparisons with PO-PSRO show that the PO component, in particular, leads to faster convergence in the early stages of training.
  • Improved Performance: The MHO consistently demonstrated superior final performance and faster improvements compared to configurations missing one or more of its core components.

Limitations and Future Work

  • Limitations: The paper acknowledges that while MHO improves efficiency, the computational demands of complex self-play are still significant. The current MiniStar environment, while useful, focuses on tactical engagements and could be expanded to include more environmental factors like terrain for richer strategy exploration.
  • Future Work: The authors suggest several promising directions:
  • Integrating Parallel Training and Distributed RL: Further enhancing the framework by combining parallel training with distributed RL parallel sampling for even greater efficiency.
  • Theoretical Guarantees: Optimizing the parallelized framework while ensuring strict theoretical guarantees for convergence.
  • Expanding MiniStar: Introducing more diverse training scenarios and environmental factors into MiniStar to create a richer simulation environment for two-player zero-sum game research.
  • Exploring Strategy Diversity: Investigating ways to introduce more diverse training scenarios to encourage broader strategy exploration.

Summary updated

Abstract

Self-play methods have achieved remarkable success in two-player zero-sum games, attaining superhuman performance in many complex game domains. Parallelizing learners is a feasible approach to handle complex games. However, parallelizing learners often leads to the suboptimal exploitation of computational resources, resulting in inefficiencies. This paper introduces the Mixed Hierarchical Oracle (MHO), which is designed to enhance training efficiency and performance in complex two-player zero-sum games. MHO efficiently leverages interaction data among parallelized solvers during the Parallelized Oracle (PO) process, while employing Model Soups (MS) to consolidate fragmented computational resources and Hierarchical Exploration (HE) to balance exploration and exploitation. These carefully designed enhancements for parallelized systems significantly improve the training performance of self-play. Additionally, MiniStar is introduced as an open source environment focused on small-scale combat scenarios, developed to facilitate research in self-play algorithms. The MHO is evaluated on both the AlphaStar888 matrix game and MiniStar environment, and ablation studies further demonstrates its effectiveness in improving the agent’s decision-making capabilities. This work highlight the potential of the MHO to optimize compute resource utilization and improve performance in self-play methods.
BibTeX
@inproceedings{tang2025efficient,
  author = {Hongsong Tang and Bo Chen and Yingzhuo Liu and Kuoye Han and Jingqian Liu and Zhaowei Qu},
  title = {{Efficient Parallel Design for Self-Play in Two-Player Zero-Sum Games}},
  booktitle = {Symmetry},
  year = {2025},
  doi = {10.3390/sym17020250},
}
Figure