February 8, 2021

Climbing and Sliding

The origins of the game of Chutes and Ladders (or its Snakes and Ladders counterpart) go back many centuries to India and a board game called moksha patam (a Hindu concept that is akin to heaven and hell). Designed as a way of instructing children in religious values, the game graphically depicts the coexistence of good and evil and illustrates the impact of chance on human affairs.

In the game, checkerboard pilgrims follow a winding path that is shortened by virtuous deeds and lengthened by sinful acts or wrongdoing. They triumph when they climb ladders that represent faith, reliability, and generosity, and they fail when they slither down snakes that signify disobedience, vanity, and greed. A die dictates the fortunes of the road.

The game's design and rules have varied over the years. Typically, a grid ten squares long and ten squares wide, the game board features several ladders and snakes (or chutes). The number of shortcuts and detours, their length, and their placement all affect how the game proceeds.

A classic Indian design may have twelve snakes and eight ladders, with one long snake reaching back down to the starting square and a ladder of more modest length extending to the winning square at the top of the board.

In modern Western versions of the game, the moralizing usually takes on a gentler cast, and the snakes are often replaced by chutes (slides). Usually, the number of ladders equals the number of snakes, though in some upwardly mobile versions the ladders predominate.


Example of a Chutes and Ladders game board.

In most of these game designs, the distribution and number of snakes and ladders probably reflect trial-and-error experience when it comes to a combination that makes a pleasing game.

However, although rolls of a die determine the moves, it's possible to use mathematics to analyze the game and figure out where to place the snakes and ladders to ensure that the game is neither too long nor too short.

Of course, you could test a board design by playing hundreds of games and recording the results. Alternatively, you can use a mathematical approach named for mathematician Andrey A. Markov (1856-1922) to compute the average length of a game.

Markov studied systems of objects that change from one state to another, according to specified probabilities. When an initial state can lead to subsequent states, and these states, in turn, can lead to additional states, the result is a Markov chain.

Suppose we examine a game of Chutes and Ladders in which there's only one player. Initially the player's token is off the board, and we call this condition state 0. The first roll of a die produces either one, two, three, four, five, or six, meaning that the player can move his (or her) token to one of the squares numbered 1, 2, 3, 4, 5, or 6 after the first roll.

If the player is lucky and rolls a one, he goes to square 1, and then up the ladder to square 38 without an additional turn. Rolling a four would again put him on a ladder, this time taking him to square 14.

So, as the result of one turn the player can end up in state 2, 3, 5, 6, 14, or 38, with an equal probability of 1/6. Squares 1 and 4 aren't considered states because the token doesn't come to rest there. Similarly, the top of any chute doesn't count as a state.

For the second roll of the die, the game can be in one of six states, and we must consider each possibility separately.

Suppose, for example, that the first throw puts the player in state 2. From there, the second roll moves him to square 3, 4, 5, 6, 7, or 8. Because 4 is the bottom of a ladder, the player immediately ascends to 14. So, starting from state 2, the player can move to state 3, 5, 6, 7, 8, or 14 with equal probability.

If the first roll happened to put the player in state 14, the second roll would bring him to square 15, 16, 17, 18, 19, or 20 with equal probability. However, landing on square 16 would plunge him back to 6. Hence, from state 14 the player can move with equal probability to state 6, 15, 17, 18, 19, or 20.

After two rolls, the game can be in a total of 21states. These states, however, are not equally likely. For example, there's only one way to reach state 44 at the end of two rolls: by rolling a one and then a six. Therefore, the probability of ending up in state 44 after two rolls is 1/6 ✕ 1/6 = 1/36.

In contrast, there are three ways of getting to state 31: by rolling three and six, by rolling five and four, and by rolling six and three. Thus, the probability of being in state 31 after two throws is (1/6 ✕ 1/6) + (1/6 ✕ 1/6) + (1/6 ✕ 1/6) = 3/36.

Such calculations can be carried out for three, four, or more rolls to create a complicated Markov chain showing how the game progresses from one set of states to another. For any position of the token, a player can readily determine the probability of ending up on that square.

You can also use the same technique to analyze particular situations. For instance, to place a chute so as to minimize a player's chance of climbing a particular ladder, you can construct a table giving the probabilities of climbing a ladder when a ladder is a given number of spaces ahead, first with no chutes in the way and then with a single chute on one of the intervening squares in front of the ladder.

A player who is one square in front of the ladder has one chance in six of rolling a one to get to the ladder, giving a probability of 1/6, or about .17. A player two squares in front can get to the ladder by rolling either a two (probability 1/6) or two ones (1/36) for a combined probability if 1/6 + 1/36, or .19.

A player who starts at square three must roll a three (1/6), two and one (1/36), one and two (1.36), or one, one, and one (1/216), for a total probability of .23, to reach the ladder.

If there is no chute, the probability of reaching the ladder turns out to be highest when the player is six spaces away.

You might think that placing a single chute immediately in front of a ladder would serve as a strong guard, but calculating the probabilities of landing there instead of on the ladder shows it to be the least effective position. A chute six squares in front is much more difficult to circumvent without missing the ladder as well.

Some of these factors come into play in some well-known versions of Chutes and Ladders. In one version, the top row, or last ten squares, on the board has three chutes. One chute is two squares in front of the finish line. A second is five squares in front, and a third is seven in front.

These chutes turn out to be effective guards, and more often than not a player wins by taking the ladder from square 80 directly to the winning 100th square, completely bypassing the treacherous final stretch.

.

Indeed, the likelihood of such a finish is measured by the fact that all three chutes in the top row land the player in the row that leads to the shortcut ladder in square 80, with no other obstacles standing in the way.

An alternative version, called Gigantik® Snakes & Ladders, has a very different set of snakes and ladders. The large game board has two places in which a guard snake immediately precedes a ladder, one near the beginning and another near the end. It also has two lengthy snakes slithering down from the top row and no ladder directly to the finishing square, so that games tend to take longer than those on a standard Chutes and Ladders board.


The theory of Markov chains offers a powerful method of analyzing probabilistic behavior in a variety of systems. Nowadays computers can readily handle large numbers of states, and researchers can quickly analyze the outcomes and fairness of such games as Chutes and Ladders and Monopoly.

The same techniques can also be used in science to model the wanderings of molecules drifting in air, the foraging patterns of birds, and the fluctuations of prices on a stock market.

Previously: Tumbling Dice
Next: Chance of Face

No comments: