Super-Human AI for Strategic Reasoning

August 14, 2018
Tuomas Sandholm

Poker has been a challenge problem in game theory, operations research, and artificial intelligence for decades. As a game of imperfect information, it involves obstacles not present in games like chess and go, and requires totally different techniques. In 2017, our AI, Libratus, beat a team of four top specialist pros in the main benchmark for imperfect-information game solving, heads-up no-limit Texas hold’em, which has 10^161 decision points. This was the first time AI has beaten top players in a very large poker game. Libratus is powered by new algorithms in each of its three main modules: 1) computing approximate Nash equilibrium strategies before the event (i.e., computing a blueprint strategy for the entire game), 2) safe nested endgame solving during play (i.e., refining the blueprint strategy on the fly in parts of the game that are reached while preserving guarantees on exploitability), and 3) fixing its own strategy to play even closer to equilibrium based on what holes opponents have tried to identify and exploit. The algorithms are domain independent and have applicability to video games, strategic pricing, finance, negotiation, business strategy, strategic market segmentation, sports, investment banking, strategic product portfolio optimization, electricity markets, bidding, auction design, acquisition strategy (e.g., for streaming companies to acquire movies), political campaigns, cybersecurity, physical security, military, bot detection, and steering evolution and biological adaptation (such as for medical treatment planning and synthetic biology). The Libratus part of this talk is joint work with my PhD student Noam Brown.

登壇者詳細

Tuomas Sandholm has published over 450 papers. 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 auctions, with over $60 billion in total spend and over $6 billion in generated savings. He is Founder and CEO of Optimized Markets, which is bringing a new optimization-powered paradigm to advertising campaign sales, scheduling, and pricing—in TV (linear and nonlinear), streaming (video and audio), display, mobile, game, and cross-media advertising. His algorithms also run the UNOS kidney exchange, which includes 69% of the transplant centers in the US. He has developed the leading algorithms for several general classes of game. The team that he leads is the multi-time world champion in computer Heads-Up No-Limit Texas Hold’em. He is Founder and CEO of Strategic Machine and Strategy Robot, which provide solutions for strategic reasoning under imperfect information in a broad range of applications. He served as the redesign consultant of Baidu’s sponsored search auctions and display advertising markets 2009-2013; within two years Baidu’s market cap increased 5x to $50 billion due to doubled monetization per user. He has served as consultant, advisor, or board member for Yahoo!, Google, Chicago Board Options Exchange, swap.com, Granata Decision Systems, and others. He holds a Ph.D. and M.S. in computer science and a Dipl. Eng. with distinction in Industrial Engineering and Management Science. Among his many honors are the IJCAI Computers and Thought Award, inaugural ACM Autonomous Agents Research Award, Allen Newell Award for Research Excellence, Sloan Fellowship, Carnegie Science Center Award for Excellence, Edelman Laureateship, and NSF Career Award. He is Fellow of the ACM, AAAI, and INFORMS. He holds an honorary doctorate from the University of Zurich.