Chutes, ladders, and Markov chains
The classic board game of Snakes and Ladders (or Chutes and Ladders) originated almost 2000 years ago in India, where it is known as Moksha Patam (see below). A turn of the game consists of a player throwing a random number between 1 and 6, and advancing a token by that number of squares. If the token ends up at the top of a snake (or chute) then the token slides to the bottom of the chute. Conversely, if the token ends up at the bottom of a ladder, then the token immediately advances to the top of the ladder. The winner is the first player to reach the square numbered 100.
Snakes and Ladders is entirely a game of chance, which makes it suitable for small children but not very exciting for anyone else. However, the game is of some mathematical interest because it is an example of a Markov chain. This means that the state of the game after the next move depends only on the previous state and the outcome of a random event; the prior history of the game is irrelevant. If we regard Snakes and Ladders as a one player game, then the game has 100 states, depending on which square the token currently occupies. State 100 is an absorbing state, which means that once this state has been reached, no further change is possible. It is also important that there are no other absorbing states, because we do not want a situation where a token is stuck indefinitely on another square.
The recent paper On the Game of Moksha-Patam by Aninda Kumar Nanda and Amit Kumar Misra enumerates and classifies the possible Snakes and Ladders boards. The board on the left of the picture above is an example of an unwinnable board. The problem with this board is that there is a sequence of six chutes on squares 94 up to 99, and it is not possible to avoid all of them, even by throwing a six. It is therefore impossible to reach square 100, and playing the game is futile. The board on the right is an example of an occasionally winnable board. If a player is lucky enough to land on square 2 on the first turn, that player will advance to square 99 and eventually complete the game. Unfortunately, if the player passes the ladder on square 2, there is no hope of completing the game, because the sequence of six chutes on squares 54 to 59 will prevent further advancement.
The best kind of board is the ultimately winnable board. These are boards in which a player is guaranteed to reach 100 eventually if enough turns are played. An uninteresting example of an ultimately winnable board is the blank board with no chutes and no ladders. The board shown on the right of the above picture is also ultimately winnable. This is not completely obvious, but follows from one of the results in the paper.
Before making a detailed analysis of the possible Snakes and Ladders boards, it helps to make some simplifying assumptions. There is no need to have a board in which the end of one chute or ladder immediately connects to another chute or ladder, and if such a feature appears, it is possible to design a functionally equivalent board that lacks the feature in question. For example, on the board at the top of the diagram above, square 79 is both the end of a chute starting at 84, and the start of a ladder ending at 98. This is functionally equivalent to having two ladders, one running from 79 to 98, and one running from 84 to 98.
The authors come up with a classification of ultimately winnable, occasionally winnable, and winnable boards. Using these results, it can be shown that the board above and to the left is ultimately winnable, whereas the board above and to the right is unwinnable. Notice that in the board on the right, the ladder from 41 to 81 is useless because it is not actually possible to reach square 41. It is, however, possible to get stuck forever between squares 52 and 79.
In the standard Milton Bradley version of Chutes and Ladders, shown above, it is known that a player will need an average of 39.2 spins to move from the starting point (essentially “square zero”) to square 100. A two player game has a mean length of 47.76 moves, and the probability that the first player to move will win is 50.9%. The authors show that the total number of Snakes and Ladders boards exceeds 6×1093, even after assumptions that no chutes or ladders share an exit. They also show that at least 88% of these boards are ultimately winnable.
Picture credits and relevant links
The Moksha Patam picture is by Jain Miniature, and appears on Wikipedia.
The photograph of the 1997 Milton Bradley version of Chutes and Ladders is my own.
The other graphics are edited versions of pictures from the paper by Aninda Kumar Nanda and Amit Kumar Misra.
Wikipedia has pages about Snakes and Ladders and Markov chains.
Substack management by Buzz and Hum.
.
This is so interesting! I never considered maths and board games to be interlinked in such fascinating ways. A food for thought. Thank you so much for this!
Excellent! Reporting on the mathematics of games is of considerable interest and relevance.