New Results on Algorithms for Creating Game-Theoretic Strategies for Large Incomplete-Information Games

Incomplete-information games - such as most auctions, negotiations, and future (cyber)security settings - cannot be solved using minimax search even in principle.  Completely different algorithms are needed.  A dramatic scalability leap has occurred in our ability to solve such games over the last eight 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 include brand new results on 1) developing Tartanian7, the world’s leading no-limit Texas Hold’em program, 2) theory that enables abstraction that gives solution quality guarantees, 3) techniques for hot starting the equilibrium finding, 4) simultaneous abstraction and equilibrium finding, 5)  theory that improves gradient-based equilibrium finding. The talk covers joint work with many co-authors, mostly Sam Ganzfried, Noam Brown, and Christian Kroer.