Deep Synoptic Monte Carlo Planning in Reconnaissance Blind Chess

Choosing a Nash equilibrium strategy is rational when the opponent is able to identify and exploit suboptimal behavior (Bowling and Veloso, 2001). However, not all opponents are so responsive, and computing a Nash equilibrium is intractable for many games. This paper presents deep synoptic Monte Carlo planning (DSMCP), an algorithm for large imperfect information games that seeks a best-response strategy rather than a Nash equilibrium strategy.

When opponents use fixed policies, an imperfect information game may be viewed as a partially observable Markov decision process (POMDP) with the opponents as part of the environment. DSMCP treats playing against specific opponents as related offline reinforcement learning (RL) problems and exploits predictability. Importantly, the structure of having opponents with imperfect information is preserved in order to account for their uncertainty.

DSMCP uses sampling to break the “curse of dimensionality” (Pineau et al., 2006) in three ways: sampling possible histories with a particle filter, sampling possible futures with upper confidence bound tree search (UCT) (Kocsis and Szepesvári, 2006), and sampling possible world states within each information state uniformly. It represents information states with a generally-applicable stochastic abstraction technique that produces a “synopsis” from sampled world states. This paper assesses DSMCP on reconnaissance blind chess (RBC), a large imperfect information chess variant.

Significant progress has been made in recent years in both perfect and imperfect information settings. For example, using deep neural networks to guide UCT has enabled monumental achievements in abstract strategy games as well as computer games (Silver et al., 2016, 2017a, 2017b; Schrittwieser et al., 2019; Wu, 2020; Tomašev et al., 2020). This work employs deep learning in a similar fashion.

Recent advancements in imperfect information games are also remarkable. Several programs have reached superhuman performance in Poker (Moravčík et al., 2017; Brown and Sandholm, 2018, 2019; Brown et al., 2020). In particular, ReBeL (Brown et al., 2020) combines RL and search by converting imperfect information games into continuous state space perfect information games with public belief states as nodes. This approach is powerful, but it relies on public knowledge and fails to scale to games with hidden actions and substantial private information, such as RBC.

Information set search (Parker et al., 2006, 2010) is a limited-depth algorithm for imperfect information games that operates on information states according to a minimax rule. This algorithm was designed for and evaluated on Kriegspiel chess, which is comparable to RBC.

Partially observable Monte Carlo planning (POMCP) (Silver and Veness, 2010) achieves optimal policies for POMDPs by tracking approximate belief states with an unweighted particle filter and planning with a variant of UCT on a search tree of histories. In practice, POMCP can suffer from particle depletion, requiring a domain-specific workaround. This work combines an unweighted particle filter with a novel information state abstraction technique which increases sample quality and supports deep learning.

Smooth UCT (Heinrich and Silver, 2015) and information set Monte Carlo tree search (ISMCTS) (Cowling et al., 2012) may be viewed as multi-agent versions of POMCP. These two algorithms for playing extensive-form games build search trees (for each player) of information states. These two algorithms and DSMCP all perform playouts from determinized states that are accurate from the current player’s perspective, effectively granting the opponent extra information. Still, Smooth UCT approached a Nash equilibrium by incorporating a stochastic bandit algorithm into its tree search. DSMCP uses a similar bandit algorithm that mixes in a learned policy during early node visits.

While adapting perfect information algorithms has performed surprisingly well in some imperfect information settings (Long et al., 2010), the theoretical guarantees of variants of counterfactual regret minimization (CFR) (Neller and Lanctot, 2013; Brown et al., 2018) are enticing. Online outcome sampling (OOS) (Lisy et al., 2015) extends Monte Carlo counterfactual regret minimization (MCCFR) (Lanctot et al., 2009) by building its search tree incrementally and targeting playouts to relevant parts of the tree. OOS draws samples from the beginning of the game. MCCFR and OOS are theoretically guaranteed to converge to a Nash equilibrium strategy. Specifically, CFR-based algorithms produce mixed strategies while DSMCP relies on incidental stochasticity.

Neural fictitious self-play (NFSP) (Heinrich and Silver, 2016) is an RL algorithm for training two neural networks for imperfect information games. Experiments with NFSP employed compact observations embeddings of information states. DSMCP offers a generic technique for embedding information states in large games. Dual sequential Monte Carlo (DualSMC) (Wang et al., 2019) estimates belief states and plans in a continuous domain via sequential Monte Carlo with heuristics.

Reconnaissance blind chess (RBC) (Newman et al., 2016; Markowitz et al., 2018; Gardner et al., 2020) is a chess variant that incorporates uncertainty about the placement of the opposing pieces along with a private sensing mechanism. As shown in Figure 2, RBC players are often faced with thousands of possible game states, and reducing uncertainty increases the odds of winning.

