Snakes & Ladders revisited

Snakes & Ladders is one of the popular board games. Just for fun, I have tried revisiting this game from a math perspective.

There are many variations of the game where each variation differs from the other in terms of the position of ladders and snakes. I picked this specific version from this wiki

Blurb from Wikipedia

Snakes and Ladders (or Chutes and Ladders) is an ancient Indian board game regarded today as a worldwide classic. It is played between two or more players on a game board having numbered, gridded squares. A number of “ladders” and “snakes” (or “chutes”) are pictured on the board, each connecting two specific board squares. The object of the game is to navigate one’s game piece from the start (bottom square) to the finish (top square), helped or hindered by ladders and snakes, respectively. The historic version had root in morality lessons, where a player’s progression up the board represented a life journey complicated by virtues (ladders) and vices (snakes).

In the above arrangement, there are a few interesting questions that one can explore ?

Given a player is in a particular square, what is the average number of steps that one needs to complete the game ?
Given a player is in a particular square, what is 1 sigma deviation of the above estimate?
The game is complete if the player lands in square 80 or square 100. What is the probability that a player lands up in Square 80 and completes the game ? What is the probability that a player lands up in Square 100 and completes the game ?
Assuming a tweak that makes the game never ending, i.e , if there is a snake at 100 that brings back the player to square 1, what is the second most probable state that he would be visiting ? First most probably state is obvious(38).

One quick and dirty way is to simulate a large number of path through the game and find an estimate for each of the above questions from the simulations. Nothing wrong with it, but in this context where all the probabilities are fixed, an elegant way to look at this problem is via “Markov Chains”.

How does one think about this problem ?

Imagine the player as a random variable indexed by time that moves along the board. Assume each of the square is in the state space of the player. In the above arrangement, the game is designed to end. In the Markovian world, these type of random variable chains are called “Absorbing Markov chain”. In our game, there are two states where the chain can get absorbed, “Square 80” and “Square 100”. So, firstly it makes sense to classify the states in to absorbing and transient states(transient meaning, the probability that eventually the player will leave that state). Also there are square that are merely placeholders, i.e the random variable never stays in such squares. As soon as the player hits those square he is transported to a different square. These are the squares at the head of the snake or start of the ladder. So, one can conveniently ignore such squares.

So, there are 2 absorbing states 80 and 100( green colored squares) , there are about 16 redundant states(black colored states). So that leaves 84 states in total where a player can be present(including 0)

One can represent the moves in the form of a transition probability matrix. In the matrix below, one can see that the states S100 and S80 have been set as absorbing states. This arrangement is useful as one can focus on the rest of the matrix. There is a ladder from 80 to 100 , but there is no difference if you assume that the square 80 is itself a separate absorbing state.

Reconfiguring the transition matrix entails placing the states in a convenient arrangement like the one shown above. Once the transition matrix is reconfigured, many interesting questions can be explored like the ones that were mentioned at the start of the post. Let’s look at them one by one

1. Given a player is in a particular square, what is the average number of steps that one needs to complete the game ?

Using the Q matrix , i.e the submatrix that is relevant to the transition states, one can easily compute the average number of steps to complete the game from various squares. The following visual gives the result. Each of the square is populated with the average number of steps needed to get absorbed.

2. Given a player is in a particular square, what is 1 sigma deviation of the above estimate?

Obviously such point estimates need to be accompanied with some sense of “how variable are these estimates”. The variance assoc iated with these steps is pretty high. The following visual gives the 1 sigma level for the above estimated values.

As one can see , the estimates have a considerable variation. The following summarizes it better

In the above visuals, the metrics for a player starting at 0 is not mentioned. It can be found that Player starting from 0 will take an average of 32 steps to finish the game with a standard deviation of 19.6 steps.

3. The game is complete if the player lands in square 80 or square 100. What is the probability that a player lands up in Square 80 and completes the game ? What is the probability that a player lands up in Square 100 and completes the game ?

Well, to answer this question, one needs to focus on the submatrix R. This submatrix summarizes the world where the chain moves from transient states to absorbing states.

Using the submatrix R, one can compute the probability of getting absorbed in to state 80 or state 100. The following visual gives the results:

Thus the probability of getting absorbed in to state 80 is about 45%-50% and goes up as it the player nears 80. Subsequently the probability of absorption in to State 80 goes to 0 and State 100 approaches 1.

4. Assuming a tweak that makes the game never ending, i.e , if there is a snake at 100 that brings back the player to square 1, what is the second most probable state that he would be visiting ? First most probably state is obvious(38).

This is an interesting question. In the earlier arrangement where the chain is an absorbing chain, there is nothing like steady state distribution of the player.The player always lands up at 100 at some point time , so the probability that he stays in a transient state approaches 0. If the game the modified like the one shown below, then one can think of a steady state distribution for the player.

This extra snake at 100 makes the chain in to a recurrent chain, i.e the player keeps revisiting various states and the chain never gets stuck in a specific state. In this tweaked version, it is obvious that the most probable square is 38. What is the second most probable state ? What is the third most probable state ? To answer such questions, one convenient way is the multiply the transition matrix by itself some n number of times and read off any row of the resulting matrix. However an elegant way to do is to look at it from its left eigen vectors and right eigen vectors. Computing the steady state distribution of this chain involves computing the left eigen vector for the transition matrix. There are many ways to do it. Perhaps a quick way is to compute the right eigen vector of the transpose of the transition matrix.

In any case, all we are trying to do is to find the steady state vector pi that satisfies the following equation.

where P is the transition probability matrix. Here is a visual that summarizes the steady state distribution

A much better way to see the steady state distribution is via a heat map

In each the squares numbered, the value represents the steady state probability, i.e, the proportion of times that a player stays in a particular square in his never ending path through this game. As one can see , the square 38 is the one with highest probability. The second likely square that player goes is Square 67 and the third likely square is Square 79.

There are tons of other things that one can explore with this simple game of “Snakes and Ladders”. But let me stop now and get back to work.