Scientists have developed an algorithm they say you’ll never, ever, beat in a game of poker. It’s the culmination of more than 10 years of work.
The program doesn't play heads-up limit Texas hold'em poker perfectly, but it's “designed to not lose to any player,” Neil Burch, one of the developers, told us.
To test out the program — which you can play online — we called up Paula Barros, a Miami-based semi-professional poker player. She spends eight hours a day playing poker and has been making a significant part of her income playing online and IRL for years now.
When she first sat down at the digital table to play against her algorithmic nemesis Cepheus, she was winning some hands and it was winning some hands. But as any gambler knows, the longer you sit at the table, the more trouble you can get into. When Barros went up against Cepheus in a tournament of 20 hands, it started dominating her. "I mean, I just feel like, why can't we win a hand now?" she said, frustrated. Overall, Cepheus beat her in 14 out of 20 hands, winning 1060 virtual chips to her 420.
Yes, 20 hands is a pretty small sample size to prove unbeatability, but it was enough for Barros to conclude that it's like "playing a tight-solid regular player."
If you’re worried this poker-playing program will decimate the poker industry, the researchers say that’s unlikely. The code is public, so in theory you could rerun it to generate Cepheus’ winning strategy. But, says Burch, you’d need a set of “beefy” computers — the researchers used a cluster of 200 machines. Then there’s the issue of how long it would take the algorithmic player to make a decision. The researchers used special compression tools to run the algorithm quickly — and those aren’t public.
“The way we have left things, it’s hard for it to respond quickly,” said Burch.
So beyond providing a procrastination tool — and yet another example of how machines might one day rule over us — why does this matter?
To start, the software, which is described in a paper in the top-tier journal Science, could mark a milestone for artificial intelligence and have implications beyond gaming — if, in fact, it’s as good as the developers say.
Computer scientists have been building machines that can play games as well as, or better than, humans for years now. IBM’s Deep Blue beat chess master Garry Kasparov in 1997. A program dubbed Chinook took the checkers world championship title in 2007.
But those are all “perfect-information games,” games where all the essential information you need to make a gametime decision is laid out on the table. In chess, for example, you can see what the state of the board is and calculate your next move from there.
Poker, though, is an imperfect-information game. The most relevant pieces of information (your opponents cards) are unknown, so you have to guesstimate what to do. That’s not unlike real-life situations — or more simply what you might experience playing the much simpler game of rock-paper-scissors.
For engineers, imperfect-information games pose a special challenge because the algorithms used to solve them have to deal with the whole game. They can’t it break into smaller chunks, the way they can with a perfect-information game, because the program needs to consider all the possible moves in a game at once. The other issue, Burch says, is you have to build randomness into the model.
Let’s go back to the rock-paper-scissors example. If you always pick rock, your opponent will catch on, and you’ll lose. Similarly in poker, if you opponent learns you only bet when you have a good hand, you’re fried.
The algorithm has to consider when to fold, bluff or call and mix those decisions in a way that’s imperceptible to the other player. And doing that — which is more or less the equivalent of getting the computer to play like a human — is harder computationally.
An artificially intelligent card shark is cool, but its significance goes beyond the coolness of robot bluffing. It could help scientists develop models for solving real-life applications in fields like security, economics and medicine, if we can only figure out how to formulate problems in those areas as games.
"If [the developers] came up with a general new way of computing things, that could dramatically improve economic research and our way of understanding systems in which players have private information," David McAdams, a professor of business administration and economics at Duke university, told us.
What’s really wild is that Cepheus taught itself how to play poker all on its own, learning from its mistakes. None of the creators actually know how to play the game.
“There’s no feedback from us. There is no supervision,” said Burch. “The rules of the game are well defined. Once you have a description, you can apply an algorithm to it. It doesn’t require any input — any expert input — into how the game should be played. You just need to learn the rules.”
And computers are good at that.
Daniel Rivero is a producer/reporter for Fusion who focuses on police and justice issues. He also skateboards, does a bunch of arts related things on his off time, and likes Cuban coffee.
Daniela Hernandez is a senior writer at Fusion. She likes science, robots, pugs, and coffee.