CS1101C Lab 7

Preliminary — Game of Sticks

The game of sticks is a variant of take-away games that involves two players picking out a number sticks from an initial pile of N sticks. In each turn, a player can pick out 1 to M sticks from the pile. Whoever takes the last stick(s) loses the game.

In this lab assignment, we shall write several variants of the game.

Note that due to the random nature of this assignment, your program output need not be exactly the same as the sample run, but results should still be consistent.

Question 1 — Two Human Players

• The number of sticks N in the initial pile (≥ 10). This input is assumed to be always valid.
• The maximum number of sticks M to pick up (between 2 to floor(√N) both inclusive). This input is assumed to be always valid.
• The starting player is determined randomly by the program.

Number of sticks (>= 10): 20 Maximum sticks to pick up (2 to 4): 3 Player #1: How many sticks to pick (1 to 3): 1 19 sticks remaining. Player #2: How many sticks to pick (1 to 3): 4 Player #2: You can only pick (1 to 3) sticks! Player #2: How many sticks to pick (1 to 3): 3 16 sticks remaining. Player #1: How many sticks to pick (1 to 3): 2 14 sticks remaining. Player #2: How many sticks to pick (1 to 3): 3 11 sticks remaining. Player #1: How many sticks to pick (1 to 3): -1 Player #1: You can only pick (1 to 3) sticks! Player #1: How many sticks to pick (1 to 3): 2 9 sticks remaining. Player #2: How many sticks to pick (1 to 3): 3 6 sticks remaining. Player #1: How many sticks to pick (1 to 3): 1 5 sticks remaining. Player #2: How many sticks to pick (1 to 3): 3 2 sticks remaining. Player #1: How many sticks to pick (1 to 3): 1 1 sticks remaining. Player #2 loses.

Number of sticks (>= 10): 10 Maximum sticks to pick up (2 to 3): 3 Player #2: How many sticks to pick (1 to 3): 3 7 sticks remaining. Player #1: How many sticks to pick (1 to 3): 3 4 sticks remaining. Player #2: How many sticks to pick (1 to 3): 3 1 sticks remaining. Player #1 loses.

A skeleton program lab7.c is provided to you.

• The seeding of the random number generator is provided for you. You might want to set the SEED to a fixed integer when developing your program.

  #define SEED 123

  You are reminded to replace with the original SEED before submitting your program.

• You are not allowed to change the main function. The same applies to questions 2 and 3 below.

• For simplicity, we shall assume that human players will not have suicidal tendancies, i.e one will NEVER take all sticks (or more than that) from the pile.

The name of your C program file must be called lab7q1.c, files with any other name will not be marked.

Question 2 — Human versus Random

Within the playGame function, the task is to invoke either humanPlay or randomPlay when the turn is 1 or 2 respectively. You are to implement the latter two functions with the following function prototypes:

• humanPlay(int *n, int m);
• randomPlay(int *n, int m);

Number of sticks (>= 10): 20 Maximum sticks to pick up (2 to 4): 3 Player #2: How many sticks to pick (1 to 3): 1 19 sticks remaining. Player #1: How many sticks to pick (1 to 3): 3 16 sticks remaining. Player #2: How many sticks to pick (1 to 3): 1 15 sticks remaining. Player #1: How many sticks to pick (1 to 3): 3 12 sticks remaining. Player #2: How many sticks to pick (1 to 3): 1 11 sticks remaining. Player #1: How many sticks to pick (1 to 3): 3 8 sticks remaining. Player #2: How many sticks to pick (1 to 3): 3 5 sticks remaining. Player #1: How many sticks to pick (1 to 3): 2 3 sticks remaining. Player #2: How many sticks to pick (1 to 3): 1 2 sticks remaining. Player #1: How many sticks to pick (1 to 3): 1 1 sticks remaining. Player #2 loses.

Number of sticks (>= 10): 10 Maximum sticks to pick up (2 to 3): 3 Player #1: How many sticks to pick (1 to 3): 3 7 sticks remaining. Player #2: How many sticks to pick (1 to 3): 1 6 sticks remaining. Player #1: How many sticks to pick (1 to 3): 3 3 sticks remaining. Player #2: How many sticks to pick (1 to 3): 1 2 sticks remaining. Player #1: How many sticks to pick (1 to 3): 1 1 sticks remaining. Player #2 loses.

As with human players, randomPlay should also not be suicidal.

The name of your C program file must be called lab7q2.c, files with any other name will not be marked.

Question 3 (Human vs Smart)

We shall replace the randomPlay in question 2 with smartPlay. It turns out that the game of sticks has a well-defined winning strategy provided the player starts first. We provide an example to illustrate the strategy.

Assume that we are presented with a pile of 7 sticks, and we need to pick up 1 to 3 sticks from the pile (i.e. M = 3). Notice that leaving 5 sticks for the other player will ensure us a win because in the next two turns, the possible picks are (1-3) or (2-2) or (3-1). This leaves one stick for the other player and thus he loses. So we pick up 2 sticks from the pile of 7 to leave 5 sticks.

