Snakes and ladders analysis using a transition matrix in R

snakes_and_ladder_board.csv

snakes_and_ladders.txt

setwd("C:\\path\\to\\board\\definition\\")

# matrix(1:9, nrow=3, byrow=TRUE)
# [row, column]
# 


# adds the movement from a die roll at a given position
add_roll <- function(transition_matrix, die_movements, die_odds, position) {
  for (i in seq(1, length(die_movements))) {
    target_index = position + die_movements[i]
    if (target_index > length(transition_matrix[1,])) {
       # if overshooting still counts as a win
       #target_index = length(transition_matrix[1,])
       # or if you have to get an exact match:
       target_index = position
    }
    transition_matrix[target_index, position] = transition_matrix[target_index, position] + die_odds[i]
  }
  return(transition_matrix)
}

# adds a snake or ladder to the board
# only difference is whether start or end is higher
add_snake_or_ladder <- function(transition_matrix, start_pos, end_pos) {
  transition_matrix[end_pos, ] = transition_matrix[end_pos, ] + transition_matrix[start_pos, ]
  transition_matrix[start_pos, ] = rep(0, length(transition_matrix[start_pos, ]))
  return(transition_matrix)
}


board_size = 100
# transition matrix of board
# board_trans[x, y] represents odds of moving from y to x
board_trans = matrix(0, nrow = board_size, ncol = board_size)

# define dice probabilities
# die_movements is distance each roll moves, die_odds is odds of getting that value
# this is basic six-sided die
die_size = 6
die_movements = c(1:die_size)
die_odds = c(rep(1/die_size, die_size))

# add movement from die to each square of board
for (i in seq(1, board_size)) {
  board_trans = add_roll(board_trans, die_movements, die_odds, i)
}

# add any snakes and ladders to the board
# this allows them to be defined by a csv file of start and end squares
# I based my csv file on this board on wikipedia:
#  https://en.wikipedia.org/wiki/Snakes_and_ladders#/media/File:Berrington_Hall_-_snakes_and_ladders_(13826426425).jpg

snakes_and_ladders <- read.csv("snakes_and_ladder_board.csv")

for (i in seq(1,length(snakes_and_ladders$start))) {
  board_trans = add_snake_or_ladder(board_trans, snakes_and_ladders$start[i], snakes_and_ladders$end[i])
}


# initialize board state
# board_state[x] is the odds that the piece is at position x
board_state = rep(0, board_size)
board_state[1] = 1 # start on first square

# median number of rolls to reach end
count = 0
target_odds = 0.5

while (board_state[board_size] < target_odds) {
  count = count + 1
  # apply one move
  board_state = board_trans %*% board_state
}

board_state
count # number of moves needed to reach the end