Friday, April 24, 2015
Brains Vs. Artificial Intelligence: Carnegie Mellon Computer Faces Poker Pros in Epic No-Limit Texas Hold’Em Competition
80,000 Hands Will Be Played in Two-week Contest at Rivers Casino in Pittsburgh
In a contest that echoes Deep Blue’s chess victory over Garry Kasparov and Watson beating two Jeopardy! Champions, computer poker software developed at Carnegie Mellon University will challenge four of the world’s best professional poker players in a “Brains Vs. Artificial Intelligence” competition beginning April 24 at Rivers Casino.
Over the course of two weeks, the CMU computer program, Claudico, will play 20,000 hands of Heads-Up No-limit Texas Hold’em with each of the four poker pros. The pros — Doug Polk, Dong Kim, Bjorn Li and Jason Les — will receive appearance fees derived from a prize purse of $100,000 donated by Microsoft Research and by Rivers Casino. The Carnegie Mellon scientists will compete for something more precious.
“Poker is now a benchmark for artificial intelligence research, just as chess once was,” said Tuomas Sandholm, a professor of computer science at Carnegie Mellon who has led development of Claudico. “It’s a game of exceeding complexity that requires a machine to make decisions based on incomplete and often misleading information, thanks to bluffing, slow play and other decoys. And to win, the machine has to out-smart its human opponents.
“Computing the world’s strongest strategies for this game was a major achievement — with the algorithms having future applications in business, military, cybersecurity and medical arenas,” Sandholm said.
Though an earlier version of the computer program, called Tartanian7, decisively won the Heads-Up, No-limit Texas Hold’em category of the Association for the Advancement of Artificial Intelligence’s Annual Computer Poker Competition last July, Sandholm said that doesn’t mean it necessarily is the equal of human players. Computers have demonstrated they can outplay humans at the simpler game of Heads-Up Limit Texas Hold’em, he noted, but not the far more complicated no-limit version.
“I think it’s a 50-50 proposition,” he said of Claudico’s chances. “I think there’s a good chance we’ll lose this thing.”
“I imagine that the humans have an edge here,” Polk said, citing the extraordinary programming challenge for a no-limit game. “However, it is very difficult to determine an outcome with any sort of stability, as I do not know what I am going to be up against.”
Polk is widely considered the world’s best player of Heads-Up No-Limit Texas Hold’em, with total live tournament earnings of more than $3.6 million. Kim, Li and Les are also among the Top 10 players in the professional game, which is largely played online.
“My strategy will change more so than when playing against human players,” Polk added. “I think there will be less hand reading so to speak, and less mind games. In some ways I think it will be nice as I can focus on playing a more pure game, and not have to worry about if he thinks that I think, etc. So I am looking forward to the match.”
“Rivers Casino is proud to partner with the number-one graduate school of computer science in the U.S., Carnegie Mellon University, right here in our own backyard,” said Craig Clark, general manager of Rivers Casino. “Regardless of whether man or machine prevails, this history-making experiment is a great win for Pittsburgh.”
The competition has been designed to ensure that the outcome is scientifically significant and not a result of luck. In addition to the large number of hands, the players will be paired to play duplicate matches — Player A will receive the same cards as the computer receives against Player B, and vice versa. One of the human players will be in isolation, to prevent any comparison of the cards. The same arrangement applies to Players C and D.
Play will proceed in two 750-hand sessions per day for 13 days over a two-week period, with one day set aside so the human players can rest.
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.
More information is available at https://www.cs.cmu.edu/brains-vs-ai.
The competition continues Carnegie Mellon’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.
The site of the competition, Pittsburgh’s Rivers Casino, opened in 2009 and has been named “Best Overall Gaming Resort in Pennsylvania” for five consecutive years by Casino Player Magazine. No one under age 21 is permitted on casino property.