An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large Extensive-Form Games

1 Introduction

Dynamic games with a finite number of moves can be modeled as extensive-form games (EFGs) that are general enough to represent scenarios with stochastic events and imperfect information. EFGs can model recreational games, such as poker, as well as real-world situations in physical security [Lis´y et al., 2016], auctions, or medicine [Chen and Bowling, 2012]. EFGs are represented as game trees where nodes correspond to states of the game and edges to actions of players. Imperfect information is modeled by grouping indistinguishable states into information sets.

There are two approaches to solving EFGs. First, the online (or game-playing) algorithms which given the observations of the game state compute the action to be played. Second, the offline algorithms which compute (approximate) the strategy in the whole game and play according to this strategy. The latter algorithms typically provide a better approximation of equilibrium strategies in large games compared to online algorithms [Boˇsansk´y et al., 2016]. One exception is the recently introduced continual resolving algorithm used in DeepStack [Moravˇc´ık et al., 2017], which provides less exploitable strategies than existing offline algorithms in headsup no-limit Texas Hold'em, an imperfect information game with 10160 decision points. The main caveat is that DeepStack exploits the specific structure of poker where all actions are observable, and the generalization to other games is not straightforward. We thus focus on offline algorithms.

Most of the existing offline algorithms [von Stengel, 1996; Zinkevich et al., 2008] require players to remember all the information gained during the game - a property denoted as a perfect recall. The main disadvantage of perfect recall is that it causes the size of strategies (a randomized selection of an action in each information set) to grow exponentially with the number of moves. Therefore, a popular approach is to use abstractions [Gilpin et al., 2007] - create an abstracted game by merging information sets to reduce the size of the strategy representation, solve the abstracted game, and translate the strategies back to the original game. The majority of existing algorithms create perfect recall abstractions, where the requirement of perfect memory severely limits possible reductions in the size of strategies of the abstracted game, as it still grows exponentially with increasing number of moves in the abstracted game (e.g., see [Gilpin and Sandholm, 2007; Kroer and Sandholm, 2014; Brown and Sandholm, 2015]). Additionally, finding optimal perfect recall abstractions is computationally hard [Kroer and Sandholm, 2014].

A limited amount of work relaxes the perfect recall restriction in abstractions. Very specific imperfect recall abstractions that allow using perfect recall solution techniques are (skew) well-formed games [Lanctot et al., 2012; Kroer and Sandholm, 2016] and normal-form games with sequential strategies [Boˇsansk´y et al., 2015; Lis´y et al., 2016]. Skew well-formed games only merge information sets, which satisfy strict restrictions on the structure of the game tree above and below them, such that for all possible strategies of the opponent, a strategy which is optimal in one of the information sets must have bounded error in the other merged sets. Players cannot observe actions of the opponent at all in normalform games with sequential strategies. These restrictions prevent us from creating sufficiently small and useful abstracted games and thus fully exploit the possibilities of imperfect recall. Existing methods for using imperfect recall abstractions without severe limitations cannot provide any guarantees of the quality of computed strategies [Waugh et al., 2009], or assume that the abstraction is given and require computationally complex algorithms to solve it [ ˇCerm´ak et al., 2017].

We address these issues in this paper and demonstrate the possible space savings achievable by automated imperfect recall abstractions. We create a novel domain-independent algorithm FPIRA, which starts with creating a coarse imperfect recall abstraction of the given perfect recall game. FPIRA then uses the fictitious play framework to simultaneously solve and refine the imperfect recall abstraction, to guarantee the convergence to Nash equilibrium of the original perfect recall game. FPIRA is conceptually similar to Double Oracle algorithm (DO) [Boˇsansk´y et al., 2014] since it creates a smaller version of the original game and repeatedly refines it until the optimal solution of the original game is found. FPIRA, however, uses a game with imperfect recall during the computation, while DO uses a smaller perfect recall game. Hence, FPIRA exploits completely different type of sparseness than DO. The experimental evaluation shows that FPIRA can solve modification of Leduc hold'em with 7 · 105 information sets using an abstracted game with 1.8% of information sets of the original game. Furthermore, experiments on other simplified pokers and random games suggest that the relative size of the needed abstractions significantly decreases as the size of the solved games increases.

