Solving huge sequential imperfect-information games, with application to poker
Can game theory be operationalized to yield effective strategies for extremely large games? I will discuss our work on developing game-independent techniques for solving sequential imperfect information games over the past three years. These techniques have yielded some of the world’s best programs for playing poker. They rival (and in some cases exceed) the skill of the best human players.
I will first discuss automated abstraction algorithms for such games. We developed a lossless abstraction algorithm that enabled us to compute a provably optimal strategy for Rhode Island Hold’em poker, an AI challenge problem introduced by Shi and Littman in 2001. The game has 3.1 billion nodes in the game tree – over four orders of magnitude more than the largest sequential imperfect-information (poker) game solved previously. I will then introduce lossy abstraction algorithms for even larger games. The best of them use clustering together with integer programming, and conduct the abstraction in a potential-aware way rather than myopically (as all prior algorithms did).
The second part of the talk covers algorithms for solving abstracted 2-person 0-sum games, like Heads-Up Texas Hold’em poker. I will present our techniques that enable Nesterov’s excessive gap technique to scale dramatically better – to games with 10^12 nodes. I will also discuss our new iterated smoothing algorithm that provably has exponentially better convergence.
Finally, I will discuss our algorithms for solving huge multi-player stochastic games. Using them we computed an epsilon-equilibrium for 3-player jam/fold Texas Hold’em tournaments.
Different parts of this research are joint work with Andrew Gilpin, Sam Ganzfried, Javier Pena, Troels Bjerre Soerensen, and Sam Hoda.
Speaker Bio
Tuomas Sandholm is Professor in the Computer Science Department at CMU. He received the Ph.D. and M.S. degrees in computer science from UMass Amherst in 1996 and 1994. He earned an M.S. (B.S. included) with distinction in Industrial Engineering and Management Science from the Helsinki University of Technology, Finland, in 1991. He has published over 300 papers on electronic commerce; game theory; artificial intelligence; multiagent systems; auctions and exchanges; automated negotiation and contracting; coalition formation; voting; safe exchange; normative models of bounded rationality; resource-bounded reasoning; machine learning; networks; and combinatorial optimization. Several of his systems have been fielded. He is also Founder, Chairman, and Chief Scientist of CombineNet, Inc., which has commercialized over 500 large-scale generalized combinatorial auctions, with over $40 billion in total spend and over $5 billion in generated savings. He is recipient of the NSF Career Award, the inaugural Autonomous Agents Research Award, the Sloan Fellowship, and the Computers and Thought Award. He is well known for being a weak poker player.