A fresh Texas Holdem-playing AI terrorhas emerged barely a month after a supercomputer-powered bot claimedvictory over four professional poker players. But insteadof relying ona supercomputers hardware, the DeepStack AI has shown how it too can decisively defeat human poker pros while running on a GPU chip equivalent to those found in gaming laptops.

The success of anypoker-playing computer algorithm inheads-up, no-limit Texas Holdem is no small feat. Thisversion of two-player poker with unrestricted bet sizes has 10160possible plays at different stages of the gamemore than the number of atoms in the entire universe. But the Canadian and Czech reseachers who developed the new DeepStack algorithm leveraged deep learning technology to create the computer equivalent of intuition and reduce the possible future plays that needed to be calculated at any point in the gameto just 107. That enabled DeepStacks fairly humble computer chip to figure out its best move for each playwithin five seconds and handily beat poker professionals from all over the world.

To make this practical, we only look ahead a few moves deep,saysMichael Bowling, a computer scientist and head of the Computer Poker Research Groupat the University of Alberta in Edmonton, Canada.Instead of playing from there, we useintuition to decide how to play.

This is a huge deal beyond just bragging rights for an AIs ability to beat the best human poker pros. AI that can handle complex poker games such as heads-up, no-limit Texas Holdem could alsotackle similarly complex real-world situations by making the best decisionsin the midst of uncertainty. DeepStacks poker-playing success while running on fairly standard computer hardware could make it much more practical for AI to tackle many other imperfect-information situations involving business negotiations,medical diagnoses andtreatments, or even guiding military robotson patrol. Full details of the research are published in the 2 March 2017 online issue of thejournalScience.

Imperfect-information games have represented daunting challenges for AI until recently because of the seemingly impossible computing resources requiredto crunch all the possible decisions. To avoidthe computing bottleneck, most poker-playing AI have used abstraction techniques that combine similar plays and outcomes in an attempt to reduce the number of overall calculations needed. They solved for a simplified version of heads-up, no-limit Texas Holdem instead of actually running through all the possible plays.

Such an approach has enabledAI to play complex games from a practical computing standpoint, but at the cost of having huge weaknesses in their abstracted strategies that human players can exploit. An analysis showed that four of the top AI competitors in the Annual Computer Poker Competition were beatable by more than 3,000 milli-big-blinds per game in poker parlance. That performance is four times worse than if the AI simply folded and gave up the pot at the start of every game.

DeepStack takes a very different approach that combines both old and new techniques. The older technique isanalgorithm developed by University of Alberta researchers that previously helped come up with a solution for heads-up, limit Texas Holdem (a simpler version of poker with restricted bet sizes). This counterfactual regret minimization algorithm, called CFR+ by its creators, comes up with the best possible play in a given situation by comparing different possible outcomesusing game theory.

By itself, CFR+ would stillruninto the same problem of the computing bottleneck in trying to calculate all possible plays. But DeepStack gets around this by only having the CFR+ algorithm solve for a few moves ahead instead of all possible moves until the end of the game. For all the other possible moves, DeepStack turns to its own version of intuition that is equivalent to a gut feeling about the value of the hidden cards held by both poker players. To train DeepStacks intuition, researchers turned todeep learning.

Deep learning enables AI to learn from example by filtering huge amounts of data through multiple layers of artificial neural networks. In this case, the DeepStack team trained their AI on the best solutions of the CFR+ algorithm for random poker situations. That allowed DeepStacks intuition to become a fast approximate estimate of its best solution for the rest of the game without having to actually calculate all the possible moves.

Deepstack presents the right marriage between imperfect information solvers and deep learning, Bowling says.

But the success of the deep learning componentsurprised Bowling. He thought the challenge would prove too tough even for deep learning. His colleaguesMartin Schmid and Matej Moravcikboth first authors on the DeepStack paperwere convinced that the deep learning approach would work. They ended upmakinga private bet on whether or not the approach would succeed. (I owe them a beer, Bowling says.)

DeepStack proved its poker-playing prowess in 44,852 games played against 33 poker pros recruited by the International Federation of Poker from 17 countries. Typically researchers would need to have their computer algorithms play a huge number of poker hands to ensure that the results are statistically significant and not simply due to chance. But the DeepStack team used a low-variance technique called AIVAT that filters out much of the chance factor and enabled them to come up with statistically significant results with as few as 3,000 games.