2 Extensive-FormGames

We first describe necessary technical introduction to extensive-form games (EFGs). A two player EFG G is a tuple {P, H, Z, P, u, I, A}. P = {1, 2} denotes the set of players. We use i to refer to a player and -i to refer to the opponent of i. Set H contains all the states of the game. P : H → P∪{c} is the function associating a player from P or nature c with every h ∈ H. Nature c represents the stochastic environment of the game. Z ⊆H is a set of terminal states. ui(z) is a utility function assigning to each leaf the value of preference for player i; ui : Z → R. For zero-sum games it holds that ui(z) = -u-i(z), ∀z ∈ Z. The imperfect information is defined using the information sets. Ii is a partitioning of all {h ∈ H : P(h) = i} into these information sets. All states h contained in one information set Ii ∈ Ii are indistinguishable to player i. The set of available actions A(h) is the same ∀h ∈ Ii. We overload the notation and use A(Ii) as actions available in Ii. A sequence σi is a list of actions of player i ordered by their occurrence on the path from the root of the game tree to some node. By seqi(h) we denote the sequence of player i leading to the state h. We overload the notation and use seqi(I) as a set of sequences of player i leading to the information set I. A game has perfect recall iff ∀i ∈ P ∀Ii ∈ Ii, for all the states h, h′ ∈ Ii holds that seqi(h) = seqi(h′ ). If there exists at least one information set where this does not hold (denoted as imperfect recall information set) the game has imperfect recall.

Definition 1. By the coarsest perfect recall refinement of an imperfect recall game G we define a perfect recall game G′ where we split the imperfect recall information sets to largest subsets satisfying the perfect recall assumption.

2.1 Strategies in Imperfect Recall Games

There are several representations of strategies in EFGs. A pure strategy si for player i is a mapping assigning ∀Ii ∈ Ii a member of A(Ii). Si is a set of all pure strategies for player i. A mixed strategy mi is a probability distribution over Si, set of all mixed strategies of i is denoted asMi. Behavioral strategy bi assigns a probability distribution over A(Ii) for each Ii. Bi is a set of all behavioral strategies for i, Bp i ⊆ Bi denotes the set of deterministic behavioral strategies for i. A strategy profile is a set of strategies, one strategy for each player. We overload the notation and use ui as the expected utility of i when the players play according to pure (mixed, behavioral) strategies.

Behavioral strategies and mixed strategies have the same expressive power in perfect recall games, but their expressive power can differ in imperfect recall games [Kuhn, 1953]. Moreover, the size of these representations differs significantly. Mixed strategies of player i use probability distribution over Si, where |Si| ∈ O(e|Z| ). Behavioral strategies create probability distribution over the set of actions (its size is proportional to the number of information sets, which can be exponentially smaller than |Z|). Hence we need to use behavioral strategies if we want to exploit the space savings caused by the reduced number of information sets due to some information abstraction.

A best response of player i against b-i is a strategy bBR i ∈ BR(b-i), where ui(bBR i , b-i) ≥ ui(b′i , b-i) for all b′i ∈ Bi (BR(b-i) denotes a set of all best responses to b-i).

Definition 2. We say that bi and b′i are realization equivalent if for any b-i, ∀z ∈ Z πb (z) = πb′ (z), where b = (bi, b-i) and b′ = (b′i , b-i) and πb (z) stands for the probability that z is reached when playing accordint to b.

The concept of realization equivalence can be applied also to different strategy representations. Finally, we define the Nash equilibrium in behavioral strategies.

Definition 3. We say that strategy profile b = {bi, b-i} is a Nash equilibrium (NE) in behavioral strategies iff ∀i ∈ P ∀bpi ∈ Bp i : ui(bi, b-i) ≥ ui(bpi , b-i).

3 Fictitious Play

Fictitious play (FP) is an iterative algorithm defined on normal-form games [Brown, 1949]. It keeps track of average strategies of both players ¯mTi , ¯mT-i . Players take turn updating their average strategy. In iteration T, player i computes sTi ∈ BR( ¯mT-1 -i ). He then updates his average strategy ¯mTi = Ti-1 Ti ¯mT-1 i + 1 Ti sTi (Ti is the number of updates performed by i plus 1). In two-player zero-sum games ¯mTi , ¯mT-i converge to a NE [Robinson, 1951]. There is a long-standing conjecture [Karlin, 2003; Daskalakis and Pan, 2014] that the convergence rate of FP is O(T - 12 ), the same order as the convergence rate of Counterfactual Regret Minimization (CFR) [Zinkevich et al., 2008] (though the empirical convergence of CFR tends to be better).

When applying FP to behavioral strategies in perfect recall zero-sum EFG G′ , one must update the average behavioral strategy ¯bti such that it is realization equivalent to ¯mti obtained when solving the normal form game corresponding to G′ for all t and all i ∈ P to keep the convergence guarantees. To update the behavioral strategy in such a way we use the following Lemma [Heinrich et al., 2015].

Lemma 1. Let bi, b′i be two behavioral strategies and mi, m′i two mixed strategies realization equivalent to bi, b′i , and λ1, λ2 ∈ (0, 1), λ1 + λ2 = 1. Then ∀I ∈ Ii

where πbi i (I) is the probability that I is visited when playing bi, defines a behavioral strategy b′′ i realization equivalent to the mixed strategy m′′ i = λ1mi +λ2m′i .

4 The FPIRAAlgorithm

Let us now describe the main algorithm (denoted as FPIRA, Fictitious Play for Imperfect Recall Abstractions) presented in this paper and prove its convergence in two-player zerosum EFGs. We give a high-level idea behind FPIRA, and we provide a pseudocode with the description of all steps.

Given a perfect recall game G′ , FPIRA creates a coarse imperfect recall abstraction G of G′ . The algorithm then follows the FP procedure. It keeps track of average strategies of both players in the information set structure of G and updates the strategies in every iteration based on the best responses to the average strategies computed directly in G′ . To ensure the convergence to Nash equilibrium of G′ , FPIRA refines the information set structure of G when needed to make sure that the strategy update does not lead to more exploitable average strategies in the following iterations compared to the strategy update made directly in G′ .

Algorithm 1: FPIRA algorithm

input : G′ , T output : ¯bTi , ¯bT-i, GT 1 G1 ←BuildAbstraction(G′) 2 ¯b01 ← PureStrat(G1 ),¯b02 ← PureStrat(G1 ) 3 for t ∈ {1, ..., T} do 4 i ← ActingPlayer(t) 5 bti ← BR(G′ , ¯bt-1 -i ) 6 Gt ←RefineForBR(Gt , bti) 7 ˆbti ← UpdateStrategy(Gt , ¯bt-1 i , bti) 8 ˜bti ←UpdateStrategy(G′ ,¯bt-1 i , bti) 9 if ComputeDelta(G′ , ˆbti , ˜bti) > 0 then 10 Gt+1 ← Refine(Gt), ¯bti ← ˜bti 11 else 12 Gt+1 ← Gt , ¯bti ← ˆbti

In Algorithm 1 we present the pseudocode of FPIRA. FPIRA is given the original perfect recall game G′ = {P, H, Z, P, u, I ′ , A′ } and a number of iterations to perform T. FPIRA first creates a coarse imperfect recall abstraction G1 = {P,H,Z, P, u, I 1 ,A1 } of G′ (line 1) as described in Section 4.1. Next, it initializes the strategies of both players to an arbitrary pure strategy in G1 (line 2). FPIRA then performs T iterations. In every iteration it updates the average strategy of one of the players and if needed the information set structure of the abstraction (the game used in iteration t is denoted as Gt = {P, H, Z, P, u, I t , At }). In every iteration player i first computes the best response bti to ¯bt-1 -i in G′ (line

5). Since bti is computed in G′ , FPIRA first needs to make sure that the structure of information sets in Gt allows bti to be played. If not, Gt is updated as described in Section 4.2, Case 1 (line 6). Next, FPIRA computes ˆbti as the strategy resulting from the update in abstracted Gt (line 7) and ˜bti as the strategy resulting from the update in original G′ (line 8). FPIRA then checks whether the update in Gt changes the expected values of the pure strategies of the opponent compared to the update in G′ using ˆbti and ˜bti (line 9, Section 4.2 Case 2). If yes, FPIRA refines the information set structure of Gt , creating Gt+1 such that no error in expected values of pure strategies of the opponent is created (Section 4.2 Case 2), sets ¯bti = ˜bti (line 10), and continues using Gt+1 . If there is no need to update the structure of Gt , FPIRA sets Gt+1 = Gt , ¯bti = ˆbti and continues with the next iteration.

