All Simulations Are Not Equal: Simulation Reweighing for Imperfect Information Games
Authors: Qucheng Gong
Yuandong Tian
Venue:  (2020)
Keywords: Contract Bridge
Simulation
Imperfect Information Games
Reweigh
Belief Modeling

Abstract: Imperfect information games are challenging benchmarks for artificial intelligent systems. To reason and plan under uncertainty is a key towards general AI. Traditionally, large amounts of simulations are used in imperfect information games, and they sometimes perform sub-optimally due to large state and action spaces. In this work, we propose a simulation reweighing mechanism using neural networks. It performs backwards verification to public previous actions and assign proper belief weights to the simulations from the information set of the current observation, using an incomplete state solver network (ISSN). We use simulation reweighing in the playing phase of the game contract bridge, and show that it outperforms previous state-of-the-art Monte Carlo simulation based methods, and achieves better play per decision. 

Under review as a conference paper at ICLR 2020
ALL SIMULATIONS ARE NoT EQUAL: SIMULATION REWEIGHING FOR IMPERFECT INFORMATION GAMES
Anonymous authors Paper under double-blind review
ABSTRACT
Imperfect information games are challenging benchmarks for artificial intelligent systems. To reason and plan under uncertainty is key towards general AI. Tra- ditionally, large amounts of simulations are used in imperfect information games, and they sometimes perform sub-optimally due to large state and action spaces. In this work, we propose a simulation reweighing mechanism using neural net- works. performs backwards verification to public previous actions and assign proper belief weights to the simulations from the information set of the current observation, using an incomplete state solver network (ISSN). We use simulation reweighing in the playing phase of the game contract bridge, and show that it outperforms previous state-of-the-ar art Monte Carlo simulation based methods, and achieves better play per decision.
INTRODUCTION
Board games like Chess and Go (Campbell et al., 2002, Silver et al. 2018) served as long-standing benchmark for AL, and they witnessed the advancement of (deep) reinforcement learning. Past successes in these benchmarks, however, are mostly about perfect information games. In the real world, agents will never have access all ground truth information and have to make decision under missing information. Thus, theories and strategies learned from imperfect information games can be better transferred to these environments. was not until recently researchers have focuses more on
imperfect information games (Heinrich & Silver 2016 Brown & Sandholm 2018 2019
Foerster
ct al. 2018b).
One key challenge in incomplete information games is to model beliefs. In perfect information games like Go and Chess, the best action only depends on the current state. Simulation, reasoning and planning is relatively easy because it is independent of the opponent and history actions, and all information is public. On the other hand, for imperfect information games like Poker (Brown) Sandholm| 2018 2019) and Contract Bridge, an agent needs to infer which state it is from the information set of the observation, which varies dramatically on different opponents and history actions. The agent also needs model actions of other agents, which might be collaborative or adversarial.
There are multiple ways address this problem. Early approaches use heuristic based system to assign different priors to possible states. Simulation based approach samples possible states and try to convert the problem into perfect information one. Each state is solved independently and accumulated together to determine the best action. An example is contract bridge bot GIB (Ginsberg, 1999). Prior works have tried to model belief explicitly with neural networks, and try to optimize it with reconstruction loss (Rong et al. 2019). Recently researchers have also tried to model belief implicitly in an end-to-end manner to capture all information given the history actions.
However, these approaches all have various shortcomings. Rule-based systems are restricted in their representation power. Simulation based approaches usually require a large number of simulations to get to relatively accurate results, and very computationally expensive. While end-to-end methods can give good results, its learned latent space is hard to interpret.
In this paper, would like model belief in computationally efficient manner, while still keeping the interpretability. For this, we propose to backtrack from the current observation using previous action sequences of the existing player and opponent. Given the current observation, we first sample

---

