PaperlayerView exact revision on arXiv

Source-linked AI summary

No-Press Diplomacy from Scratch

Anton Bakhtin, David Wu, Adam Lerer, Noam Brown

arXiv:2110.02924v1cs.LGcs.AIcs.GTcs.MA

TL;DR

Diplomacy’s enormous action space has made it difficult to train agents without human data or handcrafted reward shaping. The paper develops an equilibrium-based self-play method with double-oracle action exploration. DORA achieves superhuman performance in a two-player variant, while seven-player results suggest self-play can yield strategies incompatible with human-data-based agents.

  • Problem

    Diplomacy often has more than 10^20 legal actions per turn, and prior approaches to large action spaces used human data or handcrafted reward shaping.

    Source: §1 · p. 1

  • Method

    The method performs value iteration using equilibrium search at visited states and double-oracle exploration to add actions to a learned proposal network.

    Source: §1 · pp. 1–2

  • Results

    DORA achieves superhuman performance in two-player Diplomacy from scratch, while seven-player results show asymmetric performance against human-data-based agents.

    Source: §1 · p. 2, §6 · p. 10

  • Takeaways & Limitations

    The seven-player results provide evidence of multiple equilibria and suggest scratch self-play may be insufficient for superhuman performance in Diplomacy.

    Source: §6 · p. 10

    Despite being superhuman, the agent remains relatively exploitable.

    Source: §5.1.1 · p. 8

Abstract

from arXiv · show

Prior AI successes in complex games have largely focused on settings with at most hundreds of actions at each decision point. In contrast, Diplomacy is a game with more than 10^20 possible actions per turn. Previous attempts to address games with large branching factors, such as Diplomacy, StarCraft, and Dota, used human data to bootstrap the policy or used handcrafted reward shaping. In this paper, we describe an algorithm for action exploration and equilibrium approximation in games with combinatorial action spaces. This algorithm simultaneously performs value iteration while learning a policy proposal network. A double oracle step is used to explore additional actions to add to the policy proposals. At each state, the target state value and policy for the model training are computed via an equilibrium search procedure. Using this algorithm, we train an agent, DORA, completely from scratch for a popular two-player variant of Diplomacy and show that it achieves superhuman performance. Additionally, we extend our methods to full-scale no-press Diplomacy and for the first time train an agent from scratch with no human data. We present evidence that this agent plays a strategy that is incompatible with human-data bootstrapped agents. This presents the first strong evidence of multiple equilibria in Diplomacy and suggests that self play alone may be insufficient for achieving superhuman performance in Diplomacy.

1 Introduction

The paper tackles Diplomacy’s enormous action space with equilibrium-based self-play and action exploration. DORA achieves superhuman performance in a two-player variant from scratch, while seven-player results suggest self-play can produce strategies incompatible with human-data-based agents.

1 Introduction

  • Diplomacy often has more than 10^20 legal actions per turn, while prior approaches to large action spaces used human data or handcrafted reward shaping.The paper presents an approach that trains through self-play without human data.Source: §1 · p. 1
  • The algorithm approximates a Nash equilibrium with one-step lookahead at visited states, plays its policy, and uses its value as a training target.It computes the equilibrium over candidate actions proposed by a network trained alongside the value model.Source: §1 · pp. 1–2
  • Deep Nash value iteration initialized with a human-bootstrapped model defeats multiple prior human-derived agents in no-press Diplomacy.The paper reports that it wins by a wide margin.Source: §1 · p. 2
  • DORA achieves superhuman performance in a two-player Diplomacy variant using self-play without human data or reward shaping.The agent uses exploratory actions discovered through a double-oracle-like process.Source: §1 · p. 2
  • In seven-player no-press Diplomacy, DORA and human-data-based agents perform asymmetrically against each other's populations, suggesting incompatible equilibria.A human-data-based agent performs extremely poorly among six DORA agents, while one DORA agent underperforms among six human-data-based agents.Source: §1 · p. 2

2 Background and Related Work

The background introduces Diplomacy’s large, simultaneous action space and the stochastic-game and equilibrium concepts used to analyze it. It then reviews Nash Q-learning, double oracle, and regret matching as foundations for the paper’s approach.

