Equilibrium Refinements Improve Subgame Solving in Imperfect-Information Games

1 Introduction

Settings where parties such as people, companies, or nations interact are ubiquitous, and game theory provides the solution concepts of how the parties should act rationally. It is therefore of significant real-world importance to be able to compute (approximate) game-theoretic solutions to large games. Recreational games have often served as computational benchmarks for this purpose.

In perfect-information games, real-time subgame solving techniques have been the core of game-solving algorithms since the beginning of AI. Algorithms like minimax, alphabeta search, or Monte Carlo tree search, explore the subgame tree from the single current state of the game forward [Shoham and Leyton-Brown, 2008; Silver et al., 2018].

However, most real-world settings are imperfectinformation games. There are multiple real states consistent with a single decision point, and changing a part of an agent's strategy typically changes what that agent's optimal strategy is later and earlier in the game. Thus, a subgame cannot be solved based solely on information from that subgame.

Therefore, unlike in perfect-information games where subgame solving was a core technique from the outset, imperfect-information games where approached as a monolithic whole for the longest time. Real-time subgame solving started relatively recently [Gilpin and Sandholm, 2006]. Since then, a host of better and better subgame solving techniques have been developed [Gilpin and Sandholm, 2007; Burch et al., 2014; Ganzfried and Sandholm, 2015; Moravˇc´ık et al., 2016; Moravˇc´ık et al., 2017; Brown and Sandholm, 2017; Brown and Sandholm, 2018; Brown and Sandholm, 2019; Zhang and Sandholm, 2021; Kovaˇr´ık et al., 2023; Schmid et al., 2023; Zhang and Sandholm, 2026]. In fact, subgame solving has made the central difference in achieving superhuman play in games such as two-player no-limit Texas hold'em poker [Brown and Sandholm, 2018], multiplayer no-limit Texas hold'em [Brown and Sandholm, 2019], and dark chess (aka. Fog-of-War chess) [Zhang and Sandholm, 2026].

A common approach is to compute a coarse blueprint strategy for each agent for the entire game, and then to conduct subgame solving on the fly to refine the blueprint strategy. Gadget games were developed to compute robust strategies in the subgames. These are modifications of the sub-

egy it could have played in the past. The resulting optimal strategy of the player in such a gadget game is robust against any past strategy of the opponent [Burch et al., 2014; Moravˇc´ık et al., 2016; Brown and Sandholm, 2017]. However, existing gadget constructions, such as resolving and max-margin, only ensure that the player's strategy, in the worst case, is no worse than the blueprint. As a result, if the blueprint is poor, all of these methods may yield poor results.

We make the following contributions. 1. We show that different equilibria, which all yield the same value in the gadget game, have vastly different performance (exploitability) in the full game, when combined with the blueprint. We introduce a weaker notion of sequential equilibrium, gadget game sequential equilibrium, which is easier to compute, and propose that gadget games should be solved according to this concept. 2. We disprove the widely held belief that max-margin gadget games are strictly superior to resolving gadget games. This provides a new understanding of some prior works that have used the resolving gadget game for subgame solving rather than max-margin [Moravˇc´ık et al., 2017; Zhang and Sandholm, 2026]. 3. We introduce efficient modifications to the sequence-form linear program (SQF) and counterfactual regret minimization (CFR) that converge to these refined equilibria with minimal additional computational overhead. 4. We empirically evaluate different types of Nash equilibria in several standard benchmark games. The results show that converging to gadget game sequential equilibria can reduce exploitability by more than 50% compared to vanilla SQF and CFR. Moreover, the results show that in resolving gadget games, these equilibria exhibit similar performance gains as using unsafe subgame solving, but provably without the risk of performing worse than blueprint.

2 Background and Notation

Two-player zero-sum factored-observation stochastic game is G = (N , W, wINIT , p, A, T , R1, O), where N = {1, 2, c} is a set of players and c is a chance player, which plays fixed strategy and it is used to model stochasticity of the environment. W is the set of world states and wINIT ∈ W is an initial world state. p : W → 2N is a function that assigns acting players to a given world state w. A = ∏i∈N Ai is the set of joint actions, we also use Ai(w) ⊆ Ai to denote legal actions of i in state w. T : W × A → W is a transition function and R1 : W ×A → R is a reward function of player 1. In a zero-sum setting following holds R2(w, a) = -R1(w, a). O : W × A × W → O is the observation function and O : O0 ×O1 ×O2 is the set of joint public observations and private observations. Similarly, observation function can be factored as O = (O0, O1, O2), where O0 is a public observation given to each player and O1, O2 are private observations available to their respective players [Kovaˇr´ık et al., 2022].

History h = w0a0 . . . al-1wl ∈ (WA)∗W is a finite sequence of world states and actions, which starts in the initial state w0 = wINIT and each timestep t ∈ {0, . . . , l - 1} is a valid transition wt+1 = T (wt , at ). H is a set of all possible histories in a game G. We use h ⊑ h′ to denote h′ that contains h as a prefix and we will denote the initial history as hINIT := wINIT . Every history ends with some world state wl , we will often use history in the game functions instead of that world state, for example A(h) := A(wl ). The players do not observe the whole world state at each timestep, but they only observe public and their corresponding private observations. As a result, the player may not distinguish several different histories. si is an information set of the player, which is a set of all histories consistent with the observations of player i. Si is then set of all information sets. We will overload the notation and use si(h) to denote the information set corresponding to history h and H(si) as all histories consistent with information set si. Similarly, s0 ∈ S0 is a public state, which is an information set of the external player, that does not have any private observations, so it contains all the histories consistent with public observations. As a result, each public state contains one or more information sets of each player and we will use s0(si) to denote the public state which contains information set si and Si(s0) as a set of all information sets consistent with s0.

The behavioral strategy of the player i is πi : Si → ∆Ai a mapping from information sets to probability distribution over actions. We will often use πi(si, ai) as a probability that ai is played in si, when following πi. The strategy profile π = (π1, π2) is a joint strategy profile of both players. For any two histories h, h′ , such that h ⊑ h′ , the probability of reaching h′ from h under strategy profile π is P π (h′ |h) = ∏h′′ aw⊑h′ ∏i∈N πi(si(h′′ ), ai). Any reach probability can be factored into the components of the individual players P π (h′ |h) = ∏i∈N P π i (h′ |h). Sometimes we use P π (h) := P π (h|hINIT ).

The expected utility of history h if all players follow strategy profile π is uπi (h) = ∑h⊑h′ a P π (h′ |h)Ri(h′ , a) ∏i∈N πi(si(h′ ), ai). Moreover, vπ i (sj) = ∑h∈H(sj) P π-j (h)uπi (h) ∑h∈H(sj) P π-j (h) are a counterfactual values. If ∑h∈H(sj) P π-j (h) = 0, then vπ i (sj) = 0. The best response against a strategy πi is a strategy πBR -i ∈ BR-i(πi) that maximizes the opponents utility πBR -i = argmaxπ-i u(πi,π-i) -i (hINIT ). The subscript -i is used to identify the other player then i. When each player follows a best response strategy to each other, the resulting strategy profile is the Nash equilibrium π∗ [Nash Jr, 1950]. In two-player zero-sum games, the Nash equilibrium is the desired solution concept and we use exploitability as a metric to evaluate quality of a strategy E(πi) = uπi,πBR -i -i (hINIT ) - uπ∗ -i (hINIT ), which is how much can the opponent gain if it plays a best response compared to the value received by both players following Nash equilibrium. The exploitability is always non-negative and is zero if and only if the πi is a part of Nash equilibrium.

2.1 Subgame Solving

There are two main approaches to subgame solving in imperfect-information games. The first, common-knowledge subgame solving, considers all histories that share the public state [Burch et al., 2014; Moravˇc´ık et al., 2017; Brown and Sandholm, 2018; Schmid et al., 2023; Kub´ıˇcek et al., 2024]. The second, knowledge-limited subgame solving, considers only a subset of public state histories [Zhang and Sandholm, 2021; Liu et al., 2023; Zhang and Sandholm, 2026]. Although our work focuses on common-knowledge subgame solving, the principles apply to both paradigms.

A subgame G s0 of a game G is defined the same as the original game, but it has different initial world state wINIT,s0

in which the chance player chooses between all the histories h ∈ H(s0), where s0 is the public state which contains current decision. Assume all players followed a precomputed blueprint strategy π, the chance distribution in the initial state of the subgame is proportional to P π (h). This results in a valid game that can be solved with any algorithm for imperfect-information games.

