(Edmonton) In a world first, researchers in the Computer Poker Research Group at the University of Alberta have essentially solved heads-up limit Texas hold 'em poker with their program, called Cepheus.
"Poker has been a challenge problem for artificial intelligence going back over 40 years, and until now, heads-up limit Texas hold 'em poker was unsolved," says Michael Bowling, lead author and professor in the Faculty of Science, whose findings were published Jan. 9 in the journal Science.
For more than a half-century, games have been test beds for new ideas in artificial intelligence. The resulting successes have marked significant milestones, from IBM's Deep Blue defeating world champion Garry Kasparov in chess and Watson beating top-earning Jeopardy! champs Ken Jennings and Brad Rutter.
But as Bowling points out, defeating top human players is not the same as actually solving a game-especially a game like poker.
The challenge of imperfect information
In poker, players have imperfect information-they don't have full knowledge of past events, and they can't see their opponents' hands. The most popular variant of poker today is Texas hold 'em. When it is played with just two players and with fixed bet sizes and a limited number of raises allowed, it is called heads-up limit hold 'em.
The possible situations in this poker version are fewer than in checkers-which U of A computing science researchers solved in 2007, led by now dean of science Jonathan Schaeffer-but the imperfect-information nature of heads-up limit hold 'em makes it a far more challenging game for computers to play or solve.
"We define a game to be essentially solved if a lifetime of play is unable to statistically differentiate it from being solved at 95% confidence," explains Bowling. "Imagine someone playing 200 hands of poker an hour for 12 hours a day without missing a day for 70 years. Furthermore, imagine them employing the worst-case, maximally exploitive opponent strategy-and never making a mistake. They still cannot be certain they are actually winning."
Cepheus, created by Bowling, PhD students Neil Burch and Michael Johanson and Finnish software developer Oskari Tammelin, is the first computer program to play an essentially perfect game of poker. Cepheus accomplished this goal with no human expert help, only being given the rules of the game.
"It was trained against itself, playing the equivalent of more than a billion billion hands of poker," says Bowling. "With each hand it improved its play, refining itself closer and closer to the perfect solution. The program was trained for two months using more than 4,000 CPUs each considering over six billion hands every second. This is more poker than has been played by the entire human race."
Cepheus marks a milestone for artificial intelligence and game theory. Though many perfect-information games (in which all players are aware of everything that has occurred in the game before they make a decision) have been solved, no nontrivial imperfect-information game played competitively by humans has previously been solved. And although perfect information may be a common property of parlour games, it is far less common in real-world decision-making situations.
"The breakthroughs behind this result are general algorithmic advances that make game-theoretic reasoning in large-scale models of any sort more tractable," says Bowling.
Fun and games aside, Bowling notes that game theory has always been envisioned to have serious implications, including a surge in game-theoretic applications involving security, such as systems for airport checkpoints, air marshall scheduling and coast guard patrolling.
"With real-life decision-making settings almost always involving uncertainty and missing information, algorithmic advances-such as those needed to solve poker-are needed to drive future applications."
Think you can beat Cepheus?
You can query the program's strategy or play against it online at http://poker.srv.ualberta.ca