Don’t hold ’em – just fold ’em

The best poker player in the world doesn’t have a poker face. In fact — it has no face at all.

The new poker expert is an algorithm (AL-go-RITH-em), or problem-solving program. Called Cepheus, it has solved one form of this card game. “Solved,” in this case, means the program knows the game well enough to win against any human.

And this new algorithm may be useful beyond the card table. It can win at poker even without knowing what cards the other players are hiding. That skill may be useful elsewhere. For instance, it might help guide business decisions or predict terrorist attacks. In those circumstances, a decision-maker will seldom have all of the information he or she feels are needed.

The algorithm is “a big step toward understanding games that are closer to real-world problems,” says Murray Campbell. This computer scientist works at IBM’s Thomas J. Watson Research Center in Yorktown Heights, N.Y. Campbell did not work on the new study. He did, however, help develop a computer called Deep Blue. In 1997, it defeated world champion Garry Kasparov at chess.

For decades, scientists have been designing computers that can win games. There’s even a branch of mathematics — game theory — that focuses on finding the best strategies in competitive situations. And using such strategies, some computers have performed quite well.

In 2011, for instance, a computer program called Watson defeated its human opponents on the television game show Jeopardy! Four years earlier, Canadian computer scientists solved the game of checkers. Their program worked by reviewing the positions of each “stone” and identifying its options for moving. Then, it would choose the very best one to make the perfect move on every turn.

But poker is a harder game. Unlike in checkers, poker players cannot see everyone’s pieces (or here, cards). Another difference: In checkers, every turn has a best move. But for poker, champs don’t always play the same way. To win, a good player might choose to fool his or her opponents, known as bluffing.

Researchers have been trying to develop algorithms that can act like ace poker players and make good decisions even when they don’t have all the information about a problem. “Most algorithms can’t cope with that kind of uncertainty,” Michael Bowling told Science News. But Bowling of the University of Alberta in Edmonton, Canada, and his colleagues succeeded in creating an algorithm that can work with just partial information.

Their Cepheus is the first to solve a game where the players don’t know everything that’s already happened. (For poker, that means the players haven’t seen each other’s cards.)  The computer scientists reported how their program did it on January 9, in the journal Science.

The scientists taught the computer to play a kind of poker called Heads-up Limit Texas Hold’em. Two players each receive two cards. Then five shared cards are revealed to both players. Each player can bet, raise the bet or fold (give up) as the five visible cards are dealt. Each player uses a combination of those shared cards and the two cards he holds to make the best five-card hand.

Bowling and his team designed their algorithm to play against itself and study its own mistakes. For two months, the program ran on more than 4,000 computers. Each computer played over 6 billion hands of poker every second. The algorithm improved with each hand. After about a billion billion hands, the algorithm barely had any mistakes to learn from. It had learned how to always play the best possible poker hand.

The computers played “more hands of poker than humanity has ever played,” Bowling told Science News. He and his team are now modifying their algorithm to work for other forms of poker.

Power Words

algorithm  A group of rules or procedures for solving a problem in a series of steps. Algorithms are used in mathematics and in computer programs for figuring out solutions.

game theory  A field of mathematics that focuses on finding strategies for dealing with competitive situations where the outcome of a participant’s choice of action depends on the actions of other participants. Game theory has been applied to achieve the upper hand in war, business and biology.

computer science  The scientific study of the principles and use of computers.