breakspirit

Reverse HangMan

March 25th, 2012

I was tasked with completing a programming exercise from Rubyquiz.com and I chose to do the reverse hangman game. I opted to expand on the challenge by adding a few features I thought would be cool, such as the computer’s ability to choose the most likely letter in a given dictionary.

I wrote it in Java and it uses a sort of artificial intelligence to play a reverse game of hangman. The player gives it a word and it will use a supplied dictionary.txt file to try to figure out the word in a specified number of attempts.

Download Reverse Hangman

The AI it uses for this is four-fold. First, it will prune the dictionary file down to only the words that are the same length as the given word. Next, it will calculate the most common letters in the entire dictionary and guess those. If that becomes impossible due to the word not being in the dictionary or there being no valid letters to satisfy a dictionary word, the AI will begin randomly guessing letters. It keeps track of every letter it has ever guessed and will not guess these again. Lastly, once the application sees that there are only a few possible dictionary words left, it will attempt to guess the entire word instead of individual letters. This tactic has a high probability of success for words that are actually in the dictionary.

The game is written in such a way that it gets more efficient at guessing with each turn. So, as it guesses correct letters, it has to do less and less computation to figure out its next choice. One can exploit this and create a worst-case scenario by giving it a gibberish word made of the least common letters and of the most common length. So, inputting “zxqjkvbp” as the guessing word will cause it to have a very hard time figuring it out and can take several minutes to do so, depending on how many turns it is given. It is effectively doing all computations on a 28 thousand word dictionary until it eventually loses. Needless to say, this is an unrealistic scenario in regular use. It is possible to account for it, but there is little point in doing so. Given enough turns, the game will figure out the word 100% of the time. The default number of tries is 6.

The game is over when either the application has figured out the word or it has failed and the hang man is hung.

Leave a Reply

*

What content are you here to see?

View Results

Loading ... Loading ...


Quote of the unknown length of time

First, solve the problem. Then, write the code.
— John Johnson

breakspirit owns this site/you.
Copyright © breakspirit. All rights reserved.