A group of researchers from the University of Alberta have created an unbeatable poker program that they say marks a milestone in artificial intelligence and game theory.
“AI researchers have a long, long history of using games as a test bed for our artificial intelligence research,” said Michael Johanson, Ph.D. student in the department of computer science at the University of Alberta. “From a technical standpoint, games are nice well-defined problems, divided into specific situations, with specific actions that can be taken, with specific rewards for the players at the end of the game.”
The program, Cepheus, plays an essentially perfect game of heads-up limit Texas Hold ‘em poker.
“Even if a human opponent knew the perfect counter-strategy to Cepheus, they could spend an entire lifetime playing against it: 200 games per hour, 12 hours per day, nonstop for 70 years, for 60 million games total, and, due to the impact of luck, they would still not have statistical confidence that they were winning at the end,” said Johanson.
Cepheus marks such a breakthrough in artificial intelligence because it is the first time a computer program has solved a non-trivial human game that involves imperfect information, according to Johanson. Previous games where computer programs have exceeded human play have been limited to “two-player deterministic perfect information games,” he said, with chess and checkers being prominent examples. “Deterministic meaning that there is no random chance, and perfect information because the players can all observe everything there is to know about the state of the game.
“But the real-life scenarios, where we would like to eventually apply AI techniques, are not like this. In real-life situations, we are frequently confronted with multiple other players, we can’t predict exactly what will happen in the future, and some events appear random or unpredictable to us, and most importantly, we must constantly cope with uncertainty.”
According to Johanson, there are two important milestones to reach when studying artificial intelligence for games: The first time a program beats the world’s best human players at a game, and the first time a program plays a game perfectly so that it will never lose to any opponent.
“We achieved the first goal in 2008 when our earlier program, Polaris, defeated a team of heads-up limit Texas Hold ’em specialists,” said Johanson. “And we have now achieved the second goal as well, as Cepheus now plays the game very nearly perfectly.”
The researchers’ CFR algorithm, along with an extension of CFR (CFR+) developed by Finnish software developer Oskari Tammelin, powers Cepheus. According to Johanson, CFR is a self-play algorithm, allowing it to constantly play games against itself and improve its strategy.
“CFR+ is a breakthrough, as it learns to play the game far faster than what were the state-of-the-art algorithms just months ago,” he said. “While CFR+ took just under 1,000 CPU years to learn to play, we estimate that older algorithms might have taken 10,000 CPU years or more.” (A CPU year is 8,760 GFLOPS.)
The next step for the researchers is to take the technology inside Cepheus, such as the CFR+ algorithm, and apply it to different problems.
“Other poker games, such as no-limit Texas Hold ’em (the game most commonly shown on TV), offer new challenges, and we expect to be able to use CFR+ to greatly leap ahead of where we are now,” said Johanson.
In addition, the researchers envision applications outside the realm of games, like homeland security.
“The same things that we think about in poker—minimizing our mistakes when faced with an adversary seeking to attack us—are also present for problems such as for planning security and patrolling schedules for airports,” said Johanson.
More information about Cepheus is available here.
