snakes & ladders as markov chain

Posted on 2008-10-11
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 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


Open in new window

Question by:ArtemisF
  • 2
  • 2

Expert Comment

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) ....

Author Comment

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

Accepted Solution

PaulKeating earned 450 total points
ID: 22698852

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.
LVL 27

Assisted Solution

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.


Author Closing Comment

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

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Python multiple IF statements 4 76
Math homework question 5 82
python question 5 69
Terminology ..percentile etc 4 37
Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! How to Know You are Making a Difference at EE In August, 2013, one …
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
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 …

867 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

20 Experts available now in Live!

Get 1:1 Help Now