Solving such a subgame Gs0 results in a strategy profile πGs0 . We denote combined strategy as πi ← πGs0 i , where player i follows the new strategy πGs0 i within the subgame and the blueprint elsewhere π . This approach is known as unsafe subgame solving. While it often performs suprisingly well in practice [Gilpin and Sandholm, 2006; Gilpin and Sandholm, 2007; Ganzfried and Sandholm, 2015; Brown and Sandholm, 2017], it lacks theoretical guarantees [Burch et al., 2014; Ganzfried and Sandholm, 2015; Kovaˇr´ık et al., 2023]. The unsafety stems from assuming the opponent followed a fixed strategy in the past. However, if the opponent has played according to a different strategy, the game will look exactly the same, but the computed solution would perform vastly differently.

To rectify this, gadget games were developed to compute robust strategies [Burch et al., 2014; Moravˇc´ık et al., 2016; Brown and Sandholm, 2017]. The gadget game GG,s0 i is similar to G s0 , but instead of assuming the opponent followed the blueprint π, the gadget game introduces auxiliary information sets S G that allow the opponent to choose their reach probabilities adversarially.

Definition 1. Let G s0 be a subgame and GG,s0 i be a gadget game of player i corresponding to G s0 . Auxiliary information sets S G are all information sets that are in GG,s0 i but not in G s0 .

Different types of gadget games introduce different auxiliary information sets S G. The resolving gadget game contains an auxiliary information set for each opponent's information set s-i ∈ S-i(s0) in the root of the subgame, while the max-margin gadget game contains only a single auxiliary information set. In Figure 1 we show the construction of resolving and max-margin gadget games for a specific game. The reach max-margin gadget game has the same construction as max-margin, but uses different utility shifts [Brown and Sandholm, 2017].

The strategy resulting after solving the gadget game π ← πGG,s0 i i is guaranteed to be safe, which means it does not increase the exploitability compared to that of the agent's blueprint strategy: E(π ← πGG,s0 i ) ≤ E(π).

3 Example

To demonstrate the issues with Nash equilibria in gadget games, we present a modified version of Matching Pennies in Figure 1a. The game begins with Player 2 choosing either heads (H) or tails (T). Player 1, unaware of this choice, must choose among three actions: Forfeit (F), Heads (H), and Tails (T). By forfeiting, player 1 loses with a reward of -1. Otherwise, Player 1 receives a reward of 1 if they match Player 2's action and 0 if they do not. This game has a unique Nash

equilibrium in which both players play H and T with probability 0.5.

Assume a blueprint strategy for player 1, where π1 = [0.5, 0.5, 0] for actions F, H, T, respectively. Under this blueprint, the counterfactual values of the best response in the left and right branches of the tree are vπ1 1 (H) = 0, vπ1 1 (T) = -0.5.

In a resolving gadget game, Player 2 has the option to either enter the subgame (C) or terminate and receive the counterfactual best response value to the blueprint (T). The initial state of the subgame is decided by a chance node with probabilities proportional to the reaches P π1 1 · Pc . These "probabilities" do not necessarily sum to 1. Figure 1b illustrates the extensive-form representation of this gadget game. Any strategy of Player 1 that forces Player 2 to play into a terminating action is a Nash equilibrium. Crucially, this includes even the blueprint, which plays suboptimal action F, which is strictly dominated.

The max-margin gadget game allows Player 2 first to select an information set before the chance node determines the specific state based on the reaches P π1 1 · Pc . This construction also subtracts the counterfactual best response values from each terminal utility. Figure 1c shows the extensive-form representation of this game. In this specific case, there is a unique Nash equilibrium π1 = [0, 0.75, 0.25], which is not part of a Nash equilibrium of the whole game.

This example already hints at several of our results, which we discuss in more detail with more complicated examples in Appendix A. First, gadget games can have infinitely many equilibria that yield different values in the original game (Observation 1). Second, with some blueprint strategy, one might not be able to construct the optimal continuation strategy (Observation 2). Third, some equilibria in resolving gadget games can outperform all Nash equilibria of a max-margin gadget game (Observation 3).

4 Gadget Game Sequential Equilibria

The goal of subgame solving is to find a local strategy πGs0 i that ensures the updated strategy improves upon the blueprint strategy πi. This improvement is formally characterized in Theorem 1 (inspired by [Moravˇc´ık et al., 2017]), which shows that the resulting exploitability depends on the counterfactual best response values in the root information sets of the opponent.

