Evil Hangman

I got to know about Evil Hangman a while ago when I was reading my professor’s blog (Don’t judge me. I’m sure you googled your professors too. The Onion wrote about this.). I never got around to write this game until today when I woke up and decided that I should do something evil. Evil Hangman is like normal Hangman–players try to guess a secret word by entering different letters–except that in Evil Hangman, players are (almost) guaranteed to lose. I said “almost” because Evil Hangman is a program with a deterministic algorithm. If a player knows how it works, s/he can guess the letters in a way to maximize his/her chance of winning.

The heart of the program’s evilness lies in its aversion to commit to a fixed secret word. In normal Hangman, the program would pick a word and stick to that. In Evil Hangman, the player chooses the length of word s/he wants to play. Evil Hangman maintains a pool of candidate words that satisfy the length. Each time the player guesses a letter, Evil Hangman calculates to either accept the player’s guess or not to maximize the leftover candidates. After every guess, the candidate pool shrinks. If the player has enough guesses and places your guesses right, s/he can force the program to eventually commit to word. You can read about the program and a suggested approach here.

I followed the suggestion to divide words into different families based on each of the player’s guesses. Suppose the player chooses the word length of 3, and English language has only 6 words of this length: BAR, RAD, AND, END, DOT, AAA. The player’s first guess is A. I use 3 bit to represent each word. In the beginning, all bits are 0. If a letter in the word is the same as the player’s guess, the bit at that letter’s position is converted to 1. Then I convert these bits into 10-based integers. The value of this integer suggests which family the corresponding word belongs to.

BAR – 010 (binary) – 2 (decimal)

RAD – 010 – 2

AND – 100 – 4

END – 000 – 0

DOT – 000 – 0

AAA – 111 – 7

We see that family 2 (words whose integers are 2) and 0 are the largest, both have 2 elements each. In this case, the program chooses family 0 because then the player would have to guess more letters. For families of the same size, families with less guessed letter’s occurrence weighs more. For example, family of 000 (binary) weighs more than family of 010 and family of 010 weighs more than family of 110 and so on.

At first I planned to write this game in Python. I have heard that programmers of other languages, in their first contact with Python, experience a sentiment similar to that of “flying”.

But after a couple of hours playing with Python, I realized that I have no idea what to do with so much freedom the language gives me. So I switched back to C. I use an array of vectors to store all families, each vector represents a family. After the player’s guess and the program makes a decision to choose a family, it get rid all other words. It was a pain, given that this program requires a lot of memory handling. My friend walked in on me doing this project and he was like: “Why are you doing this to yourself?”

When I finished the program, it surprised me that winning this program was a lot easier than I thought. Either my algorithm is flawed or evil hangman is just a novice devil. Some thoughts:

– Because the program follows a fixed algorithm to decide the appearance of guessed letters, if users keep on choosing one word length and enter a fixed sequence of guessed letters, the program will end up with the same result word every time. It makes it impossible to pass the evil hangman as a normal hangman. There are a few ways I can think of to fix this problem:

  • Randomize the process to choose the leftover word family. Instead of always picking the largest word family, for 1/5th of the time, the program chooses any random family from the list of available word families. To do this, I use a random generator to generate a boolean variable with 20% probability of being true.
  • Randomize the process of applying weight to each family. Suppose the player guesses the letter “E”. For now, I set the weight such that the family that contains no E weights 1.5 times as much as families that contain 1 “E”, and families that contains 1 E weight 2 times as much as families that contain more than 1 E. Similar to above, for 1/5th of the times, the program weighs all families equally.
  • Keep track of user’s choice of word length. If user chooses the same word length more than once, the program alternates between choosing the largest word family and a random word family.

– When the word is long (like more than 15 characters), after around 5-6 well-placed guesses, players can pretty much narrow the candidate pool to a single word. Also, because players can choose the number of guesses,

– I made two of my friends play the game. It was a pleasure watching them play.

  • The first one became addicted to the game. His strategy was to guess all the vowels (aeiouy). It works. All words must contain at least one vowel. Also, by entering the most popular letters first, he forced the program to narrow down the candidate pool. He won around 20% of the time.
  • The second one chose to have 26 guesses. By entering the entire alphabet, he’s bound to win 100% of the time. To Evil Hangman’s credit, he often needs to use until the last letter of the alphabet to get the word.

– If you happen to be working on this program, I’m more than happy to talk to you about it.

Advertisements
Evil Hangman

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s