The Art of Drafting: A Team-Oriented Hero Recommendation System for Multiplayer Online Battle Arena Games

Zhengxing Chen, Truong-Huy D. Nguyen, Yuyu Xu, Chris Amato, Seth Cooper, Yizhou Sun, Magy Seif El-Nasr

TL;DR

This paper introduces a novel hero recommendation system for Multiplayer Online Battle Arena (MOBA) games that treats the hero selection process as a combinatorial game. By employing Monte Carlo Tree Search (MCTS), their system significantly improves team win rates compared to existing strategies, offering a more intelligent approach to drafting.

What Problem Does This Paper Address?

Multiplayer Online Battle Arena (MOBA) games, like League of Legends and DOTA 2, are incredibly popular e-sports where two teams of five players battle it out. A crucial, yet complex, part of these games is the "draft" or "pick" phase, where players select their in-game characters (heroes) before the match begins. With over 100 heroes available, each with unique strengths and weaknesses, and intricate synergistic and counter-play relationships between them, choosing the optimal team composition is a monumental challenge. Poor drafting can lead to frustration, reduced enjoyment, and even toxic behavior among players. This paper tackles the problem of how to systematically recommend hero picks that maximize a team's chances of winning, moving beyond simple player tendencies or basic win-rate heuristics.

Methods

The core of this paper's contribution lies in framing the MOBA drafting process as a combinatorial game. Specifically, they model it as a two-person, zero-sum game with perfect information. To solve this complex game and find optimal hero picks, they leverage Monte Carlo Tree Search (MCTS), a powerful heuristic search algorithm.

The MCTS approach involves iteratively building a search tree. The process consists of four key steps:

  1. Selection: Traversing the existing tree to find the most promising node using the Upper Confidence Bound (UCB1) criterion, balancing exploration of new options with exploitation of known good ones.
  2. Expansion: Adding a new child node to the tree when an unvisited action is taken from a selected node.
  3. Simulation (Rollout): Playing out the rest of the game from the newly expanded node using a default policy (initially random) until a terminal state is reached.
  4. Back-propagation: Updating the statistics of nodes along the path from the terminal state back to the root with the outcome of the simulation.

This iterative process allows MCTS to estimate the value of different hero combinations without needing to explore the entire massive game tree. A key aspect is the reward function, which is a predicted team win rate for a given hero line-up, trained using a machine learning model.

Datasets

The authors utilized a large dataset of DOTA 2 matches collected between February and March 2016. This dataset comprised approximately 5 million "Ranked All Pick" matches. To mitigate the influence of player skill, they specifically extracted a subset of matches played by players in the "normal skill level." This dataset was used for two primary purposes:

  • Training the Win Rate Predictor: A machine learning model was trained on this data to predict the probability of a team winning based on its hero line-up.
  • Simulation Experiments: The dataset served as the basis for simulating drafting scenarios to evaluate the performance of their proposed recommendation system against various baseline strategies.

Key Insights and Ideas

  • Drafting as a Game: Framing the hero selection as a combinatorial game provides a rigorous mathematical foundation for developing optimal strategies, moving beyond empirical observations.
  • MCTS for Strategic Depth: MCTS proves to be a highly effective technique for navigating the enormous search space of MOBA drafts. Its ability to balance exploration and exploitation allows it to discover strong hero combinations that might be missed by simpler, myopic approaches.
  • Win Rate Prediction as Reward: Using a machine learning model to predict win rates as the reward signal for MCTS is crucial. This allows the system to learn complex hero interactions and synergies that are not easily quantifiable.
  • Generality of MCTS: The paper demonstrates that the MCTS approach is adaptable to different game modes (e.g., "Captain Mode" with bans) and can handle increased complexity, suggesting its broad applicability in similar strategic decision-making scenarios.

Key Results

The empirical evaluation, conducted through extensive simulations, showed that hero teams drafted by their MCTS-based recommendation system achieved significantly higher win rates compared to teams constructed by baseline and state-of-the-art strategies.

  • "All Ranked" Mode: When compared to strategies like Random (RD), Association Rules (AR), and Highest Win Rate (HWR), their UCT-based strategies, particularly with sufficient iterations (e.g., UCT1600,2-1), consistently outperformed them. For instance, UCT1600,2-1 achieved a 61.1% win rate against HWR.
  • "Captain Mode" (with bans): The MCTS approach also demonstrated superiority in the more complex "Captain Mode," where hero bans are involved. The strength order of strategies remained consistent, with UCT-based methods outperforming others, and the win rate improvements were even more pronounced in this more sophisticated setting.
  • Efficiency: The UCT-based strategies were computationally efficient, with average wall times per pick being a small fraction of the time limit for human players, making them feasible for real-time online deployment.

Limitations and Future Work

The authors acknowledge several limitations and propose promising future directions:

  • Player-Specific Information: The current system does not account for individual player skill or familiarity with specific heroes. Future work could integrate player information to further personalize recommendations.
  • Hero Pick Sequences: If historical hero pick sequences were readily available (they are not easily accessible via official APIs), they could be used to improve the MCTS's tree policy and default policy, leading to more efficient and effective search.
  • Customization and Broader Applications: The system could be extended to account for additional drafting rules and mechanics, and its principles could be applied to other real-world scenarios involving strategic selection, such as player drafting in sports.

Summary updated

Abstract

Multiplayer Online Battle Arena (MOBA) games have received increasing popularity recently. In a match of such games, players compete in two teams of five, each controlling an in-game avatars, known as heroes, selected from a roster of more than 100. The selection of heroes, also known as pick or draft, takes place before the match starts and alternates between the two teams until each player has selected one hero. Heroes are designed with different strengths and weaknesses to promote team cooperation in a game. Intuitively, heroes in a strong team should complement each other's strengths and suppressing those of opponents. Hero drafting is therefore a challenging problem due to the complex hero-to-hero relationships to consider. In this paper, we propose a novel hero recommendation system that suggests heroes to add to an existing team while maximizing the team's prospect for victory. To that end, we model the drafting between two teams as a combinatorial game and use Monte Carlo Tree Search (MCTS) for estimating the values of hero combinations. Our empirical evaluation shows that hero teams drafted by our recommendation algorithm have significantly higher win rate against teams constructed by other baseline and state-of-the-art strategies.
BibTeX
@inproceedings{chen2018art,
  author = {Zhengxing Chen and Truong-Huy D. Nguyen and Yuyu Xu and Chris Amato and Seth Cooper and Yizhou Sun and Magy Seif El-Nasr},
  title = {{The Art of Drafting: A Team-Oriented Hero Recommendation System for Multiplayer Online Battle Arena Games}},
  booktitle = {RecSys},
  year = {2018},
  doi = {10.1145/3240323.3240345},
}

Loading related content...

Figure