Solved

snakes & ladders as markov chain

Posted on 2008-10-11
5
1,689 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

Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Article by: Nicole
This is a research brief on the potential colonization of humans on Mars.
Learn the basics of modules and packages in Python. Every Python file is a module, ending in the suffix: .py: Modules are a collection of functions and variables.: Packages are a collection of modules.: Module functions and variables are accessed us…
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.

816 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

10 Experts available now in Live!

Get 1:1 Help Now