Snakes and Ladders is a very simple board game between two or more players. The game has numbered squares that the player moves through by rolling a 6 sided dice but if a player lands on a certain square they get moved up (ladder) or down (snakes). This continues on until the a player reaches the last numbered square.
A single player will be simulated in this using the foreach and doParallel packages in R. Since each play through is independent of each other, this can be simulated in parallel allowing a great speed up.
This simulation will use a Milton Bradley’s Chutes and Ladders game board c. 1952, taken from Wikipedia page. This comprises of 100 squares with 9 ladders and 10 slides.
The ladders and slides/snakes will be set up as a data frame, allowing to quickly look up the board position and where to move the current location of the piece to. Where start is the square the ladder/slide starts and end is the square the piece will end at.
The next step is setting up to simulate a game by one person. To do this a record will be kept of the player position, number of rolls, and the number of snakes and ladders encountered. A random number will be rolled and position value will be increased and checked for ladder or snake, continuing on in this manner until the position is 100 or greater, ending the game.
This sets up the base game play, there are other variants such as rolling a 6 lets you roll again and need to roll exact value to reach the end of the board or you go back from the end the difference between the roll and remaining squares.
foreach and doParallel
Now, setting this up to simulate a certain number (N=100000) of play through using foreach and doParallel packages. The time taken to simulate N=100000 play through will be recorded for both parallel and sequential methods.
It is surprisingly easy to set up a parallel script in R using the foreach and doParallel packages. The steps outlined are described below.
The first step is registering the back-end using the registerDoParallel() function, without doing this foreach will not run! This can be specified to a certain amount of cores to use, registerDoParallel(4) will use 4 cores, or with no arguments will create 3 on Windows or ~ half the number of cores in your system if on Unix-like system.
To check how many cores/workers will be used the getDoParWorkers() will show this.
Now that the workers are set up, the foreach method can be called. This is like a regular for loop but with extra arguments. In this example, icount is the number of iterations to do and .combine tells foreach how to combine the data from each worker. Since a data frame like structure is wanted with number of rolls, number of slides, number of ladders, the rbind function is used.
To run the loop in parallel, %dopar% is called, if this was %do% it would run in parallel.
The data will be stored in a variable named out. If a variable is not assigned, the results are dumped to console.
To modify the above to run sequentially, the %dopar% argument is changed to %do%. The output and timing variable was also changed to show different timing between sequential and parallel.
The difference between running sequential and parallel:
Using these packages, it is easy to get a large speed up on parallizable problems.
Snakes and Ladders
To take a look at the turns to complete the game:
Take a look at a histogram of number of rolls to complete the game:
Plotting the above as a percentage chance to win the game in n rolls:
Finally the cumulative distribution function: