Modeling Strong and Human-Like Gameplay with KL-Regularized Search

Introduction

Self-play AI algorithms have matched or exceeded expert human performance in many games, such as chess (campbell2002deep; silver2018general), Go (silver2016mastering; silver2017mastering), and poker (moravvcik2017deepstack; brown2017superhuman; brown2019superhuman). However, the resulting policies often differ markedly from how humans play (mcilroy2020aligning). This is a serious problem for human-computer interactions that involve cooperation rather than purely competition. In such settings, modeling the other participants accurately is important for success. For example, it is important for a self-driving car at a four-way stop sign to conform to existing human conventions rather than its own self-play solution to the problem (lerer2019learning). Moreover, even in purely adversarial games, the alien nature of AI policies makes it difficult for humans to understand and learn from superhuman bots.

The classic approach toward modeling human behavior is imitation learning (IL) on human data. However, evidence in multiple games indicates that IL on expert human data produces policies that are much weaker than actual expert human play in domains with complex strategic planning. In this paper, we study the problem of producing policies that are both strong and human-like in games with complex strategic planning like chess, Go, Hanabi, and Diplomacy. In all four, we find that conducting search with KL-regularization towards an IL policy matches or exceeds the prior state of the art for prediction accuracy of expert humans while also better matching expert human performance.

In Section 3, we show that Monte Carlo tree search (MCTS) with a human imitation-learned policy prior and value function surpasses prior state-of-the-art results for human prediction accuracy in chess and Go. As explained by grill2020monte, standard MCTS with a policy prior can be viewed as a form of KL-regularized search, optimizing a value function subject to a KL-divergence term with that prior. Although MCTS has been extensively studied for developing strong agents, it has been explored much less in the context of developing human-like agents.

Section 4 builds on these findings and shows how to generalize them to a class of imperfect-information games (in which ordinary MCTS is unsound and cannot be applied) via a new algorithm for KL-regularized regret minimization. We show that existing regret minimization algorithms achieve low accuracy in predicting expert human actions in no-press Diplomacy. We then introduce the first regret minimization algorithm to incorporate a cost term proportional to the KL divergence between the search policy and a human-imitation learned anchor policy. We call this algorithm policy-regularized hedge, or piKL-hedge. We prove that piKL-hedge converges to an equilibrium in which all players’ policies are optimal given the joint policies of the players and the cost of deviating from the anchor policy. We then present results in no-press Diplomacy showing that piKL-hedge produces policies that predict human actions as accurately as imitation learning while also improving head-to-head performance in a population of prior agents.

Appendix LABEL:appendix:hanabi additionally shows that applying KL-regularization toward a human IL policy in the search algorithm SPARTA (lerer2020improving) produces similar or better human prediction accuracy while greatly improving performance in the benchmark domain of Hanabi (bard2020hanabi).

Our experiments demonstrate the benefits of KL-regularized search in all four of chess, Go, no-press Diplomacy, and Hanabi to producing agents that are simultaneously more human-like and closer in strength to actual human experts than purely imitation-learned models.

Preliminaries

We study the problem of learning policies for multiplayer games. Here we briefly introduce the key ingredients of both classes of games we study; Section 3 and Section 4 give a more formal presentation tailored to individual game types and learning algorithms.

An ($N$-player) game is defined by a state space $S$, an action space $A$, a (deterministic) transition function $T:S\times A^{N}\to S$, and a collection of reward functions $u_{i}$. We model the behavior of each player in a game as a policy $\pi_{i}:S\to\Delta(A)$ (a distribution over actions given states). In every round of a game, each player observes a (possibly incomplete) view $s_{i}^{t}$ of the current state. One or more players select actions $a_{i}^{t}\sim\pi_{i}(\cdot\mid s_{i}^{t})$, then each player receives a reward $u_{i}^{t}(s^{t},\mathbf{a}^{t}=a_{1}^{t},\ldots,a_{n}^{t})$, and the game transitions into a new state $s^{t+1}=T(s^{t},\mathbf{a}^{t})$. Each player $i$ aims to maximizes its expected reward, and the optimal policies for doing so may depend on the policies $\pi_{-i}=\{\pi_{1},\ldots,\pi_{i-1},\pi_{i+1},\ldots,\pi_{N}\}$ of the other players.

The sequential decision-making problem described above is extremely general, and in this paper we focus on two special cases. In perfect-information games, players make moves sequentially (e.g., $u^{1}$ and $s^{2}$ depend only on $a_{1}$, $u^{2}$ and $s^{3}$ depend only on $a^{2}$, etc.). Many important games, including chess and Go, fall into this category. Next, we study a more general class of imperfect-information, simultaneous-action games that make no assumptions about the dependence of different $u_{i}$ and $T$ on $\mathbf{a}$; here we focus on games with only a single round, also called matrix games. Owing to the large differences between these two settings, the tools for computing strong policies are quite different. The remainder of this paper accordingly offers a deeper exploration of each class of games: perfect-information games in Section 3 and imperfect-information games in Section 4.

Perfect-Information Games: Policy Regularization in Monte Carlo Tree Search

In this section, we focus on developing strong human-like agents for perfect-information games. Monte Carlo tree search (MCTS) has been highly successful for developing strong, but not necessarily human-like agents in this setting, and is a key component of general learning algorithms such as AlphaZero and MuZero capable of achieving superhuman performance in chess, Go, and similar games (silver2018general; schrittwieser2020mastering). By contrast, for developing human-like agents, the best prior human move prediction accuracies for chess and Go were all achieved with pure imitation learning on human data (mcilroy2020aligning; Cazenave2017; silver2017mastering).

The state of the art for predicting human moves in chess is the Maia engine created by mcilroy2020aligning via pure imitation learning without any search. However, this approach appears to be of limited effectiveness for modeling sufficiently strong humans. Although the weakest Maia models at low temperatures appear to outperform the players they imitate (due to “averaging away” of the imitated players’ individual idiosyncratic mistakes (MaiaGuestPost)) each successive model on data from stronger players improves by much less than the players improve.See ratings data at https://lichess.org/@/maia1, https://lichess.org/@/maia5, https://lichess.org/@/maia9 The strongest model, trained to predict human 1900-1999 rated players, even with low temperature appears to be clearly below a 1950-average level of performance in all but the minority of bullet-speed games (in which very little time is available for planning and players are forced to rely more heavily on intuition). Similarly, in Go, pure imitation-learning agents have not exceeded mid-expert level on various online servers despite being trained on top-expert and master-level games (Cazenave2017).

In contrast, search-based reinforcement learning (RL) agents such as AlphaZero that do not use a human policy prior play at a superhuman level, but often in non-human ways that humans find difficult to understand even when given access to interactively query and inspect the agent’s analysis (silver2017mastering; philosophies5040037).

However, we show in both chess and Go that if the human-learned model is used in MCTS with appropriate parameters, MCTS outperforms those models’ human prediction accuracy while simultaneously reducing the shortcomings in those models’ strength.

We consider sequential games where each player $i$ alternatively chooses action $a$ from a policy $\pi_{i}$ where, $a\sim\pi_{i}(\cdot\mid s)$. Each action deterministically transitions the game into a new state $s^{\prime}=T(s,a)$ and gives rewards $u_{i}(s,a)$. Notationally, we may elide the player $i$ in some places when it is clear that $i$ is the next player to move in the state being considered.

Each turn, MCTS builds a game tree over multiple iterations rooted at the current state. Each iteration $t$, MCTS explores a single path down the tree by simulating at each successive state $s$ with player $i$ to move the action:

where $Q(s,a)$ is the estimated expected future reward for $i$ from playing action $a$ in state $s$, the visit count $N(s,a)$ is the number of times $a$ has been explored from $s$, $\tau(s,a)$ is the prior policy probability, and $c_{\text{puct}}$ is a tunable parameter trading off exploration versus exploitation.

Upon reaching a state $s_{t}$ not yet seen, MCTS queries the value function $V_{i}(s_{t})$ for each player $i$, and based on $V_{i}(s_{t})$ and any intermediate rewards received, updates all $Q(s,a)$ estimates on the path traversed. The final agent policy is $\pi(s,a)=N(s,a)/\sum_{b}N(s,b)$ where $s$ is the root state, or optionally we may also have $\pi(s,a)\sim N(s,a)^{1/T}$ where $T$ is a temperature parameter. See also Appendix LABEL:appendix:mcts for a fuller description of MCTS.

grill2020monte show that the agent policy $\pi$ computed by this form of MCTS is an approximate solution to the optimization problem:

where $\lambda\sim c_{\text{puct}}\sqrt{N}$ and $N$ is the total number of iterations.

In other words, at every node of the tree recursively, MCTS implicitly optimizes its expected future reward subject to KL regularization of its policy towards the prior policy $\tau$ with strength controlled by $\lambda$. For any fixed computational budget $N$, we can therefore tune $c_{\text{puct}}$ to vary the strength of that prior, with $c_{\text{puct}}=\infty$ approximating the prior policy before search, and $c_{\text{puct}}\rightarrow 0$ approaching a greedy argmax of the $Q$ value estimates.

If our goal is a strong human-like agent rather than solely a strong agent, and the KL-regularizing policy is learned from human data, then that policy serves not just as a prior, but also as an anchor policy that regularizing towards is desirable in and of itself. With good choice of $c_{\text{puct}}$, MCTS can improve that policy while remaining close to human. Our experiments confirm that MCTS improves on the strength and human prediction accuracy of the best existing models in both chess and Go.

2 Experiments in Chess and Go

In chess and Go, we ran two main experiments each. First, in chess using the prior state-of-the-art Maia models from mcilroy2020aligning and in Go using a model trained on professional games from the GoGoD dataset, we demonstrate that MCTS with that model outperforms the raw model in human prediction accuracy. Second, we also sanity-check that MCTS with the same parameters greatly improves the strength of the same models in chess and Go.

3.2.1 Data and Model Architecture In chess, for the human-learned anchor policy we use the pre-trained Maia1100, Maia1500, and Maia1900 models from mcilroy2020aligning, achieving state-of-the-art performance on rating-conditional human move prediction. These models follow a standard AlphaZero-like residual block architecture, including both a policy and a value head, and were trained to imitate players in ratings “buckets” 1100, 1500, and 1900 respectively, based on roughly 10 million games each from the popular Lichess server (each bucket contains games between players from rating N to N+99).

For Go, we trained a deep neural net on the GoGoD professional game datasethttps://gogodonline.co.uk/. We match Cazenave2017 in using games from 1900 through 2014 for training and 2015-2016 as the test set, with roughly 73000 and 6500 games, respectively. Our architecture matches the 20-block residual net structure used by some versions of AlphaZero (silver2017mastering), except adds squeeze-and-excitation layers which have been successful in image processing tasks (hu2018SE) and self-play learning in chess and Go (lc0net; minigoSE). See Appendix LABEL:appendix:gotraining for additional details.

3.2.2 Improved Human Prediction and Strength In Table 3.2 we show the top-1 accuracy of MCTS at predicting players in chess and Go. MCTS on top of each model tested outperforms that model at predicting human moves.

In chess, the benefit provided increases greatly as the rating of players predicted increases, while the optimal choice for $c_{\text{puct}}$ appears to decrease (allowing increasingly small value differences to affect the search). This is consistent with the intuitive hypothesis that stronger players plan more deeply, increasing the value of explicitly modeling planning, and that they are more sensitive to small future value differences. In Go, despite our baseline model being equal or better than all prior imitation-learning models on the GoGoD human pro games dataset, MCTS improves it yet further.

In Figure 2, for chess we see that while KL-regularized search improves each model’s accuracy on players of its target rating, surprisingly, the improvement grows yet larger when each model predicts players of higher rating than it was trained on. This suggests that as human players improve, the incremental average change in their behavior resembles or is correlated with the way that highly-regularized search improves the strength of a baseline policy.

Additionally, in Appendix LABEL:appendix:piklcrossentropy, we show that if we apply post-processing to the MCTS policy based on grill2020monte, MCTS improves cross entropy with human moves in both chess and Go, not just top-1 accuracy. In other words, not only does policy-regularized search improve the prediction of the top move, but it also better models the overall distribution of moves that humans may likely play.