Consider the two-player extensive-form game with agents $\mathcal{P}=\{$self, opponent$\}$, actions $\mathcal{A}$, “ground truth” world states $\mathcal{X}{}$, and initial state $x_{0}\in\mathcal{X}{}$. Each time an action is taken, each agent $p\in\mathcal{P}$ is given an observation $\mathbf{o}_{p}\in\mathcal{O}$ that matches ($\sim$) the possible world states from $p$’s perspective. For simplicity, assume the game has deterministic actions such that each $a\in\mathcal{A}$ is a function $a:X{}\rightarrow\mathcal{X}{}$ defined on a subset of world states $X{}\subset\mathcal{X}{}$. Define $\mathcal{A}_{x}{}$ as the set of actions available from $x{}\in\mathcal{X}{}$.

An information state (infostate) $s\in\mathcal{S}$ for agent $p$ consists of all observations $p$ has received so far.¹¹1 An infostate is equivalent to an information set, which is the set of all possible action histories from $p$’s perspective (Osborne and Rubinstein, 1994). Let $\mathcal{X}{}_{s}\subset\mathcal{X}{}$ be the set of all world states that are possible from $p$’s perspective from $s$. In general, $\mathcal{X}_{s}$ contains less information than $s$ since some (sensing) actions may not affect the world state. Define a collection of limited-size world state sets $\mathcal{L}=\{L\subset\mathcal{X}_{s}:s\in\mathcal{S},|L|\leq\ell\}$, given a constant $\ell$.

Let $\rho:\mathcal{X}{}\rightarrow\mathcal{P}$ indicate the agent to act in each world state. Assume that $\mathcal{A}_{x}{}=\mathcal{A}_{y}$ and $\rho(x{})=\rho(y)$ for all $x{},y\in\mathcal{X}{}_{s}$ and $s\in\mathcal{S}$. Then extend the definitions of actions available $\mathcal{A}_{*}$ and agent to act $\rho$ over sets of world states and over infostates in the natural way. A policy $\pi(a|s)$ is a distribution over actions given an infostate. A belief state $B(h)$ is a distribution over action histories. Creating a belief state from an infostate requires assumptions about the opponent’s action policy $\tau(a|s)$. Let $\mathcal{R}_{p}:\mathcal{X}{}\rightarrow\mathbb{R}$ map terminal states to the reward for player $p$. Then $(\mathcal{S},\mathcal{A},\mathcal{R}_{\text{self}},\tau,s_{0})$ is a POMDP, where the opponent’s policy $\tau$ provides environment state transitions and $s_{0}$ is the initial infostate. In the rest of this paper, the word “state” refers to a world state unless otherwise specified.

Effective planning algorithms for imperfect information games must model agents’ choice of actions based on (belief states derived from) infostates, not on world states themselves. Deep synoptic Monte Carlo planning (DSMCP) approximates infostates with size-limited sets of possible world states in $\mathcal{L}$. It uses those approximations to construct a belief state and as UCT nodes (Kocsis and Szepesvári, 2006). Figure 3 provides a high-level visualization of the algorithm.

A bandit algorithm chooses an action during each node visit, as described in Algorithm 1. This bandit algorithm is similar to Smooth UCB (Heinrich and Silver, 2015) in that they both introduce stochasticity by mixing in a secondary policy. Smooth UCB empirically approached a Nash equilibrium utilizing the average policy according to action visits at each node. DSMCP mixes in a neural network’s policy ($\pi$) instead. The constant $c$ controls the level of exploration, and $m$ controls how the policy $\pi$ is mixed into the bandit algorithm. For example, taking $m=0$ always selects actions directly with $\pi$ without considering visit counts, and taking $m=\infty$ never mixes in $\pi$. As in Silver et al. (2016), $\pi$ provides per-action exploration values which guide the tree search.

Approximate belief states are constructed as subsets $\hat{B}\subset\mathcal{L}$, where each $L\in\hat{B}$ is a set of possible world-states from the opponent’s perspective. This “second order” representation of belief states allows DSMCP to account for the opponent’s uncertainty. Infostates sampled with rejection (Algorithm 2) are used as the “particles” in a particle filter which models successive belief states. Sampling is guided by a neural network policy ($\hat{\tau}$) based on the identity of the opponent. To counter particle deprivation, if $k$ consecutive candidate samples are rejected as incompatible with the possible world states, then a singleton sample consisting of a randomly-chosen possible state is selected instead.

The tree search, described in Algorithm 3, tracks an approximate infostate for each player while simulating playouts. Playouts are also guided by policy ($\pi$ and $\hat{\tau}$) and value ($\nu$) estimations from a neural network. A synopsis function $\sigma$ creates a fixed-size summary of each node as input for the network. The constant $b$ is the batch size for inference, $d$ is the search depth, $\ell$ is the size of approximate infostates, $n_{\text{vl}}$ is the virtual loss weight, and $z$ is a threshold for increasing search depth.

Algorithm 4 describes how to play an entire game, tracking all possible world states. Approximate belief states ($\hat{B}_{t}$) are constructed for each past turn by tracking $n_{\text{particles}}$ elements of $\mathcal{L}$ (from the opponent’s point of view) with an unweighted particle filter. Each time the agent receives a new observation, all of the (past) particles that are inconsistent with the observation are filtered out and replenished, starting with the oldest belief states.

This section presents the results of playing games between Penumbra and several publicly available RBC baselines (Gardner et al., 2020; Bernardoni, 2020). Each variant of Penumbra in Table 4 played 1000 games against each baseline, and each variant in Table 4 and Table 4 played 250 games against each baseline. Games with errors were ignored and replayed. The Elo ratings and 95% confidence intervals were computed with BayesElo (Coulom, 2008) and are all compatible. The scale was anchored with StockyInference at 1500 based on its rating during the competition.

Table 4 gives ratings of the baselines and five versions of Penumbra. PenumbraCache relied solely on the network policy for action selection in playouts ($m\,{=}\,0$), PenumbraTree built a UCT search tree ($m\,{=}\,\infty$), and PenumbraMixture mixed in the network policy during early node visits ($m\,{=}\,1$). The mixed strategy performed the best. PenumbraNetwork selected actions based on the network policy without performing any playouts. PenumbraSimple is the same as PenumbraMixture with the static analysis described in Section 5.4 disabled. PenumbraNetwork and PenumbraSimple serve as ablation studies; removing the search algorithm is detrimental while the effect of removing the static analysis is not statistically significant. Unexpectedly, Penumbra played the strongest against StockyInference when that program was unrecognized. So, in this case, modeling the opponent with a stronger policy outperformed modeling it more accurately.

Two algorithmic modifications that give the opponent an artificial advantage during planning were investigated. Table 4 reports the results of a grid search over “cautious” and “paranoid” variants of DSMCP. The caution parameter $\kappa$ specifies the percentage of playouts that use $\ell=4$ for the opponent instead of the higher default limit. Since each approximate infostate is guaranteed to contain the correct ground truth in playouts, reducing $\ell$ for the opponent gives the opponent higher-quality information, allowing the opponent to counter risky play more easily in the constructed UCT tree.

The paranoia parameter augments the exploration values in Algorithm 1 to incorporate the minimum value seen during the current playout. With paranoia $\phi$, actions are selected according to

where $\vec{m}$ contains the minimum value observed for each action. This is akin to the notion of paranoia studied by Parker et al. (2006, 2010).

Table 4 shows the results of a grid search over exploration constants and two bandit algorithms. UCB1 (Kuleshov and Precup, 2014) (with policy priors), which is used on the last line of Algorithm 1, is compared with “a variant of PUCT” (aVoP) (Silver et al., 2016; Tian et al., 2019; Lee et al., 2019), another popular bandit algorithm. This experiment used $\kappa=20\%$ and $\phi=20\%$. Figure 7 show that Penumbra’s value head accounts for the uncertainty of the underlying infostate.

Saliency methods may be able to identify which of the synopsis feature planes are most important and which are least important. Gradients only provide local information, and some saliency methods fail basic sanity checks (Adebayo et al., 2018). Higher quality saliency information may be surfaced by integrating gradients over gradually-varied inputs (Sundararajan et al., 2017; Kapishnikov et al., 2019) and by smoothing gradients locally (Smilkov et al., 2017). Those saliency methods are not directly applicable to discrete inputs such as the synopses used in this work. So, this paper introduces a saliency method that aggregates gradient information across two separate dimensions: training examples and iterations. Per-batch saliency (PBS) averages the absolute value of gradients over random batches of test examples throughout training. Similarly, per-bit saliency (PbS) averages the absolute value of gradients over bits (with specific values) within batches of test examples throughout training. Gradients were taken both with respect to the loss and with respect to the action policy.

Figure 8 shows saliency information for input synopsis features used by Penumbra. In order to validate that these saliency statistics are meaningful, the model was retrained 104 times, once with each feature removed (Hooker et al., 2018). Higher saliency is slightly correlated with decreased performance when a feature is removed. The correlation coefficient to the average change in accuracy is $-0.208$ for loss-PBS, and $-0.206$ for action-PbS. Explanations for the low correlation include noise in the training process and the presence of closely-related features. Ultimately, the contribution of a feature during training is distinct from how well the model can do without that feature. Since some features are near-duplicates of others, removing one may simply increase dependence on another. Still, features with high saliency — such as the current stage (sense or move) and the location of the last capture — are likely to be the most important, and features with low saliency may be considered for removal. The appendix includes saliency statistics for each feature plane.

Thanks to the Johns Hopkins University Applied Physics Laboratory for inventing such an intriguing game and for hosting RBC competitions. Thanks to Ryan Gardner for valuable correspondence. Thanks to Rosanne Liu, Joel Veness, Marc Lanctot, Zhe Zhao, and Zach Nussbaum for providing feedback on early drafts. Thanks to William Bernardoni for open sourcing high-quality baseline bots. Thanks to Solidmind for the song “Penumbra”, which is an excellent soundtrack for programming.