Monty Hall simulator: is there a better way to do this?

[robspyke]

Dear All,

I am learning c at the moment - for recreational purposes really more
than anything else - and I was just wondering if I could pick your
collective wisdom on how best to code a problem.

Basically I am certain some of you have heard of the monty hall
probablity puzzle. To recap:

1. Game show. 3 doors, Car behind door. 1 x donkey each behind others.
2. Contestant has to pick the winning door (the one with the car!)
3. Contestant picks one door (say door A)
4. Host (who knows what's behind all doors) will then open one of the
remaining unchosen doors, say door B, which he knows has a donkey
behind.
5. Remaining closed doors, door A which contestant picked, and door C.
6. Host then asks contestant if he wants to make a switch for door C.

Probabilistically it makes most sense to switch in the long run, but I
found this concept difficult to grasp initially and so have others. To
prove it (besides algebraically) I wrote the program below to run a
simulation of an arbitrary no. of iterations. It should (hopefully) be
clear to most of you what the code does.

I am trying to learn is how to code C efficiently and correctly and
optimally etc. So if you can improve on the code please do chip in.

Oh, just in case some of you are wondering... this is NOT
homework/coursework etc - purely recreational. I fortunately do not
depend on this to earn a living either I'm just demented enough to
be wanting to learn C.

I've paid most attention to the algorithm, so if the rest of the
supporting bits are crap... well that's entirely my fault

Code starts below:
--- montyhall.c ---

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// macro to return a random no from 1 - n
#define random(n) (1 + rand()%n)

// constant declarations used to reference the 4 int array
// containing the frequencies of the outcome of the simulation
#define switchdoor_correct 0
#define switchdoor_wrong 1
#define no_switchdoor_correct 2
#define no_switchdoor_wrong 3


// function prototypes
int * monty_create ();
void monty_calc (int *freq, int interations);
void monty_display (int *freq);
void setup ();

int main (int argc, char *argv[])
{
int * results;

setup();
if (argc !=2)
{
printf("Usage: Monty x\n\nWhere x = no of iteratons.\n");
exit(1);
}
results = monty_create();
monty_calc(results,atoi(argv[1]));
monty_display(results);
free (results);
}

int *monty_create()
{
int *array;
array = (int *) malloc (sizeof(int)*4);
return array;
}


void monty_calc (int *freq, int counter)
{
int x, actual, guess, switchdoor, index;

// zero out array passed to function
for (x=0; x<4;*(freq+x)=0, x++)
;

// do stated no. of iterations in counter
for (x=0;x < counter; x++)
{
actual = random (3); // prize is behind this door
guess = random (3); // contestant's guess

// contestant's decision to switch or not 50:50
switchdoor = rand() %2 ; //true = switch

//the logic is here - calcs contestant guesing
index = (actual == guess) ?
( (switchdoor) ? (switchdoor_wrong):
(no_switchdoor_correct)
)
:
( (switchdoor) ? (switchdoor_correct):
(no_switchdoor_wrong)
);
++*(freq+index);
}
} // all events recorded in frequency array returned by
reference.

void monty_display( int * freq)
{
printf("Switching the door: Correct=%d, Wrong=%d\n",
freq[switchdoor_correct], freq[switchdoor_wrong]);
printf("Not switching... : Correct=%d, Wrong=%d\n",
freq[no_switchdoor_correct], freq[no_switchdoor_wrong]);
printf("\nTotal no of iterations: %d\n",
freq[0]+freq[1]+freq[2]+ freq[3]);
printf("Probability of prize (switching) : %f\n",
freq[switchdoor_correct]/(float)(freq[switchdoor_wrong]+freq[switchdoor_correct]));
printf("Probability of prize (no switch) : %f\n",
freq[no_switchdoor_correct]/(float)
(freq[no_switchdoor_correct]+freq[no_switchdoor_wrong]));
}

void setup()
{
printf ("Monty Hall Simulator \n\n");
srand( (unsigned int) time(NULL)/ 2 );
}

 

[Christian Bau]

Dear All,

I am learning c at the moment - for recreational purposes really more
than anything else - and I was just wondering if I could pick your
collective wisdom on how best to code a problem.

Basically I am certain some of you have heard of the monty hall
probablity puzzle. To recap:

1. Game show. 3 doors, Car behind door. 1 x donkey each behind others.
2. Contestant has to pick the winning door (the one with the car!)
3. Contestant picks one door (say door A)
4. Host (who knows what's behind all doors) will then open one of the
remaining unchosen doors, say door B, which he knows has a donkey
behind.
5. Remaining closed doors, door A which contestant picked, and door C.
6. Host then asks contestant if he wants to make a switch for door C.

What the contestant should or should not do depends very much on the
_exact_ rules, and very slight changes to the rules make a huge
difference. With your set of rules the host has no choice what to do,
that makes it easy.

The usual "interesting" rules include that the host has the choice not
to open any door at all, and the host may have decided to help you or
not to help you.

 

[Thomas Stegen CES2000]

Code starts below:
--- montyhall.c ---

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// macro to return a random no from 1 - n
#define random(n) (1 + rand()%n)

This is not a good way to generate random numbers. Have
a look at:

http://www.eskimo.com/~scs/C-faq/q13.16.html

// constant declarations used to reference the 4 int array
// containing the frequencies of the outcome of the simulation
#define switchdoor_correct 0
#define switchdoor_wrong 1
#define no_switchdoor_correct 2
#define no_switchdoor_wrong 3

It is conventional to use UPPERCASE letters for macros like
this. I would strongly recommend you follow convention unless
you have a reason not to. In this case I don't think you have.

// function prototypes
int * monty_create ();
void monty_calc (int *freq, int interations);
void monty_display (int *freq);
void setup ();

int main (int argc, char *argv[])
{
int * results;

setup();
if (argc !=2)
{
printf("Usage: Monty x\n\nWhere x = no of iteratons.\n");
exit(1);
}
results = monty_create();
monty_calc(results,atoi(argv[1]));
monty_display(results);
free (results);
}

int *monty_create()
{
int *array;
array = (int *) malloc (sizeof(int)*4);

When using malloc you want to minimize explicit type
dependencies as the ones you have here. Also you
need to check for success or failure.

This is the recommended way of using malloc:

array = malloc(4 * sizeof *array);
/*Now check for failure*/
if(array == NULL)
{
handle_memory_errer();
}

So if the type of array changes then you will not have
to change this code.

return array;
}


void monty_calc (int *freq, int counter)
{
int x, actual, guess, switchdoor, index;

// zero out array passed to function
for (x=0; x<4;*(freq+x)=0, x++)
;

I would write the above.
for (x = 0; x < 4;, x++)
freq[x] = 0;

Also note the spaces between certain operators and their
operands. These are just minor style issues but in this
case I honestly think "my" version is an improvement.

// do stated no. of iterations in counter
for (x=0;x < counter; x++)
{
actual = random (3); // prize is behind this door
guess = random (3); // contestant's guess

// contestant's decision to switch or not 50:50
switchdoor = rand() %2 ; //true = switch

//the logic is here - calcs contestant guesing
index = (actual == guess) ?
( (switchdoor) ? (switchdoor_wrong):
(no_switchdoor_correct)
)
:
( (switchdoor) ? (switchdoor_correct):
(no_switchdoor_wrong)
);

This certainly look impressie... Well, not really. That you
can do this does not mean you should. Put it this way,
I am not even going to attempt to decipher this

++*(freq+index);

Again, I prefer array notations. I find those easier to keep
in mind than just using arithmetic and dereferencing.

freq[index]++;

}
} // all events recorded in frequency array returned by
reference.

void monty_display( int * freq)
{
printf("Switching the door: Correct=%d, Wrong=%d\n",
freq[switchdoor_correct], freq[switchdoor_wrong]);
printf("Not switching... : Correct=%d, Wrong=%d\n",
freq[no_switchdoor_correct], freq[no_switchdoor_wrong]);
printf("\nTotal no of iterations: %d\n",
freq[0]+freq[1]+freq[2]+ freq[3]);
printf("Probability of prize (switching) : %f\n",
freq[switchdoor_correct]/(float)(freq[switchdoor_wrong]+freq[switchdoor_correct]));
printf("Probability of prize (no switch) : %f\n",
freq[no_switchdoor_correct]/(float)
(freq[no_switchdoor_correct]+freq[no_switchdoor_wrong]));

You might be the victim of some e-mail clients linewrapping
whims here. If not the indentation leaves a bit to be desired.

Other than that it looks good. I would say that you definetely
are on the right track.

Hope I gave you something to think about at least.

One thing I would do for this kind of program is to just drop
the extra prototyping at the top and just rearrange the
order of the functions until they fit. This is probably the most
minor point I've made here.

 

[robert spyke]

robspyke wrote:

This is not a good way to generate random numbers. Have
a look at:

http://www.eskimo.com/~scs/C-faq/q13.16.html

Okay... I see the potential pitfall. I wonder if my compiler libraries
are affected by this.

While we are on this subtopic, can someone illustrate a good
algortithm for random no. generation (ie from scratch, not using any
libraries). I seem to recall some sort of a method involving integer
multiplies, divides and modulus's.... details are really hazy.

I am particularly keen on methods that avoid floating point math
altogether.

I've been trying to think of a faster way, and I suspect the only way
this gets faster is if either I code it in asm..

or I change the program logic , and I just can't think of any other
optimizations at source code level...

One other question: I am particularly interested in learning how to
write the fastest, tightest c code there is (I am not afraid to get my
hands dirty using asm) but if there was a particularly good book out
there on optimizing c coding....

or how to design or simplify algorithms in the general sense....

I would be very grateful for recommendations!

Thanks

Rob

PS - this is probably an offtopic point but if someone can tell me
what intel/windows based compiler offers the easiest, no hassle way to
slip in asm statements (preferably at source level), that would be
great - you can email me at the above (obviously knock of the nospam
bits). I've been thinking of looking at borland because it's so
incovenient to stuff asm into gcc.

 

[robert spyke]

While we are on this subtopic, can someone illustrate a good
algortithm for random no. generation (ie from scratch, not using any
libraries). I seem to recall some sort of a method involving integer
multiplies, divides and modulus's.... details are really hazy.

I am particularly keen on methods that avoid floating point math
altogether.

I've been trying to think of a faster way, and I suspect the only way
this gets faster is if either I code it in asm..

My apologies - My mistake - a paragraph got cut out before the last
paragraph above. I meant I was looking for a faster way to implement
my algorithm in the original post - not random no generation, although
given the right algo asm may be tempting

Mea culpa, you can flog me now

Rob

 

[Neil Cerutti]

Dear All,

I am learning c at the moment - for recreational purposes
really more than anything else - and I was just wondering if I
could pick your collective wisdom on how best to code a
problem.

Basically I am certain some of you have heard of the monty hall
probablity puzzle. To recap:

1. Game show. 3 doors, Car behind door. 1 x donkey each behind others.
2. Contestant has to pick the winning door (the one with the car!)
3. Contestant picks one door (say door A)
4. Host (who knows what's behind all doors) will then open one of the
remaining unchosen doors, say door B, which he knows has a donkey
behind.
5. Remaining closed doors, door A which contestant picked, and door C.
6. Host then asks contestant if he wants to make a switch for door C.

Probabilistically it makes most sense to switch in the long
run, but I found this concept difficult to grasp initially and
so have others. To prove it (besides algebraically) I wrote the
program below to run a simulation of an arbitrary no. of
iterations. It should (hopefully) be clear to most of you what
the code does.

The Monte Carlo approach is overkill. There are a very small
number of possibilities in this case (X = car, O = donkey), so
you can write an exhaustive solution.

Car_In Init_Choice Strat1_Wins? Strat2_Wins?
0: a a
0: a b
0: a c
1: b a
1: b b
1: b c
2: c a
2: c b
2: c c

Have your program go down the list, filling in the Wins columns
as you go, once for both strategies. At the end, report which
strategy won more often.

I am trying to learn is how to code C efficiently and correctly
and optimally etc. So if you can improve on the code please do
chip in.

A efficient algorithm is the place to start.

 

[Neil Cerutti]

The Monte Carlo approach is overkill. There are a very small
number of possibilities in this case (X = car, O = donkey), so
you can write an exhaustive solution.

Car_In Init_Choice Strat1_Wins? Strat2_Wins?
0: a a
0: a b
0: a c
1: b a
1: b b
1: b c
2: c a
2: c b
2: c c

Have your program go down the list, filling in the Wins columns
as you go, once for both strategies. At the end, report which
strategy won more often.

Ugh! I did one too many revisions and one too few reviews on that
one. Please ignore the X and O comment, and the numbers down the
left side.

 

[robert spyke]

The Monte Carlo approach is overkill. There are a very small
number of possibilities in this case (X = car, O = donkey), so
you can write an exhaustive solution.

Taken to the extreme, you could say that even your program is
superfluous as you can prove all this with probability calculus.

I did it because some people I was duscussing the problem with did not
believe it happened in the long run. So? Model it in the long run and
show them the figures.

Okay, that's probably because I am a bad probablity and stats teacher
- again something I have to say I do not do in real life

A efficient algorithm is the place to start.

Thanks, you are right. Mine's about as efficient as I see it (given
what I am trying to achieve) but I'm willing to bet someone else can
improve on it.

Rob

 

[E. Robert Tisdale]

Dear All,

I am learning c at the moment - for recreational purposes really more
than anything else - and I was just wondering if I could pick your
collective wisdom on how best to code a problem.

Basically I am certain some of you have heard of the Monty Hall
probablity puzzle. To recap:

1. Game show. 3 doors, Car behind door. 1 x donkey each behind others.
2. Contestant has to pick the winning door (the one with the car!)
3. Contestant picks one door (say door A)
4. Host (who knows what's behind all doors) will then open one of the
remaining unchosen doors, say door B, which he knows has a donkey
behind.
5. Remaining closed doors, door A which contestant picked, and door C.
6. Host then asks contestant if he wants to make a switch for door C.

This is a version of the "Three Prisoners Paradox"
introduced by Martin Gardner in the October 1959 issue
of Scientific American.
A version similar to the one you described
was presented by Marilyn vos Savant in Parade Magazine in 1990.
Martin Gardner presents another version in
"A Quarter-Century of Recreational Mathematics",
Scientific American, August 1998, pages 68-75.

"Mr. Jones, a cardsharp, puts three cards face down on a table.
One of the cards is an ace; the other two are face cards.
You place a finger on one of the cards, betting that this card is the ace.
The probability that you've picked the ace is clearly 1/3.
Jones now secretly peeks at each card.
Because there is only one ace among the three cards,
at least one of the cards you didn't choose must be a face card.
Jones turns over this card and shows it to you.
What is the probability that your finger is now on the ace?"

Well, obviously the probability is 1 that you have picked the ace.
Otherwise, why would a cardsharp like Mr. Jones show
one of the face cards and offer to let you change your mind?
Martin Gardner made a subtle error in presenting this version
of the Three Prisoners Paradox and never noticed the mistake.

The Three Prisoners Paradox is not a valid test
of your understanding of probability.
The probabilities are trivial to calculate.
It is a test of your ability
to sort out the subtle details of a story problem --
both by the person telling and being told the story.

If, on the other hand, Monty Hall is obliged
by the rules of the game show
to always open a door with a donkey behind it
and offer the contestant a chance to switch,
then the contestant *should* always switch
because the contestant would win the car more frequently *if*
the contestant were to play the game a large number of times.

The odd thing about Martin Garner's 1998 example is that
he didn't realize that he had changed the rules
and he concluded Mr. Jones' victim should always switch
for exactly the same reason that Monty Hall's contestant
should switch.

 

[Neil Cerutti]

Taken to the extreme, you could say that even your program is
superfluous as you can prove all this with probability
calculus.

That is true. This is a trivial enough problem that a computer
program isn't really necessary. But more simple projects are like
that.

I did it because some people I was duscussing the problem with
did not believe it happened in the long run. So? Model it in
the long run and show them the figures.

A truth table, as I suggested, is possibly more convincing.

There are good applications for the Monte Carlo method. For
example, when the set of possible states gets really large, or
the math gets really hard. ;-)

For example, a program determining the chances of rolling 35 or
higher with eight six sided dice, re-rolling all ones might be
easier to write in the Monte Carlo method.

 

[nrk]

//the logic is here - calcs contestant guesing
index = (actual == guess) ?
( (switchdoor) ? (switchdoor_wrong):
(no_switchdoor_correct)
)
:
( (switchdoor) ? (switchdoor_correct):
(no_switchdoor_wrong)
);

As long as we're into this kind of obfuscation, why not do:

index = (switchdoor << 1) | (actual == guess);

and interpret index appropriately?

-nrk.