Solved

snakes & ladders as markov chain

Posted on 2008-10-11
5
1,662 Views
Last Modified: 2012-05-05
How may i find the expected number of throws to finish a snakes and ladders game depending on the value of the initial throw?

I have a board with 25 squares so I made a 26x26 matrix with probabilities of getting to the state.

For e.g. from a 0 the probability of me getting to 0 is _, 1 is _, 2 is _.......25 is _
from a 1 the probability of me getting to 0 is _, 1 is _, 2 is _.......25 is _
and so on.

I don't know how to proceed from here.

Of course I am doing this using python, you can have a look at the code that i have currently. Its just I don't know the concept of how I can find the expected number of throws ...so if someone could shed some light that would be good
import os
 

from pylab import *

from numpy import *
 

# get the probabilities of going from one state to another.

data = loadtxt("mat.txt")

data = data.reshape(-1,26)
 

# chop off the last row and column

# transition probabilities among the transient states

Q = data[0:25,0:25]
 

# the transition probabilities from transient to absorbing

R = data[0:25,25:26]

#print R

     

# M = (I-Q)^-1       

Matrix = linalg.inv(eye(25)-Q)
 

# B = M*R

B = Matrix*R

#print B
 

count = []
 

for i in Matrix:

    sum =0

    for m in i:

        sum = sum + m

    count.append(sum)

Open in new window

0
Comment
Question by:ArtemisF
  • 2
  • 2
5 Comments
 
LVL 5

Expert Comment

by:PaulKeating
ID: 22696706
Every possible path through the board from the start square to the finish square is a succession of single-jump probabilities, and so the probability of taking exactly that path is the product of all those single-jump probabilities.

Say, for example, that your board is constructed so that consistently throwing a 6 always gets you to the foot of a ladder and always avoids the head of the snake. So for the sequence of throws 6,6,6,6.. you have a very short path through the board, say length N, but also quite a low probability: your single-jump probabilities are all p=1/6 (assuming one die) and your path probability P = p**N = 6**-N.

So for every possible path you need to compute the probability of taking that path, and the length of the path.

The path with the highest probability is the most-expected path. Say for the sake of argument its length N is 10 and its total path probability P is 0.5. Then half of the time you can expect to finish in 10 throws. The other half of the time you take a different path. Say the next most probable path has P = 0.25 N=12. So a quarter of the time your expected number of throws is 12. And so on.

You build up the expected number of throws by taking the length of each path multiplied by the probability of taking that path, so (10 * 0.5) + (12 * 0.25) ....
0
 

Author Comment

by:ArtemisF
ID: 22696805
How am I getting this length N? Am I just assuming?
I thought I was missing some clue into some formula I have to apply to my matrix of probabilities which looks like
0 0 1/6 1/6 0 1/6 1/6 0 0 1/6...
0 0 0 0 0 0 0 0 0 1....

where what I am saying is that from 0 to 0 probability is 0, from 0 to 3 probability is 1/6
from 1 to 9 probability is 1 as there is a ladder at 1
0
 
LVL 5

Accepted Solution

by:
PaulKeating earned 450 total points
ID: 22698852
Ok,

Starting from 0

0 to 0 is not interesting
0 to 1 is p=1/6: that is interesting, you are now at 1; add 1 jump , so N(0-1)=1 and cumulative probability P(0-1) for this path is 1/6, then recursively
....  1 to 9 is p=1: that is interesting, you are now at 9; add no jump (it was a ladder not a throw) so N(0-1-9) is 1 and cumulative probability P(0-1-9) is 1/6 * 1
(p=1 so no other options to consider out of square 1, the only possible path is 0-1-9)
......... 9 to 10 is p=1/6; that is interesting, you are now at 10; add 1 jump so N(0-1-9-10) = 2, and cumulative probability P(0-1-9-10) is 1/6 * 1 * 1/6; then recursively
............ 10 to 11 is p=1/6; ; that is interesting, you are now at 11; add 1 jump so N(0-1-9-10-11) = 3, and cumulative probability P(0-1-9-10) is 1/6 * 1 * 1/6 * 1/6
........... etc
......... 9 to 11 is p=1/6; that is interesting, you are now at 11, add 1 jump so N(0-1-9-11) = 2, and cumulative probability P(0-1-9-11) is 1/6 * 1 * 1/6
......... 9 to 12 is
......... 9 to 13 is
......... 9 to 14 is
......... 9 to 15 is
Then you go back to
0 to 2 is p=1/6; that is interesting, your are now at 2; add 1 jump, so N(0-2)=1 and cumulative probability P(0-2) for this path is 1/6, then recursively
... 2 to 3 is

Put another way: start at 0, take all 6 possible paths out of 0. From that point, take all possible paths (there may be fewer than 6 because if you land on 1 there is only 1 way out). And so on. Trace through each possible path, counting the dice throws and accumulating the probabilities.

You need to recognize when a snake lands you back to an earlier square because if you trace paths like that indefinitely you will get into an infinite loop. I'm not sure what "expected path length" (="expected number of throws") means in the presence of infinite loops. In theory, given enough bad throws, you can never get to the end.

To start with I would invent a silly limiting rule that the same snake cannot bite you more than once, so the second time you land on its head you can ignore it. This is logical but I suspect it will be hard to program. Or you could simply decide that a player will be declared the winner after 100 throws, so that N for a particular path through the board can never be more than 100.

To see why you need some sort of limiting rule, consider my original formula, (10 * 0.5) + (12 * 0.25) ....

and suppose you add (0.01243 * infinity) to that: you will make nonsense of the calculation, because then the expected number of throws will always be infinite.
0
 
LVL 27

Assisted Solution

by:d-glitch
d-glitch earned 50 total points
ID: 22702814
How many snakes and ladders are there?
What do the last six squares look like?

For every square that doesn't take you for an extra ride, you can calculate the expected value or rolls required to reach the finish.

I think you can work backwards from the finish line.  The expected values for
squares snake and ladder squares are the values of the final destination.
There will be some series terms that you have to solve for those squares.

You could also do a Monte Carlo simulation of the game an estimate the values that way.







0
 

Author Closing Comment

by:ArtemisF
ID: 31505397
Thank you for the advice. Both helped my understanding hence the split of points
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
Article by: Nicole
This is a research brief on the potential colonization of humans on Mars.
Learn the basics of lists in Python. Lists, as their name suggests, are a means for ordering and storing values. : Lists are declared using brackets; for example: t = [1, 2, 3]: Lists may contain a mix of data types; for example: t = ['string', 1, T…
Learn the basics of if, else, and elif statements in Python 2.7. Use "if" statements to test a specified condition.: The structure of an if statement is as follows: (CODE) Use "else" statements to allow the execution of an alternative, if the …

760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now