Learning Macromanagement in Starcraft by Deep Reinforcement Learning

Wenzhen Huang, Qiyue Yin, Junge Zhang, Kaiqi Huang

TL;DR

This paper tackles the complex "macromanagement" problem in StarCraft, which involves deciding which units to build. They propose a novel deep reinforcement learning algorithm, MA3C, that uses LSTM to handle imperfect information and asynchronous training to speed up learning. Their approach achieves high win rates against strong opponents, demonstrating effective learning of adaptive strategies.

What Problem Does This Paper Address?

StarCraft is a real-time strategy (RTS) game renowned for its complexity, featuring a vast state space, high-dimensional control, and partial observability (the "fog of war"). While AI has made strides in games like Go and even StarCraft II (e.g., AlphaStar), these often require immense computational resources. This paper focuses on decomposing StarCraft's challenges, specifically "macromanagement," which is crucial for strategic success. Macromanagement involves selecting appropriate units to build based on the current game state, resources, and technologies. Traditional methods rely heavily on expert knowledge and significant development time. Existing AI approaches, like supervised learning from replays, can be limited by the dependency on other AI modules (e.g., micromanagement). Reinforcement learning (RL) offers a promising avenue to learn these decisions without explicit expert programming, adapting to the game's dynamics and the opponent's strategy.

Methods

The authors propose a novel deep reinforcement learning algorithm called Mean Asynchronous Advantage Actor-Critic (MA3C). Key innovations include:

  • Handling Imperfect Information: They employ a Long Short-Term Memory (LSTM) network to encode a history queue of observations and actions. This allows the agent to infer the current state more accurately, mitigating the "fog of war" problem.
  • Improved Policy Gradient: MA3C computes an approximate expected policy gradient instead of the gradient of a sampled action. This aims to reduce gradient variance, leading to more stable and efficient training.
  • Asynchronous Training: Inspired by A3C, MA3C uses multiple parallel RL agents (workers) that train asynchronously. This significantly reduces the overall training time, a critical factor for complex games like StarCraft.
  • Action Space Reduction: To make learning more efficient, the action space for macromanagement is reduced to three key Zerg units: Zergling, Hydralisk, and Mutalisk. Building decisions in the early game are handled by a fixed opening strategy.
  • Reward Structure: A simple reward system is used: +1 for winning, -1 for losing. This avoids the need for expert-defined intermediate rewards.

Datasets

The paper does not introduce new datasets. Instead, it uses the StarCraft game environment itself for training and evaluation. The opponent bot used for training and testing is Steamhammer-1.2.3, an open-source StarCraft bot. For evaluation, the agent is trained against specific Steamhammer configurations and then tested against six different Steamhammer bots with varying opening strategies to assess generalization.

Key Insights and Ideas

  • History Matters: The success of the LSTM in encoding past observations and actions highlights the importance of temporal context in RTS games, especially when dealing with partial observability.
  • Adaptive Strategy Learning: The learned policy isn't just a static build order; it dynamically adjusts unit production based on the game state, opponent's actions, and even the capabilities of other AI modules within the bot.
  • Visualization as a Tool: The use of t-SNE to visualize state features colored by time, value, and policy provides a powerful way to understand the learned agent's behavior and decision-making process.
  • Cooperation with Other Modules: The paper emphasizes that the learned macromanagement strategy is not developed in isolation but is implicitly adapted to work in conjunction with other components of the AI bot (e.g., micromanagement).

Key Results

  • High Win Rates: MA3C achieves approximately 90% win rate against weaker opponents and improves win rates by about 30% against stronger opponents.
  • Generalization: An agent trained against one Steamhammer configuration demonstrates significant win rate improvements when tested against different Steamhammer bots with unseen opening strategies, indicating good generalization ability.
  • Efficiency: The asynchronous training approach significantly reduces the time required to train a competitive agent.
  • Policy Adaptation: Visualizations show the agent shifting its production strategy (e.g., favoring Mutalisks early, then balancing with Zerglings) based on game progression and perceived threats.

Limitations and Future Work

  • Q-value Estimation Bias: The effectiveness of MA3C's policy gradient is tied to the accuracy of Q-value estimation. Biases in these estimations can lead to a larger policy gradient bias compared to standard A3C.
  • Limited Exploration: The current exploration mechanism (entropy regularization) might be insufficient for extremely challenging scenarios or against highly capable opponents, potentially leading to complex learned policies that are hard to explore.
  • Future Work: The authors suggest exploring ensemble Q-networks or weighted Q-estimates to reduce Q-value estimation biases and improve stability. They also aim to enhance exploration capabilities to better handle stronger opponents and more complex scenarios.

Summary updated

BibTeX
@inproceedings{huang2021learning,
  author = {Wenzhen Huang and Qiyue Yin and Junge Zhang and Kaiqi Huang},
  title = {{Learning Macromanagement in Starcraft by Deep Reinforcement Learning}},
  booktitle = {Sensors},
  year = {2021},
  url = {https://openreview.net/forum?id=1X3X8y0oyL},
}
Figure