Pig Project

For this project you will write a program that simulates a dice rolling game.

This project is to be completed individually. I will be running everyone’s submissions through a code plagiarism detector to ensure everyone is doing their own work.

A main focus of this project is organizing your code into functions and making sure each function works as expected before moving on to the next. Read all the instructions carefully so that you know where the project is going, and then write and test your functions in the order described.

The Game Pig

In the game Pig, players race to score 100 points by rolling a single six-sided die. On your turn, you repeatedly roll the die until you choose to stop or you roll a 1, whichever comes first. If you choose to stop, then you add the sum of all your die rolls for the turn to your total score. However, if you roll a 1 before stopping, your score for this turn is 0.

For this project you will simulate a single player game of Pig, where the player is trying to reach 100 in as few turns as possible. This will not be an interactive game that will be played by a human, but rather the computer will play the game automatically using a simple strategy.

Your simulation will implement the following strategy: set a cut-off value and on each turn keep rolling until you reach the cut-off value or you roll a 1.

The question you will attempt to answer is this: what is the optimal cut-off value for this strategy? To answer this question you will run a series of Monte Carlo simulations. A Monte Carlo simulation is a simulation that involves random values and is run many times until the result converges to a numerical value.

We are interested in knowing the average number of turns it takes to reach 100 for a variety of cut-off values. So for each cut-off value you will play many games, sum up the number of turns in each game, and in the end divide the sum by the number of games to get the average number of turns for that cut-off value.

Writing the Program

Do not try to write this entire program at once. Instead, start with the simplest function and build up from there.

Create a main.c which will read command line arguments, call functions, and print results. Create simulation.h and simulation.c to put the rest of the functions in. Create a Makefile which will build the project.

Rolling a Die

In order to be able to run this simulation you need to be able to simulate rolling a die. To do this we will use the C standard library’s built-in random number generator.

C’s built in random number generator is a pseudo-random number generator (PRNG). PRNG’s are not truly random. A PRNG can generate a pseudo-random sequence which is initialized by specifying a seed. A seed is simply an integer value, and each seed value will result in a different sequence. A commonly used seed value is the current time.

To use C’s PRNG you must include stdlib.h, and to get the current time to seed the generator you must include time.h. The PRNG only needs to be seeded once each time the program runs, and a good place to do that is at the beginning of main(). Seed the number generator with this statement:

srand(time(NULL));

To get a random number, use the rand() function. rand() returns an integer value between 0 and RAND_MAX, a large constant that depends on your system, but is probably the maximum value of an int.

To roll a die we want the numbers 1 through 6, not 0 through RAND_MAX. rand() % 6 will divide the result of rand() by 6 and give us the remainder, resulting in a number from 0 through 5. Since we want numbers 1 through 6, you can use rand() % 6 + 1.

So here is your first function:

int roll_die() {
    return rand() % 6 + 1;
}

Put this function in simulation.c, put its prototype in simulation.h, and write code in main() that seeds the PRNG and then calls this function and prints out the result. Compile your program and then run it several times so that you are convinced that this function always returns 1 through 6 in a random fashion.

Playing One Turn of Pig

Once you are convinced that roll_die() works correctly, write a function that plays a single turn with a cut-off value that is passed in to the function, and returns the number of points for the turn. In this function you will need a loop which keeps rolling the die (by calling roll_die()) and adding up the sum of points until the cutoff is reached or it rolls a 1. Return the sum or 0 depending on whether it hit the cut-off or a 1 was rolled.

Edit main() so that it calls your function and prints out the turn total for the round. Compile your program and run it several times until you are convinced that your function plays a turn correctly.

Playing One Game of Pig

A game consists of repeated turns. The game stops when the score hits or exceeds 100. Write a function which takes a cut-off value as a parameter and repeatedly plays turns (by calling your turn function), adding up the sum of the turn scores until 100 is reached or exceeded. Your function should then return the number of turns.

You will want to pass the game function’s given cut-off parameter to the turn function for most of the game, but when the score gets close to 100 you will need to shrink the cut-off value. For example, say the cut-off is 20 and your current score is 92. You would not want to keep playing the next turn if your turn score hits or exceeds 8, because you have already won and you do not want to risk getting a 1 if you keep rolling. So if the difference between 100 and the current score is less than the cut-off, reduce the cut-off to be that difference.

Again, modify main() so that it calls your game function with a cut-off value and prints the number of turns it took to play the game. Run your program several times until you are satisfied that your game function works correctly.

Playing Many Games of Pig

Now write a function that performs a Monte Carlo simulation by playing many games with a given cut-off and returns the average number of turns for each game. This function should take 2 parameters: the number of games to play and the cut-off. Return the average as a double.

Modify main() again so it calls this function and prints the result. Have it play 100 games with a cut-off of 15. Run the program several times to make sure it works.

How Many Games to Play?

You’ll notice that if you’re only playing 100 games per simulation, the turn average will be rather different each time you run it. The more games you run, the more stable the average becomes.

Modify main() by adding argc and argv parameters if you have not already. This way you can pass in the number of games to run as a command line argument. To convert the argument (which will be a string) to an integer you can use a function called atoi(). Convert the second argument in argv to an integer like so:

int game_count = atoi(argv[1]);

Now when you run your program you can specify the number of games. If you called your executable pig you could run it like this to run 1000 games:

./pig 1000

Continue to increase the number of games in the simulation, running the program a few times each time. Keep increasing the number of games until the 2 digits after the decimal place in the average do not change when you run it repeatedly. Don’t be afraid to try big numbers, keeping in mind the maximum value of an int. If you get too big the program will take a long time to run. You can kill the program by pressing ctrl + c.

What is the Optimal Cut-off?

Now that you know how many games to run to get a stable average, modify main() so that it runs simulations in a loop, each time with a different cut-off value. Use the cut-off values 10 through 30 and inspect the results to see which cut-off value is lowest.

Submission

Answer the 2 questions in the file answers.md. Push all your code and your answers to git-keeper.

Git-keeper will test that all the required files exist, but will not test the code itself. For full credit you must answer the questions in answers.md and adhere to these requirements: