Claim: Human beings are not very good at generating truly random sequences.

1. Test this! Before reading any further, try to come up with as random a sequence as you can of Heads and Tails. You must do this solely out of your mind, without using any artificial aids (such as a coin). Use the system here to record and submit your sequence. Do this now, before reading any further to avoid biasing your work. You must submit at least one data set.

Do you feel confident that the sequence you generated is unpredictable?

If the above claim is true then it can be exploited in the design of a computer program that can read your mind!

The game: A computer program asks you to think of either Heads or Tails. Once your choice is made, keep it in mind and click return. At this point, the computer responds with its best guess of your choice. You should honestly tell the computer what your choice had been (Heads/Tails). The game is repeated until 100 guesses have been made. Within a few trials, the computer may be trained to "read your mind." Note, cheating is not allowed, either by you or by the computer!

2. If the computer could not read minds, what would be its success rate? This is the base success rate. A mind-reading program that exceeds the base success rate is considered to have successfully achieved its task. Explain.

3. If the computer could read minds, how might it do it?
(a) Outline a possible algorithm. Explain the idea behind the programme! Do not just write pseudo code.
(b) Formalise the rules used by the algorithm.

Hint: The only information the computer has access to is the record of your past choices of Heads and Tails.

4. Write a mind-reading computer program or script (according to the above rules and specifications) and run it (in real time and against the test data detailed below). How well does the computer do in reading your mind?

Further Information

• A program has been written that will test your program against all submitted sequences from part 1. This program will give you a score for predicting each sequence and an overall mean score. The program is found at /home/cserv1_a/module/ai23/table and can be executed on any cslin machine. To execute: Please note that your program must follow the rules below:
  1. The sequence of guesses must be exactly as defined in "The Game".
  2. The computers guess must appear as the first element on a new line.
  3. The users guess must be entered on a new line.
  4. The program must work for 100 guesses
  If you write in java, use ~ai23/table_java instead of ~ai23/table (follow the same rules!). An example program can be found at ~ai23/cw1_example. Compile it with: 'javac filename'. Run it with: 'java Guesser'. It follows the rules as required. You may also find the C++ code for this executable here and the JAVA code here. You are welcome (and strongly urged) to copy and alter this code rather than starting from scratch. Make sure that you only change the rules of the programme and not the lines that deal with i/o. They are indicated using comments.
  Hint: this programme performs well below baseline, but with a few simple changes it will perform much better. Study the programme and study the pattern that you submitted!
• The sample executable may be tested against the submitted sequences of previous years with the command
  ~ai23/table ~ai23/cw1_example (or to test your code: ~ai23/table your_executable)
• Attempts to trick or "hack" the test program will result in it being removed.
• The test program will allow you to submit your mean score into a "high-score" table. This can be seen here. Submitting your score does not carry any credit. It's just for fun.
• The submitted sequences from part 1 can be viewed here after everyone has submitted.

6. What does this exercise teach us about the way our brains generate sequences, in general, and mock-random sequences, in particular?

7. Last year somebody designed a programme that scored 28%. At a first glance it seems plausible that programmes can score this low. Was the programme likely to be correct? Motivate your answer.

Deliverables:
A. A documented mind-reading source code and executable, or script. The executable should be called "mindread". Any additional files needed for compilation (e.g. make files) must also be included.
B. Test data, runs and success rate.
C. Brief answers to each of the questions (1-7).

All files and answers to questions should be submitted electronically to SIS.

Marking: This assignment is worth 15% of the final grade. Questions are not marked uniformly, but according to the following scale: Q1 : 5 points; Q2 : 5 points; Q3 : 25 points; Q4 : 25 points; Q5 : 10 points; Q6 : 15 points; Q7 : 15 points; Total : 100 points.

Good luck!