Man vs machine: poker

It looks like we will soon add poker to the list of games (chess, checkers, backgammon) at which machines have surpassed humans. Note we're talking about heads up play here. I imagine machines are not as good at playing tournaments -- i.e., picking out and exploiting weak players at the table.

How long until computers can play a decent game of Go?

Associated Press: ...Computers have gotten a lot better at poker in recent years; they're good enough now to challenge top professionals like Laak, who won the World Poker Tour invitational in 2004.

But it's only a matter of time before the machines take a commanding lead in the war for poker supremacy. Just as they already have in backgammon, checkers and chess, computers are expected to surpass even the best human poker players within a decade. They can already beat virtually any amateur player.

"This match is extremely important, because it's the first time there's going to be a man-machine event where there's going to be a scientific component," said University of Alberta computing science professor Jonathan Schaeffer.

The Canadian university's games research group is considered the best of its kind in the world. After defeating an Alberta-designed program several years ago, Laak was so impressed that he estimated his edge at a mere 5 percent. He figures he would have lost if the researchers hadn't let him examine the programming code and practice against the machine ahead of time.

"This robot is going to do just fine," Laak predicted.

The Alberta researchers have endowed the $50,000 contest with an ingenious design, making this the first man-machine contest to eliminate the luck of the draw as much as possible.

Laak will play with a partner, fellow pro Ali Eslami. The two will be in separate rooms, and their games will be mirror images of one another, with Eslami getting the cards that the computer received in its hands against Laak, and vice versa.

That way, a lousy hand for one human player will result in a correspondingly strong hand for his partner in the other room. At the end of the tournament the chips of both humans will be added together and compared to the computer's.

The two-day contest, beginning Monday, takes place not at a casino, but at the annual conference of the Association for the Advancement of Artificial Intelligence in Vancouver, British Columbia. Researchers in the field have taken an increasing interest in poker over the past few years because one of the biggest problems they face is how to deal with uncertainty and incomplete information.

"You don't have perfect information about what state the game is in, and particularly what cards your opponent has in his hand," said Dana S. Nau, a professor of computer science at the University of Maryland in College Park. "That means when an opponent does something, you can't be sure why."

As a result, it is much harder for computer programmers to teach computers to play poker than other games. In chess, checkers and backgammon, every contest starts the same way, then evolves through an enormous, but finite, number of possible states according to a consistent set of rules. With enough computing power, a computer could simply build a tree with a branch representing every possible future move in the game, then choose the one that leads most directly to victory.

...The game-tree approach doesn't work in poker because in many situations there is no one best move. There isn't even a best strategy. A top-notch player adapts his play over time, exploiting his opponent's behavior. He bluffs against the timid and proceeds cautiously when players who only raise on the strongest hands are betting the limit. He learns how to vary his own strategy so others can't take advantage of him.

That kind of insight is very hard to program into a computer. You can't just give the machine some rules to follow, because any reasonably competent human player will quickly intuit what the computer is going to do in various situations.

"What makes poker interesting is that there is not a magic recipe," Schaeffer said.

In fact, the simplest poker-playing programs fail because they are just a recipe, a set of rules telling the computer what to do based on the strength of its hand. A savvy opponent can soon gauge what cards the computer is holding based on how aggressively it is betting.

That's how Laak was able to defeat a program called Poker Probot in a contest two years ago in Las Vegas. As the match progressed Laak correctly intuited that the computer was playing a consistently aggressive game, and capitalized on that observation by adapting his own play.

Programmers can eliminate some of that weakness with game theory, a branch of mathematics pioneered by John von Neumann, who also helped develop the hydrogen bomb. In 1950 mathematician John Nash, whose life inspired the movie "A Brilliant Mind," showed that in certain games there is a set of strategies such that every player's return is maximized and no player would benefit from switching to a different strategy.

In the simple game "Rock, Paper, Scissors," for example, the best strategy is to randomly select each of the options an equal proportion of the time. If any player diverted from that strategy by following a pattern or favoring one option over, the others would soon notice and adapt their own play to take advantage of it.

Texas Hold 'em is a little more complicated than "Rock, Paper, Scissors," but Nash's math still applies. With game theory, computers know to vary their play so an opponent has a hard time figuring out whether they are bluffing or employing some other strategy.

But game theory has inherent limits. In Nash equilibrium terms, success doesn't mean winning — it means not losing.

"You basically compute a formula that can at least break even in the long run, no matter what your opponent does," Billings said.

That's about where the best poker programs are today. Though the best game theory-based programs can usually hold their own against world-class human poker players, they aren't good enough to win big consistently.

Squeezing that extra bit of performance out of a computer requires combining the sheer mathematical power of game theory with the ability to observe an opponent's play and adapt to it. Many legendary poker players do that by being experts of human nature. They quickly learn the tics, gestures and other "tells" that reveal exactly what another player is up to.

A computer can't detect those, but it can keep track of how an opponent plays the game. It can observe how often an opponent tries to bluff with a weak hand, and how often she folds. Then the computer can take that information and incorporate it into the calculations that guide its own game.

"The notion of forming some sort of model of what another player is like ... is a really important problem," Nau said.

Computer scientists are only just beginning to incorporate that ability into their programs; days before their contest with Laak and Eslami, the University of Alberta researchers are still trying to tweak their program's adaptive elements. Billings will say only this about what the humans have in store: "They will be guaranteed to be seeing a lot of different styles."