Evil Hangman

If you aren’t familiar with the game Hangman, here is how it works:

  1. 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. TREE becomes ----)
  2. 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 E on TREE would make it become --EE). Otherwise, the player will loose a guess.
  3. 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 ALLY, COOL, and GOOD
  • -E--, which contains BETA and DEAL
  • --E-, which contains FLEW and IBEX
  • E--E, which contains ELSE
  • ---E, which contains HOPE

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.

Implementation

First, download my compiled version of this project and the dictionary file you will be using here. You can uncompress this file by typing 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 README.txt).

Next, work on writing your own version of this. Good luck!

Hints

  • Letter frequency is not the word family. Although the words ELSE and HERE both have two Es, they are parts of separate families: E--E and -E-E, respectively.
  • 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.

Credit

The Evil Hangman assignment originally comes from Keith Schwarz as a part of Stanford University’s Nifty Assignments.