Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17


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 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
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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

Moving data to the cloud? Find out if you’re ready

Before moving to the cloud, it is important to carefully define your db needs, plan for the migration & understand prod. environment. This wp explains how to define what you need from a cloud provider, plan for the migration & what putting a cloud solution into practice entails.

Question has a verified solution.

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

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…
The purpose of this article is to demonstrate how we can upgrade Python from version 2.7.6 to Python 2.7.10 on the Linux Mint operating system. I am using an Oracle Virtual Box where I have installed Linux Mint operating system version 17.2. Once yo…
Learn the basics of strings in Python: declaration, operations, indices, and slicing. Strings are declared with quotations; for example: s = "string": Strings are immutable.: Strings may be concatenated or multiplied using the addition and multiplic…
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.

715 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