Human-Level Performance in No-Press Diplomacy via Equilibrium Search
Authors: Jonathan Gray
Adam Lerer
Anton Bakhtin
Noam Brown
Venue: ICLR 2021 Oral (2021)
Keywords: multi-agent systems
regret minimization
no-regret learning
game theory
reinforcement learning

Abstract: Prior AI breakthroughs in complex games have focused on either the purely adversarial or purely cooperative settings. In contrast, Diplomacy is a game of shifting alliances that involves both cooperation and competition. For this reason, Diplomacy has proven to be a formidable research challenge. In this paper we describe an agent for the no-press variant of Diplomacy that combines supervised learning on human data with one-step lookahead search via regret minimization. Regret minimization techniques have been behind previous AI successes in adversarial games, most notably poker, but have not previously been shown to be successful in large-scale games involving cooperation. We show that our agent greatly exceeds the performance of past no-press Diplomacy bots, is unexploitable by expert humans, and ranks in the top 2% of human players when playing anonymous games on a popular Diplomacy website.

Published as a conference paper at ICLR 2021
HUMAN-LEVER PERFORMANCE IN NO-PRESS DIPLOMACY VIA EQUILIBRIUM SEARCH
Jonathan Gray, Adam Lerer, Anton Bakhtin, Noam Brown Facebook Al Research
(jsgray, alerer, yolo, noambrown ) @fb. com
ABSTRACT
Prior Al breakthroughs complex games have focused on either the purely adver- sarial or purely cooperative settings. In contrast, Diplomacy is a game of shifting alliances that involves both cooperation and competition. For this reason, Diplo- macy has proven to be formidable research challenge. In this paper we describe an agent for the no-press variant of Diplomacy that combines supervised learning human data with one-step lookahead search via regret minimization. Regret minimization techniques have been behind previous Al successes in adversarial games, most notably poker, but have not previously been shown be success- ful in large-scale games involving cooperation. We show that our agent greatly exceeds the performance of past no-press Diplomacy bots, is unexploitable by ex- pert humans, and ranks in the top 2% of human players when playing anonymous games on a popular Diplomacy website.
INTRODUCTION
A primary goal for Al research is develop agents that act optimally in real-world multi-agent interactions (i.e., games). In recent years, Al agents have achieved expert-level or even superhuman performance in benchmark games such backgammon [Tesauro 1994), chess (Campbell et al.
2002). Go Silver et al. 2016 2017 2018), poker (Moravčík et al., 2017; Brown & Sandholm 2017 2019b). and real-time strategy games (Berner et al.) 2019] Vinyals et al., 2019). However, previous large-scale game Al results have focused on either purely competitive or purely cooperative settings. In contrast, real- world games, such as business negotiations, polities, and traffic navigation, involve far more complex mixture of cooperation and competition. In such settings, the theoretical grounding for the techniques used in previous AI breakthroughs falls apart.
In this paper we augment neural policies trained through imitation learning with regret minimization search techniques, and evaluate on the benchmark game of no-press Diplomacy. Diplomacy a longstanding benchmark for research that features rich mixture of cooperation and competition. Like previous researchers, we evaluate on the widely played no-press variant of Diplomacy, in which communication only occur through the actions in the game (i.e., cheap talk is allowed).
Specifically, we begin with a blueprint policy that approximates human play in a dataset of Diplo- macy games. We then improve upon the blueprint during play by approximating the current phase of the game, assuming all players (including our agent) play the blueprint for the remainder of the game. Our agent then plays its part of the computed equilibrium. The equilibrium is computed via regret matching (RM) (Blackwell et al. 1956 Hart& & Mas-Colelll 2000).
equilibrium for
Search via RM has led to remarkable success in poker. However, RM only converges to a Nash cquilibrium in two-player zero-sum games and other special cases, and RM was never previously shown to produce strong policies in mixed cooperative/compettive game as complex as no-press Diplomacy. Nevertheless, we show that our agent exceeds the performance of prior agents and for the first time convineingly achieves human-level performance no-press Diplomacy. Specifically, we show that our agent soundly defeats previous agents, that our agent is far less exploitable than previous agents, that an expert human cannot exploit our agent even in repeated play, and, most
"Equal Contribution.

---

Published as a conference paper at ICLR 2021
importantly, that our agent ranks in the top 2% of human players when playing anonymous games on a popular Diplomacy website.
2 BACKGROUND AND RELATED WORK
Search has previously been used in almost every major game Al breakthrough, including backgam-
mon (Tesauro 1994). chess (Campbell et al. 2002). Go (Silver et al.] 2016; 2017| 2018)
poker (Moravčík et al. 2017 Brown & Sandholm 2017 2019b), and Hanabi (Lerer et al. 2020
A major exception is real-time strategy games (Vinyals
| Berner al. 2019). Similar to
SPARTA as used in Hanabi (Lerer et al. 2020), our agent conducts one-ply lookahead search (i.e.,
changes the policy just for the current game turn) and thereafter assumes all players play accord- ing to the blueprint. Similar to the Pluribus poker agent (Brown & Sandholm, 2019b), our search technique uses regret matching to compute an approximate equilibrium. In a manner similar to the sampled best response algorithm of Anthony et al. (2020), we sample a limited number of actions from the blueprint policy rather than search over all possible actions, which would be intractable.
Learning effective policies in games involving cooperation and competition has been studied exten- sively in the field of multi-agent reinforcement learning (MARL) (Shoham et al.) 2000). Nash-Q and CE-Q applied Q learning for general sum games by using Q values derived by computing Nash (or correlated) equilibrium values at the target states (Hu & Wellman| 2003 Greenwald et al.. 2003). Friend-or or-foe Q learning treats other agents as either cooperative or adversarial, where the Nash Q values are well defined Littman (2001). The recent focus on "deep" MARL has led to learning rules from game theory such as fictitious play and regret minimization being adapted deep reinforce- ment learning (Heinrich & Silver, 2016; [Brown et al.) 2019), as well as work on game-theoretic challenges of mixed cooperative/competine ria in the MARL setting (Leibo et al. 2017 Lerer & Peysakhovich 2017 2019).
settings such social dilemmas and multiple equilib-
benchmark for multi-agent Al research (Kraus & Lehmann 1988 Kraus et al. 1994, Kraus & Lehmann 1995, Johansson & Häärd 2005 Ferreira ct al. 2015). Recently, Paquette et al. (2019) applied imitation learning (IL) via deep neural networks on a dataset of more than 150,000 Diplomacy games. This work greatly improved the state of the art for no-press Diplomacy, which was previously a handcrafted agent (van Hall (013). Paqquette et al.) (2019) also tested reinforcement learning (RL.) in no-press Diplomacy via Advantage Actor-Critic (A2C) (Mnih et al., 2016). Annhhnyy et al. (2020) introduced sampled best response policy iteration, a self-play technique, which further improved upon the performance of Paquette et al. (2019).
Diplomacy in particular has served for decades
Deqquell,Paquettte
2.1 DESCRIPTION OF DIPLOMACY
The rules of no-press Diplomacy are complex; a full description is provided by Paquette et al. (2019). No-press Diplomacy is a seven-player zero-sum board game in which map of Europe is divided into 75 provinces. 34 of these provinces contain supply centers (SCs), and the goal of the game is for a player to control a majority (18) of the SCs. Each players begins the game controlling three or four SCs and an equal number of units.
The game consists of three types of phases: movement phases in which each player assigns an order to each unit they control, retreat phases in which defeated units retreat to a neighboring province, and adjustment phases in which new units are built or existing units are destroyed.
During a movement phase, player assigns an order to each unit they control. A unit's 's order may be to hold (defend its province), move to a neighboring province, convoy a unit over water, or support a neighboring unit's hold or move order. Support may be provided to units of any player. We refer to a tuple of orders, one order for each of a player's 's units, as an action. That is, each player chooses one action each turn. There the game's branching factor is massive and on some turns enumerating all actions is intractable.
average of 26 valid orders for each unit (Paquette et al. (001)). so
Importantly, all actions occur simultaneously. In live games, players write down their orders and then reveal them at the same time. This makes Diplomacy an imperfect-informatiin game in which an optimal policy may need to be stochastic in order to prevent predictability.
Diplomacy is designed in such a way that cooperation with other players is almost essential in order to achieve victory, even though only one player can ultimately win.
2

---

Published as a conference paper at ICLR 2021
A game may end in draw any turn if all remaining players agree. Draws common outcome among experienced players because players will often coordinate to prevent any individual from reaching 18 centers. The two most common scoring systems for draws are draw-size scoring (DSS), in which all surviving players equally split win, and sum-of-squares scoring (SoS), in which
player i receives score of of 2020). Throughout this paper use SoS scoring except in anonymous games against humans where the human host chooses a scoring system.
EjeN Cj where C2 is the number of SCs that player controls (Fogel
2.2 REGRET MATCHING
Regret Matching (RM) (Blackwell et al. 1936 Hart & Mas-Colell 2000) is an iterative algorithm that converges to Nash equilibrimm (NE) (Nash 1951) in two-player zero-sum games and other
special cases, and converges to a coarse correlated equilibrium (CCE) (Hannan 1957) in general.
We consider a game with / players where each player i chooses an action from a set of actions Ai- We denote the joint action as a (01, 02,-.... ...... the actions of all players other than as a-i. and the set of joint actions as A. After all players simultaneously choose an action, player i receives a reward of va(a) (which can also be represented as vi(a;, a-:)). Players may also choose probability distribution over actions, where the probability of action a; is denoted (a:) and the vector of probabilities is denoted TT.
Normally, each iteration of RM has computational complexity of [A,) In seven-player game, this is typically intractable. We therefore use a sampled form of RM in which each iteration has computational complexity of EieN [Ai)- We now describe this sampled form of RM.
Each agent i maintains an external regret value for each action a; E A,, which we refer to simply as regret. The regret iteration t is denoted (a;). Initially, all regrets are zero. On each iteration t of R.M. (a;) is set according to
(. Edea, max (FF
if Ee,EA max ((()) > 0
(as))
(I)
otherwise
1
Next, each player samples an action of from Ar according to प. and all regrets are updated such that
R = (as) + ((ana - Σ +((dd)ssa(.aa.,
(2)
afEAA
This sampled form of RM guarantees that ((a))) E O(VI) with high probability (Lanctot al. 2009). If R (as) grows sublinearly for all players' actions, as is the case in RM, then the aver- age policy over all iterations converges to a NE in two-player zero-sum games and in general the empirical distribution of players' joint policies converges to a CCE as + co.
In order to improve empirical performance, weighs updates on iteration t by El'] We also use optimism SSrgkanis et al. 2015). in which the most recent iteration counted twice when computing regret. Additionally, the action our agent ultimately plays is sampled from the final iteration's 's policy, rather than the average policy over all iterations. This reduces the risk of sampling a equilibiiuum action due to insufficient conver- gence. We explain this modification in more detail in Appendix
linear RM (Brown & Sandholm 2019a). which
3 AGENT DESCRIPTION
Our agent is composed of two major components. The first is a blueprint policy and state-value function trained via imitation learning on human data. The second is a search algorithm that utilizes the blueprint. This algorithm is executed on every turn, and approximates an equilibrium policy (for all players, not just the agent) for the current turn via RM, assuming that the blueprint is played by all players for the remaining game beyond the current turn.
In practice, rather than weigh iteration i's updates by f we instead discount prior iterations by _ in order reduce numerical instability. The two options mathematically equivalent.
3

---

Published as a conference paper at ICLR 2021
3.1 SUPERVISED LEARNING
We construct a blueprint policy via imitation learning on a corpus of 46,148 Diplomacy games col- lected from online play, building on the methodology and model architecture described by Paquette ctt al. (2019) and Anthony et al. (2020). A blueprint policy and value function estimated from hu- man play is ideal for performing search in a general-sum game, because it is likely to realistically approximate state values and other players' actions when playing with humans. Our blueprint su- pervised model is based on the DipNet agent from Paquette et al. (2019), but we make number of modifications to the architecture and training. detailed description of the architecture is provided in Appendix in this section we highlight the key differences from prior work.
We trained the blueprint policy using only a subset of the data used by Paquette et al. 2019)) specif- ically those games obtained from webdipl omacy. .rtt net) For this subset of the data, we obtained metadata about the press variant (full-press vs. no-press) which we add as a feature to the model, and anonymized player IDs for the participants in each game. Using the IDs, we computed ratings 8 for each player i and only trained the policy on actions from players with above-average ratings. Appendix B describes our method for computing these ratings.
Our model closely follows the architecture of [aquuette et al. (019)), with additional dropout of 0.4 between GNN encoder layers. We model sets of build orders single tokens because there are a small number of build order combinations and is tricky to predict sets auto-regressively with teacher foreing. We adopt the encoder changes of Anthony et al., (2020), but do not adopt their relational order decoder because it is more expensive to compute and leads to only marginal accuracy improvements after tuning dropout.
We make a small modification to the encoder GNN architecture that improves modeling. In addition to the standard residual that skips the entire GNN layer, we replace the graph convolution with the sum of a graph convolution and linear layer. This allows the model to learn hierarchy of features for each graph node (through the linear layer) without requiring a concomitant increase in graph smoothing (the GraphConv). The resulting GNN layer computes (modification in red)
1++1 Dropout (ACg + Zz-
(3)
where A is a learned linear transformation.
Finally, we achieve a substantial improvement in order prediction accuracy using a featurized order decoder. Diplomacy has over 13,000 possible orders, many of which will be observed infrequently in the training data. Therefore, by featurizing the orders by the order type, and encodings of the source, destination, and support locations, we observe improved prediction accuracy.
Specifically, in a standard decoder each order has a learned representation e,, and for some board encoding x and learned order embedding e.. P(o) = sof (m
With order featurization, we use é = c, + Afo, where fo are static order features and A is learned linear transformation. The order featurization we use is the concatenation of the one-hot order type with the board encodings for the source, destination, and support locations. We found that representing order location features by their location encodings works better than one-hot locations, presumably because the model can learn more state-contextual features
We add an additional value head to the model immediately after the dipnet encoder, that is trained to estimate the final SoS scores given a board situation. We use this value estimate during equilibrium search (Sec. 3.2 to estimate the value of Monte Carlo rollout after fixed number of steps. The value head is an MLP with one hidden layer that takes as input the concatenated vector of all board position encodings. A softmax over powers' SoS scores is applied at the end to enforce that all players' SoS scores sum to 1.
2 As noted by Anthony et al. 2020). DipNet uses variant of a GNN that learns separate weight matrix each graph location.
'W note the likelihood that a transformer with token-based decoding should capture a similar fcaturization, although Paquuttee et al. (2019) report worse performance for both a transformer and baken-based decoding.
*This slightly different than reported in Paqueete et al. 2019) because we compute token-accuracy treating a full set of build orders as a single token.
Policy accuracy for these model not comparable above because training data was modified.
4

---

Published as a conference paper at ICLR 2021
Model
Policy Accuracy
SoS v. DipNet
temp=0.5
temp=0.1
DipNet [Paquette et al. )019))
60.5%
0.143
combined build orders & encoder dropout
62.0%
encoder changes from Anthony et al. 2020
62.4%
0.150
0.198
switch to webdiplomacy training data only
61.3%
0.175
0,206
output featurization
62.0%
0.184
0,188
+ improved GNN layer
62.4%
0.183
0,205
+ merged GNN trunk
62.9%
0.199
0.202
Table 1: Effect of model and training data changes supervised model quality. We mcasure policy accuracy
well as average SoS score achieved by each agent against 6 of the original DipNet model. We measure the SoS scores in two settings: with all agents sampling orders temperature of either 0.5 0.1.
Eageet
Segut Hi-bitaake
0.50
0.5
0.40
045
0.8
02 250
512
1004
14
Figure 1: Left: Score of SearchBot using different numbers of sampled subgame actions, against 6 DipNet agents (Paquette al. (2019) temperature 0.1). of 14.3% would he tic. Even when sampling only two actions, SearchBot dramatically outperforms our blueprint, which achieves a score 20.2%. Middle: The effect of the number iterations of sampled regret matching on SearchBot performance. Right: The effect of different rollout lengths on SearchBot performance.
3.2 EQUILIBRIUM SEARCH
The policy that is actually played results from search algorithm which utilizes the blueprint policy. Let 8 be the current state of the game. On each turn, the search algorithm computes an equilibrium for subgame and our agent plays according its part of the equilibrium solution for its next action.
Conceptually, the subgame is well-defined game that begins at state s. The set of actions available each player is subset of the possible actions in state in the full game, and are referred to the subgame actions. Each player i chooses a subgame action a, resulting in joint subgame action a. After a is taken, the players make further decisions in the subgame. Instead, the players receive a reward corresponding to the players sampling actions according to the blueprint policy T for the remaining game.
The subgame actions for player are the Mr; highest-probabilii actions according to the blueprint model, where is the number of units controlled by player i and M hyperparameter (usually set to 5). The effect of different numbers of subgame actions is plotted in Figure (left).
Rolling out / the end of the game very expensive, so practice we instead roll out /² for small number of turns (usually or 3 movement phases in our experiments) until state s' is reached, and then use the value for s' from the blueprint's value network as the reward vector. Figure (right) shows the performance of our search agent using different rollout lengths. We do not observe improved performance for rolling out farther than 3 or 4 movement phases.
We compute policy for each agent by running the sampled regret matching algorithm described in Section 2.2 The search algorithm used 256 4,096 iterations RM and typically required between 2 minutes and 20 minutes per turn using single Volta GPU and CPU cores, depending on the hyperparameters used for the game. Details on the hyperparameters we used are provided in Appendix G
5

---

Published as a conference paper at ICLR 2021
4 RESULTS
Using the techniques descrihed Section g we developed an agent we call SearchBot. Our experi- ments focus two formats. The first evaluates the head-to-head performance of SearchBot playing against the population human players on a popular Diplomacy website, as well as against prior Al agents. The second measures the exploitability of SearchBot.
4.1 PERFORMANCE AGAINST A POPULATION OF HUMAN PLAYERS
The ultimate test of an Al system is how well it performs in the real world with humans. To measure this, we had SearchBot anonymously play no-press Diplomacy games the popular Diplomacy website webdip omwcy. net) Since there are 7 players in each game, average human perfor- mance is score of 14.3%. In contrast, SearchBot scored 26.6% + 3.2% Table shows the agent's performance and detailed breakdown is presented in Table Table Appendix G A qualitative analysis of the bot's play by three-time world Diplomacy champion Andrew Goff is presented in Appendix
Power
Bot Score
Human Mean
Games
Wins
Draws
Losses
All Games 26.6% + 3.2%
14.3%
116
16
43
57
Table 2: Average SoS of our agent in anonymous games against humans wwebdip pomacy .nt. Average human performance is 14.3%. Score in the case of draws was determined by the rules of the joined game. The + shows one standard error.
In addition to raw score, we measured SearchBot's performance using the Ghost-Rating sys- tem (Anthony 2020). which is a Diplomacy rating system inspired by the Elo system that ac- counts for the relative strength of opponents and that used to semi-officially rank players on webdip oma net Among no-press Diplomacy players on the site, our agent ranked 17 out of 901 players with a Ghost-Rating of 183.4 Details on the setup for experiments are provided in Appendix G
4.2 PERFORMANCE AGAINST OTHER AI AGENTS
In addition to playing against humans, we also evaluated SearchBot against prior AI agents from Pa- quette et al. (2019) (one based on supervised learning, and another based on reinforcement learning), our blueprint agent, and a best-response agent (BRBot). Table shows these results. Following prior work, we compute average scores in 'I games containing single agent of type A and six agents of type B. The average score of an identical agent should therefore be 1/7 zs 14.3%. SearchBot achieves its highest 1v6 score when matched against its own blueprint, since it is most accurately able to approximate the behavior that agent. It outperforms all three agents by a large margin, and none of the three baselines is able to achieve score of more than 1% against our search agent.
BRBot is an agent that computes a best response to the blueprint policy in the subgame. Like SearchBot, BRBot considers the kR; piobasitprobabiliiyy actions according the blueprint. Unlike SearchBot, BRBot searches over only its own actions, and rather than computing an equilibrium, it plays the action that yields the greatest reward assuming other powers play the blueprint policy.
Finally, we ran 25 games between one SearchBot and six copies of Albert (van Hall 2013). the state-of-the-arn rule-based bot. SearchBot achieved an average SoS score of 69.3%.
4.3 EXPLOITABILITY
While performance of an agent within population of human players is the most important metric, that metric alone does not capture how the population of players might adapt to the agent's presence.
"t the start of the game, the bot is randomly assigned to one of 7 powers in the game. Some powers tend perform better than others, the random assignment may influence the bot's score. To control for this, also report the bot's performance when each the powers weighed equally. Its score this case increases to 26.9% + 3.3%. Most games used draw-size scoring in case of draws, while our agent was trained based on sum-of-square scoring. If all games are measured using sum-of-squares, our agent scores 30.9% + 3.5%. OOr agent played games under different accounts; we report the Ghost-Rating for these accounts merged.

---

Published as a conference paper at ICLR 2021
1x 4. 6x
DipNet
DipNet RL
Blueprint
BRBot
SearchBot
DipNet
6.7% + 0.9%
11.6% + 0.1%
0.1% 0.1%
0.7% 1 0.2%
DipNet RL
18.9%
1.4%
10.5% + 1.1%
0.1% 0.1%
0.6% 0.2%
Blueprint
20.2% = 1.3%
7.5% = 1.0%
0.3% = 0.1%
0.9% 0.2%
BRBot
67.3% + 1.0%
43.7% = 1.0%
69.3% + 1.7%
11.1% + 1.1%
SearchBot
51.1% + 1.9%
35.2% + 1.8%
52.7% + 1.3%
17.2% + 1.3%
Table 3: Average SoS scores achieved by cach of the agents against each other. DipNet agents from (Paquette)
ct al. 2019) and the Blueprint agent use a temperature of 0.1. BRBot scores higher than ScarchBot against the Blueprint, but SearchBot outperforms BRBot in a head-to-head comparison.
For example, if our agent is extremely strong then over time other players might adopt the bot's playstyle. As the percentage of players playing like the bot increases, other players might adopt a policy that seeks exploit this playstyle. Thus, if the bot's policy is highly exploitable then it might eventually do poorly even if it initially performs well against the population of human players.
Motivated by this, we measure the exploitability of our agent. Exploitability of policy profile n (denoted e(T)) measures worst-cass performance when all but one agents follows т. Formally, the exploitability of æ defined as e(x) (max; (5(T), x_x) - (*))//N, where -- denotes the policies of all players other than i. Agent i's best response - & is defined as BR(T=+) arg max=, 0/4 (Ti, --)).
We estimate our agent's full-game exploitability in two ways: by training an RL agent to best re- spond to the bot, and by having expert humans repeatedly play against six copies of the bot. We also measure the 'local' exploitability in the search subgame and show that converges to an approxi- mate Nash equilibrium.
4.3.1 PERFORMANCE AGAINST A BEST-RESPONDING AGENT
When the policies of all players but one are fixed, the game becomes Markov Decision Process (MDP) (Howard, 1960) for the non-fixed player because the actions of the fixed players can be viewed as stochastic transitions in the "environment". Thus, we can estimate the exploitability of ı by first training best response policy BR(T=;) for each agent using any single-agent RL algorithm, and then computing EieN 02 C; -ii)/N. Since the best response RL policy will not be an exact best response (which is intractable to compute in a game as complex as no- no-press Diplomacy) this only gives
lower-bound estimate of the exploitability.
Following other work on environments with huge action spaces (Vinyals et al. 2019: Berner et al, 2.19), we use a distributed asynchronous actor-critic RL approach to optimize the exploiter pol- icy (Espeholt et al., 2018). We use the same architecture for the exploiter agent as for the fixed model. Moreover, simplify the training we initialize the exploiter agent from the fixed model.
We found that training becomes unstable when the policy entropy gets too low. The standard rem- edy is use entropy regularization term. However, due to the immense action space, an exact computation of the entropy term, Eg ps (a), is infeasible. Instead, we optimize a surrogate loss that gives an unbiased estimate of the gradient of the entropy loss (see Appendix D). We found this to be critical for the stability of the training.
Training an RL agent exploit SearchBot is prohibitively expensive. Even when choosing hyper- parameters that would result in the agent playing as fast as possible, SearchBot typically requires least full minute in order to act each turn. Instead, we collect a dataset of celf-play games of SearchBot and train supervised agent on this dataset. The resulting agent, which we refer to as SearchBot-clone, is weaker than SearchBot but requires only single pass through the neural net- work in order to act a turn. By training an agent to exploit SearchBot-clone, (likely) upper bound on what the performance would be a similar RL agent were trained against SearchBot.
obtain
We report the reward of the exploiter agents against the blueprint and SearchBot-clone agents in Figure 2 The results show that SearchBot-clone is highly exploitable, with best responder able to score at least 42% against SearchBot-clone Any score above 14.3% means the best responder is winning in expectation. However, SearchBot-clone appears to be much less exploitable than the

