Chutes And Ladders Game Design

If you grew up in India like me, Snakes and Ladders was possibly an integral part of your childhood experience. For my friends who grew up in the United States you might have played its analog - Chutes and Ladders.

Snakes and Ladders is a multiplayer game:

1. The usual board is a grid of 10x10 squares numbered from 1-100. The board has snakes with their head and tail on different squares. The board has ladders with their lowest rung and top most rung on different squares.
2. All players start at a square marked 1.
3. Each player throws a die taking turns. The turn sequence is maintained constant for a game.
4. Each player moves 'n' number of steps where 'n' is the face of the die that is thrown up. If the square on which the player has moved to has a "snake" head then the player moves to the tail of the snake. If the square on which the player has moved to has the lowest rung of the "ladder", then the player climbs to the square on the top of the ladder.
5. There are two possible finish rules: One is that the player to reach 100 exactly first is the winner. The other possible finish rule is that the player to reach or cross 100 first is the winner.

A couple of salient points about this game is that:

• though presented on a two dimensional board, the moves travel on a linear path i.e., this can be mapped onto a line;
• one player's move does not affect the other players' game unless it is the winning move where the game ends.

Designing The Game

Suppose we were to design this game how would we go about designing this game:

1. What parameters do we have to play with?
2. What is an optimal game?

The parameters available are:

1. Grid size
2. Snakes and Ladders: Number and Position
3. Die: the number of faces and the probability of each face.

An optimal game would be the one that:

Takes neither too long or too short of a time on an average to complete.

Takes neither too many nor too few "ladder climbs" and "snake falls" on an average.

Exploring the landscape

Before we embark on optimization, let us begin with exploring the landscape.

Neither A Snake Nor A Ladder

Consider a board of size 4x4 with no ladder or snake. Let us use a 2 sided fair die (essentially a coin) to reach to the end point of 16. There are no "ladder climbs" or "snake falls" to look at.

How many die throws on an average does it take for a player to reach the 16th square assuming a completion rule of greater than or equal to 16? On doing a computer simulation of 10000 plays of the game we get a histogram that looks like this:

The median number of throws of the fair two sided die that the player needs is 11 throws (assuming throw 1 is the starting point of box 1) to complete the board.

To gain some insight into the mathematics guiding this we can construct an "Absorbing Markov Chain" [1] with the following transition probability matrix T. Each element is defined as:

the conditional probability of moving to Box j given that we are in Box i

The value behind this is as follows:

1. From box 1 to box 2 there is a probability of 1/2 as we have a fair die. From box 1 to box 3 there is a probability of a 1/2 as well.
2. Box 2 - Box 3 transition probability of 1/2. Box 2 - Box 4 transition probability of 1/2.
3. In general for N< 15: Box N - Box N+1 transition probability of 1/2. Box N - Box N+2 transition probability of 1/2.
4. For N=15: The next throw of the die whatever be it we will reach the finish criterion and the Box 16. So probability is 1 for Box 15 to Box 16.
5. Once the value of a player reaches 16 there is no more movement. Hence 16 is the absorbing state.

Given the positional probability distribution of each box in a vector p where

the probability of the player being in the box i. Using this we can find the next turns probability distribution np for the player as

the probability of finding the player in box j in the next turn is the sum of probabilities of being in a box (i) times the transition probability of moving to box j from that box (i). This is essentially a vector times the transition matrix.

np=p.T

.The next position after np will have a probability distribution nnp given by

nnp=p.T.T

. Generalizing this if we begin with a probability distribution:

because we start at Box 1 with an absolute certainty then the "t+1"th turn will have the distribution given by

. The progression of probability distributions is shown as a heat map below:

Each row here is a probability distribution of the position of the player. We can see how there is a "turn on" of probability of reaching Box 16 from Turn 9. By Turn 11 we cross the probability of 0.5 and in subsequent turns it tends to 1. The values of the cumulative probability are shown below:

