Solving Imperfect Information Games Using Decomposition

Authors

  • Neil Burch University of Alberta
  • Michael Johanson University of Alberta
  • Michael Bowling University of Alberta

DOI:

https://doi.org/10.1609/aaai.v28i1.8810

Abstract

Decomposition, i.e. independently analyzing possible subgames, has proven to be an essential principle for effective decision-making in perfect information games. However, in imperfect information games, decomposition has proven to be problematic. To date, all proposed techniques for decomposition in imperfect information games have abandoned theoretical guarantees. This work presents the first technique for decomposing an imperfect information game into subgames that can be solved independently, while retaining optimality guarantees on the full-game solution. We can use this technique to construct theoretically justified algorithms that make better use of information available at run-time, overcome memory or disk limitations at run-time, or make a time/space trade-off to overcome memory or disk limitations while solving a game. In particular, we present an algorithm for subgame solving which guarantees performance in the whole game, in contrast to existing methods which may have unbounded error. In addition, we present an offline game solving algorithm, CFR-D, which can produce a Nash equilibrium for a game that is larger than available storage.

Downloads

Published

2014-06-21

How to Cite

Burch, N., Johanson, M., & Bowling, M. (2014). Solving Imperfect Information Games Using Decomposition. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8810

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms