## Chutes And Ladders

### March 4, 2011

The children’s game Chutes and Ladders, pictured at right, is a chase game in which one or more players, moving alternately, move their tokens along the numbered spaces of a board according to the roll of a die; the tokens are initially off-the-board at what is effectively space zero. Tokens that land on the bottom end of a ladder are promoted to the space at the top end of the ladder, and tokens that land on the top end of a chute are demoted to the space at the bottom end of the chute. Space 100 must be reached by exact roll of the die; if the roll of the die would take the token past space 100, the token remains where it is and play passes to the next player. The winner of the game is the first token to reach space 100.

There are several interesting questions that can be asked about the game. First, what is the minimum number of rolls required to reach space 100. Second, for a single player, what is the average number of rolls required to reach space 100. And third, for k players, what is the average number of rolls until one of the players reaches space 100 and wins the game. S. C. Althoen, L. King and K. Schilling studied these and other questions in their paper “How Long Is a Game of Snakes and Ladders?” The Mathematical Gazette, Volume 77, Number 478, March 1993, pages 71-76.

Your task is to write programs that will answer those questions. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 7 Responses to “Chutes And Ladders”

1. [...] today’s Programming Praxis exercise, our goal is to simulate the board game Chutes and Ladders. Let’s [...]

2. My Haskell solution (see http://bonsaicode.wordpress.com/2011/03/04/programming-praxis-chutes-and-ladders/ for a version with comments):

```import Control.Monad
import System.Random

promote :: Num a => a -> a
promote n = maybe n id \$ lookup n [(16,6), (47,26), (49,11), (56,53),
(62,19), (64,60), (87,24), (93,73), (95,75), (98,78), (1,38), (4,14),
(9,31), (21,42), (28,84), (36,44), (51,67), (71,91), (80,100)]

game :: IO [Int]
game = fmap (tail . turn 0 . randomRs (1,6)) newStdGen where
turn 100 _       = [100]
turn n   ~(d:ds) = n : turn (if n+d > 100 then n else promote \$ n+d) ds

stats :: Int -> Int -> IO (Int, Int, Float)
stats k n = fmap (\rs -> (minimum rs, maximum rs, average rs)) .
replicateM n . fmap minimum . replicateM k \$ fmap length game where
average xs = fromIntegral (sum xs) / fromIntegral n

main :: IO ()
main = do print =<< stats 1 100000
print =<< stats 2 100000
print =<< stats 3 100000
print =<< stats 4 100000
print =<< stats 5 100000
```
3. Graham said

Not terribly fast, though it gets the job done. To speed this up, I tried
1. Numpy arrays (which doesn’t get much of an improvement),
2. PyPy (which sped things up a lot), and
3. Cython to compile the code.
None of these three options come standard with the typical Python installation,
unfortunately. As a further exercise for myself, I went about compiling via
Cython, without changing the original code beyond all recognition; details

```#!/usr/bin/env python
from random import randrange

pos, path = 0, []
while pos < 100:
pos += randrange(1, 7)
if pos in chutes:
pos = chutes[pos]
elif pos in ladders:
path.append(pos)
if path[-1] > 100:
path[-1] = 100
return path

def mult_games(n, chutes, ladders):
return [len(single_game(chutes, ladders)) for _ in xrange(n)]

def compete(k, n, chutes, ladders):
return [min(mult_games(k, chutes, ladders)) for _ in xrange(n)]

def mean(xs):
return sum(xs) / float(len(xs))

def stats(k, n, chutes, ladders):
games = compete(k, n, chutes, ladders)
return min(games), max(games), mean(games)

if __name__ == "__main__":
chutes = {16: 6, 47: 26, 49: 11, 56: 53, 62: 19, 64: 60, 87: 24, 93: 73,
95: 75, 98: 78}
ladders = {1: 38, 4: 14, 9: 31, 21: 42, 28: 84, 36: 44, 51: 67, 71: 91,
80: 100}
for k in xrange(1, 7):
print stats(k, 100000, chutes, ladders)
```
4. I’ve got a Haskell solution similar to Remco Niemeijer’s one, so I decided not to repeat it here once more.

Instead, I solved the first question regarding the minimal number of rolls in a “theoretical” way, without simulating the game itself. I converted the game board into a directed graph — each node has 6 outgoing edges, corresponding to 6 possible rolls (or less, if it’s near 100) and then used breadth-first search to find out the shortest path length from start to finish. It turned out to be 7.

```import Data.Graph.Inductive hiding (nodes, edges, run)
import Data.Graph.Inductive.Query.BFS (esp, lesp)

start  = 0
finish = 100
step   = 6

transitions = [ (1, 38), (4, 14), (9, 31), (16, 6), (21, 42), (28, 84)
, (36, 44), (47, 26), (49, 11), (51, 67), (56, 53), (62, 19)
, (64, 60), (71, 91), (80, 100), (87, 24), (93, 73), (95, 75)
, (98, 78) ]

nodes :: [(Int, ())]
nodes = [(n, ()) | n <- [start .. finish]]

edges :: [(Int, Int, ())]
edges = concatMap (edges' . fst) nodes
where
edges' x = [ edge x n (lookup n transitions) | k <- [1 .. step], let n = x + k, n <= finish ]
edge x n (Just trans) = (x, trans, ())
edge x n Nothing      = (x, n,     ())

gameGraph :: Gr () ()
gameGraph = mkGraph nodes edges

shortestGame :: Int
shortestGame = length (esp start finish gameGraph) - 1

```
5. Mike said

Here’s my python solution. Uses the dijkstra function from a previous exercise to find the minimum path.

```from dijkstra import *
from random import randrange

chutes = {98:78, 95:75, 93:73, 87:24, 64:60,
62:19, 56:53, 49:11, 47:26, 16: 6 }

ladders = { 1:38,  4:14,  9:31, 21:42, 28:84,
36:44, 51:67, 71:91, 80:100 }

special = dict(chutes.viewitems() | ladders.viewitems())

# transision table: next_sq[current square][dice roll - 1] -> next square
# includes effects of slides and ladders, so next_sq[0][1] is 38
next_sq = [[special.get(r,min(r, 100))
for r in range(n+1,n+7)]
for n in range(101)]

# create graph from the transition table
graph = {n:{t:1 for t in next_sq[n]} for n in range(101)}

mst = dijkstra(graph,0,100)
mst[100] # returns (7, 74), min of 7 turns, previous sequare is 74

def play(nplayers=1):
sq = [0]*nplayers
nturns = 0
while True:
nturns += 1
for player in range(nplayers):
sq[player] = next_sq[sq[player]][randrange(6)]
if sq[player] == 100:
return nturns, player

for nplayers in range (1,6):
turns = [play(nplayers)[0] for _ in range(10000)]
print float(sum(turns))/len(turns), min(turns)

```
6. Vigor said

These implementations which walk a tree take a long time to run – the first haskell program takes on the order of 30 seconds to print the first statistics on my system. A faster way is to create a transition matrix and repeatedly multiply with a state vector to compute the probability of any particular state after N turns. Experimentally, after 350 iterations, this accounts for 99.9999% of all games and produces an answer of avg turns = 39.2 in under a second of CPU time.

7. Rainer said

My Try in Rexx, Using the Dijkstra-Algorithm from http://programmingpraxis.com/2011/01/04/dijkstras-algorithm/ to find the optimal strategy

```
MAX = 99999
chutes = '16-6 47-26 49-11 56-53 64-60 62-19 87-24 93-73 95-75 98-78'
ladders = '1-38 4-14 10-31 28-84 21-42 36-44 51-67 71-91 80-100'

ch. = ''
ld. = ''
erg. = ''
cnt = 0

orte = ''
strecken = ''

call init_basic
call zufall 100, 1
call zufall 100, 3
call zufall 100, 10
call zufall 100, 100
call ergebnis_zufall

start = 1
ziel = 100

d. = MAX
d.start = 0
p. = ''

call init_shortest_path
call optimal_path

exit

zufall:
parse arg t, p
ct_sum = 0
do games = 1 to t
hundert = 0
player_pos. = 0
do while hundert == 0
/* ---------------------- */
/* p = Anzahl der Spieler */
/* ---------------------- */
do player = 1 to p
wrk = 0
cp = player_pos.player
if cp == 100 then do
hundert = 1
leave
end
select
/* -------------------------------- */
/* Akt. Pos = Beginn einer Leiter ? */
/* Neue Position = Ende der Leiter  */
/* -------------------------------- */
when ch.cp > 0 then wrk = ch.cp
/* -------------------------------- */
/* Akt. Pos = Oben an Rutsche ?     */
/* Neue Position = Unten an Rutsche */
/* -------------------------------- */
when ld.cp > 0 then wrk = ld.cp
otherwise do
/* -------------------------------- */
/* Wuerfeln Zufallszahl zw. 1 und 5 */
/* -------------------------------- */
wrk = cp + random(1, 6)
ct_sum = ct_sum + 1
/* --------------------------------------*/
/* wenn neue Pos. > 100, dann ignorieren */
if wrk > 100 then iterate player
/* --------------------------------------*/
end
end
player_pos.player = wrk
end
end
end
cnt = cnt + 1
erg.cnt = p 'Personen mussten (/)',
'bei' t 'Versuchen durchschn.',
((ct_sum % p) % t) 'mal wuerfeln.'
return

init_basic:
do while words(chutes) > 0
parse value chutes with first chutes
parse value first with start'-'end
ch.start = end
end
do while words(ladders) > 0
parse value first with start'-'end
ld.start = end
end
return

init_shortest_path:
do x = 1 to 100
orte = orte x
end
do x = 1 to 100
ks = ''
if ch.x > '' then iterate
if ld.x > '' then ks = ks x'-'ld.x'-'0
do y = x+1 to min(x+6,100)
if strip(ch.y) == '' then ks = ks x'-'y'-'1
end
strecken = strecken ks
end
return

ergebnis_zufall:
say cnt
do i = 1 to cnt
say erg.i
end
return

optimal_path:
q = orte
do while words(q) > 0
u = n_nb(q)
if u == '' then leave
q = delword(q, wordpos(u,q), 1)
call relax u,strecken
end
say reverse(translate(strip(ausgabe(ziel, '')),'<',' ')),
'=' d.ziel 'Wuerfe'
return

n_nb: procedure expose d. MAX
parse arg q
min = MAX
rw = ''
do i = 1 to words(q)
w = word(q, i)
if d.w < min then do
min = d.w
rw = w
end
end
return rw

relax: procedure expose d. p.
parse arg akt,kanten
do while length(kanten) > 0
parse value kanten with kante kanten
parse value kante with von'-'nach'-'entf
select
when akt == von  then nb = nach
otherwise iterate
end
neu = d.akt + entf
if d.nb > neu then do
d.nb = neu
p.nb = akt
end
end
return

ausgabe:
parse arg vorg, route
if p.vorg == '' then return strip(reverse(route vorg))
return ausgabe(p.vorg,route vorg)

```