Thursday, January 8, 2015
Solution to Simplest Poker Game Is Just the Beginning
CMU's Sandholm Says Solving Imperfect-Information Games Has Applications in Business, Medicine, Security
By Byron Spice / 412-268-9068
A University of Alberta research group, headed by Carnegie Mellon University School of Computer Science (SCS) alumnus Michael Bowling, reports in the Jan. 9 issue of Science that it has essentially solved the game of two-player limit Texas Hold'em poker, which CMU's Tuomas Sandholm says marks a significant milestone in solving imperfect-information games.
In a Perspectives article also published by Science, Sandholm noted that tremendous progress has been made in the last 10 years in solving imperfect-information games, in which players must make decisions despite not having all of the information they might need or want.
Though two-player limit Texas Hold'em is among the simplest of poker games, the strategy developed by Bowling's group "is so close to optimal that, at the pace a human plays poker, it cannot be beaten with statistical significance in a lifetime," Sandholm wrote. "This is, to my knowledge, the largest imperfect-information game essentially solved to date, and the first one competitively played by humans that has now been essentially solved."
Sandholm, professor of computer science, is an active researcher in this area, developing poker programs that compete in the Annual Computer Poker Competition at the Association for the Advancement of Artificial Intelligence conference. This summer, at the AAAI meeting in Quebec, his Tartanian7 decisively beat all competitors in two-player, no-limit Texas Hold'em, a more complex and popular poker game than the one solved by the Alberta group. Ph.D. students Noam Brown and Sam Ganzfried were part of that successful team.
Bowling, who earned his Ph.D. in computer science in 2003, likewise has been a pioneer in computer poker research.
In contrast to computer chess, a perfect-information game that long was a benchmark for AI research, imperfect-information games mirror the types of decisions that people routinely need to make. Progress in this area, fueled by challenges such as the Annual Computer Poker Competition, Sandholm said, lead to the ability to solve detailed game models.
This has applications in business, including auctions and negotiations; in medicine, such as in making sophisticated sequential plans for disease treatments at the individual or population levels; and in fields such as cybersecurity. Sandholm's research group already has worked on applications in each of these areas.
In his article, Sandholm noted that much work is still required for larger imperfect-information games. One area of inquiry is learning how to take advantage of an opponent's poor play without also opening oneself to exploitation in return. Another area is non-zero-sum games and games with more than two players; Sandholm said these games are so complex that it is not clear that achieving a Nash equilibrium is even the right goal for these games, as it is for two-player poker games.
Carnegie Mellon's Tuomas Sandholm (pictured above) says solving imperfect-information games has applications in business, medicine and security.