A Practical Use of Imperfect Recall


Kevin Waugh, Martin Zinkevich, Michael Johanson, Morgan Kan, David Schnizlein and Michael Bowling. A Practical Use of Imperfect Recall. In Proceedings of the Eighth Symposium on Abstraction, Reformulation and Approximation (SARA), 2009.

Download


Abstract

Perfect recall is the common and natural assumption that an agent never forgets. As a consequence, the agent can always condition its choice of action on any prior observations. In this paper, we explore relaxing this assumption. We observe the negative impact this relaxation has on algorithms: some algorithms are no longer well-defined, while others lose their theoretical guarantees on the quality of a solution. Despite these disadvantages, we show that removing this restriction can provide considerable empirical advantages when modeling extremely large extensive games. In particular, it allows fine granularity of the most relevant observations without requiring decisions to be contingent on all past observations. In the domain of poker, this improvement enables new types of information to be used in the abstraction. By making use of imperfect recall and new types of information, our poker program was able to win the limit equilibrium event as well as the no-limit event at the 2008 AAAI Computer Poker Competition. We show experimental results to verify that our programs using imperfect recall are indeed stronger than their perfect recall counterparts.

Notes

This paper introduces imperfect recall abstractions, which we started using in 2008 for the Annual Computer Poker Competition and the Second Man-vs-Machine Poker Championship matches. All known efficient game solving algorithms rely on an assumption of perfect recall in their convergence proofs. Perfect recall simply means that an agent never forgets information that it has observed, even if that information later becomes irrelevant. It means that from an agent's point of view, the game forms a tree, and once it has observed something all of its later decisions are dependent on that observation.


Imperfect recall is a generalization that allows for information to be forgotten, so that information sets can be made to merge back together. This means that the agent can observe the game as a directed acyclic graph instead of strictly as a tree. While game solving algorithms such as CFR are no longer guaranteed to converge, the algorithm remains well defined and we can still attempt to run it. In practice, imperfect recall abstractions can be used to generate strategies that perform better than perfect recall abstractions. This is because imperfect recall allows us to forget irrelevant information, and spend our resources (such as memory or CPU-time) on better representing more critical -- which often means most recent -- information in the game.


Links


BibTeX

@InProceedings( 2009-sara-imperfect-recall,
  Title = "A Practical Use of Imperfect Recall",
  Author = "Kevin Waugh and Martin Zinkevich and Michael Johanson and Morgan Kan and David Schnizlein and Michael Bowling",
  Booktitle = "Proceedings of the Eighth Symposium on Abstraction, Reformulation and Approximation (SARA)",
  Year = "2009",
  Pages = "175--182",
  AcceptRate = "62\%",
  AcceptNumbers = "27 of 37"
)