Compsci 101 Fall 2012, Clever Hangman HowTo

Playing the clever or cheating version of Hangman is very similar to how the regular game of Hangman is played from a code-writing/client point of view. For this assignment you are not given any code to start, but you are encouraged to use the code you (hopefully) wrote in the original Hangman Assignment or to snarf or browse the code provided as part of that assignment. That could provided a dictionary and a module to get words from the dictionary. For clever (cheating) hangman you'll write code to play a game with words, not famous rock bands or state flowers or anything else. The code we wrote in class as part of the Hangman assignment is available as well -- with the completion of the function change_knowledge that we didn't do in class. This provides a bare-bones, minimal version of a program that plays hangman.

Reminder: some code given

There are a few main ideas to use in creating the clever version of Hangman:

  1. Divide the list of possible secret words into groups/categories and choose one of the categories as the source of the secret word that the computer knows and the human is trying to guess.

  2. Develop the program using small examples at first to be sure that your code is working. For example, don't start with 10,000 words because it may be hard to debug your program with that many. Create a smaller dictionary, for example, and use that instead of the large dictionary that came with the first hangman program.

Choosing a Word

When the user guesses a letter in the clever hangman program, the computer will change the secret word it's thinking of if that will make the game harder for the human player. However, any changes must be consistent with all previous guesses.

The user/player isn't aware that the computer is changing the secret word, because each time the player guesses, the computer may change the secret word in a consistent way that's not apparent to the player except via a frustration factor as the word seems hard and harder to guess.

You can see how the computer does this from the debugging output shown in the assignment writeup and reproduced below.

Note that this output joins a game in which the player has already guessed five letters that don't appear in the word: 'a', 'i', 's', 'e', and 'o'. The debugging output shows that the computer's secret word is jumpy chosen from among 87 words that could have been the secret word. The user has no letters correct and then guesses a 'u'.

The computer now divides its 87 words into categories: the categories are based on the existing word template which is five underscores, and the letter guessed: 'u'. There are three categories: one with 'u' as the third letter, one with 'u' as the second letter, and one with no occurrences of 'u'. 

(secret word: jumpy ) # words possible:  87
Progress:  _ _ _ _ _
letters missed:  a i s e o
guess a letter:  u
_ _ u _ _ 32
_ u _ _ _ 47
_ _ _ _ _ 8

you guessed a letter correctly!
(secret word: bulky ) # words possible:  47
Progress:  _ u _ _ _
Remember that the words the computer chooses from, and each category, must be consistent with all guesses made so far. This means none of the words can contain an 'a', 'i', 's', 'e', or 'o'. In particular, the third category, with no occurrences of 'u', includes words like dryly and crypt but not psych because it has an 's' in it and the player has been told there are no occurrences of 's'.

The numbers shown are the size of each category, so 'u' as the third letter includes 32 words such as bluff and blurb, but not trust because there is no 's'. The category with 'u' as the second letter has 47 words in it including buddy, bunch, and furry, but not rusty because there is no 's'. You write code to create the categories and count the words in each category.

The computer chooses the category with the most words, where 'u' is the second letter. It then continues to play. 


you guessed a letter correctly!
(secret word: bulky ) # words possible:  47
Progress:  _ u _ _ _
letters missed:  a i s e o
guess a letter:  b
_ u _ _ _ 33
b u _ _ _ 14

b  not in secret word
(secret word: lucky ) # words possible:  33
Note that after guessing a 'u' correctly, the computer has chosen 'bulky' as its secret word, but in fact it has chosen the entire category of words with second letter 'u' and no occurrences of 'a', 'i', 's', 'e', or 'o' as the secret word.

The player guesses 'b' and the computer finds all categories chosen from the existing list of 47 words. There are two such categories: those with 'b' as the first letter and those with no occurrences of 'b'. There are no words with 'b' in them other than in the first position because words like numbs and cuban aren't in the list of 47 words being considered.

Again the computer chooses the largest category and continues to play. Notice that the number of possible words continues to decrease. When the player guesses 'c' there are four categories. 


