TL;DR
This paper introduces DeltaDou, an AI that achieves expert-level performance in Doudizhu, a complex three-player imperfect information card game. It leverages a novel asymmetric Monte Carlo Tree Search (MCTS) and a deep reinforcement learning framework, demonstrating that self-play can significantly improve AI performance in multi-agent settings.
What Problem Does This Paper Address?
While AI has made significant strides in two-player perfect information games like chess and Go, imperfect information games, where players don't have complete knowledge of the game state, remain a significant challenge. Doudizhu, a popular Chinese card game with three players and hidden hands, exemplifies this difficulty. Existing approaches often struggle with the combinatorial explosion of possibilities and the need to infer opponents' hidden information. This paper aims to bridge this gap by developing an AI capable of mastering Doudizhu through self-play, reaching human expert levels.
Methods
DeltaDou's core innovation lies in its integration of two key techniques within an AlphaZero-like self-play framework:
- Fictitious Play MCTS (FPMCTS): This is a modified MCTS designed for imperfect information games. Instead of a single search tree, FPMCTS uses an asymmetric tree where each node represents a player's information set. This approach helps manage the state space explosion. Crucially, for the two "opponent" players, their moves are sampled from their own policy networks, rather than exploring all possibilities, which significantly speeds up the search.
- Policy-Based Inference Algorithm: To address the hidden information problem, DeltaDou incorporates an inference mechanism. This algorithm leverages the policy network to estimate the unobserved hands of other players. This is a departure from traditional methods that might rely on hand-crafted features, suggesting that learned policies are more effective in this context.
The self-play process involves these components: neural networks (policy-value networks) are used for inference and guiding the search. Each self-play episode generates game data, which is then used to update the neural networks, iteratively improving the AI's performance. To bootstrap the learning, an initial heuristic AI is used to generate a large dataset for supervised learning.
Datasets
The paper does not explicitly mention specific public datasets for training or evaluation. Instead, it relies on:
- Self-generated game data: The core of the training process involves the AI playing millions of games against itself. These games are generated with randomly dealt hands.
- Heuristic AI-generated data: An initial phase uses a hand-coded heuristic AI to play 200,000 games, generating data to bootstrap the neural network training.
- Benchmark programs: For evaluation, the paper compares DeltaDou against existing Doudizhu AI programs like XDou and RHCP, as well as human players.
Key Insights and Ideas
- Self-play is powerful for multi-agent imperfect information games: The paper demonstrates that even starting with a relatively weak AI, extensive self-play can lead to human-expert level performance in a complex game like Doudizhu.
- Asymmetric MCTS is key for managing information sets: FPMCTS effectively handles the challenge of multiple players with hidden information by focusing the search on individual information sets and sampling opponent actions.
- Learned policies are superior for inference: The authors found that using a policy network for inferring opponent hands was more effective than hand-crafted features, highlighting the power of deep learning for this task.
- Human-like play: The paper notes that DeltaDou's playing style is more similar to human players than other existing AIs, suggesting a more nuanced understanding of the game.
Key Results
- Human Expert Level Performance: DeltaDou achieved human expert level performance after days of self-play and training.
- Dominance over Baselines: DeltaDou significantly outperformed existing Doudizhu AI programs like RHCP and XDou in head-to-head tournaments. For instance, DeltaDou vs. RHCP had a 75% win rate with an ADP of +0.72, while DeltaDou vs. XDou had a 59% win rate with an ADP of +0.28.
- Comparable to Human Players: In experiments against human experts, DeltaDou achieved comparable strength, with an overall win rate of 48.5% and an ADP of -0.07 against a team of human winners.
- Inference Effectiveness: The agent with inference achieved a 54.5% win rate and +0.145 ADP against an agent without inference, demonstrating the crucial role of the inference mechanism.
Limitations and Future Work
- Initial Heuristic Dependency: The current training process relies on a hand-coded heuristic AI to bootstrap the learning. The authors aim to remove this dependency in future work, allowing training to start entirely from scratch.
- Opponent Modeling: While DeltaDou implicitly models opponents through self-play, explicit opponent modeling could further enhance its strength by exploiting weaknesses and better understanding teammates.
- Generalization to Other Games: The authors plan to adapt their framework to other imperfect information card games like bridge and skat, suggesting the potential for broader applicability.
- Occasional Missed Wins: The paper acknowledges that DeltaDou sometimes misses obvious straight wins that human players would spot, indicating room for improvement in strategic foresight.
Summary updated