If say, we are presented with a pile of 10 sticks, then there is no way we can leave 5 sticks for the other player in one move. However by backward induction, leaving 9 sticks is advantageous to us since the next two turns have possible picks of (1-3), (2-2) or (3-1) which would leave 5 sticks for the other player and as explained earlier, this is a winning situation. So given 10 sticks, we pick 1 to leave 9.

Your task is to generalize the above strategy for any values of N and M. Note that in the case of the other player starting first, we can only hope that he/she does not use our strategy. But if he/she does, then we have no choice but to delay our eventual loss by picking only one stick. This would hopefully buy us some chance for the opponent to make a mistake, so that we can capitalize on it.

Sample runs are given below with user input underlined. As per above, player #1 is the human player, while player #2 is the smart player.

Number of sticks (>= 10): 20 Maximum sticks to pick up (2 to 4): 3 Player #2: How many sticks to pick (1 to 3): 3 17 sticks remaining. Player #1: How many sticks to pick (1 to 3): 2 15 sticks remaining. Player #2: How many sticks to pick (1 to 3): 2 13 sticks remaining. Player #1: How many sticks to pick (1 to 3): 1 12 sticks remaining. Player #2: How many sticks to pick (1 to 3): 3 9 sticks remaining. Player #1: How many sticks to pick (1 to 3): 3 6 sticks remaining. Player #2: How many sticks to pick (1 to 3): 1 5 sticks remaining. Player #1: How many sticks to pick (1 to 3): 1 4 sticks remaining. Player #2: How many sticks to pick (1 to 3): 3 1 sticks remaining. Player #1 loses.

Number of sticks (>= 10): 50 Maximum sticks to pick up (2 to 7): 7 Player #1: How many sticks to pick (1 to 7): 1 49 sticks remaining. Player #2: How many sticks to pick (1 to 7): 1 48 sticks remaining. Player #1: How many sticks to pick (1 to 7): 7 41 sticks remaining. Player #2: How many sticks to pick (1 to 7): 1 40 sticks remaining. Player #1: How many sticks to pick (1 to 7): 7 33 sticks remaining. Player #2: How many sticks to pick (1 to 7): 1 32 sticks remaining. Player #1: How many sticks to pick (1 to 7): 7 25 sticks remaining. Player #2: How many sticks to pick (1 to 7): 1 24 sticks remaining. Player #1: How many sticks to pick (1 to 7): 7 17 sticks remaining. Player #2: How many sticks to pick (1 to 7): 1 16 sticks remaining. Player #1: How many sticks to pick (1 to 7): 6   ⇐ ooops! made a fatal mistake 10 sticks remaining. Player #2: How many sticks to pick (1 to 7): 1 9 sticks remaining. Player #1: How many sticks to pick (1 to 7): 1 8 sticks remaining. Player #2: How many sticks to pick (1 to 7): 7 1 sticks remaining. Player #1 loses.

Number of sticks (>= 10): 20 Maximum sticks to pick up (2 to 4): 3 Player #1: How many sticks to pick (1 to 3): 3 17 sticks remaining. Player #2: How many sticks to pick (1 to 3): 1 16 sticks remaining. Player #1: How many sticks to pick (1 to 3): 3 13 sticks remaining. Player #2: How many sticks to pick (1 to 3): 1 12 sticks remaining. Player #1: How many sticks to pick (1 to 3): 3 9 sticks remaining. Player #2: How many sticks to pick (1 to 3): 1 8 sticks remaining. Player #1: How many sticks to pick (1 to 3): 3 5 sticks remaining. Player #2: How many sticks to pick (1 to 3): 1 4 sticks remaining. Player #1: How many sticks to pick (1 to 3): 3 1 sticks remaining. Player #2 loses.

You are welcome to discuss the strategy in the IVLE forum, without giving the solution directly of course.

The name of your C program file must be called lab7q3.c, files with any other name will not be marked.

Question 4 (Random versus Smart)

Using your codes developed in questions 2 and 3, modify it such that you run a simulation for a user-specified number of trials. For each trial, N is randomly chosen to be between 10 and 100 both inclusive, while M is randomly chosen between 2 to floor(√N) both inclusive.

In this simulation exercise, we shall also request a specific seed for the user. Remember that you should seed the random number generator once per simulation, rather than for every trial. Remove all prompts with respect to a single game play. You are free to modify the main function to perform the simulation.

The sample run are as follow with user input underlined. Output the percentage win of the smart player to three decimal places.

Number of trials: 1000 Enter seed: 1 Percentage win of smart player: 99.900%

Number of trials: 1000 Enter seed: 123 Percentage win of smart player: 99.800%

Number of trials: 10000 Enter seed: 456 Percentage win of smart player: 99.780%

The name of your C program file must be called lab7q4.c, files with any other name will not be marked.

Note and Ponder

1. Assume that all user input is valid unless otherwise stated.

2. If your program does not work as you expect (logical errors), use extra printf statements to print out all the values of your variables to aid in your debugging.

3. There should be no blank lines at the start or end of each output run.

4. Most importantly, have lots of fun programming!

A total of 24 different hosts have accessed this document in the last 444 days; your host, nsrp-source.comp.nus.edu.sg, has accessed it 7 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.