Under review as a conference paper at ICLR 2020
few underlying complete information states. For each sampled state, rewind the history action to reconstruct all the history states. Then at each time step we measure how likely the agent have took that action, rather than the other actions, if this sampled history state is the ground truth. The posterior probability is calculated for each sample. At last, the final belief consists of weighted samples of the simulations rather than a uniform distribution, and more accurate.
To evaluate the likelihood for all agents in all past time steps is computationally expensive. This because at past time steps the other agents also only observe incomplete information. To get an accurate estimate of action likelihood, another round of simulation needs to be done, for each of these scenarios, since this is what the other agents use in the past time step. To solve this problem, we propose to use an Incomplete State Solver Network (ISSN) to imitate the results of simulations. We use this network to predict the action likelihood a trajectory, and assign belief weights each sample. We show that through simulation reweighing, the result is improved, when the mechanism applied to the playing phase of contract bridge.
Although we test on Contract Bridge, the proposed technique does not rely on any domain specific knowledge in this process, and general for any imperfect information games. We will open source all the code and data used to inspire further research in this direction.
CONTRACT BRIDGE
Contract bridge is a game of 4 players. Two teams of players are competing against each other. It is played with one full deck of cards, and each player is dealt with 13 cards. The game has two phases, bidding and playing.
2.1 BIDDING PHASE
During the bidding phase 4 players take turns to suggest target contract, which promises the num- ber of winning rounds in the playing phase as well as the trump suit. The bids cannot decrease in nominal value. If player is not willing to bid higher contract, the Pass bid is always available. There are also some special bids, namely Double and Redouble, which can be used to adjust the scoring of the same contract. The bidding phase ends when one is willing suggest a high contract than the current one. During the bidding phase, players usually convey extra information to their partner through the bids themselves, in order to reach the optimal contract.
2.2 PLAYING PIAAS
After the bidding phase a target contract is determined. The target contract specifies the trump suit and the number of tricks needed for the declaring side. For the playing phase, the partnership who wins the contract is the declaring side and the other partnership is the defending side. The player who first bids the suit of the target contract in the declaring side is the declarer. There are 13 rounds (called tricks) in the playing phase and the declaring side tries to accomplish the target contract.
During the playing phase, the defending side plays first (called lead). After the lead, the partner of the declarer immediately lays his hand down (called dummy), and it is visible to everyone. The declarer controls both his play and dummy's play. There is total of 13 rounds, and each round every player can only play one card. The players are required to follow suit. If they are out of the led suit, trump suit card can beat it, while discarding non- con-trump suit will be losing the trick. The rank of the cards from largest to smallest is A, K, .... 3, 2. The player with the best card wins the current trick, and plays first next round. Once the playing phase finishes, tricks won by each side are accumulated. If declarer wins enough tricks to reach the target contract, he makes the contract, otherwise the contract is down. Scores are calculated according to the target contract and the tricks taken.
RELATED WORK
Recently there are quite a few well-known works on imperfect information games. Card games are most popular among these. Texas Holdem solvers focus finding the Nash Equilibrium through
2

---

