Upcoming talks and demos:

Codemotion - Amsterdam - 16 May
DevDays - Vilnius - 17 May
Strata - London - 22 May

View Natalino Busa's profile on LinkedIn
Principal Data Scientist, Director for Data Science, AI, Big Data Technologies. O’Reilly author on distributed computing and machine learning. ​

Natalino leads the definition, design and implementation of data-driven financial and telecom applications. He has previously served as Enterprise Data Architect at ING in the Netherlands, focusing on fraud prevention/detection, SoC, cybersecurity, customer experience, and core banking processes.

​Prior to that, he had worked as senior researcher at Philips Research Laboratories in the Netherlands, on the topics of system-on-a-chip architectures, distributed computing and compilers. All-round Technology Manager, Product Developer, and Innovator with 15+ years track record in research, development and management of distributed architectures, scalable services and data-driven applications.

Friday, January 25, 2013

Markov chains for Ladders and Snakes


Snakes and Ladders, also called chutes and ladders comes from in India. Its older version called Moksha Patam, was about fate, the bummers and happy turns in life.

A special version of the Moksha Patam dates to the 16th century. This sort of games are very close to the Hindi teachings about doing well in life and about the faith mostly unavoidable which can potentially set you back in your aspiration to ascend. The underlying ideals of the Moksha Patam were transformed into a victorian board game around the 1892. That was the origin of what today we call Snakes and Ladders.

From wikipedia:
The morality lesson of the game was that a person can attain salvation (Moksha) through doing good, whereas by doing evil one will inherit rebirth to lower forms of life. The number of ladders was less than the number of snakes as a reminder that a path of good is much more difficult to tread than a path of sins. Presumably the number "100" represented Moksha (salvation).

In the original game the squares of virtue are: Faith (12), Reliability (51), Generosity (57), Knowledge (76), and Asceticism (78). The squares of vice or evil are: Disobedience (41), Vanity (44), Vulgarity (49), Theft (52), Lying (58), Drunkenness (62), Debt (69), Rage (84), Greed (92), Pride (95), Murder (73), and Lust (99).

The game

So what makes one board design a slower or faster game then the other? Is it possible that by adding a snake you might actualy end the game earlier. How long does a game last?

These are all questions which pop up after playing the game a few times. Is there a way to understand what is the outcome of the game, without playing the game, but just looking at its configuration of ladders and snakes? That's where maths come to the rescue.


I have fiddled out a quick simulator in javascript to let you play and design your own board game. Just add any special field by specifying where the special position leads to. Remember that 0 is the start position and 100 is the finish of the board game. If you don't enter any special position you will have the chance distribution of the fair game. Try to see what happens if you send back the players to the beginning when the fall on a the position before the end, by adding "on position 62  go to 0". Enjoy

Doing the maths

A board game can be see as a markov chain, where the probability of moving to the next spot depends only on the position you are currently at and the chances provided by tossing a dice.

For example, if you are on the third position in the board, and you roll a single 6-face dice, you might end up on the fourth position up to the nineth position. The chance to end up on any of this positions is 1/6. This can be expressed by this equation:

where i is the position I am currently at, j is the position I will reach after throwing the dice, and k in our case is an invariant, since the board game rules are always the same at any turn (you don't modify the board while you play on it).

Now, let's assume that the board has say 101 positions, where 0 is the start (out of the board), and 100 is the finish. Let's start easy and assume for the moment that there are no special positions in the game. Let's call this game the null game.

The probability pi,j for the first dice roll are:
p0,1 = 1/6 , p0,2 = 1/6 , p0,3 = 1/6, p0,4 = 1/6, p0,5 = 1/6, p0,6 = 1/6

p0,j = 0 for j =0, and for j>6

In general, since we always have to throw, we will always go on.
pii = 0 for every 0<= i <100

The only exception to this rule is p100,100 = 1

This means that you might keep throwing the dice, but nothing would happen since you reach the finish, so you stay in the finish. For common mortals this means you have won the game, for mathematicians it means that 63 is a persistant or recurrent position in the markov chain.

If we don't have any special spots is also impossible to go backward:
pij = 0 for every j <= i

Analysys of the null game

Firstly, let's analyze the null game. That would be a game with no snakes and no ladders. This will allow us to define the markov chain in the case of a single dice. In the null game there are no special positions with respects to dice rolls.

If we all start from "start" (position zero), what is the probability to get to the finish after 1,3, 20, 100 rolls of the dice? This is the arcane that every consumed player would like to know and where the maths ultimately boils down.

First of all we need to know the full matrix of P = {pij with 0<= i,j <100 }
  • p100,100 = 1
  • pij = 0 for every 0<= j <= i  < 100
  • pij = 1/6 for every 1 <= j - i  <= 6 and i<=100-6
  • pi,100 = i-(100-6)/6 for every 1 <= j - i  <= 6 and 100-6< i<100

If the state space is finite, the transition probability distribution can be represented by a matrix, called the transition matrix, with the (i, j)th element of P equal to :

Since each row of P sums to one and all elements are non-negative, P is a right stochastic matrix.

Intuitively, in our case, after 100 rolls you will always get to the finish. Also it's impossible to get there in less than ceil(100/6) = 17  rolls. But what about the general formula? For time-invariant markov chains such as board games this is expressed by the  marginal distribution Pr(Xn = x) is the distribution over states at time n. The initial distribution is Pr(X0 = x). The evolution of the process through one time step is described by :

In particular, since we always start from the start (no cheating there eheheh), our distribution at step 0 (before rolling any dice) is a vector [1, 0, ... 0] , hence the distribution at step k can be represented by:

X = X P=  [1, 0, ... 0] PP0 j  

... i.e. the first row of the power k of the right stochastic matrix.

Thanks to Kolmogorov, we know now that the chance distribution at the step k in the game is provided simply by calculating the power of the stocastic matrix and then taking the first row.

The vector [0,0, ... , 1] is a stable chance distribution for this given game when k approaches infinity. It means that after rolling the dice really a lot of times, and supposing that there are no special positions you will and up at the finish position (duh). Therefore the stable distribution, after many many rolls, is that you will be with a probability of 1 at the finish, and with probability 0 anywhere else. In formula:

For our game, given the way we have constrcuted P, this implies that pi = [0, ....., 0, 1] is an eigenvector for the eigenvalue 1 of the stocastic matrix Pwhen k approaches infinity.

Some results of the null game

Let's start by the first question:
How does the probability distribution look like after k dice throws?

Intuitively, after the first throw you have equal chance to end up on position 1,2,3,4,5,6 and this chance is 1/6. But the chance of ending up on position 10 on the third roll are more complex. I can roll 2, then again 2, and then 6, or 2, then 5, then 3. And so on. So basically the chance of being on a certain position after k rolls start to spread as the number of dice rolls increase.

chance of being on a certain position after k rolls
Each color displays the chance at a given turn of dice throwing.

You can see that the peak is moving on. It means that after a number of dice rolls you get closer to the end. Also not all the positions are equal. At each throw, the chance are higher that you will find yourself in a position close to the peak of the k-th curve.

Also interesting to note that the more you throw the more the probability chance curve spreads across a wider number of positions.

What about the end position?
Chance of reaching the end position after k rolls
As you can see the end position can be reached in at least 17 moves. However there is just about one chance in 6 to the power of 17 that this will happen. Also, there is a very high probability (0.91) that you will finish in less than 35 rolls. Moreover, there is a very very tiny chance that you will throw 1, for 100 times in a row. Now, these are interesting results, I would say.

What about the cumulative chance of being at position 'n' during a whole game?

We are interested in understanding how probabile is to transit on a given position on the board during the entire game. This is the cumulative marginal distribution of the chance over the position on the board 'j'.

Since the game is fair, it is not possible to go backwards or to stay on the same position hence:

However the last formula hides a catch. It assumes that the events are all independent. It means that the chance of being at position j after say 10 rolls does not depend from the fact that we reached position j at the 7th roll. Is it true? In formula, can we demonstrate that:

In the fair game, the probability of being at position j after k rolls given the fact that we reach position j after h rolls,  can be broken down according to the following:

when h<k, 
then the probability after k rolls is zero, given that we have already passed the position j at roll h<k and we cannot go backwards

when k>h, 
then the probability ofter k rolls is zero, given that we will pass at position j at roll h>k and we can't stay on the same position during two different rolls.

Since the events are independent, the union of the probabilities, is the sum of the marginal probability of being at position j after 0, 1, 2, 3 ... k rolls.

Total chance of being at position 'n' during a whole game
In the fair game, there is a peak at position 6, and a small dip at the 7th after that we can conclude that the chance of being at a given position during the game is about 28%.

Already this information is quite interesting, if I would introduce a special position, say "go back to the start", there is about one chance out of four that you might fall there. If you would play this game with four people, definitely there is a quite high chance that somebody is bound to go back to the start.

Things get more interesting if the game is not fair and you introduce special spots. In this case, the cumulative chance cannot be calculated just but adding up the marginal distributing at each roll, because events can be correlated. Intuitively, this is due to the fact that you create jumps forward or backwards, potentially adding loops or multiple paths to a given position.

However, if the amount of special positions is limited, the chance distributions decay quite quickly and the correlations could still be neglected. For a formal definition of this phenomenon check the inclusion-exclusion principle wikipedia:inclusion-exclusion principle  and Boole's inequality wikipedia:boole-inequality.

Python coding:

If you prefer Python, I have written down a snippet using numpy and matplotlib.


board game image: http://www.flickr.com/photos/bibliodyssey/
formula's and mathematics: http://en.wikipedia.org/wiki/Markov_chain