SNAKES_AND_LADDERS
Game Simulation

SNAKES_AND_LADDERS, C programs which investigate 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.

It is a simple exercise to create a simulation of the game for several players.

Since the game is essentially a race, with no other competition between the players, it can be studied in a simplified version in which there is only one player.

For the one-player version of the game, it is interesting to pose the question of the average length of a game, that is, how many rolls of the die it takes in order to reach the final square.

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 GNU LGPL license.

Languages:

SNAKES_AND_LADDERS is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

DUEL_SIMULATION, a C program which simulates N repetitions of a duel between two players, each of whom has a known firing accuracy.

FAIR_DICE_SIMULATION, a C program which simulates N tosses of 2 dice, making a histogram of the results.

HIGH_CARD_SIMULATION, a C 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 C 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 C library which simulates a Poisson process in which events randomly occur with an average waiting time of Lambda.

REACTOR_SIMULATION, a C 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."

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,
   http://www.datagenetics.com/blog/november12011/index.html
3. Desmond Higham, Nicholas Higham,
   MATLAB Guide,
   SIAM, 2005,
   ISBN13: 9780898717891.

Source Code:

• snakes_and_ladders.c, the source code.
• snakes_and_ladders.h, the include file.

Examples and Tests:

• snakes_and_ladders_test.c, a sample calling program.
• snakes_and_ladders_test.txt, the output file.

Some graphics files are created.

• snakes_commands.txt, GNUPLOT command file.
• snakes_data.txt, GNUPLOT data file.
• snakes_and_ladders.png, a PNG image of the sparsity structure of the transition matrix.

List of Routines:

• SNAKES sets up the Snakes and Ladders matrix.
• SPY_GE plots a sparsity pattern for a general storage (GE) matrix.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the C source codes.