2.1 Description of Diplomacy

  • Seven players contest 34 supply centers across 75 locations; each turn, players simultaneously order their units, making the action space too large to enumerate and coordinated orders hard to learn.A player wins at 18 centers; simultaneous play also makes mixed strategies useful to avoid predictability and exploitability.Source: §2.1 · p. 2

2.2 Stochastic Games

  • A stochastic game models simultaneous player actions whose joint action determines rewards and the next state; Nash equilibrium requires each player’s policy to be a best response to the others.An ϵ-equilibrium limits each player’s improvement from switching policies to at most ϵ; for a one-step stage game, the text denotes equilibrium by σ.Source: §2.2 · pp. 2–3

2.3 Nash Q-Learning

  • Nash Q-learning replaces standard Q-learning’s maximization with a stage-game Nash equilibrium, using its value at the successor state as the update target.The paper adapts this foundation for deep reinforcement learning and a value function rather than a Q function.Source: §2.3 · p. 3

2.4 Double Oracle

  • Double oracle iteratively computes equilibria over restricted candidate-action sets and adds best responses; when few actions suffice, this can avoid computing over the full action space.The paper uses a double-oracle-like procedure within learning and at inference to introduce novel actions.Source: §2.4 · p. 3

2.5 Regret Matching

  • Regret matching approximates equilibria in restricted games, but its convergence guarantee applies to two-player zero-sum and other special game classes, not general games.The sampled form’s average policy converges to an ϵ-equilibrium in two-player zero-sum games in O(1/ϵ^2) iterations with high probability; the paper also uses linear weighting and optimism.Source: §2.5 · p. 4

3 Algorithms

DORA combines value learning and an action-proposal policy with approximate equilibrium search, then uses double-oracle-based exploration to discover additional actions. Its guarantees and relationship to earlier methods depend on game class and algorithmic approximations.

3.1 Deep Nash Value Iteration

  • DORA learns a state-value function and action-proposal distribution from approximate stage-game Nash equilibria, sampling likely proposals and using self-play to train both networks.The value network regresses toward the equilibrium value, while the proposal network is trained toward the equilibrium policy; the method adapts Nash Q-learning for large action spaces and function approximation.Source: §3 · p. 4, §3.1 · pp. 4–5
  • The exact tabular algorithm is proven to converge to a Nash equilibrium in two-player zero-sum games under mild assumptions, but the deep approximations lack that stated guarantee.The authors relate the method to AlphaZero and ReBeL while distinguishing its one-ply regret-matching search, one-step bootstrap, and action-proposal role.Source: §3.1 · p. 5

3.2 Double-Oracle-Based Action Discovery

  • Local modifications of equilibrium candidate actions outperform uniform sampling in the reported comparison, while the authors argue that locality makes useful actions more likely to be found.The process generates a pool of actions by modifying candidate actions; random sampling is described as unlikely to find useful actions in Diplomacy’s combinatorial action space.Source: §3.2 · p. 5

4 Implementation and Methods

The implementation uses parallel self-play and training workers, replay-buffer learning, and separately designed policy and value networks. The authors also describe two procedures for training agents to exploit a fixed opponent.

4 Implementation and Methods

  • The implementation applies the described algorithms to Diplomacy, with exact parameters deferred to the appendix.The section specifies data generation, network architecture, and exploitability testing.Source: §4 · p. 6

4.1 Data Generation and Training

  • Parallel self-play workers collect states and policy and value targets in a shared replay buffer, while training workers sample it; self-play mostly follows the approximate-equilibrium policy with occasional proposal-based exploration.The exploration probability is increased on the first two turns to introduce opening-state diversity.Source: §4.1 · p. 6

4.2 Model Architecture

  • The model uses an encoder-decoder with policy and value heads, but the authors report improved stability from removing dropout and improved model quality from a transformer encoder and separate networks.The transformer replacement also removes the need to hardwire the Diplomacy map’s adjacency matrix into the architecture.Source: §4.2 · pp. 6–7

