Computation and Programming 2023
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Computation and Programming
2023
Project – The Monty Hall Problem
The project has two parts: simulate the Monty Hall Problem game and classify players according to the choices they make. First, let’s see what the Monty Hall problem is.
The Monty Hall problem
Consider a game where you have 3 doors in front of you.
Behind one of these doors there is a big prize (a car) and behind the remaining two doors there are no prizes, just agoat! But of course, you don’t know where the prize is.
You have two opportunities of choosing a door and if, in the end, you select the door behind which the car is,you win the car.
The game is played in three parts:
1. First, you choose a door (one of the three) without any additional information, so from your
perspective, there is a 1/3 chance of choosing the right door.
Let’s say you choose door number 1:
2. Then, while the chosen door remains closed, someone who knows where the prize is opens one of the two remaining doors (always one containing agoat), for instance, door 3:
3. Now you must decide if:
A. (Keep) You keep your initial choice, or
B. (Change) You change the door you want to choose as your final choice.
In this example, you can keep your choice of door 1, or you can change your choice to door 2.
What is the best strategy to win this game? Is it to use strategy A or B in the third step? Or is it irrelevant if you choose A or B?
1. Simulate the game [60 points]
The first part of your work is to build a program in C that simulates this game in such away that it can
estimate for you the probability of winning the game when you choose one of the strategies A or B.
For that, you must:
• Define a function run_once that simulates the execution of one instance of the game:
o Generate randomly the number of the door behind which the prize is.
o Generate randomly the first choice of the player.
o Depending on the previous two values, decide which door to open.
o Determine which would be the winning strategy of the run.
• Define a function run_simulation that executes the previous function a certain number of times (for instance, 100000) and accumulates the results (number of wins for each strategy).
• Display the estimation of the winning probability (number of wins / total runs) for each strategy.
For instance, the output of your program can be:
|
Total number of runs: 100000 Strategy A wins with probability 0.33 Strategy B wins with probability 0.67 |
This output is just an example. You can add other information like:
• The number of times strategy A won.
• The number of times strategy B won.
• The number of times each door had the prize behind it.
• …
You can also improve your program by adding some additional interaction like, for instance, asking the user the number of runs to execute.
2. Classify players [40 points]
Imagine a player plays this game 100 times. Would it be possible, by looking at the choices made, to know if it is likely that the player is using one of the above strategies (A or B)? The answer is Yes!
In this part of the project, you will use data from 3 different players to test, using Chi-square (x2) goodness of fittest, if the player is using strategy A, strategy B ornone of them.
For that you have access to the data corresponding to 100 games played by each player. For each game, there are 4 attributes:
• The door behind which the prize was.
• The first choice of the player.
• The door that was opened.
• The final choice of the player.
For instance, the line:
|
2 |
1 |
3 |
2 |
means that in the corresponding game:
• The prize was behind door 2.
• The player initially chose door 1.
• The door that was opened was door 3.
• The final choice of the player was door 2 (change).
We provide three CSV files with the data for 3 example players. The filenames are “ player1.csv”, “ player2.csv”, and “ player3.csv”.
We also provide a small library (read_player) that contains a single function that reads the data from a
player to an array of your program (example bellow).
In order to classify a player, you must:
• Load the corresponding data to your program (using the read_player function mentioned above).
• Analyze the corresponding array and calculate how many times the player kept its choice (and how many timeshe/she changed), and the percentage of wins.
• Calculate the Chi-square value for each of the strategies:
o Strategy A corresponds to an expectation of winning 1/3 of the time.
o Strategy B corresponds to an expectation of winning 2/3 of the time.
• Compare to the critical value at α=0.05 significance (with 1 degree of freedom).
• Decide if you reject or not the hypothesis that the player is using a particular strategy.
• Conclude (rejected just one or rejected both).
At the end, the output of your program can be something similar to:
|
Player X is following strategy A (keep). Player Y is following strategy B (change). Player Z is not following any of the two strategies . |
The above output is just an example. You can complement your program in various ways:
• Asking the user for the filename of the player you want to analyze.
• Display the values that served as the basis for the decision:
o The number of times a player decided to keep.
o The number of times a player decided to change.
o The value obtained for the statistics.
• You can define additional players (new CSV files) and test also with them. Just be careful being consistent between the number of lines you create in the file and the value of the third
parameter you pass to the read_player function.
Final Remarks
In thisLINKyou can find azip with all the files that you need.
Loading the CSV files
In order to load the CSV files that you should use to classify players, you should:
• Put the following files in the same directory:
o my_project.c – your project, the one that contains the main function.
o read_player.h – the header file corresponding to the definition of the read_player function.
o read_player.o – the implementation of the read_player function (already compiled independently).
o player1.csv – data for player 1.
o player2.csv – data for player 2.
o player3.csv – data for player 3.
• The content of the read_player.h file is explained there.
• In your main file (my_project.c), you should use the read_player function as illustrated bellow (just an example):
|
// include the standard-IO library, as usual #include <stdio.h> // include the header file with the needed prototype and the definition // of some symbolic constants. // notice that the file name is between “ “ and not < > // that’s because it is in the current folder #include "read_player.h" int main(void) { // define the variable to store, as a string, |
Running your program
To compile your program, you should use the command:
|
C:\Users\Administrator> gcc -o my_project -Wall my_project.c read_player.o |
Don’t forget to include the file read_player.oat the end of the command.
And then execute:
|
C:\Users\Administrator> ./my_project |
Projects can be done in groups of 2, 3 or 4 students.
You should submit a zip file containing:
• Your program (a file my_project.c)
• A document containing the identification of the group. For each member of the group, you should identify:
o Student number
o Chinese name
o Name in English
• A document with a copy of the execution of the program (copy/paste of the output)
• (optional) Any additional files you produced.
Submission is made through the elearning platform in a link that will be provided in a few days.
It is enough that one of the elements of the group submits the zip file.
Deadline for submission:
3 November 2023
2023-11-06
The Monty Hall Problem