Simulating Chutes & Ladders in Python

By Andres on 6 July 2024

This notebook originally appeared as a post on the blog Pythonic Perambulations.

Edit 12/19/2017: added a new subsection on analyzing Chutes & Ladders as an Absorbing Markov Chain.

Edit 2020-04-19: Andres added new sections to simulate different dice rolls and different boards. Andres left many of the anecdotes the same but had a similar situation with his son. Andres cannot presume to understand the Markov process yet.

Edit 2024-07-17: Andres was prompted to publish this after a conversation with a neighbour added a bit about bin sizes

[img: Chutes and Ladders animated simulation]

This weekend I found myself in a particularly drawn-out game of Chutes and Ladders with my four-year-old. If you’ve not had the pleasure of playing it, Chutes and Ladders (also sometimes known as Snakes and Ladders) is a classic kids board game wherein players roll a six-sided die to advance forward through 100 squares, using “ladders” to jump ahead, and avoiding “chutes” that send you backward. It’s basically a glorified random walk with visual aids to help you build a narrative. Thrilling. But she’s having fun practicing counting, learning to win and lose gracefully, and developing the requisite skills to be a passionate sports fan, so I play along.

On the approximately twenty third game of the morning, as we found ourselves in a near endless cycle of climbing ladders and sliding down chutes, never quite reaching that final square to end the game, I started wondering how much longer the game could last: what is the expected length of a game? How heavy are the tails of the game length distribution? How succinctly could I answer those questions in Python? And then, at some point, it clicked: Chutes and Ladders is memoryless — the effect of a roll depends only on where you are, not where you’ve been — and so it can be modeled as a Markov process! By the time we (finally) hit square 100, I basically had this blog post written, at least in my head.

When I tweeted about this, people pointed me to a number of similar treatments of Chutes & Ladders, so I’m under no illusion that this idea is original. Think of this as a blog post version of a dad joke: my primary goal is not originality, but self-entertainment, and if anyone else finds it entertaining that’s just an added bonus.

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:

[img: Chutes and ladders game board]

(Image source: uncyclopedia)

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

# Mapping of start : end spaces of chutes & ladders
CHUTES_LADDERS = {1:38, 4:14, 9:31, 16:6, 21:42, 28:84, 36:44,
                  47:26, 49:11, 51:67, 56:53, 62:19, 64:60,
                  71:91, 80:100, 87:24, 93:73, 95:75, 98:78}
CHUTES_LADDERS_CBEEBIES ={2:19, 5:10, 15:31, 13:1, 21:8, 27:36, 34:17, 37:23}

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

from random import Random


def simulate_cl_game(rseed=None, max_roll=6):
    """
    Simulate a full Chutes & Ladders game
    and return the number of turns to finish
    """
    rand = Random(rseed)
    position = 0
    turns = 0
    while position < 100:
        turns += 1
        roll = rand.randint(1, max_roll)
        
        # if the roll takes us past square 100, we don't move
        if position + roll > 100:
            continue
            
        # otherwise, move the position according to the roll
        position += roll
        
        # go up/down any chute/ladder
        position = CHUTES_LADDERS.get(position, position)
        if turns > 500:
            break
        
    return turns

def simulate_cl_game_cebeebies(rseed=None, max_roll=6):
    """
    Simulate a full Chutes & Ladders game
    and return the number of turns to finish
    """
    rand = Random(rseed)
    position = 0
    turns = 0
    while position < 38:
        turns += 1
        roll = rand.randint(1, max_roll)
        
        # if the roll takes us past square 38, we don't move
        if position + roll > 38:
            continue
            
        # otherwise, move the position according to the roll
        position += roll
        
        # go up/down any chute/ladder
        position = CHUTES_LADDERS_CBEEBIES.get(position, position)
        if turns > 500:
            break
       

    return turns

