Endgame Solving in Large Imperfect-Information Games

1 Endgame Solving in Large Imperfect-Information Games Sam Ganzfried and Tuomas SandholmComputer Science DepartmentCarnegie Mellon University{sganzfri, leading approach for computing strong game-theoreticstrategies in Large Imperfect-Information Games is to firstsolve an abstracted version of the game offline, then per-form a table lookup during game play. We consider a mod-ification to this approach where we solve the portion of thegame that we have actually reached in real time to a greaterdegree of accuracy than in the initial computation. We callthis approach Endgame Solving . Theoretically, we show thatendgame Solving can produce highly exploitable strategies insome Games ; however, we show that it can guarantee a lowexploitability in certain Games where the opponent is givensufficient exploitative power within the Endgame .}

2 Further-more, despite the lack of a general worst-case guarantee, wedescribe many benefits of Endgame Solving . We present anefficient algorithm for performing Endgame Solving in largeimperfect- information Games , and present a new variance-reduction technique for evaluating the performance of anagent that uses Endgame Solving . Experiments on no-limitTexas Hold em show that our algorithm leads to significantlystronger performance against the strongest agents from the2013 AAAI Annual Computer Poker and Subject [Distributed Artificial Intelligence]: MultiagentSystems; [Social and Behavioral Sciences]: Eco-nomicsGeneral TermsAlgorithms, Economics, TheoryKeywordsGame Theory; Game Solving ; imperfect Information1. INTRODUCTIONS equential Games of perfect information can be solved inlinear time by a straightforward backward induction pro-cedure in which solutions to endgames are propagated up This material is based on work supported by the NationalScience Foundation under grants IIS-1320620, IIS-0964579,and CCF-1101668, as well as XSEDE computing resourcesprovided by the Pittsburgh Supercomputing in:Proceedings of the 14th InternationalConference on Autonomous Agents and MultiagentSystems (AAMAS 2015), Bordini, Elkind, Weiss, Yolum(eds.)

3 , May 4 8, 2015, Istanbul, 2015, International Foundation for Autonomous Agentsand Multiagent Systems ( ). All rights game , this procedure does not workin general in Imperfect-Information Games because differentendgames can contain nodes that belong to the same in-formation set and cannot be treated independently. Moresophisticated algorithms are needed for this class of algorithm for Solving two-player zero-sum Imperfect-Information Games is based on a linear program (LP) for-mulation [14], which scales to Games with around 108nodesin their game tree [7]. Many interesting Games are signifi-cantly larger; for example, two-player limit Texas Hold emhas about 1017nodes, and a popular variant of two-playerno-limit Texas Hold em has about 10165nodes [12]. Toaddress such Large Games , newer approximate equilibrium-finding algorithms have been developed that scale to gameswith around 1014nodes, such as counterfactual regret mini-mization (CFR) [21] and an algorithm based on the excessivegap technique (EGT) [10].

4 These algorithms are iterativeand guarantee convergence to equilibrium in the leading approach for Solving extremely Large gamessuch as Texas Hold em (TH)2is to abstract the game downto a game with only around 1012nodes, then to compute anapproximate equilibrium in the abstract game using one ofthe algorithms described above [2, 7]. In order to performsuch a dramatic reduction in size, significant abstraction isoften (akacard)abstractioninvolvesreducing the number of nodes by bundling signals ( , forc-ing a player to play the same way with two different hands),andaction(akabetting)abstractioni nvolves reducing thenumber of actions by discretizing Large action spaces into asmall number of actions. All of the computation (both forconstructing the abstraction and computing an approximateequilibrium in the abstraction) is done offline, and a tablelookup is performed in real time to implement the consider a modification to this approach where we re-tain the abstract equilibrium strategies for the initial portionof the game tree (called thetrunk), and discard the strate-gies for the final portion (called theendgames).

