Instead of brute force simulation, we might think about the game probabilistically. On any given turn, there are six equally probable options: rolling a 1, 2, 3, 4, 5, or 6.
Depending on which space you start on, these lead to six well-defined results.
For example, the first turn, the possibilities are the squares 38, 2, 3, 14, 5, or 6, each with equal probability. We could encode this set of probabilities as a vector of length 101, with 1/6 in each associated index (here the zeroth element represents the start of the game, off of the board):
1 | |
Each entry in this vector is the probability of going from square zero to the corresponding square. This vector completely describes the first turn of the game.
Similarly, we could construct the vector describing turns from square 2:
1 | |
Again, this completely describes any turn of the game that starts at square two.
The key insight is that Chutes and Ladders is memoryless; if you’re on, say, square 19, it doesn’t matter if you got there by sliding down from square 62, or by rolling a five from square 14 – the probabilities on the next turn are exactly the same.
This kind of situation: a sequence of probabilistic transitions from one state to another with no memory of previous states, is known as a Markov Chain or Markov Process, and can be entirely described by a N x N transition matrix where N is the number of states in the system (101 states for Chutes and Ladders). The columns of the matrix contain the probability vectors we discussed above, such that element (n, m) is the probability of transitioning to element n when starting from element m.
Let’s create a Markov transition matrix for Chutes and Ladders: