Know when to fold 'em: Researchers solve heads-up limit hold 'em poker

January 8, 2015
University of Alberta researcher Michael Bowling and his team have solved heads-up limit Texas hold'em poker. Credit: John Ulan, University of Alberta

For over a half-century, games have been test beds for new ideas in Artificial Intelligence (AI) and the resulting successes have marked significant milestones - Deep Blue defeated Kasparov in chess and Watson defeated Jennings and Rutter on Jeopardy! However, defeating top human players is not the same as actually solving a game, and for the first time researchers in the Computer Poker Research Group at the Faculty of Science, University of Alberta in Canada, have essentially solved heads-up limit hold'em poker.

"Poker has been a challenge problem for going back over 40 years, and until now, heads-up limit Texas hold'em was unsolved," says Bowling, lead author and professor in the Faculty of Science whose findings were published January 9 in Science.

Poker is a family of games that exhibit imperfect information, where players do not have full knowledge of past events. The most popular variant of poker today is Texas hold'em. When it is played with just two-players (heads-up) and with fixed bet-sizes and number of raises (limit), it is called heads-up limit hold'em. While smaller than checkers, the imperfect information nature of heads-up limit hold'em makes it a far more challenging for computers to play or solve.

"We define a game to be essentially solved if a lifetime of play is unable to statistically differentiate it from being solved at 95% confidence," explains Bowling. "Imagine someone playing 200 hands of poker an hour for 12 hours a day without missing a day for 70 years. Furthermore imagine them employing the worst-case, maximally exploitive, opponent strategy, and never making a mistake."

While many perfect information games (where all players are informed of everything that has occurred in the game prior to making a decision) have been solved, e.g., Connect Four, no nontrivial imperfect information game played competitively by humans has previously been solved. These games are more challenging, with theory, computational algorithms, and instances of solved games lagging behind results in the perfect information setting. And, while perfect information may be a common property of parlour games, it is far less common in real-world decision making settings.

"The breakthroughs behind this result are general algorithmic advances that make game-theoretic reasoning in large-scale models of any sort more tractable," says Bowling.

And, while seemingly playful, game theory has always been envisioned to have serious implications, including a surge in game-theoretic applications involving security, such as systems being deployed for airport checkpoints, air marshall scheduling, and coast guard patrolling. With real-life decision-making settings almost always involving uncertainty and missing information, algorithmic advances, such as those needed to solve poker, are needed to drive future applications.

You can query the program's strategy or play against it yourself online at: http://poker.srv.ualberta.ca.

Explore further: Does emotional stability affect the success of online poker players?

More information: "Heads-up limit hold'em poker is solved," www.sciencemag.org/lookup/doi/ … 1126/science.1259433

Related Stories

The reason we lose at games

January 7, 2013

If you have ever wondered why you never seem to win at skill-based games such as poker or chess, there might be a very good reason. Writing in PNAS, a University of Manchester physicist has discovered that some games are ...

Recommended for you

New method analyzes corn kernel characteristics

November 17, 2017

An ear of corn averages about 800 kernels. A traditional field method to estimate the number of kernels on the ear is to manually count the number of rows and multiply by the number of kernels in one length of the ear. With ...

Optically tunable microwave antennas for 5G applications

November 16, 2017

Multiband tunable antennas are a critical part of many communication and radar systems. New research by engineers at the University of Bristol has shown significant advances in antennas by using optically induced plasmas ...

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.