Researchers at the University of Alberta have built a robot that has ‘solved’ the game of heads up limit Texas hold’em poker. Photo credit: Michael Bowling
Last month, Stephen Hawking caused quite a stir when he mused that advances in artificial intelligence “could spell the end of the human race.” Computer scientists quickly shot back, pointing out that today’s algorithms still struggle to recognize kittens, never mind plotting our ultimate doom. Still, with programs like Deep Blue and Watson outplaying humans on a regular basis, you might be forgiven a certain uneasy sense that the machines are gaining on us. Now, researchers at the University of Alberta have built an unbeatable card shark, a computer program that has ‘solved’ the game of heads up limit Texas hold’em poker. But there’s no need to run for the cellar just yet: while the finding has important implications for online poker fans and even medical decision makers, it’s not exactly Skynet.
Michael Bowling of the U of A’s Computer Poker Research Group led the project. “Many of the decisions we have to make in day-to-day life are filled with uncertainty: we’re often missing critical information, or we don’t know what others around us are going to do,” says Bowling. For example, a doctor trying to prescribe a treatment regimen for diabetes has to deal with the fact that each patient responds differently based on their diet, medical history, level of exercise, genetics and a host of other factors. Poker can act as a kind of test bed for developing artificial intelligence that can handle the presence of uncertainty. The idea is that by analyzing past decisions and outcomes, computer programs could predict what actions are most likely to be successful in the future.
Several years ago, the team made a splash when one of their algorithms, codenamed Polaris, won several games against top international poker players (WIRED ran a neat comic book-style story, which you can read here.) In a paper published this week in Science, they go a step further. “This program plays perfectly,” says Bowling. “Even if it told the other player exactly what it was going to do and why, the opponent still wouldn’t be able to win money over the long term.” The program — called Cepheus — has analysed every single one of the billions and billions of situations it could find itself in, and has worked out the best possible decision to make for each one. It may not win every single hand, but averaged out over time, it’s unbeatable.
Principal investigator Michael Bowling and poses in front of a screen displaying output from Cepheus. Photo credit: University of Alberta. Photo credit: John Ulan, University of Alberta
How did it get so good? Practice, practice, practice. Over the course of about two months, Cepheus played countless games against itself, eventually racking up something on the order of 8 to 10 billion, billion hands of poker. “It’s played more hands of poker than all of humanity has ever played in history,” says Bowling. At first, it was just playing randomly, but after each round it did a bit of self-reflection, calculating how much money it could have won if it had chosen to play differently, for example, to bet instead of call at a certain point. That monetary amount — the technical term is ‘regret’ — was used to inform the strategy it would use next time. Over time, the regrets got smaller and smaller until eventually, they reached zero, or at least as close to zero as it is reasonably possible to get. At this point, the game is considered to be ‘solved.’
This is not the first time a computer has solved a human game. For example, back in 2007 Jonathan Schaeffer, Bowling’s colleague at the University of Alberta, solved checkers with a computer called Chinook. Many people speculate that one day chess could also be solved. But what Cepheus has done is fundamentally different because of the uncertainty factor. While both checkers and chess are ‘bigger’ games than poker — there are a larger number of possible situations a player can face — they are perfect information games, meaning that each previous move is laid out for all to see. Cepheus, on the other hand, doesn’t know what cards its opponent has received, and thus is the first program to have solved an ‘imperfect information’ game.
You might think that an unbeatable poker robot would be a useful thing to own; set loose on the internet, it could collect earnings while its owner slept, ensuring an early retirement. Sadly (or fortunately, depending on your point of view) that probably won’t work. First of all, Cepheus only plays a very specific type of poker: heads up limit hold ‘em, which is exclusively a two-player game. Any change to the game — say adding a third player or getting rid of the betting limit — changes the situation so much so that Cepheus’s strategy falls apart. And head up limit hold ‘em, while popular in the early 2000s, is no longer widely played online, partly due to the fact that many players simply got too good at it. After Polaris started beating human players in 2008, Bowling and his team put up a website where people could improve their skills by sparring against the machine. It’s hard to say how much impact this had, but it does seem that over the next few years, the number of strong players increased and the number of weak players dwindled. In a stalemate, both players actually lose (since the online casinos take a certain percentage) so today most people don’t play unless they truly believe they have an advantage.
Is it possible that someone could one day build a machine that could ‘solve’ a more complicated form of poker? Perhaps, but it’s unlikely. “We’ve done work in more than two-player games, but we’re probably only at a good amateur level,” says Bowling. Part of the problem is that the sheer number of possible situations becomes unmanageably large, not to mention the exponentially higher levels of uncertainty. “Solving a game like that is such a huge question . . . it’s unclear what it would even mean to do that,” says Bowling. As for the suggestion that artificial intelligence is something to fear, Bowling is skeptical. “AI is simply a tool, and every tool we’ve had in history has had positive and negative uses,” he says. “Of course we need to use these tools in wise ways. But so much good can come from this, it would be a tragedy not to explore it.”
Want to try your luck in a game of heads up limit Texas hold’em against Cepheus? Click here to try it out.
