CS 261 Lab K - Mind Reading

Due Wed Apr 23 at 9:00am

Overview

In this lab, you will program the computer to read the user's mind (why didn't software developers do this a long time ago?) Your program will guess in advance whether the user will choose heads or tails, then get the actual response from the user. If your program guesses correctly, it gets a point; otherwise the user gets a point. The first one to 15 points wins. When run, your program might look something like this:

I am the Mind Reader!
****************************
I've made my prediction about what you will enter. Input 'h' or 't' below. 
Enter 'h' or 't': h
Fooey. My prediction was wrong.
Score is now human 1, computer 0
****************************
I've made my prediction about what you will enter. Input 'h' or 't' below. 
Enter 'h' or 't': t
I was right!
Score is now human 1, computer 1
****************************
I've made my prediction about what you will enter. Input 'h' or 't' below. 
Enter 'h' or 't': t
I was right!
Score is now human 1, computer 2

Underneath the hood, your program will be using a HashMap to track the user's responses, using that history to predict their guesses. The "mind reading" will be implemented by remembering the last four responses and the last response that followed such a "response history". Humans are not very good at producing genuinely random output, and this simple method is surprisingly effective at predicting their actions.

This lab will be completed in pairs. Remember to review the pair programming guidelines before you get started!

Objectives

To practice working with HashMaps
To review and implement a fixed-length queue
To practice implementing full programs

Necessary Files

No classes are provided; you'll need to write this up from scratch! But there is guidance below.

Assignment Details

You will need to make three (3) different classes for this program:

SizedQueue<E> This class should represent a fixed-sized Queue. That is, it's a queue with a size limit--when the queue is full, you dequeue the first item in order to make room for the new item.
- Make this class generic, so you'll be able to reuse it later if you want!
- Your class should support the following public interface:
```
SizedQueue(int size) //creates a new SizedQueue with the given maximum size
E push(E element) //enqueues an element, and return any items that were pushed off
E pop() //dequeues the element at the front of the queue
E peek() //returns the element at the front of the queue without removing it
int size() //returns the number of items in the queue
boolean isEmpty() //returns whether or not the queue is empty
boolean isFull() //returns whether or not the queue is full
```
- You should also override the toString() method to have it print out a nice list of the contents. This will be really useful for getting the contents to use as a key for your response history!
  - Alternatively, you could override the .equals() method AND the .hashCode() method, but that's a lot more work.
- You are welcome to use whatever underlying data structure you wish (Hint: the java.util.LinkedList class is a good one to consider).
  - It should be easy to create new, useful ADTs at this point!
MindReader The MindReader class will, unsurprisingly, contain the core mind reading logic.
- To make this class psychic, it'll need to keep a SizedQueue variable to track the user's recent response history, and a HashMap that tracks all the user's response histories and the user response that followed that history. Note that you are welcome to use the java.util.HashMap class.
  - Hint: You want to map the contents of the response histories to responses, not an entire response history object! When the player guesss HHTT, you want to be able to check if they have previously guessed that sequence; wherever it may be in the overall response history.
  - Remember to do any initialization in your constructor!
- The class needs to support two different (but simple!) methods:
  1. makeGuess() should return the program's guess for the user's next response: either heads or tails. It does this by looking if the current contents in the recent history have been previously guessed (stored in the past histories map). If so, then it returns the guess the user made following that history. If not, it should randomly pick to return heads or tails.
    - You are welcome to choose how to represent heads and tails. You might use Strings (e.g., "H", "T") or chars (e.g., 'h', 't'). Or you might consider using something like a CoinSide enumerated type, and/or constants in a Coin class for readability!
  2. update(response) should let the MindReader know how a user actually responded when it guessed. This method should store the recent response history and the actual response in the HashMap. It then adds this most recent response to the recent response history--which, being a SizedQueue, might shove out an older response (but that's okay!)
- Be sure and test this class thoroughly! Try printing out (or inspecting via the debugger) the contents of the SizedQueue and the HashMap to make sure they're what you expect!
MindReaderUI This class acts as the launcher (main) class and controls the game's interaction, which will appear on the console. Use a while loop to ask for guesses until someone wins. Inside the loop: call the makeGuess() method of the MindReader class to have the computer pick a guess, then ask the user to input a guess; then compare the guesses and print the appropriate response; and finally let the MindReader know what the outcome was with its update() method so it can be ready for the next round.
- You might consider refactoring the interaction into a separate method (perhaps playGame()) for readability, as well as to make it easy to have different UIs for the same program!
- It might also be fun to make the "winning" number of points a really high number, to enable more testing and playing :)

And that's about it! Be careful to try and keep functionality appropriately separated between classes and methods: use good coupling and cohesion!

Extensions

There are a number of ways to improve your program's pyschic abilities, which may be worth up to 10 points extra credit:

Right now, you just record the user's last response and use that in the hashmap. You might make this a bit more sophisticated: record a pair of values that represent the number of times the user followed that history with 'h', and the number of times the user followed that history with 't'. So your hashmap might have entries like: "hthh": (3, 5) which says that "hthh" was followed by 'h' three times, and 't' five times. So you would return 'h' as the computer's guess with probability 3/8, and 't' with probability 5/8. You can use a Point, a two-element array, another private class with two instance variables, or even another (!) HashMap to store this pair of responses. The idea here is to track the distribution of responses that followed a given history, instead of just the last response, and to make guesses according to that distribution.
- Other refinements may be possible. How accurate can you make your Mind Reader?
This basic process can apply to all kinds of different games. Can you modify your Mind Reader so it also wins at Rock-Paper-Scissors? You'll need a different UI class; and you should make your UI class do the "judging" of who won or not (to keep things fair). This would also let you easily swap out different psychic/AI systems easily--or even have them play themselves!

Submitting

Make sure your name is in a class comment at the top of all your classes and upload them to the LabK submission folder on hedwig. Make sure you upload your work to the correct folder! The lab is due at the start of class on the day after the lab.

After you have submitted your solution, log onto Moodle and submit the Lab K Partner Evaluation. Both partners need to submit evaluations.

Grading

This assignment will be graded based on approximately the following criteria:

Implemented a generic SizedQueue class, with the appropriate public interface [40%]
Implemented the MindReader class [5%]
Implemented the MindReader's makeGuess() method [20%]
Implemented the MindReader's update() method [15%]
A working MindReaderUI class that allows the user to play the game [10%]
Code demonstrates good object-oriented style and division of functionality [5%]
You completed your lab partner evaluation [5%]