Snakes and Ladders and Transition Matrices

Recently, /u/mikeeg555 created this post  on the statistics subreddit with their results from a simulation of 10,000,000 games of this instance of Snakes and Ladders. This is the sort of information that's good to show in an undergrad or senior secondary level classroom as a highlight of the sort of insights you can get from the kind of simulation that anyone can program.

It's a good exercise, but it got a lot of attention because, for some reason, not a single simulation found a game that ended in either exactly 129 or in exactly 251 turns. There were more than a thousand games that finished in 128 turns, and more than a thousand that finished in 130, but none for 129. The frequency of number of turns required resembled a smooth gamma distribution other than those two gaps. There were no unusually common responses to make up for the gaps. There were no further gaps at 258 (129 + 129), 387 (129 + 129 + 129), or 390 turns (129 + 251). Nothing except these two gaps was remarkable.

Why? How? Was there some cyclic, finite state, quirk to these turn counts? Was there an error in the original poster's code?

The code wasn't given until two hours after in an update, but within that time, three others had independently written programs to confirm or refute this:

/u/threenplusone, who wrote a simulator

/u/hootback , who wrote a program to calculate transition matrices in Python,

and myself, who wrote a transition matrix program in R, shown below:

None of us found the gap. (Answer why at bottom)

Transition matrices are a particularly nice way to 'solve' games like Snakes and Ladders because they give the probabilities of moving from one state (i.e. square) in a single turn. Another nice property is that you can make a new transition matrix of a pair of transitions by multiplying the matrices. We can describe a turn of snakes and ladders as two transitions:

1) A move of 1-6 spaces ahead, based on the roll of a fair 6-sided die, and, if relevant

2) A move from the bottom of a ladder to its end, or the tail of a snake to its head.

The first transition is a 100x100 matrix with six values of 1/6 in each row, and 94 values of 0. The second transition, the interaction with the board, is mostly a diagonal matrix of 1's for all the squares without a snake or ladder. When there IS a snake or ladder, the matrix row with the ladder bottom or snake tail has a value of 1 at the ladder top or snake head, and a zero on the diagonal entry. It's important to note that, at least in this version of the game, every ladder and snake leads to a square without any additional ladders and snakes.

To find the chance of getting from square i to square j in one turn, consult turn_matrix, which is the product of roll_matrix and SL_matrix (snake-ladder matrix). To find the chance in k turns, multiply turn_matrix by itself k times, and then consult entry (i,j)

Nsq = 100 # a 100 square snakes and ladders board

die_probs = rep(1/6,6) # a fair 6-sided die

die_size = length(die_probs)

roll_mat = matrix(NA,nrow=Nsq,ncol=Nsq) # transition matrix of rolls

SL_mat = matrix(0,nrow=Nsq,ncol=Nsq) # transistion matrix of snakes and ladders application

for(this_sq in 1:Nsq)

{

roll_count = 1

## Get the outcomes of a roll from square sq

roll_vec = rep(0,Nsq)

roll_vec[this_sq+(1:die_size)] = die_probs # apply the die probs

## Handle past-the-end rolls

if( length(roll_vec) > Nsq)

{

## Rule 1: Past the end --> the end

##over_prob = sum(roll_vec[-(1:Nsq)])

##roll_vec[Nsq] = roll_vec[Nsq] + over_prob

## Rule 2: Exact roll needed for end

over_prob = sum(roll_vec[-(1:Nsq)])

roll_vec[this_sq] = roll_vec[this_sq] + over_prob

## Rule 3: 'bounce' the over-roll. (Example, over-roll by 2 will end 2 squares from the end)

#over_prob_vec = roll_vec[-(1:Nsq)]

#Nover = length(over_prob_vec)

#roll_vec[(Nsq-1):(Nsq-Nover)] = roll_vec[(Nsq-1):(Nsq-Nover)] + over_prob_vec

## ALL RULES Truncate the roll vector back to the existing squares

roll_vec = roll_vec[1:Nsq]

}

## apply this vector to the matrix

roll_mat[this_sq,] = roll_vec

}

SL_mat[4,14] = 1 ## There is a ladder from 4 to 14, which is always taken

SL_mat[9,31] = 1

SL_mat[20,38] = 1

SL_mat[28,84] = 1

SL_mat[40,59] = 1

SL_mat[51,67] = 1

SL_mat[63,81] = 1

SL_mat[71,91] = 1

SL_mat[17,7] = 1 # A snake from 17 to 7

SL_mat[54,34] = 1

SL_mat[62,19] = 1

SL_mat[64,60] = 1

SL_mat[87,24] = 1

SL_mat[93,73] = 1

SL_mat[95,75] = 1

SL_mat[99,78] = 1

## All other squares lead to themselves

diag(SL_mat) = 1 - apply(SL_mat,1,sum)

#SL_mat = t(SL_mat) ## Row and columns are to-from, not from-to

### A turn consists of a roll and a snake/ladder. Only one snake or ladder/turn

turn_mat = roll_mat %*% SL_mat

### Get the game completion chance after k turns

game_length = 500

win_by_prob = rep(NA,game_length)

win_by_prob[1] = 0

kturns_mat = turn_mat

### kturns_mat[i,j] will give you the probability of ending on square j, starting on square i, in exactly k turns.

for(k in 2:game_length)

{

kturns_mat = kturns_mat %*% turn_mat

win_by_prob[k] = kturns_mat[1,Nsq]

}

win_at_prob = c(0,diff(win_by_prob))

sum(win_at_prob) ## Mean turns to finish

which(win_at_prob == 0) ## Impossible number of turns to finish

Answer: The original poster's code contained a plotting error, not a mathematical one. The gaps were an artifact of the binning system for the histogram used, which left the occasional empty bin.

Cunningham's Law states that “The best way to get the right answer on the Internet is not to ask a question, it's to post the wrong answer.” This post is a fine example, even if it was unintentional.