---

Published as a conference paper at ICLR 2021
Blueprint
0.55
SearchBot-clone
0.50
Sum of Squares
0.45
0.40
0.35
0.30
0.25
0
1000000
2000000
3000000
4000000
Training examples
Figure 2: Score of the exploiting agent against the blueprint and ScarchBot-clone as function of training time. We report the average of six runs. The shaded area corresponds three standard errors. We use temperature 0.5 for both agents as minimizes exploitability imitation learning of SearchBot, the exploitability of SearchBot is almost certainly lower than SearchBot-clone.
the blueprint. Since SearchBot-clone trained through
blueprint, which best responder can beat with of least 54%. Also, emphasize again that SearchBot is almost certainly far less exploitable than SearchBot-clone.
4.3.2 PERFORMANCE AGAINST EXPERT HUMAN EXPLOITERS
In addition to training a best-responding agent, we also invited Doug Moore and Marvin Fried, the 1st and 2nd place finishers, respectively, the 2017 World Diplomacy Convention (widely considered the world championship for full-press Diplomacy) play games against six copies of our agent. The purpose was to determine whether the human experts could discover exploitable weaknesses in the bot.
The humans played games against three types of bots: DipNet (Paquette et al., 2019) (with tem- perature set to 0.5), our blueprint agent (with temperature set to 0.5), and SearchBot. In total, the participants played 35 games against each bot; each of the seven powers was controlled by a human player five times, while the other six powers were controlled by identical copies of the bot. The performance of the humans is shown in Table While the sample size is relatively small, the results suggest that our agent less exploitable than prior bots. Our improvements the supervised learn- ing policy reduced the humans' score from 39.1% to 22.5%, which is itself large improvement. However, the largest gains came from search. Adding search reduced the humans' score from 22.5% to 5.7%. A score below 14.3% means the humans are losing on average.
Power
Human vs. 6 DipNet
Human vs. Blueprint
1 Human vs. SearchBot
All Games
39.1% %
22.5%
5.7%
Table 4: Average SoS of expert human playing against six bots under repeated play. A score less than 14.3% means the human unable to exploit the bot. Five games were played for each power for each agent, for a total 35 games per agent. For each power, the human first played all games against DipNet, then the blucprint model deseribed in Section 3.1 and then finally SearchBot.
4.3.3 EXPLOITABILITY IN LOCAL SUBGAME
We also investigate the exploitability of our agent in the local subgame defined by given board state, sampled actions, and assumed blueprint policy for the rest of the game. We simulate games between search agent and 6 DipNet agents, and plot the total exploitability of the average strategy of the search procedure as function of the number RM iterations, as well as the exploitability of the blueprint policies. Utilities u, computed using Monte Carlo rollouts with the same (blueprint)
8

---

Published as a conference paper at ICLR 2021
2x10-
2x10-1
Regret micetion
Regret Kin miseton Average
Exghiiabbity (8u5)
10
Exgloitabiily (Su5)
10.1-
6x10
6x
Regret Minirinetion
4x10-2
Blusprin.
4x
Slusprin: Slusprin:T=@051
Slusprint (Greedy)
3x10
102 3w10
10a
10
10a
107
10"
10
10a
heration
Ieration
Figure 3: Left: Distance of the RM average strategy from equilibrium as a function of the RM iteration, computed as the sum of all agents' exploitability in the matrix game in which RM is employed. RM reduces exploitability, while the blueprint policy has only slightly lower exploitability than the uniform distribution over the 50 sampled actions used in RM (i.e. RM iteration 1). For comparison,
human evaluations used 256-2048 RM itcrations, depending on the time per turn. Right: Comparison of convergence of individual strategics to the average of two independently computed strategies. The similarity of these curves suggests that independent RM computations lead to compatible cquilibria. Note: In both figures, exploitability is averaged over all phases in 28 simulated games; per-phase results are provided in Appendix P
rollout policy used during RM, and total exploitability for a joint policy is computed e(T))
>, c. ue(a;, --;) - (T). The exploitability curves aggregated over all phases are shown Figure 3 (left) and broken down by phase in the Appendix.
In Figure 3 (right), we verify that the average of policies from multiple independent executions of RM also converges an approximate Nash. For example, it possible that if each agent indepen- dently running RM converged to different incompatible equilibrium and played their part of it, then the joint policy of all the agents would not be an equilibrium. However, we observe that the exploitibility of the average of policies closely matches the exploitability of the individual policies.
5 CONCLUSIONS
No-press Diplomacy is complex game involving both cooperation and competition that poses ma- jor theoretical and practical challenges for past Al techniques. Nevertheless, our Al agent achieves human-level performance in this game with a combination of supervised learning human data and one-ply search using regret minimization. The massive improvement in performance from con- ducting search just one action deep matches larger trend seen in other games, such chess, Go, poker, and Hanabi, in which search dramatically improves performance. While regret minimization has been behind previous AI breakthroughs in purely competitive games such as poker, it was never previously shown to be successful in a complex game involving cooperation. The success of RM in no-press Diplomacy suggests that its use not limited purely adversarial games.
Our work points to several avenues for future research. SearchBot conducts search only for the cur- rent turn. In principle. this search could extend deeper into the game tree using counterfactual regret minimization (CFR) (Zinkevich et al. 2008). However, the size of the subgame grows exponentially with the depth of the subgame. Developing search techniques that scale more effectively with the depth of the game tree may lead to substantial improvements in performance. Another direction is combining our search technique with reinforcement learning. Combining search with reinforcement learning has led to tremendous success in perfect-information games (Silver et al. 2018) and more recently in two-player zero-sum imperfect-informan it remains to be seen whether similar search techniques can be developed for variants of Diplomacy that allow for coordination between agents.
games as well (Brown al. 2020). Finally,
9

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
We thank Kestas Kuliukas and the entire webddpl net team for their cooperation and for providing the dataset used in this research. We also thank Thomas Anthony, Spencer D., and Joshua M. for computing the agent's Ratisg. We additionally thank Doug Moore and Marvin Fried for participating in the human exploiter experiments in Section[.33.2 and thank Andrew Goff for providing expert commentary on the bot's play. Finally, we thank Jakob Foerster for helpful discussions.
REFERENCES
Thomas Anthony, Ghost-ratings, 2020. URL https://sites..ogle..oo///
webdipinfo//host ratings
Thomas Anthony, Tom Eccles, Andrea Tacchetti, János Kramár, Ian Gemp, Thomas C Hudson, Nicolas Porcel, Mare Lanctot, Julien Pérolat, Richard Everett, al. Learning play no-press diplomacy with best response policy iteration. arXiv preprint arXiv:2006.0463: 2020.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, al. Dota 2 with large scale deep reinforcement learning. arXiv preprint
2019.
David Blackwell et al. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1):1-8, 1956.
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, pp. eaao1733, 2017.
Noam Brown and Tuomas Sandholm. Solving imperfect-informene games via discounted regret minimization. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp- 1829-1836, 2019a.
Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, pp. eaay2400, 2019b.
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret mini- mization. In International Conference Machine Learning, pp. 793 802, 2019.
Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. Combining deep reinforcement learning and search for imperfect-informatior games. arXiv preprint arXiv:2007.13544 2020.
Murray Campbell, A Joseph Hoane Jr, and Feng-hsiung Hsu. Deep Blue. Artificial intelligence, 134 (1-2):57-83, 2002.
Arpad E Elo. The rating of chessplayers, past and present. Arco Pub., 1978.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. arXiv preprint arXiv: 1802.010 2018.
André Ferreira, Henrique Lopes Cardoso, and Luis Paulo Reis. Dipblue: A diplomacy agent with strategic and trust reasoning. In ICAART International Conference on Agents and Artificial Intel- ligence, Proceedings, 2015.
Brandon Fogel. URL 2020 03 To- Whom Tribute Is-Due Due The Next SSte----------------------ee in--in---one Sao-Scooing Systems pdf
To whom tribute due: The next step in scoring systems, 2020. http://windyiityweaseelll org/ www.ent//pload/////////tooo/ htg.a//eeeeeooooooooooooooonnono
Amy Greenwald, Keith Hall, and Roberto Serrano. Correlated q-learning. In ICML, volume 20, pp. 242, 2003.
James Hannan. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 3:97-139, 1957.
10

