91av

CIGAR smoke drifts across the baize-topped table as we sit staring suspiciously at each other. Eventually my opponent knocks back his whisky and pushes forward a large stack of chips. “Raise you 50,” he says.

I consider my cards. The full house of three jacks and a pair of queens is an excellent hand – the best I’ve had all night. But the stakes are high and careful reading of my opponent suggests his could be better. Coming after a night of cautious play, his latest extravagance suggests that this time he is onto a winner. His body language points the same way: he made his bet without hesitation and now meets my gaze unflinchingly. It’s all crucial intelligence, because poker is a game of bluff and double bluff that, perhaps more than any other game, hinges on psychology.

Or does it? A team of Canadian computer scientists might soon blow poker’s reputation as the ultimate mind game. They are developing poker-playing computer programs capable of beating human champions. If they succeed, the shock could be as great as when IBM’s chess program Deep Blue beat grandmaster Garry Kasparov six years ago.

For artificial intelligence research, the quest is a momentous one. “Poker is the quintessential human game,” says Jonathan Schaeffer, who leads the group at the University of Alberta in Edmonton. It requires cunning and risk-taking that may seem illogical. If a computer can be made to outperform humans in such an environment it will be a significant milestone, he says.

Poker games for home computers have been around for years. As with chess, they make handy teaching tools, but these simple systems seldom beat good players. Humans learn to outwit them because the programs make predictable decisions: computers make unsophisticated bluffers.

And in poker, bluffing is crucial. The player who has the best cards out of all those who remain in the round wins the pot of money bet. To maximise your winnings, if you have a good hand, you want people to think you have a weak hand so they stay in the game and bet more money. But if you have a weak hand, you might pretend it is strong to scare off the other players, leaving you to pick up the pot.

If you never bluff, your opponents will quickly learn how to predict your hand by watching how you bet. Bluffing creates doubt about the true strength of your hand, and forces your opponents to stay in the game more often even with mediocre hands. This puts them at risk of a heavy loss from your best hands; alternatively, if they fold too often, you will make a large profit from your bluffs.

Either way, you need to be good at deception. Equally important is spotting when your opponents are bluffing. That’s where psychology comes in. Weighty tomes have been written on ways to spot people’s “tells”, the subtle giveaways that reveal a bluff. Does their expression change when they pick up their cards? Do they repeatedly check their hand? Does a cheek twitch, an eyelid tremble? Any of these tics could betray a bluffer. “The critical ability is to acquire more information than you give,” says Alan Schoonmaker, author of The Psychology of Poker.

But the rising popularity of poker sites on the web shows there is more to the game than body language. This year’s World Series Poker championship was won by an internet player (the aptly named Chris Moneymaker) who had never before taken part in a live tournament.

It seems that online players have cracked the top-flight players’ secret weapon: gauging their opponents’ playing styles and betting patterns. “That’s probably the most important psychological factor,” says Schoonmaker. A common way of classifying people is whether they are “tight” or “loose”. Tight players need good cards before they consider staying in the game, while loose players are less fussy, and end up playing more hands. Another scale is whether people are passive or aggressive, referring to how often they raise the stakes.

What this amounts to is that poker players base decisions on an undefined mix of maths, psychology and gut instinct. So how can computers compete? According to most top players, they can’t. “In essence, poker is a people game,” says Barry Tanenbaum, a professional poker player and columnist for Card Player magazine. “In a mathematical sense a computer can assess its chances. But it can’t see someone twitch.” Poker expert David Sklansky is prepared to accept that a program could “theoretically” play the game at a reasonably high level, but he too doubts a computer will ever be built that can beat him.

Such scepticism does not faze the Canadian team. Schaeffer is an old hand at game-playing computer programming. In the 1980s he was one of the leading researchers developing computer chess. He was also responsible for the draughts (checkers) program Chinook, which in 1994 became the first to win an official world tournament against the reigning human world champion. But he says that poker presents a challenge of a different order. That is partly because it is a game of imperfect information; players can’t see each other’s cards so they lack key knowledge about the game, unlike in games of perfect information, such as draughts or chess.

The program that successfully overcomes this obstacle could produce great rewards. It should help to design smarter computers that can make educated guesses about the best course of action based on imperfect information. Such programs might, for example, manage a firm’s purchasing by guessing the likely strategies of business rivals. “When we interact with the real world we are dealing with imperfect information,” Schaeffer says. Poker, unlike chess, “will translate into building programs that exhibit a higher degree of intelligence”, he says.

To develop its poker program, Sparbot, the Edmonton team focused on a commonly played version of poker called limit Texas hold’em, in which bets are limited to one of two denominations – in this case $10 and $20. In the first two betting rounds players can only raise by $10 and in the last two by $20. So the computer never needs to decide how much to bet, only whether to fold, call or raise (see “How to play Texas hold’em”).

