University of Alberta Researchers Solve Heads-Up Fixed-Limit Hold'em
Under the headline "Heads-up limit hold'em poker is solved" in the magazine Science, a team of researchers from the University of Alberta in Edmonton report that their poker-playing artificial intelligence (AI) program, named Cepheus, has solved heads-up fixed-limit Texas hold'em.
Ever since AI became a goal of computer scientists mid-way through the last century, games have been the testing grounds for their progress. Early advances in AI came when computers beat the best human players in the world in "perfect-information" games like checkers or backgammon — games where all of the information is available to all players when making a decision.
A few decades ago, backgammon was immensely popular and was played for large sums of money, like poker, until the game was essentially "solved" — decision-making strategy advanced to a point of perfection and only the randomness of the dice determined the winner.
But AI has only just begun when perfect-information games are solved. The real world is not like those games. The real world that our human intelligence negotiates every day is full of imperfect information.
"Imperfect-information" games like poker — where some of the information (like your opponent's hole cards) is not known when making decisions — are a much tougher nut to crack. Programmers around the world compete at international events like the annual Association for the Advancement of Artificial Intelligence (AAAI) Computer Poker Competition and the Man-Machine Poker Competition to test the capabilities of their latest AI.
The University of Alberta Computer Poker Research Group, headed by Dr. Michael Bowling, have been competing in these events since their inception, and has a nearly two-decade-long history of developing poker-playing AI.
Heads-up fixed-limit Texas hold'em is the poker variant with the least variables. With only a single opponent, two unknown cards in play, and a rigid bet size and number of bets permitted, it is the poker game targeted by AI researchers. It is this game that the Albertan researchers have declared solved by their AI; they are able to compute Nash equilibrium strategy to the point where any player's advantage is "statistically indistinguishable from zero in a human lifetime of played games."
The AI is based on a "regret-minimizing" algorithm. Put simply, when a decision is made that is proven by hindsight to be a less-than-optimal decision, it learns and adjusts. The strategy is "learned" by repeated play between two of these algorithms. This method of determining optimum strategy also means that the AI can adjust to its opponent, making human trickiness only temporarily effective. The AI has already determined optimum decisions against average strategy, so it uses that approach as default and focuses on computing the best response to the current opponent's strategy as the match is played.
The final strategy computed by the University of Alberta AI, Cepheus, is a "close approximation to a Nash equilibrium," and reveals some truths and myths about poker strategy believed to be optimal by human poker players.
We have it ingrained in us that limping preflop is a bad strategy. The AI confirms this. The computed strategy limps only 0.06% of the time, and no hand is limped more than 0.5%.
Cepheus's final strategy also confirms that the player with the button has a "substantial advantage." But, in the dealer position, the AI caps the betting in the first round extremely rarely. Even with pocket aces, the AI caps the betting less than 0.01% of the time, and it is actually pocket twos that are capped in the first round most frequently, at 0.06%.
Also, the AI plays a much wider range of hands out of position than most human players would, and reraises small pairs much more often.
The University of Alberta Computer Poker Research Group was also the brains behind the poker-playing AI named Polaris that made headlines in 2007 when it faced Phil Laak and Ali Eslami in a series of heads-up fixed-limit hold'em matches in front of an audience at a hotel in Vancouver, B.C. The brilliant poker minds played 2,000 total hands against Polaris in four matches. Polaris tied the first round, won the second one, but then lost the last two. The reason for one of the latter losses was attributed to Polaris being switched to a new strategy that attempted to learn and adapt on the fly, which did not prove to be up to the task.
A year later, Polaris was pitted against six poker pros at the Second Man-Machine Poker Championship in Las Vegas where Polaris claimed a victory with a win-loss-tie record of 3-2-1. This AI was far superior to the one tested the year earlier, and now we are a further six and a half years in development and tweaking. It has yet to be proven, but this new program may, in fact, be unbeatable by human players.
To learn more about Cepheus, learn strategy from it, or even play against it, visit this page.