Chutes and Ladders
Description
In this game, the players take turns spinning a wheel numbered 1-6 and moving the specified number of spaces on the board, which are numbered 1-100. The object of the game is to land on the last square (labeled #100). During the game, if you land on a chute or ladder, you will move backward or foreward, respectively, a certain number of squares determined by the endpoint of the chute/ladder. If, when nearing the 100th square, you overshoot by spinning a number greater than that of the remaining number of squares on the board, you lose your turn; or in other words, you have to keep spinning until you land on 100.
In this project, we analyze the game length using a Markov chain, by considering each square as a state in state space. We construct a 101x101 transition matrix corresponding to each of the 100 squares, as well as the null square corresponding to the beginning, i.e., players do not start on the board. There are 9 ladders and 10 chutes. We only consider a single player in this analysis.
Downloads
Results
- Minimum game length: 7
- Expected game length: 39.5984
- Maximum game length: Unbounded
- 50th percentile (median): 32
- 95th percentile: 89
- 25th percentile: 21
- 75th percentile: 49
Discussion
Markov chains are square matrices which describe probabilistic transitions between states. The (i,j) component of the matrix A corresponds to the probability that a player can get to the i-th square from the j-th square in one turn. Hence, in the absence of the chutes and ladders, the matrix A is a diagonal strip of non-zero entries immediately below the diagonal (this is called a band matrix). By adding chutes and ladders, the band entries swap their non-zero terms with the squares of the endpoints of the respective chute/ladder, and hence, non-zero terms spread somewhat throughout the matrix.
An important problem in the universe of Chutes and Ladders problems is to know roughly how long it takes to finish the game. Small children are unlikely to be willing to play a game that goes on and on. One may notice that the (101,1) entry in the matrix is zero. This means that the probability of the game ending on the first spin is zero, i.e., it is impossible for the game to end after one spin. To determine the probability that the game ends on the second spin, we can look at the (101,1) term of A^2=A x A -- this will also be zero. However, repeating this, we find a non-zero entry for A^7. This means that it is possible for the game to end after 7 moves. By iterating powers of A, we can find the probabilities of the game ending for each number N. We plot this below (probability density function).
We remark that since A is a 101x101 matrix, it's not practical to analyze powers by hand. Hence, we employ Matlab to compute for us (see link for Matlab code above).
There is no maximum game length. In other words, it's theoretically possible for a game of Chutes and Ladders to last forever. However, it is not likely. Hence, to answer the impending question of how long does it take to play a game of Chutes and Ladders, we look at the probability distribution function and report the percentile rankings. We see that half of the players will finish the game in 32 (or less) spins. We also see that 95 percent of the time, the game will not exceed 89 spins. We also see that the middle range is between 21 and 49 spins.