Theorem 1. Given a blueprint strategy πi, a subgame G s0 , and a subgame strategy πGs0 i , let πi = πi ← πGs0 i . Let πBR -i ∈ BR-i(πi) and πBR -i ∈ BR-i(πi). If v(πi,πBR -i ) i (s-i) ≥ v(πi,πBR -i ) i (s-i) for each s-i ∈ S-i(s0), then u(πi,πBR -i ) i (hINIT ) - u(πi,πBR -i ) i (hINIT ) ≥ ∑s-i∈S-i(s0) P πBR -i -i (s-i)(v(πi,πBR -i ) i (s-i) - v(πi ,πBR -i ) i (s-i))

The proof is in Appendix A. Any Nash equilibrium of the resolving gadget game ensures that exploitability cannot increase by satisfying v(πi,πBR -i ) i (s-i) - v(πi ,πBR -i ) i (s-i) ≥ 0. In a max-margin gadget game, any Nash equilibrium maximizes

1

the smallest improvement in these counterfactual values.

Because this minimal improvement is always at least zero, every solution of the max-margin gadget game is also a solution of the corresponding resolving gadget game.

Proposition 1. Every Nash equilibrium of max-margin gadget game is also a Nash equilibrium of the corresponding resolving gadget game.

The max-margin gadget game can be further improved by allowing the player to pay back the "gifts" that the opponent has given through mistakes so far [Brown and Sandholm, 2017]. However, this typically requires knowledge outside of the current subgame. We demonstrate that strategies can be improved without additional information by accounting for sequential rationality.

Observation 1. There exists a game G, a subgame G s0 of G, and blueprint πi of player i, with corresponding resolving or maxmargin gadget game GG,s0 , in which different Nash equilibria result in different exploitability in the original game.

We provide an example for this and all future observations in Appendix A. In two-player zero-sum games, all Nash equilibrium yield the same unique value of the game [Kuhn and Tucker, 1951]. This is true even in a gadget game. However, thanks to Observation 1, we see that in the gadget game, not all equilibria are equal, as some lead to lower exploitability when used in the whole game. This is because the exploitability of the global strategy does not depend on the value in the root of the gadget game GG,s0 , but on the values in the information sets where the subgame G s0 begins.

Some Nash equilibria may play irrationally in parts of the gadget game that have zero reach. However, those same parts may be reached with high probability in the original game even if the opponent is playing an equilibrium of the whole game. Therefore, ensuring rational play even in unreachable nodes would be an improvement.

There has been a long line of work studying different Nash equilibria refinements in extensive-form games that ensure rationality in unreachable parts of the game [Kreps and Wilson, 1982; Selten, 1988; Van Damme, 1984; Van Damme,

2012]. The common problem with many of those refinements is that their computation necessitates playing each action with a small non-zero probability, and that the mistakes by the players should not be correlated. These conditions often make the computation numerically unstable. We observe that for gadget games, we do not need the full complexity of these refinements. Since the discrepancy between the gadget and the original game is in the auxiliary information sets, we only need to ensure rationality at the transition from the gadget game to the subgame.

Both the max-margin and resolving gadget game only add a single auxiliary information set to each trajectory, so it is enough to force at most one decision by the opponent to be played with non-zero probability in each trajectory. This means that the desired solution concept in gadget games is a weaker notion than some other refinements studied in the past [Van Damme, 2012], which simplifies their computation. Definition 2. Let S G -i be the opponent's auxiliary information sets in the gadget game GG,s0 i , and let πP (sG-i , a-i) > 0 be a prior strategy sG-i ∈ S G -i . Gadget game sequential equilibrium (GGSE) is a Nash equilibrium of a Gadget game GG,s0 i , where every action a-i ∈ A-i(sG-i ) is played with a probability greater than ϵ · πP (sG-i , a-i) as ϵ → 0+.

Gadget game sequential equilibria are a subset of Nash equilibria. They play rationally also in information sets to which the opponent plays with probability 0 from the auxiliary information sets.

Theorem 2. Assume a subgame G s0 and the corresponding gadget game GG,s0 i . Let π be a blueprint strategy. For every Nash equilibrium π∗ in the gadget game GG,s0 i , there exists a gadget game sequential equilibrium πG, that does not have lower counterfactual best response values in each root information set s-i ∈ S-i:

Corollary 1. If the optimal continuation strategy is a Nash equilibrium of a gadget game, then it is also gadget game sequential equilibrium.

