,Hello everyone, my name is Lev Kobelev, I am a Game Designer at MY.GAMES. Advanced knowledge of mathematics is rarely considered strictly necessary for game designers — or, if it is required, school level is enough. And that’s true in most cases. But sometimes, knowing certain concepts and methods from advanced mathematics can make life easier and help you look at some problems from a different angle.
In this article, we’ll analyze two mathematical concepts: Markov chains and random walks. I’ll note upfront that this article is more «popular» than «scientific», so, some things about how the formulas are derived will be omitted.
After the theory, we’ll discuss example cases where these tools might come in handy, for example:
The number of chests the player will open if more chests can come out of the chests
The amount of gold to be spent pumping up a sword, if the sword can break
The probability of winning a cash match
Alchemist’s problem
First up, let’s imagine a game where we play as an Alchemist. Our task is collecting ingredients for a new potion:
Ingredient | Location |
|---|---|
Grassweed | Chess Field |
River Meteorites | Space River |
Seirreb | Troll’s Loo |
The unique thing about this: roads between our locations can lead us to multiple, randomly selected, destinations.
We’ll denote the roads as follows: (location A → location B: the probability of moving from location A to location B):
House → Chess Field: 0.8
House → Troll's Loo: 0.2
Chess field → House: 0.5
Chess Field → Troll's Loo: 0.3
Chess Field → Space River: 0.2
Troll's Loo → House: 0.5
Troll Loo → Chess Field: 0.2
Troll Loo → Space River: 0.3
Space River → Chess Field: 0.5
Space River → Space River: 0.5
Please note: the sum of all destination probabilities from each location equals 1. If the sum is less than 1, then the difference is the probability of transition from A to A. And if it’s more, something definitely went wrong.
The Alchemist goes to get the ingredients. The question: what is the probability that, after two moves, he’ll be at Space River?
There are two possible paths to the river, consisting of two moves:
House → Chess Field → Space River: 0.8 ⋅ 0.2 = 0.16
House → Troll’s Loo → Space River: 0.2 ⋅ 0.3 = 0.06
So, the probability the alchemist will be at the River is 0.22.
Okay, what if we want to know the probability he’ll be at his house after 10 moves? After 100? This takes a lot of calculation, and that’s where Markov chains come to the rescue!
Markov chains
Let’s introduce the following symbols:
S is a finite multitude of states. In our case, this is a multitude of locations: {House, Chess Field, Troll's Loo, Space River}.
Xi is the state after the i-th transition, Xi ∈ S.
Move is a change of state Xi to Xi+1 with a given probability.
Stochastic process is a set of states {X0 , X1 , X
