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), pp. 175–182, 2009.
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.
@InProceedings(09sara, 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" )