CS 261 Lab K - Mind Reading

Due Wed Dec 03 at 3:00pm

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. Partner assignments for this lab can be found on Moodle

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 .equals() and AND the .hashCode() methods; the first returns whether or not the contents of the queues are equal, and the second will return an (int) hashcode for the queue based on its contents. That is, the hashCodes() for different queues with the same contents should be the same (since the .equals() method says they are equal).
  - Your new hashCode() should be based on the contents. You might either convert the contents to a String and then get the hashCode() of that, or get the hashCode() of the individual contents and combine them in some way (e.g., add them together in the same way Strings combine the hashcodes for chars).
- 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.
- 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
  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!

Also be sure and test your game thoroughly: giving guesses of HTHTHTHT... or HHTTHHTT... should allow the computer to easily guess your future decision!

Extensions

There are a number of ways to improve your program's pyschic abilities, which may be worth up to 2 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 vhedwig. 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 out of 18 points:

[2pt] You have implemented the SizedQueue class, which represents a fixed-length queue
[1pt] Your SizedQueue class is generic
[1pt] Your SizedQueue class includes all the required methods
[1pt] You have overridden the SizedQueue.equals() method to make queues with the same contents equal
[2pt] You have overridden the SizedQueue.hashCode() method to make queues with the same contents have the same hashCode
[1pt] You have implemented the MindReader class
[1pt] Your MindReader class keeps track of the player's guess history
[3pt] You have implemented the MindReader's makeGuess() method
[2pt] You have implemented the MindReader's update() method
[1pt] Your MindReader is able to read the player's mind!
[1pt] You have implemented a working MindReaderUI class that allows the user to play the game
[1pt] Your MindReaderUI class lets the user play until they or the computer wins
[1pt] Your program demonstrates good object-oriented style and division of functionality
[1pt] You have completed your lab partner evaluation