What is the most optimal machine learning model/algorithm to create a hangman solver?

Question

Want to create a hangman solver, So what is the best ml algorithm (lstm,reinforcement learning, or etc) to use? Do suggest any other optimal technique if you know?

Answer 1

As is often the case, training a machine learning from scratch would be very inefficient here, and you could achieve excellent results with much simpler methods.

The hangman problem breaks down to a few steps:

• Start with a list of all eligible words (you can find the Scrabble dictionary online, which is a good start) and filter to keep only words of length $n$. This list isn't too long.

• Decide on your next letter.

  • A simple way to to this is find the most common eligible word (there are lots of data sets that provide this) and pick any letter from this.
  • A better way would be to figure out the most likely letter directly. I provide an algorithm for this below.

• Provide your guess, and update your list of eligable words accordingly.

---

Code Example

# Hangman
import numpy as np
import pandas as pd
import string

# Data from https://www.kaggle.com/datasets/rtatman/english-word-frequency?select=unigram_freq.csv
all_words = pd.read_csv('unigram_freq.csv').set_index('word')
all_words.index = all_words.index.map(str) # Ensure everything is a string
all_words['length'] = all_words.index.map(len)

target_n = 5
words = all_words[all_words['length'] == target_n].sort_values('count', ascending = False)

# Most likely letter, marginalising across words
letters = list(string.ascii_lowercase)
possibilities = np.zeros((target_n, len(letters)))

for i in range(target_n):
    for j, letter in enumerate(letters):
        # Get all eligable words with letter `letter` in position `i`
        letter_pos_words = words[words.index.map(lambda w: w[i] == letter)]
        possibilities[i, j] = letter_pos_words['count'].sum()

guess_position, guess_letter_index = (v[0] for v in np.where(possibilities == possibilities.max()))
guess_letter = letters[guess_letter_index]
print('Guess: "%s" in position %i' % (guess_letter, guess_position)) # NB - Position 0 is the first letter
## Guess: "s" in position 4

You can also visualise how these letter probabilities look:

import seaborn as sb
import matplotlib.pyplot as plt
viz_df = pd.DataFrame(possibilities, columns = letters)
fig, ax = plt.subplots(figsize = (9,8))
sb.heatmap(viz_df.T, cmap = 'jet', ax=ax)
plt.show()

Answer 2

If you limit the model to propose letters and not entire words (which theoretically does not change the solution), you can just find the longest word in your alphabet, say $N$, and all the possible letters in a word, which usually are less than $35$, and create a state which is $N\times25$, add an additional $30$ dimensional vector to represent the already proposed letters, and a $10$ dimensional vector for the remaining lives, and use a NN to map it to a policy using RL with any Actor critic method, like A2C, PPO, TRPO, ACER, Rainbow and so on

Since you have a fixed size input ($N+35+30+10$) you can just use a FFNN with like 3/4 layers with an output-size of $30$ and you are good to go, and the architecture becomes close to irrelevant (you might still want to find the optimal number of layers and neurons, as in RL it has been shown that it's a very important aspect)

Answer 3

You can train a character-level masked language model. Like BERT, but with the following traits:

• The token vocabulary of the model would be the characters that are allowed in the words (e.g. lowercase Latin script letters) plus special tokens like [MASK].
• The input sequence would be a sequence of characters forming a word. Some characters would be replaced by a special token [MASK].
• The expected output would be the same as the input sequence but without any masked tokens.
• The loss would be the categorical cross-entropy between the actual model output and the expected output.