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.

## No comments:

## Post a Comment