Game theory is the study of competing interests, be it individual actors within an economy or healthy versus cancer cells within a body.
Our guests this week, Vince Knight, Mark Harper, and Owen Campbell, are here to discuss their Python project built to study and simulate one of the central problems in game theory, the prisoner's dilemma.
This is Talk Python to Me, episode 104, recorded March 8th, 2017.
Welcome to Talk Python to Me, a weekly podcast on Python, the language, the libraries, the ecosystem,
and the personalities.
This is your host, Michael Kennedy.
Follow me on Twitter where I'm @mkennedy.
Keep up with the show and listen to past episodes at talkpython.fm and follow the show on Twitter via at Talk Python.
This episode is brought to you interruption free by Talk Python Training.
That's right, I'm talking about my courses.
Whether you want to get started learning Python with the Jumpstart course, learn over 50 Pythonic coding techniques, or consume a bunch of HTTP services,
I've got a course for you.
If you're not already subscribed, be sure to be a friend of the show at talkpython.fm/friends.
I have two new courses I'll be announcing in just the next couple of weeks, as well as a major feature, so you probably don't want to miss out on that.
And finally, if you work for a company with 200 developers or more, we should talk.
I have a very special first-time offer for enterprises.
All right, now let's get on to learning how we can minimize our prison sentence by studying the prisoner's dilemma.
Oh, and Vincent, Mark, welcome to Talk Python.
Thanks for having us.
Yeah, pleasure to be here.
Yeah, it's great to make your acquaintance, and I'm really excited to talk about game theory and trade-offs and solving all these sort of standoff problems.
It's going to be so much fun.
But before we actually get into what is game theory, the library that you guys are working on, and things like that, let's start with your story.
Vincent, how did you get into programming in Python?
I'm a mathematician, and so I used various bits of commercial software during my PhD, so Mathematica, the main one.
And then I started looking for a free alternative, and that's how I stumbled on SageMath.
And from SageMath kind of fell into Python and slowly, slowly grew from there, and now I teach Python.
That's really awesome.
And so it's great that you started with SageMath.
I've had William Stein on the show, and I think SageMath is quite the cool project.
It's really generated a lot of neat things like Cython that people are doing totally different stuff with today.
Do you teach classes with SageMath, or do you just teach Python?
We used to.
I used to teach all our first years a combination of Python and SageMath, but actually for a number of reasons, I changed that over to just teaching with Python now.
So the Python Simpy library kind of does a lot of what our first years need to do and the various things about the installation.
That's getting better, especially with Cloud.SageMath, but we've just moved to just teaching Python now.
Sure.
Okay, great.
Owen, how about you?
What's your story?
Well, I'm a ZX81 generation, so I was bought one of those things as a small child, and I've never really looked back.
Once I realized that people were prepared to pay me to do this stuff, that was the career for me.
Like, you know, I could play with this toy every day and I get paid for it?
Oh my gosh, I'm in.
Count me in.
Exactly.
I don't think I've ever quite reached the level of joy of the day I made it draw a space invader, but, you know, once or twice I get close, and one day I hope to get there.
Nice, nice.
I'm relatively new to Python.
I actually started.
My eldest son is one of Vince's students, and when he started at Cardiff and said, hey, it's Python they're teaching us here, he's got a younger brother.
And I thought, right, well, we'll get a head start on, I'd better learn this stuff so that I can teach him.
And so I've only been, I must have used every language under the sun until then, but it's only in the last three, four years or so that I've done any Python work.
Now that's a really cool coincidence, and I think that's a great, it's a great service you're doing for your son to sort of like get him ready for all those things, right?
If you go into almost any kind of university with programming skills of some sort, you're at such an advantage, I think.
Well, I'm sure he'll think so too now that he hears you saying it on this podcast.
I've seen it work out well for a lot of people.
All right, Mark, how about you?
Sure, I'm a data scientist.
I currently work at Google.
Before that, I was an academic in bioinformatics, which we used a lot of Python in.
And I started with Python before that when I was a graduate student in mathematics.
I started writing C++ way back in high school, and that was okay for a while.
But then I looked for languages that were maybe more efficient with my time and less efficient with the machine's time.
So I had a very brief stint with Perl before I found Python, and then I never looked back.
Oh, that's awesome.
And you're using Python day-to-day at Google?
Among other languages, yes.
Yeah.
Okay, cool.
Yeah, you said you started with C++.
I remember when I was at university, they told me I had to start with Fortran, and I pleaded to let me do C++ instead.
I'm like, this will be so much more useful.
I'm sure.
No, no.
Fortran is the most important language you'll ever learn.
I'm not sure I still agree with them.
I was told it was a high-level language.
Yeah, there was a two-year period where C++ was the language of the future before they decided that that was Java.
You guys all worked together on this project.
How did you come to meet each other?
One, I think, the university connection there.
But how did you end up working on this project together?
I don't know if it's worth Mark starting, because I think the link was – I can't actually remember exactly how Mark kind of got started with it.
But, yeah, the link between Owen and I was through Owen's son.
I think I found your GitHub page because it was shared on an EGT blog on Google+.
Ah, yeah, yeah, yeah.
And then I went over and I poked around a little bit and realized I could add a couple strategies right away.
And I did that.
And then I came back a couple months later and started working more on it.
Yeah.
And it just kind of snowballed from there.
Okay.
Yeah, really interesting.
I think GitHub has – their slogan is like social coding or something like that.
But I really do think it's connected people in some pretty powerful ways.
It's amazing.
For me, it's just been – this whole product has just been such an amazing learning experience because, as you can tell from Mark and Owen, they've got a far greater experience and knowledge of software engineering and coding and things like that.
And so everything I've learned is from coding with these two guys, really.
It's just kind of skyrocketed my own knowledge of writing code.
So, yeah.
And that's thanks to GitHub, in a way.
Yeah, absolutely.
Thanks to GitHub.
Very cool.
So let's start with what is game theory.
So the thing that we're going to talk about is your library that solves or simulates, I guess, is really the way to think of it, a certain problem in game theory.
But let's start at a high level.
What's game theory?
Okay.
So it's loosely – loosely, it's kind of the study of interactions between different individuals or agents in some shape or form.
And so it's kind of the study of how strategic interactions form.
You know, like if I know what you know, what should I do at a very loose level?
And hard to say when it really began.
There's kind of different – people tell you different things about when it started.
But the famous game theorist is John Nash.
And he kind of found a particular solution concept to game theory.
So, yeah.
John Nash won the Nobel Prize for his work in economics.
Right.
That's right.
I originally thought it was a Fields Medal.
You guys said, no, no, no, no, no, no.
Very cool.
And he's also the subject of that movie, A Beautiful Mind, which was a great movie.
So maybe tell us, like, what example was he working with?
Do you remember what his work was on?
Yeah.
So he worked on Nash Equilibria, which is kind of a solution concept for in a strategic situation.
There'll be a set of actions that all the players can take from which no one has a reason to do anything different.
So there'll be a point at which we can't really improve.
And his work was to show using a really clever proof that that point always exists.
So it was an existence proof.
And that's kind of snowballed as a solution concept for these strategic interactions.
And so, yeah, in the movie, he has this kind of moment in the bar where he sees everything.
And that's kind of the notion that if we all do what's best for ourselves, we'll actually not necessarily do what's best for everyone, which is a big theme in game theory.
Right.
Economics as well.
And we can get into these local minima, right, where, like, nobody is benefiting from what is happening as much as they could be.
But somebody has to move first.
And so game theory kind of explores that space and finds these minimas.
So if you consider these strategies or those strategies, you'll end up in this situation.
And it's interesting in economics.
It's interesting in public policy.
And it's, you know, all sorts of places.
Right.
Mark, did you want to add something to the game theory thing?
I think it's a good summary.
The paper that Nash wrote is really famous because it's only one page long.
And it has a huge number of citations.
So it's kind of a story goes pretty deep.
But, yeah, I think just adding on what you guys said, it's really fascinating to me that there can be two stable equilibria in a game.
One which is really bad for everyone and one is really good for everyone.
And whether or not those positions are stable or not is another big part of it.
It's one thing to be at that equilibrium.
It's another thing if you can be kind of easily nudged off of it.
And that's the class.
Yeah.
How hard is it and how seated are people in their ways?
You know, you can see that looking at society sometimes.
You're like, well, why are things structured this way?
And you just, if people just did this, right?
And so I think this is really interesting to explore that.
Like one of the classical problems in this space and what is the focus of your library.
So remind me, what's the exact name of your library?
Axelrod?
The Axelrod Library.
Just Axelrod.
Okay.
I wasn't sure if there was like a dash or something.
So the Axelrod Library.
Let's start out with, what's the origin of that name?
Axelrod is the name of a researcher who did an influential tournament several decades ago
around the iterated Prisoner's Dilemma where some of the classic strategies like...
So what's the Prisoner's Dilemma?
Well, so it's named after Robert Axelrod.
That's his full name.
And the Prisoner's Dilemma is a particular situation in game theory where...
A lot of academics run into this problem, right?
They find themselves...
Just kidding.
Right, right.
So the story behind the Prisoner's Dilemma is you've got two prisoners and I guess you've
arrested both of them and they both have to decide whether they're going to rat on the other guy.
Right.
Some kind of co-conspirator, co-criminal sort of thing, right?
Right.
And if you both just...
A gang.
Right.
And if you both just don't say anything, then they have some evidence and they can maybe
get you with a low-level crime.
But if one of you rats out on the other one, then they'll use that confession against them.
So it's in the prosecution or the police's best interest to get you both to confess.
And it's in both of your own individual best interest to say nothing.
But they provide you with a big incentive to confess on the other person.
They say, well, we'll let you go without any penalty if you'll just confess to the other
person.
So it's in your rational...
It's in your own personal interest now to confess on the other person.
But the problem is it's in their best interest to confess, to testify against you as well.
And if you both confess, then it's bad for both of you, right?
This is like one of the local minimums that you can get stuck in that's really bad.
Right.
Exactly.
You both go into jail because you both don't want each other, yeah?
Okay.
And so the actual Rod library or the actual Rod project was around modeling the prisoner's
dilemma, correct?
Yeah.
So one of the things is how do people end up cooperating?
If we're all incentivized not to cooperate with each other, yet we look around, we see all
these situations where people are cooperating.
So can we devise strategies that when we play this game repeatedly that coerce or convince
our partners that they're better off cooperating with us than defecting against us?
Yeah.
Okay.
So let's think about some of the things that you can do with this library.
So the actual Rod competition was held, you said, in the 80s.
And you said the algorithms were lost or the strategies were lost to time.
Is that true?
There's some that can still be found.
But I actually exchanged a very brief, when we started this library, I exchanged a very
brief email conversation with Robert Axelrod saying, I don't suppose you happen to have
any of these strategies kicking about.
And from his very first tournament, he simply said, no, they're not around.
And some of the others are written in, what, in Fortran, I believe?
Yes.
And they're not very well documented or anything like that.
So they're quite difficult to follow.
So some have published descriptions in various books and papers.
But again, they're not usually sufficiently detailed to allow you to completely reproduce
the strategy.
Yeah.
It's not.
It's one thing to describe the concept.
It's another to implement it, right?
Yeah.
Exactly.
We had one poor individual at the PyCon UK Sprint last year who came to the
work on the project and spent the entire day wading through the Fortran code for some
strategy that he was trying to reimplement.
I don't think he was expecting to spend the day working on Fortran at a PyCon.
Well, how was your PyCon experience?
Well, people were nice, but all I did was Fortran.
It was dreadful.
Let's talk a little bit about what this library does.
It's like, so you can set up these things called strategies, right?
And you can have players and tournaments.
Maybe give us a sense for what the whole thing does.
Well, in the end, each player that's participating has a very simple choice to make, which is either
to cooperate with their fellow prisoner or to rat on them.
So a simple choice between two options.
And so what we do in the library is to say all of the different strategies that we know
about, we play them against one another.
And first of all, we do that in pairs.
So we'll put a pair of players against one another and they'll play the game repeatedly over and
over and over again.
And then we'll just match up all the different combinations of pairs for however many players
we're interested in.
And we'll tot up all the scores and see who comes out on top.
Okay, excellent.
So give us a sense for some of the, you have some clever names for the different strategies
or players, right?
Strategy and player, it's kind of the same thing.
So you've got like the basic ones, the cooperator and the defector.
But what else?
Well, probably the most famous one is the tit for tat strategy, because in Axelrod's
original tournament, one of the interesting results that came out of his work was that
this strategy was one of the most successful.
I'm sure the other two will correct me, but possibly even the most successful of the lot.
Yep.
In his tournaments.
Yep.
All right.
So what's tit for tat?
If you rat on me next time, I'm ratting on you.
I'm going to rat on you.
Yeah.
And if you're nice to me, I'll be nice to you.
So it simply, it looks at what its opponent did the last time they played and simply plays
exactly the same choice that they made when it comes around to the next turn.
So of course, if the opponent is being cooperative with it, then it will cooperate.
So it is quite a cooperative strategy and it did very well in Axelrod's original tournament.
Interesting.
And then you've got the grudger, which if you ever turn on the grudger, you're going to regret
it, right?
Well, what else?
There was a few other interesting ones.
Yeah.
There's a lot of variants of strategies where if you cross them once, they'll never cooperate
with you again.
Or maybe if you cross them, they'll forgive you once.
But if you cross them twice, then they're like, okay.
Interesting.
And so implementing these strategies is actually pretty straightforward, right?
It's like you could reasonably write a strategy in like five lines of Python.
Yeah.
Absolutely.
And that's been one of the aims of the library is to make that as simple and straightforward
as we possibly can.
Because it's a great way for somebody who's new to programming or new to Python or new
to making contributions to open source projects to get involved with something and to see an
effect very quickly.
You can invent a strategy that's not been thought of before very easily.
You can code it up in a few lines and you can get it into the library and get it participating
in the tournament.
And it has been a first contribution for many, many people to open source.
I gave a class on repeated games one morning and that afternoon, one of my students had written
their first open source contribution with a little bit of help, but not much.
So, yeah.
I think that's really great.
You know, a lot of people are super interested in contributing to open source, but I think it
feels super daunting because they see all the things they're like, oh, Django, I'd love
to.
Oh my gosh, this is a big project.
And if I break it, oh boy, Pinterest will be mad at me or whatever, right?
Whereas here, really at its core, to submit, to contribute a strategy, all you're doing
is writing a relatively simple, well, it can be simple or complicated, class method.
Just one method is kind of all you need to do.
Yeah.
So, you know, if people are there listening and they're like, hey, I'd love to get started
on this.
You've got some interesting game theory.
Definitely check this out.
I'll be linking to the GitHub repo in the show notes.
That'll be awesome.
Cool.
And we'd love to have them.
We look forward to seeing them.
That's awesome.
You guys are going to be busy with pull requests, I think.
Thanks.
Fantastic.
How many strategies do you have?
Yeah.
How many strategies do you have so far?
In the current release, which is 2.6, we got 184 strategies.
Wow.
But a lot of those are parametrized.
So, you know, you can, for example, a random strategy, we have a strategy that acts completely
randomly.
You can also pass a parameter of making it random where they select to cooperate with a
given probability.
So, in a way, we have pretty much an infinite number of strategies.
So, you have like a two-thirds cooperator, one-third defector-like?
Yeah.
And much more complicated ones as well.
Of course.
So, what are some of the more, not convoluted, but involved ones, I guess?
That's a good question.
There's several that we've implemented from the literature that try to break deadlocking
situations.
So, one of the weaknesses of tit-for-tat is it can get in these confect, or these cooperate-defect
cycles with an opponent that accidentally defects, or if the tournament is noisy or something
like that.
And so, if you can give it a small probability that it will forgive a defection, they can
get back to cooperating again.
So, there's a lot of strategies that implement little things like that, that attempt to get
the players back on track.
I see.
Just kind of break, because if you just go really clearly down the cooperate-defect,
grudge, you end up in these equilibrium really quickly, right?
And so, as you make concessions over time or take more of it into account, it can probably
be more interesting, huh?
I was going to say, Mark, if you want to talk about even some of the more complex ones where
we're using neural networks and we're training these strategies using genetic algorithms and
things like that.
Now, that is cool.
Sure.
You're probably best placed to talk about those.
Sure.
Yeah.
So, one of the great things about the library is that we have so many strategies already,
and you can use these to train new strategies using typical machine learning methods.
So, we had a couple of really interesting contributions, I guess, almost a year ago from
Martin Jones, who's, I guess, somewhat well-known in the Python community.
And he submitted a strategy that used a lookup table that he had trained to find the optimal
response against all the other strategies in the library.
And he also submitted the first one that used the neural network.
So, we've extended that method of taking a strategy based on some kind of machine learning
algorithm, training it against the other strategies, and then adding it back to the tournament to
see how it does.
And right now, those are amongst the best players in the library in terms of performance.
Oh, wow.
Okay.
How interesting.
And is it adaptive?
Or does it somehow identify?
Like, okay, I think that thing I'm playing against, that's a grudger.
So, I'm going to do a grudging thing.
That's a great question.
So, some of the strategies that try to adapt on the fly don't always do so well.
But what you'll see is the trained strategies typically learn things.
Like, if you defect too many times in a row, then they'll just decide that they're going
to give up on you.
That you're one of these strategies that is never going to cooperate with them.
So, they'll just defect with you for the rest of the time.
And we've got some population dynamics based ones as well, which we can talk about a little
more.
But they have to learn to play against themselves and the other players.
And they end up evolving like a handshake so they can recognize other variants of themselves,
but exclude opponents that aren't like them.
Really?
Wow.
That is so interesting.
What's really cool is that that kind of comes out of the training.
So, we just train them.
And so, we're not kind of designing that handshake, but we're seeing that handshake evolve, which
is kind of cool.
For sure.
Okay.
Yeah.
That's incredible.
I didn't really expect that.
Like, you know, at Google last year, they came up with those two neural networks that would
exchange encrypted data.
And a third one that was trying to break it, the Adam Eve, the Alice Bob and Eve one, that
one, that basically invented a way to talk to each other to do encryption.
And it sounds like this is kind of like that a little bit in the sense that they like know
how to play against each other.
I mean, I'm not saying it's necessarily the same thing, but.
I think it's in the similar vein.
Yeah.
It's a result of the same kinds of reinforcement training strategies.
Okay.
Interesting.
But each of our matches is typically only 200 turns long.
So, they've only got 200 bits of information to do this.
So, not quite in the same league as what Google are doing.
That's right.
And the worst thing that'll happen is they'll win a tournament.
We're not letting them just get the computers to talk to each other without us knowing what's
going on.
So, we're okay.
Yeah.
The singularity probably won't come from these strategies.
Who knows?
I mean, maybe.
But if it's ever found on GitHub by one of these other AIs, it's going to bring it back
in and it's going to be trouble.
I don't know.
If we can just get society into this local minimum, we have them.
All right.
So, the idea is you have these strategies, which are really interesting.
And then you kind of do like a survival technique, right?
You have them compete against each other over and over and over, 200 times, you say?
And then you can draw really interesting conclusions like, well, we had this even distribution at
the beginning of each type.
But at the end, we had way more grudgers or whatever.
Maybe talk about that a little bit.
Yeah.
There are a couple of variations of tournaments that you can play.
And some of them play these population dynamics.
So, in various different ways, at the end of each round, your score determines the size
of your population going into the following round.
And at the end of it, we look to see, well, who's died out, who survived through to the
end?
Has one strategy dominated the final population?
Or have we ended up in an equilibrium of three equal populations with three different strategies?
And that's actually, if you've seen the logo for the library, that sort of multicolored
plot, that's a plot that comes out of one of these population dynamic tournaments.
And it's showing one or two of those strategies are surviving very nicely through to the end
and dominating.
And a couple of them have died out and don't have very much population left at all.
Yeah.
And you have really nice visualizations of the results.
I really like those.
So, some of the tournaments you have, you say, round robin.
You have spatial ones and probabilistic endings.
What are those?
Well, as I said earlier, the first thing that we do is to pitch two players against one another
and then they compete for a certain number of rounds.
Well, in most of the tournaments, that number of rounds is fixed and it's the same for each
pair that plays.
But in the probabilistic ending, you set a probability so that in any given round, there's a probability
that that might be the last one in this match.
So, the length of matches between different pairs varies.
Whereas in all the other tournaments, they're all playing for exactly the same number of rounds.
Okay, cool.
Have you guys ever done anything like trying to study career criminals?
So, ones that go back to jail and back.
So, if you lose a round, you have to like sit out a round or something.
Only the ones that win or they somehow get released back into the population based on how long they
were sent to jail for.
I think you need to put a PR through.
I was going to say, yeah.
PR is very welcome.
Yeah.
We don't have that.
But actually, the library would allow for that to be implemented because we have these structures
for how the tournaments are in these different tournaments.
And so, you could theoretically build a tournament that has some sort of dropping out phase or things
like that.
Yeah, you could do that.
Oh, yeah.
Sounds interesting.
Yeah.
And there's lots of variants of the game that have been studied in the literature where other
than corroborate and defect, you can also like intentionally punish your opponent by taking some
of their points away or some of their money away.
And these are, you know, usually done with small studies of undergraduate students to see if it
improves the equilibrium.
And we haven't gone down that.
It was something we've talked about before.
And like Ben said, it would be relatively easy to add to the library.
But I think we've had so much fun with just the regular prisoner's dilemma that we haven't
messed with that part of it.
Yeah, you haven't had to go out there because it's still interesting to study.
I do have access to students.
That's true.
We also have a whole set of strategies that we sort of collectively refer to as the cheaters.
They don't conform to the rules of the tournament that Axelrod originally did.
They do all sorts of things within the code.
So they'll try to manipulate their opponent's code.
They'll try to manipulate the history of the scores.
And so we allow those strategies in.
And so there's quite an interesting little tournament that just plays them.
And sees, well, which is the best cheating strategy?
So who's best at writing strategies that manipulate the internals of Python and mess about with
their opponent's class methods?
Yeah.
So that's really interesting.
The normal ones, they're provided.
I mean, everybody's provided.
But the normal ones look at like, what did my player, my opponent do last time?
Did they defect?
Or did they cooperate?
And I'll do something.
But the sneaky ones, the insider trading ones, if you will, they say, you know what?
I actually have a self pointer.
And my self pointer has the opponent.
My opponent has a method that's called like respond.
And you can just overwrite that method to say, return C.
Exactly.
And it was a bit of a headache at one point, because as the library matured and became quite
a good research tool, well, a very good research tool.
We had these cheater strategies that were kind of all good fun and games at the start.
But I think we made a good decision earlier on to bring in this classification of strategies.
So you can't stumble on the cheaters by accident.
But if you want to go get them, you can.
And at the same time, there's loads of other things that we can classify strategies on.
So for example, how long is their memory?
Do they only look at what they did in the previous round?
Or do they look all the way back to the beginning of the game?
And you can kind of go and get strategies based on that.
Oh, interesting.
So basically, they provided a list of opponent responses.
And you could say, like, always, you know, trim that list to like 10 or 5 or 1 types of
responses, right?
Only consider strategies that only look at, you know, that much memory, so to speak.
Okay.
Because that's another interesting thing.
Talking about these sophisticated strategies that make use of neural nets and stuff.
There's a lot of talk in the literature, in the research literature, about whether or not
memory matters, you know?
And so this particular paper that made a lot of noise recently, well, in 2012, was it?
But they were like, actually, you know, any strategy can be beaten by a strategy that only
has very little memory.
And we're kind of seeing with the vast amount of strategies we've got that we can train strategies
that can adapt and can learn and can be very powerful and very sophisticated.
I see.
So maybe like if you're going to write a strategy yourself where it's procedural and you write
the code, like maybe it doesn't make sense to remember 200 steps and try to like, how
do I fit that in?
But if you give it to a deep learning neural network and go, here, this is what they did.
What does that mean?
Maybe it can actually find within that the patterns that we don't see.
That's right.
Mark wrote a paper on that with the coolest title ever.
It's called The Art of War.
So you could...
That's awesome.
We came up with a strategy that used a lot of memory that was very effective.
So I think there's this, there's been this kind of longstanding folk idea in the game
theory community that complicated strategies are more trouble than they're worth.
And that's because in the beginning, Tit for Tat was winning all these tournaments.
And it's a really simple strategy that only looks at their previous round.
And people tried to do all these complicated heuristics and stuff like that.
And it just didn't work because the other strategies were like, I don't know what this
other guy's doing, but it's complicated.
So I'm just going to defect against him and call it good.
I was just a human.
Come on.
I can't, I can't be.
Right.
But yeah, we've definitely seen some success with these longer, these strategies that can
be trained to do something sophisticated.
Yeah.
And how, how intense are the AIs that, that you're putting in?
Like, is this deep learning?
Is this just a neural network?
Does it involve things like TensorFlow and like GPUs or is it, is it pretty simple as far
as those go?
So the way we train all of them right now, I did play with using TensorFlow, but some of
the other strategies, the only way we can really do it is with an evolutionary algorithm.
Just mutate and see if it's good.
And so all the strategies we train now use that method, even the neural network and the
neural networks we use are pretty simple.
They're, they're basically one layer deep.
Can you give them access to, or have you given them access to previous tournaments and the
whole outcome and letting them look at that or like letting them see more than the tournament
that they're in?
I haven't currently trained one.
So I did train a neural network that tries to predict the next move.
And I let it look at a lot of games for that, but then I had trouble turning that into a
real strategy.
And it turns out it was better just to take a neural network and directly evolve the parameters
that do well on a tournament.
And in that case, it doesn't actually look at the outcomes of third party games.
I see.
All right.
You guys talk about a thing called Moran processes for population dynamics.
What's the, what's the story there?
What's that about?
I'm not familiar with that.
Sure.
So this is a, I got the classic example of a population dynamic.
You basically have a population of, in our case, in different strategies.
But if you were thinking like animals, it would be the, you'd have a bunch of animals that
have their different sizes, or they have some different characteristic, different eye color
or something like that.
And then they all interact with each other and they accrue fitness points.
In this case, they're playing the prisoner's dilemma and whatever their score is, is their
fitness.
And then you select one of them to reproduce proportional to its fitness or score.
And you randomly select one to, to die of natural causes, let's say.
And so one step at a time, the population evolves as one strategy does better than the other
ones.
I mean, it depends on the intrinsics of the strategies themselves and also the makeup of
their opponents.
So if they play well with certain opponents, then they're better off and a population has
a lot of those kinds of opponents.
I see.
So it's underlying dynamics that actually decide how the population of one type of thing,
like the grudgers or whatever, grow or shrink over time.
Yeah, exactly.
And so the questions around that are, is a population stable to invasion by a mutant
type, a different type?
Or is a strategy good at taking over a population of another type?
Oh, interesting.
Okay.
So yeah, something that sounds like it could be a cool variation on tournaments, maybe you've
done this, is what if you introduce like an invasive species type?
Like you run the tournament for like three fourths of the way through, and then you introduce
some other strategy that wasn't initially there after like others have been killed off.
Have you tried this?
Oh, there's your second PR, I think.
We're doing well here.
Yeah.
I think it would be cool because, because a lot of them, like if you look at the graphs,
it's super hard to talk about pictures on the audio.
But if you look at some of the diagrams, and I'll link to your presentation at PyCon, you'll
see that in the beginning, there'll be all these different types, and some of them will
die out after a while.
And maybe the strategies that won when they were around are not the same strategies that
win if some new type comes, right?
Yeah.
Okay.
Like if you throw a cooperator into a room full of defectors, it won't do very well, because
they'll rip it apart, basically.
Exactly.
Okay.
Quite interesting.
Yeah.
All right.
So what did you use to visualize those results?
Those graphs are really nice.
Is that Matplotlib or something else?
That's all Matplotlib.
Matplotlib.
Yeah, yeah.
That was at the start, we made it so that you could easily get various outputs of the
library.
It's all just done in Matplotlib.
Okay.
Yeah.
And there's two sub-libraries in the repository, one that does something called fingerprinting,
which is this idea from the literature that gives you an image that corresponds to a strategy,
which those are kind of neat to look at.
And then there's another one that's been around for a while that looks at how often each strategy
cooperates against each different given opponent.
So we have a lot of other visualizations and they're mostly with Matplotlib as well, with
the occasional Seaborn, I think, here and there.
Okay.
At the start, out of the three of us, I think it's fair to say I was the keenest to keep
the library very light on dependencies.
And so I was kind of a roadblock for quite a while with Mark and Owen more sensibly saying,
no, let's use all these awesome libraries to make the code better.
And I was like, no, no, no.
Let's pure Python, pure Python.
And so Matplotlib was introduced, but it had this really nasty little fix so that you could
still install the library without it.
And then eventually I understood what was the way to do things.
And so a lot of code got a lot neater when we started making use of all the great libraries.
That's nice.
The fingerprinting is another good little story.
I put an issue on the library.
It must be about 12 months back now.
One of the early ones, yeah.
Just a bright little idea, I thought, which was that we were starting to get people contributing
strategies other than the three of us.
And I was starting to find it tricky to work out, is this strategy the same as one that we've
already got?
And this is back in the days when I think we only had about 30 or 40 strategies.
And I was starting to find it tricky then because, of course, it's not enough simply to look
at the code because the same decisions can be coded in all sorts of different ways.
So it struck me that we could do with a better way of trying to decide whether a given strategy
was at least similar to one that we'd already seen.
And I naively typed that up into an issue on the repository and said something like, maybe
we should just find a handful of strategies that we play them against and we can do something
clever mathematically to work out how similar they look, thinking that my friends, the mathematicians
would go, yeah, that's a great idea.
I'll do that this afternoon.
Oh, no, they say this is a significant mathematical challenge.
And 12 months later, here we are with some poor student of Vince's doing it as his final
year project.
The interesting thing is that that poor student is actually Owen's son.
He's now doing his final year project with me.
And so he's implemented this graphical approach from the literature, which has its strengths
and weaknesses.
But actually, I think this might be news to both Mark and Owen, as well as all the listeners,
is he's just been working on a cleverer way of doing it, building a statistical model that
will spit out if two strategies are different or not.
So yeah, hopefully we'll be able to talk about that a bit more at some point.
Well, I think that's really funny that you just throw that out there.
Like, ah, you guys could just like compare strings or something and see.
No, no, this is actually a lot of work.
But on the other hand, it's super cool that something constructive as a project is coming
out of it, right?
Like, that's interesting.
And things have worked the other way, too, where I've gone like, oh, we got to do this
thing.
It's probably going to be really, really hard.
And then Owen and Mark are going, oh, you just need to use a class, something, something,
something.
And like, it's two lines of Python.
I'm like, oh, okay, cool.
I can actually do that in a less comprehension.
We're good.
Have you thought of involving like deep learning and the classification of similarities?
Like, that would be interesting.
I did write a blog post a couple of years ago where I derived a bunch of features of the
strategies and the tournaments and did a little bit with it.
But that was back right when we had just about 100 strategies and we weren't calculating as
many things.
So that's definitely worth a revisit, see if we can do more.
That's actually kind of, that was the plan with this poor final year student.
But actually, we've kind of got some really promising results using rather naive statistical
models.
So we need to look into that a bit more, but it doesn't look like we need to be too
sophisticated.
Again, because of the way the tournament is now and the, sorry, the way the library is
now, it can just create so much data for us, which is a real strength.
Oh, that's excellent.
I think this is a real service, not just for Owen's son and your student in this particular
case, but I think that it's, this kind of stuff is really valuable to students who are
coming out of school and they want to get a job, right?
If they come in and say, well, what do you know about programming?
Would you like to see my project on GitHub and maybe the paper that was published built
off of it?
And here's my optimizations I've done.
And like, if you can provide that to students, then they're in such a better place when they
go out and say, Hey, I want a job.
We actually had a student turn up today or yesterday.
I forget.
And she, you asked, didn't you, Owen?
Like, how did everyone find this library?
Because we've had quite a few people now.
And she said, Oh, actually, as part of my course, I have to contribute to an open source project.
And, you know, she'd found the actual project and seen the documentation and the community.
And she's decided to choose us, which is great.
Oh, wow.
That's really cool.
Think of how the world is going to be after 10 years of this kind of stuff.
Like all the students have to contribute to open source and they have to somehow be really
aware of this.
And they're totally familiar with, that's your pull request.
They know what that means.
Like that's just, you know, it's already got so much momentum, but I could see a world
where it's like, we'd look back at these as quaint days when open source was small.
Another good kind of side to this project is in terms of academic research.
So going back to the fact that Axelrod's original tournaments can't really be reproduced and there's
loads of papers that can't be reproduced.
That's like a problem in modern research where so much software is needed and written, but
it's not necessarily written in a sustainable way.
And so the Axelrod project is a really good example of maybe I'm a bit biased, obviously,
but I'd say best practice in terms of, you know, our code isn't only written and documented
well, but it's extremely well tested and it's constantly being refactored and improved.
And it's all, you know, a wonderful example of how you should be doing research.
Yeah.
You guys have a nice read the docs and all sorts of stuff, right?
But just to go into Owen's point, it's pretty rare for academic code to be even sufficiently
documented to use it again, let alone enhance it or anything like that.
It's just because the journals don't require it a lot of times when you publish it.
And two, I think the way we have our test suite, we really try to test every stated behavior of
every strategy so that we know that it is as close to the real deal as we can get it.
That is really awesome.
And I think it's great.
And you have sort of the case study in this example of the way not to do it and the way
to do it all wrapped into one, right?
With the actual rod original tournaments and people are like, we don't even know if we
can reproduce these strategies.
And yet there's, there are papers and stuff written on it, right?
Absolutely.
And so you're like, well, how do you validate that science, right?
That's been a real eye opener to me as somebody that's, that's got no academic background whatsoever
since the day I graduated and vowed never to sit an exam again in my life.
To come back into it, albeit on the fringes, however many years later, and find that there
are papers and papers and papers written on the back of software that isn't accessible.
And I look at that and say, well, how is that reproducible?
How is that scientific?
And it's been, it's been a real shock to me to find that we in this little project have
so much of a struggle to try and reproduce other people's results.
Yeah.
But I think what you guys are doing, I mean, obviously it's open source.
It's got version control all the way through.
So somebody can go back, well, this paper was written on this version.
It's not just, I still have the library, but I have exactly the same code.
I think that's interesting.
You know, I was talking to Kyle Cranmer from the Large Hadron Collider, and he was talking
about how this is the problem in particle physics as well, just like reproducible science in general.
And they do interesting things like have kind of an escrow service to hold the code tied to
the paper and stuff like that.
So I think, I think there's people trying different things from different angles, but yeah, very nice
work.
So what's the computational story here?
You have 183 strategies, 200 rounds.
They all fight with each other in certain ways.
Like how long does it take to run a typical tournament?
Is it pretty quick or is this like, you got to go have lunch?
Well, the full tournament on all the strategies takes about an hour on a typical machine.
So does that fit with that?
Vince has some nice 16 core machines that can really chew through it.
Yeah.
So on that, it's still just under an hour for the full noisy tournament, which is the
one that takes the longest amount of time.
Because that's another thing that's inbuilt in the library.
It's completely paralyzed.
So you can play all these matches in parallel and the library takes care of that for you.
So you can use up as many cores as you can get.
Okay.
That's cool.
And some of the classifications, if the strategies are deterministic, then we don't have to
repeat those matches.
But if the tournament's noisy or the strategies are stochastic, then we have to repeat those
more times.
So depending on exactly what strategies you choose, it can be extremely fast if they're
all deterministic or it can take a lot more time if it's like a noisy tournament.
Okay.
So have you guys tried to do any fancy tricks to make it faster or something like that?
You talked about figuring out if it's deterministic and then going, okay, it already knows
the answer to this.
I would want to very cautiously say that I think we're already doing a fair few of these
tricks, you know, like the parallelization, like vectorizing things where we can.
But again, if anyone wants to take a look and make it faster.
Writing the multiprocessing is several days of my life I'll never get back and I don't
wish to repeat.
Yeah.
And as someone else who worked on that part of it, wow, yes.
Yeah.
I think we all kind of broke our knuckles on that for a bit.
Yeah, that was...
Yeah, that sounds really cool.
Of course you want it to go as fast as possible, right?
Like, you know, maybe somehow bringing some NumPy scipy into it.
I don't really know or who knows.
But it seems like an interesting computational challenge in its own right.
Yeah.
And you guys have battled it some, it sounds like.
Yeah.
And part of it is memory overhead as well.
If you're batching out the matches, you can do them in parallel.
But if you do too many of them, then you exhaust your memory, you hit swap, and then you're
done for, you know?
Yeah.
That was a big bit of work when all of a sudden we realized that like we were using more than
16 gigs of RAM and we kind of did it all.
So now it's basically got no memory fingerprint anymore.
But we do it all to file.
But I'd forgotten about that.
Yeah.
It sounds just like an interesting algorithmic problem.
And then, you know, you've got the known structure to deal with and stuff.
But then people are throwing these strategies at you that you have no idea on how they're
going to behave.
And so that's like an interesting twist.
It just, it sounds like a fun problem to me.
Yeah.
We do label the strategies too if they have a long run time.
So some of them take 10 times, 100 times longer in whatever computations they do than
say tit for tat.
So that's another thing that we've studied, optimizing specific strategies.
There's a couple of really cool strategies in the library.
They're called meta strategies.
And they basically take a large group of the other strategies in the library, maybe all
of them, and then take the consensus vote or something like that.
So they, by definition, are 100 times slower than the other ones.
Yeah.
Because they just keep rerunning.
That's a pretty interesting idea.
It's almost like the politician thing.
You see what people are asking or what they want and just like, I'm just going to do that.
Well, however the wind is blowing, that's how we're going to cooperate here or whatever.
Yeah.
So are there interesting combinations that work well?
Have you tried that?
Instead of running all of them, go like, I think this set of them or that set, like this
mixture of like, I'll ask these 10 and see what I get.
I have played with it a lot.
So that was one of the best strategies in the early days, these meta strategies.
And of course, you know, if you give them like the top five other strategies in the library,
then it does well.
But one change we made recently is rather than take the best performer of all the strategies
in its set, if you randomly take one of the top 10 performers, it actually works better.
And if you always go after that top one, which is sort of a weird quirk of like an ensemble
machine learning method.
Yeah.
Very interesting.
You can study a lot of cool stuff with us.
It sounds like.
So maybe give us some stories like where this has been used.
Like, obviously, if any of us or any two of us, I should say, get like captured by the police
and charged with a crime, we'll know what to do.
We'll have a more informed view on what to do.
But, you know, it's not just for prisoners, right?
It applies to other things as well.
Yeah.
And Owen added a pretty interesting strategy not that long ago where you can play as a
human.
So you can pick the strategy you want to play against and you can submit C or D and practice
your one-on-one skills versus these strategies.
Nice.
That could have been an Atari game when it first came out.
One of the kind of applications of this study is to understand the evolution of social norms.
So, you know, like as Mark said at the beginning, you know, why when you look around, are we cooperative?
And then that kind of steps onto other fields of evolutionary game theory that are then applied
in like mathematical oncology and things like that.
So these ideas are all interconnected and have wide-ranging applications.
Yeah.
Okay.
Cool.
You said that there's some applications in mathematical oncology for cancer.
Yeah.
What's that?
That's kind of not immediately looking at the prison's dilemma, but the same ideas kind
of transpire that you can see the spread of a tumor inside a health body in the same way
that you can think of introducing a particular strategy into another population.
And so things like Moran processes and evolutionary dynamics and population dynamics have been used
to understand, yeah, the spread of cancer.
And so mathematical oncology.
Yeah.
You can kind of think of cancer as a cooperator that has switched strategies to a defector
and is now trying to take over.
And so can it invade that population or not?
Oh, wow.
Okay.
It's really interesting when these things make connections to somewhere where they're totally
unexpected, right?
Yeah.
Like people working, you know, I'm sure Nash wasn't thinking about cancer when he worked on
his game theory ideas.
Nash got his Nobel Prize in economics, right?
And the ideas that he was thinking about when he first wrote his paper and his thesis, they
kind of just rolled really.
And he didn't really see it coming.
Well, I'll say that.
I don't know that for sure.
But it certainly wasn't what he was thinking of when he was doing the work.
Yeah.
Very interesting.
Yeah.
And it's still using economics now.
So there's this idea, this like first approximation that everyone does what's best for them.
Like they take all the available information and they say, it's best for me to invest in
this thing.
And that's not what most people do.
Most people just copy someone else's strategy or someone else's advice.
So it's more of an evolutionary process than rational process that we would think of it.
Sure.
Does it appear in politics or is politics too slow of a process, right?
Like every four years, every six years, like is that enough for people to see these strategies
and evolve?
Or what do you think?
Well, I know there's papers that are written in political science that use this kind of stuff,
but I don't know how well applied to the real world they are.
They might just be theoretical.
I know there were lots of blog posts written about game theory and Brexit.
So some combination.
Yeah.
I was just saying, well, I was thinking of Brexit.
I was thinking of the US presidential election.
Like both of these are unexpected.
And I'm wondering if game theory has interesting things to say about them.
Don't blame us.
I'm not blaming you guys.
I was actually in London when the Brexit vote happened.
And it was very interesting to walk the streets of London the day after.
It's quite something.
A really, really neat project.
And I love how it applies to all these different things.
And I don't know if Mark and Vince have noticed, but whilst we've been chatting on our Gitter
channel, we've now had somebody new come on saying,
that they're a student.
They're on a course where they're required to contribute to an OSS project.
And they like the look of our project and they'd like to know how to get involved.
So that's awesome.
I could tell you what to say.
I didn't think this was a live broadcast, but now I'm beginning to.
Gosh, yeah.
Talk Python works fast.
Yeah.
Well, maybe it's just someone's hacked into my computer.
So what you need to tell them.
I think that's as much as it's on the one side of where the library is gone.
And it's a really sophisticated, rich research tool that has various applications and things.
But one of the other things that we've kind of really been careful to is sometimes at the
cost of efficiency, we have prioritized readability and entry of newcomers, not only to Python,
but the programming.
And I think that's something that we're all pretty proud of, that the library is a good place for newcomers.
In fact, at one point, the winning strategy, it's no longer the case, but at one point,
the winning strategy was written by a particular high schooler in the UK, which is actually Owen's other son.
So cool.
There's a lot of connections to Owen's children here.
How interesting.
They get you into all sorts of trouble.
So, Owen, here's what you need to tell that person and get her.
There's this simple problem about fingerprinting, and they should be able to knock that out right away to get started.
All right.
I think maybe we're kind of getting low on time here for talking about the project.
There's one other thing I wanted to ask you guys about here.
And you said that in the notes, you'd put down something for a thing called ugly fruitcake.
What is ugly fruitcake?
That's my son's username on Twitter.
Awesome.
Well done, Mr. Ugly Fruitcake.
No, that's awesome.
Excellent.
Okay.
So I guess we'll kind of have to leave it there.
We're getting low on time before we're talking about it.
But it's been really, really fun to talk about.
Let's talk two things really quick before we drop this, I suppose.
I still want to ask you.
One, what's the Python 3 versus Python 2 story?
Like, what support is there for each version?
So for a long time, we were supporting both.
And eventually, we kind of made what I think is one of the best decisions we've made so far is we dropped Python 2.
Was that on the 1st of December last year?
I seem to remember.
And that's just allowed us to clean up our code base so much and pull people away from legacy Python.
So yeah, we're using...
That's awesome.
I think that's a really great move.
And also, you were talking about the readability and the simplicity.
Like, as a newcomer to Python, you're often, like, hit in the face with this dichotomy.
And if you can avoid that, that's really nice.
And even as not a newcomer, it was still challenging sometimes.
We've gotten into weird cases where iterators and generators were interacting across the different versions.
Right, right.
Yeah.
Or just mistakes because of division.
Yeah, absolutely.
And then also, Jaxelrod, am I saying that correctly?
Yeah.
What is Jaxelrod?
Oh, Django Axelrod.
That's a longer-term attempt, really, to build a web app on top of this library.
So instead of installing it yourself and trying to set up tournaments on your own machine,
the idea here is to say, well, it would be good to be able to tuck this library away somewhere on a much bigger machine
and put a web front end on it, and in that front end, you could define the tournaments that you want,
submit them to the server, it would run them, and then spew the results back at you
for you to get out and do some analysis with.
That's a project that we've kicked off, and the reason for the name purely is because we're using Django
and the Django REST framework to try to do it at the moment.
But it's in fairly early stages at the moment.
So again, if anybody listening fancies getting involved, it would be an excellent area to get into.
All right. You want to do some web work and turn interested in game theory?
Here's your chance, right?
Yeah, absolutely.
It's very cool.
Okay, nice. Is that publicly available or just something you guys have?
No, no, no. It's another one of the repositories on GitHub under the actual Python organization.
All right. Awesome.
The organization GitHub profile has not only the library, but it has lots of really interesting collection of notebooks,
collection of visualizations, the fingerprints, lots of interesting repositories there,
as well as Jack Solrod and this rest of the way.
Okay, excellent. Yeah, I'll definitely link to those as well. That's great.
All right, guys, it's been super interesting. I really enjoyed our conversation.
But before I let you go, quick round of questions.
Owen, if you're going to write some Python code, where do you open up?
I'm a sublime text man.
And you said that you like the Anaconda plug-in, right?
I do. It sits there and tells me where I've gone wrong. Shows me all my mistakes, yeah.
You like people to yell at you, huh?
As long as it does it quietly so I can ignore it when I feel like it, that's fine.
Yeah, no, I think things like that that really give you that extra insight are super, super valuable.
So, cool. Mark, how about yourself?
So, I usually use PyCharm lately. I started using it about a year ago, and I really liked it.
Before that, I just used kind of a bare-bones text editor for the most part.
Okay, nice. And you probably use a lot of Jupyter, like, notebooks and stuff as well at work.
Yeah, in general. I also teach a data science class that's based on Jupyter notebooks, so I'm really comfortable.
Yeah, I like Jupyter a lot, actually.
Yeah, it's pretty neat. It's definitely got a lot of momentum.
Vince?
I also use Jupyter a bunch, but my editor's done.
Okay, awesome.
And PyPI package, we just passed over 100,000 PyPI packages, which I think is...
Yay!
That's awesome.
Yeah, that's so cool.
So, how about, like, the favorite ones? Like, same order. Owen, how about you?
I think my favorite at the moment has got to be Conch, the shell, the Python shell.
So, I've finally got to the point now where it doesn't matter what operating system I'm on, I've got exactly the same shell, and its config files are written in Python.
It's a thing of beauty.
That is beautiful. And that's X-O-N-S-H, Conch.
It is.
It's very cool, yeah. Mark?
I think Request is my favorite. It's so easy if you're doing any kind of, like, web scraping or anything like that.
I like a lot of the different ones on there. And, of course, Axelrod has got to be my favorite one.
Yeah, why not throw that out there? For sure, for sure. And Vince?
I have to mention QCiW. That's written by a PhD student of mine, so I just want to test that he actually listened to the end.
It's a library for simulating queuing processes, but I think my favorite has to be TQDM.
It's a brilliant little library that you can use to wrap any iterator, and it'll generate a progress bar for you for free.
Oh, that is cool.
Yeah, it's really, really cool, because you don't have to do anything. You just get these progress bars, which sometimes when I'm doing something, that might take a little bit of time.
I'm not sure how long. I can just quickly import TQDM, and straight away I get an idea of, oh, no, this isn't going to take an hour.
This is going to take a couple of years. I've got to change something.
Exactly. Fabulous.
Okay, great recommendations, guys. Thanks. And final call to action, people should get started with Axelrod?
Yeah, come on over. Come check us out in our Gitter room and just say hi and submit a strategy or anything else.
But yeah, we really welcome contributors.
Yeah, I can say look at the code. It looks definitely easy to jump into, especially if you want to do the strategies.
And I feel like there's a chance to plug in more interesting, intriguing things that people are not expecting and probably get some cool results.
For sure. Absolutely.
All right, guys. Well, this has been a great chatting with you. Thanks for being on the show.
Thank you so much.
Thanks for having us. Thank you.
Yeah, it's been a pleasure. Thank you.
Yes, it has. Bye.
This has been another episode of Talk Python to Me.
Today's guests have been Vince Knight, Mark Harper, and Owen Campbell.
And this episode has been sponsored by Talk Python Training.
Check out all the courses at training.talkpython.fm.
Be sure to subscribe to the show.
Open your favorite podcatcher and search for Python.
We should be right at the top.
You can also find the iTunes feed at /itunes, Google Play feed at /play, and direct RSS feed at /rss on talkpython.fm.
Our theme music is Developers, Developers, Developers by Corey Smith, who goes by Smix.
Corey just recently started selling his tracks on iTunes, so I recommend you check it out at talkpython.fm/music.
You can browse his tracks he has for sale on iTunes and listen to the full-length version of the theme song.
This is your host, Michael Kennedy.
Thanks so much for listening.
I really appreciate it.
Smix, let's get out of here.
We'll see you next time.
Thank you.