The art of drafting: a team-oriented hero recommendation system for multiplayer online battle arena games

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

TL;DR

This paper tackles the complex hero drafting phase in Multiplayer Online Battle Arena (MOBA) games by framing it as a combinatorial game. They propose a novel recommendation system using Monte Carlo Tree Search (MCTS) to suggest heroes that maximize a team's win probability, demonstrating significantly better performance than existing methods.

What Problem Does This Paper Address?

Multiplayer Online Battle Arena (MOBA) games, like League of Legends and DOTA 2, are incredibly popular and involve two teams of five players each selecting unique "heroes" from a large roster. The hero selection, or "draft," is a critical pre-game phase where teams aim to pick heroes that synergize well with their own team and counter the opponent's choices. This is a highly complex task due to the intricate relationships between hundreds of heroes, leading to a vast number of possible team compositions. Poor drafting can lead to player frustration and a negative gaming experience. Existing approaches often rely on historical pick frequencies or simple association rules, which are myopic and don't fully account for the sequential, strategic nature of the draft. This paper aims to solve this by developing a system that can make optimal hero recommendations to maximize a team's chance of victory.

Methods

The core of the paper's contribution lies in modeling the hero drafting process as a combinatorial game. Specifically, it's framed as a two-player, zero-sum game with perfect information. The authors then employ Monte Carlo Tree Search (MCTS), a powerful search algorithm for games with large state spaces, to find the optimal hero pick at each step.

The MCTS implementation uses the Upper Confidence Bound applied to Trees (UCT) algorithm. The process involves:

  • Selection: Traversing the search tree based on a UCB1 criterion to balance exploration of new hero picks and exploitation of promising ones.
  • Expansion: Adding a new node to the tree when an unvisited action (hero pick) is taken.
  • Simulation (Rollout): Playing out the rest of the draft using a default policy (initially random) until a terminal state (a complete team lineup) is reached.
  • Backpropagation: Updating the values of nodes in the tree based on the outcome of the simulation.

The "reward" for MCTS is a predicted team win rate, which is generated by a separate machine learning model trained on historical match data. This win rate predictor is crucial for evaluating the quality of a drafted hero lineup.

Datasets

The authors utilized a DOTA 2 match dataset collected between February and March 2016, containing approximately 3 million "Ranked All Pick" matches. This dataset was filtered to include only matches played at the "normal" skill level to reduce the impact of player skill variance. The dataset was used for two primary purposes:

  1. Training the Win Rate Predictor: A machine learning model was trained to predict the win probability of a given hero lineup.
  2. Simulation Experiments: The trained model and the dataset were used to simulate drafting scenarios and evaluate the performance of different recommendation strategies.

Key Insights and Ideas

  • Drafting as a Combinatorial Game: Framing the draft as a strategic, sequential game is key to applying advanced search techniques like MCTS. This moves beyond simple statistical correlations.
  • MCTS for Strategic Depth: MCTS's ability to explore future possibilities and backpropagate rewards is well-suited for the multi-step, strategic nature of hero drafting, where current picks influence future options.
  • Win Rate Predictor as Reward Function: Using a learned win rate predictor as the reward signal for MCTS allows the system to learn what constitutes a "good" team composition without explicit human-defined rules for hero synergy.
  • Generalizability to Different Modes: The MCTS approach is shown to be adaptable to different game modes, such as "Captain Mode," which includes hero banning, demonstrating its robustness.

Key Results

The paper's empirical evaluation, conducted through extensive simulations, showed that their MCTS-based hero recommendation system significantly outperforms baseline strategies.

  • Superior Win Rates: The UCT-based strategies consistently achieved higher predicted win rates compared to Random (RD), Association Rules (AR), and Highest Win Rate (HWR) strategies. For instance, the best UCT strategy (UCT1600,2-1) achieved a 61.1% win rate against HWR in "All Ranked" mode.
  • Scalability and Performance: The UCT-based strategies were computationally feasible, with average pick times well within the limits for real-time play.
  • Adaptability: In "Captain Mode," which is more complex due to hero bans, the UCT strategy still maintained its superiority, even showing a slight improvement in win rates compared to "All Ranked" mode.

Limitations and Future Work

The authors acknowledge several limitations and propose future research directions:

  • Player-Specific Information: The current system does not account for individual player skill or familiarity with specific heroes. Future work could integrate player skill data to 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 tree policy and default policy in MCTS, leading to more efficient and effective search.
  • Customization and Broader Applications: The system could be further customized for other drafting rules and extended to similar real-world scenarios, 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 Christopher 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