Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors develop a new approximation to for subgame solving that approximate common knowledge using lower-order knowledge. Using theoretical and empirical tests they show that these algorithms can reduce exploitability when the information sets are large. Finally, they use these ideas to develop a game playing agent for dark chess and test it against algorithms, a coauthor and the current top online player. 
main_review: Originality: To my knowledge this work is original and most excitingly this is one of the first game playing agents for dark chess. The research direction and prior art are clearly stated and the problem addressed in this work is both timely and at the frontier of what could be possible.

Line 27: "massive challenge problem" is unnecessary hype
Line 60-61: "massive benchmark game" again is hype -- there is no citation for this game.r chess). 

Quality: I would have liked to see empirical evaluations for higher k for at least some of the games even if there aren't theoretical guarantees available. I would also have liked to see exploitability improvements (or possible failures) from a more diverse set of blueprint strategies than just \epsilon-uniform. 


The results on dark chess are quite exciting but the best evidence that the agent is playing at the level of an amateur human comes from playing against a co-author. The possible bias of this kind of evaluation (there is a strong (unconscious) incentive to lose to get the paper into NeurIPS!) should at least be mentioned and giving the agent an ELO rating based on these two data points feels like building on top of what is already a relatively small sample size.

I did not review the proofs for correctness.  

Clarity: The paper could be organized better. In particular I would like to see a more succinct outline of the dark chess game playing agent. I would like to see a more clear contrast of what we have learned from imperfect information zero-sum games from poker and what we will learn from dark chess as they push on different aspects of the problem. Perhaps most interestingly would be a direction where a single algorithm could yield superhuman performance in both settings and this possibility could be commented on.

Is this the first work to develop a game playing agent for this game? Are there other baselines available besides a lesion of this agent? Is the Stockfish agent being run with maximum settings on the comparable hardware?

Significance: This paper passes the bar as a significant contribution with theoretical results, empirical validation and quantification and an exciting man vs. machine bake-off. I hope that by the time of the conference the experiments can be improved. Having the agent play more humans would significantly strengthen the claims here. 
limitations_and_societal_impact: See above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposes a new method for subgame solving in two-player zero-sum extensive-form games with imperfect information. Traditional subgame solvers rely on the so-called common-knowledge closure that guarantees the opponent can not exploit the strategy computed in the subgame in the whole game. The problem with the common-knowledge closure is that its size may be beyond the abilities of contemporary solvers in case the game does not reveal enough information observable by both players during the course of play. To enable solving even subgames with large common-knowledge closures of the information set in the root, the authors introduce order-k knowledge sets as sets of nodes in the game tree that are reachable from the base set in at most k-1hyperedges in the infoset hypergraph. The order-k knowledge sets reach the common-knowledge closure as k approaches infinity. The order-k knowledge sets may be much smaller than the common-knowledge sets, which results in more efficient subgame solving, but this comes at the expense of the exploitability of the computed strategy. As the authors show, the exploitability may increase by a factor linear in the size of the game. The authors hence propose two methods for mitigating it. The first method requires updating the blueprint strategy after every iteration of subgame solving, while the second method restricts the possible deviations from the blueprint strategy. Both methods guarantee that the exploitability of the new strategy will not exceed the exploitability of the blueprint. Using the order-1 knowledge-limited subgame solver as well as several other heuristics, the authors built an agent for playing a large extensive-form game called dark chess. In the experimental part of the manuscript, the authors first show that their method successfully decreases the exploitability of the blueprint strategy for seven medium-sized games. In the second part, they report results achieved with the agent playing dark chess. The agent can beat a baseline player and an amateur human player but loses against the current champion.

main_review: The idea of a limited-knowledge closure as a restriction of the common-knowledge closure is indeed natural and interesting enough to warrant further investigation. The theoretical results presented by the authors are relatively simple. Still, the proofs seem correct, and the methods proposed in Theorems 4 and 5 mitigate the main drawbacks of subgame solving based on order-k knowledge sets. I am a bit confused regarding motivation for Theorem 9, though. I understand it shows that 1-KLSS reaches a strategy that is the best response but may not be equilibrial, thus in a way mitigating exploitability even without employing methods introduced earlier. However, why would we need to solve a subgame if we already have a Nash blueprint strategy at hand? What is the point?

