Friday, January 28, 2011

Snakes and Ladders

Or Chutes and Ladder, if you're American. Yes, I am talking about the board game.
The idea came from having read about people analysing Monopoly with simulations, Markov chains and the likes. You can read about it in Math Hysteria by Ian Stewart or find a similar discussion here.

In the book, Professor Stewart also suggests that the reader might like to try the same for Snakes and Ladders. So I did*.

If you're not familiar with Snakes and Ladders and how it works, you had a very deprived childhood. There's an example game board below

I don't know if or by how much game boards vary. But for simplicity, I'm assuming this is a representative layout. Variations aren't likely to dramatically affect the overall behaviour.

Simulating the Game

You start with a 'board' with a value for each square. All squares start with a value of 0. You can simulate the dice roll by randomly picking a number between one and six and move accordingly. Whatever square you land on, you add one to that square's value. If you land on a snake or a ladder, you move along it. Repeat until you get to square 100.

At the end, you have a record of how many times each square was visited.

Here's a network graph of all possible moves.
Over-arcs are forward movements (dice rolls and ladders), under-arcs are backwards movements (snakes).

One run of the simulation is equivalent to one possible game. So what you do, is run the simulation, say, 10,000 times, and measure things like, how many times you land on each square, average or minimum number of turns it takes to get to the end, etc.

There is a way of solving this exactly, and mathematically, as discussed for Monopoly in Ian Stewart's book, and indeed as was done in this paper [pdf]. But this way is much easier.

You can get the code here.


Here's a graph of number of times each square is landed on (out of 10,000 simulations). Snakes are green, ladders are red, arcs show which squares are connected.
And you've got this slightly weird, overall, wave shape. And obviously, the snake and ladder landing squares are outliers - most visited ladders, 36-44 and 28-84; most visited snakes, 47-26 and 49-11.

NB/ technically I shouldn't include the 'entrances' of snakes and ladders in the graph, since when they're landed on, you move straight to the 'exits'. But for interests sake, they are included. They aren't included in the moves count as separate moves.

You can also graph the number of moves it takes to get to the end
The minimum moves is 7, and interestingly, you can also derive that answer from the network graph - that is the absolute minimum.

In this simulation, the mode is 21 and the average is 36.2. The maximum, in this case, is effectively around 215. But theoretically, if you were really unlucky you could keep landing on the same snake over and over; in which case, the maximum number of moves tends to infinity.

And, the last thing to look at is how much more likely you are to land on a snake than a ladder. First of all, there are (typically) 10 snakes and 9 ladders, so the simple answer would be 1.11 times more likely.

But when you go down a snake, as mentioned above, there's a chance you can go down the same snake again (or down other snakes or up other ladders). So it turns out, you're actually 1.23 times more likely to land on a snake than a ladder. Which isn't a dramatic difference; but the important thing is, you need no longer wonder.

On average, you'll land on about 4 snakes and 3.2 ladders per game.

End Games

Say you land on square 97 and roll a four; there are three possible ways to end the game:

Past the End - assume that moving past 100 means you've reached the end (this is what I did above).
This is the easiest way to end the game.

Roll Again - stay in the same square and roll again until you roll a 3 (or less).
This is effectively the same as the above, except (on average) it takes more rolls of the dice (but not necessarily more moves) to reach the end.

Loop Back - move three spaces forward (to 100) then one space back. Repeat until you land exactly one square 100.

This last one takes longer to get to the end, and has a greater risk of you landing on the snakes on squares 95 or 98, sending you back to 75 and 78 respectively.

And that's demonstrated in the graph below - both lines are effectively the same until about the last 25 squares, where the 'loop back' diverges towards more visits (as expected).
You also have the moves distribution,
which in this case is broader and pushed to right slightly; the average now 43.3. Note also that 7 is still the minimum number of moves.

Also, in the 'loop back', the odds of landing on a snake goes up again - now 1.41 times more likely than a ladder. So on average, you'll land on about 5.2 snakes and 3.7 ladders per game.

Triple Sixes

Another rule you could chose to include is - if you roll three 6s in a row, you go back to square 'zero'.

According to the simulation, you'll roll a triple six in about 13.4% of games, on average.

But the triple six seems to have no significant effect on what squares you land on, the number of snake and ladders you'll land on, or oddly enough, the distribution of how many moves it takes to get to the end. This is probably because throwing triple sixes is so rare.

So there you go. Bet you didn't think snakes and ladders could be so complicated.


* truth be told, this is something other people have already done. But I like to try these things for myself.


vapour said...
This comment has been removed by the author.
vapour said...
This comment has been removed by the author.
vapour said...

The post you make here is more important than you realise. I have often considered what I think of as 'the programming problem'. I think there is no better way of approaching the task of programmability using games. Human-derived, invented, games have an intrinsic systematic model-ability about them making it a great field for recreational programming and education. So, you inspired me to have a go because I can encode a S+L games using my limited knowledge of C++ without having to know any graphics! :) Thanks. :)

vapour said...

It would look nicer if you could remove notification of my removed comments... why do we need to know? For anybody reading, they say the exact same thing as the one you can read with the only difference that it has one or two fewer typos. Now you are enlightened! :)