CS 99

Summer 2002: HW8 7.22

A dice game; run, run, runaround vectors

Due Date: 07.25

1. Objectives

Completing all tasks in this assignment will help you:

• write nested loops
• simulate the playing of a game using rand
• use vectors to record useful data
  
  

First skim, then carefully read the entire assignment before starting any tasks.

2. A dice-throwing game
A, B, and C are throwing dice in that order; A wins if he throws a 1, 2 or 3; B wins if she throws a 4 or 5; C wins if he throws a 6. The dice rotate around from A to B to C to A, etc., until one player wins. Your task is to write a program that estimates the average number of rounds in a game (a round begins whenever A throws) and estimates the probabilities of each player winning.

Part A: Just one game
Begin by writing a program called ABCgame.m that simulates a single game. Note that the number of rounds in any given game is unknown, so you will want to use a while loop. Stop the game as soon as one of the players wins and display which player won as well as the round the game stopped.

Sample Output for Part A.
>>ABCgame
C wins in 2 rounds.

Part B: Lots of games
Now write a program that runs your game in Part A NUMTRIALS times, where NUMTRIALS is a large number of your choosing. Since you know exactly how many games you want to play you should use a for loop to run all the games.

Introduce two vectors: a 1 x NUMTRIALS vector called rounds, and a 1 x 3 vector called numWins. Store in element k of vector rounds the number of rounds it took to find a winner in game k. Store in numWins(1) the number of times A won, in numWins(2) the number of times B won, and in numWins(3) the number of times C won.

To estimate the number of rounds a typical game takes use the built-in MATLAB function mean (help mean) on variable rounds; to estimate the probabilities that each player wins, divide vector numWins by the number of trials. Report the results.

To test if your program is working correctly, you should find that for large values of NUMTRIALS, the average number of rounds is approximately 1.38462; and that the probabilities A, B, and C win are approximately 0.69231, 0.23077, and 0.07692 respectively.

Save your program as ABCtrials.m.



Sample Output for Part B.
>>ABCTrials %Note: your numbers may vary!
The estimated number of rounds to win a game using 16384 trials is 1.381226.
The estimated probabilities for the players to win are 0.69427, 0.22833, 0.077393.

Part C. Bonus*
Prove mathematically that the probabilities A, B, and C win are 9/13, 3/13 and 1/13. Can you also prove that the average number of rounds in a game is 18/13?

If you can prove the last one, I’ll be impressed!

3. Runaround arrays*

An n-element runaround array is characterized as follows:

• It is a vector with exactly n elements, with each element having a value between 1 and 9 inclusively.
• No digit appears more than once in the vector (n is thus £ 9).
• The elements form a sequence with each element telling where the next element in the sequence occurs. Starting with element 1, each digit gives the number of elements to move to the right to find the next digit in the sequence. If necessary, counting wraps around from the rightmost element back to the leftmost.
• The sequence must return to the first element after all digits in the number have been used exactly once.
  
  

An example should clarify the rules. Consider the vector [8 1 3 6 2]. To verify that this is a runaround array, we use the steps shown below:

1. Start with the first element, 8: [8 1 3 6 2]

2. Count 8 digits to the right, ending on 6 (note the wraparound): [8 1 3 6 2]

3. Count 6 digits to the right, ending on 2: [8 1 3 6 2]

4. Count 2 digits to the right, ending on 1: [8 1 3 6 2]

5. Count 1 digit to the right, ending on 3: [8 1 3 6 2]

6. Count 3 digits to the right, ending on 8 (where we began).

Write a program called Runaround.m that determines if a given vector input by the user is a runaround vector.

4. Submitting Your Work
Type your name, student ID, and the date at the top of each file. Only ABCGame.m and ABCTrials.m are required. Print and sign each file. Hand the signed documents along with your output to the teaching assistant at the beginning of lab on Thursday 25 July 2002.

*Challenge problem