It’s me again! Welcome, I’m so glad to see you again. Let’s start with some background about game theory.
Game theory is the domain of science interested in studying games, strategies, and winning conditions.
Games are a very adapted framework for our game in the maze, and a great excuse to investigate advanced algorithms.
If you manage to code a program that computes winning positions in a game, you’ll be ready for just about any programming challenge!
During the game, these players can make simultaneous decisions. For example, the python can decide to move left while the rat decides to move up.
To describe a game, we use a very specific graph that we call the « arena ». The arena is a graph where each vertex summarizes the actual state of game. By state of the game, we mean the positions of the players, the positions of remaining pieces of cheese, and the score for each player.
There are several vertices in the arena corresponding to the end of the game, when the rat or the python reaches the central position that contains the cheese. The first player to reach this position will be the winner.
As such, a play can be seen as a walk in the arena, depending on the two chosen strategies.
So, that’s all from me! In the next lesson, Patrick will show you how to compute good strategies.
Von Neumann’s minimax theorem
There are multiple categories of games, according to whether players play simultaneously (e.g., rock-paper-scissors-Spock-lizard) or not (e.g., chess), if players can hide some information (e.g., poker), etc.
In the case of PyRat, we consider a game which is simultaneous. It means that both player take decisions at the same time. This is the case in a normal game of PyRat, as moves are applied at a fixed period.
PyRat is also a game with perfect information, as all information on the board, all possible decisions that can be taken (and the gains that would result), as well as the game objective, are known by all players.
Also the game is non-cooperative, as each player is trying to win against the other.
Additionally, PyRat is a zero-sum game, as one piece of cheese taken by the player will not be taken by the opponent.
Finally, PyRat admits a finite number of pure strategies, as the number of possible decisions per arena vertex is an integer. A pure strategy is a complete definition of how a player will play a game. In particular, it determines the move a player will make for any situation they could face. When a strategy assigns probabilities to each decision, we talk about mixed stragey.
John Von Neumann’s minimax theorem is an important result in game theory. In a non-cooperative, simultaneous game with perfect information, with a finite number of pure strategies and zero-sum, the theorem states that there is at least one situation of stable interaction, namely a situation in which neither of the two players has an interest in changing its mixed strategy if the other does not change it.
In other words, what the theorem says is that there exists a situation in which both players should stabilize, as changing the strategy would not improve the gains as long as the opponent does not also change strategy.