Moreover, I believe the experimental part does not present enough evidence to support the authors’ claims fully. The primary motivation of the paper is to solve games where common-knowledge closure is too large for standard subgame solvers to compute a solution. Therefore, I would expect to find some experimental comparison with these subgame solvers in this work in terms of runtimes, memory requirements, and decreases in exploitability. For completeness, it would also help to show how big the games are (number of information sets, number of sequences, etc.) and what the difference is in sizes of common-knowledge closures and order-1 knowledge sets. If I understand it correctly, the version of 1-KLSS used in the experiments does not employ the exploitability mitigation methods. How does the exploitability (and also runtime, memory requirements) change when they are used? Do the authors have some intuition why 1-KLSS manages to refine the strategy well in some cases, but in others (e.g., dark hex or Leduc poker), it remains mostly unchanged?

Otherwise, I find the text of the manuscript to be fairly well written. The example in Appendix D illustrates well the differences between using the common-knowledge closures and order-1 knowledge sets. I would argue that including at least a shortened version of the example in the main text may significantly help the readers to familiarize themselves with the introduced concepts and may serve a better purpose than, e.g., the description of tricks used in the dark chess player (even though its performance is an impressive feat). The language of some of the definitions and claims also feels a bit too colloquial and vague at times, especially later in the paper, e.g., in Proposition 8, Theorem 9, and Definition 10.

Few other nitpicks:
Line 45: I do not think it is fair to call order-k knowledge sets a “completely different technique” when they in fact generalize the common-knowledge closures. 
“Kth-order knowledge” is mentioned in the introduction (line 46) without any (even informal) explanation.
It may also help to (at least informally) explain what a “blueprint” strategy is and what purpose it serves, as it may not be a common-knowledge among all the readers. 


### After rebuttal

Thank you for your response. 

limitations_and_societal_impact: The authors mention the limitations of their technique and describe settings when the technique may not provide significant improvements over the common-knowledge closure, which I appreciate. I still believe some experimental comparison with the standard subgame solvers is desirable, though.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a novel technique for search in imperfect information games. One problem with existing subgame solving techniques is that they construct a gadget game with a chance node that samples over all possible states in the subgame. This gadget game will be prohibitively large in large games. To overcome this problem, the authors create a smaller gadget game where only states corresponding to the k-th order common knowledge. While an unsafe method as-is, the authors introduce three fixes to make this technique safe. They show empirical results on a number of openspiel games and show that k-KLSS always improves exploitability. Their main result is impressive state-of-the-art performance on dark chess.  

main_review: My main concern with this paper is that the technique is not safe. Although the authors provide theorems 4 and 5, I don’t think these theorems will change the method to make it safe. Theorem 4 is technically correct, but I don’t think it amounts to anything that will make the technique actually safe. Going back to the counterexample in proposition 3, if we play this game against 1-KLSS, we can always exploit it because we know it will always play tails. Theorem 4 doesn’t solve this problem because it only updates the blueprint after you solve the subgame and play the action. Theorem 5 also seems weak to me because it starts with the assumption that you already have an epsilon-Nash, which is a strong assumption and in which case you could just do nothing and keep an epsilon-Nash. While affine equilibrium could be a decent solution concept (I’m not quite sure), theorem 9 also assumes that you start with a Nash equilibrium blueprint. Since there are also no experiments that use or validate these theorems, I am unconvinced that they can be used to make the technique safe in practice. With that being said, I give credit to the authors for pointing out the limitations of the method, for example in the last two paragraphs of section 4. 

Although this method seems to be unsafe, that does not disqualify it from being a good contribution, since previous unsafe subgame solving techniques have had good empirical success. However, since the method is unsafe, I would like to see some more empirical experiments to further validate the method. For example, in the medium-size game experiments, I am not convinced that adding epsilon-uniform noise is enough to systematically bias the blueprint. Instead, if you added epsilon-fold noise (where it folds with epsilon probability) for poker games, my guess would be that the new strategy would be worse than the old strategy. I like that many medium-sized games were used, but the results give the impression that 1-KLSS will always be less exploitable than the blueprint, which is not the case for different blueprints. In general, I would like to see more theoretical/empirical exploration of the types of games/blueprints where 1-KLSS performs well and where it will fail (such as the counterexample).  