4.3 Exploitability Testing

  • For exploitability testing, one approach applies Impala actor-critic directly against the search agent, while another resumes deep Nash value iteration with a modification to learn a best response.Unlike prior work described here, the first approach avoids first training a proxy policy to copy the search agent.Source: §4.3 · p. 7

5 Results

Results show DORA’s strength in two-player France vs. Austria and contrasting performance across agent populations in seven-player no-press Diplomacy. Ablations also assess architecture, double-oracle sampling, and exploitability.

5.1 Results in 2-player France vs. Austria

  • DORA achieved a variance-reduced average score of 78% against top FvA players and won significantly more than half of games as France.The authors conclude that its FvA play exceeds that of top humans.Source: Table 1 · p. 7, §5.1 · p. 8

GraphConv vs Transformers

  • Transformer encoders produced significant gains over prior Diplomacy architectures while using fewer parameters and remaining similarly fast or faster.Larger models and separate value and policy networks led to further gains.Source: GraphConv vs Transformers · p. 8, Table 2 · p. 8
  • During training, local-modification double-oracle sampling improved final FvA strength, whereas uniform random action sampling was relatively ineffective.The comparison reports final strength after training.Source: GraphConv vs Transformers · p. 8, Table 3 · p. 8
  • At inference time, local-modification sampling improved all tested baselines, while uniform random sampling improved only the weakest baseline.The random pool was ineffective at finding better actions in the large action space.Source: GraphConv vs Transformers · p. 8, Table 4 · p. 9

5.1.1 Exploitability

  • The superhuman FvA agent remained relatively exploitable, but value learning and double-oracle policy learning improved performance, and inference-time double oracle reduced exploitability from 90.5% to 85.8%.Value learning improved over the actor-critic baseline from 50% to 60.5%; policy learning further improved to 85.8% winrate over DORA.Source: §5.1.1 · pp. 8–9

5.2 Results in 7-player No-Press Diplomacy

  • HumanDNVI-NPU used a fixed human-game-trained policy to propose training actions, did not apply double oracle, and stopped training early.Its reported results are compared with agents trained from scratch and other prior agents.Source: §5.2 · p. 9
  • In 7-player no-press, DORA scored about 11% in 1v6 against SearchBot, while SearchBot scored 1.1% in reverse; separate DORA runs scored only 3–8% against each other.The table reports SoS scores against six copies; equal performance is about 14.3%.Source: Table 6 · p. 10, §5.2 · p. 10
  • HumanDNVI-NPU beat SearchBot with a 36.3% 1v6 winrate versus SearchBot’s 0.5% in reverse, yet both performed very poorly against DORA.The authors interpret the results as evidence that initialization affects which equilibrium deep Nash value iteration reaches.Source: §5.2 · p. 10

6 Conclusions and Future Work

DORA achieves superhuman performance in two-player Diplomacy without human data or reward shaping. In seven-player no-press Diplomacy, results indicate that self-play can produce play incompatible with human-data-based agents and may not suffice for superhuman performance.

6 Conclusions and Future Work

  • DORA achieves superhuman performance in two-player Diplomacy without human data or reward shaping, addressing the challenge of its combinatorial action space.The paper identifies Diplomacy’s multi-agent nature as a separate challenge.Source: §6 · p. 10
  • In seven-player no-press Diplomacy, DORA approximates an equilibrium that differs radically from those of human-data-based agents.A lone DORA agent does not exceed average performance against a population of human-data-based agents, while a lone human-data-based agent loses by a wide margin against DORA agents.Source: §6 · p. 10
  • These results suggest that self-play from scratch may be insufficient for superhuman performance in Diplomacy, unlike in six-player poker.They also suggest a wide range of equilibria, some differing dramatically from human conventions.Source: §6 · p. 10
  • DORA offers a technique for exploring equilibria without being constrained to human priors.Source: §6 · p. 10

7 Checklist

The checklist reports that code release is deferred until the camera-ready version because the extensive codebase could pose a double-blind review concern. It also points to appendices for training details, compute requirements, asset licensing, and human-subject materials.

