Five Scientists Claim They Have Solved Heads-Up Limit Texas Hold’em
If you grew up thinking that an imperfect information game such as Texas hold’em could never be solved by a man or a machine, think again.
According to a study that appeared in Science magazine on Jan. 9, a group of scientists from The University of Alberta has not only found a way to "solve" the game, but they have also published research that proves their ambitious claim.
Over the past years, Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin worked hard to achieve their goal, and today they came out with a computer program named Cepheus — a bot that they assure can't be beaten by any human poker player. Ever.
"Here, we announce that heads-up limit Texas hold’em is now essentially weakly solved," the study’s abstract writes. According to the group’s findings, their system does not guarantee "to win money on every single hand, but, in the long run, if you looked at all the hands that could happen and you averaged all of those, then the computer can’t be losing, at a losing rate — it has to be either breaking even or winning."
In an interview with the online tech magazine The Verge, the computer scientist at The University of Alberta and co-author of the study, Bowling, explains that the Cepheus software works by searching a database of pre-defined game situations in order to find the most optimal move for any given hand.
The database was built by letting the software play poker against itself, and hence allows it to learn all the possible scenarios a player could face at any given time, computer scientist from the University of Alberta, and co-author of the study Johanson explains.
"We had this training phase where the program started off playing uniform random against itself." According to Johanson, the bot had "no idea what it was doing other than following the rules of the game."
This process, however, allowed Cepheus to learn every possible move in the game and always find the ones that would lead it to a success, even in a game of imperfect information as poker.
"[Cepheus] does that by thinking of all possible decision points, and every possible action [that could take place from those points]," Bowling explains to The Verge. For example, the program might think, "What if I raise here? Instead of playing randomly, how much more money or less money would I win?"
Essentially, by doing this, the program acts as if it was thinking about all the possible consequences of every possible move, calculating the possibilities to win and the amounts of money/chips that any move would allow it to win.
In this way, if the random play ends costing it money, Cepheus is able to go back to a different scenario and find a different and optimal strategy to use in that specific situation. This allows Cepheus to adopt a different strategy in every single hand, learn from its mistakes and achieve what Bowling calls "the perfect play" by learning the games as he plays.
The scientists explained that during the preparation phase of the bot, they have used "a cluster of 200 computers, each armed with 32 GB of RAM and 24 central processing units" for 70 days. After that, according to Johanson, they had already managed to turn their creation in an already nearly perfect poker player.
"We could continue to train it, and it would continue to get better," Bowling told The Verge. "But we stopped at this point because we can’t tell it apart from being perfect."
Another interesting finding that the group claims came up during their research, is that the dealer always has an advantage in heads-up limit Texas hold'em games.
"Our computation formally proves the common wisdom that the dealer in the game holds a substantial advantage," the study says. According to Johanson, "We actually can now prove that the dealer has an advantage of what we call '88 millablinds' per game, or .088 of a big blind per game."
Besides casting some dark shadows over the games of poker and the possibility that "perfect bots" may one day become a reality to consider, the researchers believe that the result of their study may serve some other important causes as to help governments and companies to get better and "unexploitable" security systems.
Furthermore, the group explains that the lesson learned from poker may turn into a useful one to help doctors deal with diabetic patients. Following a pattern similar to the one that lead to master the "perfect play," Cepheus may now be able to always find "the optimal treatments" for diabetic patients in case of patient’s conditions changes — as it is now able to take into account any number of uncertainties. Exactly as in poker.
Polaris' Younger Brother
The name of Bowling may not sound entirely new to those ones who have been around poker for long enough to remember about Polaris, a bot launched in 2007 by the University of Alberta to prove that machines could beat humans at the poker table.
Back then, the bot started its poker career by being defeated by poker professionals Phil Laak and Ali Eslami in the "First Man-Machine Poker Championship," a two-day, four-session match held at the Association for the Advancement of Artificial Intelligence in Vancouver, Canada.
One year later, however, right after the very same Bowling admitted that programmers were able to add "an element of learning, where Polaris identifies which common poker strategy a human is using and switches its own strategy to counter" and learn from its mistakes, Polaris played — and won — in the second "Man-Machine Poker Championship", defeating a team composed by Nick Grudzien, Kyle Hendon, Rich McRoberts, Victor Acosta, Mark Newhouse, IJay Palansky, and Matt Hawrilenko.
Image courtesy of The Verge