Snakes and Ladders

Imagine you are playing snakes and ladders, and you would like to know:

• Q: how many rolls would you expect before you finish.

This latter question can be resolved by writing the snakes and ladders game as a directed graph, and understanding the game as a markov chain. It has been solved in the following paper

• How Long is a Game of Snakes and Ladders?

(S. C. Althoen, L. King, K. Schilling, The Mathematical Gazette, Vol. 77, No. 478 (Mar., 1993), pp. 71-76)

Another question is about infinite snakes and ladders. Suppose when you get to the end you loop around and start playing again. Then if you play for a long time, what is the invariant measure? Meaning, what fraction of the time would you expect to spend at each square.

This last question can be solved by solving a linear equation, which is related to the markov chain. A similar equation is solved by Google on the web graph for PageRank.

Snakes and Ladders with Options

Now consider several modification of the game.

Several obvious modifications are:

• One time during the game, you get a free roll, meaning, if you don't like your roll, you can roll again.
• One time during the game, you can choose your roll (i.e. pick the number on the die, instead of rolling)
• At each roll, you could choose between rolling a die, or flipping a coin (to move only 1 or 2 squares).

Natural questions are: how much do these options help you (i.e. how much faster would you expect to finish), and when is the best time to exercise these options.

• Q: when would you want to flip the coin?
• Q: playing optimally, how much does the option buy you?

These questions can be answered using the theory of dynamic programming (on Markov chains). These questions come up in scheduling, where the decision maker is faced with a choice of controlling a process with some randomness.

Another questions is the invariant measure for the infinite game. How long do you expect (on average) to spend at each square, if you play many games.