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:
- Training the Win Rate Predictor: A machine learning model was trained to predict the win probability of a given hero lineup.
- 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