We have a history in group of doing variance reduction techniques, Bowling explains.This new technique was pioneered in our work to help separate skill and luck.

Of all the players, 11 poker pros completed the requested 3,000 games over a period of four weeks from November 7 to December 12, 2016. DeepStack handily beat 10 of the 11 with a statistically significant victory margin, and still technically beat the 11th player. DeepStacks victory as analyzed by AIVATwas 486 milli-big-blinds per game (mbb/g). Thatsquite a showing given that 50 mbb/g is considered a sizable margin of victoryamong poker pros. This victory margin also amounted to over 20 standard deviations from zero in statistical terms.

News of DeepStacks success is just the latest blow to human poker-playing egos. ACarnegie Mellon University AI called Libratus achieved its statistically significant victory against four poker pros during a marathon tournament of 120,000 games totalplayedin January 2017. That heavily publicized eventled some online poker fans to fret about the possible death of the gameat the hands of unbeatable poker bots. But to achieve victory, Libratus still calculatedits main poker-playing strategy ahead of time based on abstracted game solvinga computer- and time-intensive process that required15 million processor-core hours on a new supercomputer called Bridges.

Worried poker fans may have even greater cause for concern with the success of DeepStack.Unlike Libratus, DeepStacks remarkably effective forward-looking intuition means itdoes not have to do any extra computing beforehand. Instead, it always looks forward by solvingforactualpossible plays several moves ahead and then relies on its intuition to approximate the rest of the game.

This continual re-solving approach that can take place at any given point in a game is a step beyond the endgame solver that Libratus used only during the last betting rounds of each game. And the fact that DeepStacks approach works on the hardware equivalent of a gaming laptop could mean the world will see the rise of many more capable AI bots tackling a wide variety of challenges beyond pokerin the near future.

It does feel like a breakthrough of the sort that changes the typesof problems we can apply this to, Bowling says. Most of the work of applying this to other problems becomes whether can we get a neural network to apply this to other situations, andI think we have experience with using deep learning in a whole variety of tasks.

IEEE Spectrum's award-winning robotics blog, featuring news, articles, and videos on robots, humanoids, drones, automation, artificial intelligence, and more. Contact us:e.guizzo@ieee.org

Sign up for the Automaton newsletter and get biweekly updates about robotics, automation, and AI, all delivered directly to your inbox.

Computer scientists take valuable lessons from a human vs. AI competition of no-limit Texas hold'em 13May2015

Howand whycomputer programs face off over the poker table 17Jul2012

Making computers unbeatable at Texas Hold 'em could lead to big breakthroughs in artificial intelligence 25Feb2015

A computer algorithm's triumph over the Texas Hold'em card game could lead to real-world security applications 8Jan2015

An AI named Libratus has beaten human pro players in no-limit Texas Hold'em for the first time 31Jan

The European Parliaments draft recommendations for governing the creation and use of robots and artificial intelligence includes rights for smartrobots 22Feb

Shakey's creators and colleagues share inside stories at the celebration and talk about robotics today 17Feb

University of Michigan "micromotes" aim to make the Internet of Things smarter without consuming more power 10Feb

Ubers experiment in San Francisco showed that bicycles and bike lanes are a problem self-driving cars are struggling to crack 31Jan

The rise of deep-learning AI could enable computers to automatically count the crowds at future inauguration days 24Jan

Gill Pratt explains why nobody in the automotive industry is anywhere close to full autonomy 23Jan

Neurala wants to build powerful AI systems that run on smartphone chips to power robots, drones, and self-driving cars 17Jan

An artificial intelligence will play 120,000 hands of heads-up, no-limit Texas Hold'em against four human poker pros 10Jan

An AI alternative to deep learning makes it easier to debug the startups self-driving cars 29Dec2016

3DSignals' deep learning AI can detect early sounds of trouble in cars and other machines before they break down 27Dec2016

If we dont get a ban in place, there will be an AI arms race 15Dec2016

The head of Alphabets innovation lab talks about its latest "moonshot" projects 8Dec2016

Maluuba sees reading comprehension and conversation as key to true AI. It's built a new way to train AIs on those skills 1Dec2016

Game theorist shows how pedestrians will exploit self-driving cars' built-in yen to yield 26Oct2016

At the White House Frontiers Conference, Stanford's Li details three crucial reasons to increase diversity in AI 19Oct2016

Continued here:

Texas Hold'em AI Bot Taps Deep Learning to Demolish Humans - IEEE Spectrum