The following is a conversation with Thomas Sanholm.

He's a professor at CMU and co-creator of Libratus, which is the first AI system to beat top human players in the game of heads-up no limit Texas Hold'em.

He has published over 450 papers on game theory and machine learning, including a best paper in 2017 at NIPS, now renamed to NewRIPS, which is where I caught up with him for this conversation.

His research and companies have had wide-reaching impact in the real world, especially because he and his group not only propose new ideas, but also build systems to prove that these ideas work in the real world.

This conversation is part of the MIT course on Artificial General Intelligence and the Artificial Intelligence Podcast.

If you enjoy it, subscribe on YouTube, iTunes, or simply connect with me on Twitter at Lex Friedman, spelled F-R-I-D.

And now, here's my conversation with Thomas Sanholm.

at the high level, the game of poker, Texas Hold'em, Heads Up!

Texas Hold'em, for people who might not be familiar with this card game?

No Limit Texas Hold'em has really emerged in the AI community as a main benchmark for testing these application independent algorithms for imperfect information game solving.

And this is a game that's actually played by humans.

You don't see that much on TV or casinos because, well, for various reasons, but you do see it in some expert level casinos and you see it in the best poker movies of all time.

It's actually an event in the World Series of poker, but mostly it's played online and typically for pretty big sums of money.

And this is a game that usually only experts play.

So if you go to your home game on a Friday night, it probably is not going to be heads up, no limit Texas hold them.

It might be no limit Texas hold them in some cases, but typically for a big group and it's not as competitive.

Much like chess or go in that sense, but an imperfect information game, which makes it much harder, because I have to deal with issues of you knowing things that I don't know, and I know things that you don't know, instead of pieces being nicely laid on the board for both of us to see.

So in Texas Hold'em, there's 2 cards that you only see, that belong to you.

And then there is, they gradually lay out some cards that add up overall to 5 cards that everybody can see.

The imperfect nature of the information is the 2 cards that you're holding up front.

Yeah, so as you said, you first get 2 cards in private each, and then there's a betting round.

Then you get 3 cards in public on the table, then there's a betting round.

Then you get the fourth card in public on the table, there's a betting round.

Then you get the fifth card on the table, there's a betting round.

So there's a total of 4 betting rounds and 4 tranches of information revelation, if you will.

Only the first tranche is private and then it's public from there.

And this is probably by far the most popular game in AI and just the general public in terms of imperfect information.

So it's probably the most popular spectator game to watch.

So, which is why it's a super exciting game to tackle.

So it's on the order of chess, I would say, in terms of popularity, in terms of the AI setting it as the bar of what is intelligence.

So in 2017, Labradas, how do you pronounce it?

Labradors beats a few, 4 expert human players.

What was the process in general for people who have not read the papers and studied?

Yeah, so the event was that we invited 4 of the top 10 players, who These are specialist players in Heads Up No Limit Texas Hold'em, which is very important because this game is actually quite different than the multiplayer version.

We brought them in to Pittsburgh to play at the Rivers Casino for 20 days.

We wanted to get 120,000 hands in because we wanted to get statistical significance.

So it's a lot of hands for humans to play, even for these top pros who play fairly quickly normally.

So we couldn't just have 1 of them play so many hands.

20 days they were playing basically morning to evening and I raised 200,000 as a little incentive for them to play and the setting was so that they didn't all get 50,000.

We actually paid them out based on how they did against the AI each.

So they had an incentive to play as hard as they could, whether they're way ahead or way behind or right at the mark of beating the AI.

And you don't make any money, unfortunately.

So originally, a couple of years earlier, I actually explored whether we could actually play for money, because that would be, of course, interesting as well, to play against the top people for money, but the Pennsylvania gaming board said no.

a musician or a boxer or something like that.

Nevertheless you were keeping track of the money and Labradors won close to 2000000 dollars I think.

So if it was for real money, if you were able to earn money, that was a quite impressive and inspiring achievement.

Yes, they were playing much like they normally do.

These top players, when they play this game, they play mostly online.

You could Imagine there's a table on a screen.

