Direct Simulation¶

The most straightforward way to get a handle on the dynamics of the game is through direct simulation: if we simulate enough games, we'll obtain a distribution of game lengths that will approximate the "true" distribution. The first step in this is to examine the game board and somehow encode the positions of the chutes and ladders on the grid:

(Image source: uncyclopedia)

We'll use a Python dictionary to store these positions:

With this in place, we can simulate the game in a few lines of Python:

Calling the function tells us how many moves were required to finish the particular game:

If we simulate many games, the result will be a distribution of how many turns are required to get to the end:

This gives us some insight, but the problem here is that the result is just an estimate of the "true" distribution; to make our estimate more precise will require many more simulations, and this can get computationally expensive.

Fortunately, there's another approach.

Chutes and Ladders as a Markov Process¶

Instead of brute force simulation, we might think about the game probabilistically. On any given turn, there are six equally probable options: rolling a 1, 2, 3, 4, 5, or 6. Depending on which space you start on, these lead to six well-defined results. For example, the first turn, the possibilities are the squares 38, 2, 3, 14, 5, or 6, each with equal probability. We could encode this set of probabilities as a vector of length 101, with 1/6 in each associated index (here the zeroth element represents the start of the game, off of the board):

0: [0, 0, 1/6, 1/6, 0, 1/6, 1/6, 0, 0, ...]

Each entry in this vector is the probability of going from square zero to the corresponding square. This vector completely describes the first turn of the game.

Similarly, we could construct the vector describing turns from square 2:

2: [0, 0, 0, 1/6, 0, 1/6, 1/6, 1/6, 1/6, 0, 0, ...]

Again, this completely describes any turn of the game that starts at square two.

The key insight is that Chutes and Ladders is memoryless; if you're on, say, square 19, it doesn't matter if you got there by sliding down from square 62, or by rolling a five from square 14 – the probabilities on the next turn are exactly the same.

This kind of situation: a sequence of probabilistic transitions from one state to another with no memory of previous states, is known as a Markov Chain or Markov Process, and can be entirely described by a N x N transition matrix where N is the number of states in the system (101 states for Chutes and Ladders). The columns of the matrix contain the probability vectors we discussed above, such that element (n, m) is the probability of transitioning to element n when starting from element m.

Let's create a Markov transition matrix for Chutes and Ladders:

The above matrix encodes everything you need to know about the game of Chutes and Ladders. (Note that there are two ways to construct this matrix: applying the chutes and ladders jumps at the end of each turn, as typically played, or applying them at the beginning of the next turn. We make this second option available for later).

The game starts with a state vector describing 100% probability of being in the zeroth state:

v_0 = [1, 0, 0, 0, 0...]

If you think about it for a while, you can convince yourself that the way to evolve this (probabilistically) to the next state is to left-multiply the vector by our transition matrix:

The result is precisely the vector we described above, encoding the probabilities of game state after one move.

To perform multiple moves, we could repeatedly multiply this vector by our transition matrix, but repeating such an operation can compound floating-point inaccuracies; a more effective (and more efficient) approach is to use a matrix power. With this in mind, lets compute the probability of finishing the game in n moves for several values of n, and compare it to the simulation result from above:

By eye it looks like our direct simulation was quite close to the Markov model, which indicates that we're on the right track in our thinking.

The cumulative distribution is also interesting:

From this, we can see that 90% of single-player games finish within about 72 moves, though it is possible for games to be much longer.

With two players, this translates to a 1% chance that the game will go 72 moves without either of the players winning. Assuming roughly 20 seconds per round, that is about 24 minutes of play time, though from personal experience I can say it feels roughly twenty times that long.

Minimum Game Length¶

But what if you get really lucky... how quickly can the game end? From our Markov chain results, we see that there is a nonzero probability of finishing the game in just seven moves, and this will happen about once in every 660 games:

The Markov chain approach doesn't immediately tell us how this happens, though the transition matrix encodes a sparse graph that can be used by scipy.sparse.csgraph to find one of these shortest paths:

lengths here is the length of the shortest path from state 0 to each of the other states:

We can use the predecessors vector here to reconstruct one of the shortest paths to state 100:

Typical Game Length¶

We've talked about the extremes, but how long should you expect the typical game to last? The answer to that question depends on what you mean by typical. Some common approaches to defining typical are the mean, median, or mode of game lengths.

The mean game length is the expected value of the number of turns, averaged over all possibilities and weighted by their relative probability:

We see that, on average, a player will finish the game in about 39 turns.

This value, though, is weighted by game length, so the small possibility of having a very long game contributes to this estimate in an outsized way. Often the median game length is a more useful statistic:

This tells us that approximately 50% of games will be finished in fewer than 32 moves, and 50% will be finished in more than 32 moves.

But both the mean and the median are offset from the peak (or mode) of the probability distribution, which we can compute as follows:

This says that you'll finish the game in 22 moves more often than any other specific number of moves.

Probably the most useful types of statistics for skewed probability distributions like this one, though, are quantiles. For example:

This tells us that 95% of the time, games will last between 11 and 106 turns. Or, to tighten the constraints a bit:

half of all games will last between 22 and 50 moves.

Learning More from the Markov Process¶

Aside from summary statistics, the Markov transition matrix for Chutes and Ladders can tell us a number of other interesting things, which we'll explore here.

Shannon Entropy¶

One interesting thing we can explore is the entropy of the distribution: you can think of the entropy as a measure of how "spread out" the distribution is in probability space; a high entropy state is one in which we have very little knowledge of where an individual draw will lie.

We can compute and visualize the entropy using the entropy function from SciPy's stats module. Let's plot the entropy as a function of the number of turns played:

We see that the entropy is maximized after eleven turns:

