Two new programs best the best at heads-up no-limit Texas Hold’em
Carnegie Mellon University
In the battle of wits between humans and machines, computers have just upped the ante.
Two new poker-playing programs can best professionals at heads-up no-limit Texas Hold’em, a two-player version of poker without restrictions on the size of bets. It’s another in a growing list of complex games, including chess, checkers (SN: 7/21/07, p. 36) and Go (SN: 12/24/16, p. 28), in which computers reign supreme.
Computer scientists from the University of Alberta in Canada report that their program, known as DeepStack, roundly defeated professional poker players, playing 3,000 hands against each. The program didn’t win every hand — sometimes the luck of the draw was against it. But after the results were tallied, DeepStack beat 10 out of 11 card sharks, the scientists report online March 2 in Science. (DeepStack also beat the 11th competitor, but that victory was not statistically significant.)
“This work is very impressive,” says computer scientist Murray Campbell, one of the creators of Deep Blue, the computer that bested chess grandmaster Garry Kasparov in 1997. DeepStack “had a huge margin of victory,” says Campbell, of IBM’s Thomas J. Watson Research Center in Yorktown Heights, N.Y.
Likewise, computer scientists led by Tuomas Sandholm of Carnegie Mellon University in Pittsburgh recently trounced four elite heads-up no-limit Texas Hold’em players with a program called Libratus. Each contestant played 30,000 hands against the program during a tournament held in January in Pittsburgh. Libratus was “much tougher than any human I’ve ever played,” says poker pro Jason Les.
Previously, Michael Bowling — one of DeepStack’s creators — and colleagues had created a program that could play a two-person version of poker in which the size of bets is limited. That program played the game nearly perfectly: It was statistically unbeatable within a human lifetime (SN: 2/7/15, p. 14). But no-limit poker is vastly more complicated because when any bet size is allowed, there are many more possible actions. Players must decide whether to go all in, play it safe with a small wager or bet something in between. “Heads-up no-limit Texas Hold’em … is, in fact, far more complex than chess,” Campbell says.
In the card game, each player is dealt two cards facedown and both players share five cards dealt faceup, with rounds of betting between stages of dealing. Unlike chess or Go, where both players can see all the pieces on the board, in poker, some information is hidden — the two cards in each player’s hand. Such games, known as imperfect-information games, are particularly difficult for computers to master.
To hone DeepStack’s technique, the researchers used deep learning — a method of machine learning that formulates an intuition-like sense of when to hold ’em and when to fold ’em. When it’s the program’s turn, it sorts through options for its next few actions and decides what to do. As a result, DeepStack’s nature “looks a lot more like humans’,” says Bowling.
Libratus computes a strategy for the game ahead of time and updates itself as it plays to patch flaws in its tactics that its human opponents have revealed. Near the end of a game, Libratus switches to real-time calculation, during which it further refines its methods. Libratus is so computationally demanding that it requires a supercomputer to run. (DeepStack can run on a laptop.)
Teaching computers to play games with hidden information, like poker, could eventually lead to real-life applications. “The whole area of imperfect-information games is a step towards the messiness of the real world,” says Campbell. Computers that can handle that messiness could assist with business negotiations or auctions, and could help guard against hidden risks, in cybersecurity, for example.
M. Moravčík et al. DeepStack: Expert-level artificial intelligence in heads-up no-limit poker. Science. Published online March 2, 2017. doi: 10.1126/science.aam6960.
T. Sumner. Year in review: AlphaGo scores a win for artificial intelligence. Science News. Vol. 190, December 24, 2016, p. 28.
A. Grant. Computer program rivals top poker players in complex card game. Science News Online, May 13, 2015.
A. Grant. New computer algorithm plays poker almost perfectly. Science News. Vol. 187, February 7, 2015, p. 14.
J. Rehmeyer. Check on checkers: In perfect game, there's no winner. Science News. Vol. 172, July 21, 2007, p. 36.