January 09, 2015

Poker program Cepheus is unbeatable, claim scientists

It may not win every hand it is dealt, but over time, no one can beat Cepheus, a computer program that scientists claim plays a near-perfect game of poker.

Unveiled in Canada on Thursday, the researchers believe that Cepheus is so good that a seasoned poker star could spend their whole life playing against it and still not come out on top.

To learn the game, Cepheus spent two months playing the equivalent of more than a billion billion hands of Texas hold’em, which is more poker games than have been played in the entirety of human history.

The feat required the number-crunching power of four thousand computer processors, each handling six billion hands every second. With each game Cepheus played, the program built up a database of cards dealt, betting decisions and outcomes. At the end of the marathon training session, the database contained 11 terabytes of information on calls, raises and folds for every hand a player could have.

Cepheus learns from an algorithm that essentially minimises its regrets: the program reviews every decision made and then learns which moves paid off and which cost it the hand. “For every single possible situation you could get into, it has a description for how you should play,” said Neil Burch, a computer scientist who helped develop Cepheus at the University of Alberta Computer Poker Research Group.

The program plays a variant of poker called heads-up limit hold’em, made famous by Michael Craig’s 2005 book, The Professor, the Banker and the Suicide King. The game involves two players who bet fixed amounts with a limit on the number of raises allowed.

“Cepheus starts off with a strategy that’s quite terrible,” said Burch. “But every time it plays a hand it comes up with a better strategy.”

It is impossible to make a program that wins every hand, because an opponent can always be dealt a pair of aces or another lucky hand. Instead, Cepheus plays the hand it is dealt in the best way possible. Before every decision, it checks its cards against the database and uses probability to play the best possible game, whether that means calling, raising or folding its hand.

“Cepheus loses to no one over a long enough time. You just have to play enough hands so that luck goes away,” said Burch.

The scientists describe how they created Cepheus in the latest issue of the journal Science. The program can be played online at the University of Alberta’s website.

“I’m sure we’ll get plenty of emails from people who will play 20 or 30 hands against it, win a little bit, and then happily declare victory and say Cepheus must have a bug. But while a human or another program could get lucky and beat Cepheus in a short match, nobody could do it consistently over a long match,” said Michael Johanson, a researcher at the lab.

The program marks a milestone in artificial intelligence and game theory because it makes optimal decisions in a game where only limited information is available: a player’s own cards and those face up on the table (the flop, turn and river, in poker terminology).

Until now, all of the major games that have been “solved” by computers are “perfect-information games” such as chess and checkers where the full history of the game is known to each player.

Poker and other card games are known as imperfect-information games and are much harder for computers to master because each player has only a limited amount of information on which to base their decisions.

The parallels between poker and real-life decision-making mean that card-playing programs are far more than toys. John von Neumann, the father of modern computing, was inspired by bluffing in poker to develop game theory. Versions of game-playing programs can be used to find the most effective ways to patrol coastlines for drugs traffickers, or the best way to schedule sky marshals on commercial flights.

The Canadian researchers said they have been careful not to release information about Cepheus that could be used to win fortunes on online casinos. But other computer experts could potentially recreate the program and unleash it on the web. Even if that happened, Burch is not convinced it would make a fortune from hapless online human players. “It’s like being a really good poker player. If you start beating people all the time, nobody will want to play with you,” he said.

1 comment:

  1. I really realize this post. Thanks for sharing really very much informative. It’s really very nice post looking forwards for another one. Matka || Satta Matka || Satta Matka Result || Mumbai Matka || Kalyan Matka

    ReplyDelete