Combinatorial game theory

Reading time15 min

In brief

Article summary

In this article, we present you some elements of “game theory”. This branch of mathematics studies strategies, and has many applications in fields such as optimization, politics, or economy.

Main takeaways

  • Game theory represent a game in an abstract space of configurations.

  • A strategy consists in a function that explains which next configuration to reach, given the current game configuration.

  • There exist mathematical results on games, such as von Neumann’s theorem.

  • These results apply to many real-life fields.

Article contents

1 — Video

Please check the video below. You can also read the transcripts if you prefer.

Information

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.

Context

Games play an important role in many domains of science. Games are widely used in economics and mathematics, but also have applications in cryptography where, typically, the goal of a game is to protect pieces of information, as well as in operating systems where the goal of the game is typically to prevent errors, or in artificial intelligence.

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!

Basic definitions

Recall that we would like to play a game in a maze where two players, a rat and a python, are trying to grab all the pieces of cheese before their opponent.

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.

For example, there's an initial vertex that corresponds to the initial configuration where both the rat and the python have score 0 and are at their starting positions, and all pieces of cheese are spread throughout the maze. Then there's also vertices corresponding to all possible configurations that might occur during a game of PyRat. Vertices are connected by edges that are labelled according to two variables. The first variable corresponds to the decision made by the rat and the second variable to the decision made by the python.

Are you ready for an example? Let's consider a simple game where a 3 by 3 maze contains a single piece of cheese at the center and the rat and python are both competing for it. From the initial configuration several things could happen. The rat can move right, up, or not at all, and the python can move left, down, or not at all. We thus have 3 times 3, so 9, configurations that can be reached from the initial configuration.

Here is what happens if the rat moves up and the python moves left. Here is what happens if the rat moves up and the python stays still. Here is what happens if the rat moves up and the python moves down. Here is what happens if the rat moves right and the python moves left. Here is what happens if the rat moves right and the python stays still. Here is what happens if the rat moves right and the python moves down. Here is what happens if the rat stays still and the python moves left. Here is what happens if the rat stays still and the python moves down. And finally, here is what happens if both the rat and the python stay still.

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.

A "strategy" of a player is a function that associates each vertex in the arena, which can also be described as each state of the game, with a move for that player.

One example of a strategy is a greedy algorithm which involves systematically going to the nearest piece of cheese in the maze. Once the two players have chosen their strategies, the game can be entirely known and the winner can be identified by letting the game of PyRat play out.

As such, a play can be seen as a walk in the arena, depending on the two chosen strategies.

Concluding words

So, that’s all from me! In the next lesson, Patrick will show you how to compute good strategies.

To go further

2 — von Neumann’s minimax theorem

2.1 — Catergories of games

There are multiple categories of games, according to whether players play simultaneously (e.g., rock-paper-scissors) 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.

2.2 — The theorem

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.

To go beyond