The NYT has a very interesting “article”:http://www.nytimes.com/2003/07/10/technology/circuits/10poke.html today on AI and poker. A group of researchers in Alberta are using game theory to create automated ‘bots that can take on and beat most players. Now this was a little worrying for me; two months ago, I wrote a “couple”:https://www.crookedtimber.org/archives/000064.html of rather confident “posts”:https://www.crookedtimber.org/archives/000068.html suggesting that game theory wasn’t very helpful in solving complex and open-ended games like poker. Indeed, as Chad Orzel “notes”:http://steelypips.org/principles/2003_06_29_principlearchive.php#105708829647353420, human beings sometimes have difficulty in dealing with this sort of stuff too.
As it turns out though, the research project in Alberta reveals as much about the limits as the merits of game theory. The researchers have to make some radical simplifications in order for game theory to be useful at all, as they reveal in this “report of their findings”:http://www.cs.ualberta.ca/~darse/Papers/IJCAI03.pdf. First, they have to lop most of the branches of the “game tree” – the map of possible moves, responses and outcomes – in order to make the game tractable at all. They assume that all possible hands can be classified as falling into one of six or seven “buckets” of broadly equivalent hands. What’s more, their program doesn’t even start to try to analyse the play pattern of their opponent; instead, it assumes that the opposing player is also playing as if she was a computer program – i.e. that she’s employing optimal strategies. This means that their program isn’t going to be able to exploit patterns in its opponent’s game, although it will tend to win in the long run against players who follow “strictly dominated” strategies (i.e., who make really bone-headed mistakes). The authors ran the program against an expert poker player, who seems to have started to win consistently as soon as he stopped trying to exploit the program’s (non-existent) human weaknesses.
The researchers have made an interesting contribution – poker is a tough problem compared to, say, chess (which is much more rigid and deterministic, and therefore much more amenable to modelling). As they say, it’s a real achievement to have created a game theoretic poker player that isn’t completely outclassed by its human opponents. But there are good reasons to suspect that this line of research won’t go that much further – poker is too complex, and too dependent on subtle social interactions that are nearly impossible to model properly. The ‘bots don’t pose too much of a threat to you yet (as long as you remember not to draw to inside straights).
{ 6 comments }
dsquared 07.10.03 at 5:27 pm
Hrrrmmmmm … I’d be more impressed if it was bridge.
Jeremy Osner 07.10.03 at 5:52 pm
I know little about game theory; does the fact that they have created this program based on a simplified game tree have any bearing on the possibility of creating a program that would work without the simplifications? — That is, would the same process be involved in building such a program, just a bit more painstaking; or is it a totally different problem?
Scott Martens 07.10.03 at 6:14 pm
This is a pretty narrow result. It applies to one variety of poker, and takes advantage of a game-tree reduction strategy whose broader applicability is difficult to ascertain, and the result is, in their words “not totally outclassed by the best human players.”
Do note carefully sections 5.2 and 5.3. It suggests to me that a major factor in their program’s success is its unorthodox playing style and inability to care how big the pot is. Given enough time, their grand master player was able to beat the computer, and they suggest that given enough time a really good player might always be able to do so. Of course, in the real world, the few thousand games you might need to work it out will probably leave you broke.
It suggests to me that the human factors still dominate poker, and that their code is taking unique advantage of that, not that they are genuinely modelling anything like an optimal strategy.
Henry 07.10.03 at 10:56 pm
Jeremy
as far as I understand it, there are two basic simplifications here. One is simplifying the game tree – frankly I’m not really qualified to comment, but I’m not confident that the simplifications work. Second is the assumption that the computer plays against another opponent that tries to optimize strategies. This is rather problematic – and probably cripples the real life application of the approach to games with serious players. Like Scott, I have my doubts as to whether this approach can do a good job, but it’s like Johnson’s dog; it’s a wonder that it’s being done at all.
Rich Rostrom 07.10.03 at 11:14 pm
On-line poker is a fairly big business these days. There have been reports (though AFAIK no proof) that some people have built programs which can log into these on-line games and play. The theoretical goal is to have a ‘bot’ whose strategy will have a positive return, however small. Unlike a real player, a bot’s time is very cheap, and even if the bot nets only a dollar an hour, a few dozen bots playing 24 hours a day could generate a nice income.
jeremy 07.11.03 at 12:30 am
Back in the days of IRC poker popularity, there were a fair number of bots that had been developed, many of which were quite profitable. While IRC poker wasn’t played for money, it certainly had much better play there than Yahoo or the free online rooms do these days, because the only people who knew about it / played on it were pretty serious about being good players.
I would be very surprised if there weren’t bots that played on online rooms.
Comments on this entry are closed.