Poker is one of the most popular card games in the world.   While it might look like a rather simple game on first passing, with a handful of cards and simple betting actions, the way it is designed leads to a lot of complexity that makes it hard for humans to master, much less an artificial intelligence.

House Rules

Since its inception in the early 19th century, it has led to a large number of variations, 

from the classic 5-card straight to the California lowball or the more popular games of recent years, such as 7-card stud and Texas Hold’em.  But regardless of which version you play, they’re all built around the same core principle: imperfect information.

What that means is that no player ever has a complete understanding of what is happening in the game.  You can see the cards in your hand and – depending on the version of the game you’re playing – the communal cards on the table. That’s the only reliable information you have to decide what to do next.  However, given the rules of the game, and the strategies people employ, you can begin to make some intelligent assumptions as to what cards are still in play, what cards your opponent might be holding, and how strong your hand is in context.  It’s what makes poker so exciting to watch, as the game is just as much about what cards your opponent thinks you’re holding as it is the value of the cards themselves.

But this is also what made it so difficult for computers to excel.  Game trees we would use for Chess and Checkers don’t make sense for poker.  Even the likes of Monte Carlo Tree Search for Go isn’t ideal because game trees assume the game has perfect information: i.e. we can see all the pieces on the board, analyse how well the game is going for us, and what decisions to make next based on future outcomes.

It’s been an active research area for years, with a variety of approaches using classical symbolic AI and machine learning exploring different avenues.  Some relied solely on the cards on the table, while others sought to understand the habits of other players and the behaviour of the table as each game continued to play out.  But despite this, no AI ever came close to defeating professional human players.

DeepStack

We finally saw several breakthroughs in the past 10 years with work such as 2016’s DeepStack: a research collaboration between the University of Alberta and both Charles University and the Czech Technical University based in Prague.  Meanwhile, 2017 saw the Libratus program from Carnegie Mellon University.  Both of these poker players have successfully defeated professional players, and this is thanks to a combination of deep learning and a technique called CounterFactual Regret minimisation (CFR).

CFR doesn’t focus on what actions you could take in a situation by anticipating all of the outcomes that might happen based on the cards you have and everything that happened before, instead, it reflects on games it has played and learns what it should have done in that situation.  It learns how to perform better in previous situations based on the cards their opponents might have had as well as what cards the opponents think I might have had. 

It’s right there in the name: it’s minimising the regret it would have from making bad decisions in the future.  

In order for DeepStack to work, it requires a lot of different situations to be visited millions of times to learn that knowledge, and that’s where the Deep Learning comes in. These functions are trained on a deep neural network by feeding it millions of different card situations, but instead of what cards you and your opponent are holding, it feeds in the ‘beliefs’ of each player: what cards do they think I have?  What cards do I think they have?  And from that it can compute a wide range of possible strategies based on the perspectives of each player.  

The more that this runs, it will begin to converge closely on the optimal strategies for different circumstances in a game of poker.  But, of course, how long is a piece of string?  It would take 1000s of human years to reach this, but with deep learning it can converge much faster.

It’s amazing how within the space of 10 years, creating AI that could compete at the highest levels of poker has gone from a distant dream to an eventuality.  And it’s opening up new possibilities, trying different poker variants, or even different card games that perhaps we wouldn’t have approached before.  There are a lot of big challenges still to tackle.