From occasional games at someone's house to the millions moved by the professional circuit, poker has become a true passion. At the same time, it is an excellent subject of study for experts in computer science and mathematics, which has led to the creation of Cepheus, software that in essence has managed to solve the poker variant known as “heads-up limit Texas Hold'em”. In other words, Cepheus cannot be defeated.
It's quite likely that at some point on a weekend, remote control in hand, you've come across a poker game on television. Players are characterized by wearing caps emblazoned with sponsor names and dark glasses, not to mention their marble expressions, in an attempt to imitate Mr. Spock while studying their cards. The slightest mistake can cause millions of dollars to change hands in a second, which confirms poker not only as a game of chance but also as a true battle of wills. Now, what happens when the opponent has no will? What happens when you play against someone who doesn't think about money or fame, but about making the best decision every time? The answer is that such an opponent could not be defeated, and that's how the University of Alberta has presented the software Cepheus.
The Mathematics Behind Cepheus
Poker is what is called a game with an imperfect amount of information, since the most critical element (the opponent's cards) is an unknown as soon as each hand begins. What the creators of Cepheus propose is to define a “perfect solution” for poker as a strategy that in the medium and long term guarantees not losing money. We know well that some poker games can last for days, and the fact of being a piece of software certainly works in Cepheus's favor. However, its performance is the product of ten years of work, two months of training (Cepheus competed against itself), and billions of hands analyzed per second. In the “heads-up limit Texas Hold'em” poker variant there are 3.16 x 10^17 different states, and 3.19 x 10^14 phases in which the player must make a decision. This amounts to a chilling 262 terabytes of information, but the people behind Cepheus managed to compress this to only eleven terabytes.
The Algorithm and Expert Opinions
As expected, there is a powerful algorithm behind Cepheus, named CFR+. The algorithm applies an optimized version of the technique known as “counterfactual regret minimization”, which in simple terms allows it to make fewer decisions, though broader and deeper, in search of the ideal solution (which may include a bluff, of course). Something to keep in mind is the response of other experts to the work of Oskari Tammelin, Michael Bowling, and the rest of the team. Tuomas Sandholm from Carnegie Mellon University declared Texas Hold'em poker as “essentially solved” while the journal Nature considers Cepheus's game as “perfect”. Is it really? Its creators say no, since there is a (very) remote probability that Cepheus might lose, but even with sixty million hands played, a human could not see the crack in the armor. If you still want to play against Cepheus, you can do so on the official site.
