5th March 2017
AI beats top human players at poker
The University of Alberta has announced details of DeepStack, a new artificial intelligence program able to beat professional human players at poker for the first time.
In 1952, Professor Sandy Douglas created a tic-tac-toe game on the EDSAC, a room-sized computer at the University of Cambridge. One of the first ever computer games, it was developed as part of a thesis on human-computer interaction. Forty-five years later, in 1997, another milestone occurred when IBM's Deep Blue machine defeated Garry Kasparov, the world chess champion. This was followed by Watson, again created by IBM, which appeared on the Jeopardy! game show and beat the top human players in 2011. Yet another breakthrough was Google's DeepMind AlphaGo, which in 2016 defeated the Go world champion Lee Se-dol at a tournament in South Korea.
Now, for the first time ever, an artificial intelligence program has beaten human professional players at heads-up, no-limit Texas hold 'em, a variation of the card game of poker. This historic result in AI has implications far beyond the poker table – from helping to make more decisive medical treatment recommendations to developing better strategic defence planning.
DeepStack has been created by the University of Alberta's Computer Poker Research Group. It bridges the gap between games of "perfect" information – like in checkers, chess, and Go, where both players can see everything on the board – and "imperfect" information games, by reasoning while it plays, using "intuition" honed through deep learning to reassess its strategy with each decision.
"Poker has been a long-standing challenge problem in artificial intelligence," said computer scientist Michael Bowling, principal investigator on the study. "It's the quintessential game of imperfect information, in the sense that players don't have the same information or share the same perspective while they're playing."
Artificial intelligence researchers have long used parlour games to test their theories because the games are mathematical models that describe how decision-makers interact.
"We need new AI techniques that can handle cases where decision-makers have different perspectives," said Bowling. "Think of any real-world problem. We all have a slightly different perspective of what's going on, much like each player only knowing their own cards in a game of poker."
This latest discovery builds on previous research findings about artificial intelligence and imperfect information games stretching back to the creation of the Computer Poker Research Group in 1996. DeepStack extends the ability to think about each situation during play to imperfect information games using a technique called continual re-solving. This allows the AI to determine the correct strategy for a particular poker situation by using its "intuition" to evaluate how the game might play out in the near future, without thinking about the entire game.
"We train our system to learn the value of situations," said Bowling. "Each situation itself is a mini poker game. Instead of solving one big poker game, it solves millions of these little poker games, each one helping the system to refine its intuition of how the game of poker works. And this intuition is the fuel behind how DeepStack plays the full game."
Thinking about each situation as it arises is important for complex problems like heads-up no-limit hold'em, which has more unique situations than there are atoms in the universe, largely due to players' ability to wager different amounts including the dramatic "all-in." Despite the game's complexity, DeepStack takes action at human speed – with an average of only three seconds of "thinking" time – and runs on a simple gaming laptop.
To test the approach, DeepStack played against a pool of professional human players recruited by the International Federation of Poker. A total of 33 players from 17 countries were asked to play in a 3,000-hand match, over a period of four weeks. DeepStack beat each of the 11 players who finished their match, with only one outside the margin of statistical significance.
A paper on this study, DeepStack: Expert-Level Artificial Intelligence in Heads-Up No-Limit Poker, is published in the journal Science.
• Follow us on Twitter
• Follow us on Facebook