Kind: captions
Language: en
the following is a conversation with
Thomas sent home he's a professor same
you and co-creator of lebra's which is
the first AI system to be 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 new reps 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 proposed 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 subscribe on youtube itunes or
simply connect with me on Twitter at Lex
Friedman spelled Fri D and now here's my
conversation with Thomas sent home can
you describe at the high level the game
of poker Texas Hold'em heads-up Texas
Hold'em for people who might not be
familiar at this card game yeah happy to
so heads up 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 obvious 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 recall to your home game on a
Friday night it probably is not gonna be
hits up no Limit Texas Hold'em it might
be no let me it takes us Hold'em in some
cases but typically for a big group and
it's not as competitive well heads up
means it's two-player so it's really
like me against you
Am I
you better much like chess or or 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 a two cards
that you only see the game on to you
yeah there is they gradually lay out
some cards that add up overall to five
cards that everybody can see yeah the
imperfect nature of the information is
the two cards that you're holding on
front yeah so as you said you know you
first get two cards in private each and
then you this a betting round then you
get three clubs in public on the table
then there's a betting round then you
get the fourth card in public on the
table they're spitting around then you
get the five fifth card on the table
there's a bending drop so there's a
total of four betting rounds and four
torrontés of information revelation if
you will the only the first tranche is
private and they omits public from there
and this is probably 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 right so
which is why it's a super exciting game
tackle so it sits on the order of chess
I would say in terms of popularity in
terms of AI setting it as the bar of
what is intelligence
so in 2017 labret does how do you
pronounce it Liberato lebra das lebra
does beats little laughing they're a
little bit Latin LeBron is beat a few
for expert human players can you
describe that event what you learned
from it what was it like what was the
process in general for people who have
not read the papers and study yeah so
the event was that we invited four of
the top 10 players with 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 the multiplayer
version we brought me in to Pittsburgh
to play at the reverse casino
for twenty days we wanted to get a
hundred and twenty thousand hands in
because we wanted to get statistical
significance so it's a lot of hands for
humans to play even for this top pros
who play fairly quickly normally so we
couldn't just have one of them play so
many hands twenty days they were playing
basically morning to evening and he
raised two hundred thousand as a little
incentive for them to play and the
setting was so that they didn't all get
fifty thousand 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 the way behind or right at the
mark of beating the AI and you don't
make any money unfortunately right no we
can't make any money so 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 so so
if we couldn't so this is much like an
exhibit like for a musician or a boxer
or something like that
nevertheless you're keeping track of the
money and brought us one close to two
million dollars I think so so if there
if it was for real money if you were
able to earn money that was a quite
impressive and inspiring achievement
just a few details what what were the
players looking at I mean were they
behind the computer what was the
interface like yes there they were
playing much like they normally do these
top players when they play this game
they play mostly online so they used to
playing through what UI yes and they did
the same thing here so there was this
layout you could imagine there's a table
on the screen this the the human sitting
there and then there's the AI sitting
there and the the screen source
everything is happening the cards coming
out and so the bets being made and we
also had the betting history for the
human so if the human for what what had
happened in the ham so far they could
actually reference back
and and and so forth is there a reason
they were given access to the betting
history for well we just uh it's a it
didn't really matter that they wouldn't
have forgotten anyway these are top
quality people but we just want to put
out there so it's not a question for
human for getting and the AI somehow
trying to get advantage of better memory
so what was that like I mean that was an
incredible accomplishment so what did it
feel like before the event did you have
doubt hope
where was your confidence at yeah that's
great so a great question so eighteen
months earlier I had organized the
similar brains versus AI competition
with our previous a I call clerical and
we couldn't beat the humans so this time
around it was only eighteen months later
and I knew that this new AI Lovato's was
way stronger but it's hard to say how
you'll do against the top humans before
you try so I thought we had about a
50/50 shot and the international betting
sites put us a us as a four to one or
five to one underdog so it's kind of
interesting that people really believe
in people and I get over AI not just
people people don't just believe over
believing themselves but they have
overconfidence in other people as well
compared to the performance of AI and
yeah so we were afford to 105 to 108
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 and in
the way people think about it in a sense
you have I mean even in chess there's no
Hollywood movies poker is this the star
of many movies and there's this feeling
that certain human facial expressions
and body language eye movement all these
tells are critical to poker you can look
into somebody's soul understand their
betting strategy and so on there so
that's probably why the possibly do you
think that is why people have a
confidence that humans will outperform
because AI systems cannot in
construct perceive these kinds of tells
they're only looking at betting patterns
and and nothing else the betting
patterns and and statistics so what's
more important to you if you step back
and human players human versus human
what's the role these tells of these
ideas that we romanticize yeah so I
split it into two parts so one is why do
humans trust he much more than AI and
all have overconfidence in humans yes I
think that's that's not really related
to tell a 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 therefore that
the Navy I could beat them yeah so I
think that's where that comes from and
and that's actually maybe a more general
lesson about the AI that until you've
seen it over perform a human it's hard
to believe it it could but then the
tails a lot of these top players they're
so good at hiding tails that among the
top players it's actually not really
worth it for them to invest a lot of
effort trying to find tails in each
other because there's a so good at
hiding them so yes at the kind of Friday
evening game tells are gonna be a huge
thing you can read other people and if
you're a good reader you you'll read
them like an open book but at the top
levels of poker no details become a list
of the much much smaller and smaller
aspect of the game as you go to the top
levels the the amount of strategies the
amount of possible actions is is very
large ten to the power of one hundred
plus so there has to be some I've read a
few the papers related it has it has to
form some abstractions of various hands
and actions so what kind of abstractions
are effective for the game of poker yeah
so you're exactly right so when you go
from a game tree that's ten to the 161
especially in an imperfect information
game it's way too large to solve
directly even with our fastest ik
finding algorithms so you wanna abstract
it first and abstraction in games is
much trickier than abstraction in mdps
or other single agent settings because
you have these abstraction pathologies
that 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 if you have to be very
careful now the the kinds of
abstractions just to zoom out we're
talking about there's the hands
abstractions and then there's betting
strategies yeah what I think actions
yeah baiting access or so there's
information obstruction 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 bits in the case of poker
yourself and the other players yes
yourself and other players and for
information abstraction we were
completely automated so these were 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 in the
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 how do you build
build this abstraction and then in the
action abstraction there it's largely
based on how humans other and other AIS
have played this game in the past but in
the beginning we actually use an
automated action abstraction technology
which is provably convergent that it
finds the optimal combination of eight
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 so what's more important
the strength of the hand so the
information retraction or the how you
play them the actions does
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 yeah 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 gonna 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 or variant
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 don't get
statistical significance let me ask
another way this question if you didn't
even look at your hands but they didn't
know that the your opponents didn't know
that how well would you be able to do oh
that's a good question there's actually
I heard this story that this is
Norwegian female poker player goal and
at uber stud who's actually won a
tournament by doing exactly that but
that would be extremely rare so so I
cannot really play well the hands do
have some role to play oh yes so LeBron
is does not use as far as I understand a
used learning methods deep learning is
there room for learning in you know
there's no reason why lab artist doesn't
you know combined with an alphago type
approach for estimating the quality for
function estimator what are your
thoughts on this maybe as compared to
another algorithm which I'm not that
familiar with deep stack the 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 teller Broadus
plays the game of poker yeah so as you
said Lee barratto's 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 technique
Saxon so and deep learning in particular
and the 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 Co or now now
also in chess and shogi it's not some
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'm 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 so that's
why it's not as simple as as it is
imperfect information games another one
I'd 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 here you have to do
something more and what we do is in one
of these papers we're looking at
allowing where we allow with the
opponent to actually take different
strategies at the leaf of the search
tree as F if you will and 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
opponent to choose from a set of
different continuation strategies and
that forces us to not be too optimistic
in our local head search and that's
that's one way you can do sound look
ahead search in imperfect information
games which is very different difficult
and in us you were asking about deep
stack what they did it was very
different than what we do either in Lee
brothers or in this new work
they were gender and Umrah generating
various situations in the game then they
were doing Luca head from there to the
end of the game as if that was a 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 deep stack
or with libertas does it mean
considering every possibility that the
game can involve is that we're talking
about extremely sort of like this
exponentially growth of a tree yes so
we're talking about exactly that
much like you do in Alpha Beta search or
want to crawl to research 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 Lee brothers
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 to
payout this it didn't do this
depth limited loka heads but now in this
new paper which is called depth limited
I think it's called depth limited
research for imperfect information games
we can actually do sound depth limited
look at it so we can actually started
with a look ahead
from the beginning of the game on
because that's too complicated to do for
this whole long game
so in Lee brothers 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 dick
so I know that every pair of cards that
you might have is equally likely I know
that for a fact
that's as follows from the rules of the
game of course except the two cards that
I have I know you don't have those yes
you have to take that into account
that's called card removal and that's
very important is the dealing always
coming from a single deck in the heads
up so you can assume single deck know
that if some if if I have the ace of
spades I know you don't have an ace of
spades
okay so in the beginning your belief is
basically the fact that it's a fair
dealing of hands but how do you adjust
start to adjust that belief well that's
a where this beauty of games here it
comes so nash equilibrium which john
nash introduced in 1950 introduces what
rational play is when you have more than
one player and these are pairs of
strategies where strategies are
contingency plans one for each player so
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 us and it
defines beliefs for each state so at the
each state it's if they take all
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 one we're in Nash equilibrium
tells me exactly what is a probability
distribution over those real world
states in my mind how does naturally
give you that distribution so why I'll
do a simple example 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 otherwise player 2 would win every
time so we can draw that as an
information set where player 1 makes one
of three 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 it but once we know the
strategy for player 1 Nash equilibrium
will say that you play 1/3 Rock 1/3
paper 1/3 caesars from that I can derive
my beliefs of the information set that
they wanted 1/3 wants it though so Bayes
gives you that basis you but is that
specific to a particular player or is it
is there something you quickly update
with the game theory isn't really player
specific so that's what 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 even
had played before it's all about
rationality so we just think the AI just
thinks about what would a rational
opponent do and what would I do if I
were right I am rational and that that's
that's the idea of game theory so it's
really a data free opponent free
approach sir comes from the design of
the game as opposed to the design of the
player exactly if there's no opponent
modeling per se I mean we've done some
work on combining opponent modeling with
game theory so you couldn't exploit weak
players even more but that's another
strand and in the Lee brothers we didn't
turn that on because I decided that
these players are too good and when you
start to exploit an opponent you'll
typically open yourself up self 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
papers exploiting opponents it sound
very interesting to explore do you think
there's room for exploitation generally
outside of LeBron us is is there subject
or people differences that could be
exploited maybe not just in poker but in
general interactions negotiations all
these other domains that yours
considering yeah I definitely we've done
some work on that and I really like
their work at hybridize is the two 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
show 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 so so it's safe but
still if somebody's weak as a player you
might want to play differently to
exploit them more so that you can think
about it this way a game theoretic
strategies are 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 from
about the opponent in certain parts of
the game tree that 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
how do you do that do you try to vary up
strategies make it unpredictable it's
like what is it
tit-for-tat strategies in prisoner's
dilemma or well it doesn't that that's a
repeated game kind of prisoner's dilemma
repeats it games but but even there
there's no proof that says that that's
the best thing but experimentally it
actually does does does well so what
kind of games are there first of all I
don't know if this is something that you
could just summarize there's perfect
information games or all the
informations on the table there is
imperfect information games there's
repeated games you play over and over
there's zero-sum games there's
nonzero-sum games yeah and then there's
a really important distinction you're
making two-player versus more players so
what are what other games out there and
what's the difference for example with
this two-player game versus more players
yeah what are the key differences right
here so let me start from the the basic
so a repeated game is a game where the
same exact game is played over and over
in these extensive form games where
think about three form maybe with these
information says to represent incomplete
information you can have kind of
repetitive interactions even repeated
games are a special case of that by the
way but if the game doesn't have to be
exactly the same selectively sourcing
all trips yes we kind of see it the same
supply base year to year but what I'm
buying is a little different every time
and the supply base is a little
different every time and so on so it's
not really repeated so to find a purely
repeated game is actually very rare in
the world so they're really a very
coarse model of what's going on then if
you move up from repeat just repeated
simple repeated matrix games not all the
way to extensive form games but in
between
they're stochastic games where you know
this these think about it like these
little matrix games
and when you take an action and your
home takes an action they determine not
which next state I'm going to next game
I'm going to but the distribution over
next games where I might be going to so
so that's the stochastic game but it's
like matrix games repeated stochastic
games extensive form games that is from
less to more general and and poker is an
example of the last one so it's really
the most general setting extensive form
games and that's kind of what the AI
community has been working on and being
benched marked on with this heads-up No
Limit Texas Hold'em
can you describe extensive form games
what was the motto here yeah so if you
imagine with the tree form so it's
really the tree form like in chess
there's a search tree versus a matrix is
a matrix yeah and that's the new matrix
is called the matrix form or by matrix
form or normal form game and here you
have the tree form so you can actually
do certain types of reasoning there that
you'll lose the information when you go
to normal form there's a certain form of
equivalence like if you go from three
form and you say it every possible
contingency plan is the strategy then I
can actually go back to the normal form
but I lose some information from the
lack of sequentiality then the
multiplayer versus two-player
distinction is an important one
so two-player games in zero-sum are
conceptually easier and computationally
easier there's still huge like this one
this one but they're conceptually easier
and computationally easier in that
conceptually you don't have to worry
about which equilibrium is the other guy
going to play when there are multiple
because any equilibrium strategy is a
best response to any other equilibrium
strategy so I can play a different
equilibrium from you and we'll still get
the right values of the game that falls
apart even with two players when you
have general some games even without
cooperation just even without
cooperation so there's a big gap from
two player zero-sum to two-player
general sum or even to three player
zero-sum that's that's a big gap
at least in theory can you maybe not
mathematically provide the intuition why
it all falls apart with three or more
players it seems like you should still
be able to have a Nash equilibrium that
yeah that's instructive that holds okay
so it is true that all finite games have
a Nash equilibrium so this is what your
Nash actually proved so they do have a
Nash equilibrium that's not a problem
the problem is that there can be many
and then there's a question of which
equilibrium to select so and if you
select your strategy from a different
equilibrium and I select mind then did
what does that mean I and in this non
zero sum games we may lose some joint
benefits we hope by being just simply
stupid we could actually both be better
off if we did something else yes and in
three player you get other problems also
like collusion that maybe you and I can
get up on a third player and we can do
radically better by colluding so that
there are lots of issues that come up
there
so no Brown student you workers on this
has mentioned I looked through the AMA
and read it he mentioned that the
ability of poker players to collaborate
will make the game he was asked the
question of how would you make the game
of poker or both of you were asked the
question how would you make the game of
poker
beyond being solvable by current AI
methods and he said that there's not
many ways of making poker more difficult
but collaboration or cooperation between
players would make it extremely
difficult so can you provide the
intuition behind why that is if you
agree with that idea yeah so we've done
a lot of work coalitional games and we
actually have a paper here with my other
student cappella Farina and some other
collaborators on after net nips on that
actually just came back from the poster
session where we present life so when
you have a collusion it's a it's a
different problem yes and it typically
gets even harder then
even the game representations some of
the game representations don't really
allow go to computation so we actually
introduced a new game representation for
for that is that kind of cooperation
part of the model is are you do you have
do you have information about the fact
that other players are cooperating or is
it just this chaos that where nothing is
known so there's some something's
unknown can you give an example of a
collusion type game or Z you select
breach that so think about bridge it's
like when you and I are on a team
our payoffs are the same the problem is
that we can't talk so so when I get my
cards I can't whisper to you what my
cards are that would not be allowed so
we have to somehow coordinate our
strategies ahead of time and only ahead
of time and then there are certain
signals we can talk about but they have
to be such that the other team also
understands them so so that that's
that's an example where the coordination
is already built into the rules of the
game but in many other situations like
auctions or negotiations or diplomatic
relationships poker it's not really
built-in but it still can be very
helpful for the coders I've read you
right somewhere the negotiations you
come to the table with prior like a
strategy that like that you're willing
to do and not willing to do those kinds
of things so how do you start to now
moving away from poker movie beyond
poker into other applications like
negotiations how do you start applying
this to other and to other domains
yeah even real world domains that you've
worked on yeah I actually have two
start-up companies doing exactly that
one is called strategic machine and
that's for kind of build applications
gaming sports all sorts of things like
that any applications of this to
business and to sports and to gaming to
various types of things for in finance
electricity markets and so on and the
other is called strategy robot where we
are taking this to military secure
the cyber security and intelligence
applications I think you worked a little
bit in how he put it advertisement sort
of suggesting ad kind of thing yeah
auction that's another component
optimized markets optimized but that's
much more about a combinatorial market
and optimization based technology that's
not using these game theoretic reasoning
technologies I think okay so what sort
of high level do you think about our
ability to use game theoretic concepts
to model human behavior do you think do
you think human behavior is amenable to
this kind of modeling so outside of the
poker games and where have you seen it
done successfully in your work I'm not
sure the goal really is modeling humans
like for example if I'm playing a
zero-sum game yes I don't really care
that the opponent is actually following
my model of rational behavior because if
they're not that's even better for me
right so so they see with the opponents
and games there's a the prerequisite is
that you've formalized the interaction
in some way that can be amenable to
analysis and you've done this amazing
work with mechanism design designing
games that have certain outcomes but so
I'll tell you an example for my for my
world of autonomous vehicles right we're
studying pedestrians and pedestrians and
cars negotiating this nonverbal
communication there's this weird and
game dance of tension where pedestrians
are basically saying I trusted you won't
kill me and so as a jaywalker I will
step onto the road even though I'm
breaking the law and there's this
tension and the question is we really
don't know how to model that well in
trying to model intent and so people
sometimes bring up ideas of game theory
and so on do you think that aspect of
human behavior can use these kinds of
imperfect information approaches
modeling
how do we how do you start to attack a
problem like that when you don't even
know how the game design the game to
describe the situation in order to solve
it okay so I haven't really thought
about jaywalking but one thing that I
think could be a good application in an
autonomous vehicles is the following so
let's say that you have fleets of
autonomous cars operated by different
companies so maybe here's the way more
fleet and here's the uber fleet if you
think about the rules of the road they
define certain little rules but that
still leaves a huge strategy space open
like as a simple example when cars merge
you know how he must merge you know they
slow down and look at each other and try
to I try to merge wouldn't it be better
if these situations would all repeat
pre-negotiated so we can actually merge
at full speed and we know that this is
the situation this is how we do it and
it's all gonna be faster but there are
way too many situations to negotiate
manually so you could do use automated
negotiation this is the idea at least
you could use automated negotiation to
negotiate all of these situations or
many of them in advance and of course it
might be that hey maybe you're not gonna
always let me go first
maybe you said okay well in these
situations all let you go first but in
exchange you're gonna give me - how much
you're gonna let me go first in this
situation yes
so it's this huge combinatorial
negotiation and do you think there's
room in that example of merging to model
this whole situation is an imperfect
information game or do you really want
to consider it to be a perfect no that's
a good question yeah that's a good
question I'm paid the price of assuming
that you don't know everything yeah I
don't know it's certainly much easier
games with perfect information are much
easier so if you can get away with it
you should but if the real situation is
of imperfect information then you're
going to have to deal with in for
imperfect information great so what
lessons have you learned the annual
computer poker competition an incredible
accomplishment of AI you know you look
at the history of deep blue
go these kind of moments when I stepped
up in an engineering effort and a
scientific effort combined to beat the
best human players so what do you take
away from this whole experience what
have you learned about designing it has
systems that play these kinds of games
and what does that mean for sort of AI
in general for the future of IAI
development yeah so that's a good
question so there's so much to say about
it I do like this type of performance
oriented research although in my group
we go all the way from like idea to
theory to experiments to big system
fielding the commercialization so we
spend that spectrum but I think that in
a lot of situations in AI you really
have to build the big systems and
evaluate them at a scale before you know
what works and doesn't and we've seen
that in the computational game theory
community that there are a lot of
techniques that look good in the small
but then they cease to look good in the
large and we've also seen that there are
a lot of techniques that look superior
in theory and I really mean in terms of
convergence rates better like
first-order methods better convergence
rates like the CFR based based
algorithms yet the CFR pay based
algorithms are the fastest in practice
so it really tells me that you have to
test this in reality the theory isn't
tight enough if you will to tell you
which algorithms are better than the
others and you have to look at these
things that in the large because any
sort of projections you do from the
small and at least in this domain be
very misleading so that that's kind of
from from a kind of science and
engineering perspective from personal
perspective it's been just a wild
experience in that with the first poker
competition the first or first brains
versus AI man-machine poker competition
that we organized there had been by the
way for other poker games there had been
previous competitions but this was for
heads up No Limit this was the first and
I probably became the most hated person
in the world of Poker and I didn't mean
to III size that they cracked in the
game for yeah it was a lot of people
felt that it was a real
threat to the whole game the whole
existence of the game if AI becomes
better than humans people would be
scared to play poker because there are
the superhuman AI is running around
taking their money and you know all of
that so so I just it's just really
aggressive just in the comments were
super aggressive I got everything
it's just short of death threats do you
think the same was true for chess
because right now they just completed
the World Championships and chess and
humans just started ignoring the fact
that there's AI systems now that I'll
perform humans and they still enjoy the
game is still a beautiful game that's
what I think yeah and I think the same
thing happens in poker and so I didn't
think of myself as somebody was gonna
kill the game and I don't think I did
yeah I've really learned to love this
game I wasn't a poker player before but
learn so many new ones is about it from
these AIS and they've really changed how
the game is played by the way so they
have these very Martian ways of playing
poker and the top humans are now
incorporating those types of strategies
into their own play so if anything to me
our work has made poker a richer more
interesting game for humans to play not
something that is gonna steer him as
away from it entirely just a quick
comment and something you said which is
if I may say so in academia is a little
bit rare sometimes it's pretty brave to
put your ideas to the test in the way
you described
saying that sometimes good ideas don't
work when you actually try to apply them
at scale and so where does that come
from I mean what if you could do a
advice for people what what drives you
in that sense were you always this way I
mean it takes a brave person I guess is
what I'm saying to test their ideas and
to see if this thing actually works
against human top human players and so
on yeah I don't know about brave but it
takes a lot of work it takes a lot of
work and a lot of time to organize do
make something big and to organize an
event and stuff like that and what
drives you in that effort because you
could still I would argue get a best
paper award and nips as you did in 17
without doing this that's right yes
and so so in general I believe it's very
important to do things in in the real
world and at scale and that's really
where the the the pudding if you will
proof is in the pudding that's what
that's where it is in this particular
case it was kind of a competition
between different groups and for many
years as to who can be the first one to
beat the top humans that heads up No
Limit Texas Hold'em so it became it
became kind of a like a competition who
can get there yeah so a little friendly
competition could be I can do wonders
for progress yes so the topic of
mechanism design which is really
interesting also kind of new to me
except as an observer if I don't know
politics and any I'm an observer of
mechanisms but you write in your paper
an automated mechanism design that I
quickly read so mechanism design is
designing the rules of the game so you
get a certain desirable outcome and you
have this work on doing so in an
automatic fashion as opposed to
fine-tuning it so what have you learned
from those efforts if you look say I
don't know at complex it's like our
political system can we design our
political system to have in an automated
fashion to have outcomes that we want
can we design something like traffic
lights to be smart where it gets
outcomes that we want so what are the
lessons you draw from that work yeah so
I still very much believe in the
automated mechanism design direction yes
but it's not a panacea
there are impossibility results in
mechanism design saying that there is no
mechanism that accomplishes objective X
in Class C so so they it's not gonna
there's no way using any mechanism
design tools manual or automated
to do certain things in mechanism design
he can't describe that again so meaning
there it's impossible to achieve that
yeah yes it was likely impossible so so
so these are these are not statements
about human ingenuity who might come up
with something smart these are proofs
that if you wanna accomplish properties
X in Class C that is not to oppose with
any mechanism the good thing about
automated mechanism design is that we're
not really designing for a class we're
designing for specific settings at the
time so even if there's an impossibility
result for the whole class it just
doesn't mean that all of the cases in
the class are impossible it just means
that some of the cases are impossible so
we can actually carve these islands of
possibility within these known
impossible classes and we've actually
done that so what one of the famous
results in mechanism design is a Meyer
sham set its weight theorem for pi Roger
Myerson and Mark Satterthwaite from 1983
so it's an impossibility of efficient
trade under imperfect information we
show that you can in many settings avoid
that and get the efficient trade anyway
depending on how they design the game
okay so depending how you design the
game and of course it's not it doesn't
in any way any way contradict to
impossibility result or impossibility
results is still there but it just finds
spots within this impossible class where
in those spots you don't have time
possibility sorry if I'm going a bit
philosophical but what lessons you draw
towards like I mentioned politics or
human interaction and designing
mechanisms for outside of just these
kinds of trading or auctioning or purely
formal games our human interaction like
a political system what how do you think
it's applicable to yeah politics or to
business to negotiations these kinds of
things
designing rules that have certain
outcomes yeah yeah I do think so have
you seen success that successfully done
yes and really oh you mean mechanism
design or automated make automated
mechanism design but so so mechanism
design itself has had fairly limited
success so far there are certain cases
but most of the real-world situations
are actually not sound from a mechanism
design perspective even in those cases
where they've been designed by very
knowledgeable mechanism design people
the people are typically just taking
some insights from the theory and
applying those insights into the real
world rather than applying the
mechanisms directly so one famous
example of is the FCC spectrum auctions
so I've also had a small role in that
and very good economists have been where
excellent economists have been working
on that with no game theory yet the
rules that are designed in practice
they're they're such that bidding
truthfully is not the best strategy
usually mechanism design we try to make
things easy for the participants so
telling the truth is the best strategy
but but even in those very high stakes
auctions where you have tens of billions
of dollars worth of expect from being
auctioned truth-telling is not the best
strategy and by the way nobody knows
even a single optimal bidding strategy
for those auctions what's the challenge
of coming up with an optimum because
there's a lot of players and there's a
lot of players but many items for sale
and the these mechanisms are such that
even with just two items or one item
bidding truthfully wouldn't be the best
strategy if you look at the history of
AI it's marked by seminal events and
alphago being a world champion human go
player I would put librettist winning
the heads of no-limit hold'em as one of
such event thank you and what do you
think
is the next such event whether it's in
your life or in the broadly AI community
that you think might be out there that
would surprise the world so that's a
great question and I don't really know
the answer in terms of game solving hits
up No Limit Texas Hold'em really was the
one remaining widely agreed-upon
benchmark so that was the big milestone
now are there other things yes certainly
there are but there there is not one
that the community has kind of focused
on so what could be other things there
are groups working on StarCraft there
are groups working on dota2 these are
video games yes or you could have like
diplomacy or Hanavi you know things like
that these are like recreational games
but none of them are really acknowledged
that's kind of the main next challenge
problem like chess or go or heads-up No
Limit Texas Hold'em was so I don't
really know in the game solving space
what is or what will will be the next
benchmark
I hope kind of hope that there will be a
next benchmark because really the
different groups working on the same
problem really drove these application
independent techniques for put very
quickly over ten years do you think
there's an open problem that excites you
that you start moving away from games
into real world games like say the stock
market trading yeah that's that's kind
of how I am so I am probably not going
to work as hard on these recreational
benchmarks I'm doing to startups on game
solving technology strategic machine and
strategy robot and we're really
interested in pushing this stuff into
practice what do you think would be
really you know a powerful result that
would be surprising that would be if you
can say I mean you know five years ten
years from now something that
statistically you would say is not very
likely but if there's a breakthrough
what achieve yeah so I think that
overall we're in a very different
situation in game theory than we are in
let's say machine learning yes
so in machine learning it's a fairly
mature technology and it's very broadly
applied and proven success in the real
world in game solving there are almost
no applications yet
we have just become superhuman which
machine learning you could argue
happened in the 90s if not earlier and
at least some supervised learning at
certain complex supervised learning
applications
now I think a next challenge problem I
know you're not asking about this way
you're you're asking about the
technology breakthrough but I think the
big big breakthrough is to be able to
show it hey maybe most of let's say
military planning or most of business
strategy will actually be done
strategically using computational game
theory that that's what I would like to
see as a next five or ten year goal
maybe you can explain to me again
forgive me if this is an obvious
question but you know machine learning
methods neural networks are suffer from
not being transparent not being
explainable a game theoretic methods you
know Nash equilibria do they generally
when you see the different solutions are
they when you talk about military
operations are they once you see the
strategies do they make sense that they
explainable or do they suffer from the
same problems as neural networks do so
that's that's a good question I would
say a little bit yes and no and what I
mean by that is that these games are
ethic strategies let's say Nash
equilibrium it has provable properties
so it's unlike let's say deep learning
where you kind of cross your fingers
hopefully it'll work and then after the
fact when you have the weights you're
still crossing your fingers and I hope
it will work here you know that the
solution quality is there this provable
or Souls from quality guarantees now
that doesn't necessarily mean that the
strategies are human understandable
that's a whole other problem so that's
also I think it deep learning and
computational game theory are in the
same boat in that sense that both are
difficult to understand but at least the
game theoretic techniques they have this
guarantees of guarantee quality so did
you see business operations to achieve
your corporations or even military in
the future being at least the strong
candidates being proposed by automated
systems do you see that yeah I do I do
but that's more of a really belief than
a substantiated fact depending on where
you land and optimism or pessimism
that's a relief to me that's an exciting
future especially if they're provable
things
in terms of optimality so looking into
the future there's a a few folks worried
about the especially you look at the
game of poker which is probably one of
the last benchmarks in terms of games
being solved they they worry about the
future and the existential threats of
artificial intelligence so the negative
impact in whatever form on society is
that something that concerns you as much
are you more optimistic about the
positive impacts of AI oh I am much more
optimistic about the positive impacts so
just in my own work what we've done so
far we run the nationwide kidney
exchange hundreds of people are walking
around alive today who would it be and
it's increased employment you had you
have a lot of people now running kidney
changes and at the transplant centers
interacting with the kidney exchange you
have extra surgeons nurses
anesthesiologists hospitals all of that
as so so employment is increasing from
that and the world is becoming a better
place
another example is combinatorial
sourcing auctions we did 800 large-scale
combinatorial sourcing auctions from
2001 to 2010 in a previous startup of
mine called combine it and we increased
the supply chain efficiency on that
sixty billion dollars of spend by twelve
point six percent so that's over six
billion dollars of efficiency
improvement in the world and this is
also like shifting value from somebody
to somebody else just efficiency
improvement like in trucking less empty
driving so there's less waste less
carbon footprint and so on it's a huge
positive impact in the near term but
sort of to stay in it for a little
longer because I think game theory is a
role to play here well let me actually
come back and tell you this is one thing
I think Asia is also going to make the
world much safer so so so that's another
aspect that often gets overlooked well
let me ask this question maybe you can
speak to the the safer so I talked to
max tegmark is do a Russell who are very
concerned about
the resume yeah and often the concern is
about value misalignment so AI systems
basically working operating towards
goals that are not the same as human
civilization human beings so it seems
like game theory has a role to play
there to to make sure the values are
aligned with human beings I don't know
if that's how you think about it if not
how do you think AI might help with this
problem how do you think a i'ma make the
world safer yeah I think this value
misalignment is a fairly theoretical
worry and I haven't really seen it in it
because I do a lot of real applications
I don't see it anywhere
the closest I've seen it was the
following type of mental exercise really
where I had this argument in the late
80s when we were building these
transportation optimization systems and
somebody had heard that it's a good idea
to have high utilization of assets so
they told me that hey why don't you put
that as objective and we didn't even
pull it as an objective because I just
showed him it you know if you had that
as your objective the solution would be
to load your trucks full and driving
circles nothing would ever get delivered
you'd have a hundred percent utilization
so yeah I know this phenomenon I've
known this for over 30 years in but I've
never seen it actually be a problem
reality in reality and yes if you have
the wrong objective the AI will optimize
that to the hilt and it's gonna fit more
than some human who's kind of trying to
so within a half-baked way with some
human insight to but I just haven't seen
that materialize in practice there's
this gap that you actually put your
finger on very clearly just now between
theory and reality that's very difficult
to put into words I think it's what you
can theoretically imagine the worst
possible case or even yeah I mean bad
cases and what usually happens in
reality so for example to me maybe it's
something you can comment on
having grown up and I had grew up in the
Soviet Union you know there's currently
10,000 nuclear weapons in the world and
for many decades it's theoretically
surprising to me that the nuclear war is
not broken out do you think about this
aspect from a game theoretic perspective
in general why is that true why in
theory you could see how things would go
terribly wrong and somehow yet they have
not yeah how do you think so so I do
think that about that a lot I think the
biggest two threats that we're facing as
mankind one is climate change and the
other is nuclear war so I saw so those
are my main two worries that they're
worried about and I've tried to do
something about climate I thought about
trying to do something for climate
change twice actually before two of my
startups had actually commissioned
studies of what we could do on those
things and we didn't really find a sweet
spot but I'm still keeping an eye out on
that if there's something where we could
actually provide a market solution or
optimization solution or some other
technology solution to problems right
now
like for example pollution critic
markets was what we were looking at then
and it was much more the lack of
political will by those markets were not
so successful rather than bad market
design so I could go in and make a
better market design but that wouldn't
really move the needle on the world very
much if there's no political will and in
the u.s. you know the market at least
the Chicago market was just shut down
and and so on so it and then it doesn't
really help create your market design
was there any nuclear side it's more so
global warming is more encroaching
problem you know nuclear weapons have
been here it's an obvious problem has
just been sitting there so how do you
think about what is the mechanism design
there that just made everything seem
stable and are you still extremely
worried I am still extremely worried so
you probably know the simple game theory
of mad so solar so this was a mutually
assured destruction and it's like it
doesn't require any computation with
small matrices you can actually convince
yourself that the game is such that
nobody wants to initiate yeah that's a
very coarse-grained analysis and it
really works in a situation where you
have two superpowers or small number of
superpowers now things are very
different you have a smaller nuke so the
threshold of initiating is smaller and
you have smaller countries and non non
nation actors who make it Nokes and so
on so it's I think it's riskier now than
it was maybe ever before and what idea
application by I you've talked about a
little bit but what is the most exciting
to you right now
I mean you you're here at nips europe's
now you have a few excellent pieces of
work but what are you thinking into the
future with several companies you're
doing what's the most exciting thing or
one of the exciting things the number
one thing but for me right now is coming
up with these scalable techniques for
game solving and applying them into the
real world they're still very interested
in market design as well and we're doing
that in the optimized markets but I'm
most interested if number one right now
is strategic machine strategy robots
getting that technology out there and
seeing as you were in the trenches doing
applications what needs to be actually
filled what technology gap still need to
be filled so it's so hard to just put
your feet on the table and imagine what
needs to be done but when you're
actually doing real applications the
applications tell you what needs to be
done and I really enjoy that interaction
is it a challenging process to apply
some of the stay the are techniques
you're working on and and having the
the various players in industry or the
military or people who could really
benefit from it actually use it what's
that process like of you know in
autonomous vehicles will work with
automotive companies and they're in in
many ways they're a little bit
old-fashioned it's difficult they really
want to use this technology there's
clearly will have a significant benefit
but the systems aren't quite in place to
easily have them integrated in terms of
data in terms of compute in terms of all
these kinds of things so deuce is that
one of the bigger challenges that you're
facing and how do you tackle that
challenge yeah I think that's always a
challenge that that's gonna slowness and
inertia really of let's do things the
way we've always done it you just have
to find the internal champions that the
customer who understand that hey things
can't be the same way in the future
otherwise bad things are going to happen
and it's in order most vehicles it's
actually very interesting that the car
makers are doing that then they're very
traditional but at the same time you
have tech companies who have nothing to
do with cars or transportation like
Google and Baidu really pushing on
autonomous cars I find it fascinating
clearly you're super excited about
actually these ideas having an impact in
the world in terms of the technology in
terms of ideas and research their
directions that you're also excited
about whether that's on the some of the
approaches you talked about for the
imperfect information games whether it's
applying deep learning just some of
these problems is there something that
you're excited in in the research side
of things yeah yeah lots of different
things in the game solving so solving
even bigger games games will you have
more hidden action of the play your
actions as well poker is a game where
really the chance actions are hidden or
some of them are hidden but the player
actions are public
the multiplayer games of various sorts
collusion opponent exploitation all and
even longer games some games that
basically go forever but they're not
repeated so seek extensive phone games
that go forever whoa what what would
that even look like how do you represent
that how do you solve that what's an
example of a game like that or is this
some of the stochastic games the imagine
let's say business strategy so it's and
not just modeling like a particular
interaction but thinking about the
business from here to eternity
or I think or let's let's say military
strategy so it's not like war is going
to go away how do you think about
military strategy that's going to go
forever how do you even model that how
do you know whether a move was good that
you somebody made and and and so on so
that that's kind of one direction I'm
also very interested in learning much
more scalable techniques for integer
programming so we had a nice email paper
this summer on that for the first
automated algorithm configuration paper
that has theoretical generalization
guarantees so if I see these many
training examples and I told my
algorithm in this way it's going to have
good performance on the real
distribution which have not seen so
which is kind of interesting that you
know algorithm configuration has been
going on now for at least 17 years
seriously and there has not been any
generalization theory before well this
is really exciting and it's been it's a
huge honor to talk to you thank you so
much to us thank you for bringing
livadas to the world and all the great
work you're done well thank you very
much it's been fun good questions
you