7 Checklist

  • The authors plan to release the code and models after double-blind review, since the extensive codebase could make violations of double-blind principles challenging to check.Source: §7 · p. 13
  • Training details and compute requirements are reported in Appendix D, and the authors state that relevant measurements include error bars.Source: §7 · p. 13
  • The checklist states that existing assets are cited and licensed, with the model and code planned for release under the MIT license.The authors also report that participant instructions are in Appendix F and that the work uses no personally identifiable information or offensive content.Source: §7 · pp. 13–14

A Neural Network Architecture

The agents use a transformer-based architecture with separate policy and value networks. The input combines board-state and order features across board locations, while the policy decoder generates orders sequentially.

A Neural Network Architecture

  • The architecture replaces the graph-convolution encoder with a transformer, removes dropout, and separates policy and value networks.The architecture is otherwise largely identical to [11], including its LSTM policy decoder.Source: A Neural Network Architecture · p. 15
  • The policy decoder uses sequential attention over encoder locations to generate orders one location at a time.Source: A Neural Network Architecture · p. 15
  • The input concatenates the current and previous board states with a recent order embedding, producing 146 feature channels for each of 81 board locations.A linear layer and learnable per-position, per-channel bias precede the transformer encoder.Source: A Neural Network Architecture · p. 15
  • Final agents use (D, C) = (10, 224), while other reported variants use (5, 192) or a shared encoder for policy and value.Source: A Neural Network Architecture · p. 15

B Theoretical Correctness of Nash Value Iteration

In the tabular setting, DNVI converges to minimax values for reachable states in two-player zero-sum stochastic games with deterministic transitions. The convergence argument adapts Nash Q-learning and depends on assumptions about equilibrium updates, state visitation, and learning rates.

B Theoretical Correctness of Nash Value Iteration

  • DNVI converges to each reachable state's minimax value in the tabular setting for two-player zero-sum stochastic games with deterministic transitions.Under the stated assumptions, its value function converges to Nash-equilibrium values, and minimax play based on those values is optimal.Source: B Theoretical Correctness of Nash… · pp. 15–16
  • The proof relates DNVI's value updates to Nash-Q updates across predecessor state-action pairs, whose convergence result applies under stated assumptions.Those assumptions require an adversarial equilibrium in every one-step game, infinitely frequent visits to all states, and a learning rate that decays to zero while its sum diverges.Source: B Theoretical Correctness of Nash… · pp. 15–16
  • The convergence result is established for deterministic transitions; the authors believe it may extend to nondeterministic transitions but do not prove that extension.Source: B Theoretical Correctness of Nash… · p. 15
  • In practice, Diplomacy's action space is too large for exact regret matching, so DNVI uses a small proposal-network candidate set and relies on Double Oracle to discover additions.Source: B Theoretical Correctness of Nash… · p. 16

C Variance Reduction in Diplomacy

The appendix describes variance reduction for human matches and practical changes for training and running DORA, including adaptations for seven-player Diplomacy.

C Variance Reduction in Diplomacy

  • Informal tests found roughly a factor-of-2 variance reduction when subtracting action-sampling luck from the final game reward, without bias in expectation.The adjustment is expected to help most when the learned Q-value estimates true state values, particularly in two-player FvA.Source: C Variance Reduction in Diplomacy · p. 17

D.1 Double Oracle optimizations

  • Double Oracle runs one player's best response at a time, truncates the opponent policy to its top k actions, and caps iterations to reduce computation.Recomputing the equilibrium lets each best response account for the opponent's newest action; truncation uses Nc × k rather than Nc × Np value calls, with minimal error.Source: §D.1 · p. 17

D.2 Pretraining

  • Pretraining uses random legal candidate actions and final-outcome targets to initialize the value model and a high-entropy proposal policy before deep Nash value iteration.The proposal policy is trained to predict regret matching on the random actions, mildly favoring high-value actions.Source: §D.2 · pp. 17–18

D.3 Extending to 7p

  • For seven-player play, the authors sample to approximate both one-step values and expected best-response values, then use depth-2 rollouts at inference but not training.They report that rollouts improved play over a value function alone, while their computational cost precluded using them during training.Source: §D.3 · p. 18

D.4.1 Double Oracle

  • The appendix points to separate Double Oracle hyperparameter settings for DORA agents.Training and inference use slightly different parameters to speed data generation.Source: §D.4.1 · p. 18, Table 9 · p. 18

