Deep Synoptic Monte-Carlo Planning in Reconnaissance Blind Chess
Authors: Gregory Clark
Venue: NeurIPS 2021 Poster (2021)
Keywords: reconnaissance blind chess
imperfect information
deep learning
imitation learning
planning
uncertainty

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.

Deep Synoptic Monte Carlo Planning in Reconnaissance Blind Chess
Gregory Clark
ML Collective, Google
gregoryclarx@goggle..o
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 samples drawn from the belief state. The algorithm accounts for uncertainty by performing inference on "synopses, 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.
Introduction
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 responsive, and computing a Nash equilibrium is intractable for many games. This paper presents deep synoptic Monte Carlo planning (DSMCP), algorithm for large imperfect information games that seeks best-response strategy rather than a Nash equilibrium strategy.
When opponents use fixed policies, an imperfect information game may be viewed as 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 2006 in three ways: sampling possible histories with 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 generally-applicalle stochas- tie abstraction technique that produces "synopsis" from sampled world states. This paper assesses DSMCP on reconnaissance blind chess (RBC), large imperfect information chess variant.
2 Background
Significant progress been made in recent years 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 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. [018] 2019 Brown et al. 2020). In particular, ReBeL. [Brown al. [0200 combines RL and search by converting
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

% win
MI
50
% occurrence
40
Percent
30
*
20
10
WA
(b)
10 100
1K
10K
100K
1M
Number of possible states
Playing RBC well requires balanc- ing risks and rewards. (a) On the left, Penumbra moved the white queen to g8. After sensing at d2, Black could infer that the white queen occu- pied one of 25 squares. That uncertainty allowed the white queen to survive and capture the black king on the next turn. (b) On the right, Penumbra moved the black queen to h2. In this case, the opponent detected and captured the black queen. The games are available online at https:// rbc. jbcapl edu/ games/ /20177 and https //rbc. //rbc.jhuapl ead/ htrr//amesss/// faams/1147718 124718
Figure 2:
Figure 1: Within 98k historical reconnaissance blind chess (RBC) games between non-random players, the win percentage tends to decrease as the number possible states increases. The mil-
games were replayed while tracking up lion states. Each bucket is labeled with an inclu- sive upper bound. The median of the maximum number of possible states encountered during a game is 4,869.
imperfect information games into continuous state space perfect information games with public belief states as nodes. This approach is powerful, but relies on public knowledge and fails to scale to games with hidden actions and substantial private information, such as RBC.
Information set search [Parker al., 2006 2010) is limited-depth algorithm for imperfect infor- mation 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 unweighted particle filter and planning with a variant of UCT on search tree of histories. In practice, POMCP can suffer from particle depletion, requiring domain-speciff workaround. This work combines unweighted particle filter with a novel information state abstraction technique which increases sample quality and supports deep learning.
Smooth UCT Heinnich and Silver 2015) and information set Monte Carlo tree search (ISMCTS) [Cowling 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 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) NNeleer and Lanctot, 2013 BBownn et al. 2018) are enticing. Online outcome sampling (OOS) Lisy et al., 2015] extends Monte Carlo counterfactual regret minimization (MCCFR) [anctot et al. 2009 by building its search tree incrementally and targeting playouts relevant parts of the tree. OOS draws samples from the beginning of the game. MCCFR and OOS are theoretically guaranteed to converge a Nash equilibrium strategy. Specifically, CFR-based algorithms produce mixed strategies while DSMCP relies on incidental stochasticity.
Neural fictitious self-play (NESP) [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 large games. Dual sequential Monte Carlo (DualSMC) [Wang al. 2019 estimates belief states and plans in continuous domain via sequential Monte Carlo with heuristics.

---

3 Reconnaissance blind chess
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 I 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 3x3 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 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 ( (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 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 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 - 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 (Miih al. 2013), counterfactual regret minimization (CFR) Zinkevich
et al. 2008), online outcome sampling (OOS) (Lisy et al.] 2013), 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. [Savelyvv (2020) also applied UCT to RBC and modeled the root belief state with 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 IkB without compression.
4 Terminology
Consider the two-player extensive-form game with agents p = {selff opponent), actions A, " "ground truth" world states X, and initial state 2o X. Each time an action is taken, each agent p E P is given an observation Op E 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 function X - X defined on subset of world states X X. Define Ag as the set of actions available from x E X.
An information state (infostate) E S for agent p consists of all observations p has received so far Let X C X' be the set of all world states that are possible from p's perspective from s. In general, X, contains less information than since some (sensing) actions may not affect the world state. Define collection of limited-size world state sets L {L C X, s E S. [L| S f). given a constant e.
Let p: X + P indicate the agent to act in each world state. Assume that Ag = Ay and p(x) = plv) for all x. E X, and s E S. Then extend the definitions of actions available A. and agent to act p over sets of world states and over infostates in the natural way. A policy ralss) is distribution over actions given an infostate. A belief state (hh is distribution over action histories. Creating a belicf state from infostate requires assumptions about the opponent's 's action policy r(als). Let
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..
3

---

Algorithm Bandit Action selection with
stochastic multi-armed bandit
Given: с >> 0, m 2
Input: policy visit counts गł, value totals q T2 5- La Tha if e-en
m2n > -Uniform(0. (0, 1]) and root then
return +- action selected by policy else
B₁
X s
return a f- argmax,
is n.
+
C
Inz
B1
X1
Algorithm 2 DrawSample - Sample selection with rejection
Bo
X
Given: k, E E Z synopsis function o, policy f
Input: previous belief distribution B, possible states X, visit counts N, value totals Q
Figure 3: DSMCP approximates infostates with size-limited sets of possible states (circles). It tracks all possible states X₁ for each turn from its own perspective and constructs belief states B, with approximate infostates from the opponent's perspective. At the root of each playout, the initial approximate infostate for the opponent is sampled from B,, and the initial approximate infostate for itself is random subset of Xt.
for 0 to k do
J + random sample from B
< (andit(f(a(JJ), N.. Q.))
I + {a(z) x J}
I t random é states from / if [4] >
return / if' n X $ Ø
return random state from
R2 bp:Ac + R map terminal states to the reward for player Then (S,A, Reelf T, 80)) is POMDP. where the opponent's policy provides environment state transitions and su the initial infostate. In the rest of this paper, the word "state" refers to a world state unless otherwise specified.
5 Deep synoptic Monte Carlo planning
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. uses those approximations to construct a belief state and as UCT nodes [ocssis and Szepesvári 2006]. Figure providess a high-level visualization of the algorithm.
bandit algorithm chooses an action during each node visit, as described in Algorithm [ This bandit algorithm is similar to Smooth UCB [Heinrich and Silver, 2015) in that they both introduce stochasticity by mixing
secondary policy. Smooth UCB empirically approached a Nash equilib- rium utilizing the average policy according to action visits at each node. DSMCP mixes in a neural network's policy (T) instead. The constant e controls the level of exploration, and m controls how the policy π is mixed into the bandit algorithm. For example, taking
0 always selects actions directly with x without considering visit counts, and taking m = oo never mixes in æ. As Silver et al. 2016), provides per-action exploration values which guide the tree search.
Approximate belief states are constructed subsets B C C, where each L E B is set of possible world-states from the opponent's 's perspective. This "second order" representation of belief states allows DSMCP to account for the opponent's uncertainty. Infostates sampled with rejection (Algo- rithm 2 are used as the "particles" in a particle filter which models successive belief states. Sampling is guided by a neural network policy (+) based the identity of the opponent. To counter particle deprivation, & consecutive candidate samples are rejected as incompatible with the possible world states, then singleton sample consisting of randomly- possible state is selected instead.

---

Algorithm 3 ChooseActions UCT playouts
Algorithm 4 PlayGame DSMCP
Given: b, d. Ru,, 2 Z synopsis func. a.
Given: Repaticles Z
policy т, opp. policy f. value func. V
N.. + 0 // Visits V (sample, action) E L x A
Input: belief distribution B, possible states X,
Q. 0/ Values V (sample, action) E C A
visit counts N, value totals Q
Xo < {
+ average of π o a over samples from B
Bo < {Xo}
while time is left do
while the game is not over do
J f random sample from /
current turn
I +- random l states in X including one in J
o + current observation
4g f Bandit (T, Noot, Qrook)
// Track all possible world states
for 0 to d do
X, < x-{a(x) : xx-1,a E Az. (
2t f the one state in InJ
// Filter belief states with the new information for = t - to 0 do
observations when a, is played on 2t
I < {a(x) x E I, a E As. Oseit ~ a(x))
X; { Xi:
3a E Ar
J {a(x)
J a E A,, Oapp" a(r)
such that a(x) E X
J < random l states in incluuing az (xz))
B: + (T B In * Ø I/ Repopulate belief states with new particles
J random states in J including a (3%a)
K; + I and μ + π if / is to act
while opponent to act or |B.| < patticles do
K; J and μ 4 F if J act
smallest i > 0 s.t. B,| < purticles
d += if N Ke.a,
1 DrawSample [ 1; X;, N, Q)
for 0 to i do
N NK,a; +=
B; < B, (T) if self to act then
0t+1 (Bandit(p((((k)))
Qk.)
- (())
a + ChooseAction X, Q) Perform action a
for 0 to do
QK,a; += if p(k,)=p((k (())) else
N Ng,a; += ny
return argmax, Qroot
The tree search, described in Algorithm 3 tracks an approximate infostate for each player while simulating playouts. Playouts are also guided by policy (I and f) and value (v) estimations from neural network. A synopsis function creates fixed-size summary of each node input for the network. The constant b is the batch size for inference, d is the search depth, l is the size of approximate infostates, nh the virtual loss weight, and is threshold for increasing search depth.
Algorithm describes how to play an entire game, tracking all possible world states. Approximate belief states (B:) are constructed for each past turn by tracking Reprttites elements of L (from the opponent's 's point of view) with unweighted particle filter. Each time the agent receives observation, all of the (past) particles that are inconsistent with the observation are filtered out and replenished, starting with the oldest belief states.
5.1 Synopsis
One of the contributions of this paper is the methodology used to approximate and encode infostates. Games that consist fixed number of turns, such as poker, admit a naturally-compact infostate representation based on observations (Heinrich and Silver] 2013 2016]. However, perfect repre- sentations are not always practical. Game abstractions are often used to reduce computation and memory requirements. For example, imperfect recall is effective abstraction when past actions
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 a manageable cardinality (E). Finally, permutation-ins function a 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 [Fank et al. 1998). Other alternatives include evaluating states with recurrent network [Rumelhart et al. 1986 one-at-a-time using permutation invvrriantn architecture [Zaheer et al. 2017 Wagstaff et al.
synopsis
2019
5

---

White
Black
g6: : e2e4
e3 h7h5
g7 d2d4
f2: f7f5
g6: : e4f5
e4: h5h4
A
d7 fie2
g4: b8c6
5
g7 e2h5
g4: h8h5
b7 d1h5
g5 g7g6
A
e7 h5e8
g6: d7d6
g6 : g6e8
Figure 4: Penumbra played as White in this short game. In the position shown on the left, Black just moved a knight from b8 to c6. From White's perspective, the black pieces could be placed in 238 different ways. Figure 5 shows set of synopsis bithoards for this information state.
3
5
10
12
13
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
42
43
45
46
47
48
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
72
73
74
75
76
77
78
79
80
82
83
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
102
103
Figure 5: This set of synopsis bithoards was used as input to the neural network before White's ss
sense on turn 5 of the game Figure 4 The synopsis contains 104 bitboards. Each bitboard encodes 64 binary features of the possible state set that the synopsis summarizes. For example, bitboard #26 contains the possible locations of opposing pawns, and bitboard #27 contains the possible locations of opposing knights. An attentive reader may notice that the black pawn on h4 is missing from bitboard #26, which due to subsampling to = 128 states before computing the bitboards. In this case, the true state was missing from the set of states used to create the synopsis. The features in each synopsis are only approximations of the infostates that they represent. The first 10 bitboards are constants, which provide information that is difficult for convolutions to construct otherwise [Liu et al. 2018)
Given functions 9: X' - {0, 13 for 0,..., ., that map states to binary features, define the 2th component of a synopsis function : -- [0. 1]. as
(X) = (zo) *; (((21) *, *,...... (:
(1)
where X {ar, .1....,.. )e) and *; is either the logical AND (A) or the logical DR (V) operation For example, if 9; encodes whether opposing knight can move to the d7 square of chess board and *; = A, then o; indicates that a knight can definitely move to d7. siguse an example game, and Figure shows an example output of Penumbra's 's synopsis function, which consists of 104 bitboard feature planes each with 64 binary features. The appendix describes each feature plane.
5.2 Network architecture
Penumbra uses residual neural network [He et al. 2016) as shown in Figure 6 The network contains 14 headsets, designed model specific opponents and regularize each other they are trained on different slices of data (Zhang et al., 2020). Each headset contains 5 heads: policy head, a value head, two heads for predicting winning and losing within the next 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 v, 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 (f) of the corresponding headset is used for

---

8x8x imput
8x8x 128 res. block
8 residual blocks omitted
8x8x 128 res. block
Headset
8x8x122
8x8x4
8x8x8
8x8x4 x4
8x8x4
8x8x216
858x65
64 dense
256 dense
256 dense
256 dense
8x8x216
Policy
Pass
Value
Soon Win
SoonLose
PieceCount
Penumbra's ' network contains a shared tower with 10 residual blocks and 14 headsets. Each headset contains 5 heads for a total of 70 output heads. The residual blocks are shown with double border, and they each contain two 3x3 convolutional layers and batch normalization. All of the convolutional layers in the headsets block for each policy head. Each headset was trained on a separate subset of the data, as described in Table T The policy head provides logits for both sense and move actions.
Figure 6:
1 1x1 convolutions with the exception of the one residual
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.
5.3 Training procedure
The network was trained on historica game data as described by Table | 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.
The reported accuracies
10% of the games were used validation data based on game filename hashes. Training examples were extracted from games multiple times since reducing possible state sets to é states is non- deterministic. A single step of vanilla stochastic gradient descent was applied one headset 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.
5.4 Implementation details
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 's turn. This static analysis applied 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 find forced win.
Piece placements are represented with bitboards [Browne 2014). and the tree of approximate infostates is implemented with 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, 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
"The games were downloaded from rbmc. www.jjuuuee....... edu in June, 2019 and rbc. jace.jhupl..co edu in August, 2020. Additionally, 5,000 games were played locally by StockyInfereece.
7

---

Table 1: Summary of headset training data and resulting validation accuracies
Validation
Multiplicity
Winner
Name
Games
# Train
Actions
Actions
Training
Weight
Gradient
% Top-1
Accuracy
Top-5
Accuracy
Accuracy
Stop
#
A11
85.6k
16.8M
L.8M
15
No
33.6
62.0
74.8
Top
49.5k
16.0M
1.6M
~9.
13
No
43.1
73.4
82.4
StrangeFish
13.3k
8.1M
0.8M
20.7
10
No
45.9
74.3
86.6
LaSalle
3.7k
4.3M
0.4M
32
4
No
36.4
68.2
69.7
Dyn. Entropy
7.8k
7.8M
0.8M
32
7
No
50.0
76.7
78.9
Oracle
20.3k
17.6M
1.9M
No
49.3
77.4
81.4
StockyInfe.
10.7k
13.5M
1,4M
16
9
No
45.2
73.6
68.3
Marmot
10.2k
3.9M
0.4M
16
8
No
24.6
55.4
80.8
Genetic
5.6k
2.3M
0.2M
16
8
No
40.4
70.5
77.9
Zugzwang
10.9k
3.1M
0.3M
12.0
5
No
47.0
71.6
80.1
Trout
18.0k
5.1M
0.5M
16
5
No
41.8
63.4
79.8
Human
6.3k
1.5M
0.2M
2
No
24.9
51.9
73.3
Attacker 15.3k
1.7M
0.2M
16
4
No
45.1
61.9
80.1
Random
17.0k
0.6M
76k
1
Yes
4.5
20.7
94.7
action is approximately proportional to the time remaining. The program processes approximately 4, 4,000 nodes per second, and it plays randomly when the number possible states exceeds million.
Experiments
This section presents the results of playing games between Penumbra and several publicly available RBC baselines [Gardner al. 2020 Bernardoni 2020). Each variant Penumbra in Table[played 1000 games against each baseline, and each variant in Table 3nd and Table 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 EtockyInference, at 1500 based on its rating during the competition.
played 250 games against
Table gives ratings of the baselines and five versions Penumbra. PenumbraCache relied solely on the network policy for action selection in playouts (m 0), PemumbraTree built UCT search tree oo), and cenumbraMixtur mixed in the network policy during early node visits (m = 1). The mixed strategy performed the best. PenumbraNetwork selected actions based the network policy without performing any playouts. PenumbraSimple is the same as a PenumbraMixtura with the static analysis described in (cctioo(554ddisaalle. as ablation studies; removing the search algorithm is detrimental while the effect of removing the static analysis not statistically significant. Unexpectedly, Penumbra played the strongest against Stocky StockyInferent Inferenee when that program was unrecognized. So, in this case, modeling the opponent with stronger policy outperformed modeling more accurately.
PenumbraNetwor and VenumbraSimple serve
Two algorithmic modifications that give the opponent an artificial advantage during planning were investigated. Table reports the results of grid search "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 guaranteed to contain the correct ground truth in playouts, reducing e for the opponent gives the opponent higher-qualins information, allowing the opponent to counter risky play more easily in the constructed UCT tree.
The paranoia parameter augments the exploration values in Algorithm to incorporate the minimum value seen during the current playout. With paranoia é, actions selected according to
go Tha
Inn nhe
argmnax (1
(1-
oma + CTa
where contains the minimum value observed for each action. This is akin the notion paranoia studied by Parker et al. 22066] 2010].

---

Table 2: Bot Elo scores
Table 3: Caution and paranoia grid search results
Bot
Recognized
Elo score
Caution
PenumbraMixture
unrecognized
1747
10%
20%
30%
PenumbraSimple
unrecognized
1739 10
PenumbraCache
unrecognized
1727 10
Paranoia
0% 1711111 1714119
1707
1702.119
PenumbraTree
unrecognized
1
10% 1711119 1705119
17261119 1695118
20% 1688.18
17001:19
1688.118
1670.118
StockyInferent
Trout
7
StockyInfed JockkInffeennce
StrangeFi.
1528
30%
1691#18 1683#18 1681=18 1666+18
CcockyInferent
Genetic
8
ProckyInference
StockyInf.
1500+
Table 4: Exploration strategy grid search results
StockyInferens
unrecognized
8
Penumbraketwork
unrecognized
1376
Exploration ratio
Aggressivelrree
unrecognized
1534:1:15
2
FullMonte
unrecognized
1028
UCBI
1698 1 19
1686 18
1696 1 18
Trout Trout
Trout
1005
aVoP 1696 + 18
1680 + 18
1695 + 18
unrecognized
997
Table44 shows the results of grid search over exploration constants and two bandit algorithms. UCBI
Kuleshov and Precup 2014] (with policy priors), which is used the last line of Algorithm T is compared with "a variant of PUCT" (a VoP) [Silver et al.) 2016 Tian et al. 2019 Lee et al. 2019]
another popular bandit algorithm. This experiment used 20% and 20%. Figure show that
Penumbra aab 's value head accounts for the uncertainty of the underlying infostate.
60-
60
90-
value
value
20-
20-
10-
10-
120
(a)
(b)
Figure 7: The mean historical win percentage and the mean network value assigned (a) train and (b) validation synopses tend to decrease as the number of world states given to a increases.
7 Per-bit saliency
Saliency methods may be able 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 al., 2018). Higher quality saliency information may be surfaced by integrating gradients over gradually -yarieedld inputs [Sundararajan et al.] [017]] Kapishnikvv et al.) 2019) and by smoothing gradients locally [Smilkov et 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 feature removed. The correlation coefficient the average change accuracy is -02008 for loss-PBS, and -0.206 for action-PhS. Explanations for the low correlation include noise in the training process and the presence of closely-related features. Ultimately, the contribution of feature during training is distinct from how well the model can do without that feature. Since

---

Per Derbant aileno
3.5
Pondsathh
3.0
Supe
2.5
Pocetter aewent proes
2.0
100000
200000
300000
400000
500000
600000
1000000
200000 300000
4000000 Steps
500000
600000
Steps
A8
Chuck
AMaclar
Guarl
Per tc saliens)
0.3
04-
Posiite aprcria pucci Poudtrr mnccah
100000 200000
300000
400000
S00000
600000
100000 206000
300000
400000
500000
6000000
Steps
Shrps
Figure 8: (a) The loss per-batch saliency (PBS) and (b) the action per-bit saliency (PbS) are taken on test examples during training. These graphs show the saliency of feature plane #8, dark squares, for each headset in one training run. The large gradients with respect to the loss suggest that the Genetic headset has overfit. (c) The loss PBS and (d) the action PbS provide insight about which synopsis features are most useful. The top-five most-salient feature planes and the least-salient feature plane shown.
for the Top headset from training
some features near-duplicates of others, removing may simply increase dependence another. Still, features with high saliency - such as the current stage (sense or move) and the location of the last capture 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.
Discussion
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 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 active of research (Russell and Norvig 2020). and RBC is 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. 201T]. How much 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.
Acknowledgements
Thanks to the Johns Hopkins University Applied Physics Laboratory for inventing such an intriguing game and for hosting RBC competitions. Thanks Ryan Gardner for valuable correspondence. Thanks to Rosanne Liu, Joel Veness, Marc Lanctot, Zhe Zhao, and Zach Nusshaum 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.
10

---

References
Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps, 2018.
Raman Arora, Teodor V. Marinov, and Mehryar Mohri. Corralling stochastic bandit algorithms, 2020.
William Bernardoni. Baseline bots. 2020.
Kyle Blowitski and Timothy Highley, Checkpoint variations for deep q-learning in reconnaissance blind chess. J. Comput. Sci. Coll., 36(3), oct 2021.
Michael Bowling and Manuela Veloso. Rational and convergent learning in stochastic games. IJCAI International Joint Conference on Artificial Intelligence, 08 2001.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(634))4118 424, 2018. ISSN 0036- doi: 10.1 20.116//cieecc.aao117777 U org/ content/ 6374/413
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885-890, 2019. ISSN 0036-8075. doi: 10. wttp://cience.aa240000. URL https://science sciencemag. org/ httg/oontent/365/660 0015//455//88/
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret mini- mization, 2018.
Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. Combining deep reinforcement learning and search for imperfecttinformation games, 2020.
Cameron Browne. Bitboard methods for games. ICGA journal, 37:67-84, 06 2014. doi: 10.3233/ ICG-2014-37202.
Rémi Coulom. Whole-histone rating: A bayesian rating system for players of time-varying strength. In H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, and Mark H. M. Winands, editors, Computers and Games, pages 113-124, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. ISBN 978-3- 540-87608-3.
Peter Cowling, Edward Powley, and Daniel Whitehouse. Information set monte carlo tree search. IEEE Transactions on Computational Intelligence and Ai in Games, 4:120-143, 06 2012. doi: 10. 1LL.O//CIAI..2022222200
Christopher Fifty, Ehsan Amid, Zhe Zhao, Tianhe Yu, Rohan Anil, and Chelsea Finn. Measuring and harnessing transference in multi-task learning. 2020.
I. Frank, D. Basin, and Hitoshi Matsubara. Finding optimal strategies for imperfect information games. In AAAIIAAI, 1998.
Ryan W. Gardner, Corey Lowman, Casey Richardson, Ashley J. Llorens, Jared Markowitz, Nathan Drenkow, Andrew Newman, Gregory Clark, Gino Perrotta, Robert Perrotta, Timothy Highley, Vlad Shcherbina, William Bernardoni, Mark Jordan, and Asen Asenov. The first international competition in machine reconnaissance blind chess. volume 123 of Proceedings of Machine Learning Research, pages 121-130, Vancouver, CA, 08-14 Dec 2020. PMLR. URL htthttp //proceedings.. www.engg.........m...........m.m wwtppppssssseepeepppppppppaaa
w gatp2///aarddee22...m html
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), Jun 2016. doi: 10. 109/cvrr.2066.900 lttp:///// doi. www.ddooooooooooooooooooo..o..o. / 10. 1109/ cvpr wwtpp............ 2016.90
Johannes Heinrich and David Silver. Smooth uet search in computer poker. In Proceedings of the 24th International Conference on Artificial Intelligence, IJCAI'15, page 554-560. AAAI Press, 2015. ISBN 9781577357384.
Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect- information games, 2016.

---

Timothy Highley, Brendan Funk, and Laureen Okin. Dealing with uncertainty: A piecewisegrid agent for recomnaissance blind chess. J. Comput. Sci. Coll., 35(8):156-165, April 2020. ISSN 1937-4771.
Sara Hooker, Dumitru Erhan, Pieter-Jan Kindermans, and Been Kim. A benchmark for interpretability methods in deep neural networks, 2018.
Andrei Kapishnikov, Tolga Bolukbasi, Fernanda Viégas, and Michael Terry. Xrai: Better attributions through regions, 2019.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. volume 2006, pages 282-2955 09 2006. ISBN 978-3-540 3-540-45775-8. doi: 10.1007/11871842 29.
Volodymyr Kuleshov and Doina Precup. Algorithms for
bandit problems, 2014.
Mare Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling, Monte carlo sampling for regret minimization in extensive games. In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 22, pages 1078-1086. Curran Associates, Inc., 2009.
Marc Lanctot, Richard Gibson, Neil Burch, Martin Zinkevich, and Michael Bowling. No-regret learning in extensive-form games with imperfect recall, 2012.
B. Lee. A. Jackson, Madams, Seth Troisi, and Derek Jones. Minigo: case study in reproducing reinforcement learning research. In RML @CLR, 2019.
Viliam Lisy, Mare Lanctot, and Michael Bowling. Online monte carlo counterfactual regret mini- mization for search in imperfect information games. volume 1, 05 2015.
Rosanne Liu, Joel Lehman, Piero Molino, Felipe Petroski Such, Eric Frank, Alex Sergeev, and Jason Yosinski. An intriguing failing of convolutional neural networks and the coordconv solution, 2018.
Jeffrey Long, Nathan R. Sturtevant, Michael Buro, and Timothy Furtak. Understanding the success of perfect information monte carlo sampling in game tree search. In Proceedings of the Twenty- Fourth AAAI Conference on Artificial Intelligence, AAAI' 10, page 134-140. AAAI Press, 2010.
Jared Markowitz, Ryan W. Gardner, and Ashley J. Llorens. On the complexity of reconnaissance blind chess, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning, 2013.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, 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)55088 513, Mar 2017. ISSN 1095-9203. doi: 10. httl///ience.aamm0000000
http: doi org / 1////10..1122 w111//////////ee aam6960 0
T. Neller and Marc Lanctot. An introduction to counterfactual regret minimization. 2013.
Andrew J. Newman, Casey L. Richardson, Sean M. Kain, Paul G. Stankiewicz, Paul R. Guseman, Blake A. Schreurs, and Jeffrey A. Dunne. Reconnaissance blind multi-chess: an experimentation platform for ISR sensor fusion and resource management. In Ivan Kadar, editor, Signal Processing, Sensor/Information Fusion, and Target Recognition XXV, volume 9842, pages 62 81. International Society for Optics and Photonics, SPIE, 2016. doi: 10.1117/12.2228122 URL https: prg/10.1117/12. 22211277
Osborme and A. Rubinstein. A Course in Game Theory. The MIT Press. MIT Press, 1994, ISBN 9780262650403. Utt.https://booke wwrooks..ooogl...o gwogle. www.books//boeccoooooooooooo www:::miidmmmmmgpmmmm
Austin Parker, Dana Nau, and V. S. Subrahmanian. Overconfidence or paranoia? search in imperfect- information games. In Proceedings of the 2 National Conference on Artificial Intelligence Volume 2, AAAI06,, page 1045-1050. AAAI Press, 2006. ISBN 9781577352815.
12

---

Austin Parker, Dana S. Nau, and V. S. Subrahmanian. Paranoia versus overconfidence in imperfect- information games. In Rina Dechter, Hector Geffner, and Joseph Y. Halpern, editors, Heuristics, Probabilities, and Causality: A Tribute to Judea Pearl, chapter 5, pages 63-87. College Publica- tions, 2010.
J. Pineau, G. Gordon, and S. Thrun, Anytime point-based approximations for large pomdps. Journal of Artificial Intelligence Research, 27:335-380, Nov 2006. ISSN 1076-9757. doi: 10.1
URL http://dx. doi. org/ 10. 1eir//air.................rrrrrr 2078
Mare Ponsen, Steven de Jong, and Mare Lanctot. Computing approximate nash equilibria and robust best-responses using sampling. J. Artif. Int. Res., 42(1):575-66) September 2011. ISSN 1076-9757.
Tord Romstad, Marco Costalba, Joona Kiiski, and et al. Stockfish open source chess engine. httts::/stoockfishchhee org. 2020.
D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning Internal Representations Error Propagation, page 318-362. MIT Press, Cambridge, MA, USA, 1986. ISBN 026268053X.
S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Pearson, 2020. ISBN 9780134671932.
Sergey Savelyev. Mastering reconnaissance blind chess with reinforcement learning, May 2020.
URL https://www sergeysav con/projects//tmm
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering atari, go, chess and shogi by planning with a learned model, 2019.
D. Silver and J. Veness. Monte-carlo planning in large pomdps. In NIPS, 2010.
D. Silver, Aja Huang. Chris Maddison, A. Guez, L. Sifre, George van den Driessche, Julian Schrit- twieser, Ioannis Antonoglou, Vedavyas Panneershelvam,, Mare Lanctot, S. Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, T. Lillicrap. M. Leach, K. Kavukcuoglu, T. Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529:484 489, 2016.
D. Silver, Julian Schrittwieser, K. Simonyan, Ioannis Antonoglou, Aja Huang. A. Guez, T. Hubert, L. Baker, Matthew Lai, A. Bolton, Yutian Chen, T. Lillicrap, Hui, L. Sifre, George van den Driessche, T. Graepel, and Demis Hassabis. Mastering the game of go without human knowledge. Nature, 550:354-3555 2017a.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Si- monyan, and Demis Hassabis. Mastering chess and shogi by self-play with general reinforcement learning algorithm, 2017b.
Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. Smoothgrad: removing noise by adding noise, 2017.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks, 2017.
Richard S. Sutton. The bitter lesson.
BitterLesson. html 2019.
Yuandong Tian, Jerry Ma, Qucheng Gong, Shubho Sengupta, Zhuoyuan Chen, James Pinkerton, and C. Lawrence Zitnick. Elf opengo: An analysis and open reimplementation of alphazero, 2019.
Nenad Tomašev, Ulrich Paquet, Demis Hassabis, and Vladimir Kramnik. Assessing game balance with alphazero: Exploring alternative rule sets in chess, 2020.
Edward Wagstaff, Fabian B. Fuchs, Martin Engeleke, Ingmar Posner, and Michael Osborne, On the limitations of representing functions sets, 2019.
13

---

Yunbo Wang, B. Liu, Jiajun Wu, Yuke Zhu, S. S. Du, Li Fei-Fei, and J. Tenenbaum. Dualsme: Tunneling differentiable filtering and planning under continuous pomdps. arXiv: Learning. 2019.
Kevin Waugh, Martin Zinkevich, Michael Johanson, Morgan Kan, David Schnizlein, and Michael Bowling, A practical use of imperfect recall. 01 2009.
J. J. Wu. Accelerating self-play learning in go, 2020.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets, 2017.
Junjie Zhang, Lingqiao Liu, Peng Wang, and Chunhua Shen. To balance or not to balance: A simple-yet-effectte approach for learning with long-tailed distributions, 2020.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimiza- tion in games with incomplete information. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances Neural Information Processing Systems, volume 20, pages 1729-1736. Cur- Associates, Inc., 2008. URL https: (01188886 Paper pdf
A. Zobrist. new hashing method with application for game playing. ICGA Journal, 13:69-73,
1990.
14


Reviews:
[{"review_id": "hCa7vhSwF9A", "reviewer": "Reviewer_94iT", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "## Originality\n\nThe builds on existing tree search algorithms for imperfect-information games, and algorithms that combine tree search and trained policies. The main original contribution seems to be the formulation of the synopses. There are also numerous design choices made to make the problem tractable that, taken collectively, result in an original system. Related work is cited extensively.\n\n## Quality\n\nThe techniques and specific design choices employed are mainly heuristics, but they are well-motivated by the goal of tractability. The key experimental results are the Elo scores from the RBC tournament, which demonstrate that the method achieves a higher playing strength than its competitors. There is a lack of ablation-type results that drill down into the impact of specific choices -- e.g., selection of particular synopsis features, choice of set sizes for approximations, etc. (at least in the main paper). Some results are also presented with little in the way of interpretation -- specifically, Section 7 and Figure 6. What do the results on saliency tell us about the synopsis features, or how could they guide the selection of features?\n\n## Clarity\n\nThe paper is generally well-written but is extremely information-dense. It feels like there was a struggle to fit in all the content, and the presentation is fairly terse.\n\n## Significance\n\nSolution methods for imperfect information games are of broad interest. This work does not make any ground-breaking advances, but demonstrates a number of practical techniques for making larger problems tractable. Since the agent won an organized RBC competition, presumably the approach will have some impact on the design of other RBC agents.\n\n## Notes:\n\nAlg. 3: What is $\\nu$?\n\nAlg. 4: Should ChooseAction take (N, Q) as arguments?\n\n159-160: Is it correct that $|X| = F$ (the size of the state set is the same as the number of features)? Should it be $|X| = \\ell$?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I see little potential for negative societal impact of this work", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "fVOrpvT4V5z", "reviewer": "Reviewer_Yimf", "summary": "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The core idea of abstracting information sets using the stochastic synopses is, to my knowledge, a novel one and appears to be very successful.  The problem is well-motivated and the results significant for this challenging problem.  On the other hand, I found the paper fairly dense, and the individual contributions not granted enough space for their explanations to be clear.  The notation was not clearly introduced, especially as it related to individual parameters.  In my opinion, this is important work, but the current presentation could be significantly improved to make the contributions more clear and understandable.  \n\nComments\n- I found the algorithm references to be slightly confusing, as the algorithms aren't named, (except for Alg. 1, 2, etc) but then are referred to in other algorithms.  I was able to figure out what was going on, but this made the description a bit harder to follow. \n- Many of the parameters and variables that are used to define the algorithms are not described (that I could find), anywhere in the text or algorithm descriptions.  For example, an $m$ value is referred to multiple times in the text (page 7 line 193, page 8 line 204-205) but the only place it appears is in Algorithm 1.  I would have appreciated some discussion in the text of what this $m$ value controls or influences in the operation of the algorithm.  It was unwieldy to have to flip back from page 8 to the definition of Alg. 1 and then try to figure out how the versions of Penumbra that were evaluated differ.  \n- In a similar fashion I could see no discussion or explanation of $b$, $d$, $n_{vl}$, and $\\nu$, which are referred to in Alg. 3.  \n- Towards the end of Alg 3. \"Bandit\" is mispelled \"Bandi\" and the final parameter passed to it is a 0, where it should be false to match other usages. \n- I found the explication of the Synopsis method, a key contribution of the work, hard to follow. In particular, I failed to see the connection between formula 1 and the contents of Figure 4.  Specifically, the example following formula 1 leads me to see each $x_j$ as a different world states possible (in the abstraction set), while the $g_i$ function used refers to moving to a specific square on the board.  Combined with the AND function, this gives a single binary value that tells whether or not it is guaranteed that the knight can move to that square.  In Figure 4, we see bitboards, the same size as the chessboard, which are described as summarizing things like all the places an enemy pawn could appear. The connection between these two was not immediate to me.  Would the bitboard for the example feature (knight movement) have a black bit everywhere that the knight could definitely move, and a white bit where it might not be able to move?  \n- How were the 14 different headsets of the network used in the planning?  This was an interesting detail to me that I would have loved to have more of an explanation of.  The text merely says that the policy heads and the All value head were used for planning, but how this occurs was left undescribed. \n- Why does having a smaller l for the opponent lead to more cautious play?  My first thought is that the fewer states that are considered in each opponent infoset the more chance there is that we miss the truth and thus it would seem less cautious and more risky to have fewer.  I would have loved more discussion about this. \n- What did it mean for an opponent to be \"recognized as\" vs. \"unrecognized\" in the experimental results? I couldn't find a discussion of what this meant or entailed in the paper anywhere. \n- In the discussion of Saliency (Section 7) I was expecting some conclusions about which type of synopsis features were found to be most impactful.  Am I correct in assuming that the features shown in Figure 6 were also found to be salient in other training runs?  \n- As far as the saliency features, how were these determined?  Were these hand-designed, or learned somehow? \n\nIn summary, I really like this work, the problem it addresses, and the methods it uses.  But I was left with many questions and confusions as I tried to parse the contributions and what had actually been done from the paper itself.  \n\nAddendum: I appreciated the author's responses and am more confident that with the changes they describe the work will be clear enough. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Discussion was adequate", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "dHRWiOM0Gkb", "reviewer": "Reviewer_wWRf", "summary": "The paper describes Penumbra, a top reconnaissance blind chess program, with focus on the state abstraction and the Monte Carlo planning algorithm. ", "questions": "", "limitations": "", "rating": 5, "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": "The main algorithmic contribution is probably the deep synoptic Monte Carlo planning algorithm, but there is little evaluation of it, other than the game program being strong (which can be due to other factors as well). It would be useful to have a more in-depth comparison with other planning algorithms used by the top competitors.\n\nThe paper includes a detailed description of the network architecture and other implementation details, but I am not sure that some of these details are too important for the planning algorithm.\n\nReconnaissance blind chess is a complex domain with many interesting properties for the NIPS audience. Therefore, I regard it as a very good benchmark. However, the particular algorithmic ideas need to be properly evaluated and compared directly with possible alternatives, and not just indirectly through the performance of a game program that happens to include it. As it is, the paper seems a solid paper for a game conference, but I am not sure that it presents sufficient interest for the NIPS audience.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Z2TwqJ_JOCG", "reviewer": "Reviewer_qSQf", "summary": "This paper describes a Reconnaissance blind chess (RBC) program Penumbra that won the 2020 RBC rating competition. Penumbra’s method is called “deep synoptic Monte Carlo planning” which is a set of bandit, belief state summarization, imitation learning techniques that together act on an underlying POMDP model. \n", "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": "Originality: This combination of techniques that leads to an effective algorithm for playing RBC, in my opinion, is novel and interesting. The most original part of the methodology seems to be the synoptic function (summary function) that takes as input approximate infostates and outputs a fixed size summary through the use of logical operators that “scalarize” across the set of possible world states (= a belief state).\n\nQuality: \nThe approach to summarizing approximate infostates is clever and makes sense. However, as a reader, it would be nice to see a clearer discussion regarding the related work with respect to the synopsis function.\nCan the authors discuss what happens when there is no training data for an opponent? How well does Penumbra handle playing against a new opponent? Is there a possibility of catastrophic outcomes if Penumbra uses the model of one opponent but plays against another? These would be useful to discuss in a limitations section.\n\n\nClarity: The paper is generally well-written with intuitive illustrations. It was a pleasure to read. I have a few points below --- it would help to make some notation more precise or give explanations when there is possible ambiguity.\nLine 106: Clarify the statement “equivalently, the set of all possible action histories from p’s perspective”. \nLine 104: Why is the action a function defined on a subset of world states?\nThe discussion about n_particles and the unweighted particle filter deserves more clarity -- I was a bit lost in reading this part as few details are given.\nTypo in Algorithm 3: Bandi -> Bandit\nHow are SoonWin, SoonLose, and PieceCount used?\n\nSignificance: Given the performance of Penumbra in the RBC competition, my judgment is that this constitutes a significant contribution to gameplay AI. The method of summarizing infostates seems generalizable to other settings and perhaps could be studied theoretically: how much are we losing by collapsing infostates in this manner? Could the authors give a discussion on this point?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors could discuss further limitations given some of the questions posed above. They do point out that they are not trying to compute a Nash equilibrium.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers had several concerns about this work, but after discussion these were generally agreed to be fixable issues - with one exception. One reviewer felt very strongly that RBC would not be sufficient to demonstrate the generality of the contribution. I suspect that some of the disagreement here may be an issue of different sub communities having different expectations. While RBC may be a familiar and accepted benchmark in one sub community, it may not be familiar in others - even some that aren't that far away.

The potential narrowness of the appeal of this paper indicates that a poster may be the more appropriate route.

I would also encourage the authors to find some way to make their contribution appeal more broadly if is is practical to (convincingly) make the case that it has broader application than to a single benchmark.
Decision: Accept (Poster)