def simulate_cl_game_cebeebies_past(rseed=None, max_roll=6):
    """
    Simulate a full Chutes & Ladders game
    and return the number of turns to finish
    no need for exact number. 
    """
    rand = Random(rseed)
    position = 0
    turns = 0
    while position < 38:
        turns += 1
        roll = rand.randint(1, max_roll)
        
        if position + roll > 38:
            break
            
        # otherwise, move the position according to the roll
        position += roll
        
        # go up/down any chute/ladder
        position = CHUTES_LADDERS_CBEEBIES.get(position, position)
        if turns > 500:
            break

    return turns

def simulate_cl_game_cebeebies_bounce(rseed=None, max_roll=6):
    """
    Simulate a full Chutes & Ladders game
    and return the number of turns to finish
    """
    rand = Random(rseed)
    position = 0
    turns = 0
    while position < 38:
        turns += 1
        roll = rand.randint(1, max_roll)
        
        # if the roll takes us past square 100, bounce back
        if position + roll > 38:
            bounce = (position + roll) - 38
            position = 38 - bounce
            # go up/down any chute/ladder
            position = CHUTES_LADDERS_CBEEBIES.get(position, position)
            continue
            
        # otherwise, move the position according to the roll
        position += roll
        
        # go up/down any chute/ladder
        position = CHUTES_LADDERS_CBEEBIES.get(position, position)
        if turns > 500:
            break

    return turns


def simulate_cl_game_cebeebies_d8(rseed=None, max_roll=8):
    """
    Simulate a full Chutes & Ladders game
    and return the number of turns to finish
    """
    rand = Random(rseed)
    position = 0
    turns = 0
    while position < 38:
        turns += 1
        roll = rand.randint(1, max_roll)
        
        # if the roll takes us past square 100, we don't move
        if position + roll > 38:
            continue
            
        # otherwise, move the position according to the roll
        position += roll
        
        # go up/down any chute/ladder
        position = CHUTES_LADDERS_CBEEBIES.get(position, position)
        if turns > 500:
            break

    return turns

def simulate_cl_game_cebeebies_bounce_d8(rseed=None, max_roll=8):
    """
    Simulate a full Chutes & Ladders game
    and return the number of turns to finish
    """
    rand = Random(rseed)
    position = 0
    turns = 0
    while position < 38:
        turns += 1
        roll = rand.randint(1, max_roll)
        
        # if the roll takes us past square 100, bounce back
        if position + roll > 38:
            bounce = (position + roll) - 38
            position = 38 - bounce
            # go up/down any chute/ladder
            position = CHUTES_LADDERS_CBEEBIES.get(position, position)

            continue
            
        # otherwise, move the position according to the roll
        position += roll
        
        # go up/down any chute/ladder
        position = CHUTES_LADDERS_CBEEBIES.get(position, position)
        if turns > 500:
            break

    return turns

def simulate_cl_game_cebeebies_bounce_d6d8d8(rseed=None, d6_roll=6, d8_roll=8 ):
    """
    Simulate a full Chutes & Ladders game
    and return the number of turns to finish
    """
    rand = Random(rseed)
    position = 0
    turns = 0
    while position < 38:
        turns += 1
        roll = rand.randint(1, d6_roll)
        
        # if the roll takes us past square 100, bounce
        if position + roll > 38:
            bounce = (position + roll) - 38
            position = 38 - bounce
            # go up/down any chute/ladder
            position = CHUTES_LADDERS_CBEEBIES.get(position, position)
            
            
        # otherwise, move the position according to the roll
        position += roll
        # go up/down any chute/ladder
        position = CHUTES_LADDERS_CBEEBIES.get(position, position)
        # second dice roll
        roll = rand.randint(1, d8_roll)
        
        # if the roll takes us past square 100, bounce back
        if position + roll > 38:
            bounce = (position + roll) - 38
            position = 38 - bounce
            # go up/down any chute/ladder
            position = CHUTES_LADDERS_CBEEBIES.get(position, position)
            
            
        # otherwise, move the position according to the roll
        position += roll
        # go up/down any chute/ladder
        position = CHUTES_LADDERS_CBEEBIES.get(position, position)

        #Third Dice roll
        roll = rand.randint(1, d8_roll)
        
        # if the roll takes us past square 100, bounce
        if position + roll > 38:
            bounce = (position + roll) - 38
            position = 38 - bounce
            # go up/down any chute/ladder
            position = CHUTES_LADDERS_CBEEBIES.get(position, position)
            continue
            
        # otherwise, move the position according to the roll
        position += roll

        # go up/down any chute/ladder
        position = CHUTES_LADDERS_CBEEBIES.get(position, position)

        # NEED TO PUT A LIMIT OF THE NUMBER OF TURNS! IF MORE THAN 100 BREAK!
        if turns > 500:
            break

    return turns

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

simulate_cl_game()

21

simulate_cl_game_cebeebies()

13

simulate_cl_game_cebeebies_bounce()

10

simulate_cl_game_cebeebies_past()

7

simulate_cl_game_cebeebies_d8()

20

simulate_cl_game_cebeebies_bounce_d6d8d8()

32

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

# Jupyter notebook plotting setup & imports
%matplotlib inline
import matplotlib.pyplot as plt
import numpy
plt.style.use('seaborn')

sim_times = 1000
sim_games_CBBC_past = [simulate_cl_game_cebeebies_past() for i in range(sim_times)]
sim_games_CBBC_bounce = [simulate_cl_game_cebeebies_bounce() for i in range(sim_times)]
sim_games_CBBC = [simulate_cl_game_cebeebies() for i in range(sim_times)]
bins = range(60)
plt.hist([sim_games_CBBC,sim_games_CBBC_bounce, sim_games_CBBC_past], bins, label=['cbbc_d6','cbbc_d6_bounce', 'cbbc_d6_past'])
plt.xlabel('Number of Turns to win')
plt.ylabel('Fraction of games')
plt.title('Lengths of Snakes & Ladders %d Games'% sim_times);
plt.legend(loc='upper right')

<matplotlib.legend.Legend at 0x7f0bdf9e4a30>

sim_games_CBBS_bounce_d6d8d8 = [simulate_cl_game_cebeebies_bounce_d6d8d8() for i in range(sim_times)]
sim_games_CBBC_bounce_d8 = [simulate_cl_game_cebeebies_bounce_d8() for i in range(sim_times)]
sim_games_CBBC_bounce = [simulate_cl_game_cebeebies_bounce() for i in range(sim_times)]
bins = range(60)
plt.hist([sim_games_CBBC_bounce, sim_games_CBBC_bounce_d8, sim_games_CBBS_bounce_d6d8d8], bins, label=['CBBC_d6_bounce', 'CBBC_bounce_d8', 'CBBC_bounce_d6d8d8'])
plt.xlabel('Number of Turns to win')
plt.ylabel('Fraction of games')
plt.title('Simulated Lengths of Chutes & Ladders %d Games'% sim_times);
plt.legend(loc='upper right')

<matplotlib.legend.Legend at 0x7f0bddb181c0>

sim_games_CBBS_bounce_d6d8d8 = [simulate_cl_game_cebeebies_bounce_d6d8d8() for i in range(sim_times)]
sim_games_CBBC_bounce_d8 = [simulate_cl_game_cebeebies_bounce_d8() for i in range(sim_times)]
sim_games_CBBC_bounce = [simulate_cl_game_cebeebies_bounce() for i in range(sim_times)]
sim_games_CBBC_d8 = [simulate_cl_game_cebeebies_d8() for i in range(sim_times)]
sim_games_CBBC = [simulate_cl_game_cebeebies() for i in range(sim_times)]
sim_games = [simulate_cl_game() for i in range(sim_times)]
bins = range(60)
plt.hist([sim_games,sim_games_CBBC,sim_games_CBBC_bounce, sim_games_CBBC_d8,sim_games_CBBC_bounce_d8, sim_games_CBBS_bounce_d6d8d8], bins, label=['standard','cbbc_d6','cbbc_d6_bounce', 'cbbc_d8','CBBC_bounce_d8', 'CBBC_bounce_d6d8d8'])
plt.xlabel('Number of Turns to win')
plt.ylabel('Fraction of games')
plt.title('Simulated Lengths of Chutes & Ladders %d Games'% sim_times);
plt.legend(loc='upper right')

