Advertisement

I'm all in: University of Alberta unveils computer that is unbeatable at Texas hold 'em

I'm all in: University of Alberta unveils computer that is unbeatable at Texas hold 'em

Watch out poker players, because scientists have developed a computer that is a Texas hold ’em card shark.

While in the world of computer game theory this seems like fun and games, it may in fact have serious, real-world implications from airport security to coast guard patrolling.

Basically, the card game – at least the head-to-head version that is so popular around the globe – has been “solved” by a newly-developed computer algorithm.

A team of researchers at Edmonton’s University of Alberta have come up with a program that provably can do no worse than tie in this specific variant of poker.

“When we say solved, we mean it exactly in the same sense that we might solve a mathematical equation, as in ‘solve for X’ in an algebra problem,” said Michael Johanson, co-author of the Science magazine study published today.

“In this case, the ‘X’ that we solve for is a perfect, unbeatable strategy for playing this poker game.”

While the computer program is not exactly perfect, it does come as close as possible by being able to reliably compute an optimal playing strategy that assumes their opponent is playing a perfect game.

“So much so that even if a human knew the perfect counter-strategy to use, and spent their entire life playing against our program – 200 games per hour, 12 hours per day, every day, for 70 years, or 60 million games – that still wouldn’t be enough games to have statistical confidence that they were winning at the end.” Johanson explained.

“So even though someone might win over a short match by playing well and also being luckier than our program, it is no longer possible to beat it over a long match.”

Until now, for other games like checkers, researchers have come up with computer players that can play the game perfectly, so that it never loses to any opponent.

In checkers, if both players play perfectly, then the game always ends in a draw, says Johanson.

But these simple games are known as “deterministic perfect information” games – deterministic meaning that there is no random chance, and perfect information meaning that both players know everything there is to know about the game. In checkers, Johanson says this is done by just looking at the board. “You can see all of the pieces, and no information is hidden from you,” he said.

Poker, on the other hand, is a “stochastic imperfect information game” – stochastic because there is random chance involved in the card deals, and imperfect information because we can’t see the opponent’s cards.

“Whenever our program has to act, there is a critical piece of information that it cannot know, and so it has to reason about what cards the opponent might be holding,” Johanson said.

“So, our result of solving this poker game means two things. First, we now have an essentially perfect, unbeatable strategy for playing the game, meaning it cannot lose to any human or computer adversary, even if that adversary has a copy of our program and strategy. And second, this is the first time that anyone has ever solved a non-trivial imperfect information game that humans actually play. “

The checkers program Chinook defeated humans for the first time in 1994, and Deep Blue beat Kasparov in chess back in 1997.

Even though heads-up limit Texas hold’em is a smaller game than checkers in terms of the number of decision points, it wasn’t until 2008 that the University of Alberta team’s program, Polaris, defeated human poker pros for the first time.

“Checkers was solved in 2007, and it took another seven years for us to now solve this poker game,” Johanson said.

Game theory has practical applications for security problems. Researchers from the University of Southern California have used game theory to solve homeland security issues like scheduling air marshals on flights, designing airport security schedules, and coast guard patrols for ports.

This new computer program has also recently been applied to medicine too, specially for developing diabetes treatment policies.

“This approach is useful because there is much we don’t know about a newly-diagnosed diabetes patient, such as how their body will react to insulin or exercise or sleep,” Johanson explained.

“Our poker algorithm learns a safe way to begin treating this patient, without risking overdosing or undressing insulin, while we learn more about their body.”