Chutes And Ladders
March 4, 2011
Our method is to simulate playing a large number of games and count the outcomes. Chutes and ladders are represented as association-lists with the from square in the car and to square in the cdr:
(define chutes '((16 . 6) (47 . 26) (49 . 11)
(56 . 53) (62 . 19) (64 . 60) (87 . 24)
(93 . 73) (95 . 75) (98 . 78)))
(define ladders '((1 . 38) (4 . 14) (9 . 31)
(21 . 42) (28 . 84) (36 . 44) (51 . 67)
(71 . 91) (80 . 100)))
A single game is the path that one token takes to reach space 100. The first cond clause ends the game, the second cond clause stays if the roll of the die is beyond the end, the third cond clause handles chutes and ladders, and the final cond clause handles all other squares. The loop accumulates the path through the board; p
is the current position, and ps
is the path. The lambda in the third clause takes the “true” result of an a-list lookup, which is a start/end pair, and extracts the ending position:
(define (game)
(let loop ((ps '(0)))
(let* ((die (randint 6 0)) (p (+ (car ps) die)))
(cond ((= 100 (car ps)) (cdr (reverse ps)))
((< 100 p) (loop (cons (car ps) ps)))
((or (assoc p chutes) (assoc p ladders))
=> (lambda (x) (loop (cons (cdr x) ps))))
(else (loop (cons p ps)))))))
For instance, a sample game might look like this; the player hit the 9/31 ladder and the 80/100 ladder, but no chutes, for a 16-roll game:
> (game)
(6 7 31 37 42 48 50 55 57 63 65 68 72 74 79 100)
Function games
executes (game)
multiple times and reports the lengths of the various games played:
(define (games n)
(let loop ((n n) (gs '()))
(if (zero? n) gs
(loop (- n 1) (cons (length (game)) gs)))))
Compete
reports the lengths of n games each played by k players. The expression (apply min (games k))
reports the number of turns taken by the winner:
(define (compete k n)
(let loop ((n n) (gs '()))
(if (zero? n) gs
(loop (- n 1) (cons (apply min (games k)) gs)))))
Finally, stats
gathers statistics:
(define (stats k n)
(let ((gs (compete k n)))
(values (apply min gs) (apply max gs)
(exact->inexact (/ (apply + gs) n)))))
Here are some sample results:
> (stats 1 1000000)
7
349
39.290771
> (stats 2 100000)
7
154
26.3613
> (stats 3 100000)
7
111
21.73284
> (stats 4 100000)
7
94
19.20292
> (stats 5 100000)
7
80
17.70565
The minimum number of turns to complete the game is 7 (Wikipedia says 6; perhaps their board is somewhat different than ours). It takes on average 39.3 turns to reach space 100. Games get shorter as the number of players increases, since at least one of the players beats the average. The poor fellow who rolled 349 times before reaching space 100 was terribly unlucky; presumably, he should wait until tomorrow to buy a lottery ticket, as he certainly has no luck today.
We used randint
from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/RPq4Ocqx.
My Haskell solution (see http://bonsaicode.wordpress.com/2011/03/04/programming-praxis-chutes-and-ladders/ for a version with comments):
[…] today’s Programming Praxis exercise, our goal is to simulate the board game Chutes and Ladders. Let’s […]
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
available on codepad.
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.
Here’s my python solution. Uses the dijkstra function from a previous exercise to find the minimum path.
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.
My Try in Rexx, Using the Dijkstra-Algorithm from https://programmingpraxis.com/2011/01/04/dijkstras-algorithm/ to find the optimal strategy
[…] la serpiente posición. A la derecha? He utilizado la simulación para resolver este problema en mi blog. Mi solución es en el Esquema; también hay soluciones en Haskell y Python. Además de la […]
[…] usato la simulazione per risolvere questo problema sul mio blog. La mia soluzione è a Regime; ci sono anche soluzioni in Haskell e Python. Oltre alla simulazione […]