There’s Now A Computer That Can Destroy You At Poker
Computers are top-notch gamers. Since the 1970s, artificial intelligence has shamed our greatest chess players, outgunned our top trivia junkies and dominated at Connect Four. But all of these upsets had one thing in common: They involved “perfect information games.” That is, each player already knew everything that had happened in the game before they made any decisions. In poker, that’s not possible.
But scientists presented the first algorithm ever to solve an imperfect information game on Thursday, using the old standby of closed-handed gameplay: Texas Hold’em. In a study published in the journal Science, researchers showed that their computer program could “solve” Texas Hold’em poker with a strategy of bets and bluffs so optimal that it virtually never loses.
Given the sheer amount of money that flows through the gambling industry, it is conceivable that a program like this one could be quite disruptive on the casino floor. For now, however, there are no plans for commercialization.
Beyond gameplay, the program could eventually be used to develop optimal strategies for medicine and security, specifically for situations in which decision-makers must act quickly based on limited information. “Even after playing a lifetime of poker, there’s still a high probability that you would lose, even if you found an edge against the program,” says Michael Bowling, a computer scientist at the University of Alberta and lead author of the paper. “But the techniques that we used to solve the game apply even more broadly than entertainment activities. I’m talking about any decision-making scenario. Politics becomes a game. Auctions become a game. Security becomes a game.”
Training Cepheus, AI Poker Champion
Forget everything you ever knew about losing to a computer. In checkers or chess, each player has all of the information that he or she needs to make an informed decision—which makes it easy for a computer, a veritable database of the best possible moves, to sweep every round. But when it comes to Texas Hold’em, “That whole process of search doesn’t work,” Bowling says. “It’s hard to reason through how the other player might respond without knowing what cards they’re going to hold.”
“Solving” poker has long been the goal of many artificial intelligence researchers. But ambition often turned to frustration. In the late 1990s, Koller and Pfeffer of the University of California Berkeley declared, “We are nowhere close to being able to solve huge games such as full-scale poker, and it is unlikely that we will ever be able to do so.”
Until Cepheus came along. Bowling and his team instructed the computer to play billions of poker games against itself. Initially, they taught Cepheus only the basic rules of Texas Hold’em. The computer started off playing randomly, but eventually it began to learn. Cepheus started compiling lists of “regrets”—situations in which it could have folded or bluffed or bet differently, and won more money by doing so. The researchers then programmed Cepheus to begin acting on its most serious regrets, while ignoring its more minor regrets.
Ultimately, Cepheus whittled its list of regrets nearly down to zero. Now the program can bet and bluff with the best. “If you do this in a precise mathematical way, you can prove your regrets are guaranteed to go down to zero,” Bowling says. “And in the process of approaching zero, you must be approaching perfect play.”
Cepheus isn’t perfect, but it is guaranteed not to lose in the long run. That’s about as good as it gets for a game that still relies partially on chance.
Playing Poker Against Terrorists
Cepheus’ performance has other experts in the field of artificial intelligence excited. “It’s a really interesting paper, with a convincing argument that a particular form of poker has been essentially solved,” says Howard Williams, a computer scientist and doctoral student at Queen Mary University of London, who was not involved in the study.
Beyond poker, Bowling envisions a new set of algorithms that could help security officers optimize checkpoints, random searches and placement of air marshals on flights. In these situations, a program like Cepheus could be taught to view potential terrorists as other players in a high-stakes game rife with variables. “That’s very close to what we have achieved here for the game of poker. It’s a strategy guaranteed not to lose,” he says.
And, of course, there’s always that perfect poker game. But only if Cepheus can find someone willing to play against it. “I wouldn’t like to play a game against a computer configured to play according to the presented solution,” Williams says. “I wouldn’t ever play heads up limit Hold’em against an opponent that I couldn’t have a meaningful conversation with!”
If, however, you find yourself tempted (I know I am), Bowling and his team have set up a website where you can try your luck against Cepheus itself—the one computer program that always knows when to hold ’em and when to fold ’em.