Solving Imperfect Information Games Using Decomposition

Neil Burch, Michael Johanson, and Michael Bowling. Solving Imperfect Information Games Using Decomposition. In Proceedings of the Twenty-Eighth Conference on Artificial Intelligence (AAAI), pp. 602–608, 2014.




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.


  Title = "Solving Imperfect Information Games Using Decomposition",
  Author = "Neil Burch and Michael Johanson and Michael Bowling",
  Booktitle = "Proceedings of the Twenty-Eighth Conference on Artificial Intelligence (AAAI)",
  Pages = "602--608",
  Year = "2014",
  AcceptRate = "28\%",
  AcceptNumbers = "398 of 1406"

Generated by (written by Patrick Riley) on Fri Feb 13, 2015 15:54:26