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)
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 IllegalArgumentException if wordLength is less than one or if maxGuesses is less than one. You should throw an IllegalStateException if
there are no words found of wordLength.
You should also (uniformly) randomly select a word from the provided dictionary data/scrabble.txt that is wordLength
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 final.
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 SortedSet is TreeSet.
This means you will have to iterate over the SortedSet a random number of times to find the right word.
More about SortedSet and TreeSet:
In Java, 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 IllegalArgumentException.
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.
Task 1.
Implement the methods in RandomHangmanChooser as described above.
Notice it says “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 SortedSet is TreeSet. This means you will have to iterate over the SortedSet a random number of times to find the right word.” In addition, the guide urges you to use a static field that is a java.util.Random within your RandomHangmanChooser class.
Thus, to choose the random word, one approach would be to use your Random object that you have as a field to generate a random integer between 0 and the length of your SortedSet that stores the possible words. Then, use a for-each loop to iterate through the SortedSet that number of times (counting the number of times you have iterated using a counter variable). Once you have iterated that number of times, you have reached your word, so store it as your chosen word and break. This way, you have randomly selected a word.
Alternately, if you wish to avoid iterating over your SortedSet, you can instead create an ArrayList out of your SortedSet (syntax new ArrayList<>(wordsOfLength), where wordsOfLength is the name of your SortedSet), then generate a Random index in the manner specified above, then index directly into this ArrayList to find your random word. Both methods are viable solutions to generating a random word.
isUpperCase(c) is a function that returns True if c is upper case and False if c is lower case. However, the function will also return False if c = special character, or ‘-‘. Thus, the use of isUpperCase(c) will fail our tests and is not an effective way of checking whether or not the guessed character is upper case. The same is true for isLowerCase(c), so we would recommend not using these methods in general.
When you declare a variable as final, this means that once the value is assigned, it cannot be modified. If you attempt to modify this value, the system will let you know with an error message. This means that you cannot initialize a final chosen word variable inside of a for loop.
During the first iteration of the for loop, the variable chosen word will be assigned and declared final. During the second iteration of the for loop, you will attempt to modify the value of the previously declared variable, resulting in a ‘final variable is assigned in a loop’ error.
This often means that your game is not ending properly, so the tests are running out of guesses to try and have no more elements (yielding a NoSuchElementException). Check that in your isGameOver function, you are returning true if the number of guesses is 0, as well as if the pattern is fully revealed. In addition, check that you only throw exceptions when you should be, as otherwise it will cycle through the guesses and not take any of them, leading to a similar issue.
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:
| Pattern | Family |
|---|---|
---- |
[ally, cool, good] |
-e-- |
[beta, deal] |
--e- |
[flew, ibex] |
---e |
[hope] |
e--e |
[else] |
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:
| Pattern | Family |
|---|---|
-oo- |
[cool, good] |
---- |
[ally] |
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
Mapas a field. - You may not have more than four non-static fields.
Task 2.
Implement the methods in EvilHangmanChooser as described above.
Be careful to check all prerequisite conditions before starting to build your pattern. For instance, if I ask for a word of size 1000000, this will not be found in the dictionary and so an exception should be thrown immediately. If you don’t check this first and start trying to construct a pattern of dashes of length 1000000, this will likely manifest as an “infinite loop”. So, you should make sure to eliminate such cases before your code tries to handle them.
One possible cause of this could be if you are storing your pattern as a field, and updating it before you have added the newly guessed letter to your guessed-letters set. This would result in your stored pattern only having been generated from previous guesses, therefore missing out on the current guess. Try switching the order between updating your pattern and updating your guessed letters, such that your guessed letters get updated first.
This could be a sign that your isGameOver function is immediately returning true, thus the game would immediately exit and thus output nothing. We recommend setting a breakpoint within that function, then running the debugger, to see what isGameOver is returning. It’s also worth checking what you set your initial values to - you could inadvertently be setting values in your constructor that trigger an immediate game over.
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.
Task 3.
Implement the method in AIHangmanGuesser as described above.
If you want to access scrabble.txt, the path name you need to specify is “data/scrabble.txt”, as the scrabble file is located in a data folder. Simply writing “scrabble.txt” will result in a FileNotFoundException.
The failure of this test is a sign that your pattern matching may not be working as desired in getGuess. When you are finding words that fit the pattern, make sure that you are not allowing words where the word contains a letter that has been guessed and is incorrect at that position. In other words, if your pattern has a ‘-‘ and your prospective word contains a letter at that position that has already been guessed, that word does not match (which is why ‘adam’ does not match the pattern ‘ad-m’ because there is a dash where ‘a’ has been guessed).
If you read the red error message for this test, it will say “AIHangmanGuesser should have a field with the type ‘java.lang.String’, but does not.”. This means this error is being thrown because your AIHangmanGuesser needs to have a String field, more specifically a field for the file name for the dictionary. The String field should be static (meaning it is the same for all instances of the class) and final (meaning it won’t be reassigned/changed).
One thing to check is that for the pathname for the scrabble.txt file, you are using “data/scrabble.txt”, not a full path name unique to your computer (i.e. do not use something like “C:\Users\user\CS2 projects\project02\data\scrabble.txt”). If you use the full path, it will fail the gitlab tests because those run on a different machine.
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.