SNAKES_PROBABILITY, a MATLAB program which computes the game length probabilities for Snakes and Ladders, by Desmond Higham and Nicholas Higham.
Snakes and Ladders is a children's game played on a 10x10 numbered board. A player's turn consists of rolling a single die, and moving the indicated number of squares. If the final square is the foot of a ladder, the player moves up to a higher numbered square. If the final square is the mouth of a snake, the player moves downward.
For the one-player version of the game, it is interesting to pose the question of the probability that a particular game will take a certain number of moves.
By adding a square 0, where the player begins, the game board can be modeled as a vector of length 101, and the transitions from one square to another can be modeled by a transition matrix. Most commonly, the entries in row I will be zero except that columns I+1 through I+6 will have the value 1/6. However, rows which correspond to a snake or ladder, and rows for which I+6 is greater than 100, must be handled specially.
Given the transition matrix A, the one player game can be modeled as a Markov Chain Monte Carlo system. In particular, given an initial starting vector v, the probability distribution after one move is the vector A' * v, and repeated multiplication by A' will display the exact probability distribution at every step.
The computer code and data files made available on this web page are distributed under the GNU LGPL license.
SNAKES_PROBABILITY is available in a MATLAB version.
DICE_SIMULATION, a MATLAB program which simulates N tosses of M dice, making a histogram of the results.
DUEL_SIMULATION, a MATLAB program which simulates N repetitions of a duel between two players, each of whom has a known firing accuracy.
FAIR_DICE_SIMULATION, a MATLAB program which simulates N tosses of 2 dice, making a histogram of the results.
GAMBLERS_RUIN_SIMULATION, a MATLAB program which simulates the game of gambler's ruin.
HIGH_CARD_SIMULATION, a MATLAB program which simulates a situation in which you see the cards in a deck one by one, and must select the one you think is the highest and stop.
ISING_2D_SIMULATION, a MATLAB program which carries out a Monte Carlo simulation of an Ising model, a 2D array of positive and negative charges, each of which is likely to flip to be in agreement with neighbors.
POISSON_SIMULATION, a MATLAB library which simulates a Poisson process in which events randomly occur with an average waiting time of Lambda.
RANDOM_WALK_1D_SIMULATION, a MATLAB program which simulates a random walk in a 1-dimensional region.
RANDOM_WALK_2D_AVOID_SIMULATION, a MATLAB program which simulates a self-avoiding random walk in a 2-dimensional region.
RANDOM_WALK_2D_AVOID_TASKS, a MATLAB program which computes many self avoiding random walks in a 2-dimensional region by creating a job which defines each walk as a task, and then computes these independently using MATLAB's Parallel Computing Toolbox task computing capability.
RANDOM_WALK_2D_SIMULATION, a MATLAB program which simulates a random walk in a 2-dimensional region.
RANDOM_WALK_3D_SIMULATION, a MATLAB program which simulates a random walk in a 3-dimensional region.
REACTOR_SIMULATION, a MATLAB program which is a simple Monte Carlo simulation of the shielding effect of a slab of a certain thickness in front of a neutron source. This program was provided as an example with the book "Numerical Methods and Software."
ROULETTE_SIMULATION, a MATLAB program which simulates the spinning of a roulette wheel and the evaluation of certain common roulette bets.
SIR_SIMULATION, a MATLAB program which simulates the spread of a disease through a hospital room of M by N beds, using the Susceptible/Infected/Recovered (SIR) model.
SNAKES_AND_LADDERS, a MATLAB program which simulates the game of Snakes and Ladders.
SNAKES_BAR, a MATLAB library which produces bar charts of the count, PDF and CDF estimates for the length of a one-player game of Snakes and Ladders, produced by simulating N games.
SNAKES_HISTOGRAM, a MATLAB library which produces histograms of the count, PDF and CDF estimates for the length of a one-player game of Snakes and Ladders, produced by simulating N games.
SNAKES_MATRIX, a MATLAB program which computes the transition matrix for Snakes and Ladders
TRAFFIC_SIMULATION, a MATLAB program which simulates the cars waiting to get through a traffic light.
TRUEL_SIMULATION, a MATLAB program which simulates N repetitions of a duel between three players, each of whom has a known firing accuracy.
Desmond Higham, Nicholas Higham
You can go up one level to the MATLAB source codes.
