Computer Poker: AI Contest is a Big Deal

Academically speaking, computer poker is all about game theory. But to the rest of the world, Texas Hold'Em is all about having some fun and making a couple of bucks--or rather, not losing your shirt.

Whether for the excitement, money, or class credits, poker is all the rage these days, even with the American Association for Artificial Intelligence (AAAI) which is holding its first Computer Poker Competition at the upcoming annual AAAI conference.

Among others, entrants include the likes of Carnegie Mellon University and the University of Alberta (my alma mater), both of which have added computer poker to their research. At the U of A, in fact, the Computer Poker Research Group, led by Jonathan Schaeffer (who I interviewed in this podcast) last year, is part of the The University of Alberta GAMES Group which examines game theory across the board, so to speak.

In CMU's case, the poker team is led by computer science professor Tuomas Sandholm and graduate student Andrew Gilpin, who have built a be poker robot called "GS1" developed by Sandholm, who is also director of CMU's Agent-Mediated Electronic Marketplaces Lab, and Gilpin. Though not yet the equal of the best human players, GS1 outperformed the two leading "pokerbots" in playing heads-up, limit Texas Hold'Em in tests at CMU earlier this year. Both of GS1's opponents were commercially available programs that, like other pokerbots, incorporate the expertise of human poker players. GS1, by contrast, develops its strategy after performing an automated analysis of poker rules. Sandholm and Gilpin have since developed an improved version of their game-theory-based program, called "GS2," which will compete in the AAAI event.

Unlike chess, where the status of all of the chess pieces is known to both players, poker forces players to make decisions based on incomplete information. "You don't know what the other guy is holding," Sandholm explained. And the sheer number of possible combinations of cards dealt, cards on the table and bets in two-player Texas Hold'Em games -- 10^18, or a billion times a billion -- makes it impossible for even the fastest computers to fully analyze every hand.

In his computer poker research, Sandholm has developed pokerbots that precompute the strategies for playing the first two rounds of Texas Hold'Em, the so-called "pre-flop" and "flop" rounds, when players are first dealt two cards and then three additional cards are positioned face-up. For the third and fourth betting rounds, the "turn" and the "river," his pokerbots update the probability of each possible hand by taking into account betting as well as the revealed cards. The strategy for those rounds is then computed in real-time for the setting at hand.

To reduce the computational complexity, GS1 and GS2 automatically recognize strategically equivalent hands. For instance, 25,989,600 distinct hands are possible in the second round, but only about a million are strategically different. That's still too many to compute, so the pokerbots group strategically similar hands together. The end result is 2,465 groups, a small enough number to allow computational analysis.

Source code for the contest is available for download. The server for the competition is written in Java and runs on Windows.

Posted by Jon Erickson at 08:47 AM  Permalink