For some poker players, today may be the day they fold their hopes of becoming the best in the world. A team of researchers at the University of Alberta has created a virtually invincible poker-player computer program, dubbed Cepheus.

By playing billions of hands against itself, Cepheus has learned the best strategy for heads-up, limit hold’em – a spin-off of the popular card game Texas hold’em, but with two players (heads-up) and fixed bet sizes (limit). As a result, this poker variant has been essentially solved by the program, meaning it plays an almost perfect game.

Additional Images

University of Alberta researcher Michael Bowling, left, says his team has created a computer program that is very close to unbeatable at heads-up limit hold’em poker. The Associated Press

“Even if you played 60 million hands of poker for 70 years, 12 hours a day, and never made any mistakes, you still wouldn’t be able to say with statistical confidence you were better than this program,” said study author and computer scientist Michael Bowling.

A perfect solution would mean a program would never lose money against an opponent in the long run. Bowling and his colleagues can’t say that about Cepheus, but they know the computer can stay ahead for at least as long as any human can live. The team has even set up a website where visitors can try their hand against the program.

“We’re not quite perfect, but we’re so close that even after a lifetime of playing against it, you wouldn’t know it wasn’t perfect,” Bowling said. The study was published online Thursday in the journal Science.

Perfect solutions have been found for the games checkers and Connect Four, but unlike poker, these are characterized as perfect-information games. In other words, players know everything that has happened in the game before making their move.

“The other games that have been solved in the past – like checkers – are games of perfect information,” said software engineer Eric Jackson, a computer poker hobbyist who was not involved in the research. “Games of imperfect information are harder, and I think it may be surprising to some that they can be solved by computers.”

Heads-up, limit hold’em marks the first imperfect-information game competitively played by humans that has been essentially solved, according to the research. Poker, with its core strategy of bluffing, thoroughly embodies a situation in which players hide information to their advantage.

As with any human player, Cepheus learns through experience, except its only opponent is itself. Even if humans are unable to win against Cepheus, the opportunity to learn from the best is certainly there. For instance, the program proves that the dealer does hold a distinct advantage in the game. Also, raising as the first move as opposed to calling is favorable in the vast majority of situations, since it can cause the opponent to immediately fold.

Although Bowling and his colleagues admittedly create programs like Cepheus for fun, the game can be seen as a stand-in for the imperfect-information stand-offs encountered in the real world. One party versus another, each with conflicting goals, unaware of whether their opponent will strike or stand down.

“You can view the conflict between terrorists on the one hand and homeland security on the other hand as a ‘game’ and use the tools of game theory to try and find strategies for security that are optimal,” Jackson said.

Bowling has even collaborated with diabetes physicians to come up with an algorithm to best treat patients, with the disease being the “opponent” in such a game.

Related Stories