Analysing Snakes and Ladders as a Markov Chain

Question

The game of Snakes and Ladders is a good candidate for analysis with a Markov Chain because of its memorylessness: at a given point in the game, the player's progression from the current square is independent of how they arrived at that square.

In Markov Chain theory, the probability of a move from square $i$ to square $j$ is given by a transition matrix, $\mathbf{T}$. First consider a board with 100 squares and no snakes and no ladders. The player starts off the board, in a square we number 0, so the transiton matrix has dimensions $101 \times 101$, where we label the rows $i=0,1,2,\cdots 100$ as squares to move from and columns $j=0,1,2,\cdots 100$ as squares to move to. The first row the transition matrix therefore represents the probabilities of moving to each square from square 0, the start; the second row represents the probabilities of moving to each square from square 1, and so on. The moves are decided by the roll of a fair, six-sided die so the first few rows of the transition matrix in this case look like:

\begin{align*} \left( \begin{array}{ccccccccccc} 0 & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & 0 & 0 & 0 & \cdots & 0\\ 0 & 0 & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6}& \frac{1}{6} & 0 & 0 & \cdots & 0\\ \cdots \end{array} \right) \end{align*}

That is, (reading the first row) starting on square 0, there is a zero probability of remaining there, and a $\frac{1}{6}$ probability of landing on each of the squares numbered 1–6. Reading the second row gives the probabilities for progression from square 1 ($\frac{1}{6}$ for each of the destination squares 2–7), and so on.

Some people play Snakes and Ladders with the requirement that, to win, the player must land exactly on square 100, but those of us who don't feel the need to prolong the game any longer than absolutely necessary allow anyone with a roll that lands on or passes 100 to win. This will change the probabilities in the transition matrix for squares 94–99. For example, from square 97, a roll of 3,4,5 or 6 is sufficient to win. The bottom row of the transition matrix will be full of zeros because there is nowhere to go from square 100.

The game can be analysed with a row vector, $\mathbf{v}$ with 101 components, representing the probabilities that the player is on each of the squares. Initially, $\mathbf{v}^{(0)}$ is $(1, 0, 0, \cdots, 0)$: the player is certainly on square 0 before the game has begun. Subsequently, $\mathbf{v}$ evolves by the relation $$ \mathbf{v}^{(k+1)} = \mathbf{v}^{(k)} \mathbf{T}. $$ That is, the probabilities for the next move, $k+1$, are given by the dot product of the current state vector, $\mathbf{v}^{(k)}$ and the transition matrix, $\mathbf{T}$.

1. Construct the transition matrix for the above problem and plot the probability of winning as a function of $k$. What is the modal number of moves required by a single player to finish the game?

2. Now construct the transition matrix and repeat the exercise for a real game with the Snakes and Ladders given in the table below.

Hint: The probability of arriving on the "From" squares above may be set to zero and added to the corresponding "To" square.

Solution

import numpy as np
import matplotlib.pyplot as plt

# Set up the transition matrix
T = np.zeros((101, 101))
for i in range(1,101):
    T[i-1,i:i+6] = 1/6

# House rules: you don't need to land on 100, just reach it.
T[95:100,100] += np.linspace(1/6, 5/6, 5)

# The player starts at position 0.
v = np.zeros(101)
v[0] = 1

n, P = 0, []
cumulative_prob = 0
# Update the state vector v until the cumulative probability of winning
# is "effectively" 1
while cumulative_prob < 0.99999:
    n += 1
    v = v.dot(T)
    P.append(v[100])
    cumulative_prob += P[-1]
mode = np.argmax(P)+1
print('modal number of moves:', mode)

# Plot the probability of winning as a function of the number of moves
fig, ax = plt.subplots()
ax.plot(np.linspace(1,n,n), P, 'g', lw=2, alpha=0.6)
ax.set_xlim(15)
ax.set_xlabel('Number of moves')
ax.set_ylabel('Probability of winning')

plt.show()

import numpy as np
import matplotlib.pyplot as plt

ladders = [(3,19), (15,37), (22,42), (25,64), (41,73),
           (53,74), (63,86), (76,91), (84,98)]
snakes = [(11,7), (18,13), (28,12), (36,34), (77,16),
          (47,26), (83,39), (92,75), (99,70)]
trans = ladders + snakes

# Set up the transition matrix
T = np.zeros((101, 101))
for i in range(1,101):
    T[i-1,i:i+6] = 1/6

for (i1,i2) in trans:
    iw = np.where(T[:,i1] > 0)
    T[:,i1] = 0
    T[iw,i2] += 1/6

# House rules: you don't need to land on 100, just reach it.
T[95:100,100] += np.linspace(1/6, 5/6, 5)
for snake in snakes:
    T[snake,100] = 0

# The player starts at position 0.
v = np.zeros(101)
v[0] = 1

n, P = 0, []
cumulative_prob = 0
# Update the state vector v until the cumulative probability of winning
# is "effectively" 1
while cumulative_prob < 0.99999:
    n += 1
    v = v.dot(T)
    P.append(v[100])
    cumulative_prob += P[-1]
mode = np.argmax(P)+1
print('modal number of moves:', mode)

# Plot the probability of winning as a function of the number of moves
fig, ax = plt.subplots()
ax.plot(np.linspace(1,n,n), P, 'g-', lw=2, alpha=0.6, label='Markov')
ax.set_xlabel('Number of moves')
ax.set_ylabel('Probability of winning')

plt.show()