Sparsified Linear Programming for Zero-Sum Equilibrium Finding
  Computational equilibrium finding in large zero-sum extensive-form
imperfect-information games has led to significant recent AI breakthroughs. The
fastest algorithms for the problem are new forms of counterfactual regret
minimization [Brown and Sandholm, 2019]. In this paper we present a totally
different approach to the problem, which is competitive and often orders of
magnitude better than the prior state of the art. The equilibrium-finding
problem can be formulated as a linear program (LP) [Koller et al., 1994], but
solving it as an LP has not been scalable due to the memory requirements of LP
solvers, which can often be quadratically worse than CFR-based algorithms. We
give an efficient practical algorithm that factors a large payoff matrix into a
product of two matrices that are typically dramatically sparser. This allows us
to express the equilibrium-finding problem as a linear program with size only a
logarithmic factor worse than CFR, and thus allows linear program solvers to
run on such games. With experiments on poker endgames, we demonstrate in
practice, for the first time, that modern linear program solvers are
competitive against even game-specific modern variants of CFR in solving large
extensive-form games, and can be used to compute exact solutions unlike
iterative algorithms like CFR.
