“Daddy, will you play a game with me?”
I’d been left in charge, whilst my wife had some well-earned time to herself. Baby brother had been bounced to sleep, and now big sister was wanting some attention.
“Sure! What shall we play?”
My daughter fished around in the cupboard, then thumped a box on the table. My heart sank. “Snakes and Ladders”, she announced.
For the benefit of any reader who has the good fortune never to have thus occupied their children, Snakes and Ladders is a game played on 10 x 10 board wherein players take it in turns to move across the board boustrophedonically (that is, left to right then right to left – I’ve been itching to work that word into a blog post), on each go moving the number of spaces indicated by the throw of a die. The winner is the first person to reach the last space on the board. The only modicum of excitement to be found in the game is provided by the eponymous snakes and ladders, which connect certain squares on the board. Land on a square at the foot of a ladder, and you zoom ahead to the square at its top. But beware the squares where snakes lie in wait: land here, and you must slide back down the board to the snake’s tail.
You see then, why I wasn’t thrilled at my daughter’s choice: I don’t expect much from a children’s game, but it is nice to be sure that it will finish before one’s brain goes into power-save mode. And no mathematician would be prepared to give such a guarantee about this game: it is perfectly possible to find yourself within a throw of winning, but the next moment unceremoniously snaking your way back to the beginning, to start all over again.
So as I fixed my grin in place and started rolling the die, I got to wondering: how long till we can play something else? How many turns does a game of Snakes and Ladders last, on average? By the time I’d slid down my first snake, I knew how I could find out: I would set my computer playing snakes and ladders, over and over, and instruct it to count how many turns each game took. Apply a little high-school Maths and Stats to the results, and I’d have my answer.
I will confess the game board received little of my attention from then on, as code began to assemble in the editor in my mind (which has syntax highlighting, but is lacking Intellisense - CommonSense too, my wife would tell you). When I realised that I could use PLINQ to parallelise the code and speed up the simulation, my fingers began itching to get at the keyboard.
Here’s how the code turned out, once I fired up Visual Studio.
Modelling the Game
First, a fluent interface for defining the game board:
var board = new BoardBuilder()
.Length(100)
.Ladder().From(1).To(38)
.Ladder().From(4).To(14)
.Ladder().From(9).To(31)
.Snake().From(16).To(6)
.Ladder().From(21).To(42)
.Ladder().From(28).To(84)
.Ladder().From(36).To(44)
.Snake().From(47).To(26)
.Snake().From(49).To(11)
//...
.Build()
Then the game logic. The GameBoard built by the BoardBuilder consists of a number of Places. Each Place has a reference to the Place following it on the board, and if it is at the foot of a ladder or the head of a snake then it has a reference to the Place at the other end of the link. Most of the logic of the game simulation is contained in the MoveOn method. This method is defined recursively. It is passed the numberOfPlaces that the player should move, and it returns a reference to the Place they end up at, taking into account any snakes or ladders leaving the final square. For simplicity, I’ve decided that players cannot move beyond the last space on the board – they simply get stuck there, whatever they throw.
class Place
{
private Place _ladderTo;
private Place _chuteTo;
private Place _nextPlace;
// ...
public Place MoveOn(int numberOfPlaces)
{
Contract.Requires(numberOfPlaces >= 0, "numberOfPlaces must be positive");
if (numberOfPlaces > 0)
{
if (IsLastSpace)
{
return this;
}
else
{
return _nextPlace.MoveOn(numberOfPlaces - 1);
}
}
if (_ladderTo != null)
{
return _ladderTo;
}
else if (_chuteTo != null)
{
return _chuteTo;
}
else
{
return this;
}
}
// ...
}
}
Running the Simulation
At last, the simulation:
var gameLengths
= 1.To(numberOfTrials)
.Select(trial =>
{
var die = new Die();
return board.
FirstPlace
.Unfold(place => place.MoveOn(die.Roll()))
.TakeWhile(place => !place.IsLastPlace)
.Count();
})
.ToList();
Not much to look at, is it? I start by generating a simple sequence, 1.To(numberOfTrials), and for each item in that sequence I instruct the computer to play a LINQified game of Snakes and ladders, and to count how many moves it takes to get to the end of the board. Each game starts by creating a new Die (would be handy if we could do that in real life – we’re always losing ours). Then, using the Unfold method, seeded with the first place on the board, we generate a sequence of all the spaces landed on during that game. We pull items out of this sequence until we hit the last place on the board, at which point we count how many moves the game took.
Analysing the Results
Of course, we want to do some analysis on the results. LINQ makes it trivial to find the average length of a game:
var averageLength = games.Average();
This turns out to be 35.8 moves.
More interesting is the frequency distribution of game lengths which tells us how often we can expect to play games of a given length.
var frequencyDistribution =
gameLengths
.GroupBy(gameLength => gameLength)
.OrderBy(gameLengthGroup => gameLengthGroup.Key)
.Select(gameLengthGroup => gameLengthGroup.Key + "," + gameLengthGroup.Count() + "," + gameLengthGroup.Count() / (double)numberOfTrials)
.ToList();
System.IO.File.WriteAllLines("SnakesAndLadderResult.csv", frequencyDistribution);
gameLengths is the sequence containing the length of each simulated game. This query is counting how many games of each length were encountered in the simulation by grouping together all games of the same length. After ordering the groups, shortest game length first, it creates a string for each group, listing the length, the absolute number of games of that length and the frequency of that length of game. File.WriteAllLines is a neat method that (from .Net 4.0 onwards) takes an IEnumerable<string> and writes each string as a new line to a file, giving us an instant CSV file from which Excel can draw a pretty chart:
This shows that in at least half of all games I’ll need to throw the dice 28 times or more before getting to the end. Worse, there’s a 10% chance that it’ll be 68 moves or more before I beat those slippery snakes.
The PLINQ Part
Where does PLINQ come into all this? And what is PLINQ anyway? PLINQ is an extension to LINQ, part of the Parallel Tasks library that is shipping as part of .Net 4.0. You know how you splashed out for that quad-core, hyper-threading enabled processor and geeked out over all those little processor utilisation charts in Task Manager – then noticed that your CPU rarely hits more than 12.5% total utilisation? Well PLINQ helps you put those lazy cores to work. 
var gamesLengths
= 1.To(numberOfTrials)
.AsParallel()
.Select(trial =>
{
var die = new Die();
return board.
FirstPlace
.Unfold(place => place.MoveOn(die.Roll()))
.TakeWhile(place => !place.IsLastPlace)
.Count();
})
.ToList();
Spot it? Check out line 3. AsParallel(), that’s all you need to add. It takes a standard Linq-to-Objects query, and splits the work across multiple threads. On my bog-standard dual-core home laptop, that change took the time to run 1 million iterations down from 58 seconds to 36. That’s a 1.5x speed-up – by changing one line of code! And the best thing is, the speed-up increases as the number of cores in your machine goes up. On my Core i7 Quad core box at work, the simulation took 7 seconds in its parallelised form – and 9 seconds without the AsParallel magic! Still a 1.3x speed up – but overshadowed by the sheer awesomeness of the Nehalem architecture!
I should point out one subtlety here. You might have been wondering why it was necessary to create a new Die for every game? Why not share a die between games, like you do in the real world? The reason is the multiple threads introduced by the AsParallel() call. The Roll() method on Die calls through to Random.Next() under the covers, and the Next method isn’t thread-safe.
The easiest fix then, is to give each game its own Die. But there’s another thing: with all those threads beavering away simultaneously there’s a good chance that several Die will be created at the same time, each initializing their own instance of Random at the same time. Since Random by default seeds itself from the system clock, this would result in identical games being played – not exactly representative of the real world.
So what I do is have a static instance of Random which I use to seed all the others, taking care to take a lock on it of course:
class Die
{
private Random _random;
private static Random _seedGenerator = new Random();
public Die()
{
lock (_seedGenerator)
{
_random = new Random(_seedGenerator.Value.Next());
}
}
public int Roll()
{
return _random.Next(1, 7);
}
}
