Cepheus and the “Solving” of Heads-Up LHE

Yesterday I was writing about the “New York Times 4th Down Bot” and related efforts by those studying stats to present math-based models for dictating how best to coach a football game. There was a related story last week regarding the team of researchers at the University of Alberta who have been working for several years on “solving” heads-up fixed-limit hold’em, with their new study published in the January 2015 issue of the journal Science “announc[ing] that heads-up limit Texas hold’em is now essentially weakly solved.”

I remember many years ago -- way back in the summer of 2007 -- speaking with Jonathan Schaeffer of the University of Alberta about Polaris, the computer program developed by his team of researchers that comprised the university’s Computer Poker Research Group (CPRG) in the dept. of Computing Science which he chaired. An LHE match between Polaris and two pros, Phil Laak and Ali Eslami, took place that summer in which the humans won, and for PokerNews I spoke to Schaeffer about Polaris and the CPRG’s goals.

“One of these days -- within 5 to 10 years -- two-person, limit hold’em will be solved,” he said to me. Here we are about seven-and-a-half years later, and it sounds like those continuing the work there at Alberta have fulfilled Schaeffer’s prediction.

The new heads-up LHE-playing program is called Cepheus and is in fact available to play against online, although when I went to the site there were “too many in queue” and I was invited to come back later to try.

With my academic affiliation I have been able to get a copy of the Science study and have read through it. Simply titled “Heads-up limit hold'em poker is solved,” it begins by pointing out that while certain “perfect-information” games like Connect Four and checkers have been solved, others like chess have not even if much-celebrated events like Deep Blue’s victory over Garry Kasparov has led some to suggest it has. “Defeating top human players is not the same as ‘solving’ a game,” the study’s four authors point out.

The study then notes how only “perfect-information” games have been solved thus far, making their claim regarding the “imperfect-information” game of heads-up limit hold’em groundbreaking. Reference is made to the work of game theory pioneer John von Neumann and the element of bluffing that distinguishes poker, to Michael Craig’s The Professor, the Banker, and the Suicide King (which details the high-stakes LHE games between by Andy Beal and “the Corporation”), as well as to the previous work of Schaeffer and his team at Alberta.

An explanation of what it means to “solve” a game follows, with the distinction “weakly solved” referring to a game in which “for the initial position(s), a strategy has been determined to obtain at least the game-theoretic value, for both players, under reasonable resources.” From that definition, the researches extrapolate that as far as heads-up LHE goes, it is safe to say that the game is “essentially weakly solved... if a human lifetime of play is not sufficient to establish with statistical significance that the strategy is not an exact solution.”

From there comes further refinement of what is meant by an “imperfect-information game” then an explanation of the programming of Cepheus and the “solution” ultimately found. This admittedly is where your humble scribbler feels especially humbled, not being versed in the various fields of the researchers.

Back in 2007 there was already lots of talk about “poker bots” and online poker, so I had to ask Schaeffer about Polaris and how it might relate to the online game. “I want to be clear,” he told me. “We do not play online poker. None of our software is enabled to play online poker on any of the sites.”

Nor has being able to “solve” heads-up limit hold’em ever been the endgame for the researchers at Alberta. They conclude their study by noting how “the breakthroughs behind our result are general algorithmic advances that make game-theoretic reasoning in large-scale models of any sort more tractable.” In other words, as often gets pointed out by those who study game theory as it applies to recreational games or sports, the findings there have value in other realms involving human decision-making.

As a longtime fan of LHE, I’m curious to learn more about Cepheus, including how it was created and what it can do. If you are also curious, here’s a good piece on the FiveThirtyEight site summarizing the team’s work and placing it in a broader context by Oliver Roeder called “Computers Are Learning How to Treat Illnesses By Playing Poker and Atari.” And I’m about to go listen to the latest episode of the Thinking Poker podcast on which Andrew Brokos had on as guests two of the study’s authors, Michael Bowling and Michael Johanson of the CPRG at Alberta, to talk about Cepheus.

In the meantime I’m going to keep queueing up to try to play Cepheus. Last night Vanessa Selbst was on PokerStars playing at some some 8-game play money tables, and I actually sat at one for a few orbits. Feeling equally intimidated to sit across from Cepheus, I think.