Why Do Snakes and Ladders Games Take So Long?

One game is pure luck

Play three or four games on the board above (Play to the end is quicker), and write down how many turns each took. The board lists your finished games too.

• a.How different were your games? What was the shortest, and the longest?
• b.From your games alone, what would you say the average game is? How sure are you?

Ten thousand games at once

This board plays games by itself, as fast as it can. Choose how many, and press Play.

• a.Play 10 games five times. Watch the average: how much does it jump about?
• b.Now play 10,000 games a few times. How much does the average change now?
• c.Look at the bar chart of 10,000 games. Where are the tallest bars? Is the average in the middle of the tall bars, or to their right?
• d.Look at Longest. How long is the longest game in 10,000?

Now take things off the board. Tap a snake or a ladder (it fades), play 10,000 games, and compare the new average with the last one (the sentence above the chart shows both).

• a.Take off the longest snake, from 87 down to 24. How much shorter do games get?
• b.Put it back (or press Put every snake and ladder back). Which one ladder makes the most difference when it is taken off? Try the long one from 28 to 84, then the short one from 80 to 100.

A simulation is a program that plays out the real thing with random numbers standing in for luck. It needs three parts:

• the rules, written exactly: start on square 0 (off the board); each turn, roll a die; move; if you land on a ladder’s foot, climb it; on a snake’s head, slide down; you must land exactly on 100;
• a random number for each roll, from 1 to 6, all equally likely, as a fair die gives (random.randint(1, 6), which you met in Grade 8);
• many games, and the results counted: the average, the shortest, the longest.

One game is a story; ten thousand games are evidence.

The board as a list

How does a program know where the snakes and ladders are? The neat way is a list of 101 numbers, one for each square from 0 to 100, saying where you end up if you land there. For most squares that is the square itself. For a ladder’s foot, it is the top; for a snake’s head, its tail.

So a whole move is one line: square = board[square + roll]. Landing on 28 gives board[28], which is 84, up the ladder. Landing on 29 gives 29, an ordinary square.

One turn in blocks

Here is one turn as a block program, with three of the board’s jumps: the ladders at 28 and 80 and the snake at 87. It asks where you are and what you rolled, and says where you end up.

A whole game is this turn repeated until the square is 100; a simulation is that game repeated thousands of times. Blocks light up each block as they go, far too slowly for thousands of games, so the rest is in Python.

One game

The board’s 19 jumps are a list of pairs, [from, to], nine ladders then ten snakes. A loop turns them into the board list. Then a while loop plays one game, keeping a list of every square the counter ends a turn on.

import randomrandom.seed(1) jumps = [[1, 38], [4, 14], [9, 31], [21, 42], [28, 84], [36, 44],         [51, 67], [71, 91], [80, 100],         [16, 6], [47, 26], [49, 11], [56, 53], [62, 19], [64, 60],         [87, 24], [93, 73], [95, 75], [98, 78]]board = list(range(101))for jump in jumps:    board[jump[0]] = jump[1] square = 0turns = 0path = []while square < 100:    roll = random.randint(1, 6)    turns = turns + 1    if square + roll <= 100:        square = board[square + roll]    path.append(square)print(path)print('Finished in', turns, 'turns')

[2, 7, 8, 11, 12, 6, 10, 14, 20, 24, 26, 27, 31, 32, 44, 48, 53, 54, 60, 60, 63, 69, 91, 96, 97, 100]Finished in 26 turns

list(range(101)) makes the list 0, 1, 2, … 100, and board[jump[0]] = jump[1] changes one square of it. random.seed(1) makes Python’s random numbers start from a fixed point, so this program plays the same game every time and you can check it against the page. Take that line out (or change the 1) and every Run plays a new game.

Many games

To play many games, put one game in a function that gives back how many turns it took. Then call it again and again. This program plays 10 games, five times over, and prints each set with its average.

import randomrandom.seed(1) jumps = [[1, 38], [4, 14], [9, 31], [21, 42], [28, 84], [36, 44],         [51, 67], [71, 91], [80, 100],         [16, 6], [47, 26], [49, 11], [56, 53], [62, 19], [64, 60],         [87, 24], [93, 73], [95, 75], [98, 78]]board = list(range(101))for jump in jumps:    board[jump[0]] = jump[1] def play_game(board):    square = 0    turns = 0    while square < 100:        roll = random.randint(1, 6)        turns = turns + 1        if square + roll <= 100:            square = board[square + roll]    return turns for i in range(5):    games = []    for g in range(10):        games.append(play_game(board))    print(games, ' average', sum(games) / 10)

