/************************************************************/
/* */
/* Monte Carlo analysis of the Monte Hall problem */
/* */
/* Started: 25 March 2010 */
/* Last edited: 25 March 2010 */
/* Status: Have painfully, but ultimately */
/* successfully, translated it into C */
/* */
/* (Actually, the translation was easy. As always with */
/* C programs, it was the debugging that took forever.) */
/* */
/* WARNING: this program is painfully slow, at least as */
/* compiled with Watcom C. Apparently Watcom generates */
/* code that's only about one tenth as fast as the code */
/* generated by XDS Modula-2. It is known, from other */
/* tests, that C compilers can't do the optimisations */
/* that compilers for high-level languages can do, but */
/* this is one of the worst discrepancies I've ever seen. */
/* */
/************************************************************/
#include
#include
#include
/************************************************************************/
/* GLOBALS */
/************************************************************************/
/* The definitions that have to be added to every C program. */
typedef unsigned char BOOLEAN;
#define FALSE 0
#define TRUE 1
#define EQ ==
/************************************************************************/
#define testing FALSE
typedef unsigned int Door;
/* It's not obvious how to define a set in C. I will, however, choose */
/* an implementation where bit i (i = 1..3) is set to say that door i */
/* is included in the set. The compiler can't enforce this, of course, */
/* but we will place trust in the fact that this code has been */
/* translated from working code in a higher-level language. */
typedef unsigned int DoorSet;
/************************************************************************/
/* MISCELLANEOUS UTILITIES */
/************************************************************************/
static BOOLEAN DoorInSet (Door d, DoorSet S)
/* Returns TRUE iff door d is in set S. */
{
return ((S & (1 << d)) != 0);
}
/************************************************************************/
static DoorSet Exclude (Door d, DoorSet S)
/* Excludes d from set S. */
{
return (S & ~(1 << d));
}
/************************************************************************/
/* RANDOM NUMBER GENERATION */
/************************************************************************/
static void Randomize (void)
/* Resets the random number generator. */
{
srand (clock());
}
/************************************************************************/
static int RandInt (int min, int max)
/* Returns a random number between min and max, inclusive. */
{
return (min + (rand() % (max - min + 1)));
}
/************************************************************************/
static Door RandomDoor (DoorSet ChooseFrom)
/* Chooses a random door. */
{
Door d;
unsigned int i, N;
/* How many doors are in the set? */
N = 0;
for (d = 1; d <= 3; d++)
{
if (DoorInSet (d, ChooseFrom)) N++;
}
/* Choose a random number that depends on N. */
if (N == 0)
{
printf ("ERROR: There are no doors to choose from.\n");
return 0;
}
i = RandInt(1, N);
/* We want to return the i'th member of the set. */
d = 1;
while (i > 0)
{
if (DoorInSet (d, ChooseFrom)) --i;
/* If you're translating this code into another language */
/* then you should, as a matter of defensive programming, */
/* check for d = MAX(DoorNumber) at this point. (That */
/* should never happens, but maybe there's a bug in the */
/* code.) In Modula-2 that's a non-issue, because the */
/* run-time system will catch an "out of range" error. */
if (i > 0)
{
if (d == 3) printf ("Serious bug.\n");
d++;
}
}
return d;
}
/************************************************************************/
/* THE TOP-LEVEL PROCEDURES */
/************************************************************************/
static BOOLEAN ContestantWins (BOOLEAN MontyKnows, BOOLEAN UserSwitches)
/* A single simulation. The first parameter is TRUE iff Monty */
/* knows where the prize is, and will avoid revealing that location */
/* if possible. The second parameter is TRUE iff the user will */
/* decide to switch if given the choice. We return TRUE iff the */
/* contestant wins in this simulated game. */
{
#define AllDoors 14
Door door, PrizeDoor, ChosenDoor, OpenDoor;
DoorSet S;
PrizeDoor = RandomDoor (AllDoors);
ChosenDoor = RandomDoor (AllDoors);
/* The following commented-out line can be uncommented if you */
/* want to simulate the case where the contestant always */
/* chooses the same door. */
/*ChosenDoor = 1;*/
/* Now Monty has to decide which door to open. The choice */
/* depends on whether Monty knows where the prize is. */
S = AllDoors;
S = Exclude (ChosenDoor, S);
if (MontyKnows) S = Exclude (PrizeDoor, S);
OpenDoor = RandomDoor (S);
if (testing)
{
printf (" The prize is behind door %u", PrizeDoor);
printf (" and the contestant has chosen door %u\n", ChosenDoor);
printf (" Monty has opened door %u\n", OpenDoor);
}
/* If Monty accidentally reveals the prize (which can happen */
/* only if MontyKnows is FALSE), the contestant wins without */
/* having to make a decision about switching. */
if (OpenDoor == PrizeDoor) return TRUE;
if (UserSwitches)
{
S = AllDoors;
S = Exclude (ChosenDoor, S);
S = Exclude (OpenDoor, S);
/* S now has only one member, and the following loop */
/* will find it. */
for (door = 1; door <= 3; door++)
{
if (DoorInSet (door, S)) ChosenDoor = door;
}
if (testing)
printf (" The contestant has decided to switch to door %u\n",
ChosenDoor);
}
return ChosenDoor == PrizeDoor;
}
/************************************************************************/
static double Simulate (BOOLEAN MontyKnows, BOOLEAN UserSwitches)
/* The first parameter is TRUE iff Monty knows where the prize is, */
/* and will avoid revealing that location if possible. The second */
/* parameter is TRUE iff the user will decide to switch if given */
/* the choice. The return result is the simulated probability */
/* of winning. */
{
#define NumberOfRuns 10000000
unsigned int run, NumberOfWins;
NumberOfWins = 0;
for (run = 1; run <= NumberOfRuns; run++)
{
if (testing) printf (" Run %u\n", run);
if (ContestantWins (MontyKnows, UserSwitches)) NumberOfWins++;
}
return (double)NumberOfWins / (double)NumberOfRuns;
}
/************************************************************************/
static void DoTheSimulations (void)
/* Tests all of the scenarios. */
{
double answer1, answer2;
Randomize();
printf ("Case A: Monty doesn't know where the prize is\n");
if (testing) printf (" Case A1: The contestant chooses not to switch\n");
answer1 = Simulate (FALSE, FALSE);
if (testing) printf (" Case A2: The contestant chooses to switch\n");
answer2 = Simulate (FALSE, TRUE);
printf ("If the contestant doesn't switch, his chances of winning are %f\n", answer1);
printf ("If the contestant does switch, his chances of winning are %f\n", answer2);
printf ("-------------------------------------------------------------------\n");
printf ("Case B: Monty DOES know where the prize is\n");
if (testing) printf (" Case B1: The contestant chooses not to switch\n");
answer1 = Simulate (TRUE, FALSE);
if (testing) printf (" Case B2: The contestant chooses to switch\n");
answer2 = Simulate (TRUE, TRUE);
printf ("If the contestant doesn't switch, his chances of winning are %f\n", answer1);
printf ("If the contestant does switch, his chances of winning are %f\n", answer2);
}
/************************************************************************/
int main (void) {DoTheSimulations(); return 0;}