Efficient Subgame Refinement for Extensive-form Games
Authors: Zhenxing Ge
Zheng Xu
Tianyu Ding
Wenbin Li
Yang Gao
Venue: NeurIPS 2023 poster (2023)
Keywords: Subgame solving
extensive-form game
imperfect information

Abstract: Subgame solving is an essential technique in addressing large imperfect information games, with various approaches developed to enhance the performance of refined strategies in the abstraction of the target subgame. However, directly applying existing subgame solving techniques may be difficult, due to the intricate nature and substantial size of many real-world games. To overcome this issue, recent subgame solving methods allow for subgame solving on limited knowledge order subgames, increasing their applicability in large games; yet this may still face obstacles due to extensive information set sizes. To address this challenge, we propose a generative subgame solving (GS2) framework, which utilizes a generation function to identify a subset of the earliest-reached nodes, reducing the size of the subgame. Our method is supported by a theoretical analysis and employs a diversity-based generation function to enhance safety. Experiments conducted on medium-sized games as well as the challenging large game of GuanDan demonstrate a significant improvement over the blueprint.

Efficient Subgame Refinement for Extensive-form Games
Zhenxing Ge Nanjing University Nanjing, Jiangsu, China zhenxingge@smail .nju.eu..cm edu.cn
Zheng Xu
Nanjing University Nanjing, Jiangsu, China xuzhengcs@smaill nju. edu.
Tianyu Ding
Wenbin Li' Nanjing University Nanjing, Jiangsu, China liwenbin@nju.e edu. cn
Yang Gao" Nanjing University Nanjing, Jiangsu, China gaoy@nju. ju. edu. cn
Microsoft Corporation Redmond, Washington, USA tiayyddin@miccoooof..cm com
Abstract
Subgame solving is an essential technique in addressing large imperfect information games, with various approaches developed to enhance the performance of refined strategies in the abstraction of the target subgame. However, directly applying existing subgame solving techniques may be difficult, due to the intricate nature and substantial size of many real-world games. To overcome this issue, recent subgame solving methods allow for subgame solving limited knowledge order subgames, increasing their applicability in large games: yet this may still face obstacles due to extensive information set sizes. To address this challenge, we propose generative subgame solving (GS2) framework, which utilizes a generation function identify subset of the earliest-reached nodes, reducing the size of the subgame. Our method is supported by theoretical analysis and employs a diversity-ban -ased generation function enhance safety. Experiments conducted on research games as well as the challenging large game of GuanDan demonstrate a significant improvement over the blueprint.
Introduction
Subgame solving is standard technique commonly adopted by superhuman AIs to play in games [Campbell et af.) [002 Silver et af.] 2016). This approach takes advantage of the fact that for perfect information games (where both players have complete knowledge about the state of the game), finding optimal strategies at any given decision node only requires knowledge of the subgames rooted at that node [Brown and Sandholm 2017]. Therefore, AI agents can make use of this fact to improve their own strategies while playing with others, which proves significantly beneficial for large games, e.g., Chess [Campbell al. 2002 and Go Silver al. 2017].
Recent advancements in langgame-solvving techniques have proven to be highly successful in imperfect information games, such no-limit Texas hold'em poker [Moravčík al. 2017 Brown and Sandholm 2018, 2019], Mahjoog [Li et al.) 2020). and dark chess [/hang and Sandholm 2021] However, state-of-the-art subgame solving algorithms suffer from the efficiency of constructing and solving large games. This limitation hinders their practicality for performing subgame-solving on large subgame trees, thus restricting their application in games such as DouDiZhu (Zha al.
2021 Jiang et al. 2019) and GuanDan [u et al. 2022], which have average information set sizes
"Correpooding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

