If you aren’t familiar with the game Hangman, here is how it works:
- One player decides on a word for the other player to guess. That player
writes down the number of characters in the word as dashes. (eg.
- The other player guesses letters that may be in the word. If the letter
appears anywhere in the word, the player which decided the word reveals the
locations of the letters which match. (eg. guessing
TREEwould make it become
--EE). Otherwise, the player will loose a guess.
- If the player runs out of guesses, they lose and the player which decided the word reveals it.
Your job will be to implement a computer version of Hangman, where the human guesses against the computer. While there are many viable strategies for building competitive computer game players, there is one approach that has been fairly neglected in modern research — cheating. Why spend all the effort trying to teach a computer the nuances of strategy when you can simply write a program to play dirty and win handily all the time?
Cheating at Hangman
If we choose our word at the end of the game, rather than the beginning, we can defeat the player under most cases, we just have to make it look like we are following the rules. To do this, we must reveal letters only when it gives us a larger set of words than if we didn’t reveal any. Here is an example:
Say we make the player guess a four letter word, and our dictionary contains the following words:
ALLY BETA COOL DEAL ELSE FLEW GOOD HOPE IBEX
The user then guesses the letter
E and we try to make the largest set of
words possible. To do this, we break down our words into word families:
----, which contains
-E--, which contains
--E-, which contains
E--E, which contains
---E, which contains
We then don’t reveal any letters (as
---- was the largest set of words), and
reduce the set of words we can use to:
ALLY COOL GOOD
After that, we just repeat the same process till either the user runs out of guesses or guesses all the letters in the only remaining word.
Stop! Make sure you fully understand how we will be cheating at Hangman before proceeding. This is critical to the understanding of this project.
First, download my compiled version of this project and the dictionary file you
will be using here. You can uncompress this file
tar zxvf hangman_jack.tar.gz. Play my version of Hangman a few
times to get a feel for it. There is even a command line flag that allows you
to see its working word set each turn (see
Next, work on writing your own version of this. Good luck!
- Letter frequency is not the word family. Although the words
HEREboth have two
Es, they are parts of separate families:
- Check and make sure there are enough words. In order to play Hangman with a word length of N, there must be at least one word with length N. Keep in mind there are some gaps in the dictionary for word length, the longest word has a length of 29, but there are no words with length 28 or 27.
The Evil Hangman assignment originally comes from Keith Schwarz as a part of Stanford University’s Nifty Assignments.