---

Published as a conference paper at ICLR 2021
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5)11127-1150) 2000.
Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect- information games. arXiv preprint urXiv:1603.01122 2016.
Ralf Herbrich, Tom Minka, and Thore Graepel. Trueskill a bayesian skill rating system. In Advances in neural information processing systems, pp- 569-576, 2007.
Ronald A Howard. Dynamic programming and markov processes. 1960.
Junling Hu and Michael P Wellman. Nash q-learning for general-sum stochastic games. Journal of machine learning research, 4(Nov)::039--169) 2003.
Stefan J Johansson and Fredrik Håård. Tactical coordination in no-press diplomacy. In International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 423-430, 2005.
Sarit Kraus and Daniel Lehmann. Diplomat, an agent in multi agent environment: An overview. In IEEE International Performance Computing and Communications Conference, pp. 434-435. IEEE Computer Society, 1988.
Sarit Kraus and Daniel Lehmann. Designing and building negotiating automated agent. Compu- tational Intelligence, 11()):322-17,, 1995.
Sarit Kraus, Eithan Ephrati, and Daniel Lehmann. Negotiation in a non-cooperative environment. Journal of Experimental & Theoretical Artificial Intelligence, 3(4):255 281, 1994.
Mare Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling. Monte carlo sampling for regret minimization in extensive games. In Advances in neural information processing systems, pp. 1078-1086, 2009.
Joel Z Leibo, Vinicius Zambaldi, Mare Lanctot, Janusz Marecki, and Thore Graepel. Multi-agent reinforcement learning in sequential social dilemmas. arXiv preprint 17Xiv:1702.03037, 2017.
Adam Lerer and Alexander Peysakhovich. Maintaining cooperation in complex social dilemmas using deep reinforcement learning. arXiv preprint arXiv: (707.0007 2017.
Adam Lerer and Alexander Peysakhovich. Learning existing social conventions via observation- ally augmented self-play. In Proceedings the 2019 AAAI/ACM Conference Al, Ethics, and Society, pp. 107-114. ACM, 2019.
Adam Lerer, Hengyuan Hu, Jakob Foerster, and Noam Brown. Improving policies via search in cooperative partially observable games. In AAAI Conference on Artificial Intelligence, 2020.
Michael I. Littman. Friend-or-foe q-learning in general-sum games. In ICML,, volume 1, pp. 322- 328, 2001.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pp. 1928-1937, 2016.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morril, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-511) 2017.
John Nash. Non-cooperative games. Annals of mathematics, pp. 286-295, 1951.
Philip Paquette, Yuchen Lu, Seton Steven Bocco, Max Smith, O-G Satya, Jonathan K Kummerfeld, Joelle Pineau, Satinder Singh, and Aaron Courville. No-press diplomacy: Modeling multi-agent gameplay. In Advances in Neural Information Processing Systems, pp. 4474-4485, 2019.
Yoav Shoham, Rob Powers, and Trond Grenager. Multi-agent reinforcement learning: critical
survey. Web manuscript, 2, 2003.
11

---

Published as a conference paper at ICLR 2021
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 429(7587)448,, 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Mattew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354, 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play, Science, 362(6419): 1144, 2018
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regu- larized learning in games. In Advances in Neural Information Processing Systems, pp. 2989-2997, 2015.
Gerald Tesauro. TD-Gammon, a self-teaching backgammon program, achieves master-level play. Neural computation, 6(2):215-219, 1994.
Jason van Hal. Diplomacy AI Albert, 2013. URL /tt.ttss///btte..ogg...o/////11
dippomacyai//
Oriol Vinyals, Igor Babuschkin, Wojciech M Czamecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)350-354, 2019.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. Advances neural information processing systems, pp- 1729-1736, 2008.
12

---