4.1 Creating the Initial Abstraction

FPIRA creates G1 (line 1 in Algorithm 1) as a coarse imperfect recall abstraction of G′ by merging possible information sets, such that the coarsest perfect recall refinement of G1 is G′ . To achieve this, FPIRA needs to make sure that when merging a set of information sets J ⊆ Ii there are no two distinct I, I ′ ∈ J which, when merged, create a perfect recall information set. This is required since, as discussed in the next section, the algorithm splits only imperfect recall information sets. If FPIRA joined information sets not resulting in the imperfect recall information set, it would end up solving a different game.

More formally, we use the following algorithm to build G1 . For all i create Ki as a set of disjoint subsets of information sets I ′ i of G′ , such that ⋃K′∈Ki K′ = I ′ i , and

In other words, all the information sets in K′ must have the same number of actions available and the same length of the sequence of i leading to them. Every K′ ∈ Ki gives us candidates for merging. However, as discussed above, we need to make sure that we never merge any pair of information sets, which would result in a perfect recall information set after the merge. Hence, we further split every K′ ∈ Ki to the smallest possible set J = {J 1 , ..., J k }, such that

I and I ′ are information sets of G′ , hence both seqi(I) and seqi(I ′ ) are singletons. J needs not be unique, in our implementation we choose randomly between possible J . Finally, every information set in the information set structure I 1 of G1 corresponds to J j from the union of all J for all players.

4.2 Updating Gt

There are two reasons for splitting some I ∈ I t i in iteration t (we assume player i computes the best response in t): (1) the best response computed in G′ prescribes more than one action in I or (2) I causes expected values of some pure strategy of -i to be different after the average strategy update of i compared to what would happen when updating in G′ .

To formally describe the splitting rules, let us first define mappings Φt : I ′ → I t , which for I ∈ I ′ returns the information set containing I in Gt and Φ-1 t : I t → ℘(I ′ ), the inverse of Φt. By Ξt : A′ → At and Ξ-1 t : At → ℘(A′ ) we denote a mapping of actions from G′ to Gt and vice versa.

Case 1: FPIRA checks in every iteration t if there exists I ∈ I t i where the best response bti prescibes more than 1 action. If yes, FPIRA splits I to a set of information sets ˆ I and inforation set I ′′ , such that ∀ˆ Ia ∈ ˆ I, ˆ Ia is a unification of all I ′ ∈ Φ-1 t (I) where bti (I ′ , a′ ) = 1 for Ξt(a′ ) = a and I ′′ = {h ∈ I|∀ˆ I ∈ ˆ I : h /∈ ˆ I} (line 6 in Algorithm 1).

Case 2: The algotrithm first constructs the average behavioral strategy ˆbti in Gt (line 7). This is done according to Lemma 1 from ¯bt-1 i with weight ti-1 ti and bti with weight 1 ti , where ti is the number of updates performed by i so far, plus 1 for the initial strategy (bti is used with mappings Φt and Ξt). Next, FPIRA constructs ˜bti (line 8) in the same way in the information set structure of G′ (¯bt-1 i is used with mappings Φ-1 t and Ξ-1 t ). FPIRA then computes

as described below (line 9). If ∆ti = 0, none of the pure strategies of -i changed its expected value compared to the update in G′ . In this case, FPIRA sets Gt+1 = Gt , ¯bti = ˆbti (line 12). If ∆ti > 0, the expected value of some pure strategy of -i changed when updating the strategy in Gt , compared to the expected value it would get against the strategy updated in G′ . FPIRA then creates Gt+1 in the following way. Every imperfect recall information set I ∈ I t i which is visited when playing bti is split to a set of information sets ˆ I ⊆ Φ-1 t (I) and an information set I ′′ , such that ˆ I contains all the I ′ ∈ Φ-1 t (I) which can be visitedwhen playing bti , I ′′ contains the rest of h ∈ I. The average strategy in all I ′ ∈ ˆ I ∪{I ′′ } before the strategy update is set to the strategy previously played in I. More formally, ∀I ′ ∈ ˆ I ∪ {I ′′ } the strategy is set to