Under review as a conference paper at ICLR 2020
counterfactual regret minimization (Zinkevich et al. 2008 Libratus (Brown & Sandholm 2018
utilizes nested safe subgame solving to reach very low exploitability. It can also enhance the back- ground blueprint strategy in real time using self-improver. DeepStack (Moravčík et al. 2017) uses a value network to approximate value function. They both outperform top human professional play- ers. Bayesian Action Decoder (BAD)(Foerster et al.) 2018h) proposes to model public belief and private belief separately, and sample policy based on an evolving deterministic communication pro- tocol. This protocol is then improved through Bayesian updates. BAD is able reach near optimal results in two-player Hanabi, outperforming previous methods by significant margin.
The contract bridge game itself has also attracted multiple researcher's 's attention. There are multi- ple works trying to solve automatic contract bridge bidding (Yeh & Lin 2016; Rong et al.) (2019). There are also commercial software programs which uses a combination of heuristic and simula- tion methods to make superior moves during the playing phase of contract bridge. Among those Ginnshns,,rg, 1999). Jack and Wbridge5 are the most notable ones. They are championship winning programs in world computer bridge tournament. GIB won in 1998 and 1999, whereas from 2001 to 2018 Jack and Wbridge5 snatched 16 titles out of 18.
Game theoretical methods (Myerson 2013 Dudik & Gordon 2009) are principled ways to solve in- complete information games. However, they are computationally prohibitive with large states (Sand-)
holm 2010). Simulation methods are crucial in game solving, for both perfect information and
imperfect information games. MCMC algorithms are proposed and studied (Roberts & Rosenthal
2004) Strong agents in perfect information games (Campbell et al.] 2002; [Silver al.) 2016
2017
2018) relies heavily on simulation and/or knowledge distilled from simulations, Recently it is
shown that simulations can also be efficiently done in imperfect information games setting (Brown)
& Sandholm 2018 Moravčík et al. (017))
Belief modeling is key factor in imperfect information games. Monte Carlo Sampling from known information. known as determination, is a basic technique to models beliefs given observa- Buro tions (Whitehouse et al.) 2011] Ginsberg, 1999; Buro et al., 2009 Ward & Cowling, 2009 Schäfer
et al. 2008). MCTS under imperfect information has also been studied in Whitehouse (2014).
Since brute-force sampling in large (potentially exponential) information set is inefficient, some prior works on card games models belief via independent assumptions (Foerster et al. 2018b) via
latent neural representations (Rong et al., 2019 Tian et al., 2018). Besides them, LOLA (Foerster) et al. 2018a) agents learn with anticipated learning of opponents to reach stronger performance. There are also attempts to model belief in real time strategy games (Synnaeve et al. 2018 Tian &
Gong
2018
Reweighing, or prioritizing examples in training is a common concept. It is commonly used to speed up training or make training more robust. One example usage in reinforcement learning is prioritized experience replay (Schaul et al., 2015). Researchers have also worked on adaptive rejection sampling methods, such as Gilks & ( and more recently Maddison et al. (2014).
4
SIMULATION REWEIGHING
4.1 PROBLEM SETUP
We prepare a dataset of bridge deals from expert tournament play. It contains 84k deals and 2.4 million states from the playing phase. During some deals, the playing phase finishes prematurely because an agreement is made on the remaining tricks, if the remaining play is obvious. We split the dataset into 90% training set and a 10% testing set. Double Dummy Solver (DDS) (lOS))Fcom computes the maximum tricks each side can get if all the plays are optimal. We run DDS on all 2.4 million positions, to get the corresponding results for each available action. This serves as ground truth of the current position. For each position, we run 50 simulations compute the baselines and serve as training target of the pretrained network. Each call to DDS takes about 5 milliseconds.
http:://ww. http://wwwwwiackbiidee.oooo wttp:///cc/eiin.nneeeeeceeee
http://www.wrridee5..cc www.:wwbriggee..om
https://github.cco br dge/dds
3

---

Under review as a conference paper at ICLR 2020
actions (which play!
Double Dummy
North
Sample [Complete info)
Action suggested
Dummy
West # AJ82
East
KS3
?
Sample [Complete infi)
South
?
Sample n [Complete info)
Obsarvation incomplete information
611
Incomplete State Solver Networks (ISSN)
Counts/roobablily
Figure I: Incomplete State Solver Network (ISSN). Given an observation with incomplete informa- tion, traditional approaches (c.g.. GIB) first sample its possible complete information states, solve them to get good actions and accumulate the good actions to get a accumulated count/probability of each action. In contrast, directly learn Incomplete State Solver Network (ISSN) to predict which actions are likely given the incomplete information observation.
a,
a,
0.85
0.20
Most Likely
0.74
0.83
p(s))
0.19
0.32
S
S
Possible Past
Information
ISSN
?
0.19
0,2
?
Observation from other player's POV
Current Observation
Figure 2: Reweighing sampled states by backtracking. Given the current observation or, we sample possible complete states st and check whether they likely happen given the previous actions. This is done via checking whether the likelihood of each previous actions a-j is high given the backtracked state, using ISSN. Note that ISSN takes incomplete state as the input mimic how the other players reason about the current situations from what they can see. Disclaimer: the probabilities are real results from trained network.
4.2 GIB BASELINE
Suggested by the GIB paper, for given position, Monte Carlo sampling is conducted. A set of deals is constructed by shuffling the unknown positions and each deal should be consistent with previous history (e.g. if player has discarded some other suit during previous spade play, he should not have any more spades left). GIB uses additional human designed heuristics from bidding and playing check consistency. For simplicity, in this work just discarding information to check consistency. For each simulation DDS score is computed for each available move. The move with maximum expected score during these simulations is selected.

---

Under review as a conference paper at ICLR 2020
4.3 METHOD
The drawback of the baseline is obvious. First, it is mostly independent on the history actions except for the consistent shuffling. The information gained the previous actions is mostly lost. Second, DDS run is very slow, since it conducts a full search from the current position. Furthermore, to get relatively accurate results, large amount of simulations are needed. This results in slow playing.
We propose a new procedure to improve the above process. We pretrain two networks, one with imperfect information and one with perfect information, both approximate the simulation results of DDS. We call the imperfect information network Incomplete State Solver Net wetwork (ISSN) and perfect information network State Solver Network (SSN) For each hand position A: simulations of DDS are run. For each simulation, the moves with the optimal number of tricks are marked as the optimal moves. We sum up the optimal moves counter in these k simulations.
This results in counter for cach legal move and treat this the training target. The process is described in Figure 1
Once the pretrained network is ready, tion, we still sample deals. Instead of using DDS calculations for each of these simulations, we use the ISSN get the optimal move counter for each legal move d(si; a). In previous works, optimal moves counter is accumulated across all simulations; In our approach, all simulations are not equal and they have to be reweighed by ISSN. From each simulation of the current positions 8,, check the past T history moves. The history states given the simulation state are reconstructed. noted as st.-j where ranges from to T. For all and j we use the Incomplete State Solver Network to calculate the probabilities of actual moves selected ((a-j(st,-)) The posterior probability of sim- ulation s; then II p(a-slss,--) Finally, the moves suggested by the reweighed simulations is
the networks in the following manner: For each posi-
shown in Equation] |
max
EI
p(a-,lss.- a)
(I)
The aforementioned approach is shown in Figure 2
4.4
TRAINING DETAILS
4.4.1 FEATURES
We extract the following features from a state. We use 4x52 bits to represent the remaining cards in all players' hands. There is a proper mask, indicating if the cards visible to the current player, if we are training with imperfect information. The next 52 bits indicates if the current card is a trump. Then,
3x52 bits represent the cards in play in the current round, since up 3 players may have played a card. Finally we use an additional 16 bits to indicate the discarding information in history moves. If player does not follow suit suit j some point the history, the corresponding bit is marked with 1. These features are concatenated together. We use data augmentation to shuffle the suits, and changes the input features and targets correspondingly.
4.4.2 NETWORK
The network uses an initial fully connected layer transform the input representation, and then fully connected layer and 800 hidden units. A skip connection is added every 2 layers. A last fully connected layer
neurons added to get the resulting policy. Finally, illegal actions of the policy are masked out and the resulting weights re-normalized.
The feature representation and network architecture is shown in Figure
4.4.3 TRAINING PROCEDURE
For each position in the dataset, we run k = 50 simulations. We solve each of these simulations using DDS. To train ISSN, for each original deal and simulations, optimal moves counter is then calculated for each legal action. We normalize the counter to make this a probability distribution, and each action's probability is directly proportional the counter. The loss function is the Kullhack-Leibler
5

---

Under review as a conference paper at ICLR 2020
Fasture sstraction
Cards
Current Trick
Trump
Discard Information
State
52 x
52
52
16
x4
Init
FC
ReLU
FC
ReLU
Final
Mask
Policy
Figure 3: Feature representation and network architecture of ISSN.
Table 1: Pretrained network strength compared with DDS ground truth. Results are recorded the metric of trick loss per state.
Network Cost
ISSN
0.064
SSN 0.024
DDS
divergence between the DDS simulation results and network results. To train SSN, we just use the original deal's DDS results counter as the training target. The simulation results are discarded in this case. We train the model with ADAM optimizer (Kingma & Ba 2014) with learning rate of lc-4.
EXPERIMENT RESULTS
We set the evaluation metric as the average tricks loss from optimal play assuming perfect infor- mation. The ground truth play is the DDS result for the original deal and all simulation deals. We compare the following algorithm with the ground truth to get the costs of the policy.
5.1 PRETRAINED NETWORKS
Pretrained networks are trained to imitate the DDS results. However, due to network representa- tion power and imperfect information, there will be performance gap. We show the strength of pretrained networks in Table
5.2 BASELINES
We implement three baselines. The first baseline similar to the GIB Baseline approach, where we accumulate all the DDS simulation results, and pick the best action. We denote this baseline as dds balseasel We implement another baseline which also uses the belief reweighing technique, but without using the pretrain networks. To accomplish this, given hand position, we first run k simulations. For each simulations, we need to reconstruct history states, and check the probability of history actions. Thus for each reconstructed state need to again run k simulations, consistent with the reconstructed states, to get all the DDS scores, and compute the probability to take the specified move p(a-şi (((a-)(s,-j)) (8. We denote this baseline DDS + DDS. Since the Incomplete State Solver Network an imperfect information network learning from the DDS data to estimate p(a p(a-}lli, (88,)))))))) DDS DDS serves an upper bound that ISSN can reach. We should note that DDS DDS runs k² simulations for each position and is very computationally expensive. The third baseline does not use DDS information but directly predict the action from imperfect information state. We refer to this as nn-basel line
5.3 MAIN RESULTS
We compare our approaches with the baseline methods, and compute the cost of the approaches. We pick T = 3 in pretrained networks.
First, We examine the performance using the Incomplete State Solver Network in junction with DDS, noted ISSN DDS. It outperforms dds-based was-baaeline line using DDS simulations only. The weighted simulations are a better approximate to possible hidden states the agent is in. The perfor- mance of ISSN DDS is also close DDS DDS, which is the upper bound it reach.