Thanks to Theorem 2 and Corollary 1, it is enough to search the space of gadget game sequential equilibria without the risk of excluding equilibria that would result in lower exploitability.

5 Choice of Prior

While GGSE ensures rationality in the subgame, the performance of the resulting strategy is influenced by the choice of the prior πP . We first define the ideal target, which is the optimal strategy player i could play in the subgame, without changing strategy in the past.

Definition 3. Let G s0 be a subgame of game G. Also, let ˆ πi be a blueprint strategy, but only in the information sets S ′ i , which preceded some information set from Si(s0). The optimal continuation strategy ˆπ∗i satisfies

There could be multiple optimal continuation strategies, and ideally, we would like to find a strategy that is part of some optimal continuation strategy ˆπ∗i . Finding such a strategy naively requires solving the whole game with a fixed strategy of player i before reaching the subgame. A more scalable approach is to use a trained value function outside of the path to the subgame, which is called "full gadget" by Milec et al. [2024]. However, this approach requires a value function, which is difficult to train and grows linearly with the length of the game, making it less tractable than the resolving or max-margin gadget games.

Observation 2. There exists a game G, a subgame G s0 of G, and blueprint strategy π of player i, with corresponding resolving or maxmargin gadget game GG,s0 , in which no Nash equilibrium is part of the optimal continuation strategy ˆπ∗i

Observation 2 demonstrates that when using the resolving or max-margin gadget game, the optimal continuation strategy may not be reconstructible.

In practice, many prior works have used unsafe resolving, which assumes the opponent followed the blueprint in the past [Gilpin and Sandholm, 2006; Gilpin and Sandholm, 2007; Ganzfried and Sandholm, 2015; Brown and Sandholm, 2017]. Although it often yields stronger performance in practice than prior safe subgame solving techniques, it runs the risk of producing strategies that are more exploitable than the blueprint. We propose using the blueprint as the prior, which combines the best of both worlds, as the strategy will always be safe, but it will leverage the information from the blueprint.

Specifically, for a resolving Player 1, we set the prior of auxiliary information set sG2 and action a, which lead to information set s2 in the root of the subgame to be proportional to the reach of s2.

The blueprint may play some actions with probability 0, so in our experiments, we clip the value to πP 2 (sG2 , a2) ≥ 10-3 .

Using the opponent's part of the blueprint in subgame solving was explored in the poker AI Deepstack, where it was used as a warm-start strategy in the root of the gadget game [Moravˇc´ık et al., 2017]. Contrary to our approach, they used a blueprint only in the first iteration, so their approach did not generally converge to GGSE.

6 Superiority of the Resolving Gadget Game

There has been a long-standing consensus that the maxmargin gadget game is an improvement over the resolving gadget game. However, the authors of the AI poker system Deepstack noted that resolving gadget game performed better in early experiments [Moravˇc´ık et al., 2017]. Similarly, the Obscuro AI agent for dark chess solves both the resolving and max-margin gadget games, and then heuristically chooses one of those two [Zhang and Sandholm, 2026].

Previously, these discrepancies were often attributed to the use of imperfect value functions in nested subgame solving. The logic was that if the value function is inaccurate, the safety constraints from Theorem 1 might be impossible to satisfy, leading to more exploitable strategies.

We offer another explanation that shows the max-margin gadget game can be outperformed by resolving even in endgame situations or when using a perfect value function. We show that the max-margin gadget game with a poor blueprint may eliminate some equilibria that are still obtainable by the resolving gadget game. Moreover, the maxmargin gadget game may remove all equilibria that are part of the optimal continuation strategy ˆπ∗i .

Observation 3. There exists a game G, a subgame G s0 of G, and a blueprint strategy πi of player i, in which some Nash equilibria of the corresponding resolving gadget game are less exploitable than any Nash equilibrium in the corresponding max-margin gadget game.

The reason for this performance degradation is that in the max-margin gadget game, the opponent chooses at the root which information set it should play into based on how much improvement the player can get there, which introduces a bias to any Nash equilibrium strategy. In contrast, the resolving gadget game does not exhibit this bias toward certain parts of the game based on the blueprint. Therefore, when using an informed prior, such as the blueprint, the resolving gadget game often outperforms the max-margin.

7 Converging to Gadget Game Sequential Equilibria