The strategy resulting from update in G′ is a valid strategy in Gt+1 after such update, hence ¯bti = ˜bti . Notice that G′ is still the coarsest perfect recall refinement of Gt+1 , additionally by setting ¯bti = ˜bti , we made sure that ∆ti = 0 since the update is now equal to the update that would occur in G′ . This, as we will show in Section 4.3, is sufficient to guarantee the convergence of ¯bti ,¯bt-i to Nash equilibrium of G′ .

Computing ∆ti . Given ˆbti and ˜bti , ∆ti can be computed as

∆ti can be computed in O(|Z|) as a standard best response tree traversal.

Example 1. Let us demonstrate several iterations of FPIRA algorithm. Consider the perfect recall game from Figure 1 (a) as G′ and the imperfect recall game from Figure 1 (b) as G1 . The function Ξ1 is Ξ1(t) = Ξ1(v) = c, Ξ1(u) = Ξ1(w) = d, identity otherwise. Note that when we apply strategies from G′ to Gt and vice versa, we assume that it is done with respect to Ξt and Ξ-1 t . Lets assume that FPIRA first initializes the strategies to ¯b01 (b) = ¯b01 (d) = 1, ¯b02 (e) = 1.

Iteration 1: The player 1 starts in iteration 1. FPIRA computes b11 ∈ BR(¯b02 ) in G′ , resulting in b11 (b) = b11 (v) = 1. Next, FPIRA checks whether b11 is playable in G1 . Since there is no information set in G1 for which b11 assigns more than one action, we do not need to update G1 in any way. We follow by computing ˆb11 and ˜b11 according to Lemma 1 with λ1 = λ2 = 0.5. In this case ˆb11 (b) = ˜b11 (b) = 1,ˆb11 (c) = ˜b11 (v) = 0.5. Since ˆb11 and ˜b11 are equal, w.r.t. Ξ1, we know that ∆i = 0. Hence we let G2 = G1 , ¯b11 = ˆb11 and Ξ2 = Ξ1.

Iteration 2: Player 2 continues in iteration 2. Notice that player 2 does not have imperfect recall, hence there is no need to discuss this iteration in such detail. FPIRA computes the best response to ¯b11 , resulting in b22 (f) = 1. The algorithm then computes ˆb22 and ˜b22 , resulting in ˆb22 (e) = ˜b22 (e) = 0.5. Hence, we let G3 = G2 , ¯b22 = ˆb22 and Ξ3 = Ξ2.

Iteration 3: The best response in this iteration is b31 (a) = b31 (u) = 1, which is again playable in G3 , hence we do not need to update G3 at this point. FPIRA computes ˆb31 resulting in ˆb31 (a) = 1 3 ,ˆb31 (d) = 23 , ˜b31 is, on the other hand, ˜b31 (a) = 13 , ˜b31 (t) = 1,˜b31 (w) = 0.5 (both according to Lemma 1 with λ1 = 23 , λ2 = 13 ). In this case, ∆31 = 1 since by playing f player 2 gets 23 against ˆb31 compared to 53 against ˜b31 . Hence, the algorithm splits all imperfect recall information sets reachable when playing b31 , in this case I1, as described in Section 4.2, Case 2, resulting in G′ . Therefore, G4 = G′ , ¯b31 = ˜b31 and Ξ4 is set to identity.

4.3 Theoretical Properties

We show that the convergence quarantees of FP in two-player zero-sum perfect recall game G′ [Heinrich et al., 2015] directly apply to FPIRA solving G′ .

Theorem1. The exploitability of ¯bti computed by FPIRA applied to perfect recall two-player zero-sumEFGG′ is exactly equal to the exploitability of ¯ b′ ti , computed by FP applied to G′ in all iterations t and for all i.

