Marvin, the Paranoid Android
Marvin, the paranoid android, has ‘brain the size of a planet’.
He is seldom allowed to use his brain.
As a result, he is bored and depressed.
His depression is now so bad that he has regressed into a child-like state.
Marvin’s builder, Sirius Cybernetics Corporation, has anticipated this and provided a reset mechanism.
In his depressed state, Marvin’s brain is stuck in an infinite loop - he keeps imagining the lab where he was built.
Marvin continuously utters an (x,y) coordinate in the lab.
To reset Marvin, you need to correctly answer whether there is an obstacle for each coordinate uttered by Marvin.
Unfortunately, Marvin’s manual is missing and no one knows the actual map.
However, SCC has provided a set of potential maps, each with a probability of being correct.
All you need now is to read Marvin’s mind to figure out which map is correct!
Fortunately, Marvin is a forgiving robot and will reset if you don’t make too many mistakes.
Your aim is to construct a prediction algorithm that learns from previous answers so that it minimizes the number of mistakes over the entire sequence.
The following two sequences have different correct maps. Experiment with them to design your learning algorithm.
