PaperlayerView exact revision on arXiv

Source-linked AI summary

DouZero: Mastering DouDizhu with Self-Play Deep Reinforcement Learning

Daochen Zha, Jingru Xie, Wenye Ma, Sheng Zhang, Xiangru Lian, Xia Hu, Ji Liu

arXiv:2106.06135v1cs.AIcs.LG

TL;DR

DouDizhu is an unsolved multi-agent reinforcement-learning problem with partial observability, cooperation, and a massive variable action space. DouZero combines deep neural networks, action encoding, and parallel actors with Monte-Carlo methods, and it achieves strong performance against existing DouDizhu systems after days of training. The paper argues that classical Monte-Carlo methods can work effectively in large, complex card games.

  • Problem

    DouDizhu challenges reinforcement learning with competition, cooperation, partial observability, huge state spaces, and up to 10^4 possible actions.

  • Method

    DouZero enhances Monte-Carlo methods with deep neural networks, action encoding, and parallel actors without human knowledge or state/action abstraction.

  • Results

    DouZero outperforms existing DouDizhu AI programs after days of training and is described as the strongest DouDizhu AI system up to date.

  • Takeaways & Limitations

    Classical Monte-Carlo methods can deliver strong results in large-scale card games requiring reasoning about competition and cooperation over huge state and action spaces.

  • Takeaways & Limitations

    The system does not yet incorporate bidding into reinforcement learning and leaves explicit modeling of Peasant collaboration for future work.

Abstract

from arXiv · show

Games are abstractions of the real world, where artificial agents learn to compete and cooperate with other agents. While significant achievements have been made in various perfect- and imperfect-information games, DouDizhu (a.k.a. Fighting the Landlord), a three-player card game, is still unsolved. DouDizhu is a very challenging domain with competition, collaboration, imperfect information, large state space, and particularly a massive set of possible actions where the legal actions vary significantly from turn to turn. Unfortunately, modern reinforcement learning algorithms mainly focus on simple and small action spaces, and not surprisingly, are shown not to make satisfactory progress in DouDizhu. In this work, we propose a conceptually simple yet effective DouDizhu AI system, namely DouZero, which enhances traditional Monte-Carlo methods with deep neural networks, action encoding, and parallel actors. Starting from scratch in a single server with four GPUs, DouZero outperformed all the existing DouDizhu AI programs in days of training and was ranked the first in the Botzone leaderboard among 344 AI agents. Through building DouZero, we show that classic Monte-Carlo methods can be made to deliver strong results in a hard domain with a complex action space. The code and an online demo are released at https://github.com/kwai/DouZero with the hope that this insight could motivate future work.

1. Introduction

DouDizhu poses a difficult multi-agent learning problem because players must compete and cooperate under partial observability with a very large, variable action space. DouZero addresses these challenges with a simple, domain-knowledge-free system that combines Monte-Carlo methods, deep networks, action encoding, and parallel actors.

  • DouDizhu combines competition, cooperation, partial observability, and an action space of up to 10^4 possible actions.
  • Earlier systems relied on human heuristics, action decomposition, Bayesian inference, or computationally expensive search.CQN could not beat simple heuristic rules after twenty days, while DeltaDou required more than two months of training.
  • DouZero avoids state and action abstraction and human knowledge by enhancing Monte-Carlo methods with deep neural networks, action encoding, and parallel actors.
  • Classical Monte-Carlo methods can deliver strong results in a large-scale card game requiring reasoning about both competition and cooperation.The system uses days of training on a single GPU server rather than the large computational resources required by some poker AI systems.

2. Background of DouDizhu

DouDizhu is a three-player shedding game in which two Peasants cooperate against a Landlord, making coordination and action selection central challenges. Its huge combination space includes many legal moves that vary with the hand and can make an apparently improper play lose the game.

  • DouDizhu is a three-player shedding game where two Peasants form a team against the Landlord.The Peasants win when either Peasant is first to empty their hand.
  • DouDizhu remains an unsolved multi-agent reinforcement-learning benchmark because Peasants must cooperate against the Landlord.
  • Cards for states and actions are represented as 4×15 one-hot matrices, with columns for ranks and jokers and rows for card counts.
  • 27,472 card combinations produce state-dependent legal actions, including 391 legal combinations in one example hand.These combinations include Solos, Pairs, Trios, Bombs, Planes, and Quads.

3. Deep Monte-Carlo

Deep Monte-Carlo replaces tabular action values with neural estimates from complete episodic returns, making Monte-Carlo learning suitable for DouDizhu. Its action-feature inputs support generalization across rarely seen moves while avoiding several scalability problems of DQN and policy-gradient methods.

  • The Q-network encodes historical moves with an LSTM and predicts state-action values from concatenated state and action representations.It uses six MLP layers with hidden dimension 512.
  • Deep Monte-Carlo replaces the Q-table with a neural network trained by mean-squared error on sampled returns.
  • DouDizhu suits Deep Monte-Carlo because games are episodic and parallel actors can generate many samples per second.Parallel sampling helps alleviate the high variance traditionally associated with Monte-Carlo methods.
  • Action features let Deep Monte-Carlo generalize over unseen actions, while evaluating only legal actions keeps computation efficient in most states.
  • DQN is unstable in DouDizhu because its overestimation bias becomes difficult to control with function approximation and very large action spaces.
  • Monte-Carlo estimation avoids waiting for next-state values to converge in DouDizhu’s long-horizon, sparse-reward episodes.
  • DQN is slow because each update must scan variable legal-action sets, whereas Deep Monte-Carlo provides wall-clock scalability.

