C++ Simulator for the Monthy Hall Game

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1 [but the door is not opened], and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice?

[From Wikipedia]

Introduction

The game is simple: first the player chooses a door, than the host opens one of the remaining doors which has a goat behind it, then the player is offered the chance to change door. At the end, the last door the player chose is opened and the hidden object is the player’s prize. The player’s objective is to open the door that hides the car.

To understand the gist of the game, whether it should be better to change the door or to keep the previously selected one, consider this simple explanation.

If you want to change door, then you will win if your first choice was a goat-door.
If you don’t want to change door, then you will win if your first choice was the car-door.

At the beginning, you can pick a goat-door with a probability of 2/3 (66%).
At the beginning, you can pick a car-door with a probability of 1/3 (33%).

If you decide to change door, you will win with a probability of 2/3.
If you decide not to change door, you will win with a probability of 1/3.

Well, this is the game, then it comes the simulator.

The Simulator

Code here: https://github.com/vincepii/MontyHallSimulator

I was watching the football match between Portugal and Czech Republic and getting bored.
My brother proposed me to implement a model to simulate the Monty Hall problem, and that was a great idea.

While I was at coding, I decided that it was more interesting to develop a full emulator of the game, rather than a tiny mathematical simulation model, and this is what I did. Nevertheless, the emulator performs well also for simulations (10,000,000 runs of the game in less than 7 seconds on my notebook).

If you want to try it, or take a look at the code, you can find it on GitHub.

If you are only interested in some results, this is what happens when running 10,000,000 cycles:

vince@vince-VPCSB1C5E:~$ montyhallsimulator --cycles 10000000

Number of games (total): 10000000
Number of times the player changed doors: 5002849
Games result (WON/TOTAL): 5003182/10000000 (50.0318%)
Winning rate when changing door: 3336568/5002849 (66.6934%)
Winning rate when NOT changing door: 1666614/4997151 (33.3513%)

It is funnier to see what happens every game, using the verbose mode:

vince@vince-VPCSB1C5E:~$ montyhallsimulator --cycles 1 --verbose

The player Chose door number 2
The host Chose door number 1
The Player Changed its door and picked door number 0
The Player Won the game, car behind door number 0

The simulator also works with more than three doors, applying the same rules. This could be interesting for statistical analysis.

For the complete list of options, just type – -help:

vince@vince-VPCSB1C5E:~$ montyhallsimulator --help
Program options:
  --help                Help message
  --doors arg (=3)      Number of doors (default: 3)
  --cycles arg (=1)     Number of runs of the game (default: 1)
  --verbose             Verbose mode, prints player and host actions (default: 
                        false)

Technicalities

The Pseudo-Random-Number-Generator that the simulator uses is the boost::mt19937, initialized with a time-dependent seed.

In order to test different PRNGs easily, the generator has been encapsulated inside an Adapter class and instantiated with a Singleton to ensure that always the same generator with the same seed is used across a simulation.

I have used the boost::program_options library for options parsing. If downloading the run-time libraries (e.g.: libboost-program-options-dev package under Ubuntu) is a problem for you, the main.cpp file can be easily edited to manually assign values to the doors, cycles, and verbose variables. Then the code for options handling can be removed.

I’ve used the CMake build system to create Makefiles for the code. That’s another requirement.

Advertisements

Don’t trust the temporaries (C++)!

Class X is defined as follows (C++):


class X {
    std::map<uint32_t, uint32_t> _map;
public:
    X() {
        for (uint32_t i = 0; i < 20; i++) {
            _map[i] = i + 10;
        }
    }

    std::map<uint32_t, uint32_t> getTheMap() const {
        return _map;
    }
};

The getTheMap method returns by value.

What is the output of this code?

X x;
std::map<uint32_t, uint32_t>::const_iterator it = x.getTheMap().begin();
std::map<uint32_t, uint32_t>::const_iterator et = x.getTheMap().end();

for (; it != et; it++) {
    std::cout << "[" << it->first << ";" << it->second << "]" << std::endl;
}

It’s undefined!

At lines 2 and 3, the map iterators are obtained on a temporary object which is destroyed just at the end of the statement. That’s because getTheMap() returns by value. Consequently, on the for loop at line 5, we are iterating over unallocated memory.

My main concern about class X code was to find a way to stop users using it the wrong way (such as in the above code sample). I was told on stackoverflow that in C++11 the STL itself should have a protection to make that code illegal.

Another interesting and very elegant solution is the use of a wrapper:

class X {
    std::map<uint32_t, uint32_t> _map;

    class InternalWrapper {
        const std::map<uint32_t, uint32_t>& _internalMap;

    public:
        InternalWrapper(const std::map<uint32_t, uint32_t>& map) :
            _internalMap(map)
        {}

        operator std::map<uint32_t, uint32_t>() const {
            return _internalMap;
        }

    };

public:
    X() {
        for (uint32_t i = 0; i < 20; i++) {
            _map[i] = i + 10;
        }
    }

    InternalWrapper getTheMap() const {
        return InternalWrapper(_map);
    }
};

The magic of this code is done by the automatic type conversion operator at line 12.

Now, the getTheMap() method returns an object of type InternalWrapper by value. This object can be implicitly converted to std::map<uint32_t, uint32_t> type, but it doesn’t have begin() and end() methods, so the following line of code is illegal:

std::map<uint32_t, uint32_t>::const_iterator it = x.getTheMap().begin();

The user is now prevented from using the interface incorrectly and the only way he can use it is the correct one, this one:

std::map<uint32_t, uint32_t> map = x.getTheMap();
std::map<uint32_t, uint32_t>::const_iterator it = map.begin();
std::map<uint32_t, uint32_t>::const_iterator et = map.end();

Wow!

Object-oriented blinking with Arduino

Yesterday I started programming again with Arduino.

First thing I setup the Eclipse environment and to test it I ran the very simple blink program.


void setup() {
 pinMode(13, OUTPUT);
 }

void loop() {
 digitalWrite(13, HIGH);
 delay(100);
 digitalWrite(13, LOW);
 delay(100);
 }

Then, I wanted to go OO, so I wrote a class to represent a blinking object!

Header:

class Blink {
 private:
 unsigned long _onInterval;
 unsigned long _offInterval;
 uint8_t _blinkingLedId;
 bool _ledActivity;

public:

Blink(unsigned long onInterval, unsigned long offInterval, uint8_t blinkingLedId);

void oneBlink();

void setLedActivity(bool ledActivity);
 };

Implementation:

Blink::Blink(unsigned long onInterval, unsigned long offInterval, uint8_t blinkingLedId) :
 _onInterval(onInterval), _offInterval(offInterval), _blinkingLedId(blinkingLedId)
 {
 _ledActivity = true;
 pinMode(_blinkingLedId, OUTPUT);
 }

void Blink::oneBlink()
 {
 // LED activity disabled?
 if (_ledActivity == false)
 return;

// ON
 digitalWrite(_blinkingLedId, HIGH);
 delay(_onInterval);

// OFF
 digitalWrite(_blinkingLedId, LOW);
 delay(_offInterval);
 }

void Blink::setLedActivity(bool ledActivity) {
 _ledActivity = ledActivity;
 }

Main:

Blink *b;

void setup() {
 b = new Blink(2000, 2000, 13);
 }

void loop() {
 b->oneBlink();
 }

Well, okay, OOP doesn’t add anything to the story here, but how about having a blinking object instead of a procedural set of blinking statements :D? Exciting!