<matplotlib.legend.Legend at 0x7f0bddab3a60>

CBBC_bounce_d6d8d8 = [simulate_cl_game_cebeebies_bounce_d6d8d8() for i in range(sim_times)]
sim_games_CBBC_bounce_d8 = [simulate_cl_game_cebeebies_bounce_d8() for i in range(sim_times)]
sim_games_CBBC_bounce = [simulate_cl_game_cebeebies_bounce() for i in range(sim_times)]
bins = range(60)
plt.hist([sim_games_CBBC_bounce, sim_games_CBBC_bounce_d8, CBBC_bounce_d6d8d8], bins, label=['cbbc_d6_bounce', 'CBBC_bounce_d8', 'CBBC_bounce_d6d8d8'])
plt.xlabel('Number of Turns to win')
plt.ylabel('Fraction of games')
plt.title('Simulated Lengths of Chutes & Ladders %d Games'% sim_times);
plt.legend(loc='upper right')

<matplotlib.legend.Legend at 0x7f0bdd297970>

sim_games_CBBC_bounce = [simulate_cl_game_cebeebies_bounce() for i in range(sim_times)]
sim_games_CBBC = [simulate_cl_game_cebeebies() for i in range(sim_times)]
sim_games = [simulate_cl_game() for i in range(sim_times)]
bins = range(60)
plt.hist(sim_games, bins,  alpha=0.25, label='standard')
plt.hist(sim_games_CBBC, bins,  alpha=0.75, label='cbbc_d6')
plt.hist(sim_games_CBBC_bounce, bins,  alpha=0.75, label='cbbc_d6_bounce')
plt.xlabel('Number of Turns to win')
plt.ylabel('Fraction of games')
plt.title('Simulated Lengths of Chutes & Ladders %d Games'% sim_times);
plt.legend(loc='upper right')

<matplotlib.legend.Legend at 0x7f0bdd1df2b0>

sim_games = [simulate_cl_game_cebeebies() for i in range(sim_times)]

plt.hist(sim_games, bins=range(60))
plt.xlabel('Number of Turns to win')
plt.ylabel('Fraction of games')
plt.title('Simulated Lengths of Chutes & Ladders %d Games CBBC d6'% sim_times);

sim_games = [simulate_cl_game_cebeebies_bounce() for i in range(sim_times)]

plt.hist(sim_games, bins=range(60))
plt.xlabel('Number of Turns to win')
plt.ylabel('Games out of %d'% sim_times)
plt.title('Simulated Lengths of Chutes & Ladders %d Games CBBC d6 bounce'% sim_times);

sim_games = [simulate_cl_game_cebeebies_d8() for i in range(sim_times)]

plt.hist(sim_games, bins=range(60))
plt.xlabel('Number of Turns to win')
plt.ylabel('Games out of %d'% sim_times)
plt.title('Simulated Lengths of Chutes & Ladders %d Games CBBC d8' % sim_times);

What is a bin? why choose 60 or a range of 60 :[1, 2, 3, 4, …, 59, 60] or any clever distribution? can I really say it is the number of turns to win in the x axis? or is it more of a representation?

Lets find out! First lets just do the same simulations of the games.

sim_games_d8 = [simulate_cl_game_cebeebies_d8() for i in range(sim_times)]
sim_games_bounce = [simulate_cl_game_cebeebies_bounce() for i in range(sim_times)]

n_bins = 60

fig, axs = plt.subplots(1, 2, sharey=True, tight_layout=True)
fig.suptitle('Bin %d Simulated Lengths of Chutes and Ladders  %d Games'% (n_bins,  sim_times))

axs[0].hist(sim_games_d8, bins=n_bins)
axs[0].set_title('with D8 dice')
axs[0].set_ylabel('Games won out of %d'% sim_times)
axs[0].set_xlabel('Number of Turns to win')
axs[1].hist(sim_games_bounce, bins=n_bins)
axs[1].set_title('with D6 but bouncing')
axs[1].set_xlabel('Number of Turns to win')


n_bins = range(60)

fig, axs = plt.subplots(1, 2, sharey=True, tight_layout=True)
fig.suptitle('Bin {bins} Simulated Lengths of Chutes and Ladders  {games} Games'
             .format(bins="list [1, 2, .., 59, 60]",  games = sim_times))

axs[0].hist(sim_games_d8, bins=n_bins)
axs[0].set_title('with D8 dice')
axs[0].set_ylabel('Games won out of %d'% sim_times)
axs[0].set_xlabel('Number of Turns to win')
axs[1].hist(sim_games_bounce, bins=n_bins)
axs[1].set_title('with D6 but bouncing')
axs[1].set_xlabel('Number of Turns to win')

n_bins = 'auto'#https://en.wikipedia.org/wiki/Histogram#Number_of_bins_and_width

fig, axs = plt.subplots(1, 2, sharey=True, tight_layout=True)
fig.suptitle('Bin {bins} Simulated Lengths of Chutes and Ladders  {games} Games'
             .format(bins="'auto'",  games = sim_times))

axs[0].hist(sim_games_d8, bins=n_bins)
axs[0].set_title('with D8 dice')
axs[0].set_ylabel('Games won out of %d'% sim_times)
axs[0].set_xlabel('Number of Turns to win')
axs[1].hist(sim_games_bounce, bins=n_bins)
axs[1].set_title('with D6 but bouncing')
axs[1].set_xlabel('Number of Turns to win')

n_bins = [0,10, 20, 30, 40, 50, 60]

fig, axs = plt.subplots(1, 2, sharey=True, tight_layout=True)
fig.suptitle('Bin {bins} Simulated Lengths of Chutes and Ladders  {games} Games'
             .format(bins=n_bins,  games = sim_times))

axs[0].hist(sim_games_d8, bins=n_bins, rwidth=0.95)
axs[0].set_title('with D8 dice')
axs[0].set_ylabel('Games won out of %d'% sim_times)
axs[0].set_xlabel('Number of Turns to win')
axs[1].hist(sim_games_bounce, bins=n_bins, rwidth=0.95)
axs[1].set_title('with D6 but bouncing')
axs[1].set_xlabel('Number of Turns to win')


n_bins = [0,10, 20, 30, 40,  60]

fig, axs = plt.subplots(1, 2, sharey=True, tight_layout=True)
fig.suptitle('Bin {bins} Simulated Lengths of Chutes and Ladders  {games} Games'
             .format(bins=n_bins,  games = sim_times))

axs[0].hist(sim_games_d8, bins=n_bins, rwidth=0.95)
axs[0].set_title('with D8 dice')
axs[0].set_ylabel('Games won out of %d'% sim_times)
axs[0].set_xlabel('Number of Turns to win')
axs[1].hist(sim_games_bounce, bins=n_bins, rwidth=0.95)
axs[1].set_title('with D6 but bouncing')
axs[1].set_xlabel('Number of Turns to win')


Text(0.5, 0, 'Number of Turns to win')

So in this case the bins do represent the number of turns. But there is a catch!

  1. The first set of plots takes all the games even that random game out of 1000 games that took more than 80 turns to finish! and divides it into 60 equally spaced sections. So the D8 simulation without bounce almost all of the games are done by turn 60. But in the D6 version with Bounce there is still maybe 20 games that take more than 60 turns to finish.
  2. The second set of plots uses a list of bins. This means I told the program to only show me the data up to turn number 60. This is good if I want to compare the x axis like for like.
  3. Uses the “auto” binning technique which divides the ranges into parts that depend on the number of turns it takes to win. It is explained (here)[https://numpy.org/doc/stable/reference/generated/numpy.histogram_bin_edges.html#numpy.histogram_bin_edges] from what it seems it is the most memory effiencent way to do do it? notice there is a slight difference in comparison with the first one I did with 60 bins. The auto function seems to have chosen a lower number of bins.
  4. The clearest representation what bins are can be seen in the last two sets of plots which I used the trick of using a list of values that I am interested in. I also added a space between the bins to make it clear the separation between bins [¹]. It can be read the following way:
    1. [0,10, 20, 30, 40, 50, 60] We simulate 1000 games. The first columns represent the amount of games out of the 1000 games that took 10 or less turns to finish. The second column represent the amount of games out of 1000 games that took between 10 and 20 turns to finish. (…) The last column represents the amount of games out of 1000 games that took between 50 and 60 turns to finish. NOTE: if you add the amounts from the last columns you get arount 50 and 130 respetively.
    2. [0,10, 20, 30, 40, 60] notice I skipped 50 We simulate 1000 games. the first columns represent the amount of games out of the 1000 games that took 10 or less turns to finish. The second column represent the amount of games out of 1000 games that took between 10 and 20 turns to finish. (…) The last column represents the amount of games out of 1000 games that took between 40 and 60 turns to finish. NOTE: compare the amount of game won between 30 and 40 turns and the amount of games won between 40 and 60 turns.

Technically if you add the amount of games from each column it will add up to 1000 but because we stopped counting at 60 turns (in these latter cases) you are not adding all those game that took more than 60 turns to finish.

[¹]: This is not good practice when doing histograms because it makes it look like a barchart.

So let us to only 100 simulations that way the Y axis can be seen as a % and we can re do the last two plots as an even clear comparison. I will add the number value of each bin as well. Notice it does not always need to add to 100 as I am not showing all the bins!

sim_times=100
sim_games_d8 = [simulate_cl_game_cebeebies_d8() for i in range(sim_times)]
sim_games_bounce = [simulate_cl_game_cebeebies_bounce() for i in range(sim_times)]


n_bins = [0,10, 20, 30, 40, 50, 60]

fig, axs = plt.subplots(1, 2, sharey=True, tight_layout=True)

fig.suptitle('Bin {bins} Simulated Lengths of Chutes and Ladders  {games} Games'
             .format(bins=n_bins,  games = sim_times))

(n, bins, patches) = axs[0].hist(sim_games_d8, bins=n_bins, rwidth=0.95)
axs[0].set_title('with D8 dice')
axs[0].set_ylabel('Games won out of {total} sums {list}'.format(total=sum(n), list=n))
axs[0].set_xlabel('Number of Turns to win')
(n, bins, patches) = axs[1].hist(sim_games_bounce, bins=n_bins, rwidth=0.95)
axs[1].set_title('with D6 but bouncing')
axs[1].set_ylabel('Games won out of {total} sums {list}'.format(total=sum(n), list=n))
axs[1].set_xlabel('Number of Turns to win')


n_bins = [0,10, 20, 30, 40,  60]

fig, axs = plt.subplots(1, 2, sharey=True, tight_layout=True)
fig.suptitle('Bin {bins} Simulated Lengths of Chutes and Ladders  {games} Games'
             .format(bins=n_bins,  games = sim_times))

(n, bins, patches) = axs[0].hist(sim_games_d8, bins=n_bins, rwidth=0.95)
axs[0].set_title('with D8 dice')
axs[0].set_ylabel('Games won out of {total} sums {list}'.format(total=sum(n), list=n))
axs[0].set_xlabel('Number of Turns to win')
(n, bins, patches) =  axs[1].hist(sim_games_bounce, bins=n_bins, rwidth=0.95)
axs[1].set_title('with D6 but bouncing')
axs[1].set_ylabel('Games won out of {total} sums {list}'.format(total=sum(n), list=n))
axs[1].set_xlabel('Number of Turns to win')

Text(0.5, 0, 'Number of Turns to win')

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. To be continued…

Back to blog

A Community Interest

C4AD was registered as a Private company limited by guarantee without share capital Community Interest Company (CIC). In short: not for profit and asset locked. The company's activities will provide benefit to those living in the South West London area and beyond with the use of Science, Technology, Engineering, Arts and Maths. STEM needs Arts to be successful so at C4AD S.T.E.A.M. is promoted: the aim is to demystify STEAM. The company is no more, but the activities continue as a free time activity!