snakes_and_ladders, a C code which provides tools for studying 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.
The information on this web page is distributed under the MIT license.
snakes_and_ladders is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version and a Python version.
c_simulation, a C code which uses simulation to study card games, contests, and other processes which have a random element. Usually, the purpose is to try to predict the average behavior of the system over many trials.