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:
- 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.
- Expansion: Adding a new child node to the tree when an unvisited action is taken from a selected node.
- 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.
- 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