The State of Techniques for Solving Large Imperfect-Information Games, Including Poker

Опубликовано 22 июня 2016, 1:40

The ability to computationally solve imperfect-information games has a myriad of future applications ranging from auctions, negotiations, and (cyber)security settings to medical domains. A dramatic scalability leap has occurred in the capability to solve such games over the last nine years, fueled in large part by the Annual Computer Poker Competition. I will discuss the key, domain-independent, techniques that enabled this leap, including automated abstraction techniques and approaches for mitigating the issues that they raise, new equilibrium-finding algorithms, safe opponent exploitation methods, techniques that use qualitative knowledge as an extra input, and endgame solving techniques. I will also include new results on 1) developing the world’s best Heads-Up No-Limit Texas Hold'em poker program, 2) theory that enables abstraction that gives solution quality guarantees, 3) techniques for hot starting equilibrium finding, 4) simultaneous abstraction and equilibrium finding, and 5) theory that improves gradient-based equilibrium finding. I will also cover the Brains vs AI competition that I recently organized where our AI, Claudico, challenged four of the top-10 human pros in Heads-Up No-Limit Texas Hold'em for 80,000 hands. (The talk covers joint work with many co-authors, mostly Noam Brown, Sam Ganzfried, and Christian Kroer.