Solving Large Sequential Games with the Excessive Gap Technique

Christian Kroer, Gabriele Farina, Tuomas Sandholm

Abstract

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.

Bibtex entry

@inproceedings{Kroer18:Solving, title={Solving Large Sequential Games with the Excessive Gap Technique}, author={Kroer, Christian and Farina, Gabriele and Sandholm, Tuomas}, booktitle={Conference on Neural Information Processing Systems (NIPS)}, year={2018} }

Download

Paper PDF

Typo or question?

Get in touch!
gfarina AT cs.cmu.edu

Metadata

Venue: NeurIPS 2018
Topic: Decision Making, Optimization, and Computational Game Theory