A key advantage of GGSE is that it can be computed using standard tabular algorithms with only minor modifications. We describe how to modify the sequence-form linear program and counterfactual regret minimization to converge to GGSE. Both of these approaches are based on the idea of assuming the opponent makes small mistakes in the auxiliary information sets S G

7.1 Sequence-FormLinear Program

Consider the SQF for finding Player 1's part of the Nash equilibrium [Koller et al., 1996]:

Now consider a gadget game GG,s0 and a perturbation vector p ∈ R|S2| that is zero everywhere except for sequences that end with action in the auxiliary information set a2 ∈ A2(sG2 ), where it contains the prior πP 2 (sG2 , a2). The following linear program approximates GGSE for a sufficiently small ϵ:

This formulation resembles the LP used to find one-sided quasi-perfect equilibria [Farina and Sandholm, 2021]. It similarly does not require an arbitrarily small ϵ, but it suffices to solve for a small ϵ. If the solution remains optimal when ϵ is set to 0, then the solution is the desired equilibrium. Otherwise, the ϵ decreases, and the program is solved again. However, this LP presents two key distinctions over one-sided quasi-perfect equilibria. First, the trembles are assumed only in auxiliary information sets S G 2 rather than every decision point. Second, within the same decision points, two actions may be played with different minimal probabilities, depending on the prior πP .

7.2 Counterfactual Regret Minimization

The majority of successful subgame-solving applications have used counterfactual regret minimization (CFR), which iteratively minimizes counterfactual regret at each decision node. To approximate GGSE with CFR, we adopt the approach of Farina et al. [2017], which modifies the Regret Matching within CFR framework by introducing the concept of basis matrix Bsi ∈ R|Ai(si)|×|Ai(si)| . Each entry in the matrix is non-negative, and each row and column sum to 1. This matrix serves as a transformation from the non-perturbed strategy to the perturbed one, and then transforms the regrets from the perturbed space to the non-perturbed one.

We use this basis in auxiliary information sets sG2 :

I is an identity and P is a symmetric matrix where a column corresponding to action a2 ∈ A2(sG2 ) contains πP 2 (sG2 , a2).

This change does not significantly increase per-iteration time, but converging to an equilibrium may require more iterations based on the ϵ and P , which we show in Section 8.

When using either the CFR or SQF, the resulting equilibrium is a GGSE, but it need not be consistent with the prior πP . The GGSE is consistent with the prior only if the equilibrium itself does not play into any part of the subgame. The solutions of the max-margin gadget game wuill always be inconsistent, but those of the resolving gadget game can be consistent (exactly when all the counterfactual values are lower than the optimal ones).

8 Experiments

We evaluated the proposed algorithms for finding GGSE across three standard benchmark games: imperfectinformation Goofspiel 5, Leduc hold'em, and Liar's dice 1,4. In each of those games, we generated 25 blueprints

(b) Goofspiel 5, depth 2

(d) Liar's dice 1,4, depth 1

Figure 2: Exploitability of the resolved strategy from each subgame based on blueprint's exploitability when using CFR as solver.

from different checkpoints of CFR. These serve as realistic approximations of blueprint strategies typically produced by abstraction-based methods or Monte Carlo CFR. We also generated 20 blueprints, in which the behavioral strategy in each information set was drawn independently from the Dirichlet distribution Dir(α), with αi = 1.

We solve subgames at specific decision points. In Goofspiel and Liar's dice, we solve every subgame following a fixed number of moves, and in Leduc hold'em, we solve all subgames after the public card is revealed. For each game and blueprint, we computed different types of subgame equilibria using the CFR modification discussed in Section 7.2, with CFR+ updates [Tammelin et al., 2015]. We compare three different prior settings: no prior, uniform prior, or blueprint prior. For comparison, we also include the optimal continuation strategy and unsafe solving, which assumes both players play a fixed strategy before the subgame.

The relationship between the exploitability of the resolved strategy and the exploitability of the blueprint is shown in Figure 2. In Appendix B, we provide statistical analysis for our results and the same results when using SQF as a solver. We also show the convergence curves in Figure 3 for one of the blueprints to demonstrate the computational overhead in convergence when using a prior. We highlight the following results from this experiment.

• Incorporating the prior does not increase the exploitability and often decreases it. The gains are more significant when using the resolving gadget game.
• Inmany cases, the max-margin solutions outperform the resolving ones when no prior is used, in line with prior

work. However, when using the prior, in Leduc hold'em, the solutions of the resolving gadget game outperform the max-margin ones, confirming that max-margin does not have to be superior to resolving.

• Although unsafe solving performs well when the blueprint is poor, its performance degrades as the blueprint improves. In contrast, when using the resolving gadget game with a blueprint prior, the solution achieves performance comparable to unsafe solving while being safe, effectively combining the strengths of both approaches.
• Converging to GGSE with CFR requires more iterations. Even with fewer iterations, the performance does not deteriorate compared to not using a prior at all, suggesting that using the prior does not come with any downside.

8.1 Nested Depth-Limited Subgame Solving

In large games, it is intractable to solve the whole game from the current decision point all the way to terminal states. The common approach to address this is to use nested depth-limited subgame solving, also known as midgame solving [Brown et al., 2018; Brown and Sandholm, 2019; Kub´ıˇcek et al., 2024]. This approach trains a value function that is used after a fixed number of moves. In our experiments, we used a value function based on multi-valued states, which, after the depth limit, abstracts the entire rest of the game into a single decision by both players, in which they choose a strategy for the remainder of the game [Brown and Sandholm, 2019; Kovaˇr´ık et al., 2023].

We trained 10 different value functions in imperfectinformation Goofspiel 7 and Liar's dice 2,4, both of which are large enough that exploitability cannot be computed efficiently, using the approach of Kub´ıˇcek et al. [2024]. Then we matched different types of subgame solving at each encountered decision point. Head-to-head performance does not directly correspond to exploitability, because neither technique aims to exploit the opponent; rather, each approximates the Nash equilibrium of the entire game. Figure 4 shows the win-rate of each subgame solving technique against the worst matchup out of all the other techniques, which serves as a very limited approximation of exploitability. We provide the full head-to-head win-rates in Appendix B.

The results confirm that using the prior is beneficial even in head-to-head play. In Goofspiel, the unsafe solving performs well, while the solutions of the max-margin gadget game perform poorly, regardless of the prior. The situation in Liar's dice is the opposite. In both games, the solutions from the resolving gadget game with a blueprint prior consistently perform well across opponents.

9 Conclusions and Future Research

We studied gadget games, a subgame solving technique for imperfect-information games. While gadget games provide essential safety guarantees, they often contain infinitely many Nash equilibria. We showed that those equilibria may seem equivalent in the context of the gadget game, but when used in the original game, they lead to vastly different exploitability.

We proposed a new equilibrium refinement, specifically tailored to gadget games, gadget game sequential equilibrium, that improves upon vanilla Nash equilibria. We provided modifications to both the sequence-form linear program and counterfactual regret minimization to compute those refinements with negligible additional computational overhead.

We provided a novel explanation for the empirical superiority of the resolving gadget game over max-margin. We showed that the max-margin gadget game introduces an inherent bias into the solution, potentially excluding good equilibria that remain solutions of the resolving gadget game. We empirically verified that this occurs regularly in some games.

We compared different subgame-solving methods across multiple benchmarks and verified that converging to gadget game sequential equilibria consistently performs as well or better than both unsafe solving and the usual unrefined Nash equilibria to which CFR and the sequence form LP converge in gadget games. Thanks to improved theoretical understanding and empirical performance, this work establishes gadget game sequential equilibrium as the preferred solution concept for subgame solving in imperfect-information games.

Even though we established that there are games where neither the resolving nor the max-margin gadget game have the optimal continuation strategy as a solution, there is potential future work to either develop a new gadget game or to modify the existing ones so that they can reconstruct an optimal continuation strategy without the linear growth in size of the game as "full gadget". Another future research direction is to verify whether gadget game sequential equilibria present similar performance gains even when using the reach max-margin gadget game and/or when conducting knowledge-limited subgame solving. Also, there is potential to apply gadget game sequential equilibria to subgame solving in large recreational games like Texas hold'em and dark chess as well as to real-world game applications.

Acknowledgments

This work is supported by National Science Foundation grant RI-2312342 , the Vannevar Bush Faculty Fellowship ONR N00014-23-1-2876, the Czech Science Foundation GA2518353S, the Grant Agency of the Czech Technical University in Prague (SGS23/184/OHK3/3T/13). The access to the computational infrastructure of the OP VVV funded project CZ.02.1.01/0.0/0.0/16 019/0000765 "Research Center for Informatics" is also gratefully acknowledged. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the funding agencies.