So how does Sparbot work? The programmers used the branch of mathematics known as game theory, which concerns situations where two or more players interact with the aim of maximising a certain variable: it could be money, as with poker, or a more abstract quantity such as security, as when the players are opposing military powers.

To understand how this approach relates to poker, consider a highly simplified version of the game in which there are only three cards in the pack – say jack, queen and king – two players and one round of betting, in which there can only be one initial raise. Clearly, player 1 should raise whenever he holds a king. But how often should he bluff by raising when he is holding a queen or a jack? And in response, how often should player 2 call, and how often should she fold?

The answer depends on the size of the bet relative to the size of the pot. Say the bet is $10 and there’s $20 in the pot: it turns out that player 1 should bluff one-quarter of the time and player 2 should call two-thirds of the time.

Unfortunately, game theory has its limitations. As the number of possible hands and betting sequences rise, the problem quickly becomes too large for even the most powerful computers to calculate. And poker has a huge number of variables. In two-player limit Texas hold’em (played with a full deck of cards) there are a billion billion possible combinations of hands and betting sequences.

To cut the problem down to more manageable proportions, Sparbot classifies its hand into one of seven groups according to its strength in the poker ranking table. Even this leaves 30 million possible combinations of hand-groups and betting sequences, and it took a powerful computer seven days to churn out a look-up table that relates what to bet with a given hand and preceding betting sequence. But once that was done, Sparbot could refer to the table to decide how to play, and that takes only a matter of milliseconds.

Man versus machine

Last year, the team set up a website on which members of the public could play Sparbot head-to-head – for pretend money. The challenge was accepted by more than 15,000 people, ranging from novices to masters, and they played hundreds of thousand of hands. Overall the computer came out ahead, by over a dollar a hand, on average.

Sparbot’s inability to see opponents’ faces did not seem to hamper it. Of course, the humans couldn’t see Sparbot’s face either, but the humans had weaknesses that Sparbot didn’t. If Sparbot had a run of good luck, many players experienced “strong emotional reactions” that affected their judgement, according to Darse Billings, a former professional poker player and now the program’s lead designer. Sparbot, of course, doesn’t have emotions.

One of the program’s strongest challenges came in January, when Gautam Rao, a top online player also based in Edmonton, agreed to play an exhibition match against Sparbot. At first, things went badly for Rao. He followed his usual aggressive tactics, and by the end of three days he was down more than $2200. Then he realised what was going wrong. “The computer wasn’t getting scared,” he recalls. So he started playing less aggressively, and it paid dividends. After seven days and more than 7000 hands, he finally quit, $3000 up.

Despite Sparbot’s defeat, the programmers were happy it had performed as well as it did. Their work received wide acclaim when in August it won the distinguished paper award at the 2003 International Joint Conference on Artificial Intelligence. But the team is already working to surpass Sparbot. Its big weakness, Billings says, is a lack of “opponent modelling” – predicting people’s style of play based on their past performance. So the team has started work on a program called Adaptibot which does just that.

Adaptibot records the exact details of every hand its opponent plays. This allows it to classify players in a much more refined way than the traditional psychological scales of loose/tight and passive/aggressive. The next time it encounters a familiar betting sequence, Adaptibot assumes the opponent has a similar distribution of hands as before, and bets accordingly. “Looseness or agressiveness is subsumed by the data on how someone is statistically likely to play,” Billings says.

Although the program is still in development, its main flaw is already clear: it performs less well while it is still getting to know an opponent. So now the team is considering a Sparbot-Adaptibot hybrid that starts off by using game theory, but then shifts towards opponent modelling. “We are really convinced that the adaptive approach is the way to go,” Billings says.

While the Edmonton team seems closest to developing a world-beating program, others are also taking an interest in poker’s unique challenges. At the University of Tsukuba in Japan, a team led by Takehisa Onisawa wants to use a program to work out the best strategy for human players. His system plays a different variant of poker called seven-card stud, in which each player is dealt seven cards, four of which are face-up. The program bases its decisions on simple rules and probability theory in a manner similar to home computer programs. But in a unique twist, it influences certain decisions with fuzzy logic, which helps to translate vague and continuously varying quantities into yes-or-no decisions.

Whether this approach will eventually surpass Adaptibot it’s too early to say. So far the Japanese program has only played against complete novices and beats them only about half the time. Onisawa is not certain that it will ever be possible to beat top human players.

But not too long ago, beating novices was all chess programs could manage. Alan Schoonmaker has no doubt that computers will eventually beat the poker equivalent of a grandmaster. He points out that most games hinge not on the winner’s cunning but on the loser’s errors. That is one area where computers are clearly superior. “If they are properly programmed, computers have the great advantage of following the rules,” he says. “They never make mistakes.” That, at least, is a safe bet.