up to 1023 and 1000 respectively. The substantial size of these games dramatically increases the magnitude of players' [Z,] in subgame, rendering impractical find desirable strategies in real time, as convergence within the limited time frame cannot be guaranteed. To address this computational challenge, techniques such as Abstraction [Sandholm] [015] Brown et al., 2015] are commonly used in Texas Hold 'mm. However, it has been observed that these techniques are inadequate for games like GuanDan (Zha et al. 2021]. A recent work [Zhang and Sandholm 2021 has partially alleviated this problem by partitioning the subgame tree according to players' knowledge order and discarding nodes that are "far away" from the current infoset. This approach can enable safe strategy refinement under specific conditions of usage in much smaller subgame, effectively reducing the number of subgame-solving player's ' information sets [Zz]. Nonetheless, the large number of states within other players' infosets [_ remains unmanageably large and cannot be further reduced, making it difficult to apply these approaches to large games. Moreover, the players' infoset might be complex, and enumerating all states within these sets during subgame construction can be non-trivial task, adding to the complexity of subgame development.
To address the intricate nature of large games, present novel approach called generative subgame solving (GS2). Real-time refinement of these games requires the utilization of a reduced subgame that encompasses fewer players' infosets, which can be efficiently constructed and solved in an online manner while maintaining certain safety guarantees. Our proposed GS2 framework employs generation function that generates a subset of the other player's 's infoset, effectively reducing the number of information states [_-]. Subsequently, a subgame is constructed using nodes rooted in these states. The proposed GS2 framework enables players to construct a more manageable subgame, even in the context of large games. However, the exploitability of the refined strategy may potentially increase compared to the previous knowledge-limiter subgame solving, as there is information loss during the construction of the subgame tree. To mitigate this, we begin by providing a theoretical analysis of GS2. We then propose a diversity-based generation function that produces "diverse" subsets, as determined by the analysis, to reduce the exploitability of the refined strategy. Experiments show that GS2, when combined with diversity-based generation function, significantly enhances performance, making it comparable to the knowledge- limited subgame solving method, while requiring much less computation time.
In this paper, we make the following specific contributions:
We propose novel subgame solving method generatiee subgame solving (GS2). Unlike traditional techniques that require the full information set, GS2 innovatively generates a subset of the opponent's infoset, thereby reducing the number of information states. This allows for substantial subgame size reduction, making GS2 particularly beneficial for large games, which have historically been challenging due to their vast information set sizes.
We provide the thcoretical analysis of GS2 with arbitrary generation functions, a feature that has been largely overlooked in the past. We leverage the theoretical understanding to introduce a diversity-bast generation function for GS2, leading to a significant reduction in the potential exploitability of the refined strategy, common issue encountered in previous showledge-limitee subgame-solving techniques.
We conduct extensive experiments for evaluating GS2 on both research games and the notoriously complex large poker game, GuanDan. The experiments underscore the practical value of our method, as GS2 successfully reduces exploitability and increases the expected payoff with appropriate generation functions. In comparison to the knowledge-limin limited subgame-solving method, GS2 delivers comparable performance while significantly reduc- ing computation time. Moreover, in relatively large games with time limits, GS2 outperforms the lnolledge-limitdd subgame solving, thus showcasing its effectiveness and efficiency.
2 Related Work
The concept of refining coarse strategy (also known blueprint) in imperfect information games has been studied for a long time GGilpin and Sandholm 2006). A crucial component of modern refinement techniques is determining the new strategy, which can be adapted from the blueprint or computed from seratch.
The adaptation-based method samples the outcomes of the current games and adapts the current strategy. Online outcome sampling (OOS) method [Lisy et al. (005) is a simulation-based algorithm
that relies on Monte Carlo Counterfactual Regret Minimization Lanctot et al. 2009], which conducts

---

targeted outcome sampling and updates the regret of each action, resulting in an adapted strategy. Monte Carlo Continual Resolving method [Sustr et al., 2019] combines OOS with the Continual Resolving method [Moravčík et al. 2017] to enhance sampling efficiency while minimizing memory costs associated with OOS. Parametric Monte-Carlo Policy Adaptation method [Li et al., 2020] improves this by performing Monte Carlo tree search for sampling, as well as gradient updates using the sampled trajectories to adjust the blueprint. Despite being theoretically sound, most Adaptation- based Methods are limited in application due to requiring online adaptation to be performed using the same or similar method that computes the blueprint.
On the other hand, methods that compute the new strategy from scratch have no such requirement. Endgame subgame solving methods [Ganzfried and Sandholm 2015 Gilpin and Sandholm 2006] first construct the subgame and assume that all the players conform to the pre-defined blueprint before reaching the subgame. The new strategy is then computed in the subgame and the player that performs endgame solving proceeds implement the new strategy instead of the blueprint in the subgame. Conversely, safe subgame solving methods [Burch et al. 2014 Moravcik et al. 2016 Brown and Sandholm 2017, Brown et al.) 2018 Zhang and Sandholm, 2021 use an evaluation function to construct an augmented subgame, ensuring that the new strategy devised in the augmented subgame is less exploitable than the blueprint.
Search algorithms are also applied for obtaining better joint policy within teammates in collaborative
games such Hanabi [Lerer al., 2020, Hu et al. [021] and the bidding phases of contract Bridge (Tian et al. 2020]. For example. SPARTA [Lerer et al. 2020] utilizes exact belief updates for single-agent search and multi-agent search and retrospective belief updates for multi-agent search to handle the large belief range. Subsequently, the strategy is improved through Monte Carlo rollouts. On the other hand, instead of maintaining an explicit belief distribution in single-agent search, Learned Belief Search (Hu et al., 2021] method uses learned belief model to sample states from the belief distribution, allowing for the application in games with large belief space. Rather than simply improve the strategy via rollouts, Joint Policy Search (Tian et al. 2020) method first decomposes the global changes of the game value into local changes at each infoset, and then iteratively improves the strategy based on the decomposition. Although these approaches primarily focus improving strategy in collaborative settings and could not be directly used in games with adversaries, the underlying idea could be helpful when developing new technique that searches within teammates in games like GuanDan.
Our method follows the scheme of subgame solving. Different from the existing methods, our method focuses on expanding the applicability of subgame solving to large games that are intractable for existing techniques. This is achieved by generating smaller subgame, thereby enabling the integration of techniques that enhance the safety and performance of the refined subgame strategy, such as those presented in [urcch et al. 2014 Brown and Sandholm 2017).
It is worth noting that previous techniques, such [Brown and Sandholm 2015 Brown et al. 2015). J
also explored the real-time reduction of the entire subgame. These techniques specifically consider the subgame tree that follows rational opponent's action and disregards the remaining parts. While these techniques appear promising, they lack a solid theoretical guarantee. Furthermore, they are only applicable action abstraction, as the chance player's 's actions are determined by a fixed probability distribution, and one cannot assume the rationality of the chance player. Thus, these techniques are not suitable for real-world games that involve enormous chance outcomes, such as GuanDan.
3 Preliminaries
3.1 Extensive-form Games
An extensive-form game with imperfect information can be formulated as G (N, P.I, {u]}} where N = 21, {C(c) is the set of players, c denotes the chance player who chooses actions with a fixed probability, H is the set of all possible history sequences a a'a2... a² and each a² is an action. For each history h E H, player function P: H + N gives the acting player. Additionally. the action set A(h) contains legal actions that player P(h) can choose, which is formally expressed as A(h) {a]h- E H). The set of leaf nodes, or terminal nodes, is denoted by Z. For each player i N, the payoff function W; : Z -> R is the payoff that player will receive upon reaching terminal history E Z. Imperfect information is represented by information sets (infosets).
3

---

Infoset I is the set of information partitions of H. For any infoset I; Z,, histories h, h' E I are indistinguishable to player As such, the acting player and the corresponding legal action set must be the same for all nodes in the same information set. Hence, by denoting the acting player and action set at infoset I as P(I,) and AT.), we have P())) P(h), A(T,) = A(h), wh E JT. We also use I (h) to denote the infoset that contains h for player i.
A strategy 0z (4,) is probability distribution over the actions A(L:) for each infoset 1, and its probability of a specific action is denoted by a;(44, a). Note that P(4.) i. Let -i denote all the players in the game except player i, 0; E Σ, and 0-i E Σ_ denote player and -''s strategies, respectively. Player i's expect payoff when all the players adhere to the profile (a,, ox-) is denoted by u, -.:). A Nash Equilibrium is a self- enforcing strategy profile o' that no one has an incentive to unilaterally change its strategy. Therefore, Vi E N, u,
2 max,ÇEr; u(o o²,). A best response strategy BR BR( = maxo; ui(d', a-1) is strategy that maximizes player i's own payoff against -i. The exploitability of strategy a; in a two-player rero-sum game is denoted by exp(o:), representing how much payoff player i can lose by changing their strategy from of to oj against their opponent's 's best response strategy. Formally, exp(o,) = u, o²,)) (, B BR(a,)). where o is the Nash Equilibrium strategy.
For two history h, h', we write h C N' if there is an action sequence leading from h to h'. The probability of reaching history h when all players act according to is represented by is player i's contribution history h when players play according to a is denoted by eg (h) = Zez n² (h, 2)222,2, (2), where x" (h, 2) is the probability of reaching terminal node 2 from h. or 0 if h E z does not hold. The value of an infoset ug (1) is the sum of the expected values of all nodes in the infoset, and each one weighted by the player's counterfactual probability.
to the probability. The expect value of player I "
x" (h) I (h', a), and Tद (h)
(F")(r" (f)) The counterfactual best response This can be formally expressed as uf = Σxer (1)
value of (T=: to strategy a-; upon reaching infoset is the best value for player against a-i- (BR( (o.o((o... .).0-)) (I,
This can be defined as wī (7= vi (BR(o_ :):0=:;()) (T) and (a-/TTa) 1/
An imperfect information subgame (hereafter subgame) is set of nodes in game tree, in which information is not divided over infosets. Formally, a subgame S is set of nodes h E H. such that Wh' E H, if 3h E S and h' 3 h. then h S. Moreover, S is closed under infoset: Yh E S, if h e 4 and h E 1, for some player i, then h E S. We define Stop as the set of carliest-raachable nodes in S, then h E Stop if and only if h and h & for all h C h.
3.2 Prior Subgame Solving Methods
In this section, we review the existing methods of subgame solving in imperfect information games. Without loss of generality, we assume that Player (P1) is the responsible party for subgame solving. Within this context, P1 is provided with an initial blueprint strategy and aims to optimize it. During playthrough, Pl reaches an infoset / and carries out subgame solving to refine the blueprint for the remainder of the game.
As an initial step, standard subgame-solving methods enumerate the top node of the subgame whenever player reaches particular information set, allowing them to have direct access to the entire subgame tree. Once the subgame S is constructed, the augmented subgame or gadget game is formed and solved by an appropriate equilibrium finding algorithm. Most subgame solving methods differ mainly in the methodology of constructing the augmented subgame.
The augmented subgame G' in Endgame solving [Ganzfried and Sandholm, 2015) begins with a chance node that leads to all nodes in Stop. The probability of reaching node Shop is proportional to the reach probability of node h in the original game G, provided that the players are playing according to the blueprint o, that is. reaching h with probability Σn's (A] The augmented
(h)
subgame G' is then solved, producing a new strategy of for P1. For the remainder of the game, P1 is expected to replace the blueprint with o..
Subgame resolving [Burch et al. 2014) differs from endgame solving in the structure of augmented subgames. The initial node of the augmented subgame is chance node, with Player 2 (P2)'s alternative node, denoted by hy, added between each node h E Stop and the initial node. Each hr is reached with probability that is in proportion to P2's probability of reaching h, if it tries

---

to do so-that is Tー (h). The set of h is denoted by Sr, with the infoset in S, being determined according to P2's infoset in Stop- P2 is presented with two choices for each alternative node: entering htop or terminating the game and receiving an alternative payoff at Iz I2(htop), which is equal to the counterfactual best response of the blueprint, or uz (5 (I2
Subgame resolving develops a strategy that will not be worse than the blueprint. Conversely, Maxmargin subgame solving [Moravcik al. 2016) seeks to optimize the strategy to ensure that P2 will receive a lower payoff' if it chooses to enter the subgame. Formally, the margin of a strategy of in subgame S is defined as (o u ( up (12). Maxmargin subgame solving hence attempts to find a strategy of that maximizes E M (()))12).
On the other hand, knowledge- limited subgame solving (KLSS) [Zhang and Sandholm 2021 aims to construct a small augmented subgame while providing safety guarantees. KLSS partitions Stop into different knowledge orders based the distance from / in the infoset hypergraph of the subgame. The k-th order knowledge limited subgame solving constructs the subgame using nodes at most units away from the current history h in the original Stop- KLSS takes advantage of the fact that nodes outside the k-th order and their descendants can be discarded if Pl's strategy at these nodes is fixed after the payoff' correctly scaled by nodes inside the (k + 1)-th order. Hence, the Stop of the subgame in the 1tt order KLSS (I-KLSS) can be as small as the player's current infoset and its descendants, which significantly reduces the subgame size.
1
4 Generative Subgame Solving (GS2)
4.1 General GS2 Framework
In Section 3.2 all methods except KLSS perform subgame solving on the entire subgame tree, which intractable for large-size games that are difficult to abstract. KLSS attempts to address the problem by limiting the set Stop to a lower knowledge order, which reduces the subgame size but is still not feasible for games with a large infoset size. For example, in heads-up Texas Hold" em, where one player only holds two cards, the infoset size is more than (52) 1326, making it easy to construct for 1 I-KLSS. On the contrary, in games such as GuanDan, with four players each holding 27 cards at the start, the infoset size can be as large as 1030, Consequently, constructing and storing the corresponding subgame on a computer becomes impractical.
Even if the subgame is somehow constructed, current equilibrium finding [Lanctot et al. 2009 Farina
et al. 2021 algorithm that bound player i's regret by O //T.l
is not guaranteed to converge in real- rime- This is due to the presence of up to 1020 other players' infosets in a single player i's infoset in GuanDan. Furthermore, the subgame cannot be abstracted using the techniques in Texas Hold'em em [Zha et al. 202T]. Thus, simply applying I-KLSS would exceed the time limit, necessitating further reduction in subgames.
Motivated by this, we propose Generative Subgame Solving (GS2) method to reduce the memory and time cost by solving only subgames within a subset of the entire 1 I-KLSS subgame tree. Specifically, let Q = [Q,, Q2,.... Qn) be the set of all subsets of Stop. such that if E Qr. Vh E (h) N E Qr. Here, Q is referred to as a block of Stop- GS2 then introduces a generation function with probability distribution f Ii A 10), where | is the |0/-simplex. Upon reaching infoset 1, GS2 first generates Q ~ f() and then constructs the generative subgame such that, Vh E Q,, h E S and vh h, E
Let (+) be the probability of Qr and w() Er.eq, ((), Q7) be the probability that considered.
Proposition 4.1. Given a strategy 01 in two-player zero-sum game G, reached infoset h, and a generation function f. the refined subgame strategy ou is computed by GS2 with safe subgame solving techniques. Let of be the strategy that plays according to of in subgame S and 0ı elsewhere. Let 5(011h) = max,; wā( [I2 - (ā (I))).) Then the exploitability of the expected strategy (xp(E(o)) is bounded by
exp(E(o')) < cxp(o1) + max - (1-w()))))))))) 2 (I<(h) h).
(1)
hel
5

---

Proposition 4.1 gives the upper bound for GS2 with arbitrary generation functions. d can be regarded as a metric for evaluating the effectiveness of the blueprint strategy, measuring its improvement compared to the worst strategy. While GS2 may increase exploitability, it can efficiently reduce the size of the subgame. balanced games where each unobserved move of other players and chance [Q-1 of the other player's infoset is events have roughly the same size of potential outcomes, only [
considered, thus, the approximate equilibrium can be efficiently computed. Decreasing Q~1 reduces the computational requirement, but it also leads to lower (h) and a potential increase in exploitability, The choice of the generation function f can be trade-off between potential improvement and safety.
Intuitively, Proposition 4.] implies that the new strategies solved by GS2 will be less exploitable histories h E Stop more frequently considered in the sampled Q, (resulting in lower 1 - wh)) or the blueprint does not perform well (leading to lower 101 h)). ). As such, it is suitable to apply GS2 in games with coarse blueprint, unlike previous unsafe subgame solving methods [Ganzfried and Sandholm 2015 Gilpin and Sandholm 2006) that necessitate the blueprint to be close to a Nash equilibrium construct accurate belief distributions. To further enhance safety, one can apply GS2 in large subgames and switch to other safe subgame-solving methods as the subgame size decreases, since GS2 intentionally designed to be effective in handling large subgames.
For large-scale games, sampling block from a non-trivial generation function ʃ is challenging due to the numerous blocks involved. However, randomly generating a single state /: in current infoset I is feasible (e.g., randomly choosing a valid opponent hand in poker), and the block can be obtained by repeating the random generation process and adding all h' that is in the same player 2's infoset of h. This approach is referred to as the random generation function. The generated size & is defined as the size of a randomly generated set of h. When using this function, the upper bound of exploitability increment for the expected strategy will decrease in proportion to the size of the generated block. we have
According to Proposition 4.1
exp(Blo()) s exp(oi) + (1
k
max T L (Z((I(()))(((),)) hET)
(2)
[77]
for the expected strategy E[oi]-
To enhance the safety of GS2, is suggested by Equation (2 to generate as many states as time permits. While increasing the number of states would improve the guarantee, it would also increase the time and resource requirements for solving the subgame. However, the generated size can be controlled and kept relatively small compared to the original subgame. Moreover, techniques such as Abstraction, which traverse the entire infoset, can combined to further reduce the subgame size while maintaining the theoretical guarantee. It is preferable to have larger generated blocks, which require simpler techniques to operate on them. Previous techniques [Ganzfried and Sandholm 2014] that involve comparing all potential outcomes would be time-consuming in large games. In contrast, GS2 reduces the subgame size by considering the counterfactual value of the states according to a diversity-based generation function. In general, a diversity- -bssed generation function generates block Q' such that the maximum earth mover's 's distance between any player 2's infoset and Q' is minimized:
Q' = arg min max dist(I2, Q),
(3)
Q 120,
where dist Q) = EN minzee |u] (a - (1) Let H(I)) be the set of in- foset that is not vastly dissimilar from Bz specifically defined as (12 E Qr\0'1% = arg mag ΣN [u] (()1(112) The counterfactual reach probability of infoset 12 is scaled up by ΣleEH(g) (T2).. In two-player zero-sum games, it is equal to finding subset such that the alternative values of infosets are likely to be uniformly distributed in range [mins,co. | max (2(01 which can be efficiently obtained through techniques such dynamic programming.
Intuitively, the diversity-based generation function generates a block that is the most "diverse" and is able to encompass a wide range of situations (including unobserved others' or chance behaviors) with a small number of infosets. The pseudo-code for GS2 utilizing the diversity- generation function is presented in Appendix C.8

---

2
l
Continue as the original game
Part of the Liar's Dice game
121
Continue as in the original game
Continue in the original game
(b) 1-KLSS subgame tree of infoset IT
(c) GS2 subgame tree of infoset 41.
Figure 1: Example of GS2 in Liar's Dice. The white node is a chance node, representing exogenous events. Nodes are colored in blue if the acting player player and red for player (a) Part of the Liar's ' Dice game tree. higj is the history that the two players' dice landed on i and respectively. For simplicity, descendants of h4s that would not be changed in the standard implementation of 1-KLSS and GS2 are omitted.
(b) The 1-KLSS subgame tree of infoset I,- (c) The GS2 subgame tree of infoset I, GS2 only constructs the subgame with a subset of I, The subset shown is for illustration purposes and would be generated by generation function in practice.
4.2 Example of How GS2 Works
To further clarify the concept of GS2, we present a simple example. Figure iillustatee an example of GS2 applied in Liar's Dice with 8-sided dice. In this example, (the white node) is the chance node, representing exogenous events. Nodes are colored in blue if the acting player player I and red for player 2. Figure ((a) shows a portion of the Liar's Dice game tree. Fach player dice at the beginning. For simplicity, the remainder of the game omitted and replaced by the gray area, as the nodes rooted at each history h will not be altered in the subgame-solving process.
player wishes refine its strategy after determining that infoset has been reached, the subgame constructed by I-KLSS is shown in Figure (bb) The chance nodes are redundant since they only have one chance outcome but are retained for consistency. ú, is the scaled alternative value of
(22 Everyti =23(h"
(0 IZ (h1m)) for player I's blueprint 01. Formally, 05.
(21()
The payoff for player 2 is then subtracted by a r. upon reaching the corresponding node. Additional payoffs should also be taken into consideration, accounting for the omitted subtree.
GS2 further reduces the subgame size, as shown in Figure (Cc) It only constructs subgame for subset of J, which generated by a diversity- the computational efficiency of the subgame solving in large games but also refines the blueprint by selectively focusing on the most typical portions of the game tree.
generation function. This not only increases
Experiments
5.1 Evaluation on Research Games
To evaluate the practical performance GS2, experiments are conducted on range commonly used research games with varying infoset sizes.
7

---

3-cank Lodie
Lia's Dicee with sided
T with T-dleed diee.
03-
Rarpial
Karpie
Unude
Utadd
K1S8 onieaia
032
Unaat:
and
Explonssttey
9.34
013441
0524
0:14
05-
038
Rwd
K-3
R=4
K
(a)
(b)
(c)
Goofspeel, tandons order roual.
10-ord Goofapiel ascending order cound.
12.aard Goolipidl axcending
L-LLSS-eatinted
4.5
15524
632 D
KESS leawe
0.20
I K1.8 licile)
11554
655D
9.54
(G23
0.20
046
0.8
0.2
(d)
(c)
(f)
Figure 2: Exploitability of GS2 with random generation function (GS2-R) and diversity generation function (GS2-D) in different games (Lower is better). GS2 and refine the strategy in 3 seconds, while I-KLSSS-unimited and Unsafe subgame solving method are not. (a) 3-rank limit Ledue poker. (b) Liar's ' Dice with 6-sided dice. (c) Liar's Dice with 7-sided dice. (d) 5-card Goofspiel, random order with rounds. (e) 10-card Goofspiel, ascending order with 3 rounds. (f) 12-card Goofspiel, ascending order with 3 rounds.
are required to
Implementation details. All games are implemented using the open-source library Open- Spiel (Lanctot et al., [019]. each game, a blueprint first computed via the CFR algorithm, after which GS2 is applied at each infoset after both players have taken one action to refine the blueprint. The subgame is solved in a nested fashion, utilizing Maxmargin solving with linear programming whenever feasible, and otherwise employing MCCFR (Lanctot et al. 2009]] The unsafe subgame solving method is implemented based on Ganzfried and Sandholm [2015], Brown and Sandholm [2017]. The computation time is limited for 1-LLSS [Zhang and Sandholm 2021| and GS2. In these methods, the player is allotted a maximum of 3 seconds to compute an approximate Nash Equilibrium after constructing a subgame. In order to provide comprehensive evaluation of GS2's performance, we also present the results of 1-KLSS and unsafe subgame solving, where there are time constraints imposed the computation. It is important to note that GS2 is not expected to surpass the performance of these two methods, as obtaining an exact Nash Equilibrium may require significantly more time. For instance, when solving the subgame of Liar's Dice with 7 dice sides, the computation time for the strategy in unsafe subgame solving can reach up to 122 seconds, and 41 seconds for I-KLSS, rendering them impractical for real-time decision-making In contrast, GS2 with k = 3 only necessitates 10 seconds of computation time at the same infoset 2 showcasing its efficiency.
Results. The effect of varying the value k (i.e., the number of other player's infosets in the generated block) in the diversity-based generation function is evaluated, and the exploitability of blueprints and refined strategies is presented in Figure 2 Experimental results demonstrate that GS2 is capable of effectively reducing exploitability in practice for coarse blueprint in limited computation time, despite the absence of safety guarantees. As the size of the game increases, GS2 with diversity generation exhibits superior performance compared evident from the results presented in Figure 2(c) and Figure 2 However, in the case of 10-card Goofspiel and 12-card Goofspiel, where the infoset size is extremely large, GS2 with random generation is comparatively inferior to that of other methods. This discrepancy arises due to the inherent limitation of randomly generating a block, as fails to yield a desirable subgame within the confines of an infoset size reaching up to 1110. Consequently, this inability to generate good
I-KLSS with limited computation time. as
"The experiment was conducted on Intel(R) Xeon(R) Gold 6242R CPU @ 3.10GHz
8

---

subgame leads to an increase in exploitability. For 5-card Goofspiel and Liar's s Dice, GS2 with diversity generation performs closely to I-KLSS-unlimited but with significantly less computation time, showing the effectiveness of GS2. Additionally, the results suggest that as k increases, the exploitability of the refined strategy decreases, which aligns with previous theoretical analysis.
For other baselines, the unsafe subgame solving demonstrates excellent performance in 3-rank limit Ledue poker, but it performs inferior Liar's Dice due the lack of a safety guarantee. While I-KLSS without time limits exhibits the best performance in most games, it requires significantly more computation time than GS2, as discussed previously.
5.2 Evaluation on GuanDan
We use the techniques in Appendix to create an agent for the game of GuanDan. The choice to test GS2 on GuanDan is driven by the game's complexity, which surpasses that of other games such as DouDizhu, and the availability of several benchmark agents due to a GuanDan Al competition. GS2 is tested against the two champions of the competition to evaluate its performance:
The first champion is rule-based agent and is tested against top human professionals. Despite never having won in a GuanDan tournament, the agent has achieved victory for certain decks in the tournament and has proven to be challenging for experts who not familiar with it.
The second champion a DMC [Zha et al. 2021 agent with warm surm-starting and post- processing that has 90% winning percentage against the first champion in the GuanDan tournament. We believe it to be an expert-level agent, although it has not been tested against human experts.
Implementation details. The state-action value function of GuanDan is created by DMC and the
subgame is further simplified as outlined in C.2 The approximation is implemented based on the concept of not just sampling from opponent infosets but also within the infoset itself to manage complexity. This approach is like applying a specific generation function to the opponent's infoset. leads to a conservative strategy refinement by assuming opponents are aware of the player's exact private information. Such an assumption prevents a drastic rise in exploitability at the present infoset. This method is influenced by patterns observed in the game of GuanDan. In this game, as actions unfold, uncertainty diminishes, thus human players are expected to guess the others' cards, especially near the end of the game, which is crucial for expert players. Therefore, considering the worst case that the opponents know the player's s cards would be practical. Even though this idea seems somewhat domain-specific,
believe it is also applicable to similar games.
During the entire game, only one player performs subgame solving, while the teammate continues to play according to the state-action value function. In other words, the teammate will select the action with the highest value among all legal actions. The opponent team consists of two identical agents who do not communicate during the game. To better evaluate performance, we conduct tournaments with a fixed game level. each tournament, deck is played four times to minimize variance. The player who performs GS2 rotates their seat the next player after each round of play. At the end of each game, players will receive a score according to the order in which the player and its teammate empty their hand, which is equal to the value of levels they would prompt in the original GuanDan game for the winning team and the negative value for the losing team. A more detailed description of Guan is given in Appendix B The tournament is then repeated 100 times and the average score of GS2 in each position is calculated.
Results. We first present the results when playing against the second champion. Different settings of i are applied in the tournament. Despite the remarkably small value of l relative to the size of the infoset, the results shown in Figure indicate that the application of GS2 leads a significant performance gain. It also shows that as more states are generated by GS2, the better its performance becomes. The results of GS2 against the first champion are given in Figure first champion, GS2 has less improvement in the average score. We believe that this is attributed to the outstanding performance of the strategy constructed by the value function, which results in the improvement not being fully reflected in the average score. Overall, the experiment results suggest that GS2 able to improve the performance of a given blueprint in large games with desirable subgame sizes.
Compared to the

---

mloageine
122
1.12
Posittin
Position
Position
P
Position
Positiin
Position
Pesiiiin
(a) Performance against the second champion agent.
Performance against the first champion agent.
Figure 3: The avarage score of GS2 against two prior agents at each position in GuanDan (Higher is better). The score of the blueprint (blue) gives the baseline value that agents could achieve without subgame solving at each position.
6 Conclusion and Future Work
We propose novel progame--ollingg method, named GS2, which is designed to address the challenges posed by games with imperfect information and large infoset sizes. GS2 only constructs partial subgame tree, thereby reducing the memory and time costs associated with conventional subgame solving. Our method able to construct robust strategies for large games with unmanageable infoset sizes. We theoretically analyze the exploitability bound for GS2 and propose diversity- -aaeed generation function to mitigate the issue of unsafeness. Through experimental evaluations in research games and a complex poker game game-GuanDDan GuanDan, we demonstrate that GS2 indeed decreases exploitability and improves the performance of the given blueprint in practice.
While GS2 shows promising performance with a simple diversity- generation function, it is that further research needed address the limitations of the method, particularly when alternative values are not adequate for describing the state. Additionally, it remains an open question to whether safe generation function exists that can further expand the applicability of GS2.
important
7 Acknowledgement
We thank the anonymous reviewers for their constructive comments. This work was supported in part by Science and Technology Innovation 2030 New Generation Artificial Intelligence Major
201.2000001A0100055 the National Natural Science Foundation of China(No. 62192783, No.621061111 (No.BE2021028) Jiangsu Natural Science Foundation (BK20221441) Jiangsu Provincial Double- Innovation Doctor Program (ISSCBS2021002)) 10021), and part by Collaborative Innovation Center of Novel Software Technology and Industrialization.
No.622761427 Primary Research & Development Plan of Jiangsu Province
References
Noam Brown and Tuomas Sandholm. Safe and nested subgame solving for imperfecttinformation games. Advances in neural information processing systems, 30:689-699, 2017.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418-444, 2018.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885-890, 2019.
Noam Brown and Tuomas W Sandholm. Simultaneous abstraction and equilibrium finding in games. 2015.
Noam Brown, Sam Ganzfried, and Tuomas Sandholm. Hierarchical abstraction, distributed equilib- rium computation, and post-procsssing, with application to a champion no-limit texas hold' em
10

---

agent. In Proceedings of the 2015 International Conference on Autonoooou Agents and Multiagent Systems, pages 7-15, 2015.
Noam Brown, Tuomas Sandholm, and Brandon Amos.
Depth-limited solving for imperfect- information games. Advances in neural information processing systems, 31, 2018.
Neil Burch, Michael Johanson, and Michael Bowling. Solving imperfect information games using decomposition. In /wenty-eighth AAAI conference on artificial intelligence, 2014.
Murray Campbell, A Joseph Hoane Jr, and Feng-hsiung Hsu. Deep blue. Artificial intelligence, 134 (1-2):57-83, 2002.
Farina, Kroer, al. Better regularization for sequential decision spaces fast convergence rates for nash, correlated, and team equilibria. In EC'21: Proceedings of the 22nd ACM Conference on Economics and Computation, 2021.
Sam Ganzfried and Tuomas Sandholm. Potential-aware imperfect-recall abstraction with earth mover's distance in imperfect- inffrecaionno games. In Proceedings of the AAAI Conference Artificial Intelligence, volume 28, 2014.
Sam Ganzfried and Tuomas Sandholm. Endgame solving in large imperfecttinfformaiin games, In Proceedings of the 2015 International Conference Autonomous Agents and Multiagent Systems, pages 37-45, 2015.
Andrew Gilpin and Tuomas Sandholm. A texas hold' em poker player based on automated abstraction and real-time equilibrium computation. In Proceedings of the fifth international joint conference on Autonomous agents and mulliagent systems, pages 1453-1454, 2006.
Hengyuan Hu, Adam Lerer, Noam Brown, and Jakob Foerster. Learned belief search: Efficiently improving policies in partially observable settings. arXiv preprint
2021.
Qiqi Jiang, Kuangzheng Li, Boyao Du, Hao Chen, and Hai Fang. Deltadou: Expert-level doudizhu ai through self-play. In IJCAI, pages 1265-1271, 2019.
Mare Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling. Monte carlo sampling for regret minimization in extensive games. Advances in neural information processing systems, 22. 2009.
Marc Lanctot, Edward Lockhart, bean-Baptiste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafiei. et al. Openspiel: A framework for reinforcement learning in games. arXiv preprint arXiv:1908.09444 2019.
Adam Lerer, Hengyuan Hu, Jakob Foerster, and Noam Brown. Improving policies via search in cooperative partially observable games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7187-7194, 2020.
Junjie Li, Sotetsu Koyamada, Qiwei Ye, Guoqing Liu, Chao Wang, Ruihan Yang, Li Zhao, Tao Qin, Tie Yan Liu, and Hsiao- Wuen Hon. Suphx: Mastering mahjong with deep reinforcement learning. arXiv preprint arXiv:2003. 12222003..39000 13590, 2020.
Viliam Lisy. Mare Lanctot, and Michael H Bowling. Online monte carlo counterfactual regret minimization for search in imperfect information games. In Proceedings of the 2015 International Conference Autonomous Agents and Multiagent Systems, pages 27-36, 2015.
Yudong Lu, Jian Zhao, Youpeng Zhao, Wengang Zhou, and Houqiang Li. Danzero: Mastering guandan game with reinforcement learning. arXiv preprint 10.iv:22 17087, 2022.
Matej Moravcik, Martin Schmid, Karel Ha, Milan Hladik, and Stephen Gaukrodger. Refining subgames in large imperfect information games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-51) 2017.

---

Tuomas Sandholm. Abstraction for solving large incomplete incomplete-informatton games. In Twenty-Ninth AAAI Conference on Artificial Intelligence, pages 4127-4131, 2015.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwisser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 529(7587):484 489, 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, 55017676):354-399 2017.
Michal Sustr, Vojtëch Kovařík, and Viliam Lisý. Monte carlo continual resolving for online strategy computation in imperfect information games. In Proceedings of the 18th International Conference on Autonomous Agents and MulliAgent Systems, pages 224-232, 2019.
Yuandong Tian, Qucheng Gong, and Yu Jiang. Joint policy search for multi-agent collaboration with imperfect information. Advances in Neural Information Processing Systems, 33:19931-19944 2020.
Daochen Zha, Jingru Xie, Wenye Ma, Sheng Zhang, Xiangru Lian, Xia Hu, and Ji Liu. Douzero: Mastering doudizhu with self-play deep reinforcement learning. In International Conference Machine Learning, pages 12333-12344, PMLR, 2021.
Brian Zhang and Tuomas Sandholm. Subgame solving without common knowledge. Advances in Neural Information Processing Systems, 14:23993-24004, 2021.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. Advances in neural information processing systems, 20, 2007.
12


Reviews:
[{"review_id": "Gi8cjjaY2C", "reviewer": "Reviewer_EqAE", "summary": "The paper presents a generative subgame solving framework that can scale to games with a large amount of hidden information. One of the key ideas behind the generative framework is to prioritize exploration based on diversity. The paper evaluates on small-sized tabular games and a large poker-like game called GuanDan.", "questions": "Please see above.", "limitations": "The authors adequately addressed the limitations. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Overall, I have a positive opinion of the paper, with a few reservations (see below). In terms of strengths, I appreciated experiments on a real game. The structure and organization is also appropriate, with only minor clarity issues. While the method appears to be mostly a heuristic, it seems to be working pretty well in practice, and for that reason it seems worthy of discussion at the conference.", "weaknesses": "I find that the paper could be improved by expanding the discussion along the following directions:\n- I think more should be done to ablate the choice of diversity-based generating function. The method proposed fundamentally boils down to sampling possible compatible histories in the infoset by means of a \"diversity-based generation function\". Many choices of prioritization could be imagined, and it would be important to have some form of data points about what tends to work and what doesn't. Also, data supporting the need of using prioritization as opposed to not prioritizing as all would be nice to have. \n- The discussion around KLSS as introduced by Zhang and Sandholm (L37) seems to suggest that it is a safe method, as it is said \"This approach enables the safe refinement of strategies\". However, KLSS is typically used in an unsafe way in practice.\n\nI also think that the paper should discuss the following relevant related literature:\n- Approaches used in the game of Hanabi. While common-interest in nature, the techniques that have been proposed in Hanabi have an overlap with the material of the paper. For example, the work on Learned Belief Search should be discussed.\n- Approaches used in the game of Bridge, such as joint policy search, also seem relevant. \n\nOther comments:\n- I feel like calling the games of section 5.1 \"medium\" is rather generous. The games only have a few hundreds sequences per player and can, for example, be solved exactly using the simplex algorithm via the sequence-form.\n- L113, \"one cannot assume rationality of the chance player\". I found this obscure.\n\nIn conclusion, while I find the underlying idea rather straightforward, I think the strengths outweigh the weaknesses despite the limited evaluation. However, I think the paper would substantially benefit from adding more data regarding the choice of prioritization functions, and expanding the discussion regarding related literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable and insightful comments. \n\n- **Regarding the choice of functions.** \n\n  We appreciate your insight on the importance of thoroughly ablating the choice of our diversity-based generation function. In the current study, our choice for the diversity-based generation function was driven by both theoretical considerations and empirical performance in our preliminary experiments. However, we understand the importance of showcasing a more exhaustive comparison. To address this comment, we have included a more detailed comparative analysis in the supplementary material attached to our global response. \n\n  The experiment is conducted in Leduc poker. In this evaluation, we employ all feasible deterministic generations, as opposed to a probability distribution, for each individual infoset right after the cards are dealt. The data points, located at $(x, y, z)$, correspond to instances of generated subgame with the opponent private cards set is $\\{x,y,z\\}$. The results show that the diversity generation function could perform well at all the player's infoset.\n\n- **Regarding the discussion of KLSS.** \n\n  Thank you for the observation. To clarify, we will revise the statement to read: \"This approach can enable safe strategy refinement under specific conditions of usage\" in the updated version.\n\n- **Regarding the relevant related literature.** \n\n  Thank you for highlighting the relevance of methods from the games of Hanabi and Bridge. In subsequent versions of our paper, we will expand upon this in the related work section:\n\n  Search algorithms are also applied for obtaining better joint policy witin teammates in collaborative games such as Hanabi [1-2] and the bidding phases of contract Bridge [3].  For example, SPARTA [1] utilizes exact belief update for single agent search and multi-agent search and retrospective belief updates for multi-agent search to handle the large belief range. Subsequently, the strategy is improved through Monte Carlo rollouts. On the other hand, instead of maintaining an explicit belief distribution in single agent search, Learned Belief Search [2] method uses a learned belief model to sample states from the belief distribution, allowing for the application in games with large belief space. Rather than simply improve the strategy via rollouts, Joint Policy Search [3] method first decompose the global changes of the game value into local changes at each infoset, and then iteratively improve the strategy based on the decomposition.Although these approaches primarily focus on improving strategy in collaborative settings and could not be directly used in games with adversaries, the underlying idea could be helpful when developing new technique that conducts search within teammates in games like GuanDan. \n\n- **Regarding the word \"medium\".** \n\n  Thank you for pointing out the potential mischaracterization. We utilized the term \"medium\" based on the terminology from KLSS [Zhang and Sandholm]. We will revise the term to \"research games\" or \"simple games\" in the updated version of our paper.\n\n- **Regarding the comments on L113.** \n\n  Thank you for pointing out the ambiguity. In L113, when we mention \"rationality of a player\", we refer to the assumption made in some prior techniques (e.g., the iteratively deepening method used in KLSS) that the opponent will avoid empirically suboptimal actions. This allows one to prune parts of the game tree based on this assumption. However, since a chance player operates under a fixed probability distribution, this assumption of rationality is not applicable.Thus, using the iteratively deepening approach in this context would be unsound. We will elaborate on this distinction in the revised version for clarity.\n\n[1] Lerer A, Hu H, Foerster J, et al. Improving policies via search in cooperative partially observable games[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2020, 34(05): 7187-7194.\n\n[2] Hu H, Lerer A, Brown N, et al. Learned belief search: Efficiently improving policies in partially observable settings[J]. arXiv preprint arXiv:2106.09086, 2021.\n\n[3] Tian Y, Gong Q, Jiang Y. Joint policy search for multi-agent collaboration with imperfect information[J]. Advances in Neural Information Processing Systems, 2020, 33: 19931-19942."}, {"review_id": "5iFo02kfZv", "reviewer": "Reviewer_D79X", "summary": "The contributions of the paper are twofold:\n- On the theoretical hand, the paper introduces a bound on the total increase in exploitability when refining the strategy in a subgame that consider only some of the possible infosets of the adversary in a stochastic way. \n\t- This bound is based on considering that the exploitability of the refined strategy may increase (in the worst case) due to updating in the worst possible way the strategy for some of the opponent's infosets ($\\delta$ term in the bound). This extra exploitability is then weighted for the probability of not sampling such an adversary infoset ($1-\\omega$) term and for the probability of having reached that infoset in game ($\\pi$ term)\n- This theoretical bound is then used to design of the *Generative Subgame Solving (GS2)* algorithm. GS2 samples some of the nodes $h$ in the current infoset of the refining player. To sample the different $h$ that will belong to the subgame that will be refined, a *diversity-based generation function* is used. This function is an heuristics that selects the histories such that the distribution of counterfactual values at the infosets of the opponent at the root of the GS2 subgame are representative of the distribution that there would have been in the 1-KLSS. This allows to avoid to refine the strategy considering too pessimistic or too optimistic \"cuts\" of the original subgame, even if there is no formal proof that this reduces exploitability", "questions": "Other then asking the authors to share their view/clarify the weakness I listed in the previous section, I add the following questions to clarify specific points of the paper:\n- KLSS's explanation (Line 189-192) is unclear. I suggest just keep formal definition which is fine (and not the partially repeated phase at line 189). Also the $k$-th order knowledge limited subgame starts from the *infoset $I$* of the current player and not from the *current history $h$* as indicated.\n- I'd like to ask for a confirmation: is $\\pi^{\\sigma'_1}_{-2}(\\mathcal I_2(h)) = \\pi^{\\sigma_1}_{-2}(\\mathcal I_2(h)) \\ \\forall h \\in S_{top}$?\n\nMinor typos:\n- Line 255: is there any connection that was intended between controlling the $k$ parameter and the possible use of abstraction techniques? In my understanding, they are two techniques that can be applied independently. If this is the case, \"Therfore\" should me substituted with \"Moreover\" or a synonym thereof.", "limitations": "N/A", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Interesting and novel technical approach, which allows to interpolate between the unsafe solving from Ganzfried and Sandholm to the safe approach of 1-KLSS\n- Formalism used is in line with previous works in the field\n- Both medium and larger scale experiments. This allows to verify both the correctness and the scalability of the proposed approach\n- clear structure of the paper and clear descriptions of the adopted solutions\n- an example of how the technique would be applied on a game is presented, further clarifying the concepts", "weaknesses": "- Some of the claims presented by the paper are misleading or poorly justified:\n\t- The bound presented in Proposition 4.1 bounds the possible increase in exploitability from the blueprint to the refined strategy as the worst case scenario in which the refined strategy is maximally losing in case the opponent decides to switch to play only to that infoset.\n\t- Lines 235-240 claim that GS2 is more suitable for situations in which $\\delta$ is already low, differently to traditional unsafe solving techniques. This means that the blueprint is of low quality, and therefore GS2 cannot make things too much worse in terms of exploitability wrt the original (already bad) blueprint. I don't get why such an argument would not apply as it to any other subgame solving technique\n\t- Line 290-291: \"[GS2] also refines the blueprint by selectively focusing on the most relevant portions of the game tree\". The introduced diversity generated function only considers the adversary's infosets as counterfactual values. There is no clear connection to how the sampled histories should be the **most relevant** from a strategy refinement perspective\n- The large scale experimental setting presented feels disconnected from the techniques presented by the paper:\n\t- As indicated in Appendix C.2: *Although standard GS2 need to generate the full second-order knowledge infosets, we only consider the nodes in the first-order knowledge infoset.* I interpreted this as the fact that the set of histories $\\{h \\in S_{top}: \\exists I_2: h \\in I_2 \\land  \\exists h' \\in I_1, I_2\\}$ is not added to the constructed subgame. My opinion is that this approximation is really important to the point that the resulting algorithm should be clearly distinguished from GS2 as presented in the previous parts of the paper. This because while GS2 is a \"partial cut\" version of 1-KLSS, not adding all nodes in $I_2$ makes the technique possibly much more unsafe, and more similar to a \"partial cut\" version of the unsafe abstraction techniques from Ganzfried and Sandholm.\n- GS2 is an unsafe solving technique: no cases in which such an unsafeness becomes evident are presented, leaving open the question of when such a technique may fail", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. We sincerely appreciate your valuable feedback. Here are our responses.\n\n- **Regarding the exploitability bound.**\n\n  Thank you for pointing out this aspect. Indeed, the bound presented is specific to the infoset. The reason for this is rooted in the fact that GS2 is constructed upon the KLSS framework. Consequently, obtaining an exploitability bound is not as straightforward as with conventional subgame solving techniques. We recognize that the proposition can be extended to strategies where GS2 is applied to disjoint subgames; in such cases, the additional term would vary based on the maximum across these subgames. We will ensure that this clarification is included in the revision of the paper.\n\n- **Regarding L235-240.**\n\n  Thank you for raising this concern. In many unsafe subgame solving techniques, like endgame solving, the assumption is that the opponent blueprint is close to equilibrium; deviations from this can hinder strategy refinement. Thus, the coefficient $1-\\omega$ in the exploitation bound will increase up to 1. That's why we say GS2 is more suitable than unsafe solving.\n\n- **Regarding Line 290-291**\n\n  Thanks for the great point. Our use of the term \"relevant\" was imprecise. What we intended to convey is that the GS2 framework focuses on portions of the game tree that are \"typical\" or representative based on the adversary's infosets as counterfactual values. We appreciate the clarification and will correct this in the revision to more accurately reflect our approach.\n\n- **Regarding the implementation in Appendix C.**\n\n  We appreciate the observation. The approximation is implemented based on the concept of not just sampling from opponent infosets but also within the infoset itself to manage complexity. This approach is like applying a specific generation function to the opponent's infoset. It leads to a conservative strategy refinement by assuming opponents are aware of the player's exact private information. Such an assumption prevents a drastic rise in exploitability at the present infoset. \n\n  This method is influenced by patterns observed in the game of GuanDan. In this game, as actions unfold, uncertainty diminishes,  thus human players are expected to guess the others' cards especially near the end of the game, which is crucial for expert players. Therefore, considering the worst case that the opponents knows the player's cards would be practical. Even though this idea seems somewhat domain-specific, we believe it is also applicable to similiar games.\n\n- **Regarding the unsafeness.**\n\n  GS2's safety is contingent upon the quality of the generation function used. Specifically, if the generation function were to primarily target situations where opponents face challenges, the refinement could become overly optimistic, making it susceptible to exploitation.\n\n- **Regarding Question 1**. \n\n  Thanks for your suggestions. We will correct it in the later version.\n\n- **Regarding Question 2**.\n\n  If $\\sigma_1$ and $\\sigma_1'$ are the same outside the subgame $S$, the answer is yes.\n\n- **Regarding the typos.**\n\n  Thanks for the advise. We will make the corrections."}, {"review_id": "scSL8PxC0s", "reviewer": "Reviewer_hSoE", "summary": "The paper proposes a novel subgame resolving algorithm in Extensive-Form games called GS2, which will only sample a portion of subgames and dramatically reduce computation complexity.", "questions": "Listed in weaknesses.", "limitations": "Yes the authors have addressed the limitations adequately.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The new subgame resolving algorithm GS2 has a theoretical guarantee, as all previous work did.\n- The paper has sufficient experiments and also gets great performance in the Guandan game.", "weaknesses": "No code was released. Since subgame refinement is really an engineering topic, if possible, I think releasing the code will greatly benefit the whole community to do improvements in the future. Otherwise it will be really hard to reproduce the work since there are too many details in implementing algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your recognition of the merits of our work. In response to your concern, we are in the process of refining our code to ensure its clarity and ease of use. Once finalized, we commit to making it publicly accessible."}, {"review_id": "58GadzjHjs", "reviewer": "Reviewer_gWJJ", "summary": "The paper proposes GS2, a method to overcome the problem of large information states in subgame solving in imperfect-information games. Theoretical results and experimental evaluation on GuanDan are presented, with impressive results.", "questions": "1. (L522) \"Although standard GS2 need to generate the full second-order knowledge infosets, we only consider the nodes in the first-order knowledge infoset\" Does this imply that, in the subgame, the opponent essentially has complete information about the history at the root of the subgame? \n    * If so, this seems like a fairly strong simplification, and I am fairly surprised at the strong practical performance. Why do you believe that GuanDan has such a structure that this simplification does not completely destroy performance?\n    * If not, I assume you will have to incorporate second-order nodes *somewhere*. How, precisely is that done?\n1. (Sec C.3) What depth and branching factor limits are used in the GuanDan experiments?\n1. In the tabular experiments, it appears that the performance of GS2-R and GS2-D get closer to each other as $k$ increases. I would be interested to see experiments with slightly larger $k$, perhaps $k=5$ or $k=10$, to see if this effect continues. Along these lines, how computationally expensive is it in GuanDan to use a larger $k$? That is, if you were to set $k=10$ (say) in GuanDan, would the time taken in subgame solving be then too long to use in realtime? ", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main idea of the paper, to use a diversity function to filter the set of states, is nice. The practical results are particularly impressive: experiments on medium-sized games seem to clearly indicate that the diversity function has a positive impact, and the experiments on GuanDan seem to suggest that the bot is state-of-the-art.", "weaknesses": "I was a reviewer on an earlier version of this paper, during which time I had a robust discussion with the paper authors. The present submission is much improved and has addressed most of the concerns I had with the previous version. I have only a few lingering questions and minor concerns from that discussion, mostly concerning the experiments; see below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your appreciation and valuable comments/suggestions for our works. We hope these response would address the lingering concerns.\n\n* **Regarding  Question 1**. \n\n  Thank you for your insights. In GuanDan, we indeed operate under the assumption that opponents possess complete information. This stems from a sampling across the opponent's infoset, functioning as a specialized sampling approach. The rationale is based on the observation that, as GuanDan progresses, actions reduce game uncertainty. Hence, adept players often anticipate other players' cards -- a crucial skill for proficient players, especially as the endgame approaches.\n\n  It's worth noting that while this simplification might yield a more conservative strategy at the beginning, the subgame is solved in a depth-limited manner. Consequently, leaf node values are derived from a blueprint devoid of complete information. This ensures that opponents cannot excessively capitalize on having complete information, thus mitigating the potential negative impact of our simplification.\n\n* **Regarding Question 2**.\n\n  Thank you for the question.\n\n  \\- Branch Factor: We set the branch factor to 2 for each action type. Actions in GuanDan are divided into several types, as detailed in the \"Card Type\" section of Appendix B. For each infoset, the player is allowed to choose from all types in its hand if no one plays any cards after the player's last action. Otherwise, only the same card types, \"Pass (not playing any cards)\" or \"Bomb (a special cards type)\" can be played. Thus the numbers of actions after pruning may not be the same for each infoset.\n\n  \\- Depth Limit: The default depth limit is set at 10, inclusive of the teammate's node which possesses only a single legal action. However, if the combined card count for all opponents' hands exceeds 27, the depth limit is reduced to 8.\n\n* **Regarding Question 3**.\n\n  Thank you for your insightful question.\n\n  As $k$ grows larger, the sets generated by GS2-R are more likely to be diverse in small infoset, thus yielding similar performance outcomes when contrasted with those generated by GS2-D. As you suggested, we conduct experiments with $k=8$ and $k=10$ in Goofspiel. The results for these additional experiments can be found in Section 2 of the global response PDF. The results shows the performance of GS2-D and GS2-R would getting closer as $k$ increasing. It also shows that the exploitability of the resulting strategy will increase due to the time limit, showcasing the necessity of reducing subgame size.\n\n  Regarding computational complexity in GuanDan: it is indeed a primary concern. In our experiments, we employed two Intel(R) Xeon(R) Gold 6242R CPUs @ 3.10GHz, using the multi-process version of MCCFR. The 30s time limit for GuanDan is greater than that of Texas Holdem, allowing for additional iterations. With these specifications, GS2 is efficient enough for k=10. However, for substantially larger $k$ values, like 40 or 50, convergence becomes problematic in scenarios with expansive branching. Specifically, we noticed minimal improvement against the two baselines when $k=40$ or $50$, compared to the performance when $k=30$. We attribute this to the linear growth in the number of opponent infosets as $k$ increases, causing the strategy to stall before surpassing the performance of the smaller $k$"}]

Author rebuttal:
### **Global response**

Dear Reviewers,

Thank you very much again for your helpful comments. We appreciate your recognization of our work and would like to engage with you in our responses to your questions/comments. If you have any questions about our work or our response, we would be happy to discuss them further.

Best Regards,

the Authors.

Meta-review: The paper proposes a novel sub-game solver that can scale to extensive form games with a large amount of hidden information.
This method proposed in the paper is sound and very effective in practice, as witnessed by its performance in a real game.
The reviewers raised some issues the authors properly addressed in their rebuttals, thus making the reviewers converge on a consensus about acceptance.
The authors need to consider the reviewers' suggestions while preparing the final version of their paper.
Decision: Accept (poster)