Published as a conference paper at ICLR 2021
A FULL IMITATION LEARNING MODEL ARCHITECTURE DESCRIPTION
In this section, provide full description of the model architecture used for the supervised Diplo- macy agent.
[Powers]
ENG
Policy Decoder
Beard Moves
Emb actions
FRA
Beard State
Festurized
LSTM
Order PAR
Arras
200
Featurized Decoder
Order
RUH
200
State layer, D=120)
Featurized Decoder
Encoder GNN
LSTM
Order BUR
Encoder
|8 layers, D-120)
#2x120
81x120
Merged [8 layers, D-240)
Value Decoder
Vaus
YewG
VYRA
19440
ViTA
81x240
Loc Feats
layer, 120D)
VGER
Vous
VrUR
Figure 4: Architecture of the model used for imitation learning in no-press. Diplomacy.
Board State Encodins
1. Type (Aryy Fleet, None)
2. Unit Power (AUS, FRA, ITA, GER, RUS, TUR, None)
10
3. Builtibble Removabll
Dislodged Type
Fleet,
TUR, None)
6. Area Type (Land, Watter Coest)
7. Supply Center Owner (AUS, TUR, None)
Senson (priing foll, Winter)
Build Mumbers (latager
powe)
Type (MoPress,
Figure 5: Features used for the board state encoding.
prev layer
Encoder GNN Layer
GraphConw
(Independent
Linear
BatchNorm RelU Dropout
next layer
Figure 6: Architecture of an encoder GNN layer.
13

---

Published as a conference paper at ICLR 2021
The model architecture is shown in Figure 4 It consists of a shared encoder and separate policy and value decoder heads.
The input to the encoder is set of features for each of the 81 board locations (75 regions 6 coasts). The features provided for each location are shown in F The first 7 feature types (35 features/location) match those of Paquette al. (2019), and the last three feature types (in italics) are for global board features that are common across all locations: a 20-d embedding of the current season; the net number of builds for each power during build phase; and a single feature identifying whether it is a no-press or full-press game.
The encoder has two parallel GNN trunks. The Current State Encoder takes the current board state as input, while the Previous State Encoder takes the board state features from the last movement phase, concatenated with 20-dimensional feature at each location that a sum of learned embeddings for each order that ocurred at this location during all phases starting at the last movement phase.
The current board state and previous board state are each fed to an 8-layer GNN, whose layer ar- chitecture is shown in Figure [6] The GraphConv operation consists of a separate learned linear transformation applied at each board location, followed by application of the normalized board ad- jacency matrix [8] In parallel with the GraphConv is linear layer that allows the learning of a feature hierarchy without graph smoothing. This is followed by batchnorm, a ReLU non-linearity, and dropout probability 0.4. The 81 x 120 output features from each of these GNNs are then concate- nated and fed to another 8-layer GNN with dimensional 240. The output of this encoder are 240 features for each board location.
The value head takes as input all 81 x 240 encoder features concatenated into a single 19440- dimensional vector. An MLP with single hidden layer followed by a softmax produces predicted sum-of-squares values for each power summing to 1. They are trained to predict the final SoS values with MSE loss function.
The policy head aego--egressively predicts the policy for a particular power one unit at time with 2-layer LSTM of width 200. Unit orders are predicted the global order used by Paquette et al. (2019). The input to the LSTM at each step is the concatenation of (a) the 240-d encoder features of the location whose orders are being predicted; (b) 60-d embedding of the power whose policy is being computed; (c) an 80-d embedding of the predicted orders for the last unit.
A standard decoder matrix can be thought of as learned vector for each valid order, whose dot product with the LSTM output predicts the logit of the order probability given the state. We featurize these order vectors as shown in Figure The decoder vector for "PAR RUH- BUR" for example, would be the sum of a learned vector for this order and learned linear transformations of (a) one-hot features for the order source (RUH), destination (BUR), type (S); and (b) the encoder features the source (RUH) and destination (BUR) locations.
Build orders are different than other order types because the set of source locations for build orders is not known in advance. So the decoder needs to predict an unordered set of build orders during build phase, which is tricky to compute correctly with an autoregressive decoder and teacher forcing. Luckily, since power can only build in its 3-4 home supply centers, there are only 170 sets of build orders across all powers, so we just consider each possible set of builds as a single order, rather than predicting them one by one. We do not do featurized order decoding for build orders.
B COMPUTING PLAYER RATINGS IN HUMAN DATA
To compute player ratings, we used regularized logistic outcome model. Specifically, we optimize a vector of ratings s by gradient descent that minimizes the regularized negative log likelihood loss
[(s|D)
Σ -o: 85) X/s|2
(U)ED
over dataset D consisting of all pairs of players (i.j) where player achieved a "better" outcome than player j in a game. We found this approach led to more plausible scores than Elo (Elo 1978) or TrulSkill (Herbrich et al. 2007) ratings.
"s noted in Anthony et al. 2020), this differs from standard graph convolutional layer in that separate weights are used for each board location.
14

---

Published as a conference paper at ICLR 2021
Location Features (From Encoder)
+ Decodor 15TM
PAR
BEL
[Areas]
HOL
Score (logit) for "PAR RUH- BUR"
Order Src Encoder
RUH
[Unear]
BRE
BUR
Encader
[Linar]
Mona ammaa mana
Order Feat Encoder (Unear)
Order features for "PAR S RUH - BUR"
1. Order type (Hold, Move, Support, Comvoy, None)
2. Undertying order type (Hold, Move, Convos, Monel
3. Undertying order location (PAR, BRE,..)
Underfynn order det (191) sitt.... -.l
Underfying order
Figure 7: Illustration of featurized order decoding.
Paquette et al. (2019) took an orthogonal approach to filter poor players from the training data: they only trained on "winning" powers, i.e. those who ended the game with at least 7 SCs. This filtering is sensible for training a policy for play, but is problematic for training policies for search. In a general-sum game, it is crucial for the agent to be able to predict the empirical distribution of actions even for other agents who are destined to lose.
C SEARCH EXAMPLE
The listing below shows the policy generated by run of our search algorithm for the opening move of Diplomacy when running for 512 iterations and considering possible actions per power.
For each possible action, the listing below shows
probs The probability of the action in the final strategy.
bp_p The probability of the action in the blueprint strategy.
avg_u The average predicted -f-uuursss utility of this action.
orders The orders for this action
ACSTRIA
avg_ ovg_utiiity--. 1.15622
proba
ba_p
avg_u
ordezs
0.53548
0.13268
0.15637
I'A VCE
ZRI' "F TRI ALB 13 BUD SER!)
0.46092
0.52308
0.14439
GAL'
4F
SEA')
0.00122
0.03470
0.14861
281',
FAI
ALB ALB
GAL")
0.00077
0.03031
0.11967
("A VCE
BUD",
<F DR1
BUD SER')
0.00035
0,05173
0.11655
I'A VTE
GAL" <P Ph1
A. VEN! BOD SER)
0.00015
0.04237
0.12087
GAL' 4F
BID
0.00007
0,14803
0.09867
GNL" 1F TRI
VEN
BERT)
0.00000
0,04209
0.03997
['A VEE BY, KP T&T
ET,
'A BUD Hr]
SSGLAND
svq_utillty=o..
07112
hp.p
evg
0.41978
0.20369
0.07151
1ON
YOR')
0.36925
0.29343
0.07161
[12 EDI NWO
4F
128
KTB ,
LVP
YOR')
0.10536
0.06897
0.07282
PF RDT
NTH
FF 1ON
ENG
'A TVP
MATA)
0.07133
0.36475
0.03381
4F
0.05174
0.01649
0.07202
NIH
88
10N
EDI")
0.00249
0,60813 3
0.5660
( RDT
NWG?
79 1ON
XTM
IVP
MAIT)
0.00006
0,00320
0.06878
( HDI
NAC
10N
ENG
CA
LVP
EDI")
TRANCR avg.ut
i1ity=0.22159
proba
baLe
orders
0.92038
0.090115
0.21772
1 BRF
MAC' AA PAR
GAS
'A MAR SUR()
0.06368
6.42617
0.18878
AA
0.00317
0.07987
0.16941
(1B
HhD" 'A FAR
FIC
BUR")
0.00049
0.6561 6
0616929
(F ARF
FA PAR
NUR/
MAR SPAr)
0.00023
0.17340
0.67685
(FB BRE
HAO'
AA FA2
BUR
MAn SPAT)
0.00004
0.68629
EIC
0.00081
0,09291
0, 15828
( RND PAR
NURY,
PAR
15

---

Published as a conference paper at ICLR 2021
0.c0000
0.05872
(/2 BY, ET,
BC1
GERKINY
wwt_utt111y10.222555
probo
tg_p
avg_u
ozdezs
0.29050
0.01362
0.21360
DEN!
AA MIN
RIE!))
0.28319
0.02358
0.21381
DEN"
MUN
BURT
XIE
0.16508
0.01628
0.21739
I1 XIE DEX
AA MUN
H'
BER KIBT)
0.04168
0.21979
0.21350
(re KIE DEN"
AA MUN
BORY
BER KIET)
0.01212
0.47409
0.21287
MUN
RIE!)
0.00003
0.14238
MUN
RIE
0.00000
0.16896
0.13748
[12 KIE
BOE
MIN
ROB
BER SIE!)
0.00000
0,03355
0.01917
IYF XIE BY, 13. NUW E5, TA BER B01
proba
ba_p
avQ_u
ozdezs
0.41700
0.19181
0.13609
["2 NME 108
RCN
APD VEB
VEN S 18I'1
0.25931
0.07652
0.12465
(rg NAP
108
AA RGN
KA VEN 7RI')
0.13084
0.29314
0.12831
0.C97ED
0.03761
0.15193
19W
AA RCN
TRT))
0.69412
0.16622
0.13539
(18 MAP
108
AA RCM
APO1
VEN BT
0.00034
0.05575
0.11554
1r MAE
1087
1A BCH
A20'
VEN
PIET)
0.00028
0.10953
0.c0000
0,05589
(1B BY,
ET, BC1
RCSSIA
probs
urdeess
0.64872
0.05968
0.06804
UKRY
WAR 52. WAR
BLX'
0.28869
0.07200
0.05801
I1 9C8/8C /8C
BOT
SIP'.
BLM
0.64914
0.67998
0.05925
(18 SCB /9C
BOT
URR
XA MAR
GAL
SEV
BLA
0.01133
0.01147
0.05023
(rg SCR
BOT"
*A. 1428
SEV <A WAR
DK3
SEV
0.00120
6,02509
0.05008
0.00064
11B 8T9/3C
BOT
MCB
STPT.
MAR
SEV
BLAC
0.00027
0,01591
0.04404
(18 /BC
BOT'
SEV*, XX WAR
GALY
SEV
ROW
0_00000
0,03655
0.02290
F 5TP /SC BY 1A MDS Pf, YA WAR If, SEV B1
SURKEY
proba
ba_p
avq_u
ozdezs
0.82614
0.25313
0.13787
I ANK
ITLA*, A EMY
ARMY
CON ROT/1)
0.14130
0,00651
0.12942
(1B ANK
BLK'
A
ANE
COX
BULT)
0.00074
0.01740
0.11270
COW
EMY
BUL()
0.00069
0.05901
0.12192
[18 ANK
CON
AA SXC
ANEY
CON
BUL()
0.00030
0,00750
0.11557
1 ANK
GOX!
A
SMY 11
DON
0.00001
0.00598
0.10175
0.00001
0,03314
0,04464
(1B ANK BY,
COX
D RL DETAILS
Each action in the MDP is sequence of orders (o1....,o.) 0.). The probability of the order under policy me is defined by LSTM in auto regressive fashion, i.e., ne (a) I (oo(os)o) ... 0z-1) 1))- To make training more stable, we would like to prevent entropy H (TT) := = -uwwo log( no (a) from collapsing to zero. The naive way to optimize the entropy of the joint distribution is to use a sum of entropies for each individual order, i.e., d H ())) Ei= (TT(( ....)) However, de
we found that this does not work well for our case probably because there are strong correlations
between orders. Instead we use an unbiased estimate of the joint entropy that is agnostic to the size of the action space and requires only to be able to sample from model and to adjust probabilities of the samples.
Statement 1, Let To ()) be a probability distribution over a discrete set A, such that Va E A To(a) smooth function of vector of parameters 0. Then
d dg
(H(T(())) = EEanoo (1 + log Ta(a)) log (o()..
dg
16

---

Published as a conference paper at ICLR 2021
Proof. Proof is similar to one for REINFORCE:
d =
(TT())))
(- Earni log mo(a))
d8
d0
d
Σ
Ta(a) log
d0
aaAA
Σ
d
TTa (a) log (a)
Te(a) d
log (a(a) + log no d
= Σ
d0 =e((a)
d0
(a(a) d
Σ
log (a( + log To ( d0
log To(a)
d8
oEA
Σ TT(a) (1+ log To(a)) d log me(a)
do
aEA
= En
(1+ d0
d
log mo(a))
E SUBGAME EXPLOITABILITY RESULTS
Figure 8 plots the total exploitability of joint policies computed by RM in the subgame used for equilibrium search at each phase simulated Diplomacy games.
F PLAYING ACCORDING TO THE FINAL ITERATION'S POLICY IN RM
As described in Section 2.2 in RM it is the average policy over all iterations that converges to an equilibrium, not the final iteration's policy. Nevertheless, in our experiments we sample an action from the final iteration's 's policy. This technique has been used successfully in past poker agents (Brown& & Sandholm 2019b). At first glance this modification may appear to increase ex- ploitability because the final iteration's 's policy is not equilibrium and in practice is often quite pure. However, in this section we provide evidence that sampling from the final iteration's 's policy when using a Monte Carlo version of RM may lower exploitability compared sampling from the average policy, and conjecture an explanation.
Critically, in the sampled form of RM the final iteration's policy depends the random seed, which is unknown to the opponents (while we assume opponents have access to our code, we assume they do not have access to our run-time random seeds). Therefore, the opponent is unlikely to be able to predict the final iteration's 's policy. Instead, from the opponent's perspective, the policy we play is sampled from an average of final-iteration policies from all possible random seeds. Due to randomness in the behavior of sampled R.M, we conjecture that this average has low exploitability.
To measure whether this is indeed the case, we ran sampled RM for 256 iterations on two Diplomacy situations (the first turn in the game and the second turn in the game) using 1,024 different random seeds, and averaged together the final iteration of each run. We also ran sampled RM on two random matrix games with 10,000 different random seeds. The results, shown in Table 5) confirm that averaging the final iteration over multiple random seeds leads to low exploitability.
We emphasize that while we measured exploitability in these experiments by running sampled regret matching over multiple random seeds, we only need to run for a single random seed in order to achieve this low exploitability because the opponents do not know which random seed we use. Unfortunately, measuring the exploitability of the final iteration over 1,024 random seeds is about 1,024x expensive as measuring the exploitability of the average strategy over all iterations (and
17

---

Published as a conference paper at ICLR 2021
Gamee 1
Game
10a
10'
1908
1907
11044
Bioloaaiity 1563)
Erolotabityy (5e5)
1906
1905
10-4.
10-4
1904
1903
1902
10
10
10
10a
30*
10a
10
10
10a
10'
Ieeraton
Iteration
Game 3
Game
1908
Exclatabiity 1565)
1907
1906
1906
1905
1904
1903
1903
1900
1902
10'7
1901
1901
10a
10*
10A
10r
Gamee
Game
10a
1907
10
1904
Explatabiity (505)
Exploisbiitty (5a5)
10-1.
1904
10-1
10'7
1901
10
1901
Iteration
Iteration
10
1912
Explaiabitty 1505)
10-4-
1305
1904
1903
1902
10'7
102
10a
10a
10*
Reration
Figure 8: Exploitabilityy as function of RM iteration each phase of simulated games with search agent (until the game ends the search agent is eliminated). Aggregate results in Figure
even 1,024 seeds would provide only an approximate upper bound on exploitability, since computing the true exploitability would require averaging all possible random seeds). Therefore, in order to keep the computation tractable, we measure the exploitability the average strategy of single runs in Figure
18

---

Published as a conference paper at ICLR 2021
Method
Subgame
Subgame
10x10 Random
100x100 Random
Ave. Final Policies
0.00038
0.0077
0.019
0.063
Ave. of Ave. Policies
0.00027
0.0074
0.035
0.092
Single Ave. Policy
0.00065
0.0140
0.078
0.225
Single Final Policy
0.00880
0.0580
0.478
0.706
Table Exploitability 256 iterations of RM using either the final iteration's 's policy or the average iteration policy, and either using the policy from single run or the policy average over multiple runs. Subgame and Subgame 2 are subgames from Diplomacy S1901 and F1901. respectively. 10x10 Random and 100x 100 Random random matrix two-player zero-sum games with entries having value in [0, 1) sampled uniformly randomly. For Subgame
Subgame "Ave. Final Policies" and "Ave. of Ave. Policies" are the average of 1,024 runs with different random seeds. For 10x10 Random and 100x 100 Random, 10,000 seeds were used.
G DETAILS ON EXPERIMENTAL. SETUP
Most games wwwdiploooee net were played with 24-hour turns, though the agent also played in some "live" games with 5-minute turns. Different hyperparameters were used for live games non-live games. In non-live games, typically ran RM for 2,048 iterations with rollout length of movement phases, and set M (the constant which is multiplied by the number of units determine the number of subgame actions) equal 5. This typically required about 20 minutes to compute. In live games (including games in which one human played against six bots) and in games against non- non-human opponents, we ran RM for 256 iterations with rollout length of movement phases, and set M equal to 3.5. This typically required about 2 minutes to compute. In all cases, the temperature for the blueprint in rollouts was set to 0.75.
Power
Score
Human Mean
Games
Wins
Draws
Losses
All Games
26.6% + 3.2%
14.3%
116
16
43
57
Normalized By Power
26.9% + 3.3%
14.3%
116
16
43
57
Austria
31.4% + 9.4%
11.0%
17
3
6
8
England
38.0% 10.1%
12.6%
6
France
19.0% + 6.2%
16.9%
19
1
8
10
Germany
36.8% + 8.0%
15.0%
2
4
Italy
31.5% + 10.5%
11.6%
14
3
5
6
Russia
17.6% + 7.6%
14.8%
18
2
4
12
Turkey
14.6% + 7.0%
18.2%
16
4
11
Table 6: Average score of our agent anonymous games against humans on webdiplomacy .net Average human performance is 14.3%. Score in the case of draws was determined by the rules of the joined game. The + shows one standard error. Average human performance was calculated based on SoS scoring of historical games webdi cmacy. net
The experiments on webdiplomacy net occurred over three-monte timespan, with games commonly taking one to two months to complete (players are typically given 24 hours to act). Freezing research and development over such a period would have been impractical, so our agent was not fixed for the entire time period. Instead, serious bugs were fixed, improvements to the algorithm were made, and the model was updated.
In games on webdip ceciiipoomman lomacy net, draw was submitted if SearchBot did not gain center in two years, or if the agent's 's projected sum-of-san ofun-of--uuarss score was less than the score it would achieve way submit draws through wnwwedidploma API, draws were submitted manually once the above criteria was satisfied. Games against other bots, shown in Table automatically ended in draw if no player won by 1935.
by an immediate draw. Since there
.nt
19

---

Published as a conference paper at ICLR 2021
Power
1 Human vs. 6 DipNet
Human vs. Blueprint
1 Human vs. 6 SearchBot
All Games
39.1%
22.5%
5.7%
Austria
40%
20%
0%
England
28.4%
20%
0%
France
20%
4.3%
40%
Germany
40%
33%
0%
Italy
60%
20%
0%
Russia
40%
20%
0%
Turkey
45.1%
40%
0%
Table 7: Average SoS score one expert human playing against six bots under repeated play. A score less than 14.3% suggests the human is unable to exploit the bot. Five games were played for cach power for cach agent, for total of 35 games per agent. For each power, the human first played all games against DipNet, then the blueprint model descrihed in Section 3.1 and then finally SearchBot.
H QUALITATIVE ASSESSMENT OF SEARCHBOT
Qualitatively, we observe that SearchBot performs particularly well in the early and mid game. However, we observe that it sometimes struggles with endgame situations. In particular, when it is clear that one power will win unless the others work together to stop it, SearchBot will sometimes continue to attack its would-be allies. There may be multiple contributing factors to this. One im- portant limitation, which we have verified in some situations, that the sampled subgame actions may not contain any action that could prevent loss. This is exacerbated by the fact that players typically control far more units in the endgame and the number of possible actions grows expo- nentially with the number of units, the sampled subgame actions contain a smaller fraction of all possible actions. Another possible contributing factor is that the state space near the end of the game far larger, there is relatively less data for supervised learning in this part of the game. Finally, another possibility is that because the network only has a dependence on the state the board and the most recent player actions, is unable sufficiently model the future behavior of other players in response to being attacked.
Although the sample size is small, the results suggest that SearchBot performed particularly well with the central powers of Austria, Germany, and Italy. These powers are considered to be the most difficult to play by humans because they are believed require an awareness of the interactions between all players in the game.
I ANECDOTAL ANALYSIS OF GAMES BY EXPERT HUMAN
Below present commentary from Andrew Goff, three-time winner of the world championship for Diplomacy. The comments are lightly edited for clarity. This is intended purely as anecdotal commentary from selection of interesting games.
GAME
net htt.://ccyy..ee/ooooooo/gggggaao 1D211928 (bot as Germany)
The bot is doing a lot of things right here, particularly if they are playing for an 18. The opening to Tyrolia is stronger than most players realise, and the return to defend Munich is exactly how to play it. Building fleets hyper-aggressive but in Gunboat is good indication move, particularly after the early fight between England and France. 1902 the board breaks very favourably for Germany, but its play is textbook effective. The bounce Belgium in Fall a very computer move... 9/10 times it bounces it does in the game, but the 1/10 times it is train wreck, England retreats to Holland and France is angry so it is a risk human players don't often take.
1903 is bit wilder. The play in the North is solid (Scandinavia is more important than England centres I agree) but the move to Burgundy seems premature. gunboat it is probably fine. but why not Ruhr then Belgium? Why not give France greater opportunity suicidally help you against
20

---

Published as a conference paper at ICLR 2021
England and Italy. suspect this is artefact of being trained against other Al that would not do that?
1904 has nice convoy (to Yorkshire) and strong moves over the line into Russia. It is all good play, but in fairness the defences put up by the opponents are weak. After that the next few years are good consolidations
little fidgety in Norway but not unreasonable. 1907 see Turkey do Russia and from here you should expect an 18- a terrible move by Turkey. It should be all over now and is just clean-up. Even as Turkey and Russia patch things up quite quickly, Turkey picks off an Italian centre and now it really is all over. France collapses, Germany cleans up professionally, and score one for AI.
Overall, Germany's play was aggressive early and then clinical late. Some pretty bad errors by Turkey gave Germany the chance, and they took 9/10
GAME 2
-0m12999mm (bot Italy)
Spoiler Alert: this one isn't so good. The opening sleepy and the attack on Vienna in 1902 is just wrong against human players. Then the whole rest of the board is playing terribly too Austria goes for a Hail Mary by attacking their only potential ally... Turkey tries convoy that if had worked would suggest collusion... this is all terrible. Now everyone is fighting everyone and meanwhile Genmany and France have cleaned up England. By 1905 at least the AI has given up attacking Austria for the time being- picking the competent over the nonsense and the day is saved as France and Germany descend into brawling over the spoils.
It doesn't 't last. Another year another flip/flop. The same attempted trick again (move to Pie then up to Tyrol). Italy requires patience and the Al is showing none at all. Austria gets around to Armenia they're playing OK tactically but they have a mad Italian hamstringing them both. Meanwhile France is now officially on top and will present a solo threat soon. The start of 1908 sees Italy finally making some progress against Austria, but France is too big now... it is all strategically mess from 1902 onward and it shows. As positive though, some of the tacties here are first rate... Nap- Alb is tidy, the progress that is being made against Austria is good in isolation.
Then follows 8 years of stalemate tactics none of which is interesting. Italy played well, was lucky Turkey didn't take their centres at the death, and that's all there is.
Overall, I'd say this looked like human player. And just like most human players: rubbish at Italy. 3/10
GAME 3
(bot Austria)
I was about to say 1901 was all boring and then the Al in Austria has built a flect. That's wild. With Italy attacking France it isn't unreasonable... but still. Anyhow the game continues into 1903 he deploys that fleet beautifully. Italy just doesn't care about - which is strategically very poor by them. The weird thing here is that Austria seems more intent on attacking Russia than Turkey. If you have the second fleet then surely Turkey is the objective, otherwise you't 're splitting forces a lot. In gunboat it is... passable. In non-Gunboar this is all-but suicidal. If RT get their heads together they'll '1 belt Austria, but as we see in this game they don't 't so Austria does well from it. It's similar to game I in that this is the most aggressive way play.
One thing really stands out here and that is that the Al is making the moves that are most likely to result in an error by the opponent (See: Turkey, S1904). This present elsewhere but this turn captures it beautifully. Why did Smyrna go to Con? What shocker. But without moves that can take advantage of errors like this it doesn't matter. Italy also makes a key mistake here: Mar holds instead of + Gas. They've lost momentum on the turn Austria gains lot. In Fall Austria builds 3 armies and Italy gets nothing and the chance is there to solo.
"To "dot" a player in Diplomacy means attack an ally for a gain of only one center.
21

---

Published as a conference paper at ICLR 2021
The stab comes immediately and appropriately, and Austria has fleet in the Black Sea and Aegean. Italy is a turn too late into the Northern French centres. There a subtle problem to the Al's play here though, not seen in the Germany game. There's 's effort to move over the stalemate positions. At this point in the German game it moved aggressively into Russia... here it ignores Germany and aims for the Russian centres again and that shows lack of awareness of where the 18th centre must come from.
The game continues and Austria cleans up the Eastern centres very effectively. like ignoring the German move to Tyrolia and Vienna - not very human but also very correct (as we will see there's nothing there support it so it just gets yeeted in Spring 1908. However, Spring 1908 has tactical error (one of the few outright wrong moves I've seen!) where:
Gre s Adr Ion; Aeg s Adr lon; Adr Ion.
You only need one support and Adriatic is more useful than Greece... so better is: Gre lon; Aeg s lon; Adr Apu.
This allows Nap Rom; Apu Nap next turn. A very odd mistake as this is the kind of detail I'd expect AI to do better than human. Ultimately doesn't matter so much as Italy going to concede Tunis to set up rock-solid defence of Spa/Mar. But still.
And now. ... The ultimate "Not good". For four turns in a row England fails to defend StP correctly and the Al misses it and therefore the chance to get 18. England is attacking Livonia with 3 and moving only one unit into StP behind it. Germany is not cutting Prussia. So:
Pru Lvn, War Lvn, Lvn s Mos - StP, Mos - StP
And Austria gets an 18. This a really bad miss by the Al (not to mention England). As in every decent human player or better would have got an 18 here.
Overall, Austria played a really good game but didn't do some of the things had high hopes for after game 1 - they didn't 't move over the stalemate and they didn't 't play as tactically precisely. Then the miss at the end... makes me feel good about being human. 7/10 until the last move, but in the end 5/10.
GAME 4
(bot as Russia)
StP Fin. Cute. The whole board just completely opens in the other direction from Russia they get 7 centres at the end of 1901. wish that happened to me when played Russia. Of course, now everyone moves against Russia so we'll see how the Al defends. Italy has just demolished France, which makes this a strange game strategically too.
F1903 you could write whole article on. What it looks like is Russia and Turkey successfully signalling "alliance" and that is impressive for an AI. The tactics are good - -ignorngg Warsaw to get Budapest, but the bounce in Sweden and drop Baltic so much. Why England didn't 't support Den Swe is a mystery and it is probably all over for Russia if they do. But they didn't 't so play on.
The English play from here on is just great. F1905 the move through Swe Den the height of excellence. It obviously helped Russia too, but from an awful position there is now real potential... what great move. Focussing on the AI just gets the tacties right. pushes Germany back and nails the timing to take Vienna. But then it builds a Fleet in Sev. No no no. An Army in Sev is better tactically and also doesn't 't tip off the Turk. Just as got the signalling right earlier it got exactly wrong here.
In the end the Turk starts blundering under pressure so as the kids say: "Whatever". The F1906 move of Adr - Alb instead of supporting Tri is egregiously bad and turns a bad position into terrible one. They proceed to self-immolate and Russia and Italy are cruising now, and England's 's play remains first class. The clean-up of Turkish dots is effective, and then the rest is quite boring.
The biggest thing that struck me about this game (apart from England's 's brilliant recovery) was that Russia didn't t manage unit balance well. Disbanding their only Norther fleet was a long-tem error even if it made the most sense at the time; build F Sev instead of A Sev... and then ironically being left with too few Southern Fleets anyhow. Russia is hard like that, but the Al played no better than
22

---

Published as a conference paper at ICLR 2021
good human player on that score. To give a practical example England never had enough Fleets to blow up F Bal, so if you swap A Pru for F Bal then this is a real chance at an 18.
Overall, interesting game characterised by the best and worst of human play (England/Turkey) and a strong but flawed game by the AI. 7/10.
GAME 5
http://webbipllnne htt.oy..ee/t/tbrr httpp//wrr....p....mmmm011311111
(bot France)
Right off the bat I am biased as I love this kind of opening as France. The Fleet in English Channel is not good news though. We get as we watch a clinical tactics lesson. About F1906/S1990 there needed to be a pivot to help Italy and stop attacking Germany in order to stop the 18, and it just never came. What had been good display of defence turned into a disaster of Al greed and lack of appreciation for the risk of another player getting an 18. Not only did the Al allow the 18 to happen, but it can fairly reasonably be blamed for it. I think this is something in the reward conditions you might need to look at, as this play makes no sense it isn't even worth digging into further here - it just flat out strategically wrong.
defence from the AI, and frankly the next 5 years are boring
Overall, good tactics but terrible game awareness and strategy. 2/10.
GAME 6
http:// p omacy. net. net/board. php?game ID=318329 (bot as England)
This is more like it. In fact, I think this is the best game of Gunboat I've seen in ages. There's a pressure and inevitability about it from about 1903 onward... Turkey is aggravating everyone near them, and England is moving in second and having people just let take their centres it outplays Germany (and punishes F Kie Hol by bouncing Denmark.. heartily approved), then Russia and Austria just walk out of their centres for it. This makes the attack against France with Italy easy. The game should draw at this point, but Turkey just can't help themselves and stabs Italy when England is already on 15 terrible, inexcusable play. Italy doesn't I even turn around to fight Turkey, but it doesn't 't matter as there just too many disbands and Turkey's armies not fast enough to get to the front.
It's an 18 and it is going on 34. Solo victories are usually caused by someone else making terrible play and this is no exception- - Tuureyy was awful. But they also require precise play by the winner. The Al delivered. Even though this is not the style prefer play England as, every move makes sense. The builds are precise, the critical moments are executed perfectly (For example: S1908 convoy Lon Pic, then ignoring Holland to force English Channel... that's high level play right there) and the sense of not attacking Russia when given the chance few times is [chef's kiss]. Then, above all, the presence to stop building fleets and get the armies rolling - this is the inflection point of great England play and it caught Turkey off guard as they built another fleet, then an army that moved to Armenia, England rushed the middle of the board and Turkey just can't cover all the gaps alone. This opened the door "The Mistake" and Turkey walked right through it.
This is the easiest game to analyse because there's 's just no glaring mistakes by the AI and it takes correct advantage of the situation throughout. This is the only game that made me think the AI could eventually consistently beat human players. As impressive as the German game was it was hyper-win-oriented it is high risk/high reward. This... this is just excellent Gunboat Diplomacy from start to finish.
Overall superb. 10/10.
GAME 7
It= (bot as Austria)
Sometimes you just get killed.
I saw the first four turns and thought "this will be over by 1905" but to my delight the AI fought out bravely and also did its very best try and get back in the game rather than accepting being
23

---

Published as a conference paper at ICLR 2021
tucked in Greece it made run for home centre and then did everything it could to get second build. All to no avail in the end, but the play is hard to fault.
Obviously this is shorter review as there really isn' 't anything to here. But finishing thought will be this challenge that an Al faces most when it starts playing with natural language as well as just gunboat. In gunboat it is just crap shoot who gets attacked early and how vicious it is; in non-gunboat this is a factor very much control of the player. think the Al has proven tactically savvy enough
it once gets start, but will it get starts in non-gunboats?
Overall - just forget this game ever happened, the same as any good human player would. 5/10.
24


Reviews:
[{"review_id": "bYgXlsJt5Si", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a combination of imitation learning and search applied to the multiplayer, simultaneous-move game of no-press Diplomacy. While both techniques have been used before, even in concert, there are some domain-specific challenges: more than two players, simultaneous moves, and a very large branching factor per player. The authors use imitation of human play for value estimates and selection of candidate actions, and External Regret Matching to generate a one-step policy. Experimental validation showed the agent to have strong human-level performance, and was hard to exploit using other machine-learning techniques.\n\nTo the best of my knowledge, I agree with the author's claim that the imitation/search agent from this paper is the first to demonstrate human-level performance in the game of Diplomacy. This is a non-trivial result: Diplomacy is a large problem, and is thought to require fairly complicated interaction between players throughout a game, as well as the ability to handle the uncertainty of other player's moves. There is no claim of guaranteed performance across a general class of problems, but the paper's method seems general enough to apply elsewhere.\n\nThe writing was generally clear, although asking \"could I duplicate these results?\" did raise a few questions about some details.\nThe experimental results against humans seem well constructed, and do a reasonable job to support the claim that the agent demonstrates human-level play. The assorted exploitability-inspired experiments help support the notion that the agent's play is strong, rather than just doing well based on some peculiarity of human play.\n\n---------- specific issues\n\nsection 2.2 \"(which can also be represented as v_i(a_i, a_{-i}).\"\nClosing parenthesis missing?\n\n\"ERM guarantees that R^t_i(a_i) in \\mathcal{O}(\\sqrt{t}). If R^t_i(a_i) grows sublinearly for all players' actions, as in ERM, then the average policy over all iterations converges to a NE in two-player zero-sum games and in general the empirical distribution of players' joint policies converges to a CCE as t approaches infinity.\"\nHow does the sampling interact with this? The regret bound is w.r.t. the probabilistic policy pi^t_i, but sampled a_{-i}. Connecting this bound to describe the joint behaviour (i.e., Nash eq'm) prThis paper proposes a combination of imitation learning and search applied to the multiplayer, simultaneous-move game of no-press Diplomacy. While both techniques have been used before, even in concert, there are some domain-specific challenges: more than two players, simultaneous moves, and a very large branching factor per player. The authors use imitation of human play for value estimates and selection of candidate actions, and External Regret Matching to generate a one-step policy. Experimental validation showed the agent to have strong human-level performance, and was hard to exploit using other machine-learning techniques.\n\nTo the best of my knowledge, I agree with the author's claim that the imitation/search agent from this paper is the first to demonstrate human-level performance in the game of Diplomacy. This is a non-trivial result: Diplomacy is a large problem, and is thought to require fairly complicated interaction between players throughout a game, as well as the ability to handle the uncertainty of other player's moves. There is no claim of guaranteed performance across a general class of problems, but the paper's method seems general enough to apply elsewhere.\n\nThe writing was generally clear, although asking \"could I duplicate these results?\" did raise a few questions about some details.\nThe experimental results against humans seem well constructed, and do a reasonable job to support the claim that the agent demonstrates human-level play. The assorted exploitability-inspired experiments help support the notion that the agent's play is strong, rather than just doing well based on some peculiarity of human play.\n\n---------- specific issues\n\nsection 2.2 \"(which can also be represented as v_i(a_i, a_{-i}).\"\nClosing parenthesis missing?\n\n\"ERM guarantees that R^t_i(a_i) in \\mathcal{O}(\\sqrt{t}). If R^t_i(a_i) grows sublinearly for all players' actions, as in ERM, then the average policy over all iterations converges to a NE in two-player zero-sum games and in general the empirical distribution of players' joint policies converges to a CCE as t approaches infinity.\"\nHow does the sampling interact with this? The regret bound is w.r.t. the probabilistic policy pi^t_i, but sampled a_{-i}. Connecting this bound to describe the joint behaviour (i.e., Nash eq'm) proceeds easily when considering the joint pi^t. However, in this case the joint is only connected by the specific sampled actions. Does the statement about convergence to NE apply to sampled ERM (With high probability? In expectation?) or only to ERM? \n\nTable 1\nWhat are T=0.5 and T=0.1?  I assume they're the temperature parameter, for action selection in DipNet, but this isn't described until later.\n\nFigure 1, \"Sampling a single action leads to poor performance\"\nHow is the graph intended to be interpreted? In the graph, 1 search action looks to be significantly better than the blueprint.\n\n\"M_i is a hyperparameter that is proportional to the number of units controlled by player i.\"\nProportional how? If power i controls n units, the algorithm will sample M_i actions? M_i*n actions? k*n actions for some hyperparameter k? Please clarify this sentence.\nAre the samples select independently across units somehow, or just the top orders for the round (for that possibly very large number of actions)?\n\n\"We compute a policy for each agent by running the sampled algorithm described in Equation 1 and Equation 2\".\nSection 2.2 describes a few modifications, one of which would seem to modify equation 2. Maybe saying instead that it is running the sampled algorithm described in Section 2.2?\nHow many iterations are used?\n\n\"If our agent is an ESS (or Nash equilibrium), then a population of players all playing the agent's policy could not be 'invaded' by a different policy.\"\nWouldn't this only apply to ESS, not Nash eq'm in general? \n\nSection 4.2.1\nWhat does a sum-of-squares score of 0.54 or 0.42 represent? Are those scores good? Huge? Tiny? The drop is statistically significant. Is that drop of ~0.12 large? Small? Are we supposed to care about the drop? Or just how low they both are? Or just how low the SearchBot-clone result is?\nIt seems like this section would be helped by having a short summary statement of the conclusions the authors would like to draw.\n\nSection 4.2.2\nIt was nice to see that the humans beat the human-imitation blueprint, while they struggled quite a bit against SearchBot. It might be worth specifically noting that not only was the blueprint imitation an improvement on DipNet in this setting, it was specifically the search method making the largest improvement.\n\nSection 4.2.3\nCFR->ERM?  The text talks about plotting versus the number of ERM iterations, while the figure talks about CFR.\n\nFigure 3\nWhat exactly is the average being talked about in the first paragraph? The averaging mention in Section 2.2 (which is not used during search in normal play)? The self-play strategy profile which is a combination of one strategy from each of the 7 runs (not really an average)?  Something else?\nIs \"average\" in the first paragraph different than \"average\" in the right figure? The average line on the left doesn't seem to match the average line on the right: on the right, there seems to be a slight bump upwards at the end, which doesn't seem to be present on the left.\n\nOn the right plot, why not include all (or at least multiple) independent plots, to give a more complete picture of the variance?\n\nInclude some mention or mark indicating how many iterations are used during play? As is, I don't know how this graph relates to the search as used in SearchBot.oceeds easily when considering the joint pi^t. However, in this case the joint is only connected by the specific sampled actions. Does the statement about convergence to NE apply to sampled ERM (With high probability? In expectation?) or only to ERM? \n\nTable 1\nWhat are T=0.5 and T=0.1?  I assume they're the temperature parameter, for action selection in DipNet, but this isn't described until later.\n\nFigure 1, \"Sampling a single action leads to poor performance\"\nHow is the graph intended to be interpreted? In the graph, 1 search action looks to be significantly better than the blueprint.\n\n\"M_i is a hyperparameter that is proportional to the number of units controlled by player i.\"\nProportional how? If power i controls n units, the algorithm will sample M_i actions? M_i*n actions? k*n actions for some hyperparameter k? Please clarify this sentence.\nAre the samples select independently across units somehow, or just the top orders for the round (for that possibly very large number of actions)?\n\n\"We compute a policy for each agent by running the sampled algorithm described in Equation 1 and Equation 2\".\nSection 2.2 describes a few modifications, one of which would seem to modify equation 2. Maybe saying instead that it is running the sampled algorithm described in Section 2.2?\nHow many iterations are used?\n\n\"If our agent is an ESS (or Nash equilibrium), then a population of players all playing the agent's policy could not be 'invaded' by a different policy.\"\nWouldn't this only apply to ESS, not Nash eq'm in general? \n\nSection 4.2.1\nWhat does a sum-of-squares score of 0.54 or 0.42 represent? Are those scores good? Huge? Tiny? The drop is statistically significant. Is that drop of ~0.12 large? Small? Are we supposed to care about the drop? Or just how low they both are? Or just how low the SearchBot-clone result is?\nIt seems like this section would be helped by having a short summary statement of the conclusions the authors would like to draw.\n\nSection 4.2.2\nIt was nice to see that the humans beat the human-imitation blueprint, while they struggled quite a bit against SearchBot. It might be worth specifically noting that not only was the blueprint imitation an improvement on DipNet in this setting, it was specifically the search method making the largest improvement.\n\nSection 4.2.3\nCFR->ERM?  The text talks about plotting versus the number of ERM iterations, while the figure talks about CFR.\n\nFigure 3\nWhat exactly is the average being talked about in the first paragraph? The averaging mention in Section 2.2 (which is not used during search in normal play)? The self-play strategy profile which is a combination of one strategy from each of the 7 runs (not really an average)?  Something else?\nIs \"average\" in the first paragraph different than \"average\" in the right figure? The average line on the left doesn't seem to match the average line on the right: on the right, there seems to be a slight bump upwards at the end, which doesn't seem to be present on the left.\n\nOn the right plot, why not include all (or at least multiple) independent plots, to give a more complete picture of the variance?\n\nInclude some mention or mark indicating how many iterations are used during play? As is, I don't know how this graph relates to the search as used in SearchBot.\n\n=-=  Comments after author discussion\n(Minor) concerns have been addressed.  Thank you for the revisions.", "extra_scores": {}, "extra_text": {}}, {"review_id": "C3MzikM6LY_", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors consider \"no-press Diplomacy\", a complex game played by humans which involves (limited) cooperation and competition.\n\nThe method uses a policy and value function learned from human games, together with a test-time search. The imitation-learned policy is used both to restrict the actions considered in the search and also to roll out the leaf nodes of the search (to a fixed depth, after which the value function is used). The search process is a sampled form of external regret matching.\n\nSeveral wrinkles required for good performance are clearly motivated and explained, e.g. handling low-entropy policies and large action spaces.\n\nThe authors evaluate against existing bots, against multiple human players on webdiplomacy.net, and against two human experts. In all cases, the authors algorithm outperforms its opponents.\n\nIt is not feasible to compute exact exploitability in a game of this size, or even to train an approximate best response against the searching agent. The authors therefore train an approximate best-response RL agent against both the imitation-learned policy and a distillation of the searchbot, strongly suggesting that the distilled search is less exploitable than the imitation-learned policy.\n\nThe method described is novel, but also a fairly straightforward extension of prior work to this domain, incorporating a single-ply search on top of an imitation-learned policy. Although there is nothing radically new, the combination of very strong empirical results, and clear & detailed explanation of the methods involved combine to make this a clear accept. I was particularly happy to see the thorough evaluations including bots, a field of humans, and world-class players, and an attempt at investigating exploitability. \n\nComments on the paper:\n* In figure 3, it might be clearer to plot the two graphs on the same scale.\n* In the Qualitative Assessment of SearchBot section, I would have been interested in any comments the human experts might have made.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "8tuFtum3gBa", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\n\nThe paper addresses the problem of No Press Diplomacy. It applies existing search techniques to improve on an imitation policy, which is learned with improvements on existing supervised learning methods for the domain. The resulting policy is tested against previous learned agents and humans, showing impressive results.\n\nI recommend accepting this paper. It tackles an important multiagent environment, producing the first agent to demonstrate human-level play. While the techniques used are not especially novel, their success in a complex mixed-motive 7-player game is interesting. I have no major concerns about the paper, except for the specific claim that the agent 'convincingly surpasses human performance' - I think this is overstated and should be removed before acceptance.\n\n # Strengths\n\nDiplomacy is an important multiagent domain, involving a complex action space and a mixture of cooperation and competition between players, which necessitates new approaches. Research on this domain is timely, building on recent work as well as a long history of AI research. This paper advances the state of the art in this domain.\n\nThe search method in the paper (external regret matching on a subsampled game, evaluated with on-policy rollouts) is clearly explained and situated in the existing literature. While it is not particularly novel, the successful application to this type of domain is.\n\nOverall, the experiments performed in the paper demonstrate convincingly that SearchBot is a large improvement on policies learned from imitation, and that it is human level.\n * The results in ad-hoc play with humans are impressive. They clearly show that SearchBot is the standard of a fairly strong human player. This is a particularly important contribution in the domain of Diplomacy; I agree with the authors that performance against humans is the ultimate test, and in a 7-player game it is not clear a priori that an agent that fares well against other agents will also do well against humans.\n\n* Play with expert humans shows that SearchBot is not overly exploitable; it is impressive that experts get well below the average result in this setting.\n\n* The agent exploitability analysis is good, showing that SearchBot is (almost certainly) less exploitable by RL than the blueprint it is based on.\n\nThe paper is well-written; related work is addressed well, and the methods and findings are for the most part very clear.\n\n# Weaknesses\n\n## Experiments\n\nI think the claim made in the introduction that it 'convincingly surpasses human-level performance' is too strong, and should be removed or clarified. The natural reading of this is that SearchBot is better than the best human players; but the results in the paper do not bear this out. The reported ranking is 23/1128, and many players in this ranking have played very few games and are unlikely to have an accurate rating. The descriptions elsewhere in the paper (such as the title and conclusions) of 'human-level performance' seem to me to be the appropriate strength of claim.\n\nIt is unclear how strong the human players SearchBot faced in the webdiplomacy evaluation were. I think it would be very useful to include some information on this, and on how SearchBot fares against players of different skill levels. This may well affect how meaningful the reported rank is; if SearchBot has overwhelmingly played rather weak players, its rank is probably not comparable with top human players, who presumably face much stronger opposition.\n\nThe paper compares to two other agents; the SL and RL version of DipNet. Previous work has compared to the rules-based agent Albert; this has the advantage that this bot is independent of human imitation data. Adding this comparison would be valuable, and would help substantiate the strong claim that SearchBot ‘greatly exceeds the performance of past no-press Diplomacy bots’.\n\nThe effects of two key search parameters - rollout length and subgame size - are investigated. However, the effect of the number of iterations of ERM on play strength is not addressed in the paper; I would like to see a similar experiment to those in Figure 1 which looks at this.\n\nSome winrates are presented with confidence intervals, but some in Tables 3, 5 and 6 are not. These should be added.\n\n## Reproducibility\n\nThe methods and results are generally well explained, but I think there are a few places where there could be more detail:\n* The experiments which do not involve humans do not have a clear explanation of the hyperparameters used (particularly for search). A section like Appendix F should be added for this.\n* The experiments between bots used the SoS rules. However, I could not find a description of the circumstances under which games were declared draws.\n* The imitation learning architecture is described only as changes to previous work; I think setting out the entire architecture in an appendix would aid reproducibility, as currently the reader needs to read two other papers to reproduce this.", "extra_scores": {}, "extra_text": {}}, {"review_id": "50VoyyYf7eF", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors apply an interesting twist on 1-ply search to the problem of playing no-press Diplomacy. Diplomacy is an especially interesting application, because it is neither zero-sum nor two-player, in contrast to many recent AI success stories.  Before each action, they compute an equilibrium of the next step of the game, assuming that each player will thereafter play according to a \"blueprint\" strategy learned via imitation learning.  The equilibrium is computed using regret matching.  The resulting agent has very strong performance against both the previous state of the art bots, and against expert human players.\n\nThe paper is clearly organized and well written; I thoroughly enjoyed reading it.  The empirical evaluations are careful.  I especially appreciated that the improved blueprint strategy was evaluated on its own (i.e., without search) to clearly separate which benefits came from the improved representation vs. the addition of 1-ply equilibrium search.\n\nThe idea of finding the equilibrium for each \"stage game\" of an extensive form game was new to me, and it appears to be very effective.  My main concern with this paper is that I would have liked to see some sort of justification for why we would expect this to work and where we should expect it to go wrong.  The fact that Diplomacy is non-zero-sum means that we no longer have strong theoretical guarantees about equilibrium's being the \"right thing\" to play. Should we expect this technique to be broadly applicable, or is it exploiting something specific to Diplomacy?\n\nThe equilibrium-search approach is in contrast with simply attempting to best respond to the blueprint strategy (apparently this is the approach of [Anthony 2020]?)  How does your technique compare to this best-response technique?  I see empirical comparisons to [Paquette 2019] but not [Anthony 2020].\n\nI was surprised by just how computationally expensive this technique turns out to be; that is surely a drawback that will need to be addressed.\n\nOverall I think this paper makes a valuable and well executed contribution, and I recommend acceptance.  I have some further minor comments below.\n\n=== Minor comments ===\n\n- p.4: \"We add an additional value head...\": Can you give some details about the motivation behind this architecture change?\n\n- p.6: \"If the bot's performance for each of the 7 powers is weighted equally, this score increases...\": this sentence didn't make sense to me.  Possibly it assumes more familiarity with Diplomacy than I have?\n\n- p.6: \"This can partly be interpreted through an evolutionary lens...\": What does the ESS view add that is not already present in the equilibrium view?  I would either flesh this out a lot more or drop references to ESS entirely.\n\n- p.6: The definition of exploitability on p.6 is wrong because it doesn't subtract off $u_i(\\pi)$ (also inconsistent with definition on p.8, which appears to be correct)\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that this paper is very solid work, that presents great progress in no-press diplomacy. The method and presented experiments are of very good quality and the work merits to be presented at ICLR.
Decision: Accept (Oral)