Abstraction for Solving Large Incomplete-Information …

1 Abstraction for Solving Large Incomplete-Information GamesTuomas SandholmComputer Science DepartmentCarnegie Mellon UniversityAbstractMost real-world games and many recreational gamesare games of incomplete information . Over the lastdozen years, Abstraction has emerged as a key enablerfor Solving Large Incomplete-Information games . First,the game is abstracted to generate a smaller, abstractgame that is strategically similar to the original , an approximate equilibrium is computed inthe abstract game. Third, the strategy from the abstractgame is mapped back to the original this paper, I will review key developments in thefield. I present reasons for abstracting games , and pointout the issue of Abstraction pathology. I then review thepractical algorithms for information Abstraction and ac-tion Abstraction . I then cover recent theoretical break-throughs that beget bounds on the quality of the strategyfrom the abstract game, when measured in the originalgame.

2 I then discuss how to reverse map the opponent saction into the Abstraction if the opponent makes a movethat is not in the Abstraction . Finally, I discuss other top-ics of current and future real-world games (such as auctions, negotiation set-tings, security games , cybersecurity games , and medicalgames) and many recreational games are games of incom-plete information . Over the last dozen years, abstractionhas emerged as a key enabler for Solving Large Incomplete-Information games . For instance, it has become an essentialtool in the arsenal of the leading teams working on buildingprograms for playing a high level, the process works in three stages, see Fig-ure 1. First, the game is abstracted to generate a smaller, ab-stract game that is strategically similar to the original , the abstract game is solved for (near-) , the strategy from the abstract game is mapped backto the original to abstract gamesDepending on the setting, there can be different motivationsfor using Abstraction on games :Copyrightc 2015, Association for the Advancement of ArtificialIntelligence ( ).

3 All rights equilibrium Nash equilibrium Original game Abstracted game Abstraction algorithm Custom algorithm for finding a Nash equilibrium Reverse model Figure 1: Framework for abstracting games . The original game may be too Large to solve for equilib-rium with today s technology. This is the case, for exam-ple, in heads-up ( , two-player) Texas Hold em poker even though the game is a two-player zero-sum game, andsuch games can be solved in polynomial time in the sizeof the game tree. The original game tree would simply beprohibitively Large (Johanson 2013). The equilibrium solver may require a simpler game classthan what the original game is. For example, it may re-quire a game with discrete actions and/or states. Or, anequilibrium might not even be known to exist in the origi-nal game class. This has been pointed out as a motivationto abstract, for example, in computer billiards (Archibaldand Shoham 2009).

4 The original game is too difficult or too Large to writedown in full detail so Abstraction is needed in modeling. This is the case typically in empirical game the-ory (Wellman 2006; Wellman et al. 2005) where thegame is not given explicitly but rather access to thegame is by taking part in a simulation, for example atrading agents simulation. All modeling of real-world settings as games can bethought of as Abstraction . Thus it is important to haveresults that tie the Abstraction coarseness to solutionquality for example, regret of the computed strategywhen evaluated in the original game. Otherwise, wecould not know what our game models really have tosay about is game Abstraction , really?At its core, game Abstraction amounts to assuming restric-tions on the players strategy spaces. The most commonform of game Abstraction isinformation Abstraction , whereinformation states are bundled together.

5 Another commonform of game Abstraction isaction Abstraction , where someof the actions in the real game are assumed not to be example, if the original game has a continuum of possi-ble actions (or a prohibitively Large set of possible discreteactions) at some information sets in the game, action ab-straction would create a model where typically only a smalldiscrete set of actions is Abstraction has challenges that do notarise when using Abstraction in single-agentsettingsAbstraction in games is fundamentally different and morechallenging than Abstraction in single-agent settings (suchas Markov Decision Processes). In games , unlike in single-agent settings, Abstraction can be nonmonotonic, that is,pathological. Strategies computed in a fine-grained abstrac-tion can be worse when evaluated in the original game thanthose computed in a strictly coarser Abstraction (Waugh etal.)