We measure the strength impact of regularized search with 1000 gamesIn Go, we also use the open-source KataGo (Wu2020Go) to determine when the game is over and to score the result. Unlike RL agents, humans which our models imitate universally pass and score the game well before it becomes mechanically scorable, so we use KataGo as a neutral judge. per $c_{\text{puct}}$ setting between the raw model policy and the MCTS policy, sampling each at temperature 1. Figure 1 shows the change in human prediction accuracy of MCTS in both chess and Go plotted jointly versus winrate of MCTS against the raw model. Rather than solely a tradeoff between strength and accuracy, most $c_{\text{puct}}$ values in the range we tested increase both, some achieving more than 90% winrate while still improving human prediction. See Appendix LABEL:appendix:chessgo_experiments for results at lower temperature and evidence that accuracy improves further at longer time controls.

Although we did not test against humans directly to calibrate, this gives clear evidence that a well-tuned human-regularized MCTS agent would be better able to match the 1900-1999-rated chess players that Maia1900 currently falls hundreds of Elo short of imitating, while simultaneously being more accurate to their move-by-move behavior, and similarly for human-imitation agents in Go.

While MCTS is a popular search algorithm for perfect-information deterministic games, it is not able to compute optimal policies in imperfect-information games. Instead, iterative algorithms based on regret minimization are the leading approach to search in imperfect-information games.

Hedge (littlestone1994weighted; freund1997decision) is an iterative regret minimization algorithm that in general converges to a coarse correlated equilibrium (CCE) (hannan1957approximation). In the special case of two-player zero-sum games, it also converges to a Nash equilibrium (NE) (nash1951non).

Regret Matching (RM) (blackwell1956analog; hart2000simple) is another equilibrium-finding algorithm similar to Hedge that has historically been more popular and that we compare our algorithm to in this paper.

The effectiveness of the implicit KL-regularization in MCTS that we study in Section 3 motivates us to develop an equilibrium-finding algorithm called piKL-Hedge that similarly biases the search towards an anchor policy. In LABEL:sec:results_diplomacy, we show that piKL-Hedge achieves better empirical performance against baseline human-imitation models than Hedge and RM in a large imperfect-information game, as well as much higher human prediction accuracy.

We consider a game with $\mathcal{N}$ players where each player $i$ chooses an action $a$ from a set of actions $\mathcal{A}_{i}$. We denote the actions of all players other than $i$ as $\bm{a}_{-i}$. After all players simultaneously choose an action, player $i$ receives a reward of $u_{i}(a,\bm{a}_{-i})$. Players may also choose a probability distribution over actions, where the probability of action $a$ is denoted $\bm{\pi}_{i}(a)$ and the vector of probabilities is denoted $\bm{\pi}_{i}$. We also define the fixed policy that we are interested in biasing player $i$ towards as the anchor policy $\bm{\tau}_{i}\in\Delta(A_{i})$.

Each player $i$ maintains a regret for each action. The regret on iteration $t$ is denoted $R_{i}^{t}(a)$. Initially, all regrets are zero. On each iteration $t$ of Hedge, $\bm{\pi}^{t}_{i}(a)$ is set according to

Next, each player samples an action $a^{*}$ from $\mathcal{A}_{i}$ according to $\pi_{i}^{t}$ and all regrets are updated such that

It is proven that the average policy of Hedge over all iterations converges to a NE in two-player zero-sum games and, more broadly, the players’ joint policy distribution converges to a CCE as $t\rightarrow\infty$.

We wish to model agents that seek to maximize their expected reward, while at the same time playing “close” to the anchor policy. The two goals can be reconciled by defining a composite utility function that adds a penalty based on the “distance” between the player policy and their anchor policy, with coefficient $\lambda_{i}\in[0,\infty)$ scaling the penalty.

For each player $i$, we define $i$’s utility as a function of the the agent policy $\bm{\pi}_{i}\in\Delta(A_{i})$ given policies $\bm{\pi}_{-i}$ of all other agents:

2 No-Regret Learning for Policy-Regularized Utilities

In this section, we present Algorithm 1, a no-regret algorithm based on Hedge for any player $i$ to learn strong policies relative to the regularized utilities defined in (5). As we show in LABEL:prop:regret in LABEL:sec:proofs, it guarantees that each player $i$ accumulates sublinear regret (of order $\log T$) with respect to the regularized utility functions:

no matter the opponents’ actions $\bm{a}_{-i}^{t}$ at each time $t$.