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
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
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
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 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
public RandomHangmanChooser(int wordLength, int maxGuesses)
The constructor is passed the target word length and the maximum number of wrong guesses the player is allowed to make.
You should throw an
wordLength is less than one or if
maxGuesses is less than one. You should throw an
there are no words found of
You should also (uniformly) randomly select a word from the provided dictionary
data/scrabble.txt that is
characters long to be the secret word. You will likely want to store the chosen word as a field; if you do, it must be
When selecting a random word from a set of possible words of
wordLength, you must use a
SortedSet to store the words. One implementation of a
This means you will have to iterate over the
SortedSet a random number of times to find the right word.
SortedSet is an interface that not only stores unique elements, but also sorts them by their natural ordering. This ordering can also be specified by a Comparator to define how to compare individual elements. When the iterator is evoked, the set is traversed automatically by this order.
TreeSet implements the SortedSet interface by using a tree data structure to store the elements. What’s a tree? Hang tight for a few more lectures!
So, the best way to write this into our code is:
SortedSet<Type> set = new TreeSet<>();
public int makeGuess(char letter)
This method should return the number of occurrences of the guessed letter in the secret word, and update the number of guesses remaining.
This method should throw an
IllegalStateException if the number of guesses left is not at least one.
Additionally, it should throw an
IllegalArgumentException if the character being guessed was guessed previously.
All guesses passed to
makeGuess should be lowercase letters. If not, your method should throw an
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
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.
Implement the methods in
RandomHangmanChooser as described above.
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 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
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:
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
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
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
Here is the example scenario in pictorial form:
The tests will also check the following additional requirements:
- You may not store any kind of
Mapas a field.
- You may not have more than four non-static fields.
Implement the methods in
EvilHangmanChooser as described above.
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 class should implement the
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
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
a letters have already been revealed.
Implement the method in
AIHangmanGuesser as described above.
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!
This project is adapted from an assignment by Keith Schwarz.