A University of Alberta research group headed by SCS alumnus Michael Bowling reports in the January 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.