Saturday, October 8, 2011

How long is a game of snakes and ladders?

The detailed answer can be found here. You can stop right now or roll the dice and play on ...

The game originated in India more than 800 years ago and is still popular there. Other board games (Chaturangam or chess, and Pachisi or Ludo) also originated here, and a future post will explore the familiar stochastic OR topic of 'a gambler's ruin' in ancient India. Here's a picture of a native SNL board. The original Indian name of the SNL game translates to 'the path to salvation' and was supposed to be morally educational as well as enjoyable for kids. It's actually pretty profound.

From an Operations Research perspective, the game can be modeled as a Markov Chain. The moral lessons for kids in the Markovian property of SNL seems to be that no matter how terrible a path you took to get to a certain point, you retain the same possibility of salvation by consistently performing good deeds. Note the absence of any non-Markovian historical baggage of original sin. Similarly, a lifetime of virtuousness can be temporarily undone by a single big act of indiscretion that can literally bring you back to square one. As kids, we always felt nervous about the long snake lurking around the 99th square waiting to yank us down.

Per the paper (linked above) published in 1993, simulations indicated that the average number of moves for a 10X10 square game of SNL was around 39. More precisely, using the Markov Chain state transition equations, the authors (Althoen, King, and Schilling) calculate the exact expected number of moves in the "Milton Bradley version of Chutes and Ladders" to be equal to this impressive but twitter-unfriendly ratio:


or approximately 39.2. Other interesting results based on a sensitivity analysis of this value wrt adding or dropping snakes and/or ladders include:
- a six-sided die based game of SNL with no snakes or ladders lasts around 33 moves on average. A unit snake seemingly prolongs the game more than a ladder can speed it up. I felt that pretty acutely as a kid. Yet again, in true Steve Jobsian fashion (or maybe not), it turns out that the seemingly idle SNL time in Bangalore, India was a solid foundation for a career in O.R practice.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.