[26, 9, 16, 9, 13, 59, 98, 26, 73, 33]  average 36.2[32, 55, 29, 20, 37, 53, 27, 15, 75, 50]  average 39.3[21, 23, 9, 38, 15, 32, 15, 19, 53, 70]  average 29.5[65, 10, 12, 30, 97, 34, 100, 46, 23, 23]  average 44.0[12, 41, 86, 175, 32, 31, 35, 57, 12, 33]  average 51.4

Ten games are not enough: the averages of the five sets are far apart. Let the page play 10,000 of your games instead. It calls your play_game(board) from the program just above, as you have it (press Edit to change it), and draws the bar chart of your games.

Ten thousand games, counted

Now the numbers. sum(), min() and max() work on a whole list. To find the most common game, the program counts how many games took each number of turns: [0] * (max(games) + 1) is a list of zeros, one counter for each number of turns from 0 to the longest game (323 counters in this run), and counts.index(max(counts)) finds where the biggest count is.

import randomrandom.seed(1) jumps = [[1, 38], [4, 14], [9, 31], [21, 42], [28, 84], [36, 44],         [51, 67], [71, 91], [80, 100],         [16, 6], [47, 26], [49, 11], [56, 53], [62, 19], [64, 60],         [87, 24], [93, 73], [95, 75], [98, 78]]board = list(range(101))for jump in jumps:    board[jump[0]] = jump[1] def play_game(board):    square = 0    turns = 0    while square < 100:        roll = random.randint(1, 6)        turns = turns + 1        if square + roll <= 100:            square = board[square + roll]    return turns games = []for i in range(10000):    games.append(play_game(board)) print('Average:', sum(games) / len(games), 'turns')print('Shortest:', min(games), '  Longest:', max(games)) counts = [0] * (max(games) + 1)for g in games:    counts[g] = counts[g] + 1most = counts.index(max(counts))print('Most common:', most, 'turns, in', counts[most], 'games') over = 0for g in games:    if g > 100:        over = over + 1print('Over 100 turns:', over, 'games')

Average: 39.1898 turnsShortest: 7   Longest: 322Most common: 24 turns, in 272 gamesOver 100 turns: 280 games

Change the board

A simulation can answer “what if?” questions about a board that doesn’t exist yet. What happens if we add a ladder? Surely games get shorter. And if we add a snake, longer. Here is a test: a tiny new ladder from 79 to 81, and, separately, a tiny new snake from 29 to 27.

import randomrandom.seed(1) jumps = [[1, 38], [4, 14], [9, 31], [21, 42], [28, 84], [36, 44],         [51, 67], [71, 91], [80, 100],         [16, 6], [47, 26], [49, 11], [56, 53], [62, 19], [64, 60],         [87, 24], [93, 73], [95, 75], [98, 78]]board = list(range(101))for jump in jumps:    board[jump[0]] = jump[1] def play_game(board):    square = 0    turns = 0    while square < 100:        roll = random.randint(1, 6)        turns = turns + 1        if square + roll <= 100:            square = board[square + roll]    return turns def average(board):    total = 0    for i in range(10000):        total = total + play_game(board)    return total / 10000 print('The board as it is:      ', average(board)) board[79] = 81      # a new ladder, from 79 up to 81print('With a ladder 79 to 81:  ', average(board))board[79] = 79      # take it off again board[29] = 27      # a new snake, from 29 down to 27print('With a snake 29 to 27:   ', average(board))

The board as it is:       39.1898With a ladder 79 to 81:   41.8118With a snake 29 to 27:    38.0584

• The average game is about 39 turns, but the most common games are much shorter, in the 20s. The shortest game in 10,000 took 7 turns; the longest took 322. About 3 games in every 100 took more than 100 turns. A game of snakes and ladders is short more often than long, but when it is long, it is very long: the long tail.
• A ladder made the game longer. The new ladder from 79 to 81 added more than 2 turns to the average. A counter on 79 used to have a chance of rolling a 1 onto square 80, the best ladder on the board. The new ladder carries it past 80, so that chance is lost.
• A snake made the game shorter. The snake from 29 to 27 cut more than a turn. A counter that would have walked past 28 is sent back to 27, and gets a second chance to land on 28 and climb to 84.

Nobody would guess the last two. The program doesn’t guess: it plays. That is the power of a simulation: ask “what if?” of a board, a bus timetable or the weather, and play it out thousands of times.

Without rolling a die

Can the average be worked out exactly, with no luck at all? Imagine not one counter but a huge crowd of players on the start square, say 6 × 6 × 6 × 6 × 6 × 6 × 6 = 279,936 of them. On the first turn, a sixth of them roll each number, so the crowd splits into six equal groups. On the next turn each group splits into six again, and so on. Players who reach 100 leave the board. Counting how many leave on each turn gives the exact average, with no random numbers at all.

