snakes_matrix


snakes_matrix, a MATLAB code which computes the transition matrix for the game of Snakes and Ladders.

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.

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 information on this web page is distributed under the MIT license.

Languages:

snakes_matrix is available in a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

snakes_matrix_test

chebyshev_matrix, a MATLAB code which defines the Chebyshev differentiation matrix, by Lloyd Trefethen.

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

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

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

gamblers_ruin_simulation, a MATLAB code which simulates the game of gambler's ruin.

high_card_simulation, a MATLAB 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, a MATLAB 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.

jordan_matrix, a MATLAB code which returns a random matrix in Jordan canonical form.

levenshtein_matrix, a MATLAB code which returns the Levenshtein distance matrix defined by two strings.

magic_matrix, a MATLAB code which computes a magic matrix, for any odd order n, such that all rows and columns have the same sum.

monopoly_matrix, a MATLAB code which computes the adjacency and transition matrices for the game of Monopoly.

plasma_matrix, a MATLAB code which sets up a matrix associated with a problem in plasma physics.

poisson_simulation, a MATLAB code which simulates a poisson process in which events randomly occur with an average waiting time of lambda.

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

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

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

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

reactor_simulation, a MATLAB 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."

risk_matrix, a MATLAB code which computes the transition and adjacency matrix for the game of risk.

roulette_simulation, a MATLAB code which simulates the spinning of a roulette wheel and the evaluation of certain common roulette bets.

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

snakes_probability, a MATLAB code which computes the game length probabilities for snakes and ladders, by desmond higham and nicholas higham.

tennis_matrix, a MATLAB code which computes the transition matrix for a game of tennis, which has 17 distinct states.

test_matrix, a MATLAB code which defines test matrices for which the condition number, determinant, eigenvalues, eigenvectors, inverse, null vectors, P*L*U factorization or linear system solution are known. Examples include the Fibonacci, Hilbert, Redheffer, Vandermonde, Wathen and Wilkinson matrices.

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

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

usa_matrix, a MATLAB code which defines the adjacency matrix for US states, using a variety of matrix formats.

wathen_matrix, a MATLAB code which compares storage schemes (full, banded, sparse triplet, sparse) and solution strategies (A\x, linpack, conjugate gradient (CG)) for linear systems involving the Wathen matrix, which can arise when solving a problem using the finite element method (FEM).

web_matrix, a MATLAB code which stores sample matrices describing a web page network. These matrices are typically very sparse, and the examples here are stored using the sparse triplet (ST) format. They can be used to demonstrate pagerank and other graph algorithms.

wishart_matrix, a MATLAB code which produces sample matrices from the Wishart or Bartlett distributions, useful for sampling random covariance matrices.

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

Source Code:


Last modified on 02 January 2020.