Poker AI: Can a Super Computer Beat 4 Top Pros?
80,000 hands of Heads-Up No-limit Texas Hold'em will be played in a two-week contest. Who will come out on top?
Sandholm said imperfect information games such as poker are tremendously difficult because each player must reason what the opponent’s actions signal about the opponent’s cards and what the player’s own actions signal to the opponent. A no-limit game, in which players may bet or raise any amount up to all their chips, adds even greater complexity.
Two-player no-limit Hold’em, Sandholm said, has 10161 (1 followed by 161 zeroes) situations, or information sets, that a player may face —vastly more than all of the atoms in the universe. By contrast, the easier game of limit Hold’em, in which bets and raises are limited to a pre-determined amount, has only 1013 (1 followed by 13 zeroes) information sets.
A computer poker group at the University of Alberta, headed by CMU alumnus Michael Bowling, reported earlier this year in the journal Science that it has near-optimally solved that simpler game.
To tackle the tougher no-limit version, Claudico was built using algorithms that analyzed the basic rules of poker to devise a winning strategy, rather than try to encode the tricks and strategies of human experts. “Claudico” is Latin for “limp.” In poker, limping means to get into a hand by calling, rather than raising or folding. Humans generally dismiss limping as bad strategy, but Claudico embraces it.
“The pros may find that playing Claudico is like playing a Martian,” said Sandholm, noting limping is just one of the ways the computer differs from human players.
Even an abstracted version of the no-limit game was so large that it necessitated that Sandholm and his Ph.D. students, Sam Ganzfried and Noam Brown, use the Pittsburgh Supercomputing Center’s Blacklight supercomputer to compute Claudico’s strategy. Blacklight has a huge amount of random access memory – 16 trillion bytes, or roughly 8,000 times more than the most powerful tablet computers. Though Claudico will run on a CMU computer as it plays the pros, it will use Blacklight during the event to continuously improve its strategy.
The competition continues CMU’s pioneering research in artificial intelligence, which began with the creation of the first AI program, Logic Theorist, in 1956. The top-ranked School of Computer Science includes the world’s first Machine Learning Department and some of the world’s leading scientists in computational game theory, market design, natural language processing, computer vision, speech translation, thought identification and collaboration among intelligent agents.
During the 1970s and ‘80s, Hans Berliner, then a CMU senior research scientist, worked on a series of chess-playing machines, including Hitech, which in 1985 was the first to achieve the rank of senior master. In the late ‘80s, three CMU grad students, Feng-hsiung Hsu, Murray Campbell and Thomas Anantharaman, developed a faster chess machine, ChipTest. When IBM hired the trio, ChipTest evolved into Deep Blue, which finally beat Kasparov in 1997.
IBM’s Watson, which beat Jeopardy champions Brad Rutter and Ken Jennings in 2011, benefited from the contributions of Eric Nyberg and his students in SCS’s Language Technologies Institute.