4. DouZero System

DouZero represents cards and game context with structured features, then uses a neural Q-network to estimate state-action values. Its training system parallelizes trajectory generation across actors while a learner updates position-specific global networks.

  • DouZero encodes each card combination as a 4×15 one-hot matrix and represents state context with card matrices and one-hot vectors.The state includes hand cards, other players’ cards, recent moves, remaining-card counts, and bombs played.
  • The system uses an LSTM for historical moves and a multilayer network to estimate values from state-action representations.
  • Multiple actor processes sample trajectories while one learner updates three global Q-networks for the three player positions.Actors maintain synchronized local networks and communicate data through shared buffers.

5. Experiments

Experiments compare DouZero with existing programs across performance, training efficiency, bidding, human alignment, inference speed, and cooperation. DouZero consistently performs strongly, often surpassing established methods within days while using efficient inference.

  • Performance against Existing Programs: DouZero dominates rule-based, supervised-learning, CQN, and DeltaDou baselines in head-to-head WP and ADP evaluations.Against DeltaDou, it achieves WP 0.586 and ADP 0.258.
  • Performance against Existing Programs: DouZero's WP-optimized model beats other bots on Botzone despite not being trained for Botzone's additional card-category bonuses.The evaluation uses a different scoring mechanism from the training objective.
  • Analysis of Learning Progress: DouZero surpasses SL within two days and DeltaDou within ten days, although DeltaDou was pretrained on heuristics and trained for more than two months.DouZero starts from scratch, supporting the reported efficiency of model-free self-play reinforcement learning.
  • Analysis of Learning Progress: Using more actors accelerates training in wall-clock time while the tested actor settings show similar sample efficiency.The comparison evaluates 15, 30, and 45 actors against SL.
  • Analysis of DouZero on Expert Data: On human data, DouZero initially aligns with human expertise but later achieves improving ADP against SL as accuracy on human plays declines.The authors interpret the later divergence as discovery of strategies humans may not easily discover.
  • Inference Efficiency: DouZero is orders of magnitude faster at inference than DeltaDou, CQN, RHCP, and RHCP-v2 because it performs one neural-network forward pass per step.The alternatives require Monte Carlo simulations or expensive card decomposition.

6. Related Work

CFR and related methods have advanced imperfect-information games, but DouDizhu's huge game tree and branching factor make direct traversal computationally intensive. Reinforcement learning offers another approach developed in poker, while DouDizhu remains a substantially harder setting.

  • CFR is a leading iterative algorithm for poker, but traversing DouDizhu's huge game tree is computationally intensive.The passage attributes this difficulty to DouDizhu's large tree and branching factor.
  • Reinforcement learning has achieved competitive performance in imperfect-information poker games.

7. Conclusions and Future Work

The paper presents DouZero as a strong pure-RL system for DouDizhu and concludes that enhanced Monte-Carlo methods can perform well in a difficult domain. It also outlines extensions involving architectures, bidding, search, off-policy learning, collaboration, scalability, and other tasks.

  • Conclusions: DouZero enhances classic Monte-Carlo methods with deep neural networks, action encoding, and parallel actors for DouDizhu.The paper describes the resulting system as conceptually simple, effective, and efficient.
  • Future Work: Future work includes alternative neural architectures, bidding in reinforcement learning, search integration, off-policy learning, explicit collaboration modeling, scalable frameworks, and testing other tasks.
  • DouDizhu Setting: DouDizhu combines huge state and action spaces with incomplete information and cooperation between the two Peasants.The game includes bidding and card-playing phases, and legal moves span many card combinations.
  • DouDizhu Setting: DouDizhu's action space contains 27,472 actions, with card combinations and kicker choices making individual decisions consequential.The action-space summary identifies DouDizhu as more complex than the compared games described in the passage.
  • Representations: The neural representation combines card matrices, player-hand counts, bomb counts, and recent move history, with historical moves encoded for an LSTM.State and action representations are concatenated as network input.

C.2. Data Collection and Neural Architecture of Supervised Learning

The supervised-learning setup uses filtered data from high-league users and converts action prediction into binary classification because most of the 27,472 action classes are illegal in practice. The model reuses DouZero's architecture with a Sigmoid output and selects the highest-scoring action.

  • Data Collection: User data are collected from a popular DouDizhu mobile app and filtered to retain highest-league players' actions.The filtering is intended to ensure data quality.
  • Training Objective: The action-prediction problem has 27,472 classes, but most actions are illegal, making exhaustive class iteration expensive.
  • Training Objective: The supervised model reuses DouZero's neural architecture, adds a Sigmoid output, and trains as a binary classification task with binary cross-entropy loss.Ten percent of the data are randomly sampled for validation.
  • Inference: The agent performs the action with the highest prediction score.

