CMU Creates AAAI Winning Poker Bot
I don’t play poker that much (or, at least I won’t admit to it publicly ;-), but I’m familiar enough with the game to know that mathematics plays a central role. It’s not surprising, then, that poker is incredibly seductive to lots of computer scientists — basically, this is a game that can reward you if you are good at math. But how far does this go? Can poker be “solved” mathematically, in the same way that games like chess and checkers can be solved?
Intuitively, poker seems different. For example, is it a good idea to make a bet that doubles the size of the pot? Well, that depends in part on whether you have a better than 2-to-1 chance of winning. But knowing this depends on what cards your opponents have, and of course this is information that is generally unavailable. And what about bluffing? Doesn’t the use of outright lying and trickery take poker out of the mathematical realm?
Well, Tuomas Sandholm and his student, Andy Gilpin, have been showing, through their leading research, that it is possible to win at poker — at least in head-to-head situations — purely mathematically. Their approach uses game theory, the branch of applied mathematics that has to do with analyzing interactions (especially strategic competitions) between two parties. This is a branch of mathematics that is finding more and more applications in computer science, especially in zero-sum situations (that is, situations where one player improves only at the other player’s expense). Tuomas and Andy, though, have been fascinated with the fact that playing poker involves making decisions with imperfect information. This makes poker a challenging and mathematically interesting application. Furthermore, solving it appears likely to lead to many other useful decision-making applications, in areas as diverse as e-commerce, robotics, and even fighting terrorism.
Along with collaborator Troels Bjerre Sørensen, Tuomas Sandholm and Andy Gilpin have created a winning poker bot in the 2008 AAAI Poker Bot Competition. In a field of 9 bots, playing a tournament and total of 2,160,000 hands, the Sandholm-Gilpin-Sørensen poker bot won the most chips in the heads-up Texas Hold’em Limit competition. (Texas Hold’Em is a popular type of poker; “limit” refers to the variant that limits the amount of money that can be bet per betting round.) Also doing well at the AAAI competition is the well-established group from the University of Alberta. They won the Texas Hold’em No-Limit competition.
For the first time, AAAI also held a 6-player no-limit competition. Exactly how to rank the bots isn’t clear in this case, though in terms of the number of small blinds won, the CMU bot by Sam Ganzfried, Andy Gilpin, and Tuomas Sandholm was fourth out of a field of six.
Well, it’s been a few months since I’ve played poker with Andy and Sam. Time to think about another home game…
Congratulations to Tuomas, Andy, and Sam! Great showing!
Peter Lee @ August 10, 2008
This is some very interesting research. I wonder if the casinos have caught wind of this yet..