---

Under review as a conference paper at ICLR 2020
Table 2:
Comparison between neural belief simulator and baselines. Results recorded in the
metric of trick loss state.
Method dds-baseline
Simulation Method
Reweighing Method
DDS calls
NN calls
Cost
DDS
None
k
0 0.0389
ISSN + DDS
DDS
ISSN
k
kT
0.0380
DDS + DDS
DDS
DDS
0.0378
nn- in-baseline
ISSN
None
0
0.0640
SSN
SSN
None
0
0.0565
ISSN SSN
SSN
ISSN
0
k(T 1)
0.0554
K
8
A
Q
/
(a)
ISSN
0.111
0.158
0.149
0.150
0.161
0.138
0.134
Policy
10
4
a
A
3
DDS
ISSN
0.063
0.094
0.102
0.102
0.095
0.322
0.003
0.106
0.114
Policy
AQ3 0.2%
(c)
100%
Figure 4: Examples and results using the final model. (a) and (b) from test data, where in (a) ISSN fails to find the best move, and in (b) ISSN finds the best move. (c) is from simulation data, where the agent is to make a decision on the unusual play of Q
Second, we examine the performances of approaches without using DDS. These approaches run very fast. The use of State Solver Network with k simulations outperforms the an-baseline We also check the performance using both Incomplete State Solver Network and State Solver Network, noted as ISSN + SSN. It outperforms using SSN only. This demonstrates that the reweighing technique also work well with neural network simulation results.
In both approaches, ISSN and simulation reweighing helps to improve the performances. The result shown in 2
EXAMPLES
We feed few examples shown in Figure 4 (a) and (b) are from test data. In (a) is a no-trump contract. The agent has to decide which suit attack. is close call and the network suggests to play VA, where the optimal play is to play spades. In (b) trumps are diamonds. The agent is able to clearly locate the only best play suggested by DDS QQ. (C) from simulation data to demonstrate that ISSN is trained well. The agent is making a decision where J,, & K, &Q has been played in the current trick. Q an unusual play under opponent's K; At runtime, the agent simulates k times, and we pick simulations among them. In the first simulation the previous player has AQ3. If that is the case, playing Q from AQ3 is a bad play. if you play A you will win the current trick, and since AK are already played, Q is very likely win the next trick well. Playing will lose this trick, although will win sometime the future, the agent basically throws away a trick. ISSN correctly suggests so, assigning only 0.2% probability to this situation. In the second simulation the previous player
final trained networks check their performances. The results

