Deep Synoptic Monte Carlo Planning in Reconnaissance Blind Chess
Year: 2022

Abstract:
This paper introduces deep synoptic Monte Carlo planning (DSMCP) for large imperfect information games. The algorithm constructs a belief state with an unweighted particle filter and plans via playouts that start at samples drawn from the belief state. The algorithm accounts for uncertainty by performing inference on “synopses,” a novel stochastic abstraction of information states. DSMCP is the basis of the program Penumbra, which won the official 2020 reconnaissance blind chess competition versus 33 other programs. This paper also evaluates algorithm variants that incorporate caution, paranoia, and a novel bandit algorithm. Furthermore, it audits the synopsis features used in Penumbra with per-bit saliency statistics.

heading: 1 Introduction
text: 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.

heading: 2 Background
text: 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,b, 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 [Moravčí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
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
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.

heading: 3 Reconnaissance blind chess
text: 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 1, RBC players are often faced with thousands of possible game states, and reducing uncertainty increases the odds of winning.
Game rules Pieces move in the same way in RBC as in chess. Players cannot directly observe the movement of the opposing pieces. However, at the beginning of each turn, players may view the ground truth of any 3×3 patch of the board. The information gained from the sensing action remains private to that player. Players are also informed of the location of all captures, but not the identity of capturing pieces. When a requested move is illegal, the move is substituted with the closest legal move and the player is notified of the substitution. For example, in Figure 2 (a), if Black attempted to move the rook from h8 to f8, the rook would capture the queen on g8 and stop there instead. Players are always able to track the placement of their own pieces. Capturing the opposing king wins the game, and players are not notified about check. Passing and moving into check are legal.
Official competition This paper introduces the program Penumbra, the winner of the official 2020 RBC rating competition. In total, 34 programs competed to achieve the highest rating by playing public games. Ratings were computed with BayesElo [Coulom, 2008], and playing at least 100 games was required to be eligible to win. Figure 2 shows ground truth positions from the tournament in which Penumbra voluntarily put its queen in danger. Players were paired randomly, but the opponent’s identity was provided at the start of each game which allowed catering strategies for specific opponents. However, opponents were free to change their strategies at any point, so attempting to exploit others could backfire. Nonetheless, Penumbra sought to model and counter predictable opponents rather than focusing on finding a Nash equilibrium.
Other RBC programs RBC programs have employed a variety of algorithms [Gardner et al., 2020] including Q-learning [Mnih et al., 2013], counterfactual regret minimization (CFR) [Zinkevich et al., 2008], online outcome sampling (OOS) [Lisy et al., 2015], and the Stockfish chess engine [Romstad et al., 2020]. Another strong RBC program [Highley et al., 2020, Blowitski and Highley, 2021] maintains a probability distribution for each piece. Most RBC programs select sense actions and move actions in separate ways while DSMCP unifies all action selection. Savelyev [2020] also applied UCT to RBC and modeled the root belief state with a distribution over 10,000 tracked positions. Input to a neural network consisted of the most-likely 100 positions, and storing a single training example required 3.5MB on average which was large enough to hinder training. This work represents training examples with compact synopses which are less than 1kB without compression.

heading: 4 Terminology
text: Consider the two-player extensive-form game with agents P = {self, opponent}, actions A, “ground truth” world states X , and initial state x0 ∈ X . Each time an action is taken, each agent p ∈ P is given an observation op ∈ O that matches (∼) the possible world states from p’s perspective. For simplicity, assume the game has deterministic actions such that each a ∈ A is a function a : X → X defined on a subset of world states X ⊂ X . Define Ax as the set of actions available from x ∈ X . An information state (infostate) s ∈ S for agent p consists of all observations p has received so far.1 Let X s ⊂ X be the set of all world states that are possible from p’s perspective from s. In general, Xs contains less information than s since some (sensing) actions may not affect the world state. Define a collection of limited-size world state sets L = {L ⊂ Xs : s ∈ S, |L| ≤ `}, given a constant `. Let ρ : X → P indicate the agent to act in each world state. Assume that Ax = Ay and ρ(x) = ρ(y) for all x, y ∈ X s and s ∈ S. Then extend the definitions of actions available A∗ and agent to act ρ over sets of world states and over infostates in the natural way. A policy π(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 τ(a|s). Let
1An infostate is equivalent to an information set, which is the set of all possible action histories from p’s perspective [Osborne and Rubinstein, 1994].
. . .
. . .
. . .
. . .. . . . . .
B̂0
B̂1
B̂t
. . .
. . .
. . .
X0
X1
Xt
Algorithm 1 Bandit – Action selection with a stochastic multi-armed bandit
Algorithm 2 DrawSample – Sample selection with rejection
Rp : X → R map terminal states to the reward for player p. Then (S,A,Rself, τ, s0) is a POMDP, where the opponent’s policy τ provides environment state transitions and s0 is the initial infostate. In the rest of this paper, the word “state” refers to a world state unless otherwise specified.

heading: 5 Deep synoptic Monte Carlo planning
text: 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 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 (π) instead. The constant c controls the level of exploration, and m controls how the policy π is mixed into the bandit algorithm. For example, taking m = 0 always selects actions directly with π without considering visit counts, and taking m =∞ never mixes in π. As in Silver et al. [2016], π provides per-action exploration values which guide the tree search.
Approximate belief states are constructed as subsets B̂ ⊂ L, where each L ∈ 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 (τ̂ ) 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.
Algorithm 3 ChooseAction – UCT playouts Given: b, d, `, nvl, z ∈ Z+, synopsis func. σ,
policy π, opp. policy τ̂ , value func. ν Input: belief distribution B̂, possible states X , visit counts N, value totals Q π̄ ← average of π ◦ σ over b samples from B̂ while time is left do J ← random sample from B̂ I ← random ` states in X including one in J a0 ← Bandit(π̄,Nroot,Qroot) for t = 0 to d do xt ← the one state in I ∩ J o← observations when at is played on xt I ← {a(x) : x ∈ I, a ∈ AI , oself ∼ a(x)} J ← {a(x) : x ∈ J, a ∈ AJ , oopp∼ a(x)} I ← random ` states in I including at(xt) J ← random ` states in J including at(xt) Kt ← I and µ← π if I is to act Kt ← J and µ← τ̂ if J is to act d += 1 if NKt,at > z for i = 0 to t do NKi,ai += nvl
at+1 ← Bandit(µ(σ(Kt)),NKt ,QKt) q ← ν(σ(Kt)) for i = 0 to t do
QKi,ai += q if ρ(Kt)=ρ(Ki) else −q NKi,ai += 1− nvl
return a← argmaxa Qroot
Algorithm 4 PlayGame – DSMCP Given: nparticles ∈ Z+ N∗,∗ ← 0 // Visits ∀ (sample, action) ∈ L ×A Q∗,∗ ← 0 // Values ∀ (sample, action) ∈ L×A X0 ← {x0} B̂0 ← {X0} while the game is not over do t← current turn o← current observation // Track all possible world states Xt←{a(x) : x∈Xt−1, a∈Ax, oself∼a(x)} // Filter belief states with the new information for i = t− 1 to 0 do Xi ← {x ∈ Xi : ∃a ∈ Ax
such that a(x) ∈ Xi+1} B̂i ← {I ∈ B̂i : I ∩Xi 6= ∅}
// Repopulate belief states with new particles while opponent to act or |B̂t| < nparticles do i← smallest i > 0 s.t. |B̂i| < nparticles I ← DrawSample(B̂i−1, Xi,N,Q) B̂i ← B̂i ∪ {I} if self to act then a← ChooseAction(B̂t, Xt,N,Q) Perform action a
The tree search, described in Algorithm 3, tracks an approximate infostate for each player while simulating playouts. Playouts are also guided by policy (π and τ̂ ) and value (ν) estimations from a neural network. A synopsis function σ 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, ` is the size of approximate infostates, nvl 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 (B̂t) are constructed for each past turn by tracking nparticles elements of 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.

heading: 5.1 Synopsis
text: One of the contributions of this paper is the methodology used to approximate and encode infostates. Games that consist of a fixed number of turns, such as poker, admit a naturally-compact infostate representation based on observations [Heinrich and Silver, 2015, 2016]. However, perfect representations are not always practical. Game abstractions are often used to reduce computation and memory requirements. For example, imperfect recall is an effective abstraction when past actions are unnecessary for understanding the present situation [Waugh et al., 2009, Lanctot et al., 2012].
DSMCP employs a stochastic abstraction which represents infostates with sets of world states and then subsamples to a manageable cardinality (`). Finally, a permutation-invariant synopsis function σ produces fixed-size summaries of the approximate infostates which are used for inference. An alternative is to run inference on “determinized” world states individually and then somehow aggregate the results. However, such aggregation can easily lead to strategy fusion [Frank et al., 1998]. Other alternatives include evaluating states with a recurrent network [Rumelhart et al., 1986] one-at-a-time or using a permutation-invariant architecture [Zaheer et al., 2017, Wagstaff et al., 2019].
Given functions gi : X → {0, 1} for i = 0, . . . , F that map states to binary features, define the ith component of a synopsis function σ : L → {0, 1}F as
σi(X) = gi(x0) ∗i gi(x1) ∗i · · · ∗i gi(x`) (1)
where X = {x0, x1, . . . , x`} and ∗i is either the logical AND (∧) or the logical OR (∨) operation. For example, if gi encodes whether an opposing knight can move to the d7 square of a chess board and ∗i = ∧, then σi indicates that a knight can definitely move to d7. Figure 4 shows an example game, and Figure 5 shows an example output of Penumbra’s synopsis function, which consists of 104 bitboard feature planes each with 64 binary features. The appendix describes each feature plane.

heading: 5.2 Network architecture
text: Penumbra uses a residual neural network [He et al., 2016] as shown in Figure 6. The network contains 14 headsets, designed to model specific opponents and regularize each other as they are trained on different slices of data [Zhang et al., 2020]. Each headset contains 5 heads: a policy head, a value head, two heads for predicting winning and losing within the next 5 actions, and a head for guessing the number of pieces of each type in the ground truth world state. The Top policy head and the All value head are used for planning as π and ν, respectively. The other heads (including the SoonWin, SoonLose, and PieceCount heads) provide auxiliary tasks for further regularization [Wu, 2020, Fifty et al., 2020]. While playing against an opponent that is “recognized” (when a headset was trained on data from only that opponent), the policy head (τ̂ ) of the corresponding headset is used for
the opponent’s moves while progressing the particle filter (Algorithm 2) and while constructing the UCT tree (Algorithm 3). When the opponent is unrecognized, the Top policy head is used by default.

heading: 5.3 Training procedure
text: The network was trained on historical2 game data as described by Table 1. The reported accuracies are averages over 5 training runs. The All headset was trained on all games, the Top headset was trained on games from the highest-rated players, the Human headset was trained on all games played by humans, and each of the other 11 headsets were trained to mimic specific opponents.
10% of the games were used as validation data based on game filename hashes. Training examples were extracted from games multiple times since reducing possible state sets to ` states is nondeterministic. A single step of vanilla stochastic gradient descent was applied to one headset at a time, alternating between headsets according to their training weights. See the appendix for hyperparameter settings and accuracy cross tables. Training and evaluation were run on four RTX 2080 Ti GPUs.

heading: 5.4 Implementation details
text: Penumbra plays RBC with DSMCP along with RBC-specific extensions. First, sense actions that are dominated by other sense actions are pruned from consideration. Second, Penumbra can detect some forced wins in the sense phase, the move phase, and during the opponent’s turn. This static analysis is applied at the root and to playouts; playouts are terminated as soon as a player could win, avoiding unnecessary neural network inference. The static analysis was also used to clean training games in which the losing player had sufficient information to find a forced win.
Piece placements are represented with bitboards [Browne, 2014], and the tree of approximate infostates is implemented with a hash table. Zobrist hashing [Zobrist, 1990] maintains hashes of piece placements incrementally. Hash table collisions are resolved by overwriting older entries. The tree was not implemented until after the competition, so fixed-depth playouts were used instead (m = 0). Inference is done in batches of 256 during both training and online planning. The time used per
2The games were downloaded from rbmc.jhuapl.edu in June, 2019 and rbc.jhuapl.edu in August, 2020. Additionally, 5,000 games were played locally by StockyInference.
action is approximately proportional to the time remaining. The program processes approximately 4,000 nodes per second, and it plays randomly when the number of possible states exceeds 9 million.

heading: 6 Experiments
text: 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 2 played 1000 games against each baseline, and each variant in Table 3 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 2 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=∞), 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 3 reports the results of a grid search over “cautious” and “paranoid” variants of DSMCP. The caution parameter κ specifies the percentage of playouts that use ` = 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 ` 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 φ, actions are selected according to
argmax a
( (1− φ) ~qa
~na + φ~ma + cπa
√ lnn
~na
) (2)
where ~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 2: Bot Elo scores
Bot Recognized as Elo score PenumbraMixture unrecognized 1747± 11 PenumbraSimple unrecognized 1739± 10 PenumbraCache unrecognized 1727± 10 PenumbraTree unrecognized 1641± 9 StockyInference Trout 1610± 7 StockyInference StrangeFi. 1528± 8 StockyInference Genetic 1512± 8 StockyInference StockyInf. 1500± 8 StockyInference unrecognized 1474± 8 PenumbraNetwork unrecognized 1376± 9 AggressiveTree unrecognized 1134± 15 FullMonte unrecognized 1028± 20 Trout Trout 1005± 22 Trout unrecognized 997± 22
Table 3: Caution and paranoia grid search results
Caution 0% 10% 20% 30%
Pa ra
no ia 0% 1711±19 1714±19 1707±19 1702±19
10% 1711±19 1705±19 1726±19 1695±18 20% 1688±18 1700±19 1688±18 1670±18 30% 1691±18 1683±18 1681±18 1666±18
Table 4: Exploration strategy grid search results
Exploration ratio c 1 2 4
UCB1 1698± 19 1686± 18 1696± 18 aVoP 1696± 18 1680± 18 1695± 18
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 κ = 20% and φ = 20%. Figure 7 show that Penumbra’s value head accounts for the uncertainty of the underlying infostate.

heading: 7 Per-bit saliency
text: 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.

heading: 8 Discussion
text: Broader impact DSMCP is more broadly applicable than some prior algorithms for imperfect information games, which are intractable in settings with large infostates and small amounts of shared knowledge [Brown et al., 2020]. RBC and the related game Kriegspiel were motivated by uncertainty in warfare [Newman et al., 2016]. While playing board games is not dangerous in itself, algorithms that account for uncertainty may become effective and consequential in the real world. In particular, since it focuses on exploiting weaknesses of other agents, DSMCP could be applied in harmful ways.
Future work Planning in imperfect information games is an active area of research [Russell and Norvig, 2020], and RBC is a promising testing ground for such research. Penumbra would likely benefit from further hyperparameter tuning and potentially alternative corralled bandit algorithms [Arora et al., 2020]. Modeling an opponent poorly could be catastrophic; algorithmic adjustments may lead to more-robust best-response strategies [Ponsen et al., 2011]. How much is lost by collapsing infostates with synopses is unclear and deserves further investigation. Finally, the “bitter lesson” of machine learning [Sutton, 2019] suggests that a learned synopsis function may perform better.

heading: Acknowledgements
text: 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.

Review summaries:
This paper presents Deep Synoptic Monte Carlo Planning, the technique behind the 2020 champion Reconnaissance Blind Chess (RBC) program Penumbra.  This method samples possible world states to approximate information sets, which it then abstracts uses synopses.  These abstracted information sets are then used monte-carlo planning to determine actions to take in the game.  The approach, with some RBC specific tweaks, is evaluated in the RBC domain and shown to be very successful. 

The paper describes an approach to planning in imperfect information games called DSMCP. The algorithm is the basis for a system that won the 2020 reconnaissance blind chess competition. The algorithm views the game as a POMDP by assuming a fixed policy for the opponent. Infostates are represented compactly using a particle filter where each particle represents a set of world states with a maximum size. These are further compressed as "synopses", which are conjunctions or disjunctions of Boolean features over all the states in the set. The synposes are then input to a neural network that has been trained to imitate one of a set of possible policies including several other RBC programs. Policy action choices are mixed with UCB action choices to create a search tree. Saliency of different synopses is found to be somewhat correlated with decreased performance when removing that feature.