6 2009a). Essentially this can happen because we assumeour opponent plays within the restricted strategy set that theabstraction affords him, but in reality he may use a strategythat falls outside our abstract nonmonotonicity has cast doubt on the entire ab-straction approach for games . There has been a significantamount of experimental work on Abstraction in games overthe last dozen years, and experience suggests that in prac-tice in Large games such as heads-up Texas Hold em poker,finer-grained abstractions yield programs that play betteragainst other programs. Furthermore, it has been shown ex-perimentally in heads-up limit Texas Hold em poker thatfiner-grained abstractions yield programs that have lowerexploitability that is, they play better against their worst-case opponent (Johanson et al. 2011). Over the last twoyears, theoretical breakthroughs have finally been madethat tie Abstraction choices to solution quality in the origi-nal game (Sandholm and Singh 2012; Lanctot et al.

7 2012;Kroer and Sandholm 2014a; 2014b).The state of practical game abstractionmethodologyIn this section I will review the state of practical abstractionmethodology. In the following section I will review recenttheoretical abstractionInitially, game abstractions were created by hand, us-ing domain-dependent knowledge (Shi and Littman 2002;Billings et al. 2003). The last eight years have witnessed theadvent of work in game Abstraction algorithms (Gilpin andSandholm 2006; 2007b; Zinkevich et al. 2007). Through-out that period, important experimental advances have beenmade (Gilpin and Sandholm 2007a; Gilpin, Sandholm, andS rensen 2007; 2008; Waugh et al. 2009b; Schnizlein,Bowling, and Szafron 2009; Johanson et al. 2013; Ganzfriedand Sandholm 2013; 2014).Early work on lossless Abstraction enabled the solutionof Rhode Island Hold em, an AI challenge problem billion nodes in the game tree (Gilpin and Sandholm2007b).

8 When moving to even bigger games , lossless ab-straction typically yields abstract games that are too Large tosolve, so lossy Abstraction is brief, the main ideas for practical lossy information ab-straction in games have included the following. Using integer programming to optimize the Abstraction (typically within one level of the game at a time) (Gilpinand Sandholm 2007a). Potential-awareabstraction, where the information sets ofa player at a given level of the game tree are not bucketedbased on some measure such as strength of a poker hand,but rather by the probability vector of transitions to statebuckets at the next level (Gilpin, Sandholm, and S rensen2007). Imperfect-recallabstraction, where a player is forced toforget some detail that he knew earlier in the game so as tobe able to computationally afford a more refined partitionof more recent information (Waugh et al.)

9 2009b).The currently leading practical algorithm for information ab-straction uses a combination of the latter two ideas and obvi-ates the first (Ganzfried and Sandholm 2014). Using abstrac-tion that divides the game disjointly across multiple bladesof a supercomputer for equilibrium-finding computation,strong strategies have been constructed for heads-up no-limit Texas Hold em (with stacks 200 big blinds deep as inthe Annual Computer Poker Competition (ACPC)) (Brown,Ganzfried, and Sandholm 2014; 2015). That original gamehas10165nodes in the game tree (Johanson 2013).Action abstractionAction Abstraction remained a manual endeavor for muchlonger than information Abstraction . The last four years havewitnessed the emergence of automated action Abstraction tocomplement techniques in automated information abstrac-tion. The first techniques iteratively adjusted the action dis-cretization (bet sizing in no-limit poker) (Hawkin, Holte, andSzafron 2011; 2012).

10 Recently, iterative methods have beenintroduced to do this in a way that guarantees convergenceto the optimal discretization (assuming the problem is con-vex) (Brown and Sandholm 2014).Action Abstraction algorithms have also been developedbased on discrete optimization: selecting a small set of pro-totypical actions to allow from the original discrete set ofactions (Sandholm and Singh 2012). Both an integer pro-gramming algorithm and a greedy algorithm was , those algorithms are only for stochastic games andare not scalable theoretical breakthroughsSince 2011, there have been significant theoretical break-throughs in game Abstraction . In brief, despite abstractionpathologies these results tie the fineness of Abstraction tobounds on how good the strategy derived from the abstractgame is in the original and Gatti (2011) give bounds for the specialgame class of Patrolling Security games .