Can Snakes & Ladders last forever?
Several Christmases ago I found myself horribly bored. I was stuck at my mother-in-law's house. In the absence of anything else to do, my kids and I spent the morning playing Snakes & Ladders. They found it dull. I was about ready to jump through window just to escape one game that just never, ever seemed to end.
Interesting maths
Interesting questions arose as the games went on and on and on. It's easy to see that with bad luck a game can go on for a long, long time - but how long, exactly? What's the average length of a game, and what does the distribution look like?
Initial Results
I wrote a small simulation of the game on my laptop that night. Just one lonely player, always rolling dice and moving their counter in endless games of solo snakes and ladders (it's the saddest image).
Play for long enough and patterns emerge. Half of all games end after the median of 33 turns. There are two paths to the shortest possible game of 7 turns. If you play a million games, at least one of them will probably take more than 400 turns to finish. The longest game I've ever seen took 729 turns to finish.
1,000,000,000,000 is 999,999,999,999 Too Many
I never liked linear algebra, so in an act of electronic cruelty I forced my desktop PC play one trillion games of Snakes and Ladders and collected the results. I hope our future AI overlords will understand.
Average Game Length
As often happens in the real world, the easy-to-calculate mean lets us down. The data's shape (more below) makes its value of XXX too large. The median fares better. Of the trillon games played half took fewer moves the the median, half too more.
More Than 100 Moves?!
The perpetual game that inspired this chain of thought cannot have actually been more than 30 or 40 rolls - otherwise I surely would have defenestrated myself in truth. The sad truth is that a disturbingly high 3.3% of the trillion games played took more than 100 moves to complete.
When playing with children you must insist that the whole game ends when any one of the players win. Keep playing to see who comes second, third, then last is a recipe for boredom in enormous quantities. I did not so specify that fateful afternoon.
Longest Game
Of all the trillion games, the longest took 729 rolls to finish. The second-longest took 666. 33 billion (3.3%) of solo games took longer than 100 moves. Yikes!
Two Shortest Games
The shortest game takes only 7 rolls. You have a 1 in 639 chance of doing it. What's cool is that there are several distinct routes to take:
[(4, 14), (6, 20), (4, 24), (4, 84), (6, 90), (5, 75), (5, 100)]
1. Roll a 4 to climb ladder to 14.
2-4. Take three rolls to foot of ladder on square 28. Climb to 84.
From here either:
5-6. Take two rolls to snake on 95 and slide down to 75.
7. Roll a 5 to foot of ladder on square 80. Climb to victory!
[(4, 14), (6, 20), (4, 24), (4, 84), (6, 90), (5, 75), (5, 100)]
1. Roll a 4 to climb ladder to 14.
2-4. Take three rolls to foot of ladder on square 28. Climb to 84.
From here either:
5-6. Take two rolls to snake on 95 and slide down to 75.
7. Roll a 5 to foot of ladder on square 80. Climb to victory!
Markov Chains
The game board is really a discrete-time Markov chain with 100 states (or 81 if you're feeling particularly pedantic). I try and avoid terminology when trying to explain (or understand) a new concept. Richard Feynman said something like, "If you can't explain something in simple terms, you don't understand it.". Markov chain gets to be an exception only because it has the coolest name. It's not nearly as complicated (or impressive) as the name suggests.
The First Links on the Chain
Picture the game board. You roll the dice for your first move, a value from one to six. There are two ladders that you might land on (some initial excitement?) Let's say you threw a one and ended up on 38. Your next roll you have a 1/6 chance of landing on either 39, 40, 41, 42, 43, or 44.
Here's the important bit. These odds remains the same no matter how you got to square 38 in the first place. It doesn't matter if it's your second roll or your 100th: if you start your turn on square 38 your next roll will take you to one of the following squares with equal probability. Each step is independent of every other.
You can fill in (and add-up) the odds for each square into a 2-dimensional matrix (a transition matrix if you're Googling) which you can then square then cube to work out the odds for the second then third move, and so on. Watch the excellent Numberphile video linked at the bottom of this article for a better explanation of how to calculate out the expected game length (and with much better graphics!).
More than one weirdo
It's gratifying to know you're not the only wierdo in the world. Since I started playing around with this topic several years ago, several other articles and videos on the same topic have caught my attention:
Published 14 Mar 2024