Heads-up limit Texas hold 'em poker solved by University of Alberta scientists

Poker players beware — there's a new star in town and it'll beat the best players around.

Researchers from the University of Alberta have created a computer algorithm that essentially solves heads-up limit Texas hold 'em poker — a two-player version of the card game.

• Read the paper in Science
• Listen to an interview with Micheal Bowling on CBC's Quirks & Quarks Saturday

"Can we build a program that makes all the right moves, that it can't be beat no matter what the opponent does against it?" Michael Bowling, a professor for the university's computing science department and one of the authors of the study published in Science, says that was what his team set out to achieve.

If this played online right now, it would certainly be a money winner— Michael Bowling, study co-author

The new algorithm, dubbed CFR, should beat any human out there. Though Bowling admits, the chance of being perpetually dealt bad cards means someone could theoretically beat it.

In long-term games, where the luck evens out, opponents don't stand much of a chance.

"While it's possible that a human could sit down and play the perfect response to it, even after a lifetime, [the person] still wouldn't be guaranteed to be winning," Bowling says.

For those interested in trying, a lifetime would be 70 consecutive years of playing 12 hours a day, seven days a week without a single break.

The algorithm could also easily challenge online players.

"If this played online right now, it would certainly be a money winner," says Bowling of the algorithm's play.

But don't expect Bowling and the other computer poker research group members to be cashing in on the program any time soon by setting the algorithm loose on online casino games.

They don't use the program in online casino play. And there's not much money to be won in this version of poker, Bowling says. High-stakes games tapered off around 2010 when the gap between those considered the best narrowed significantly and winnings dropped.

'Test bed' for artificial intelligence ideas

Few of the scientists actually play the game, but they are fascinated by its application to artificial intelligence.

"Games have always been seen as a test bed and sort of a proving ground for new artificial intelligence ideas," says Bowling.

• Why the University of Waterloo churns out poker stars
• Are we taking artificial intelligence seriously enough?

Poker mimics real world challenges that involve uncertainty, but allows scientists to test their ideas in a safe way — without experimenting on people.

Bowling hopes to take game theory and apply it to creating artificial intelligence algorithms for real-life decision making in areas like national security. It could be applied to setting up patrols and checkpoints at airports or on public transit to catch fare evaders. 

"You want to build something that essentially has no hole. That can't be beaten.… That same kind of game theoretic reasoning is what we have to do in poker."

He's already been working with a team studying whether artificial intelligence can adjust how much insulin people with chronic diabetes should take.

4,000 CPUs required

None of this is a quick process, and creating the new algorithm to crack the game took a long time.

The game has an "enormous scale" with billions  — or 10,000 billion to be more exact — decisions a player might have to make, Bowling says. The scientists required four petabytes, or 4,000 terabytes, of disc space to write down a strategy.

The algorithm started without knowing how to play the game. It then played hand after hand against itself, updating its strategy every time.

That process called for "a massive amount of computational power." The scientists set up 4,000 central processing units (CPUs) to play these hands. The computers took two months to play out all the possibilities.

"In the end, it actually played more hands of poker than probably all of humanity has ever played the game," says Bowling.

A single CPU would have needed 1,000 years to do the same computation.

Next, the computer poker community is focusing on the no-limit version of the game, Bowling says, but its complexity is "dramatically larger."

He doesn't believe no-limit poker can be essentially solved and thinks the next benchmark will be to see if technology can beat the best no-limit poker players instead. 

Watson won against humans on Jeopardy, and Deep Blue reigned over Garry Kasparov in chess. It may only be a matter of time before artificial intelligence wins at the poker table too.