Researchers have solved heads-up limit Texas hold 'em poker with a new computer named Cepheus.
For over half a century games have been used to test artificial intelligence, but having the ability to beat human players is not the same as solving the game itself, the University of Alberta reported.
"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," said Michael Bowling, lead author and professor in the faculty of science, whose findings were published Jan. 9 in the journal Science.
In poker, players have "imperfect information," meaning they do not know what is in their opponent's hand or what moves they have made in the past. The possible situations in Texas hold 'em are fewer than what is available in checkers, but the imperfect information makes it more difficult to 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," explained 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 is the first computer program to play a "perfect" game of poker, and it accomplished this after only being given the basic rules of the game.
"It was trained against itself, playing the equivalent of more than a billion billion hands of poker," Bowling said. "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."
The finding could lead to new game-theoretic applications in the security field, such as in airport checkpoints 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," Bowling concluded.
