Programmers Take On Texas Hold 'em, And Win

(Inside Science) -- Researchers in Canada have developed a poker-playing robot program – a bot – that can solve limited Texas Hold'em poker, a game with ten-thousand billion possibilities.

Imagine someone playing 200 games of poker an hour for 12 hours a day against the same poker robot without missing a day for 70 years. That person couldn't tell the difference between a perfect bot or an imperfect one, said Michael Bowling, a professor of computer science at the University of Alberta in Edmonton, because there is always an element of chance in the hands. With the new program, a person's winnings would be exactly what would be expected in playing against a perfect bot.

To a game theorist, that means the problem has been solved, and marks the largest game of its kind to be solved by an algorithm.

However, that doesn't mean the bot could always defeat a human player in an actual game, Bowling said. Further, they found, the dealer, or the "first mover," has a distinct advantage, something poker players have suspected to be true, although the bot found some nuances that would make for a better strategy.

The results are published in this week's Science.

Since the early days of computing, scientists have attempted to crack chess, considered by many the most difficult and intellectual of games. It took almost half a century for them to devise chess programs good enough to beat grandmasters. In 1997, an IBM computer program called Deep Blue defeated world chess champion Garry Kasparov in a six-game match. You now probably have a desktop computer program just as good as Deep Blue.

Chess programs use artificial intelligence techniques where "lookaheads" at future moves (if I do this and he does that and I do this) are a central element.

But chess is a perfect-information game, meaning the two players both have all the information they need to play. They know what pieces are on the board, and where they can move. Checkers also is a perfect-information game that has been solved by computers.

Poker, like Scrabble, is an imperfect-information game where the players do not have all the information they need. Game theorists love it, and there is an annual worldwide competition to design the best card-playing bot to solve poker.

Lookaheads will not solve the problems in imperfect-information games, and, unlike chess, luck is a factor.

The Alberta bot is gigantic, filling 15 terabytes of data even after compression. It consists largely of a look-up table.

The scientists researching poker are using game theory, a method of decision-making developed by mathematicians like John Von Neumann (who was a master poker player) and John Nash (immortalized in the film "A Beautiful Mind"). Bowling and his colleagues, concentrated on heads-up limited Texas hold'em poker, a variant of the game.

In this limited version, players are dealt two cards face down, and five "community cards," shared by both players in four betting rounds. The amounts of each bet are fixed, and each player has the only choices of raising the bet, calling the bet, or folding. The pot grows with each round.

You have no control over what cards are dealt. You do not know what cards your opponent has face down on the table; the best you can do is to memorize betting history.

Your task is to make the best five-card hand you can and hope it is better than your opponents', or at least make he or she think it is.

In the words of the Kenny Rogers song: "You've got to know when to hold 'em, know when to fold 'em, know when to walk away, and know when to run."

The possible information sets, which translate to possible moves, are vast, about 319,000,000,000,000 (319 trillion), according to Tuomas Sandholm, who runs another poker lab at Carnegie Mellon University in Pittsburgh, and who wrote an accompanying article in Science. 

No-limit Texas Hold 'em is a far more popular game because it has no limit on the money bet. The number of information sets is almost unfathomable, "a number bigger than the number of atoms in the universe," said Sandholm. "If each atom in the universe was a universe, you still wouldn't get to that number [6.38 x 10¹⁶¹, or 6.38 with 161 zeroes after it.]"

That game has not been solved, and Bowling said it probably never will. Sandholm's team won the computer poker world championship with a program to play the unlimited game, but they didn't solve it.

Avi Rubin, a poker player who also is director of the Information Security Institute at Johns Hopkins University, said the notion the dealer or first mover has an advantage is well known to poker players because that person also has the last decision, and it comes when the pot is at its largest.

The Alberta bot is "no threat to human poker players," he said; the games people play are far more complicated than the limited game Bowling and company solved. Many games are played with eight or nine people at a table. A newly popular version of poker called Omaha Hold'em involves each player getting four cards down, and making the best hand using two of them plus three of the community cards, he said.

Why should serious scientists engage in this kind of research? The Alberta scientists said game theory has well-known practical applications, including use in negotiations, auctions, security and medical research--and, quoting Alan Turing--"the sheer fun of the thing."