Potential-aware automated abstraction of sequential games, and holistic equilibrium analysis of Texas Hold’em poker

We present a new automated abstraction algorithm for sequential imperfect information games. While most prior automated abstraction algorithms employ a myopic expected-value computation as a similarity metric, our algorithm considers a higher-dimensional space consisting of histograms over abstracted classes of states from later stages of the game. This enables our bottom-up abstraction algorithm to automatically take into account positive and negative potential. We further improve the abstraction quality by making multiple passes over the abstraction, enabling the algorithm to narrow the scope of analysis to information that is relevant given abstraction decisions made for earlier parts of the game. We also present a custom indexing scheme based on suit isomorphisms that enables one to work on significantly larger games than before. We apply the techniques to heads-up limit Texas Hold’em poker. Whereas all prior game theory-based work for Texas Hold’em poker used generic off-the-shelf linear program solvers for the equilibrium analysis of the abstracted game, we make use of a recently developed algorithm based on the excessive gap technique from convex optimization. This paper is, to our knowledge, the first to abstract and game-theoretically analyze all four betting rounds in one run (rather than splitting the game into phases). The resulting player beats the prior leading poker programs (GS2, Sparbot, and Vexbot) with statistical significance.