Proof. Assume that the initial strategies ¯b01 ,¯b02 in FPIRA and initial strategies ¯ b′ 01 , ¯ b′ 02 in the FP are realization equivalent, additionally assume that the same tie breaking rules are used when more than one best response is available. We prove the Theorem by induction. If

where Bp is the set of pure behavioral strategies in G′ , then

First, the initial step trivially holds from the initialization of strategies. Now let us show that the induction step holds. Let bti be the best response chosen in iteration t in FPIRA and b′ti be the best response chosen in t in FP. From (2) and the use of the same tie breaking rule we know that bti = b′ti . From Lemma 1 we know that

However, same holds also for ¯bt+1 i since FPIRA creates Gt+1 fromGt so that ∆ti = 0. Hence

From (1) and from the equality bti = b′ti follows that

4.4 Memory and Time Efficiency

FPIRA needs to store the average behavioral strategy for every action in every information set of the solved game, hence storing the average strategy in Gt instead of G′ results in significant memory savings directly proportional to the decrease of information set count. Additionally, when the algorithm computes ˜bti , it can temporarily refine the information set structure of Gt only in the parts of the tree that can be visited when playing the pure best response bti according to I ′ i to avoid representing and storing G′ . Moreover, one typically does not have to store and traverse the whole game tree when computing a best response. When storing the bti , we do not store behavior in the parts of the game unreachable due to actions of i. For this reason, there are typically large parts of the game tree omitted, since i plays only 1 action in his information sets. Hence, the best response computation does not prevent us from solving large domains with excessive memory requirements (we provide results showing that the best responses are small in Section 5). Finally, efficient domain-specific implementations of best response (e.g., on poker [Johanson et al., 2011]) can be employed to further reduce the memory and time requirements. The iteration of FPIRA takes approximately twice the time needed to perform one iteration of FP in G′ , as it now consists of the standard best response computation in G′ , the modified best response computation to obtain ∆ti and two updates of average behavioral strategies (which are faster than the update in G′ since the average strategy is smaller).

5 Experiments

We introduce the domains used for experimental evaluation of FPIRA. We follow by the discussion of the convergence and the size of abstractions needed to solve these domains.

