Fall 2015

The State of Techniques for Solving Large Imperfect-Information Games

Wednesday, November 18th, 2015 1:30 pm2:10 pm

Add to Calendar

The ability to computationally solve imperfect-information games has a myriad of future applications ranging from auctions, negotiations, and (cyber)security settings to guiding evolution and adaptation in 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. Time permitting, I will 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 warm starting equilibrium finding, 4) simultaneous abstraction and equilibrium finding, 5) lossless tree pruning algorithms for incomplete-information settings, and 6) theory that improves prior best gradient-based equilibrium-finding algorithms. 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.