`

Timezone: »

 
Poster
Solving Large Sequential Games with the Excessive Gap Technique
Christian Kroer · Gabriele Farina · Tuomas Sandholm

Wed Dec 05 07:45 AM -- 09:45 AM (PST) @ Room 210 #77
in Wed Poster Session A »

There has been tremendous recent progress on equilibrium-finding algorithms for zero-sum imperfect-information extensive-form games, but there has been a puzzling gap between theory and practice. First-order methods have significantly better theoretical convergence rates than any counterfactual-regret minimization (CFR) variant. Despite this, CFR variants have been favored in practice. Experiments with first-order methods have only been conducted on small- and medium-sized games because those methods are complicated to implement in this setting, and because CFR variants have been enhanced extensively for over a decade they perform well in practice. In this paper we show that a particular first-order method, a state-of-the-art variant of the excessive gap technique---instantiated with the dilated entropy distance function---can efficiently solve large real-world problems competitively with CFR and its variants. We show this on large endgames encountered by the Libratus poker AI, which recently beat top human poker specialist professionals at no-limit Texas hold'em. We show experimental results on our variant of the excessive gap technique as well as a prior version. We introduce a numerically friendly implementation of the smoothed best response computation associated with first-order methods for extensive-form game solving. We present, to our knowledge, the first GPU implementation of a first-order method for extensive-form games. We present comparisons of several excessive gap technique and CFR variants.

Keywords: Game Theory and Computational Economics
[ Paper] 

Author Information

Christian Kroer (Faceook, Core Data Science)
Gabriele Farina (Carnegie Mellon University)
Tuomas Sandholm (Carnegie Mellon University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors