Winning at Snakes and Ladders

Winning at Snakes and Ladders

The fantastic Marcus de Sautoy has just made a video on how to use Markov chains to work out how long it will take to win at Snakes and Ladders.  This uses a different method to those I’ve explored before (Playing Games with Markov Chains) so it’s well worth looking at in more detail.  

The game

This simplified version of Snakes and Ladders will have 9 squares, one ladder and one snake.  Contestants will roll one dice and then advance that number of squares.  If contestants land on a snake they fall to the bottom and if they land on a ladder they climb to the top.  Contestants have to roll an exact number to reach the 9th square (and win) – otherwise they remain where they are.

The board

This is the board that we will use.  The 0 symbolises the fact that players are not on the board before they roll a dice for the first time.  We can see that for this game it is not possible to remain on squares 4 or 8 (anyone landing on square 4 will be transported to square 7 and anyone landing on square 8 will slide down to square 2).

7 by 7 matrix

We can then create a 7 by 7 matrix as follows:

The first row will show the probabilities of landing on different squares when starting at 0.  The second row will show the probabilities of landing on different squares if starting at 1.

We can now start to fill in this matrix.  When we start at 0, then we are equally likely to land on 1,2,3,5,6,7 but it is impossible to remain on 0 and so we can fill in this row with:

Next we can consider what happens when we start at 1.  It’s impossible to go to 0, it’s also impossible to remain on 1, and this time there is a 2/6 chance of landing on 7 (either by rolling a 6 or rolling a 3 and climbing the ladder).  This gives:

We can carry on with this method to fill in the rest of the matrix.  We can note that once we get to starting on square 3 and above we can land on square 9 and hence win.  We don’t need to record these probabilities.  For example when we start on 3, there is a 1/6 chance of winning by rolling a 6 and therefore landing on 9.

We can also note that when we get to 5 or above it is possible that we remain where we are.  If you are on 5 and roll a 5 or 6 this will take you beyond 9, and so in the rules of our game you will remain on 5.

If we take all this into account we get the following matrix:

Now in our previous exploration on Markov chains, we could simply take this matrix to a high power to see the steady state probabilities, which will tell us the long term probabilities for being on each location.  However if we do this here we get the 0 matrix.  This is because as we play the game a long time we no longer would expect to be at any of the squares 0-8, because we would expect to have won the game (and hence be on square 9).

Finding the expected number of throws until we reach square 9.  

If we call the matrix above Q, then Q tells us the probability of being on any square after 1 roll.  Q squared would then tell us the probability of being on any square after 2 rolls etc.  So if we do the following calculation:

This will add up all the likelihoods of being on any given square after 0 throws (the identity matrix), after 1 roll (Q) after 2 rolls (Q squared) etc.  Adding this infinite sum together serves as providing us with our expectation of how many throws we will spend on each square.

Adding this sum gives:

We can treat this like a sum to infinity – but with matrices.  Here the sum to infinity formula has the identity matrix I rather than 1 in the denominator because I is the equivalent of the multiplicative identity 1 in regular arithmetic.  The video talks through a similar method.  This is then equivalent to: 

which now requires that we find the inverse of this matrix.  We can do this by using our GDC on the following problem:

This gives the following matrix (first row shown).

We can then look at the first row to see how many rolls we are likely to spend on each of the different squares when starting on 0 (the start of our game).  This shows that for example we would expect to spend 3.54 rolls on square 7.  We can think of time spent as counting before the roll – hence there is a value of 1 for the 0 square (we spend 1 go there as we roll). 

If we then add the values in this row, this must be the total expected time we would expect to be on one of these squares before we finally reach square 9.  Adding this up gives 8.6.  So we would expect to finally reach 9 after 8.6 goes.  (Note that the video has a mistake in it and incorrectly gives the answer of 10).

So – a very nice method of working out expected roll times by using matrices! 

Python code

We can also use the Monte Carlo method to use some Python code to simulate this, to see if this does indeed agree with our prediction.  This involves writing some code to play the game thousands of times to find an average.  Let’s see what this would look like:

This is a rudimentary Python code which I made to do the job.  It’s set to play the game just under 10,000 times and then calculate the average winning length.  When I run it I get the following:

This pleasingly agrees with our matrices method!  Let’s give the computer processors a bit more of a test and make it play the game 10,000,000 times.  This time we get:

Yes – this does look like it’s converging towards 8.6.  

Extension ideas?

This game could be changed so that when you roll beyond the 9 square, you “bounce back” – i.e if you are on 7 and roll a 3, then you go two squares to 9 then bounce back to 8.  Changing the Python code for this game now gives an expected length of approximately 9.7.