U. of Alberta Researchers Claim Solution to Heads-Up LHE Poker Strategy
A team of researchers at Canada’s University of Alberta have claimed to have developed an “essentially perfect” solution to one of the simpler forms of poker contested by human players, heads-up fixed-limit Texas hold’em (HULHE or heads-up LHE). The group, conducting their research over the course of several years in their long-running Cepheus Poker Project, have announced the publication of their solution to the simplified game in the January 2015 issue of Science Magazine.
The four primary researchers behind the Cepheus project are Michael Bowling, Neil Burch, Michael Johanson and Oskari Tammelin. Bowling, Burch and Johanson are affiliated with the Department of Computing Science at the University of Alberta in Edmonton. Their paper for Science, “Heads-up Limit Poker is Solved,” is accompanied by the launch of an interactive site offering visitors the chance to play against the Cepheus program, and understand the basics behind the long-running project.
Heads-up limit specialists wishing to test their mettle against the Cepheus code (for fun, not real money) can visit http://poker.srv.ualberta.ca/.
The Cepheus Poker Project represents a culmination of 11 years of study and development of an idealized solution for heads-up, a limited-strategy but intensely competitive game variation. Heads-up fixed-limit hold’em was the game format contested by the players in Michael Craig’s The Professor, the Banker, and the Suicide King, which featured the tale of a series of high-stakes heads-up LHE battles between wealthy Texas banker Andy Beal and a team of Las Vegas’s “Big Game” poker pros, including such players as Doyle Brunson, Jennifer Harman and Ted Forrest.
The Cepheus project is the successor to an earlier project and optimized computer program for heads-up LHE that first emerged from the U. of Alberta efforts. That earlier version, dubbed Polaris, was narrowly defeated by poker pros Phil Laak and Ali Eslami in a high-profile “man v. machine” square-off back in 2007.
Since then, the U. of Alberta researchers have maintained their efforts. According to information published by the team, the final Cepheus solution involved playing a billion, billion hands (1,000,000,000,000,000,000 hands) over the span of two months. During that final solving run, the Cepheus program was optimally trained by playing against itself at the rate of six billion hands per second, far beyond the scope of what any human being could accomplish even given a full life-time of continuous poker play.
Even at that, the Cepheus solution represents only a “weak solution,” meaning that it achieves optimum results only against another idealized opponent — for example, another copy of Cepheus itself. That said, Cepheus would play “nearly optimal” poker against a wide variety of foes and, given the ability to train itself further against a given human foe’s particular tendencies, would represent a formidable, perhaps unbeatable (in the long run) foe.
According to the Cepheus researchers, what makes this game solution special is that it’s the first time a game of imperfect information has been declared “solved”. Many simpler games have been solved by computers in the past, ranging from tic-tac-toe to checkers and Connect 4, two games mentioned specifically by the Cepheus programmers in the summary accompanying their work.
Poker is different than all these other games, in that the hole cards (down cards) that are dealt to players represent an ongoing source of hidden information, or probabilistic uncertainty. That’s why even a weak probabilistic solution to this poker variant — one of the simplest in all of poker — is really no threat at all to the wider world of poker play.
The Cepheus solution includes bluffs and misdirections and other strategic moves that are a natural part of poker, meaning that even though the researchers claim that the game is “solved,” that solution means remembering and invoking bluff/fold percentages for every possible combination of hole cards and board cards that could be displayed. Such a memory is also far beyond the capability of virtually any human player. The solutions, once computed, typically include a mix of betting actions which include “always raise,” “always fold,” or “raise or fold according to an optimized percentage.
The Cepheus program seldom calls, except in a capped pot. That’s a sign of strong play as well.
It makes a neat story, of course, and the Alberta researchers deserve congratulations on discovering their idealized solution. The “About Cepheus” page at the project’s online home includes a summary paragraph about exactly why the effort was undertaken. It may seem grandiose, but even if that, the solutions may well play into a discovery in some far different application or use down the road, in a way we can’t even foresee. According to the group:
Cepheus marks a milestone for artificial intelligence and game theory. Many games have been solved previously, notably Connect 4 and checkers. Even more games have seen computers surpass human performance, notably chess and Othello. Such successes have a common property: they all have perfect information, where all players have all of the relevant information to make their decisions. Poker is the antithesis of perfect information where the one most relevant piece of information, the other players’ cards, is exactly what is not known. Just as games of chance were a driving force behind Pascal and Fermat’s development of the field of probability, poker was a driving force behind von Neumann’s development of the field of game theory.
COMMENTS