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.”