Solving imperfect information games using decomposition
- Neil Burch, Department of Computing Science, University of Alberta
- Michael Johanson, University of Alberta
- Michael Bowling, University of Alberta
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.
Citation
N. Burch, M. Johanson, M. Bowling. "Solving imperfect information games using decomposition". National Conference on Artificial Intelligence (AAAI), (ed: Carla E. Brodley, Peter Stone), pp 602-608, July 2014.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Burch+al:AAAI14,
author = {Neil Burch and Michael Johanson and Michael Bowling},
title = {Solving imperfect information games using decomposition},
Editor = {Carla E. Brodley, Peter Stone},
Pages = {602-608},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 2014,
}Last Updated: October 29, 2020Submitted by Sabina P
