What is the expected number of moves it takes a single player to win Chutes and Ladders?

The expected number of moves it takes a single player to win Chutes and
Ladders is

4701963530284262061680976447702295260969373555678655812977547 /
118741353443887754043709082737855602672874458412108079756280

which is approximately 39.5984.

I was surprised not to find this fraction on the web, despite the
number of sites containing the computation:

* http://tinyurl.com/5az5j gives the numerical result 39.5984, but not
  the exact result.

* http://tinyurl.com/49bq7 and http://tinyurl.com/3pv5p and
  http://tinyurl.com/6fctr solve the problem for a slightly different
  version, in which there is a chute from 47 to 26 rather than 48 to
  26.  My son's version is quite new, so I assume that the "47" version
  is older.  For the "47" version, the exact expression for the
  expected number of moves is

  225837582538403273407117496273279920181931269186581786048583 /
  5757472998140039232950575874628786131130999406013041613400

  which is approximately 39.2251.

  Although the approximation is given on the last two sites above, the
  exact expression does not occur there, nor anywhere else on the web.
  It is curious that the "48" version is so much harder than the "47":
  0.373 moves just from moving a chute entrance.  The main reason for
  this is that there is a chute entrance at 49 as well.  Without the
  chute from 49 to 11, the difference in expectations between the "48"
  and "47" versions is only 0.122.

* http://tinyurl.com/66oyk does give an exact expression, but for a
  problem which is different in two ways.  Although it does have the
  chute from 48 to 26, it replaces the ladder from 1 to 38 with one
  from 1 to 23.  Furthermore, it treats a spin moving you past 100 as a
  victory, whereas the rules stipulate that you do not move in this
  situation.  I'm not convinced that there is a version with a ladder
  from 1 to 23: this could simply be a mistake of "not climbing all the
  way up".  The change of "38" to "23" produces only a small difference
  in the expected number of moves: 39.4325, in the latter version.  It
  is the ending rule that makes the expectation quoted on this site so
  small: 36.0043.

Here is some Mathematica code that computes the expected number of
moves.

cldata = {{1,38},{4,14},{9,31},{16,6},{21,42},{28,84},{36,44},{48,26},
  {49,11},{51,67},{56,53},{62,19},{64,60},{71,91},{80,100},{87,24},
  {93,73},{95,75},{98,78}};
Clear[a,stoi];
a[s_] := s; (a[#[[1]]] = #[[2]])& /@ cldata;
ns = Length[states = Select[Range[0,99],a[#]==#&]];
zer = Table[0,{ns}];
(stoi[#[[1]]] = #[[2]])& /@ Transpose[{states,Range[ns]}];
rw[s_] := Sum[asp = a[s+i]; If[asp > 100,asp = s];
  If[asp < 100,ReplacePart[zer,1/6,stoi[asp]],zer],{i,6}];
Plus@@First[Inverse[IdentityMatrix[ns] - rw /@ states]]

-- Jim Ferry <corkleb...@hotmail.com> (sci.math and rec.puzzles,
   January 2005)

[ Editor: the code is rewrapped at the semicolons; it was posted as
one long line.  The address is shortened as in the Google Groups copy
that was collected. ]

> Okay, where'd you get this? It's a cool amount, though.

-- Poly-Poly Man

I wrote a Mathematica program to compute it.  It's included in the
original post.  The idea is that you consider a vector v(n) of the
probabilities of being on each square at move n, and then construct a
"transition matrix" T such that v(n+1) = T v(n).  The expected number
of moves is a function of T.

-- Jim Ferry

Well, I got

   331383032821169320669389948357825257572206047154891555617265433
   ---------------------------------------------------------------
   9203993450370268328812248809434927944759825554168023433299080

which is about 36.00426647 .  This has been on the web at

   http://www.math.niu.edu/~rusin/uses-math/games/chutes/index.html

for some time.  I haven't reviewed the computations since I did them
so I don't know why our answers differ.

-- Dave Rusin <r...@vesuvius.math.niu.edu>

I cited
http://www.math.niu.edu/~rusin/uses-math/games/chutes/chutes.sum which
is a child of the page you mention.  I ran it through tinyurl to get
http://tinyurl.com/66oyk .  There are two differences between your
computation and mine.  You have a ladder from 1 to 23, whereas I have
one from 1 to 38.  More importantly, you have a laxer ending condition,
allowing one to move past 100 to win, whereas I require one to hit 100
exactly.

If I modify my code to incorporate those two differences I get the
same answer as you:

(* Modified version: 38 -> 23, no "If[asp > 100,asp = s];" *)
cldata = {{1,23},{4,14},{9,31},{16,6},{21,42},{28,84},{36,44},{48,26},
  {49,11},{51,67},{56,53},{62,19},{64,60},{71,91},{80,100},{87,24},
  {93,73},{95,75},{98,78}};
Clear[a,stoi];
a[s_] := s; (a[#[[1]]] = #[[2]])& /@ cldata;
ns = Length[states = Select[Range[0,99],a[#]==#&]];
zer = Table[0,{ns}];
(stoi[#[[1]]] = #[[2]])& /@ Transpose[{states,Range[ns]}];
rw[s_] := Sum[asp = a[s+i]; (* If[asp > 100,asp = s]; *)
  If[asp < 100,ReplacePart[zer,1/6,stoi[asp]],zer],{i,6}];
Plus@@First[Inverse[IdentityMatrix[ns] - rw /@ states]]

-- Jim Ferry

Since Snakes and Ladders boards by different makers have snakes, and
ladders, in different positions, and no one layout is the "standard",
at least in the United States, it isn't surprising that no one there
has tried extended calculations for that game - as opposed, say, to
Monopoly, which does have a single standardized form.

-- John Savard

My son's version has a chute from 48 to 26.  There seems to be another
version with a chute from 47 to 26 instead.  As far as I know (which is
not very far, admittedly) these are the only two variants.

-- Jim Ferry

[ Editor: on the name of the game: ]

We've always known the game as Snakes and Ladders (in New Zealand).
Does your version have pictures of children being good (by the
ladders) and being bad (by the chutes/snakes)?

-- Richard Brown

And in Britain.  Snakes and Ladders appears in Ken Russell's The Lair
of the White Worm (1988), which is reason enough to change it.  [...]
Yes, one of the links posted shows an actual gameboard.

-- mensanator

When I was a kid our board game was called "ropes and ladders",
probably the same thing tho.

-- Lloyd