Computer Plays Hangman!

Scenario

A few months back, I encountered a very interesting coding problem. I was supposed to design a ‘Hangman Player’. Yes, I had to build a system which could play the game Hangman with the server. And the game was not played using words, but rather phrases. After a lot of brainstorming, I was able to build a decent system that could win 70-80% of the time. It was a challenge which I had to solve in a limited time frame, so I did the best I could. If you need some reminding on what the game is, here’s a quick reference.

I wrote a Python client which played with the server provided by the challenge. I no longer have access to the server, so I also decided to write a server of my own as well.

What did I use?

• Python
• Java
• SpringBoot
• MySQL
• DataMuse Web Api

Github

Hangman Client
Hangman Server

The Hangman Player (Client) Algorithm

The client I wrote behaved similar to how a human mind would approach a Hangman game; see the current set of inputs, and try to find a letter which might have the best chance of filling a good chunk of those blanks (honestly, I never thought that much). Let me explain the algorithm through an example:

Suppose our Hangman string is HIS TRUTH.

The input we get is ___ _____

Since I don’t have a point to start, I do a warmup and hit the server with the most commonly occurring letters, i.e. ‘T’ and ‘E’ (check letter frequency). This gives me a good starting point.

My string is now ___ T__T_. Notice that I have also made a wrong guess. So I only have 2 more wrong guesses left.

Then, I split the string into words. For each word, I fetch the most relevant words using the Datamuse API. Datamuse API is a really powerful free API which gives the most relevant words based on a set of constraints. In my case, I provide the words filled with the letters I know. So, for each word, I fetch the most relevant words from the Datamuse API, and choose the top 10 words (sorted by the f-score returned by the API).

For instance, for the partial word T__T_ (which corresponds to TRUTH), the API returns (showing only 4 records here):

{
    word: "truth",
    score: 2314,
    tags: [
    "f:168.310927"
    ]
},
{
    word: "trite",
    score: 2200,
    tags: [
    "f:1.200587"
    ]
},
{
    word: "taste",
    score: 1727,
    tags: [
    "f:49.705728"
    ]
},
{
    word: "teeth",
    score: 1659,
    tags: [
    "f:55.472105"
    ]
},

Then, I calculate the rank of each distinct character for each word search. For example, for letter H, it’s score is recorded as:
score = 168.310927 + 55.472105
Word Complexity = (no of letters known in the word)/(total word length)
In this case, the word complexity for T__T_ becomes 2/5.
Score for H for this word is = Word Complexity x score.

I do the same for each word of Hangman string. Final score of H is the average of the score of H for each word in Hangman string.

So, after doing a cumulative rank of all characters, I choose the character with the highest score as the next guess.

This process is repeated till the status of the game is either DEAD or FREE.

Caveats

This algorithm works majority of the time. However, there are situations where it does not work. One of the situations being where all but one words have been guessed. In that case, it starts guessing from A, B… But that can be optimized as well.

Hangman Server

I decided to write a REST server of my own using SpringBoot and MySQL to test my client. The server supported the following APIs:

Request:
GET /play

Response:
status = 'ALIVE'
token  = <some token>
remaining_guesses = 3
state = ____ ___ _______

When a new game starts, the user requests a new token from the server. The service generates a token, randomly selects a phrase from the database, and maps the token with that phrase, sending back the response with status ALIVE.

Request:
GET /play?token=<>&guess=<>

Response:
status = 'ALIVE' or 'DEAD' or 'FREE'
token = <same token>
remaining_guesses = 3 or 2 or 1 or 0
state = __A__ _A A_____

User sends in a guess for the phrase, with the token. The system checks if its a valid guess, or not, and returns the appropriate response, while also updating the database with the updated state.

Conclusion

This was a fun coding challenge and quite different to the projects I had been working on. It soon turned out into a mini project. It helped me learn along the way about how I could program a computer to do tasks which might not seem that intuitive, but on closer inspection, they do have a logical flow. There is still room for optimization and experimentation, but I’m happy with the results right now. Will probably visit it again sometime in the future.