There's the human sitting there, and then there's the AI sitting there.

The screen shows everything that's happening.

The card's coming out and shows the bets being made.

We also had the betting history for the human.

If the human forgot what had happened in the hand so far, they could actually reference back and so forth.

Is there a reason they were given access to the betting history

These are top quality people, but we just wanted to put out there so it's not a question of a human forgetting and the AI somehow trying to get advantage of better memory.

I mean, that was an incredible accomplishment.

So 18 months earlier, I had organized a similar brains versus AI competition with our previous AI called Cloudico, and we couldn't beat the humans.

So this time around, it was only 18 months later, and I knew that this new AI, Libratus, was way stronger, but it's hard to say how you'll do against the top humans before you try.

And the international betting sites put us as a 4 to 1 or 5 to 1 underdog.

So it's kind of interesting that people really believe in people over AI.

People don't just over-believe in themselves, but they have overconfidence in other people as well compared to the performance of AI.

And yeah, so we were a 4-1 or 5-1 underdog.

And even after 3 days of beating the humans in a row.

We were still 50-50 on the international betting sites.

Do you think there's something special and magical about poker in the way people think about it?

In the sense you have, I mean, Even in chess, there's no Hollywood movies.

And there's this feeling that certain human facial expressions and body language, eye movement, all these tells are critical to poker.

Like you can look into somebody's soul and understand their betting strategy and so on.

So that's probably why, possibly do you think that is why people have a confidence that humans will outperform?

Because AI systems cannot, in this construct, perceive these kinds of tells.

They're only looking at betting patterns and nothing else, the betting patterns and statistics.

So what's more important to you if you step back and human players, human versus human, what's the role of these tells, of these ideas that we romanticize?

So 1 is why do humans trust humans more than AI and have overconfidence in humans?

I think that's not really related to the tele-question.

It's just that they've seen these top players, how good they are, and they're really fantastic.

So it's just hard to believe that an AI could beat them.

And that's actually maybe a more general lesson about AI that until you've seen it overperform a human, it's hard to believe that it could.

But then the tails, a lot of these top players, they're so good at hiding tells that among the top players, it's actually not really worth it for them to invest a lot of effort trying to find tells in each other because they're so good at hiding them.

So yes, at the kind of Friday evening game, tells are going to be a huge thing.

And if you're a good reader, you'll, you'll read them like an open book, but at the top levels of poker now, the tells become a less, a much smaller and smaller aspect of the game as you go to the top levels.

The amount of strategies, the amounts of possible actions

is very large, 10 to the power of 100 plus.

So there has to be some, I've read a few of the papers related, it has to form some abstractions of various hands and actions.

So What kind of abstractions are effective for the game of poker?

So when you go from a game tree that's 10 to the 161, especially in an imperfect information game, it's way too large to solve directly, even with our fastest equilibrium finding algorithms.

And abstraction in games is much trickier than abstraction in MDPs or other single agent settings.

Because you have these abstraction pathologies.

Like if I have a finer grained abstraction, the strategy that I can get from that for the real game might actually be worse than the strategy I can get from the coarse grained abstraction.

Now the kinds of abstractions, just to zoom out, we're talking about, there's the hands abstractions and then there's betting strategies.

So there's information abstraction, to talk about general games, information abstraction, which is the abstraction of what chance does.

And this would be the cards in the case of poker.

And then there's action abstraction, which is abstracting the actions of the actual players, which would be bets in

And for information abstraction, we were completely automated.

So these are algorithms, but they do what we call potential aware abstraction, where we don't just look at the value of the hand, but also how it might materialize into good or bad hands over time.

And it's a certain kind of bottom-up process with integer programming there and clustering and various aspects.

And then in the action abstraction, there, it's largely based on how humans and other AIs have played this game in the past.

But in the beginning, we actually used an automated action abstraction technology, which is provably convergent, that it finds the optimal combination of bet sizes, but it's not very scalable.

So we couldn't use it for the whole game, but we used it for the first couple of betting actions.

more important, the strength of the hand, so the information extraction, or how you play them, the actions?