C.3. Neural Architecture and Training Details of Bidding Network

The bidding network predicts whether a player should bid using hand-card and move information. It represents the input with 128 features and uses an MLP with a Sigmoid output trained for binary prediction.

  • Bidding Task: Bidding determines whether a player should become the Landlord based on hand-card strength and preceding players' decisions.The bidding decision is binary: bid or not bid.
  • Bidding Task: The bidding phase is simpler than card-playing because the agent considers hand cards and other players' decisions for a binary prediction.
  • Input Features: The bidding network uses 128 features representing hand cards and players' moves.
  • Architecture: The network is an MLP with layer sizes 512, 256, 128, 64, 32, and 16, followed by a Sigmoid output.It is trained with binary cross-entropy.

D.1. Full WP and ADP Results for Landlord and Peasants

DouZero performs strongly for both Landlord and Peasants under WP and ADP, with a larger advantage for Peasants that may reflect learned cooperation.

  • DouZero’s advantage over competing algorithms is larger for Peasants than for Landlord.The authors suggest this may reflect cooperation skills learned by the two Peasants agents.
  • WP evaluates DouZero and baselines by whether average Landlord and Peasant win probability exceeds 0.5.
  • ADP evaluates DouZero and baselines by whether average Landlord and Peasant average difference in points exceeds 0.

D.2. Comparison of Using WP and ADP as Objectives

WP and ADP produce different strategic behaviors and favor agents trained for their matching objective. The objectives should therefore be selected according to the intended DouDizhu scenario.

  • Objective-dependent strategies: WP-trained agents play bombs more aggressively, whereas ADP-trained agents are more cautious because losing after a bomb can increase ADP loss.WP does not double the points when a bomb is played, while ADP can be doubled by an improperly played bomb.
  • Cross-objective evaluation: DouZero trained with ADP performs slightly worse on WP, while DouZero trained with WP performs slightly worse on ADP.
  • Scenario dependence: Other metrics may be appropriate in scenarios with score doubling, so objectives should be adjusted to the scenario.
  • Evaluation setup: When ADP is used as reward, DouZero’s WP is evaluated against baselines using the same Landlord and Peasant averaging rule.
  • Evaluation setup: ADP results against baselines are reported for agents trained with WP rewards and for bidding-network variants.
  • Head-to-head comparison: DouZero (ADP) outperforms DouZero (WP) in ADP, while DouZero (WP) is better in WP.

D.3. Additional Results of Learning Progress

DouZero improves rapidly during self-play training, surpassing supervised learning quickly and DeltaDou within a limited training budget. The experiments track performance, losses, roles, and Botzone deployment constraints.

  • Training progress: Figure 15 compares WP and ADP against SL and DeltaDou as training days increase.
  • Training progress: Figure 16 compares WP and ADP against SL and DeltaDou as the number of training actions increases.
  • Training progress: DouZero surpasses SL after about 5 × 10^8 training timesteps and DeltaDou within 5 × 10^9 timesteps on one server with four 1080 Ti GPUs and 48 processors.
  • Training diagnostics: Learning progress is examined through rewards, losses, and role-specific performance during training.
  • Self-play procedure: Training uses self-play for the Landlord and both Peasant positions, with randomly generated decks and learner updates from partially observed episodes.
  • Botzone evaluation: Botzone evaluates bots through scheduled matches, role exchanges, game scores, and Elo updates.
  • Deployment constraints: Botzone imposes per-decision time limits, memory limits, and a 140 MB model-size limit.Decisions must finish within 1 second, or 6 seconds for Python programs, with no more than 256 MB memory.

E.3. Discussion of Ranking Stability

Botzone rankings are unstable because DouDizhu outcomes depend heavily on initial cards, the platform omits bidding, and games are infrequent. Case studies nevertheless illustrate strategic planning, cooperation, and objective-dependent play.

  • Ranking stability: DouDizhu Elo rankings suffer fluidity because outcomes depend on initial hands, bidding is omitted, matched games use different hands, and games are infrequent.DouZero has the chance to play about one Elo game every 2 hours on average.
  • Ranking stability: Botzone’s ranking instability limits how directly leaderboard position can represent absolute agent strength.
  • Strategic play: WP-focused case studies show aggressive bomb use, while later-stage examples illustrate improved planning and strategic hand management.
  • Strategic play: DouZero examples show strategic choices such as breaking a bomb for a long chain, passing to preserve future control, and avoiding moves that break chains.
  • Cooperation: Peasant cooperation cases show agents passing to let teammates empty their hands, including when the acting Peasant could otherwise play a winning move.
  • Objective-dependent behavior: WP and ADP agents develop different styles: WP favors aggressive bomb use, whereas ADP weighs the potential loss from bombs more cautiously.
Loading 2106.06135v1…