The Statistics of Chutes and Ladders

A Tech article with View Comments posted 7 July 2009.
Tags: games, statistics

Seeing this node on Chutes and Ladders over at PerlMonks, I thought it would be interesting to throw my hat into the ring. Chutes and Ladders can be represented as a time-homogenous Markov chain with 100 possible states. Each state transition can be represented in a matrix (size 100×100) of transition probabilities T, where T_ij is the probability of transitioning from state i to state j. Then you represent the probability of being in a certain state after a transition as the 1×100 matrix P, where for the beginning of the game (P_0) the first entry is 1 and the other ninety-nine are 0. ¹

From this, you get interesting, relatively easy to solve equations. For example, if you are in state P_0 (in the beginning of the game) then P_1 = T x P_0 (the matrix product). In fact, P_n = T x P_(n-1). That means that you can chain them together, so that P_n = T x T x … for n “Ts” … x T x P_0. ²

Most of the transition probabilities are just 1/6 (a fair spin of a six-valued spinner). ³ But when you hit a chute or ladder, your destination changes, which makes it much more interesting. ⁴ It also means that there are combinations of spins that could result in a game of infinite length.⁵

Some results:

1. According to the analytical approach, you should win in 7 turns 0.04% of the time. This is the fastest you can win, and disagrees with toolic’s empirical code significantly. Toolic estimated the probability at 0.15% (1,597 out of 1,000,000 games played). I don’t know where the discrepancy comes from.
2. There is a 50% chance that the game will end for a given player in 30 turns.
3. There is a 90% chance that the game will end for a given player in 68 turns.
4. The game does asymptotically converge to the end square, so while you could loop around forever, the chances of getting to turn 1000 are far lower than winning PowerBall several times.
5. If you rolled only 2, you would win in 30 moves. The chances of this happening are 1 in 10,737,41,824.
6. If you rolled only 4, you would win in 17 moves. The chances of this happening are 1 in 131,072.
7. If you rolled only 6, you would win in 20 moves. The chances of this happening are 1 in 1,048,576.
8. Rolling only 1, 3, or 5 results in infinite looping.

Here’s the perl code to do it. You’ll need to install Math::Matrix.

use strict;
use warnings;
use Math::Matrix;

my $matrix_size = 100;
my %transition = (
   # Ladders
   #  Start
         1  => {end =>  38, action => 'up ladder'},
         4  => {end =>  14, action => 'up ladder'},
         9  => {end =>  31, action => 'up ladder'},
        21  => {end =>  42, action => 'up ladder'},
        28  => {end =>  84, action => 'up ladder'},
        36  => {end =>  44, action => 'up ladder'},
        51  => {end =>  67, action => 'up ladder'},
        71  => {end =>  91, action => 'up ladder'},
        80  => {end => 100, action => 'up ladder'},
   # Chutes
   #  Start
        16  => {end =>   6, action => 'down chute'},
        48  => {end =>  26, action => 'down chute'},
        49  => {end =>  11, action => 'down chute'},
        56  => {end =>  53, action => 'down chute'},
        62  => {end =>  19, action => 'down chute'},
        64  => {end =>  60, action => 'down chute'},
        87  => {end =>  24, action => 'down chute'},
        93  => {end =>  73, action => 'down chute'},
        95  => {end =>  75, action => 'down chute'},
        98  => {end =>  78, action => 'down chute'}
);

# Define dice probabilities
my @dice_index = (0..6);
my @dice = (0, 1/6, 1/6, 1/6, 1/6, 1/6, 1/6);

# Create transition matrix
my $transition_matrix = Math::Matrix->new(map { [ map { 0 } (1..$matrix_size) ] } (1..$matrix_size));
foreach my $state (1..$matrix_size) {
    foreach my $dice_roll (@dice_index) {
        my $destination = $state + $dice_roll;
        if (exists $transition{ $destination }) {
            $transition_matrix->[ $transition{ $destination }{end} - 1 ][ $state - 1 ] += $dice[$dice_roll];
            next;
        }
        $destination = $matrix_size if $destination > $matrix_size;
        $transition_matrix->[ $destination - 1 ][ $state - 1 ] += $dice[$dice_roll];
    }
}

# Set initial state
my $state_probabilities = Math::Matrix->new(map { [0] } (1..$matrix_size));
$state_probabilities->[0][0] = 1;

# Loop through turns
my $turn = 0;
while($turn < 100) {
    $turn++;
    $state_probabilities = $transition_matrix->multiply( $state_probabilities );
    my $p_ending = $state_probabilities->[$matrix_size - 1][0];
    print "Game has $p_ending chance of ending after $turn turns.\n";
}

# Print results
$state_probabilities->print;