Do you remember that scene from the movie 21 where Kevin Spacey gave our protagonist Ben the game show host problem?

What Kevin Spacey described is known as the Monty Hall problem. It became famous as a question from a reader’s letter to Marilyn vos Savant’s “Ask Marilyn” column in Parade magazine in 1990.

Marilyn’s answer caused quite a bit of controversy at the time and whilst I don’t understand the formal mathematical proof, it’s a problem that can be easily proved through simulations.

## Simulation with F#

First, let’s set up a few types to represent the problem domain:

Pretty self-explanatory here:

- behind every
*Door*is a*Prize*; - the
*Prize*is either a*Car*or a*Goat*; - you
*Win*if you get the*Car*in the end, otherwise you*Lose*

When you start a new game you always have three doors, arranged in some random order.

After you had given your initial choice, the game show host will reveal one of the doors that has a *Goat?.*

Here we have a function that takes in the *doors *and the player’s initial *choice*; and return the index of a *door *that:

- the player didn’t choose; and
- has a goat

Putting it together, we have a function that takes in the *doors* as well as the player’s *strategy* and return whether the player *Win *or *Lose *at the end of the game.

From the code above you can guess the type signature of the *strategy *function to be ** int –> int –> int**. That is, it takes two integers – the player’s initial choice and the index of the door the host has revealed – and return the player’s final choice.

Now, given the two choices we have – to stay or to change, we can represent it with two strategies:

*strategyA*would stay with the player’s original choice;*strategyB*would change

We can now use these two functions to call *play *with.

*p.s. notice we have essentially implemented the **Strategy** pattern, but without all the boilerplates and interfaces and classes? With just functions! Isn’t that sweet?*

To be kinder to ourselves, let’s add another helper function that will take in our chosen *strategy *and run a simulation of 1000 games, and return the number of games that we have won with this strategy:

Finally, let’s run our simulations and see how the two strategies perform.

Running this simulation over and over, *strategyB *consistently outperforms *strategyA *by roughly 2-to-1, which is exactly what we expected.

You can also just run the simulation yourself on **.Net Fiddle **here, just click the **Run** button at the top.

## Improving our code

Whilst the above is sufficient for its purpose and it’s a pretty short solution, there’re couple of things that can be improved in hindsight:

- player’s choice – to
*Stay*, or*Change*– is not explicitly represented in the domain; - whilst a
*Change*can only lead to one outcome – changing to the door that isn’t revealed nor initially chosen – it is expressed implicitly by the logic in*strategyB*; - if we were to introduce another strategy (e.g. decide to stay or change randomly) then we’d have to duplicate the logic for change.

To make these improvements is really easy. We can start by adding a type to present the two choices available to the player:

Then we can update the *play *function to work with it:

So now, our strategy implementations become much simpler:

Again, you can try out this updated version on **.Net Fiddle **here. It also includes a ‘random’ strategy which chooses to *Stay* or *Change *using the *rand* function we created earlier.

There are other things we can improve still. For instance, how do we encapsulate the constraint of having only 3 doors as part of our model?

This way, we can eliminate another invalid state using the type system. I’ll leave that as a teaser to you and feel free to share your solution in the comments!

Pingback: F# Weekly #34,#35,#36, 2015 | Sergey Tihon's Blog

Hans Krusewould use the array length instead of 2 or a type. (Vb.net/C# programmer talking)

Pingback: Done With Computers | The Monty Hall Problem

Pingback: F# Weekly #17-18, 2016 – Sergey Tihon's Blog