Shoots and ladders

Yesterday evening, my older son decided to play shoots and ladders. We’ve played this before. He enjoys it and is getting better at not cheating and dealing well with sometimes losing. It’s also good practice at some simple counting and arithmetic.

However, I got to thinking (usually not a good idea). Theoretically, it’s a game that could go on forever. You could always keep getting stuck getting pulled back by a shoot, or never hitting the right ladder. The probability of never finishing is I assume basically impossible, but what does the tail or probability look like? What kind of average game is there, what are the quartiles like, etc. Would those probabilities change if the shoots and ladders were in a different configuration?

There’s I’m certain different approaches to this problem. I’m sure there’s a purely analytical approach that relies on probability theory. I remember enough Prob and Stat to use terms like “expected value” and be reasonably confident I’m using it right, but that’s where my expertise falls off. So instead of an analytical approach, what about just an approximation through brute force? Could I write a program to simulate one, ten, 100, 1,000 games? With a random set of shoots and ladders? If I ran that a few times and put it all in a spreadsheet I bet I could do some basic prob and stat analytics to answer my original questions.

So here’s my basic outline of pseudocode

//Set (or get from comand line args) the basic parameters: random seed, number of shoots and ladders, number of games to try, number of players per game

// Randomize shoots and ladders positions on the 1-100 line. A shoot or ladder is a direcctional mapping from one position to another.

//For n, n <  where n is the number of games to try

//turn t = 0

//while there is no winner

//For p, p < number of players, and no winner

//roll dice, update playerPositons[p]

//did player land on a shoot or a ladder?

// if so, move to mapped location, update position again

// Did the player land on 100? if so, winner, break

// record or output number of turns

I should eventually (with filling in some of the assumptions above) get some maybe csv output I can put into a spreadsheet and to avg(), min(), max(), quartile() etc.

Update:

I wrote the above pseudo code into some real (not very good) Java code (GitHub repo here). Some initial results! Tests of game sizes below 100,000 were pretty variable. I could get average number of turns (really rounds, not player turns) anywhere from 10 to over 30. Even when testing with 100,000 it still varied, but started to hover in the 15-25 range.

One million game runs could be calculated quickly, but the console output (at least in my IDE) got truncated. So rather than doing some more math in the code, just re-ran the 100,000 setup a few times. With 600,000, it really started to converge around an average of 22 rounds to find a victory. Each 100k set of course had a different setup of shoots and ladders, but it was interesting that it converged very quickly with that. The minimum of my 600k set is 5 turns, the max was 136 (that’s like a 2+ hour game, ugh). The first quartile was 16, and the third was 26. So realistically, most games of Shoots and Ladders are probably lasting about 40ish minutes (assuming one minute per player per round). That feels generally right to me, though added variance would of course need to be taken into account when playing with a four year old who doesn’t want to go to bed.