---

Under review as a conference paper at ICLR 2020
Table 3:
Ablation studies in the number of layers and hidden neurons of the fully connected layer.
Results are recorded in the metric of average trick loss.
Network
Layers
Hidden neurons
Cost
ISSN
4
400
0.067
ISSN
800
0.066
ISSN
8
400
0.066
ISSN
8
800
0.064
SSN
4
400
0.027
SSN
4
800
0.026
SSN
8
400
0.025
SSN
8
800
0.024
Table 4: Ablation studies in the effect of data augmentation. Results are recorded in the metric of average trick loss.
Network
Data Augmentation
Cost
ISSN
No
0.075
ISSN
Yes
0.064
SSN
No 0.052
SSN
Yes
0.024
Ablation studies in the effect of the training target. Results recorded in the metric of average trick loss.
Table 5:
Training target
Cost
Simulation optimal moves counter Indicator function of simulated best moves
0,041
0.024
has QT. Since J is played, QT are equal cards, and we expect a similar probability to both
actions. ISSN suggests playing Q from QT 51 %. In the last simulation the previous player has only single spade remaining, he has to play that card. After these reasoning, the simulations are reweighed, so the agent focuses more on more likely simulations.
7 ABLATION STUDIES
We conduct the following ablation studies during the training of ISSN and SSN. First, we examine the effects of changing the number of layers and hidden neurons of the fully connected layers. The result shown Table 3 We can see that with more layers and more hidden units the performance increases, but the gain is minimal.
We find that data augmentation plays a critical role the pretraining of the networks. The result shown in Table Without data augmentation, the performance drops significantly.
For the perfect information network to imitate DDS results, we can either choose the DDS simulation optimal move counter as the training target, train indicator function of the simulated best moves only. The latter results a sharper distribution, and performs better given setting. The result comparison is shown in Table 5
8 CONCLUSION AND FUTURE WORK
In this work, we present Incomplete State Solver Network that can suggest actions with imperfect information. We use the network outputs to calculate the probabilities simulations and reweigh them correspondingly. The weighted simulations perform better, and demonstrate it in contract bridge playing phase. ISSN improves the performances both ground truth simulations using DDS and network simulations with SSN. This approach is not specific to the contract bridge game, but general to all imperfect information games. We are also interested long range belief modeling with recurrent networks for imperfect information games, and we leave this future work.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science. 45846474)4418-244, 2018. ISSN 0036-8075. doi: 10. 10.1126/sceence aao1733. URL https: http://sccennccee .ar.eesscccee scwencemag wtt.e/ewwaarr...oo.eeeeeeeeeeeee http://oonenntt////33
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456); 885-890, 2019. ISSN 0036-8075. doi: 10.1 http://ciinn.aa2440000. URL htttps://ccienee
Michael Buro, Jeffrey Richard Long. Timothy Furtak, and Nathan Sturtevant. Improving state eval- uation, inference, and search in trick-based card games. In Twenty-First International Joint Con- ference on Artificial Intelligence, 2009.
Murray Campbell, A Joseph Hoane Jr, and (1-2):57-83, 2002.
Hsu. Deep blue. Artificial intelligence, 134
Miroslav Dudik and Geoffrey Gordon. A sampling-based approach computing equilibria in succinct extensive-form games. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pp. 151-160. AUAI Press, 2009.
Jakob Foerster, Richard Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-leaming awareness. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. pp. 122-130. International Founda- tion for Autonomous Agents and Multiagent Systems, 2018a.
Jakob N. Foerster, Francis Song, Edward Hughes, Neil Burch, lain Dunning, Shimon Whiteson, Matthew Botvinick, and Michael Bowling. Bayesian action decoder for deep multi-agent rein- forcement learning. CoRR, abs//811.011e0111 11.01445,, 2018b. URL htlltttt////ax...oo///bbbas/
01458
W. R. Gilks and Pascal Wild. Adaptive rejection sampling for gibbs sampling. 1992.
Matthew L Ginsberg. Gib: Steps toward an expert-level bridge-playing program. In IJCAI, pp. 584-593, Citeseer, 1999.
Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect- information games. arXiv preprint arXiv:/603.0/ 121, 2016.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014.
Chris Maddison, Daniel Tarlow, and Tom Minka. A sampling. In Advances in Neural Information Processing Systems, pp. 3086-3094, 2014.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisy, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up up no-limit poker. Science, 356(6337):508 2017. ISSN 0036-8075, doi: 10. http://cinnc..aam696.. URL UBLLittte://cceeeeeeeeeeeee http://cceeneeeeceeeem...o...o// 356/ 6337/508)
Roger B Myerson. Game theory. Harvard university press, 2013.
Gareth O. Roberts and Jeffrey S. Rosenthal. General state space markov chains and meme algorithms. Probability Surveys, 1(0):2071, 2004. ISSN 1549-5787, doi: 10.1214/ 154957804400000024 UtLhttp:://et doi http://.....22111133340000010000
12
Jiang Rong, Tao Qin, and Bo An. Competitive bridge bidding with deep neural networks. CoRR, abs/1903.00900, 2019, URL http:://axxii..... htt.rrggga///1.... 00900
Tuomas Sandholm. The state of solving large incomplete-infomattio games, and application to poker. Al Magazine, 314):133- 2010.
Jan Schäfer. Michael Buro, and Knut Hartmann. The uet algorithm applied to games with imperfect information. Diploma, Outo- Von-Guericks Univ. Magdeburg, Magdeburg, Germany, 2008

