Subgame solving without common knowledge
Authors: Brian Hu Zhang
Tuomas Sandholm
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Subgame solving
imperfect information
common knowledge

Abstract: In imperfect-information games, subgame solving is significantly more challenging than in perfect-information games, but in the last few years, such techniques have been developed. They were the key ingredient to the milestone of superhuman play in no-limit Texas hold'em poker. Current subgame-solving techniques analyze the entire common-knowledge closure of the player's current information set, that is, the smallest set of nodes within which it is common knowledge that the current node lies. While this is acceptable in games like poker where the common-knowledge closure is relatively small, many practical games have more complex information structure, which renders the common-knowledge closure impractically large to enumerate or even reasonably approximate. We introduce an approach that overcomes this obstacle, by instead working with only low-order knowledge. Our approach allows an agent, upon arriving at an infoset, to basically prune any node that is no longer reachable, thereby massively reducing the game tree size relative to the common-knowledge subgame. We prove that, as is, our approach can increase exploitability compared to the blueprint strategy. However, we develop three avenues by which safety can be guaranteed. First, safety is guaranteed if the results of subgame solves are incorporated back into the blueprint. Second, we provide a method where safety is achieved by limiting the infosets at which subgame solving is performed. Third, we prove that our approach, when applied at every infoset reached during play, achieves a weaker notion of equilibrium, which we coin affine equilibrium, and which may be of independent interest. We show that affine equilibria cannot be exploited by any Nash strategy of the opponent, so an opponent who wishes to exploit must open herself to counter-exploitation. Even without the safety-guaranteeing additions, experiments on medium-sized games show that our approach always reduced exploitability in practical games even when applied at every infoset, and a depth-limited version of it led to---to our knowledge---the first strong AI for the challenge problem dark chess.

Subgame solving without common knowledge
Brian Hu Zhang
Tuomas Sandholm Computer Science Department, CMU Strategic Machine, Inc. Strategy Robot, Inc.
Computer Science Department Carnegie Mellon University bhzhang@cs. cmu, edu
Optimized Markets, Inc. sandholm9cs. cmu, edu
Abstract
In imperfect-infomme games, subgame solving is significantly more challenging than in perfect-informatio games, but in the last few years, such techniques have been developed. They were the key ingredient to the milestone of superhuman play in no-limit Texas hold' em poker. Current subgame-solving techniques analyze closure of the player's 's current information set, that is, the smallest set of nodes within which it is common knowledge that the current node lies. While this is acceptable in games like poker where the common- knowledge closure relatively small, many practical games have more complex information structure, which renders the common-knowledee large enumerate or even reasonably approximate. We introduce an approach that overcomes this obstacle, by instead working with only low-order knowledge. Our approach allows an agent, upon arriving at an infoset, basically prune any node that is no longer reachable, thereby massively reducing the game tree size relative to the increase exploitability compared to the blueprint strategy. However, we develop three avenues by which safety can be guaranteed. First, safety guaranteed if the results of subgame solves are incorporated back into the blueprint. Second, we provide a method where safety achieved by limiting the infosets at which subgame solving is performed. Third, prove that our approach, when applied at every infoset reached during play, achieves weaker notion equilibrium, which coin affine equilibrium, and which may be of independent interest. We show that affine equilibria cannot be exploited by any Nash strategy of the opponent, opponent who wishes to exploit must open herself to counter-exploitation. Even without the gueeyyggaattneinng additions, experiments on medium-sized games show that our approach always reduced exploitability in practical games even when applied at every infoset, and a knowledge- the first strong Al for the challenge problem dark chess.
the entire mommon-knowleed
closure impractically
subgame. We prove that, is, our approach can
version led to-to our
Introduction
Subgame solving is the standard technique for playing perfect-information games that has been used by strong agents in wide variety of games, including chess [7, 25] and go [22]. Methods for subgame solving in serfect-information games exploit the fact that a solution to subgame can be computed independently of the rest of the game. However, this condition fails in the imperfect-information setting, where the optimal strategy in subgame can depend on strategies outside that subgame.
Recently, subgame solving techniques have been extended imperfect-informaiio games [9, 13]. Some of those techniques are provably safe in the sense that, under reasonable conditions, incorporating them into agent cannot make the agent more exploitable [6, 21, 2, 20, 5, 26, 1, 16].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