The expected number of turns to reach box 16 from box 1 can also be computed mathematically using the following technique [2].

Organize the transition probability matrix T into

From here we can get expected number of turns to reach the "absorbing" state i.e., the final box as:

where 1 represents a vector of 1s. We get the following expected turns to reach the final box as:

1-11, 2-10, 3-9, 4-9, 5-8, 6-7, 7-7, 8-6, 9-5, 10-5, 11-4, 12-3, 13-3, 14-2, 15-1

Here 1-11 represents the expected number of steps to reach 16th box from 1st box is 11. This is what was predicted by the histogram as well.

Single Ladder Board

What if we add a single ladder to this board, say from box 2 to box 9?

The distribution changes to:

a bimodal distribution one where the ladder is used and the other where the ladder is not used. Looking at the transition matrix for this scenario we get the following:

Any position that lands on box 2 automatically moves to 9. So transition probability from (1 to 2) is added to (1 to 9). Any transition from (2 to 3) or (2 to 4) does not exist anymore. So in essence we are going to do away with column and row for box "2".

This results in the following progression of probabilities.

We see the two pathways activated, one where the ladder is used and other where it is not used. The expected number of turns for this transition probability matrix is:

1-8, 3-9, 4-9, 5-8, 6-7, 7-7, 8-6, 7-5, 8-5, 9-4, 10-3, 11-3, 12-2, 13-1

where we can see if we start at 1 we have an expectation of 8 turns whereas if we were to start at 3 we expect a larger number of turns because we missed the ladder.

Single Snake Board

Now if we were to reverse the above ladder to form a snake from box 9 to box 2? Unlike a ladder, if we get bitten by the snake it does not make us immune to it again as we climb our way back up.

So unlike the bimodal distribution we observed earlier we will observe a merger of multiple distributions as shown below:

If one gets bitten by the snake multiple times, the number of throws required by the player increases quite a bit as is to be expected. This is a long right tailed distribution with the probability being lower as the number of snake use increases.

Looking at the transition matrix for this scenario we get the following:

Any position that lands on box 9 automatically moves to 2. So transition probability from (7 to 9) , (8 to 9) is added to (7 to 2), (8 to 2) respectively. Any transition from (9 to 10) or (9 to 11) does not exist anymore. So in essence we are going to do away with column and row for box "9".

This results in the following progression of probabilities.

We see the multiplicity of pathways activated, each where the snake bites multiple times.

Mathematically we can see the number of expected turns to reach the final box as:

1-20, 2-19, 3-19, 4-18, 5-18, 6-16, 7-17, 8-13, 10-5, 11-4, 12-3, 13-3, 14-2, 15-1

We see that it takes about 20 turns for us to complete the board. After we cross the head of the snake there is a large decrease in number of turns from 13 turns to 5 turns.

Conclusion

In summary, we observe that:

1. Expected number of turns to complete: a board with only a single ladder is less than a board with no ladder or a snake which in turn is less than a board with only a single snake.
2. A board with a ladder has two distributions for number of turns required to complete the board - one where the ladder is used and one where it is not used.
3. A board with a snake has a long right tailed distribution for number of turns required to complete the board because of repeated use of the snake with lower and lower probabilities.

Now for the study of what happens when we have boards with:

1. a snake of different length
2. a ladder of different length
3. a snake and a ladder interacting

Look out for part 2 of this blog for answers to this.

References

[1] Cheteyan, L.A., Hengeveld, S. and Jones, M.A., 2011. Chutes and Ladders for the impatient.The College Mathematics Journal,42(1), pp.2-8.

[2] https://en.wikipedia.org/wiki/Absorbing_Markov_chain

Chutes And Ladders Game Design

Source: https://www.linkedin.com/pulse/snakes-ladders-game-design-part-1-meenakshi-sundaram-manivannan

Posted by: allbrightwatermint.blogspot.com

Share this post