Does it, you know, the romanticized notion again is that it doesn't matter what hands you have, that the actions, the betting, may be the way you win, no matter what hands you have.

So that's why you have to play a lot of hands so that the role of luck gets smaller.

So you could otherwise get lucky and get some good hands and then you're going to win the match.

Even with thousands of hands, you can get lucky because there's so much variance in no limit Texas hold'em because if we both go all in, it's a huge stack of variance.

So there are these massive swings in no limit Texas hold'em.

So that's why you have to play not just thousands, but over a hundred thousand hands to get statistical significance.

If you didn't even look at your hands, but they didn't know that, the opponents didn't know that, how well would you be able to do?

There's actually, I heard this story that there's this Norwegian female poker player called Annette Oberstad, who's actually won a tournament by doing exactly that, but that would be extremely rare.

Okay, so the hands do have some role to play.

So, Libratus does not use, as far as I understand, use learning methods, deep learning.

Is there room for learning in, you know, there's no reason why LibreOptics doesn't, you know, combine with an AlphaGo type approach for estimating the quality for function estimator.

Maybe as compared to another algorithm, which I'm not that familiar with, DeepStack, the engine that does use deep learning, that It's unclear how well it does, but nevertheless uses deep learning.

So what are your thoughts about learning methods to aid in the way that Libratus plays the game of poker?

Yeah, so as you said, Libratus did not use learning methods and played very well without them.

Since then, we have actually, actually here, we have a couple of papers on things that do use learning techniques.

And sort of the way you're talking about, where it's learning an evaluation function.

But in imperfect information games, unlike let's say in Go or now also in chess and shogi, it's not sufficient to learn an evaluation for a state because the value of an information set depends not only on the exact state, but it also depends on both players' beliefs.

Like if I have a bad hand, I'm much better off if the opponent thinks I have a good hand.

And vice versa, if I have a good hand, I'm much better off if the opponent believes I have a bad hand.

So the value of a state is not just a function of the cards.

It depends on, if you will, the path of play, but only to the extent that is captured in the belief distributions.

So that's why it's not as simple as it is in perfect information games.

And I don't wanna say it's simple there either.

It's of course very complicated computationally there too, but at least conceptually it's very straightforward.

There's a state, there's an evaluation function, you can try to learn it.

And what we do is in 1 of these papers, we're looking at allowing, where we allow the opponent to actually take different strategies at the leaf of the search tree, if you will.

And that is a different way of doing it, and It doesn't assume, therefore, a particular way that the opponent plays, but it allows the opponent to choose from a set of different continuation strategies.

And that forces us to not be too optimistic in a look-ahead search.

And that's 1 way you can do sound look-ahead search in imperfect information games, which is very difficult.

What they did, it was very different than what we do, either in Libratus or in this new work.

They were randomly generating various situations in the game.

Then they were doing the look ahead from there to the end of the game, as if that was the start of a different game.

And then they were using deep learning to learn those values of those states, but the states were not just the physical states, they include the belief distributions.

When you talk about look ahead for DeepStack or with Libratus, does it mean considering every possibility that the game can evolve?

Are we talking about extremely sort of like this exponential growth of a tree?

Yes, so we're talking about exactly that.

Much like you do in alpha beta search or Monte Carlo tree search, but with different techniques.

So there's a different search algorithm and then we have to deal with the leaves differently.

So if you think about what Librarus did, we didn't have to worry about this because we only did it at the end of the game.

So we would always terminate into a real situation and we would know what the payout is.

It didn't do these depth-limited lookaheads.

But now in this new paper, which is called Depth-Limited Search for Imperfect Information Games, we can actually do sound depth-limited lookaheads.

So we can actually start to do the look ahead from the beginning of the game on because that's too complicated to do for this whole long game.

So in Libratus, we were just doing it for the end.

So and then the other side, this belief distribution.

So is it explicitly modeled what kind of beliefs that the opponent might have?

Yeah, yeah, it is explicitly modeled, but it's not assumed.

The beliefs are actually output, not input.

