AAAI Publications, Workshops at the Twenty-Seventh AAAI Conference on Artificial Intelligence

Font Size: 
Improving Performance in Imperfect-Information Games with Large State and Action Spaces by Solving Endgames
Sam Ganzfried, Tuomas Sandholm

Last modified: 2013-06-29


Sequential games of perfect information can be solved by backward induction, where solutions to endgames are propagated up the game tree.  However, this does not work in imperfect-information games because different endgames can contain states that belong to the same information set and cannot be treated independently.  In fact, we show that this approach can fail even in a simple game with a unique equilibrium and a single endgame.  Nonetheless, we show that endgame solving can have significant benefits in imperfect-information games with large state and action spaces: computation of exact (rather than approximate) equilibrium strategies, computation of relevant equilibrium refinements, significantly finer-grained action and information abstraction, new information abstraction algorithms that take into account the relevant distribution of players' types entering the endgame, being able to select the coarseness of the action abstraction dynamically, additional abstraction techniques for speeding up endgame solving, a solution to the ``off-tree" problem, and using different degrees of probability thresholding in modeling versus playing. We discuss each of these topics in detail, and introduce techniques that enable one to conduct endgame solving in a scalable way even when the number of states and actions in the game is large. Our experiments on two-player no-limit Texas Hold'em poker show that our approach leads to significant performance improvements in practice.


Game Theory; Game Playing; Imperfect Information; Poker

Full Text: PDF