Progress:  _ u _ _ _
letters missed:  a b e i o s
guess a letter:  c
c u _ _ _ 2
_ u c _ _ 2
_ u _ _ _ 21
_ u _ c _ 8

c  not in secret word
(secret word: funny ) # words possible:  21
Progress:  _ u _ _ _
letters missed:  a c b e i o s
guess a letter:
In summary here, the key in writing clever hangman is to divide the list of possible words into disjoint or non-overlapping categories and choose the largest category to continue to play. Each time the category must be consistent with previous guesses, but that's pretty simple to do, because your code will make sure that the list of possible secret words is always consistent with all guesses.

When the game first starts, all words are possible. If the user guesses 't', the categories can be represented in part as below with corresponding sizes. Note that are 14 five-letter words that start and end with 't', but only 7 words that end in double 'tt'. 


_ _ t _ _ 167
t _ t _ _ 6
_ t _ _ _ 89
t _ _ _ t 14
_ _ _ _ _ 3153
_ _ _ t _ 267
_ t _ _ t 6
_ _ _ t t 7
_ _ t _ t 1
...

Creating Categories

The main idea in creating categories is to use a dictionary in which each possible template/strings is a key and the corresponding value is a list (or set) of words that matches that template. For example, words matching 
't _ t _ _'
are

[titan, tithe, title, titus, total, tutor]

and words matching 

'_ _ _ t t'

are

[brett, burtt, hiatt, knott, pratt, scott, wyatt]

To create this dictionary, you iterate over every possible word (initially this is all words, but the list of possible words changes after each guess made by the player). You should compare each possible word to the template and the letter guessed by the user. This combination of word, template, and letter creates a category/key in the dictionary. For example, suppose the player is guessing a four-letter word and the list of possible words is as follows with no letters guessed and the player guessing 'O'. 

  [ "OBOE", "NOON", "ODOR", "ROOM", "SOLO", "TRIO", "GOTO", "OATH", "OXEN", "PICK", "FRAT", "HOOP"]
Categories would be defined as follows by iterating over the words. Since no letters have been guessed, the template is "_ _ _ _" This table below is a diagram, you use lists, strings, or something else for different values. The important part is to be able to create a dictionary key from the template, the word, and the guessed letter. (Hint: strings make great dictionary keys because they are immutable, lists cannot be keys because they are mutable).

Combination Resulting Key
" _ _ _ _ ", "OBOE", "O" "O _ O _"
" _ _ _ _ ", "NOON", "O" "_ O O _"
" _ _ _ _ ", "ODOR", "O" "O _ O _"
" _ _ _ _ ", "ROOM", "O" "_ O O _"
" _ _ _ _ ", "SOLO", "O" "_ O _ O"
" _ _ _ _ ", "TRIO", "O" "_ _ _ O"
" _ _ _ _ ", "GOTO", "O" "_ O _ O"
" _ _ _ _ ", "OATH", "O" "O _ _ _"
" _ _ _ _ ", "OXEN", "O" "O _ _ _"
" _ _ _ _ ", "PICK", "O" "_ _ _ _"
" _ _ _ _ ", "FRAT", "O" "_ _ _ _"
" _ _ _ _ ", "HOOP", "O" "_ O O _"

This would create a dictionary with six values as shown below.

Key Value
"O _ O _" "OBOE", "ODOR"
"_ O O _" "NOON", "ROOM", "HOOP"
" _ O _O" "SOLO" "GOTO"
"_ _ _ O" "TRIO"
"O _ _ _" "OATH", "OXEN"
"_ _ _ _" "PICK", "FRAT"

In a game-playing program, the largest collection of values (most words) corresponds to key "_ O O _" so the computer would pick a secret word at random from the list of three words: ["NOON", "ROOM", "HOOP"] and the template for the game would be "_ O O _" with three possibilities. The player may think she has hit the jackpot with two O's in the word, and that may be true, but there are more words to eliminate than with any other template.