Calculate Average Duration of Snakes & Ladders Game

[Crumbles]

I want to calculate the average duration of a snakes and ladders game in terms of the number of moves. Does anybody have any idea on how to tackle the problem?

 

[BicycleTree]

How do you play snakes and ladders?

 

[Crumbles]

It's a board game that consists of an array of numbers from 1 to 100 that you play by rolling a die. You can find an online version http://www.bbc.co.uk/schools/numbertime/games/snakes.shtml.

You start the game off the board [if you get a 1 from your first throw, you move to square 1, if you get a 2, square 2, etc] and move according to the roll of the die. You win when you get to square 100. On your way there, you come across snakes and ladders. If the roll of your die leads you to the foot of a ladder, you get to move up the ladder. But if it leads you to the head of a snake, you follow the snake to the square that contains its tail.

You will need shockwave to load the link above. You can also find a jpeg of the board http://www.hants.gov.uk/museum/toys/history/images/snakes.jpg .

 

[BicycleTree]

It looks like it's too complicated to do manually and you should probably just write a program to simulate it.

 

[Crumbles]

Yes, writing a program is my plan. But I have been advised against doing it by literally taking an average with the computer playing the game many times. It is apparently very time consuming and yields very inaccurate answers.

It can be worked out by probabilities from what I got told... Any ideas?

 

[BicycleTree]

I don't believe it is such a bad idea to do it with the computer playing the game many times--probably no more than a couple hundred moves a game so you could play a million games. But if you don't want to do it that way then you could do it like this: start out with 0 on each square except for the first square that has 1. Then put 1/6 on each of the 6 squares following square 1 and make the first square 0. If any of the 1/6's are on a ladder or a snake, then put them at the end of the ladder or snake. You should probably use linked nodes that can also be referenced by array to represent the board. On each iteration, take the value on each square and distribute it evenly over the following 6 squares, accounting for snakes or ladders. (You should use a second board as a buffer for the next step). When a value appears at the finish, you record the value and what iteration it finished at in another array (this second array should be huge, it must have as many elements as the number of game moves you simulate). When, say, 99.9% of the value is at the finish, you terminate. That other array then has the probability distribution of 1 player finishing in x moves if he is playing alone. Then from that array you can find the probability distribution of 2 players (assuming there are 2) finishing in n moves which is what I assume you want.

 

[BicycleTree]

Actually, I think there is a way to calculate the average for the 2 player game as you go, so you don't need the huge array. Of course if you are only interested in the average for the 1 player game then it's easy, you just multiply each incoming value by the move it arrives at, and add that to a running total. But there is a way to calculate it for a 2 player game as well.