CSE142

Homework #2

Let's Make N Deals

Electronic turn-in for part A due: Sunday, April 15, 10:00pm
Paper receipt for part A due in class Monday, April 16.

Electronic turn-in for part B due: Sunday, April 22, 10:00pm
Paper receipt for part B due in class Monday, April 23.

The Task The Game The Argument Part A details Part B details Supplied code and files Your write-up Guidelines, hints and help Submission Extras Announcements

You've been thinking about that stupid "Let's Make a Deal" problem again and it has your head swimming. Time to straighten things out with a little dose of mind-bogglingly swift simulation. Instead of reasoning through the problem (that's just gotten you dizzy!), you'll just have your computer run it 10,000 times and get the answer from that.

The Task

Let's Make a Deal (LMAD) was a game show in which a contestant could get a car by winning a guessing game. A slight variation of that game has become a popular point of contention among mathematicians, statisticians, and computer scientists.

Your job: write a "simulation" of the LMAD game to help us understand the best strategy for the game.

The LMAD Game: Slightly Modified for CSE

You, the contestant, are faced with three doors: numbers 1, 2, and 3. Behind one of these doors (selected at random) is a spool of fiber optic cable and a team of highly skilled personnel ready to install it right from the Internet backbone to your room. Behind each of the other two doors is a nasty old slice of leftover pizza from last quarter's ACM¹ movie night. The challenge, then, is to choose the door with fiber optic cable.

As the contestant, you get to choose one of the doors. Then, the host of the show selects from the two remaining doors one that has a slice of pizza behind it and reveals that door to you. (If the host has a choice of doors to reveal, we'll assume that he chooses randomly.) Note that he always can and always will reveal a door with pizza behind it -- never the door concealing the prize! Now, you have the choice of sticking with your door or switching to the remaining closed door. After you make this choice, the host reveals whether you have won (chosen the door containing fiber optic cable)².

For example, let's say the cable is randomly placed behind door #2. Doors #1 and 3 each hide only a slice of pizza:

Door #1 Door #2 Door #3

Old Pizza Fiber Cable Old Pizza

The contestant chooses door #3. The host then reveals that door #1 hides only a slice of pizza (he could not reveal door #2 because it has the cable!). Finally the contestant chooses to switch her pick to door #2, the door is opened to reveal the cable, and our contestant goes home to start a new day trading service with the extra bandwidth.

Door #1	Door #2	Door #3
Old Pizza	Fiber Cable	Old Pizza

The Argument

  Marvin: The chances that the door you picked has the cable are one
          in three, and that's all there is to it!

  Stewe: No, no. There's only two doors left after we see one slice
         that could possibly have the cable; so, the odds are 50/50!

  Marvin [agitated]: How could revealing that door POSSIBLY change the odds?

  Stewe [hackles rising]: New information affects posterior probabilities!!

  Marvin: Well, not in this case, it doesn't!

  Stewe: Does so!

  Marvin: Does not!

  Stewe: Does so!

  [This astute meeting of minds drags on before eventually the two realize 
   that they can have their students settle the argument for them.]

  Marvin and Stewe: We'll just have our students settle this for us!

All characters and events portrayed in this assignment are fictional. Any resemblance to real people or incidents is purely coincidental and entirely in your head.

Distracted by the LMAD problem, Stewe and Marvin haven't been able to concentrate on anything! (Why did you think they'd been so listless in lecture?) You need to resolve this problem through simulation. The assignment is broken down into two parts..

Part A details

Write a program that plays a single game of LMAD. It should run in "interactive" mode, meaning that a human user acts as the contestant. In this mode, the program automatically picks a door to contain the cable (at random). Then, it prompts the contestant for her choice. Next, the program reveals old pizza behind one of the other two doors. (Sometimes there will only be one legal choice of door to reveal and sometimes there will be two; your program should choose randomly if it has a choice.) Then, prompt the contestant to either switch or keep her pick and respond to her selection. Finally, reveal the cable and tell the user whether she won! Here are two sample runs to give you the idea. The program's output is in blue while the user's input is in green. There's no need to duplicate this exactly!

Please choose a door (1, 2, or 3): 3 Monty reveals a slice of pizza behind door #2. Do you want to switch doors? (y/n): y You switch to door #1. The cable was behind door #3! Sorry, you lose. Enjoy your pizza! Please choose a door (1, 2, or 3): 1 Monty reveals a slice of pizza behind door #3. Do you want to switch doors? (y/n): n You stick with door #1. The cable was behind door #1! You win! Enjoy your fiber connection!

You must implement the "play_game" function with its prototype (return type, parameters, and name) exactly as given. For Part A, it should play the LMAD game, but you can safely ignore both the parameter (the thing in parentheses) and the return value. However, put your game playing code into the function's body. You can (and should) also make use of the "random_int" function to generate random values when you need them. Its use is documented in the code. You are free to write any new functions you feel you need as well.

You should complete and submit this part by the Part A deadline listed at the top of this assignment!

Part B details

Part A is a good start toward resolving the argument, but Stewe and Marvin need lots of games to decide their argument! For this part, you will enable the program to play in two new, automatic modes and write a loop that lets you run many games automatically. For this part, you no longer need to support interactive play, but make sure you save a copy of your working Part A code just in case you need it!

The two modes you need to support are mode 's' for "switch" in which the program takes on the role of the contestant, automatically chooses a door, and always switches doors; and mode 'k' for "keep" in which the program automatically plays as well but always keeps its original pick. You should continue to use the "play_game" function to play a single LMAD game, but now it should use the value of its parameter (either 's' or 'k') to decide what mode to run in, and it should return a 1 for a win and a 0 for a loss.

Also, change your program so that it can run many games. Start by asking the user what mode she wants to play in (switch or keep) and how many games she wants to play. Next, play as many games as the user requested in the requested mode. Finally, summarize the games by telling the user what percentage of them were wins.

Here's a sample run to give you an idea of what this might look like. There's no need to duplicate this exactly!

Please enter a mode.. 's' for switch, or 'k' for keep: k Running in keep mode. I will never switch doors when Monty asks. Please tell me how many games to play: 10 Playing 10 games for you in keep mode.. You won 4 out of 10 games. That's 40.0% of the games! Maybe you should head straight to Vegas.

Supplied Code and Files

There is a small amount of supplied code this time around. We have provided a skeleton for your play_game function and a pre-written function for picking random numbers.

This is basically just a small starter for your project which includes the input statements and a sample output statement. Get it as a self-extracting archive or just the individual .c and .h files (only use these if you are not working on Windows): the starter .c file, the debugging header file, and the debugging source file.

The debug.c and debug.h files are purely to make debugging easier for you. They provide a function called "debug_printf" which you can call just like printf. However, debug_printf only actually prints in debug mode (it does nothing in release mode). You need not use debug_printf if you do not wish to. If you use it, you should not change it, as you will not be able to turn in a modified copy of it.

There is no sample solution this time! Use the example runs above to help you understand the problem.

Your Writeup

As with all assignments, you should include a text file in your submission called README.txt which describes your project. We have supplied a starter file that includes the questions below. As always, include the following standard info:

Your name
Your student ID
Your section
Approximately how many hours you spent on the assignment
Acknowledgment of any help you received on the assignment from any source other than the lectures/sections, the staff, or the course textbook. (Note that acknowledging activities which constitute cheating does not stop them from being cheating!)

For this assignment, we also request answers to two sets of questions. The sets cover parts A and B, and we suggest that you answer the Part A questions as you work on that part. However, none of the questions are due until the Part B deadline! Your entire README.txt should be turned in with Part B. Except for your experimental table, don't write more than a couple of sentences to answer any one of these questions!

Part A questions:

If we changed this problem so that there were four doors rather than three, how much more difficult would the program be to write?
Describe some function which (if someone else had written it for you) would make writing a program with four doors (or five, or more) easier. Why would it help?

Part B questions:

What's the most insightful or interesting question you thought of, asked, or heard asked about this assignment? If it was a question you heard, make sure you attribute the source! Explain briefly why this was such a good question and what you think the (an?) answer is.
What did you enjoy about this assignment? What did you hate? Could we have done anything to make it better (either the assignment itself or the way we handled handing it out, clarifying it, or turnin procedure)?
Finally, perform an experiment to determine the best strategy (switch or keep) and write up the results of your tests in your README.txt file. Your results should be in the form of a table with one column for the "keep" strategy and one column for the "switch" strategy. First, ensure that your program is working. Then, perform one run for each of the two conditions (switch and keep) playing 1, 10, 100, 1000, and then 10000 games. Record the percentage win results reported by your program in the appropriate location in the table. Below this, tell us what you think the actual odds of winning are with each strategy based on your data. Finally, suggest which strategy Marvin and Stewe should use when they appear on the game.

For your experiments, do not perform multiple runs and pick the "best" result! You are not being graded on how close to "correct" your results are; moreover, this is an inherently random process and there will be some variation in numbers. Intentionally selecting the results you prefer from multiple experimental trials is unethical. Moreover, in CSE in particular, it can be difficult to balance the need to debug to improve a complex implementation against the danger of unintentionally fudging results; this is a peril of being a scientist studying an artifact of your own invention. Do your best to make your balance on this assignment effective and ethical.

Guidelines, Hints, and Help

Coding style (following The Way) is vitally important for this assignment and all others. We will generally grade your code for three things: functionality (does it work?), style (is it readable, maintainable, and changeable?), and robustness (does it work well?). So, style will factor in heavily. Moreover, if your code does not work perfectly or is not perfectly robust, you will lose fewer points if we can understand the problem's cause... and good style will help us to read your code enormously.

The following advice should help greatly with your work. Some of it will seem vaguely familiar.

Start early. Despite the fact that it improves your life immensely, so many people ignore this advice. It always pays to get an early start.
Read these instructions completely and carefully.
Before writing a single line of code, plan your solution on paper. Try thinking about what you would do to perform the computations yourself.
Develop and test the program a bit at a time. Don't try to write the whole program and test it all at once. Instead, try getting a small part working. Then, test and add more pieces bit by bit until the whole job is done.
Use the debug_printf statement to help you debug the project. debug_printf works exactly like printf except that you can make the debug_printf statements stop printing in your final program. This means that you can leave the debug_printf statements in your code³! Curious how that can be? Change to release mode by doing something and see what happens.
Before turning in your work, test it thoroughly.
When it comes to grading, there's nothing better than a happy TA. Make your TA a happy TA: Your code should be neat and readable, with sensible variable names.
It's tempting to name a variable "switch" in this assignment. Don't. "switch" is a reserved word which we'll learn later.
Start right now!

Submission

Use the Part A turnin form to turn in the first part and the Part B turnin form for the second. Do not submit your debug.c and debug.h files! You should neither change nor submit these; we will provide copies on the turnin server.

Nothing better to do?

Finished your work for your three project courses, polished off that term paper, done with your eight hours of work on your full-time job, tucked the children in to bed, and feeling antsy for more? First, turn in a working version of your code. Then, try these ideas for further fun.

For the last assignment, you had a substantial testing tool (the visualization). Construct a testing tool for this assignment.
The LMAD problem extends naturally to more than three doors, more than one prize, and more than one revealed door. Try performing one of these extensions. Note that several of these are hard, especially without some of the tools we'll discuss later in the quarter. So, don't take this on until you have completed and turned in an elegant, working version of the assignment. Moreover, design your approach carefully before you start coding.

Finished with the assignment and all of the above suggestions? Well.. um.. Steve's bike could really use a polish (but no extra credit is available, d'oh!).

Footnotes:

"ACM" is the Association for Computing Machinery, the oldest and most prestigious organization in computer science. The local undergrad chapter performs various services for CSE students and students interested in computer science (including holding a regular movie night).
From the Car Talk website (cartalk.cars.com): Monty Hall himself pointed out that this is a minor deviation from the actual game. The contestant on the show does not get to switch after a door is revealed. On the other hand, if the contestand doesn't get to switch, is it still an interesting problem?
Like the rest of your code, however. The debug_printf statements should be well written and make sense. In other words, don't write:
debug_printf("# %d\n", cable_door);
Write this instead:
debug_printf("# Cable is behind door %d\n", cable_door);