Poker aficionados have been pondering the best strategies ever since the card game was invented. Now along comes the perfect exponent, one who knows all the optimal plays and so always wins in the long run 鈥� or so its makers claim.
The unbeatable player is a piece of software created by computer scientists at the University of Alberta in Edmonton, Canada. They say they have worked out the ideal strategy for a particular form of the game. The work could have applications to real-world situations in which people try to achieve preferred outcomes 鈥� including auctions and tightened security for air travel.
Poker is a popular test bed for artificial intelligence research because, unlike games like chess or checkers, each player holds cards that other players cannot see. 鈥淭he whole interesting part of the game comes from the fact that you don鈥檛 have perfect information,鈥� says Michael Bowling, a member of the team that devised the new software.
Advertisement
For several years now, poker-playing programs 鈥� including others Bowling has created 鈥� have been able to hold their own with the best human players, but no program has been powerful enough to sift through all the possible scenarios and select the absolute best play in every case.
Subtle boost
Until now, say Bowling and his colleagues. They took their previous best program, named Polaris, and made a subtle change to the way it learns from experience. The new version is more willing to make plays that had failed in the past but might still work if they form part of a bigger, more sophisticated strategy. They also fine-tuned it by optimising its use of disc space and memory.
Together, these tweaks made the new program, Cepheus, about a thousand times quicker, giving Bowling鈥檚 team enough power to compute the perfect strategy for every possible situation in the two-player poker variant known as Heads Up Limit Hold 鈥楨m. They have shown that no alternative would reliably come out ahead over a human lifetime鈥檚 worth of playing.
Bowling鈥檚 strategy doesn鈥檛 demystify poker in such a way as to kill people鈥檚 interest in the game. For one thing, the algorithms amount to 12 terabytes of data, so they鈥檙e not something a human player could pore over in a weekend (or a lifetime). Players can, however, practise against the computer or querying it about particular scenarios; indeed, Bowling鈥檚 team has a where anyone can do just that.
Moreover, most poker games involve more than two players and often have no betting limits. This makes the games far harder to analyse, says Bowling. Nor will most players gain much from consulting Cepheus鈥檚 perfect strategy. Few players make full use of the many poker-training websites that already exist, says Phil Laak, a professional player.
Flight security
Bowling鈥檚 techniques should prove helpful in real-world situations where parties have incomplete information. Milind Tambe at the University of Southern California in Los Angeles has developed software that assigns air marshals to flights in a way that terrorists cannot predict, while giving maximum protection to flights deemed most vulnerable. The software makes several simplifying assumptions, so Bowling鈥檚 approach could help in building a more realistic approach, says Tambe.
Similarly, telecommunications companies bidding for newly available radio frequencies need a strategy to get enough bandwidth for least cost. 鈥淣o one knows the rational way of bidding in a typical spectrum auction,鈥� says at Carnegie Mellon University in Pittsburgh, Pennsylvania.
Again, software may hold the answer. 鈥淚f you鈥檙e in a high-stakes domain like cybersecurity or auctions where billions are on the line, it would be really nice to know that you鈥檙e playing optimally instead of just doing a really decent job,鈥� says Sandholm.
Journal reference:
Article amended on 1 January 1970
When this article was first published, we incorrectly attributed to Phil Laak a comment that was in fact made by Michael Bowling. This has now been corrected.
