Solving Imperfect Information Games Using Decomposition

Decomposition, i.e., independently analyzing possible subgames, hasproven to be an essential principle for effective decision-making inperfect information games. However, in imperfect information games,decomposition has proven to be problematic. To date, all proposedtechniques for decomposition in imperfect information games haveabandoned theoretical guarantees. This work presents the firsttechnique for decomposing an imperfect information game into subgamesthat can be solved independently, while retaining optimalityguarantees on the full-game solution. We can use this technique toconstruct theoretically justified algorithms that make better use ofinformation available at run-time, overcome memory or disk limitationsat run-time, or make a time/space trade-off to overcome memory or disklimitations while solving a game. In particular, we present analgorithm for subgame solving which guarantees performance in thewhole game, in contrast to existing methods which may have unboundederror. In addition, we present an offline game solving algorithm,CFR-D, which can produce a Nash equilibrium for a game that is largerthan available storage.