4
News Feature
thursday, march 24, 2011
the
raise
www.thegatewayonline.ca
of the machines
The U of A Computer Poker Research Group goes all-in to attempt to make the first unbeatable AI in the world’s highest stakes card sport
Written by Lance Mudryk Photographed by Amirali Sharifi
B
eating the best humans at Jeopardy! is one thing, but to go heads up in no-limit poker may be an even more challenging task for a computer to solve, and the University of Alberta Computer Poker Research Group is working to do just that. In 2008, their poker robot Polaris played six matches of two-player limit Texas Hold ‘Em against two of the best players in the world, and managed to outperform them by $200,000, winning three matches, losing two, and tying one. This achievement shouldn’t be taken lightly. Poker is an incredibly complex game, and even two-player limit betting, the simplest form of Texas Hold ‘Em, has roughly the same number of unique states as there are stars in the universe. For games with more than two players or no-limit betting, the problem becomes that much more formidable. But it’s just another challenge for researcher Nolan Bard, a doctoral student working on the project. “This is a really hard problem to solve. Being able to play at that level would be able to demonstrate the ability to solve these really big games, exploit human players and learn quickly, and do a lot of things integral to decision-making problems that you can see in a lot of different areas,” Bard said. It’s not clear exactly what will come from the research, but some of the techniques that have been developed in the group have been applied outside of poker towards other games. Bard emphasizes the importance of game
theory and how it can be applied to a variety of different disciplines, from economics to biology to philosophy. The power and sophistication of the programs used to solve poker can be adapted to work in these other fields so that computers are able to compute large problems quickly and more accurately than humans. “I don’t know if it’s necessarily been our work, but poker work in general has [been] applied in security systems — where people should patrol and stuff, in a way to optimize security surveillance in airports,” said Richard Gibson, another doctoral student in the group. Though Polaris’ poker win in 2008 was a great accomplishment for the research group, they have been hard at work on developing better programs since then. The two major problems they are facing are dealing with multiple opponents and no-limit games. “Solving no-limit is closer in our grasps than multiplayer [games],” said Bard. “I’d say we’re making progress. The complication there is you can make any sort of bet size, so that in the game theory sense, it kind of explodes the space up. [...] It’s some ridiculous number that’s even impossible to store on a disc, on your computer, what to do at every single situation. There are too many scenarios of what to do.” The problem with multiplayer games is that they allow a greater exploitation of the program. The poker bots work by calculating a “Nash equilibrium,” which is a theory that each player has a chosen strategy and nothing to benefit by
unilaterally changing strategies. The computer decides their moves based on the Nash equilibrium, keeping in mind that if no one changes strategies, it’s guaranteed to gain more than it loses. However, with multiplayer games, there is more of a likelihood that one of the players will change strategy, and it’s harder for the poker bot to predict what the outcomes are going to be. “We’re looking at your average value over time. If you played forever, you’re guaranteed to take a certain percentage,” Gibson adds. That was the tradition of their research, but as more complexities are added to the game, it becomes easier to be exploited by human opponents. In a three-person game, their programs can perform well as long as their opponents don’t team up against it. As far as the future of artificial intelligence goes, both Bard and Gibson agree that super-advanced AIs are still distant fantasies. “For computers to get to a level where they could listen or read something like this, understand the context of a conversation, and then synthesize something new and novel — this is still far, far off,” Bard said. “In the ‘50s, it was basically said, ‘If you could create a program that plays chess and could beat human players at chess, there you go, you have AI.’ Well, we’ve done that. Right now, that’s not AI,” Gibson added. “That’s not interesting. Can you do that in poker? Well, we can try to do that, and as soon as we do that, the bar’s going to be even higher.”