Computer poker
The perfect card sharp
NOUGHTS and crosses (known as tic-tac-toe in America) is one of the first games children learn. The more inquisitive among them soon realise there are strategies that always win if your opponent makes a mistake, and guarantee a draw even if he does not. (The best is to start out in one of the grid’s corners.) When a provably ideal strategy such as this is discovered for any given game, mathematicians describe that game as being “solved”.
Using computers, quite a few games have now been solved in this formal mathematical sense. These include Connect Four, nine-men’s morris and draughts. One thing those examples have in common is that they are “perfect information” games, meaning each player knows, at all times, everything that is going on. Not all perfect information games have been so solved. Chess has not. Neither has Go. But no non-trivial “imperfect information” game, such as one involving playing cards, has ever been solved formally.
Strictly speaking, this remains true. But, as he reports in a paper in this week’s Science, Michael Bowling of the University of Alberta has come close enough to solving a version of poker called Heads-Up Limit Hold’Em (HULHE) that a player armed with his strategy can virtually guarantee coming out ahead of any opponent who is not using it. Such a player would not expect to lose, even over a lifetime of games against an error-free opponent.
Dr Bowling picked HULHE because, in poker terms, it is about as simple as it gets. Only two can play, and betting is heavily restricted. This means only 1.38x1013 (13.8 trillion) different circumstances can arise within it. Still, that is quite a large number, so previous attempts at solving even this form of poker have involved some simplification. But such simplification means losing important details, and the resulting strategies are an imperfect fit to the real game. By speeding up the algorithms, Dr Bowling’s team managed to bring the full game within reach of computational brute force, in the form of 200 computers, each sporting 24 processors, working in parallel for more than two months.
Admittedly, the result will not be of immediate use to card sharps. Although the researchers have built a webpage that contains a strategy tool based on their results (readers can try playing against the machine at
poker.srv.ualberta.ca), they have deliberately hobbled its response times to avoid giving succour to cheats.
Mechanising poker is not, though, Dr Bowling’s primary purpose in developing this software. Many problems that do not look like games, from airport security to medical diagnosis, can nevertheless be modelled as such, and he hopes his algorithm can be adapted to analyse those, too. The program has, nevertheless, answered several bar-room debates about HULHE. It has quantified the well-known advantage that the dealer enjoys. It also suggests that “limping”—a betting strategy favoured by some strong players with certain hands, which involves resisting the temptation to raise the bet as their first action—is usually a bad idea.
Whether computers will ever be able to solve other forms of poker remains doubtful. Merely removing the betting restrictions on HULHE, for instance, boosts the range of possibilities to 6.38x10161, a figure so mind-bogglingly big that it far exceeds the number of subatomic particles in the observable universe. No amount of improvement in computer hardware will ever make such a problem tractable. The only hope is an enormous, and unlikely, conceptual breakthrough in how to attack the question.
There are, of course, poker-playing programs out there already that play more complicated versions of the game than HULHE. The best are better than most humans. But they, like chess-playing programs, do not actually solve the game in a mathematically rigorous sense. They just process more data that a human brain can cope with, and thus arrive at a better answer than most such brains can manage.
The most interesting computational solution to poker, though, would be one that did work more like a human brain, for instance by looking for the famous “tells” that experienced players claim give away their opponent’s state of mind, or even bluffing those opponents about its own intentions. When computers can do that, mere humans—and not just poker players—should really start worrying.
