Thank you.
Yeah, thanks to everyone who's stuck around to the end of the day.
I was going to make a joke about how I'm headlining foster,
but based on the room size, I'm not going to make that joke anymore.
So thanks to coming to my talk, it's about pie gambit,
which is an open-source software for game theory.
It's part of a broader gambit project.
And yeah, my name's Ed, I work at the Andrewing Institute in London.
I'm a research data scientist and also research software engineer.
So some of you may have heard the talk earlier about that.
So before I talk about gambit software itself, I need to introduce game theory.
So game theory is this field of study that came out of economics all the way back in the 1950s.
So it was invented by John Nash and the relevance to today,
as well as economics, is that it's increasingly being used in modelling of cybersecurity,
especially anything to do with AI and multi-agent systems.
And game theory is defined as mathematical models of what we call strategic interactions between games,
between players rather.
So strategic interactions between players, which we call games.
And the players in these games can be humans, as was the case obviously,
in the original use case of economics.
But that can also be extended to animals, you know, there are ecologists that if you use game theory,
and of course, AI agents.
So the players of the games are basically any sort of intelligent agent that can form strategies.
So gambit is a software project that includes tools for doing game theory.
In particular, it focuses on finite non-cooperative games.
So these are games that have an end, so they're finite.
The end of the game, each player has kind of a pay-off associated.
And a non-cooperative, so the players are adversarial, they're competing with one another.
As I mentioned, as it's used in a variety of domains, in terms of the software,
I'm going to be talking about Pi Gambit, which is the Python package,
where that's built on top of C++, and there are CLI tools and a graphical user interface.
And the project is quite old, so I don't know if anyone remembers the 1980s.
I don't, but it's been going that long, and some of the people involved who I'm working with have been working on it for that long.
But more recently, the work has been taking place at the Alan Cheering Institute,
and in particular, we've been working on Pi Gambit, which is what I'm talking about in this talk.
But just to note, we've also been working on a project involving large language models,
so that project is about translating natural language descriptions of games into the game code.
The game code is Pi Gambit, which is what are we talking about now.
And also, a relevance to this conference, and some of the talks earlier,
we want to work on open source community building, because it is an open source project.
So Pi Gambit is the Python package associated with Gambit, as I mentioned,
it basically has two core features. It allows you to construct games in the few lines of code,
and then it has a library of algorithms.
And one set of algorithms is used to compute what we call Nash Equilibria,
so Nash was the guy he saw earlier. Nash Equilibria basically scenario in a game,
where none of the players have any incentive left to deviate their strategy,
so they're at Equilibrium, and I'll walk you through an example of that in the moment.
So what I'm going to talk about is exactly those two things.
I'm going to show how you can construct a game in Pi Gambit, how you can compute the Nash Equilibria.
And I'm also going to demonstrate how the package is interoperable with some of the other packages in the Python scientific computing ecosystem,
in particular one from DeepMind, called OpenSpeel, which is also all about game theory.
Okay, so let's switch to the live demo.
So hopefully you're all still awake.
It can try and pay attention to this, so I'm going to demonstrate Pi Gambit in action through a couple of example games.
The first thing I'm going to demonstrate is that first feature it's all about which is how to construct a game.
And I'm going to demonstrate that both with Pi Gambit, and as you can see here at the bottom, the draw tree package,
which we've built specifically to help visualize games that are built with Pi Gambit.
So I'm going to talk you through this very simple game, and it's a game that is an extensive form game.
That's the game theory terminology.
As you'll see, basically that just means tree structure.
The game is called stripped down poker.
That's not to be confused with the strip poker, which is an entirely different thing.
Pause for laughter, thank you.
There's a unit.
Okay, so basically there's two players.
We're going to call them Allison Bob.
And the start of the game is there's a deck of cards.
There's only two types of cards, King and Queen, and there's 50% King cards, 50% Queen cards, King is better than Queen.
Okay, so player one Alice, we begin the game.
The card is dealt at random to Alice, and she gets to see whether it's a King or a Queen.
Bob, whose player two does not observe the card, that's very important.
So the second thing is that Alice then gets a decision.
She has to choose either the bet, action, or fold action.
If she chooses to fold, obviously she loses, and Bob wins what's in the pot.
If she chooses to bet, then she'll add another $1 to the pot.
Now, of course, she could be betting on the King, which would be a genuine, you know, she's betting on the King,
or she could be bluffing because she's betting on the Queen.
So if Alice did bet, Bob then gets an action decision.
He then either calls or folds.
Of course, again, if he folds, then Alice wins and the game ends.
If he chooses to call, then he's adding his $1 to the pot.
And then if he got to that point where he's called Alice's race, then if Alice had the King, then she's the winner.
But if it was the Queen and she was bluffing, then Bob's the winner.
Okay, so see how we can model that simple game with Pygambit code.
Can everyone read the code?
Alright, so I'm big enough.
I'm seeing knots.
Okay, good.
Okay, so the first thing we're going to do is create the game object in Pygambit.
So very simply, we're going to run Game Neutree.
We've added our players, Alice and Bob, given it title.
And the important thing to note straight away is that when we print the list of players here,
there's actually three players.
So we've got Alice involved, the players that we've created.
But we've also got this chance player.
And this is how Gambit models the element of chance.
See, model it as a chance player.
And that what that actually means is that the very first action in the game,
which we can create by using this append move function.
We're going to append it to the root node of the game, which is all we have so far.
But the player that we're going to set it to is the chance player.
So the first action of the game, we're going to append to the chance player.
And essentially, it's going to be either a king or a queen because that's what's being dealt from the deck of cards.
Each of those is going to be with probability 50% one half.
And then we get the start of our game tree, which is very simply like this.
But the start of the game, and then after either that king or queen was dealt,
we've now got two new nodes in our Gambit game object.
Okay, so how do we then add Alice player ones moves to the game?
So in this case, what we're going to do is iterate through the children of the root nodes,
which are these two we've just constructed.
And we're going to add our actions of betting fold.
And we're going to do that for both of those.
And if we do that now, you can see that we've independently for each of those child nodes of the root node added Alice's actions.
So that's important as we'll come to see that those are two distinct what we call in game theory information sets.
And this is different when we come to Bob player two.
Because if you remember earlier, we said that Bob doesn't know what card was dealt at the start of the game.
So in this case, we're going to call the append move function again.
But instead of looping through each of the nodes, we're just going to call it once and pass in a list of the two nodes to apply it to.
So when we do this, we generate what looks the set almost the same.
But instead, we've got the two nodes at which Bob has to make a decision circled.
And what that is called is in game theory as an information set.
It basically tells us that when Bob is making a decision, he doesn't know whether he's here or here.
He doesn't know whether the king or queen was dealt.
All he knows is that Alice has bet.
Okay.
So the final step of constructing our game is that we need to add outcomes to all of the terminal nodes of the game.
So there are four possible outcomes that we have in our game.
The first one, which we're labeling from Alice's perspective, player one, is the big win, where she's got two dollars and Bob has lost two.
And there's another option where she's just one with one dollar.
And then she can also lose two and lose just one.
So we can add all of them with the add outcome.
But then we also need to assign all of those outcomes to the terminal nodes in the game tree,
which if we look at the tree, there's actually six of them not just four.
So there's four different fold nodes and those two others.
So we assign each of those outcomes to their appropriate terminal nodes.
And look at our final game.
We've got our stripped poker that's stripped down poker game models entirely.
So that's how you construct a game in pie gambit.
I'll also just mention this package here, draw tree that we've developed.
So for the software engineers in the room, basically under the hoods, this is generating latex code,
and specifically tick graphics, which is a submodular of latex.
And even more specifically it's using the Jupiter ticks widget to render this nicely.
OK, but back to understanding this game and what pie gambit can do.
So as I mentioned, the other thing as well as constructing games that pie gambit does is it solves them.
So what does that mean?
It means we can compute the Nash equilibria to remind you what that is.
So equilibria are stable situations where no player has an incentive to deviate their strategy that they play.
So gambit has a range of algorithms to do this.
I'm just going to show one of them here, which is the LCP solve, which is a linear complementarity problem algorithm.
And we can just call that in one line of code, and we've got the answer.
OK, but it gives you back this Nash computation result object, which is a bit hard to understand.
So let's take a little look at what's actually going on here.
If we look at the equilibria of the result, we can see that there's just one that was found for this simple game.
And if we look at index the equilibria, the equilibria part of the result object, what we get is something called a mix behavior.
So what's a mix behavior? A mix behavior profile basically tells us for each information set the probability distribution over actions of the information set.
So that's probably quite hard to understand, so I'll try and illustrate that a bit more clearly.
If we look at the mix behavior for Alice, player one, what we've got here is one zero and then one third, two thirds.
OK, so what does that mean? So I'm just going to run through some code here that's explained that a bit more clearly.
Basically at the first information set, which we'll call information set zero, Alice plays bets with the probability one, Alice plays fold with probability zero.
At the second information set Alice plays bet with probability one third and fold with probability two thirds.
That's what this means, and to explain that even more, if you think about it, this is the scenario where the king was dealt.
So essentially, her strategy, according to the equilibria, is when she's got the king, is always bet.
When she's dealt the queen, she's going to bluff one third at the time, and she's going to fold two thirds at the time.
So that's what that means, and that's how you can explore the strategy that was given to the first player, according to this equilibria that gambits computed.
If we now look at player two, Bob, we can see he only has one information set as you remember earlier, so he's always going to play.
He's always going to play call with probability two thirds and fold with probability one third.
So that's his strategy. He has no incentive to deviate from according to this equilibria that gambit has calculated for this particular game.
Okay, cool. So that's how you can construct a game with pygambit and also compete in the equilibria.
I'm going to show a little bit now about interoperability with this other package called OpenSphere, which is a python package developed by, I guess python and c++ package developed by DeepMind.
We're going to use the same game again, let's begin with, but yeah, so this package is developed by DeepMind, it's also used for game theory.
So we can very easily load our game that we defined in pygambit in pygspile.
And what this allows us to do, maybe after zoom out a little bit to get it all on screen, is it allows us to step through the game.
So where gambit allowed us to construct the game in compute equilibria, OpenSphere is a package that's all used for reinforcement learning and other kinds of ways of iteratively playing games.
And so it has this idea of a game state, so we can start with our initial game state and then all that this code is doing is sort of iterating through the game.
And it's saying, if it's a chance node, so remember from our game, the very first action is taken by the chance player, it's just going to pick the king or the queen according to the probabilities.
And for everything else after that, it's just going to pick up random one of the possible actions.
So I ran that code and we've got the simulation of the game here.
A queen was dealt, Alice picked fold and the game ended with Alice losing.
If we run it again, let's try and get a different answer.
Maybe we'll get, yeah, there we go. We'll get the king was dealt, Alice stupidly folded, which is not what she would have done if she was playing the equilibrium strategy we looked at earlier.
But yeah, that's just the way you can, so with OpenSphere, you can just step through the game that way and simulate pay threes.
This is important because unlike Gambit where what you're doing is just defining a game and then computing the equilibrium for much larger games where that comes computationally intractable.
You can use OpenSphere to do things like reinforcement learning agents to learn strategies through self play.
So player strategies can change over time as these games are played and you may eventually really reach an equilibrium.
So what I'm going to try and do, I think we've got time, I've not seen any time science come up.
I'm not paying attention to anything.
Okay.
Well everyone's riveted, so we'll carry on.
So I'm going to demonstrate sort of, yeah, as I mentioned, OpenSphere would be used for a much larger games.
But I'm going to demonstrate how you might iteratively get to an equilibrium that could be via OpenSphere.
It looks similar to what you were getting gambit.
So to do that, I'm going to load a much an even simpler game, which is from the PiSphere library matrix RPS,
that's literally rock paper scissors. So in gambit, that literally looks like this.
What we were looking at previously was an extensive form tree game.
Now we're looking at a normal form table game.
This is not very hard to understand.
If you have player one player's rock against rock, it's a draw.
If they play rock against paper, they lose, and yeah, it's very simple to understand.
Hopefully you'll know rock paper scissors.
So again, we can simulate a play through with OpenSphere by setting the states and then simply doing one, a Pi actions with player one playing zero,
which is a player one, a player two playing one, which is paper and player one, the second player wins.
Okay, so if we plug that game into gambit's LCP solve, very intuitively, the equilibrium strategy that it finds for both players is that they're both going to play exactly one-thirds rock paper and scissors.
Okay, makes sense, right?
So let's now look at OpenSphere's replicated dynamics module to model how player strategies are the choice of rock paper scissors,
with probabilities, x, y, or z, can evolve over time based on how they perform once against one another.
And we can see how they will converge on the very same equilibrium that gambit competed.
So to simulate this, I'm going to start with a situation where both players are playing a strategy of rock 30% at the time, paper 30% of the time, scissors 40% of the time.
So ignore this plotting code, but very simply, if we start with both players playing rock and paper 30% and sorry, yeah, and scissors 40% what you can see is that playing rock becomes a good strategy,
because the other player is playing scissors more often.
And so over time steps obviously rock becomes more chosen more often as the players change their strategies to respond to the rewards that they're getting.
And as it becomes really popular, what that means is that paper becomes actually a better strategy, because the other player is choosing rock most often.
And so that is the chosen strategy that goes up in frequency.
And then what you get is that oscillation over time.
It's all around this one third, which is the equilibria, but it never quite meets it.
But if we simply just plot the average over time, what you see is that clearly we are approximating that equilibrium.
Anyway, that was just a fun way of showing that these two packages are interoperable and how with a very simple game.
You can use this iterative approach to come to the same conclusions you might have done with gambit.
And if we plug in our actual equilibria, the strategies never deviates.
Okay.
So that was a very brief introduction to pygambit and some associated packages.
So it is an open source project, otherwise wouldn't be here.
And new contributors are welcome.
Please do check out our website, which has links to documentation, where you can find all of that information.
Just a little bit about the project and what's coming next.
So there's a lot of work that I've done sort of this year in updating the project documentation for gambit.
There's a bunch of nice tutorials online from which this material has been derived.
But there's going to be more of that.
A lot of the postdocs that I work with who are the proper game theory people, not software engineers like me.
They've been working on increasing the algorithmic efficiency of some of those national computation algorithms that you can see listed here.
We're going to carry on working on this interfacing with other tools in the scientific computing ecosystem.
And a big feature that we're working on at the moment is just making a nice library or catalog of games.
So there's plenty of examples that users can easily load when they start using the package.
And so that's all I'll take any questions. Thank you.
Yes.
How do you know if I can put some thought to the game in a bit of a time frame?
How do you know the question was how do you know Pygambit can solve the game in a reasonable time frame?
That's a good question. I don't know the answer to that. I think the best answer would be as a user would be to just give things a try.
But those of the people I work with who are the experts in all of these algorithms certainly themselves have recognized plenty of inefficiencies.
And that's why I mentioned one of the things that they're working on at the moment is trying to make you know improve the performance as much as possible.
But yeah, I think the only answer can give us try stuff.
Certainly another thing I'll mention is that part of the reason that I talked about this interoperability with OpenSpile is one thing that people have noticed is that these algorithms fall down for like really large games.
What do I mean by really large games? I'm not particularly what I mean by that.
But some of the people I worked with did a project on generating games through prompting LLMs.
And so they came up with some very big complicated games which could be the LLMs or co-generation LMs and they were able to output Pygambit code that could construct a game.
And that wasn't difficult, but of course with some of those really large games that came out of our projects.
These algorithms fell down, so that is an ongoing area of research.
What is the key for real use case scenario for example in economics?
Yeah, you're also not the domain expert on this.
Yeah, I mean the example I have is not for economics, but from war gaming, but that's one of the other.
It's not a concrete example. I'm just saying another field.
So there's also some of my colleagues are working on sort of combined traditional game theory and reinforcement learning strategies for modeling cyber attacks.
And attack a defender scenarios, so that's another big area of research at the moment.
But yeah, I can't give you a list of papers, but hopefully that is one thing that by visiting the Gambit website, it'll be us find out.
Okay. Cool.
Thank you.
Thank you very much.