5 Then, in realtime, we solve the relevant Endgame that we have reached toa greater degree of accuracy than the initial abstract strat-egy, where we use Bayes rule to compute the distribution ofplayers private information leading into the endgames fromthe precomputed trunk strategies. This approach, which wecallendgame Solving , is depicted in Figure present the first theoretical analysis of Endgame solv-1 Prior work has shown that precomputing solutions toendgames offline can be effective in Large perfect-informationgames [1, 18]. In contrast, we solve endgames Appendix A for background on Texas Hold em 1: Endgame Solving (re-)solves the relevantendgame that we have actually reached in real timeto a greater degree of accuracy than in the in Imperfect-Information Games , and show that it can ac-tually produce highly exploitable strategies in some fact, we show that it can fail even in a simple game witha unique equilibrium and a single Endgame , even if our basestrategy were an exact equilibrium (of the full game) and wewere able to compute an exact equilibrium in the , we show that Endgame Solving can guarantee alowexploitability(difference between game value and pay-off against a nemesis) in some Games when the opponent isgiven sufficient exploitative power within the Solving has been used by several prior agentsfor the limit variation of TH (where bets must be of a sin-gle fixed size).

6 The agent GS1 precomputed strategies onlyfor the first two rounds, using rough approximations for thepayoffs at the leaves of that trunk based on the (unrealistic)assumption that there was no betting in future rounds [7].Then in real time, the relevant Endgame consisting of thefinal two rounds was solved using the LP algorithm. GS2precomputed strategies for the first three rounds, using sim-ulations to estimate the payoffs at the leaves; it then solvedthe endgames for the final two rounds in real time [8].However Endgame Solving has not been implemented byany competitive agents for the significantly larger and morechallenging domain of no-limit Texas Hold em (NLTH) priorto our work. We present a new algorithm that is capa-ble of scaling to extremely Large Games such as no-limitTexas Hold em, and incorporates several algorithmic im-provements over the prior approaches (the benefits describedin this paragraph would be improvements over the prior ap-proaches even for the limit variant).

7 First, the prior ap-proaches assume that the private hand distributions lead-ing into the Endgame are independent, while they are ac-tually dependent and the full joint distribution should becomputed. The na ve way of accomplishing this would re-quireO(n2) strategy table lookups, wherenis the numberof private hands (1081 for the final round of poker), andcomputing these distributions would become the bottleneckof the algorithm and make the real-time computation in-tractable; however, we developed a technique for comput-ing the joint distributions that requires justO(n) strategytable lookups. Second, the prior approaches use a singleperfect-recall card abstraction that has been precomputedoffline (which assumes a uniform random distribution forthe opponent s hand distributions).

8 In contrast, we use animperfect-recall card abstraction3that is computed in realtime in a finer granularity than the initial offline abstraction3 imperfect -recall abstractions allow for greater flexibility inwhich hands can be grouped together, and significantly im-prove performance over perfect-recall abstractions [20, 13].and that is tailored specifically to the relevant distributionof the opponent s hands at the given hand history. Further-more, the prior approaches did not compare performancebetween Endgame Solving and not using it (since the basestrategies were not computed for the endgames), while weprovide such a recent work, which appeared subsequently to thefirst version of this work, has presented approaches for de-composing Imperfect-Information Games into smaller gamesthat can be solved independently offline, and provides sometheoretical guarantees on full-game exploitability.

9 One ofthese approaches has only been applied to the small domainof limit Leduc Hold em, which has 936 information sets inits game tree, and is not practical for larger Games such asNLTH due to its running time [3]. A second related (offline)approach includes counterfactual values for game states thatcould have been reached off the path to the endgames [11].This approach has been demonstrated to be effective in limitLeduc Hold em, and has also been implemented in NLTH,though no experimental results are given for that NLTH, it is implemented by first Solving the game ina coarse abstraction, then fixing the strategies for the pre-flop (first) round, and re- Solving for certain endgames start-ing at the flop (second round) after common preflop bet-ting sequences have been played. All of this computation isdone offline.

10 In contrast, our approach enables us to solveendgames at the river (final round) in real time. It is infea-sible to solve the river endgames using the prior approachfor several reasons. First, there are far too many of themto be solved individually in advance (there is a different onefor each sequence of public cards and betting actions). Sec-ond, by the time play gets down to the river, there are manypossible alternative actions that a player could have takento avoid reaching the given Endgame , and counterfactualvalues for each of these would need to be computed andthen included in the solution to the Endgame solver; thiswould likely be infeasible to do in real time. Solving theriver endgames, as opposed to the flop endgames which theprior approach does, is very important because CFR onlyoccasionally samples from a specific river Endgame duringthe course of the initial equilibrium computation, while itvery frequently samples from the flop endgames that followcommon preflop betting sequences.