What this tells you is that when you complete 11 turns, you should expect positions of various players to be very spread out. Prior to this, the probability distribution is clumped near the beginning of the board. After 11 moves, you can take heart that you're unavoidably on the path to the game's end.

Eigenvectors and Stationary States¶

The Markov transition matrix can be examined directly to learn about the dynamics of the game. For example, the eigenvectors of a transition matrix with eigenvalue equal to one tell us about stationary states; that is, states which are unchanged after applying the transition matrix.

We can compute these eigenvectors this way:

There is only one stationary state in Chutes and Ladders (with eigenvalue equal to one); let's see what it is:

Graciously, the single stationary state is a completed game. What this means is that you are very unlikely to find yourself in an infinitely looping, unending game. I doubt the game designers did this stationary state calculation when designing the game, but I bless them for their accidental success in this regard.

Fundamental Matrix¶

As we have set up the transition matrix, once you reach state 100 you remain there with 100% probability. In mathematical terms, the end of the game is an "absorbing state", because once you are there you cannot transition to any other state. What this means is that Chutes and Ladders is an absorbing Markov Chain, and we can do a few more interesting things with the transition matrix.

This all starts with computing the fundamental matrix N of the absorbing Markov chain, which is a simple transformation of the Markov transition matrix:

(Note that we used the version of our process where jumps happen at the beginning of the turn, so that we can more easily reason about the effects of ladders and chutes).

The (n,m) entry of the fundamental matrix tells us the expected number of times that we will visit state n when starting at state m on our way to the absorbing state.

Let's plot these expected values when starting at state 0, the beginning of the game

The profile is pretty interesting. The most striking feature is that you're expected to visit square 99 approximately 1.5 times per game, on average! This is due to the fact that once you land on square 99, you have to roll a 1 to exit it; each additional turn that you don't roll a 1 is counted as another visit.

Let's look at the top few other most visited states:

The next most visited state is state 0, which you visit exactly once at the start of each game. After that is square 47, which is visited about 3/4 times per game on average. Interestingly, this square is the top of a chute, and thus is the most used of all chutes in the game.

We can also look at the least visited squares on the board:

Surprisingly, the least likely square is 67, and is visited even less often than square 1, which you have the possibility of hitting only once per game, if you roll a 1 on the first roll! Looking at the graph above, it is clear that squares 55-75 or so are visited relatively rarely, due to the positions of chutes and of ladders within the game board.

The Big Chute and Big Ladder¶

One thing my daughter would probably like to know: how often will you to hit the "big slide" or the "big ladder" during a game? These are at squares 87, and 28, respectively:

We see that a player is expected to slide down the big chute a bit over once in every two games on average, and climb the big ladder slightly more often: just under six times in every ten games on average.

Time to Absorption¶

The fundamental matrix can also be used to compute other quantities; for example the matrix product with a column of ones gives the expected "time to absorption"; that is, the expected number of turns until finishing the game from any given square. Let's use the "jump-at-the-end" version of the matrix again:

From the first square, the expected time to completion is 39.7 moves: this is half a move than the 39.2 moves we computed previously, because we're using a different form of the matrix (here we count climbing the ladder from square 80 to square 100 as one extra move)

This vector can tell us what the best first roll is: as my daughter has intuited, starting out by rolling a 1 and climbing the first ladder is best: it decreases your expected time to completion by five moves. The worst first roll is a 2: this actually increases your expected time to completion by 0.5 turns, on average: rolling a 2 to start is akin to moving away from the goal.

By the time you get to the 99th square, your espected time to completion is 6 moves, because you have a 1/6 chance of rolling the 1 required to win. Two squares back, on the 97th square, your expected time to completion goes up to 11 moves, because of the chute present on the 98th square.

The fundamental matrix lets you quantititatively explore a number of other properties of the game; for example, we could adjust the matrix to make square 80 an absorber as well, and ask how probable we are to complete the game there versus landing on square 100 directly. Or we could compute quantities such as the variance of the number of visits and number of steps above. For more discussion of applications of the fundamental matrix of an absorbing Markov chain, see the wikipedia article. A nice undergraduate-level introduction to these concepts can be found in Chapter 11 of Grinstead and Snell's “Introduction to Probability” (pdf available here).

Visualizing the Board¶

Just for fun, let's use Python's tools to visualize these probability states in an intuitive way. We'll use the above scan of the original Chutes and Ladders game as our background, and plot the probability distribution on top of this using a custom colormap with changing transparency

Using this, we can visualize the probability distribution after any number of turns:

After one turn, the distribution is quite tight: there are six possible states we can find ourselves in.

After two turns, things become more spread out, though they are still clumped around a few more likely values.

After 3 turns, the distribution is getting even further apart.

After 50 turns, many games will be finished, but there's still a non-negligible probability of finding yourself in spaces across the board.

Animating the Simulations¶

These board visualizations will be a bit more intuitive if we animate the results; here I'll do this using the excellent ImageIO package to stitch together an animated GIF from the individual matplotlib plots. (Note that you can also do this sort of animation directly in matplotlib, but matplotlib's GIF writer requires some extra command-line tools that ImageIO does not).

Let's start with a function that will build a GIF using ImageIO from a generator of matplotlib figures:

Now we can create some simulations and make a GIF. I'll tweak the frame durations of the gif a bit to emphasize the more interesting earlier frames:

The resulting GIF looks like this:

Conclusion¶

I hope you've enjoyed this exploration of Chutes & Ladders, and even if you haven't, I'm certain you'll take solace in the fact that I did. And to Jace: if you ever come across this post at some point years down the road, I hope you'll someday experience the joy of playing Chutes & Ladders with your kids for as many hours as I did with you.

Thanks for reading!

This post was written entirely in the Jupyter notebook. You can download this notebook, or see a static view on nbviewer.