Leduc Hold'em. Leduc Hold'em is a two-player poker, which is used as a common benchmark in imperfectinformation game solving because it is small enough to be solved but still strategically complex. There is a deck of cards with a given number of card types and a given number of cards per type (in standard Leduc hold'em there are 3 types of cards, 2 cards for each type). There are two rounds. In the first round, each player places an ante of 1 chip in the pot and receives a single private card. A round of betting follows. Every player can bet from a limited set of allowed values or check. After a bet, the player can raise, again choosing the value from a limited set, call or forfeit the game by folding. The number of consecutive raises is limited. A public shared card is dealt after one of the players calls or after both players check. Another round of betting takes place with identical rules. The player with the highest pair wins. If none of the players has a pair, the player with the highest card wins.

RandomGames. Since there is no standardized collection of benchmark EFGs, we use randomly generated games to obtain statistically significant results. We randomly generate a perfect recall game with varying depth and branching factor 5. To control the information set structure, we use observations assigned to actions - for player i, nodes h with the same observations generated by all actions in history belong to the same information set. Every action generates a temporary utility which is randomly generated in the interval (-2, 2). The utility for player 1 in every leaf is then computed as the sum of the temporary utilities of actions leading from the root of the game to the leaf. In this way, we create more realistic games, with the notion of good and bad moves.

5.1 Results

In all the presented results, FPIRA was terminated when the difference of the expected values of best responses against the average strategies was below 10-2 .

Leduc Hold'em. In Figure 2 (a) we show the exploitability of the average strategies computed by the FP and FPIRA (y-axis) as a function of iterations (log x-axis) on Leduc Hold'em with 4 card types, 3 for each type, 2 possible bet and raise values and 4 consecutive raises allowed. The observed identical convergence rate of FPIRA and the FP is a direct consequence of Theorem 1. Both algorithms needed ∼ 5·103 iterations to converge to the gap 10-2 in the expected values of best responses against the average strategies. In Figure 2 (b) we show the information set count of Gt and G′ (log y-axis) as a function of iterations (log x-axis) in the same setting. As expected, the highest increase in the information set count of Gt is at the beginning of the algorithm since the information set structure is extremely coarse and the strategies vary significantly between iterations. In the later stages of the convergence, we observe almost no changes in the information set structure. Additionally, in Figure 2 (c) we present relative information set counts for initial and final abstraction, relative size of the largest best response which needed to be

10 6

stored and total information set count of the original perfect recall game in poker domains, first when increasing number of bets and raises and when increasing number of allowed consecutive raises. The size of both abstractions decreases in both parameters, hence the sizes of the average strategies stored in FPIRA decrease proportionally. Besides storing the average strategy in the current abstraction, FPIRA also stores the best response computed in G′ before updating the average strategy. To show the maximal memory needed to store these best responses we provide the number of information sets of G′ for which there is an action prescribed in the largest best response during the run of FPIRA. These results show that the sizes of the best responses do not threaten the memory efficiency of FPIRA. This leads to significant memory savings in large domains with only approximately twice as much time needed per iteration compared to the FP applied directly to the perfect recall game. Additionally, the results suggest that further scaling of the solved domains will significantly reduce the relative size of the abstractions. This observation is further supported by the fact that the relative support size of Nash equilibria in poker-like domains decreases as the game size increases [Schmid et al., 2014].

Random games. To show the performance of FPIRA in games with varying structure, we performed additional experiments on 50 instances of random games for depth 7 and 30 instances for depth 8. FPIRA was able to solve the instances using abstractions which had on average only 4.9% ± 0.7% of the information sets of the original game for depth 7 and 1.2%±0.3% for depth 8. The perfect recall instances had on average 2.6 · 104 ± 4 · 103 and 1.1 · 105 ± 3 · 104 information sets for depth 7 and 8 respectively. Notice that the sizes of abstractions needed to solve the random games are significantly smaller than in the case of poker with similar information set counts. This is caused by the moves of nature at the start of poker, which cause large parts of the game tree to be visited when playing according to one pure strategy. Hence when computing ∆ti , there is a significantly higher number of pure strategies of -i that we need to check, and therefore more information set splits, compared to games with no nature.

6 Conclusion

We present the first algorithm that automatically creates imperfect recall abstractions and uses them to solve the original extensive-form game with perfect recall. While the imperfect recall abstractions of perfect recall games can significantly reduce the space necessary for storing strategies, their use has been rather limited. Previous works use either very restricted subclasses of imperfect recall abstractions [Lanctot et al., 2012; Kroer and Sandholm, 2016; Boˇsansk´y et al., 2015], heuristic approaches [Waugh et al., 2009], or only focus on solving the given imperfect recall game [ ˇCerm´ak et al., 2017].

Our main contribution is the memory efficient algorithm FPIRA that provides an automatically created imperfect recall abstraction that is sufficient for a Nash equilibrium strategy in the original perfect recall game. As a consequence, a strategy from the abstracted game can be used directly in the original game without the need to use translation techniques, nor is the quality of such strategy affected by choice of the abstraction. The FPIRA algorithm is based on fictitious play (FP) and provides the same guarantees of the convergence as if FP were applied directly to the original perfect recall game. The experimental evaluation shows that we are able to solve modification of Leduc hold'em with 7 · 105 information sets using an abstracted game with 1.8% of information sets of the original game. Furthermore, the experiments on different versions of Leduc hold'em and random games suggest that the relative size of the needed abstractions significantly decreases as the size of the solved games increases.

A natural step for future work is to generalize FPIRA to other learning algorithms - e.g., Counterfactual Regret Minimization (CFR) [Zinkevich et al., 2008] that is used for solving large extensive-form games with perfect recall. However, this generalization is not straightforward since the updates, and the identification of whether an information set should be split is significantly more challenging in that case.

Acknowledgments

This research was supported by the Czech Science Foundation (grant no. 15-23235S), and by the Grant Agency of the Czech Technical University in Prague, grant No. SGS16/235/OHK3/3T/13. Computational resources were provided by the CESNET LM2015042 and the CERIT Scientific Cloud LM2015085, provided under the programme "Projects of Large Research, Development, and Innovations Infrastructures".