In this project, we will focus on the client view of data structures. The idea is to become familiar with how to use the fundamental different types of data structures (lists, maps, sets, etc.) before we implement them ourselves later. Remember, if you get stuck for more than 30 minutes on a bug, you should come to office hours.

The Game of Hangman

A game of hangman is played by two players: the chooser and the guesser. First, the “chooser” picks a secret word, and then the “guesser” repeatedly guesses single letters that might be in the word until they either run out of guesses (i.e., the chooser wins) or guess every letter in the word (i.e., the guesser wins). You can read more details on the Wikipedia page: https://en.wikipedia.org/wiki/Hangman_(game). We will be using the dictionary of words called “data/scrabble.txt”.

Goals and Outcomes

In this project, you will write two different implementations of “choosers” and one implementation of a “guesser”.

By the end of this project, you will…

• be able to play games of hangman using your AIs
• have experience working with built-in Java data structures (in particular, sets and maps)
• continue to work with interfaces to swap out multiple implementations

Overview and Implementation Strategy

In this project, we represent choosers and guessers using the interfaces IHangmanGuesser and IHangmanChooser.

Because a game of hangman is parameterized on (1) the type of guesser, and (2) the type of chooser, we have provided a console-based main “runner” program called HangmanGame which instantiates any guesser and chooser of your choice and plays them against each other.

We have provided you with a simple console-based implementation of IHangmanGuesser which allows a user (you!) to play against an implementation of IHangmanChooser.

First, you will implement a chooser that randomly chooses a word from a dictionary. Then, you will implement a chooser that secretly delays choosing a word until it is forced to by the guesser’s guesses (evil hangman). Finally, you will implement a guesser which will attempt to use frequency distributions of letters to decide which letters to choose.

RandomHangmanChooser Requirements

Your RandomHangmanChooser class should randomly choose a word to be the secret. In addition to a constructor, you will have to write methods that support playing an actual game of hangman with your chooser. To facilitate testing, you must use a single instance of java.util.Random, and it must be a static field in your class which is initialized outside the constructor!

You may not use more than three non-static fields in RandomHangmanChooser.

public RandomHangmanChooser(int wordLength, int maxGuesses)

public int makeGuess(char letter)

public boolean isGameOver()

This method should return true when the player has correctly guessed the word or when the player has run out of guesses, and false otherwise.

public String getPattern()

This method should return the current pattern to be displayed for the game using guesses that have been made. Letters that have not yet been guessed should be displayed as a dash. There should be no leading or trailing spaces.

public SortedSet<Character> getGuesses()

This method should return the current set of letters that have been guessed by the player.

public int getGuessesRemaining()

This method should return the number of wrong guesses the player can make before the game ends.

public String getWord()

This method should return the secret word being considered by the RandomHangmanChooser. Since it reveals the word when called, this method should not allow the user to make any more guesses in the future.

Interlude: Playing A Game

In addition to running our tests, you should actually play hangman with your implementation. Use the HangmanGame run configuration to actually play a couple games.

EvilHangmanChooser Requirements

Your EvilHangmanChooser class should delay picking a word until it is forced to. As a result, the computer is always considering a set of words that could be the answer. In order to fool the user into thinking it is playing fairly, the computer only considers words with the same letter pattern.

For example, suppose that the computer knows the words in example.txt:

ally beta cool deal else flew good hope ibex

In our game, instead of beginning by choosing a word, the computer narrows down its set of possible answers as the user makes guesses. When the user guesses e, the computer must reveal where the letter e appears. Since it hasn’t chosen a word yet, its options fall into five families:

The guess forces the computer to choose a family of words, but not a particular word in that family.

The computer could use several different strategies for picking the family to display. Your program should always choose the family with the largest number of words. This strategy is reasonable because it leaves the computer’s options open.

For the example described above, the computer would pick ----. This reduces the possible answers it can consider to:

ally cool good

Since the computer didn’t reveal any letters, it counts this as a wrong guess and decreases the number of guesses left to 6. Next, the user guesses the letter o. The computer has two word families to consider:

It picks the biggest family and reveals the letter o in two places. This was a correct guess so the user still has 6 guesses left. The computer now has only two possible answers to choose from:

cool good

If the user guesses a letter that doesn’t appear anywhere in your set of words, say t, the family you previously chose is still going to match. In this case, you’d count t as a wrong answer.

When the user picks d, the computer removes “good” from its consideration (because the family with “cool” is alphabetically before the family with “good”) and is now locked into using “cool” as the answer.

You should implement the same constructor and methods as in RandomHangmanChooser with the added restrictions that they use the “evil” algorithm. Many of them will be identical, but the constructor and makeGuess will likely be significantly different.

In particular, your makeGuess method should should find all the possible word families split on the guessed letter and pick the one with the most words. Use a Map to associate family patterns with the set of words that have each pattern. If there is a tie (two of the word families are of equal size), you should pick the one whose pattern is alphabetically earlier. The easiest way to do this is use a TreeMap instead of a HashMap. Note that the - character comes alphabetically before all lower-case letters! The set of words representing the biggest family then becomes the dictionary for the next round.

Keep in mind that the patterns come from the words themselves. On any given turn, there is a current set of words that all have the same pattern. When the user guesses a new letter, go through each of the words that you have in the current set and figure out what the correct new pattern would be for that particular word given the new guess. You are likely to get different patterns for different words.

Your task is to process each of the words in the current set, putting each into a set that corresponds to the new pattern for that particular word. Different words go in different sets because they have different patterns. Once you have processed all of the words, you go through the different sets and find the one with the most words. That becomes the new set used by the EvilHangmanChooser.

Here is the example scenario in pictorial form:

The tests will also check the following additional requirements:

• You may not store any kind of Map as a field.
• You may not have more than four non-static fields.

Interlude: Playing A Game II

Once again, it will be beneficial to actually play a game with your implementation. It should be noticably more difficult to win against your evil implementation than the random one.

AIHangmanGuesser Requirements

Your AIHangmanGuesser class should implement the IHangmanGuesser interface.

The guesser interface is… quite simple. It has a single method getGuess which takes in the current known pattern and the set of previous guesses, and returns the next guess to make. You should have a static variable for the name of the dictionary file like in the Alice in Wonderland example from class.

We will make the assumption that both the guesser and the chooser are using a known dictionary. (In our case, it’s scrabble.txt.)

At a high-level, you should implement the following algorithm:

• Find all words in the dictionary that match the pattern
• Loop through all unguessed letters to find the number of occurrences of each letter in the remaining words.
• Return the letter with the highest frequency (in a tie, use the alphabetically first letter).

You may implement this algorithm in whatever way you see fit. We do, however, recommend using lists and maps.

Before you implement your algorithm, consider the pattern ad-m. Note that this pattern does not match adam, because all the a letters have already been revealed.

Interlude: Playing A Game III

Again! Again! Face your AI against your random chooser and your evil chooser. How does it fare? You might consider writing a second guesser that does something more intelligent in an attempt to regularly beat the evil chooser! If you do, let us know! We’d love to see what you come up with!

Acknowledgements

This project is adapted from an assignment by Keith Schwarz.