Of course, the starting beliefs are input, but they just fall from the rules of the game because we know that the dealer deals uniformly from the deck.

So I know that every pair of cards that you might have is equally likely.

That just follows from the rules of the game.

Of course, except the 2 cards that I have.

That's called card removal, and that's very important.

Is the dealing always coming from a single deck in the heads up?

know that if I have the ace of spades, I know you don't have an ace of spades.

So in the beginning, your belief is basically the fact that it's a fair dealing of hands, but how do you start to adjust that belief?

Well, that's where this beauty of game theory comes.

So Nash equilibrium, which John Nash introduced in 1950, introduces what rational play is when you have more than 1 player.

And these are pairs of strategies where strategies are contingency plans, 1 for each player, so that neither player wants to deviate to a different strategy, given that the other doesn't deviate.

But as a side effect, you get the beliefs from Bayes' rule.

So Nash equilibrium really isn't just deriving in these imperfect information games, Nash equilibrium doesn't just define strategies, it also defines beliefs for both of us.

So at each state, each, they call information sets.

At each information set in the game, there's a set of different states that we might be in, but I don't know which 1 we're in.

Nash equilibrium tells me exactly what is the probability distribution over those real world states in my mind.

How does Nash equilibrium give you that distribution?

So you know the game rock, paper, scissors.

So we can draw it as player 1 moves first and then player 2 moves.

But of course, it's important that player 2 doesn't know what player 1 moved.

So we can draw that as an information set where player 1 makes 1 of 3 moves first, and then there's an information set for player 2, so player 2 doesn't know which of those nodes the world is in.

But once we know the strategy for player 1, Nash equilibrium will say that you play 1 third rock, 1 third paper, 1 third scissors.

From that I can derive my beliefs on the information set that they're 1 third, 1 third, 1 third.

But is that specific to a particular player or Is it something you quickly update with the specific player?

No, the game theory isn't really player specific.

So that's also why we don't need any data.

We don't need any history how these particular humans played in the past or how any AI or human had played before.

So we just think, the AI just thinks about what would a rational opponent do?

And what would I do if I were, I am rational and what's, that's the idea of game theory.

So it's really a data-free, opponent-free approach.

the design of the game as opposed to the design of the player.

mean, we've done some work on combining opponent modeling with game theory so you can exploit weak players even more.

But that's another strand and in Libratus we didn't turn that on because I decided that these players are too good.

And when you start to exploit an opponent, you typically open yourself up to exploitation.

And these guys have so few holes to exploit and they're world's leading experts in counter-exploitation.

So I decided that we're not gonna turn that stuff on.

Actually, I saw a few of your papers on exploiting opponents.

Do you think there's room for exploitation generally outside of Libratus?

Is there a subject or people differences that could be exploited, maybe not just in poker, but in general interactions and negotiations, all these other domains that you're considering?

And I really like the work that hybridizes the 2.

So you figure out what would a rational opponent do.

And by the way, that's safe in these zero-sum games, two-player zero-sum games, because if the opponent does something irrational, yes, it might throw off my beliefs, but the amount that the player can gain by throwing off my belief is always less than they lose by playing poorly.

But still, if somebody's weak as a player, you might wanna play differently to exploit them more.

So you can think about it this way, a game theoretic strategy is unbeatable, But it doesn't maximally beat the other opponent.

So the winnings per hand might be better with a different strategy.

And the hybrid is that you start from a game theoretic approach.

And then as you gain data about the opponent in certain parts of the game tree, then in those parts of the game tree, you start to tweak your strategy more and more towards exploitation, while still staying fairly close to the game theoretic strategy so as to not open yourself up to exploitation too much.

Do you try to vary up strategies, make it unpredictable?

Tit for tat strategies in Prisoner's Dilemma or?

Simple prisoner's dilemma, repeated games.

But even there, there's no proof that says that that's the best thing.

But experimentally, it actually does well.

So what kind of games are there, first of all?

See all Lex Fridman transcripts on Youtube

Tuomas Sandholm: Poker and Game Theory | Lex Fridman Podcast #12