Homework 3

Due: Tuesday, February 20 at 11:59 pm

Submission: On Courseworks

Instructions

Please read the instructions carefully. An incorrectly formatted submission may not be counted.

To submit, put all python files in a folder called uni-hw3 (so for me this would be tkp2108-hw3). Then compress this folder into a .zip file. For most operating systems, you should be able to right click and have a “compress” option in the context menu. This should create a file called tkp2108-hw3.zip (with your uni). Submit this on courseworks.

Background

In this problem, we will explore a probability puzzle called the Monty Hall Problem. Named after the host of a classic television game show, this problem is seemingly paradoxical, but can be easily verified with a computer simulation. The problem setup is as follows:

You're on a game show and presented with three identical doors.
Behind one of the doors is a brand new car. Behind the other two are goats.

You are asked to pick a door. If you've picked the one continaing the car, you get to keep it.

Then, the host opens one two doors you did not pick, revealing a goat.
You are asked if you'd like to change your pick to the other unopened door. Do you switch?

Intuition would suggest that you started with a 1/3 change, and now you have a 1/2 chance, so changing your pick wouldn’t make a difference. But this is incorrect. A simple visual explanation is provided on Wikipedia, which I find very intuitive.

You had a 1/3 chance of picking the right door at the start, and a 2/3 chance of the prize being behind one of the remaining two doors. Within the two unpicked doors, each had a 50–50 chance of holding the prize.

Revealing the contents of the two unpicked doors doesn’t change the probability that your initial pick was right, it just shifts the probability between the two unpicked doors.

There are a variety of ways to show why, some more intuitive than others. In this assignment we will leverage a concept from probability theory called the Law of Large Numbers. This theorem basically says that if a coin flip has 50% chance of heads and 50% chance of tails, after 100 flips you might not get exactly 50 heads and 50 tails, but as the number of flips N -> ∞, the number of heads and tails will trend closer towards N/2.

So we will code up the Monty Hall problem and run a large number of simulations where we either choose to keep the original door or to switch. After a certain number of simulations, our win and loss rate should stabilize, and will correspond to our original odds.

We will also look at a generalized Monty Hall problem, where instead of 3 initial doors with 2 goats and 1 car, there are N initial doors with N-1 goats and 1 car. We would expect if our initial pick wins with probability 1/3 and switching wins with probability 2/3, then in the generalized problem we would expect our initial pick to win with probability 1/N and switching to win with probability N-1/N. We will test this hypothesis via simulation.




Part 1

Before we dive into the simulation, we first need to code up the actual game. If we’re careful in the design of our code, we will be able to reuse a lot of the logic of a manual player-vs-computer game when it comes time to write the computer-vs-computer simulation.

Representing the game

We will represent our game with two lists. The first list will be the contents of the doors, which we will randomly generate.

CAR = "c"
GOAT = "g"

door_contents = [CAR, GOAT, GOAT]

The second list will be the state of the game as viewer by the player. This starts out as:

PICK = "*"
UNKNOWN = "?"

game_state = [UNKNOWN, UNKNOWN, UNKNOWN]

We will then ask the user to pick a door (or in the case of the simulation, pick one at random). Assuming the user picked door 0, this would update the game state like so:

game_state = [PICK, UNKNOWN, UNKNOWN]

Using the known contents of the doors, we will then reveal goats, leaving the player’s choice and one extra door alone:

game_state = [PICK, UNKNOWN, GOAT]

We can then ask the user if they want to switch (or simulate them always switching), and swap the player’s pick with the remaining unknown door.

game_state = [UNKNOWN, PICK, GOAT]

Finally, to determine the result of the game, we can compare the game state (and the user’s pick in particular) to the original door contents.

door_contents = [CAR, GOAT, GOAT]
game_state = [UNKNOWN, PICK, GOAT]

users_pick = game_state.index(PICK)  # 1

if door_contents[users_pick] == CAR:
    print("You won!")
else:
    print("You lost!")

Running the game - the main function

Let’s take a look at some pseudocode and some skeleton code for our game. First, let’s start with the main function of our program:

CAR = "c"
GOAT = "g"
PICK = "*"
UNKNOWN = "?"


def main():
    # Ask the user if they want to run a single game (a) , or run a simulation (b)
    # Ask for number of doors
    # If the want to play a single game:
    #     call the playSingleGame function, passing in the number of doors
    # Else:
    #     print "Not Implemented Until Part 2"

This function will either call the playSingleGame function, or print out that we haven’t implemented the simulation yet (this will be done in part 2). We also create a few global variables to represent the contents of our board and the state of our game. This is just a convenience for us so we can use the variables in our code directly, without having to remember the underlying strings. So in our code we can just say x = CAR instead of having to remember that "c" represents the car. Now let’s look at the playSingleGame function.

Playing a single game

def playSingleGame(num_doors):
    play_again = "y"
    while play_again == "y":
        # Call a function to generate a list of door contents, 1 CAR and num_doors-1 GOATs
        # Call a function to generate the initial game state, all UNKNOWN

        # Print out the initial game state

        # Ask the user to pick a door
        # Update the game state to change the user's pick from UNKNOWN to PICK

        # Print the game state again

        # Call a function to update the game state to reveal goats, leave the user's pick and 1 other UNKNOWN untouched

        # Print the game state again

        # Ask the user if they want to switch, y or n
        # If they want to switch:
        #     Find the index of the user's current PICK
        #     Find the index of the remaining UNKNOWN
        #     Swap them

        # Print the user's pick
        # Print out the underlying door contents
        # If the index of the user's PICK == the index of the CAR:
        #     Print that the user won!
        # Else:
        #     Print that the user lost!

        # Ask if they want to play again
        play_again = input("Would you like to play again (y/n): ")

There’s a lot going on here! We’ve logically broken down the game into a sequence of smaller steps. Ideally, we’ll put these steps into functions so that we can run them later on without the user’s interactions (e.g. for the simulation). Let’s break down what each of these steps should do.

Play-again loop

def playSingleGame(num_doors):
    play_again = "y"
    while play_again == "y":
        ...
        play_again = input("Would you like to play again (y/n): ")

We’re pretty comfortable with this pattern, having used it a few times in HW2.

Generating door contents and game state

# Call a function to generate a list of door contents, 1 CAR and num_doors-1 GOATs
# Call a function to generate the initial game state, all UNKNOWN

Our first step is to generate the underlying door contents, and to generate the initial game state. If we make both of these reuseable functions, we’ll benefit later on. So essentially we want something like:

# Call a function to generate a list of door contents, 1 CAR and num_doors-1 GOATs
door_contents = generateDoors(num_doors)

# Call a function to generate the initial game state, all UNKNOWN
game_state = initializeGame(num_doors)

generateDoors should create a list of length num_doors, with one CAR and num_doors-1 GOAT. We should make sure its randomly shuffled to ensure our game is fair.

initializeGame should create a list of length num_doors, initially just containing UNKNOWN since the player hasn’t picked a door and goats have not been revealed yet.

Printing the game state

# Print the game state

This is as simple as printing " ".join(game_state).

Updating the game state

# Ask the user to pick a door
# Update the game state to change the user's pick from UNKNOWN to PICK

...

# Ask the user if they want to switch, y or n
# If they want to switch:
#     Find the index of the user's current PICK
#     Find the index of the remaining UNKNOWN
#     Swap them

For these types of operations, anytime we need to update the game state, we simply modify the game_state variable. If we need to look for the user’s pick, we can use game_state.index(PICK). When we want to find the remaining UNKNOWN, we can use game_state.index(UNKNOWN). And just like before, we should try to make them reuseable python functions.

# Ask the user if they want to switch, y or n
if switch == "y":
    game_state = switchUserPick(game_state)

Revealing the goats

# Call a function to update the game state to reveal goats, leave the user's pick and 1 other UNKNOWN untouched

Like before, ideally we want this to be a self contained function that randomly updates num_doors - 2 doors from UNKNOWN to GOAT (we leave the user’s PICK and a single UNKNOWN). So we want the code to look like:

# Call a function to update the game state to reveal goats, leave the user's pick and 1 other UNKNOWN untouched
game_state = revealGoats(game_state, door_contents)

The revealGoats function will be discussed further in class, but my pseudocode looks like:

def revealGoats(game_state, door_contents):
    # we want to leave 1 remaining goat and don't touch the user's pick, so let to_open be the length of the contents - 2
    # we will open doors until count == to_open, so initialize count to 0
    # while count < to_open
    #    pick a random door
    #    if its not already opened, its not the user's pick, and its not the car...
    #        open it and increment `count`
    # return game_state

Game result

# Print the user's pick
# Print out the underlying door contents
# If the index of the user's PICK == the index of the CAR:
#     Print that the user won!
# Else:
#     Print that the user lost!

Getting the result of the game is the last piece of the puzzle. The user’s pick is the PICK in game_state, and the position of the car is CAR in door_contents. So to check if the user won, we can check if the position of the user’s pick corresponds to the position of the car:

users_pick = game_state.index(PICK)
users_reward = door_contents[users_pick]

if users_reward == CAR:
    # Win!
else:
    # Lose!

Sample game

Here is what it looks like when I run the game from my solutions:

Would you like to play a single round (a), run a simulation (b): a
How many doors would you like to play with: 4

Game: ? ? ? ?

Please pick a door between 0 and 3: 2

Game: ? ? * ?

Revealing the goats!

Game: g g * ?

Would you like to switch (y/n): y
You picked door 3
The door contents were:

Game: g g g c

You won the car!

Would you like to play again (y/n): n



Part 2

In part 2, instead of playing the game ourselves, we will have the computer randomly play the game a certain number of times. Instead of printing out the results, we will collect the total number of wins and losses. If we have the computer always make the same choice (e.g. to switch), then the law of large numbers says that the total number of wins should roughly correspond to the initial probability of winning if we switch. The number of losses should then correspond to the probability of winning if we do not switch.

If this is confusing, just think about a game of heads and tails. If we always pick heads, and we flip a coin 1000 times, we expect to win ~500 times. If we didn’t know if the coin was fair and we won ~900 times, then we could surmise that the initial coin was not fair 50/50 heads/tails, but was rather closer to 90/10 heads/tails.

If we designed our code for part 1 well, we shouldnt have to write too much additional code. Here is what my updated pseudocode for the main function looks like:

    # (These lines are the same as before)
    # Ask the user if they want to run a single game (a) , or run a simulation (b)
    # Ask for number of doors
    # If the want to play a single game:
    #     call the playSingleGame function, passing in the number of doors
    # Else:
    #
    #     (new lines)
    #
    #     Ask the user how many simulations they want to run
    #     call simulateSingleGame, passing in the number of doors and number of simulations, return the number of wins and losses
    #     print out wins / number of simulations as win probability, losses / number of simulations as loss probability

Simulating a single game

Now, the only thing left for us to do is to run a single game configuration (e.g. how many doors) a certain number of times. Here is what my pseudocode looks like, attempting to reuse as much code as possible from before.

def simulateSingleGame(num_doors, num_simulations):
    wins = 0
    losses = 0
    for i in range(0, num_simulations):
        # Call a function to generate a list of door contents, 1 CAR and num_doors-1 GOATs
        # Call a function to generate the initial game state, all UNKNOWN

        # Pick a door randomly to represent the user's pick
        # Update the game state to change the user's pick from UNKNOWN to PICK

        # Call a function to update the game state to reveal goats, leave the user's pick and 1 other UNKNOWN untouched

        # Have the user switch:
        #     Find the index of the user's current PICK
        #     Find the index of the remaining UNKNOWN
        #     Swap them

        # If the index of the user's PICK == the index of the CAR:
            wins += 1
        # Else:
            losses += 1

Notice, almost all of this code is the same as before! By making our code modular and reuseable, we are able to use individual functions for different reasons and in different ways.

Sample simulation

Here is what it looks like when I run the simulation from my solutions:

Would you like to play a single round (a), run a simulation (b): b
How many doors would you like to play with: 3
How many simulations would you like to run: 1000
There were 663 wins and 337 losses
So keeping the original door wins with probability 33.7%, and switching wins with probability 66.3%

Here is a another run, this time choosing only 2 doors (e.g. there is no reveal). This run yields the expected result, of roughly 50/50 chance

Would you like to play a single round (a), run a simulation (b): b
How many doors would you like to play with: 2
How many simulations would you like to run: 1000
There were 475 wins and 525 losses
So keeping the original door wins with probability 52.5%, and switching wins with probability 47.5%

If we play a game with more doors, it becomes even more necessary to switch. This backs up the logic above, but its nice to have concrete simulation evidence:

Would you like to play a single round (a), run a simulation (b): b
How many doors would you like to play with: 10
How many simulations would you like to run: 1000
There were 904 wins and 96 losses
So keeping the original door wins with probability 9.6%, and switching wins with probability 90.4%