jumps = [[1, 38], [4, 14], [9, 31], [21, 42], [28, 84], [36, 44],         [51, 67], [71, 91], [80, 100],         [16, 6], [47, 26], [49, 11], [56, 53], [62, 19], [64, 60],         [87, 24], [93, 73], [95, 75], [98, 78]]board = list(range(101))for jump in jumps:    board[jump[0]] = jump[1] players = [0] * 101      # how many players stand on each squareplayers[0] = 6 ** 7      # 279,936 of them, all at the startstart = players[0]average = 0for turn in range(1, 501):    moved = [0] * 101    for square in range(100):        for roll in range(1, 7):            if square + roll <= 100:                to = board[square + roll]            else:                to = square            moved[to] = moved[to] + players[square] / 6    finished = moved[100]    if turn <= 8:        print('Turn', turn, ':', round(finished), 'players finish')    average = average + turn * finished / start    moved[100] = 0    players = movedprint('Average:', round(average, 3), 'turns')print('Still playing after 500 turns:', round(sum(players), 3))

Turn 1 : 0 players finishTurn 2 : 0 players finishTurn 3 : 0 players finishTurn 4 : 0 players finishTurn 5 : 0 players finishTurn 6 : 0 players finishTurn 7 : 423 players finishTurn 8 : 1212 players finishAverage: 39.225 turnsStill playing after 500 turns: 0.001

The crowd’s average, 39.225 turns, is the exact answer, and your 10,000 random games came within a few hundredths of it. No player finishes in fewer than 7 turns, and only 423 of 279,936 do it in exactly 7: about 1 game in 660. (Mathematicians call a game like this, where the next move depends only on where you are now, a Markov chain, after the Russian mathematician Andrey Markov.)

In 1993 three mathematicians, Steve Althoen, Larry King and Kenneth Schilling, published “How Long Is a Game of Snakes and Ladders?” in The Mathematical Gazette. They worked out this board exactly and found an average of about 39.2 turns, about 41.9 with a ladder from 79 to 81, and about 38.0 with a snake from 29 to 27: the numbers your programs found. They also found that a board with no snakes or ladders at all takes about 33 turns (try it: jumps = []). The snakes lengthen the game more than the ladders shorten it.

Other ways to finish. Many families don’t play the exact-landing rule. In your play_game, let any roll that reaches or passes 100 finish the game. What happens to the average? And in another version you bounce back: from 97, a roll of 5 goes 3 squares forward to 100 and 2 back, to 98 (that is Challenge ★). Which rule makes the longest games?

Real games have two or more players, and the game ends when the first one reaches 100. Change your program to play two play_games and keep the smaller. Is a two-player game shorter or longer than one player’s? Does the player who goes first win more often?

An open question for you: the worst board. You are designing a board with 100 squares, and you may place one ladder and one snake anywhere. Where would you put them to make the longest average game? The shortest? Your average(board) can test any idea in seconds. (For the board on this page, which single new snake makes games shortest? You have seen that a snake can.)

★ Bounce back (blocks)

In this version of the game, a roll that goes past 100 bounces back: from 97, a roll of 5 goes 3 forward to 100 and 2 back, to 98. Finish the program so that it says the new square (leave out the snakes and ladders here). Then press Test.

★★ Replay a game (Python, from Grade 8)

Write finish(jumps, rolls): given a board’s jumps (a list of [from, to] pairs, like jumps above) and the rolls of one game in order, give back the turn on which the counter reaches 100, or -1 if the rolls run out first. Use the rule on this page: a roll past 100 is wasted.

def finish(jumps, rolls):    # give back the turn the counter reaches 100, or -1    return -1 print(finish([[80, 100]], [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2]))

★★★ The shortest possible game (Python, from Grade 8)

Write shortest_game(jumps): the fewest turns in which a game on that board can possibly finish (with the luckiest rolls). Every test board can be finished.

def shortest_game(jumps):    # the fewest turns in which a game can reach 100    return 0 print(shortest_game([]))

• Grade 6, Information and Data: bar charts, like the one of 10,000 games.
• Grade 8, Decisions and Loops in Python: the while loop that plays one game.
• Grade 10, Data Science: simulations of a ticket counter, and how to check that a simulation is right.
• Grade 11, Modelling and Simulation: a ball, a planet and an epidemic, simulated one step at a time.
• Grade 8, Functions: functions like play_game that give back an answer.
• How do you always win at Nim? Another game, but one where luck plays no part and a program can play perfectly.