## Analysis of Chutes and Ladders

Introduction

A friend of mine has been playing the board game Chutes and Ladders recently with his son.  The game is pretty simple: starting off of the board (effectively on “square zero”), each player in turn rolls a die (actually, spins a spinner) and– if possible– moves forward the indicated number of squares in serpentine fashion on the board shown below:

Chutes and Ladders board layout. In some variants, the chute from square 48 to 26 starts at square 47 instead.

If a player lands on the tail of an arrow, he continues along the arrow to the indicated square, ending his turn there.  (“Chutes” are arrows leading backward, and “ladders” are arrows leading forward.)  The first player to land exactly on square 100 wins the game.

My friend emailed me with the question, “What is the expected number of turns before the game is over?”  I think this is a nice problem for students, since it yields to the usual two-pronged attack of (1) computer simulation and (2) “cocktail napkin” derivation of an exact solution.

This is certainly not a new problem.  See the references at the end of this post for just a few past analyses of the game as a Markov chain.  My goal here is to provide an intuitive derivation of the exact expected length of the game as a solution to a system of linear equations, while staying away from the more sophisticated machinery of Markov chains, fundamental matrices, etc., that younger students may not be familiar with.

Unbounded vs. infinite

Before getting to the exact solution, though, it is worth addressing a comment in the referenced DataGenetics blog post about Monte Carlo simulation of the game:

“Whilst the chances of a game running and running are essentially negligible (constantly landing on snakes [i.e., chutes] and going around in circles), there is a theoretical chance that the main game loop could be executing forever. This is bad, and will lock-up your code. Any smart developer implementing an algorithm like this would program a counter that is incremented on each dice roll. This counter would be checked, and if it exceeds a defined threshold, the loop should be exited.”

I strongly disagree with this.  The valid concern is that there is no fixed bound on how many turns a particular simulated game might take; that is, for any chosen positive integer $r$, there is a positive probability that the game will require at least $r$ turns, due to repeatedly falling backward down chutes.  However, the probability is zero that the game will execute forever; we can be certain that the game will always eventually terminate.  There is a difference between unbounded and infinite execution time.  In fact, such explicit “safety clamping” of the allowed number of moves implicitly changes the answer, modifying the resulting probability distribution (and thus the expected value) of the number of moves, albeit by an admittedly small amount.

There are situations where games can take an infinitely long time to finish– Chutes and Ladders just isn’t one of them.  For example, in this multi-round card game, everything is fine as long as $p > 1/2$.  And even when $p = 1/2$, the game is still guaranteed to finish, although the expected number of rounds is infinite.  But when $p < 1/2$, there is a positive probability that the game never finishes, and indeed continues “forever.”

Recursive expected values

To see how to analyze Chutes and Ladders, first consider the following simpler problem: how many times should you expect to flip a fair coin until it first comes up heads?  Let $x$ be this desired expected value.  Then considering the two possible outcomes of the first flip, either:

• It comes up heads, in which case we are done after a single flip; or
• It comes up tails… in which case we are right back where we started, and so should expect to need $x$ additional flips (plus the one we just “spent”).

That is,

$x = \frac{1}{2}(1) + \frac{1}{2}(1 + x)$

Solving yields $x=2$.  More generally, if P(success) is $p$, the expected number of trials until the first success is $1/p$.

Solution

We can apply this same idea to Chutes and Ladders.  Let $x_i$ be the expected number of turns needed to finish the game (i.e., reach square 100), starting from square $i$, where $0 \leq i \leq 100$ (so that $x_0$ is the value we really want).  Then

$x_i = 1 + \frac{1}{6}\sum_{j=1}^6 x_{f(i,j)}, i < 100$

$x_{100} = 0$

where $f(i,j)$ is the number of the square reached from square $i$ by rolling $j$— which is usually just equal to $i+j$, but this function also “encodes” the configuration of chutes and ladders on the board, as well as the requirement of landing exactly on square 100 to end the game.

So we have a system of 100 linear equations in 100 unknowns, which we can now talk the computer into solving for us (in Python):

import numpy as np

n, m = 100, 6
chutes = {1: 38, 4: 14, 9: 31, 16: 6, 21: 42, 28: 84, 36: 44,
48: 26, 49: 11, 51: 67, 56: 53, 62: 19, 64: 60, 71: 91,
80: 100, 87: 24, 93: 73, 95: 75, 98: 78}

A = np.eye(n)
b = np.ones(n)
for i in range(n):
for j in range(1, m + 1):
k = i if i + j > n else chutes.get(i + j, i + j)
if k < n:
A[i][k] -= 1.0 / m
x = np.linalg.solve(A, b)


Results

The following figure shows all of the resulting values $x_i$.  For example, the expected number of turns to complete the game from the start is $x_0 = 39.5984$.

Expected number of (additional) turns to finish game starting from the given square.

Note that we can easily analyze the “house rule” used in the DataGenetics post– allowing a player to win even when “overshooting” square 100– simply by changing the k=i in line 12 to k=n.  The result is a modest reduction in game length, to about 36.1931 turns.  (Edit: However, this is not the whole story.  See this subsequent post addressing the fact that the game involves multiple players.)

References:

1. Althoen, S. C., King, L., and Schilling, K., How Long Is a Game of Snakes and Ladders?  The Mathematical Gazette, 77(478) March 1993, p. 71-76 [JSTOR]
2. DataGenetics blog, Mathematical Analysis of Chutes and Ladders [HTML]
3. Hochman, M., Chutes and Ladders [PDF]
This entry was posted in Uncategorized. Bookmark the permalink.

### 8 Responses to Analysis of Chutes and Ladders

1. I agree with your disagreement on that point in the DataGenetics post. There are certainly situations when that’s a concern — like avoiding unbounded loops when under a real time constraints — but that’s certainly not the case here.

Reducing the problem to some elementary linear algebra is really neat. I wasn’t expecting that since my intuition was that the chute/ladder configuration would require more encoding. In your Python solution, should that be np.eye() and np.ones()?

Since I knew it would be a fun exercise, I coded up my own little Monte Carlo program to play around with the problem. My lazy programmer mindset always has me reaching for simulation over analysis.

• You’re right, thanks for the catch. I have a habit of starting with “from visual import *” in my sandbox, which also brings in numpy automatically, but forgot to fix this up after the switch.

Also, I should point out that the “system of linear equations” approach is not really a *different* approach from using the fundamental matrix in the corresponding Markov chain. In the above code, the matrix A is I-Q, where Q is the fundamental matrix, and solving the corresponding matrix equation effectively computes (I-Q)^-1, and multiplying by b=ones(n) sums the top row.

2. bhumishah says:

Great article. Thanks

3. gtownescapee says:

Nice analysis. I didn’t see the system of equations solution coming either. I meant to comment sooner, but I was waiting on my real life simulation to finish 😉

4. Kyle Miller says:

The slide 48->26 should be 47->26, changing 39.598 to 39.225. I was wondering where my own analysis diverged from yours then figured I should check my chutes and ladders carefully!

I took a slightly different approach by taking entry (100,1) of (I-Q)^(-2), which effectively calculates the expected number of turns, using the idea that entry (i,j) of Q^n is the probability of going from square j to square i in n turns.

• Note that, as the linked DataGenetics blog post points out, there are several different versions of the game out there. The one my friend had was identical to the one described in that post, which has 48->26. However, the picture of the 1952 version on the (also linked) Wikipedia page has 47->26.

You’re right that the fundamental matrix is a compact means of expressing the solution here as well; as noted in the article, the intent here was to explictly avoid the linear algebra and target a solution approachable by younger students.