These techniques formed the core ingredient toward recent superhuman breakthroughs in Als for no-limit Texas hold' em poker [3, 4]. However, all of the prior techniques have shared weakness that limits their applicability: as first step, they enumerate the entire pommon--knwweede closure of the player's is current infoset, which is the smallest set of states within which common knowledge that the current node lies. In two-player community-card poker (in which each player is dealt private hole cards, and all actions are public, e.g., Texas hold' em), for example, the common-knowledge closure contains one node for each assignment of hole cards to both players. This set has manageable size in such poker games, but in other games, it is unmanageably large.
We introduce a different technique to avoid having to enumerate the entire common -nwwledge closure. We enumerate only the set of nodes corresponding to kth-order knowledge for finite k-in the present work, we focus mostly on the case k = 1. for it already gives us interesting results. This allows an agent to only conduct subgame solving on still-reachable states, which in general is a much smaller set than the whole common-know
subgame.
We prove that, as is, the resulting algorithm, 1-KLSS, does not guarantee safety, but we develop three avenues by which safety can be guaranteed. First, safety is guaranteed if the results of subgame solves are incorporated back into the blueprint strategy. Second, we provide method by which safety is achieved by limiting the infosets at which subgame solving is performed. Third, we prove that our approach, when applied at every infoset reached during play, achieves a weaker notion of equilibrium, which we coin affine equilibrium and which may be of independent interest. We show that affine equílibria cannot be exploited by any Nash strategy of the opponent: an opponent who wishes to exploit an affine equilibrium must open herself to counter-exploitation. Even without these three safety-guarann guaranteenn additions, experiments on medium-sized games show that 1-KLSS always reduced exploitability in practical games even when applied at every infoset.
We use depth-limited 1-KLSS to create, to our knowledge, the first agent capable of playing dark chess, a large imperfect-informatior variant of chess with similar game tree size, at high level. We test it against opponents of various levels, including a baseline agent, an amateur-level human, and the world's ' highest-rated player. Our agent defeated the former two handily, and, despite losing to the top human, exhibited strong performance in the opening and midgame, often gaining a significant advantage before losing it in the endgame.
2 Notation and definitions
An extensive-form perfect-recale zero-sum game with explicit observations (hereafter game) I between two players b and é consists of:
(1) a tree H of nodes with labeled edges, rooted at a root node 0 E H. The set of leaves, or terminal nodes, of H will be denoted Z. The labels the edges are called actions. The child node reached by playing action a at node h will be denoted ha.
(2) a utility function u. Z + R.
(3) map P: (H Z) (NATURE, @ 9) denoting which player's 's turn is.
(4) for each player i E {@, 3.. and each internal node h E H \ Z, an observation (+(h) that player learns upon reaching h. The observation must uniquely determine whether player i has the move; i.c., if (h) = Oth'', then either P(h), P(h') i, or P(h), P(h') # i.
(5) for each node h with P(h) NATURE, a distribution p(-lh) over the actions at h.
player i's observation sequence (hereafter sequence) mid playthrouho is the sequence of observa- tions made and actions played by i so far. The set of sequences of player i will be denoted E, The observation sequence at node h (immediately after i observes (.))) will denoted 8; (h)..
We say that two states f = 00000.................. ar and h²' = .b,...b, ~ h., if s; (h) = (h'). An equivalence class of nodes infoset for player i. If two nodes at which player i moves belong to the same infoset 1, the same of actions must be available h and N'. If a is legal action at we will use La to denote the sequence reached by playing action a at I.
be are indistinguishable to player i, denoted H under ~ an information set, or
If u. u' are nodes or sequences, 3 w' means is an ancestor or prefix (respectively) of u' (or u' w). If S is set of nodes, f ž S means h > h' for some h' E S, and S {2: 2 S}.

---

A sequence-forn mixed strategy (hereafter strategy) of player is vector I E IR",, in which (s)) denotes the probability that player i plays all the actions in the sequence s. If a node or infoset, then we will use the overloaded notation æ(h) == ==ss(())) The set of valid strategies for each player forms convex polytope [15], which we will denote X and Y for d and ( respectively. A strategy profile (2r, y) E X x Y is pair of strategies. The payoff for ( in a strategy profile (I, v) will be denoted u(z, y) ;= >> E
where p(z) is the probability that nature plays all the strategies on the path from 0 to 2. (The payoff for
-(xx y) since the game is zero-sum.) The payoff matrix is the matrix A E I x3% whose bilinear form is the utility function, that is, for which (x. Ay) = u(x; y). Most common game-solving algorithms, such as linear programming [15], counterfactual regret minimization and its modern variants [31, 8), and first-order methods such as EGT [12, 17] work directly with the payoff matrix representation of the game.
The counterfactual best- response value (hereafter best-response value) u² [x) to a @-strategy x X upon playing action a at the normalized best value for against æ after playing a at I: u" (a)la)= = Eeg ([h)a[h] MiinggY:x((aae)) (s)0 ((2))(2)x((2)((z) The best-response value at an infoset is defined as u² (x(1) = max, u² (x( [a). The best-response value u' (z) (without specifying an infoset) is the best-response value at the root, i... mingey u(x,)) Analogous definitions hold for @-strategy y and @-infoset I. A player is playing an E-best response in a strategy profile (x. y) if u(x, y) is within of the best-response value of her opponent's strategy. We say that (z. y) is am E-Nash equilibrium (s-NE) if both players are playing E-best responses. Best responses and Nash equilibria are, respectively, 0-best responses and O-Nash equilibria. An NE strategy is one that is part of an NE. The set of NE strategies is also a convex polytope [15].
We say that two nodes h and h are transpositions if an observer who begins observing the game at h or h' and sees both players' actions and observations at every timestep cannot distinguish between the two nodes. Formally, h, h' are transpositions if, for all action sequences a1 dg.
(I) ha ae is valid (i.e., for all j. aj is legal move in haj is valid, and in this case, we have O,(hai ... ag)) = O,(h'a a ii........ .......... aj) for all players and times 0 < j S t, and
... a)-1)) 1) if and only if h'ai.. ..
(2) ha ag is terminal if and only if h'a a is terminal, and in this case, we have u(hai ... a.) = u(h'a. ..).
For example, ignoring draw rules, two chess positions are transpositions if they have equal piece locations, castling rights, and en passan! rights.
3 Common-knowledee subgame solving
In this section we discuss prior work on subgame solving. First, @ computes blueprint strategy for the full game. During a playthrough, + reaches an infoset 1, and would like to perform subgame solving to refine her strategy for the remainder of the game. All prior subgame solving methods that we are aware of require, as a first step, constructing [6, 21, 2, 20, 5, 26, 1, 16], or at least approximating via samples [27], the common-knoowldde closure of I. Definition 1.
The infoset hypergraph G of a game I' is the hypergraph whose vertices are the nodes of T, and whose hyperedges are information sets.
Definition 2.
Let be a set of nodes in I. The order-k knowledge set 5h is the set of nodes that
are at most distance k - 1 away from S in G. The common- -nonloed---wweggeeee closure S is the connected component of G containing S.
Intuitively, if we know that the true node is in S, then we know that the opponent knows that the true node is in 52 we know that the opponent knows that know that the true node is in S etc., and it is common knowledge that the true node is in S After constructing 1 (where L, as above, is the infoset @ has reached), standard techniques then construct the subgame T (or an abstraction of it), and solve it to obtain the refined strategy. In this section we describe three variants: resolving [6], maxmargin [21], and reach subgame solving [2].
Let Hop be the set of root nodes of 0 that is, the set of nodes h E 000 for which the parent of h is not in for In subgame resolving, the following gadget game is constructed. First, nature chooses node h Hopp with probability proportional to p(h)z(h). Then, e observes her infoset Lg (h).
3

