Source-linked AI summary
Learning to Play No-Press Diplomacy with Best Response Policy Iteration
Thomas Anthony, Tom Eccles, Andrea Tacchetti, János Kramár, Ian Gemp, Thomas C. Hudson, Nicolas Porcel, Marc Lanctot, Julien Pérolat, Richard Everett, Roman Werpachowski, Satinder Singh, Thore Graepel, Yoram Bachrach
TL;DR
Diplomacy combines many-agent mixed motives with simultaneous moves and a large combinatorial action space, making it a challenging setting for reinforcement learning. The paper introduces Sampled Best Responses and policy-iteration methods approximating fictitious play; its agents outperform prior state of the art, and equilibrium analysis indicates consistent improvement.
Problem
Many-agent mixed-motive settings are less amenable to the simple RL methods used in two-player zero-sum games, while Diplomacy adds simultaneous moves and a large combinatorial action space.
Source: §1 · pp. 1–2Method
The paper trains No-Press Diplomacy agents with policy iteration, using Sampled Best Responses and variants that approximate iterated best response and fictitious play.
Source: §1 · p. 2Results
The agents outperform the previous state of the art against reference populations and head-to-head, and equilibrium analysis shows consistent improvements.
Source: §1 · p. 2, §5 · pp. 7–8Takeaways & Limitations
The improved agents provide a prerequisite for investigating mixed motives and many-player learning in Diplomacy.
Source: §6 · p. 8FPPI-1’s marginal policy predictions weaken its connection to fictitious play, and it continues imitating historical best responses that may be weaker than later ones.
Source: §3.2 · p. 5
Abstract
from arXiv · showhide
Recent advances in deep reinforcement learning (RL) have led to considerable progress in many 2-player zero-sum games, such as Go, Poker and Starcraft. The purely adversarial nature of such games allows for conceptually simple and principled application of RL methods. However real-world settings are many-agent, and agent interactions are complex mixtures of common-interest and competitive aspects. We consider Diplomacy, a 7-player board game designed to accentuate dilemmas resulting from many-agent interactions. It also features a large combinatorial action space and simultaneous moves, which are challenging for RL algorithms. We propose a simple yet effective approximate best response operator, designed to handle large combinatorial action spaces and simultaneous moves. We also introduce a family of policy iteration methods that approximate fictitious play. With these methods, we successfully apply RL to Diplomacy: we show that our agents convincingly outperform the previous state-of-the-art, and game theoretic equilibrium analysis shows that the new process yields consistent improvements.
1 Introduction
The introduction motivates learning in Diplomacy as a test of mixed-motive, many-agent interaction, where the assumptions that simplify two-player zero-sum games do not apply. It presents Sampled Best Responses and policy iteration methods as a way to train agents that outperform prior state of the art.
1 Introduction
- Diplomacy challenges RL with more than two players, simultaneous moves, and a large combinatorial action space.Players choose without knowing others’ actions; the game is estimated to have a game-tree size of 10^900 and 10^21 to 10^64 legal joint actions per turn.Source: §1 · p. 2
- The agents outperform the previous state of the art against reference populations and head-to-head, while equilibrium analysis shows consistent improvement.The paper also reports that FPPI-2 is its strongest method.Source: §1 · p. 2
- The paper trains No-Press Diplomacy agents with policy iteration and proposes Sampled Best Responses to handle simultaneous moves and the large action space.Prior RL attempts had not improved performance over imitation learning, motivating the paper’s approach.Source: §1 · p. 2
2 Background and Related Work
The background contrasts Diplomacy with prior work on two-team and cooperative games, noting the relative scarcity of large competitive many-player settings. It then summarizes rules that make Diplomacy’s simultaneous moves, support, and alliances central to play.
2 Background and Related Work
- Prior work on large competitive many-player games is limited; many-player Poker is a notable exception, but its abstractions and frequent early folds reduce many-player interactions in practice.In Diplomacy, two-player situations are rare and alliances are crucial.Source: §2 · p. 2
- Earlier Diplomacy AI included rule-based systems and a TD-learning attempt, while DipNet used imitation learning and A2C did not significantly improve it.The authors report replicating the A2C result with their improved network architecture.Source: §2 · pp. 2–3
2.1 No-Press Diplomacy: Summary of Game Rules
- Each turn, players simultaneously order all units without seeing others’ orders; the resulting position is determined by the moves and rules, without chance.Players capture supply centers to build units, and winning requires a majority of supply centers.Source: §2.1 · p. 3
- Support can let a unit overcome resistance, but it can be cut; because no player can win alone, alliances are essential and interactions are mixed-motive.The France–Germany–Italy example illustrates how support can change a move’s outcome.Source: §2.1 · p. 3
3 Reinforcement Learning Methods
The methods use policy iteration to improve neural policies, with Sampled Best Response (SBR) approximating best responses in Diplomacy’s large action space. Best Response Policy Iteration combines SBR with iterated best response or fictitious-play variants, alongside an updated neural architecture.
3 Reinforcement Learning Methods
- Policy iteration trains policies and value functions to imitate actions and outcomes generated by an improvement operator, beginning from human-game imitation.The operator uses a previous policy and value function to seek a policy that defeats the previous policy.Source: §3 · p. 3
3.1 Sampled Best Response (SBR)
- SBR approximates best responses by improving one turn at a time, sampling candidate actions and estimating their values with Monte Carlo opponent-action samples.Using the same sampled opponent actions across candidates reduces variance; best responses may still perform arbitrarily poorly against other policies.Source: §3.1 · pp. 3–4
3.2 Best Response Policy Iteration
- BRPI combines approximate best responses with policy iteration; FPPI-2 imitates the latest best response while sampling historical checkpoints to represent the empirical opponent strategy.Sampling one shared checkpoint for all opponents preserves correlations; the resulting time-averaged policy is a mixture over checkpoints.Source: §3.2 · pp. 4–5
- In the Blotto case study, stochastic best responses, especially SBR, improve fictitious-play convergence, and SBR improves IBR behavior relative to exact best responses.Exact IBR is ineffective in the studied many-agent Blotto game.Source: §3.2 · p. 5
3.3 Neural Architecture
- The neural architecture replaces DipNet’s LSTM decoder with a GNN relational order decoder and makes two encoder feature changes, increasing validation prediction accuracy by 4–5%.The changes also replace alliance features with recent board state and learned embeddings of actions since that phase, and remove FiLM while adding node features to GNN edge features.Source: §3.3 · p. 5
4 Evaluation Methods
The evaluation assesses agent strength against other agents and reference populations, then examines whether policies improve consistently across training and how exploitable they remain. Its measures include head-to-head comparisons, population scores, checkpoint meta-games, and SBR-based exploitability estimates.
4 Evaluation Methods
- Head-to-head 1v6 matches compare final agents and can reveal whether one agent can invade a population, a perspective connected to evolutionary stable strategies.The matches place one agent against six of another type.Source: §4 · p. 6
- In population evaluation, one agent plays against six independently drawn opponents, with its country randomized, and its average score is reported.The reference populations are DipNet or a uniform mixture of 15 final RL agents from different BRPI methods.Source: §4 · p. 6
- Checkpoint meta-games test transitivity by comparing outcomes among policies from a training run; later policies should perform better when training is transitive.The evaluation uses either a symmetric seven-player game and QRE analysis or a simplified 1v6 payoff heatmap.Source: §4 · p. 6
- SBR-based exploitability is estimated from the average score of one SBR agent against six copies of the evaluated policy.The few-shot variant uses human-imitation candidates and a value function from an independent BRPI run.Source: §4 · p. 6
5 Results
BRPI agents outperform supervised-learning and A2C baselines head-to-head, while population and meta-game analyses indicate continued or transitive improvement. FPPI-2 performs best head-to-head, though all agents remain exploitable at the end of training.
Head-to-head comparison
- All learning methods improve over supervised-learning baselines and DipNet A2C head-to-head, with FPPI-2 achieving the best 1v6 winrate against each algorithm.FPPI-2 is also the strategy against which singleton agents perform worst.Source: §5 · p. 7, Table 1 · p. 7
Winrate Against a Population
- Against DipNet, all PI methods quickly win more often than the 1/7 identical-agent reference, while against a mixture of final BRPI agents they improve steadily through training.FPPI-1 tends to underperform IBR and FPPI-2 against that mixture.Source: §5 · p. 7, Figure 2 · p. 7
Policy Transitivity
- Nearly every checkpoint beats earlier checkpoints in 1v6 meta-games, although FPPI-2 checkpoint 4 is later beaten by subsequent checkpoints by larger margins.This illustrates that beating predecessors need not prevent later exploitability.Source: Figure 3 · p. 8, §5 · p. 8
- In QRE meta-games, most probability mass consistently falls on recent checkpoints, indicating transitive strategy improvement rather than cycling among specialized strategies.This pattern is also observed for IBR, whose checkpoints are trained only to beat the previous checkpoint.Source: Figure 3 · p. 8, §5 · p. 8
Exploitability
- All agents remain fairly exploitable at training's end, with strongest exploiters reaching 48% winrate, although few-shot exploitability falls during training.Final training targets are less exploitable than final networks.Source: §5 · p. 8
6 Conclusion
The paper presents BRPI with SBR as an approach to training Diplomacy agents, and identifies FPPI-2 as its strongest method. The resulting No-Press agents provide a basis for further study of mixed motives and many-player interaction.
6 Conclusion
- BRPI with SBR addresses Diplomacy's simultaneous moves and large combinatorial action space, and the approach also showed beneficial SBR stochasticity in Blotto.The paper reports consistent improvement over the state of the art in Diplomacy.Source: §6 · p. 8
- FPPI-2 is the strongest method, while IBR is also surprisingly effective.FPPI-2 combines RL with fictitious play.Source: §6 · p. 8
- Improved No-Press Diplomacy gameplay is described as a prerequisite for studying mixed motives and many-player learning, including opponent incentives, signalling, and negotiation in Press variants.The paper lists human-level play and reducing exploitability among future questions.Source: §6 · p. 8
Broader Impact
The work offers a training algorithm for simulated environments with simultaneous, decomposable actions, while noting constraints on realistic real-world application. It also frames Diplomacy as a possible sandbox for studying cooperation and manipulative behavior.
Broader Impact
- The methods can train agents in sufficiently simulatable environments with simultaneous actions and decomposable sub-actions, but realistic business or logistics applications require significant additional work.Possible application areas include multi-unit games, fleets of cars or robots, and sequential resource allocation.Source: Broader Impact · p. 9
- The current algorithms assume known rules and perfect information between turns, whereas real-world use would require robust planning under uncertainty.The paper cautions that real-world scenarios are unlikely to be captured at Diplomacy's level of abstraction.Source: Broader Impact · p. 9
- Work on Diplomacy may support research on cooperative agents and trust, while full-game communication also raises the possibility of agents that manipulate trust through false communication.The authors propose studying manipulative behavior in a sandbox to help mitigate it in real-world applications.Source: Broader Impact · p. 9
- The work is presented as an algorithmic building block for many-agent strategy research and as a possible route toward studying cooperation, trust, and alliances.The authors connect this prospect to prior findings that independent RL agents can default to non-cooperative behavior.Source: Broader Impact · p. 9
Appendices
The appendix uses many-player Colonel Blotto to examine sampled best responses and policy-iteration variants, with equilibrium-distance measures used to assess convergence. Its experiments show that sampling can improve early convergence, while outcomes depend on the iteration and sampling choices.
A.1 Definitions and Notation Regarding Equilibria
- The appendix defines NashConv as the sum of players’ gains from unilateral deviation and CCEDist as a related measure that sums positive deviation incentives; its general response framework includes IBR and fictitious play.IBR overwrites the policy with a best response, while fictitious play averages the best responses seen so far.Source: §A.1 · p. 18, §A.1.1 · p. 19, §A.2 · p. 19
A.3 Warm-up: Fictitious Play versus Iterated Best Response (IBR)
- In Blotto(2, 10, 3), fictitious play reduces NashConv over time while deterministic IBR remains fully exploitable; averaging helps, whereas MaxEnt IBR remains non-convergent.Stochastic fictitious play also reduces NashConv, but its temperature affects convergence and its plateaus reflect convergence toward quantal response equilibria rather than Nash equilibria.Source: §A.3 · p. 20, Figure 4 · p. 20
A.4.1 Trade-offs and Scaling
- FP+SBR reaches target approximation quality much sooner than fictitious play, although fictitious play can eventually surpass it and may be infeasible in larger games.In Blotto(2, 10, 6), FP+SBR reaches an accuracy in 1 second that takes fictitious play over three hours; the reported speed advantage applies only up to a threshold accuracy.Source: §A.4.1 · p. 21, Figure 5 · p. 21
- In multiplayer Blotto, FP+SBR reaches fictitious play’s catch-up CCEDist in at most 1 second, while fictitious play takes over 25,000 seconds in Blotto(4, 8, 3).Fictitious play also takes over 10,000 seconds in Blotto(5, 6, 3).Source: Figure 6 · p. 21, §A.4.1 · p. 22
A.4.2 Effects of choices of B and C
- Increasing B reduces FP+SBR’s distance to equilibrium, and larger C works better when B is high; with B=64, two largest games reach CCEDist ≤0.3 while fictitious play remains over three times farther after six hours.At low B, plateaus occur farther from equilibrium, and a small candidate sample count of 2–4 appears to work best.Source: §A.4.2 · p. 22, Figure 7 · p. 22
A.5.1 Effects of choices of B and C
- With BRPI, B strongly affects the plateau and C separates plateau values; higher C is generally better at lower B, possibly because BRPI represents stochastic policies through a fixed number of samples.The authors suggest the fixed N-sample granularity may matter more than error in maximizing over a crude expectation.Source: §A.5.1 · p. 23, Figure 8 · p. 23
- BRPI can train a mixed policy from multiple stochastic best-response samples per iteration instead of explicitly computing the average policy, but it requires retaining past policies.For large games, the authors suggest saving network checkpoints periodically and querying them as needed.Source: §A.5.1 · p. 23
A.5.2 Varying the Candidate Sampling Policy
- For BRPI with B = 2 and C = 16, uniformly sampled past policies give the clearly best long-term CCEDist among tested candidate-sampling schemes, followed by initial + uniform and initial + latest.Source: §A.5.2 · p. 23
A.5.3 Iterated Sampled Best Response
With the last policy as BRPI’s base sampling policy, no candidate-sampling scheme wins across all tested games, though initial-plus-latest is a safe choice. Sampled best responses also make iterated response effective where exact best response makes no progress.
A.5.3 Iterated Sampled Best Response
- There is no clear candidate-sampling winner across the tested games when BRPI uses the last policy as its base, but initial-plus-latest is a safe choice.Its plateau values match those from uniform-past sampling in two of the three games, despite generally higher plateaus across the candidate schemes.Source: §A.5.3 · p. 24, Figure 10 · p. 24
- Using sampled rather than exact best responses can dramatically improve iterated best response, whose sampled version reaches CCEDist plateaus comparable to FP+SBR.The sampled-response plateaus are generally higher than those obtained with uniform-past base sampling.Source: §A.5.3 · pp. 24–25
B.1 Behavioural analysis
Across behavioral analyses, exploitability tests, and head-to-head matches, the BRPI variants show distinct strategic patterns and strong competitive performance. Results also qualify how exploitability is measured and how candidate policies affect comparisons.
B.1 Behavioural analysis
- BRPI agents show substantially less cross-power hold support and more cross-power move support, while A2C attempts both less often but succeeds more often.Support success is measured by whether the other power makes the corresponding move or non-moving order.Source: §B.1 · p. 25
- BRPI reduces peace proportion while maintaining peace correlation, whereas A2C significantly reduces both measures.These statistics are calculated for non-distant powers, defined as powers with the option to intrude on one another.Source: §B.1 · p. 25
B.2 Exploitability
- A low few-shot exploitability score does not by itself imply a strong agent: coordinated agents playing preset moves could unite against a deviator.Few-shot exploiters use an independent BRPI value function and imitation-policy candidates to make comparisons between policies more comparable.Source: §B.2 · pp. 25–26
- Few-shot exploitability is lower for IBR and FPPI-2 than for supervised learning, but the best-exploiter comparison is less clear.All networks were least exploitable at temperature 0.5; the authors note that the best-exploiter comparison may be affected by a weaker value function for supervised learning.Source: §B.2 · p. 26, Figure 12 · p. 27
B.3 Head to head comparisons
- Against populations of final networks from all BRPI runs (1 vs 6 BRPI), IBR and FPPI-2 do better than FPPI-1; latest-and-initial candidates perform best, while imitation-policy candidates substantially improve performance against DipNet.Source: §B.3 · p. 29
C Imitation Learning and Neural Network Architecture
The paper adapts DipNet’s imitation-learning architecture and data pipeline for its RL agents. It also specifies training settings and BRPI sampling and reward choices.
C Imitation Learning and Neural Network Architecture
- The network encodes recent orders, board state, season, power, and build numbers with graph networks, then uses a relational order decoder to generate consistent unit orders.The architecture uses separate 12-layer GNN stacks for board and recent-move representations, followed by three additional GNN layers and a four-layer relational order decoder.Source: C Imitation Learning and Neural… · p. 30
- The imitation architecture produces a slight performance improvement over DipNet, and the RL experiments choose the architecture with highest imitation accuracy despite a winrate decline.The authors prioritize imitation accuracy because the RL improvement loop relies on imitation.Source: C Imitation Learning and Neural… · pp. 30–31, Table 7 · p. 31
C.1 Hyperparameters
- Imitation training uses Adam at learning rate 0.003, batch size 256, and an even mixture of the No-Press and Press datasets.Two thousand randomly selected games from each dataset are held out for validation.Source: §C.1 · p. 31
C.2 Data cleaning
- Data cleaning excludes nonstandard games and games that cannot be replayed successfully after attempted corrections to inconsistent observations and order conventions.The processing also excludes games that remain unparsable after corrections for forced moves and convoy interpretations.Source: §C.2 · pp. 31–32
D BRPI settings
- BRPI updates its target every 7.5 million experience steps and uses two base profiles plus 16 candidate moves per player for sampled best response.When candidate moves come from two sources, eight are sampled from each; games are forced to draw after random lengths, with rewards based on supply centers for those draws.Source: D BRPI settings · pp. 32–33
E A2C with V-Trace off policy correction
The paper implements A2C with V-Trace as a policy-gradient baseline and reports its performance against imitation learning. It also describes confidence-interval calculations and an equilibrium-analysis procedure.
E A2C with V-Trace off policy correction
- A2C uses an actor-learner architecture with self-play experience, importance-weighted batched updates, and supervised learning on trajectory returns rather than TD value targets.Its off-policy correction expands probabilities sequentially across unit orders, conditioned on earlier orders.Source: E A2C with V-Trace off policy correction · p. 33
- A2C winrate against the imitation-learning starting point rises for about 3M steps, then gradually declines; comparisons use the agent’s best winrate against that starting point.The figure’s step count represents state, action, reward triplets used by the central learner, and error bars cover 7,000 games.Source: E A2C with V-Trace off policy correction · p. 33, Figure 14 · p. 33
F Calculation of Confidence Intervals
- For 1v6 winrate tables, confidence intervals reflect game-outcome randomness, not training randomness, and combine Wilson intervals across agent, opponent, and country combinations.The combination method corrects for imbalances in evaluation data, such as those caused by timeouts or machine failures.Source: F Calculation of Confidence Intervals · p. 34
G Gradient Descent for Finding an ϵ-Nash Equilibrium in the Meta-Game
- The equilibrium analysis uses gradient descent on profile exploitability, while adding entropy regularization yields a Quantal Response Equilibrium interpretation.The paper describes the regularized objective as a way to model bounded rationality.Source: G Gradient Descent for Finding an… · p. 34
H Theoretical Properties of Fictitious Play
The appendix establishes convergence guarantees for continuous-time fictitious-play variants in many-player games. It also estimates Diplomacy’s action-space scale from human-game data, noting a downward bias in those estimates.
H Theoretical Properties of Fictitious Play
- The analysis extends continuous-time fictitious play’s convergence to a CCE from two-player settings to many-player games.The paper identifies continuous-time fictitious play as descending exploitability in two-player zero-sum games.Source: H Theoretical Properties of Fictitious… · p. 35
- The continuous-time stochastic result concerns responses to historical entropy-regularized rewards, with the standard continuous-time fictitious-play result recovered when λ = 0.Entropy in the best response makes mixed strategies more common than unregularized best responses.Source: H Theoretical Properties of Fictitious… · pp. 35–36
- Continuous-time stochastic fictitious play converges to an ϵ-CCE, with ϵ bounded by λ times the range of each player’s entropy function.The argument relates regret to coarse correlated equilibrium and decomposes regret into an O(1) regularized term and a λ-dependent O(T) term.Source: H Theoretical Properties of Fictitious… · pp. 36–37
I Size Estimates for Diplomacy
- The game-size estimate inspects legal actions across 21,831 No-Press human-dataset games, but unusually short cancellation games bias the estimates downward.The authors do not attempt to filter those unusually short games.Source: I Size Estimates for Diplomacy · p. 39
I.1 Legal Joint Actions per Turn
The appendix quantifies movement-phase action growth and estimates the game-tree size, while noting that the game tree is technically infinite.
I.1 Legal Joint Actions per Turn
- Movement-phase possibilities rise from 1022.3 on turn one to a maximum of 1064.3 legal action combinations, with a median of 1045.8.The first turn has 22 units, each with approximately 10 independently selectable actions; the movement phase accounts for most gameplay.Source: §I.1 · p. 39
- Different action combinations can lead to the same state, so the count of combinations does not imply an equal number of distinct outcomes.For example, a support action may not affect adjudication if the supported move is not taken or the support is cut.Source: §I.1 · p. 39
I.2 Estimate of the Game Tree Size
- The game-tree estimate multiplies the number of legal actions available at each turn; its median estimated size is 10896.8.The estimate is calculated for a single game from its turn-by-turn action counts.Source: §I.2 · p. 39
- Because Diplomacy has no repetition rule or turn limit, its game tree is technically infinite, making the reported size a rough estimate.The median is reported because the arithmetic mean is dominated by the exceptionally long game; truncating games at 20 movement phases gives a median of 10867.8 and a maximum of 101006.7.Source: §I.2 · p. 39