A team of researchers from the University of Alberta comp sci department have ‘essentially solved’ heads-up limit hold’em, a significant accomplishment for game theory and artificial intelligence, but nowhere near the end of poker despite what some headlines would have you believe.
“The breakthroughs behind our result are general algorithmic advances that make game-theoretic reasoning in large-scale models of any sort more tractable,” write Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin in their paper Heads-up hold’em limit poker is solved, published in the current issue of Science.
Limit Hold’em: Researchers solved a specific, constrained version of Texas hold’em
Despite the claims running around that the researchers new program can beat anyone at poker, or even at Texas Hold’em, the restrictions are important to understanding what was actually accomplished. First, for those who may not be familiar with the game, Texas Hold’em is a poker variant where each player has two cards in their hand and the entire table shares another five cards face up. The best five-card hand out of seven wins with four different chances to bet during a single round. Heads-up means that there are only two players and limit means that there is a maximum bet size.
“It is also the smallest variant of poker played competitively by humans. HULHE has 3.16 × 10^17 possible states the game can reach, making it larger than Connect Four and smaller than checkers,” the researchers explain. “However, because HULHE is an imperfect-information game, many of these states cannot be distinguished by the acting player, as they involve information about unseen past events (i.e., private cards dealt to the opponent). As a result, the game has 3.19 × 10^14 decision points where a player is required to make a decision.”
A brute force solution to a game like this would require looking at every decision point to find the Nash equilibrium, the state where neither player can improve their odds of winning unilaterally. As you can guess, that’s computationally very difficult and a lot of advances in computational game theory involve finding clever ways to get very good approximations to the Nash equilibrium without having to analyze every single decision point.
CFR+ gives a new tool for analyzing complex games
The researchers developed a new algorithm called CFR+ based on the previous best model CFR (counterfactual regret minimization), which allows them to tackle much larger games than had previously been analyzed. The results do offer some insight into heads-up play (the algorithm almost never limps into a bet, and more surprisingly almost never caps in the first round of betting when it’s the dealer), but what’s more important is the steady progress toward being able to analyze larger and more complex games. We’re still nowhere near ‘solving’ a full table of no-limit hold’em, but it’s a big step nonetheless.
