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

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.

Speaker Bios

Tuomas Sandholm is Professor at Carnegie Mellon University in the Computer Science Department, with affiliate professor appointments in the Machine Learning Department, Ph.D. Program in Algorithms, Combinatorics, and Optimization (ACO), and CMU/UPitt Joint Ph.D. Program in Computational Biology. He is the Founder and Director of the Electronic Marketplaces Laboratory. He has published over 450 papers on market design, optimization (search and integer programming, combinatorial optimization, stochastic optimization, and convex optimization), game theory, AI, auctions, exchanges, advertising markets, computational advertising, kidney exchange, prediction markets, (automated) market making, automated negotiation, preference elicitation, game solving, equilibrium finding, opponent modeling/exploitation, voting, coalition formation, normative models of bounded rationality, resource-bounded reasoning, privacy, safe exchange, multiagent learning, machine learning, and networks. He has 26 years of experience building optimization-powered electronic marketplaces, and has fielded several of his systems. In parallel with his academic career, he was Founder, Chairman, and CTO/Chief Scientist of CombineNet, Inc. from 1997 until its acquisition in 2010. During this period the company commercialized over 800 of the world’s largest-scale generalized combinatorial multi-attribute auctions, with over 60 billion in total spend and over 6 billion in generated savings. Dr. Sandholm’s algorithms run the UNOS kidney exchange, which includes 143 transplant centers. He is Founder and CEO of Optimized Markets, Inc., a startup that is bringing a new paradigm to advertising campaign sales, inventory allocation, and scheduling—in TV, streaming, display, radio, mobile, game, and cross-media advertising. He also served as the redesign consultant of Baidu’s sponsored search auctions and display advertising markets; within two years Baidu’s market cap increased 5x due to better monetization. He has served as consultant, advisor, or board member for Yahoo!, Google, Chicago Board Options Exchange, swap.com, Granata Decision Systems, and others. He has developed the leading algorithms for several general classes of game; for example, they won the most recent world championships in computer Heads-Up No-Limit Texas Hold’em. He holds a Ph.D. and M.S. in computer science and a Dipl. Eng. (M.S. with B.S. included) with distinction in Industrial Engineering and Management Science. Among his many honors are the inaugural ACM Autonomous Agents Research Award, Computers and Thought Award, Edelman Laureateship, Sloan Fellowship, NSF Career Award, and Carnegie Science Center Award for Excellence. He is Fellow of the ACM, AAAI, and INFORMS.