The results for Dark Chess are very exciting and I view them as being a major contribution. Games such as Dark Chess/Recon Chess/Stratego have recently emerged as the next benchmark for the 2p zero-sum research community, and this paper is the first to achieve very strong performance on these types of very large games. However, I would like to see discussion in the paper of how general this method is. Section 5 seems to include a lot of domain-specific tricks, which makes me less sure that it can generalize to a game like Stratego. Furthermore, I am not sure why this method works on Dark Chess. A possible explanation the authors give is that |I^1| is much less than |I^{\infty}| in Dark Chess but not in poker. Do the authors have any evidence for this claim? “In such settings [poker], we do not expect our techniques to give much improvement over the current state of the art” should include clearer explanation for why: is it that “I^3 = I^∞ for every I (and I^2 is already very close to I^∞, excluding only “blockers”)“, or is it “Further, I^∞ itself is quite small”? Perhaps the information of the sizes of |I^k| for different k can be included in the experiments. I don’t see how Dark Chess has a fundamentally different information structure from poker, in that the private information in Dark Chess can be viewed as a hand in poker, so some further explanation of this would be great. For example, would this method work for Gin Rummy? Also, isn’t |I^1| still prohibitively large in Dark Chess? How are these subgames solved tractably? 

I am confused about how you can throw out the nodes in $\bar{I^{k+1}} \setminus \bar{I^k}$. In section 4 item 2 the authors say that “the payoff at these nodes is only a function of ⊖’s strategy in the subgame and the blueprint strategy.” but this doesn’t make sense to me. When running CFR on the gadget game, ⊖’s policy in the subgame changes every iteration, so the payoff for each node of that kind needs to be recomputed every iteration. Is just this a simply a simplification? Should these nodes actually be recomputed but instead it works empirically if we replace them with static values from the blueprint? 

Additionally, I would like to see more details, maybe in the appendix, about how the Dark Chess AI was created. For example, how was the subgame solved (CFR, LP?), what are all the hyperparameters? 

Overall, I am excited by the results in this paper and by the novel method, so I would like to see the paper accepted, but I think the paper could be made stronger with the suggestions above.  

__________________
I have read the rebuttal and do not change my score. Thank you for the detailed responses to my questions, that clears a lot up. 
limitations_and_societal_impact: This work is mainly theoretical so I think the authors have adequately addressed the limitations and societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper deals with two related problems. The more fundamental contribution is an analysis and partial algorithmic solution to the problem of subgame solving in a subclass of games with intractable large public states. The other is creation and evaluation of an AI for playing dark chess - a chess variant with imperfect information. The key solution to the first problem is to assume limited nesting of player’s beliefs about the opponent’s beliefs. The paper is quite thorough in exploring at least some theoretical guarantees of this approach, since finding counterexamples would not be hard. The empirical evaluation shows that the algorithm practically works much better than the theoretical guarantees suggest. For the second problem, the paper introduces an algorithm which shares the key idea with the solution to the first problem, but then adds many theoretically unsound domain-specific modifications. The paper shows that this algorithm performs well against other programs as well as moderately strong human players.

main_review: Originality: The idea of limiting the amount of nesting in beliefs is quite straightforward and has appeared before. However, the depth of its analysis in the context of EFGs and turning it into a decent bot for playing a human-scale game is definitely novel.

Clarity: The paper is very dense and requires quite a lot of background knowledge to sully comprehend. However, I assume it is still understandable on a higher level of abstraction even without that. 

One thing that was not clear to me is how exactly were the games in the experimental evaluation split to subgames. Were all subgames in the games resolved for the evaluation in Table 1?

Quality: The notation in the paper is consistent and understandable.  The propositions are believable, though I did not check all the proofs in the appendix carefully. The experiments are well designed, thorough and performed on a wider variety of games. 

Significance: The problem of large public states is a natural next research challenge in generalisation of theoretically sound imperfect information game playing to arbitrary domains. This paper proposes a solution that seems to work very well in practice and provides some insight into properties of this problem. I expect this paper to inspire further research in this direction in the near future.


Minor comments: 

The long lists of sometimes even 9 citations are not really helpful for understanding the presented paper, nor for knowing what the reader should find in the referenced papers. The really look like an attempt to artificially increase the number of citations in a clique and should be, in my opinion, avoided.

I like the observations at the beginning of Section 4 (lines 149-163). I think it may be useful to reference them from follow-up papers. Restructuring them o a form of a proposition / observation with a unique number within the paper would make it easier.

Theorem 9 sounds very weak as it is. Why would we run subgame solving if we already have an equilibrium. Why it is difficult to generalize it to starting with an epsilon-equilibirum?

limitations_and_societal_impact: The authors did not addressed the limitations and potential negative societal impact. While a generic discussion of the dangers of game theoretic research could be added, I personally do not think it is necessary for this paper.
review_title: null

Meta-review: This appears to be a solid paper with strong reviews. The reviewer concerns were addressed with clarity and detail by the authors. I hope that any final version of the paper will incorporate improvements as a result of the reviewer feedback.

Decision: Accept (Spotlight)