snakes_probability


snakes_probability, an Octave code 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.

Licensing:

The computer code and data files made available on this web page are distributed under the MIT license

Languages:

snakes_probability is available in a MATLAB version and an Octave version.

Related Data and Programs:

snakes_probability_test

dice_simulation, an Octave code which simulates n tosses of m dice, making a histogram of the results.

duel_simulation, an Octave code which simulates n repetitions of a duel between two players, each of whom has a known firing accuracy.

fair_dice_simulation, an Octave code which simulates n tosses of 2 dice, making a histogram of the results.

gamblers_ruin_simulation, an Octave code which simulates the game of gambler's ruin.

high_card_simulation, an Octave code 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, an Octave code 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, an Octave code which simulates a poisson process in which events randomly occur with an average waiting time of lambda.

random_walk_1d_simulation, an Octave code which simulates a random walk in a 1-dimensional region.

random_walk_2d_avoid_simulation, an Octave code which simulates a self-avoiding random walk in a 2-dimensional region.

random_walk_2d_simulation, an Octave code which simulates a random walk in a 2-dimensional region.

random_walk_3d_simulation, an Octave code which simulates a random walk in a 3-dimensional region.

reactor_simulation, an Octave code 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, an Octave code which simulates the spinning of a roulette wheel and the evaluation of certain common roulette bets.

sir_simulation, an Octave code 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, an Octave code which simulates the game of snakes and ladders.

snakes_bar, an Octave code 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, an Octave code 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, an Octave code which computes the transition matrix for snakes and ladders

traffic_simulation, an Octave code which simulates the cars waiting to get through a traffic light.

truel_simulation, an Octave code which simulates n repetitions of a duel between three players, each of whom has a known firing accuracy.

Author:

Desmond Higham, Nicholas Higham

Reference:

  1. Steve Althoen, Larry King, Kenneth Schilling,
    How long is a game of Snakes and Ladders?,
    The Mathematical Gazette,
    Volume 77, Number 478, March 1993, pages 71-76.
  2. Nick Berry,
    A Mathematical Analysis of Snakes and Ladders,
    https://www.datagenetics.com/blog/november12011/index.html
  3. Desmond Higham, Nicholas Higham,
    MATLAB Guide,
    SIAM, 2005,
    ISBN13: 9780898717891.

Source Code:


Last modified on 01 July 2023.