Go Premium for a chance to win a PS4. Enter to Win


snakes & ladders as markov chain

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

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 1800 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 200 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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
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…
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Suggested Courses

963 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