Disclosure: Behind the scenes!
(What's different in this game then regular Hangman game? Why is this one more difficult to win??)
This algorithm was introduced to me in the Data structure's class (Fall2018) at UT Austin, taught by Mike Scott.
The simple answer to the question is: The algorithm does not pick a single word until it has to. Instead, it keeps a list of possible words based on user guesses. Here' how it picks the "active word list".
The words (really just Strings) in the active list all have the same pattern as the "word" displayed to the user.
A pattern consist of the letters that have been guessed correctly and the letters that have not been guessed yet. For example, if the current pattern is "-e-e-" then the words "beget", "beret", "bevel", "defer", "deter" and so forth would be in the list of active words. The "-" characters are wildcard characters and represent any character that has not been guessed yet.
Here's how the algorithm narrows the active list of words:
Suppose that the user has asked for a 5-letter word. Instead of picking a specific 5-letter word, it considers all 5-letter words from the original dictionary. Suppose that the dictionary contains just the following 9 words:
- [ally, beta, cool, deal, else, flew, good, hope, ibex]
Now, suppose that the user guesses the letter "e". The program need to indicate which letters in the word it've "picked" are e's. Of course, it dosent hve to "pick" a word, and so there are multiple options about where it reveal the e's. Every word in the set falls into one of five "word families:"
- "- - - -": which is the pattern for [ally, cool, good]
- "- e - -": which is the pattern for [beta, deal]
- "- - e -": which is the pattern for [flew, ibex]
- "e - - e": which is the pattern for [else]
- "- - - e": which is the pattern for [hope]
In the interests of simplicity, it chooses the largest of the remaining word families for Hard difficulty level. In this case, it picks the family "- - - -" with the largest "word family". This reduces the set of words to:
Since it didn't reveal any letters, it counts "e" as a wrong guess.
In case of a tie, it picks the word family that revels the minimum letters in the current word.
If this still results in a tie, it breaks the tie by picking the pattern that is "smallest" based on the lexigraphical ordering of Strings. Here, "---a" is lexigraphically smaller (or before) "a---".
Medium and easy dificulty level chooses the remaining word families as under:
Medium behavior for picking new list of words in makeGuess method:
- Guess 1, PICK HARDEST WORD LIST
- Guess 2, PICK HARDEST WORD LIST
- Guess 3, PICK HARDEST WORD LIST
- Guess 4, PICK SECOND HARDEST WORD LIST IF IT EXISTS, OTHERWISE PICK HARDEST
- Guess 4, PICK HARDEST WORD LIST
- Guess 5, PICK HARDEST WORD LIST
- Guess 6, PICK HARDEST WORD LIST
- Guess 7, PICK HARDEST WORD LIST
- Guess 8, PICK SECOND HARDEST WORD LIST IF IT EXISTS, OTHERWISE PICK HARDEST
- and so forth ...
Easy behavior for picking new list of words in makeGuess method:
- Guess 1, PICK HARDEST WORD LIST
- Guess 2, PICK SECOND HARDEST WORD LIST IF IT EXISTS, OTHERWISE PICK HARDEST
- Guess 3, PICK HARDEST WORD LIST
- Guess 4, PICK SECOND HARDEST WORD LIST IF IT EXISTS, OTHERWISE PICK HARDEST
- Guess 5, PICK HARDEST WORD LIST
- Guess 6, PICK SECOND HARDEST WORD LIST IF IT EXISTS, OTHERWISE PICK HARDEST
- and so forth ...