D.4.2 DORA training

  • Seven-player training adds a pretraining stage without Double Oracle and uses smaller transformer models because games and equilibrium computations are more costly.Each seven-player game is 4–5 times longer, and each equilibrium computation requires 3 times more operations than in FvA.Source: §D.3 · p. 18, §D.4.2 · p. 19, Table 10 · p. 19

D.4.3 Evaluation details

The appendix specifies evaluation comparisons and distributed data generation, then describes adapting deep Nash value iteration to train exploiters against a fixed agent policy.

D.4.3 Evaluation details

  • Evaluations compare DORA with released DipNet and SearchBot checkpoints, using temperature 0.5 for DipNet and SearchBot's search parameters for DORA and HumanDNVI-NPU.The cited table lists parameters for seven-player agents evaluated with search.Source: §D.4.3 · p. 19, Table 11 · p. 19

D.4.4 Distributed training and data generation

  • The distributed setup separates training, rollout, data collection, evaluation, and metric aggregation processes across machines; the main DORA run used 192 GPUs across 24 machines.In the stated 8-GPU-machine configuration, GPU and CPU utilization exceeded 90% on average.Source: §D.4.4 · pp. 19–20

E Adapting Deep Nash Value Iteration to Learn Best Responses

  • One-sided regret matching turns deep Nash value iteration from equilibrium learning into best-response exploitation against the exploited agent's precomputed policy.Unlike SBR [3], this approach directly trains the proposal policy to sample exploitative candidate actions and the value model to favor states with high future exploitability.Source: E Adapting Deep Nash Value Iteration… · p. 20

F Human data

The human-match section reports results from five top players; the action-exploration example shows how adding a missed action changes the predicted outcome of a position.

F Human data

  • The human-match protocol invited top players to play 10 games against the bot, allowed practice beforehand, and asked them not to cancel games or call draws except at clear stalemate.Results were intended for an academic paper, with players choosing whether to use their real name, username, or GhostRating.Source: F Human data · pp. 20–21
  • Five contacted top players played the bot; none had a positive win rate, but no individual played enough games for a statistically significant performance measure.They ranked 1st, 8th, 16th, 22nd, and 29th in FvA on webdiplomacy.net by the cited Ghost-Ratings system.Source: F Human data · p. 21

G Action Exploration Example

  • The example position had more than 4 million valid actions, leaving less than a 1% chance of finding a best-response action when training evaluates about 1,000 actions.The approximate local modification approach is presented as a way to reduce search size and find good approximate best responses with relatively few actions.Source: G Action Exploration Example · p. 21
  • After the missing Austrian action was added, France's army was crushed and disbanded, and DORA learned that action without inference-time Double Oracle.The agent's probability of moving Mar to Pie and its expected score in the state both fell once the action entered the candidate set.Source: G Action Exploration Example · p. 21, Figure 4 · p. 22

H Additional Results for 7-player No-Press Diplomacy

Additional seven-player results examine human-compatible strategies and the effect of Double Oracle training, including the reported gains from a short Double Oracle fine-tuning phase.

H Additional Results for 7-player No-Press Diplomacy

  • Early stopping and freezing the proposal network helped agents converge toward strategies more effective against human-like models.HumanDNVI-NPU uses a fixed supervised human-game blueprint to propose actions during training, whereas HumanDNVI updates its proposal network but uses no Double Oracle.Source: H Additional Results for 7-player… · p. 22, Table 12 · p. 23
  • Using the human blueprint policy during both training and testing performed worse than HumanDNVI-NPU, suggesting trained policies can strengthen an agent while policy updates inside RL can move training away from human-compatible strategies.The authors note that future work may find better ways to combine these benefits.Source: H Additional Results for 7-player… · p. 22
  • After 300k updates without Double Oracle, 60k more with it doubled score versus SearchBot and greatly increased score versus Dipnet.Table 13 describes the comparison as showing a significant strength increase even from a small fraction of training time with Double Oracle.Source: H Additional Results for 7-player… · p. 22, Table 13 · p. 23
Loading 2110.02924v1…