If you thought IBM's chess-playing computer, Deep Blue, was impressive, this is going to blow you away. Two-player limit Texas hold'em poker has been solved. Pitted one-on-one against the world's best poker players, a new computer program named Cepheus would never lose. You can even challenge it to a game, yourself.
Cepheus, developed by Finnish software developer Oskari Tammelin in collaboration with a team of University of Alberta researchers led by computer scientist Michael Bowling, is designed to trounce all challengers at the popular variation of poker known as heads-up limit hold'em (HULHE). The researchers' work is impressive on several levels. The biggest accomplishment is, arguably, the scientists' counterfactual regret minimization algorithm. Among computer-poker researchers, "counterfactual regret minimization" refers to a computer's ability to learn from experience by assessing the extent to which its previous decisions have failed and using that information to recalibrate its strategy for future implementation. One of the techniques to emerge in the course of the strategy's optimization was bluffing.
The other major accomplishment is the team's compression method. There are 3.16 × 1017 states that can be reached in a game of heads-up limit hold'em, and 3.19 × 1014 possible stages at which a player must make a decision. Keeping track of these states and points of commitment has, in the past, required on the order of 262 terabytes of storage. Part of what makes Bowling and Tammelin's research so impressive is the compression method they've devised to reduce the required storage volume to just 11 terabytes, which makes it easier and quicker for their algorithm to plan and enact its strategy.
That strategy might lose on a hand-to-hand basis (chance is chance, the researchers say – no amount of number crunching can save you from a crummy hand), but it always wins in the long-run. To quote Nature's Philip Ball, Cepheus "plays perfectly, to all intents and purposes":
That means that this particular variant of poker, called heads-up limit hold'em (HULHE), can be considered solved... The strategy the authors have computed is so close to perfect "as to render pointless further work on this game", says Eric Jackson, a computer-poker researcher based in Menlo Park, California.
Popular games like chess and checkers have been "solved" in the past. But these games differ fundamentally from poker, in which a player's situational knowledge is limited:
...poker is harder to solve than draughts. Chess and draughts are examples of perfect-information games, in which players have complete knowledge of all past events and of the present situation in a game. In poker, in contrast, there are some things a player does not know: most crucially, which cards the other player has been dealt. The class of games with imperfect information is especially interesting to economists and game theorists, because it includes practical problems such as finding optimal strategies for auctions and negotiations.
"This is, to my knowledge, the largest imperfect-information game essentially solved to date," writes Carnegie Mellon University computer scientist Tuomas Sandholm, who didn't participate in the study, in a perspective piece accompanying the paper in this week's issue of Science. It's also, he sys, "the first one competitively played by humans that has now been essentially solved."
Top image via Shutterstock