---

and is given the choice to either exit or play. If she exits, the game ends at terminal node 2 with u(2) = u" ( This payoff is called the alternate payoff at (h).. Otherwise, the game continues from node h. In maxmargin solving, the objective is changed to instead find a strategy x' that maximizes the minimum margin M(T) := -u (a'Ir) u (a:] [) associated with any O-infoset T intersecting 1op- (Resolving only ensures that all margins are positive). This can be accomplished by modifying the gadget game. In reach subgame solving, the alternative payoffs u* (x(() are decreased by the gift at I, which is a lower bound on the magnitude of error that e has made by playing to reach in the first place. Reach subgame solving can be applied on top of either resolving or margin
The full game I' is then replaced by the gadget game, and the gadget game is resolved to produce a strategy x' that will use to play to play after I. To use nested subgame solving, the process repeats when another new infoset is reached.
4 Knowledge-limited subgame solving
In this section we introduce the main contribution of our paper, knowledge-limitee subgame solving. The core idea is to reduce the computational requirements of safe subgame solving methods by discarding nodes that are "far away" (in the infoset hypergraph G) from the current infoset.
Fix an odd positive integer k. In order-k k knowledge-linin -imited subgame solving (k- (s-KLSS), we fix O's strategy outside 1 and then perform subgame solving as usual. Pseudocode for all algorithms can be found in the appendix. This carries many advantages:
(1) Since @'s strategy is fixed outside 7t, O's best response outside ] is also fixed. Thus, all nodes outside Th+I can be pruned and discarded.
(2) At nodes h E ] IK, O's strategy is again fixed. Thus, the payoff at these nodes is only a function of @'s strategy in the subgame and the blueprint strategy. These payoff's can be computed from the blueprint and added to the row of the payoff matrix corresponding to @'s s empty sequence. These nodes can then also be discarded, leaving only I*.
(3) Transpositions can be accounted for if k = 1 and we allow a slight amount of incorrectness. Suppose that h, h I are transpositions. Then @ cannot distinguish from h'' ever again. Further, Os information structure after h in T is identical to her information structure in h in 1 Thus, in the payoff matrix of the subgame, h and h induce two disjoint sections of the payoff matrix A, and A₂ that are identical except for the top row (thanks to Item 2 above). We can thus remove one (say, at random) without losing too much. If one section of the matrix contains entries that are all not larger than the corresponding entries of the other part, then we can remove the latter part without any loss since is weakly dominated.
The transposition merging may cause incorrect behavior (over-optimism) in games such as poker, but believe that its effect in game like dark chess, where information is transient at best and the evaluation of a position depends more on the actual position than on the players' information, is minor. Other abstraction techniques can also be used to reduce the size of the subgame, if necessary. We will denote the resulting gadget game ]
In games like dark chess, even individual infosets can have size 107, which means even 7 can have size 14 or larger. This is wholly unmanageable in real time. Further, very long shortest paths can exist in the infoset hypergraph G. As such, it may be difficult to even determine whether given node is in so much less expand all its nodes, even approximately. Thus, being able to reduce to I for finite k is a large step in making subgame solving techniques practical.
The benefit of KLSS can be seen concretely in the following parameterized family of games which we coin N V-matching pennies. We will use it as a running example in the rest of the paper. Nature first chooses an integer n E {1.....N) } uniformly at random. observes [n/2] and e observes [nn + 1)/2j. Then, @ and @ simultaneously choose heads or tails. If they both choose heads, () scores n. If they both choose tails, @ scores N n. If they choose opposite sides, e scores O. For any infoset / just after nature makes her move, there is no common knowledge whatsoever, so / 20 is the whole game except for the root nature node. However, _ consists of only ((k) nodes.
On the other hand, in community Hold'Em, _ always has size most (52)
poker, 1 itself is quite small: indeed, in heads-up Texas
(50) 2s 1.. x 10th and even fewer after public cards

---

have been dealt. Furthermore, game-specific tricks or matrix sparsification [14, 29] can make game solvers behave as if 1 x 10 This is manageable in real time, and is the key that has enabled recent breakthroughs in Als for no-limit Texas hold' em [20, 3, 4]. In such settings, we do not expect our techniques to give improvement over the current state of the art.
The rest of this section addresses the safety of KLSS. The techniques in Section 3 are safe in the sense that applying them at every infoset reached during play in nested fashion cannot increase exploitability compared to the blueprint strategy [6. 21, 2]. KLSS is not safe in that sense:
There exists game and blueprint for which applying 1-KLSS at every infoset reached during play increases exploitability by a factor linear in the size of the game.
Proposition 3.
Proof. Consider the following game. Nature chooses an integer v. E [I,...,NN] and tells @ but not O. Then the two players play matching pennies, with & winning if the pennies match. Consider the blueprint strategy for @ that plays heads with probability exactly 1/2 + 2/N, regardless of n. strategy for +D. However, if maxmargin 1-KLSS is applied
This strategy is a independently at every infoset reached, @ will deviate to playing tails for all n, because she is treating her strategy at all m # n as fixed, and the resultant strategy is more balanced. This strategy is exploitable by @ always playing tails.
Despite the above negative example, we now give multiple methods by which we can obtain safery guarantees when using KLSS.
4.1 Safety by updating the blueprint
Our first method of obtaining safety is to immediately and permanently update the blueprint strategy after every subgame solution is computed. Proofs of the results in this section can be found in the appendix.
Theorem 4. Suppose that whenever k-KLSS performed at infoset (e.g., it can be performed at every infoset reached during play in nested manner), and that subgame strategy is immediately and permanently incorporated into the blueprint, thereby overriding the blueprint strategy in T8. Then the resulting sequence of blueprints has non-increasing exploitability.
To recover full safety guarantee from Theorem 4, the blueprint-not the subgame solution- should be used during play, and the only function of the subgame solve is to update the blueprint for later use. One way to track the blueprint updates is to store the computed solutions to all subgames that the agent has ever solved. In games where only reasonably small number of paths get played in practice (this can depend on the strength and style of the players), this is feasible. In other games this might be prohibitively storage intensive.
It may seem unintuitive that we cannot use the subgame solution on the playthrough on which it is computed, but maintaining safety. This is because, if we allow the choice of information set T in Theorem 4 to depend the opponent's 's strategy, the resulting strategy is exploitable due to Proposition 3. By only using the subgame solve result at later playthroughs, the choice of / no longer depends on the opponent strategy at the later playthrough, so we recover a safety guarantee.
use it forever after that (by incorporating it into the blueprint), while
One might further be concerned that what the opponent or nature does in some playthrough of the game affects strategy in later playthroughs and thus the opponent can learn more about, or affect, the strategy she will face in later playthroughs. However, this is not a problem. If the blueprint an e-NE, the opponent (or nature) can affect which s-NE will play at later playthroughs, but because we will always play from some e-NE, we remain unexploitable.
In the rest of this section we prove forms of safety guarantees for 1-KLSS that do not require the blueprint to be updated at all.
4.2 Safety by allocating deviations from the blueprint.
We now show that another way to achieve safety of 1-KLSS is to carefully allocate how much it is allowed to deviate from the blueprint. Let G' be the graph whose nodes are infosets for @ and in which two infosets / and I' share an edge if they contain nodes that are in the same i-infoset. In other words, G' the infoset hypergraph G. but with every @-infoset collapsed into a single node.
5

---

Theorem 5. Let x be an E-NE blueprint strategy for @. Let I be an independent set in G' that is closed under ancestor (that is, if and II then I' I). Suppose that 1-KLSS is performed at every infoset in I, to create strategy x'. Then x' is also an E-NE strategy.
To apply this method safely, we may select beforehand distribution over independent sets of G', which induces a map V(") + R where p(1) Prz-z [[ E 2]. Then, upon reaching infoset 1, with probability 1 p(T), play the blueprint until the end of the game; otherwise, run 1-KLSS at (possibly resulting in more nested subgame solves) and play that strategy instead. It is always safe to set p(T) S 1/x where X(I*) denotes the chromatic number of the subgraph of G' induced by the infosets in the common-knowe knowledw closure I For example, if the game is perfect information, then G'[ is the trivial graph with only one node I, so, as expected, it is safe to set p(I) that is, perform subgame solving everywhere.
4.3 Affine equilibrium, which guarantees safety against all equilibrium strategies.
We now introduce the notion of affine equilibrium. We will show that such equilibrium strategies safe against all NE strategies, which implies that they only exploitable by playing non-NE strategies, that is, by opening oneself up to counter-exploitation We then show that 1-KLSS finds such equilibria.
Definition 6. A vector x is an affine combination of vectors .i,... Zy. if x Σ; a; = 1, where the coefficients as can have arbitrary magnitude and sign.
> -i-1 a with
Definition 7. An affine equilibrium strategy is an affine combination of NE strategies.
In particular, if the NE is unique, then so is the affine equilibrium. Before stating our safety guarantees, we first state another fact about affine equilibria that illuminates their utility.
Proposition 8. Every affine equilibrium is a best response to every NE strategy of the opponent.
In other words, every affine equilibrium is an NE of the restricted game I' in which @ can only play her NE strategies in I. That is, affine equilibria are not exploitable by NE strategies of the opponent, not even by safe exploitation techniques [10]. So, the only way for the opponent to exploit an affine equilibrium is to open herself up to counter-exploitation. Affine equilibria may be of independent interest as a reasonable relaxation of NE in settings where finding an exact or approximate NE strategy may be too much to ask for.
Theorem 9. Let x be a blueprint strategy for Q and suppose that x happens to be an NE strategy. Suppose that we run 1-KLSS using the blueprint x, at every infosel in the game, to create stralegy x. Then x' is an affine equilibrium stralegy.
The theorem could perhaps be generalized to approximate equilibria, but the loss of a large factor (lincar in the size of the game, in the worst case) in the approximation would be unavoidable: the counterexample in the proof of Proposition 3 has ((1/N)-NE becoming ((1--NE, in game where the Nash equilibria are already affine-closed (that is, all affine combinations of Nash equilibria Nash equilibria). Furthermore, it is nontrivial even define e-affine equilibrium.
Theorem and Proposition 3 together suggest that 1-KLSS may make mistakes when x suffers from systematic errors (e.g., playing certain action too frequently overall rather than in particular infoset). 1-KLSS may overcorrect for such errors, as the counterexample clearly shows. Intuitively, the blueprint plays action too often (e.g., folds in poker), 1-KLSS may try to correct for that game- wide error fully in each infoset, thereby causing the strategy to overall be very far from equilibrium (c.g., folding way too infrequently in poker). However, we will demonstrate that this overcorrection never happens in our experiments in practical games, even if the blueprint contains very systematic errors.
Strangely, the proofs of both Theorem 9 and Theorem 5 do not work for K-KSSS when l: > 1, because it is no longer the case that the strategies computed by subgame solving are necessarily played-in particular, for k: > 1, K-LSSS on an infoset computes strategies for infosets I' that are no longer reachable, and such strategies may never be played. For k xhttht is, for the case of common knowledge-itt is well known that the theorems hold via different proofs [6, 21, 2]. We leave the investigation of the case 1 < ke < oo for future research.

---

2
C
Ca
R1
C2
R3
h
h
Co
C2
Ca h
h
E
h
h
h
h
t
h
h
1
4
O
O
3
O
2
4
O
Figure I: A simple game that we use in our example. The game is modified version of 4-matching pennies. The two players are red (+) and eyan (+). Fill color of a node indicates the player to move at that node. Blank nodes are nature or terminal; terminal nodes are labeled with their utilities. Nodes will referred to by the sequence of edges leading to that node; for example, the leftmost terminal node is 1hh. Dotted lines indicate information sets for that player, and the colored labels give names to those information sets (R for red and C' for cyan). (The --infosets C% and Ca2 are singletons, containing nodes 1 and 4 respectively). The details of the subgame at irrelevant. Nature's strategy at the root node is uniform random.
da
C2
C
CA
R1
C22
R3
Co
C
t
h
h
h
t
h
h
h
4
2
O
3
O
2
Figure 2: The common-knowledge subgame Rt, [' Nature's strategy at all its nodes, once again, is uniform random. The nodes de and d4 are redundant because nature only has one action, but we include these for consistency with the pseudocode.
-1/2
-5
C
R
h
Co
h
h
h
O
4
2
O
3
Figure 3: The subgame for 1-KLSS at R1 Once again, both nature nodes are redundant, but included for consistency with the pseudocode. The counterfactual value at & is scaled up because the other half of the subtree is missing. In addition to this, e gains value 3/2 for playing h and for playing C2, accounting for that missing subtree.
7

---

5 Example of how 1-KLSS works
Figure shows a small example game, Suppose that the @-blueprint uniform random, and consider an agent who has reached infoset R1 and wishes to perform subgame solving. Under the given blueprint strategy, @ has the following counterfactual values: 1/2 at C and C², and 5/2 at C22
The common-knowledge maxmargin gadget subgame [(R can be seen in Figure 2. The 1-KLSS maxmargin gadget subgame [ can be seen in Figure 3.
The advantage of 1-KLSS is clearly demonstrated in this example: while both KLSS and common- knowledge subgame solving prune out the subgame at node 5, 1-KLSS further prunes the subgames at node 4 (because it is outside the order-2 set R2 and thus does not directly affect Rt) and node 3 (because it only depends on O's strategy in the subgame-and not @'s strategy-and thus can be added to a single row of B).
The payoff matrices corresponding these gadget subgames can be found in Appendix C.
6 Dark chess: An agent from only a value function rather than a blueprint
In this section, we give an overview of our dark chess agent, which uses 1-KLSS as a core ingredient. More details can be found in Appendix D. Although wrote agent in game-specifie fashion, many techniques in this section also apply to other games.
Definition 10. A trunk of game I is modified version of I in which some internal nodes h of T have been replaced by terminal nodes and given utilities. We will call such nodes internal leaves. When working with a trunk, internal leaves h can be expanded by adding all of their children into the tree, giving these children utilities, and removing the utility assigned to h.
In dark chess, constructing a blueprint is already difficult problem due to the sheer size of the game, and expanding the whole game tree is clearly impractical. Instead, we resort to a depth-limited version of L-KLSS. In depth- limited subgame solving, only trunk of the game tree is expanded explicitly, and approximations are made to the leaves of the trunk.
Conventionally in depth- limited subgame solving of leaf, both players are allowed choose among continuation strategies for the remainder of the game [5, 1, 16, 27]. In the absence of a mechanism for creating reasonable blueprint, much less multiple blueprints to be used as continuation strategies, we resort to only using an approximate value function ū H + RR. We will not formally define what good value function is, except that it should roughly approximate "the value" of a node h E H, to the extent that such quantity exists (for a more rigorous treatment of value functions in subgame solving, see Kovařík et al., 2021 [16]). In this setting, this is not too bothersome: the dominant term in any reasonable node-value function in dark chess will be material count, which is common knowledge anyway. We use a value function based on Stockfish 13, currently the strongest available chess engine.
games, at each trunk
Subgame solving in ioperfect-informaaiee uation strategies) has not been explored our knowledge (since it not theoretically sound), but it seems reasonable to assume that it would work well with sufficient depth, since increasing depth effectively amounts to adding more and more continuation strategies.
games with only approximate leaf values (and no contin-
To perform nested subgame solving, every time it is our turn, we perform 1-KLSS at our current information set. The generated subgame then replaces the original game, and the process repeats. This approach has the notable problem of information loss over time: since all the solves are depth-limited eventually, we will reach a point where we fall off the end of the initially-crean point, those nodes will disappear from consideration. From game- theoretc perspective, this equates to always assuming that the opponent knew the exact state of the game d timesteps ago, where d is the search depth. As remedy, one may consider sampling some number of infosets I' > 12 \ I to continue expanding. We do not investigate this possibility here, as we believe that would not yield significant performance benefit in dark chess (and may even hurt in practice: since no blueprint is available at /', a new blueprint would have to be computed. This effectively amounts to 3-LLSS, which may lack theoretical guarantees compared to 1- 1-KLSS).
game tree. At this
8

---

Table 1: Experimental results in medium-sizer games. Reward ranges in all games normalized to lie in [-1,1]. Ratio is the blueprint exploitability divided by the post-subgame-solvingg exploitability. The value was set to 0.25 in all experiments, but the results qualitatively similar with smaller values of e such as 0.1. In the g-bet/fold variants, the blueprint is the least-exploitable strategy that always plays that action with probability at least (Kuhn poker with 0. 0.25-fold has exact Nash equilibrium for PI, so we do not include it). Descriptions and statistics about the games can be found in the appendix.
exploitability
game
blueprint
after 1-KLSS
ratio
2x2 Abrupt Dark Hex
.0683
.0625
1.093
4-card Goofspiel, random order
.171
.077
2.2
4-card Goofspiel, increasing order
.17
.0
00
Kuhn poker
.0124
.0015
8.3
Kuhn poker (g-bet)
.0035
.0
OC
3-rank limit Leduc poker
.0207
.0191
1.087
3-rank limit Ledue poker (s-fold)
.0055
.0057
1.087
3-rank limit Ledue poker (e-bet)
.0097
.0096
1.011
Liar's 's Dice, 5-sided die
.181
.125
1.45
100-Matching pennies
.0013
.0098
0.13
7 Experiments
Experiments in medium-sized games. We conducted experiments various small and medium- sized games to test the practical performance I-KLSS. To do this, we created blueprint strategy for @ that is intentionally weak by forcing @ to play an E-uniform strategy (i.e., at every infoset I, every action a must be played with probability at least e/m where m is the number of actions at I). The blueprint is computed as the least-exploitable strategy under this condition. During subgame solving, the same restriction is applied at every infoset except the root, which means theoretically that it is possible for any strategy to arise from nested solving applied to every infoset in the game. The mistakes made by playing with this restriction are highly systematic (namely, playing bad actions with positive probability e); thus, the argument at the end of Section 4 suggests that we may expect order-1 subgame solving to perform poorly in this setting.
We tested on wide variety of games, including some implemented in the open-source library OpenSpiel [19]. All games were solved with Gurobi 9.0 [1 I. and subgames were solved in a nested fashion at every information set using maxmargin solving. We found that, in all practical games (i.e., all games tested except the toy game 100-matching pennies) 1-KLSS in practice always decreases the exploitability of the blueprint, suggesting that 1-KLSS decreases exploitability in practice, despite the lack of matching theoretical guarantees. Experimental results can be found in Table 1. We also conducted experiments at O (so that the blueprint is exact NE strategy, and all the subgame solving needs to do is not inadvertently ruin the equilibrium), and found that, in all games tested, the equilibrium strategy was indeed not ruined (that is, exploitability remained 0). Gurobi was reset before each subgame solution was computed, to avoid warm-starting the subgame solution at equilibrium.
The experimental results suggest that despite the behavior of 1-KLSS in our counterexample to Proposition 3, in practice 1-KLSS can be applied at every infoset without increasing exploitability despite lacking theoretical guarantees.
Experiments in dark chess. We used the techniques of Appendix D to create agent capable of playing dark chess. We tested on dark chess instead of other imperfect-informatee such as Kriegspiel or recon chess, because dark chess has recently been implemented by a major chess website, chess.com com (under the name Fog of War Chess) and has thus exploded in recent popularity, producing strong human expert players. Our agent runs on single machine with 6 CPU cores.
chess variants,
We tested our agent by playing three different opponents:
(1) A 100-game match against a baseline agent, which is, in short, the same algorithm as our agent, except that it only performs imperfect-information search to depth 1, and after that uses Stockfish's 's perfect-information evaluation with iterative deepening. The baseline agent

---

is described in more detail the appendix. Our agent defeated it by score of 59.5 40.5, which statistically significant the 95% level.
One of the authors of this paper is rated approximately 1700 on chess.com in Fog of War, and has played upwards of 20 games against the agent, winning only two and losing the remainder.
(3)
Ten games against FIDE Master Luis Chan ("luizzy"), who is currently the world's strongest player on the Fog of War blitz rating list' on chess.com, with rating of 2416. Our agent lost the match 9-1. Despite the loss, agent demonstrated strong play in the opening and midgame phases of the game, often gaining large advantage before throwing it away in the endgame by playing too pessimistically.
The performances against the two humans put the rating of our agent at approximately 2000, which is strong level of play. The agent also exhibited nontrivial plays such as bluffing by attacking with unprotected pieces, and making moves that exploit the opponent's ' lack of knowledge-sometiing that agents like the baseline agent could never do. We have compiled and uploaded some representative samples of gameplay of our dark chess agent, with comments, at this link.
8 Conclusions and future research
developed a novel approach subgame solving, k-KLSS, imperfect-informalee games that avoids dealing with the common-knowledge closure. Our methods vastly increase the applicability of subgame solving techniques; they can now used in settings where the common common-knowlede -nowledge closure is too large enumerate or approximate. We proved that as is, this does not guarantee safety of the strategy, but we developed three avenues by which safety guarantees can be achieved. First, safety is guaranteed if the results of subgame solves are incorporated back into the blueprint strategy. Second, the usual guarantee of safety against any strategy can be achieved by limiting the infosets at which subgame solving is performed. Third, proved that 1-KLSS, when applied at every infoset reached during play, achieves a weaker notion of equilibrium, which we coin affine equilibrium and which may be of independent interest. We showed that affine equilibria cannot be exploited by any Nash strategy of the opponent, so an opponent who wishes to exploit an affine equilibrium must open herself counter-exploitation. Even without the guretttguraatteiing additions, experiments on medium-sized games showed that 1-KLSS always reduced exploitability in practical games even when applied every infoset, and lepth-limited 1-KLSS led to, our knowledge, the first strong AI for dark chess.
This opens many future research directions:
(1) Analyze K-LSSS for < k < oo in theory and practice.
(2) Incorporate function approximation via neural networks to generate blueprints, particles, or both.
(3) Improve techniques for large games such as dark chess, especially managing possibly- game-critical uncertainty about the opponent's position and achieving deeper, more accurate search.
Acknowledgments and Disclosure of Funding
This material is based on work supported by the National Science Foundation under grants IIS- 1718457, IIS-190141 and CCF-1733556, and the ARO under award W91 1NF2010081. We also thank Noam Brown and Sam Sokota for helpful comments.
'That rating list is by far the most active, it is reasonable assume those ratings most representative.
10

---

References
[1] Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong, Combining deep reinforcement learning and search for imperfect-information games. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
[2] Noam Brown and Tuomas Sandholm. Safe and nested subgame solving for imperfect- information games. In Conference on Neural Information Processing Systems (NeurIPS), 2017.
[3] Noam Brown and Tuomas Sandholm. Superhuman Al for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418-222 2018.
[4] Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, 365(6456):885- 2019.
[5] Noam Brown, Tuomas Sandholm, and Brandon Amos.
Depth-limited solving for imperfect- information games. In Conference Neural Information P Processing Systems (NeurIPS), 2018.
[6] Neil Burch, Michael Johanson, and Michael Bowling. Solving imperfect information games using decomposition. In AAAI Conference Artificial Intelligence (AAAI), 2014.
[7] Murray Campbell, A Joseph Hoane Jr, and Feng-hsiung Hsu. Deep Blue. Artificial Intelligence, 134(1-2):57-833 2002.
[8] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive Blackwell approachability: Connecting regret matching and mirror descent. In AAAI Conference on Artificial Intelligence (AAAI), 2021.
[9] Sam Ganzfried and Tuomas Sandholm. Endgame solving in large imperfect-infooration games. In International Conference on Autonomous Agents and Multi-Agen Systems (AAMAS), 2015. Early version in AAAI-13 workshop on Computer Poker and Imperfect Information.
[10] Sam Ganzfried and Tuomas Sandholm. Safe opponent exploitation. ACM Transaction Economics and Computation ( (TEAC), 5(2):8:1-288 2015. Best of EC- special issue.
[11] Gurobi Optimization, L.I.C Gurobi optimizer reference manual, 2020.
[12] Samid Hoda, Andrew Gilpin, Javier Peña, and Tuomas Sandholm. Smoothing techniques for computing Nash equilibria of sequential games. Mathematics of Operations Research, 35(2), 2010.
[13] Eric Jackson. A time and space efficient algorithm for approximately solving large imperfect information games. In AAAI Workshop on Computer Poker and Imperfect Information, 2014.
[14] Michael Johanson, Kevin Waugh, Michael Bowling, and Martin Zinkevich. Accelerating best response calculation in large extensive games. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2011.
[15] Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel. Fast algorithms for finding randomized strategies in game trees. In ACM Symposium on Theory of Computing (STOC), 1994.
[16] Vojtëch Kovařík, Dominik Seitz, and Viliam Lisý. Value functions for depth-limited solving in imperfecttinfforation games. In AAAI Reinforcement Learning in Games Workshop, 2021.
[17] Christian Kroer, Gabriele Farina, and Tuomas Sandholm. Solving large sequential games with the excessive gap technique. In Conference Neural Information Processing Systems (NeurIPS), 2018.
[18] H. W. Kuhn. A simplified two-person poker. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games, volume of Annals of Mathematics Studies, 24, pages 97-103. Princeton University Press, Princeton, New Jersey, 1950.
[19] Mare Lanctot, Edward Lockhart, Jean- -aptiste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafiei, Daniel Hennes, Dustin Morrill, Paul Muller, Timo Ewalds, Ryan Faulkner, János Kramár, Bart De Vylder. Brennan Saeta, James Bradbury, David Ding, Sebastian Borgeaud, Matthew Lai, Julian Schritwiisser, Thomas Anthony, Edward Hughes, Ivo Danihelka, and Jonah Ryan-Davis. OpenSpiel: A framework for reinforcement learning in games. CoRR, abs/1908 hts/1908.0m 009409953, 2019.

---

[20] 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, May 2017.
[21] Matej Moravcik, Martin Schmid, Karel Ha, Milan Hladik, and Stephen Gaukrodger. Refining subgames in large imperfect information games. In AAAI Conference on Artificial Intelligence (AAAI), 2016.
[22] David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484, 2016.
[23] David J Slate and Lawrence R Atkin. Chess 4.5 the Northwestern University chess program. In Chess skill in Man and Machine, pages 82-118. Springer, 1983,
[24] Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: Opponent modelling in poker. In Proceedings of the 2 Annual Conference on Uncertainty Artificial Intelligence (UAI), July 2005.
[25] Stockfish. https: https: httpss///stoccffsshhsssssese org/ 2021.
[26] Michal Sustr, Vojtéch Kovařík, and Viliam Lisy. Monte Carlo continual resolving for online
strategy computation in imperfect information games. In Autonomous Agents and Multi-Agent Systems, pages 224-232, 2019.
[27] Michal Sustr, Vojtech Kovařík, and Viliam Lisy. Particle value functions in imperfect informa- tion games. In AAMAS Adaptive and Learning Agents Workshop, 2021.
[28] Brian Hu Zhang and Tuomas Sandholm. Small Nash equilibrium certificates in very large games. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
[29] Brian Hu Zhang and Tuomas Sandholm. Sparsified linear programming for zero-sum equilib- rium finding. In International Conference on Machine Learning (ICML), 2020.
[30] Brian Hu Zhang and Tuomas Sandholm. Finding and certifying (near-)optimal strategies in black-box extensive-form games. In AAAI Conference on Artificial Intelligence (AAAT), 2021.
[31] Martin Zinkevich, Michael Bowling, Michael Johanson, and Carmelo Piccione. Regret mini- mization games with incomplete information. In Conference on Neural Information Process- ing Systems (NeurIPS), 2007.
12


Reviews:
[{"review_id": "z3HK7J0NwSM", "reviewer": "Reviewer_be5C", "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.\n", "questions": "", "limitations": "", "rating": 8, "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: 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.\n\nClarity: 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. \n\nOne 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?\n\nQuality: 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. \n\nSignificance: 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.\n\n\nMinor comments: \n\nThe 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.\n\nI 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.\n\nTheorem 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?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "mfbrOyV31Y", "reviewer": "Reviewer_Dn9V", "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.\n", "questions": "", "limitations": "", "rating": 6, "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": "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?\n\nMoreover, 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?\n\nOtherwise, 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.\n\nFew other nitpicks:\nLine 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. \n“Kth-order knowledge” is mentioned in the introduction (line 46) without any (even informal) explanation.\nIt 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. \n\n\n### After rebuttal\n\nThank you for your response. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "I do not have any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "25"}, "extra_text": {}}, {"review_id": "N7MuXIZ7h_m", "reviewer": "Reviewer_kM15", "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. ", "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: 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.\n\nLine 27: \"massive challenge problem\" is unnecessary hype\nLine 60-61: \"massive benchmark game\" again is hype -- there is no citation for this game.r chess). \n\nQuality: 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. \n\n\nThe 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.\n\nI did not review the proofs for correctness.  \n\nClarity: 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.\n\nIs 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?\n\nSignificance: 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "2gwTxoGvJtv", "reviewer": "Reviewer_MEQH", "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.  \n", "questions": "", "limitations": "", "rating": 7, "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": "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. \n\nAlthough 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).  \n\nThe 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? \n\nI 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? \n\nAdditionally, 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? \n\nOverall, 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.  \n\n__________________\nI have read the rebuttal and do not change my score. Thank you for the detailed responses to my questions, that clears a lot up. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is mainly theoretical so I think the authors have adequately addressed the limitations and societal impact. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

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)