---

Under review as a conference paper at ICLR 2020
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay, 2015.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354, 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou. Matthew Lai, Arthur Guez, Mare Lanetot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Si- monyan, and Demis Hassabis. general reinforcement learning algorithm that masters chess, shogi, and go through self-play, Science, 362(6419):1100 1144, 2018. ISSN 0036-8075, doi: 10.1 10.1126/science.aarbbi aar64444.
URL htte::/scceence.scienemeeee
6419/1140
Gabriel Synnaeve, Zeming Lin, Jonas Gehring, Dan Gant, Vegard Mella, Vasil Khalidov, Nicolas Carion, and Nicolas Usunier. Forward modeling for partial observation strategy games-a starcraft defogger. In Advances in Neural Information Processing Systems, pp. 10738-10748, 2018.
Yuandong Tian and Qucheng Gong. Latent forward model for real-time strategy game plan- ning with incomplete information, 2018. URL
H1LAMMbRM
Zheng Tian, Shihao Zou, Tim Warr, Lisheng Wu, and Jun Wang. Learning multi-agent implicit communication through actions: A case study in contract bridge, collaborative imperfect- information game. CoRR, abs/1810.04444, 2018. URL http::/aaxx...or///bbaa..
04444
Colin D Ward and Peter I Cowling. Monte carlo search applied to card selection magic: The gathering. In 2009 IEEE Symposium on Computational Intelligence and Games, pp. 9-16. IEEE, 2009.
Daniel Whitehouse. 2014.
Monte carlo tree search for games with hidden information and uncertainty.
Daniel Whitehouse, Edward J Powley, and Peter Cowling. Determinization and information set monte carlo tree search for the card game dou di zhu. In 2011 IEEE Conference on Computational Intelligence and Games (CIG' I1), pp. 87-94. IEFE, 2011.
Chih-Kura Yeh and Hsuan-Tien Lin. Automatic bridge bidding using deep reinforcement learning.
CoRR, abs/1607.032000 2016. http://////arx org/ abs 1 1607 03290
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In Advances in neural information processing systems, pp. 1729-1736 2008
10


Reviews:
[{"review_id": "ByxET2cDsr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces two networks that are trained to predict DDS. While one is trained with perfect information, the other one (ISSN) with imperfect information.\nThe ISSN is then used to compute posterior probability distribution (based on a history leading to the current state). The ideas is that such posterior distribution should perform better compared to uniform distribution when used in determinization process.\n\nI like the idea / motivation of the paper, but the authors could do a better job of explaining the motivation to people less familiar with techniques based on the determinization framework.\nI also like the baselines that they chose to compare against - but the resulting comparison is far from perfect (see Issues section).\n\nMinor issues:\n -  Please do a careful language check - the grammar is wrong in many places (most notably plural/singular nouns).\nWhile this does not hurt the semantics, it makes it sometimes cumbersome to read.\n\n  - Since this work is mostly about using non-uniform distribution during the determinization process, I think it's worthwhile to also mention [Whitehouse, Daniel. Monte carlo tree search for games with hidden information and uncertainty. Diss. University of York, 2014.] as reference point.\n\nIssues:\n - My biggest issue is the experimental and evaluation section. The reported improvements seem small, but most importantly - it is impossible to asses the relevance of the results. \n  There are no confidence intervals or variance reported. Given the seemingly small improvements, this could easily be noise?\n\n - While I am not certain, I assume that your numbers in Table 2 come from the 'test' split of the data - one would guess you used that split to stop the training (select the best model)?\n  If that is the case, I don't think you can use the same split during the evaluation (even though you evaluate differently) - the reported numbers will be biased.\n\nImprovement Suggestions\n  - Please see my issues with the evaluation.\n  - You say you will release the data and code - that is great, do it!\n  - Your figures are way too large for what they do. I think you should make them much more compact and use the resulting space to improve and expand the experimental section. Please add lot more details about the evaluation.\n\nSummary:\nI think the paper is looking into an interesting problem and is going in the right direction, but the experimental section is at this point no good enough to suggest an acceptance.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJx2XMoiFS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\nThis paper deals imperfect information games, and builds a Bayesian method to model the unknown part of the current state, making use of the past moves (which constrain the game, here Contract Bridge).\nThis new Bayesian method is compared to Monte Carlo style techniques, which are much more computationally expensive (they draw random samples of the unknown part of the information and then solve the perfect-information version of the game, for each simulated possible full-state).\nThe work also introduces a Neural Network (NN) to estimate the best moves in the perfect-information version of the game (instead of making the full tree search of the optimal moves to play).\nThe final model proposed (ISSN+SSN) uses a NN combined with Bayesian computation, using the NN at each time step of the past to update the belief about the current missing information.\n\nOverall the paper is written clearly: as a non-expert in RL, I was able to follow rather easily what is done.\n\n\nHowever, the results are not convincingly good.  Maybe it is just the interpretation/contextualization that is insufficient.  I have 3 important remarks:\n\n1. It is stated in the abstract \"that it [the new method] outperforms previous state-of-the-art Monte Carlo simulation based methods, and achieves better play per decision.\"  However, the costs in the 'reweighing DDS' section (table 2) are lower (better) than those of the 'reweighing SSN' section.  The results show improvement upon using some reweighing, as ISSN+sthg is better than without ISSN (although by a very small relative decrease in cost).\n1.a. I understand that the NN-based methods (last three lines of table 2) are incomparably faster than the DDS-based approaches (baseline). And the total rate of tricks loss per initial state remains low (6% seems small as an absolute value).  But, they are almost double of the DDS-based loss rates !  It is not clear how this can be considered 'outperforming' or 'better play per decision'.  If you can explain in which sense those are good results for the SSN vs DDS, please do so. If they are not, please do acknowledge it, and eventually contextualize (maybe a 2-fold increase of loss rate is okay given the large speedup obtained?).\n1.b. in the same way, it is not clear how ISSN outperforms its no-memory counterparts, given the loss decreases are essentially negligible. Maybe one needs to increase the value of T to make ISSN's success more obvious?\n2. In addition, why not compare this Bayesian method with other Bayesian methods (quoted at the very end of section 3)?  Here the paper focuses on comparison with 'deterministic'  methods, i.e. methods which sample complete states (simulations) to then solve the complete-information version of the game (via exhaustive tree search).  Those are what I would call brute-force methods.\nHowever, although simulations may be done (expensively) for contract bridge, in some other cases this kind of sampling may become prohibitively expensive, so that only Bayesian methods are left.  If this kind of argument is the justification for your work, please make it more explicitly.  Otherwise please correct me and explain the context (the role of Bayesian methods, what has been done and what hasn't been) more clearly.\nIf you are to situate the work within the Bayesian-based approaches, the question remains: is ISSN+SSN better than other Bayesian-inspired, \"information-completing\" methods ?  \nTo summarize, the paper convincingly shows that Bayesian-NN methods can compete with expensive brute force methods, but it would be very nice to see how the method introduced compares with other recent Bayesian approaches. (Or if no such comparison can be done, explain why).\n\n3. In addition, here it seems your baseline is based on GIB, which was winning tournaments ~20 years ago: why not compare with Wbridge5 or JackBridge ?  I think you need to at least explain your choice.\n\nBecause of these weak points in terms of experimental results, I lean to reject the paper.  However, depending on the authors answers and clarifications on my 3 important remarks above, I am ready to change my rating.\n\n\n\nAlso, I have a couple of more or less minor remarks to improve the paper:\nThe definition of the cost is not explicitly given: \"We set up the evaluation metric by tricks loss per deal. The ground truth play is DDS result for the original deal and all simulation deals. We compare all the following algorithmS with the ground truth to get costs of the policy.\"\nYou should rephrase this to make the definition of 'cost' very explicit. Is it simply the average rate of lost tricks (per given set of 13 cards in the agent hands) ?\nThis is quite crucial and make the reading of results a bit complicated (especially since results fo not match the conclusion announced in the abstract).\n\n\"DDS) 3 computes the maximum tricks  each side can get if all the plays are optimal\"\nIn this place and a couple others, you should explicitly recall whether you mean 'assuming perfect information', or not.  Sometimes it can get confusing, and a bit of repetition won't hurt.  I think I understood correctly that DDS solves (perfectly) the perfect information game, but at times I thought other methods also made use of the full information (?)\nFigure 4c is nicely explained and this part really illustrates well the idea of the method, I like it. Although, the notation AQ3 was not obvious for me at first, and I think it is worth improving this figure, making use of the right-hand-side space, to make it an autonomously explanatory figure.\n'position': the term is not defined. I would guess it means the current state of the game (the agent's hand and the cards played in the past or during the current trick). This should be said explicitly.\nAlso \"hands\" seem to refer to the 4 hands (1 for each player) (is that correct?)\n\nThere are wrong singular/plurals ('s'/no 's') in several places. This is simple to correct and should be corrected.\n\nin section 7, ablation studies. This is a very nice study, but you should precise how much you augment the data here (or recall by how much, if you say it earlier).\n\nThis passage is unclear and should be rephrased for clarity:\n\"We run DDS on all 2.4 million positions, to get the\ncorresponding results for each available action. This serves as ground truth of the current position.\nFor each position, we run 50 simulations to compute the baselines and serve as training target of the\npretrained network. Each call to DDS takes about 5 milliseconds.\"\n\nThis passage is unclear and should be rephrased for clarity:\n\"For simplicity, in this work we just use discarding information.\"\n\nThis passage is slightly unclear and should be rephrased for clarity:\n\"For each simulation, the moves with the optimal number of\ntricks are marked with optimal moves. We sum up the optimal moves counter in these k simulations.\nThis results in a counter for each legal move and we treat this as the training target. The process is\ndescribed in Figure 1.\"\"\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "BJeru3k2Yr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents an approach to playing imperfect information games, an “Incomplete State Solver Network” (ISSN) within the domain of contact bridge. The paper’s primary technical contributions are the network, and a large dataset of contact bridge games, which the authors make publicly available. \n\nI believe that the work that the authors did in regards to this paper is valuable. However, I had a very hard time following along with the paper. The major issue is the language, which I mean both in terms of particular phrases or terms going unexplained, and the grammar and phrasing of the sentences. \n\nThe most clear early example of terms and phrases going unexplained is the second section describing contract bridge. Many terms are used without any explanation. For example, what a target contract is or what a trump means in the case of contract bridge. This made the remainder of the paper, including the results difficult to understand. \n\nAs an indication of the grammar and phrasing issues in the paper I have below included issues from just the first page of the paper: \n- “In real world”-> “In the real world”\n- “have to made decision” -> “have to make decisions”\n- “researchers steers towards” -> “researchers have focused on”\n- “Chess, best action” -> “Chess, the best action”\n- “it is independent of opponent and action history” -> “it is independent of the opponent or action history”\n- “history actions” -> “action histories”\n- “In early ages there are heuristic based system to assign different prior” -> “Early approaches employ heuristic based systems to assign different priors”\n- “try to convert the problem to a perfect” -> “try to convert the problem into a perfect”\n- “explicitly with neural networks, and try to optimize it” -> “explicitly with neural networks, trying”\n- (not a phrasing issue but I would have appreciated a citation for the claim at the end of the third paragraph of the intro)\n- “Simulation based approach usually requires large” -> “Simulation based approaches usually require a large”\n- “sequences of existing player and opponent” -> “sequences of the existing player and opponent”\n- “a few underlying complete information state” -> “a few underlying complete information states” \n\nThis issue of readability came up in the figures as well. The figures in the paper are dense and very difficult to parse. There is little explanation in the text, and I found them difficult to glean anything from without an understanding of contact bridge.\n\nFrom what I can gather from the paper this is good and valuable work. However, I think the paper is not yet ready for publication as a communication of this work. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: A method is introduced to estimate the hidden state in imperfect information in multiplayer games, in particular Bridge. This is interesting, but the paper falls short in various ways. Several reviewers complained about the readability of the paper, and also about the quality and presentation of the interesting results. 

It seems that this paper represents an interesting idea, but is not yet ready for publication.
Decision: Reject